線性規(guī)劃的提出課件

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

在線性約束條件下,求線性目標(biāo)函數(shù)的最大值或最小值問題,稱為線性規(guī)劃問題.線性規(guī)劃主要解決：如何利用現(xiàn)有的資源，使得預(yù)期目標(biāo)達(dá)到最優(yōu)。1第一章線性規(guī)劃與單純形法在線性約束條件下,求線性線性規(guī)劃是運(yùn)籌學(xué)的重要分枝，也是運(yùn)籌學(xué)最基本的部分。20世紀(jì)30年代末，前蘇聯(lián)學(xué)者康托洛維奇首先研究了線性規(guī)劃問題。1939年，他撰寫的《生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法》一書，是線性規(guī)劃應(yīng)用于工業(yè)生產(chǎn)問題的經(jīng)典著作。然而這項(xiàng)工作長(zhǎng)期不為人們所知。2線性規(guī)劃是運(yùn)籌學(xué)的重要分枝，也是運(yùn)籌學(xué)最基本的部分。第二次世界大戰(zhàn)期間，由于戰(zhàn)爭(zhēng)的需要，柯勃門（T.C.Koopmans）重行、獨(dú)立地研究了運(yùn)輸問題。后來丹捷格（G.B.Dantzig）于1947年發(fā)現(xiàn)了單純形方法，并將其應(yīng)用于與國(guó)防有關(guān)的諸如人員的輪訓(xùn)、任務(wù)的分派等問題。此后，線性規(guī)劃的理論和方法日漸趨于成熟。3第二次世界大戰(zhàn)期間，由于戰(zhàn)爭(zhēng)的需要，柯勃門（T.C兩類決策問題▲對(duì)給定的任務(wù)，如何用最少的資源去完成它▲如何利用有限的緊缺資源產(chǎn)生最大的經(jīng)濟(jì)或社會(huì)效益4兩類決策問題▲對(duì)給定的任務(wù)，如何用最少的資源去完成它▲如運(yùn)籌學(xué)中應(yīng)用最廣泛的方法之一運(yùn)籌學(xué)的最基本的方法之一，網(wǎng)絡(luò)規(guī)劃，整數(shù)規(guī)劃，目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃都是以線性規(guī)劃為基礎(chǔ)的解決稀缺資源最優(yōu)分配的有效方法，使付出的費(fèi)用最小或獲得的收益最大歷史悠久、理論成熟、應(yīng)用廣泛從1964年諾貝爾獎(jiǎng)設(shè)經(jīng)濟(jì)學(xué)獎(jiǎng)后，到1992年28年間的32名獲獎(jiǎng)?wù)咧杏?3人(40%)從事過與線性規(guī)劃有關(guān)的研究工作，其中比較著名的還有Simon，Samullson，Leontief，Arrow，Miller等

線性規(guī)劃的特點(diǎn)5運(yùn)籌學(xué)中應(yīng)用最廣泛的方法之一線性規(guī)劃的特點(diǎn)5第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型

例1：某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品都需要用到A、B兩原材料，每噸甲、乙產(chǎn)品所需的原材料數(shù)量及利潤(rùn)值以及這兩種原材料在計(jì)劃期內(nèi)能提供的數(shù)量見下表，問如何安排生產(chǎn)計(jì)劃，即甲乙各生產(chǎn)多少噸，使該廠和利潤(rùn)最大？單位產(chǎn)品所用原材料甲乙原材料數(shù)量（噸）A5424B8648利潤(rùn)（千元/噸）45求MAX6第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型例1：某企業(yè)生產(chǎn)甲、乙兩線性規(guī)劃所研究的對(duì)象屬于最優(yōu)化的范疇，本質(zhì)上是一個(gè)極值問題。和其它最優(yōu)化問題一樣，在建立線性規(guī)劃問題的數(shù)學(xué)模型時(shí)，應(yīng)首先明確三個(gè)基本要素：

決策變量（decisionvariables）：它們是決策者所控制的那些數(shù)量，它們?nèi)∈裁磾?shù)值需要決策者來決策，問題的求解就是找出決策變量的最優(yōu)值。7線性規(guī)劃所研究的對(duì)象屬于最優(yōu)化的范疇，本質(zhì)上是一個(gè)極

約束條件（constraints）：它們是決策者在現(xiàn)實(shí)世界中所受到的限制，或者說決策變量在這些限制范圍之內(nèi)才有意義。

目標(biāo)函數(shù)（objectivefunction）：它代表決策者希望對(duì)其進(jìn)行優(yōu)化的那個(gè)指標(biāo)。目標(biāo)函數(shù)是決策變量的函數(shù)。線性規(guī)劃問題的特征是目標(biāo)函數(shù)和約束條件中的函數(shù)都是決策變量的線性函數(shù)，并且約束是必不可少的(否則不存在有實(shí)際意義的解)。8約束條件（constraints）：它們是決策者在現(xiàn)例2：某公司經(jīng)銷一種產(chǎn)品，下設(shè)三個(gè)生產(chǎn)點(diǎn)，每日的產(chǎn)量分別是A1：5，A2：7，A3：8（噸），分別運(yùn)往四個(gè)銷售點(diǎn)，各地的銷量分別為B1：3，B2：4，B3：5，B4：8（噸），已知每噸產(chǎn)品從各生產(chǎn)地到各銷售點(diǎn)的運(yùn)價(jià)如下，問該公司如何調(diào)運(yùn)產(chǎn)品，可在滿足各銷售點(diǎn)需要量的前提下，總運(yùn)費(fèi)最??？單位運(yùn)價(jià)（百元/噸）B1B2B3B4A1411310A21928A3741059例2：某公司經(jīng)銷一種產(chǎn)品，下設(shè)三個(gè)生產(chǎn)點(diǎn)，每日的產(chǎn)量分別是A①每一個(gè)問題都有一組變量---稱為決策變量，一般記為下面從數(shù)學(xué)的角度來歸納上述兩個(gè)例子的共同點(diǎn)。②每個(gè)問題中都有決策變量需滿足的一組約束條件---線性的等式或不等式。對(duì)決策變量每一組值：代表了一種決策方案。通常要求決策變量取值非負(fù)，即二、線性規(guī)劃問題的數(shù)學(xué)模型10①每一個(gè)問題都有一組變量---稱為決策變量，一般記為下面從數(shù)③都有一個(gè)關(guān)于決策變量的線性函數(shù)---稱為目標(biāo)函數(shù)。要求這個(gè)目標(biāo)函數(shù)在滿足約束條件下實(shí)現(xiàn)最大化或最小化。將約束條件及目標(biāo)函數(shù)都是決策變量的線性函數(shù)的規(guī)劃問題稱為線性規(guī)劃。有時(shí)也將線性規(guī)劃問題簡(jiǎn)記為L(zhǎng)P（linearprogramming)其數(shù)學(xué)模型為：11③都有一個(gè)關(guān)于決策變量的線性函數(shù)---稱為目標(biāo)函數(shù)。要求這上述模型的簡(jiǎn)寫形式為：這里“s.t.”是“subjectto”的縮寫，即“滿足于”的意思。12上述模型的簡(jiǎn)寫形式為：這里“s.t.”是“subjectt若令13若令13線性規(guī)劃問題可記為矩陣和向量的形式：用向量表示時(shí)，上述模型可寫為：14線性規(guī)劃問題可記為矩陣和向量的形式：用向量表示時(shí)，上述模型可注意目標(biāo)和約束均為變量的線性表達(dá)式如果模型中出現(xiàn)如的非線性表達(dá)式，則不屬于線性規(guī)劃。15注意目標(biāo)和約束均為變量的線性表達(dá)式15基本概念約束條件(constraintconditions)目標(biāo)函數(shù)(objectivefunction)決策變量(decisionvariable)數(shù)學(xué)規(guī)劃問題

在某些約束條件下，求解目標(biāo)函數(shù)達(dá)到極大或極小的問題線性規(guī)劃問題（LinearProgramming,LP.）約束條件是變量的線性方程或不等式組，目標(biāo)函數(shù)也是變量的線性函數(shù)的數(shù)學(xué)規(guī)劃問題線性規(guī)劃的基本任務(wù)在線性約束下，求出適當(dāng)?shù)臎Q策變量使得線性目標(biāo)函數(shù)達(dá)到最大或最小16基本概念約束條件(constraintconditio可行解（feasiblesol.）

使得約束條件成立的決策變量的一組值可行域（feasibleregion）全體可行解組成的集合（經(jīng)常記為S）最優(yōu)解（optimalsol.）

可行域中使目標(biāo)函數(shù)達(dá)到所需最大或最小的可行解17可行解（feasiblesol.）使得約束條件成立的決策三、線性規(guī)劃問題的標(biāo)準(zhǔn)形式LP問題的數(shù)學(xué)模型的標(biāo)準(zhǔn)形式為：其中常數(shù)項(xiàng)18三、線性規(guī)劃問題的標(biāo)準(zhǔn)形式LP問題的數(shù)學(xué)模型的標(biāo)準(zhǔn)形式為：其LP問題標(biāo)準(zhǔn)形式的特征是：⑴求目標(biāo)函數(shù)的最大值；⑵約束條件為變量滿足線性方程組且為等式；⑶方程組中變量、常數(shù)項(xiàng)皆非負(fù)。19LP問題標(biāo)準(zhǔn)形式的特征是：⑴求目標(biāo)函數(shù)的最大值；19一般形式化為標(biāo)準(zhǔn)形式當(dāng)約束條件中有“<=”時(shí)，加上一個(gè)非負(fù)新變量，使之成為等式。這個(gè)新變量稱為松弛變量（slackvariable）當(dāng)約束條件中有“>=”時(shí)，減去一個(gè)非負(fù)新變量，使之成為等式．這個(gè)新變量稱為剩余變量（surplusvariable）當(dāng)約束條件右端常數(shù)項(xiàng)為負(fù)數(shù)時(shí)，將等式兩邊乘以（-1）當(dāng)某一決策變量沒有非負(fù)限制時(shí)，引進(jìn)兩個(gè)新的非負(fù)變量x’,x’’，令X=X’-X’’，代入約束條件和目標(biāo)函數(shù)中，即可化為非負(fù)變量的問題當(dāng)要求解目標(biāo)函數(shù)Z的最大值時(shí)，引進(jìn)新的目標(biāo)函數(shù)Z’，令Z=-Z’，則變成求Max。20一般形式化為標(biāo)準(zhǔn)形式當(dāng)約束條件中有“<=”時(shí)，加上一個(gè)非負(fù)例3將LP問題化為標(biāo)準(zhǔn)形。解：引進(jìn)新的目標(biāo)函數(shù)于是原LP問題化為標(biāo)準(zhǔn)形式：21例3將LP問題化為標(biāo)準(zhǔn)形。解：引進(jìn)新的目標(biāo)函數(shù)于是原LP例：MAXZ=3X1-X2+2X32X1-X2+X3>=4-4X1+X2+3X3=83X1+2X2+X3<=9X1,X2>=0,X3自由變量MAXZ=3X1-X2+2X3’-2X3’’2X1-X2+X3’-X3’’–X4=4-4X1+X2+3X3’-3X3’’=83X1+2X2+X3

’-X3’’+X5=9X1,X2,X3

’,X3

’

’,X4,X5>=022例：MAXZ=3X1-X2+2X3MAXZ=3X1例：公交線路人員優(yōu)化問題某晝夜服務(wù)的公交線路每天各時(shí)間區(qū)段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下：班次時(shí)間所需人數(shù)

16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030

設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間區(qū)段一開始時(shí)上班，并連續(xù)工作八小時(shí)，問該公交線路至少配備多少名司機(jī)和乘務(wù)人員。列出此問題的線性規(guī)劃模型。P46:Ex923例：公交線路人員優(yōu)化問題P46:Ex923決策變量：Xi為第i班開始上班的人數(shù)i=1,…,6目標(biāo)函數(shù)：MinZ=X1+X2+X3+X4+X5+