最新-第三章：線性規(guī)劃數(shù)學模型【課件】-PPT

1、第三章 線性規(guī)劃線性規(guī)劃（Linear Programming,LP）是運籌學中研究較早、理論成熟的重要分支之一，網(wǎng)絡規(guī)劃、整數(shù)規(guī)劃、目標規(guī)劃和多目標規(guī)劃都是以線性規(guī)劃為基礎的。在公共管理和工商管理中都有廣泛的應用。解決稀缺資源最優(yōu)分配的有效方法，使付出的費用最小或獲得的收益最大。公共交通、垃圾清理、提供服務成本最小問題；救災搶險、消防滅火、制止犯罪的最快反應問題；控制污染、能源規(guī)劃、經(jīng)濟布局的最優(yōu)化問題，等等。1馮諾伊曼(Von Neuman)和摩根斯坦(Morgenstern)1944年發(fā)表的 博弈論與經(jīng)濟行為涉及與線性規(guī)劃等價的對策問題及線性規(guī)劃對偶理論從1964年諾貝爾獎設經(jīng)濟學獎后，

2、到1992年28年間的32名獲獎者中有13人(40%)從事過與線性規(guī)劃有關的研究工作，其中比較著名的還有Simon，Samullson，Leontief，Arrow，Miller等2研究對象有一定的人力、財力、資源條件下，如何合理安排使用，效益最高某項任務確定后，如何安排人、財、物，使之最省3線性規(guī)劃模型是通過對實際問題的分析而建立的表示決策變量、最優(yōu)目標和約束條件之間關系的一組數(shù)學關系式，由決策變量、目標函數(shù)和約束條件三部分組成。在滿足一組約束條件下，求一組決策變量的值，使目標函數(shù)達到最優(yōu)。4線性規(guī)劃的特點決策變量連續(xù)性：求解出的決策變量值可以是整數(shù)、小數(shù)；線性函數(shù)：目標函數(shù)方程和約束條件方

3、程都是線性方程；單目標：目標函數(shù)是單目標，只有一個極大值或一個極小值；確定性：只能應用于確定型決策問題。5 A B 備用資源 煤 1 2 30 勞動日 3 2 60 倉庫 0 2 24 利潤 40 50例1、生產(chǎn)計劃問題A, B各生產(chǎn)多少, 可獲最大利潤?6 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0 max Z= 40 x1 +50 x2解:設產(chǎn)品A, B產(chǎn)量分別為變量x1 ， x27例2求：最低成本的原料混合方案 原料 A B 每單位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8 每單位添 加劑中維生 12 14 8

4、 素最低含量8解：設每單位添加劑中原料i的用量為xi(i =1,2,3,4)minZ= 2x1 + 5x2 +6x3+8x4 4x1 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14 2x2 + x3+3x4 8 xi 0 (i =1,4)9一般式Max(min)Z=C1X1+ C2X2+CnXna11X1+ a12X2+ a1nXn (=, )b1a21X1+ a22X2+ a2nXn (=, )b2 am1X1+ am2X2+ amnXn (=, )bmXj 0(j=1,n)10要解決的問題的目標可以用數(shù)值指標反映對于要實現(xiàn)的目標有多種方案可選擇有影響決策的若干約

5、束條件11 圖解法AX=b (1)X 0 (2)maxZ=CX (3)定義1：滿足約束(1)、(2)的X=(X1 Xn)T稱為LP問題的可行解，全部可行解的集合稱為可行域。定義2：滿足(3)的可行解稱為LP問題的最優(yōu)解12例1、maxZ=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 013解：(1)、確定可行域 X1 0 X1 =0 (縱) X2 0 X2=0 (橫) X1+2X2 30 X1+2X2 =30 (0,15) (30,0)2030100102030X2DABC3X1+2X2 =60(0,30) (20,0) 2X2 =2414(2)、

6、求最優(yōu)解解：X* = (15,7.5) Zmax =975Z=40X1+50X20=40X1+50X2 (0,0)， (10,-8)C點： X1+2X2 =30 3X1+2X2 =600203010102030X1X2DABC15例2、 maxZ=40X1+ 80X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0160Z= 40 X1 + 80X2 =0 X1 + 2X2 =30DABCX2X1最優(yōu)解：BC線段B點 C點X(1)=(6,12) X(2)=(15,7.5)X= X(1)+(1-) X(2) (0 1)求解17X1 =6+ +(1- )15X2=12+

7、+(1- )7.5X1 =15-9X2 =7.5+4.5 (0 1)X= = +(1- )maxZ=1200 X1 6 15 X2 12 7.518無界無有限最優(yōu)解例3、 maxZ=2X1+ 4X2 2X1+X2 8-2X1+X2 2X1 , X2 0Z=02X1+ X2=8-2X1+ X2=28246X240X119例4、 maxZ=3X1+2X2 -X1 -X2 1X1 , X2 0無解無可行解-1X2-1X1020總結 唯一解 無窮多解 無有限最優(yōu)解 無可行解有解無解21單純形法單純形法（Simplex Method）是美國數(shù)學家但澤（Dantzig）于1947年提出的?；舅枷胧峭ㄟ^有

8、限次的換基迭代來求出線性規(guī)劃的最優(yōu)解。22兩個變量的LP問題的解： 可行域為凸多邊形（凸集）X(1)X(2)凸多邊形凹多邊形X(1)X(2)23頂點原理頂點（極點） 凸集中滿足一下條件的點：凸集中通過任意兩個點的直線上都不包含此點作為內點，它只能是凸集的端點。頂點原理 由于線性規(guī)劃問題的可行域都是凸集，如果存在最優(yōu)解，必然對應于可行域凸集的至少一個頂點；如果只有一個最優(yōu)解，它必然對應于一個頂點；如果存在多個最優(yōu)解，它們必然相鄰。24頂點原理的運用頂點原理證明，如果線性規(guī)劃的最優(yōu)解存在，要找到最優(yōu)解，只要找到可行域凸集頂點的坐標，將其代入目標函數(shù)，使得目標函數(shù)值最大的點就是最優(yōu)解。考察例1的情形

9、。25單純形法的指導思想是，不需要考察和計算所有頂點，如存在最優(yōu)解，可以任意頂點為起點，求出初始解，然后轉到相鄰頂點，看目標函數(shù)值是否有改善。利用單純形法解決線性規(guī)劃問題，實際上是從線性規(guī)劃問題的一個基本可行解轉移到另一個基本可行解，同時目標函數(shù)值不減少的過程。對于兩個變量的線性規(guī)劃問題，就是從可行域的一個端點轉移到另一個端點，而使得目標函數(shù)的值不減少。26線性規(guī)劃的擴展一、整數(shù)規(guī)劃（整數(shù)線性規(guī)劃）：部分或全部的決策變量只能取整數(shù)值。例1轉變成整數(shù)規(guī)劃情形27二、01規(guī)劃： 變量的取值被限定為0或1，可以看成是整數(shù)規(guī)劃的擴展。 例2：某市擬建設若干公共圖書館，經(jīng)過調研得到相關數(shù)據(jù)如下表?，F(xiàn)財政預算不超過2