【正文】 ? A2+B2+C2≥10,000 ? 非負(fù)約束： ? Ai， Bi， Ci≥0 (i=1,2) 第三章 線性規(guī)劃 第三章 線性規(guī)劃 ? 線性規(guī)劃問題概述 ? 線性規(guī)劃問題的圖解法 ? 單純形法 ? 對(duì)偶問題 ? 敏感性分析 第三章 線性規(guī)劃 ? 圖解法的過程介紹 ? 規(guī)劃問題求解的幾種可能結(jié)果 ? 圖解法延伸 第三章 線性規(guī)劃 圖解法的過程介紹 ?花瓶問題 ? 目標(biāo)函數(shù) max z =12B+10S ? 材料約束 2B+S≤160 （ 1） ? 時(shí)間約束 1/3B+1/3S≤40 （ 2） ? 儲(chǔ)存約束 3B+2S≤260 （ 3） ? 非負(fù)約束 B≥0, S≥0 第三章 線性規(guī)劃 直線把圖分為兩部分，直線上方的點(diǎn)都不符合約束條件， 而直線上和直線下方的點(diǎn)都滿足約束條件。 第三章 線性規(guī)劃 最優(yōu)解為： ?B=20, S=100 將 B和 S值代入目標(biāo)函數(shù)中得： ?Z=12 20+10 100=1240 所以最大利潤值是 1240。 第三章 線性規(guī)劃 圖解法的步驟： ? 其中一個(gè)變量作為橫坐標(biāo)軸，另一個(gè)變量作為縱坐標(biāo)軸，畫出平面直角坐標(biāo)系，并適當(dāng)選取單位坐標(biāo)長度，由于變量是非負(fù)的，因此，畫出坐標(biāo)系的第一象限即可。 ? 出各約束條件在坐標(biāo)軸上對(duì)應(yīng)的直線，找出可行域（常用陰影區(qū)域標(biāo)識(shí)）。 ? 圖標(biāo)目標(biāo)函數(shù)， z是一個(gè)待求的目標(biāo)函數(shù)值。目標(biāo)函數(shù)常用一組平行虛線表示，離坐標(biāo)原點(diǎn)越遠(yuǎn)的虛線表示的目標(biāo)函數(shù)值越大。 ? 確定最優(yōu)解。因?yàn)樽顑?yōu)解是可行域中使目標(biāo)函數(shù)值達(dá)到最優(yōu)的點(diǎn)，當(dāng)目標(biāo)函數(shù)直線由原點(diǎn)開始向右上方移動(dòng)時(shí)， z值開始增大，一直移到目標(biāo)函數(shù)直線與可行域相切時(shí)為止，切點(diǎn)就是最優(yōu)解的點(diǎn)。 第三章 線性規(guī)劃 ?無窮多最優(yōu)解 ?無界解 ?無解或者無可行解 第三章 線性規(guī)劃 ?圖解法的解體方法和幾何判斷對(duì)于求解一般的線性規(guī)劃問題有很大啟發(fā)： ? 性規(guī)劃問題的解的情況有以下幾種：唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解。 ? 線性規(guī)劃問題有解，那么可行域是凸集。 ? 規(guī)劃問題優(yōu)解存在，那么唯一最優(yōu)解一定是可行域凸集的某個(gè)頂點(diǎn)；無窮最優(yōu)解一定是可行域的某個(gè)邊或某個(gè)面。 ? 規(guī)劃問題的一般解體思路：先找出凸集的任一頂點(diǎn)，計(jì)算該點(diǎn)處目標(biāo)函數(shù)值，與周圍相鄰頂點(diǎn)處的目標(biāo)函數(shù)值相比較，如果該點(diǎn)值最大，那么該點(diǎn)就是最優(yōu)解或者最優(yōu)解之一；如果不是，那么就對(duì)目標(biāo)函數(shù)值比該點(diǎn)大的另一點(diǎn)重復(fù)此過程，直到找出最優(yōu)解。 第三章 線性規(guī)劃 ? 實(shí)例分析： ? 某工廠生產(chǎn) A,B兩種產(chǎn)品，分別經(jīng)過三道工序，已知建立的模型如下所示，可行域?yàn)橥苟噙呅?OACDB, 試以圖解法求解最優(yōu)生產(chǎn)方案。 ? 目標(biāo)函數(shù) max z =20A+30B ? 工序一約束 2A+B≤ 40 ? 工序二約束 A+2B≤ 40 ? 工序三約束 A+B≤ 25 ? 非負(fù)約束 A≥ 0, B≥ 0 第三章 線性規(guī)劃 第三章 線性規(guī)劃 ?A+2B=40 工序二約束 ?A+B=25 工序三約束 ?聯(lián)立以上方程，可以求得最優(yōu)解 ?A=10, B=15 ?代入目標(biāo)函數(shù)，求得最大目標(biāo)函數(shù)值為20*10+30*15=650。 第三章 線性規(guī)劃 第三章 線性規(guī)劃 ? 線性規(guī)劃問題概述 ? 線性規(guī)劃問題的圖解法 ? 單純形法 ? 對(duì)偶問題 ? 敏感性分析 第三章 線性規(guī)劃 單純形法 ? 線性規(guī)劃問題的標(biāo)準(zhǔn)形式 ? 線性規(guī)劃問題解的概念和基本定理 ? 單純形法解題步驟 第三章 線性規(guī)劃 ?規(guī)定線性規(guī)劃問題的一般形式： ?目標(biāo)函數(shù) ?約束條件 （ i =1,……m ） ?非負(fù)約束 0 ( j =1,……,n) ??? njjj xcz1m a xjnjjji bxa ???1jx ?第三章 線性規(guī)劃 轉(zhuǎn)化為標(biāo)準(zhǔn)形式方法： ? 如果模型的目標(biāo)函數(shù)為極小值： ，那么令 z’=z , 。 ? 如果右端項(xiàng) bi小于零，等式兩端同時(shí)乘以 1 。 ? 約束條件一般情況下是不等式。例如： x1+x2≤6, 令 x3=6x1x2 ， x3 ≥0，將約束條件轉(zhuǎn)化為 x1+x2+x3=6 ， x3稱作松弛變量。如果有 x1+x2≥6 ,令 x4=6x1x2 , x4≥0，約束條件轉(zhuǎn)化為 x1+x2x4=6， x4稱作剩余變量。 ? 變量取值可能無約束。決策變量可以大于或等于零，也可以小于零。此時(shí)令xj=xj’xj’’, xj’≥0, xj’’≥0, 將其代入線性規(guī)劃模型。 ? 決策變量小于等于零 , 即 xj≤0。令 xj’=xj , 將 xj’代入線性規(guī)劃模型。 ??? nj jj xcz 1mi n第三章 線性規(guī)劃 ?目標(biāo)函數(shù) ?約束條件 （ i =1,……m ） ?非負(fù)約束 xj 0 ( j =1,……,n) ??? njjj xcz1m a xinjjji bxa ???1?第三章 線性規(guī)劃 ?可行解：滿足約束條件的解為可行解，全部可行解的集合為可行域。 ?最優(yōu)解：使目標(biāo)函數(shù)值達(dá)到最大的可行解為最優(yōu)解。 ?定理一 ： 若線性規(guī)劃問題存在可行解，則問題的可行域?yàn)橥辜? ?定理二 ： 線性規(guī)劃問題的基可行解對(duì)應(yīng)于線性規(guī)劃問題可行域的頂點(diǎn)。 ?定理三 ：若線性規(guī)劃問題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解。 第三章 線性規(guī)劃 ?已知模型如下： ?目標(biāo)函數(shù) max z =20A+30B ?工序一約束 2A+B≤40 ?工序二約束 A+2B≤40 ?工序三約束 A+B≤25 ?非負(fù)約束 A≥0, B≥0 第三章 線性規(guī)劃 ?，引入三個(gè)松弛變量： C、 D、 E ?原問題轉(zhuǎn)變?yōu)槿缦滦问剑? max z =20A+30B+0C+0D+0E 2A+B+C=40 A+2B+D=40 A+B+E=25 A≥0, B≥0,C≥0,D≥0,E≥0 第三章 線性規(guī)劃 ?約束條件的系數(shù)矩陣為： ? U=(P1 ,P2 ,P3 ,P4 ,P5) = ? P3= ， P4= ， P5= 三個(gè)向量是線性無關(guān)的 ? 這些向量構(gòu)成基矩陣： V=(P3, P4, P5 ) = ??????????100110102100112??????????001??????????010??????????100??????????100010001第三章 線性規(guī)劃 ? 對(duì)應(yīng)于 V的變量為基變量，他們分別為： C=402AB D=40A2B E=25AB ? 將上述基變量代入目標(biāo)函數(shù)中，得到： Z=20A+30B+0 當(dāng)還未生產(chǎn)時(shí)， A=B=0，資源未被利用。取 C=40 ,D=40 ,E=25，利潤值還未產(chǎn)生， 得到初始基本可行解： X(0) =(0， 0， 40， 40， 25)。 第三章 線性規(guī)劃 ? B的取值滿足： C=402AB≥0 D=40A2B≥0 E=25AB≥0 ? 因?yàn)?A=0,所以有： C=40B≥0 D=402B≥0 E=25B≥0 ? B的取值要求滿足上述三式，因此 B為 : ? B=min {40/1 ,40/2 ,25/1} =20 第三章 線性規(guī)劃 ? 現(xiàn)在知道， A=0 ,B=20 ,將其代入三個(gè)約束條件中， 2A+B+C=40 A+2B+D=40 A+B+E=25 ? 得到一組新的解： X(1)=(0， 20， 20， 0， 5) ? 將上面三式變形，得到下式： C+B=403/2A (1) 2B=40AD (2) E+B=25A (3) 第三章 線性規(guī)劃 ? 將其進(jìn)行轉(zhuǎn)化， (1)1/2*(2)， (2)/2， (3)(2)/2，上述三式又變?yōu)椋? C=203/2A (4) B=201/2A1/2D (5) E=51/2A+1/2D (6) ? 將上述三式代入目標(biāo)函數(shù)式中， Z=600+5A15D V=(C, B, E) = ??????????100010001第三章 線性規(guī)劃 ? 根據(jù) (4)、 (5)、 (6)式可以得到新的約束方程的系數(shù)矩陣： ? U= ? 從目標(biāo)表達(dá)式 Z=600+5A15D上看， A的系數(shù)式正值，說明增加 A的產(chǎn)量仍然可以提高利潤， A的取值滿足： ? C=203/2A≥0 ? B=201/2A1/2D≥0 ? E=51/2A+1/2D≥0 ????????????12100211210021001023第三章 線性規(guī)劃 ? 由于 D=0，可得： C=203/2A≥0 B=201/2A≥0 E=51/2A≥0 ? A要求滿足上述三式，因此 A=min { 20/, 20/, 5/}=10 ? A變?yōu)榛兞浚?E變?yōu)榉腔兞?，?A=10, E=0代入三個(gè)約束條件中： 2A+B+C=40 A+2B+D=40 A+B+E=25 ? 通過求解可得： B=15, C=5, D=0 第三章 線性規(guī)劃 ? 新的基本可行解為： X(2)=(10， 15， 5， 0， 0)。 ? 用 A置換 E，得到： C+3/2A=20 B+1/2A=201/2D 1/2A=5+1/2DE ? 經(jīng)變形得到下面三個(gè)新的式子： C=53/2D+3E B=15D+E A=10+D2E 第三章 線性規(guī)劃 ?將上述三式帶入目標(biāo)函數(shù) Z=65010D10E ?從上式可以看出， D、 E系數(shù)皆為負(fù)，如果這些變量值增加，將導(dǎo)致目標(biāo)函數(shù)值的減少。因此最佳生產(chǎn)方案為： X(2)=(10， 15， 5， 0， 0) 最大利潤值為： Z=650 第三章 線性規(guī)劃 ?例 Keku公司一直開始從事汽車零配件的設(shè)計(jì)、生產(chǎn)，最近公司設(shè)計(jì)了兩種新型改良產(chǎn)品 (產(chǎn)品 I和 II)。根據(jù)以往新產(chǎn)品上市的經(jīng)驗(yàn)和市場(chǎng)行情， Keku公司預(yù)計(jì)每生產(chǎn)一件產(chǎn)品 I可獲利 2元，每生產(chǎn)一件產(chǎn)品 II可獲利 3元。公司準(zhǔn)備利用現(xiàn)有的生產(chǎn)資源，在計(jì)劃期內(nèi)安排生產(chǎn) I、 II兩種新產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及 A、 B兩種原材料的消耗，如下表所示。 第三章 線性規(guī)劃 I II 設(shè) 備 1 2 8臺(tái)時(shí) 原材料 A 4 0 16m3 原材料 B 0 4 12kg 站在 Keku公司的立場(chǎng)想知道如何安排生產(chǎn)才能獲利最多？ 用單純形法對(duì)它進(jìn)行求解。 第三章 線性規(guī)劃 ?分別設(shè) 、 表示在計(jì)劃期內(nèi)產(chǎn)品 I、 II的產(chǎn)量，建立該問題的數(shù)學(xué)模型為： 21 32m a x xxz ??????????????0,12416482212121xxxxxx第三章 線性規(guī)劃 ?