運(yùn)籌平時(shí)所有課件-圖解法

提綱建立線性規(guī)劃問題的模型線性規(guī)劃問題的一般形式&標(biāo)準(zhǔn)形式圖解法提綱建立線性規(guī)劃問題的模型線性規(guī)劃問題的一般形式&標(biāo)準(zhǔn)形式圖解法【例1】最優(yōu)生產(chǎn)計(jì)劃問題某廠有甲乙丙三種產(chǎn)品，經(jīng)過三道工序加工，每種產(chǎn)品的加工時(shí)間、各工序加工能力和單位利潤(rùn)如下：產(chǎn)品工序單位產(chǎn)品加工時(shí)間加工能力（min/d）甲乙丙1311240420單位利潤(rùn)325廠方如何安排生產(chǎn)計(jì)劃可以使總利潤(rùn)最大？決策變量：x1，x2，x3分別為產(chǎn)品甲、乙、丙的計(jì)劃日產(chǎn)量決策變量：x1，x2，x3分別為產(chǎn)品甲、乙、丙的計(jì)劃日產(chǎn)量目標(biāo)函數(shù)：每天的利潤(rùn)值3x1+2x2+5x3最大決策變量：x1，x2，x3分別為產(chǎn)品甲、乙、丙的計(jì)劃日產(chǎn)量目標(biāo)函數(shù)：每天的利潤(rùn)值3x1+2x2+5x3最大約束條件及非負(fù)限制：x1321

,

x3

0max 3x1

2x2

5x31

31

2x1

2x2

x3

4303x

2x

460x1,

x2

,

x3

0s.t.

x

4x

420例1的線性規(guī)劃模型為：【例2】配料問題某廠生產(chǎn)雞飼料，每份100kg，飼料中營(yíng)養(yǎng)成分要求及所用飼料中各營(yíng)養(yǎng)成分的含量及成本數(shù)據(jù)如下：配料營(yíng)養(yǎng)成分大豆粉玉米粉石灰石含量要求單位蛋白質(zhì)0.50.090≥22％配料鈣0.0020.0010.38≥0.8％且≤1.2％含量粗纖維0.080.020≤5%單位配料成本2.50.9260.164應(yīng)該如何配置該雞飼料可使成本最低？x1，x2，x3分別為每100kg飼料中大豆粉、玉米粉和石灰石的配置數(shù)量min 2.5x1

0.926x2

0.164x30.5x1

0.09x2

221

2

31

21

20.002x

0.001x

0.38x

0.8s.t.0.08x

0.02x

5x1

x2

x3

100x1

,

x2

,

x3

00.002x

0.001x

0.38x3

1.2x1，x2，x3分別為每100kg飼料中大豆粉、玉米粉和石灰石的配置數(shù)量【思考題】短期投資決策問題，現(xiàn)有以下四種投資項(xiàng)目某公司在年初有100萬(wàn)閑置可供選擇：A：每年初都可以投資，年末可收回投資的115％；，第五年末可收回投資額的B：第二年初投入一筆

145％；C：第三年初投入一筆，第五年末可收回投資額的135％，但該項(xiàng)目至多只可投資40萬(wàn)元；D：每年初可年利率為6％的一年期債券，年底歸還。必須在第五年末全部收回，如何安排投資可使公司在第五年末擁有

最多？xaj為對(duì)第j

年年初投入項(xiàng)目A的xb

,xc為投入項(xiàng)目B和C的

；xdj為對(duì)第j

年年初購(gòu)入債券的，j=1,2,3,4;，j=1,2,3,4,5;xaj為對(duì)第j

年年初投入項(xiàng)目A的xb

,xc為投入項(xiàng)目B和C的

；xdj為對(duì)第j

年年初購(gòu)入債券的，j=1,2,3,4;，j=1,2,3,4,5;xa

2

xb

xdxa

4

xd

4

1.1d

5

as.t.x

1.15xxc

xaj

,

xb

,

xc

,

xdjxa3

xc

xd

3

1提綱建立線性規(guī)劃問題的模型線性規(guī)劃問題的一般形式&標(biāo)準(zhǔn)形式圖解法線性規(guī)劃問題的一般形式max(min)s.t.Z

c1x1

c2

x2

cn

xna11x1

a12

x2

a21x1

a22

x2

a1n

xn

(,

)b1

a2n

xn

(,

)b2

amn

xn

(,

)bmam1x1

am2

x2

x1,

x2

xn

()0線性規(guī)劃問題的一般形式j(luò)

1max(min)s.t.x

j

()0,

j

1,

2

nnZ

cj

x

jn

aij

x

j

(,

)bi

,

i

1,

2

mj

1線性規(guī)劃問題的標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式：

的線性規(guī)劃總可以化22n

nam1x1

am2

x2cn

xn成

!max

Z

c1x1

c2

x2

s.t.a11x1

a12

x2

a1n

xn

b1a21x1

a22

x2

amn

xn

bmx1,

x2

xn

0

a

x

bbi

0(i=1,……m)x

j

0,

j

1,

2

n其中bi

0(i=1,2,….m)j

1s.t.nmax

Z

cj

x

jn

aij

x

j

bi

,

i

1,

2

mj

1不妨寫成矩陣的形式？21aaaa

a11

a1222a1n

b1

x1

a

b

x

2

a

b

x

m1

m2mn

m

n

系數(shù)矩陣A

2n

,資源向量b

2

,

X

價(jià)值向量C

c1

c2

cn

,max Z=

CXs.t.

AX=bX

0如何將一般形式化為標(biāo)準(zhǔn)形式？1.

若目標(biāo)函數(shù)是求最小值minZ

=

CX令

Z’= -

Z,則max

Z’= -

CX如何將一般形式化為標(biāo)準(zhǔn)形式？2.若約束條件是不等式(1)若約束條件是“”不等式y(tǒng)i

0是非負(fù)的松馳變量

(2)若約束條件是“”不等式y(tǒng)i

0是非負(fù)的松馳變量n

nj

1

j

1

yi

biaij

xj

bi

aij

x

jn

nj

1

j

1

yi

biaij

xj

bi

aij

x

j如何將一般形式化為標(biāo)準(zhǔn)形式？若約束條件的某一常數(shù)項(xiàng)bi<0，這時(shí)只要在bi相對(duì)應(yīng)的約束方程兩邊乘上-1若變量xj≤0，則引進(jìn)一個(gè)非負(fù)變量xj’≥0，令xj’=-xj若變量xj

，引進(jìn)兩個(gè)非負(fù)變量xj’

、xj”

≥0，令xj=

xj’

-

xj”將下列問題化成標(biāo)準(zhǔn)形式:s.t.max

Z

=

2x1+3x2x1+2x2

84x1

164x212x1,

x2

0s.t.min

Z

=

-x1+2x2-3x3x1+x2+x3

7x1-x2+x3

2-3x1+x2+2x3

=

5x1,x2

0,x3?min

Z=

x1

+2x2

-3

x3x1

+2

x2

-

x3

≤52x1

+3

x2

-

x3

≥6-x1

-

x2

+x3

≥

-2x1≥0,

x3

≤0s.t.step1min

Z=

x1

+2

x2

+3

x3′x1

+2

x2

+

x3′

≤52x1

+3

x2

+

x3′≥6-x1

-

x2

-

x3′

≥

-2x1

≥0,

x3′

≥0step2min

Z=

x1

+2

(x

′-x

〃)+3

x

′2

2

3x1

+2

(x

′-x

〃)

+

x

′

≤52

2

32x1

+3

(x

′-x

〃)

+

x

′

≥62

2

3-

x1

-′

〃

′(x2

-x

2

)

-

x3

≥

-2′

〃

′x1,

x2

,

x2

,

x3

≥0step3min

Z=

x1

+2(x

′-x

〃)+3

x

′2

2

3x1

+2(x

′-x

〃)+x

′≤52

2

32x1

+3(x

′-x

〃)+x

′≥62

2

3x1

+ (x

′-x

〃

)

+

x

′

≤

22

2

3x1,x

′,x

〃,x

′≥02

2

3step4min

Z=

x1

+2(x

′-x

〃)+3

x

′2

2

3x1

+2

(x

′-x

〃)

+

x

′+

x

=52

2

3

4′

〃

′2x1

+3

(x2

-x

2

)

+

x3≥6≤

2x1

+ (x

′-x

〃)+x

′2

2

3′

〃

′x1,

x2

,

x

2

,

x3

,

x4

≥0step5x1

+ (x

′-x

〃)+x

′2

2

3′

〃

′min

Z=

x1

+2

(x2

-x

2

)

+3x3′

〃

′x1

+2

(x2

-x

2

)

+

x3

+

x4

=5′

〃

′2x1

+3

(x2

-x

2

)

+

x3

-

x5

=

6≤

2′

〃

′x1,

x2

,

x

2

,

x3

,

x4

,

x5

≥0step6min

Z=

x1

+2(x

′-x

〃)+3

x

′2

2

3x1

+2

(x

′-x

〃)

+

x

′+

x

=52

2

3

42x1

+3

(x

′-x

〃)

+

x

′

-

x

=

62

2

3

5x1

+ (x

′-x

〃

)

-

x

′

+

x

=

22

2

3

6x1,

x

′,

x

〃,

x

′,

x ,

x ,

x

≥02

2

3

4

5

6step7max

Z’=

-x1

-2(x

′-x

〃)-3x

′+0x

+0x

+0x2

2

3

4

5

6′

〃

′x1

+2

(x2

-x

2

)

+

x3

+

x4′

〃

′2x1

+3

(x2

-x

2

)

+

x3-

x5=5=

6+

x6

=

2x1

+ (x

′-x

〃

)

-

x

′2

2

3′

〃

′x1,

x2

,

x

2

,

x3

,

x4

,

x5

,

x6

≥0提綱建立線性規(guī)劃問題的模型線性規(guī)劃問題的一般形式&標(biāo)準(zhǔn)形式圖解法線性規(guī)劃問題的解求解方法—般有兩種方法圖解法單純形法兩個(gè)變量、直角坐標(biāo)適用于任意變量、但需將一般形式變成標(biāo)準(zhǔn)形式圖解法解的概念可行解：滿足約束條件及非負(fù)限制的解為可行解。所有可行解的集合為可行域。最優(yōu)解：使目標(biāo)函數(shù)取得最優(yōu)的可行解。例3.生產(chǎn)計(jì)劃問題某廠生產(chǎn)甲乙兩種產(chǎn)品，各自的零部件分別在A、B車間生產(chǎn)，最后都需在C車間裝配，相關(guān)數(shù)據(jù)如表所示：?jiǎn)柸绾伟才偶?、乙兩產(chǎn)品的產(chǎn)量，使利潤(rùn)為最大。產(chǎn)品車間工時(shí)單耗甲

乙生產(chǎn)能力A108B0212C3436單位產(chǎn)品獲利35圖解法x1≤82x2

≤123x1

+4

x2

≤36x1

≥0,

x2

≥0S.t.x1

=82x2

=12x136x290ABC(4,6)D

4

8

123x1

+4

x2

=36五邊形OABCD內(nèi)(含邊界)的任意一點(diǎn)都是滿足所有約束條件的一個(gè)解，即可行解

。1.可行域的確定所有可行解的集合為可行域。在圖上，可行域即所有約束條件共同圍成的區(qū)域。例3的數(shù)學(xué)模型為max Z=

3x1

+5

x2圖解法Z=30Z=42Z=15最優(yōu)解的確定目標(biāo)函數(shù)Z=3x1+5x2

代表以Z為參數(shù)的一族平行線。x1

=82x2

=1236x290

x1ABD4

8

123x1

+4

x2

=36位于同一直線上的點(diǎn)的目標(biāo)函數(shù)值相同。最優(yōu)解：可行解中使目標(biāo)函數(shù)最優(yōu)(最大或最小)的解C(4,6)求解結(jié)果：max Z=

3x1

+5

x2x1

≤82x2

≤123x1

+4x2

≤36x1

≥0,

x2

≥0甲、乙兩產(chǎn)品的最優(yōu)產(chǎn)量分別為x1=4，x2=6時(shí)取得最大的利潤(rùn)為3x1+5x2

=42.圖解法圖解法補(bǔ)充定理（證明過程省略）：若可行域有界，線性規(guī)劃的最優(yōu)解一定可以在可行域的頂點(diǎn)上達(dá)到。圖解法4.解的可能性唯一最優(yōu)解：只有一個(gè)最優(yōu)解