WORD整理版 X= 45/11 -11/90 由于X2的值小于0，所以最优解将发生变化 4）P6’=(3/11,-3/4)T σ6=217/20>0

所以对最优解有影响。 5）当C2=6 σ1=-137/33 σ4=4/11 σ5=-17/22

由于σ4大于0所以对最优解有影响

5. 求如图所示的网络的最大流和最小截集(割集)，每弧旁的数字是（cij , fij ）。（15分）

V1 (5,0) (3,3) (3,3) VS （4,1） V2 (4,0)

(9,3) (8,4) V3 Vt (6,0) 最大流为：14

V1 (5,3) (3,3) (3,0) V2 Vs (4,4) (4,1) (9,7) (8,8) Vt V3 (6,6)

6. 考虑如下线性规划问题（20分） Max z=3x1+x2+4x3

s.t. 6x1+3x2+5x3≤9

3x1+4x2+5x3≤8 x1，x2， x3≥0

回答以下问题： 1）求最优解；

2）直接写出上述问题的对偶问题及其最优解；

3）若问题中x2列的系数变为（3，2）T，问最优解是否有变化； 4）c2由1变为2，是否影响最优解，如有影响，将新的解求出。

优质参考资料

WORD整理版 Cj 3 1 4 0 0 CB XB b X1 X2 X3 X4 X5 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) 若问题中x2列的系数变为（3，2）T 则P2’=(1/3,1/5)T σ2=-4/5＜0

所以对最优解没有影响 4）c2由1变为2 σ2=-1＜0

所以对最优解没有影响

7. 求如图所示的网络的最大流和最小截集(割集)，每弧旁的数字是（cij , fij ）。（10分） 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

优质参考资料

WORD整理版

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为：

优质参考资料

WORD整理版

MaxW=2y1-3y2 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

优质参考资料