线性规划及单纯形法课件

1、先修课：高等数学，基础概率、线性代数先修课：高等数学，基础概率、线性代数特点：系统整体优化；多学科的配合；模型方法的应用特点：系统整体优化；多学科的配合；模型方法的应用规定规定目标目标和和明确明确问题问题收集收集数据数据和和建立建立模型模型求解求解模型模型和和优化优化方案方案检验检验模型模型和和评价评价方案方案方案方案实施实施和和不断不断改进改进解决问题解决问题制定决策制定决策表表1-11-1问题分析：问题分析：（1）问题的目标是什么？）问题的目标是什么？ 合理安排生产，实现利润最大化合理安排生产，实现利润最大化（2）利润与哪些因素有关？）利润与哪些因素有关？ 产量和单位产量的利润产量和单位产

2、量的利润按工艺资料规定，按工艺资料规定，生产每件产品生产每件产品I I需占用各设备分别为需占用各设备分别为2 2、1 1、4 4、0h0h；生产每件产品生产每件产品IIII需占用设备分别为需占用设备分别为2 2、2 2、0 0、4h4h；已知各设备计划期内用于生产两种产品的能力分别为已知各设备计划期内用于生产两种产品的能力分别为1212、8 8、1616、12h12h0,124164821222. .32max2121212121xxxxxxxxtsxxz表表1-21-2分析：分析：问题的目标是什么？问题的目标是什么？ 通过三种煤的组合实现混合煤的价格通过三种煤的组合实现混合煤的价格最低最低问

3、题目标实现的约束条件是什么？问题目标实现的约束条件是什么？ 含硫量和发热量含硫量和发热量0,1025. 003. 005. 001. 017000180002000016000. .767080min321321321321321xxxxxxxxxxxxtsxxxz目标函数目标函数约束条件约束条件表表1-31-3），；，（321j321i0252010152551. .15080100901207012010080minij332313322212312111332331322221312111332331322221312111xxxxxxxxxxxxxxxxxxxtsxxxxxxxxxz0

4、,18231224. .500300max21212121xxxxxxtsxxz0,.,),(.),(.),(. .maxmin21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz）或（nmmnmmnnnccbbbaaaaaaaaamxxx212121222211121121c21价值系数动活资源决策变量决策变量及各类系数之间的对应关系决策变量及各类系数之间的对应关系),.,1(0),.,2 , 1(),(. .maxminj11njxmibxatsxczinjjijnjjj）或（),.,1(0),(P

5、.CXmaxminj1njxbxtsznjjj）或（mmjjjjnnbbbbnjaaaPxxxXccc.);,.,2 , 1( ,.;.;,.,C21212121）（式中：0X),(AX. .CXmaxminbtsz）或（mnmmnnaaaaaaaaa.A212222111211式中：A A为约束方程组（约束为约束方程组（约束条件）的条件）的系数矩阵系数矩阵。),.,1(0),.,2, 1(.maxj11njxmibxatsxczinjjijnjjj),.,1(0),.,2, 1(.maxj11njxmibxatsxczinjjijnjjjnjjjxcz1minnjjjxcz1max0, 0

6、xxxxx，取值无约束，3213213213213210,-63-2-342392.32-minxxxxxxxxxxxxtsxxxz0,63323-4223932. .00332max54 3321 33215 33214 332154 3321xxxxxxxxxxxxxxxxxxxxtsxxxxxxz63323, 422329),0, 0(, 3321 33215 33214 33 333xxxxxxxxxxxxxxxxxxxzz令X4X4为松弛变量为松弛变量X5X5为剩余变量为剩余变量0,24261553. .2max21212121xxxxxxtsxxz0,24261553. .002m

7、ax43214213214321xxxxxxxxxxtsxxxxz无约束43214321432143214321, 0,2232x-1432-24. .5243-minxxxxxxxxxxxxxxxtsxxxxz0,2)(232x-143224-. .00)(5243max 443216 443215 44321 4432165 44321xxxxxxxxxxxxxxxxxxxxxtsxxxxxxxz)0, 0(, 44 444xxxxxzz令）（）（）（）（40,3515216411222. .32max21212121xxxxxxtsxxz）（）（）（）（40,3515216411222.

8、 .32max21212121xxxxxxtsxxzx1x1x2x2Q4Q4Q3Q3Q2Q2Q1Q1）（）（）（）（40,3515216411222. .32max21212121xxxxxxtsxxzx1x1x2x2Q4Q4Q3(3,3)Q3(3,3)Q2 (4,2)Q2 (4,2)Q1Q1从图形中我们看到阴影部从图形中我们看到阴影部分的图形是凸的，以后我分的图形是凸的，以后我们要证明，如果线性规划们要证明，如果线性规划问题存在可行域，则可行问题存在可行域，则可行域一定是一个凸集。域一定是一个凸集。）（）（）（）（40,3515216411222. .32max21212121xxxxxxt

9、sxxz）（）（）（）（40,3515216411222. .32max21212121xxxxxxtsxxzx1x1x2x233212zxxZ=6Z=6）（）（）（）（40,3515216411222. .32max21212121xxxxxxtsxxzx1x1x2x2Q4Q4Q3(3,3)Q3(3,3)Q2 (4,2)Q2 (4,2)Q1Q1）（）（）（）（40,3515216411222. .33max21212121xxxxxxtsxxzx1x1x2x2Q4Q4Q3(3,3)Q3(3,3)Q2 (4,2)Q2 (4,2)Q1Q1）（）（）（）（40,3515216411222. .33

10、max21212121xxxxxxtsxxz0,24-2. .2max2112121xxxxxtsxxzx1x1x2x2如图：此问题有可行域，但为无界解（无最优解）如图：此问题有可行域，但为无界解（无最优解）其原因是由于在建立实际问题的数学模型时遗漏了某些其原因是由于在建立实际问题的数学模型时遗漏了某些必要的资源约束。必要的资源约束。0,4126. .32max21212121xxxxxxtsxxzx1x1x2x2用图解法求解时找不到满足所有约束条件的公共范围，用图解法求解时找不到满足所有约束条件的公共范围，这时此问题无可行解。原因是模型本身有错误，约束条这时此问题无可行解。原因是模型本身有错

11、误，约束条件相互矛盾，应检查修正。件相互矛盾，应检查修正。（a）（b）（c）（d）),.,1(0),.,2 , 1(. .maxzj11njxmibxatsxcinjjijnjjj（a a）（b b）（c c）),.,1(0),.,2 , 1(. .maxzj11njxmibxatsxcinjjijnjjj（a a）（b b）（c c）mnmmnnaaaaaaaaa.212222111211）（mmmmmPPaaaa,.,.B11111B B中的每一个列向量中的每一个列向量P Pj j（j=1,mj=1,m）称为）称为基向量基向量，与基，与基向量向量P Pj j对应的变量对应的变量x xj j

12、称为称为基变量基变量。线性规划中除基变。线性规划中除基变量以外的其他变量称为量以外的其他变量称为非基变量非基变量。),.,2 , 1(. .1mibxatsinjjij基基基向量基向量mnmmnnaaaaaaaaaA112222111211显然，显然，r r ( ( A A ) ) min ( min ( m m , , n n ) ; ) ; r r ( ( A AT T ) = ) = r r ( ( A A ) ) . . 求矩阵求矩阵 A A 的秩，其中的秩，其中.174532321A : :在在 A A 中，容易看出阶子式中，容易看出阶子式,013221而而 A A 的三阶子式只有一

13、个的三阶子式只有一个 , 0|A因此因此. 2)(Ar)5,.,2 , 1(02261035. .-2-4max53214321321jxxxxxxxxxtsxxxzj102610-011-15A610-15B1010-15B2110-05B3261-1B41201-B80211-B71601B60911B51001B9由线性代数知道，基矩阵由线性代数知道，基矩阵B B必为非必为非奇异矩阵，即奇异矩阵，即|B|0|B|0。当矩阵。当矩阵B B的的行列式等于零是就不是基。行列式等于零是就不是基。010-15B2102610-011-15A),.,1(0),.,2 , 1(. .maxzj11nj

14、xmibxatsxcinjjijnjjj（a a）（b b）（c c）对某一特定的基对某一特定的基B B，令非基变量等于零，令非基变量等于零，利用（利用（b b）求解出基变量，）求解出基变量，则这组解成为基则这组解成为基B B的基本解。的基本解。)1 (22112222212111212111nnnnnnnnnnbxaxaxabxaxaxabxaxaxa0det212222111211nnnnnnaaaaaaaaaAnjABxjj, 2, 1,detdet),.,1(0),.,2 , 1(. .maxzj11njxmibxatsxcinjjijnjjj（a a）（b b）（c c）)5,.,2

15、 , 1(02261035. .-2-4max53214321321jxxxxxxxxxtsxxxzj610-15B12610352121xxxxT000152），（)5,.,2 , 1(02261035. .-2-4max53214321321jxxxxxxxxxtsxxxzj21035141xxxT040051-），（010-15B2T)1(000152），（XT)2(040051-），（XT1272100），（X对应的基对应的基B1B1称为可行基称为可行基基本最优解基本最优解基本可行解基本可行解最优解最优解基本解基本解可行解可行解箭尾的解一定是箭头的解，否则不一定成立箭尾的解一定是箭头的

16、解，否则不一定成立)5,.,1(01551641222. .00032max524132154321jxxxxxxxxtsxxxxxzj标准型标准型)5,.,1(01551641222. .00032max524132154321jxxxxxxxxtsxxxxxzj100500100400122AP1P1P2P2P3P3P4P4P5P5矩阵矩阵A A的秩的秩33。所以只要。所以只要找出找出3 3个列向量组成的矩阵个列向量组成的矩阵满秩，这满秩，这3 3个向量就是线性个向量就是线性规划问题的一个基。规划问题的一个基。100500100400122AP1P1P2P2P3P3P4P4P5P5令与基对

17、应的变量为基变量，其余变量为非基变量，令与基对应的变量为基变量，其余变量为非基变量，令非基变量等于零，求解方程组就可以找出基解。令非基变量等于零，求解方程组就可以找出基解。下表中列出本线性规划问题的全部基、基解。下表中列出本线性规划问题的全部基、基解。每生产一件产品每生产一件产品可获利可获利2 2元，每生产一件产品元，每生产一件产品可可获利获利3 3元，问应如何安排计划使该工厂获利最多元，问应如何安排计划使该工厂获利最多? ? 0124164823221212121x ,xxxxx:xxzmax约束条件目标函数) 11 (00032max54321xxxxxz5 , 2 , 10124)21

18、(164825241321jxxxxxxxxj约约束束条条件件100010040004121,54321PPPPPA100,010,001543PPP100010001,543PPPB124)21 (164825241321xxxxxxx)31 (412416282514213xxxxxxx从从(1-2)(1-2)式中可式中可以得到（以得到（1-31-3）) 11 (00032max54321xxxxxz)41 (32021xxz到这里，完成了单纯形法的第一个环节：确定初始基到这里，完成了单纯形法的第一个环节：确定初始基本可行解；然后再确定这个基本可行解是否是最优的，本可行解；然后再确定这个基

19、本可行解是否是最优的，如果不是，则还要继续去寻找最优解！如果不是，则还要继续去寻找最优解！)31 (412416282514213xxxxxxx)41 (32021xxz)51 (041201602825423xxxxx)31 (412416282514213xxxxxxx)31 (412416282514213xxxxxxx )61 (312424161825214123xxxxxxx 713413241612125214513xxxxxxx）（ 8-1432951xxz2143maxxxz0,303402212121xxxxxx43210043maxxxxxz0,3034024321421

20、321xxxxxxxxxx10310112,4321PPPPA1001,43PPB基变量为：基变量为：x3x3，x4x4非基变量为：非基变量为：x1x1，x2x2令非基变量令非基变量x1=x2=0 x1=x2=0，代入约束方程中，代入约束方程中0,3034024321421321xxxxxxxxxx得到：得到：x3=40 x3=40，x4=30 x4=30则初始基本可行解为：则初始基本可行解为：X X（0 0）= =（0 0，0 0，4040，3030）T T基变量的检验数为零基变量的检验数为零40/140/130/330/340/140/130/330/3X2X2希望变成希望变成1 1希望变

21、成希望变成0 0这样，形成的基就是单位矩阵。因此，对增广矩阵进这样，形成的基就是单位矩阵。因此，对增广矩阵进行行初等变换初等变换！ 4 440401010增广矩阵的第增广矩阵的第2 2行中的每个元素都行中的每个元素都3 3 得：如图所示得：如图所示1/31/31 11/31/31010增广矩阵的第增广矩阵的第1 1行行- -第第2 2行行 得：如图所示得：如图所示5/35/3 0 0-1/3-1/33030经过增广矩阵的初等变换后，基变成了单位矩阵经过增广矩阵的初等变换后，基变成了单位矩阵40401010确定基可行解确定基可行解X X（1 1）= =？令非基变量令非基变量x1=x4=0 x1=

22、x4=0，基变量，基变量x2=10 x2=10，x3=30 x3=30所以所以X X（1 1）= =（0 0，1010，3030，0 0）T T基可行解是否是最优解？基可行解是否是最优解？因为因为3=03=0了，所以只需要将了，所以只需要将22变换为变换为0 0。方法：矩阵的第。方法：矩阵的第3 3行行- -第第2 2行行4 4-40-40 0 0 5/35/3-4/3-4/3得出：得出：X X（1 1）= =（0 0，1010，3030，0 0）T T不是最优解不是最优解下一步：确定换入变量和换出变量下一步：确定换入变量和换出变量请大家自己运算，直到确定最优解。请大家自己运算，直到确定最优解

23、。30301818x1x13 3将基（将基（P1 P2P1 P2）初等变换为单位矩阵）初等变换为单位矩阵方法：方法： 5/3 5/3 - -1/31/3确定基本可行解确定基本可行解X X（2 2）= =（1818，4 4，0 0，0 0）T T最优性性判断？最优性性判断？ - -5/35/3看到所有的检验数都小于看到所有的检验数都小于0 0，所以，所以X X（2 2）是最优解是最优解同时目标函数值为同时目标函数值为7070 1 13/53/5-1/5-1/51818 0 0-1/5-1/52/52/54 4 0 0 -1 -1 -1 -1 -70 -70-z-z0,24261553. .2ma

24、x21212121xxxxxxtsxxz0,212665. .22min2121212121xxxxxxxxtsxxz0,2-10242-. .42ax2121212121xxxxxxxxtsxxzm5432100042maxxxxxxz0,201242-54321521421321xxxxxxxxxxxxxx初始单纯形表如下：初始单纯形表如下：X X（0 0）= =（0 0，0 0，4 4，1010，2 2）T T2 24 40 00 00 00 0判断是否最优？判断是否最优？不是最优！不是最优！换基方案？换基方案？换入变量：换入变量：x2x2，2 25 5换出变量：换出变量：x3x3543

25、2100042maxxxxxxz0,201242-54321521421321xxxxxxxxxxxxxx经初等变换，将（经初等变换，将（P2P2，P4P4，P5P5）变换为单位矩阵）变换为单位矩阵判断是否最优？判断是否最优？-1/2-1/2 2 21/21/2 1 1 0 0 0 01/21/2 -1 -11/21/2基本解为基本解为X X（1 1）= =（0 0，2 2，0 0，6 6，4 4）T T 2 2 6 6 4 4不是最优解！不是最优解！ 4 4 0 0 -2 -2 -8 -8换基方案？换基方案？ 换入变量：换入变量：x1x1， 3 3 8 8换出变量：换出变量：x4x4经初等变

26、换，将（经初等变换，将（P1P1，P2P2，P5P5）变换为单位矩阵）变换为单位矩阵判断是否最优？判断是否最优？基本解为基本解为X X（2 2）= =（3 3，7/27/2，0 0，0 0，5/25/2）T T是最优解！是最优解！ 0 0 1 1 0 0 1/4 1/4-1/2-1/23/4 3/4 1/4 1/41/21/2-1/4 -1/4 7/2 7/2 3 3 5/2 5/2 -2 -2-20-20 0 0 0 0目标函数值为目标函数值为z=20z=20但是这时，非基变量但是这时，非基变量x3x3的检验数为零，表示原问题还有其他的最的检验数为零，表示原问题还有其他的最优解，也就是说这是

27、多重最优解的情况。还可以进一步迭代！优解，也就是说这是多重最优解的情况。还可以进一步迭代！换基方案？换基方案？ 换入变量：换入变量：x3x3， 换出变量：换出变量：x5x5 14 14 10/3 10/3 x3 x3经初等变换，将（经初等变换，将（P1P1，P2P2，P3P3）变换为单位矩阵）变换为单位矩阵基本解为基本解为X X（3 3）= =（14/314/3，8/38/3，10/310/3，0 0，0 0）T T 1 1 0 0 0 01/31/31/31/3-1/3-1/3-1/3-1/32/32/34/34/38/38/314/314/310/310/3基本解为基本解为X X（3 3）

28、是最优解！是最优解！ 目标函数值目标函数值z=20z=200,25 . 01. .00 x22ax43214213214321xxxxxxxxxxtsxxxzm因为问题是最大化问题，这时非基变量因为问题是最大化问题，这时非基变量x1x1的检验数的检验数=2=2（00），可以作为进基变量，但是增广矩阵中），可以作为进基变量，但是增广矩阵中x1x1对应对应的系数都小于的系数都小于0 0，所以目标函数无上界，问题无最优解！，所以目标函数无上界，问题无最优解！0|minikikiaab0,122102434. .23max321321321321321xxxxxxxxxxxxtsxxxz)5,.,1(

29、0122102434. .0023max3215321432154321jxxxxxxxxxxxxtsxxxxxzj0012-21021-101-134-A系数矩阵系数矩阵A A为：为：系数矩阵系数矩阵A A中不包含单位矩阵，中不包含单位矩阵，因此增加人工变量去构造单位因此增加人工变量去构造单位矩阵，但增加的人工变量不能矩阵，但增加的人工变量不能影响目标函数。影响目标函数。)7,.,1(0122102434. .0023max73215321643217654321jxxxxxxxxxxxxxxtsMxMxxxxxxzj)5,.,1(0122102434. .0023max3215321432

30、154321jxxxxxxxxxxxxtsxxxxxzj0012-21021-101-134-A)7,.,1(0122102434. .0023max73215321643217654321jxxxxxxxxxxxxxxtsMxMxxxxxxzj100012-2001021-10101-134-A系数矩阵系数矩阵A A为：为：有有1 1单位子矩阵单位子矩阵）（7, 5, 6100010001BPPP系数为负数，我们知道在换基时，系数为负数，我们知道在换基时，会把它们置换出来，这样就不会影会把它们置换出来，这样就不会影响目标函数了响目标函数了)7,.,1(0122102434. .0023max

31、73215321643217654321jxxxxxxxxxxxxxxtsMxMxxxxxxzj)7,.,1(0122102434. .0023max73215321643217654321jxxxxxxxxxxxxxxtsMxMxxxxxxzj3-4M3-4M 2+3M2+3M -1+M-1+M-M-M0 03-2M3-2M2+M2+M -1+2M-1+2M-M-M0 0换基：换入变量换基：换入变量x3x3，换出变量，换出变量x7x70 0-6-6 5 50 0-3-3 3 33 38 85M5M 0 0 5-6M5-6M换基：换入变量换基：换入变量x2x2，换出变量，换出变量x6x6换基：

32、换入变量换基：换入变量x1x1，换出变量，换出变量x5x51 1-6/5-6/5-1/5-1/50 03/53/53/53/50 0-2/5-2/53/53/531/531/5-2/5-2/511/511/50 0 5 5 0 0X=(31/3,13,19/3,0,0)X=(31/3,13,19/3,0,0)T T最优值最优值z=152/3z=152/3 1 1 1 15/35/331/331/3 0 0 1 1 2 21313 0 0 0 02/32/319/319/3-5-5-25/3-25/3 0 0miiR1wmin0,122102434. .23max321321321321321xxxxxxxxxxxxtsxxxz)5,.,1(0122102434. .0023max3215321432154321jxx