3）若问题中 x2列的系数变为（3，2）T，问最优解是否有变化； 4）c2由 1
变为 2，是否影响最优解，如有影响，将新的解求出。
Cj CB 0 0 Cj-Zj 0 4 Cj-Zj 3 4
Cj-Zj最优解为 X1=1/3,X3=7/5,Z=33/5 2对偶问题为Minw=9y1+8y2 6y1+3y2≥3
对偶问题最优解为 y1=1/5,y2=3/5 3若问题中 x2列的
3y1+4y2≥1 5y1+5y2≥4 y1,y2≥0
系数变为（3，2）T则P2’=(1/3,1/5
σ2=-4/5＜0所以对最优解没有影响 4）c2由 1
变为2 σ2=-1＜0所以对最优解没有影响 7.求如图所示的网络的最大流和最小截集
）。
（10分） V1 (9,5 (4,4 V3 (6,3 T 3 XB X4 X5
(割集，每弧旁的数字是（cij , fij
b 9 8 X1 6 3 3 X4 X3 1 8/5 3 3/5 3/5 X1 X3 1/3 7/5 1 0 0 1 X2 3 4 1 -1 4/5 -11/5 -1/3 1
2 4 X
3 5 5
4 0 1 0 0 1 0 0 X4 1 0 0 1 0 0 1/3 -1/
5 -1/5 0 X5 0 1 0 -1 1/5 -4/5 -1/3 2/5
解： (5,4 (7,5 V4 V1 (9,7 (4,4 V3 (6,4 (3,2 Vs (5,4 (4,0 Vt
VS (3,1 (3,0 (4,1 Vt (5,3 V2
(7,7 6/9
V2最大流＝11 (5,5 V4 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元，最优计划的变化为：
）产品Ⅰ的利润在[6,15]变化
X*=(x1,x2,x3,x4,x5,x6’=(175/6,275/6,25,0,0,0’ Z*=775 3
时，原最优计划保持不变。
4）设备 A的能力在[60,150]变化时，最优基变量不
变。
5）新产品值得生产。
6）最优计划的变化为：
给出成性规划问题： (15
X*=(x1,x2,x3,x4,x5,x6’=(190/6,350/6,10,0,0,60 ’ Z*=706.7 9.
分 7/9
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
用图解法求得 LD的最优解为：
y1-2y2≤2 2y1+y2≤3 y1+3y2≤6 y1≥0,y2≤0 2
-1/5’ 3由互补松弛定理：原问题的最优解为：
Y*=(y1,y2’=(8/5,
某部门有 3个生产同类产品的工厂(产地，生产的产
X*=(x1,x2,x3’=(8/5,1/5,0’ 10.
品由 4个销售点(销地出售，各工厂的生产量， W*=19/5各销售点的销售量(单位.t
以及各工厂到各销售点的单位运价(元/t示于下表中，要求研究产品如何调运才能
产销使总运量最小？(10分 B1 B2 B3 B4产量 A1 4 12 4 11 32 A2 2 10 3 9 20 A3 8 5 11 6 44 96╲96销量 16 28 28 24解：最优调运方案为： A1-B3和 B4 A2-B1和 B4
A3-B2和 B4 28t和 4t 16t和 4t 28t和 16t 8/9
最小总运费为：460元 11.求解下列 0-1规划问题 maxz=3x1+2x2-5x3-2x4+3x5 x1+x2+x3+2x4+x5≤4 7x1+3x3-4x4+3x5≤8 11x1-6x2+3x4-3x 5≥3 xj=0或1 (j=1,…，5解：最优解为：x1=x2=1，其他为 0，最优目标函数值为 5 9/9。