運(yùn)籌學(xué)5-單純形法VIP

.,第五章單純形法,1.線性規(guī)劃問題的解2單純形法3求初始基的人工變量法,.,1.線性規(guī)劃問題的解,(1)解的基本概念,定義在線性規(guī)劃問題中，約束方程組(2)的系數(shù)矩陣A(假定)的任意一個(gè)階的非奇異(可逆)的子方陣B(即)，稱為線性規(guī)劃問題的一個(gè)基陣或基。,.,基陣,非基陣,基向量,非基向量,基變量,非基變量,.,令,則,定義在約束方程組(2)中，對于一個(gè)選定的基B，令所有的非基變量為零得到的解，稱為相應(yīng)于基B的基本解。,.,定義在基本解中，若該基本解滿足非負(fù)約束，即，則稱此基本解為基本可行解，簡稱基可行解；對應(yīng)的基B稱為可行基。,定義在線性規(guī)劃問題的一個(gè)基本可行解中，如果所有的基變量都取正值，則稱它為非退化解，如果所有的基本可行解都是非退化解。稱該問題為非退化的線性規(guī)劃問題；若基本可行解中，有基變量為零，則稱為退化解，該問題稱為退化的線性規(guī)劃問題。,基本解中最多有m個(gè)非零分量。,基本解的數(shù)目不超過個(gè)。,.,非可行解,解的集合：,可行解,基本解,最優(yōu)解,基本可行解,解空間,.,(2)解的基本性質(zhì),判別可行解為基可行解的準(zhǔn)則,定理1線性規(guī)劃問題的可行解是基可行解的充要條件是它的非零向量所對應(yīng)的列向量線性無關(guān).,線性規(guī)劃問題的基本定理:定理2和定理3,定理2線性規(guī)劃問題有可行解,則它必有基可行解.,定理3若線性規(guī)劃問題有最優(yōu)解,則一定存在一個(gè)基可行解是它的最優(yōu)解.,.,幾點(diǎn)結(jié)論,若線性規(guī)劃問題有可行解,則可行域是一個(gè)凸多邊形或凸多面體(凸集),且僅有有限個(gè)頂點(diǎn)(極點(diǎn));線性規(guī)劃問題的每一個(gè)基可行解都對應(yīng)于可行域上的一個(gè)頂點(diǎn)(極點(diǎn));若線性規(guī)劃問題有最優(yōu)解,則最優(yōu)解必可在基可行解(極點(diǎn))上達(dá)到;線性規(guī)劃問題的基可行解(極點(diǎn))的個(gè)數(shù)是有限的,不會(huì)超過個(gè).,上述結(jié)論說明:線性規(guī)劃的最優(yōu)解可通過有限次運(yùn)算在基可行解中獲得.,.,2單純形法,例1,(1)單純形法的引入,.,解：(1)、確定初始可行解,B=(P3P4P5)=I,令X1=X2=0,X(1)=(0,0,30,60,24)TZ(1)=0,.,(2)、判定解是否最優(yōu),Z=0+40X1+50X2當(dāng)X1從0或X2從0Z從0,X(1)不是最優(yōu)解,.,(3)、由一個(gè)基可行解另一個(gè)基可行解。,5040選X2從0，X1=0,X2=min(30/2,60/2,24/2)=12X2：進(jìn)基變量，X5：出基變量。,.,B2=(P3P4P2),.,1/2，代入式，,令X1=X5=0X(2)=(0,12,6,36,0)TZ(2)=600,.,(2)判斷,400X(2)不是最優(yōu)解。,(3)選X1從0，X5=0,X1=min(6/1,36/3,aik(i=1,2,m)不全小于或等于零，即至少有一個(gè)aik0(1km);bi0(I=1,2,m),即X(0)為非退化的基可行解。則從X(0)出發(fā)，一定能找到一個(gè)新的基可行解X(1)，使得CX(1)CX(0)。,.,(5)單純形表,將線性規(guī)劃問題典式中各變量及系數(shù)填寫在一張表格中，該表即為單純形表。,.,單純形方法的矩陣表示,.,對應(yīng)I式的單純形表I表(初始單純形表),對應(yīng)B式的單純形表B表,迭代,當(dāng)CN-CBB-1N0時(shí)，即為最優(yōu)單純形表,.,(1)、確定初始基域初始基本可行解,列出初始單純形表,(3)、若有j0，Pj全0，停止，沒有有限最優(yōu)解；否則轉(zhuǎn)(4),(2)、對應(yīng)于非基變量檢驗(yàn)數(shù)j全小于零。若是，停止，得到最優(yōu)解；若否，轉(zhuǎn)(3)。,(6)單純形法的迭代步驟,.,定Xr為出基變量，arm+k為主元。,由最小比值法求：,Maxj=m+kXm+k進(jìn)基變量,j0,(4)、,.,轉(zhuǎn)(2),(5)、以arm+k為中心，換基迭代,從步驟(2)-(5)的每一個(gè)循環(huán)，稱為一次單純形迭代.,.,單純形表計(jì)算步驟舉例給定線性規(guī)劃問題,.,初始基,最優(yōu)單純形表,B-1,初始基可行解,最優(yōu)值,初始單純形表,唯一最優(yōu)解,.,例2,.,.,達(dá)到最優(yōu)狀態(tài)時(shí)，若存在非基變量為零，則為有無窮多最優(yōu)解,.,例3,.,可以為零,.,例4,例5,無法獲得初始基和初始基可行解,.,3求初始基的人工變量法,求解線性規(guī)劃問題的單純形法第一步就是要找到一個(gè)初始可行基并求出初始基可行解，以它作為迭代的起點(diǎn)。獲得初始可行基及初始基可行解的途徑主要有：(1)試算法；(2)人工變量法。在約束方程組中的每一個(gè)沒有單位向量的約束方程中人為加入一個(gè)變量，使系數(shù)矩陣中湊成一個(gè)單位方陣，以形成一個(gè)初始可行基陣。,.,約束條件：a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2.am1x1+am2x2+amnxn+xn+m=bmx1，x2，xn,xn+1,xn+m0,s.t,人工變量,人工基,.,等價(jià)否？,.,大M法,兩階段法,.,大M法與二階段法的一些說明由于人工變量在原問題的解中是不能存在的，應(yīng)盡快被迭代出去，因此人工變量在目標(biāo)函數(shù)中對應(yīng)的價(jià)值系數(shù)應(yīng)具有懲罰性，稱為罰系數(shù)。大M法實(shí)質(zhì)上與原單純型法一樣，M可看成一個(gè)很大的常數(shù)人工變量被迭代出去后就不會(huì)再成為基變量當(dāng)檢驗(yàn)數(shù)都滿足最優(yōu)條件，但基變量中仍有人工變量，說明原線性規(guī)劃問題無可行解大M法手算很不方便，因此提出了二階段法計(jì)算機(jī)中常用大M法二階段法手算可能容易,.,例6,大M法,.,.,最優(yōu)解,人工變量被迭代出去后就不會(huì)再成為基變量,.,例4,.,未達(dá)到最優(yōu)狀態(tài)，但無法繼續(xù)改進(jìn)，即無有限最優(yōu)解,.,例5,已達(dá)到最優(yōu)狀態(tài)，但基變量中的人工變量未退出，故無可行解,.,例6,(2)兩階段法,.,第