文档详情

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

发布:2017-12-22约6.02千字共12页下载文档
文本预览下载声明
习题二 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
显示全部
相似文档