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

第二章

線性規(guī)劃的圖解法

主要內(nèi)容：

§1問題的提出（什么是線性規(guī)劃）§2圖解法§3圖解法的靈敏度分析重點(diǎn)和難點(diǎn)重點(diǎn)：（1）線性規(guī)劃問題的主要概念（2）線性規(guī)劃問題的數(shù)學(xué)模型（3）線性規(guī)劃圖解法的過程（4）陰影價(jià)格的定義和靈敏度分析難點(diǎn)：靈敏度分析第一節(jié)問題的提出

線性規(guī)劃是運(yùn)籌學(xué)最成熟的一個(gè)分支。開始是在生產(chǎn)組織管理和制定交通運(yùn)輸方案方面，后來波及更廣的范圍，小到一個(gè)班組的計(jì)劃安排，大至整個(gè)部門，以至國民經(jīng)濟(jì)計(jì)劃的最優(yōu)化方案分析，它都有用武之地。第一節(jié)問題的提出1．線性規(guī)劃的典型應(yīng)用合理利用線材問題配料問題投資問題產(chǎn)品生產(chǎn)計(jì)劃勞動(dòng)力安排運(yùn)輸問題第一節(jié)問題的提出例1．某工廠在計(jì)劃期內(nèi)要安排I、Ⅱ兩種產(chǎn)品的生產(chǎn),已知生產(chǎn)單位產(chǎn)品所得的設(shè)備臺(tái)時(shí)及Ａ、B兩種原材料的消耗，以及資源的限制如表所示。該工廠每生產(chǎn)一單位產(chǎn)品I可獲利50元，每生產(chǎn)一單位產(chǎn)品Ⅱ可獲利100元，問工廠應(yīng)分別生產(chǎn)多少個(gè)I產(chǎn)品和Ⅱ產(chǎn)品才能使工廠獲利最多?III資源限制設(shè)備11300臺(tái)時(shí)原料A21400kg原料B01250kg第一節(jié)問題的提出這個(gè)問題可以用以下的數(shù)學(xué)模型來加以描述。

x1＝生產(chǎn)I產(chǎn)品的數(shù)量x2=生產(chǎn)Ⅱ產(chǎn)品的數(shù)量。決策變量（Decisionvariables）

maxz=50x1+100x2目標(biāo)函數(shù)（Objectivefunction）第一節(jié)問題的提出數(shù)學(xué)模型：目標(biāo)函數(shù)：MAXZ=50X1+100X2滿足約束條件：X1+X2≤3002X1+X2≤400X２≤250X1、X2≥0第一節(jié)問題的提出

１、數(shù)學(xué)模型的目標(biāo)函數(shù)為變量的線性函數(shù)，約束條件也為變量的線性等式或不等式，故此模型稱之為線性規(guī)劃。２、如果目標(biāo)函數(shù)是變量的非線性函數(shù)，或約束條件中含有變量非線性的等式或不等式的數(shù)學(xué)模型則稱之為非線性規(guī)劃。第一節(jié)問題的提出３、把滿足所有約束條件的解稱為該線性規(guī)劃的可行解。４、把使得目標(biāo)函數(shù)值最大(即利潤最大)的可行解稱為該線性規(guī)劃的最優(yōu)解，此目標(biāo)函數(shù)值稱為最優(yōu)目標(biāo)函數(shù)值，簡稱最優(yōu)值。第一節(jié)問題的提出建立線性規(guī)劃問題數(shù)學(xué)模型的步驟：１、定義決策變量，每個(gè)問題都用一組決策變量（X1X2X3………XN）表示某一方案；這組決策變量的值就代表一個(gè)具體方案，一般這些變量的取值是非負(fù)的２、用決策變量的線性函數(shù)形式寫出所要追求的目標(biāo)，稱之為目標(biāo)函數(shù)。３、寫出約束條件，這些約束條件可用線性等式或線性不等式表達(dá)。具有上述3個(gè)特征的問題為線性規(guī)劃問題。第一節(jié)問題的提出我們的任務(wù)就是要選擇一組或多組方案，使目標(biāo)函數(shù)值最大或最小。從選擇方案的角度說，這是規(guī)劃問題。從使目標(biāo)函數(shù)值最大或最小的角度說，就是優(yōu)化問題。線性規(guī)劃數(shù)學(xué)模型的一般表示方式思考題某公司由于生產(chǎn)需要，共需要Ａ，B兩種原料至少350噸(A，B兩種材料有一定替代性)，其中A原料至少購進(jìn)125噸。但由于A，B兩種原料的規(guī)格不同，各自所需的加工時(shí)間也是不同的，加工每噸A原料需要2個(gè)小時(shí)，加工每噸B原料需要1小時(shí)，而公司總共有600個(gè)加工小時(shí)。又知道每噸A原料的價(jià)格為2萬元，每噸B原料的價(jià)格為3萬元試問在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購買A、B兩種原料，使得購進(jìn)成本最低?解：設(shè)X1為購進(jìn)原料A的噸數(shù)，X2為購進(jìn)原料B的噸數(shù)。第二節(jié)圖解法Z=27500例1的數(shù)學(xué)模型：目標(biāo)函數(shù)：

MAXZ=50X1+100X2約束條件：

X1+X2≤3002X1+X2≤400X２≤250X1、X2≥0可行解可行域等值線第二節(jié)圖解法這樣就得到了例1的最優(yōu)解B點(diǎn)，B點(diǎn)的坐標(biāo)為(50，250)，因此最佳決策為X1=50，X2=250,此時(shí)Z＝27500這說明該廠的最優(yōu)生產(chǎn)計(jì)劃方案是生產(chǎn)I產(chǎn)品50單位，生產(chǎn)Ⅱ產(chǎn)品250單位，可得最大利潤27500元。

把X1=50，X2=250代入約束條件得：

1*(50)+1*(250)＝300臺(tái)時(shí)設(shè)備

2*(50)+l*(250)=350千克原料A，1*(250)＝250千克原料B第二節(jié)圖解法

在線性規(guī)劃中，對(duì)一個(gè)約束條件中沒使用的資源或能力的大小稱之為松弛量。記為Si。第二節(jié)圖解法像這樣把所有的約束條件都寫成等式，稱為線性規(guī)劃模型的標(biāo)準(zhǔn)化，所得結(jié)果稱為線性規(guī)劃的標(biāo)準(zhǔn)形式。第二節(jié)圖解法同樣對(duì)于≥約束條件中，可以增加一些代表最低限約束的超過量，稱之為剩余變量，把≥約束條件變?yōu)榈仁郊s束條件，加了松弛變量與剩余變量后，思考題的數(shù)學(xué)模型為：線性規(guī)劃問題的幾個(gè)特點(diǎn)：線性規(guī)劃問題的可行解的集合是凸集線性規(guī)劃問題的基礎(chǔ)可行解一般都對(duì)應(yīng)于凸集的極點(diǎn)凸集的極點(diǎn)的個(gè)數(shù)是有限的最優(yōu)解只可能在凸集的極點(diǎn)上，而不可能發(fā)生在凸集的內(nèi)部第三節(jié)圖解法的靈敏度分析

“心有靈犀一點(diǎn)通”

靈敏度分析又稱為后優(yōu)化分析

Post-optimizationAnalysis第三節(jié)圖解法的靈敏度分析線性規(guī)劃是靜態(tài)模型參數(shù)發(fā)生變化，原問題的最優(yōu)解還是不是最優(yōu)哪些參數(shù)容易發(fā)生變化C,b,A每個(gè)參數(shù)發(fā)生多大的變化不會(huì)破壞最優(yōu)解靈敏度越小，表示解的穩(wěn)定性越好。第三節(jié)圖解法的靈敏度分析所謂靈敏度分析就是在建立數(shù)學(xué)模型和求得最優(yōu)解之后，研究線性規(guī)劃的一些系數(shù)Ci、aij、bj變化時(shí)，對(duì)最優(yōu)解產(chǎn)生什么影響?第三節(jié)圖解法的靈敏度分析靈敏度分析的作用：1、Ci、aij、bj這些系數(shù)都是估計(jì)值和預(yù)測值，不一定非常精確。2、即使這些系數(shù)值在某一時(shí)刻是精確值，它們也會(huì)隨著市場條件的變化而變化。有了靈敏度分析就不必為了應(yīng)付這些變化而不停地建立新的模型和求其新的最優(yōu)解，也不會(huì)由于系數(shù)的估計(jì)和預(yù)測的精確性而對(duì)所求得的最優(yōu)解存有不必要的懷疑。第三節(jié)圖解法的靈敏度分析一、目標(biāo)函數(shù)中的系數(shù)Ｃi的靈敏度分析例1中生產(chǎn)一個(gè)單位的I產(chǎn)品可以獲利50元(C1＝50)，生產(chǎn)一個(gè)單位的Ⅱ產(chǎn)品可以獲利100元(C2＝100)。在目前的生產(chǎn)條件下求得生產(chǎn)I產(chǎn)品50單位．生產(chǎn)Ⅱ產(chǎn)品250單位可以獲得最大利潤。當(dāng)I、Ⅱ產(chǎn)品中的某一產(chǎn)品的單位利潤增加或減少時(shí)，為了獲取最大利潤就應(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)X1＝50，X2＝250的頂點(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ù)中的系數(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的靈敏度分析

(1)C1在什么范圍內(nèi)變化時(shí)頂點(diǎn)B仍然是其最優(yōu)解。(2)C2在什么范圍內(nèi)變化時(shí)頂點(diǎn)B仍然是其最優(yōu)解。(3)當(dāng)C1和C2都變化時(shí)，頂點(diǎn)B何時(shí)還是最優(yōu)解。The100percentrule百分之百法則目標(biāo)函數(shù)系數(shù)同時(shí)變動(dòng)的百分之百法則(The100percentruleforsimultaneouschangesinobjectivefunctioncoefficients)：如果目標(biāo)函數(shù)的系數(shù)同時(shí)變動(dòng)，計(jì)算出每一系數(shù)變動(dòng)量占該系數(shù)最優(yōu)域允許變動(dòng)量的百分比，而后，將各個(gè)系數(shù)的變動(dòng)百分比相加，如果所得的和不超過百分之一百，最優(yōu)解不會(huì)改變，如果超過百分之一百，則不能確定最優(yōu)解是否改變。

3.2約束條件中右邊系數(shù)bj的靈敏度分析

當(dāng)約束條件右邊系數(shù)bj變化時(shí)，其線性規(guī)劃的可行域也將變化，這樣就可能引起最優(yōu)解的變化。1、設(shè)例1中的設(shè)備臺(tái)時(shí)效增加了10個(gè)臺(tái)時(shí)，共有臺(tái)時(shí)數(shù)310個(gè)，這樣例1中的設(shè)備臺(tái)時(shí)效的約束條件就變?yōu)椋簒1+x2≤3103.2約束條件中右邊系數(shù)bj的靈敏度分析

在約束條件右邊常量增加一個(gè)單位而使最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)的數(shù)量稱之為這個(gè)約束條件的對(duì)偶價(jià)格。3.2約束條件中右邊系數(shù)bj的靈敏度分析２、原料Ａ如果增加10千克，給最優(yōu)解和最優(yōu)值產(chǎn)生的影響。第三節(jié)圖解法的靈敏度分析在目標(biāo)函數(shù)求最大值的情況下，除了對(duì)偶價(jià)格大于零、等于零的情況外，還存在著對(duì)偶價(jià)格小于零的情況。當(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í)題第三章線性規(guī)劃問題的計(jì)算機(jī)求解一、ExcelExcel的線性規(guī)劃二、WinQSBQSB-QuantitativeSystemforBusiness作業(yè)：SpecificMotors公司汽車模型生產(chǎn)問題SpecificMotors公司生產(chǎn)三種類型的汽車，型號(hào)分別為X、Y和Z。三種產(chǎn)品的凈收入分別是1000、3000和6000美元。每生產(chǎn)一個(gè)產(chǎn)品X需要40人小時(shí)