線性規(guī)劃講義.ppt

1、線性規(guī)劃講義（linear program）,組員： 林舒進(jìn) 萬軍 曾躍文 李婷,線性規(guī)劃（LP）,線性規(guī)劃是使用數(shù)學(xué)模型描述相關(guān)問題的一種工具 內(nèi)涵 線性：模型中所有的數(shù)學(xué)函數(shù)都是線性函數(shù)。 規(guī)劃：等同與計(jì)劃，既在模型中找找出最優(yōu)解。,線性規(guī)劃解決什么類型的問題,狹義問題：給活動(dòng)分配資源（競(jìng)爭(zhēng)性活動(dòng)中以最佳的可能方式分配有限資源） 例如：生產(chǎn)設(shè)施的分配，國家資源和家庭必須品的分配，部長職位的選舉，海運(yùn)模式的選擇，農(nóng)業(yè)生產(chǎn)計(jì)劃，放射性治療等 廣義問題：數(shù)學(xué)模型符合線性規(guī)劃一般形式的任何問題都是線性規(guī)劃問題,線性模型的三個(gè)要素,決策變量:待求的未知數(shù) 約束條件：一組線性方程，該線性方程的集合為決

2、策變量的可行域 目標(biāo)函數(shù)：用函數(shù)表示的追求的目標(biāo)，通常是最大或者最小,構(gòu)建線性規(guī)劃模型,圖解法,無窮多解 無界解 無可行解,模型解的術(shù)語,可行解（feasible solution）滿足所以約束條件的解（非可行解） 可行域（feasible region）所有可行解的集合 最優(yōu)解（optimal solution）目標(biāo)函數(shù)取得最有利的可行解,模型解的術(shù)語,基（the basis）：約束方程構(gòu)成矩陣中的非奇異矩陣（基向量、基變量、基解） 基可行解：非負(fù)的基解 可行基：對(duì)應(yīng)基可行解的基,單純形法原理分析,單純型法（simplex method）,1947年喬治.丹捷格（George Dantzig

3、）提出單純形法，（喬治.丹捷格堪稱運(yùn)籌學(xué)最重要的先驅(qū)，由于在單純形法及其他方面的很多重要貢獻(xiàn)，他被稱為線性規(guī)劃之父）單純形法已經(jīng)被證實(shí)是真正有效的方法，如今通常用于在計(jì)算機(jī)上解決大型問題。（除了一些小問題，這種方法總是在計(jì)算機(jī)上實(shí)現(xiàn)）單純形法的延伸和變化也被用來對(duì)模型進(jìn)行優(yōu)化后分析（包括靈敏度分析）,單純形法的實(shí)質(zhì),單純形法是一個(gè)代數(shù)計(jì)算過程，但它本質(zhì)上是基于幾何原理 了解這些幾何原理能為我們理解單純形法的運(yùn)算步驟提供非常直觀的解釋，同時(shí)也有助于我們將解釋為什么單純形法為什么會(huì)如此有效,單純形法的幾何原理,約束邊界（constraint boundary）：每個(gè)約束條件都是一條直線，該直線就是

4、滿足對(duì)應(yīng)約束的邊界線 角點(diǎn)解（corner-point solutions）：約束邊界的交點(diǎn) 角點(diǎn)可行解（CPF solutions）：在可行域上的角點(diǎn) 相鄰（adjacent）：兩個(gè)CPF解位于同一條約束邊界上，它們是相鄰的，兩個(gè)相鄰的CPF解連成的一條線段被稱為可行域的邊 （edge） 最優(yōu)性檢驗(yàn)（optimality test）：如果一個(gè)CPF解沒有比它更好（以z來衡量）的相鄰CPF解，那么它就是最優(yōu)解,幾何原理示例,關(guān)鍵的解原理,解原理1：?jiǎn)渭冃畏ㄖ魂P(guān)注CPF解 解原理2：?jiǎn)渭冃畏ㄊ且粋€(gè)迭代算法（一個(gè)系統(tǒng)化的求解過程，它重復(fù)著一系列固定的我們稱之為迭代的步驟，直到得到期望的結(jié)果），結(jié)構(gòu)

5、如下,關(guān)鍵的解原理,解原理3： 只要有可能單純形法的起始步驟就選擇原點(diǎn)作為初始CPF解 解原理4：已知一個(gè)CPF解，從計(jì)算上來說，獲取它的相鄰CPF解的信息比獲取其他CPF解的信息更快 解原理5：得到當(dāng)前的CPF解后，單純形法考察從這個(gè)解出發(fā)的可行域的每一條邊（不是計(jì)算相鄰CPF解，而僅僅是判斷沿這條邊移動(dòng)時(shí)z的增長率）,關(guān)鍵的解原理,解原理6：z增長率為正，意味著相鄰CPF解優(yōu)于當(dāng)前CPF解；z增長率為負(fù)，意味著相鄰CPF解并不優(yōu)于當(dāng)前CPF解。因此，最優(yōu)性檢驗(yàn)及時(shí)檢查是否有邊界線會(huì)帶給z正的增長率，如果沒有，則證明當(dāng)前的CPF解是最優(yōu)的。,構(gòu)建單純形法,單純形法通常是在計(jì)算機(jī)上實(shí)施的，而計(jì)

6、算機(jī)只能執(zhí)行代數(shù)運(yùn)算，因此需要把上述幾何原理轉(zhuǎn)化成可應(yīng)用代數(shù)計(jì)算的步驟。 第一步：把不等式約束轉(zhuǎn)化為等價(jià)的等式約束，這個(gè)過程考引入松弛變量（slack variables）來完成 模型的擴(kuò)展模式（augmented form）：原線性模型在引入松弛變量后形成的新的模式,擴(kuò)展模式的術(shù)語,擴(kuò)展解（augmented solution）：原始變量（決策變量）取值再加入相應(yīng)的松弛變量取值后形成的解 基本解（basic solution）：是一個(gè)擴(kuò)展后的角點(diǎn)解 基本可行解（BF解）：是擴(kuò)展的CPF解（非負(fù)）（非基變量，基變量，基） BF解相鄰（adjacent）：當(dāng)非基變量只有一個(gè)不同時(shí)，兩個(gè)BF解相鄰（因此，從當(dāng)前BF解轉(zhuǎn)到另一個(gè)相鄰的BF解時(shí)，圍繞著把一個(gè)變量從非基變量轉(zhuǎn)變?yōu)榛兞縼磉M(jìn)行）,單純形法的代數(shù)-初始化,選擇 為非基變量（這些變量設(shè)為0）,單純形法的代數(shù)-最優(yōu)性檢驗(yàn),單純形法的代數(shù)-確定移動(dòng)方向,單純形法的代數(shù)-確定在何處停下,單純形法的代