运筹学习题及答案

第一章（39页）

1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。 （1）max zx1x2 5x1+10x250

x1+x21 x24 x1，x20

（2）min z=x1+1.5x2

x1+3x23 x1+x22 x1，x20

（3）max z=2x1+2x2

x1-x2-1

-0.5x1+x22

x1，x20

（4）max z=x1+x2

x1-x20

3x1-x2-3

x1，x20

解： （1）（图略）有唯一可行解，max z=14 （2）（图略）有唯一可行解，min z=9/4 （3）（图略）无界解 （4）（图略）无可行解

1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。

（1）min z=-3x1+4x2-2x3+5x4 4x1-x2+2x3-x4=-2

x1+x2+3x3-x414

-2x1+3x2-x3+2x42

x1，x2，x30，x4无约束

（2）max snmzkpk

zkaikxik

i1k1xk1mik1(i1,...,n)

xik0 (i=1…n; k=1,…,m)

（1）解：设z=-z,x4=x5-x6, x5,x60 标准型：

Max z=3x1-4x2+2x3-5(x5-x6)+0x7+0x8-Mx9-Mx10 s. t .

-4x1+x2-2x3+x5-x6+x10=2

x1+x2+3x3-x5+x6+x7=14

-2x1+3x2-x3+2x5-2x6-x8+x9=2

x1,x2,x3,x5,x6,x7,x8,x9,x100

初始单纯形表: 3 cj CB XB -4 x2 2 x3 -5 x5 5 x6 0 x7 0 x8 -M -M x9 x10 i b 2 14 x1 -M 0 x10 x7 -4 1 1 1 -2 3 1 -1 -1 1 0 1 0 0 0 0 1 0 2 14 -M x9 2 -2 [3] -1 2 -2 0 -1 1 0 0 2/3 -z 4M 3-6M 4M-4 2-3M 3M-5 5-3M 0 -M 0 (2)解：加入人工变量x1，x2，x3，…xn，得： Max s=(1/pk)i1nk1mikxik-Mx1-Mx2-…..-Mxn

s.t.

xixik1 (i=1,2,3…,n)

k1mxik0, xi0, (i=1,2,3…n; k=1,2….,m)

CB M是任意正整数 初始单纯形表： --M … -a11cj pkM M b … XBxnx11 x1x2 1 1 … 1 nM 1 0 0 1 … … 0 0 0 0 … 0 1 … 0 … … … … 1 0 … 0 a11 Ma12pk … … a1mpk … an1… pk an2pk … … amnpk i x12 x1m xn1 xn2 xnm -M -M … -M -s x1 x2 1 0 … 0 a12M… … … … … … 0 a1mM… 0 … 0 … … … 1 … an1M0 0 … 1 an2M… … … … … 0 0 … 1 amnM … xn pkpkpkpkpkpk 1.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标函数，确定最优解。 （1）max z=2x1+3x2+4x3+7x4 2x1+3x2-x3-4x4=8 x1-2x2+6x3-7x4=-3

x1,x2,x3,x40

(2)max z=5x1-2x2+3x3-6x4

x1+2x2+3x3+4x4=7

2x1+x2+x3+2x4=3

x1x2x3x40

（1）解：

系数矩阵A是：

23141267 令A=(P1，P2，P3，P4)

P1与P2线形无关，以（P1，P2）为基，x1，x2为基变量。

有 2x1+3x2=8+x3+4x4 x1-2x2=-3-6x3+7x4 令非基变量x3，x4=0 解得：x1=1；x2=2

基解X(1)=（1，2，0，0)T为可行解

z1=8

同理，以（P1，P3）为基，基解X(2)=（45/13，0，-14/13，0)T是非可行解； 以（P1，P4）为基，基解X(3)=（34/5，0，0，7/5)T是可行解，z3=117/5； 以（P2，P3）为基，基解X(4)=（0，45/16，7/16，0)T是可行解，z4=163/16； 以（P2，P4）为基，基解X(5)=（0，68/29，0，-7/29)T是非可行解； 以（P4，P3）为基，基解X(6)=（0，0，-68/31，-45/31)T是非可行解； 最大值为z3=117/5；最优解X(3)=（34/5，0，0，7/5)T。 （2）解：

系数矩阵A是：

12342112 令A=(P1，P2，P3，P4)

P1，P2线性无关，以（P1，P2）为基，有： x1+2x2=7-3x3-4x4

2x1+x2=3-x3-2x4 令 x3，x4=0得

x1=-1/3，x2=11/3

基解X(1)=（-1/3，11/3，0，0)T为非可行解；

同理，以（P1，P3）为基，基解X(2)=（2/5，0，11/5，0)T是可行解z2=43/5； 以（P1，P4）为基，基解X(3)=（-1/3，0，0，11/6)T是非可行解； 以（P2，P3）为基，基解X(4)=（0，2，1，0)T是可行解，z4=-1； 以（P4，P3）为基，基解X(6)=（0，0，1，1)T是z6=-3； 最大值为z2=43/5；最优解为X(2)=（2/5，0，11/5，0)T。

1.4分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每一步相当于图形的哪一点。

（1）max z=2x1+x2 3x1+5x215 6x1+2x224

x1，x20

（2）max z=2x1+5x2

x14

2x212 3x1+2x218

x1，x20

解：（图略）

（1）max z=33/4 最优解是(15/4,3/4) 单纯形法：

标准型是max z=2x1+x2+0x3+0x4 s.t. 3x1+5x2+x3=15 6x1+2x2+x4=24 x1,x2,x3,x40 单纯形表计算： cj 2 b 15 24 0 3 4 -8 3/4 15/4 -33/4 x1 1 x2 0 x3 0 x4 i CB XB 0 0 -z 0 2 -z 1 2 -z x3 x4 3 [6] 2 0 1 0 0 1 0 5 2 1 [4] 1/3 1/3 1 0 0 1 0 0 1 0 0 1/4 -1/12 -1/12 0 1 0 -1/2 1/6 -1/3 -1/8 5/24 -7/24 5 4 3/4 12 x3 x1 x2 x1 解为：（15/4，3/4，0，0 )T Max z=33/4

迭代第一步表示原点；第二步代表C点（4，0，3，0)T； 第三步代表B点（15/4，3/4，0，0 )T。 （2）解：（图略）

Max z=34 此时坐标点为（2，6） 单纯形法，标准型是： Max z=2x1+5x2+0x3+0x4+0x5

s.t. x1+x3=4 2x2+x4=12 3x1+2x2+x5=18

x1,x2,x3,x4,x50

(表略)

最优解 X=（2，6，2，0，0 )T Max z=34

迭代第一步得X(1)=（0，0，4，12，18)T表示原点，迭代第二步得X(2)=（0，6，4，0，6)T，第三步迭代得到最优解的点。

1.5以1.4题（1）为例，具体说明当目标函数中变量的系数怎样变动时，满足约束条件的可行域的每一个顶点，都可能使得目标函数值达到最优。 解：目标函数：max z=c1x1+c2x2 (1)当c20时

x2=-（c1/c2）x1+z/c2 其中，k=-c1/c2

kAB=-3/5，kBC=-3

 k当c2当c2 当c2当c2 当c2当c2kBC 时，

c1，

c2同号。

0时，目标函数在C点有最大值 0时，目标函数在原点最大值。

kBCk

kABcc时，1，2同号。

0， 目标函数在B点有最大值； 0，目标函数在原点最大值。

kAB k

cc0时，1， 2同号。

0时，目标函数在A点有最大值 0时，目标函数在原点最大值。

 k 当c2当c2cc0时，1 ，2异号。 c0，1 c0，1 kAB0时，目标函数在A点有最大值； 0时，目标函数在C点最大值。

 k= 当c2当c2cc时，1， 2同号

0时，目标函数在AB线断上任一点有最大值 0，目标函数在原点最大值。

 k= 当c2当c2kBC时，

c1，

c2同号。

0时，目标函数在BC线断上任一点有最大值 0时，目标函数在原点最大值。

c k=0时，1=0 当c2当c20时，目标函数在A点有最大值

0，目标函数在OC线断上任一点有最大值

（2）当c2=0时，max z=  c1 

c1x1

0时，目标函数在C点有最大值

0时，目标函数在OA线断上任一点有最大值

c1c1=0时，在可行域任何一点取最大值。

1.6分别用单纯形法中的大M法和两阶段法求解下列线性问题，并指出属于哪类解。

（1）max z=2x1+3x2-5x3

x1+x2+x315

2x1-5x2+x324

x1，x20

（2）min z=2x1+3x2+x3

x1+4x2+2x38

3x1+2x26

x1，x2，x30

（3）max z=10x1+15x2+12x3 5x1+3x2+x39 -5x1+6x2+15x315 2x1+x2+x35

x1，x2，x30

（4）max z=2x1-x2+2x3

x1+x2+x36

-2x1+x32 2x2-x30

x1，x2，x30

解：（1）解法一：大M法 化为标准型：

Max z=2x1+3x2-5x3-Mx4+0x5-Mx6 s.t. x1+x2+x3+x4=7 2x1-5x2+x3-x5+x6=10

x1,x2,x3,x5,x4,x60 M是任意大整数。

单纯形表： cj 2 b 7 x1 3 x2 -5 x3 -M x4 0 x5 -M x6 i CB XB -M x4 1 1 1 1 0 0 7 -M x6 10 17M 2 5 [2] -5 1 2M-5 1/2 1/2 0 0 1 0 -1 -M 1/2 -1/2 1 0 -1/2 1/2 5 4/7 - -z -M 2 x4 x1 3M+2 3-4M 0 [7/2] 1 -5/2 -z 3 2 x2 x1 2M-10 0 4/7 45/7 0 1 (7/2)M+8 0.5M-6 0 1 0 0 1/7 6/7 -50/7 2/7 5/7 0.5M+1 -1.5M-1 1/7 -1/7 -1/7 1/7 -z -102/7 0 -M-16/7 -1/7 -M+1/7 最优解是：

X=（45/7，4/7，0，0，0 )T 目标函数最优值 max z=102/7 有唯一最优解。 解法二：

第一阶段数学模型为 min w= x4+ x6 S.t. x1 +x2+ x3+ x4=7

2 x1-5 x2+ x3- x5+ x6=10

x1,x2,x3,x4，x5,x60

（单纯形表略） 最优解

X=（45/7，4/7，0，0，0 )T

目标函数最优值 min w=0 第二阶段单纯形表为： 2 c j3 x2 -5 x3 0 x5 i CB XB b 4/7 45/7 x1 3 2 x2 x1 0 1 1 0 1/7 6/7 1/7 -1/7 -z 最优解是 -102/7 0 0 -50/7 -1/7 X=（45/7，4/7，0，0，0 )T

Max z=102/7

（2）解法一：大M法

z=-z 有max z=-min （-z）=-min z 化成标准形：

Max z=-2x1-3x2-x3+0x4+0x5-Mx6-Mx7 S.T.

x1+4x2+2x3-x4+x6=4 3x1+2x2-x5+x7=6 x1,x2,x3,x4，x5,x6，x70 （单纯性表计算略）

线性规划最优解X=（4/5，9/5，0，0，0 ，0)T 目标函数最优值 min z=7

非基变量x3的检验数3=0，所以有无穷多最优解。 两阶段法：

第一阶段最优解X=（4/5，9/5，0，0，0，0 )T是基本可行解,min w=0 第二阶段最优解（4/5，9/5，0，0，0，0 )T min z=7 非基变量x3的检验数3=0，所以有无穷多最优解。

（3）解：大M法

加入人工变量，化成标准型：

Max z=10 x1+15 x2+12 x3+0 x4+0 x5+0 x6-M x7 s.t. 5 x1+3 x2+ x3+ x4=9 -5 x1+6 x2+15 x3+ x5=15 2 x1+ x2+ x3- x6+ x7=5 x1,x2,x3,x4，x5,x6，x70 单纯形表计算略

当所有非基变量为负数，人工变量x7=0.5，所以原问题无可行解。 两阶段法（略）

（4）解法一：大M法

单纯形法，（表略）非基变量x4的检验数大于零，此线性规划问题有无界解。 两阶段法略

1.7求下述线性规划问题目标函数z的上界和下界；

Max z=c1x1+c2x2

a11x1a12x2b1 a21x1a22x2b2

8b112，10b214，2a125，1c13，4c26，1a113，其中：

2a214，4a226

解：

 求Z的上界

Max z=3x1+6x2 s.t. -x1+2x212 2x1+4x214

x2，x10

加入松弛变量，化成标准型，用单纯形法解的，最优解 X=（0，7/2，5，0 )T

目标函数上界为z=21

存在非基变量检验数等于零，所以有无穷多最优解。  求z的下界 线性规划模型： Max Z= x1+4x2 s.t. 3x1+5x28 4x1+6x210 x2，x10

加入松弛变量，化成标准型，解得：

最优解为

X=（0，8/5，0，1/5 )T

目标函数下界是z=32/5

1.8表1-6是某求极大化线性规划问题计算得到的单纯形表。表中无人工变

caaac量，1，2，3，d，1，2为待定常数，试说明这些常数分别取何值时，以下

结论成立。

（1）表中解为唯一最优解；（2）表中解为最优解，但存在无穷多最优解；（3）该线性规划问题具有无界解；（4）表中解非最优，对解改进，换入变量为x1，换出变量为x6。 基b x3 d x4 2 x6 3 cjzj x1 x2 x3 x4 x5 a2 x6 4 -1 a3 c1 a11 0 0 0 0 1 0 0 0 0 1 0 -3 -5 c2 -1 -4 -3 解：

（1）有唯一最优解时，d0，c10，c20

（2）存在无穷多最优解时，d0，c10，c2=0或d0，c1=0，c20. （3）有无界解时，d0，c10，c2（4）此时，有d0，c10且a10

0，3/a30并且c1c2，a3d/4

1.9某昼夜服务的公交线路每天个时间段内所需司机和乘务员人数如下： 班次 时间 所需人数 1 6点到10点 60 2 10点到14点 70 3 14点到18点 60 4 18点到22点 50 5 22点到2点 20 6 2点到6点 30 设司机和乘务人员分别在各时间区段一开始时上班，并连续上班8小时，问该公交线路至少配备多少司机和乘务人员。列出线型规划模型。

解 ：

设xk（k=1，2，3，4，5，6）为xk个司机和乘务人员第k班次开始上班。 建立模型：

Min z=x1+x2+x3+x4+x5+x6 s.t. x1+x660 x1+x270 x2+x360 x3+x450 x4+x520 x5+x630

x1,x2,x3,x4,x5,x6 0

1.10某糖果公司厂用原料A、B、C加工成三种不同牌号的糖果甲乙丙，已知各种糖果中ABC含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价如表所示： 原料 甲 乙 丙 原料每月成本（元/限制用量千克） （千克） A 2 2000 60% 15% B 1.5 2500 C 1 1200 20% 60% 50% 加工费 0.5 0.4 0.3 售价 3.4 2.85 2.25 问该厂每月应当生产这三种牌号糖果各多少千克，使得获利最大？建立数学模型。

解:

解：设x1，x2，x3是甲糖果中的A，B，C成分，x4，x5，x6是乙糖果的A，B，C成分，x7，x8，x9是丙糖果的A，B，C成分。

线性规划模型：

Max z=0.9x1+1.4x2+1.9x3+0.45x4+0.95x5+1.45x6-0.05s.t. -0.4x1+0.6x2+0.6x30

x7+0.45

x8+0.95

x9

-0.2x1-0.2x2+0.8x30 -0.85x4+0.15x5+0.15x60 -0.6x4-0.6x5+0.4x60 -0.7

x7-0.5

x8+0.5

x90

x1+x4+ x2+x5+

x72000

x82500 1200

x7x8x9,, 0

x3+x6+

x9x1,x2,x3,x4,x5,x6,

1.11某厂生产三种产品I、、III。每种产品经过AB两道加工程序，该厂有两种设备能完成A工序，他们以A1,A2表示；有三种设备完成B工序，分别为

B1，B2，B3；产品I可以在AB任何一种设备上加工，产品可以在任何规格

的A设备上加工，但完成B工序时，只能在B1设备上加工；产品III只能在A2，

B2上加工。已知条件如下表，要求安排最优生产计划，使该厂利润最大化。

设备 A1 A2 产品 I 5 7 6 4 7 0.25 1.25 II 10 9 8 0.35 2.00 III 12 11 0.5 2.8 设备有效台满负荷时的时 设备费用 6000 300 10000 4000 7000 4000 321 250 783 200 B1 B2 B3 原料费 单价 解：

产品1，设A1,A2完成A工序的产品x1，x2件；B工序时，B1,B2，B3完成

B工序的x3，x4，x5件，产品，设A1,A2完成A工序的产品x6，x7件；B工序时，工序的

B1x9完成B的产品为件；

x8件；产品111，

A2完成A工序的

x9件，

B2完成B

x1+ x2= x3+ x4+ x5 x6+

x7=

x8

建立数学模型：

Max z=(1.25-0.25)*( x1+ x2)+(2-0.35)*( x6+

x6)300/6000-(7 x2+9

x7)+(2.8-0.5)

x9-(5 x1+10

x7+12

x9)321/10000-(6 x3+8

x8)250/4000-(4 x4+11

x9)783/7000-7 x5*200/4000 s.t

5 x1+10 x6 6000 7 x2+9 6 x3+8

x7x8+12

x9 10000

4000 7000

4 x4+11

x97 x5 4000

x1+ x2= x3+ x4+ x5 x6+

x7=

x8

x1,x2,x3,x4,x5,x6,

x7x8x9,, 0

最优解为X=（1200，230，0，859，571，0，500，500，324 )T 最优值1147. 试题：

1. （2005年华南理工大学）设某种动物每天至少需要700克蛋白质、30克矿物质、100毫

克维生素。现有5种饲料可供选择，每种饲料每公斤营养成分的含量及单价如下表所示：

试建立既满足动物生长需要，又使费用最省的选用饲料方案的线性规划模型。

表 1—1 饲料 蛋白质（克） 矿物质（克） 维生素（毫克） 价格（元/公斤） 1 3 1 0.5 0.2 2 2 0.5 1 0.7 3 1 0.2 0.2 0.4 4 6 2 2 0.3 5 18 0.5 0.8 0.8 解题分析：这是一道较简单的数学规划模型问题，根据题意写出约束即可。 解题过程：minz0.2x10.7x20.4x30.3x40.8x5

3x12x2x36x418x5700x0.5x0.2x2x0.5x302345 s..t10.5xx0.2x2x0.8x10012345x1,x2,x3,x4,x50

第二章（67页）

2.1用改进单纯形法求解以下线性规划问题。

（1）Max z=6x1-2x2+3x3 2x1-x2+3x32

x1+4x34 x1，x2，x30

（2）min z=2x1+x2 3x1+x2=3 4x1+3x26

x1+2x23 x1,x20

解： （1）

先化成标准型：

Max z=6x1-2x2+3x3+0x4+0x5 s.t. 2x1-x2+2x3+x4=2

x1+4x3+x5=4 x1,x2,x3,x4,x5 0

10T令B0=（P4，P5）= XB0=（x4,x5),CB0=(0,0)

01212TXN0=(P1,P2,P3)=xxx) , =（，， N1230104102CN0=(6,-2,3)，B01=b,=0

014非基变量的检验数

CN0CB0B01N0CN0N=-==(6,-2,3)

0因为x1的检验数等于6，是最大值，所以，x1为换入变量，

B10221b0=；B0P1=

41由规则得：

=1

x4为换出变量。

20TB1=(P4，P5)=,XB1=（x1,x5)，CB=(6,0).

111N1=(P4,P2,P3), XN1=（x4，x2，x3)T

0.501CN1=(0，-2，3)，B11=b,=1

0.513非基变量的检验数 N1=（-3，1，-3）

因为x2的检验数为1，是正的最大数。所以x2为换入变量；

0.5B10P2=

0.5由规则得：

=6

所以x5是换出变量。

21TXB2=(P1，P2)=xx),=（,，CB2=(6,-2). B12210N2=(P4,P5，P3), XN2=（x4，x5，x3)T CN2=(0，0，3)，B21014=,b2= 126非基变量的检验数 N2=（-2，-2，-9）

非基变量的检验数均为负数，愿问题已达最优解。

4最优解X= 

6即：X=（4,6,0)T

目标函数最优值 max z=12 （2） 解 ：

Min z=2x1+x2+0x3+Mx4+Mx5+0x6 S.T. 3x1+x2+x4=3 4x1+3x2-x3+x5=6

x1+2x2+x6=3 x1,x2,x3,x4,x5, x60

M是任意大的正数。

（非基变量检验数计算省略）

原问题最优解是X=（0.6，1.2，0） 目标函数最优值： z=12/5

2.2已知某线性规划问题，用单纯形法计算得到的中间某两步的加算表见表，试将空白处数字填上。 3 5 4 0 0 0 c jCB XB 5 0 x2 x5 b 8/3 14/3 x1 x2 x3 x4 x5 x6 2/3 -4/3 1 0 0 5 1/3 -2/3 0 1 0 0 0 x6 cj-zj 20/3 5/3 -1/3 0 0 . . . 4 4 -2/3 -5/3 0 0 1 0 x2 x3 x1 cj-zj 15/41 -6/41 -2/41 8/41 5/41 -12/41 -10/41 4/41 15/41 解： cj 3 b 8/3 14/3 20/3 x1 5 x2 4 x3 0 x4 0 x5 0 x6 CB XB 5 0 0 x2 x5 x6 cj-zj . . . 5 4 3 x2 x3 x1 cj-zj 80/41 50/41 44/41 0 0 1 0 1 0 0 0 0 1 0 0 15/41 -6/41 -2/41 -45/41 2.3写出下列线性规划问题的对偶问题。 （1）min z= 2 x1+2 x2+4 x3

2 x1+3 x2+5 x3 2 3 x1+ x2+7 x3 3

x1+4 x2+6 x3 5 x1 ,x2, x3 0

（1）

解：对偶问题是： Max w=2y1-3y2-5y3 s.t.

2y1-3y2-y32 3y1-y2-4y32 5y1-7y2-6y34

y1,y2,y30

(2)max z= x1+2x2+3 x3+4 x4 -x1+x2-x3-3x4=5 6x1+7x2+3x3-5x48 12x1-9x2-9x3+9x420

x1,x20;x3 0;x4无约束

解：

对偶问题： Min w=5y1+8y3+20S.t. -y1+6y3+12 y1+7y3-9

y4

y41

y42 y4 -y1+3y3-9

3 =4

-3y1-5y3+9

y4y1无约束，y30；

y40

（3）min z=cijxij

i1j1mnxj1nijai i=1,…,m

xi1mijbj j=1,…,n

xij0

解：

''对偶问题: max w=aiy+bjymj

m''ini1j1''cs.t. yi''+ymjij

''yy i,mj 无约束 i=1,2,….m; j=1,2,….n

''

(4)

Max z=cjxj

j1naxijj1nnjbi, i=1,…., m1m

axijj1jbi, i=m11,m12,...,m

xj0,当j=1，….，n1n

xj无约束，当j=n11,...,n

m解：

Min w=bjyi''

i1s.t.

ai1mijyi''cj j=1,2,3…n1

ai1mijnnyi''cj j=1+1, 1+2,….n

yi''0 i=1,2…. m1

yi''无约束， i=m1+1, m1+2….m

2.4判断下列说法是否正确，并说明为什么. (1)如线性规划问题的原文题存在可行解，则其对偶问题也一定存在可行解。 （2）如线性规划的对偶问题无可行解，则原问题也一定无可行解。

（3）如果线性规划问题的原问题和对偶问题都具有可行解，则该线性规划问题一定有有限最优解。

(1)错误，原问题有可行解，对偶问题可能存在可行解，也可能不存在； （2）错误，对偶问题没有可行解，原问题可能有可行解也可能有无界解； （3）错误，原问题和对偶问题都有可行解，则可能有有限最优解也可能

有无界解；

2.5设线性规划问题1是：

Max z1=cjxj

j1naxijj1njbi ，i=1，2…，m

xj0,j1,2....,n

*（y1*,...,ym）是其对偶问题的最优解。

又设线性规划问题2是 Max z2cjxj

j1naxijj1njbi +ki ，i=1，2…，m

xj0,j1,2....,n

其中ki是给定的常数，求证：

max z2max z1+kiyi*

i1m解：

证明：把原问题用矩阵表示：

Max z1=CX s.t. AXb X0 b=（b1,b2...bm)T

设 可行解为X1,对偶问题的最优解Y1=（y1，y2…ym ）已知。 Max z2=CX

s.t. AXb+k X0 k=（k1,k2...km)T

设可行解为X2，对偶问题最优解是Y2,对偶问题是， Min w=Y(b+k) S.t. YA C Y 0 因为

Y2是最优解，所以

Y2（b+k）Y1（b+k）

X2是目标函数z2的可行解，A

X2YXYb+k ；2A22（b+k）Y1b+Yk

原问题和对偶问题的最优函数值相等，所以不等式成立，证毕。

2.6已知线性规划问题 Max z=c1x1c2x2c3x3

a11ax121a12ax222a13ax32310x4b10=x15b 2xj0,j1,...,5

用单纯形法求解，得到最终单纯形表如表所示，要求： （1） 求a11，a12，a13，a21，a22，a23，b1，b2的值； （2） 求c1,c2,c3的值；

XB b 3/2 x1 x2 x3 x4 x5 x3 1 0 1 1/2 -1/2 x2 cjzj 2 1/2 -3 1 0 0 0 -1 0 2 -4 解：

（1）初始单纯形表的增广矩阵是：

aC1=11a21a12a22a13a2310b1

01b2最终单纯形表的增广矩阵为

1010.50.51.5C2= 220.5101C2是

C1作初等变换得来的，将的单位矩阵。有：

C2作初等变换，使得

C2的第四列和第五列

的矩阵成为

C2a11=9/2； a12=1； a13=4； a21=5/2； a22=1； a23=2； b1=9； b2=5

由检验计算得：

c1=-3； c2=c3=0

2.7已知线性规划问题 Max z=2x1+x2+5x3+6x4 s.t. 2x1+x3+x48 2x1+2x2+x3+2x412

xj0，j=1,…4

*1，试应用对偶问题对偶变量y1，y2，其对偶问题的最优解是y1*=4，y2的性质，求原问题的最优解。

解：

对偶问题是：

Min w=8y1+12y2 s.t. 2y1+2y22 2y21

y1+y25 y1+2y26 y1，y20

ˆ是原问题和对偶问题的可行解，那么，YˆX=0ˆ，Y互补松弛性可知，如XS

YSXˆ=0，当且仅当Xˆ，Yˆ是最优解。 设 X,Y是原问题和对偶问题的可行解，YS=（y3，有： Y

XS

=0; 且 YSX=0

x5=x6=0，原问题约束条件取等号，x3=4；x4=4

最优解X=（0，0，4，4)T

目标函数最优值为44。

2.8试用对偶单纯形法求解下列线性规划问题。 （1）min z=x1+x2 2x1+x24 x1+7x27 x1,x20

(2) min z=3x1+2x2+x3+4x4 2x1+4x2+5x3+x4 0 3x1- x2+7x3-2x4 2 5x1+2x2+x3+10x4 15

x1 ,x2, x3, x4 0

解： （1）

取w=-z，标准形式：

y4，y5，y6）

和

Max w=-x1-x2+0x3+0x4 s.t.

-2x1-x2+x3=-4 -x1-7x2+x4=-7 x1，x2，x3，x40 单纯形法求解（略）： 最优解：

X=（21/13，10/13，0，0)T 目标函数最优值为31/13。

（2）令：w=-z，转化为标准形式： Max w=-3x1-2x2-x3-4x4+0x5+0x6+0x7 s.t.

-2x1-4x2-5x3-x4+x5=0 -3x1+x2-7x3+2x4+x6=-2 -5x1-2x2-x3-6x4+x7=-15

x1，x2，x3，x4，x5，x6，x70

单纯形法略

原问题最优解：

X=（3，0，0，0，6，7，0)T 目标函数最优值为9。 2.9现有线性规划问题 max z=- 5x1+5x2+13x3 - x1+x2+3x3 20 12 x1+4x2+10x3 90

x1 ，x2， x3 0

先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？

（1） 约束条件1的右端常数20变为30

（2） 约束条件2的右端常数90变为70 （3） 目标函数中x3的系数变为8

1（4） x1的系数向量变为

12（5） 增加一个约束条件2x1+3x2+5x350 （6） 将约束条件2变为10x1+5x2+10x3100 解：

把原问题化成标准型的：

Max z=-5 x1+5 x2+13 x3+0 x4+0 x5 s.t

- x1+ x2+3 x3+ x5=20 12 x1+4 x2+10 x3+ x5=90

x1，x2，x3，x4，x50

单纯形法解得： 最优解：

X=（0，20，0，0，10)T 目标函数最优值为100。

非基变量x1的检验数等于0，原线性问题有无穷多最优解。 （1）约束条件的右端常数变为30 有 bB1b 因此 bbb 单纯形法解得： 最优解：

X=（0，0，9，3，0)T 目标函数最优值为117。

2右端常数变为70 （2）约束条件○有 bB1b 因此 bbb

单纯形法解得，最优解： X=（0，5，5，0，0)T

目标函数最优值为90。

（3）x3的系数变成8，x3是非基变量，检验数小于0，所以最优解不变。

0（4）x1的系数向量变为

5x1是非基变量，检验数等于-5，所以最优解不变。

3 （5）解：加入约束条件○用对偶单纯形表计算得： X=（0，25/2，5/2，0，15，0)T 目标函数最优值为95。

（6）改变约束条件，P3,P4,P5没有变化，

线性规划问题的最优解不变。

2.10已知某工厂计划生产I,II,III三种产品，各产品在ABC设备上加工，数据如下表， 设备代号 每月设备 I II III 有效台时 A 8 2 10 300 B 10 5 8 400 C 2 13 10 420 单位产品利润3 2 2.9 /千元 （1）如何充分发挥设备能力，使生产盈利最大？ （2）如果为了增加产量，可借用其他工厂的设备B，每月可借用60台时，租金为1.8万元，问借用是否合算？

（3）若另有两种新产品IV,V，其中IV为10台时，单位产品利润2.1千元；新产品V需用设备A为4台时，B为4台时，C为12台时，单位产品盈利1.87千元。如A,B,C设备台时不增加，分别回答这两种新产品投产在经济上是否划算？

（4）对产品工艺重新进行设计，改进结构，改进后生产每件产品I，需要设备A为9台时，设备B为12台时，设备C为4台时，单位产品利润4.5千元，问这对原计划有何影响？

解：

（1）设：产品三种产品的产量分别为，x1，x2，x3，建立数学模型： Max z=3x1+2x2+2.9x3 s.t.

8x1+2x2+10x3300 10x1+5x2+8x3400 2x1+13x2+10x3420

x1,x2,x30

把上述问题化为标准型，用单纯形法解得： 最优解：

X=（338/15，116/5，22/3，0，0，0)T

目标函数最优值为2029/15。 （2）

设备B的影子价格为4/15千元/台时，借用设备的租金为0.3千元每台时。 所以，借用B设备不合算。 （3）

设备V,V生产的产量为x7，x8，系数向量分别为：

P7(12,5,10)T P8(4,4,12)T

检验数7=-0.06，所以生产V不合算，

8=37/300，生产V合算。 单纯形法计算得： 最优解：

X=（107/4，31/2，0，0，0，0，55/4)T 目标函数最优值为10957/80。

（4）改进后,检验数1=253/300，大于零。

所以，改进技术可以带来更好的效益。

2.11分析下列参数规划中当t变化时最优解的变化情况。 （1）Max z(t)=(3-6t) x1+(2-2t) x2+(5-5t) x3 (t0) s.t.

x1+2x2+x3 430

3x1+2x3 460

x1+4x2 420 x1，x2，x30

（2）Max z(t)=(7+2t)x1+(12+t) x2+(10-t)x3 (t0) s.t.

x1+x2+x3 20

2x1+2x2+ x3 30

x1，x2，x30

（3）Max z(t)=2x1+x2 (0 t 25) s.t.

x1 10+2t x1 +x2 25-t x2 10+2t x1，x20

（4）Max z(t)=21x1+12x2+18x3+15x4 (0 t 59) s.t.

6x1+3x2+6x3+3x4 30+t 6x1-3x2+12x3+6x4 78-t 9x1+3x2-6x3+9x4 135-2t

x1，x2，x3，x40

解：

（1）化成标准形式：

Max z(t)=(3-6t) x1+(2-2t) x2+(5-5t) x3+0x4+0x5+0x6 (t0) s.t.

x1+2x2+x3+x4=430

3x1+2x3+x5=460

x1+4x2+x6=420

x1，x2，x3，x4，x5, x60

令t=0，用单纯形表计算， 3-6t 2-2t c j5-5t x3 0 x4 0 x5 0 x6 i CB XB B 100 230 20 x1 x2 2-2t 5-5t 0 -z x2 x3 x6 -1/4 3/2 2 1 0 0 0 0 1 0 0 0.5 0 -2 t-1 -1/4 1/2 [1] 2t-2 0 0 1 0 - 460 20 1350t t-4 -1350 t增大，t大于1，首先出现4，5大于0，所以当0t1时有最优解。 X=（0，100，230，0，0，20)T

目标函数最优值为1350（t-1） （0t1）。 t=1是第一临界点。 t大于1时，x6是换出变量。

t大于1，最优解是：X=（0，0， 0，430，460，420)T 目标函数最优值为

Max z(t)=0， （t大于1）

（2）

化成标准型，然后令t=0，单纯形法解得：

t开始增大时，当t大于8/3时，首先出现优解。

目标函数最优值Max z(t)=220，（0t8/3） 所以，t=8/3为第一临界点。 当8/34大于0，所以0t8/3，得最

4为换入变量，由规则，x3为换出变量，使用单纯形法

继续迭代，t继续增大，当t>5，首先1大于0，8/3X=（0，15，0，5)T

目标函数最优值为180+15t ，（8/3当t>5时，x1是换入变量，x2为换出变量，单纯性法计算， 当t继续增大，所有检验数都非正，所以当t>5，最优解： X=（15，0，0，5)T

目标函数最优值为105+30t， t〉0

(3)化成标准型，令t=0,用单纯形法计算得：

当t开始增大，t大于5时，首先出现b2小于0，当0t5，最优解为： X=（10+2t，0，10+2t，5-t，0)T 目标函数最优值为6t+30 ，（0t5）。 所以t=5是第一临界点。

当t大于5时，x4是换出变量，x5是换入变量。用对偶单纯形法计算， 当t大于5时，最优解为： X=（10+2t，15+t，0，0，t-5)T

目标函数最优值为35+5t。 （4）解：

先化为标准型，令t=0，用单纯形法计算，得：

当t开始增大，当t大于6时，首先出现b2小于0，当0t6，有最优解： X=（0，0，0，10+t/3，0，18-3t，45-5t)T 目标函数最优值为150+5t （0t6）。

当t大于6时，首先出现b2小于0，x6是换出变量，x2是换入变量，使用单纯形法计算得：t继续增大，当t大于11时，b3首先小于零，x7是换出变量，x3为换入变量，对偶单纯形法迭代得： 当 t≤59，有最优解：

X=（0，t/3-2，t/8-11/8，59/4-t/4，0，0，0)T

目标函数最优值为5t/2+345/2 ，（111. （2006年西北工业大学）已知线性规划：

maxz3x12x2

x12x243x2x122s..t1 x1x23x1,x20（1） 用单纯形法求解该线性规划问题的最优解和最优值；

（2） 写出线性规划的对偶问题；

（3） 求解对偶问题的最优解和最优值。

解题分析：本题考察了线性规划与对偶问题的知识，要求读者熟知对偶理论。

18解题过程：X*5353200 5Tmaxz12，有无穷多解。

对偶问题为：

minw4y112y23y3

y13y2y33s..t2y12y2y32 y,y,y0123Y*010 w*z*12

2. （2005年东南大学）写出如下线性规划问题的对偶问题：

maxzx12x2x3

x1x2x32xxx1s..t123

2xxx2123x3 无限制x10,x20,并利用弱对偶性说明z的最大值不大于1。

解题过程：原问题的对偶问题为：

minw2y1y22y3

y1y22y31yyy23 s..t12y1y2y31y10,y30,y2由于（0，1，0）是上述对偶问题的可行解，由弱对偶性可知，对原问题的任一可行解

X都有 CXY b21，所以z的最大值不大于1。 1而Yb0102

第三章（86页）

3.1判断表中给出的调运方案能否作为用表上作业法求解时的最初解？为什么？

表3—1 销地1 产量 2 3 4 产地 1 2 3 销量 表3—2 销1 地 产地 1 2 3 4 5 销量 0 5 5 2 15 15 3 15 15 4 10 10 5 15 25 5 产量 150 90 240 200 210 410 300 250 550 250 80 330 50 20 70 400 500 300 300 100 解：

表3—1中，有5个数字格，作为初始解，应该有m+n-1=3+4-1=6个数字格，所以表3-1的调运方案不能作为用表上作业法求解时的初始解。

表3-2中，有10个数字格，而作为初始解，应该有m+n-1=9个数字格，所以表3-2的调运方案不能作为表上作业法的初始解。

3.2

表3-3和表3-4中分别给出两个运输问题的产销平衡表和单位运价表，试用伏格尔法直接给出近似最优解。

表3-3 销地 1 产量 2 3 产地 1 5 1 8 12 2 2 4 1 14 3 3 6 7 4 销量 9 10 11 表3-4 销产量 1 2 3 4 5 地 产地 1 10 2 3 15 9 25 2 5 20 15 2 4 30 3 15 5 14 7 15 20 4 20 15 13 M 8 30 销量 20 20 30 10 25 解：

（1）在表3-3中分别计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。得到： 销地 1 2 3 行差额 产地 1 5 1 8 4 2 2 4 1 1 3 3 6 7 3 列差额 1 3 6 从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，上表中，第三列是最大差额列，此列中最小元素为1，由此可以确定产地2的产品应先供应给销售地3，得到下表： 销地 1 2 3 产量 产地 1 12 11 2 14 3 4 销量 9 10 11 同时将运价表第三列数字划去，得 销地 1 2 产量 产地 1 5 1 12 2 2 4 14 3 3 6 4 销量 9 10 对上表中的元素，计算各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列，重复上面的步骤，直到求出初始解，最终结果是：

销地 1 2 3 产量 产地 1 2 10 12 2 3 11 14 3 4 4 销量 9 10 11 （2）3-4分别计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素。（方法同3-3相同）

最终得出原问题的初始解： 销地 1 2 3 4 5 产量 产地 1 2 3 4 销量 25 20 30 20 30 20 20 30 10 25 3.3用表上作业法求给出运输问题的最优解（M是任意大正数） （1） 销地 甲 乙 丙 丁 产量 产地 1 3 7 6 4 5 2 2 4 3 2 2 3 4 3 8 5 3 销量 3 3 2 2 解：

1计算出各行和各列的次最小运费和最小运费的差额，填入该表的最（1）○右列和最下列。

2从行差额或者列差额中找出最大的， ○选择它所在的行或者列中的最小元素，丙列中的最小元素为3，由此可以确定产地2的产品应先供应丙的需要，

而产地2的产量等于丙地的销量，故在（2，丙）处填入0，同时将运价表中的丙列和第二行的数字划去，得到： 销地 甲 乙 丙 丁 产量 产地 1 3 7 4 5 2 3 销量 4 3 3 3 5 2 2 3 3对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，○

1○2，直到求出初始解为止。得到下表：填入该标的最右列和最下行，重复步骤○ 销地 甲 乙 产地 1 3 2 3 0 3 销量 3 3 使用位势法进行检验： 丙 丁 产量 2 2 2 0 2 5 2 3 1上表中，数字格处填入单位运价并增加一行一列，在列中填入ui（i=1，○

2，3），在行中填入vj（j=1，2，3，4），先令同）来确定销地 产地 1 2 3 uivi+=cij（i，jB，B为基，下

uiv和i，得到下表： 甲 乙 丙 丁 ui vi3 4 3 3 2 -（

3 5 4 2 4 0 -2 1 2由ij=○

cijuivi+）（i，j为非基，下同）计算所有空格的检验数，并在

丁 每个格的右上角填入单位运价，得到下表 销地 甲 乙 丙 产地 1 3 7 0 5 1 2 2 4 1 4 0 3 4 3 0 0 2 ui4 0 6 0 3 0 8 0 2 5 -2 1 vi3 2 5 4 由上表可以看出，所有的非基变量检验数≥0，此问题达到最优解。 又因为34=0，此问题有无穷多最优解。 总运费min z=3*3+3*3+2*3+2*4=32

（2） 销地 甲 乙 丙 产地 1 10 6 7 2 16 10 5 3 5 4 10 销量 5 2 4 丁 产量 12 9 10 6 4 9 4 1计算出各行和各列的次最小运费和最小运费的差额，填入该表解：（2）○的最右列和最下列。

2从行差额或者列差额中找出最大的， ○选择它所在的行或者列中的最小元素，甲列是最大差额列，甲列的最小元素是5，所以产地3的产品先供应甲

的需求，同时将运价表中产地3所在行的数字划去。

3对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， ○

1○2，直到求出初始解为止。得到下表：填入该标的最右列和最下行，重复步骤○ 销地 甲 乙 产地 1 1 2 2 3 4 销量 5 2 使用位势法进行检验： 丙 丁 产量 1 3 4 6 6 4 9 4 1上表中，数字格处填入单位运价，并增加一行一列，在列中填入ui（i=1，○

2，3），在行中填入vj（j=1，2，3，4），先令u1=0，由 为基，下同）来确定

2由ij=○

uivi+=cij（i，jB，B

uiv和i.

cij-（

uivi+）（i，jN）计算所有空格的检验数，并在每个格的右

上角填入单位运价，得到下表

销地 产地 1 2 3 甲 乙 丙 丁 ui12 0 10 0 16 8 5 0 10 6 10 6 4 3 6 8 7 0 7 1 5 0 10 4 11 9 -2 10 -5 vi 由上表可以看出，所有的非基变量检验数≥0，此问题达到最优解。 此问题有唯一最优解。 总运费min z=118 （3） 销地 甲 乙 丙 丁 戊 产量 产地 1 2 3 4 销量 10 2 1 8 4 20 10 20 6 4 5 8 7 3 6 9 30 10 7 2 10 6 4 5 4 5 6 2 9 解：（3）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售地己，令单位运价为0。销量为2。这样就达到了产销平衡。

用伏格尔法求初始解： ○1计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。

○2从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，产地1所在的行是最大差额行，最小元素0，说以一产地的产品应该优先供应己的需要，同时划掉己列的数字。

○3对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤○1○2，直到求出初始解为止。得到下表： 销地 甲 乙 丙 丁 戊 己 产量 产地 1 2 3 4 销量 4 4 4 4 使用位势法进行检验： 3 3 6 2 2 2 2 4 2 2 5 6 2 9 1上表中，数字格处填入单位运价，并增加一行一列，在列中填入ui（i=1，○

2，3，4），在行中填入vj（j=1，2，3，4，5，6），先令u1=0，由 jB，B为基，下同）来确定

2由ij=○

uivi+=cij（i，

uiv和i.

cij-（

uivi+）（i，jN）计算所有空格的检验数，并在每个格的右

上角填入单位运价。

由上表可以看出，所有的非基变量检验数≥0，此问题达到最优解。

又因为14=0，此问题有无穷多最优解。 总运费min z=90 （4） 销地 甲 乙 产地 1 2 3 4 5 销量 100 10 13 0 9 24 120 28 100 11 36 60 6 23 30 80 M 11 18 34 60 18 21 3 19 80 丙 29 丁 13 14 戊 22 16 产量 100 120 M 140 解：（4）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售地己，令单位运价为0。销量为40。这样就达到了产销平衡。

用伏格尔法求初始解： ○1计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下行。

○2从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，同时划掉所在列或行的元素。

○3对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤○1○2，直到求出初始解为止。

并用位势法进行检验： 销地 甲 乙 丙 丁 戊 己 ui 产地 1 2 3 10 18 2 8 13 M 3 M-16 0 0 6 29 0 21 1 11 3 14 0 M 13 6 16 12 0 -10 22 12 0 0 0 0 0 4 4 5 24 2 10 9 0 11 0 28 0 16 0 23 7 36 3 21 0 18 10 30 5 13 M-6 19 8 34 6 16 22 0 17 0 -12 12 -5 vi由上表可以看出，所有的非基变量检验数≥0，此问题达到最优解。 又因为31=0，此问题有无穷多最优解。

总运费min z=5520 3.4

已知运输问题的产销平衡表、单位运价表及最优调运方案如下表所示 表1 销产量 B2 B4 B1 B3 地 产地 5 10 15 A1 A2 0 5 5 10 15 15 15 10 25 5 A3 销量 表2 销地 产地 B1 B21 7 14 c22 B3 B411 20 18 A1 （1）（2）

10 12 2 20 9 16 A2A3A2A2到到

B2B4的单位运价在什么范围变化时，上述最优方案不变？

的单位运价变为何值时，有无穷多最优方案。除表1中方案

外，至少写出其他两个。

解：

1在对应表的数字格处（c22未知）填入单位运价，并增加一行，在列中(1)○

填入ui（i=1，2，3），在行中填入vj（j=1，2，3，4），先令u1=0，由

uivi+=cij（i，jB）来确定

2由ij=○

uiv和i.

cij-（

uivi+）（i，jN）计算所有空格的检验数，并在每个格的右

上角填入单位运价（c22未知）。

最优调运方案不变，则所有非基变量的检验数都是非负。所以：

c22-30 c22+100

10-c220 24-c220 18-c220 解得: 3c2210

单位运价在此区间变化时，最优调运方案不变。

1在对应表的数字格处（c22未知）填入单位运价，并增加一行，在（2）○

列中填入ui（i=1，2，3），在行中填入vj（j=1，2，3，4），先令u1=0，由 （i，jB）来确定

2由ij=○

uivi+=cijuiv和i.

cij-（

uivi+）（i，jN）计算所有空格的检验数，并在每个格的右

上角填入单位运价（c22未知）。

有无穷多最优方案，则至少有一个非基变量的检验数为0.

取c24-17=0，所以单价变为17时，该问题 有无穷多最优调运方案。 另外的两种调运方案： 1 ○销地 产地 A1 A2 B1 B2 B3 B40 10 产量 15 25 0 15 15 A3 5 5 2 ○

15 15 10 5 销量 销地 产地 A1 A2 B1 B2 B3 B4 10 10 产量 15 25 5 0 5 5 15 0 15 15 15 A3 销量 3.5 某百货公司去外地采购ABCD四种规格的服装，数量分别为：A,1500套；B，2000套；C，3000套；D，3500套；有三个城市可以供应上述服装，分别为：I，2500套，II，2500套；III，5000套。已知下表，求预期盈利最大的采购方案。 A B C D I 10 5 6 7 II 8 2 7 6 III 9 3 4 8 解：

因为利润表中的最大利润是10，所以令M=10，用M减去利润表上的数字，此问题变成一个运输问题，见下表： 销地 A B C D 产量 产地 I 0 5 4 3 2500 II 2 8 3 4 2500 III 1 7 6 2 5000 销量 1500 2000 3000 3500 使用伏格尔法计算初始解： ○1计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下行。

○2从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，同时划掉所在列或行的元素。

○3对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤○1○2，直到求出初始解为止。

销地 A 产地 I 1500 II III 销量 1500 使用位势法检验： B C D 产量 500 1500 2000 500 2500 3000 3500 3500 2500 2500 5000 1数字格处填入单位运价，并增加一行一列，在列中填入ui（i=1，2，3）○，在行中填入vj（j=1，2，3，4），先令u1=0，由

uiviu+=cij（i，jB，）来确定iv和i.

2由ij=○

cij-（

uivi+）（i，jN）计算所有空格的检验数，并在每个格的右

上角填入单位运价。

如果没有得到最优解，用逼回路法进行改进。 盈利最大方案： 销地 A B C 产地 I 0 5 4 0 0 II 2 8 3 3 4 0 III 1 7 6 0 1 1 0 5 4 vi D ui3 0 2 4 4 2 1 1 -1 此时，总运费为28000元;最大盈利为72000元。 3.6甲乙丙三个城市每年需要煤炭分别为：320万吨、250万吨、350万吨，由A、B两处煤矿供应。煤炭供应量分别为：A,400万吨；B,450万吨；运价如下表，由于需大于供应，经研究平衡决定，甲城市供应量可以减少0~30万吨，乙城市需要完全供应，丙城市供应不少于270万吨。试求将供应量分配完又使总运费最低的调运方案。 甲 乙 丙 A B

解：

15 21 18 25 22 16 此问题的供应量小于需求量，假设供应地C，产量为70万吨。 用伏格尔法求解得： 销地 甲 甲‘ 乙 丙 丙‘ 供应 产地 A B C 需求 150 140 30 290 30 使用位势法检验： 250 250 270 270 10 70 80 400 450 70 1数字格处填入单位运价，并增加一行一列，在列中填入ui（i=1，2，3）○，在行中填入vj（j=1，2，3，4），先令u1=0，由

uiviu+=cij（i，jB，）来确定iv和i.

2由ij=○

cij-（

uivi+）（i，jN）计算所有空格的检验数，并在每个格的右

上角填入单位运价。

如果没有得到最优解，用闭回路法进行改进。 最优解时，最小运费是14650万元。

3.7某造船厂根据合同要从当年起连续三年末各提供三条规格型号相同的大型客货轮。已知该厂这三年内生产大型客货轮的能力及每艘客货轮成本如下表， 年度 正常生产时间内 加班生产时间内 正常生产时的 可完成的客货轮可完成的客货轮每艘成本/万元 数 数 1 2 3 500 2 4 2 600 3 1 3 550 已知加班生产时，每艘客货轮的成本比正常生产高出70万元，又知道造出来的可货轮如当年不交货，每艘积压一年造成积压损失40万元，在签合同时，该厂已经存储了2艘客货轮，而该厂希望在第三年木完成合同后还能存储一艘备用，问该厂如何安排每年的生产量，能够在满足上述要求的情况下，总的生产费用加积压损失最少？

解：

设A1，A2，A3是三年的需求订货，B1，B2，B3是三年的正常生产能力；B1，

，B3是三年的加班能力，S是事先积压产生的供货能力。第三年的需求量是4B2艘。此问题产销不平衡，增加设想销地A4，运价0，销量7. 使用伏格尔法求初始解：并用位势法检验：

此问题有无穷多最优解， 总运费 min z=4730万元 销地 A2 A1 A3 产地 B1 B1 B2  B2A4 0 0 0 0 供应量 0 60 60 60 -10 60 500 540 600 550 620 B3  B3S 40 -460 需求量 500 540 560 -60 试题：(2001年上海大学)

某产品由产地Ai发往销地Bj的每吨运费如下表： 元/吨 B1 B2 B3 供应量（吨） A1 50 40 60 150 A2 45 30 65 200 A3 20 10 50 250 需求量 150 220 180 为满足各销地需求，应如何确定运输方案使总费用最小？ （1） 建立此运输问题的数学模型。

（2）将此问题化为产销平衡的运输问题，并求出一个初始基本可行解。 解：（1）设xij某产品为从Ai发往销地Bj的吨数，则此运输问题的数学模型为：

maxz50x1140x1260x13245x2130x2265x2320x3110x3250x33x11x12x13150x21x22x23200x31x32x33250s.tx11x21x31150x12x22x32220x13x23x33180xij0,i,j1,2,3

（2）增加一个虚拟销地B4，其需求量为50吨，各产地到虚拟销地B4的每吨运费分别为0，则可将此问题化为如下产销平衡的运输问题： 元/吨 B1 B2 B3 B4 供应量 A1 50 40 60 0 150 A2 45 30 65 0 200 A3 20 10 50 0 250 需求量 150 220 180 50 由最小元素法可得到如下的一个初始基本可行解： 元/吨 B1 B2 B3 B4 供应量 A1 100 50 150 A2 120 80 200 A3 30 220 250 需求量 150 220 180 50 第四章（98页）

4.1若用以下表达式作为目标规划的目标函数，试述其逻辑是否正确？ （1）max=d1+d1 （2）max z=d1-d1 （3）min z=d1+d1 （4）min z=d1-d1

解：（1）不正确 （2）正确 （3）正确 （4）正确 4.2

试用图解法找出以下目标函数的满意解；

（1）min z=P1（d1+d1）+P2（2d2+d3） s.t. x1-10x2+d1-d1=50 3x1+5x2+d2-d2=20 8x1+6x2+d3-d3=100

x1，x2，d1，d1，d2，d2，d3，d30

（2）min z=P1（d3+d4）+P2d1+P3d2+P4(d3+1.5d4) s.t.

x1+x2+d1-d1=40

x1+x2+d2-d2=100 x1+d3-d3=30 x2+d4-d4=15

x1，x2，d1，d1，d2，d2，d3，d3,d4,d40

(3) min z=P1（d1+d1）+P2 d2+P3d3 s.t. x1+x2+d1-d1=10 3x1+4x2+d2-d2=50 8x1+10x2+d3-d3=300

x1，x2，d1，d1，d2，d2，d3，d30

解

（1）满意解是：（50，0） （2）满意解是：（25，15） （3）满意解是：（10，0）

4.3使用单纯形法求解下列目标规划问题。

（1）min z=P1 d1+P2 d2+P3（5d3+3 d4）+P4 d1 s.t.

x1+x2+d1-d1=80

x1+x2+d2- d2=90

x1+d3-d3=70 x2+d4-d4=45

x1，x2，d1，d1，d2，d2，d3，d3,d4,d40

（2）min z=P1 d2+P1 d2+P2 d1 s.t. x1+2x2+d1-d1=10 10x1+12x2+d2-d2=62.4

x1+2x28

x1，x2，d1，d1，d2，d2 0

（3）min z=P1（d1+ d2）+P2 d3 s.t. x1+x2+d1-d1=1 2x1+2x2+d2-d2=4 6x1-4x2+d3-d3=50

x1，x2，d1，d1，d2，d2，d3，d30

解：

（1）把原问题转化为： Min z=P1d2+P1d2+P2d1 S.T.

x1+2x2+d1-d1=10

10x1+12x2+d2-d2=62.4 2x1+x2+x3=8

x1，x2，x3，d1，d1，d2，d20 x3是松弛变量

单纯形法计算得： cj 0 0 0 P2 0 P1 P2 i CB P2 P1 XB d1 d2 b 10 62.4 8 x1 x2 x3 d1 d1 d2 d2 1 10 2 -10 -1 【2】 0 12 1 -12 -2 0 1 0 0 1 0 0 0 0 -1 0 0 0 1 0 1 0 0 0 0 -1 0 2 0 5 5.2 8 0 P1 P2 x3 迭代… 原问题最优解x1=0，x2=5.2，非基变量的的检验数是0，所以有多重解； 继续迭代得到：

x1=0.6，x2=4.7也是满意解

（2）

使用单纯形法计算：

x1=70，x2=20

（3）满意解是

x1=1，x2=0

4.4有以下目标规划问题

min z=P1d1+P2 d4+P3（5d2+3 d3）+P3（5d3+3d2） s.t. x1+x2+d1-d1=80

x1+d2-d2=70 x2+d3-d3=45 d1+d4-d4=10

x1，x2，d1，d1，d2，d2，d3，d3，d4，d40

（1）用单纯形法求解

（2）若目标函数变成min z=P1d1+ P3d4+P2（5d2+3 d3）+P2（5d3+3d2），问原问题的解有什么变化？

（3）若第一个目标约束的右端改为120，原满意解有何变化？ 解：

（1） 单纯形法计算得到：

x1=70，x2=45是满意解

（2） 实际上是对优先因子P2，P3进行调换，最优解不变。

001（3）bBb1001040000100

11004000100b列出现负数，d1行的系数乘以-1，重新迭代，x1=75，x2=45是满意解； 4.5某工厂生产两种产品，产品I每件获利10元，产品II每件获利8元。每生产1件产品I需要3小时，生产产品II需要2.5小时，每周的有效时间120小时，若加班生产，产品I每件利润少1.5元，每件产品II利润少1元，决策者希望在允许的时间和加班时间获取最大利润，试建立该问题的目标规划模型，并求解？ 解：条件不足，无法建立模型。

4.6某商标的酒是用三种等级的酒兑制而成。已知道三种酒的供应量和单位成本如下表；

设该种牌号酒有三种商标（红黄蓝），各种商标的酒对原料酒的混合比及售价见下表，决策者规定：首先必须严格按规定比例兑制各种商标的酒，其次获利最大；再次，红商标的酒每天至少生产2000kg，列出数学模型。 解：

设xi1，xi2，xi3（i=1，2，3）表示第i种等级的兑制红黄蓝三种商标的酒的数量，数学模型：

Max z=P1(d1+d2+d3+d4+d5+d6)+P2d8+P3d7 s.t.

x31-0.1（x11+x21+x31）+d1-d1=0 x11-0.5（x11+x21+x31）+d2-d2=0

x32-0.7（x12+x22+x32）+d3-d3=0 x12-0.2（x12+x22+x32）+d4-d4=0 x33-0.5（x13+x23+x33）+d5-d5=0 x13-0.1（x13+x23+x33）+d6-d6=0 x11+x21+x31+d7-d7=2000 xij0 (i=1,2,3;j=1,2,3)

其中，

z=5.5(x11+x21+x31)+5(x12+x22+x32)+4.8（x13+x23+x33）

-6(x11+x12+x13)-4.5(x21+x22+x23)-3(x31+x32+x33)+d8-d8

试题：

1. 某生产基地每天需从A、B两仓库中提取原材料用于生产，需提取的原材料有：原材料甲不少于240件，原材料乙不少于80公斤，原材料丙不少于120吨。已知：从A仓库每部货车能运回生产基地甲4件，乙2公斤，丙6吨，运费200元/部；从B仓库每部货车每天能运回生产基地甲7件，乙2公斤，丙2吨，运费160元/部，问：为满足生产需要，生产基地每天应发往A、B两仓库多少部货车，并使总运费最少？ 解题过程：根据题意列出下表： 原单位 甲 乙 丙 运费 材运量 （件） （公斤） （吨） （元/部） 料 仓库 A B 需求量 4 7 240 2 2 80 6 2 120 200 160 设每天发往A，B两仓库的货车数分别为x1,x2部，则有

minz200x1160x2

① ② ③ ⑤ ④

4x17x22402x2x802s..t1

6x12x21200 x1,x2且为整数

**10,x230，恰先不考虑整数约束，用图解法（如上图），得最优解为x1好是整数解。故x*(10,30)就是原问题的最优整数解，且z*6800。

故生产基地每天发往A仓库10部车，发往B仓库30部车，可使总运费最

少为6800元。

第五章答案

5.1对下列整数规划问题，问：用先解相应的线性规划，然后凑整的办法，能否求到最优整数解？ （1） max z=3x1+2x2 s.t.

2x1+3x214.5 4x1+x216.5

x1,x20 x1,x2是整数

（1） 解：将上述问题化为： Max z=3x1+2x2+0x3+0x4 s.t.

2x1+3x2+x3=14.5 4x1+x2+x4=16.5

x1,x2,x3,x40 x1,x2N

用单纯形法求解： cj 3 b 29/2 33/2 0 x1 2 x2 0 x3 0 x4 i CB XB 0 0 x3 x4 2 【4】 3 3 1 2 T1 0 0 0 1 0 29/4 33/8 -z （迭代过程略） 相应的线性规划问题最优解是X*= 7/2,5/2,0,0,目标函数的最优值z=31/2 凑整数时，X1=4,3,0,0,是非可行解；

X2=4,2,0,0，是非可行解； X3=3,3,0,0，是非可行解； X4=3,2,0,0，是可行解，z=13；

TTTT使用分支定界法解整数规划问题。 令z=31/2，x1=x2=0是可行解。 所以z=0，0z*31/2 把原问题分解为两个问题： （I） s.t.

2x1+3x214.5 4x1+x216.5 0x13; x20 （II） s.t.

max z2=3x1+2x2 max z1=3x1+2x2

2x1+3x214.5 4x1+x216.5 4x1; x20

将上述问题化为标准型，使用单纯形法求解：

x1=3，x2=2是最优整数解，z=13.

（2）max z=3x1+2x2 s.t.

2x1+3x214 2x1+x29

x1,x20 x1,x2是整数

（2） 解：

使用图解法或者单纯形法求解此问题，线性规划问题最优解是（13/4，5/2） 目标函数最优值max z=59/4；

凑整数时，X1=(3,2)T,是可行解，z=13；

X2=(3,3)T，是非可行解； X3=(4,2)T，是非可行解； X4=(4,3)T，是非可行解；

使用分支定界法求解原整数规划问题，令 令z=59/4，x1=x2=0是可行解。 所以z=0，0z*59/4； 把原问题分解为两个问题： （a）max z1=3x1+2x2 s.t. 2x1+3x214 2x1+x29

0x13; x20 （b）max z2=3x1+2x2 s.t. 2x1+3x214 2x1+x29 4x1; x20

解得：最优整数解是x1 =4，x2=1； 目标函数是14.

5.2用分支定界法解： Max z= x1 +x2 s.t.

2 x1+9x2/14 51/14 -2 x1+ x2 1/3

x1 ，x2 0 x1 x2都是整数。

图解法解得：最优解是B点（51/46+7/69-1/6，51/23+14/69） 目标函数最优值为：58/23+51/46-1/6 使用分支定界法求解，

令z=58/23+51/46-1/6，x1=x2=0是可行解； 因此 z=0，故0z*58/23+51/46-1/6 将原问题分解为下列问题： （I）Max z1= x1 +x2 s.t.

2 x1+9x2/14 51/14 -2 x1+ x2 1/3

x21 x1 ，x2 0

（I）Max z1= x1 +x2 s.t.

2 x1+9x2/14 51/14 -2 x1+ x2 1/3

x22 x1 ，x2 0

按照以上步骤，

求解最终得到：最优解是（1，2） 目标函数最优值z=3

5.3用Gomory切割法解如下问题： （1）max z=x1+x2 s.t. 2x1+x26 4x1+5x220

x1,x20 x1,x2是整数

解：

将上述问题化成标准型： max z=x1+x2+0x3+0x4 s.t. 2x1+x2+x3=6 4x1+5x2+x4=20

x1,x2，x3，x40 x1,x2，x3，x4是整数

单纯形法求得最优解是：X*= 5/3,8/3,0,0T，目标函数最优值变量之间的关系：

x1+5x3/6-x4/6=5/3 x2-2x3/3+x4/3=8/3

13/3 把系数和常数项都分解成为整数和非负真分数之和； 所以有： 2/3-5x3/6-5x4/60 2/3-（x3+x4）/30

加入松弛变量x5，继续迭代得到最终结果：X*= 0,4,2,0,0，目标函数最优值4

解得：最优整数解是x1 =0，x2=4； 目标函数是4. （3） max z=3 x1- x2 s.t. 3 x1-2 x23 -5x1-4x2-10 2x1+x25

x1,x20 x1,x2是整数

T解：

将原问题化成标准型，并使用单纯形法求解：

最优解为X*= 13/7,9/7,0,31/7,0，目标函数最优值30/7

从单纯形表可以得到变量间的关系，把系数和常数项都分解成整数和非负分数之和，可以得知： 6/7-（x3/7+2x5/7）0

加入松弛变量x7，把新的约束条件加入后，继续迭代，得到最终的结果： 最优解是x1=1，x2=2

目标函数最优值1.

5.4某城市的消防总部将全市划分为11个防火区，设有四个防火站，如图所示(课本P114)，其中①②③④是四个消防站，1，2，…11是防火区域，根据历史资料证实，各个消防站可在事先规定的允许时间内对所有负责的地区的火灾予以消灭，虚线表示各地区是哪个消防站负责，现在总部提出：是否可以减少消防站的数目，仍能够负责各个地区的防火任务，如果可以，关闭哪个？ 提示：对每个消防站定义一个0-1变量xi，令

T1xi

01代表当某个防火区域由第i个消防站负责，0代表不是它负责。然后对每个防火区域列出约束条件； 解：

1令xi

01代表当某个防火区域由第i个消防站负责，0代表不是它负责；i=1，2，3，4。 建立数学模型： Min z=xi

i14s.t. x1+x21

x11 x1+x31 x31 x1+x3+x41 x1+x41 x1+x2+x41 x2+x41 x41 x3+x41

有以上约束条件可以解得：

x1=x3=x4=1

继续求解

当x2=0时，是可行解，目标函数是3； 当x2=1时，是可行解，目标函数是4； 比较可以得到，最优解是

X*= 1,0,1,1，目标函数最优值是3.

T所以，可以关闭消防站②。

5.5在有相互排斥的约束条件的问题中，如果约束条件时型的，我们加yiM（yi是0-1变量，M是很大的常数）的方法统一在一个问题中。如果是型的，我们将如何利用yi和M呢？

解：在m个约束条件右端分别减去yiM（yi是0-1变量，M是很大的常数，i=1，2…m） 并且yim1

i1m5.6解0-1规划： （1）max z=4x1+3x2+2x3 s.t.

2x1-5x2+3x34 4x1+x2+3x53

x2+x31 x1,x2,x3=0或1

解：

将（0，0，0）（0，0，1）（0，1，0）（1，0，0）（0，1，1）（1，0，1）（1，1，0）（1，1，1）分别带入到约束条件中，可以得到：原问题的最优解是（0，0，1），目标函数最优值2.

（2）min z=2x1+5x2+3x3+4x4 s.t. -4x1+x2+x3+x40 -2x1+4x2+2x3+x44

x1+x2-x3+x41 x1，x2，x3，x4=0或1

解：

X*= 0,1,0,0是一个可行解，目标函数数值是4； 所以可以增加约束条件： 2x1+5x2+3x3+4x44

T把可能的解（0，0，0，0）（0，0，0，1）…（1，1，1，1）分别带入约束条件的问题中，得到最优解X*= 0,1,0,0，目标函数最优值4.

5.7有四个工人，指派他们完成4种工作，每人做各种工作所消耗的时间如下表，问指派哪个人去完成哪种工作，可以使得总耗时最小？ 任务 A B C D 人员 甲 15 乙 19 丙 26 丁 19 解：系数矩阵C为： 151926192124232218 17261921231718T18 23 17 21 21 22 16 23 24 18 19 17 ① 系数矩阵的每行元素减去该行的最小元素得矩阵B ② B矩阵的每列元素减去该列的最小元素得到矩阵A 此时，细数矩阵的每行每列都有元素0.

先给a11加圈，然后给a24加圈，划掉a44。给a32加圈，划掉a33得：

01102269440 003360此时，画圈的数目是3,少于4个，所以指派不成功，进入下一步， 给第四行打√号，给第四列打√号，给第二行打√号，将第一，第三行画一横线，将第四列画纵线，变换矩阵得到

001012610330 004250给第一，第四列打√号，对第一，第二，第四行打√号，给第一，第四列画一纵线，第三行画一横线，变换矩阵得到

甲 乙 丙 丁

001210410111 006030得到最优指派方案为： 甲—B；乙—A; 丙—C；丁—D。 所消耗的总时间是70. 试题：

1. （2006年复旦大学）采用变量代换，试把非线性0—1整数规划

maxzx12x2x3x1x2x3

3x14x2x33 s..tx,x,x12为30或1 转换成一个0—1整数规划。

解题分析：0—1规划即约束中自变量只能取值0或1。

当x2x31 1,解题过程：令y1 ，故有x2x3y1

否则 0,当x1x2x31 1,再令y2 ，故有x1x2x3y2

否则 0,而x12与x1等价，故原问题可等价地写为

maxzx1y1y2

3x14x2x33y1x2y1x3y2x1s..ty2x2 y2x3x2x3y11xxxy22123x1,x2,x3,y1,y2为0或1

2. （2005年南京大学）现要在5个工人中确定4个人来分别完成四项工作中的

一项工作。由于每个工人的技术特长不同，他们完成各项工作所需的工时也不同。每个工人完成每项工作所需工时如表5—1所示。

表5—1 所需工时 工人 工作 A Ⅰ Ⅱ Ⅲ 9 4 5 B 4 6 4 C 3 5 7 D 7 6 5 Ⅳ Ⅴ 7 10 5 6 2 7 3 4 试找出一个工作分配方案，使总工时最少。

解题分析：本题属“不平衡”指派问题，故应先虚拟一项工作，使其平衡，再按

常规求解即可。

解题过程：虚拟一项工作E，设每人完成E所需时间都是“0”，从而转化为五个

人完成五项工作的分配问题，再用匈牙利法求解。

最优解为：Ⅰ—C，Ⅱ—A，Ⅲ—B，Ⅳ—D，Ⅴ—E，即应安排工人Ⅰ、Ⅱ、Ⅲ、Ⅳ分别完成工作C、A、B、D，此时所用时间最少，为3+4+4+3=14。