運(yùn)籌學(xué)答題題庫(kù)2020

l.minz=2再+3馬+天

再+4x2+2x3>8

3國(guó)+2尤2)6

再，入2，^.

解：大M法

z'=-z有maxz'=-min(-z')=-minz

化成標(biāo)準(zhǔn)形：

z

Maxz=-2xx-3x2-+0x4+0x5

S.T.

國(guó)+4%+2玉-%+x6=4

3國(guó)+2々-毛+毛=6

xl,x2,x3,x4,毛，毛，Xy>0

(單純性表計(jì)算略)

線性規(guī)劃最優(yōu)解乂=(4/5,9/5,0,0,0,0尸

目標(biāo)函數(shù)最優(yōu)值minz=7

非基變量七的檢驗(yàn)數(shù)％=。，所以有無(wú)窮多最優(yōu)解。

2.已知某線性規(guī)劃問(wèn)題，用單純形法計(jì)算得到的中間某兩步的加算表見(jiàn)表，試將

空白處數(shù)字填上。

354000

Cj

b

XB天

cB再%%工6

58/32/3101/300

014/3-4/305-2/310

020/35/304-2/301

-1/304-5/300

15/418/41-10/41

-6/415/414/41

%3

-2/41-12/4115/41

X]

Cj-Zj

解:

354000

%

b

XBX]x

cB2%%

58/3

x2

014/3

%

020/3

%

Ci%

580/4101015/41

X?

450/41001-6/41

x3

344/41100-2/41

王

000-45/41

CjYj

3.已知線性規(guī)劃問(wèn)題

Maxz=2再+%+5犬3+6x4

s.t.2再+毛+/<8

2七+2%+七+2/412

>0,j=l,...4

對(duì)偶變量X，%，其對(duì)偶問(wèn)題的最優(yōu)解是y；=4,y；=l,試應(yīng)用對(duì)偶問(wèn)題

的性質(zhì)，求原問(wèn)題的最優(yōu)解。

解：

對(duì)偶問(wèn)題是：

Minw=8y+12%

s-t.2yx+2y2>2

2>1

X+%25

X+2%*

%，-o

互補(bǔ)松弛性可知，如文，戶是原問(wèn)題和對(duì)偶問(wèn)題的可行解，那么，YXs=0

和

公文=0,當(dāng)且僅當(dāng)父，另是最優(yōu)解。

設(shè)X,丫是原問(wèn)題和對(duì)偶問(wèn)題的可行解，松=(%，%，％，%)

有：

YXs=0;且與X=0

x5=x6=0,原問(wèn)題約束條件取等號(hào)，X3=4；X4=4

最優(yōu)解x=(0,0,4,4)「

目標(biāo)函數(shù)最優(yōu)值為44o

4.試用對(duì)偶單純形法求解下列線性規(guī)劃問(wèn)題。

(1)minz=再+x2

2再+九2"

xl+7x2>7

x1,x2>0

(2)minz=3再+2x2+七+4%

2+4x2+5+x4>0

3%-9+7毛-2%>2

5X1+2X2+X3+10X4>15

再，%2，％3，X420

解：

(1)

w=-z,標(biāo)準(zhǔn)形式：

Maxw=-x1-x2+0x3+0x4

s.t.

-2再-9+玉二-4

-西-7x2+x4=-7

再，x2,x3,x4>0

單純形法求解(略)：

最優(yōu)解：

X=(21/13,10/13,0,Of

目標(biāo)函數(shù)最優(yōu)值為31/13。

(2)令：w=-z,轉(zhuǎn)化為標(biāo)準(zhǔn)形式：

Maxw=-3再-2%2-毛-4%4+0%5+0x6+0毛

s.t.

-2-4%2-5%3-九4+毛二0

-3再+%-7毛+2%+%=-2

-5再-2%2-%3-6%4+%7=-15

西，x2,x3,x49x5,x69x7>0

單純形法略

原問(wèn)題最優(yōu)解：

X=(3,0,0,0,6,7,0)r

目標(biāo)函數(shù)最優(yōu)值為9。

5.（2006年西北工業(yè)大學(xué)）已知線性規(guī)劃：

maxz=3芯+2x2

一玉+2X2<4

3%+2々V12

s.t.<

玉一%2V3

x^x2>0

（1）用單純形法求解該線性規(guī)劃問(wèn)題的最優(yōu)解和最優(yōu)值；

（2）寫(xiě)出線性規(guī)劃的對(duì)偶問(wèn)題；

（3）求解對(duì)偶問(wèn)題的最優(yōu)解和最優(yōu)值。

解題分析：本題考察了線性規(guī)劃與對(duì)偶問(wèn)題的知識(shí)，要求讀者熟知對(duì)偶理論。

-17

解題過(guò)程：%*=---00

_555_

maxz=12,有無(wú)窮多解。

對(duì)偶問(wèn)題為：

minw=4yl+12y2+3y3

f+3%+為?3

s.t.<2%+2y2-%22

,%，%，%20

r=[010]w=z*=12

6.用表上作業(yè)法求給出運(yùn)輸問(wèn)題的最優(yōu)解（M是任意大正數(shù)）

（1）

肖地甲乙丙T產(chǎn)量

產(chǎn)地

137645

224322

343853

銷(xiāo)量3322

解：

（1）①計(jì)算出各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該表的最

右列和最下列。

②從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最

小元素，丙列中的最小元素為3,由此可以確定產(chǎn)地2的產(chǎn)品應(yīng)先供應(yīng)丙的需要，

而產(chǎn)地2的產(chǎn)量等于丙地的銷(xiāo)量，故在（2,丙）處填入0,同時(shí)將運(yùn)價(jià)表中的

丙列和第二行的數(shù)字劃去，得到：

肖地甲乙丙T產(chǎn)量

產(chǎn)地

13745

22

34353

銷(xiāo)量332

③對(duì)上表中的元素分別計(jì)算各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額,

填入該標(biāo)的最右列和最下行，重復(fù)步驟①②，直到求出初始解為止。得到下表:

肖地甲乙丙T產(chǎn)量

產(chǎn)地

1325

2202

3033

銷(xiāo)量3322

使用位勢(shì)法進(jìn)行檢驗(yàn)：

①上表中，數(shù)字格處填入單位運(yùn)價(jià)并增加一行一列，在列中填入%（i=l,

2,3）,在行中填入,（j=l,2,3,4）,先令%+匕=與（i,jeB,B為基，下

同）來(lái)確定附和匕，得到下表:

肖地甲乙丙T

Uj

產(chǎn)地

1340

232-2

3431

3254

匕

②由0=%-（%+匕）（i,j為非基，下同）計(jì)算所有空格的檢驗(yàn)數(shù)，并在

yJ

每個(gè)格的右上角填入單位運(yùn)價(jià)，得到下表

肖地甲乙丙T

產(chǎn)地

137640

0510

22432-2

1400

343851

0020

3254

匕

由上表可以看出,所有的非基變量檢驗(yàn)數(shù)NO,J比問(wèn)題達(dá)到最4憂解。

又因?yàn)?4=0，此問(wèn)題有無(wú)窮多最優(yōu)解。

總運(yùn)費(fèi)minz=3*3+3*3+2*3+2*4=32

(2)

肖地甲乙丙T產(chǎn)量

產(chǎn)地

11067124

21610599

35410104

銷(xiāo)量5246

解：（2）①計(jì)算出各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該表

的最右列和最下列。

②從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最

小元素，甲列是最大差額列，甲列的最小元素是5,所以產(chǎn)地3的產(chǎn)品先供應(yīng)甲

的需求，同時(shí)將運(yùn)價(jià)表中產(chǎn)地3所在行的數(shù)字劃去。

③對(duì)上表中的元素分別計(jì)算各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額,

填入該標(biāo)的最右列和最下行，重復(fù)步驟①②，直到求出初始解為止。得到下表:

肖地甲乙丙T產(chǎn)量

產(chǎn)地

11214

2369

344

銷(xiāo)量5246

使用位勢(shì)法進(jìn)行檢驗(yàn)：

①上表中，數(shù)字格處填入單位運(yùn)價(jià)，并增加一行一列，在列中填入對(duì)（i=l,

2,3）,在行中填入,（j=l,2,3,4）,先令%=0,由%+匕=與（i,jeB,B

為基，下同）來(lái)確定“，和匕.

②由%=%-（%+匕）（i,jeN）計(jì)算所有空格的檢驗(yàn)數(shù)，并在每個(gè)格的右

上角填入單位運(yùn)價(jià)，得到一;表

肖地甲乙丙T

產(chǎn)地

11067120

01

2161059-2

8600

3541010-5

0384

106711

匕

由上表可以看出，所有的非基變量檢驗(yàn)數(shù)三0,J比問(wèn)題達(dá)到最《尤解。

此問(wèn)題有唯一最優(yōu)解。

總運(yùn)費(fèi)minz=118

(3)

7肖地甲乙丙T戊產(chǎn)量

產(chǎn)證、

1102059105

221083066

312071042

4863759

銷(xiāo)量44624

解：（3）此問(wèn)題是一個(gè)產(chǎn)銷(xiāo)不平衡的問(wèn)題，產(chǎn)大于銷(xiāo)。增加一個(gè)假象銷(xiāo)售

地己，令單位運(yùn)價(jià)為0。銷(xiāo)量為2。這樣就達(dá)到了產(chǎn)銷(xiāo)平衡。

用伏格爾法求初始解：

①計(jì)算出各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該表的最右列

和最下列。

②從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元

素，產(chǎn)地1所在的行是最大差額行，最小元素0,說(shuō)以一產(chǎn)地的產(chǎn)品應(yīng)該優(yōu)先供

應(yīng)己的需要，同時(shí)劃掉己列的數(shù)字。

③對(duì)上表中的元素分別計(jì)算各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額,

填入該標(biāo)的最右列和最下行，重復(fù)步驟①②，直到求出初始解為止。得到下表:

7肖地甲乙丙T戊己產(chǎn)量

產(chǎn)證、

1325

2426

322

44329

銷(xiāo)量446242

使用位勢(shì)法進(jìn)行檢驗(yàn)：

①上表中，數(shù)字格處填入單位運(yùn)價(jià)，并增加一行一列，在列中填入"，（i=l,

2,3,4）,在行中填入匕（j=l,2,3,4,5,6）,先令％=0,由"，+匕』（i,

jeB,B為基,下同）來(lái)確定/和匕.

②由4=%-（%+匕）（i,jeN）計(jì)算所有空格的檢驗(yàn)數(shù)，并在每個(gè)格的右

上角填入單位運(yùn)價(jià)。

由上表可以看出，所有的非基變量檢驗(yàn)數(shù)三0,此問(wèn)題達(dá)到最優(yōu)解。

又因?yàn)榍?=。，此問(wèn)題有無(wú)窮多最優(yōu)解。

總運(yùn)費(fèi)minz=90

7.使用單純形法求解下列目標(biāo)規(guī)劃問(wèn)題。

(1)minz=P]d~+P2d；+月(54+3d；)+《d：

s.t.

國(guó)+%+4-d：=80

西+&+d；-d；=90

%+4■-d；=70

/+-d：—45

,*^2'd、，d]，d2，d?，,d42。

(2)minz=Pxd；+P、d；

s.t.再+2%2+4-4+=10

10再+12%2+2：-a=62.4

+2x2<8

Xj9%29d、，4,d?9d?N0

(3)minz=P1(+d；)+gd~

s.t.xx+x2~^d~-=1

2%+2冗2+d；-d；=4

6%-4%+d；-d；=50

9*^2'd、，d]9，d?，(^3，20

解：

(1)把原問(wèn)題轉(zhuǎn)化為：

Minz=P、d；+P、d；+旦d~

S.T.

x1+2x2+d~-=10

10%1+12%2+6?2--^2-62.4

2再+%2+%3=8

Xj,%2，%3，4，4,d-2，d?20

x3是松弛變量

單純形法計(jì)算得：

0000

Cj2Pi64

b

XBXiX?&d~d：d~d；

cB

101[2]01-1005

d~

62.410120001-15.2

Rd~

0821100008

-10-1200002

旦-1-200100

迭代…

原問(wèn)題最優(yōu)解西=0,々=5.2,非基變量的的檢驗(yàn)數(shù)是0,所以有多重解;

繼續(xù)迭代得到：

%!=0.6,%=4.7也是滿意解

(2)

使用單純形法計(jì)算：

%!=70,=20

(3)滿意解是

%1=1,^=0

8.有四個(gè)工人，指派他們完成4種工作，每人做各種工作所消耗的時(shí)間如下表,

問(wèn)指派哪個(gè)人去完成哪種工作，可以使得總耗時(shí)最?。?/p>

壬務(wù)ABCD

人員

甲15182124

乙19232218

丙26171619

T19212317

解：系數(shù)矩陣C為:

15182124

19232218

26172619

19212317

①系數(shù)矩陣的每行元素減去該行的最小元素得矩陣B

②B矩陣的每列元素減去該列的最小元素得到矩陣A

此時(shí)，細(xì)數(shù)矩陣的每行每列都有元素0.

先給勺加圈，然后給如加圈，劃掉%4。給?2加圈，劃掉?3得：

'0269一

1440

10003

_2360

此時(shí)，畫(huà)圈的數(shù)目是3,少于4個(gè)，所以指派不成功，進(jìn)入下一步，

給第四行打J號(hào)，給第四列打J號(hào)，給第二行打J號(hào)，將第一，第三行畫(huà)一橫線，

將第四列畫(huà)縱線，變換矩陣得到

'02610-

0330

10004

1250

給第一，第四列打J號(hào)，對(duì)第一，第二，第四行打J號(hào)，給第一，第四列畫(huà)一縱

線，第三行畫(huà)一橫線，變換矩陣得到

甲乙丙丁

'00410-

0111

12006

1030

得到最優(yōu)指派方案為：甲一B；乙一A;丙一C；T—Do

所消耗的總時(shí)間是70.

9.（2005年南京大學(xué)）現(xiàn)要在5個(gè)工人中確定4個(gè)人來(lái)分別完成四項(xiàng)工作中的

一項(xiàng)工作。由于每個(gè)工人的技術(shù)特長(zhǎng)不同，他們完成各項(xiàng)工作所需的工時(shí)也

不同。每個(gè)工人完成每項(xiàng)工作所需工時(shí)如表5—1所示。

表5—1

所需工0?\］作

ABcD

I9437

II4656

III5475

IV7523

V10674

試找出一個(gè)工作分配方案，使總工時(shí)最少。

解題分析：本題屬“不平衡”指派問(wèn)題，故應(yīng)先虛擬一項(xiàng)工作，使其平衡，再按

常規(guī)求解即可。

解題過(guò)程：虛擬一項(xiàng)工作E,設(shè)每人完成E所需時(shí)間都是“0”，從而轉(zhuǎn)化為五個(gè)

人完成五項(xiàng)工作的分配問(wèn)題，再用匈牙利法求解。

最優(yōu)解為：I—C,II—A,III—B,IV—D,V—E,即應(yīng)安排工人I、

n、ni、W分別完成工作C、A、B、D,此時(shí)所用時(shí)間最少，為3+4+4+3=14。

10解：已知線性規(guī)劃

maxZ=3再+4x2+5x3

玉+2X2-X3<10

<2玉一%+3%3-5

Xj>0,7=1,2,3

（1）求原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解；（2）求最優(yōu)解不變時(shí)C/的變化范圍

（1）化標(biāo)準(zhǔn)型2分

maxZ=3芯+4x2+5x3

xl+2X2-x3+x4=10

<2再-x2+3X3+x5=5

Xj>Q,j=1,2,,5

（2）單純形法5分

CBXB為蒞吊羽怎b

4苞1100.60.27

5吊1010.20.44

C(j)-Z(j)-600-3.4-2.848

(3)最優(yōu)解X=(0,7,4)；Z=48(2分)

(4)對(duì)偶問(wèn)題的最優(yōu)解丫=(3.4,2.8)(2分)

qe(—oo,9),c,>——,c3>—1

3

(5)Aci<6,AC2>-17/2,AC3>-6,貝!](4分)

11.求下列指派問(wèn)題（min）的最優(yōu)解（10分）

5685

12152018

C=

91097

9656

解:

01300030

03860286

=>

23202220

41014001（5分）

1

X=,Z=30

1

1

（5分）

12.求下圖VI到V8的最短路及最短路長(zhǎng)（10分）

vl到v8的最短路有兩條：尸18={vl,v3,v6,”8}及P18={vl,v3,v7,v6,v8},最短路長(zhǎng)為21。（3分）

13.某公司要將一批貨從三個(gè)產(chǎn)地運(yùn)到四個(gè)銷(xiāo)地，有關(guān)數(shù)據(jù)如下表所示。

供

銷(xiāo)地應(yīng)

BB

Bi2B34量

產(chǎn)地

56

A17379

0

40

A226511

0

75

A36425

0

32244838

需求量

0000

現(xiàn)要求制定調(diào)運(yùn)計(jì)劃，且依次滿足：

(1)B3的供應(yīng)量不低于需要量；

(2)其余銷(xiāo)地的供應(yīng)量不低于85%；

(3)A3給B3的供應(yīng)量不低于200；

(4)A?盡可能少給Bi；

(5)銷(xiāo)地B2、B3的供應(yīng)量盡可能保持平衡。

(6)使總運(yùn)費(fèi)最小。

試建立該問(wèn)題的目標(biāo)規(guī)劃數(shù)學(xué)模型。

13.設(shè)殉為A,?到B/的運(yùn)量，數(shù)學(xué)模型為

minz=《4+￡(&+4+〃4)+g"5+g",+月("7+。；)+紜。；

再3+々3+*33+4——480員保證供應(yīng)

再］+%2i+%31+d?-d；—2744需求的85%

Xj2+%22+”32+4-d；—204為需求的85%

%14+X24+%34+Z—d；=323息需求的85%

X33+4_d；—200人1寸員

s.t.<%21-逋=。4對(duì)與

2X11+2%21+2%31—%12—*22—*32+"7—=0為與員的平衡

34

ZX-公=。運(yùn)費(fèi)最小

i=lj=l

Xtj>0(z=1,2,3；J=1,2,3,4);

“d：>0(z=l,2,...,8);

14、用分枝定界法求解下列整數(shù)規(guī)劃問(wèn)題：(提示:可采用圖解法)

maxZ=40xi+90x2

pXj+7x2456

s.tS7x,+20x2470

1%,X220且為整數(shù)

Xx

15、A、B兩個(gè)煤礦負(fù)責(zé)供應(yīng)甲、乙、丙三個(gè)城市煤炭。已知A、B兩礦年產(chǎn)量、三個(gè)城市

的需求量以及從兩煤礦至各城市煤炭運(yùn)價(jià)如下表。由于供不應(yīng)求，經(jīng)協(xié)商，甲城市必要時(shí)可

少供應(yīng)0—30萬(wàn)噸，乙城市需求須全部滿足，丙城市需求不少于270萬(wàn)噸。試求：將甲、乙

兩礦煤炭全部分配出去，滿足上述條件又使總運(yùn)費(fèi)最低的調(diào)運(yùn)方案。(15分)

7^甲乙丙產(chǎn)量

A151822400

B212516450

銷(xiāo)量(T)320250350

解：(1)依題意得產(chǎn)銷(xiāo)平衡表如下：

甲，甲”乙丙，丙”產(chǎn)量

A1515182222400

B2121251616450

CM0MM070

銷(xiāo)量(T)2903025027080

(2)做初始的調(diào)運(yùn)方案(伏格爾法)

產(chǎn)甲，甲，，乙丙，丙”產(chǎn)量

銷(xiāo)

A1515182222400

150250

B2121251616450

1403027010

CM0MM070

70

銷(xiāo)量(T)2903025027080

(3)用位勢(shì)法進(jìn)行檢驗(yàn)

產(chǎn)甲，甲”乙丙，丙”U

銷(xiāo)

A1515182222

0001212-6

B2121251616

001000

CM0MM0

M-5-5M-80-16

V2121241616

(4)做閉回路調(diào)整

調(diào)整后為：

產(chǎn)甲，甲”乙丙，丙”產(chǎn)量

銷(xiāo)

A1515182222400

150250

B2121251616450

14027040

CM0MM070

3040

銷(xiāo)量(T)2903025027080

(5)進(jìn)行進(jìn)一步檢驗(yàn)

產(chǎn)甲，甲”乙丙，丙”U

銷(xiāo)

A1515182222

0001212-6

B2121251616

051000

CM0MM0

M-50M-8M0-16

V2116241616

(6)調(diào)整后的方案為最優(yōu)方案

最低費(fèi)用=150X15+250X18+140X21+270X16+40X16+30X0+40X0=14650

16、分配甲、乙、丙、丁四人去完成5項(xiàng)任務(wù)。每人完成各項(xiàng)任務(wù)時(shí)間如下表所示。由于任

務(wù)數(shù)多于人數(shù)，故規(guī)定其中有一人可兼完成兩項(xiàng)任務(wù)，其余三人每人完成一項(xiàng)，試確定總花

費(fèi)時(shí)間最少的指派方案。（15分）

ABCDE

甲2529314237

乙3938262033

丙3427284032

T2442362345

解：假設(shè)增加一個(gè)人戊完成各項(xiàng)工作的時(shí)間取A、B、C、D、E最小值。

得效率矩陣為：

ABCDE

甲「2529314237

乙3938262033

丙3427284032

T2442362345

戊2427262032

各行減最小值，各列減最小值：得

ABCDE

_4_5_J7_7

乙19185)8

兩力~0~~1丁中

T11912317

戊475力7

變換得

ABCDE

甲「（45187

乙1317407

西-(T飛~14^

Tq1811J16

戊2646

進(jìn)一步

ABCDE

甲「001183

乙1813003

丙1100180

T0147012

戊32002

最有指派方案

ABCDE

甲「01000

乙00010

丙00001

T10000

戊00100

甲——B,乙——C,D,丙——E,T——A

最低費(fèi)用=29+26+20+32+24=131

17.石油輸送管道鋪設(shè)最優(yōu)方案的選擇問(wèn)題：如圖所示，其中A為出發(fā)點(diǎn)，E為

目的地，B、C、D分別為三個(gè)必須建立油泵加壓站的地區(qū)，其中的Bi、B2、B3；。、

C2、C3Q1、D2分別為可供選擇的各站站點(diǎn)。圖中的線段表示管道可鋪設(shè)的位置，

線段旁的數(shù)字為鋪設(shè)管線所需要的費(fèi)用，問(wèn)如何鋪設(shè)管道才使總費(fèi)用最小？

解：

第四階段：Di—E3；D2—E4；

第三階段:Ci—Di一E5；C2—D2—E8；Cs—Di一E8；Cs—D2一E8；

第二階段：Bi—Ci一Di一E11；Bi-C2—D2—E11；B2—Ci一Di一E8；

Bs—Ci—Di—E9；Bs—C2—D2—E9；

第一階段：A—Bi—Ci—Di—E14；A—Bi—C2—D2—E14；

A—B2—Ci—Di—E13；A—B3—Ci—Di—E13；

A—B3—C2—D2—E13；

最優(yōu)解：A—Bs-Ci-Di—E；A—Ba-Ci-Di—E；A—B3-C2—D2—E

最優(yōu)值：13

18.某大學(xué)準(zhǔn)備對(duì)其所屬的7個(gè)學(xué)院辦公室計(jì)算機(jī)聯(lián)網(wǎng)，這個(gè)網(wǎng)絡(luò)的可能聯(lián)通的途徑如圖所示,

圖中V1,……，V7表示7個(gè)學(xué)院辦公室，圖中的邊為可能聯(lián)網(wǎng)的途徑，邊上的所賦權(quán)數(shù)為這

條路線的長(zhǎng)度，單位為百米。請(qǐng)?jiān)O(shè)計(jì)一個(gè)網(wǎng)絡(luò)能聯(lián)通7個(gè)學(xué)院辦公室，并使總的線路長(zhǎng)度為最

短。

解：①在G中找到一個(gè)圈(Vi,V7,V6,VO，并知在此圈上邊[Vi,V6]的權(quán)

數(shù)10為最大，在G中去掉邊[Vi,V目得圖Gi,如上圖所示

②在G1中找到一個(gè)圈(V3,V4,V5,V7,V3),去掉其中權(quán)數(shù)最大的邊[V4,V5],

得圖G2,如上圖所不

③在G2中找到一個(gè)圈(V2,V3,V5,V7,V2),去掉其中權(quán)數(shù)最大的邊

[Vs>V7],得圖G3,如上圖所不

④在G3中找到一個(gè)圈(V3,V5,V6,V7,V3),去掉其中權(quán)數(shù)最大的邊

[V5,Ve]?得圖G4,如上圖所不

⑤在G4中找到一個(gè)圈(V2,V3,V7,V2),去掉其中權(quán)數(shù)最大的邊

[V3,V7],得圖Gs，如上圖所不

⑥在G5中已找不到任何一個(gè)圈了，可知G5即為圖G的最小生成樹(shù)。

這個(gè)最小生成樹(shù)的所有邊的總權(quán)數(shù)為3+3+3+1+2+7=19

19.某電力公司要沿道路為8個(gè)居民點(diǎn)架設(shè)輸電網(wǎng)絡(luò)，連接8個(gè)居民點(diǎn)的道路圖如圖

所示，其中Vi,……，V8表示8個(gè)居民點(diǎn)，圖中的邊表示可架設(shè)輸電網(wǎng)絡(luò)的道路，

邊上的賦權(quán)數(shù)為這條道路的長(zhǎng)度，單位為公里，請(qǐng)?jiān)O(shè)計(jì)一個(gè)輸電網(wǎng)絡(luò)，聯(lián)通這8個(gè)居

民點(diǎn)，并使總的輸電線路長(zhǎng)度為最短。

①在圖中找到一個(gè)圈(Vl,V2,V5,V3)，并知在此圈上邊［Vl,V2］和

［V3,V5］的權(quán)數(shù)4為最大，在圖中去掉邊［V1,V2］；

②在圖中找到一個(gè)圈(V3,V4,V8,V5,V3,V1),去掉其中權(quán)數(shù)最大的邊

［V4,V8］；

③在圖中找到一個(gè)圈(V3,V4,V5,V3),去掉其中權(quán)數(shù)最大的邊［V4,V5］；

④在圖中找到一個(gè)圈(V5,V2,V6,V7,V5),去掉其中權(quán)數(shù)最大的邊

［V2,V6］；

⑤在圖中找到一個(gè)圈(V5,V7,V8,V5),去掉其中權(quán)數(shù)最大的邊［V5,V8］o

⑥在圖中已找不到任何一個(gè)圈了，可知此即為圖G的最小生成樹(shù)。

這個(gè)最小生成樹(shù)的所有邊的總權(quán)數(shù)為2+2+4+2+3+3+2=18

20矩陣對(duì)策的最優(yōu)純策略

甲乙乒乓球隊(duì)進(jìn)行團(tuán)體對(duì)抗賽，每對(duì)由三名球員組成，雙方都可排成三種不同的

陣容，每一種陣容可以看成一種策略，雙方各選一種策略參賽。比賽共賽三局，

規(guī)定每局勝者得1分，輸者得-1分，可知三賽三勝得3分，三賽二勝得1分，三

賽一勝得-1分，三賽三負(fù)得-3分。甲隊(duì)的策略集為Si={3,a2,a3},乙隊(duì)的策略

集為Sl={01,彷，加},根據(jù)以往比賽得分資料，可得甲隊(duì)的贏得矩陣為A,如下：

3-13

試問(wèn)這次比賽各隊(duì)?wèi)?yīng)采用哪種陣容上場(chǎng)最為穩(wěn)妥。

解：甲隊(duì)的6,a2,a3三種策略可能帶來(lái)的最少贏得，即矩陣A中每行的最小元

素分別為：1,-3,-1,

在這些最少贏得中最好的結(jié)果是1,即甲隊(duì)?wèi)?yīng)采取策略③，無(wú)論對(duì)手采用什么

策略，甲隊(duì)至少得1分。而對(duì)乙隊(duì)來(lái)說(shuō)，策略國(guó)，刖，的可能帶來(lái)的最少贏得，

即矩陣A中每列的最大因素(因?yàn)閮扇肆愫筒呒钻?duì)得分越多，就使得乙隊(duì)得分越

少)，分別為：3,1,3,

其中乙隊(duì)最好的結(jié)果為甲隊(duì)得1分，這時(shí)乙隊(duì)采取囪策略，不管甲隊(duì)采用什么

策略甲隊(duì)的得分不會(huì)超過(guò)1分（即乙隊(duì)的失分不會(huì)超過(guò)1）。這樣可知甲隊(duì)?wèi)?yīng)采用

ai策略，乙隊(duì)?wèi)?yīng)采取叫策略。把這種最優(yōu)策略ai和俄分別稱為局中人甲隊(duì)、乙

隊(duì)的最優(yōu)純策略。這種最優(yōu)純策略只有當(dāng)贏得矩陣A=（aij）中等式

maxmina”=minmaxa.

ijji

成立時(shí)，局中人才有最優(yōu)純策略，并把（ai,[32）稱為對(duì)策G在純策略下的解，

又稱（ai,廿2）為對(duì)策G的鞍點(diǎn)。

21矩陣對(duì)策的混合策略

解：首先設(shè)甲使用6的概率為Xi',使用a2的概率為X*并設(shè)在最壞的情況下

（即乙出對(duì)其最有利的策略情況下），甲的贏得的平均值等于V。這樣我們建立以

下的數(shù)學(xué)關(guān)系：

1.甲使用ai的概率Xi'和使用a2的概率X2’的和為1,并知概率值具有非負(fù)性，

即Xi'+X2'=1,且有Xi'三0,X2‘叁0.

2.當(dāng)乙使用Pi策略時(shí)，甲的平均贏得為：5Xi'+8X2’,此平均贏得應(yīng)大于等于V,

即5XI'+8X2'叁V

3.當(dāng)乙使用p2策略時(shí)，甲的平均贏得為：9Xi'+6X2,此平均贏得應(yīng)大于等于V,

即9XI'+6X2'叁V

第二步，我們來(lái)考慮V的值，V的值與贏得矩陣A的各因素的值是有關(guān)的，如

果A的各元素的值都大于零，即不管甲采用什么策略，乙采用什么策略，甲的贏

得都是正的。這時(shí)的V值即在乙出對(duì)其最有利的策略時(shí)甲的平均贏得也顯然是正

的。因?yàn)锳的所有元素都取正值，所以可知V>0.

第三步，作變量替換，令Xi=/（i=1,2）

考慮到V>0,這樣把以上5個(gè)數(shù)量關(guān)系式變?yōu)椋?/p>

X1+X=—,X1叁0,X220,

2V

5Xi+8X2叁1

9Xi+6X2叁1

對(duì)甲來(lái)說(shuō)，他希望V值越大越好，也就是希望（的值越小越好，最后，我們就

建立起求甲的最優(yōu)混合策略的線性規(guī)劃的模型如下：

minXu-X2

約束條件：5XI+8X2

9Xi+6X2叁1

X1叁0,X2叁0

同樣求出乙最優(yōu)混合策略，設(shè)y“y2’分別為乙出策略01,02的概率，V為甲出

對(duì)其最有利的策略的情況下，乙的損失的平均值。

同樣我們可以得到：

y>+y2'=1,

5yi+9y2=V

8yi+6y2=V

yf叁0,y2‘叁0.

同樣作變量替換，令yi=/(i=1,2)

得關(guān)系式：yi+y2=?

5yi+9y2=1

8yi+6y2=1

yi叁0,y2Mo.

乙希望損失越少越好，即V越小越好而(越大越好，這樣我們也建立了求乙的

最優(yōu)混合策略的線性規(guī)劃的模型如下：

maxyn-y2

約束條件：5yi+9y2

8yi+6y2=1

yi叁0,y2叁0.

22.考慮下列線性規(guī)劃(20分)

MaxZ=2Xi+3X2

r2Xi+2X2+X3=12

XI+2X2+X4=8

J4Xi+X5=16

4X2+X6=12

、XjN0(j=l,2,...6)

其最優(yōu)單純形表如下：

基變量XIX2X3X4X5X6

X30001-1-1/40

XI410001/40

X64000-21/21

X220101/2-1/80

°j000-3/2-1/80

當(dāng)C2=5時(shí)，求新的最優(yōu)解

解當(dāng)C2=5時(shí)

o4=—5/2

o