【正文】 運(yùn)籌學(xué) Operations Research 吳清烈 東南大學(xué)經(jīng)濟(jì)管理學(xué)院 電子商務(wù)系暨管理工程研究所 02583795358, 13337835398, 線性規(guī)劃的圖解法與單純形解法 ? 線性規(guī)劃問題的圖解法 ? 線性規(guī)劃單純形解法的原理 ? 線性規(guī)劃單純形解法的計(jì)算步驟 ? 單純形法計(jì)算的矩陣描述 ? 線性規(guī)劃單純形求解的大 M法 ? 線性規(guī)劃單純形求解的兩階段法 ? 線性規(guī)劃單純形求解可能的循環(huán)現(xiàn)象 ? 線性規(guī)劃單純形法的改進(jìn) 線性規(guī)劃問題的圖解法 ? 圖解法，就是用作圖的方法求解線性規(guī)劃問題。 ? 簡(jiǎn)單、直觀的圖解法一般只適用于具有兩個(gè)決策變量的線性規(guī)劃問題。 ? 用圖解法求解實(shí)際線性規(guī)劃問題，一般按照如下基本步驟： Step1 畫直坐標(biāo)系； Step2 根據(jù)約束條件畫出可行域； Step3 畫過坐標(biāo)原點(diǎn)的目標(biāo)函數(shù)線； Step4 確定目標(biāo)函數(shù)值的增大方向 (目標(biāo)函數(shù)線法線方向 ) Step5 目標(biāo)函數(shù)線沿著增大方向平行移動(dòng)，與可行域相交且有最大目標(biāo)函數(shù)值的頂點(diǎn)，即為線性規(guī)劃問題的最優(yōu)解 。 線性規(guī)劃問題的圖解法舉例 max z =2 x1+x2 3x1+x2 ≤12 x1+x2 ≤5 x2 ≤3 x1， x2 ≥0 1 2 3 4 5 1 2 3 4 x2x1Q13 x1+ x2= 1 2 x1+ x2= 5Q2 ( 3 . 5 , 1 . 5 )目 標(biāo) 函 數(shù) 線 z = 0 可 行 域 為O Q1 Q2 Q3 Q4x2 = 3Q4 Q3 ON線性規(guī)劃問題求解的幾種可能結(jié)局 ? 存在唯一最優(yōu)解。如上例。 ? 存在無窮多個(gè)最優(yōu)解。 如在上例中，將目標(biāo)函數(shù)改為 max z=3x1+x2,這時(shí) Q1 與 Q2以及 Q1 與 Q2之間的所有點(diǎn)均為最優(yōu)解 。 ? 存在無界解（有可行解但無有界最優(yōu)解） 。 如在上例中，只含有 x2 ≤3一個(gè)約束，可行域?yàn)闊o界， z的取值可無窮大。 ? 無解或無可行解。如下述線性規(guī)劃問題 max z=2 x1+x2 x1+x2≤2 x1+x2≥5 x1， x2≥0， 約束條件矛盾，因而無可行解。 由圖解法得到的啟示 ? 線性規(guī)劃問題求解的基本依據(jù)是：線性規(guī)劃問題的最優(yōu)解總可在可行域的頂點(diǎn)中尋找。尋找線性規(guī)劃問題的最優(yōu)解只需比較有限個(gè)頂點(diǎn)處的目標(biāo)函數(shù)值。 ? 線性規(guī)劃問題求解時(shí)可能出現(xiàn)四種結(jié)局：唯一最優(yōu)解、無窮多個(gè)最優(yōu)解、無有界解、無解或無可行解。 ? 如果某一線性規(guī)劃問題有最優(yōu)解，我們可以按照這樣的思路來求解：先找可行域中的一個(gè)頂點(diǎn)，計(jì)算頂點(diǎn)處的目標(biāo)函數(shù)值，然后判別是否有其它頂點(diǎn)處的目標(biāo)函數(shù)值比這個(gè)頂點(diǎn)處的目標(biāo)函數(shù)值更大，如有，轉(zhuǎn)到新的頂點(diǎn)，重復(fù)上述過程，直到找不到使目標(biāo)函數(shù)值更大的新頂點(diǎn)為止。 線性規(guī)劃單純形解法的原理 ? 單純形方法的基本思想 從可行域中的一個(gè)基可行解出發(fā)，判別它是否已經(jīng)是最優(yōu)解，如不是，尋找下一個(gè)基可行解，并且同時(shí)努力使目標(biāo)函數(shù)得到改進(jìn)，如此迭代下去，直到找到最優(yōu)解或判定問題無解為止。 ? 單純形算法必須解決三個(gè)方面的問題： 1. 如何確定初始的基可行解？ 2. 如何進(jìn)行解的最優(yōu)性判別？ 3. 如何尋找改進(jìn)的基可行解？ 確定初始的基可行解 ? 標(biāo)準(zhǔn)型的線性規(guī)劃問題 ??????????0m a x1XbxPCXznjjj???????????????100000100001),( 21????? mPPP系數(shù)矩陣中存在一個(gè)單位陣 以單位陣為一初始可行基。令非基變量取值為零，便得到一基可行解。 最優(yōu)性檢驗(yàn)和解的判別 對(duì)標(biāo)準(zhǔn)型的一般線性規(guī)劃問題，經(jīng)過變換、迭代總可將線性規(guī)劃約束條件中非基變量移至。方程右邊，得如下形式： 11 , 2 , ,ni i i j jjmx b a x i m????? ? ??最優(yōu)性檢驗(yàn)和解的判別 將上式代入目標(biāo)函數(shù)式中，整理得 jnmjmiijijmiii xaccbcz )(1 11? ???? ???????????miii bcz10 nmjaczmiijij ,1,1????? ??令 jnmjjj xzczz )(10 ??????最優(yōu)性檢驗(yàn)和解的判別 nmjzc jjj ,1 ??????再令 01njjjmz z x????? ?稱為檢驗(yàn)數(shù) 。 在線性規(guī)劃模型中，可以用檢驗(yàn)數(shù) 替代目標(biāo)函數(shù)中的價(jià)值系數(shù) cj。 j?最優(yōu)解的判別定理 ? 定理 1 最優(yōu)解的判別定理 若 ? ? T( 0 )12 , , , , 0 , , 0mX b b b? ? ??為對(duì)應(yīng)于基 B 的一個(gè)基可行解，對(duì)于一切 j = m +1 , … , n , 有檢驗(yàn)數(shù) ? j≤ 0, 則 X ( 0 ) 為最優(yōu)解。 ? 定理 2 有無窮多最優(yōu)解的判別定理 若 ? ? T( 0 ) 12 , , , , 0 , , 0mX b b b? ? ??為對(duì)應(yīng)于基 B 的一個(gè)基可行解，對(duì)于一切 j = m +1, … , n , 有檢驗(yàn)數(shù) ? j ≤ 0, 且存在某個(gè)非基變量對(duì)應(yīng)的檢驗(yàn)數(shù) ? m + k =0, 則該線性規(guī)劃問題有無窮多個(gè)最優(yōu)解。 最優(yōu)解的判別定理 ? 定理 3 有 無界解的判別定理 若? ? T( 0 ) 12 , , , , 0 , , 0mX b b b? ? ??為對(duì)應(yīng)于基 B 的一個(gè)基可行解，存在某個(gè)非基變量對(duì)應(yīng)的檢驗(yàn)數(shù) ? m + k 0, 并且對(duì)應(yīng)的變量系數(shù),i m ka ??≤ 0 ， i = 1,2, , … , m , 則該線性規(guī)劃問題有無界解（或無有界最優(yōu)解）。 尋找改進(jìn)的基可行解 ? 當(dāng)檢驗(yàn)?zāi)硞€(gè)基可行解不是最優(yōu)、也非無界，那么就應(yīng)該從該頂點(diǎn)（基可行解）處出發(fā)，尋找一個(gè)新的能使目標(biāo)函數(shù)值改進(jìn)的相鄰頂點(diǎn)（基可行解）。 注： 稱兩個(gè)基可行解為相鄰的，是指它們之間變換且僅變換一個(gè)基變量。 ? 具體的方法是：在基變量中，選出一個(gè)，讓它變?yōu)榉腔兞浚煌瑫r(shí)，從非基變量中，選出一個(gè)，讓它變?yōu)榛兞浚瑥亩鴺?gòu)造一個(gè)新基。 ? 我們希望：每變換一次，就得到一個(gè)新的基可行解，并且是盡可能使目標(biāo)函數(shù)值改進(jìn)的基可行解。 換入變量的確定 jnmjj xzz ?????10 ?如果存在多個(gè) σj 0, 則取 0,?? km? 假定存在一個(gè) 我們?nèi)? kmx ?為換入變量。 ? ?0|max ??? jjjkm???換出變量的確定 設(shè)換入新基的變量mkx ?取值 ?? ( ?? ≥ 0) , 其余的非基變量仍取值為 0 。 令 ( 1 )( 1 )( 1 ),0 ( 1 , , , )1 , 2 ,mkji i i m kxx j m n j m kx b a i m?????? ? ? ? ???? ? ?但 T( 1 ) ( 1 ) ( 1 ( 1 ) ( 1 ) ( 1 )12 , , , , 0 , , 0 , , 0 , , 0l m m kX x x x x x ???? ??） ， ， 新解必須滿足非負(fù)約束，從而必須 (1), 0 , 1 , 2 ,i i i m kx b a i m????? ? ?≥ 換出變量的確定 就必須要求,0, ?? ? kmia 0, ???? ? ?kmii ab若 kmiiab????,?從而必須有：，取kmllkmiia ababkmi ???? ????????????????? ,0m i n m i n,? )1(,m i n kmkmll xab???? ??? ??令0,)1( ?????????kmllkmlll ababx于是有我們選 lx為換出變量。 lx尋找改進(jìn)的基可行解 ? 可以證明 ( x1, x2,…, xl1, xl+1, …, xm, xm+k)所對(duì)應(yīng)的 m個(gè)列向量 P1, P2,…, Pl1, Pl+1, …, Pm, Pm+k線性無關(guān)，因而B=(P1, P2,…, Pl1, Pl+1, …, Pm, Pm+k)是一個(gè)新基。 ? 最佳換入換出變量確定 ????????????