第十七讲运筹学模型——线性规划基础模型

yunjiang · 发表于 2004-7-22 10:19:27

（一）从营养配餐问题谈起
　　问题分析与模型建立
　　医院为病人配制营养餐，要求每餐中含有铁不低于50单位，蛋白质不低于40单位，钙不低于42单位。假设仅有两种食品A和B可供配餐，相关数据见表4-0。试问，如何购买两种食品进行搭配，才能即使病人所需营养达到需求，又使总花费最低？
　　　　　<IMG src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image042.gif">

yunjiang · 发表于 2004-7-22 10:19:46

设购买食品A和B依次为x1和x2（kg），则有
　　营养最低要求满足：
　　10x1+5x2≥50 （铁含量）
　　5x1+8x2≥40 （蛋白质含量）
　　6x1+5x2≥42 （钙含量）
　　总花费数记为Z，则有数学模型
　　　　　　　 <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image003.gif"> 
　　　　　 s．t．<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image007.gif"> 
　　其中的x1,x2称为问题的决策变量，minz表示求这样的x1、x2取值，使函数z取最小值。由于它是人们要达到的目标，也称之为目标函数。最低营养要求条件组合在一起，以s·t·表示，它是对目标函数取最小值的一组限制条件，通常称之为约束条件组，s·t·是英文subject to…的缩写。
　　像上述数学模型这样，具有关于决策变量的线性函数作为目标函数并求其最值，同时伴有关于决策变量的线性不等式（也可以是线性等式）的约束条件这类数学模型，我们称之为线性规划问题，其理论已成系统，解法完善，应用面非常广泛。这里只能简介其基本模型，并介绍其图解法。

yunjiang · 发表于 2004-7-22 10:20:00

模型求解
　　这里采用一种几何的方法——图解法来求解。应该注意的是，图解法只适合于具有两个决策变量情形，对于决策变量多于两个的情形就只能借助于文字教材附录介绍的单纯形解法。现就本例说明图解法的具体作法及相关概念。
　　首先以x1,x2为坐标轴，建立平面直角坐标系（如图4-1），由于x1,x2均非负，故只画出了第一象限。
　　其次，将其余约束条件几何化。条件（4.1）表示的是一个半平面，先画出直线10x1+5x2=50,因为10x1+5x2≥50，故直线（4.1）的上方区域即条件（4.1）所满足的x1,x2的取值范围；同理将条件（4.2）、（4.3）也几何化，并注意到几个条件要同时满足，便求得一个以顶点A、B、C、D为顶点的右上方无界的五边形区域 <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image009.gif"> ABCD <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image011.gif"> 。这个区域内的任一点（x1,x2）都是一个可行性配餐方案，在线性规划中被称为可行解，可行解的全体集合你为可行域 。我们的目标便是从这无数多个配餐方案中寻求一个使目标函数达到最小值的可行性方案，称之为最优解。
　　最后，为了求出最优解，将目标函数也进行几何化，有 <

>　　 <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image013.jpg"> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image015.jpg"> <

>　　　　　　　图4—1 　　　　　　图4—2

yunjiang · 发表于 2004-7-22 10:20:25

<OBJECT codeBase=http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=6,0,29,0 height=200 width=300 classid=clsid

27CDB6E-AE6D-11cf-96B8-444553540000><

ARAM><

ARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM> <embed src="../images/flash/table_4_1.swf" quality="high" pluginspage="http://www.macromedia.com/go/getflashplayer" type="application/x-shockwave-flash" width="400" height="300"></embed></OBJECT>

yunjiang · 发表于 2004-7-22 10:21:27

<

> 　　　　　　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image017.gif">
　　称为目标函数直线族，因为其中的Z作为参数出现。易见，随着Z的逐渐增大，目标函数直线（4.4）向右上方平行移动。也就是说，随着目标函数直线的逐渐往右上方平移，Z的值越来越大，反之，Z的值越来越小（如图4-2）。又原问题是求函数Z的最小值，故应令目标函数直线尽可能往左下方平移。但这种平移是有限制的，即点（x1,x2）必须在可行域内。于是两者的结合便可确定本例的最优解。
　　注意，目标函数直线往左下方平移过程只有两个结果：一个是与可行域的某个顶点相切，另一个是与可行域的某个边界线段相切。当前者实现时，意味着原问题有唯一一组最优解，当后者实现时，由于该线段上每个点都给出最优解，原问题将有无数多组最优解。当然这些解对应的目标函数值是一样的。怎样去判断呢？这只需将目标函数直线的斜率k0与边界所在直线的斜率k <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image019.gif"> 进行比较即可：当存在kj=k0时，则问题有无数多组解，第j条直线所在边界线段上所有点均为最优解；若对于任意的j，k0≠kj时，问题便只有一组解。本例属于后一情形，故仅有一组解。
　　不仅如此，通过上述斜率关系分析可知目标函数直线与直线（4.1）和直线（4.3）的交点（顶点C）相切，即直线（4.1）与直线（4.3）的交点即最优解点。于是问题就变成了求解方程组
　　　　　　　　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image021.gif"> 
　　易解得x1=2,x2=6为最优解，通常记作向量形式<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image025.gif"> 
　　对应的目标函数值称为最优值而记作 Z*=26

yunjiang · 发表于 2004-7-22 10:21:41

模型分析、检验与推广
　　（1）从上述分析可见，线性规划问题若有最优解，则最优解或最优解之一必定可在其可行域的顶点处达到。由此可知，要求线性规划问题的最优解，只需在其可行域的顶点中寻找，而可行域的顶点是有限的，这就使线性规划的求解变得简单化了。
　　（2）假如本题的目标函数不是求最小而是求最大值，会出现什么结果？请读者思考。
　　（3）本题最后定解时，只用了直线（4.1）与直线（4.3），而直线（4.2）来用上，这件事说明了什么？请读者从实际问题背景给以解释。
　　（4）实际上，每日三餐都要讲究营养，并且三餐花样不同，则须在几种不同食品中选取几种不同食品组合，这更符合实际要求。
　　（5）对于某些特殊人物群体，还要附加一些其它营养限制。比如某些病人对某种营养的要求不仅要求最低需求，还要有最高限量。这只须在相应的约束条件上加以上限条件即可。例如本例中，按最优解，第二种营养成份含量超出最低需求18个单位，现按医嘱加以限制条件<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image027.gif">，其它不变，请读者求出新最优解。

yunjiang · 发表于 2004-7-22 10:21:56

（二）为下岗工人当参谋 
　　例1 有一技之长的老吴
　　问题提出与模型假设
　　工人老吴下岗后，打算利用自己的一技之长生产两种产品A、B出售，而手头只有12000万积蓄。为了充分发挥这点资金的作用，找到了应用数学系的一位教师，请他帮忙。经交谈，有以下数据被确定：
　　①工艺数据：生产每单位产品A需要用到三种原料Ⅰ、Ⅱ、Ⅲ依次为2，4，6个单位，生产单位产品B的用量则依次为1，3，4个单位。
　　②成本与利润数据：根据市场原料价位，生产每单位产品的原料费，运销等杂支等，确定单位产品A、B的利润约为500元、350元。
　　③总资金12000元按原料需求比，分配初步确定为：购买三种原料依次为300、600和810个单位，所余资金留作机动。
　　依据上述数据，希望给出一个生产方案，使总利润达到最大。

yunjiang · 发表于 2004-7-22 10:22:11

模型建立与求解
　　设生产A、B两种产品分别为x1和x2单位，有利润函数
　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image029.gif"> 
　　又由工艺数据及原料投入量，有
　　原料Ⅰ限制： <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image031.gif"> 
　　原料Ⅱ限制： <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image033.gif"> 
　　原料Ⅲ限制： <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image035.gif"> 
　　以及x1,x2≥0，便得到 <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image037.gif"> 
　　　　　 <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image039.gif"> 
　　使用图解法，很容易得到其最优解为X*=（15，180）T，而最优值为　Z*=7。05万。

yunjiang · 发表于 2004-7-22 10:22:24

模型分析、检验与推广
　　（1）实际问题中,还可以提出特殊的约束条件,如某种产品AK必须完成一定数量aK,则应有xK≥ak;又如产品Al的生产量不得超过限量al,则相当于增加约束条件0≤xl≤al。
　　（2）若视bi为第i种设备的最大加工能力，则aij便被解释为产品Aj需在设备Bi上加工的时间。又若出现x1+x2≤10，则可视为产品A1，A2的总产量在市场上的最大占有份额为10个单位，等等。可见，上述模型可以有较宽的适用面。
　　（3）就来例来说，我们还可以咨询三种资源的利用率如何，尚有无潜力可挖掘等问题。事实上，只要将最优解 <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_17/htm/sxjm17.files/image041.gif"> 代入原约束条件中即可见，x*使约束条件（4.5）成为严格不等式。这说明资源工尚有90个单位未被利用，利用率仅为70%，这自然是一种浪费；又将x*代入约束条件（4.6）和（4.7），两约束条件均成为严格等式，这说明资源Ⅱ和Ⅲ的进货量被完全充分地利用了。换句话说，资源Ⅱ和Ⅲ按优化机制完全被利用转化为价值。那么这时很容易想象，再增加一些资源Ⅱ和Ⅲ的使用量，这个优化机制是否还能进一步消化这些新增资源量而转化为价值呢？也就是说，这些资源是否尚有潜力可挖？有关这方面知识可参阅文字教材附录，这里不再赘述。

duanshumo · 发表于 2004-7-24 00:32:19

谢谢你的帖子

		自动登录	找回密码
密码			注-册-帐-号

第十七讲 运筹学模型——线性规划基础模型

第十七讲运筹学模型——线性规划基础模型