運(yùn)籌學(xué)4單純形法迭代原理教學(xué)課件

單純形法

迭代原理1單純形法

迭代原理1三.單純形法的基本思想

1、頂點(diǎn)的逐步轉(zhuǎn)移即從可行域的一個(gè)頂點(diǎn)（基本可行解）開(kāi)始，轉(zhuǎn)移到另一個(gè)頂點(diǎn)（另一個(gè)基本可行解）的迭代過(guò)程，轉(zhuǎn)移的條件是使目標(biāo)函數(shù)值得到改善（逐步變優(yōu)），當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)值時(shí)，問(wèn)題也就得到了最優(yōu)解。2三.單純形法的基本思想

1、頂點(diǎn)的逐步轉(zhuǎn)移

根據(jù)線性規(guī)劃問(wèn)題的可行域是凸多邊形或凸多面體，一個(gè)線性規(guī)劃問(wèn)題有最優(yōu)解，就一定可以在可行域的頂點(diǎn)上找到。

于是，若某線性規(guī)劃只有唯一的一個(gè)最優(yōu)解，這個(gè)最優(yōu)解所對(duì)應(yīng)的點(diǎn)一定是可行域的一個(gè)頂點(diǎn)；若該線性規(guī)劃有多個(gè)最優(yōu)解，那么肯定在可行域的頂點(diǎn)中可以找到至少一個(gè)最優(yōu)解。頂點(diǎn)轉(zhuǎn)移的依據(jù)？3根據(jù)線性規(guī)劃問(wèn)題的可行域是凸多邊形或凸多面體轉(zhuǎn)移條件？轉(zhuǎn)移結(jié)果？使目標(biāo)函數(shù)值得到改善得到LP最優(yōu)解，目標(biāo)函數(shù)達(dá)到最優(yōu)值

2．需要解決的問(wèn)題：(1)為了使目標(biāo)函數(shù)逐步變優(yōu)，怎么轉(zhuǎn)移？(2)目標(biāo)函數(shù)何時(shí)達(dá)到最優(yōu)——判斷標(biāo)準(zhǔn)是什么？

4轉(zhuǎn)移條件？解LP問(wèn)題單純形法的基本思路：

初始可行基：設(shè)法在約束矩陣中構(gòu)造出一個(gè)m階單位陣初始基本可行解檢驗(yàn)數(shù)進(jìn)基變量：檢驗(yàn)數(shù)離基變量：最小比值準(zhǔn)則5解LP問(wèn)題單純形法的基本思路：初始可行基：設(shè)法在約束矩陣1.確定初始基本可行解

LP:？希望在化LP的標(biāo)準(zhǔn)形式時(shí)，A中都含有一個(gè)m階單位陣。61.確定初始基本可行解LP:？希望在化LP的標(biāo)觀察法——觀察系數(shù)矩陣中是否含有現(xiàn)成的單位陣？LP限制條件中全部是“≤”類(lèi)型的約束

——將新增的松弛變量(+)作為初始基變量，對(duì)應(yīng)的系數(shù)列向量構(gòu)成單位陣；LP限制條件有“≥”類(lèi)型的約束——左端新增剩余變量(-)后，再加上一個(gè)非負(fù)的新變量—人工變量。LP限制條件有“=”類(lèi)型的約束——直接在左端加上人工變量。7觀察法7在引入人工變量后，與原先的約束方程不完全等價(jià)，為此，需要在目標(biāo)函數(shù)上做些“修正”——大M法或兩階段法

非基變量取0，算出基變量，搭配在一起構(gòu)成初始基本可行解：8在引入人工變量后，與原先的約束方程不完全等價(jià)，為此，需要在目2.建立判別準(zhǔn)則判斷：初始基本可行解或經(jīng)過(guò)若干次迭代后得到的新基本可行解—當(dāng)前解—是否為最優(yōu)解？一般（經(jīng)過(guò)若干次迭代），對(duì)于基B，用非基變量表出基變量的表達(dá)式

為：典式若92.建立判別準(zhǔn)則判斷：初始基本可行解或經(jīng)過(guò)若干次迭代后得到的用非基變量表示目標(biāo)函數(shù)的表達(dá)式：

典式檢驗(yàn)數(shù)10用非基變量表示目標(biāo)函數(shù)的表達(dá)式：典式檢驗(yàn)數(shù)10其中（1）最優(yōu)性判別定理（2）有無(wú)窮多個(gè)“最優(yōu)解”的判別定理

11其中（1）最優(yōu)性判別定理（2）有無(wú)窮多個(gè)“最優(yōu)解”的判別定理3、進(jìn)行基變換（1）進(jìn)基變量的確定——原則：正檢驗(yàn)數(shù)（或最大正檢驗(yàn)數(shù)）所對(duì)應(yīng)的變量進(jìn)基，目的是使目標(biāo)函數(shù)得到改善。（2）離基變量的確定——在保持解的可行性的前提下，使目標(biāo)函數(shù)較快增大。123、進(jìn)行基變換（1）進(jìn)基變量的確定——原則：正檢驗(yàn)數(shù)（或最大>

=

<當(dāng)時(shí)，為使，需要從而，最大可取到最小比值原則則該LP無(wú)最優(yōu)解。13>=<當(dāng)時(shí)，為離基變量：是可行解！是否還是基本解？是14離基變量：是可行解！是否還是基本解？是14從而，目標(biāo)函數(shù)得到了改善。15從而，目標(biāo)函數(shù)得到了改善。15第四節(jié)單純形表16第四節(jié)單純形表16（1）建立初始單純形表，假定B=I，b≥0設(shè)maxZ=c1x1+c2x2+…+cnxn將目標(biāo)函數(shù)改寫(xiě)為：-Z+c1x1+c2x2+…+cnxn=0寫(xiě)成增廣矩陣的形式

17（1）建立初始單純形表，假定B=I，b≥0將目標(biāo)函數(shù)改寫(xiě)為：-Zx1x2xmxm+1……xn右端檢驗(yàn)數(shù)行-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCB最后一行是檢驗(yàn)數(shù)行，標(biāo)出了對(duì)應(yīng)決策變量xj的檢驗(yàn)數(shù)第一行是價(jià)值系數(shù)行，標(biāo)出了決策變量xj的價(jià)值系數(shù)cj第二行是標(biāo)示行，標(biāo)出了表中主體各行的含義。第一列標(biāo)出了基變量的價(jià)值系數(shù)。第二列標(biāo)出了當(dāng)前基變量的名稱(chēng)。第三列是右端項(xiàng)，前m個(gè)元素是當(dāng)前基本可行解的基變量的取值最小比值準(zhǔn)則18-Zx1x2xmxm+1……xn右端檢驗(yàn)數(shù)行-Z0-ZXBc-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCB將初始數(shù)據(jù)填入上表，可得到初始單純形表。觀察檢驗(yàn)數(shù)行，若所有的，則停止計(jì)算。否則進(jìn)行下一步。1.檢驗(yàn)當(dāng)前基本可行解是否為最優(yōu)解？最優(yōu)性判別定理19-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmc2.檢驗(yàn)是否為無(wú)界解？則該LP無(wú)最優(yōu)解。3.選擇進(jìn)基變量從而xm+t是進(jìn)基變量，pm+t為進(jìn)基向量，并稱(chēng)表中pm+t所在的列為主列。4.選擇離基變量最小比值準(zhǔn)則從而xl是離基變量，并稱(chēng)表中離基變量所在的行為主行。5.基變換主行和主列的交叉元素稱(chēng)為主元素al,m+t202.檢驗(yàn)是否為無(wú)界解？則該LP無(wú)最優(yōu)解。3.選擇進(jìn)基變量從而-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCBnmmnmmnmnmaaaaaass...0...00...1...00............0...10...0...0111,21,211,1++++mmmbxcbxcbxc:::222111clxlbl00...0al,m+1...aln[]主行同除以al,m+t,即將主元素化為1將新的主行的(-ai,m+t)倍分別加到第i行，即將主列的其他元素化為0.將新的主行的倍分別加到最后一行，即將xm+t的檢驗(yàn)數(shù)化為0.21-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmc-Z'0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCBnmmnmmnmnma'a'a'a'a'a'ss...0...00...1...00............0...10...0...0111,21,211,1++++mmmb'xcb'xcb'xc:::222111cm+txm+tb'm+t00...0a'l,m+1...a'ln''6.回到1,對(duì)新解作最優(yōu)性檢驗(yàn)。22-Z'0-ZXBcjx1x2xmxm+1……xnc1c2cm例：用單純形法求解線性規(guī)劃問(wèn)題解：

標(biāo)準(zhǔn)化：以對(duì)應(yīng)的系數(shù)列向量構(gòu)成一單位矩陣，取初始基為基變量，為非基變量。

23例：用單純形法求解線性規(guī)劃問(wèn)題解：標(biāo)準(zhǔn)化：以對(duì)應(yīng)的系數(shù)列向建立初始單純行表[]基變換[]確定為離基變量，而為進(jìn)基變量，以為主元素。24建立初始單純行表[]基變換[]確定為離基變量基變換[][]確定為離基變量，而為進(jìn)基變量，以為主元素。25基變換[][]確定為離基變量，而為進(jìn)基變基變換[]確定為離基變量，而為進(jìn)基變量，以為主元素。26基變換[]確定為離基變量，而為進(jìn)基變量，以為主元素上表中檢驗(yàn)數(shù)滿足最優(yōu)性條件，得到最優(yōu)解：及最大值：27上表中檢驗(yàn)數(shù)滿足最優(yōu)性條件，得到最優(yōu)解：及最大值：27說(shuō)明用單純形法從當(dāng)前解迭代到下一個(gè)基本可行解時(shí)，兩者之間只有一個(gè)基變量不同（從而也有一個(gè)非基變量不同），稱(chēng)兩者為相鄰的基本可行解（即相鄰的頂點(diǎn)）。28說(shuō)明28

作業(yè)P441.4分別用圖解法和單純形法求解下述線性規(guī)劃問(wèn)題。29

單純形法

迭代原理30單純形法

迭代原理1三.單純形法的基本思想

1、頂點(diǎn)的逐步轉(zhuǎn)移即從可行域的一個(gè)頂點(diǎn)（基本可行解）開(kāi)始，轉(zhuǎn)移到另一個(gè)頂點(diǎn)（另一個(gè)基本可行解）的迭代過(guò)程，轉(zhuǎn)移的條件是使目標(biāo)函數(shù)值得到改善（逐步變優(yōu)），當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)值時(shí)，問(wèn)題也就得到了最優(yōu)解。31三.單純形法的基本思想

1、頂點(diǎn)的逐步轉(zhuǎn)移

根據(jù)線性規(guī)劃問(wèn)題的可行域是凸多邊形或凸多面體，一個(gè)線性規(guī)劃問(wèn)題有最優(yōu)解，就一定可以在可行域的頂點(diǎn)上找到。

于是，若某線性規(guī)劃只有唯一的一個(gè)最優(yōu)解，這個(gè)最優(yōu)解所對(duì)應(yīng)的點(diǎn)一定是可行域的一個(gè)頂點(diǎn)；若該線性規(guī)劃有多個(gè)最優(yōu)解，那么肯定在可行域的頂點(diǎn)中可以找到至少一個(gè)最優(yōu)解。頂點(diǎn)轉(zhuǎn)移的依據(jù)？32根據(jù)線性規(guī)劃問(wèn)題的可行域是凸多邊形或凸多面體轉(zhuǎn)移條件？轉(zhuǎn)移結(jié)果？使目標(biāo)函數(shù)值得到改善得到LP最優(yōu)解，目標(biāo)函數(shù)達(dá)到最優(yōu)值

2．需要解決的問(wèn)題：(1)為了使目標(biāo)函數(shù)逐步變優(yōu)，怎么轉(zhuǎn)移？(2)目標(biāo)函數(shù)何時(shí)達(dá)到最優(yōu)——判斷標(biāo)準(zhǔn)是什么？

33轉(zhuǎn)移條件？解LP問(wèn)題單純形法的基本思路：

初始可行基：設(shè)法在約束矩陣中構(gòu)造出一個(gè)m階單位陣初始基本可行解檢驗(yàn)數(shù)進(jìn)基變量：檢驗(yàn)數(shù)離基變量：最小比值準(zhǔn)則34解LP問(wèn)題單純形法的基本思路：初始可行基：設(shè)法在約束矩陣1.確定初始基本可行解

LP:？希望在化LP的標(biāo)準(zhǔn)形式時(shí)，A中都含有一個(gè)m階單位陣。351.確定初始基本可行解LP:？希望在化LP的標(biāo)觀察法——觀察系數(shù)矩陣中是否含有現(xiàn)成的單位陣？LP限制條件中全部是“≤”類(lèi)型的約束

——將新增的松弛變量(+)作為初始基變量，對(duì)應(yīng)的系數(shù)列向量構(gòu)成單位陣；LP限制條件有“≥”類(lèi)型的約束——左端新增剩余變量(-)后，再加上一個(gè)非負(fù)的新變量—人工變量。LP限制條件有“=”類(lèi)型的約束——直接在左端加上人工變量。36觀察法7在引入人工變量后，與原先的約束方程不完全等價(jià)，為此，需要在目標(biāo)函數(shù)上做些“修正”——大M法或兩階段法

非基變量取0，算出基變量，搭配在一起構(gòu)成初始基本可行解：37在引入人工變量后，與原先的約束方程不完全等價(jià)，為此，需要在目2.建立判別準(zhǔn)則判斷：初始基本可行解或經(jīng)過(guò)若干次迭代后得到的新基本可行解—當(dāng)前解—是否為最優(yōu)解？一般（經(jīng)過(guò)若干次迭代），對(duì)于基B，用非基變量表出基變量的表達(dá)式

為：典式若382.建立判別準(zhǔn)則判斷：初始基本可行解或經(jīng)過(guò)若干次迭代后得到的用非基變量表示目標(biāo)函數(shù)的表達(dá)式：

典式檢驗(yàn)數(shù)39用非基變量表示目標(biāo)函數(shù)的表達(dá)式：典式檢驗(yàn)數(shù)10其中（1）最優(yōu)性判別定理（2）有無(wú)窮多個(gè)“最優(yōu)解”的判別定理

40其中（1）最優(yōu)性判別定理（2）有無(wú)窮多個(gè)“最優(yōu)解”的判別定理3、進(jìn)行基變換（1）進(jìn)基變量的確定——原則：正檢驗(yàn)數(shù)（或最大正檢驗(yàn)數(shù)）所對(duì)應(yīng)的變量進(jìn)基，目的是使目標(biāo)函數(shù)得到改善。（2）離基變量的確定——在保持解的可行性的前提下，使目標(biāo)函數(shù)較快增大。413、進(jìn)行基變換（1）進(jìn)基變量的確定——原則：正檢驗(yàn)數(shù)（或最大>

=

<當(dāng)時(shí)，為使，需要從而，最大可取到最小比值原則則該LP無(wú)最優(yōu)解。42>=<當(dāng)時(shí)，為離基變量：是可行解！是否還是基本解？是43離基變量：是可行解！是否還是基本解？是14從而，目標(biāo)函數(shù)得到了改善。44從而，目標(biāo)函數(shù)得到了改善。15第四節(jié)單純形表45第四節(jié)單純形表16（1）建立初始單純形表，假定B=I，b≥0設(shè)maxZ=c1x1+c2x2+…+cnxn將目標(biāo)函數(shù)改寫(xiě)為：-Z+c1x1+c2x2+…+cnxn=0寫(xiě)成增廣矩陣的形式

46（1）建立初始單純形表，假定B=I，b≥0將目標(biāo)函數(shù)改寫(xiě)為：-Zx1x2xmxm+1……xn右端檢驗(yàn)數(shù)行-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCB最后一行是檢驗(yàn)數(shù)行，標(biāo)出了對(duì)應(yīng)決策變量xj的檢驗(yàn)數(shù)第一行是價(jià)值系數(shù)行，標(biāo)出了決策變量xj的價(jià)值系數(shù)cj第二行是標(biāo)示行，標(biāo)出了表中主體各行的含義。第一列標(biāo)出了基變量的價(jià)值系數(shù)。第二列標(biāo)出了當(dāng)前基變量的名稱(chēng)。第三列是右端項(xiàng)，前m個(gè)元素是當(dāng)前基本可行解的基變量的取值最小比值準(zhǔn)則47-Zx1x2xmxm+1……xn右端檢驗(yàn)數(shù)行-Z0-ZXBc-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCB將初始數(shù)據(jù)填入上表，可得到初始單純形表。觀察檢驗(yàn)數(shù)行，若所有的，則停止計(jì)算。否則進(jìn)行下一步。1.檢驗(yàn)當(dāng)前基本可行解是否為最優(yōu)解？最優(yōu)性判別定理48-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmc2.檢驗(yàn)是否為無(wú)界解？則該LP無(wú)最優(yōu)解。3.選擇進(jìn)基變量從而xm+t是進(jìn)基變量，pm+t為進(jìn)基向量，并稱(chēng)表中pm+t所在的列為主列。4.選擇離基變量最小比值準(zhǔn)則從而xl是離基變量，并稱(chēng)表中離基變量所在的行為主行。5.基變換主行和主列的交叉元素稱(chēng)為主元素al,m+t492.檢驗(yàn)是否為無(wú)界解？則該LP無(wú)最優(yōu)解。3.選擇進(jìn)基變量從而-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCBnmmnmmnmnmaaaaaass...0...00...1...00............0...10...0...0111,21,211,1++++mmmbxcbxcbxc:::222111clxlbl00...0al,m+1...aln[]主行同除以al,m+t,即將主元素化為1將新的主行的(-ai,m+t)倍分別加到第i行，即將主列的其他元素化為0.將新的主行的倍分別加到最后一行，即將xm+t的檢驗(yàn)數(shù)化為0.50-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmc-Z'0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCBnmmnmmnmnma'a'a'a'a'a'ss...0...00...1...00............0...1