1、山西大學經濟與管理學院山西大學經濟與管理學院運籌學運籌學主講：范建平主講：范建平 博士博士第二章 單純形法2.1 基本思想2022年3月7日星期一山西大學經濟與管理學院 范建平22.1 基本思想2022年3月7日星期一山西大學經濟與管理學院 范建平3p單純形法（單純形法（Simplex Method） ，1947年由美國學者年由美國學者George Dantzig首先提出。首先提出。p從內容上分從內容上分2種種n原本方法（原本方法（Primal Simplex Method）n對偶方法（對偶方法（Dual Simplex Method）p從形式上分從形式上分3種種n方程組形式（方程組形式（基本

2、思想基本思想）n表格形式（表格形式（運算步驟運算步驟）n矩陣形式矩陣形式*2.1.1 基本思路2022年3月7日星期一山西大學經濟與管理學院 范建平4D(0,4)A(6,0)O(0,0)x1x2C(3,4)B(6,2)z法向z=0等值線R2.1.1 基本思路2022年3月7日星期一山西大學經濟與管理學院 范建平5p首先確定可行域首先確定可行域R內的一個極點作為內的一個極點作為始點始點，稱為，稱為初始基初始基本可行解；本可行解；p然后檢驗當前解（可行極點）是否最優，是則結束；然后檢驗當前解（可行極點）是否最優，是則結束；p否則，從該點出發，進化到另一極點，使目標函數值上否則，從該點出發，進化到另

3、一極點，使目標函數值上升（至少不降），又保達點可行；升（至少不降），又保達點可行；p如此不斷迭代，直到目標函數值達到最大，或依法判明如此不斷迭代，直到目標函數值達到最大，或依法判明無解。無解。2.1.2 唯一前提2022年3月7日星期一山西大學經濟與管理學院 范建平6p【例例2-1】試用方程組形式的單純形法，求解范例的試用方程組形式的單純形法，求解范例的LP問題。問題。p解：范例的標準形如下：解：范例的標準形如下：12132412512345max321628. .2318,0zxxxxxxstxxxx x x x x【例2-1】2022年3月7日星期一山西大學經濟與管理學院 范建平7 312

4、12124532=06282318zxxxxxxxxx（0）1,2,3,4,5jzxj 牢記變量 值須達最大，恒保其余變量均須非負，只需求解下列方程組： 345zxxx將 作為附加方程式（0）的永恒基變量，再取松弛變量 ， ， 作為約束方程式，的基變量，典式它們的列向量構成一個4階單位陣，這說明方程組已是。如前1.2.4節所述，這是單純形法的唯一前提。1212-3 -2=302zxzxxxLP將目標函數改寫成 ，將其納入約束方程組中，得到問題的等價問題。2.1.3 進化規程2022年3月7日星期一山西大學經濟與管理學院 范建平8p1. 確定一個可行極點作為始點確定一個可行極點作為始點34500

5、3450,0,0,1,6,8 8Tx x xz 00在典式（）的約束方程組中，以=為基，得到相應的一個基本可行解是以為基變可行解的本=基量XBa a aX 325121412032=02218368zxxxxxxxxx（ ）03450,z=x x x各分量中，基變量的值，約束方程式，的右端常數；對應的目標函數值，附加方程式（0）對應的右端常數，0.恰為恰為XX 00z=很容易識別方程組的一個基本可行解，及其對應的目標函數值0.這樣就能確定 這是典為始式的必然結果，（初始基）。點本可行解XX2.1.3 進化規程2022年3月7日星期一山西大學經濟與管理學院 范建平9p2. 檢驗當前解是否最優，稱

6、為最優性檢驗檢驗當前解是否最優，稱為最優性檢驗 1,2,jjxjn將式（0）成為，其中 的系數。稱為，記為可據以檢這正是將式（檢驗方程檢驗0）引入方程驗前解組的是否最優，數用意所在。01,2,LP0,jjjn最優性檢驗的準則：若一切檢驗數非負：，則問題的當前解最優；否則，只要存在一個負（1）（2）檢驗數則當前解非優。 1213241253=0062823182zxxxxxxxxx（ ）0120= 32=-對范例的當前解進行最優性檢驗如下：，可以判定當前解非優。XX201,z00 xx：的前兩個分量意味著不生產甲、乙兩種產品，利潤為0；只要安排生產甲、乙兩種產品就能范例的經濟使利潤值意義釋。解增

7、大X2.1.3 進化規程2022年3月7日星期一山西大學經濟與管理學院 范建平10p3. 從當前極點進化到另一極點，既使目標值上升，又保達點可行從當前極點進化到另一極點，既使目標值上升，又保達點可行 12,0z00 xx由于目前均為非基變量，如果讓它們變為基變量，即讓其取值從0變為正數，由是可知，就能使目標函數值 增大。121,200kxxxk 這就需要從當前的非基變量和選擇一個變為基變量，即所謂選擇“上進路線”。kkkxxx專業術語稱為：；或者說選擇一個非基變量，讓選擇一個進基變量進基。m：在一個線性規劃中，基變量的個數恒注等于階數意.選哪個xk作為進基變量？甲產品的單位利潤為300元，乙產

8、品的單位利潤為200元，所以選擇生產甲產品2.1.3 進化規程2022年3月7日星期一山西大學經濟與管理學院 范建平111345=33rmxxxxx范例的階數，有 個基變量。在確定進基后，必須在原有的3個基變量， ，中選擇一個變為非基變量。rrkrrxxxxx專業術語稱為：選擇一個；或者說選擇一個基變量，讓離基。即以變量替換離基1145113511340,0,6,8,18,0,0,0,0,0,0TTTTxx xxxxxx x0=上述基變量的替換意味著，要將當前的基本可行解轉化為另一個=本解：或或基XXXX要保證新基本解的可行性。選哪個xr作為出基變量？ 要確保達點X1的可行性，X1的各分量除了

9、x1變為正數， x2仍為非基變量等于0，其他分量x3，x4，x5必須全都保持取值非負保持取值非負。2.1.3 進化規程2022年3月7日星期一山西大學經濟與管理學院 范建平1231511416 -82-118-2618 2xxxxxxx00031452 1=66,0,0,8,6Txxx即所謂“”，從而，有式可得：0（離基），8，從而得到一個新的基本可行解，即所謂“”確定行程抵達的新極點=X134516,-=min 6,18 2 =6xxxxx不能取否則， ，全都為正數，無一離基。所以式（2 2）只能取等式，即有：1min 6,18 2 =6-x （有：2故2）345:(0)xxx從方程組中的式

10、，中，依次解出， ， ，并令其，可得 這就實現了一次基本可行解的轉換，或可行基之間的變換，簡稱為（可行）基變換。相應的運算稱為換基運算。單純形法本質上就是一種迭代運算。 325121412032=02218368zxxxxxxxxx（ ）2.1.4 可行基變換2022年3月7日星期一山西大學經濟與管理學院 范建平13p1.轉換規則轉換規則主元的確定主元的確定n通過進基、離基變量的更替，實現了從一個極點進化到另一個極點。通過進基、離基變量的更替，實現了從一個極點進化到另一個極點。為確保始終是在可行基或可行極點之間轉換，必須遵循以下規則。為確保始終是在可行基或可行極點之間轉換，必須遵循以下規則。確

11、定進基變量的規則最小檢（1） 驗數規則2|01,2,3jjkkkkkjxaxn min ，進按照：確定的對應的非基變量，同時，確定的系數列向量基列。為主a 12131241252=00160+ 2823183zxxxxxxxxxx（ ）進基主列2.1.4 可行基變換2022年3月7日星期一山西大學經濟與管理學院 范建平14p1.轉換規則轉換規則主元的確定主元的確定確定離基變量和主元的規則最?。?） 比值規則1,2,20=3|0ikilikiklklkkraaimblaaaxbbamin最根據主列中中的一切正數按照式確定，以及對應的第 行（方程）為（主方程），主行中的原基變量就是離基變量，同時確

12、定主列中的主行小比值主素行元為主元。 12131241252=00160+ 28231368 18 21zxxxxxxxxxx（ ）進基主列比值主行主元離基2.1.4 可行基變換2022年3月7日星期一山西大學經濟與管理學院 范建平15p2. 轉換方法轉換方法換基運算換基運算n換基運算即對當前方程組進行一系列換基運算即對當前方程組進行一系列初等變換初等變換，其目的是：，其目的是：將主列化成將主列化成單位向量單位向量，以符合典式。，以符合典式。n（1）將主元化為）將主元化為1。l用主元的倒數乘以主方程，得到新方程（用主元的倒數乘以主方程，得到新方程（a），稱為），稱為源方程。源方程。n（2）再將

13、主列中其余元素全部消去）再將主列中其余元素全部消去，都化為，都化為0.l欲消去主列中哪行非欲消去主列中哪行非0元素，就用其相反數乘以源方程（元素，就用其相反數乘以源方程（a）后，再）后，再加給該非加給該非0元素所在行。反復這樣，主列化成元素所在行。反復這樣，主列化成單位列向量單位列向量。 (1)由于主元為1，已經符合要求；將主方程填寫入新方程組中，仍置于原行序處，作為，表上記號（如打），以備正確識別源方程、援用。2.1.4 可行基變換p范例的可行基變換范例的可行基變換 12131241252=00160+ 28231368 18 21zxxxxxxxxxx（ ）進基主列比值主元離基 100.(

14、2)再將方程組主列中其余非元素全部消去，都化為a 這樣得到一個新方程組 ，如右所示。 2313242352+3=180628326zxxxxxxxxx（ ） 114150=,18,6,0,0,8,6Tz 換基運算可確保方程組 必定符合典式，得到以為基的基本可行解：其標值。比好目Ba aXaX2.1.4 可行基變換2022年3月7日星期一山西大學經濟與管理學院 范建平17 23123242352=180106288 236 32zxxxxxxxxxx（ ）進基主列比值主行主元離基35133452355 32 3=22064 32 342 31 32zxxxxxxxxxx（ ） 1210=-2進行

15、最優性檢驗：式存在負檢驗數，可以判定當前解非優，仍需進行換。再對基變XX 按主元對方程組 進行一次換基運算，得到新方程組 ： *6,2,0,4,00T由于式中，所有檢驗數均為非負，故得到最優基本解：X*z =22 ,最優值：同圖解法結果一致。2.2 基本方法2022年3月7日星期一山西大學經濟與管理學院 范建平182.2.1 單純形表上述方程組的初等變換，可以用形式更簡明的增廣矩陣的初等變換取代。上述方程組的初等變換，可以用形式更簡明的增廣矩陣的初等變換取代。1211211111,11222,12,10122-1000001001010jmmnmmnmnmnmmm mmnmnmccccccxx

16、xxxcxaabbbcxaacxaaz表一般單純形表的基本結構比值基解檢驗行“”列填寫基基變量；jc“ ”列填寫基變量對應的價值系數；012,0,0Tmb bb“”列填寫方程組的右端常數，他們就是同行基變量的，據此識別當前的基本可解行解：值X 0=(24a),1,2,(24 )jTBTjBjjzzcjnb00它們按如下公檢驗行對應上一節所謂檢驗方程。其中 為當前解對應的，目標函數值檢驗數。式算出：為C bC a2.2.2 單純形法的運算步驟20LP=,1,12,2,TBTjBjjzcjn0將原問題化成標準形。在系數矩陣中找出或一個做初始基，建立典式構造滿秩排列陣初始單純形表。其檢驗行的數據按下

17、列公式算出：標準化建立單純性表C bC a 單純形法的運算步驟共有六步，其中前2步為預備步驟，后4步為迭代步驟。預備步驟僅為建立符合典式的初始單純形表。而迭代步驟則是反復運用的主要步驟，包括：解的判斷（3、4兩步）和基變換（5、6兩步）兩部分工作，具體如下：2022年3月7日星期一山西大學經濟與管理學院 范建平2.2.2 單純形法的運算步驟21134,2,40,LP5jssjna只要檢若所有檢驗數都非負：0，則當前解最優，停止；否則轉。檢驗數而且它對應的系數列向量 中不含正數，即可判斷最優性原問題解無驗行界，檢驗解無界停止；否則中存在一個轉判斷。2.2.2 單純形法的運算步驟|01,2,5,j

18、jkkkkkjnxxa 先按最小檢驗數規則確定進基變量和主列，即按確定的對應的非基變量，同確定主元時，確定的系數列向量min ，進基列。為主610.jlkca先畫一個新表，調整“基”列、“ ”列，即以進基變量及其價值系數替代離基變量及其價值系數；其余基變量及其價值系數不變。然后，按主元對原表進行一次換基運算，其目的是，其中主元化為換基運，其余把主元素列化成算單位全化為向量=|0ilikiklklkrbbaalxaa再按最小比值規則確定主行和離基變量，從而確定主元，即按確min定，以及對應的第 行為，主行中的原基變量離基，同時確定主行、主列交叉處元素最小比值主行為主元。2.2.3 單純形法的運算

19、過程 2022年3月7日星期一山西大學經濟與管理學院 范建平23p【例例2-2】試用表格形式的單純形法，再次求解范例的試用表格形式的單純形法，再次求解范例的LP問題問題12132412512345max321628. .12318,0zxxxxxxstxxxx x x x x解：（第0次迭代）標準化滿秩單位陣，符合典式，可以建立初始單純形表。先畫出表頭2jc建立典式單純形表基解2.2.3 單純形法的運算過程 2022年3月7日星期一山西大學經濟與管理學院 范建平24545132433261000802001800123000320002001100jxxcxxxxxx比值基解檢建立典式單純形驗

20、表行00111222=0,0,06,8,180=0,0,0 1,0,233=0,0,0 1,0,2022,jTTBTTBjTTBzzcc 不必計算；只需計算目標值 和非基變量檢計算檢驗行驗數基變：量的檢驗數C bC aC a13=-3=-2最由于檢驗行中優性存在負檢驗數，,2，所以當檢驗前解非優。142由于負檢驗數,所對應的系數列向量中都含有正數，不屬解無界判斷故于解無界。2.2.3 單純形法的運算過程 2511113111min -3 -2 =-53=6 186=min=121=6xxxa按最小檢驗數規則：，確定對應的非基變量,同時確定的系數列向量為主列。再按最小比值規則：，確定最小比值對應

21、的第1行位主行，主行中的原基變量（第1次迭。代）確定主進基離。元基為主元a12345345320000601006 1=6=08020100182300118 2=9032000jcxxxxxxxx檢行比值基解驗442515133200036010008020100603-201810-2300jxxcxxxxxx1比值基解檢驗行2.2.3 單純形法的運算過程 2022年3月7日星期一山西大學經濟與管理學院 范建平261336jcxx畫一個新表，調整“基”列、“ ”列,即以進基變量及其價值系數 替代離基變量及其價值系數0；其余變量及其價值系換基運算數不變。2454531120060300080

22、2010018230010-3-2000301jcxxxxxxxx1比值基解檢驗行3=-2由于檢驗行中存在負檢驗數2，所以當最優前性檢驗:解非優。42由于負檢驗數所對應的系數列向量含有正數，不解無界判屬于斷故:解無界。2.2.3 單純形法的運算過程 2022年3月7日星期一山西大學經濟與管理學院 范建平272322252=-2=25axxx唯一負檢驗數對應的非基變量,同時確定 的系數列向量為主列。再按最小比值規則：對應的第3行位主行，主行中的原基變（第2次迭代）進基離基確定元。主量。為主元a513451422-5 3200036010008020108 24062-206 3=11802=-3

23、002jcxxxxxxxx表范例的迭代單純形表主元的確定比值基解1檢驗行2.2.3 單純形法的運算過程 3236jca畫一個新表，調整“基”列、“ ”列,按主元對原表進行一次換換基運算基運算。134512422-6 3200036010004004 31-2 3220-2 301 322005 302 3jxxcxxxxxx表范例的最優單純形表比值基解1檢驗行1*6,2,0,4-02-,2Tz在單純性表計算過程中，除了初始單純形表的檢驗行數據，須按公式（2 4）計算外，其余迭代單純形表的檢驗行數據，都由由于所有檢驗數都非負，所以當前解最優，換基運算而得出，但公式（2 4。有：）仍有效X=(24

24、a),1,2,(24 )TBTjBjjzcjnb0C bC a2.3 其他法則2022年3月7日星期一山西大學經濟與管理學院 范建平292.3.1 人工方法2022年3月7日星期一山西大學經濟與管理學院 范建平30p如前所述，單純形方法首先需要確定一個初始基本可行如前所述，單純形方法首先需要確定一個初始基本可行解，這是通過確定解，這是通過確定典式典式自動得到的。自動得到的。n典式典式： 在約束方程組的系數矩陣中存在一個在約束方程組的系數矩陣中存在一個滿秩排列陣滿秩排列陣的的標準型標準型LP問題。問題。p這樣就產生以下問題：這樣就產生以下問題：n有些有些LP問題根本沒有可行解，更無基本可行解；問

25、題根本沒有可行解，更無基本可行解；n有些約束方程組線性相關，其系數矩陣為降秩矩陣；有些約束方程組線性相關，其系數矩陣為降秩矩陣；nLP問題的標準型多為非典式問題的標準型多為非典式。p本節介紹本節介紹LP問題問題典范化典范化的一般法的一般法人工方法人工方法n即即大大M法法和和兩階段法兩階段法【例2-3】試用單純形法求解下列LP問題2022年3月7日星期一山西大學經濟與管理學院 范建平311212212max232. . -23,0zxxxxstxxx x12123241234max23(0)2-=. . -2+=3,0zxxxxxstxxxx x x x所得模型并非所得模型并非典式典式解：標準化

26、模型。1212325254413max232-+=2. . -2+=3,0zxxxxxstxxxxxxxxx加非負人工變量加非負人工變量x5x4 ，x5的系數構的系數構成成滿秩排列陣滿秩排列陣，已成典式已成典式00,0,20,3TX x4 ，x5為基變量的初始為基變量的初始基本可行解基本可行解前前4個分量顯然不是原個分量顯然不是原方程的解。方程的解。 一般而言，給一個等式方程左端加上一個非負變量，多半會破壞原方程的解，除非該變量取值為0.啟發：通過單純形方法的換基運算，讓人工變量全部離基，從而取值為0。關鍵是如何構造目標函數。1. 大M法2022年3月7日星期一山西大學經濟與管理學院 范建平3

27、2p這里，這里，M0，是一個很大的正數。，是一個很大的正數。p大大M法的基本思想：法的基本思想：n在標準型在標準型LP模型（模型（1-2）的函數約束方程（）的函數約束方程（1-2b）左端，適當引入非負）左端，適當引入非負人工變量，為系數矩陣構造一個滿秩排列陣，并將人工變量，為系數矩陣構造一個滿秩排列陣，并將M作為人工變量在目作為人工變量在目標函數中的系數，構成人工問題。標函數中的系數，構成人工問題。n所謂所謂“適當引入適當引入”，即，即 “最少引入最少引入”，如，如【例例2-3】，只需引入一個人，只需引入一個人工變量就可構造工變量就可構造2階（滿秩）排列陣，從而構造成如下人工問題：階（滿秩）排

28、列陣，從而構造成如下人工問題：12512352412345max232-+=2. . -2+=3,0zxxMxxxxxstxxxx x x x x注意：用單純形法求解這類人工問題，只要最終全部人工變量都能從“基”列中替換出去，則不論在第三步（最優解），還是第四步（解無界）結束，所得人工問題的結果就是原問題的結果；否則，若存在人工變量無法從“基”列中被替換出去，原問題無可行解。1. 大M法33p用大用大M法求解法求解【例例2-3】的人工問題的人工問題2345441512-7 M-3200-21-1010312010-3- -200311 2-1 201 20405 2-1 211 230-1 2

29、-3 20+3 2jxcxxxxxxxx表按大法求解【例2 3】迭代單純形表M比值基解M檢驗行2M2MM檢驗行M1M(a)(b)32-7b=-3 22-7bLP在表的（ ）的檢驗行中存在一個檢驗數，它所對應的系數列向量中不含正數，可確定該人工問題解無界。在表的（ ）“基”列中不存在人工變量，故原問題也為無界。注意：一旦一個人工變量離基，即可刪除該列。大M法不便于計算機編程；編程時往往采用兩階段法。2. 兩階段法2022年3月7日星期一山西大學經濟與管理學院 范建平34p該法把問題的求解分為該法把問題的求解分為兩個階段兩個階段：n第第1階段通過構造并求解人工問題來判斷有無可行解，無則階段通過構造

30、并求解人工問題來判斷有無可行解，無則結束，有則能夠獲得原問題的一個初始基本可行解；結束，有則能夠獲得原問題的一個初始基本可行解；n然后轉入第然后轉入第2階段求解原問題。階段求解原問題?！纠?-4】試用兩階段法求解例2-3中的LP問題2022年3月7日星期一山西大學經濟與管理學院 范建平35p解解 第第1階段階段 構造并求解人工問題：構造并求解人工問題：512352412345max-2-+=2. . -2+=3,0wxxxxxstxxxx x x x x注意：目標函數是脫離原目標函數而虛擬的，必須納入全部人工變量，并且其系數全都為-1；原變量的系數全部為0。 人工問題的目標函數值w0，當用單純

31、形法求解這類人工問題而最終結果為：【例2-4】試用兩階段法求解例2-3中的LP問題2022年3月7日星期一山西大學經濟與管理學院 范建平36p（1）若）若w*0,則意味著原問題無可行解，停止。則意味著原問題無可行解，停止。p（2）若）若w*=0,則意味著原問題有可行解，分以下情況：則意味著原問題有可行解，分以下情況：若基列中不存在人工變量，則直第2階段接轉入求解原問題。BlBllxnx若基列中存在人工變量，譬如第 行的基變量是人工變量，而且該行的前個變量(即原問題的變量)系數全都是0。這說明原問題的該約束與其他約束線性相關,是多余無用的,刪除所在行和列,類似情況全都刪除相應行、列。0,Bllk

32、lkkBllxnaaxx第 行的基變量是人工變量，而且該行的前個變量系數不全是0，譬如則以為主元進行一次換基運算，可以使原變量取代作基變量；類似情況全都這樣處理。2. 兩階段法37p用兩階段法求解用兩階段法求解【例例2-3】的人工問題的人工問題2345454112-8 -0000-21-10103-12010-10011 2-1 201 20405 2-1 211 20000001jcxxxxxxxxx表按兩階段法求解【例2 4】迭代單純形表1比值基解1檢驗行22第一階段11檢驗行(a)(b)*2-800,bjw在表的（ ）的所有檢驗數全都非負，意味著人工問題已獲最優解；最優值則意味著原問題有

33、可行解；基列中不可轉存在入第人工變量，二階段。2. 兩階段法p第第2階段階段 求解原問題求解原問題1123442-9 -320011 2-1 200405 2-1 2130-1 2-3 203jxxxxcxx第二階段表按兩階段法求解【例2 4】初始單純形表比值基解檢驗行132-9=-3 2LP在表的檢驗行中，存在一個負檢驗數，它所對應的系數列向量中不含正數，可確定原問題解無界。0-jjjjjccccz首先，建立原問題的初始單純型表，這可以依據第一階段的最終單純型表來構建（1） 刪除人工變量各列，清空“ 行”、“ 列”和檢驗行中一切原有數據。（2） 將原問題目標函數中的價值系數填入“ 行”、“

34、列”中。（3） 按公式（2 4）重新計算目標函數值和檢驗數，填入檢驗行中。然后，按單純形法的迭代步驟，完成后續運算工作。 構建的初始單純形表如下：【例2-5】試用單純形法求解下列LP問題2022年3月7日星期一山西大學經濟與管理學院 范建平391212212max2-. . -2,0zxxxxstxxx x1解：引入剩余變量x3、 x4，化為標準型。試用單純形法求解下列LP問題再引入人工變量x5、 x6， 按兩階段法構造并求解人工問題。121221234max2-. . -2,0 xxzxxxxstxxx x x x15612251234566max-. . -2,0wx xxxxstxxxx

35、 x x x xxxx1【例2-5】試用單純形法求解下列LP問題2022年3月7日星期一山西大學經濟與管理學院 范建平40123456562-10 -0000-11-1-1010-2-110-101-300100jcxxxxxxxx表第按兩階段法求解【例2 5】初始單純形表11比值基解一階檢驗行1段112-10= -在表的檢驗行中，所有檢驗數都非負，人工問題已獲最優解，其目標值30,判定原問題無可行解。課堂練習 1231323123min6818023. .232,0wyyyyystyyy yy*5 3, , 2 3202TYw其最優解和最優值為：2.3.2 相持規則2022年3月7日星期一山

36、西大學經濟與管理學院 范建平42p當備擇進基、離基變量相持不下時，如何選擇？當備擇進基、離基變量相持不下時，如何選擇？1min|0.(23a)jjkkkx按最小檢驗數規則確定進基變量時，若有不止一個同時最進基相持的小，則相應的哪個進基呢？此即處理規則進基相持。kx盡管不同選擇后續迭代繁簡不一，但因目前沒有簡明方法據以恰當判斷，因此，的處理規則是：在相持的諸變量任選一中，作為進進基相個持基變量。【例2-6】試用單純形法求解下列LP問題2022年3月7日星期一山西大學經濟與管理學院 范建平431212212max+. . 22,0zxxxxstxxx x1試用單純形法求解下列LP問題解：引入松弛變

37、量x3、 x4，化為標準型,已經符合典式。121221234max+. . 2+2,0 xxzxxxxstxxx x x x1用單純形法求解，在初始單純形表就出現了x1、 x2的進基相持 。任選x1進基，又出現x3、 x4的離基相持。1234342-11 -61100011101 1=021012 2=0-1-100jcxxxxxx表【例2 】的初始單純形表進基離基變量相持比值基解1檢驗行2.3.2 相持規則2022年3月7日星期一山西大學經濟與管理學院 范建平44p按此規則續解按此規則續解【例例2-6】=min|0(2.23 )ilikiklkrbbabaax按最小比值規則確定離基變量時，若

38、有不止一個比值同時最小，則相應的哪個離基呢離基相持的？此即處理規則離基相持。342-11=,x x如表中：兩個最小比值1對應的變量的離基相持，如何選擇？這是一個重要問題，因為無論如何選擇，換基運算后，必然導致一個，而這就有可能使后續的迭退代化基本可行解出現循環。rrxrx的處理規則：在相持的諸變量中,那個離基相作選下標最為離大的持基變量。【例2-6】試用單純形法求解下列LP問題p在離基相持的在離基相持的x3、 x4中，選下標大的中，選下標大的x4離基，結果如下：離基，結果如下：23434312112-12 -61100011101 1=021012 2=0-1-10001 21-1 20=11

39、11 201 2210-1 211 2112-11110-111001000jcxxxxxxxxxx表【例2 】的迭代單純形表突破離基相持退化比值基解1檢驗行0檢驗行0檢驗行(a)(b)(0) 在表（2-12a）得到以B1=a3、 a1為基的退化基本可行解及其目標值：X1=(1,0,0,0)T, z=1X1中有一個基變量x3=0,故謂之“退化”45 在表（2-12b）得到以B2=a1、 a2為基的最優基本可行解及其目標值：X*=(1,0,0,0)T, z*=1X*也是退化基本可行解2.3.2 相持規則2022年3月7日星期一山西大學經濟與管理學院 范建平46p3. 多重最優解多重最優解p求解線

40、性規劃有求解線性規劃有4種可能的結果：種可能的結果：n唯一解；多重解；解無界；無可行解。唯一解；多重解；解無界；無可行解。p其中，、都已就單純形法舉例說明，只有多重其中，、都已就單純形法舉例說明，只有多重解未做說明。解未做說明。p單純形法的單純形法的3、4兩步，分別給出兩種停止運算的規兩步，分別給出兩種停止運算的規則。最優性檢驗步驟則。最優性檢驗步驟3，在迭代表格首次出現檢驗數全，在迭代表格首次出現檢驗數全部非負時（該表格稱為部非負時（該表格稱為最優單純形表最優單純形表，簡稱，簡稱最優表最優表），），算法結束。此時，算法結束。此時，如何識別多重解如何識別多重解？2.3.2 相持規則2022年3月7日星期一山西大學經濟與管理學院 范建平47p【定理定理2-1】 多重最優解判別準則多重最優解判別準則=1LP0jjx非基變量的（） 在最優表中,有一個或更多個,則該問題有多重檢驗數最優解。2jjjxax（ ）若該的系數列向量中含有,則按單純形法另作幾次迭代，每次都選一個這樣的進基，就能得到其他最優基本解或最正數優極點；*11221LP,=+01,2,1