线性规划练习题

1、&表1.15是一个求极大值线性规划的单纯形表，其中X4, X5, X6是松弛变量。表 1.15q22CbXbbX1X2X3X4X5X60X5212-12X21-11-2X142a-1-a+8c j-1（1）把表中缺少的项目填上适当的数或式子。（2）要使上表成为最优表，a应满足什么条件?（3）何时有无穷多最优解？（4）何时无最优解？（5）何时应以X3替换X1 ？&答案（1）把表中缺少的项目填上适当的数或式子。Cj122000CbXbbX1X2X3X4X5X60X5200121-12X2101-110-21X14102a-10-a+8c j004-2a-10a-4（2）要使上表成为

2、最优表，a应满足22（3）当a=2或a=4时有无穷多最优解（4）当a>8时无最优解（5）当1<a<2时应以X3替换X19. 已知某线性规划的初始单纯形表和最终单纯形表如表1.16 ,请把表中空 白处的数字填上，并指出最优基 B及B-1。表 1.16C2-11000CbXbbX1X2X3X4X5X60X43111000X51-120100X611-1001(T j2-110000X410-1-22X1151/21/2-1X25-1/21/26609 .答案第一表的右端常数向量为10,第二表前四列构成矩阵Id011、101/2 0©1-3/2 0j131 *广1-1-2

3、 A最优基B =01-101/21/21°1b<°-1/21/2 用单纯形法计算时得到的中间某两步的计算见表10. 已知某线性规划问题,1.17，试将空白处填上数字。15/41110.答案 b2 =B b = -6/41-2/418/415/41-12/41-10/418/380/414/4115/41 _20/3 一 .44/41 一14/350/41表 1.17C354000CbXbbX1X2X3X4X5X6X28/32/3101/300X514/3-4/305-2/310X620/35/304-2/301c j-1/304-5/300X2X3X115/41-6/

4、41-2/418/415/41-12/41-10/414/4115/41c j所以表中的数字填写如下表。C354000CbXbbX1X2X3X4X5X65X28/32/3101/3000X514/3-4/305-2/3100X620/35/304-2/301c j-1/304-5/300543X2X3X180/4150/4144/4100110001015/41-6/41-2/418/415/41-12/41-10/414/4115/41c j000-45/41-24/41-11/411某个线性规划的最终表是表1.18表 1.18Cj01-200CbXbbX1X2X3X4X50X113/210

5、0-1/25/21X25/2010-1/23/2-2X31/2001-1/21/2c j000-1/2-1/2初始基变量是X1, X4, X5o(1)求最优基 B= ( P1, P2, P3)； (2)求初始表。11.答案初始基变量是X1, X4, X5o1 - 2 1(1) 最优基B = 01-3<0 1 -1(2)初始表为:C01-200CbXbbX1X2X3X4X50X121-21000X4101-3100X5201-101c j01-2003.写出下列线性规划的对偶问题:(1) max z =3% -x2 x3,+2x2 +x3 兰 4一 +2x2 -4x3 Z1*% X2 +3

6、x3 =1xi > 0, x 0, x3无约束(2) min z = 2x - x2 3x3 x4X + 2x2 _ x3 _ x4 兰 4 -治 + x2 + 2x3 = 22x1+x3 +2x4 3 1、Xi王0,X2乞0,X3,X4无约束 max z = 2x 2x2 3x3 x4+ x2 + x3 + x4 兰 12 2x1 - X2 *3x3= -1x1 一 x3 + x4 兰 3X1 , X 0 , X3 , X4无约束(4) maxz 二 7x -4x2 3x34论 +2x2 6x2 兰 243x -6x2 -4x3 X15 5x2 + 3x3 = 30台£ 0

7、, x3兰0 ,x2无约束(5) maxzp 2x2 3x3 4x4一捲 + x2 - x3 -7x3 = 56x + 7x2 + 3x3 _ 5x4 兰 8 12x 一9x2 9x3 +9x4 兰 30x1 ,x 0 , , x 0 , x4 无约束3答案（1）min w = 4y1 y2 y3”如一y2十y3王32y2目2 - 丫3 - Ty1 -4y2 +3y3 =1y色0 , y2兰0, y3无约束maxw 二 4% 2y2 y3'% - y2 + 2y3 兰 22% + y2z1“ -% +2y2 + y3 =3-y1+2y3=1y10, y2无约束y -0(3) min w

8、 = 12y y2 3y3(4) minw = 24y115y2 30y3y2y2+y3>2yi -y2z 2 yi +3y2 _y3 =3yi5=1yi -。山乞o,y2无约束(5) min w = 5y8y230y3-yi *6y2 +12y31yi +7y2 -9y3 A2«+3y2 _9y3 兰 3-7% -5y2 +9y3 =4 y3 Z 0, y2兰0 , %无约束4yi 3y2- 72yi - 6y25y3 = -4-6y _ 4y2 3y3 乞 3y _ 0, y2乞0 , y3无约束一、下面是某公司关于三个产品生产组合问题的线性规划，其中（2, 5, 8）为产

9、品的价格，（96，40，60）为三个生产车间的能力，其目标函数、约束条件及最优单纯形表 如下：max Z=2x i+5x2+8x36xi+8x2+4x3W 962xi + X2 +2x3 405xi+3x2+2x3W 60Xi, l=1,2,3基变量XiX2X3X4X5X6解fX21/6-1/3X3-1/122/3X6-1/3-1/3（1 ）填完上表，指出原问题与对偶问题最优解。（2）评论每个车间的追加能力对公司的价值。（3 ）若设计部门又提出一个新产品，其预测价格为7,生产单位产品消耗三个车间工时数据为（10, 2, 2）,试问公司是否该考虑其投产，为什么?（答案）：（1）基变量XiX2X3

10、X4X5X6解f19/3001/611/30X21/3101/6-1/308/3X35/601-1/122/3056/3X67/300-1/3-1/3144/3x=(0,8/3,56/3,0,0,44/3),y*=(1/6,11/3,0)(2) 1/6,11/3,0(3) d 4< 0,不投产。有一工厂，由三个车间生产四种产品，三个车间的生产能力分别为（4, 3, 3）（百小时），四种产品价格分别为（2, 4, 1, 1/2）（千元），其产品组合的线性规划为max Z=2x 1+4X2+X3+1/2X4xi+3x2+X4W 42xi +X2w 3X2+4X3+X4 3Xi, i=1,2,

11、3,4设X5,X6,X7依次为以上三个不等式的松弛变量，以下是该问题的不完全表:基变量X1X2X3X4X5X6X7解fX22/5-1/50X1-1/53/50X3-1/10-1/201/4(1) 完成上表；(2) 在保持最优基不变的情况下，产品1的价格可以增加多少？(3) 从外厂调剂给而车间2百小时的生产能力， 但每百小时需支付 0.4千元，这种调剂可以接受吗？若可以接受，能净增加多少收入?(答案)：(1)基变量X1X2X3X4X5X6X7解f00017/2011/109/201/4X20102/52/5-1/50X1100-1/5-1/53/50X30013/20-1/101/201/4 5

12、/4 w cK 15/2 ;(3)可以接受，净增0.1千元。八、已知线性规划问题为min Z=8x 1+6x2+3x 3+6x4X1+2X2+X433X1 +X2 + X3+X46X3+X42X1+ X32Xi0, i=1,2,3,4 解：对偶问题为max W=3y 1+6y2+2y3+2y4yi+3y2+y4w 82y1+y2w 6y2 + y3 + y4W 3y1 +y2 +y3 w 6yi0, i=1,2,3,4九、已知线性规划问题为max Z=2x 1+4X2+X3+X4X1+3X2+ X4W 82x1 +X2w 6(1) 写出其对偶问题(2) 已知原问题的最优解为x*=(1,1,2,

13、0)试根据对偶 理论直接求出对偶问题的最优解。(2)根据互补松弛定理，由X1 , X2 ,X3> 0有y1+3y2+y4=82y什y2=6y2 + y3 + y4=3解得Y=(2,2,1,0),此解也满足对偶约束条件4,因此为对偶问题可行解其对应的目标函数为w=3 X 2+6X 2+2=20=Z*所以Y=(2,2,1,0)为对偶问题的最优解。(1)写出其对偶问题(2 )已知原问题的最优解为x =(2,2,4,0)试根据对偶理论直接求出对偶问题的最优解。X2 + X3 + X4= 6Xi + X2 + X3 w 9Xi0, i=1,2,3,4解： (1)对偶问题为min W=8y 1+6y2+6y3+9y4y1+2y2+y4w 83y1+y2 +y3 + y4w 6 y3 + y4w 3 y1+ y3w 6yi0, i=1,2,3,