0 X4 9 6 3 5 1 0 0 X5 8 3 4 5 0 1 Cj-Zj 3 1 4 0 0 0 X4 1 3 -1 0 1 -1 4 X3 8/5 3/5 4/5 1 0 1/5 Cj-Zj 3/5 -11/5 0 0 -4/5 3 X1 1/3 1 -1/3 0 1/3 -1/3 4 X3 7/5 0 1 1 -1/5 2/5 Cj-Zj 0 -2 0 -1/5 -3/5 最优解为X1=1/3,X3=7/5,Z=33/5 2)对偶问题为 Minw=9y1+8y2 6y1+3y2≥3
3y1+4y2≥1 5y1+5y2≥4 y1,y2≥0
对偶问题最优解为y1=1/5,y2=3/5
3) 若问题中x列的系数变为（3，2）T
2 则PT2’=(1/3,1/5) σ2=-4/5＜0
所以对最优解没有影响 4）c2由1变为2 σ2=-1＜0
所以对最优解没有影响
7. 求如图所示的网络的最大流和最小截集(割集)，每弧旁的数字是（cij , f V1 (4,4 ) V3
(9,5) (6,3)
VS (3,1) (3,0) (4,1) Vt
(5,3) (7,5) V2 (5,4) V4
解：
V1 (4,4) V3 (9,7) (6,4) (3,2) (4,0) Vs Vt (5,4) (7,7)
V2 (5,5) V4 最大流＝11
6 / 8
ij ）。（10分） 8. 某厂Ⅰ、Ⅱ、Ⅲ三种产品分别经过A、B、C三种设备加工。已知生产单位各种产品所需的设备台时，设备的现有加工能力及每件产品的预期利润见表： Ⅰ Ⅱ Ⅲ 设备能力(台.h) A 1 1 1 100 B 10 4 5 600 C 2 2 6 300 单位产品利润10 6 4 (元) 1)建立线性规划模型，求获利最大的产品生产计划。(15分) 2)产品Ⅲ每件的利润到多大时才值得安排生产？如产品Ⅲ每件利润增加到50/6元，求最优计划的变化。(4分)
3)产品Ⅰ的利润在多大范围内变化时，原最优计划保持不变。(2分) 4)设备A的能力在什么范围内变化时，最优基变量不变。(3分)
5)如有一种新产品，加工一件需设备A、B、C的台时各为1、4、3h，预期每件为8元，是否值得生产。(3分)
6)如合同规定该厂至少生产10件产品Ⅲ，试确定最优计划的变化。(3分) 解：1）建立线性规划模型为： MaxZ=10x1+6x2+4x3 x1+x2+x3≤100 10x1+4x2+5x3≤600 2x1+2x2+6x3≤300 xj≥0,j=1,2,3
获利最大的产品生产计划为：X*=(x1,x2,x3,x4,x5,x6)’=(100/3,200/3,0,0,0,100)’ Z*=2200/3 2）产品Ⅲ每件利润到20/3才值得生产。如果产品Ⅲ每件利润增加到50/6元，最优计划的变化为：X*=(x1,x2,x3,x4,x5,x6)’=(175/6,275/6,25,0,0,0)’ Z*=775 3）产品Ⅰ的利润在[6,15]变化时，原最优计划保持不变。 4）设备A的能力在[60,150]变化时，最优基变量不变。 5）新产品值得生产。
6）最优计划的变化为：X*=(x1,x2,x3,x4,x5,x6)’=(190/6,350/6,10,0,0,60 )’ Z*=706.7
9. 给出成性规划问题：(15分) Min z=2x1+3x2+6x3
x1+2x2+x3≥2 -2x1+x2+3x3≤-3 xj≥0 j=1,?，4 要求：
(1)写出其对偶问题。(5分)
(2)利用图解法求解对偶问题。(5分)
(3)利用(2)的结果，根据对偶问题性质写出原问题最优解。(5分) 解：1）该问题的LD为： MaxW=2y1-3y2
7 / 8
y1-2y2≤2 2y1+y2≤3 y1+3y2≤6 y1≥0,y2≤0
2)用图解法求得LD的最优解为：Y*=(y1,y2)’=(8/5,-1/5)’ W*=19/5 3)由互补松弛定理：
原问题的最优解为：X*=(x1,x2,x3)’=(8/5,1/5,0)’
10. 某部门有3个生产同类产品的工厂(产地)，生产的产品由4个销售点(销地)出售，各工厂的生产量，各销售点的销售量(单位.t)以及各工厂到各销售点的单位运价(元/t)示于下表中，要求研究产品如何调运才能使总运量最小？(10分) B1 B2 B3 B4 产量 产 销 A1 4 12 4 11 32 2 10 3 9 20 A2 8 5 11 6 44 A3 销量 16 28 28 24 96╲96 解：最优调运方案为： A1-B3和B4 28t和4t A2-B1和B4 16t和4t A3-B2和B4 28t和16t 最小总运费为：460元
11. 求解下列0-1规划问题 maxz=3x1+2x2-5x3-2x4+3x5
x1+x2+x3+2x4+x5≤4 7x1+3x3-4x4+3x5≤8 11x1-6x2+3x4-3x5≥3
xj=0或1 (j=1,?，5)
解：最优解为：x1=x2=1，其他为0 ，最优目标函数值为5
8 / 8
相关推荐：
loading