第二章習(xí)題運籌學(xué)

第二章習(xí)題

12、對于下面的線性規(guī)劃問題，以3=(4,4,4)為基寫出相對應(yīng)的典式。

S,L34—5+24+鼻=7

?-2%+4^+巧=12

-4巧+3/+8覆+Xg=10

x產(chǎn)。,j'=l…6

解：由題可以知：

3-12100'

4-24001。

-438001Cr=p-21000]

-120-3-12'

400-240

取一個基3=(4AA),即：L381」且-438

在matlab中可以計算得到:

8

7

4豆§-39f

「5131

C：MN-4=

428

由工=c；5-?尸可得典式的目標(biāo)函數(shù):

513

尸-產(chǎn)+5

由/+用‘4即=b可得:

由此與題中線性規(guī)劃問題相對應(yīng)的典式為:

14、用單純形法求解線面的線性規(guī)劃問題，并在平面上畫出迭代點走過的路線。

minz=-2%-%

st.2耳+5q460

瑪+/418

3天+均444

■410

N，%之0

解：由題先將題中線性規(guī)劃問題化為標(biāo)準(zhǔn)形:

min名=-2毛一/

及t2曰+5,+/=60

彳+馬+4-18

3b+巧+胃=44

X/NO.

251000'

110100

A=

310010

由此可寫出A,即為：1°1°001

則可以得出H=(4444)是一個單位矩陣，且力184410fX),

所以基6是可行基，為基變量，不馬為非基變量。基■對應(yīng)的基本可行

解為：x.(00601844107,其目標(biāo)函數(shù)值4=。。方程組一已是典式，得

到一張單純形表如下：

444A馬4HflS

2100000

.25100060

411010018

A3*1001044

，01000110

由題可知，N=(4A),000]，c；=[-2-1]

檢驗數(shù)可由公=可用’加-4可得：一不是負(fù)數(shù)，則當(dāng)前解不是最優(yōu)解，4列中有三

個元素大于零，取：

故轉(zhuǎn)軸元為4,■為進(jìn)基變量，弓為出基變量。

目前的新基為含=（44A4）,進(jìn)行旋轉(zhuǎn)變換后得下表:

.4AA馬A

工

000.￡0re

T9~T

13w

■0T100T

r￡10

40010

73T

\\44

A1300T0V

A01000110

（44c9210

x=—0——。*

它對應(yīng)的基本可行解為：1333其目標(biāo)函數(shù)值為

_881

4=-不。但'”孑為正數(shù)，仍不是最優(yōu)解,此時以％為轉(zhuǎn)軸元，弓為進(jìn)基變

量，4為出基變量，進(jìn)行旋轉(zhuǎn)變化得下表:

A

￡111

000~3~30

旦■

■001~70

35

4°10202

1D

A100~770T

￡V絲

A000-771T

119.n15>r

它對應(yīng)的基本可行解為：“I63-------00——

62)目標(biāo)函數(shù)值為T,此時

檢驗數(shù)向量6為負(fù)數(shù)，故為最優(yōu)解。

16、用單純形法求解下列線性規(guī)劃問題:

min2=-24-巧+西

s.t.3A4x,+60

西-三+25410

A+巧一/420

Xji.0,j=1,2,3

⑴、

解：由題先將題中線性規(guī)劃問題化為標(biāo)準(zhǔn)形:

minz=-2J^-

S.t.3%+為+覆+與=60

不一巧+2覆+/-10

馬+/一百+維=20

勺NO,j=1,2,3,4,5,6

「311100'

A=-12010

由此可以得到矩陣1-1001

則可以得出(444)是一個單位矩陣，且5■頌1。20),X,所以基B

是可行基，一為基變量，一為非基變量?；?。對應(yīng)的基本可行解為：

*=(00061020片其目標(biāo)函數(shù)值4=0。

由此寫出最初的單純性表：

.AAAAAms

21-10000

A31110060

,1*-1201010

A11100120

由題可知，N=(A44),。：=勤。0]埼=42-11]

檢驗數(shù)可由仁=可用’^-4可得：I不是負(fù)數(shù)，則當(dāng)前解不是最優(yōu)解，4列中有三

個元素大于零，取：

故轉(zhuǎn)軸元為,為進(jìn)基變量，弓為出基變量。

進(jìn)行旋轉(zhuǎn)變換后得下表：

A4

03-50-20-20

1-3030

A04-5

1-1201010

-30-1110

402*

它對應(yīng)的基本可行解為：*?例1°1°『，其目標(biāo)函數(shù)值為4=-20。但仁=3為正

數(shù)，仍不是最優(yōu)解，此時以.為轉(zhuǎn)軸元，。為進(jìn)基變量，不為出基變量，進(jìn)行旋

轉(zhuǎn)變化得下表：

XTB：

■44A4A

￡￡

000,1-35

-210

40011-1

￡01015

A102

￡5

、0102

。匕=-35

它對應(yīng)的基本可行解為：x-(155目標(biāo)函數(shù)值為4此時檢驗數(shù)向

量6為負(fù)數(shù)，故為最優(yōu)解。

minz=xl-x2+x3+x5-x6

3毛+曰+4=6

A+2天一為=10

一毛+/=0

馬+/+與=6

0030110

012-1000

Jl—

--1000010

解：由此可以得到矩陣L0°1001

則可以得出(AA44)是一個單位矩陣，且b?(61006)r>0,所以

基3是可行基，斗馬，馬馬為基變量，。與，不為非基變量?；?。對應(yīng)的基本可行

解為：x-(01000606『，其目標(biāo)函數(shù)值4=0。

由此寫出最初的單純形表：

444馬4

-11T0-1100

■00301106

A012-100010

4-10000100

00100116

由題可知，N=(A44),。：=0-I1°]4=口°-1]

檢驗數(shù)可由,「可用火一埼可得：a=1不是負(fù)數(shù)，則當(dāng)前解不是最優(yōu)解,

故。為進(jìn)基變量，弓為出基變量。

進(jìn)行旋轉(zhuǎn)變換后得下表：

.44444

03-50-20-20

，04-51-3030

A1-1201010

A02*-30-1110

它對應(yīng)的基本可行解為：*?00101°『，其目標(biāo)函數(shù)值為4=-20。但仁=3為正

數(shù)，仍不是最優(yōu)解，此時以.為轉(zhuǎn)軸元，。為進(jìn)基變量，4為出基變量，進(jìn)行旋

轉(zhuǎn)變化得下表：

.A4A馬AMl

￡￡

00~30~7-35

0011-1-210

10201015

0105

2

它對應(yīng)的基本可行解為：x-QS50F,目標(biāo)函數(shù)值為4=75,此時檢驗數(shù)向

量，為負(fù)數(shù)，故為最優(yōu)解。

18、寫出下面線性規(guī)劃的對偶規(guī)劃

min104+103

s.t.54+2巧>5

%+4%23

%+3毛22

84+2524

%,當(dāng)為自變量

52

14

A=

13

解：由題可得”0。M,“632%卜2],

有定義可得原問題的線性規(guī)劃問題的對偶規(guī)

劃為：

按分量形式寫出的對偶規(guī)劃為:

max5/+3丐+2%+4%

風(fēng)力

5陰+%+碣+8用=10

2巧+4%+3%+2%-10

w戶。,J=1,2凡4

mm4+5

Sit.$+2/￡5

1.

產(chǎn)+/=3

20.把線性規(guī)劃問題:馬，瑪.馬20I己為p.

⑴用單純形算法解P；

⑵寫出P的對偶普；

⑶寫出P的互補(bǔ)松緊條件，并利用他們解對

偶普。

解：（I）、由題將F化為標(biāo)準(zhǔn)形式為:

mm4+馬

乳￡蒼?2/十4■5

，1-

3巧+/=3

4%馬，

4201、

A-1

由此可寫出4,即為：〔°5I°j

則可以得出一是一個單位矩陣，且一所以基6

是可行基，小毛為基變量，冷，為非基變量。基

a對應(yīng)的基本可行解為：X?G。3or,其目標(biāo)函

數(shù)值釬。。得到一張單純形表如下：

000

12015

00

213

將第。行化成檢驗行為:

0I018

12*o15

A01103

5

它對應(yīng)的仁=5為正數(shù)，仍不是最優(yōu)解，以弓為

進(jìn)基變量，用為出基變量，進(jìn)行旋轉(zhuǎn)變化得下

表：

-100-77

A11011

A001-J7

它對應(yīng)的Q=4,所以問題P的最優(yōu)解為“最

7

優(yōu)值為：4

⑵、由題可得:

nrin4+5

S.L-再-20￡-5

\1.

G9+巧=3

鼻，馬，瑪20

所以可得對偶規(guī)劃：

max―5嗎+3%

一.41

-2叫+!啊￡0

%<1

町之0

(3)、由題問題戶的最優(yōu)解為N以及互補(bǔ)松緊

性定律可得：

-2叫+-0

w2=1

由此解得:

￡

4

11'，最優(yōu)值

由此對偶問題的最優(yōu)解為:W=

為:-5叫+3嗎1

22、用對偶單純形法求解

min2冬+35+4百

4+25+

2天一馬+3再24

(1)、。。馬20

解：由題將原問題寫成標(biāo)準(zhǔn)形式:

mm+30+44

st4+24+馬一冬03

2瑪-\+3瑪-毛=4

2。

所以有:

nnn2不+3馬+44

st_內(nèi)_2/-4+4■-3

一2%+，-3瑪+^=-4

不與，均H20

G-2-110]

由題"1-21-3Q1,以“為基向量，單純性

表如下：

-1-2-110-3

-21-301-4

由此檢驗數(shù)為耳=-2?,以，為離基變量，蒼為

進(jìn)基變量，旋轉(zhuǎn)得：

■?444ms

0-4-1Q-14

11

A0-f1-T-

<1-TI0-T2

同理，檢驗數(shù)小于零，以。為離基變量，號為

進(jìn)基變量,旋轉(zhuǎn)得:

4ms

28

00T

1

035

10IU

由最優(yōu)化準(zhǔn)則可得原問題的最優(yōu)解為:

r

112o28

X=

55，最優(yōu)值為：T

第三章整數(shù)線性規(guī)劃

】、某廠產(chǎn)生43兩種產(chǎn)品，每件產(chǎn)品均要在

甲、乙、丙各臺設(shè)備上加工。每件第，種產(chǎn)品

在第i臺設(shè)備上加工消耗工時為勾，一，2寸

現(xiàn)在各臺設(shè)備可用于生產(chǎn)這兩種產(chǎn)品的工時

分別為每件第j種產(chǎn)品可以提供利潤

根據(jù)需要48產(chǎn)品的生產(chǎn)量不能少于戶

件，JT2。而生產(chǎn)的43產(chǎn)品數(shù)量必須取整

數(shù)。問如何安排生產(chǎn)能使該廠利潤最大？是

建立該數(shù)學(xué)問題的數(shù)學(xué)模型。

解：設(shè)生產(chǎn)科兩種產(chǎn)品的數(shù)量分別為不當(dāng)

則要使利潤最大則目標(biāo)函數(shù)為：

根據(jù)題意可得限制條件有:

/S4

4at芝+'/，A

A"

力上與

,0.為整數(shù)

綜上可得該問題的數(shù)學(xué)模型為：

maxN=

友大知4+^口覆土4

的1%+*=丐

?"+%與44

%"

4之與

不,為整數(shù)

2、指派問題

設(shè)有「項任務(wù)要完成，恰有n個人有能力去完

成任何一項任務(wù)，第，個人完成第，項任務(wù)需

要的時間為1「”卬試寫出一個使總花費

時間最少的人員分配工作方案的數(shù)學(xué)模型。

解：由題可運用I變量，根據(jù)題意可設(shè)》表示

要使總花費時間最少，則：

■a

minz?￡￡浴

根據(jù)題意可得限制條件有:

綜上可得其數(shù)學(xué)模型為：

■■

min工￡

EZ

&￡￡飛=1.f=1產(chǎn)”

4tl

自/=1,j=l,…通

.=Q或！.i,j=l,-,a

6、用分支定界法解下述Q問題：

解：由題記原問題的松弛問題為4,顯然4滿足替代問題的要求:

'24+35414

+。V9

[%。0,且為整數(shù)

4的最有解為：一均不是整數(shù)，則從中選！進(jìn)行分枝。

在4中分成兩個問題耳和彳，如下：

rmxz-3J^+2^招：mu_=3.+2與

2%+34<142天+3馬￡14

+與M92芍+.M9

覆M2與23

A，/20,且為整數(shù)玉420,且為整數(shù)

由此耳的最優(yōu)解為%=354=2,Z=14.5,4的最優(yōu)解為.

由于兩個子問題的最優(yōu)解仍不是原問題的可行解，所以選取邊界較大的子問題，繼

續(xù)分枝，在其分別分成兩個子問題《和心,如下：

%:nmz=3*+29

24+3當(dāng)＜1424+3馬<14

24+，V924+5M9

馬42WV2

4V3424

4馬占。，且為整數(shù).%右。，且為整數(shù)

由此弓的最優(yōu)解為A=3,與=2,z=13,&的最優(yōu)解為瑪=4,^=l,z=14

這兩個解均為原問題的可行解，所以保留可行解中最大的，即：

內(nèi)=4,5=1,z=14

總體過程如下：

第4章非線性規(guī)劃

5、判別以下函數(shù)哪些是凸函數(shù)，哪些是凹的，哪些是非凸非凹的？

(1)式/芍)-60-10苞-4/+*匕馬

(2)北小5)=-4-54+244+104-105

(3)式不巧，/)=彳+3名+9其-2再，+6毛4+2芍/

解：（1Ax）的-矩陣為:

2-1

v'/W

-12

V'4*）的各階順序主子式分別為:

2-1

3>0

2X,-12

?'〃*）是正定的，所以門“）是凸函數(shù)。

（2）0）的一矩陣為:

-22、

V‘?x)

2-10/

V’"*）的各階順序主子式分別為:

-22

16X)

-2<0,2-10

所以門”）是凹函數(shù)。

（3）歡成的一矩陣為:

(2-22、

V'f(x)=-266

,2618

V’4*）的各階順序主子式分別為:

2-22

2-2-2660

=8X)

618

2X,-262

P'W*）是半正定的，所以式“）是凸函數(shù)。

7、證明下列規(guī)劃為凸規(guī)劃

Jmin4+2再/+24

(1)產(chǎn)±問：該問題是否存在最優(yōu)解？

解：由題可得目標(biāo)函數(shù)式工)的一矩陣為：

,(62、

V/(<)=[24)

7,“編的各階順序主子式分別為：

62、

=20>0

6X),B4

是半正定的，所以武力是凸函數(shù)。

又對于條件爪“)=砥，有尸鼠X》?。顯然它是一個半正定矩陣，g(x)是凸函數(shù)，所

以該非線性規(guī)劃是一個凸規(guī)劃。

8、設(shè)(1)?4才+總已知時I1J,試用解析方法求嚼《+”)

的極小點。

+

解：由題可得1+1

帶入六孫始■4吊+彳，中得：%*+T*)=乂1-+(1+//=]45產(chǎn)-46/+5

即：

/to-4(1-6"+(1+.145P-4f+5

所以

f(t)=290t-46

金生

令290"小?0則2如

所以當(dāng)人有忖嚼小吸小

9、用0.618法求一下問題的近似解嘲"'"以'+?]-?""已知函數(shù)的單谷

區(qū)間.535],要求最后區(qū)間精度,=0.8

解：由題迭代過程如下表：

0123

?0.51.6461.6461.646

q1.6462.3542.084

2.3542.7922.3542.084

b3.53.52.7922.354

Pi-0.783-0.961-1.938

VAA

92-0*12.652-0.961

換”換"換》換，

換，

第三輪迭代開始有，-m-2.354-1.646?0.708<0.8-6,所以近似最

優(yōu)解為％2.084,p(t)--L938。

10、用而咖I法求以下問題的近似最優(yōu)解向0")‘-”-6/-16打4給定

4?6/-10之并用解析方法求出該問題的精確最優(yōu)解，然后比較二者結(jié)果。

解：用Afewtaa法求解如下：

先求出j?r(r)-12^-24?-12

計算結(jié)果列于下表：

k**@'&)

16344276

24.735685.4592145.0742

34.164514.813496.1687

44.01050.886084.7573

54.0000

12、用GM㈤疝法對噂1而G+G作非精確一維搜索，取

3*A.八

G=—=0.L%=0>7,

“2、增大探索點系數(shù)a-2.

解：由題*0=。禽=2啊中(0)=0,/(0)=-1

又因為‘⑹="(。)+嗎W(Q)=奈

所以有：P&)*叭°)+嗎加'(°)