【教學(xué)】第三章：線性規(guī)劃數(shù)學(xué)模型

第三章線性規(guī)劃線性規(guī)劃（LinearProgramming,LP）是運(yùn)籌學(xué)中研究較早、理論成熟的重要分支之一，網(wǎng)絡(luò)規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃都是以線性規(guī)劃為基礎(chǔ)的。在公共管理和工商管理中都有廣泛的應(yīng)用。解決稀缺資源最優(yōu)分配的有效方法，使付出的費(fèi)用最小或獲得的收益最大。公共交通、垃圾清理、提供服務(wù)成本最小問題；救災(zāi)搶險、消防滅火、制止犯罪的最快反應(yīng)問題；控制污染、能源規(guī)劃、經(jīng)濟(jì)布局的最優(yōu)化問題，等等。1整理ppt馮?諾伊曼(VonNeuman)和摩根斯坦(Morgenstern)1944年發(fā)表的

《博弈論與經(jīng)濟(jì)行為》涉及與線性規(guī)劃等價的對策問題及線性規(guī)劃對偶理論從1964年諾貝爾獎設(shè)經(jīng)濟(jì)學(xué)獎后，到1992年28年間的32名獲獎?wù)咧杏?3人(40%)從事過與線性規(guī)劃有關(guān)的研究工作，其中比較著名的還有Simon，Samullson，Leontief，Arrow，Miller等2整理ppt研究對象有一定的人力、財力、資源條件下，如何合理安排使用，效益最高某項任務(wù)確定后，如何安排人、財、物，使之最省3整理ppt線性規(guī)劃模型是通過對實(shí)際問題的分析而建立的表示決策變量、最優(yōu)目標(biāo)和約束條件之間關(guān)系的一組數(shù)學(xué)關(guān)系式，由決策變量、目標(biāo)函數(shù)和約束條件三部分組成。在滿足一組約束條件下，求一組決策變量的值，使目標(biāo)函數(shù)達(dá)到最優(yōu)。4整理ppt線性規(guī)劃的特點(diǎn)決策變量連續(xù)性：求解出的決策變量值可以是整數(shù)、小數(shù)；線性函數(shù)：目標(biāo)函數(shù)方程和約束條件方程都是線性方程；單目標(biāo)：目標(biāo)函數(shù)是單目標(biāo)，只有一個極大值或一個極小值；確定性：只能應(yīng)用于確定型決策問題。5整理pptAB備用資源煤1230勞動日3260倉庫0224利潤4050例1、生產(chǎn)計劃問題A,B各生產(chǎn)多少,可獲最大利潤?6整理ppt

x1

+2x2

303x1+2x2

60

2x2

24

x1，x2

0

maxZ=40x1+50x2解:設(shè)產(chǎn)品A,B產(chǎn)量分別為變量x1，x27整理ppt例2求：最低成本的原料混合方案

原料ABＣ每單位成本

14102261253171642538

每單位添加劑中維生12148

素最低含量8整理ppt解：設(shè)每單位添加劑中原料i的用量為xi(i=1,2,3,4)minZ=2x1

+5x2+6x3+8x44x1

+6x2+x3+2x4

12x1

+x2+7x3+5x4

142x2

+x3+3x4

8

xi

0(i=1,…,4)9整理ppt一般式Max(min)Z=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXn(=,)b1a21X1+a22X2+…+a2nXn

(=,)b2………am1X1+am2X2+…+amnXn

(=,)bmXj0(j=1,…,n)10整理ppt要解決的問題的目標(biāo)可以用數(shù)值指標(biāo)反映對于要實(shí)現(xiàn)的目標(biāo)有多種方案可選擇有影響決策的若干約束條件11整理ppt圖解法AX=b(1)X

0(2)maxZ=CX(3)定義1：滿足約束(1)、(2)的X=(X1…Xn)T稱為LP問題的可行解，全部可行解的集合稱為可行域。定義2：滿足(3)的可行解稱為LP問題的最優(yōu)解12整理ppt例1、maxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X2013整理ppt解：(1)、確定可行域

X10X1=0(縱)X20X2=0(橫)X1+2X230X1+2X2=30(0,15)(30,0)2030100102030X2DABC3X1+2X2=60(0,30)(20,0)

2X2=2414整理ppt(2)、求最優(yōu)解解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2(0,0)，(10,-8)C點(diǎn)：X1+2X2=30

3X1+2X2=600203010102030X1X2DABC15整理ppt例2、maxZ=40X1+80X2X1+2X2303X1+2X2602X224

X1,X2016整理ppt0Z=40X1+80X2=0

X1+2X2=30DABCX2X1最優(yōu)解：BC線段B點(diǎn)C點(diǎn)X(1)=(6,12)X(2)=(15,7.5)X=

X(1)+(1-

)X(2)(01)求解17整理pptX1=6++(1-

)·15X2=12++(1-

)·7.5X1=15-9

X2=7.5+4.5

(01)X==

+(1-

)maxZ=1200

X1615

X2127.518整理ppt無界無有限最優(yōu)解例3、maxZ=2X1+4X22X1+X28-2X1+X22X1,X20Z=02X1+X2=8-2X1+X2=28246X240X119整理ppt例4、maxZ=3X1+2X2-X1-X21X1,X20無解無可行解-1X2-1X1020整理ppt總結(jié)唯一解無窮多解無有限最優(yōu)解無可行解有解無解21整理ppt單純形法單純形法（SimplexMethod）是美國數(shù)學(xué)家但澤（Dantzig）于1947年提出的?；舅枷胧峭ㄟ^有限次的換基迭代來求出線性規(guī)劃的最優(yōu)解。22整理ppt兩個變量的LP問題的解：可行域?yàn)橥苟噙呅危ㄍ辜(1)X(2)凸多邊形凹多邊形X(1)X(2)23整理ppt頂點(diǎn)原理頂點(diǎn)（極點(diǎn)）凸集中滿足一下條件的點(diǎn)：凸集中通過任意兩個點(diǎn)的直線上都不包含此點(diǎn)作為內(nèi)點(diǎn)，它只能是凸集的端點(diǎn)。頂點(diǎn)原理由于線性規(guī)劃問題的可行域都是凸集，如果存在最優(yōu)解，必然對應(yīng)于可行域凸集的至少一個頂點(diǎn)；如果只有一個最優(yōu)解，它必然對應(yīng)于一個頂點(diǎn)；如果存在多個最優(yōu)解，它們必然相鄰。24整理ppt頂點(diǎn)原理的運(yùn)用頂點(diǎn)原理證明，如果線性規(guī)劃的最優(yōu)解存在，要找到最優(yōu)解，只要找到可行域凸集頂點(diǎn)的坐標(biāo)，將其代入目標(biāo)函數(shù)，使得目標(biāo)函數(shù)值最大的點(diǎn)就是最優(yōu)解。考察例1的情形。25整理ppt單純形法的指導(dǎo)思想是，不需要考察和計算所有頂點(diǎn)，如存在最優(yōu)解，可以任意頂點(diǎn)為起點(diǎn)，求出初始解，然后轉(zhuǎn)到相鄰頂點(diǎn)，看目標(biāo)函數(shù)值是否有改善。利用單純形法解決線性規(guī)劃問題，實(shí)際上是從線性規(guī)劃問題的一個基本可行解轉(zhuǎn)移到另一個基本可行解，同時目標(biāo)函數(shù)值不減少的過程。對于兩個變量的線性規(guī)劃問題，就是從可行域的一個端點(diǎn)轉(zhuǎn)移到另一個端點(diǎn)，而使得目標(biāo)函數(shù)的值不減少。26整理ppt線性規(guī)劃的擴(kuò)展一、整數(shù)規(guī)劃（整數(shù)線性規(guī)劃）：部分或全部的決策變量只能取整數(shù)值。例1轉(zhuǎn)變成整數(shù)規(guī)劃情形27整理ppt二、0－1規(guī)劃：變量的取值被限定為0或1，可以看成是整數(shù)