运筹学第二章线性规划的图解法

1、Chapter 1 线性规划线性规划Linear Programming Page 1 2022年5月9日星期一1【例例1.1】最优生产计划问题。最优生产计划问题。某企业在计划期内计划生产甲、某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备乙、丙三种产品。这些产品分别需要要在设备A、B上加工，需上加工，需要消耗材料要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加，按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表工及所需要的资源如表1.1所示。已知在计划期内设备的加工能所示。已知在计划期内设备的加工能力各为力各为200台时，可供材料分别为台时，可供材料分别为

2、360、300公斤；每生产一件甲、公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为乙、丙三种产品，企业可获得利润分别为40、30、50元，假定元，假定市场需求无限制。市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？利润收入最大？问题问题举例举例一一、线性规划、线性规划Chapter 1 线性规划线性规划Linear Programming Page 2 2022年5月9日星期一2 产品产品 资源资源 甲甲 乙乙 丙丙现有资源现有资源设备设备A 3 1 2 200设备设备B 2 2 4 200材料材料C 4

3、 5 1 360材料材料D 2 3 5 300利润（元利润（元/件）件） 40 30 50表表1.1 产品资源消耗产品资源消耗Chapter 1 线性规划线性规划Linear Programming Page 3 2022年5月9日星期一3321503040maxxxxZ0003005323605420042220023321321321321321xxxxxxxxxxxxxxx，【解解】设设x1、x2、x3 分别为甲、乙、丙三种产品的产量数学模型分别为甲、乙、丙三种产品的产量数学模型为：为： 产品产品 资源资源 甲甲 乙乙 丙丙现有资现有资源源设备设备A 3 1 2 200设备设备B 2 2

4、 4 200材料材料C 4 5 1 360材料材料D 2 3 5 300利润（元利润（元/件）件） 40 30 50最优解最优解X=(50,30,10);Z=3400Chapter 1 线性规划线性规划Linear Programming Page 4 2.2 二维问题的图解法二维问题的图解法 Graphical Method1212122401.5300,0 xxxxxx 2143maxxxZChapter 1 线性规划线性规划Linear Programming Page 5 2022年5月9日星期一51111221211222212( ,)( ,)0,0a xa xba xa xbxx

5、1122max(min) Zc xc x二维线性规划二维线性规划(目标函数目标函数)(约束条件约束条件)具有两个变量的最优化问题有明显的几何意义，具有两个变量的最优化问题有明显的几何意义，往往可以用图解法获得最优解往往可以用图解法获得最优解Chapter 1 线性规划线性规划Linear Programming Page 6 2022年5月9日星期一6可行点可行点( (解解) )：满足所有约束条件的点：满足所有约束条件的点 可行域可行域：可行点组成的集合：可行点组成的集合1111221211222212( ,)( ,)0,0a xa xba xa xbxx 1122max(min) Zc xc

6、 x(目标函数目标函数)(约束条件约束条件)Chapter 1 线性规划线性规划Linear Programming Page 7 2022年5月9日星期一712326xx 1x2xo12326xx12326xxChapter 1 线性规划线性规划Linear Programming Page 8 2022年5月9日星期一81232xxk 0k 6k 12k (3,2)1x2xo直线沿着矢量直线沿着矢量( (梯度梯度) )方向移方向移动动,k,k值增大；值增大；反之反之k k值减小。值减小。矢量矢量(梯度梯度)方向方向Chapter 1 线性规划线性规划Linear Programming P

7、age 9 2022年5月9日星期一9 线性规划：线性规划：图解法的步骤图解法的步骤：1.1.求可行解集合。求可行解集合。分别求出满足每个约束包括变量非分别求出满足每个约束包括变量非 负要求负要求的区域，其交集就是可行解集合，或称为的区域，其交集就是可行解集合，或称为可行域可行域；2.绘制目标函数图形。绘制目标函数图形。先过原点作一条矢量指向点（先过原点作一条矢量指向点（c1,c2)，矢量的方向就是目，矢量的方向就是目标函数标函数增加增加的方向，称为的方向，称为梯度方向梯度方向，再作一条与矢量垂直的，再作一条与矢量垂直的直线，这条直线就是目标函数图形；直线，这条直线就是目标函数图形；3.求最优

8、解。求最优解。依据目标函数求最大或最小移动目标函数直线，依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是直线与可行域相交的点对应的坐标就是最优解。最优解。2.2 图解法图解法The Graphical Method1122Zc xc x 目目标标函函数数Chapter 1 线性规划线性规划Linear Programming Page 10 2022年5月9日星期一10一般地，将目标函数直线放在可行域中一般地，将目标函数直线放在可行域中求最大值时直线沿着求最大值时直线沿着矢量矢量(梯度梯度)方向移动方向移动 求最小值时沿着矢量求最小值时沿着矢量(梯度梯度)的反方向移

9、动的反方向移动Chapter 1 线性规划线性规划Linear Programming Page 11 2022年5月9日星期一11x1x2O1020304010203040(3,4)(15,10)最优解最优解 X = (15,10)最优值最优值 Z = 8540221xx305 . 121xx1212122401.5300,0 xxxxxx 例例3.112max34Zxx 2.2 图解法图解法The Graphical MethodChapter 1 线性规划线性规划Linear Programming Page 12 2022年5月9日星期一12246x1x2246最优解最优解 X = (

10、 3, 1 )最优值最优值 Z = 5(3,1)121212123643600 xxxxxxxx 、min Z = x1+2x2例例3.2(1,2)3 图解法图解法The Graphical MethodChapter 1 线性规划线性规划Linear Programming Page 13 2022年5月9日星期一13246x1x2246X（2）（3,1）X（1）（1,3）(5,5)121212123643600 xxxxxxxx 、min Z=5 x1+5 x2例例3.3有无穷多个最优解有无穷多个最优解即具有多重解即具有多重解,通解为通解为 01 ,)1 ()2() 1 (XXX 当当=0

11、.5时时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 3 图解法图解法The Graphical MethodChapter 1 线性规划线性规划Linear Programming Page 14 2022年5月9日星期一14246x1x2246(1,2)121212123643600 xxxxxxxx 、无界解无界解(无最优解无最优解)max Z=x1+2x2例例3.43 图解法图解法The Graphical MethodChapter 1 线性规划线性规划Linear Programming Page 15 2022年5月9日星期一15x1x2O1020304010

12、2030405050121212122401.530500,0 xxxxxxxx 无可行解无可行解即无最优解即无最优解max Z=10 x1+4x2例例3.53 图解法图解法The Graphical MethodChapter 1 线性规划线性规划Linear Programming Page 16 2022年5月9日星期一16由以上例题可知，线性规划的解有由以上例题可知，线性规划的解有4 4种形式：种形式：1.有唯一最优解有唯一最优解( (例例3.13.1，例，例3.2)3.2)2.有多重解有多重解( (例例3.3)3.3)3.有无界解有无界解( (例例3.4)3.4)4.无可行解无可行解

13、( (例例3.5)3.5)1 1、2 2情形为有最优解情形为有最优解3 3、4 4情形为无最优解情形为无最优解2.2 图解法图解法The Graphical MethodChapter 1 线性规划线性规划Linear Programming Page 17 线性规划问题的一般模型 一般地，假设线性规划数学模型中有m个约束，有n个决策变量xj， j=1,2,n。 目标函数中变量的系数用cj表示，cj称为价值系数。 约束条件的变量系数用aij表示，aij称为工艺系数。 约束条件右端的常数用bi表示，i=1,2,m，bi称为资源限量。Chapter 1 线性规划线性规划Linear Program

14、ming Page 18 2.1 线性规划的标准型线性规划的标准型Standard form of LPChapter 1 线性规划线性规划Linear Programming Page 19 2022年5月9日星期一1912312312312328(1)3(2)325(3)00 xxxxxxxxxxxx 、 无符号要求3213maxxxxZ线性规划问题的模型线性规划问题的模型Chapter 1 线性规划线性规划Linear Programming Page 20 2022年5月9日星期一201 1221111221121 1222221 122max(min)(, )(, )(, )0,1,

15、2,nnnnnnmmmnnmjZc xc xc xa xa xa xba xa xa xba xaxaxbxjn 或或或线性规划问题的模型线性规划问题的模型Chapter 1 线性规划线性规划Linear Programming Page 21 2022年5月9日星期一21 在用单纯法求解线性规划问题时，为了讨论问题在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。方便，需将线性规划模型化为统一的标准形式。1.3 线性规划的标准型线性规划的标准型Standard form of LP线性规划问题的标准型为线性规划问题的标准型为:1目标函数求目标函数求最大值最大

16、值;2约束条件都为等式方程约束条件都为等式方程;3变量变量 xj 非负非负;4常数常数 bi 非负非负.Chapter 1 线性规划线性规划Linear Programming Page 22 2022年5月9日星期一22mibnjxbxaxaxabxaxaxabxaxaxaijmnmnmmnnnn,2, 1,0,2, 1,02211222222111212111max Z=c1 x1+c2 x2+cn xn 1.3 线性规划的标准型线性规划的标准型Standard form of LP线性规划问题的标准型为线性规划问题的标准型为: :Chapter 1 线性规划线性规划Linear Prog

17、ramming Page 23 2022年5月9日星期一231212121212max342403303320,0Zxxxxxxxxx x1231231231228332500 xxxxxxxxxxx 、3213maxxxxZChapter 1 线性规划线性规划Linear Programming Page 24 2022年5月9日星期一2412121212min34240330,0Zxxxxxxxx Chapter 1 线性规划线性规划Linear Programming Page 25 2022年5月9日星期一250,30340243min21212121xxxxxxxxZ【例例1】 将下

18、列线性规划化为标准型将下列线性规划化为标准型 Chapter 1 线性规划线性规划Linear Programming Page 26 2022年5月9日星期一2612min34Zxx 12max34Zxx 0 xyZ = f(x)( )zf x 目标函数求最大值目标函数求最大值？zz Chapter 1 线性规划线性规划Linear Programming Page 27 2022年5月9日星期一27【解解】化为标准型化为标准型341212121234m ax34240330,0Zxxxxxxxxxxxx0,30340243min21212121xxxxxxxxZ则标准型为则标准型为:12m

19、ax34Zxx 加入松驰变量加入松驰变量 x3123240 xxx124330 xxx加入松驰变量加入松驰变量 x4Chapter 1 线性规划线性规划Linear Programming Page 28 2022年5月9日星期一28【例例2】将下列线性规划化为标准型将下列线性规划化为标准型 【解解】（）因为（）因为x3无符号要求无符号要求 ，即，即x3取正值也取正值也可取负值，标准型中要求变量非负，所以令可取负值，标准型中要求变量非负，所以令 0,33333 xxxxx其中1.3 线性规划的标准型线性规划的标准型Standard form of LP1231231231228(1)3(2)3

20、25(3)00 xxxxxxxxxxx 、123min3ZxxxChapter 1 线性规划线性规划Linear Programming Page 29 2022年5月9日星期一29 (3)第二个约束条件是第二个约束条件是号，在号，在号号 左端减去剩余变量左端减去剩余变量(Surplus variable)x5，x50。也称松驰变量。也称松驰变量123min3Zxxx 12312312312328(1)3(2)325(3)00 xxxxxxxxxxxx 、无符号要求、无符号要求1.3 线性规划的标准型线性规划的标准型Standard form of LP(2) 第一个约束条件是第一个约束条件是

21、号，在号，在左端左端加入松驰变量加入松驰变量 (slack variable) x4，x40,化为等式；化为等式；341228xxxx12353xxxxChapter 1 线性规划线性规划Linear Programming Page 30 2022年5月9日星期一30(4)第三个约束条件是第三个约束条件是号且常数项为负数号且常数项为负数.2613325xxxx 523321xxx123min3Zxxx 12312312312328(1)3(2)325(3)00 xxxxxxxxxxxx 、无符号要求、无符号要求加入松驰变量加入松驰变量x6同时两边乘以同时两边乘以1Chapter 1 线性规划

22、线性规划Linear Programming Page 31 2022年5月9日星期一31（5）目标函数是）目标函数是最小值最小值，为了化为求，为了化为求最大值最大值，令，令Z= - Z,得到得到 maxZ= - minZ，即当，即当Z达到达到最大值最大值时时, Z达到达到最小值最小值，反之亦，反之亦然。然。 3213minxxxZ无符号要求、32132132132100)3(523)2(3) 1 (82xxxxxxxxxxxx123max3Zxxx Chapter 1 线性规划线性规划Linear Programming Page 32 2022年5月9日星期一321.3 线性规划的标准型线

23、性规划的标准型Standard form of LP综合起来得到下列标准型综合起来得到下列标准型 4563333331212121233456(28332)50 xxxxxxxxxxxxxxxxxxxxxx 、 、 、 、 、 、 、 、 、 、 、12333max3Zxxxx 123min3Zxxx 12312312312328(1)3(2)325(3)00 xxxxxxxxxxxx 、无符号要求、无符号要求Chapter 1 线性规划线性规划Linear Programming Page 33 2022年5月9日星期一33注：化标准型的方法注：化标准型的方法1、目标极小化极大：、目标极小化极大：min( f )= - max ( - f )2、不等