最全运筹学习题及答案

本文格式为Word版，下载可任意编辑——最全运筹学习题及答案第1页共64页

运筹学习题答案

第一章（39页）

1.1用图解法求解以下线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。（1）maxz?x1?x25x1+10x2?50

x1+x2?1x2?4x1，x2?0

（2）minz=x1+1.5x2

x1+3x2?3x1+x2?2x1，x2?0

（3）maxz=2x1+2x2

x1-x2?-1-0.5x1+x2?2x1，x2?0

（4）maxz=x1+x2

x1-x2?0

3x1-x2?-3

x1，x2?0

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

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

第2页共64页

（1）minz=-3x1+4x2-2x3+5x44x1-x2+2x3-x4=-2

x1+x2+3x3-x4?14

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

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

（2）maxs?nmzkpkzk???aikxiki?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标准型：Maxz?=3x1-4x2+2x3-5(x5-x6)+0x7+0x8-Mx9-Mx10s.t.

-4x1+x2-2x3+x5-x6+x10=2x1+x2+3x3-x5+x6+x7=14-2x1+3x2-x3+2x5-2x6-x8+x9=2x1,x2,x3,x5,x6,x7,x8,x9,x10?0初始单纯形表:3cj?CBXBx10x7-4x22x3-5x55x60x70x8-M-Mx9x10?ib214x1-M0-4111-231-1-1101000010214第3页共64页

-Mx92-2[3]-12-20-11002/3-z?4M3-6M4M-42-3M3M-55-3M0-M0(2)解：参与人工变量x1，x2，x3，…xn，得：Maxs=(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)CBM是任意正整数初始单纯形表：--M…-a11cjpkMMb…xnx11XBx1x211…1nM1001……0000…01…0…………10…0a11?Ma12pk……a1mpk…an1…pkan2pk……amnpk?ix12x1mxn1xn2xnm-M-M…-M-sx1x210…0a12?M………………0a1m?M…0…0………1…an1?M00…1an2?M……………00…1amn?M…xnpkpkpkpkpkpk1.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标函数，确定最优解。（1）maxz=2x1+3x2+4x3+7x42x1+3x2-x3-4x4=8x1-2x2+6x3-7x4=-3

x1,x2,x3,x4?0

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

第4页共64页

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+4x4x1-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???第5页共64页

令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）maxz=2x1+x23x1+5x2?156x1+2x2?24

x1，x2?0

（2）maxz=2x1+5x2

x1?4

2x2?123x1+2x2?18

x1，x2?0

第6页共64页

解：（图略）

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

标准型是maxz=2x1+x2+0x3+0x4s.t.3x1+5x2+x3=156x1+2x2+x4=24x1,x2,x3,x4?0单纯形表计算：cj2b1524034-83/415/4-33/4x11x20x30x4?iCBXBx3x400-z02-z12-z3[6]2010010521[4]1/31/31001001001/4-1/12-1/12010-1/21/6-1/3-1/85/24-7/24543/412x3x1x2x1解为：（15/4，3/4，0，0)TMaxz=33/4

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

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

第7页共64页

s.t.x1+x3=42x2+x4=123x1+2x2+x5=18

x1,x2,x3,x4,x5?0

(表略)

最优解X=（2，6，2，0，0)TMaxz=34

迭代第一步得X(1)=（0，0，4，12，18)T表示原点，迭代其次步得X(2)=（0，6，4，0，6)T，第三步迭代得到最优解的点。1.5以1.4题（1）为例，具体说明当目标函数中变量的系数怎样变动时，满足约束条件的可行域的每一个顶点，都可能使得目标函数值达到最优。解：目标函数：maxz=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，目标函数在原点最大值。

kABk

cc0时，1，2同号。

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

第8页共64页

?k当c2当c2cc0时，1，2异号。c0，1c0，1kAB0时，目标函数在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时，maxz=?c1??

c1x1

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

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

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

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

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

x1+x2+x3?15

2x1-5x2+x3?24

x1，x2?0

（2）minz=2x1+3x2+x3

第9页共64页

x1+4x2+2x3?8

3x1+2x2?6

x1，x2，x3?0

（3）maxz=10x1+15x2+12x35x1+3x2+x3?9-5x1+6x2+15x3?152x1+x2+x3?5

x1，x2，x3?0

（4）maxz=2x1-x2+2x3

x1+x2+x3?6

-2x1+x3?22x2-x3?0

x1，x2，x3?0

解：（1）解法一：大M法

化为标准型：

Maxz=2x1+3x2-5x3-Mx4+0x5-Mx6s.t.x1+x2+x3+x4=72x1-5x2+x3-x5+x6=10

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

单纯形表：cj2b7x13x2-5x3-Mx40x5-Mx6?iCBXBx4-M1111007第10页共64页

-Mx61017M25[2]-512M-51/21/20010-1-M1/2-1/210-1/21/254/7--z-M2x4x13M+23-4M0[7/2]1-5/2-z32x2x12M-1004/745/701(7/2)M+80.5M-601001/76/7-50/72/75/70.5M+1-1.5M-11/7-1/7-1/71/7-z-102/70-M-16/7-1/7-M+1/7最优解是：X=（45/7，4/7，0，0，0)T目标函数最优值maxz=102/7有唯一最优解。解法二：第一阶段数学模型为minw=x4+x6S.t.x1+x2+x3+x4=72x1-5x2+x3-x5+x6=10x1,x2,x3,x4，x5,x6?0（单纯形表略）最优解X=（45/7，4/7，0，0，0)T目标函数最优值minw=0其次阶段单纯形表为：2cj3x2-5x30x5?iCBXBx2x1b4/745/7x13201101/76/71/7-1/7

第11页共64页

-z最优解是-102/700-50/7-1/7X=（45/7，4/7，0，0，0)T

Maxz=102/7

（2）解法一：大M法

z?=-z有maxz?=-min（-z?）=-minz化成标准形：

Maxz?=-2x1-3x2-x3+0x4+0x5-Mx6-Mx7S.T.

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

线性规划最优解X=（4/5，9/5，0，0，0，0)T目标函数最优值minz=7非基变量x3的检验数?3=0，所以有无穷多最优解。两阶段法：

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

（3）解：大M法参与人工变量，化成标准型：

Maxz=10x1+15x2+12x3+0x4+0x5+0x6-Mx7s.t.5x1+3x2+x3+x4=9-5x1+6x2+15x3+x5=152x1+x2+x3-x6+x7=5x1,x2,x3,x4，x5,x6，x7?0单纯形表计算略

第12页共64页

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

（4）解法一：大M法

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

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

Maxz=c1x1+c2x2

a11x1?a12x2?b1a21x1?a22x2?b2

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

2?a21?4，4?a22?6

解：

?求Z的上界

Maxz=3x1+6x2s.t.-x1+2x2?122x1+4x2?14x2，x1?0参与松弛变量，化成标准型，用单纯形法解的，最优解X=（0，7/2，5，0)T

目标函数上界为z=21存在非基变量检验数等于零，所以有无穷多最优解。?求z的下界线性规划模型：MaxZ=x1+4x2s.t.3x1+5x2?84x1+6x2?10x2，x1?0

参与松弛变量，化成标准型，解得：

第13页共64页

最优解为

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。基bx3dx42x63cj?zjx1x2x3x4x5a2x64-1a3c1a1100001000010-3-5c2-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?00，3/a30并且c1?c2，a3d/41.9某昼夜服务的公交线路每天个时间段内所需司机和乘务员人数如下：班次时间所需人数16点到10点60210点到14点70314点到18点60418点到22点50522点到2点2062点到6点30设司机和乘务人员分别在各时间区段一开始时上班，并连续上班8小时，问该公交线路至少配备多少司机和乘务人员。列出线型规划模型。

第14页共64页

解：

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

Minz=x1+x2+x3+x4+x5+x6s.t.x1+x6?60x1+x2?70x2+x3?60x3+x4?50x4+x5?20x5+x6?30x1,x2,x3,x4,x5,x6?01.10某糖果公司厂用原料A、B、C加工成三种不同牌号的糖果甲乙丙，已知各种糖果中ABC含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价如表所示：原料甲乙丙原料每月成本（元/限制用量千克）（千克）A22000?60%?15%B1.52500C11200?20%?60%?50%加工费0.50.40.3售价3.42.852.25问该厂每月应当生产这三种牌号糖果各多少千克，使得获利最大？建立数学模型。解:

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

线性规划模型：

Maxz=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

第15页共64页

-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?1200x7x8x9,,?0x3+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上加工。已知条件如下表，要求安排最优生产计划，使该厂利润最大化。设备A1A2B1B2B3产品I576470.251.25II10980.352.00III12110.52.8设备有效台满负荷时的时设备费用600030010000400070004000321250783200原料费单价解：

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

第26页共64页

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

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

和

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

y4，y5，y6）

XS

=0;且YSX=0

x5=x6=0，原问题约束条件取等号，x3=4；x4=4最优解X=（0，0，4，4)T

目标函数最优值为44。

2.8试用对偶单纯形法求解以下线性规划问题。（1）minz=x1+x22x1+x2?4x1+7x2?7x1,x2?0

(2)minz=3x1+2x2+x3+4x42x1+4x2+5x3+x4?03x1-x2+7x3-2x4?25x1+2x2+x3+10x4?15

x1,x2,x3,x4?0

解：（1）

取w=-z，标准形式：

第27页共64页

Maxw=-x1-x2+0x3+0x4s.t.

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

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

（2）令：w=-z，转化为标准形式：Maxw=-3x1-2x2-x3-4x4+0x5+0x6+0x7s.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现有线性规划问题maxz=-5x1+5x2+13x3-x1+x2+3x3?2012x1+4x2+10x3?90

x1，x2，x3?0

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

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

第28页共64页

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

??1?（4）x1的系数向量变为??

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

把原问题化成标准型的：

Maxz=-5x1+5x2+13x3+0x4+0x5s.t

-x1+x2+3x3+x5=2012x1+4x2+10x3+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

第29页共64页

目标函数最优值为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设备上加工，数据如下表，设备每月设备IIIIII有效台时A8210300B1058400C21310420单位产品利润322.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，建立数学模型：Maxz=3x1+2x2+2.9x3s.t.

第30页共64页

8x1+2x2+10x3?30010x1+5x2+8x3?4002x1+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)TP8?(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）Maxz(t)=(3-6t)x1+(2-2t)x2+(5-5t)x3(t?0)s.t.

x1+2x2+x3?430

3x1+2x3?460

第31页共64页

x1+4x2?420x1，x2，x3?0

（2）Maxz(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）Maxz(t)=2x1+x2(0?t?25)s.t.

x1?10+2tx1+x2?25-tx2?10+2tx1，x2?0（4）Maxz(t)=21x1+12x2+18x3+15x4(0?t?59)s.t.

6x1+3x2+6x3+3x4?30+t6x1-3x2+12x3+6x4?78-t9x1+3x2-6x3+9x4?135-2tx1，x2，x3，x4?0

解：

（1）化成标准形式：

Maxz(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

第32页共64页

x1+4x2+x6=420

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

令t=0，用单纯形表计算，3-6t2-2tcj5-5tx30x40x50x6?iCBXBx2x3x6B10023020x1x22-2t5-5t0-z-1/43/22100001000.50-2t-1-1/41/2[1]2t-20010-460201350tt-4-1350t增大，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目标函数最优值为Maxz(t)=0，（t大于1）（2）化成标准型，然后令t=0，单纯形法解得：t开始增大时，当t大于8/3时，首先出现优解。

目标函数最优值Maxz(t)=220，（0?t?8/3）所以，t=8/3为第一临界点。当8/35，首先?1大于0，8/35时，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，（11

第41页共64页

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，此问题有无穷多最优解。总运费minz=90（4）销地甲乙产地12345销量10010130924120281001136606233080M11183460182131980丙29丁1314戊2216产量100120M140解：（4）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售地己，令单位运价为0。销量为40。这样就达到了产销平衡。用伏格尔法求初始解：○1计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下行。○2从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，同时划掉所在列或行的元素。○3对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤○1○2，直到求出初始解为止。

并用位势法进行检验：销地甲乙丙丁戊己ui产地12310182813M3M-16006290211113140M13616120-1022120000第42页共64页

04452421090110280160237363210181030513M-619834616220170-1212-5vi由上表可以看出，所有的非基变量检验数≥0，此问题达到最优解。又由于?31=0，此问题有无穷多最优解。

总运费minz=55203.4已知运输问题的产销平衡表、单位运价表及最优调运方案如下表所示表1销产量B1B2B3B4地产地51015A1A2A30551015151510255销量表2销地产地B1B21714c22B3B4112018A1（1）（2）

1012220916A2A3A2A2到到

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

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

外，至少写出其他两个。

解：

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

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

uivi+=cij第43页共64页

（i，j?B）来确定

2由?ij=○

uiv和i.

cij-（

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

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

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

c22-3?0c22+10?0

10-c22?024-c22?018-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○销地产地A1A2B1B2B3B4010产量152501515第44页共64页

A3552○

1515105销量销地产地A1A2A3B1B2B3B41010产量15255055150151515销量3.5某百货公司去外地购买ABCD四种规格的服装，数量分别为：A,1500套；B，2000套；C，3000套；D，3500套；有三个城市可以供应上述服装，分别为：I，2500套，II，2500套；III，5000套。已知下表，求预期盈利最大的购买方案。ABCDI10567II8276III9348解：由于利润表中的最大利润是10，所以令M=10，用M减去利润表上的数字，此问题变成一个运输问题，见下表：销地ABCD产量产地I05432500II28342500III17625000销量1500200030003500使用伏格尔法计算初始解：○1计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下行。

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

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

第45页共64页

销地A产地I1500IIIII销量1500使用位势法检验：BCD产量5001500200050025003000350035002500250050001数字格处填入单位运价，并增加一行一列，在列中填入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）计算所有空格的检验数，并在每个格的右上角填入单位运价。假使没有得到最优解，用逼回路法进行改进。盈利最大方案：销地ABC产地I05400II283340III176011054viDui30244211-1此时，总运费为28000元;最大盈利为72000元。3.6甲乙丙三个城市每年需要煤炭分别为：320万吨、250万吨、350万吨，由A、B两处煤矿供应。煤炭供应量分别为：A,400万吨；B,450万吨；运价如下表，由于需大于供应，经研究平衡决定，甲城市供应量可以减少0~30万吨，乙城市需要完全供应，丙城市供应不少于270万吨。试求将供应量分派完又使总运费最低的调运方案。甲乙丙

第46页共64页

AB

解：

152118252216此问题的供应量小于需求量，假设供应地C，产量为70万吨。用伏格尔法求解得：销地甲甲‘乙丙丙‘供应产地ABC需求1501403029030使用位势法检验：250250270270107080400450701数字格处填入单位运价，并增加一行一列，在列中填入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某造船厂根据合同要从当年起连续三年末各提供三条规格型号一致的大型客货轮。已知该厂这三年内生产大型客货轮的能力及每艘客货轮成本如下表，年度正常生产时间内加班生产时间内正常生产时的可完成的客货轮可完成的客货轮每艘成本/万元数数123500242600313550已知加班生产时，每艘客货轮的成本比正常生产高出70万元，又知道造出来的可货轮如当年不交货，每艘积压一年造成积压损失40万元，在签合同时，该厂已经存储了2艘客货轮，而该厂希望在第三年木完成合同后还能存储一艘备用，问该厂如何安排每年的生产量，能够在满足上述要求的状况下，总的生产费用加积压损失最少？

解：

第47页共64页

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

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

此问题有无穷多最优解，总运费minz=4730万元销地A1A2A3产地B1B1?B2?B2B3?B3A40000供应量0606060-1060500540600550620S40-460需求量500540560-60试题：(2023年上海大学)某产品由产地Ai发往销地Bj的每吨运费如下表：元/吨B1B2B3供应量（吨）A1504060150A2453065200A3201050250需求量150