运筹学(第3版) 习题答案 26
（9）什么是基本解、可行解、基本可行解、基本最优解，这四个解之间有何关系。 （10）简述线性规划问题检验数的定义及其经济含义。
返回顶部
运筹学(第3版) 习题答案 27
第2章 线性规划的对偶理论
2.1某人根据医嘱，每天需补充A、B、C三种营养，A不少于80单位，B不少于150单位，C不少于180单位．此人准备每天从六种食物中摄取这三种营养成分．已知六种食物每百克的营养成分含量及食物价格如表2-22所示．（1）试建立此人在满足健康需要的基础上花费最少的数学模型；（2）假定有一个厂商计划生产一中药丸，售给此人服用，药丸中包含有A，B，C三种营养成分．试为厂商制定一个药丸的合理价格，既使此人愿意购买，又使厂商能获得最大利益，建立数学模型．
含量 食物 营养成分 A B C 食物单价（元/100g） 一 13 24 18 0.5 二 25 9 7 0.4 表2-22 三 14 30 21 0.8 四 40 25 34 0.9 五 8 12 10 0.3 六 11 15 0 0.2 需要量 ≥80 ≥150 ≥180 【解】（1）设xj为每天第j种食物的用量，数学模型为
minZ?0.5x1?0.4x2?0.8x3?0.9x4?0.3x5?0.2x6?13x1?25x2?14x3?40x4?8x5?11x6?80?24x?9x?30x?25x?12x?15x?150?123456??18x1?7x2?21x3?34x4?10x5?180??x1、x2、x3、x4、x5、x6?0（2）设yi为第i种单位营养的价格，则数学模型为
maxw?80y1?150y2?180y3?13y1?24y2?18y3?0.5?25y?9y?7y?0.4123??14y1?30y2?21y3?0.8??40y1?25y2?34y3?0.9?8y?12y?10y?0.323?1?11y1?15y2??0.2??y1,y2,y3?0
2.2写出下列线性规划的对偶问题
运筹学(第3版) 习题答案 28
?y1?2y2?1?x1?3x2?5x3?10?（1）? 【解】?3y1?y2?3 ?2x1?x2?x3?4??x,x,x?0?5y1?y2?2?123??y1,y2?0minw?15y1?10y2maxZ?2x1?x2?x3?y1?y2?2?x1?2x2?4x3?15?（2）? 【解】?2y1?3y2?1 ??x1?3x2?x3?10??x,x?0,x无约束??4y1?y2?13?12??y1无约束；y2?0min?x1?3x2?2x3maxw?10y1?4y2?10y1?7y2?4y3?2?10x1?x2?x3?4x4?14?y?6y?8y?1123?（3）?7x1?6x2?2x3?5x4?20 【解】? ????y1?2y2?6y3??44x?8x?6x?x＝9234?1??4y?5y?y?3123???x1,x2?0,x3无约束，x4?0??y1?0,y2?0,y3无约束maxZ?2x1?x2?6x3?7x4maxZ?2x1?x2－4x3?3x4minw?14y1?20y2?9y3maxZ?2x1?x2?6x3?7x4?3x1?2x2?x3?6x4?12?3x1?2x2?x3?6x4?12?6x?5x?x?634?6x?5x?x?6?1134（4）? 【解】????x1?2x2?x3?2x4??2
?x?2x?x?2x??2?1?234?8?x?20?x1?81??x1?20???x1?0，x2,x3,x4无约束??x1?0，x2,x3,x4无约束minw?12y1?6y2?2y3+8y4?20y5?3y1?6y2?y3?y4?y5?2??2y?2y?113对偶问题为： ? ?y?5y?y??6?123??6y?y?2y?7123???y1?0,y2?0，y3,?0，y4?0，y5?02.3考虑线性规划
minZ?12x1?20x2?x1?4x2?4?x?5x?2?12??2x1?3x2?7??x1,x2?0
运筹学(第3版) 习题答案 29
(1)说明原问题与对偶问题都有最优解；
(2)通过解对偶问题由最优表中观察出原问题的最优解；
－
(3)利用公式CBB1求原问题的最优解； (4)利用互补松弛条件求原问题的最优解． 【解】(1)原问题的对偶问题为
maxw?4y1?2y2?7y3?y1?y2?2y3?12??4y1?5y2?3y3?20?y?0,j?1,2,3?j
容易看出原问题和对偶问题都有可行解，如X＝(2，1)、Y＝(1，0，1)，由定理2.4知都有最优解。
(2)对偶问题最优单纯形表为 C(j) Basis y3 y1 C(j)-Z(j) C(i) 7 4 4 y1 0 1 2 y2 -1/5 7/5 7 y3 1 0 0 y4 4/5 -3/5 0 y5 -1/5 R. H. S. 28/5 2/5 0 -11/5 0 -16/5 -1/5 4/5 w=42.4 对偶问题的最优解Y＝(4/5,0,28/5)，由定理2.6，原问题的最优解为X=(16/5，1/5)，Z＝42.4
1?1??4?4???5?55?5??1（3）CB=(7,4),B???, X?(7,4)???(16/5,1/5)
??32???32????55???55??(4)由y1、y3不等于零知原问题第一、三个约束是紧的，解等式
?x1?4x2?4 ?2x?3x?7?12得到原问题的最优解为X=(16/5，1/5)。
2.4证明下列线性规划问题无最优解
minZ?x1?2x2?2x3?2x1?x2?2x3?3 ?x?2x?3x?2?123?x,x?0,x无约束3?12证明：首先看到该问题存在可行解，例如x=(2,1,1)，而上述问题的对偶问题为
maxw?3y1?2y2?2y1?y2?1?y?2y??2 ?12???2y1?3y2??2??y2?0,y1无约束运筹学(第3版) 习题答案 30
由约束条件①②知y1≤0，由约束条件③当y2≥0知y1≥1，对偶问题无可行解，因此原问题也无最优解(无界解)。
2.5已知线性规划
maxZ?15x1?20x2?5x3?x1?5x2?x3?5?5x?6x?x?6 ?123??3x1?10x2?x3?7??x1?0,x2?0,x3无约束的最优解X?(,0,1419T)，求对偶问题的最优解． 4【解】其对偶问题是：
minw?5y1?6y2?7y3?y1?5y2?3y3?15?5y?6y?10y?20 ?123??y1?y2?y3?5??y1,y2,y3?0由原问题的最优解知，原问题约束③的松弛变量不等于零(xs3?0)，x1、x3不等于零，则对偶问题的约束①、约束③为等式，又由于xs3?0知y3＝0；解方程
?y1?5y2?15 ?y?y?5?12得到对偶问题的最优解Y=(5/2,5/2,0)；w＝55/2＝27.5
2.6用对偶单纯形法求解下列线性规划
（）1minZ?3x1?4x2?6x3?x1?2x2?3x3?10??2x1?2x2?x3?12?x,x,x?0?123
【解】将模型化为
minZ?3x1?4x2?6x3??x1?2x2?3x3?x4??10 ???2x1?2x2?x3?x5??12?x?0,j?1,2,3,4,5?j对偶单纯形表： cj CB XB 3 X1 4 X2 6 X3 0 X4 0 X5 b