線性規(guī)劃及單純形法(含緒論)

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

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

subjectto的縮寫，“受限制于……”當(dāng)前第15頁\共有105頁\編于星期二\13點(diǎn)問題的提出例2

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

當(dāng)前第18頁\共有105頁\編于星期二\13點(diǎn)概念和模型一般形式：max（或min）

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

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

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

當(dāng)前第19頁\共有105頁\編于星期二\13點(diǎn)概念和模型緊縮形式：max（或min）

當(dāng)前第20頁\共有105頁\編于星期二\13點(diǎn)概念和模型矩陣形式：max（或min）

稱為決策變量向量

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

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

當(dāng)前第21頁\共有105頁\編于星期二\13點(diǎn)標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)型的主要特征：①目標(biāo)最大；②約束等式；③變量非負(fù)；④右端非負(fù)。當(dāng)前第22頁\共有105頁\編于星期二\13點(diǎn)標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型的緊縮形式：標(biāo)準(zhǔn)型的矩陣形式：當(dāng)前第23頁\共有105頁\編于星期二\13點(diǎn)標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型的向量形式：其中：當(dāng)前第24頁\共有105頁\編于星期二\13點(diǎn)標(biāo)準(zhǔn)化把一般的LP化成標(biāo)準(zhǔn)型的過程稱為線性規(guī)劃問題的標(biāo)準(zhǔn)化方法：1目標(biāo)標(biāo)準(zhǔn)化

minZ

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

(1.1c)(1.1a)(1.1b)(1.1d)當(dāng)前第29頁\共有105頁\編于星期二\13點(diǎn)圖解法

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

1.建立平面直角坐標(biāo)系，標(biāo)出坐標(biāo)原點(diǎn),坐標(biāo)軸的指向和單位長度。2.對約束條件加以圖解，找出可行域。3.畫出目標(biāo)函數(shù)等值線。4.結(jié)合目標(biāo)函數(shù)的要求求出最優(yōu)解。當(dāng)前第30頁\共有105頁\編于星期二\13點(diǎn)圖

解

法(1.1c)(1.1a)(1.1b)(1.1d)當(dāng)前第31頁\共有105頁\編于星期二\13點(diǎn)圖解法 (a)可行域有界(b)可行域有界 (c)可行域無界 唯一最優(yōu)解 多個最優(yōu)解 唯一最優(yōu)解(d)可行域無界(e)可行域無界(f)可行域?yàn)榭占?多個最優(yōu)解 目標(biāo)函數(shù)無界無可行解當(dāng)前第32頁\共有105頁\編于星期二\13點(diǎn)線性規(guī)劃及單純形法線性規(guī)劃問題及數(shù)學(xué)模型圖解法單純形法原理單純形法計(jì)算步驟單純形法進(jìn)一步討論數(shù)據(jù)包絡(luò)分析其他應(yīng)用例子當(dāng)前第33頁\共有105頁\編于星期二\13點(diǎn)§3單純形法原理線性規(guī)劃問題的解的概念凸集及其頂點(diǎn)幾個基本定理當(dāng)前第34頁\共有105頁\編于星期二\13點(diǎn)解

的

概

念可行解：變量滿足所有約束條件的一組值可行解集：所有可行解構(gòu)成的集合可行域：可行解集構(gòu)成n維空間的區(qū)域線性規(guī)劃問題當(dāng)前第35頁\共有105頁\編于星期二\13點(diǎn)解的概念最優(yōu)解：使得目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解最優(yōu)值：最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值目的：求最優(yōu)解和最優(yōu)值求解方法：單純形法當(dāng)前第36頁\共有105頁\編于星期二\13點(diǎn)解的概念先研究AX=b設(shè)系數(shù)矩陣A是m×n矩陣，秩為m，B是A中m×m階非奇異子矩陣（即|B|≠0），則稱B是線性規(guī)劃問題的一個基。B是由m個線性獨(dú)立的列向量組成基向量基變量非基變量：其余變量當(dāng)前第37頁\共有105頁\編于星期二\13點(diǎn)解的概念A(yù)X=BXB+NXN=b令非基變量XN=0得BXB=b和特解XB=B-1b結(jié)合XN=0

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

XB≥0XN=0可行基：對應(yīng)于基可行解的基A=（B|N）當(dāng)前第38頁\共有105頁\編于星期二\13點(diǎn)解的概念最優(yōu)基：對應(yīng)的基本可行解也是最優(yōu)基本可行解個數(shù)≤基的個數(shù)≤Cnm基本可行解的非零分量均為正分量，其正分量個數(shù)≤m。退化的基本可行解：基本可行解的非零分量個數(shù)小于m時(shí)，也就是在基本可行解中一個或多于一個的基變量取零值時(shí)當(dāng)前第39頁\共有105頁\編于星期二\13點(diǎn)凸

集

及

其

頂

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

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

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

K（0<α<1），則稱K為凸集。當(dāng)前第40頁\共有105頁\編于星期二\13點(diǎn)凸

集

的

概

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

K，X（2）

K使

X=αX（1）+（1-α）X（2）（0<α<1）則稱X為K的一個頂點(diǎn)（也稱為極點(diǎn)或角點(diǎn)）。當(dāng)前第41頁\共有105頁\編于星期二\13點(diǎn)凸

集

的

概

念凸集凸集不是凸集頂點(diǎn)當(dāng)前第42頁\共有105頁\編于星期二\13點(diǎn)基

本

定

理若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解（可行域頂點(diǎn)）是最優(yōu)解。定理1引理定理2定理3若線性規(guī)劃問題存在可行解，則該問題的可行解集（即可行域）是凸集。線性規(guī)劃問題的可行解x＝(x1,x2,…,xn)為基可行解的充要條件是x的正分量所對應(yīng)的系數(shù)列向量是線性獨(dú)立的。線性規(guī)劃問題的基可行解x對應(yīng)線性規(guī)劃問題可行域(凸集)的頂點(diǎn)當(dāng)前第43頁\共有105頁\編于星期二\13點(diǎn)解的幾何意義猜想1線性規(guī)劃的可行域是凸集；猜想2最優(yōu)解若存在，則可以在可行域的頂點(diǎn)上得到；猜想3可行域的頂點(diǎn)的個數(shù)是有限的；猜想4若有兩個最優(yōu)解，則其連線上的點(diǎn)也是最優(yōu)解，即最優(yōu)解有無窮多個猜想5對于標(biāo)準(zhǔn)型的線性規(guī)劃X是可行域頂點(diǎn)的充分必要條件是X是基本可行解。當(dāng)前第44頁\共有105頁\編于星期二\13點(diǎn)求解思路

求一個初始基本可行解

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

不是

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

是否存在？如何得到？是否唯一？如何判斷？如何改善？如何判斷沒有有限最優(yōu)解？當(dāng)前第45頁\共有105頁\編于星期二\13點(diǎn)線性規(guī)劃及單純形法線性規(guī)劃問題及數(shù)學(xué)模型圖解法單純形法原理單純形法計(jì)算步驟單純形法進(jìn)一步討論數(shù)據(jù)包絡(luò)分析其他應(yīng)用例子當(dāng)前第46頁\共有105頁\編于星期二\13點(diǎn)§4

單純形法

迭代原理單純形方法引例單純形法的一般描述表格單純形法一般問題的處理單純形法矩陣描述幾點(diǎn)注意事項(xiàng)當(dāng)前第47頁\共有105頁\編于星期二\13點(diǎn)單純形方法引例用單純形法的思想求解線性規(guī)劃問題：當(dāng)前第48頁\共有105頁\編于星期二\13點(diǎn)單純形方法引例例基本解（0，0，0，3，9）也是可行的

當(dāng)前第49頁\共有105頁\編于星期二\13點(diǎn)單純形方法引例例初始基本可行解X(0)=（0，0，0，3，9）含義：不生產(chǎn)任何產(chǎn)品，工時(shí)剩余為3，材料剩余為9，利潤為Z(0)=0

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

當(dāng)前第50頁\共有105頁\編于星期二\13點(diǎn)單純形方法引例例初始基本可行解X(0)=（0，0，0，3，9）當(dāng)x1（或x2,x3）增加一個單位時(shí)，會使目標(biāo)增加2（或3）單位考慮將x1（或x2,x3）并為非零變量，x2,x3價(jià)值系數(shù)加大，將x2變?yōu)榛兞俊胱兞?。?dāng)前第51頁\共有105頁\編于星期二\13點(diǎn)單純形方法引例例初始基本可行解X(0)=（0，0，0，3，9）當(dāng)x2作為引入變量，為使新解X(1)仍為基可行解，必須使且使x4或x5中有一個等于零——退出變量（1-1）當(dāng)前第52頁\共有105頁\編于星期二\13點(diǎn)單純形方法引例例由(1-1)第四、第五式，得為使新解X(1)為基可行解此時(shí)，變?yōu)榱悖瑇5為退出變量新的基可行解為X(1)=(0,9/4,0,3/4,0)目標(biāo)函數(shù)值Z(1)=27/4>Z(0)當(dāng)前第53頁\共有105頁\編于星期二\13點(diǎn)單純形方法引例例系數(shù)列向量此時(shí)，進(jìn)一步分析引入x1或x3是否會更好？引入哪一個更好？當(dāng)前第54頁\共有105頁\編于星期二\13點(diǎn)單純形方法引例首先考慮引入x1，由于計(jì)算增加單位x1所創(chuàng)增的凈經(jīng)濟(jì)價(jià)值同理，可計(jì)算增加單位x3所創(chuàng)增的凈經(jīng)濟(jì)價(jià)值檢驗(yàn)數(shù)當(dāng)前第55頁\共有105頁\編于星期二\13點(diǎn)單純形方法引例例基本可行解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)當(dāng)前第56頁\共有105頁\編于星期二\13點(diǎn)單純形法一般步驟1.初始基本可行解的確定（觀察法）；當(dāng)前第57頁\共有105頁\編于星期二\13點(diǎn)單純形法一般步驟1.初始基本可行解的確定（觀察法）；基基本可行解當(dāng)前第58頁\共有105頁\編于星期二\13點(diǎn)單純形法一般步驟2.從約束中解出基變量；當(dāng)前第59頁\共有105頁\編于星期二\13點(diǎn)單純形法一般步驟3.代入目標(biāo)消去基變量，得到非基變量xj的檢驗(yàn)數(shù)

j；當(dāng)前第60頁\共有105頁\編于星期二\13點(diǎn)單純形法一般步驟3.代入目標(biāo)消去基變量，得到非基變量xj的檢驗(yàn)數(shù)

j；當(dāng)前第61頁\共有105頁\編于星期二\13點(diǎn)單純形法一般步驟4.判斷最優(yōu)；最優(yōu)性判別定理：若是對應(yīng)于B的基本可行解，j是用非基變量表示目標(biāo)函數(shù)的表達(dá)式中非基變量xj的檢驗(yàn)數(shù)，若對于一切非基變量的角指數(shù)j均有j≤0則當(dāng)前基本可行解為最優(yōu)解。對于任意可行解X，對于基本可行解X0，當(dāng)前第62頁\共有105頁\編于星期二\13點(diǎn)單純形法一般步驟5.沒有有限最優(yōu)解的判斷；無最優(yōu)解判別定理：若是對應(yīng)于B的基本可行解，非基變量xk的檢驗(yàn)數(shù)k>0,且對于i=1,2,……,m均有aik≤0,則問題沒有有限最優(yōu)解。當(dāng)前第63頁\共有105頁\編于星期二\13點(diǎn)單純形法一般步驟6.改進(jìn)目標(biāo)

若k>0，則選xk進(jìn)基;用最小比值法確定xk的最大值θ，使基變量xl取0值，其它基變量非負(fù)；即xl出基，目標(biāo)改善kθ，換基過程若θ不存在,則Z→∞，沒有有限最優(yōu)解。當(dāng)前第64頁\共有105頁\編于星期二\13點(diǎn)單純形法一般步驟7.主元變換（樞變換或旋轉(zhuǎn)變換）xk進(jìn)基，xl出基，解出新的基變量當(dāng)前第65頁\共有105頁\編于星期二\13點(diǎn)§5表格單純形法標(biāo)準(zhǔn)型：當(dāng)前第66頁\共有105頁\編于星期二\13點(diǎn)表格單純形法標(biāo)準(zhǔn)型：當(dāng)前第67頁\共有105頁\編于星期二\13點(diǎn)表格單純形法當(dāng)前第68頁\共有105頁\編于星期二\13點(diǎn)表格單純形法基變量檢驗(yàn)數(shù)最小比值列基變量系數(shù)右端常數(shù)當(dāng)前第69頁\共有105頁\編于星期二\13點(diǎn)CB基

cj21000bx1x2x3x4x50x315051000x424620100x5511001cj-zj21000解：表1-7當(dāng)前第70頁\共有105頁\編于星期二\13點(diǎn)01/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當(dāng)前第71頁\共有105頁\編于星期二\13點(diǎn)表1-9中所有j<=0,且基變量中不含人工變量，最優(yōu)解X=(7/2,3/2,15/2,0,0);最優(yōu)值Z=17/2.當(dāng)前第72頁\共有105頁\編于星期二\13點(diǎn)練習(xí)1：求解線性規(guī)劃表格單純形法CB

XB

cj25000

xj

bx1x2x3x4x50x34111004/10x42-1201010x521-1001-cj-zj０25０００當(dāng)前第73頁\共有105頁\編于星期二\13點(diǎn)向右迭代一步CB

XB

cj25000

xj

bx1x2x3x4x50x333/201-1/2025x21-1/2101/20-0x531/2001/216cj-zj59/200-5/202x12102/3-1/305x22011/31/300x5201-1/32/31cj-zj1400-3-10當(dāng)前第74頁\共有105頁\編于星期二\13點(diǎn)練習(xí)2：求解線性規(guī)劃CB

XB

cj1200

xj

bx1x2x3x40x301-2100x431001－Ｚ０12００表格單純形法沒有有限最優(yōu)解當(dāng)前第75頁\共有105頁\編于星期二\13點(diǎn)算法思路

求一個初始基本可行解

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

不是

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

是否存在？如何得到？是否唯一？如何判斷？如何改善？如何判斷沒有有限最優(yōu)解？當(dāng)前第76頁\共有105頁\編于星期二\13點(diǎn)§5單

純

形

法

進(jìn)

一

步

討

論處理方法一大Ｍ法人造基添加人工變量造成基去掉人工變量人工變量當(dāng)前第77頁\共有105頁\編于星期二\13點(diǎn)§5單

純

形

法

進(jìn)

一

步

討

論原問題的可行解新問題的可行解目標(biāo)值結(jié)論：新問題的最優(yōu)解中，如果人工變量均為零，則得到的解也是原問題的最優(yōu)解，否則原問題無可行解當(dāng)前第78頁\共有105頁\編于星期二\13點(diǎn)例6大M法-M0-10x500010x6-M00-11-21x6-M0014M-2M-3cj-zj101309x7-M011114x40x7x4x3x2x1b-M010-3cjXBCB表1-10當(dāng)前第79頁\共有105頁\編于星期二\13點(diǎn)0x400001-1/21/2-1/20x23011/30001/3-3x11102/301/2-1/21/6cj-zj00303/2-M-3/2-M+1/2CBXBcj-30100-M-Mbx1x2x3x4x5x6x70x4330211-100x21-21-10-110-Mx7660403-31cj-zj6M-304M+103M-4M00x400001-1/21/2-1/20x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cj-zj-9/2000-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當(dāng)前第80頁\共有105頁\編于星期二\13點(diǎn)CB

XB

cj1200-M

bx1x2x3x4x50x4111010-Mx54-12-101cj-zj-4M-M2M+2-M00大M法舉例當(dāng)前第81頁\共有105頁\編于星期二\13點(diǎn)CB

XB

cj1200-M

bx1x2x3x4x52x2111010-Mx52-30-1-21cj-zj2-2M-1-3M0-M-2-2M0所有檢驗(yàn)數(shù)<0已經(jīng)是最優(yōu)解x5=2人工變量不為零,表示原問題無可行解參照圖解法結(jié)果當(dāng)前第82頁\共有105頁\編于星期二\13點(diǎn)§5單

純

形

法

進(jìn)

一

步

討

論處理方法二兩階段法人造基添加人工變量造成基去掉人工變量人工變量當(dāng)前第83頁\共有105頁\編于星期二\13點(diǎn)兩

階

段

法

如果線性規(guī)劃問題中的aij、bi或cj等參數(shù)值與這個代表M的數(shù)相對比較接近，或遠(yuǎn)遠(yuǎn)小于這個數(shù)字，由于計(jì)算機(jī)計(jì)算時(shí)取值上的誤差，有可能使計(jì)算結(jié)果發(fā)生錯誤。為了克服這個困難，可以對添加人工變量后的線性規(guī)劃問題分兩個階段來計(jì)算，稱兩階段法。當(dāng)前第84頁\共有105頁\編于星期二\13點(diǎn)§5單

純

形

法

進(jìn)

一

步

討

論第一階段第一階段最優(yōu)解中:如果Z<0,則原問題沒有基本可行解;如果Z=0,則若人工變量全為非基變量,則得到原問題的基本可行解.否則基本可行解退化,繼續(xù)迭代就可以得到基本可行解.當(dāng)前第85頁\共有105頁\編于星期二\13點(diǎn)§5單

純

形

法

進(jìn)

一

步

討

論第二階段以第一階段最優(yōu)基作為初始基本可行解,繼續(xù)迭代.第一階段當(dāng)前第86頁\共有105頁\編于星期二\13點(diǎn)例6兩階段法第一階段：-10-10x500010x6-100-11-21x6-10004-2cj-zj1013-19x7-1011114x40x7x4x3x2x1

b-10000

cj

XBCB表1-11當(dāng)前第87頁\共有105頁\編于星期二\13點(diǎn)請注意:第一階段的最優(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

XBCB當(dāng)前第88頁\共有105頁\編于星期二\13點(diǎn)3/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當(dāng)前第89頁\共有105頁\編于星期二\13點(diǎn)單純形法矩陣描述當(dāng)前第90頁\共有105頁\編于星期二\13點(diǎn)單純形法矩陣描述當(dāng)前第91頁\共有105頁\編于星期二\13點(diǎn)單純形法矩陣描述當(dāng)前第92頁\共有105頁\編于星期二\13點(diǎn)幾點(diǎn)注意事項(xiàng)檢驗(yàn)數(shù)的計(jì)算；進(jìn)基變量的選?。蝗粲胁恢挂粋€變量可以進(jìn)基時(shí),只取一個；最小比值；若有不止一個最小比值時(shí)，只能選取其中之一行對應(yīng)的基變量出基；沒有有限最優(yōu)解的情況；最優(yōu)解是否唯一；最優(yōu)表中非基變量檢驗(yàn)數(shù)等于零時(shí),可能最優(yōu)解不唯一。當(dāng)前第93頁\共有105頁\編于星期二\13點(diǎn)線性規(guī)劃及單純形法線性規(guī)劃問題及數(shù)學(xué)模型圖解法單純形法原理單純形法計(jì)算步驟單純形法進(jìn)一步討論數(shù)據(jù)包絡(luò)分析其他應(yīng)用例子當(dāng)前第94頁\共有105頁\編于星期二\13點(diǎn)數(shù)據(jù)包絡(luò)分析(DataEnvelopmentAnalysis,DEA),§6數(shù)據(jù)包絡(luò)分析根據(jù)多項(xiàng)投入指標(biāo)和多項(xiàng)產(chǎn)出指標(biāo),利用線性規(guī)劃的方