管理运筹学I讲义.doc

《管理运筹学I讲义.doc》由会员分享，可在线阅读，更多相关《管理运筹学I讲义.doc（31页珍藏版）》请在三一文库上搜索。

1、第二章线性规划（LP）2.1线性规划数学模型的建立LP问题提出：苏联：康德洛维奇 1939一、线性规划数学模型的三要素：1.决策变量(decision variable)：决策问题待定的量值。用字母（例如X1,X2,Xn）来表示可控制的因素。每一组决策变量的实际值就表示一个具体方案。2.目标函数（objective function）：MaxZ=CX 或 MinZ=CX；(衡量决策优劣的准则)特点：（1）单一目标；（2）关于决策变量的线性函数。（定义：课本P20）3.约束条件(constraint conditions)：s.t. (subject to) 受制于约束；AX(，=)b特点：若干

2、关于决策变量的线性函数。二、LP数学模型的一般形式（1）繁写形式目标函数：Max （Min）z = c1 x1 + c2 x2 + + cn xn 约束条件： a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 s.t. am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0 （2）向量形式 目标函数：Max （Min） z = CX (，=)bXj 0 (j=1,2, ,n)其中，C=(c1 , c2 , , cn )(价值向量) X= (x1 , x2

3、, , xn )T(决策变量向量) b=(b1 , b2 , , bm )T (限定向量) pj= (a1j ， a2j amj ) T (约束条件系数列向量)注：矩阵相乘条件：左列=右行(3)矩阵形式目标函数：Max （Min） z = CX约束条件： AX （ =, ）b X 0其中，C=(c1 , c2 , , cn )(价值向量) X= (x1 , x2 , , xn )T(决策变量向量) b=(b1 , b2 , , bm )T (限定向量、资源向量) a11 a12 a1n a21 a22 a2n (系数矩阵) A= am1 am2 amn 三、建模的一般步骤 前提假设：假设模型中

4、有n个决策变量，m个约束条件。1.分析问题,设出决策变量 根据实际问题定义决策变量（ x1 ，x2 ， ，xn ）， 2.根据所提问题列出目标函数 目标函数一般表达式： MaxZ （或 MinZ）= c1 x1 + c2 x2 + + cn xn 注：目标函数是一个用决策变量表示的线性函数，其有两种基本形式：最大化目标或最小化目标。 本例中，目标函数为： 3.根据已知条件列出所有约束条件例1.生产计划安排问题某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，单位产品的获利，如下表所示：问题：计划期内工厂应分别生产多少单位、产品才能使工厂

5、获利最多？ 解：设工厂在计划期内应安排生产产品X1件, 产品X2件。 Max z = 50 x1 + 100 x2 x1 + x2 300 s.t. 2 x1 + x2 400 x2 250 x1 , x2 0 练习：请写出例1数学模型中的价值向量，决策变量向量，限定向量及约束条件系数矩阵四、LP数学模型的特点1.单一目标2. 双线性（1）目标函数是关于决策变量的线性函数；（2）所有约束条件是关于决策变量的线性函数 建模例题讲解：见ppt投资问题例某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年

6、到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。据测定每万元每次投资的风险指数如下表：问：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？解： 1）确定决策变量：连续投资问题。 设 xij ( i = 15，j = 14)表示第 i

7、年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量： 1 2 3 4 5 A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24a) MaxZ = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； s.t. x51 = 1.1x41+ 1.25x32； xi2 30 ( i

8、=1、2、3、4 )， x33 80， x24 100 xij 0( i = 1、2、3、4、5；j = 1、2、3、4） b)MinZ = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24 x11+ x12 = 200 x21 + x22+ x24 = 1.1x11 x31 + x32+ x33 = 1.1x21+ 1.25x12 x41 + x42 = 1.1x31+ 1.25x22 s.t. x51 = 1.1x41+ 1.25x32 xi2 30 ( i =1、2、3、4 ) x33 80，x24 100 1.1x51 + 1.2

9、5x42+ 1.4x33+ 1.55x24 330 xij 0( i = 1、2、3、4、5；j = 1、2、3、4）2.2线性规划数学模型的求解一图解法（一）图解法的适用条件 有且仅有两个决策变量X1，X2。（二）图解法的基本思路1.基本概念对于LP数学模型 : Max （Min） z = CX (1) AX （ =, ）b (2) X 0 (3)（1）可行解 满足约束条件(2)、（3）式的解称为LP问题的可行解。 （2）可行域 由可行解构成的区域称为可行域。 （3）最优解 满足（1）式的可行解称为LP问题的最优解。注：LP问题求解的最终目标：求出最优解(主要包括决策变量最优值和目标函数最优

10、值)2.基本思路 先求出可行解（找出可行域），再在可行解的基础上求出最优解。(三)、图解法的基本步骤例2 用图解法求解下列线性规划问题Max z = 50 x1 + 100 x2 x1 + x2 300 2 x1 + x2 400 s.t. x2 250 x1 , x2 0第一步：由所有约束条件作图求出可行域。 可行域：所有约束条件围成的公共区域。 本例中，可行域为ABCDE第二步：作一条目标函数等值线，判断目标函数等值线平移的方向。具体方法：方法一：将Z看作参数，将目标函数写成斜截式（y=kx+b）。本例中，目标函数写为：X2=可见，随着Z值的增大，截距增加，故目标函数等值线平移的方向是右上

11、方。方法二：将Z代入具体的值，画出目标函数等值线，判断其平移方向。x1x2z=20000=50x1+100x2 z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE第三步：平移目标函数等值线，定位于最优解点，联立方程求解最优解点的值。 （PPT20） 本例中，最优点为B点。其坐标为（50，100），故此LP的最优解为：X=(50,100)T，Z*max=5050+100250=27500(元)在此最优方案下的资源消耗情况：设备台时：150+1250=300（台时）原料A：250+1250=350（公斤）原料B：050+1250=250（

12、公斤）结论：设备台时和原料B全部消耗，原料A剩余：400-350=50（公斤）(四) 图解法解的情况1.唯一最优解 LP问题的最优解在可行域的某一个顶点上取得，此时，LP只有唯一的一个最优解，只需求出顶点坐标即可。 举例：见例2。2.无穷多最优解 LP问题的目标函数等值线斜率与某条约束直线斜率相等，平移目标函数等值线，会与此约束直线重合，此时，可行域的某条边（即重合线段）上所有的点都是最优点。举例：例3 用图解法求解下列线性规划问题(PPT24) Max z = 50 x1 + 50x2 x1 + x2 300 2x1 + x2 400 s.t. x2 250 x1 , x2 03.无可行解(

13、PPT27) LP问题的可行域不存在（可行域为），此时，称此LP问题无可行解。举例：例4 用图解法求解下列线性规划问题 Max z = 50 x1 + 100x2 x1 + x2 300 2 x1 + x2 400 s.t. x2 250 4 x1 + 3x2 1200 x1 , x2 0如图所示，可行域为，故此LP问题无可行解。注： LP问题无可行解通常说明数学模型中存在互相矛盾的约束条件。4.无界解（PPT29） 可行域无界，目标函数等值线平移的方向恰恰为无界方向，此时，称此LP问题为无界解。举例：例5 用图解法求解下列线性规划问题 Max z = x1 + x2 x1 - x2 1 s.

14、t. -3x1 + 2x2 6 x1 , x2 0注： LP问题无界解通常说明数学模型中忽略了一些必要的约束条件。思考问题:可行域无界，LP一定为无界解吗？ 答案：不一定。只有在目标函数等值线平移的方向与可行域无界的方向一致时，才为无界解。例如：例6 用图解法求解下列线性规划问题 Min z = x1 + x2 x1 - x2 1 s.t. -3x1 + 2x2 6 x1 , x2 0 此LP问题有唯一最优解，最优解为:X=(0,0)T， Z*max=0+0=0.总结: 图解法优缺点。 优点:操作简便，直观; 缺点:是一种几何求解方法，当决策变量超过两个时，图解法失效。此时，需要寻找另外一种解

15、法：代数解法（即单纯形法）。重要定理:1.若可行域中，在两个顶点上达到最优解，则这两个顶点连线上任一点也为最优解，即此LP有无穷多最优解。2.若可行域存在，则可行域为凸多边形。 凸多边形：多边形上任何两点的连线上所有的点仍在此多边形上，这样的多边形称之为凸多边形。3.若LP存在最优解，则最优解一定可在可行域凸多边形的顶点上取得。（五）图解法的灵敏度分析1、灵敏度分析(1)灵敏度分析的含义 建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci , aij , bj 变化时，对最优解产生的影响。(2)为什么进行灵敏度分析 LP数学模型中的一个或多个参数（系数）ci , aij ,

16、bj 值一般都是估计值或预测值，因此，这些值会随时发生变化。(3)灵敏度分析的具体工作 找出ci , aij , bj值的一个变化范围，在此范围内变化，原LP问题最优解保持不变。2、目标函数中的系数 ci 的灵敏度分析讨论:Ci变化对LP最优解的影响。目标函数等值线斜率 k=- (c1 / c2 ) ：（1）与kAB相等：无穷多最优解；（2）介于kAB和kBC之间：最优点在B点，原最优解不变；（3）与kBC相等：无穷多最优解；（4）介于kBC 和kCD之间：最优点在C点；（5）与kCD相等：无穷多最优解；（6）介于 kCD和900直线之间：最优点在D点；结论：综上所述，目标函数等值线斜率在-1

17、，0之间，即当 -1 - (c1 / c2 ) 0时，原最优解保持不变。情况一： c1 变，c2 不变； 假设产品的利润100元不变，即 c2 = 100，则当0 c1 100时，原最优解仍是最优解。 情况二： c2 变，c1 不变； 假设产品的利润 50 元不变，即 c1 = 50 ，则当50 c2 + 时，原最优解仍是最优解。 情况三： c1 ，c2都变； 假设产品、的利润分别为60元、55元，则 - 2 - (60 / 55) - 1 那么，最优解为x1 + x2 =300和2 x1 + x2 =400 的交点： x1 = 100，x2 = 200 （C点）。3、约束条件右端常数项 bj

18、 的灵敏度分析 当约束条件右端常数项 bj 变化时，线性规划的可行域发生变化，可能引起最优解的变化。 （1）b1的值变化 假设 b1变化为310，这时可行域扩大，最优解为：x2 = 250 和 x1 + x2 = 310的交点 x1 = 60，x2 = 250 。 此时，增加的利润 z =变化后的总利润 - 变化前的总利润 = (5060+ 100250) - (50 50+100 250) = 500 设备的对偶价格= z/ b=500 /10 = 50 说明在每增加（减少）1个台时的设备能力就可增加（减少）50元利润。 对偶价格：约束条件常数项增加一个单位而使目标函数最优值得到改进的数量，

19、称之为该约束条件的对偶价格。 课堂练习:试求出例1中原材料A和原材料B的对偶价格.（2） b2的值变化 假设原料 A 增加10 千克时，即 b2变化为410，这时可行域扩大，但最优解仍为 x2 = 250 和 x1 + x2 = 300 的交点 x1 = 50，x2 = 250 。此变化对总利润无影响，该约束条件的对偶价格为 0 。 解释：原最优解没有把原料 A 用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。（3） b3的值变化 b3的值变为300，则最优解为： x1 = 0，x2 = 300 原料 B对偶价格为： z/ b=2500/ 50 =50。总结：1.某一约束

20、条件的对偶价格仅在某一范围内是有效的。2.当约束条件常数项bj增加一个单位时，有：如果对偶价格大于零，则其目标函数最优值得到改进，即对于极大化问题，目标函数最优值增加；对于极小化问题，目标函数最优值减小。如果对偶价格小于零，则其目标函数最优值会劣化，即对于极大化问题，目标函数最优值减小；对于极小化问题，目标函数最优值增加。如果对偶价格等于零，则其目标函数最优值不变。（六）“管理运筹学”软件的输入及输出信息分析一、输入信息注意：1.输入系数须为整数或小数，不能为分数，分数需化为小数。2.合并同类项。二、输出信息分析 本题中目标函数的最优值是27500，x1=50, x2=250。 相差值表示相应

21、的决策变量的目标系数需要改进的数量，使得决策变量为正值，当决策变量已为正数时，相差数为零。 松弛/剩余变量的数值表示还有多少资源没有被使用。如果为零，则表示与之相对应的资源已经全部用上。 对偶价格表示其对应的资源每增加一个单位，将增加多少个单位的最优值。 目标函数系数范围表示最优解不变的情况下，目标函数的决策变量系数的变化范围。当前值是指当前的最优解中的系数取值。 常数项范围是指约束条件的右端常量。上限值和下限值是指当约束条件的右端常量在此范围内变化时，与其对应的约束条件的对偶价格不变。当前值是指现在的取值。当有多个系数变化时，需要进一步讨论。 百分之一百法则：对于所有变化的目标函数决策系数（

22、约束条件右边常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过100%时，最优解不变（对偶价格不变 ）。 * 允许增加量 = 上限 - 现在值 c1 的允许增加量为 100 - 50 = 50 b1 的允许增加量为 325 - 300 = 25 * 允许减少量 = 现在值 - 下限 c2 的允许减少量为 100 - 50 = 50 b3 的允许减少量为 250 - 200 = 50 * 允许增加的百分比 = 增加量 / 允许增加量 * 允许减少的百分比 = 减少量 / 允许减少量 例： c1 变为 74 , c2 变为 78, 则 (74 - 50) / 50 + (100 - 7

23、8 ) / 50 = 92%，故最优解不变。 b1 变为 315 , b3 变为 240, 则 (315 - 50) / 25 + (250 - 240 ) / 50 = 80%，故对偶价格不变。在使用百分之一百法则进行灵敏度分析时，要注意：1）当允许增加量（允许减少量）为无穷大时，则对任意增加量（减少量），其允许增加（减少）百分比均看作0；2）百分之一百法则是充分条件，但非必要条件；也就是说超过100%并不一定变化；3）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化的情况。这种情况下，只有重新求解。 注意：1. 当约束条件中的常数项增加一个单位时，最优目标函数值增加的

24、数量称之为影子价格。在求目标函数最大时，当约束条件中的常数项增加一个单位时，目标函数值增加的数量就为改进的数量，所以影子价格等于对偶价格；在求目标函数值最小时，改进的数量就是减少的数量，所以影子价格即为负的对偶价格。2. “管理运筹学”软件可以解决含有100个决策变量及50个约束方程的线性规划问题，可以解决工商管理中大量的问题。如果想要解决更大的线性规划问题，可以使用由芝加哥大学的L.E.Schrage开发的Lindo计算机软件包的微型计算机版本Lindo/PC。二、单纯形法单纯形法的开发：(simplex method)1947年，乔治.丹齐格(George Dantzig)（美国数学家，线

25、性规划之父）单纯形法：是一种代数迭代的方法。（一）单纯形法的基本思路 从可行域中某一个顶点开始，判断此顶点是否是最优点，如不是,则再找另一个使得其目标函数值更优的顶点，（这一过程称之为迭代），再判断此点是否是最优点。重复以上工作，直至找到一个顶点为其最优点，即使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。问题1: 如何寻找初始顶点?问题2: 如何判别所寻找的顶点是否为最优点?（最优性检验方法）问题3: 若所找顶点不是最优点，如何再寻找另一个顶点，即如何迭代?（迭代方法）问题1：求初始顶点(两条约束直线的交点) 求解线性方程组(AX=b) 将初始模型标准化。（二）LP数学模型的

26、标准化1.标准型(矩阵形式)目标函数：MaxZ = CX约束条件：AX=b ，X 0 2.标准型的特点(1)目标函数为极大化(MaxZ = CX) ；(2)所有约束条件均为等式约束(AX=b)；(3)所有决策变量均非负(X0)；(4)约束条件右端常数项均非负(b 0) 3.初始模型的标准化 对于各种非标准形式的初始线性规划数学模型，我们总可以通过以下变换，将其转化为标准形式。(1)极小化目标函数的问题 若目标函数为Minf =CX，则令z-f，则该极小化问题与下面的极大化问题有相同的最优解，即Maxz =-CX。 但必须注意，尽管以上两个问题的决策变量最优值相同，但它们目标函数最优值却相差一个

27、符号，即：Minf -Maxz(2)约束条件不是等式的问题 若约束条件为AXb，此时，应引入一个新的变量Xs（称松弛变量），约束条件变为：AX+ Xs =b。若约束条件为AXb，此时，应引入一个新的变量Xt（称剩余变量），约束条件变为：AX- Xt =b。注：松弛变量和剩余变量统称为附加变量。 数学模型中规定附加变量均为非负决策变量，且其在目标函数中的系数为0。（3）约束条件右端常数项有负值的问题 在标准形式中，要求所有右端常数项必须非负。当某一个右端常数项为负值时，则 该约束条件两端同时乘以-1即可。（4）决策变量为无约束变量（自由变量） 在标准形式中，每一个变量取值必须非负。当某一个变量x

28、k为无约束变量，可以令 xk = xk- xk” 其中，规定xk0，xk”0。 即用两个非负变量之差来表示一个无约束变量，当然xk的符号取决于xk和xk”的大小（5）决策变量为有界变量若xjuj,即xj- uj 0，此时令xj=xj- uj，有 xj= xj+ uj，即在数学模型中用xj+ uj替换xj。 若xj uj,即uj-xj 0，此时令xj=uj-xj，有xj= uj-xj，即在数学模型中用uj-xj替换xj。 4.标准化步骤处理决策变量（自由变量和有界变量） 处理约束条件 处理目标函数例1：将以下线性规划问题转化为标准形式 Minf = 2 x1 -3x2 + 4 x3 3 x1 +

29、 4x2 - 5 x3 6 s.t. 2 x1 + x3 8 x1 + x2 + x3 = 9 x1 0 , x2 0, x3 自由变量解：(1)处理决策变量。令：x4 =-x1, x3= x5 x6 ; (2)处理约束条件。有2个不等式约束，分别引进附加变量x7，x8 ， 第三个约束条件的右端常数项值为负，在等式两边同时乘-1; (3)将目标函数转换成极大化： 令z= -f = -2x1+3x2-4x3 通过以上变换，可以得到以下标准形式的线性规划问题： MaxZ = 3x2 + 2x4 - 4x5 + 4x6 + 0x7 + 0x8 4x2-3x4-5x5 +5x6 + x7 = 6 s.

30、t. -2x4 +x5 x6 -x8= 8 -x2 + x4 -x5 + x6 = 9 xj 0(j=2,4,5,6,7,8)（三）基本概念LP: Max(Min)Z = CX (1) AX=b (2) X 0 (3)其中，A=(aij)mn，一般，mn，且R(A)=m。1.基： 已知A=(aij)mn ，其秩为m(R(A)=m) 。从A中任取m个线性无关的列向量构成的矩阵B，（即B是A中mm阶非奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。注：一个LP问题的基的个数是不唯一的，最多为： 个。2.基向量,非基向量： 基B中的一列pi称为一个基向量。 在A中除了基B之外的一列pj则称

31、之为基B的一个非基向量。注：一个LP有m个基向量， nm个非基向量。3.基变量,非基变量： 与基向量pi相应的变量xi称基变量，基变量有m个。 与非基向量pj相应的变量xj称非基变量，非基变量有nm个。4.基本解,基本可行解,基本最优解 对于一个基B，令所有的非基变量为0，求得满足（2）式的解，称作一个基本解。注：即求解一个m元的线性方程组，由线性代数知识得知，可得到唯一的一组解。 若求得的基本解又满足（3）式，则称此基本解为基本可行解。 若基本可行解又满足（1）式，即使得目标函数达到最优值，则又称此基本可行解为基本最优解。5.可行基，最优基 与基本可行解相对应的基称作可行基；与基本最优解相对

32、应的基称作最优基。注：基本可行解 可行基例2：求出下列LP问题的所有基本解，基本可行解，基本最优解。 MaxZ = 50 x1 + 100 x2 x1 + x2 300 2 x1 + x2 400 s.t. x2 250 x1 , x2 0标准化，得： MaxZ = 50 x1 + 100 x2 + 0x3 + 0x4 + 0x5 x1 + x2 + x3 = 300 2 x1 + x2 + x4= 400 s.t. x2 + x5= 250 xj 0(j=15)其中， 1 1 1 0 0 ,基有 -1=9个。 A= 2 1 0 1 0 0 1 0 0 1重要结论： 1.(定理) LP问题的一

33、个基本可行解对应于可行域的一个顶点。 一个基本可行解 可行域的一个顶点。 2.以单位矩阵Imm做基，其基本解的特点是：所有非基变量xj =0，所有基变量xi =b（标准型中规定b 0 ），故单位矩阵可做可行基。回到单纯形法的思路：寻找初始顶点 寻找一个初始基本可行解 寻找一个初始可行基 构造单位矩阵（Imm）作为初始可行基 （四）初始可行基的构造情况1. 对于约束条件AX b AX + xr =b.情况2.对于约束条件AX = b AX + xs =b情况3.对于约束条件AX b AX - xk =b AX - xk +xt=b注意:人工变量在目标函数中的系数:对于极小化问题,为M(取值很大的

34、正数,也称罚因子);对于极大化问题,为-M.课堂练习：将以下线性规划问题化为标准形式,并构造初始可行基. Minf = 2 x1 -3x2 + 4 x3 3 x1 + 4x2 - 5 x3 6 s.t. 2 x1 + x3 8 x1 + x2 + x3 = -9 x1 0 , x2 0, x3自由变量解：标准化并构造初始可行基，得：MaxZ = 3x2 + 2x4 - 4x5 + 4x6 + 0x7 + 0x8- Mx9- Mx10 4x2-3x4-5x5 +5x6 + x7 = 6 s.t. -2x4 +x5 x6 -x8 + x9 = 8 -x2 + x4 -x5 + x6 + x10 =

35、 9 xj 0(j=2,4,5,6,7,8,9,10) 注:x7 ,x8为附加变量,x9,x10为人工变量（五）最优性检验 例：MaxZ = 50 x1 + 100 x2 x1 + x2 300 2 x1 + x2 400 s.t. x2 250 x1 , x2 0第一步：标准化并构造初始可行基，得： MaxZ = 50 x1 + 100 x2 + 0x3 + 0x4 + 0x5 x1 + x2 + x3 = 300 2 x1 + x2 + x4= 400 s.t. x2 + x5= 250 xj 0(j=15)第二步：只用非基变量来表示目标函数。1.检验数的含义:只用非基变量来表示目标函数后，目标函数中所有决策变量(非基变量) 的系数即为各变量的检验数,一般记为j。基变量的检验数必为零。2.检验数j一般表达式的推导 现从一般数学模型里推导出检验数 的表达式。 可行基为m阶单位矩阵的线性规划模型如下（假设其