运筹学复习题解答.ppt

* 运筹学复习 题及其解答 1：某药厂生产A、B、C三种药物，可供选择的原料有甲、乙、丙、丁，四种原料的成本分别是5元，6元，7元，8元。每公斤不同原料所能提取的各种药物的数量（单位：克/公斤）见下表 药厂要求每天生产A药恰好100克，B药至少530克，C药不超过160克，要求选配各种原料的数量既满足生产需要，又使总成本最小，试建立此问题的数学模型。 不超过160克 至少530克 恰好100克 生产量 8 7 6 5 成本（元/kg） 2 6 1 丁 1 5 1 丙 1 4 1 乙 2 5 1 甲 C B A 药名 原料 解：设 x1 , x2 , x3 , x4 分别为原料甲、乙、丙、丁的选配数量（单位：公斤），则有 min z =5x1+6x2+7x3+8x4 s . t . x1+ x2+ x3+ x4 = 100 5x1+4 x2+5 x3+ 6 x4 ? 530 2x1+ x2+ x3+ 2 x4 ? 160 x1 , x2 , x3 , x4 ? 0 2：用单纯形法求解线性规划问题 解：化为标准形为 0 0 0 1 –1 2 0 ? 1 0 0 – 1 1 1 20 x6 0 0 1 0 2 – 1 1 10 x5 0 0 0 1 1 1 3 60 x4 0 x6 x5 x4 x3 x2 x1 B-1b XB CB ? 0 0 0 1 –1 2 C 20 10 20 0 0 0 1 –1 2 0 ? 1 0 0 – 1 1 1 20 x6 0 0 1 0 2 – 1 1 10 x1 2 0 0 1 1 1 3 60 x4 0 0 30 4 -5 -3 0 10 2 -3 -1 0 1 -3 -2 20 7.5 5 ? 1 –1 0 – 3 2 0 10 x2 -1 0 1 0 2 – 1 1 10 x1 2 0 –3 1 – 5 4 0 30 x4 0 1 5 -1.5 -0.5 0.5 15 0 0.5 0.5 0.5 10 0 1 -1 -2 25 0 0 0 -1.5 -1.5 -0.5 所以，所求最优解为, x1=15 , x2=5 , x3=0 , x4=10 , x5=x6=0 最优值为：z*=25 3 ： 用大M法计算下列线性规划 max z = 2x1 + 3x2 s.t. 2x1 + x2 ? 16 x1 + 3x2 ? 20 x1 + x2 = 10 x1, x2 ? 0 解：化为标准形并加入人工变量为： max z = 2x1 + 3x2 - Mx5 - Mx6 s.t. 2x1 + x2 + x4 = 16 x1 + 3x2 - x3 + x5 = 20 x1 + x2 + x6= 10 x1, x2 , x3 , x4 , x5 , x6 ? 0 -M-3 -M 0 0 0 -1 30 ?j 3 -1 0 1 0 1 10 x3 0 1 0 0 0 1 2 10 x2 3 -1 0 1 0 0 1 6 x4 0 x6 x5 x4 x3 x2 x1 B-1b XB CB -M -M 0 0 3 2 cj 最优解为(0，10)T , 最优值为 z* = 30 4： 利用两阶段法计算下题： max z = 30x1+40x2?100x3 s.t. 4x1+3x2 ?x3=30 x1+3x2 ?x3=12 x1, x2 , x3 ? 30 第一阶段：m in z = x4+ x5 s.t. 4x1+3x2 ?x3 + x4 =30 x1+3x2 ?x3 + x5 =12 x1, x2 , x3 , x4 , x5 ? 30 ? ?1 ?1 0 0 0 C x5 x4 x3 x2 x1 b XB CB 10 0 1 ? 1 3 4 30 x4 ?1 4 1 0 ? 1 3 1 12 x5 ?1 0 0 2 6 5 ? 42 ?j 6 ?1 1 0 0 3 18 x4