《运筹学》复习例题

线性规划的表格单纯形法一工厂生产A、B、C三种产品所需的劳力分别为6、3和5个工作日单位，所消耗的原材料 分别为3、4和5kg，各单位产品的收益分别为2、1和5元，工厂每日能提供的劳力数为100 人，材料量为80kg。问该工厂应如何安排生产才能使总的收益达到最大。（1）建立线性规划的数学模型；（2）用表格单纯形法求解；（3）当劳力数增加10人，材料量增加20kg时新的最优方案；（4）写出对偶问题和对偶问题的最优解。（5）求 x1 的价值系数在什么范围变化最优解不变解：设A、B、C三种产品的产量分别为x ,x ,x，则数学模型为123max z 二 2 x + x + 5 x1 2 36x + 3x + 5x 1001233x + 4x + 5x 0123(2) 化为标准型max z 二 2x + x + 5 x1236x + 3x + 5x + x 二 10012343x + 4x + 5x + x 二 801235x , x , x ,x , x 012345C.21500eCBXBbX1X2X3X4X50X410063510200X5803450116C -Zj j215000X4203-101-15Xo163/54/5101/5C -zj j-1-300-1最优解为X二x2=0，x3=16，最大的利润z=80元。（3） 由上表知最优基矩阵的逆1-1111110101B -i=，B-ib 二=01/501/510020c.21500eCXbXXXXXBB123450X4103-101-15XQ203/54/5101/5C -zj j-1-300-1所以新的最优解为X二x2=0，x3=20，最大的利润z=100元。（4） 对偶问题为min w = 100 y + 80 y126 y + 3 y 3123 y + 4 y 1125 y + 5 y 512y1,y20 12对偶问题的最优解 y1=0,y2=1.互补松弛性的应用 该问题的对偶问题为0（2）（3）（4）min w 二 8 y +12 y2 y + 2 y 21 22 y 1s.t.2 512y + 2 y 61 2 y , y 0 12由互补松弛性：若充,P分别是原问题和对偶问题的可行解，那么空=0和丫尤=0，当 ss且仅当X与Y为最优解。设x * = （*, x *,兀*,x *丄为原问题的最优解。 1234X = （x , x s 56其中x ,x为原问题约束条件的松弛变量。而为对偶问题的最优解。Ys =（y3, y4, y5, y6）其中勺y4y6为与相对应的松弛变量。Y*X = 0sY X* = 0s=4,y2*=1. (3)(4) 为等式，故 y = y = 0 56(1)(2)为不等式，故y丰0, y丰034由 Y X* = 0即sy x * + y x * + y x * + y x * = 0 3 1 4 2 5 3 6 4得 x * 二 x * 二 0 12 y , y 012由 Y*X= 0s得 x = x = 056即原问题的约束条件应取等号x + x34x + 2 x34=8=12x解得1 3x4=4=4所以，原问题的最优解为X * =（0,0,4,4目标函数最优值max z = 2 x 0 +1 x 0 + 5 x 4 + 6 x 4 = 44运输问题例题设有产量分别是8, 9的两个原料产地A、, A2,欲将原料运往需求量分别为6, 5, 8的三 个销地，单位运价表如下，试写出该问题的数学模型并求运费最省的调运方案。（20 分）销地 产地、B1B2B3产量A12361A16548销量658解：因总产量为 17,总销量为 19,所以是产小于销的运输问题,增加一个产地转化为产销 平衡的运输问题为：、销地 产地B1B2B3产量A11236A26548A30005销量658按表上作业法,首先用伏格尔法求得初始基可行解如下表：销也 产地Bb2b3产量A】628a2549A22销量658用位势法求得检验数为：销地 产也Bb2b3A】000U=8a2500U =6a3530U =0V=-5V=-3V=0由于检验数全部非负，则该初始基可行解即为最优解，最优值为53. 数学模型为用分枝定界法求解下面的整数规划max z 二 3 x + 2 x + x1 23x + x 2 x 61232 x + 3 x 112x x + 2 x 0, x , x , x 为整数123123已知其放松的线性规划的最优单纯形表：c.321000CBXBbx1x2x3x4x5x62x211/30101/31/31/31x34/3001-1/121/65/123x51001/201/2c -zjj000-25/12-5/6-31/12解：由线性规划的最优单纯形表知其最优解为乂=5,2=11/3,3=4/3非整数解,最优值z0=71/3, xi=0，x2=0，x3=0为一整数可行解，目标函数值为z=0,定界0 Z 71/3。分枝x2 4，相应的问题设为Bi或B2，解B1如下表:c.32100009CBXBbx1x2x3x4x5x6x72x211/30101/31/31/301xQ4/3001-1/121/65/1203x151001/201/200xz30100001c -zj j000-25/1-5/6-31/10222x211/30101/31/31/301x34/3001-1/121/65/1203x151001/201/200x7-2/3000-1/3-1/3-1/31c jz000-25/1-5/6-31/10222x2301000011x31001-1/401/41/23x151001/201/200x2000111-3c j000-5/40-7/4-5/2z j得到一个整数最优解xi=5, x2=3, x3=1，最优值为22,因该最优解是满足整数条件，所以该整数规划的下界z=22。同理求解另一个线性规划问题（要写出求解的单纯形表）B2，因无可行解，因此该整数 规划的上界也为22，所以整数规划的最优值为22，上面的这个解即为最优解。指派问题题解某公司有五个经理分别派往五项五个地区负责市场开拓，预计相应的净收益如下 表（单位：百万元），试求使总收益最大的分派方案并写出该问题的数学模型（每 人只负责一个地区）。任务 人员12345111776122975863103817411513810565538解：数学模型为111213141521222324+ 10x + 3x+ 8x+ x+ 7x+ 11x+ 5x+13x + 8x+ 10x313233343541424344+ 6x + 5x + 5x+ 3x+ 8x5152535455x+ x + x+ x+ x 二1x+ x+ x+ x+ x=111121314151121314151x+ x + x+ x+ x=1x+ x+ x+ x+ x=121222324251222324252x+ x + x+ x+ x=1x+ x+ x+ x+ x=131323334351323334353x+ x + x+ x+ x=1x+ x+ x+ x+ x=141424344451424344454x+ x + x+ x+ x=1x+ x+ x+ x+ x=151525354551525354555x= 1或 0,i,j =1,2,545ijmax z = llx + 7x + 7x + 6x + 12x + 9x + 7x + 5x + 8x + 6x-1215560_-11-7-7-6-12_-9-7-5-8-6-902413-10-3-8-1-7-1007293-11-5-13-8-10-1328053-6-5-5-3-8 _-823350_mmmin 21VVV 2440 0 0 0440 0 0 1 05284则最优解为1 0 0 0 026440 0 10 01230 10 0 0min1,3,5,5,2,1,3,4=1,最优值为 48。线性规划与灵敏度分析题解一工厂生产A、B、C三种产品所需的劳力分别为6、3和5个工作日单位，所消耗的原材料 分别为3、4和5kg，各单位产品的收益分别为2、1和5元，工厂每日能提供的劳力数为100 人，材料量为80kg。问该工厂应如何安排生产才能使总的收益达到最大。（6）建立线性规划的数学模型；（7）用表格单纯形法求解；（8）当劳力数增加10人，材料量增加20kg时新的最优方案；（9）写出对偶问题和对偶问题的最优解。解：设A、B、C三种产品的产量分别为x ,x ,x，则数学模型为123max z = 2 x + x + 5 x1 2 36x + 3 x + 5 x 100 1233x + 4x + 5x 0123(2) 化为标准型max z 二 2x + x + 5 x1 2 36x + 3x + 5x + x 二 10012343x + 4x + 5x + x 二 801235C.215009CBXBbx1x2x3x4x50x4100635100x58034501C -zj j215000x4203-101-15x2163/54/5101/5C -zj j-1-300-1最优解为X二x2=0, x3=16，最大的利润z=80元。 (3)由上表知最优基矩阵的逆1-1111110101B -i=，B -1b 二=01/501/510020c.215009CXbxxxxxBB123450x4103-101-15xc203/54/5101/5C -zj j-1-300-1所以新的最优解为x= x2=0, x3=20,最大的利润z=100元。(4)对偶问题为min w = 100 y + 80 y6 y + 3 y 3123 y + 4 y 1125 y + 5 y 512y1,y20对偶问题的最优解 y1=0,y2=1.最大流的标号法用标号法求下图所示的公路交通网络的最大流量(要求写出标号过程并说明得到的的确是最 大流)，其中，弧旁的数字是(c f )。.ij ij解: 首先，给V标上(0, +8 )S(2)检查v ,给v为起点的未饱和弧的未标号的终点v标号(v , 1 (v ),其中s s 2 s 21 (v )二 min1 (v ), c f 二 min+s,15 7二 82 ss 2s 2其它点不符合标号条件。(3) 检查v，给v为终点的非零流弧的未标号的起点v标号(v , 1 (v )，其中2 2 3 2 31 (v )二 min1 (v ), f 二 min8,4二 43 2 32其它点不符合标号条件。(4) 检查v，给v为起点的未饱和弧的未标号的终点v、v标号(v , 1 (v ) )、(v , 1 (v )33464466其中，1 (v )二 min1 (v ),c f 二 min4,5 4二 14 334341 (v ) = min1 (v ), c f = min4,5 1 = 46 3 36 36 其它点不符合标号条件。(5) 检查v，给v为起点的未饱和弧的未标号的终点v标号(v , 1 (v )其中，6 6 t t t1(v )=min1(v ),c f =min4,105=4t 66 t6t其它点不符合标号条件。由于v已标号，反向搜索可得增广链卩=(v , v ),(v , v ),(v , v ),(v , v )，在该增广链t s 2 3 2 3 6 6 t的前相弧(v ,v ),(v ,v ),(v ,v )上增加1 (v ) = 4，在后向弧(v ,v )上减去1 (v ) = 4，其s 2 3 6 6 t t 3 2 t它弧上的流量不变，则可得一流量v( f) = 20的新的可行流如下图。V3(5,5)V6重新开始标号：首先，给V标上(0, +8 )s(7) 检查v ,给v为起点的未饱和弧的未标号的终点v标号(v , 1 (v )，其中s s 2 s 21 (v )二 min1 (v ), c f 二 min+s,15 11二 42 ss 2s 2其它点不符合标号条件。(8) 检查v，没有以v为起点的未饱和弧的未标号终点和以v为终点的非零流弧的未标号2 2 2 起点，因此不能增加标号点，标号进行不下去了，所以该可行流必为最大流,最大流的流量 为 v(f)=20。事实上，可令V = v ,v ，V = v ,v ,v ,v ,v ，则最小截集(V ,V)的截量1s 213456 t11C(V ,V) = c + c + c = 9 + 5 + 6 = 20 = v( f)。1 1s 32524最短路的标号法用Dijkstra标号法求v到v的最短路及最短路线stvt解：i=0,给v标上(P(v ) = 0 ,九(v ) = 0 ),其余各点均为T标号点，s s sT(v ) = +8,九(v ) = M, j = 2,3,4,t，记S = v k = s。jj0 si=1,考察以v为起点的弧的终点v、v ,由于P(v ) + w = 0 +10 = 10 +8、s 2 3 ss 2s。T 标 号 分 别 为T(v3)，将v3的T标号改为PP(v ) + w = 0 + 3 = 3 8，修ss 3T(v ) = 10, X(v ) = s,T(v ) = 3,九(v )=2233标号，即P(v ) = 3,记S =b ,v h = 3.由于 P(v)+w =3+5=810，3323 1 s 3i=2, 考 察 以 v3 为 起 点 的 弧 的 终 点 v2 、 v4 ，P(v )+w =3+12=15+8334324修 改v2 、v4 的 T 标 号 分 别 为24T(v )二&九(v )二 3,T(v )二 15,X(v )二 3。计算 min2244jT(v2)，将 V2的T标号改为P标号，即 P(v2)二 8，记 S2J，分 v2 I k = 2.i=3, 考 察 以 v 为 起 点 的 弧 的 终 点 v 、 v ，2 4 t由于 P(v ) + w = 8 + 6 = 14 +8 ,22 tP(v ) + w 二 8 + 2 二 10 15 ,修改 v、v 的224t4T 标号为 T(v ) = 14, X(v ) = 2 ,ttT(v ) = 10,X (v ) = 2。计算 m44T(v ) ，j4P(v )二 10，记 S 二 b , v , v , v k 二 4.43 s 324将v4的T标号改为P标号，即=10 + 3 = 13 14，修改v的T标号ti=4,考察以v4为起点的弧的终点vt，由于P(v4)+ w4t为T(v ) = 13,X (v ) = 4，计算minT(v )，将v的T标号改为P标号，即ttjttP(v )二 13，记 S 二v ,v ,v ,v ,v k 二 10t4s 324 t由于Vt得到了 P标号，所以得到了 Vs到Vt的最短路vs , v3, v2, v4, vt，最短路的权为P(v )二 13 ot