运筹学复习题及答案
一、一个毛纺厂用羊毛和涤纶生产A、B、C混纺毛料，生产1单位A、B、C
分别需要羊毛和涤纶3、 2； 1、 1； 4、4单位，三种产品的单位利润分别为4、1、5。每月购进的原料限额羊毛为8000单位，涤纶为3000单位，问此毛纺厂如何安排生产能获得最大利润？（要求：建立该问题的数学模型）
解：设 生产混纺毛料ABC各x1、x2、x3单位
max z＝x1+x2+5x3
3x1+x2+4x3≤8000 2x1+x2+4x3≤3000 x1,x2,x3≥0
二、写出下述线性规划问题的对偶问题
max s=2x1+3x2-5x3+x4
x1+x2-3x3+x4≥5 2x1 +2x3-x4≤4 x2 +x3+x4=6
x1,x2,x3≥0；x4无约束
解：先将原问题标准化为：
max s=2x1+3x2-5x3+x4
-x1-x2+3x3-x4≤-5 2x1 +2x3-x4≤4 x2 +x3+x4=6 x1,x2,x3≥0；x4无约束
则对偶问题为：
min z=-5y1+4y2+6y3
-y1+2y2≥2 -y1+ y2≥3 3y1+ 2y2+y3≥-5 -y1-y2+y3=1 y1,y2≥0,y3无约束
三、求下述线性规划问题
min S =2x1＋3x2－5x3
x1＋x2－3x3 ≥5 2x1 ＋2x3 ≤4 x1，x2，x3≥0
解：引入松弛变量x4，x5，原问题化为标准型：
max Z=-S =-2x1-3x2+5x3
x1＋x2－3x3 －x4=5 2x1 ＋2x3 +x5=4
x1，x2，x3, x4,x5≥0 对应基B0＝（P2,P5）的单纯形表为 5 T(B0)=
4 15 1 1 -3 -1 0 2 0 2 0 1 1 0 -4 -3 0 x1的检验数为正，x1进基，由min｛5/1,4/2｝=4/2知，x5出基，迭代得新基B1=(P2,P1),对应的单纯形表为
3 T(B1)=
2 13 0 1 -4 -1 -1/2 1 0 1 0 1/2 0 0 -5 -3 -1/2 至此，检验数全为非正，已为最优单纯形表。对应的最优解为： x1=2,x2=3,x3=x4=x5=0,max z=-13,故原问题的最优解为： x1=2,x2=3,x3 =0,min s=13。
四、利用大M法求解下面线性规划问题:
maxs??x1?2x2?x3s.t.?2x1?x2?x3??4??6?x1?2x2?x1,x2,x3?0?
解：引入松弛变量x4和人工变量x5，构造如下规划：
maxs??x1?2x2?x3?Mx5s.t.??2x1?x2?x3?x4?4
?x1?2x2?x5?6??x,x,x,x,x?0?123454 6 －2 1 1 1 0 1 2 0 0 1 对应基B0＝（P4,P5）的单纯形表为
T(B0)= 6-1+M 2+2M 1 0 M 0 x1的检验数为-1+ M>0，x1进基，由min｛6/1｝=6/1知，x5出基，迭代得新基B1=(P4,P1),对应的单纯形表为
T(B1)=
16 6 6 0 5 1 1 2 1 2 0 0 1 0 4 1 0 1-M x3的检验数为1>0，x3进基，由min｛16/1｝=16/1知，x4出基，迭代得新基B2=(P3,P1),对应的单纯形表为
16 T(B2)=
6 0 5 1 1 2 1 2 0 0 1 -10 -1 0 -1 0 -1-M 至此，检验数全为非正，已为最优单纯形表。对应的最优解为： x1=6,x2=0,x3=16,x4=x5=0,最优值max z=10。
五、已知线性规划问题(L):
mins?x1?2x2?3x3s.t.?2x1?x2?2x3?6 ?x?3x?2x?8?123?x1,x2,x3?0?(1)写出该问题的对偶表,从而给出其对偶问题(D).
(2)用对偶单纯形法求解问题. 解：(1)该问题的对偶表, x1 x2 x3 1 2 1 2 1 3 3 Min Max 其对偶问题(D)为 max Z=6y1+8y2 2y1+ y2≤1 y1+3y2≤2 2y1+2y2≤3 y1,y2≥0
c b
2 6 y1 2 8 y2 (2)用对偶单纯形法求解问题. 引入松弛变量x4、x5，构造如下规划：
maxZ??S??x1?2x2?3x3s.t.??2x1?x2?2x3?x4??6???x1?3x2?2x3?x5??8?x1,x2,x3,x4,x5?0?
对应基B0＝（P4,P5）的单纯形表为
－6 -2 -1 -2 1 0 T(B0)= －8 -1 -3 -2 0 1 0 -1 -2 -3 0 0 检验数全为非正，基变量x4＝－6，x4出基,利用偶单纯形法，由min｛－1/－2，－
2/-1,-3/-2｝=－1/－2知，x1进基，迭代得新基B1=(P1,P5),对应的单纯形表为
3 1 1/2 1 -1/2 0 T(B1)= －5 0 -5/2 -1 -1/2 1 3 0 -3/2 -2 -1/2 0 基变量x5＝－5，x5出基,利用偶单纯形法知，x2进基，迭代得新基B2=(P1,P2),对应的单纯形表为
2 T(B2)= 2 1 0 4/5 -3/5 1/5 0 1 2/5 1/5 -2/5 6 0 0 -7/5 -1/5 -3/5 至此,得到最优解:x1=x2=2,x3=x4=x5=0,最优值maxZ=-6,故原问题的最优解为: x1=x2=2,x3=0, 最优值minS=6.
六、某运输问题的产销平衡表和运价表如下，试用表上作业法求最优调运方案。
销地 产地 A1 A2 A3 销量 B1 1 0 3 10 B2 2 4 1 10 B3 6 2 5 10 产量 7 12 11 30 解：由最小元素法得初始运输方案 A1 A2 A3 销量 10 10 B1 B2 10 10 B3 7 2 1 10 产量 7 12 11 30 总运费S=0×10＋1×10＋6×7＋2×2＋5×1=61
经计算λ11＝（6＋0）－（2＋1）＝3>0,调整量Δ=min（7,10）＝7， 经调整，得新运输方案： A1 A2 A3 销量 总运费S=61－3×7＝40
至此，所有检验数均以非正，该运输方案已为最优。即：
A1运到B1 7个单位；A2运到B1 3个单位；A2运到B3 9个单位
B1 7 3 10 B2 10 10 B3 9 1 10 产量 7 12 11 30 A3运到B2 10个单位；A3运到B3 1个单位；总运费S＝40个单位
七、某极大化整数规划对应的线性规划的最优单纯形表如下：
5/2 13/4 -69/4 0 1 1/2 -1/2 1 0 -1/4 3/4 0 0 -3/4 -3/4 试建立割平面方程并求原整数规划的最优解。
解：由x2=5/2为非整数，对应方程为：5/2=x2+1/2x3-1/2x4
即：x2－x4-2=1/2-(1/2x3+1/2x4),得Gomery割平面：1/2-(1/2x3+1/2x4)<0 引入松弛变量x5,添加约束： -1/2x3-1/2x4 ＋x5=－1/2,由表 5/2 13/4 -1/2 -69/4 0 1 1/2 -1/2 0 1 0 -1/4 3/4 0 0 0 -1/2 -1/2 1 0 0 -3/4 -3/4 0 利用对偶单纯形法迭代得到新单纯形表： 2 7/2 1 -33/2 0 1 0 -1 1 1 0 0 1 -1/2 0 0 1 1 -2 0 0 0 0 -3/2 由7/2=x1+x4-1/2x5,得Gomery割平面：1/2-1/2x5+<0 引入松弛变量x6,添加约束： -1/2x5 ＋x6=－1/2,由表
2 7/2 1 -1/2 -33/2 0 1 0 -1 1 0 1 0 0 1 -1/2 0 0 0 1 1 -2 0 0 0 0 0 -1/2 1 0 0 0 0 -3/2 0 利用对偶单纯形法迭代得到新单纯形表： 1 4 3 1 -15 0 1 0 -1 0 -2 1 0 0 1 0 -1 0 0 1 1 0 -4 0 0 0 0 1 -2 0 0 0 0 0 -3