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

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

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

subjectto的縮寫，“受限制于……”當前16頁，總共104頁。問題的提出例2

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

當前19頁，總共104頁。概念和模型一般形式：max（或min）

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

稱為價值系數(shù)或目標函數(shù)系數(shù)

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

當前20頁，總共104頁。概念和模型緊縮形式：max（或min）

當前21頁，總共104頁。概念和模型矩陣形式：max（或min）

稱為決策變量向量

稱為價值系數(shù)向量或目標函數(shù)系數(shù)向量

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

當前22頁，總共104頁。標準形式標準型的主要特征：①目標最大；②約束等式；③變量非負；④右端非負。當前23頁，總共104頁。標準型標準型的緊縮形式：標準型的矩陣形式：當前24頁，總共104頁。標準型標準型的向量形式：其中：當前25頁，總共104頁。標準化把一般的LP化成標準型的過程稱為線性規(guī)劃問題的標準化方法：1目標標準化

minZ

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

(1.1c)(1.1a)(1.1b)(1.1d)當前30頁，總共104頁。圖解法

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

1.建立平面直角坐標系，標出坐標原點,坐標軸的指向和單位長度。2.對約束條件加以圖解，找出可行域。3.畫出目標函數(shù)等值線。4.結合目標函數(shù)的要求求出最優(yōu)解。當前31頁，總共104頁。圖

解

法(1.1c)(1.1a)(1.1b)(1.1d)當前32頁，總共104頁。圖解法 (a)可行域有界(b)可行域有界 (c)可行域無界 唯一最優(yōu)解 多個最優(yōu)解 唯一最優(yōu)解(d)可行域無界(e)可行域無界(f)可行域為空集 多個最優(yōu)解 目標函數(shù)無界無可行解當前33頁，總共104頁。線性規(guī)劃及單純形法線性規(guī)劃問題及數(shù)學模型圖解法單純形法原理單純形法計算步驟單純形法進一步討論數(shù)據(jù)包絡分析其他應用例子當前34頁，總共104頁?！?單純形法原理線性規(guī)劃問題的解的概念凸集及其頂點幾個基本定理當前35頁，總共104頁。解

的

概

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

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

XB≥0XN=0可行基：對應于基可行解的基A=（B|N）當前39頁，總共104頁。解的概念最優(yōu)基：對應的基本可行解也是最優(yōu)基本可行解個數(shù)≤基的個數(shù)≤Cnm基本可行解的非零分量均為正分量，其正分量個數(shù)≤m。退化的基本可行解：基本可行解的非零分量個數(shù)小于m時，也就是在基本可行解中一個或多于一個的基變量取零值時當前40頁，總共104頁。凸

集

及

其

頂

點1、基本概念：

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

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

K（0<α<1），則稱K為凸集。當前41頁，總共104頁。凸

集

的

概

念頂點——設K是凸集，XK；若K中不存在兩個不同的點X（1）

K，X（2）

K使

X=αX（1）+（1-α）X（2）（0<α<1）則稱X為K的一個頂點（也稱為極點或角點）。當前42頁，總共104頁。凸

集

的

概

念凸集凸集不是凸集頂點當前43頁，總共104頁?；?/p>

本

定

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

求一個初始基本可行解

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

不是

求使目標得到改善的基本可行解

是否存在？如何得到？是否唯一？如何判斷？如何改善？如何判斷沒有有限最優(yōu)解？當前46頁，總共104頁。線性規(guī)劃及單純形法線性規(guī)劃問題及數(shù)學模型圖解法單純形法原理單純形法計算步驟單純形法進一步討論數(shù)據(jù)包絡分析其他應用例子當前47頁，總共104頁?！?

單純形法

迭代原理單純形方法引例單純形法的一般描述表格單純形法一般問題的處理單純形法矩陣描述幾點注意事項當前48頁，總共104頁。單純形方法引例用單純形法的思想求解線性規(guī)劃問題：當前49頁，總共104頁。單純形方法引例例基本解（0，0，0，3，9）也是可行的

當前50頁，總共104頁。單純形方法引例例初始基本可行解X(0)=（0，0，0，3，9）含義：不生產任何產品，工時剩余為3，材料剩余為9，利潤為Z(0)=0

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

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

j；當前61頁，總共104頁。單純形法一般步驟3.代入目標消去基變量，得到非基變量xj的檢驗數(shù)

j；當前62頁，總共104頁。單純形法一般步驟4.判斷最優(yōu)；最優(yōu)性判別定理：若是對應于B的基本可行解，j是用非基變量表示目標函數(shù)的表達式中非基變量xj的檢驗數(shù)，若對于一切非基變量的角指數(shù)j均有j≤0則當前基本可行解為最優(yōu)解。對于任意可行解X，對于基本可行解X0，當前63頁，總共104頁。單純形法一般步驟5.沒有有限最優(yōu)解的判斷；無最優(yōu)解判別定理：若是對應于B的基本可行解，非基變量xk的檢驗數(shù)k>0,且對于i=1,2,……,m均有aik≤0,則問題沒有有限最優(yōu)解。當前64頁，總共104頁。單純形法一般步驟6.改進目標

若k>0，則選xk進基;用最小比值法確定xk的最大值θ，使基變量xl取0值，其它基變量非負；即xl出基，目標改善kθ，換基過程若θ不存在,則Z→∞，沒有有限最優(yōu)解。當前65頁，總共104頁。單純形法一般步驟7.主元變換（樞變換或旋轉變換）xk進基，xl出基，解出新的基變量當前66頁，總共104頁。§5表格單純形法標準型：當前67頁，總共104頁。表格單純形法標準型：當前68頁，總共104頁。表格單純形法當前69頁，總共104頁。表格單純形法基變量檢驗數(shù)最小比值列基變量系數(shù)右端常數(shù)當前70頁，總共104頁。CB基

cj21000bx1x2x3x4x50x315051000x424620100x5511001cj-zj21000解：表1-7當前71頁，總共104頁。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當前72頁，總共104頁。表1-9中所有j<=0,且基變量中不含人工變量，最優(yōu)解X=(7/2,3/2,15/2,0,0);最優(yōu)值Z=17/2.當前73頁，總共104頁。練習1：求解線性規(guī)劃表格單純形法CB

XB

cj25000

xj

bx1x2x3x4x50x34111004/10x42-1201010x521-1001-cj-zj０25０００當前74頁，總共104頁。向右迭代一步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當前75頁，總共104頁。練習2：求解線性規(guī)劃CB

XB

cj1200

xj

bx1x2x3x40x301-2100x431001－Ｚ０12００表格單純形法沒有有限最優(yōu)解當前76頁，總共104頁。算法思路

求一個初始基本可行解

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

不是

求使目標得到改善的基本可行解

是否存在？如何得到？是否唯一？如何判斷？如何改善？如何判斷沒有有限最優(yōu)解？當前77頁，總共104頁?！?單

純

形

法

進

一

步

討

論處理方法一大Ｍ法人造基添加人工變量造成基去掉人工變量人工變量當前78頁，總共104頁?！?單

純

形

法

進

一

步

討

論原問題的可行解新問題的可行解目標值結論：新問題的最優(yōu)解中，如果人工變量均為零，則得到的解也是原問題的最優(yōu)解，否則原問題無可行解當前79頁，總共104頁。例6大M法-M0-10x500010x6-M00-11-21x6-M0014M-2M-3cj-zj101309x7-M011114x40x7x4x3x2x1b-M010-3cjXBCB表1-10當前80頁，總共104頁。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當前81頁，總共104頁。CB

XB

cj1200-M

bx1x2x3x4x50x4111010-Mx54-12-101cj-zj-4M-M2M+2-M00大M法舉例當前82頁，總共104頁。CB

XB

cj1200-M

bx1x2x3x4x52x2111010-Mx52-30-1-21cj-zj2-2M-1-3M0-M-2-2M0所有檢驗數(shù)<0已經是最優(yōu)解x5=2人工變量不為零,表示原問題無可行解參照圖解法結果當前83頁，總共104頁?！?單

純

形

法

進

一

步

討

論處理方法二兩階段法人造基添加人工變量造成基去掉人工變量人工變量當前84頁，總共104頁。兩

階

段

法

如果線性規(guī)劃問題中的aij、bi或cj等參數(shù)值與這個代表M的數(shù)相對比較接近，或遠遠小于這個數(shù)字，由于計算機計算時取值上的誤差，有可能使計算結果發(fā)生錯誤。為了克服這個困難，可以對添加人工變量后的線性規(guī)劃問題分兩個階段來計算，稱兩階段法。當前85頁，總共104頁?！?單

純

形

法

進

一

步

討

論第一階段第一階段最優(yōu)解中:如果Z<0,則原問題沒有基本可行解;如果Z=0,則若人工變量全為非基變量,則得到原問題的基本可行解.否則基本可行解退化,繼續(xù)迭代就可以得到基本可行解.當前86頁，總共104頁。§5單

純

形

法

進

一

步

討

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

b-10000

cj

XBCB表1-11當前88頁，總共104頁。請注意:第一階段的最優(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當前89頁，總共104頁。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當前90頁，總共104頁。單純形法矩陣描述當前91頁，總共104頁。單純形法矩陣描述當前92頁，總共104頁。單純形法矩陣描述當前93頁，總共104頁。幾點注意事項檢驗數(shù)的計算；進基變量的選??；若有不止一個變量可以進基時,只取一個；最小比值；若有不止一個最小比值時，只能選取其中之一行對應的基變量出基；沒有有限最優(yōu)解的情況；最優(yōu)解是否唯一；最優(yōu)表中非基變量檢驗數(shù)等于零時,可能最優(yōu)解不唯一。