运筹学作业-王程

1、运筹学作业王程信管 1302目录运筹学作业 1第一章 线性规划及单纯形法 3第二章 线性规划的对偶理论与灵敏度分析 25第三章运输问题 56第四章 目标规划 67第五章整数规划 78第六章非线性规划 92第七章动态规划 103第八章 图与网络分析 106第九章 网络计划 108第一章线性规划及单纯形法分别用图解法和单纯形法求下列线性规划问题，指出问题具有唯一最优解、 无穷多最优解、无界解还是无可行解；当具有限最优解时，指出单纯形表中 的各基可行解对应图解法中可行域的哪一顶点。(1) minz 2x13X2（2）maxz3x12x24x16x262x1X22s.t.3x1 2x24s.t.3x1

2、4x212X1,X20X1, X20(3)maxz 10 X15x2（4）maxz5x16x23x14 x292x1X22s.t.5x12 x28s.t.2x1 3x22x1, x20X1, X2 0解：图解法:X2216 1当X2 X1 z经过点（-厂）时，z最小，且有无穷多个最优解335 5图解法:该问题无可行解图解法：52单纯形法:在上述问题的约束条件中分别加入松弛变量人,人,化为标准型:maxz 10X|+5x2 0x3 0x43为 4x2 X3 9s.t. 5x1 2x2 x4 8加2公3凶 0由线性规划问题的标准型可列出单纯初始形表逐步迭代，计算结果如下表所单纯形表的计算结果表明:

3、 单纯形表迭代的第一步得 单纯形表迭代的第二步得 单纯形表迭代的第三步得示：Cj10500aCBXBbX1X2X3X40X39341030X4852018/5Cj-Zj105000X321/5014/51-3/53/210X18/512/501/54Cj-Zj010-25X23/2015/14-3/1410X1110-1/72/7Cj-Zj00-5/14-25/14*3t *3X ( ,1,0,0) T,Z 105 1202 2X(0)(0,0,9,8) T，表示图中原点0( 0,0)X(1)(8,0, 21,0) T，表示图中 C 点55X(2)(1,3,0,0) T，表示图中 B点2图解法

4、:X25 1当x2经过点(2,2)时，z取得唯一最优解6 6将下述线性规划问题化成标准形式。(1) min z3片 4x2 2x3 5x44xx2 2x3 X4s.t.xix2 x3 2x4142x1 3x2 x3 x4x1, x2, x3 0,x4 无约束解：上述问题中令z乙x4 x4 x4,其中x4 0,x4 0,则该问题的标准形式为maxz 3x1 4x2 2x3 5x4 5x4 4x1 x2 2x3 x4 x4 2x1 x2 x3 2x4 2x4 x5 14 s.t.2x1 3x2 x3 x4 x4 x6 2 x1,x2,x3,x4 ,x4 , x5 , x6 02)min z 2x1

5、 2x2 3x3x1 x2x3 4s.t. 2x1 x2 x3 6x10, x20, x3无约束解：上述问题中令z乙x,x,X3 X3 X3,其中x/ 0,X3” 0,则该问题的标准形式为max z2x12x2x3x1x2x3x3 4s.t. 2x1 x2x3 x3x46x1,x2,x3 , x3 , x4对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解1)max z3x15x2(2)min z5x12x23x3 2x4x1x34x12x23x34x4 72 s.t.x2x412s.t. 2x12x2x32x4 33x12x2x518xj 0(j1,L ,4)xj0 j1,L,

6、5解：（1）该线性规划问题的全部基解见下表中的，打V者为基可行解, 注 * 者为最优解， z* =36。序号xiX2X3X4X5z可行？2620036*V4306027V4600-642X094-6045X0640630V00412180V40012612V60-212018X(2)该线性规划问题的标准形式为:max z5x12x23x3 2xX12x23 X34x4 7s.t. 2x12x 2X32x4 3Xj0(j1，,4)其全部基解见下表中的，打V者为基可行解，注 *者为最优解，z =5序号X1X2X3X4Z /可行？0011-5*V0-1/202-5X0-1/220-5*V-1/300

7、11/6-2X2/5011/50-43/5V-411/20031X题(3)中，若目标函数变为 maxz ex d冷，讨论c,d的值如何变化，使该问 题可行域的每个顶点依次使目标函数达到最优。解：由目标函数maxz ex 可得：冷 彳为 彳kx彳，其中k 彳d d dd3当3 k 0时可行域的顶点A使目标函数达到最优;53当5 k 3时，可行域的顶点B使目标函数达到最优;245当 k -时，可行域的顶点C使目标函数达到最优;2当c 0,d0或c 0,d0时，最优解为0点。分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪一类解。(1 mins.t.z 2为 3x2 x1 4x2

8、2x3 3片 2x2Xi，X2，X30X38(2)max z 10x,15x2 12x35x, 3x2 x395x1 6x215x315s.t.2 x1 x2 x35冷必压 0(1)解：大怯：在上述线性规划问题的约束条件中减去剩余变量、Xs,再分别加上人工变量 xc、x?，得minz 2x1 3冷x, 4x? 2x3s.Bx1 2x2 xsX3X4X70x4 Oxg M怡 MXc 86为X，沟,x4,x5,xj,X70其中M是一个任意大的正数，据此可列出初始单纯形表如下:Cj23100MM9 iCbbX1X2X3X4X5X6X7MX68142-10102MX763200-1013Cj-Zj2-

9、4M3-6M1-2MMM003X221/411/2-1/401/408MX725/20-11/2-1-1/214/5Cj-Zj545M20M丄234Im2MCO I寸WCO I CXI03X29/5013/5-3/101/103/10-1/102Xi4/510-2/51/5-2/5-1/52/5Cj-Zj0001/21/2M-1/2M-1/2由单纯形表的计算结果得：最优解 X目标函数最优值z*2 - 3 9755X存在非基变量检验数3=0，故该线性规划问题有无穷多最优解。4 9匚，匚,0,0,0,0,05 5两阶段法：x4, x5,再分别加上人工变量先在上述线性规划问题的约束条件中减去剩余变量

10、X6,x7,得第一阶段的数学模型min w=x6 x7为 4x2 2x3 x4 x68s.t. 3x1 2x2 x5 x76Xi，X2，X3，X4, X5, X6，X70据此可列出单纯初始形表如下:Cj00000119 iCbXbbX1X2X3X4X5X6X71X68142-101021X763200-1013Cj -Zj-4-6-211000X221/411/2-1/401/4081X725/20-11/2-1-1/214/5Cj -Zj520112132000X2xi9/54/501103/5-2/5-3/101/51/10-2/53/10-1/5-1/102/5Cj-Zj0000011T

11、第一阶段求得的最优解X*上,9,0,0,0,0,0 ，目标函数的最优值w 0,因人5 5T工变量X6 x? 0,所以-,9,0,0,0,0,0是原线性规划问题的基可行解。于是可5 5以进行第二阶段计算，将第一阶段的最终表中的人工变量取消， 并填入原问题的目标函数的系数，如下表:Cj231009 iCBXbbX1X2X3X4X53X29/5013/5-3/101/102X14/510-2/51/5-2/5Cj-zj0001/21/2由表中计算可知，原线性规划问题的最优解X*4 ,9,0,0,0,0,0 ，目标函数的5 5最优值z* 2 | 3 9 7，由于存在非基变量检验数3=0，故该线性规划问

12、题有无穷多最优解解：大M法：在上述线性规划问题的约束条件中加上松弛变量5,减去剩余变量g,再加上 人工变量得maxz 1CX1+15C, 12x30X4 0Xs 0x. M 治6x2 15x3 xx3 沧 X7155x1,x2,x3,x4, x5,xg,x?其中M是一个任意大的正数，据此可列出单纯形表如下:Cj101512000-M9 iCBXbbX1X2X3X4X5X6X70X4953110009/50X515-56150100-MX7521100-115/2Cj-Zj10+2M15+M12+M00-M010X19/513/51/51/500090X524091611003/2-MX77/5

13、0-1/53/5-2/50-117/3Cj-Zj0c M9 510+3M522 -M50M010X13/2139/8003/16-1/800012X33/209/1611/161/1600-MX71/20-43/800-7/16-3/80-11Cj-Zj02743“M8 800217 “M8 1653 “M8 80M0由单纯性表的最终表可以看出，所有非基变量检验数j 0，且存在人工变量1X7-，故原线性规划问题无可行解。2两阶段法：x4, X5,减去剩余变量x6,再在上述线性规划问题的约束条件中加上松弛变量加上人工变量X7,得第一阶段的数学模型min w=x75x1 3x2 Xq x49s.t

14、.5为 6x2 15x32x1X2X3x6X5X7155X-,X2,X3,X4,X5, X6,X7据此可列出单纯初始形表如下:Cj00000019 iCBbX1X2X3X4X5X6X70X4953110009/50X515-56150100-1X7521100-115/2Cj-Zj-2-1-1001010X19/513/51/51/500090X524091611003/21X77/50-1/53/5-2/50-117/3Cj-Zj0-1/53/5-2/50100X13/2139/8003/16-1/80000X33/209/1611/161/16001X71/20-43/800-7/16-3

15、/80-11Cj-Zj0438007/163/8010第一阶段求得最优解xj ,|0,因人工变量x7 20，且非基变量检验数j 0，所以原线性规划问题无可行解。考虑下述线性规划问题：zc1 x1c2 x2a1 xa2 x?b|a?1 xa 22 x?b?x1, x20maxs.t.式中，c 3,4 C2 6, 13,2 目2 5,8 b 12,2 a21 4,4 a22 6,10 b2 14,试确定目标函数最优值的下界和上界。解：（1）上界对应的模型如下（c，b取大，a取小）max z3 x16 x21 x12 x212s.t. 2 x14 x214x1 , x20最优值（上界）为：21;（2

16、）下界对应的模型如下（c, b取小，a取大）maxzx14 x23 x15 x28s.t.4x16x210X1 , x20最优值（下界）为：。已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到表1-21，试求括弧中未知数a : l的值。表 1-21项目x 1x 2x 3x 4x 5X46(b)(c)(d)10x 51-13(e)01Cj -Zj(a)-1200X1(f)g)2-11/20X54:h)(i)11/21Cj -Zj0-7(j)(k)(l)解：abcdefgh ijkl324-223105-5-3/20若X,X（2）均为某线性规划问题的最优解，证明在这两点连线上的所有点也是该 问

17、题的最优解。证明：设X和X满足:max zC T XAXbX0对于任何0a1,两点连线上的点X满足：XaX(1 a ) X也是可行解，且C TXC T aX (1)C T (1 a )X C T aX aC TX (2) C TX c T X所以 X也是最优解。考虑线性规划问题maxz x 2x2 x3 4x4(i)(ii)人 Xx4 4 2s.t. 2x! x? 3x3 2x 5 7x1,x2,x3,x4模型中，为参数，要求:组成两个新的约束(i)=(i)+(ii),(ii)=(ii)-2(i),根据式(i)和式(ii)，以xi,为基变量，列出初始单纯形表；(i)人备3 2 解：(ii)冷为

18、1Cj fa21-4CB基bX1X2X3X4aX13+2 B101-12X21-B01-10Cj-Zj003- aa-4 在表中，假定 =0 ，则 为何值时， x1,x2 为问题的最优基；解：如果=0,贝V当34时，为必为问题的最优基变量。 在表中，假定 =3，贝U 为何值时，K,x2为问题的最优基。解：如果 =3,则当-11时，X!,X2为问题的最优基变量。试述线性规划模型中“线性”二字的含义，并用实例说明什么情况下线性的假 设将被违背。答：线性的含义：一是严格的比例性，如生产某产品对资源的消耗量和可获取 的利润，同其生产数量严格成比例；二是可叠加性，如生产多种产品时，可获 取的总利润使各项

19、产品的利润之和，对某项资源的消耗量应等于各产品对该资 源的消耗量之和；三是可分性，即模型中的变量可以取值为小数、分数或某一 实数；四是确定性，指模型中的参数 cj,aij,bi 均为确定的常数。很多实际问题往往不符合上述条件，例如每件产品售价 3 元，但成批购买 就可以得到折扣优惠。判断下列说法是否正确，为什么？ 含n个变量m个约束的标准型的线性规划问题，基解数恰好为 Cnm个；答：错误。基本解的个数 =基的个数 Cnm 线性规划问题的可行解如为最优解，贝该可行解一定为基可行解；答：错误。当有唯一最优解时，最优解是可行域顶点，对应基本可行解；当 有无穷多最优解时，除了其中的可行域顶点对应基本可

20、行解外，其余最优解不 是基本可行解。 如线性规划问题存在可行域，贝可行域一定包含坐标的原点；答：错误。如果约束条件中有一个约束所对应的区域不包含坐标的原点，贝 即使有可行域，也不包含坐标的原点。 单纯形法迭代计算中，必须选取同最大检验数 j 0对应的变量作为换入 基的变量。答：错误。若此时最大检验数j 0，可是Pj 0，则问题是无界解，计算结束线性规划问题maxz CX,AX b,X 0,如X是该问题的最优解，又 0为某 一常数，分别讨论下列情况时最优解的变化。目标函数变为maxz CX ；目标函数变为maxz (C )X ；C目标函数变为maxz X，约束条件变为AX b。解：最优解不变；C

21、为常数时最优解不变，否则可能发生变化；最优解变为：X/入。某饲养场饲养动物出售，设每头动物每天至少需要 700g蛋白质、30g矿物质、 100mg维生素。现有五种饲料可供选用，各种饲料每 kg营养成分含量及单价如 表1-22所示。表 1-22饲料蛋白质/g矿物质/g维生素/mg价格/(元/kg)1310.50.2220.51.00.7310.20.20.446220.35180.50.80.8要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。解：设Xj表示第i种饲料数量，i 1,2,3, 4,5min z0.2 x10.7 x20.4 X30.3 x40.8 X53x12x2x3

22、6 x418 x5700丄Xi0.5 x20.2 X32x40.5 x530s.t.0.5x1x20.2 X32x40.8 X5100Xi0, i 1,2,3, 4,5最优解为 Xi X2 X30, X439.74, x 25.64, z 32.44（元）辽源街邮局从周一到周日每天所需的职员人数如下表1-23所示。职员分别安排在周内某一天开始上班，并连续工作5天，休息2天。表 1-23人周一二三四五六日所需人数17131519141611要求确定：该邮局至少应配备多少职员，才能满足值班需要； 因从周一开始上班的，双休日都能休息；周二或周日开始上班的，双休日 内只能有一天得到休息；其他时间开始上

23、班的，两个双休日都得不到休息，很 不合理。因此邮局准备对每周上班的起始日进行轮换 （但从起始日开始连续上5 天班的规定不变），问如何安排轮换，才能做到在一个星期内每名职工享受到同 等的双休日的休假天数； 该邮局职员中有一名领班，一名副领班。为便于领导，规定领班于每周一、 三、四、五、六上班，副领班于一、二、三、五、日这 5天上班。据此试重新 对上述要求和建模和求解。解：(1)设x(i 1,2,K,7)表示星期一至星期天开始上班的人数，则建立如下 的数学模型。目标函数：min z % x2 x3 x4 x5 x? x7XiX4X5XX7i3xXX6X7Xii5X3XX7XiX2i9约束条件：s.

24、t. x4X7XiX2X3i4X5XiX2X3X4i6x6X2X3X4X5iiX7X3X4X5X6i7Xi,X2,X3,x4,X5,6,X70解得最优解为 X* (7,4,2,8,0,2,0), z* 23则该邮局至少应配备23名职员，才能满足值班需要。对这23名职工分别编号，以23周为一个周期，这23名职工上班安排见下表。每周上班 时间起止周职工职工职工？职工？职工周一周五i7281622172323,16周二周六8ii9i223,1314710周三周日i2i3i3i445561112周四下周一i42i15226137141320周五下周二222323,1141515162122此时只需在每

25、天人数中减去领班和副领班两人即可，重现建模如下:min z=x1 x2 x3 x4 x5 x6 x7X1X4X5X6X715X1X2X5X6X712X1X2X3X6X713X1X2X3X4X718X1X2X3X4X512X2X3X4X5X616X3X4X5XX710X1,X2, X3, X4,X5, X6,X70一艘货轮分前、中、后三个舱位，它们的容积与最大允许载重量如表1-24所示。现有三种货物待运，已知有关数据列于表1-25。又为了舱运安全，前、中、后舱的实际载重量大体积保持各舱最大允许载重量的比例关系。具体要求：前、后舱分别与中舱之间载重量比例的偏差不超过15%前、后舱之间不超过10%问

26、该货轮应装载A、B、C各多少件运费收入 为最大？试建立这个问题的线性规划模型。表 1-24项目前舱中舱后舱最大允许载重量/t200030001500容积/m3400054001500表 1-25商品数量/件每件体积/（m3/件）每件重量/（t/件牛）运价/（元/件）A6001081000B100056700C80075600解：用i=1,2,3表示A、B、C三种货物，j=1,2,3表示前、中、后三个舱，用x(i , j)表示货物i在舱j的装载量。max z 1000( x(1,1)x(1,2)+ x(1,3)+700( x(2,1)+ x(2,2)+ x(2,3)+600( x(3,1)+ x

27、(3,2)+ x(3,3)商品数量约束：1)x(1,1)x(1,2)x(1,3)6002)x(2,1)x(2, 2)x(2,3)10003)x(3,1)x(3, 2)x(3,3)800商品容积约束：4)10x(1,1)5x(2,1)7x(3,1)40005)10 x(1,2)5x(2, 2)7x(3, 2)54006)10x(1,3)5x(2,3)7x(3,3)1500最大载重量约束：7)8x(1,1)6x(2,1)5x(3,1)20008)8 x(1,2)6x(2, 2)5x(3, 2)30009)8 x(1,3)6x(2,3)5x(3,3)1500重量比例偏差约束：10)8 x(1,1)6

28、x(2,1)5x(3,1)Id0.15)(8 x(1,2)6x(2,1)5x(3, 2)11)8 x(1,1)6x(2,1)5x(3,1)3(10.15)(8 x(1,2)6x(2,1)5x(3, 2)12)8 x(1,3)6x(2,3)5x(3,3)i(10.15)(8 x(1,2)6x(2,1)5x(3, 2)13)8 x(1,3)6x(2,3)5x(3,3)2(10.15)(8 x(1,2)6x(2,1)5x(3, 2)14)8 x(1,3)6x(2,3)5x(3,3)0.1)(8 x(1,1)6x(2,1)5x(3,1)15)8 x(1,3)6x(2,3)5x(3,3)3(10.1)(

29、8 x(1,1)6x(2,1)5x(3,1)4长城通信公司拟对新推出的一款手机收费套餐服务进行调查，以便进一步设计改进。调查对象设定为商界人士及大学生，要求：总共调查600人，其中大学生不少于250人；方式分电话调查和问卷调查，其中问卷调查人数不少于 30%对大学生电话调查 80%以上应安排在周六或周日，对商界人士电话调查 80鸠上应安排在周一至周五；问卷调查时间不限。已知有关调查费用如表 1-26所示，问该公司应如何安排调查，使总的费用为最省。表1-26兀/人次调查对象电话调查问卷调查周一至周五周六、日大学生3.02.55.0商界人士3.53.05.0解：设x“, x2为周一至周五对大学生和

30、商界人士电话调查人数,2,x22为双休日对上述 人员电话调查人数，为3必23分别为问卷调查人数，则数学模型为minz 3.CX11 2.5Xi2 5.CX13 3.5x?i 3.CX22 5.CX23X|1 X12 X13 x?1 X22 X23600x11 X12x13 250X|3x?3S.t.X121800.8X11 X12X210.8X21 X2最优解X|1 0,Xi2 350Xl3 0,X2158,x?2 11,x23 180 z2014生产存储问题。某厂签订了 5种产品（i=1，5） 上半年的交货合同。已知 各产品在第j月（j=1，6）的合同交货量D ，该月售价Sj 、成本价co及

31、 生产1件时所需工时aij。该厂第j月的正常生产工时为tj，但必要时可加班生产，第j月允许的最多加 班工时不超过tj/,并且加班时间内生产出来的产品每件成本增加额外费用 Cij / 元。若生产出来的产品当月不交货，每件库存 1个月交存储费p元。试为该厂 设计一个保证完成合同交货，又使上半年预期盈利总额为最大的生产计划安排。解：设Xjj为i种产品j月正常时间生产数,56maXzi1j5aij Xijc15aij Xijs.t. i 1j(Xikk1Xij0(sij1cij )xij(sijX；j为加班时间生产数，模型为j,(Xik Xik Dik ) k1cijcij )xij c1pij1tj

32、tjxik)Dikk1(j(j(j宏银公司承诺为某建设项目从 2003 年起的1,L ,6)1,L ,6)1,L ,6)4 年中每年年初分别提供以下数额贷款： 2003年 100万元， 2004年 150万元， 2005 年 120万元， 2006年110 万元。以上贷款资金均需于 2002 年年底前筹集齐。但为了充分发挥这笔资 金的作用，在满足每年贷款额情况下，可将多余资金分别用于下列投资项目： 于2003年年初购买A种债券，期限3年，到期后本息合计为投资额的140% 但限购 60万元； 于2003年年初购买B种债券，期限2年，到期后本息合计为投资额的125%且限购 90 万元； 于2004

33、年年初购买C种债券，期限2年，到期后本息合计为投资额的130% 但限购 50万元； 于每年年初将任意数额的资金存放于银行，年息 4%，于每年年底取出。 求宏银公司应如何运用好这笔筹集到的资金，使 2002年年底需筹集到的资金数 额为最少。解：用Xj（i为第1,2,3年年初，j 1,2,3,4分别为A, B,C, D四类投资数）min z 480(x11x12 x13x14 )(x21 x22x11(1140%)110x1160x12(1125%)120x1290s.t. x23(1130%)110x2350(x11x12x13x14)(14%)100(x21x22x23x24)(14%)150

34、(x31x32x33x34)(14%)120x23x24)(x31x32x33x34)红豆服装厂新推出一款时装， 据经验和市场调查， 预测今后 6 个月对该款时装的需求为： 1 月 3000件， 2月 3600件， 3月 4000 件， 4月 4600 件， 5月 4800件， 6月 5000 件。生产每件需熟练工人工作 4h,耗用原材料150元，售价为240元/件。该厂1月初有熟 练工80人，每人每月工作160h。为适应生产需要，该厂可招收新工人培训，但培训一名新 工人需占用熟练工人 50h 用于指导操作， 培训期为一个月， 结束后即可上岗。 熟练工人每月 工资 2000 元，新工人培训期间

35、给予生活补贴 800 元，转正后工资与生产效率同熟练工人。 又熟练工人（含转正一个月后的新工人）每月初有2%因各种原因离职。已知该厂年初已加工出 400件该款时装作为库存，要求 6月末存库 1000件。又每月生产出来时装如不在当月 交货，库存费用为每件每月 10元。试为该厂设计一个满足各月及 6月末库存要求，又使1 6 月总收入为最大的劳动力安排方案。解：设该厂每月初拥有熟练工人数t（t 1L ,6）,每月招收培训的新工人数为t, 该厂月末库存为t, 一月初库存为。，R为各月对时装的需求数，则数学模型为6maxz（每月销售收入 熟练工人工资 培训工人补助 原材料费 库存费）i1It 1 40x

36、t 12.5yt RtIt It 1 40xt 40yt 1 12.5yt Rts.t.xt 1 0.98xt ytxt,yt 0解得z*=87512元，各月有关数字如下：t123456Xt8082.47106.62130.93128.32125.75yt4.0725.8026.45000it559.3400637.38970.021000第二章线性规划的对偶理论与灵敏度分析写出下列线性规划问题的对偶问题，并以对偶问题为原问题，再写出对偶的对 偶问题。(1) min z2x12x24x3x13x24x322x1x23x33s.t.x14x23x35Xi , X20, X3无约束y12 y2y3

37、2s.t.3y1 y24 y324 y1 3y2 3y34y10, y20, y3无约束对偶的对偶问题：minv 2m1 2m 24mm1 3m 24m322m1 m23m33s.t.m1 4m23m35m1 ,m20,m3无约束(2) max z 5x1 6x23x3x1 2x22x35x1 5x2x33s.t.4x1 7x23x38捲无约束，x20,x30解：对偶问题： min w5y13y2 8y3y1y24y3 5w33y25y32 y1解：对偶问题： maxs.t.2y1 5y27y362y1 3y23y33丫无约束，y20, y30max v5m16m23m3m12m22m30对偶

38、的对偶问题：m1 5m2 3m30s.t.4m1 7m2 3m30无约束，m20, m30n1(3) minzcij xiji1j1nxij ai (i 1,L ,m)j1ms.t. xij bj(j 1,L ,n)i1xij 0 (i 1,L ,m, j 1,L ,n)mn解：对偶问题： maxwai yibj yj mi 1 j 1s.t.yi yj m cij (i 1,L ,m, j 1,L ,n)yi 无限制，i 1,L ,n m对偶的对偶问题：mnminvcij xiji 1 j 1nxijai(i 1,L ,m)j1ms.t.xijbj(j 1,L ,n)i1Xj 0 (i 1,

39、L ,m, j 1L ,n)(4) max zaij1j X jbi(i 1,L,m1 m)ns.t.aij1j X jbi(i m11,m12,L ,m)xj0( j 1,L ,n1n)Xj无:约束( j n11,L ,n)对偶问题：minw b1 y1b2 y2 Lbmymmaijyii1c j ( j1,2,L ,n1)s.t.maijyii1cj (jn1 1,n1 2,Lyi 0( i1,L ,m1)y无约束(jm1 1,L ,m)cjxjn解：ncjxj对偶的对偶问题： max,n)naij Xj b j1i (i1,L,m1m)ns.t.aij Xj bj1i (im11,m12

40、,L ,m)Xj 0( j1,L,n1n)xj无约束(jn11,L,n)j1判断下列说法是否正确，并说明为什么。如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； 答：错误。如果原问题是无界解，则对偶问题无可行解。如果线性规划的对偶问题无可行解，则原问题也一定无可行解； 答：错误。如果对偶问题无可行解，也可能是因为原问题是无界解。在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问 题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；答：错误。如果原问题是求极小，则结论相反。任何线性规划问题具有唯一的对偶问题。答：正确。已知某求极大线性规划问题用单纯形法求解时

41、的初始单纯形表及最终单纯形表如表2-30所示，求表中各括号内未知数(a)(I)的值。Cj T322000Cb基bX1X2X3X4X5X60X4(b)1111000X515(a)120100X6202(c)1001Cj-Zj3220000X45/400(d)(l)-1/4-1/43Xi25/410(e)03/4(i)2X25/201(f)0(h)1/2Cj-Zj0(k)(g)0-5/4(j)解:l=1 , k=0, a=2, c=3,h=-1/2 ,b=10,e=5/4 ,f=-1/2 ,d=1/4 ,g=-3/4 , i=-1/4 , j=-1/4.给出线性规划问题min z 2x1 3x25x3 6x4x1 2x2 3x3x42s.t. 2x1x2 x33x43Xj0( j1,L ,4)写出其对偶问题；用图解法求解对偶问题；利用的结果及根据对偶问 题性质写出原问题最优解。解：其对偶问题为:min w2y13y2Yi2y222yiy23s.t.3y1y25yi3 y26yi 0, y 0图解法求解：8 1 *求得最优解为y18,y2 5,z195(3)根据互补松弛型性质可以得到最优解X*(7 /5,0,1/ 5,0)给出线性规划问题max z3x2x25x3X12 x2X35003x12x3460s.t.X14