运筹学(第五版)习题答案

资源大全更新时间:2025-05-05 13:31:28

2024年1月8日发(作者：衡水中学初中部数学试卷)

运筹学习题答案第一章（39页）1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。（1）max z=x1+x25x1+10x2£50 x+x³1 12x2£4 x1，x2³0 （2）min z=x1+1.5x2x1+3x2³3 x1+x2³2 x1，x2³0 （3）max z=2x1+2x2x1-x2³-1 -0.5x1+x2£2 x1，x2³0 （4）max z=x1+x2x1-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无约束

无约束

zk（2）max s=nmpk

zk=mååi=1k=1ikaikxik

å-xk=1=-1(i=1,...,n)

xik³0

(i=1……,m) (i=1…n; k=1,（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 1235678910x,x,x,x,x,x,x,x,x³0 初始单纯形表: 3 -4 2 cj®

CB

XB

-5 x5

5 x6

0 0 -M -M x9

x10

qi

b 2 14 x1

x2

x3

x7

x8

-M x10

0 x7

-4 1 1 1 -2 3 1 -1 -1 1 0 1 0 0 0 0 1 0 2 14

-M x9

-z¢

2 -2 [3] -1 2 -2 0 -1 1 0 0 2/3

4M 3-6M 4M-4 2-3M 3M-5 5-3M 0 -M 0 (2)解：加入人工变量x1，x2，x3，…xn，得：

，得：

Max s=(1/p)ikn=1mk=1ååaikxik-Mx1-Mx2-…..-Mxn

s.t.

mxi+xik=1

(i=1,2,3…(i=1,2,3…,n) åxik³0, xi³0,

(i=1,2,3…….,m) (i=1,2,3…n; k=1,2k=1M是任意正整数

是任意正整数

初始单纯形表：

c

jCB

XB--M …

-apk

apk

M M b x1x2…

xnx11x12

1112…

a1mpk

…

apk

…

n1n2amnpk

qi

…

x1m

…

0 …

xn1…

0 …

0

xn2

…

xnm

…

0 …

…

1 …

amnMpk+

-M x1

1 x2

1

1 0 0 1

…

0 1 …

0

1 0 …

0 a12pk0 0 …

1 an2Mpk+

-M …

-M -s …

…

xn

1 0 0 …

1 0 n0 0 M

…

0 a11

Mpk+…

…

1

…

an1…

+Ma1mMpk+Mpk+

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 12T解得：x=1；x=2 基解X=（1，2，0，0)为可行解

为可行解

z1=8 (2)T(1)同理，以（P，P）为基，基解X13是非可行解；

=（45/13，0，-14/13，0)是非可行解；

T以（P，P）为基，基解X14(3)=（34/5，0，0，7/5)是可行解，z3=117/5；

=（0，45/16，7/16，0)是可行解，z4=163/16；

=（0，68/29，0，-7/29)是非可行解；

是非可行解；

=（0，0，-68/31，-45/31)是非可行解；

(3)TTT以（P2，P3）为基，基解X以（P，P）为基，基解X24(4)(5)以（P4，P3）为基，基解X(6)最大值为z3=117/5；最优解X（2）解：

）解：

系数矩阵A是：

是：

=（34/5，0，0，7/5)。

Té1234ùêú

ë2112û

令A=(P1，P2，P3，P4) P1，P2线性无关，以（P1，P2）为基，有：

）为基，有：

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

2x1+x2=3-x3-2x4

令

x3，x4=0得

12x=-1/3，x=11/3

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

为非可行解；

同理，以（P1，P3）为基，基解X(3)(2)(1)T=（2/5，0，11/5，0)是可行解z2=43/5；

TT以（P，P）为基，基解X14是非可行解；

=（-1/3，0，0，11/6)是非可行解；

(4)以（P，P）为基，基解X23=（0，2，1，0)是可行解，z4=-1；

=（0，0，1，1)是z6=-3；

(2)TT以（P4，P3）为基，基解X2(6)最大值为z=43/5；最优解为X=（2/5，0，11/5，0)。

T1.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 12x，x³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 T1 x2

0 x3

0 x4

qi

CB

XB

x3

x4

x1

0 0 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

-z 0 x3

2 x1

-z 1 2 x2

x1

-z

解为：（15/4，3/4，0，0 )

Max z=33/4 迭代第一步表示原点；第二步代表C点（4，0，3，0)；

第三步代表B点（15/4，3/4，0，0 )。

（2）解：（图略）

（图略）

Max z=34 此时坐标点为（2，6）

单纯形法，标准型是：

Max z=2x1+5x2+0x3+0x4+0x5

TT

s.t.

x1+x3=4

2x2+x4=12

3x1+2x2+x5=18 x1,x2,x3,x4,x5³0 (表略) 最优解

最优解

X=（2，6，2，0，0 )

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

4，0，6)，第三步迭代得到最优解的点。

T(2)=（0，6，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 l

k当c2当c2c1c2kBC 时，

同号。

时，

，同号。

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

点有最大值

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

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

kBCl

当c2当c2kkABc1时，，c2同号。

同号。

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

点有最大值；

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

，目标函数在原点最大值。

l

kAB

k 0时，c1，

c2同号。

同号。

当c2当c20时，目标函数在A点有最大值

点有最大值

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

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

c1c2l

k 0时，，异号。

异号。

当c2当c2c10，

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

点有最大值；

c10，

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

点最大值。

kAB时，c1，

c2同号

同号

l

k= 当c220时，目标函数在AB线断上任一点有最大值

线断上任一点有最大值

当c0，目标函数在原点最大值。

，目标函数在原点最大值。

BCc1c2kl

k= 时，，同号。

同号。

当c2当c20时，目标函数在BC线断上任一点有最大值

线断上任一点有最大值

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

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

c1l

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

点有最大值

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

线断上任一点有最大值

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

l

c1l

l

解。

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

x1+x2+x3£15 0时，目标函数在C点有最大值

点有最大值

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

线断上任一点有最大值

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

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

c1c11.6分别用单纯形法中的大M法和两阶段法求解下列线性问题，并指出属于哪类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 -5x+6x+15x£15 2x1+x2+x3³5 x1，x2，x3³0 123（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 12356

2x-5x+x-x+x=10 x1,x2,x3,x5,x4,x6³0

M是任意大整数。

是任意大整数。

单纯形表：

cj

2 x1

3 x2

-5 x3

-M x4

0 x5

-M x6

qi

CB

XB

b -M x47

1 1 1 1 0 0 7

-M x610

-z -M x42 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 -

3M+2 3-4M 0 [7/2] 1 -5/2 x1

-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 )

目标函数最优值

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 T（单纯形表略）

（单纯形表略）

最优解

TX=（45/7，4/7，0，0，0 )

目标函数最优值

min w=0 第二阶段单纯形表为：

第二阶段单纯形表为：

2 cj

CB

XB

x2

x1

3 x2

-5 x3

0 x5

qi

b 4/7 45/7 x1

3 2 0 1 1 0 1/7 6/7 1/7 -1/7

-z 最优解是

最优解是

-102/7 0 T0 -50/7 -1/7

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

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)

目标函数最优值

min z=7 非基变量x的检验数s=0，所以有无穷多最优解。

，所以有无穷多最优解。

两阶段法：

第一阶段最优解X=（4/5，9/5，0，0，0，0 )是基本可行解,min w=0 第二阶段最优解（4/5，9/5，0，0，0，0 )

min z=7 非基变量x3的检验数s3=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 单纯形表计算略

单纯形表计算略

TT33T

当所有非基变量为负数，人工变量x7=0.5，所以原问题无可行解。

，所以原问题无可行解。

两阶段法（略）

（4）解法一：大M法

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

两阶段法略

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

的上界和下界；

Max z=c1x1+c2x2

1111221ax+ax£b

a21x1+a22x2£b2

1£c1£3，4£c2£6，8£b1£12，10£b2£14，2£a12£5，其中：-1£a11£3，2£a21£4，4£a22£6

解：

l 求Z的上界

的上界

Max z=3x1+6x2

s.t.

-x1+2x2£12

2x1+4x2£14 x2，x1³0 加入松弛变量，化成标准型，用单纯形法解的，最优解

加入松弛变量，化成标准型，用单纯形法解的，最优解

X=（0，7/2，5，0 )

目标函数上界为z=21 存在非基变量检验数等于零，所以有无穷多最优解。

存在非基变量检验数等于零，所以有无穷多最优解。

l 求z的下界

的下界

线性规划模型：

Max Z= x1+4x2

s.t. 3x1+5x2£8

4x1+6x2£10

x2，x1³0 加入松弛变量，化成标准型，解得：

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

T

最优解为

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

目标函数下界是z=32/5 1.8表1-6是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，a，a，a，d，c，c为待定常数，试说明这些常数分别取何值时，以下结论成立。

结论成立。

（1）表中解为唯一最优解；（2）表中解为最优解，但存在无穷多最优解；（3）该线性规划问题具有无界解；（4）表中解非最优，对解改进，换入变量为x1，换出变量为x6。

基b x3

d x4

2 x6

3 jjT12312x1

x2

x3

x4

x5

a2

x6

4 -1 a3

a1

-3 -5 1 0 0 0 0 1 0 0 0 0 1 0 -1 -4 -3 c-z

c1

解：

c2

（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.

-0.4x1+0.6x2+0.6x3£0 x7+0.45x8+0.95x9

-0.2x1-0.2x2+0.8x3£0

-0.85x4+0.15x5+0.15x6£0

-0.6x4-0.6x5+0.4x6£0

-0.7x7-0.5x8+0.5x9£0

x1+x4+

x2+x5+x7£2000 x8£2500 x9

x3+x6+£1200 x7x8x9,,

³0 x1,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

B1

B2

B3

产品

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 10000 4000 7000 4000

设备费用

300 321 250 783 200

原料费

单价

解：

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

B工序的x3，x4，x5件，产品Õ，设A1,A2完成A工序的产品x6，x7件；B工序时，工序的B1x8A2x9B2完成B的产品为件；产品111，完成A工序的件，完成Bx9件；

件；

x1+ x2= x3+ x4+ x5

x6+ x7= x8

建立数学模型：

Max z=(1.25-0.25)*( 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

x7x8x9x1,x2,x3,x4,x5,x6,,,

³0 最优解为X=（1200，230，0，859，571，0，500，500，324 )

最优值1147. 试题：

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

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

如下表所示：

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

型。

T

饲料

1 2 表

1—1 蛋白质（克）（毫克）价格（元/公蛋白质（克）矿物质（克）

矿物质（克）维生素斤）

斤）

3 1 0.5 0.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ïïx1+0.5x2+0.2x3+2x4+0.5x5³í

1+x2+0.2x3+2x4+0.8x5³100x0.5ïï³1,x2,x3,x4,x5x0î

第二章（67页）

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

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

6x1-2x2+3x3

（1）Max z=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 Tæ10öB0B045令B=（P，P）=çè01÷ø

X=（x,x),C=(0,0) 045Tæ2-12öN0123÷

, X=（x，x，x)

N=(P,P,P)=çè104ø0123-10æ2÷ö

ç10ö÷,b=çC=(6,-2,3)，B0=æè01øè4øN0非基变量的检验数

非基变量的检验数

N0CB0B0N0CN0CN-==(6,-2,3) s=0-1因为x1的检验数等于6，是最大值，所以，x1为换入变量，

为换入变量，

B-10-1æ2öæ2ö01b=ç÷；BP=ç÷

è4øè1ø0由q规则得：

规则得：

q=1 x4为换出变量。

为换出变量。

Tæ20ö1B15÷,X=（x,x)，CB=(6,0). B=(P，P)=çè11ø1451N=(P,P,P),

X=（x，x，x)

1423N1T423-1æ0.50öæö÷,b1=ç1÷

CN1=(0，-2，3)，B1=çè-0.51øè3ø非基变量的检验数

非基变量的检验数

sN1=（-3，1，-3）

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

为换入变量；

-102æ-0.5öBP=èç0.5÷ø

由q规则得：

规则得：

q=6 所以x5是换出变量。

是换出变量。

Tæ2-1öB212B=(P，P)=ç÷,X=（x,x)，CB2=(6,-2). è10ø212N2=(P4,P5，P3),

XN2=（x4，x5，x3)

T-1æöæöCN2=(0，0，3)，B2=ç01÷,b2=ç4÷

è-12øè6ø非基变量的检验数

非基变量的检验数

sN2=（-2，-2，-9）

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

æ4ö最优解X= ç÷

è6ø即：X=（4,6,0)

目标函数最优值

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 TM是任意大的正数。

是任意大的正数。

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

原问题最优解是X=（0.6，1.2，0）

目标函数最优值：

z=12/5 2.2已知某线性规划问题，用单纯形法计算得到的中间某两步的加算表见表，试将空白处数字填上。

表，试将空白处数字填上。

3 5 4 0 0 0 cj

CB

XB

x2

x5

5 0 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 -10/41 4/41 -12/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

x2

x5

x6

cj-zj

5 0 0

. . .

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写出下列线性规划问题的对偶问题。

写出下列线性规划问题的对偶问题。

2 x1+2 x2+4 x3

（1）min z=

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=2y-3y-5y

s.t.

2y1-3y2-y3£2

3y1-y2-4y3£2

5y1-7y2-6y3£4 y1,y2,y3³0 1234123(2)max z= x+2x+3 x+4 x

-x1+x2-x3-3x4=5 6x1+7x2+3x3-5x4³8 12x1-9x2-9x3+9x4£20 x1,x2³0;x3

£0;x4无约束

无约束

解：

对偶问题：

Min w=5y1+

-y1+6y3+12

y1+7y3-9y4

y4³1 y4³2 £3 =4

-y1+3y3-9y4

-3y1-5y3+9y4

y1无约束，y3£0；y4³0

mn（3）min z=inåå-1j=1cijxij

åj=1xij=ai

i=1,…i=1,…,m mi=1xij=bj

j=1,…j=1,…,n åxij³0 min解：

解：

\'\'ij\'\'m+j对偶问题: max w=i=1ay+j=1byås.t. y+y

(4) n\'\'i\'\'m+jåå

£cij

y,y\'\'i\'\'m+j….n i=1,2,….m; j=1,2, 无约束

无约束

i=1,2,…Max z=j1cjxj

å=nåj=1naijxj£bi, i=1,…., m1£m

åj=1aijxj=bi,

i=m1+1,m1+2,...,m

xj³0,当j=1，….，n1£n

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

m解：

解：

Min w=i1bjyi

=\'\'å=s.t.

miji=1ay³cj

j=1,2,3…j=1,2,3…n1

\'\'iå

måi=1\'\'ay³cj

j=ij\'\'in1+1, n1+2,…+2,….n yi³0

i=1,2…i=1,2…. m1

11y无约束，

无约束，

i=m+1, m+2…+2….m i\'\'

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

（2）如线性规划的对偶问题无可行解，则原问题也一定无可行解。

）如线性规划的对偶问题无可行解，则原问题也一定无可行解。

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

问题一定有有限最优解。

(1)错误，原问题有可行解，对偶问题可能存在可行解，也可能不存在；

（2）错误，对偶问题没有可行解，原问题可能有可行解也可能有无界解；

（3）错误，原问题和对偶问题都有可行解，则可能有有限最优解也可能有无界解；

有无界解；

2.5设线性规划问题1是：

是：

nMax

z1=nåj=1cjxj

aijxj£bi ，i=1，2…，m åj=1xj³0,j=,n

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

）是其对偶问题的最优解。

又设线性规划问题2是

n**Max z2=nåj=1cjxj

aijxj£bi

+ki ，i=1，2…，m åj=1xj³0,j=,n

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

是给定的常数，求证：

mmax

z2£max

z1+åi=1kiyi

*解：

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

Max z1=CX s.t.

AX£b

X³0 b=（b)

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

）已知。

Max z2=CX

s.t.

AX£b+k

X³0 k=（km)

设可行解为X2，对偶问题最优解是Y2,对偶问题是，

对偶问题是，

Min w=Y(b+k) S.t. YA ³C

Y ³0 Y2Y2因为是最优解，所以（b+k）£Y1（b+k）

TX2是目标函数z2的可行解，AX2Y2X2Y2b+k A；££（b+k）£Y1b+Yk 原问题和对偶问题的最优函数值相等，所以不等式成立，证毕。

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

2.6已知线性规划问题

已知线性规划问题

Max z=c1x1+c2x2+c3x3

éa11ù1êúx+ëa21ûéa12ù2êúx+ëa22ûéa13ù3êúx+ëa23ûé1ù4êúx+ë0ûéb1ùé0ùêúx5=êú

ëb2ûë1ûxj³0,j=1,...,5

用单纯形法求解，得到最终单纯形表如表所示，要求：

（1）求a11，a12，a13，a21，a22，a23，b1，b2的值；

的值；

（2）求c1,c2,c3的值；

的值；

XB

x3

b

3/2 x1

x2

x3

x4

x5

1 0 1 1/2 -1/2

x2

cj-zj

2 1/2 -3 1 0 0 0 -1 0 2 -4

解：

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

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

éa11C1=êëa21a12a22a13a2310b1ùú

201bû最终单纯形表的增广矩阵为

最终单纯形表的增广矩阵为

é1010.5-0.51.5ùú

C2=ê22ûë0.510-1C2是C1作初等变换得来的，将2C2作初等变换，使得C2的第四列和第五列的矩阵成为C的单位矩阵。有：

的单位矩阵。有：

a11=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 jx³0，j=1,…j=1,…4 12对偶变量y，y，其对偶问题的最优解是y=4，y=1，试应用对偶问题2*1*的性质，求原问题的最优解。

的性质，求原问题的最优解。

解：

对偶问题是：

Min w=8y1+12y2

s.t. 2y1+2y2³2 2

2y³1

y1+y2³5

y1+2y2³6

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

YSXˆ=0，当且仅当Xˆ，Yˆ是最优解。

是最优解。

设

X,Y是原问题和对偶问题的可行解，YS=（y3，有：

有：

YXS=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)

目标函数最优值为31/13。

（2）令：w=-z，转化为标准形式：

，转化为标准形式：

Max w=-3x1-2x2-x3-4x4+0x5+0x6+0x7

s.t. -2x1-4x2-5x3-x4+x5=0 12346T-3x+x-7x+2x+x=-2 -5x1-2x2-x3-6x4+x7=-15 x1，x2，x3，x4，x5，x6，x7³0 单纯形法略

单纯形法略

原问题最优解：

X=（3，0，0，0，6，7，0)

目标函数最优值为9。

2.9现有线性规划问题

现有线性规划问题

5 5x1+5x2+13x3

max z=-- x1+x2+3x3

£20 12 x1+4x2+10x3

£90 x1 ，x2，

x3

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

么变化？

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

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

x的系数向量变为ç÷

è12ø1（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)

目标函数最优值为100。

非基变量x1的检验数等于0，原线性问题有无穷多最优解。

，原线性问题有无穷多最优解。

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

Db¢=BDb

因此

b¢=b+Db¢

单纯形法解得：

最优解：

X=（0，0，9，3，0)

目标函数最优值为117。

2右端常数变为70 （2）约束条件○有

Db¢=BDb

因此

b¢=b+Db¢

单纯形法解得，最优解：

TTT-1-1X=（0，5，5，0，0)

目标函数最优值为90。

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

，所以最优解不变。

æ0ö（4）x1的系数向量变为ç÷

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

，所以最优解不变。

3

（5）解：加入约束条件○用对偶单纯形表计算得：

用对偶单纯形表计算得：

X=（0，25/2，5/2，0，15，0)

目标函数最优值为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.

T

8x1+2x2+10x3£300 10x1+5x2+8x3£400 2x1+13x2+10x3£420 x1,x2,x3³0 把上述问题化为标准型，用单纯形法解得：

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

最优解：

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

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

（2）

设备B的影子价格为4/15千元/台时，借用设备的租金为0.3千元每台时。

所以，借用B设备不合算。

设备不合算。

（3）

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

，系数向量分别为：

TP=(12,5,10)

7T8P=(4,4,12)

检验数s7=-0.06，所以生产IV不合算，

不合算，

合算。

s8=37/300，生产V合算。

单纯形法计算得：

最优解：

X=（107/4，31/2，0，0，0，0，55/4)

目标函数最优值为10957/80。

，大于零。

（4）改进后,检验数s¢=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 131T3x+2x

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 1353x+2x+x=460

x1+4x2+x6=420 x1，x2，x3，x4，x5, x6³0 令t=0，用单纯形表计算，

，用单纯形表计算，

cj

3-6t B 100 230 20 x1

2-2t x2

5-5t x3

0 x4

0 x5

0 x6

qi

CB

XB

x2

x3

x6

2-2t 5-5t 0 -z -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，首先出现s4，s5大于0，所以当0£t£1时有最优解。

时有最优解。

X=（0，100，230，0，0，20)

目标函数最优值为1350（t-1）（0t1）。

t=1是第一临界点。

是第一临界点。

££t大于1时，x6是换出变量。

是换出变量。

t大于1，最优解是：X=（0，0，

0，430，460，420)

目标函数最优值为

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

（2）

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

，单纯形法解得：

t开始增大时，当t大于8/3时，首先出现s大于0，所以0£t£8/3，得最4TT优解。

优解。

目标函数最优值Max z(t)=220，（0£t£8/3）

所以，t=8/3为第一临界点。

为第一临界点。

4当8/35，首先s1大于0，8/3

的时候，最优解为：

X=（0，15，0，5)

目标函数最优值为180+15t ，（8/3

所以，t=5为第二临界点。

为第二临界点。

当t>5时，x1是换入变量，x2为换出变量，单纯性法计算，

为换出变量，单纯性法计算，

当t继续增大，所有检验数都非正，所以当t>5，最优解：

，最优解：

X=（15，0，0，5)

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

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

用单纯形法计算得：

当t开始增大，t大于5时，首先出现b2小于0，当0£t£5，最优解为：

，最优解为：

X=（10+2t，0，10+2t，5-t，0)

目标函数最优值为6t+30 ，（0£t£5）。

所以t=5是第一临界点。

是第一临界点。

当t大于5时，x4是换出变量，x5是换入变量。用对偶单纯形法计算，

是换入变量。用对偶单纯形法计算，

当t大于5时，最优解为：

时，最优解为：

X=（10+2t，15+t，0，0，t-5)

目标函数最优值为35+5t。

（4）解：

）解：

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

，用单纯形法计算，得：

当t开始增大，当t大于6时，首先出现b2小于0，当0£t£6，有最优解：

TTTTTX=（0，0，0，10+t/3，0，18-3t，45-5t)

目标函数最优值为150+5t （0£t£6）。

当t大于6时，首先出现b2小于0，x6是换出变量，x2是换入变量，使用单373纯形法计算得：t继续增大，当t大于11时，b首先小于零，x是换出变量，x为换入变量，对偶单纯形法迭代得：

为换入变量，对偶单纯形法迭代得：

当

t≤59，有最优解：

，有最优解：

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

目标函数最优值为5t/2+345/2 ，（11

试题：

1. （2006年西北工业大学）已知线性规划：

年西北工业大学）已知线性规划：

maxz=3x1+2x2

T

ì-x1+2x2£4ïï3x1+2x2£í

1-x2£3xïïîx1,x2³0（1）用单纯形法求解该线性规划问题的最优解和最优值；

用单纯形法求解该线性规划问题的最优解和最优值；

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

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

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

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

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

T18332ù解题过程：X=é00

ëûê555úmaxz=12，有无穷多解。

，有无穷多解。

对偶问题为：

*minw=4y1+12y2+3y3

ì-y1+y2+y3³ïí2y1+2y2-y3³2

ïy1,y2,y3³0îY=010

w=z=12

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

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

maxz=x1+2x2+x3

***ìx1+x2-x3£2ïïx1-x2+x3=11-2+x3³stíï2

ï2x³x£x3 无限制îx10,x20,并利用弱对偶性说明z的最大值不大于1。

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

123minw=2y+y+2y

ìy1+y2+2y3³1ïïy1-y2+y3£2s..tí

123yyyï-++=1ïy1³0,y3£0,y21，0）是上述对偶问题的可行解，由弱对偶性可知，对原问题的由于（0，î任一可行解

任一可行解

bX都有

都有

CX£Y

é2ùêú==而Yb[010]ê1ú1，所以z的最大值不大于1。

êúë2û

第三章（86页）

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

什么？

表3—1

销地1

产量

2 3 4

产地

1 0

2

3 5

销量

5

表3—2

销1

地

产地

15

2 3

15

4

10

5

15

25

5

产量

1 150 250 400

2 200 300 500

3 250 50 300

4 90 210 300

5 80 20 100

销量

240 410 550 330 70

解：

表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

2

3

9

2

1

4

6

10

3

8

1

7

11

产量

12

14

4

表3-4

销1

地

产地

1 10

2 3 4 5

产量

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 2 3 列差额

列差额

5 2 3 1 1 4 6 3 8 1 7 6 4 1 3

从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，上表中，第三列是最大差额列，此列中最小元素为1，由此可以确定产地2的产品应先供应给销售地3，得到下表：

，得到下表：

2 3 销地

产量

销地

1 产量

产地

1

2 3 9 10 销量

销量

同时将运价表第三列数字划去，得

11 11 12 14 4

销地

1 2 产量

产量

产地

1 5 1 12

2 2 4 14

3 3 6 4

9 10 销量

销量

对上表中的元素，计算各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列，重复上面的步骤，直到求出初始解，最终结果是：

该表的最右列和最下列，重复上面的步骤，直到求出初始解，最终结果是：

销地

产地

1 1 2 3 产量

产量

2 10

12 2 3 11 14 3 4 4

9 10 11 销量

销量

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

相同）

最终得出原问题的初始解：

2 3 4 5 销地

产量

销地

1 产量

产地

1 25

2 20 30

3 20

4 30

20 20 30 10 25 销量

销量

3.3用表上作业法求给出运输问题的最优解（M是任意大正数）

是任意大正数）

（1）

销地

产地

1 2 3 销量

销量

解：

甲乙丙丁产量

产量

3 2 4 3 7 4 3 3 6 3 8 2 4 2 5 2 5 2 3

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 2 3 甲乙丙丁产量

产量

3

0

3

2

2 2 0

2 5 2 3

3 3 销量

销量

使用位势法进行检验：

1上表中，数字格处填入单位运价并增加一行一列，在列中填入ui（i=1，○2，3），在行中填入vj（j=1，2，3，4），先令同）来确定销地

销地

产地

1 2 3 uivicij+=（i，jÎB，B为基，下ui和，得到下表：

，得到下表：

甲乙丙丁

viui

vi3

4 3

3 2

3

5 4 2

4 0 -2 1

2由sij=cij-（ui+vi）○（i，j为非基，下同）计算所有空格的检验数，并在每个格的右上角填入单位运价，得到下表

每个格的右上角填入单位运价，得到下表

销地乙丙

销地甲

产地

1 2 3 3 0 5

2 1 4 4 0 0 7 1 4 0 3 2 8 3 6 丁

ui4 0

0 2 -2 0 5 1 0

vi3

2 5 4

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

，此问题达到最优解。

又因为s34=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 2 甲

1

乙

2

丙

1 3

4 丁

6

6 产量

产量

4 9 4

3 4

5 2 销量

销量

使用位势法进行检验：

1上表中，数字格处填入单位运价，并增加一行一列，○数字格处填入单位运价，并增加一行一列，在列中填入ui（i=1，uiviij2，3），在行中填入v（j=1，2，3，4），先令u=0，由

，由

+=c（i，jÎB，Buivi为基，下同）来确定和. j12由sij=○cij-（uivi（i，jÎN）计算所有空格的检验数，并在每个格的右+）上角填入单位运价，得到下表

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

销地

产地

1 2 3 甲乙丙丁

ui12 0

10 0

16 8 6 5 0 3 10 6 6

10 4 8 7 0 7 1 5 10 4 11 0 9 -2 10 -5

vi

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

，此问题达到最优解。

此问题有唯一最优解。

总运费min z=118 （3）

乙丙丁戊产量

产量

销地

甲

产地

1 2 3 4 10 2 1 8 20 10 20 6 5 8 7 3 9 30 10 7 10 6 4 5 5 6 2 9 4 4 6 2 4 销量

销量

解：（3）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售地己，令单位运价为0。销量为2。这样就达到了产销平衡。

。这样就达到了产销平衡。

用伏格尔法求初始解：

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

和最下列。

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

应己的需要，同时划掉己列的数字。

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

乙丙丁戊己产量

产量

销地

甲

产地

1 2

4

3

2 2

4 2

2 5 6 2 9

3

4 4 3

4 4 6 销量

销量

使用位势法进行检验：

1上表中，数字格处填入单位运价，并增加一行一列，○数字格处填入单位运价，并增加一行一列，在列中填入ui（i=1，

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

，由

jÎB，B为基，下同）来确定2由sij=○uivicij+=（i，uivi和. cij-（uivi（i，jÎN）计算所有空格的检验数，并在每个格的右+）上角填入单位运价。

上角填入单位运价。

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

，此问题达到最优解。

又因为s14=0，此问题有无穷多最优解。

，此问题有无穷多最优解。

总运费min z=90 （4）

乙

销地

甲

产地

1 2 3 4 5

10

13 0

9 11

M 6

23 18

21 11

18 30

80 丙

29 丁

13

14 3 戊产量

产量

22 100

19 80 34 60 16 120 M 140 销量

销量

解：（4）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售地己，令单位运价为0。销量为40。这样就达到了产销平衡。

。这样就达到了产销平衡。

用伏格尔法求初始解：

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

和最下行。

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

素，同时划掉所在列或行的元素。

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

并用位势法进行检验：

乙丙丁戊己

销地

甲

ui

产地

1 2 3 18

10 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 24

28

36

100 120 100 60

0 4 4 5 2 24 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 -5 17 0 12 -12

vi

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

，此问题达到最优解。

又因为s31=0，此问题有无穷多最优解。

，此问题有无穷多最优解。

总运费min z=5520 3.4

已知运输问题的产销平衡表、单位运价表及最优调运方案如下表所示

表1

产量

销B2

B4

B1

B3

地

产地

A1

A2

A

3

0

5

10

15

10

15

25

5

销量

5

表2

销地

B1

产地

B21

7

14

c22

B3

B411

20

18

A1

10

12

2

20

9

16

A2A3

（1）（2）解：

1在对应表的数字格处（c22未知）填入单位运价，并增加一行，在列中(1)○A2A2到到B2B4的单位运价在什么范围变化时，上述最优方案不变？

在什么范围变化时，上述最优方案不变？

的单位运价变为何值时，有无穷多最优方案。除表1中方案外，至少写出其他两个。

外，至少写出其他两个。

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

，由

uivicij+=

（i，jÎB）来确定2由sij=○uivi和. cij-（uivi（i，jÎN）计算所有空格的检验数，并在每个格的右+）上角填入单位运价（c22未知）。

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

c22-3³0 c22+10³0 10-c22³0 24-c22³0 18-c22³0 解得: 3£c22£10 单位运价在此区间变化时，最优调运方案不变。

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

（2）○1在对应表的数字格处（c未知）填入单位运价，并增加一行，在uivicijji1vuu列中填入（i=1，2，3）2，3，4），在行中填入（j=1，，先令=0，由

+=（i，jÎB）来确定22ui和. vi2由sij=cij-（ui+vi）○（i，jÎN）计算所有空格的检验数，并在每个格的右上角填入单位运价（c22未知）。

有无穷多最优方案，则至少有一个非基变量的检验数为0. 24取c-17=0，所以单价变为17时，该问题

时，该问题有无穷多最优调运方案。

有无穷多最优调运方案。

另外的两种调运方案：

1 ○销地

销地

产地

A1

A2

B1

B2

B3

B40 产量

产量

15 25

0 15

15 10

A3

5 5

15

10 5 销量

销量

2

○销地

销地

产地

A1

A2

A3

B1

B2

B3

B4

产量

15 25 5

0 5 15 0

15

10

5 15 15 10 销量

销量

3.5

某百货公司去外地采购ABCD四种规格的服装，数量分别为：A,1500套；B，2000套；C，3000套；D，3500套；有三个城市可以供应上述服装，分别为：I，2500套，II，2500套；III，5000套。已知下表，求预期盈利最大的采购方案。

A B C D

I

II

III

10

8

9

5

2

3

6

7

4

7

6

8

解：

因为利润表中的最大利润是10，所以令M=10，用M减去利润表上的数字，此问题变成一个运输问题，见下表：

此问题变成一个运输问题，见下表：

销地

A B

产地

I 0 5 C D 产量

产量

4 3 2500 II 2 8 3 4 2500 III 1 7 6 2 5000 1500 2000 3000 3500 销量

销量

使用伏格尔法计算初始解：

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

和最下行。

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

素，同时划掉所在列或行的元素。

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

销地

产地

I II A B C D 产量

产量

1500

500

500 2500

3000

3500 3500 2500 2500 5000

III 1500

1500 2000 销量

销量

使用位势法检验：

1数字格处填入单位运价，并增加一行一列，在列中填入ui（i=1，2，3）○，ijiiji在行中填入v（j=1，2，3，4），先令u1=0，由

）来确定u，由

u+v=c（i，jÎB，和. 2由sij=○vicijuivi（i，jÎN）计算所有空格的检验数，并在每个格的右-（+）上角填入单位运价。

上角填入单位运价。

如果没有得到最优解，用逼回路法进行改进。

盈利最大方案：

销地

A B C D

产地

I 0 5 4 0 0 2

II 2 8 3 3 4 0 4 III 1 7 6 ui3 0

4 -1 2 1

vi0 0

1 5 1 4

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 150

B 140 30 C

290 30 需求

需求

使用位势法检验：

250

270

10 70 80 400 450 70

1数字格处填入单位运价，并增加一行一列，在列中填入ui（i=1，2，3）○，在行中填入vj（j=1，2，3，4），先令u1=0，由

，由

uivicijui+=（i，jÎB，）来确定vi和. 2由sij=○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¢，B2¢，B3¢是三年的加班能力，S是事先积压产生的供货能力。第三年的需求量是4艘。此问题产销不平衡，增加设想销地A4，运价0，销量7. 使用伏格尔法求初始解：并用位势法检验：

使用伏格尔法求初始解：并用位势法检验：

此问题有无穷多最优解，

总运费

min z=4730万元

万元

销地

213A

A

产地

B1

B1¢

B2

B2¢

B3

B3¢

供应量

A4

0 0 0

0

-60 0 60 60 60 -10 60 -460

500

540

600

550 620 S 40

500 540 560 需求量

需求量

试题：(2001年上海大学)

某产品由产地Ai发往销地Bj的每吨运费如下表：

的每吨运费如下表：

B1 元/吨

B2

B3

供应量（吨）

150 200 250

A1 50 40 60 A2

45 30 65 A3

20 10 50 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íx11x21x31++=150ïx12+x22+x32=220ïx13ï+x23+x33=180ïxijijî³0,,=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 150 10 220 50 180 0 50 250

由最小元素法可得到如下的一个初始基本可行解：

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=d+d

（4）min z=d1-d1

解：（1）不正确

）不正确

（2）正确

）正确

（3）正确

）正确

（4）正确

）正确

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

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

-+-1+1-+-+

（1）min z=P1（d1+d1）+P2（2d2+d3）

s.t. x-10x+d-d=50 12-1+1-+++3x1+5x2+d2-d2=20 8x+6x+d-d=100 12-3+3-+x，x，d，d，d，d，d，d³0 12-1+1+2-2-3+3（2）min z=P（d+d）+Pd+Pd+P(d+1.5d) s.t.

x+x+d-d=40 12-1+11+3+42+13-24-3-4x+x+d-d=100 12+2+-2x1+d3-d3=30 x+d-d=15 212-1+1-1+1+2-2-2-3+3+3-4+4-4+4-x，x，d，d，d，d，d，d,d,d³0 P（d+d）+P

d+Pd

(3) min x+x+d-d=10 12-1+13x+4x+d-d=50 12-2+28x+10x+d-d=300 12-3+3x1，x2，d1，d1，d2，d2，d3，d3³0 -++--+解

（1）满意解是：（50，0）

（2）满意解是：（25，15）

（3）满意解是：（10，0）

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

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

（1）min z=P

d+P

d+P（5d+3 d）+P

d

1234-1+

x+x+d1-d1=80 1212-2+2-+x+x+d- d=90

更多推荐

问题,目标,对偶,函数,单位,运价

本文发布于:2024-01-08 22:25:21，感谢您对本站的认可！

本文链接:https://www.sxydy.com/post/shijuan/a2750038518655dd2d101fab7b9f56b7.html

问题目标对偶函数单位运价

上一篇：数值分析第五版第1章习题答案-李庆扬
下一篇：运筹学(第五版) 习题答案

发布评论取消回复

评论列表（有 0 条评论）

运筹学(第五版)习题答案

发布评论取消回复

最近发表

热门文章

标签列表

运筹学(第五版)习题答案

相关文章

发布评论取消回复

最近发表

热门文章

标签列表