熊伟编《运筹学》习题二详细解答.doc

习题二 1．某人根据医嘱，每天需补充A、B、C三种营养，A不少于80单位，B不少于150单位，C不少于180单位．此人准备每天从六种食物中摄取这三种营养成分．已知六种食物每百克的营养成分含量及食物价格如表2-22所示．（1）试建立此人在满足健康需要的基础上花费最少的数学模型；（2）假定有一个厂商计划生产一中药丸，售给此人服用，药丸中包含有A，B，C三种营养成分．试为厂商制定一个药丸的合理价格，既使此人愿意购买，又使厂商能获得最大利益，建立数学模型． 表2-22 含量 食物 营养成分 一 二 三 四 五 六 需要量 A 13 25 14 40 8 11 ≥80 B 24 9 30 25 12 15 ≥150 C 18 7 21 34 10 0 ≥180 食物单价（元/100g） 0.5 0.4 0.8 0.9 0.3 0.2 【解】（1）设xj为每天第j种食物的用量，数学模型为 （2）设yi为第i种单位营养的价格，则数学模型为 2．写出下列线性规划的对偶问题 （1） 【解】 （2） 【解】 （3） 【解】 （4） 【解】 对偶问题为： 3．考虑线性规划 (1)说明原问题与对偶问题都有最优解； (2)通过解对偶问题由最优表中观察出原问题的最优解； (3)利用公式CBB－1求原问题的最优解； (4)利用互补松弛条件求原问题的最优解． 【解】(1)原问题的对偶问题为 容易看出原问题和对偶问题都有可行解，如X＝(2，1)、Y＝(1，0，1)，由定理2.4知都有最优解。 (2)对偶问题最优单纯形表为 C(j) 4 2 7 0 0 R. H. S. Basis C(i) y1 y2 y3 y4 y5 y3 7 0 -1/5 1 4/5 -1/5 28/5 y1 4 1 7/5 0 -3/5 2/5 4/5 C(j)-Z(j) 0 -11/5 0 -16/5 -1/5 w=42.4 对偶问题的最优解Y＝(4/5,0,28/5)，由定理2.6，原问题的最优解为X=(16/5，1/5)，Z＝42.4 （3）CB=(7,4),, (4)由y1、y3不等于零知原问题第一、三个约束是紧的，解等式 得到原问题的最优解为X=(16/5，1/5)。 4．证明下列线性规划问题无最优解 证明：首先看到该问题存在可行解，例如x=(2,1,1)，而上述问题的对偶问题为 由约束条件①②知y1≤0，由约束条件③当y2≥0知y1≥1，对偶问题无可行解，因此原问题也无最优解(无界解)。 5．已知线性规划 的最优解，求对偶问题的最优解． 【解】其对偶问题是： 由原问题的最优解知，原问题约束①等于零，x1、x2不等于零，则对偶问题的约束①、约束③为等式，y1＝0；解方程 得到对偶问题的最优解Y=(5/2,5/2,0)；w＝55/2＝27.5 6．用对偶单纯形法求解下列线性规划 【解】将模型化为 对偶单纯形表： cj 3 4 5 0 0 CB XB X1 X2 X3 X4 X5 b 0 0 X4 X5 －1 [－2] －2 －2 －3 －1 1 0 0 1 －8 －10 C(j)-Z(j) 3 4 5 0 0 0 0 3 X4 X1 0 1 [－1] 1 －5/2 1/2 1 0 －1/2 －1/2 －3 5 C(j)-Z(j) 0 1 7/2 0 3/2 0 5 3 X2 X1 0 1 1 0 5/2 －2 －1 1 1/2 －1 3 2 C(j)-Z(j) 0 0 1 1 1 b列全为非负，最优解为x＝(2，3，0)；Z＝18 【解】将模型化为 3 4 0 0 b XB CB X1 X2 X3 X4 X3 0 [-1] -1 1 0 -4 X4 0 2 1 0 1 2 Cj－Zj 3 4 0 0 　 X1 3 1 1 -1 0 4 X4 0 0 [-1] 2 1 -6 Cj－Zj 0 1 3 0 　 X1 3 1 0 1 1 -2 X2 4 0 1 -2 -1 6 Cj－Zj 0 0 5 1 　 出基行系数全部非负，最小比值失效，原问题无可行解。 【解】将模型化为 cj 2 4 0 0 0 b XB CB X1 X2 X3 X4 X5 X3 0 2 3 1 0 0 24 X4 0 -1 -2 0 1 0 -10 X5 0 -1 [-3] 0 0 1 -15 Cj－Zj 2 4 0 0 0 　 X3 0 1 0 1 0 1 9 X4 0 -1/3 0 0 1 －2/3 0 X2 4 1/3