第2章 單純形法

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

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

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

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

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

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

7、大X2.1.3 進(jìn)化規(guī)程2022年3月7日星期一山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平10p3. 從當(dāng)前極點(diǎn)進(jìn)化到另一極點(diǎn)，既使目標(biāo)值上升，又保達(dá)點(diǎn)可行從當(dāng)前極點(diǎn)進(jìn)化到另一極點(diǎn)，既使目標(biāo)值上升，又保達(dá)點(diǎn)可行 12,0z00 xx由于目前均為非基變量，如果讓它們變?yōu)榛兞?，即讓其取值?變?yōu)檎龜?shù)，由是可知，就能使目標(biāo)函數(shù)值 增大。121,200kxxxk 這就需要從當(dāng)前的非基變量和選擇一個(gè)變?yōu)榛兞?，即所謂選擇“上進(jìn)路線”。kkkxxx專(zhuān)業(yè)術(shù)語(yǔ)稱(chēng)為：；或者說(shuō)選擇一個(gè)非基變量，讓選擇一個(gè)進(jìn)基變量進(jìn)基。m：在一個(gè)線性規(guī)劃中，基變量的個(gè)數(shù)恒注等于階數(shù)意.選哪個(gè)xk作為進(jìn)基變量？甲產(chǎn)品的單位利潤(rùn)為300元，乙產(chǎn)

8、品的單位利潤(rùn)為200元，所以選擇生產(chǎn)甲產(chǎn)品2.1.3 進(jìn)化規(guī)程2022年3月7日星期一山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平111345=33rmxxxxx范例的階數(shù)，有 個(gè)基變量。在確定進(jìn)基后，必須在原有的3個(gè)基變量， ，中選擇一個(gè)變?yōu)榉腔兞?。rrkrrxxxxx專(zhuān)業(yè)術(shù)語(yǔ)稱(chēng)為：選擇一個(gè)；或者說(shuō)選擇一個(gè)基變量，讓離基。即以變量替換離基1145113511340,0,6,8,18,0,0,0,0,0,0TTTTxx xxxxxx x0=上述基變量的替換意味著，要將當(dāng)前的基本可行解轉(zhuǎn)化為另一個(gè)=本解：或或基XXXX要保證新基本解的可行性。選哪個(gè)xr作為出基變量？ 要確保達(dá)點(diǎn)X1的可行性，X1的各分量除了

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

28、列陣，從而構(gòu)造成如下人工問(wèn)題：12512352412345max232-+=2. . -2+=3,0zxxMxxxxxstxxxx x x x x注意：用單純形法求解這類(lèi)人工問(wèn)題，只要最終全部人工變量都能從“基”列中替換出去，則不論在第三步（最優(yōu)解），還是第四步（解無(wú)界）結(jié)束，所得人工問(wèn)題的結(jié)果就是原問(wèn)題的結(jié)果；否則，若存在人工變量無(wú)法從“基”列中被替換出去，原問(wèn)題無(wú)可行解。1. 大M法33p用大用大M法求解法求解【例例2-3】的人工問(wèn)題的人工問(wèn)題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檢驗(yàn)行2M2MM檢驗(yàn)行M1M(a)(b)32-7b=-3 22-7bLP在表的（ ）的檢驗(yàn)行中存在一個(gè)檢驗(yàn)數(shù)，它所對(duì)應(yīng)的系數(shù)列向量中不含正數(shù)，可確定該人工問(wèn)題解無(wú)界。在表的（ ）“基”列中不存在人工變量，故原問(wèn)題也為無(wú)界。注意：一旦一個(gè)人工變量離基，即可刪除該列。大M法不便于計(jì)算機(jī)編程；編程時(shí)往往采用兩階段法。2. 兩階段法2022年3月7日星期一山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平34p該法把問(wèn)題的求解分為該法把問(wèn)題的求解分為兩個(gè)階段兩個(gè)階段：n第第1階段通過(guò)構(gòu)造并求解人工問(wèn)題來(lái)判斷有無(wú)可行解，無(wú)則階段通過(guò)構(gòu)造

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

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

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

33、可行解；基列中不可轉(zhuǎn)存在入第人工變量，二階段。2. 兩階段法p第第2階段階段 求解原問(wèn)題求解原問(wèn)題1123442-9 -320011 2-1 200405 2-1 2130-1 2-3 203jxxxxcxx第二階段表按兩階段法求解【例2 4】初始單純形表比值基解檢驗(yàn)行132-9=-3 2LP在表的檢驗(yàn)行中，存在一個(gè)負(fù)檢驗(yàn)數(shù)，它所對(duì)應(yīng)的系數(shù)列向量中不含正數(shù)，可確定原問(wèn)題解無(wú)界。0-jjjjjccccz首先，建立原問(wèn)題的初始單純型表，這可以依據(jù)第一階段的最終單純型表來(lái)構(gòu)建（1） 刪除人工變量各列，清空“ 行”、“ 列”和檢驗(yàn)行中一切原有數(shù)據(jù)。（2） 將原問(wèn)題目標(biāo)函數(shù)中的價(jià)值系數(shù)填入“ 行”、“

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

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

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

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

38、有不止一個(gè)比值同時(shí)最小，則相應(yīng)的哪個(gè)離基呢離基相持的？此即處理規(guī)則離基相持。342-11=,x x如表中：兩個(gè)最小比值1對(duì)應(yīng)的變量的離基相持，如何選擇？這是一個(gè)重要問(wèn)題，因?yàn)闊o(wú)論如何選擇，換基運(yùn)算后，必然導(dǎo)致一個(gè)，而這就有可能使后續(xù)的迭退代化基本可行解出現(xiàn)循環(huán)。rrxrx的處理規(guī)則：在相持的諸變量中,那個(gè)離基相作選下標(biāo)最為離大的持基變量?！纠?-6】試用單純形法求解下列LP問(wèn)題p在離基相持的在離基相持的x3、 x4中，選下標(biāo)大的中，選下標(biāo)大的x4離基，結(jié)果如下：離基，結(jié)果如下：23434312112-12 -61100011101 1=021012 2=0-1-10001 21-1 20=11

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

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