線性規(guī)劃的一般求解方法——單純形法

  文件類別:營銷資料

  文件格式:文件格式

  文件大?。?73K

  下載次數(shù):1821

  所需積分:9點

  解壓密碼:qg68.cn

  下載地址:[下載地址]

清華大學卓越生產(chǎn)運營總監(jiān)高級研修班

綜合能力考核表詳細內容

線性規(guī)劃的一般求解方法——單純形法

第三章 線性規(guī)劃的一般求解方法 ——單純形法
它的一般形式為:

稱為約束條件(Subject to)。 稱為變量的非負約束條件。其余的變量可取正值、負值、或零值,稱這樣的變量為符號無限制變量或自由變量。 線性規(guī)劃模型的特征是:一組決策變量 ,一組約束條件。一個目標函數(shù)。目標函數(shù)和約束條件都是線性的。

二、線性規(guī)劃問題的標準行式是什么? 如何將一個LP問題的一般形式轉換為 標準形式? (1)、這里規(guī)定的標準形式為:

簡記為:
用矩陣表示為:
用列向量表示為:
(2)為了把一般形式的LP變換為標準形式,必須消除其不等式約束和符號無限制變量。
目標函數(shù)的轉換
約束條件的轉換
變量的非負約束的轉換
任何形式的線性規(guī)劃數(shù)學模型都可以轉換成標準型的線性規(guī)劃


三、什么是可行解、可行域,可行域的幾何結構?
滿足所有約束條件的決策變量,稱為可行解或可行點(feasible point)。
使目標函數(shù)值最大的可行解稱為最優(yōu)解
所有可行點組成的集合稱為可行域(feasible region),記為D.
給定一個LP問題可行域D,下列三種情況必居其一
D = ø 稱該問題無解或不可行。 D ø 且可行域有界。則線性規(guī)劃問題一定存在最優(yōu)解。這時最優(yōu)解唯一,也可能有無窮多。 D ø, 且可行域為無界,則線性規(guī)劃問題或者有最優(yōu)解(唯一或無窮多)也可能沒有有限的最優(yōu)解。 當可行域非空時,可行域的幾何結構為(多面)凸集
四、基本解、基本可行解 (basic solution、basic feasible solution)



五、 LP問題的幾何意義(單純形表的數(shù)學原理)
若線性規(guī)劃問題存在可行域,則其可行域D是凸集
線性規(guī)劃問題的可行解為基可行解的充要條件是的正分量所對應的系數(shù)列向量線性無關。
X是基本可行解的充分必要條件是X是可行域D的頂點
一個標準的LP問題,若有可行解,則至少有一個基本可行解
一個標準的LP問題,若有有限的最優(yōu)值,則一定存在一個基本可行解是最優(yōu)解。


X是基本可行解的充分必要條件是X是可行域D的頂點

由以上定理可知,最優(yōu)解一定在某一基本可行解處達到。因此單純形法的基本思想是:先找一個基本可行解,然后判斷它是否為最優(yōu)解,如不是,就找一個更好的基本可行解,再進行判斷,如此迭代進行,直到找到最優(yōu)解或者判斷該問題無界。
1.單純形表 為了計算的方便,我們可以將單純形法的全部計算過程在一個類似增廣矩陣的數(shù)表上進行,這種表格稱單純形表,不同的教材設計表格稍有不同,這里設計如下:
2.  單純形方法步驟

 Step1 轉換一般的LP模型為標準型。
Step2  找一個初始可行基。
Step3  計算單純形表中的各矩陣。
Step4 構造單純形表。
Step5 判斷最優(yōu)解,是,則結束。否     則,轉入下一步。
Step6 換基迭代,返回Step5。

如何得到第一個基本可行解? 為了得到初始基本可行解,要首先找到初始基本可行基,設B為約束矩陣的一個m階子式,如果B非奇異,則矩陣B是一個基, 進一步,若 ,那么B是初始基本可行基。 就是初始基本可行解。找初始基本可行基的方法如下 1.觀察法與試驗法。2.大M法。3.兩階段法
如何判斷基本可行解是最優(yōu)解? 對線性規(guī)劃問題的求解結果可能出現(xiàn)唯一最優(yōu)解、無窮多最優(yōu)解、無界解和無可行解四種情況,



——掌握線性規(guī)劃問題的數(shù)學原理及代數(shù)的單純形解法是學習LP的最高境界。 ——掌握這一方法對于以后的學習大有裨益,希望同學們發(fā)揚十二分的耐心和鉆研精神。


2、寫出初始單純形表

3、判斷基本可行解是最優(yōu)解 由于檢驗數(shù)有正數(shù),且對應的列向量不全為負,故進行換基迭代,
4、換基迭代 選上表中的 為軸心項
5、判斷、由于檢驗數(shù)有正數(shù)且對應的列向量不全為負,故進行換基迭代,選上表中的 為軸心項
由單純形表得一基最優(yōu)解, 由于有非基變量的檢驗數(shù)為零,則此線性規(guī)劃有無窮解。選上表中的 為軸心項.
原線性規(guī)劃所有最優(yōu)解為:
如何用QM軟件求解LP問題 三角洲航空公司的航班配置問題(怎樣為各條航線分配班機和為乘客分配座位)。用LP模型解決,用到60000個變量,40000個約束條件。
課堂練習 A、用單純形法求解兩個變量的LP問題。 B、用QM軟件求解LP問題
謝謝


線性規(guī)劃的一般求解方法——單純形法
 

[下載聲明]
1.本站的所有資料均為資料作者提供和網(wǎng)友推薦收集整理而來,僅供學習和研究交流使用。如有侵犯到您版權的,請來電指出,本站將立即改正。電話:010-82593357。
2、訪問管理資源網(wǎng)的用戶必須明白,本站對提供下載的學習資料等不擁有任何權利,版權歸該下載資源的合法擁有者所有。
3、本站保證站內提供的所有可下載資源都是按“原樣”提供,本站未做過任何改動;但本網(wǎng)站不保證本站提供的下載資源的準確性、安全性和完整性;同時本網(wǎng)站也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的損失或傷害。
4、未經(jīng)本網(wǎng)站的明確許可,任何人不得大量鏈接本站下載資源;不得復制或仿造本網(wǎng)站。本網(wǎng)站對其自行開發(fā)的或和他人共同開發(fā)的所有內容、技術手段和服務擁有全部知識產(chǎn)權,任何人不得侵害或破壞,也不得擅自使用。

 我要上傳資料,請點我!
人才招聘 免責聲明 常見問題 廣告服務 聯(lián)系方式 隱私保護 積分規(guī)則 關于我們 登陸幫助 友情鏈接
COPYRIGT @ 2001-2018 HTTP://c5m8.com INC. ALL RIGHTS RESERVED. 管理資源網(wǎng) 版權所有