至此，已得到整数解：x1=4,x2=1,x3=3,x4=0,最优值为15。

八、线性规划问题如下：

max s= -x1+2x2

-x1+x2≤2………………资源1 x1+2x2≤6………………资源2 x1，x2≥0

（1） 用单纯形法求最优解； （2） 资源1的影子价格；

（3） 资源2由目前的6变为8，最优值会发生怎样的变化，最优解是多少? （4） 对c2进行灵敏度分析。

解：(1)引入松弛变量x3,x4,原问题化为标准型：

max s=-x1+2x2 -x1+x2＋x3 ＝2 x1+2x2 ＋x4＝6 x1，x2 ，x3 ，x4≥0

对应基B0＝（P3P4）的单纯形表 2 T(B0)=

6 0 -1 1 1 0 1 2 0 1 -1 2 0 0 迭代得到新基B1＝（P2P4）,对应的单纯形表为： 2 T(B1)=

2 －4 -1 1 1 0 3 0 -2 1 1 0 -2 0 迭代得到新基B2＝（P2P1）,对应的单纯形表为： 8/3 T(B2)=

2/3 -14/3 0 1 1/3 1/3 1 0 -2/3 1/3 0 0 -4/3 -1/3 至此，检验数已经请为非正，得原问题得最优解： x1=2/3,x2=8/3,最优值maxS＝14/3.

（2）由最优单纯形表T(B2)得知资源1的影子价格为松弛变量x3的检验数的负数，

即为4/3。

（3）因为最优基B= B2的逆矩阵为

B=

所以，

Bb=

-1

-1

1/3 1/3 -2/3 1/3 2 8

1/3 1/3 -2/3 1/3

＝

10/3 4/3

>0

故最优基不变，最优解改变为：x1＝4/3,x2=10/3,对应的最优值为16/3。 （4）设c2的摄动量为δ，最优基不变。

此时，C=(-1,2+δ,0,0),CB=(2+δ,-1),由C -CBB-1A≤0,得 4＋δ≥0 1＋δ≥0

因此δ≥－1，即c2＝2+δ≥1，故当c2在[1,+∞)变化时,最优基不变,生产计划

不变.

九、某物资的产销平衡表及运价表如下，求总运费最省的调运方案。 平衡表 运价表(百元/吨)

销地 产地 产量 B1 B2 B3 B4 (吨) 3 5 7 B1 B2 B3 B4 2 5 9 8 1 9 2 6 7 5 4 3 A1 A2 A3 销量(吨) 6 3 2 4 15 解:利用最小元素法得到初始可行解(运输方案)

销地 产地 产量 B1 B2 B3 B4 (吨) A1 1 2 3 A2 5 5 A3 1 2 4 7 销量(吨) 6 3 2 4 15 对应的总运费s0=1×2+2×5＋5×1＋1×5＋2×4＋4×3=42(百元) 利用位势法计算检验数λij=cij-(ui+vj),如下: B1 B2 B3 B4 ui A1 5 5 0 A2 5 -1 4 -1 A3 5 0 vj 2 5 4 3 检验数λ23=c23-(u2+v3)=2-(4-1)=-1,表中不是最优运输方案,需调整,调整量为δ

=min={2,2,5}=2,新运输方案为:

销地 产地 产量 B1 B2 B3 B4 (吨) A1 3 0 3 A2 3 2 5 A3 3 4 7 销量(吨) 6 3 2 4 15 对应的总运费s1=3×2+0×5＋3×1＋3×5＋2×2＋4×3=40(百元)或s1=s0+λ23δ=42-1×2=40(百元)

利用位势法计算检验数λij=cij-(ui+vj),如下: B1 B2 B3 B4 ui A1 5 5 0 A2 5 4 -1 A3 5 2 0 vj 2 5 3 3 此时,检验数全为非负, 表中已是最优运输方案, 总运费为40百元. 十、利用割平面法,求下面问题:

maxs?2x1?x2s.t.x1?x2?6? ?x?4x?3?12?x,x?0且均为整数2?1

解：引入松弛变量x3，x4，构造辅助LP：

maxs?2x1?x2s.t.?x1?x2?x3?6

??x1?4x2?x4?3?x,x,x,x?0?12346 T(B0)=

3 0 1 1 1 0 1 －4 0 1 2 1 0 0 对应基B0＝（P3P4）的单纯形表

迭代得到新基B1＝（P3P1）,对应的单纯形表为：

3 T(B1)= 3 0 5 1 －1 1 －4 0 1 －6 0 9 0 －2 迭代得到新基B2＝（P2P1）,对应的单纯形表为： 3/5 T(B2)= 27/5 0 1 1/5 －1/5 1 0 4/5 1/5 －57/5 0 0 -9/5 －1/5 检验数已经全为非正，得到辅助LP的最优单纯形表，由于解不是整数，所以不是原整数规划问题的解.对应第二个方程的Gomery割平面： 2/5－（4/5x3＋1/5x5）<0

引入松弛变量x5,添加约束： -4/5x3-1/5x4 ＋x5=－1/5,由表

3/5 27/5 -2/5 0 1 1/5 －1/5 0 1 0 4/5 1/5 0 0 0 -4/5 -1/5 1 －57/5 0 0 -9/5 －1/5 0 利用对偶单纯形法迭代得到新单纯形表：

1 5 2 0 1 1 0 －1 1 0 0 0 1 0 0 －4 1 －5 －11 0 0 －1 0 －1 至此，得到原整数规划的最优解：x1＝5，x2＝1，最优值为maxS=11.