第一節(jié) 基本概念第二節(jié) 線性規(guī)劃問題的圖解法第三節(jié) 線性規(guī)劃模型的解及性質(zhì)第四節(jié)

單純形法第五節(jié) 對偶規(guī)劃第六節(jié) 運輸問題及表上作業(yè)法線性規(guī)劃第四節(jié) 單純形法一、單純形法的解題過程二、線性規(guī)劃模型的變換三、單純形法的計算方法四、一般情況的處理--人工變量法一、單純形法的解題過程得到最優(yōu)解或證明最優(yōu)解不存在線性規(guī)劃標準形檢查該點是否最優(yōu)解從可行域某個頂點開始不是取一個“相鄰”、“更好”的頂點上次課講授內(nèi)容二、 線性規(guī)劃模型的變換①目標求極大值②變量非負③右端項非負④全部等式約束單純形法要求線性規(guī)劃模型標準形式規(guī)范形式⑤系數(shù)矩陣中包含一個單位子矩陣每個約束方程中要有一個變量的系數(shù)１，而這個變量在其余方程中不出現(xiàn)。上次課講授內(nèi)容三、 單純形法的計算方法單純形法的基本步驟:（1）建立初始單純形表確定基變量、非基變量以及基變量、非基變量（全部對于0）和目標函數(shù)的值，并求出相應(yīng)的檢驗數(shù)（在用非基變量表達的目標函數(shù)表達式中，我們稱非基變量xj的系數(shù)（或其負值）為檢驗數(shù)）

；上次課講授內(nèi)容（2）檢驗、確定進基變量如果任何一個非基變量的值增加都不能使目標函數(shù)值增加，即所有檢驗數(shù)非正，則當(dāng)前的基本可行解就是最優(yōu)解，計算結(jié)束。若存在檢驗數(shù)大于0，那么絕對值最大者對應(yīng)的非基變量xj稱為“進基變量”，轉(zhuǎn)（3）。單純形法的基本步驟:(3)

確定出基變量滿足這個基變量xr稱為出基變量。轉(zhuǎn)（4）。如果進基變量的值增加時，所有基變量的值都不減少，即所有aij非正，則表示可行域是不封閉的，且目標函數(shù)值隨進基變量的增加可以無限增加，此時，不存在有限最優(yōu)解，計算結(jié)束。單純形法的基本步驟:（4）迭代運算將進基變量作為新的基變量，出基變

量作為新的非基變量，確定新的基、新的基本可行解和新的目標函數(shù)值。在新的基變量、非基變量的基礎(chǔ)上重復(fù)（1）。單純形法的基本步驟:注意：單純形法中每一步運算只能用矩陣初等行變換；表中第3列(b列)的數(shù)總應(yīng)保持非負（≥0）當(dāng)所有檢驗數(shù)均非正（≤0）時，得到最優(yōu)單純形表?？赡艹霈F(xiàn)的特殊情況單純形法求解中的特殊情況1．最終產(chǎn)生最優(yōu)值的單純形表中，某一非基本變量的檢驗數(shù)＝0，意味著作任何增大，目標函數(shù)的最優(yōu)值不變．此時線性規(guī)劃問題的最優(yōu)解并不唯一，有多重最優(yōu)解．（見下面例題）例

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

令于是原線性規(guī)劃問題變?yōu)闃藴市问剑簡渭冃伪淼?0-10013/81/4311

0

-1/8

1/40

0

-1

0126-3

-1

-1

-1x1

x2

x3

x4-2

[2]

1

03

1

0

1-2

2

0

0-1

1

?

0[4]

0

-1/2

1b-1

x3

4-1

x4

6Cj

-Zj-1

x2

2-1

x4

4Cj

-Zj-1-x32x1Cj

-Zj最優(yōu)解為：最優(yōu)值為：2．當(dāng)樞列（進基變量所在列）中的每一項系數(shù)不是0就是負值時，說明所有約束條件對進基變量的增加都無約束作用，因此目標函數(shù)可以無限地增加．這種情況我們稱為無有限最優(yōu)解（或稱有無界解或無最優(yōu)解）．但在現(xiàn)實中，不可能有此情況，往往是模型建立錯誤，遺漏了一些約束條件所致．單純形法求解中的特殊情況單純形法求解中的特殊情況3．在選取進基變量時，有2個及2個以上變量的檢驗數(shù)具有相同的最大正值（極小化問題為相同的最小負值），這時可任選其中一個變量進基．選擇進基變量的不同，可能在達到最優(yōu)解前迭代的次數(shù)也不同，但事先無法預(yù)測．4．出現(xiàn)相同的最小比值，此時可從具有相同最小比值所對應(yīng)的基本變量中，選擇下標最大的那個基本變量為出基變量．這時有可能出現(xiàn)退化的基本可行解，即至少有一個基本變量為零（見規(guī)劃教材例2-8中的表

2-6和表2-7）．出現(xiàn)退化的基本可行解對運算帶來麻煩，理論上可能出現(xiàn)單純形法陷入循環(huán)或閉環(huán)，在每次迭代中值保持不變，不能使解趨向最優(yōu)解．但幸運的是，在實際應(yīng)用中從未遇到或發(fā)生過這種情況．盡管如此，人們還是對如何防止出現(xiàn)循環(huán)作了大量研究。提出了各種避免循環(huán)的方法。單純形法求解中的特殊情況在選擇進基變量和出基變量時作以下規(guī)定：j①

在選擇進基變量時，在所有

>

0的非基變量中選取下標最小的進基；②當(dāng)有多個變量同時可作為出基變量時，選擇下標最小的那個變量出基。這樣就可以避免出現(xiàn)循環(huán),當(dāng)然，這樣可能使收斂速度降低。#避免循環(huán)的方法：五、一般情況的處理--人工變量法一般情況的處理：主要是討論初始基本可行解不明顯時，常用的方法。例如

P53

3(4)規(guī)范化規(guī)范化標準化考慮一般問題：bi

>

0

，

i

=

1

,

…

,

mMax

z

=

c1

x1

+

c2

x2

+

…

+

cn

xns.t.a11

x1+

a12

x2

+…+

a1n

xn

=

b1a21

x1+

a22

x2

+…+

a2n

xn

=

b2...am1

x1+

am2

x2+…+

amn

xn

=

bmx1

，x2

，…

，xn

≥

0引入人工變量

xn+i

≥

0，i

=

1

,…,

m；a11

x1+

a12

x2+

…

+

a1n

xn+

xn+1=

b1=

b2+

xn+2a21

x1+

a22

x2+

…

+

a2n

xn...am1

x1+

am2

x2+

…

+

amn

xn

+

xn+m

=

bmx1,

x2

...

xn

,

xn+1,

…,

xn+m

≥

01．

兩階段法：兩階段法是把一般問題的求解過程分為兩步：第一步：求解原問題的一個基本解：建立一個輔助問題。對于前面的約束方程組，構(gòu)造一個標函數(shù)為：Min

z＝

xn+1

＋xn+2

＋…＋xn+m這樣，從目標最優(yōu)角度迫使人工變量取零值，以達到原問題一個基本可行解的目的。這個階段的輔助問題有下列明顯的事實：設(shè)X*

=(

x*

,

x*

,…

,

x*

,

x*

,

…,

x*

）1

2

n

n＋1

n＋m為這個問題的最優(yōu)解，那么，若x*

x*

x*n+1

＝

n＋2＝…＝

n＋m＝0，則(x*

,

x*

,…

,

x*

）為原問題的一個基本可行解，這時1

2

n目標函數(shù)值為零；否則，即x*

,

…,

x*

不全為零時，說n＋1

n＋m明原問題無可行解。即引入人工變量

xn+i

≥

0，i

=

1

,…,

m；構(gòu)造:Min

Ｚ＝

xn+1

＋

xn+2

＋

…

＋

xn+mMaxＺ

=

-

xn+1

-xn+2

-

…

-

xn+ma11

x1+

a12

x2+

…

+

a1n

xn+

xn+1

=

b1

a21

x1+

a22

x2+

…

+

a2n

xn+

xn+2

=

b2...am1

x1+

am2

x2+

…

+

amn

xn+

xn+m

=

bmx1

，

x2

，...，

xn

，

xn+1

，…，

xn+m

≥

0顯然，xj

=

0

，

j

=

1,

…

,

n

;xn+i

=

bi

，

i

=

1,

…

,

m是基本解,它對應(yīng)的基是單位矩陣。結(jié)論：若得到的最優(yōu)解滿足

xn+i

=

0i

=

1,…,m

，則是原問題的基本可行解;否則，原問題無可行解。得到原問題的基本可行解后，第二階段求解原問題。第二步：求解原問題：以第一步得到的基本可行解為初始基本可行解，用單純形法求解原問題。在表格計算過程中，這一步的初始單純形表可這樣產(chǎn)生（1）由第一步的最優(yōu)單純形表刪去xn＋1

，xn＋2

，…，xn+m列；把第一行的目標函數(shù)系數(shù)行換為原問題目標函數(shù)的系數(shù)；檢驗數(shù)行直接用前文介紹的方法在表格上計算得到，即用xj的價值系數(shù)cj減去cB列的各元素與xj列各對應(yīng)元素的乘積，把計算結(jié)果填入xj列的最后一行，得到檢驗數(shù)σj 。例1：Max

Z

=

5x1

+

2x2

+

3x3

-

x4x1

+

2x2

+

3x3

=

152x1

+

x2

+

5x3

=

20x1

+

2x2

+

4x3

+

x4

=

26x1

,

x2

,

x3

,

x4

≥

0第一步

求解原問題的一個基本解：Max

Z

=

-

x5

-

x6x1

+

2x2

+

3x3

+

x5

=

152x1

+

x2

+

5x3

+

x6

=

20x1

+

2x2

+

4x3

+

x4

=

26x1

,x2

,x3

,x4

,x5

,x6

≥

0第一階段得到原問題的基本可行解:(0，15/7，25/7，52/7)T第二步，求解原問題：把基本可行解填入表中得到原問題的最優(yōu)解:(25/3，10/3，0，11)T最優(yōu)目標值：112/3引入人工變量

xn+i

≥

0

（i

=

1

,

…

,

m）及充分大正數(shù)

M

。得到：Max

Z

=

c1

x1

+

c2

x2

+

cn

xn

+

M

xn+1

+

Mxn+ma11

x1

+

a12

x2

+

…

+

a1n

xn

+

xn+1

=

b1a21

x1

+

a22

x2

+

…

+

a2n

xn

+

xn+2

=

b2...am1

x1

+

am2

x2

+

…

+

amn

xn

+

xn+m

=

bmx1

,x2

，…

，xn

，xn+1

，…

，xn+m

≥02．大M法Max

Z=

5x1+

2x2+

3x3-x4

-M

x5-M

x6x1+

2x

2+

3

x3+

x5

=152

x1+

x2+

5

x3+

x6

=

20x1+

2

x2+

4

x3+

x4

=

26x1