第二次和第三次課合訂單純形法第1頁，共42頁，2023年，2月20日，星期一一、基本思想從標準型的LP模型的一個基可行解出發，判斷是否是最優。如果是最優解，結束運算；否則，設法找到一個更優（目標函數值減小）的基本可行解。如此繼續，經過有限次迭代代，就可以找到LP的最優解或判別LP問題有沒有最優解。第三節單純形法（Simplexmethod）(1947)G.B.Dantzig第2頁，共42頁，2023年，2月20日，星期一找出一個初始基本可行解是否最優轉移到另一個基本可行解（找出更小的目標函數值）最優解是否循環結束基本思想框圖如何找初始基本可行解？如何判斷是否最優解？如何轉換基本可行解？第3頁，共42頁，2023年，2月20日，星期一

求回顧上一節例1：的一個基本解和一個基本可行解.第4頁，共42頁，2023年，2月20日，星期一解:約束方程的增廣矩陣為：x2

x4注意到A是2×4矩陣,r(A)＝2.由于第2列和第4列線性無關,構成一個2階單位子塊，因此可構成一個基矩陣.取為基變量,為自由變量,用自由變量表表示基變量得如下同解方程組:第5頁，共42頁，2023年，2月20日，星期一又因5>0,6>0,該解顯然非負，因此這個解也是一個基本可行解。x2

x4第6頁，共42頁，2023年，2月20日，星期一基變量取為其他變量的情況若取為基變量,為自由變量,由于基本解中自由變量全取零,所以只需對第一列,第二列以及常數項列組成的矩陣初等行變換至行最簡形:由此可得基本解:又因3>0,8>0,該解顯然非負，因此這個解也是一個基本可行解。第7頁，共42頁，2023年，2月20日，星期一結論:

若系數矩陣A中存在m階單位子塊,得到基本可行解之后,如何判斷它是否是最優解呢?

設約束線性方程組AX=b的系數矩陣A的秩R(A)=m,則有如下結論成立：記增廣矩陣為（A,b），其中,基變量的取值為單位子塊中1所對應的右邊常數項非負,且對應的常數那么從增廣矩陣中便可讀出一個基本可行解.項的值,自由變量取值全為零.第8頁，共42頁，2023年，2月20日，星期一該解是否最優呢?將代入目標函數表達式中消去得注意到的系數為-10<0,而可行域中可見,當時,目標函數值減小,所以不是最優解.思考:若此時目標函數中自由變量的系數均大于零,那么這個解是否是最優解?第9頁，共42頁，2023年，2月20日，星期一1.單純形表中心部位

A

右列

b

底行(檢驗行)

0

右下端目標函數中常數項的相反數目標函數中變量的系數底線二、單純形表及容許的運算r(A)＝m第10頁，共42頁，2023年，2月20日，星期一2.容許運算中心部位Ab右列底行

0右下端1)底線以上的行可進行初等行變換(三種);2)底線以上的行乘常數后加至底行(包括右下端).底線使表具備下面四個特點:①

②

③④第11頁，共42頁，2023年，2月20日，星期一3.終止條件(最優性條件)當表格具備如下特點:②右列元素非負①

中心部位具有m階單位子塊③底行中相應于單位子塊位置的元素為0(基變量對應的底行元素為零)④底行其他元素非負(自由變量對應的元素非負)則從表格中即可讀得LP問題的最優解和最優值.滿足①②時,可讀出基本可行解滿足①②③時,判斷該解是否最優.滿足①②③④時,可斷定該基本可行解是最優解.第12頁，共42頁，2023年，2月20日，星期一最優解(值)的讀法:

單位子塊中1所在列對應的變量(基變量)取相應右列的值,其余變量(自由變量)取值為零,將它們寫在一起即是一個最優解.而此時右下端元素的相反數即為相應的最優值.第13頁，共42頁，2023年，2月20日，星期一20-41

6-1130

5

1

-3

24

0

20-41

6-1130

5

-10

0

270

-9

的系數為-10<0滿足①②滿足①②③但④不滿足4.舉例第14頁，共42頁，2023年，2月20日，星期一

以上講述了利用單純形表以及容許運算求得一個基本可行解,并判斷其是否最優的方法.

若該基本可行解不是最優的,那么如何由當前表得到一個更優(對應的目標函數值下降)的基本可行解呢?

由上面例題知,取值大于零時,目標函數值下降.這就意味著將成為基變量,不再是自由變量;那么中至少一個將由基變量變為自由變量.單純形法的后半部分討論的主要內容.當前基本可行解不是最優怎么辦?第15頁，共42頁，2023年，2月20日，星期一設當前表格已具備①②③三個特點,但④不滿足:三、基可行解的轉換1)進基變量的確定對應的取為進基變量;從底行中任選一個負元素,比如第16頁，共42頁，2023年，2月20日，星期一2)離基變量的確定“最小比例原則”也稱

原則選取一個,記為

從所選元素所在的列(第j列)底線以上的正元素中按其中:3)進行旋轉運算利用容許的運算將變為1,該列其它元素(包括底行相應的元素)變為0,從而實現將變為基變量的目的.第17頁，共42頁，2023年，2月20日，星期一1.單純形法的迭代步驟1）將問題化為標準型,寫出相應的表格;2）建立滿足①②③三個特點的初始單純形表:若1)對應的表格滿足①②③,直接進入第3)步;若1)對應的表格滿足①②,但③不滿足,則利用將底行以上行的若干倍數加到底行,使③滿足;若1)對應的表格不滿足①②,則借助大M法(下一節的內容)使①②滿足,然后再使③滿足.四、單純形算法及應用第18頁，共42頁，2023年，2月20日，星期一3）若底行元素全非負,則得到最優解，結束運算;否則轉4）.4)確定進基變量對應的取為進基變量;從底行中任選一個負元素,比如令5)確定離基變量從所選元素所在的列(第j列)底線以上的正元素中按第19頁，共42頁，2023年，2月20日，星期一“最小比例原則”選取一個,記為其中:6)進行旋轉運算利用容許的運算將變為1,該列其它元素變為0,從而實現將變為基變量的目的.7）觀察得到的新表(滿足①②③).若底行所有元素均非負,則已得最優解,結束運算;否則,返回第4)步.第20頁，共42頁，2023年，2月20日，星期一2.例題解析例1.求解LP20-41

6-1130

5

1

-3

24

0

解:該LP已是標準形,故直接列出如下表格:滿足①②為判斷該解是否最優,利用容許的運算使③滿足,得:第21頁，共42頁，2023年，2月20日，星期一

2

0

-4

1

6

-1

1

3

0

5

-10

0

270-9

1

0

-21/23

0

1

11/2800

75

21

滿足①②③但④不滿足滿足①②③④可見此LP有最優解最優值為第22頁，共42頁，2023年，2月20日，星期一例2.

求解LP解:先化LP為標準形,列出如下表格:第23頁，共42頁，2023年，2月20日，星期一方法一：

-1

1

1

00

2

1

2

0

10

1031001

15

-2

-3

000

0

-1

1

1

00

2

3

0

-2

10

640-101

13

-5

0

300

6

第24頁，共42頁，2023年，2月20日，星期一

0

1

1/31/30

4

1

0

-2/31/3

0

2

0

05/3-4/31

50

0-1/35/3016

010

3/5-1/53

1

0

0

-1/52/54

001-4/53/53

0

0

0

7/5

1/5

17

滿足①②③④第25頁，共42頁，2023年，2月20日，星期一

010

3/5-1/53

1

0

0

-1/52/54

001-4/53/53

0

0

0

7/5

1/5

17

滿足①②③④是化為標準形的LP的最優解.

略去松弛變量，故原LP問題的最優解為最優值為第26頁，共42頁，2023年，2月20日，星期一方法二：取底行中左邊第一個負元素對應的變量為進基變量

-1

1

1

00

2

1

2

0

10

1031001

15

-2

-3

000

0

04/3

1

01/3

7

05/3

01-1/3

5

1

1/3

001/3

5

0-7/3

002/310

第27頁，共42頁，2023年，2月20日，星期一

0

01-4/5

3/5

3

0

103/5

-1/5

3

1

0

0-1/5

1/5

4

0007/51/5

17

滿足①②③④是化為標準形的LP的最優解.

略去松弛變量，故原LP問題的最優解為最優值為第28頁，共42頁，2023年，2月20日，星期一3.注意事項（可能出現的情況）1）若迭代過程中右列元素中出現‘‘0’’元素(此時對應的基本可行解中某基變量的取值為0)，那么稱該基本可行解是退化的,接下來的迭代可能出現循環.解決辦法:在每次選進基變量時,每次選底行中左邊第一個負元素對應的變量為進基變量,這就是改進的單純形法.2）若最終表格中底行元素均非負,且所有自由變量(非基變量)對應的底行元素(檢驗數)均大于‘‘0’’

,則此時LP有唯一最優解.第29頁，共42頁，2023年，2月20日，星期一3）若最終表格中底行元素均非負,且存在某自由變量(非基變量)對應的底行元素(檢驗數)等于‘‘0’’

,則此時LP有無窮多最優解.4）若最終表格中底行存在負元素,且有一個進基變量所在的列中底線以上沒有正元素(無法迭代下去),則此LP問題無最優解.以上結論的證明參見<<運籌學>>清華大學出版社.第30頁，共42頁，2023年，2月20日，星期一例3.用單純形法求解解:將上述線性規劃化為標準形:第31頁，共42頁，2023年，2月20日，星期一方法一：

1

1

1

1

00

12

2

1

-1

010

6-130001

9

-1

2

-1000

0

01/2

3/2

1

-1/20

9

1

1/2

-1/201/20

3

07/2

-1/201/21

12

05/2

-3/2

01/20

3

滿足①②③但④不滿足滿足①②③但④不滿足第32頁，共42頁，2023年，2月20日，星期一

0

1/3

1

2/3

-1/30

6

1

2/3

0

1/3

1/30

6

0

11/3

01/3

1/31

15

0

3

0100

12

滿足①②③④略去松弛變量,得原LP最優解為

最優解:注:由于最終表底行中自由變量

對應的系數為0,

故有無窮多最優解，即該最優解不是唯一最優解。第33頁，共42頁，2023年，2月20日，星期一方法二：

1

1

1

1

00

12

2

1

-1

010

6-130001

9

-1

2

-1000

0

1

1

1

1

00

12

3

2

011

0

18

-13

00

0

1

9

03

0100

12

滿足①②③但④不滿足滿足①②③④第34頁，共42頁，2023年，2月20日，星期一1

1

1

1

00

12

3

2

011

0

18

-13

0