運(yùn)籌學(xué)課件第一章線性模型

---第1

章線性規(guī)劃---線性規(guī)劃的模型Linear

Programming2006/08-1-2006/08-2----第

1

章 線性規(guī)劃---1.1.2

線性規(guī)劃問題的一般數(shù)學(xué)模型1.相關(guān)概念（1）決策變量：指模型中要求解的未知量，簡稱變量。（2）目標(biāo)函數(shù)：指模型中要達(dá)到的目標(biāo)的數(shù)學(xué)表達(dá)式。（3）約束條件：指模型中的變量取值所需要滿足的一切限制條件。此三項(xiàng)內(nèi)容稱為模型結(jié)構(gòu)的三要素。2006/08-3----第1

章線性規(guī)劃---2.線性規(guī)劃模型的一般要求（1）變量：取值為連續(xù)的、可控的量；（2）目標(biāo)函數(shù)：線性表達(dá)式；（3）約束條件：線性的等式或者不等式。---第

1

章 線性規(guī)劃---線性規(guī)劃問題的一般形式max

z=c1x1+c2x2+………+cnxns.t.a11x1+a12x2+………+a1nxn≤(=,

≥)b1a21x1+a22x2+………+a2nxn≤b2…………

…am1x1+am2x2+………+amnxn≤bmx1

,x2,

………,xn≥0s.t.---subject

to2006/08-4----第1

章線性規(guī)劃---2006/08-5----第1

章線性規(guī)劃---2006/08-6----第1

章線性規(guī)劃---2006/08-7----第1

章線性規(guī)劃---2006/08-8-2006/08-9----第

1

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

z

=

c1

x1

+

c2

x2

+...

+

cn

xna11

x1

+

a12

x2

+

...

+

a1n

xn

=

b121

1

22

2

2n

n

2m1

1m2

2j

=1,

2,...,

nmn

nma

x

+

a

x

+

...

+

a

x

=

bs.t.

...ax

+

a

x

+...

+

a

x

=

bx

j

?

0;2006/08-10----第1

章線性規(guī)劃---4.

線性規(guī)劃模型的標(biāo)準(zhǔn)形式變量：所有變量均xj≥0目標(biāo)函數(shù)：為取“max”形式約束條件：全部約束方程均為“=”連接約束右端項(xiàng)：bi≥0非標(biāo)準(zhǔn)形式情況有變量：xj≤0,或xj無約束目標(biāo)函數(shù)：min約束條件：“≤”或“≥”約束右端項(xiàng)：bi<0---第1

章線性規(guī)劃---LP的標(biāo)準(zhǔn)化：（1）變量：若若xj￡0，令xj=-xj￠，xj￠?0xj無約束，則令xj=xj￠－xj

￠，xj￠?0，xj

￠?0xzzzminz

￠=

-

zz

￠max2006/08-11-（3）約束方程：當(dāng)“￡”時，引進(jìn)松弛（slack）變量+xs；如x1+x2￡3

x1+x2+x3=3當(dāng)“?”時，引進(jìn)剩余（surplus）變量-xs；如x1+2x2?4

x1+2x2－x4=4（2）目標(biāo)函數(shù)：若求

min

z，則

令

z￠=-z，等價于求

max

（z

￠）即有

min

z=

-max

（-

z）i（4）約束右端項(xiàng)：當(dāng)b<0，則不等式兩端同乘（-1）---第

1

章 線性規(guī)劃---例：將下述LP模型標(biāo)準(zhǔn)化：obj.

Min z=2x1-

x2+3x3st. x1+2

x2+4x3

￡

63x1-

2x2+

x3

=

42x1-

x2

-

3x3

?5x1

?

0,

x2無符號限制, x3

￡

0解：設(shè)

z￠=

-

z,

x2=

x2￠-

x2￠￠,x2￠

?0

,

x2￠￠?0, x3=

-

x3

￠,x3￠?0，x4?0,

x5?0,

則有obj. Max

z￠=-2x1

+(x2￠-

x2￠￠)

+

3x3

￠st.

x1+2(x2￠-

x2￠￠)

-

4x3

￠+x4=6

3x1

-2(x2￠-

x2￠￠)

-

x3

￠=42x1

-

(x2￠-

x2￠￠)

+

3x3

￠-x5=5x1

?0,

x2￠?0,

x2￠￠?0,

x3

￠?0,

x4

?0,

x5

?02006/08-12-2006/08-13----第1

章線性規(guī)劃---復(fù)習(xí)思考題：什么是模型結(jié)構(gòu)的三要素？什么是線性規(guī)劃模型？能舉出線性規(guī)劃模型的