單純形法

迭代原理運(yùn)籌學(xué)4單純形法迭代原理三.單純形法的基本思想

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

即從可行域的一個(gè)頂點(diǎn)（基本可行解）開始，轉(zhuǎn)移到另一個(gè)頂點(diǎn)（另一個(gè)基本可行解）的迭代過程，轉(zhuǎn)移的條件是使目標(biāo)函數(shù)值得到改善（逐步變優(yōu)），當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)值時(shí)，問題也就得到了最優(yōu)解。運(yùn)籌學(xué)4單純形法迭代原理

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

于是，若某線性規(guī)劃只有唯一的一個(gè)最優(yōu)解，這個(gè)最優(yōu)解所對應(yīng)的點(diǎn)一定是可行域的一個(gè)頂點(diǎn)；若該線性規(guī)劃有多個(gè)最優(yōu)解，那么肯定在可行域的頂點(diǎn)中可以找到至少一個(gè)最優(yōu)解。頂點(diǎn)轉(zhuǎn)移的依據(jù)？運(yùn)籌學(xué)4單純形法迭代原理

轉(zhuǎn)移條件？轉(zhuǎn)移結(jié)果？使目標(biāo)函數(shù)值得到改善得到LP最優(yōu)解，目標(biāo)函數(shù)達(dá)到最優(yōu)值

2．需要解決的問題：

(1)為了使目標(biāo)函數(shù)逐步變優(yōu)，怎么轉(zhuǎn)移？

(2)目標(biāo)函數(shù)何時(shí)達(dá)到最優(yōu)——

判斷標(biāo)準(zhǔn)是什么？

運(yùn)籌學(xué)4單純形法迭代原理解LP問題單純形法的基本思路：

初始可行基：設(shè)法在約束矩陣中構(gòu)造出一個(gè)m階單位陣初始基本可行解檢驗(yàn)數(shù)進(jìn)基變量：檢驗(yàn)數(shù)離基變量：最小比值準(zhǔn)則運(yùn)籌學(xué)4單純形法迭代原理1.確定初始基本可行解

LP:？希望在化LP的標(biāo)準(zhǔn)形式時(shí)，A中都含有一個(gè)m階單位陣。運(yùn)籌學(xué)4單純形法迭代原理觀察法——觀察系數(shù)矩陣中是否含有現(xiàn)成的單位陣？LP限制條件中全部是“≤”類型的約束

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

非基變量取0，算出基變量，搭配在一起構(gòu)成初始基本可行解：運(yùn)籌學(xué)4單純形法迭代原理2.建立判別準(zhǔn)則判斷：初始基本可行解或經(jīng)過若干次迭代后得到的新基本可行解—當(dāng)前解—是否為最優(yōu)解？一般（經(jīng)過若干次迭代），對于基B，用非基變量表出基變量的表達(dá)式

為：典式若運(yùn)籌學(xué)4單純形法迭代原理用非基變量表示目標(biāo)函數(shù)的表達(dá)式：

典式檢驗(yàn)數(shù)運(yùn)籌學(xué)4單純形法迭代原理其中（1）最優(yōu)性判別定理（2）有無窮多個(gè)“最優(yōu)解”的判別定理

運(yùn)籌學(xué)4單純形法迭代原理3、進(jìn)行基變換（1）進(jìn)基變量的確定——原則：正檢驗(yàn)數(shù)（或最大正檢驗(yàn)數(shù)）所對應(yīng)的變量進(jìn)基，目的是使目標(biāo)函數(shù)得到改善。（2）離基變量的確定——在保持解的可行性的前提下，使目標(biāo)函數(shù)較快增大。運(yùn)籌學(xué)4單純形法迭代原理>

=

<當(dāng)時(shí)，為使，需要從而，最大可取到最小比值原則則該LP無最優(yōu)解。運(yùn)籌學(xué)4單純形法迭代原理離基變量：是可行解！是否還是基本解？是運(yùn)籌學(xué)4單純形法迭代原理從而，目標(biāo)函數(shù)得到了改善。運(yùn)籌學(xué)4單純形法迭代原理第四節(jié)單純形表運(yùn)籌學(xué)4單純形法迭代原理（1）建立初始單純形表，假定B=I，b≥0

設(shè)maxZ=c1x1+c2x2+…+cnxn將目標(biāo)函數(shù)改寫為：-Z+c1x1+c2x2+…+cnxn=0寫成增廣矩陣的形式

運(yùn)籌學(xué)4單純形法迭代原理-Zx1x2xmxm+1……xn右端檢驗(yàn)數(shù)行-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCB最后一行是檢驗(yàn)數(shù)行，標(biāo)出了對應(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)前基變量的名稱。第三列是右端項(xiàng)，前m個(gè)元素是當(dāng)前基本可行解的基變量的取值最小比值準(zhǔn)則運(yùn)籌學(xué)4單純形法迭代原理-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCB將初始數(shù)據(jù)填入上表，可得到初始單純形表。觀察檢驗(yàn)數(shù)行，若所有的，則停止計(jì)算。否則進(jìn)行下一步。1.檢驗(yàn)當(dāng)前基本可行解是否為最優(yōu)解？最優(yōu)性判別定理運(yùn)籌學(xué)4單純形法迭代原理2.檢驗(yàn)是否為無界解？則該LP無最優(yōu)解。3.選擇進(jìn)基變量從而xm+t是進(jìn)基變量，pm+t為進(jìn)基向量，并稱表中pm+t所在的列為主列。4.選擇離基變量最小比值準(zhǔn)則從而xl是離基變量，并稱表中離基變量所在的行為主行。5.基變換主行和主列的交叉元素稱為主元素al,m+t運(yùn)籌學(xué)4單純形法迭代原理-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.運(yùn)籌學(xué)4單純形法迭代原理-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,對新解作最優(yōu)性檢驗(yàn)。運(yùn)籌學(xué)4單純形法迭代原理例：用單純形法求解線性規(guī)劃問題解：

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

運(yùn)籌學(xué)4單純形法迭代原理建立初始單純行表[]基變換[]確定為離基變量，而為進(jìn)基變量，以為主元素。運(yùn)籌學(xué)4單純形法迭代原理基變換[][]確定為離基變量，而為進(jìn)基變量，以為主元素。運(yùn)籌學(xué)4單純形法迭代原理基變換[]確定為離基變量，而為進(jìn)基變量，以為主元素。運(yùn)籌學(xué)4單純形法迭代原理上表中檢驗(yàn)數(shù)滿足最優(yōu)性條件，得到最優(yōu)解：及最大值：運(yùn)籌學(xué)4單純形法迭代原理說明用單純形法從當(dāng)前解迭代到