第二章線性規(guī)劃的圖解法(簡(jiǎn))

1、第二章第二章線性規(guī)劃的圖解法線性規(guī)劃的圖解法 主要內(nèi)容： 1 問題的提出 （什么是線性規(guī)劃）2 圖解法3 圖解法的靈敏度分析重點(diǎn)和難點(diǎn)o 重點(diǎn)：重點(diǎn)： （1）線性規(guī)劃問題的主要概念）線性規(guī)劃問題的主要概念 （2）線性規(guī)劃問題的數(shù)學(xué)模型）線性規(guī)劃問題的數(shù)學(xué)模型 （3）線性規(guī)劃圖解法的過程）線性規(guī)劃圖解法的過程 （4）陰影價(jià)格的定義和靈敏度分析）陰影價(jià)格的定義和靈敏度分析o 難點(diǎn)：難點(diǎn)： 靈敏度分析靈敏度分析第一節(jié) 問題的提出 線性規(guī)劃是運(yùn)籌學(xué)最成熟的一個(gè)分支。開始是在生產(chǎn)組織管理和制定交通運(yùn)輸方案方面，后來波及更廣的范圍，小到一個(gè)班組的計(jì)劃安排，大至整個(gè)部門，以至國(guó)民經(jīng)濟(jì)計(jì)劃的最優(yōu)化方案分析，它

2、都有用武之地。 第一節(jié) 問題的提出1線性規(guī)劃的典型應(yīng)用 合理利用線材問題 配料問題 投資問題 產(chǎn)品生產(chǎn)計(jì)劃 勞動(dòng)力安排 運(yùn)輸問題第一節(jié) 問題的提出例例1 1某工廠在計(jì)劃期內(nèi)要安排某工廠在計(jì)劃期內(nèi)要安排I I、兩種產(chǎn)品的生產(chǎn)兩種產(chǎn)品的生產(chǎn), ,已知生已知生產(chǎn)單位產(chǎn)品所得的設(shè)備臺(tái)時(shí)及、產(chǎn)單位產(chǎn)品所得的設(shè)備臺(tái)時(shí)及、B B兩種原材料的消耗，以兩種原材料的消耗，以及資源的限制如表所示。該工廠每生產(chǎn)一單位產(chǎn)品及資源的限制如表所示。該工廠每生產(chǎn)一單位產(chǎn)品I I可獲利可獲利5050元，每生產(chǎn)一單位產(chǎn)品元，每生產(chǎn)一單位產(chǎn)品可獲利可獲利100100元，問工廠應(yīng)分別生元，問工廠應(yīng)分別生產(chǎn)多少個(gè)產(chǎn)多少個(gè)I I產(chǎn)品和產(chǎn)

3、品和產(chǎn)品才能使工廠獲利最多產(chǎn)品才能使工廠獲利最多? ?III資源限制設(shè)備11300臺(tái)時(shí)原料A21400kg原料B01250kg第一節(jié) 問題的提出這個(gè)問題可以用以下的數(shù)學(xué)模型來加以描述。這個(gè)問題可以用以下的數(shù)學(xué)模型來加以描述。 x x1 1生產(chǎn)生產(chǎn)I I產(chǎn)品的數(shù)量產(chǎn)品的數(shù)量 x x2 2= =生產(chǎn)生產(chǎn)產(chǎn)品的數(shù)量。產(chǎn)品的數(shù)量。決策變量（Decision variables） 第一節(jié) 問題的提出數(shù)學(xué)模型：數(shù)學(xué)模型：目標(biāo)函數(shù)：目標(biāo)函數(shù)：MAX Z=50XMAX Z=50X1 1 +100X +100X2 2滿足約束條件：滿足約束條件： X X1 1+X+X2 2 300 300 2X 2X1 1+X+

4、X2 2 400 400 X X 250250 X X1 1、X X2 2 0 0第一節(jié) 問題的提出 、數(shù)學(xué)模型的目標(biāo)函數(shù)為變量的線性函數(shù)，、數(shù)學(xué)模型的目標(biāo)函數(shù)為變量的線性函數(shù)，約束條件也為變量的約束條件也為變量的線性等式或不等式線性等式或不等式，故此，故此模型稱之為模型稱之為線性規(guī)劃線性規(guī)劃。 、如果目標(biāo)函數(shù)是變量的非線性函數(shù)，或約、如果目標(biāo)函數(shù)是變量的非線性函數(shù)，或約束條件中含有變量非線性的等式或不等式的數(shù)束條件中含有變量非線性的等式或不等式的數(shù)學(xué)模型則稱之為學(xué)模型則稱之為非線性規(guī)劃非線性規(guī)劃。第一節(jié) 問題的提出 、把滿足所有約束條件的解稱為該線性規(guī)劃、把滿足所有約束條件的解稱為該線性規(guī)劃

5、的的可行解可行解。、把使得目標(biāo)函數(shù)值最大、把使得目標(biāo)函數(shù)值最大( (即利潤(rùn)最大即利潤(rùn)最大) )的可行的可行解稱為該線性規(guī)劃的解稱為該線性規(guī)劃的最優(yōu)解最優(yōu)解，此目標(biāo)函數(shù)值稱，此目標(biāo)函數(shù)值稱為最優(yōu)為最優(yōu)目標(biāo)函數(shù)值目標(biāo)函數(shù)值，簡(jiǎn)稱，簡(jiǎn)稱最優(yōu)值最優(yōu)值。第一節(jié) 問題的提出建立線性規(guī)劃問題數(shù)學(xué)模型的步驟：建立線性規(guī)劃問題數(shù)學(xué)模型的步驟：、定義決策變量定義決策變量，每個(gè)問題都用一組決策變量（，每個(gè)問題都用一組決策變量（X X1 1X X2 2X X3 3XXN N）表示某一方案；這組決策變量的值就代）表示某一方案；這組決策變量的值就代表一個(gè)具體方案，一般這些變量的取值是非負(fù)的表一個(gè)具體方案，一般這些變量的取

6、值是非負(fù)的 、用決策變量的線性函數(shù)形式寫出所要追求的目標(biāo)，稱、用決策變量的線性函數(shù)形式寫出所要追求的目標(biāo)，稱之為之為目標(biāo)函數(shù)目標(biāo)函數(shù)。 具有上述具有上述3 3個(gè)特征的問題為個(gè)特征的問題為線性規(guī)劃問題。線性規(guī)劃問題。第一節(jié) 問題的提出 我們的任務(wù)就是要選擇一組或多組方案，使目我們的任務(wù)就是要選擇一組或多組方案，使目標(biāo)函數(shù)值最大或最小。從選擇方案的角度說，標(biāo)函數(shù)值最大或最小。從選擇方案的角度說，這是規(guī)劃問題。從使目標(biāo)函數(shù)值最大或最小的這是規(guī)劃問題。從使目標(biāo)函數(shù)值最大或最小的角度說，就是優(yōu)化問題。角度說，就是優(yōu)化問題。線性規(guī)劃數(shù)學(xué)模型的一般表示方式線性規(guī)劃數(shù)學(xué)模型的一般表示方式技術(shù)系數(shù)右端項(xiàng)價(jià)值系數(shù)

7、線性規(guī)劃問題的規(guī)模約束行數(shù)變量個(gè)數(shù): ;: ;: ;: ;:0,),(),(),(.)(max(min)21221122222121112121112211ijjjnmnmnmmnnnnnnabcmnmnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxf思考題 某公司由于生產(chǎn)需要，共需要，B兩種原料至少350噸(A，B兩種材料有一定替代性)，其中A原料至少購(gòu)進(jìn)125噸。但由于A，B兩種原料的規(guī)格不同，各自所需的加工時(shí)間也是不同的，加工每噸A原料需要2個(gè)小時(shí)，加工每噸B原料需要1小時(shí)，而公司總共有600個(gè)加工小時(shí)。又知道每噸A原料的價(jià)格為2萬元，每噸B原料的價(jià)格為3萬元試問在滿

8、足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購(gòu)買A、B兩種原料，使得購(gòu)進(jìn)成本最低?解：設(shè)X1為購(gòu)進(jìn)原料A的噸數(shù)，X2為購(gòu)進(jìn)原料B的噸數(shù)。第二節(jié) 圖解法Z=27500例1的數(shù)學(xué)模型：目標(biāo)函數(shù)：MAX Z=50X1 +100X2約束條件：X1+X2300 2X1+X2400 X 250 X1、X2 0可行解可行解可行域可行域等值線等值線第二節(jié) 圖解法 這樣就得到了例1的最優(yōu)解B點(diǎn)，B點(diǎn)的坐標(biāo)為(50，250)，因此最佳決策為X1=50，X2=250,此時(shí)Z27500這說明該廠的最優(yōu)生產(chǎn)計(jì)劃方案是生產(chǎn)I產(chǎn)品50單位，生產(chǎn)產(chǎn)品250單位，可得最大利潤(rùn)27500元。 把X1=50，X2=250代入約

9、束條件得： 1*(50)+1*(250)300臺(tái)時(shí)設(shè)備 2*(50)+l*(250)=350千克原料A， 1*(250)250千克原料B第二節(jié) 圖解法 在線性規(guī)劃中，對(duì)一個(gè)約束條件中沒使用的資源或能力的大小稱在線性規(guī)劃中，對(duì)一個(gè)約束條件中沒使用的資源或能力的大小稱之為之為松弛量松弛量。記為記為Si Si。第二節(jié) 圖解法 像這樣把所有的約束條件都寫成等式，稱為線性規(guī)劃模型的標(biāo)準(zhǔn)化，所得結(jié)果稱為線性規(guī)劃的標(biāo)準(zhǔn)形式。第二節(jié) 圖解法同樣對(duì)于約束條件中，可以增加一些代表最低限約束的超過量，稱之為剩余變量，把約束條件變?yōu)榈仁郊s束條件，加了松弛變量與剩余變量后，思考題的數(shù)學(xué)模型為：線性規(guī)劃問題的幾個(gè)特點(diǎn)：o

10、 線性規(guī)劃問題的可行解的集合是凸集o 線性規(guī)劃問題的基礎(chǔ)可行解一般都對(duì)應(yīng)于凸集的極點(diǎn)o 凸集的極點(diǎn)的個(gè)數(shù)是有限的o 最優(yōu)解只可能在凸集的極點(diǎn)上，而不可能發(fā)生在凸集的內(nèi)部第三節(jié) 圖解法的靈敏度分析“心有靈犀一點(diǎn)通”靈敏度分析又稱為后優(yōu)化分析Post-optimization Analysis第三節(jié) 圖解法的靈敏度分析o 線性規(guī)劃是靜態(tài)模型o 參數(shù)發(fā)生變化，原問題的最優(yōu)解還是不是最優(yōu)o 哪些參數(shù)容易發(fā)生變化n C, b, Ao 每個(gè)參數(shù)發(fā)生多大的變化不會(huì)破壞最優(yōu)解o 靈敏度越小，表示解的穩(wěn)定性越好。第三節(jié) 圖解法的靈敏度分析 所謂所謂靈敏度分析靈敏度分析就是在建立數(shù)學(xué)模型和就是在建立數(shù)學(xué)模型和求得

11、最優(yōu)解之后，研究線性規(guī)劃的一些系求得最優(yōu)解之后，研究線性規(guī)劃的一些系數(shù)數(shù)C Ci i、a aij ij、b bj j變化時(shí)，對(duì)最優(yōu)解產(chǎn)生什么影變化時(shí)，對(duì)最優(yōu)解產(chǎn)生什么影響響? ?第三節(jié) 圖解法的靈敏度分析 靈敏度分析的作用：1、Ci、aij、bj這些系數(shù)都是估計(jì)值和預(yù)測(cè)值，不一定非常精確。2、即使這些系數(shù)值在某一時(shí)刻是精確值，它們也會(huì)隨著市場(chǎng)條件的變化而變化。有了靈敏度分析就不必為了應(yīng)付這些變化而不停地建立新的模型和求其新的最優(yōu)解，也不會(huì)由于系數(shù)的估計(jì)和預(yù)測(cè)的精確性而對(duì)所求得的最優(yōu)解存有不必要的懷疑。第三節(jié) 圖解法的靈敏度分析一、目標(biāo)函數(shù)中的系數(shù)i的靈敏度分析 例1中生產(chǎn)一個(gè)單位的I產(chǎn)品可以獲

12、利50元(C150)，生產(chǎn)一個(gè)單位的產(chǎn)品可以獲利100元(C2100)。在目前的生產(chǎn)條件下求得生產(chǎn)I產(chǎn)品50單位生產(chǎn)產(chǎn)品250單位可以獲得最大利潤(rùn)。當(dāng)I、產(chǎn)品中的某一產(chǎn)品的單位利潤(rùn)增加或減少時(shí)，為了獲取最大利潤(rùn)就應(yīng)該增加或減少這一產(chǎn)品的產(chǎn)量，也就是改變最優(yōu)解。3.1 目標(biāo)函數(shù)中的系數(shù)Ci的靈敏度分析 目標(biāo)函數(shù)的斜率在直線E(設(shè)備約束條件)的斜率與直線F(原料B的約束條件)的斜率之間變化時(shí)，坐標(biāo)X150，X2250的頂點(diǎn)B仍然是最優(yōu)解。如果目標(biāo)函數(shù)的直線反時(shí)針旋轉(zhuǎn)，當(dāng)目標(biāo)函數(shù)的斜率等于直線F的斜率時(shí)，則可知直線AB上的任一點(diǎn)都是其最優(yōu)解。如果繼續(xù)反針旋轉(zhuǎn)，則可知A點(diǎn)為其最優(yōu)解。3.1 目標(biāo)函數(shù)中

13、的系數(shù)Ci的靈敏度分析 如果目標(biāo)函數(shù)直線順時(shí)針方向旋轉(zhuǎn)，當(dāng)目標(biāo)函效的斜率等于直線E的斜率時(shí)，則可知直線BC上的任一點(diǎn)都是其最優(yōu)解。如果繼續(xù)順時(shí)針方向旋轉(zhuǎn)，當(dāng)目標(biāo)函數(shù)的斜率在直線E的斜率與直線G的斜率之間，則頂點(diǎn)C為其最優(yōu)解。3.1 目標(biāo)函數(shù)中的系數(shù)Ci的靈敏度分析The 100 percent rule百分之百法則百分之百法則目標(biāo)函數(shù)系數(shù)同時(shí)變動(dòng)的百分之百法則目標(biāo)函數(shù)系數(shù)同時(shí)變動(dòng)的百分之百法則(The 100 percent rule for simultaneous changes in objective function coefficients)：如果目標(biāo)函數(shù)的系數(shù)同時(shí)變動(dòng)，計(jì)算出每一

14、系數(shù)變動(dòng)量占該系數(shù)最優(yōu)域允許變動(dòng)量的百分比，而后，將各個(gè)系數(shù)的變動(dòng)百分比相加，如果所得的和不超過百分之一百，最優(yōu)解不會(huì)改變，如果超過百分之一百，則不能確定最優(yōu)解是否改變。 3.2 約束條件中右邊系數(shù)bj的靈敏度分析3.2 約束條件中右邊系數(shù)bj的靈敏度分析在約束條件右邊常量增加一個(gè)單位而在約束條件右邊常量增加一個(gè)單位而使最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)的數(shù)量稱之為使最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)的數(shù)量稱之為這個(gè)約束條件的這個(gè)約束條件的對(duì)偶價(jià)格對(duì)偶價(jià)格。3.2 約束條件中右邊系數(shù)bj的靈敏度分析第三節(jié) 圖解法的靈敏度分析 在目標(biāo)函數(shù)求最大值的情況下，除了對(duì)偶價(jià)格大于零、等于零的情況外，還存在著對(duì)偶價(jià)格小于零的情況

15、。當(dāng)某約束條件對(duì)偶價(jià)格小于零時(shí)，約束條件右邊常數(shù)增加一個(gè)單位，就使得最優(yōu)目標(biāo)函數(shù)值減少一個(gè)其對(duì)偶價(jià)格。第三節(jié) 圖解法的靈敏度分析 對(duì)目標(biāo)函數(shù)值求最小值的情況下，當(dāng)對(duì)偶價(jià)格大于零時(shí)，約束條件右邊常數(shù)增加一個(gè)單位就使其最優(yōu)目標(biāo)函數(shù)值減少一個(gè)其對(duì)偶價(jià)格；當(dāng)對(duì)偶價(jià)格等于零時(shí)，約束條件右邊常數(shù)增加一個(gè)單位，并不影響其最優(yōu)目標(biāo)函數(shù)值；當(dāng)對(duì)偶價(jià)格小于零時(shí)，約束條件右邊常數(shù)增加一個(gè)單位，就使得其最憂目標(biāo)函數(shù)值增加一個(gè)其對(duì)偶價(jià)格。第三節(jié) 圖解法的靈敏度分析 當(dāng)約束條件右邊常數(shù)增加個(gè)單位時(shí)：1.如果對(duì)偶價(jià)格大于零，則其最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)，即求最大值時(shí)變得更大；求最小值時(shí)，變得更小。2.如果對(duì)偶價(jià)格小于零，則其最優(yōu)目標(biāo)函數(shù)值變大，即求最大值時(shí)，變得小了；求最小值時(shí)變得大了。3.如果對(duì)偶價(jià)格等于零，則其最優(yōu)目標(biāo)函數(shù)值不變。習(xí)題一、一、Excelo Excel 的線性規(guī)劃的線性規(guī)劃二、二、WinQSBo QSB-Quantitative System for Business 作業(yè)：Specific Motors公司汽車模型生產(chǎn)問題o Specific Motors公司生產(chǎn)三種類型的汽車，型號(hào)分別為X、Y和Z。三種產(chǎn)品的凈收入分別