第一章緒論線性規(guī)劃與單純形法

運(yùn)籌學(xué)OperationsResearch夫運(yùn)籌帷幄之中，決勝千里之外?！斑\(yùn)籌學(xué)是一門應(yīng)用于管理有組織系統(tǒng)的科學(xué)”，“運(yùn)籌學(xué)為掌管這類系統(tǒng)的人提供決策目標(biāo)和數(shù)量分析的工具”?！洞笥倏迫珪?shū)》運(yùn)籌學(xué)“用數(shù)學(xué)方法研究經(jīng)濟(jì)、民政和國(guó)防等部門在內(nèi)外環(huán)境的約束條件下合理分配人力、物力、財(cái)力等資源，使實(shí)際系統(tǒng)有效運(yùn)行的技術(shù)科學(xué)，它可以用來(lái)預(yù)測(cè)發(fā)展趨勢(shì)，制定行動(dòng)規(guī)劃或優(yōu)選可行方案”——《中國(guó)大百科全書(shū)》運(yùn)籌學(xué)定義運(yùn)籌學(xué)“主要研究經(jīng)濟(jì)活動(dòng)與軍事活動(dòng)中能用數(shù)量來(lái)表達(dá)有關(guān)運(yùn)用、籌劃與管理方面的問(wèn)題，它根據(jù)問(wèn)題的要求，通過(guò)數(shù)學(xué)的分析與運(yùn)算，作出綜合性的合理安排，以達(dá)到較經(jīng)濟(jì)較有效地使用人力物力”——《辭海》運(yùn)籌學(xué)“應(yīng)用分析、試驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中人、財(cái)、物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理”?！吨袊?guó)企業(yè)管理百科全書(shū)》運(yùn)籌學(xué)定義運(yùn)籌學(xué)所研究的，通常是在必須分配稀缺資源的條件下，科學(xué)地決定如何最佳地設(shè)計(jì)和運(yùn)營(yíng)人—機(jī)系統(tǒng)。對(duì)象：人—機(jī)系統(tǒng)條件：資源稀缺方法：模型化，定量化特點(diǎn)：最優(yōu)化目的：決策支持運(yùn)籌學(xué)定義運(yùn)籌學(xué)簡(jiǎn)史起源：古代戰(zhàn)爭(zhēng)、娛樂(lè)、建設(shè)田忌賽馬丁渭修皇宮學(xué)科產(chǎn)生：第二次世界大戰(zhàn)問(wèn)題：合理利用稀缺戰(zhàn)爭(zhēng)資源保護(hù)自己、消滅敵人1938年7月，波得塞雷達(dá)站的負(fù)責(zé)人羅伊用OperationalResearch命名防空作戰(zhàn)系統(tǒng)運(yùn)行的研究1940年9月英國(guó)成立了由物理學(xué)家布萊克特(Blackett)領(lǐng)導(dǎo)的第一個(gè)運(yùn)籌學(xué)小組l942年美國(guó)和加拿大也都相繼成立運(yùn)籌學(xué)小組運(yùn)籌學(xué)簡(jiǎn)史反潛艇戰(zhàn)庫(kù)普曼(Koopmans)——搜索論肖克萊(Shockley)對(duì)策論商船編隊(duì)和艦隊(duì)護(hù)航擴(kuò)展：戰(zhàn)后用于民用事業(yè)成型：各個(gè)分支成熟成熟：計(jì)算機(jī)、信息技術(shù)結(jié)合發(fā)展：學(xué)科結(jié)合、滲透應(yīng)用廣度和深度、方法和算法的完善運(yùn)籌學(xué)模型特點(diǎn)：系統(tǒng)的整體觀念多學(xué)科的綜合模型方法的應(yīng)用符號(hào)語(yǔ)言、便于交流事前分析、減少失誤抽象反映實(shí)際、突出共性優(yōu)點(diǎn)：確定目標(biāo)，明確約束抓主要矛盾、舍次要矛盾選擇模型、設(shè)定變量描述約束和目標(biāo)、確定參數(shù)選擇求解方法、求解問(wèn)題靈敏度分析、評(píng)價(jià)匯總、解釋結(jié)果、報(bào)告

運(yùn)籌學(xué)方法論提出問(wèn)題建立模型求解、優(yōu)化測(cè)試、控制方案實(shí)施學(xué)科主要分支規(guī)劃理論線性規(guī)劃非線性規(guī)劃運(yùn)輸問(wèn)題整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃目標(biāo)規(guī)劃圖論與網(wǎng)絡(luò)理論排隊(duì)論存儲(chǔ)論決策論對(duì)策論沖突分析可靠性理論計(jì)劃協(xié)調(diào)技術(shù)圖解協(xié)調(diào)技術(shù)國(guó)內(nèi)教學(xué)中常用的求解運(yùn)籌學(xué)模型的軟件LINDOWinQSBExcel對(duì)于大型復(fù)雜的數(shù)學(xué)模型，通常先要使用一個(gè)建模系統(tǒng)有效表達(dá)數(shù)學(xué)模型并將其輸入計(jì)算機(jī)AMPLMPLOPLGAMSLINGO運(yùn)籌學(xué)算法與主要應(yīng)用軟件第一章線性規(guī)劃及單純形法線性規(guī)劃及單純形法線性規(guī)劃問(wèn)題及數(shù)學(xué)模型圖解法單純形法原理單純形法計(jì)算步驟單純形法進(jìn)一步討論數(shù)據(jù)包絡(luò)分析其他應(yīng)用例子§1線性規(guī)劃問(wèn)題問(wèn)題的提出線性規(guī)劃問(wèn)題的數(shù)學(xué)模型線性規(guī)劃概念和模型問(wèn)題的提出例1美佳公司計(jì)劃制造Ⅰ、Ⅱ兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)備A，B的臺(tái)時(shí)、調(diào)試工序時(shí)間及每天可用于這兩種家電的能力、各售出一件時(shí)的獲利情況，如表所示。問(wèn)該公司應(yīng)制造兩種家電各多少件，使獲取的利潤(rùn)為最大。數(shù)學(xué)模型例1中先用變量x1和x2分別表示美佳公司制造家電Ⅰ和Ⅱ的數(shù)量。這時(shí)該公司可獲取的利潤(rùn)為(2x1+x2)元，令z=2x1+x2，因問(wèn)題中要求獲取的利潤(rùn)為最大，即maxz。z是該公司能獲取的利潤(rùn)的目標(biāo)值，它是變量x1，x2的函數(shù)，稱為目標(biāo)函數(shù)。x1，x2的取值受到設(shè)備A、B和調(diào)試工序能力的限制，用于描述限制條件的數(shù)學(xué)表達(dá)式稱為約束條件。由此例1的數(shù)學(xué)模型可表為：數(shù)學(xué)模型(1.1c)目標(biāo)函數(shù)約束條件(1.1a)(1.1b)(1.1d)max:maximize的縮寫(xiě)，“最大化”，s.t.

subjectto的縮寫(xiě)，“受限制于……”問(wèn)題的提出例2

捷運(yùn)公司在下一年度的1~4月的4個(gè)月內(nèi)擬租用倉(cāng)庫(kù)堆放物資。已知各月份所需倉(cāng)庫(kù)面積列于表1-2。倉(cāng)庫(kù)租借費(fèi)用隨合同期而定，期限越長(zhǎng)，折扣越大，具體數(shù)字見(jiàn)表1-3。租借倉(cāng)庫(kù)的合同每月初都可辦理，每份合同具體規(guī)定租用面積和期限。因此該廠可根據(jù)需要，在任何一個(gè)月初辦理租借合同。每次辦理時(shí)可簽一份合同，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所付租借費(fèi)用最小。表1-2單位：100m2表1-3單位：元/100m2數(shù)學(xué)模型例2中若用變量xij表示捷運(yùn)公司在第i(i=1,…,4)個(gè)月初簽訂的租借期為j(j=1,…,4)個(gè)月的倉(cāng)庫(kù)面積的合同。因5月份起該公司不需要租借倉(cāng)庫(kù)，故x24，x33，x34，x42，x43，x44均為零。該公司希望總的租借費(fèi)用為最小，故有如下數(shù)學(xué)模型：目標(biāo)函數(shù)約束條件s.t.min：minimize，“最小化”概念和模型定義：對(duì)于求取一組變量xj(j=1,2,…..,n)，使之既滿足線性約束條件，又使具有線性的目標(biāo)函數(shù)取得極值的一類最優(yōu)化問(wèn)題稱為線性規(guī)劃問(wèn)題。概念和模型一般形式：max（或min）

目標(biāo)函數(shù)約束條件非負(fù)約束稱為決策變量

稱為價(jià)值系數(shù)或目標(biāo)函數(shù)系數(shù)

稱為資源常數(shù)或約束右端常數(shù)稱為技術(shù)系數(shù)或約束系數(shù)

概念和模型緊縮形式：max（或min）

概念和模型矩陣形式：max（或min）

稱為決策變量向量

稱為價(jià)值系數(shù)向量或目標(biāo)函數(shù)系數(shù)向量

稱為資源常數(shù)向量或約束右端常數(shù)向量稱為技術(shù)系數(shù)或約束系數(shù)矩陣

標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)型的主要特征：①目標(biāo)最大；②約束等式；③變量非負(fù)；④右端非負(fù)。標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型的緊縮形式：標(biāo)準(zhǔn)型的矩陣形式：標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型的向量形式：其中：標(biāo)準(zhǔn)化把一般的LP化成標(biāo)準(zhǔn)型的過(guò)程稱為線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)化方法：1目標(biāo)標(biāo)準(zhǔn)化

minZ

等價(jià)于max(-Z)maxZ’=-∑cjxj2化約束為等式加松弛變量、減剩余變量3變量非負(fù)化做變換或4右端非負(fù)標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化舉例（例3）：線性規(guī)劃及單純形法線性規(guī)劃問(wèn)題及數(shù)學(xué)模型圖解法單純形法原理單純形法計(jì)算步驟單純形法進(jìn)一步討論數(shù)據(jù)包絡(luò)分析其他應(yīng)用例子§2圖解法1．什麼是圖解法？線性規(guī)劃的圖解法就是用幾何作圖的方法分析并求出其最優(yōu)解的過(guò)程。求解的思路是：先將約束條件加以圖解，求得滿足約束條件的解的集合（即可行域），然后結(jié)合目標(biāo)函數(shù)的要求從可行域中找出最優(yōu)解。圖解法2.圖解法(例1)運(yùn)用圖解法，以求出最優(yōu)生產(chǎn)計(jì)劃（最優(yōu)解）。

(1.1c)(1.1a)(1.1b)(1.1d)圖解法

由于線性規(guī)劃模型中只有兩個(gè)決策變量，因此只需建立平面直角坐標(biāo)系就可以進(jìn)行圖解了。

1.建立平面直角坐標(biāo)系，標(biāo)出坐標(biāo)原點(diǎn),坐標(biāo)軸的指向和單位長(zhǎng)度。2.對(duì)約束條件加以圖解，找出可行域。3.畫(huà)出目標(biāo)函數(shù)等值線。4.結(jié)合目標(biāo)函數(shù)的要求求出最優(yōu)解。圖

解

法(1.1c)(1.1a)(1.1b)(1.1d)圖解法 (a)可行域有界(b)可行域有界 (c)可行域無(wú)界 唯一最優(yōu)解 多個(gè)最優(yōu)解

唯一最優(yōu)解(d)可行域無(wú)界

(e)可行域無(wú)界

(f)可行域?yàn)榭占?多個(gè)最優(yōu)解

目標(biāo)函數(shù)無(wú)界

無(wú)可行解線性規(guī)劃及單純形法線性規(guī)劃問(wèn)題及數(shù)學(xué)模型圖解法單純形法原理單純形法計(jì)算步驟單純形法進(jìn)一步討論數(shù)據(jù)包絡(luò)分析其他應(yīng)用例子§3單純形法原理線性規(guī)劃問(wèn)題的解的概念凸集及其頂點(diǎn)幾個(gè)基本定理解

的

概

念可行解：變量滿足所有約束條件的一組值可行解集：所有可行解構(gòu)成的集合可行域：可行解集構(gòu)成n維空間的區(qū)域線性規(guī)劃問(wèn)題解的概念最優(yōu)解：使得目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解最優(yōu)值：最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值目的：求最優(yōu)解和最優(yōu)值求解方法：?jiǎn)渭冃畏ń獾母拍钕妊芯緼X=b設(shè)系數(shù)矩陣A是m×n矩陣，秩為m，B是A中m×m階非奇異子矩陣（即|B|≠0），則稱B是線性規(guī)劃問(wèn)題的一個(gè)基。B是由m個(gè)線性獨(dú)立的列向量組成基向量基變量非基變量：其余變量解的概念A(yù)X=BXB+NXN=b令非基變量XN=0得BXB=b和特解XB=B-1b結(jié)合XN=0

稱為對(duì)應(yīng)于B的基本解；基本解個(gè)數(shù)=基的個(gè)數(shù)≤Cnm基可行解可行的基本解

XB≥0XN=0可行基：對(duì)應(yīng)于基可行解的基A=（B|N）解的概念最優(yōu)基：對(duì)應(yīng)的基本可行解也是最優(yōu).基本可行解個(gè)數(shù)≤基的個(gè)數(shù)≤Cnm基本可行解的非零分量均為正分量，其正分量個(gè)數(shù)≤m。退化的基本可行解：基本可行解的非零分量個(gè)數(shù)小于m時(shí)，也就是在基本可行解中一個(gè)或多于一個(gè)的基變量取零值時(shí)凸

集

及

其

頂

點(diǎn)1、基本概念：

凸集——設(shè)K是n維歐氏空間的一個(gè)點(diǎn)集，若任意兩點(diǎn)X（1）∈K，X（2）∈K的連線上的一切點(diǎn)：

αX（1）+（1-α）X（2）∈

K（0<α<1），則稱K為凸集。凸

集

的

概

念頂點(diǎn)設(shè)K是凸集，XK；若K中不存在兩個(gè)不同的點(diǎn)X（1）

K，X（2）

K使

X=αX（1）+（1-α）X（2）（0<α<1）則稱X為K的一個(gè)頂點(diǎn)（也稱為極點(diǎn)或角點(diǎn)）。凸

集

的

概

念凸集凸集不是凸集頂點(diǎn)基

本

定

理若線性規(guī)劃問(wèn)題有最優(yōu)解，一定存在一個(gè)基可行解（可行域頂點(diǎn)）是最優(yōu)解。定理1引理定理2定理3若線性規(guī)劃問(wèn)題存在可行解，則該問(wèn)題的可行解集（即可行域）是凸集。線性規(guī)劃問(wèn)題的可行解x＝(x1,x2,…,xn)為基可行解的充要條件是x的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。線性規(guī)劃問(wèn)題的基可行解x對(duì)應(yīng)線性規(guī)劃問(wèn)題可行域(凸集)的頂點(diǎn)解的幾何意義猜想1線性規(guī)劃的可行域是凸集；猜想2最優(yōu)解若存在，則可以在可行域的頂點(diǎn)上得到；猜想3可行域的頂點(diǎn)的個(gè)數(shù)是有限的；猜想4若有兩個(gè)最優(yōu)解，則其連線上的點(diǎn)也是最優(yōu)解，即最優(yōu)解有無(wú)窮多個(gè)猜想5

對(duì)于標(biāo)準(zhǔn)型的線性規(guī)劃X是可行域頂點(diǎn)的充分必要條件是X是基本可行解。求解思路

求一個(gè)初始基本可行解

是

判斷基本可行解是否最優(yōu)結(jié)束

不是

求使目標(biāo)得到改善的基本可行解

是否存在？如何得到？是否唯一？如何判斷？如何改善？如何判斷沒(méi)有有限最優(yōu)解？線性規(guī)劃及單純形法線性規(guī)劃問(wèn)題及數(shù)學(xué)模型圖解法單純形法原理單純形法計(jì)算步驟單純形法進(jìn)一步討論數(shù)據(jù)包絡(luò)分析其他應(yīng)用例子§4單純形法迭代原理單純形方法引例單純形法的一般描述表格單純形法一般問(wèn)題的處理單純形法矩陣描述幾點(diǎn)注意事項(xiàng)單純形方法引例用單純形法的思想求解線性規(guī)劃問(wèn)題：?jiǎn)渭冃畏椒ㄒ窘猓?，0，0，3，9）也是可行的.

單純形方法引例初始基本可行解X(0)=（0，0，0，3，9）含義：不生產(chǎn)任何產(chǎn)品，工時(shí)剩余為3，材料剩余為9，利潤(rùn)為Z(0)=0

初始基本可行解是否最優(yōu)解?是否可以生產(chǎn)某種產(chǎn)品使目標(biāo)提高？當(dāng)x1（或x2,x3）增加一個(gè)單位時(shí)，會(huì)使目標(biāo)增加2（或3）單位

單純形方法引例初始基本可行解X(0)=（0，0，0，3，9）當(dāng)x1（或x2,x3）增加一個(gè)單位時(shí)，會(huì)使目標(biāo)增加2（或3）單位考慮將x1（或x2,x3）并為非零變量，x2,x3價(jià)值系數(shù)加大，將x2變?yōu)榛兞俊胱兞?。單純形方法引例初始基本可行解X(0)=（0，0，0，3，9）當(dāng)x2作為引入變量，為使新解X(1)仍為基可行解，必須使且使x4或x5中有一個(gè)等于零——退出變量（1-1）單純形方法引例由(1-1)第四、第五式，得為使新解X(1)為基可行解此時(shí)，變?yōu)榱?，x5為退出變量新的基可行解為X(1)=(0,9/4,0,3/4,0)目標(biāo)函數(shù)值Z(1)=27/4>Z(0)單純形方法引例系數(shù)列向量此時(shí)，進(jìn)一步分析引入x1或x3是否會(huì)更好？引入哪一個(gè)更好？單純形方法引例首先考慮引入x1，由于計(jì)算增加單位x1所創(chuàng)增的凈經(jīng)濟(jì)價(jià)值同理，可計(jì)算增加單位x3所創(chuàng)增的凈經(jīng)濟(jì)價(jià)值檢驗(yàn)數(shù)單純形方法引例基本可行解X(1)=(0,9/4,0,3/4,0)取x1進(jìn)基，同樣，此時(shí)，為x4退出變量。新的基可行解為X(2)=(1,2,0,0,0)目標(biāo)函數(shù)Z(2)=2+6=8>27/4=Z(0)此時(shí)非基變量檢驗(yàn)數(shù)均為負(fù)，解最優(yōu)單純形法一般步驟1.初始基本可行解的確定（觀察法）；單純形法一般步驟1.初始基本可行解的確定（觀察法）；基基本可行解單純形法一般步驟2.從約束中解出基變量；單純形法一般步驟3.代入目標(biāo)消去基變量，得到非基變量xj的檢驗(yàn)數(shù)

j；單純形法一般步驟3.代入目標(biāo)消去基變量，得到非基變量xj的檢驗(yàn)數(shù)

j；單純形法一般步驟4.判斷最優(yōu)；最優(yōu)性判別定理：若是對(duì)應(yīng)于B的基本可行解，j是用非基變量表示目標(biāo)函數(shù)的表達(dá)式中非基變量xj的檢驗(yàn)數(shù)，若對(duì)于一切非基變量的角指數(shù)j均有j≤0則當(dāng)前基本可行解為最優(yōu)解。對(duì)于任意可行解X，對(duì)于基本可行解X0，單純形法一般步驟5.沒(méi)有有限最優(yōu)解的判斷；無(wú)最優(yōu)解判別定理：若是對(duì)應(yīng)于B的基本可行解，非基變量xk的檢驗(yàn)數(shù)k>0,且對(duì)于i=1,2,……,m均有aik≤0,則問(wèn)題沒(méi)有有限最優(yōu)解。單純形法一般步驟6.改進(jìn)目標(biāo)若k>0，則選xk進(jìn)基;用最小比值法確定xk的最大值θ，使基變量xl取0值，其它基變量非負(fù)；即xl出基，目標(biāo)改善kθ，換基過(guò)程若θ不存在,則Z→∞，沒(méi)有有限最優(yōu)解。單純形法一般步驟7.主元變換（樞變換或旋轉(zhuǎn)變換）xk進(jìn)基，xl出基，解出新的基變量表格單純形法表格單純形法表格單純形法基變量檢驗(yàn)數(shù)最小比值列基變量系數(shù)右端常數(shù)CB基

cj21000bx1x2x3x4x50x315051000x424620100x5511001cj-zj21000解：表1-701/602/614x120-1/301/30cj-zj1-1/604/601x500015015x30x5x4x3x2x1b00012

cj基CB表1-8-1/21/40017/2x12-1/2-1/4000cj-zj3/2-1/40103/2x21-15/25/410015/2x30x5x4x3x2x1b00012

cj基CB表1-9表1-9中所有j<=0,且基變量中不含人工變量，最優(yōu)解X=(7/2,3/2,15/2,0,0);最優(yōu)值Z=17/2.練習(xí)1：求解線性規(guī)劃CB

XB

cj25000

xj

bx1x2x3x4x50x34111004/10x42-12010∞0x521-10012/1cj-zj０25０００表格單純形法CB

XB

cj25000

xj

bx1x2x3x4x50x34111004/10x42-12010∞0x521-10012/1cj-zj0250002x121-1001∞0x320210-12/20x44010114/1cj-zj-40700-2向右迭代一步練習(xí)2：求解線性規(guī)劃CB

XB

cj1200

xj

bx1x2x3x40x301-2100x431001－Ｚ０12００表格單純形法沒(méi)有有限最優(yōu)解算法思路

求一個(gè)初始基本可行解

是

判斷基本可行解是否最優(yōu)

結(jié)束

不是

求使目標(biāo)得到改善的基本可行解

是否存在？如何得到？是否唯一？如何判斷？如何改善？如何判斷沒(méi)有有限最優(yōu)解？§5單

純

形

法

進(jìn)

一

步

討

論處理方法一大Ｍ法人造基添加人工變量造成基去掉人工變量人工變量§5單

純

形

法

進(jìn)

一

步

討

論原問(wèn)題的可行解新問(wèn)題的可行解目標(biāo)值結(jié)論：新問(wèn)題的最優(yōu)解中，如果人工變量均為零，則得到的解也是原問(wèn)題的最優(yōu)解，否則原問(wèn)題無(wú)可行解例6大M法-M0-10x500010x6-M00-11-21x6-M0014M-2M-3cj-zj101309x7-M011114x40x7x4x3x2x1b-M010-3cjXBCB表1-100x400011-1/2-1/2-1/20x23011/30001/3-3x11102/301/2-1/21/6cj-zj00303/2-M-3/2-M+1/2CBXBcj-30100-M-Mbx1x2x3x4x5x6x70x4331110000x21-21-10-110-Mx766310001cj-zj6M-304M+103M-4M00x400001-1/21/2-1/20x25/2-1/2100-1/41/41/4-3x33/23/20103/401/4cj-zj-2/9000-3/4-M+3/4-M-1/4最優(yōu)解:X=(0,5/2,3/2,0,0,0,0)最優(yōu)值：Z=3/2大M法舉例CB

XB

cj1200-M

xj

bx1x2x3x4x50x4111010-Mx54-12-101cj-zj012000CB

XB

cj-1-200-M

xj

bx1x2x3x4x50x4111010-Mx54-12-101cj-zj012000-2x2111010-Mx52-30-1-21cj-zj210020CB

XB

cj-1-200-M

xj

bx1x2x3x4x5-2x2111010-Mx52-30-1-21－Ｚ210020M2-30-1-20所有檢驗(yàn)數(shù)<0已經(jīng)是最優(yōu)解x5=2人工變量不為零,表示原問(wèn)題無(wú)可行解參照?qǐng)D解法結(jié)果線性規(guī)劃及單純形法線性規(guī)劃問(wèn)題及數(shù)學(xué)模型圖解法單純形法原理單純形法計(jì)算步驟單純形法進(jìn)一步討論數(shù)據(jù)包絡(luò)分析其他應(yīng)用例子單

純

形

法

進(jìn)

一

步

討

論處理方法二兩階段法人造基添加人工變量造成基去掉人工變量人工變量?jī)?/p>

階

段

法如果線性規(guī)劃問(wèn)題中的aij、bi或cj等參數(shù)值與這個(gè)代表M的數(shù)相對(duì)比較接近，或遠(yuǎn)遠(yuǎn)小于這個(gè)數(shù)字，由于計(jì)算機(jī)計(jì)算時(shí)取值上的誤差，有可能使計(jì)算結(jié)果發(fā)生錯(cuò)誤。為了克服這個(gè)困難，可以對(duì)添加人工變量后的線性規(guī)劃問(wèn)題分兩個(gè)階段來(lái)計(jì)算，稱兩階段法。單

純

形

法

進(jìn)

一

步

討

論第一階段第一階段最優(yōu)解中:如果Z<0,則原問(wèn)題沒(méi)有基本可行解;如果Z=0,則若人工變量全為非基變量,則得到原問(wèn)題的基本可行解.否則基本可行解退化,繼續(xù)迭代就可以得到基本可行解.單

純

形

法

進(jìn)

一

步

討

論第二階段以第一階段最優(yōu)基作為初始基本可行解,繼續(xù)迭代.第一階段例6兩階段法第一階段：-10-10x500010x6-100-11-21x6-10004-2cj-zj1013-19x7-1011114x40x7x4x3x2x1

b-10000

cj

XBCB表1-11請(qǐng)注意:第一階段的最優(yōu)解不是唯一的33-11x50-4-31-1x6-100-11-21x2000406cj-zj104066x7-1012033x40x7x4x3x2x1

b-10000

cj

XBCB表1-1101/20-1/2x50-1-1/201/2x6-11/301/3103x20-10000cj-zj1/602/3011x10-1/210000x40x7x4x3x2x1

b-10000

cj

XBCB3/20300cj-zj1/20-1/2x5001/3103x2002/3011x1-312000x40x4x3x2x1

b010-3

cj

XBCB表1-12第二階段-3/43/4-1/4-1/2x50001-1/25/2x20000-9/2cj-zj0103/23/2x3110000x40x4x3x2x1

b0000

cj

XBCB幾點(diǎn)注意事項(xiàng)檢驗(yàn)數(shù)的計(jì)算；進(jìn)基變量的選取；若有不止一個(gè)變量可以進(jìn)基時(shí),只取一個(gè)；最小比值；若有不止一個(gè)最小比值時(shí)，只能選取其中之一行對(duì)應(yīng)的基變量出基；沒(méi)有有限最優(yōu)解的情況；最優(yōu)解是否唯一；最優(yōu)表中非基變量檢驗(yàn)數(shù)等于零時(shí),可能最優(yōu)解不唯一。線性規(guī)劃及單純形法線性規(guī)劃問(wèn)題及數(shù)學(xué)模型圖解法單純形法原理單純形法計(jì)算步驟單純形法進(jìn)一步討論數(shù)據(jù)包絡(luò)分析其他應(yīng)用例子數(shù)據(jù)包絡(luò)分析(DataEnvelo