第三章 線性規(guī)劃及圖解法課件

蘭州大學(xué)管理學(xué)院運(yùn)籌學(xué)

-------數(shù)據(jù)、模型與決策2010年用第三章線性規(guī)劃及圖解法運(yùn)籌學(xué)第三章

線性規(guī)劃及圖解法第三章線性規(guī)劃及圖解法第三章線性規(guī)劃及圖解法確定型決策——線性規(guī)劃方法線性規(guī)劃——所有資源限制條件式和目標(biāo)式都是自變量的一次方關(guān)系。

描述的是在一定資源限制下(自然狀態(tài))，給出了很多個(gè)可以選擇的不同方案(運(yùn)行方案)，從這些方案中找到一個(gè)最好的方案來(lái)執(zhí)行。第三章線性規(guī)劃及圖解法第一節(jié)問(wèn)題的提出

一、線性規(guī)劃數(shù)學(xué)模型二、線性規(guī)劃模型的三個(gè)基本要素三、線性規(guī)劃數(shù)學(xué)模型的一般形式第三章線性規(guī)劃及圖解法一、線性規(guī)劃數(shù)學(xué)模型

例1某工廠在計(jì)劃期內(nèi)要安排I，Ⅱ兩種產(chǎn)品的生產(chǎn)。生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A，B兩種原材料的消耗以及資源的限制如下表所示。工廠每生產(chǎn)一個(gè)單位產(chǎn)品I可獲利50元，每生產(chǎn)一個(gè)單位產(chǎn)品Ⅱ可獲利100元，問(wèn)工廠應(yīng)分別生產(chǎn)多少單位產(chǎn)品I和產(chǎn)品Ⅱ才能使獲利最多？

產(chǎn)品資源III資源限制設(shè)備11300臺(tái)時(shí)原料A21400kg原料B01250kg第三章線性規(guī)劃及圖解法建立問(wèn)題的數(shù)學(xué)關(guān)系2、用xl和x2以線性函數(shù)形式表達(dá)工廠所要求的最大利潤(rùn)的目標(biāo):單位產(chǎn)品I和Ⅱ的利潤(rùn)3、以xl和

x2的線性不等式來(lái)表示問(wèn)題中相應(yīng)資源的限制條件：臺(tái)時(shí)數(shù)的限制：xl+x2≤300maxz=50xl＋100x2，原材料的限量：2xl+x2≤400，

x2≤250解:1、設(shè):xl，x2分別表示產(chǎn)品I和產(chǎn)品Ⅱ的產(chǎn)量。第三章線性規(guī)劃及圖解法例1的線性規(guī)劃數(shù)學(xué)模型maxz＝50xl+100x2滿足條件：xl＋

x2≤3002xl+x2≤400

x2≤250

xl≥0，

x2≥0即：這一類問(wèn)題都可以用這種語(yǔ)言、這種方式來(lái)表達(dá)。第三章線性規(guī)劃及圖解法二、線性規(guī)劃模型的三個(gè)基本要素（1）決策變量（約束變量）：用符號(hào)來(lái)表示可控制的因素，如xi。（2）目標(biāo)函數(shù)：Maxz

或Minf，用來(lái)計(jì)算和實(shí)現(xiàn)問(wèn)題目標(biāo)。（3）約束條件：s.t.(subjectto)滿足于（一個(gè)等式或不等式組），一般是問(wèn)題的資源限制條件。第三章線性規(guī)劃及圖解法

例2：營(yíng)養(yǎng)配餐問(wèn)題

假定一個(gè)成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場(chǎng)上只有四種食品可供選擇，它們每千克所含的熱量和營(yíng)養(yǎng)成分及市場(chǎng)價(jià)格見(jiàn)下表。問(wèn)如何選購(gòu)才能在滿足營(yíng)養(yǎng)的前提下使購(gòu)買食品的費(fèi)用最??？序號(hào)食品名稱熱量(kcal/kg)蛋白質(zhì)(g/kg)鈣(mg/kg)價(jià)格(元/kg)1雞肉100050400142雞蛋8006020063大米9002030034白菜200105002第三章線性規(guī)劃及圖解法解：（1）確定決策變量設(shè)xi為第i種食品每天的購(gòu)入量；（3）確定約束條件食品的熱量、蛋白質(zhì)和鈣的單位含量構(gòu)成和總含量應(yīng)滿足最低要求。（2）確定目標(biāo)函數(shù)購(gòu)買食品的費(fèi)用為最小，總費(fèi)用為：14x1+6x2+3x3+2x4第三章線性規(guī)劃及圖解法配餐問(wèn)題的線性規(guī)劃模型

minZ=14x1+6x2+3x3+2x4

s.t.1000x1+800x2+900x3+200x4

300050x1+60x2+20x3+10x4

55400x1+200x2+300x3+500x4

800

x1，x2

，x3

，x4

0總熱量蛋白質(zhì)鈣食用量不能為負(fù)第三章線性規(guī)劃及圖解法一般線性規(guī)劃問(wèn)題的建模過(guò)程（1）理解要解決的問(wèn)題。明確在什么條件下，要追求什么目標(biāo)。（2）定義決策變量。每個(gè)問(wèn)題都用一組決策變量(x1,x2,…,xn)表示，當(dāng)這組決策變量取具體值時(shí)就代表一個(gè)具體方案，一般這些變量取值是非負(fù)的。（3）用決策變量的線性函數(shù)形式寫出所要追求的目標(biāo)，即目標(biāo)函數(shù)，按問(wèn)題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。（4）用一組決策變量的等式或不等式來(lái)表示在解決問(wèn)題過(guò)程中所必須遵循的約束條件（決策分析中的自然狀態(tài)）。第三章線性規(guī)劃及圖解法三、線性規(guī)劃數(shù)學(xué)模型的一般形式

max(min)z=clxl+c2x2+…+cnxn；滿足約束條件：

al1xl+a12x2+…+a1nxn≤（=，≥）b1a21xl+a22x2+…+a2nxn≤（=，≥）b2………am1xl+am2x2+…+amnxn≤（=，≥）bmxl，x2，…，

xn≥0ci是目標(biāo)函數(shù)的變量系數(shù)，也稱做價(jià)值系數(shù)；

aij是約束條件的變量系數(shù)，也稱做資源配置系數(shù)；

bj是常數(shù)項(xiàng)，也稱做資源限制量。其中：第三章線性規(guī)劃及圖解法線性規(guī)劃問(wèn)題的求解方法1、二維線性規(guī)劃問(wèn)題的圖解法；2、高維線性規(guī)劃問(wèn)題的單純形方法手工求解；3、計(jì)算機(jī)軟件求解。第三章線性規(guī)劃及圖解法第二節(jié)圖解法

特征：只包含兩個(gè)決策變量的線性規(guī)劃問(wèn)題，才可用圖解法來(lái)求解。優(yōu)點(diǎn)：簡(jiǎn)單直觀，有助于了解線性規(guī)劃問(wèn)題求解的基本原理。方法：在以x1，x2為坐標(biāo)軸的直角坐標(biāo)系里，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量

x1，

x2的一組值，也就代表了一個(gè)具體的決策方案。第三章線性規(guī)劃及圖解法一、最大化問(wèn)題的圖解法

仍用例1來(lái)介紹線性規(guī)劃問(wèn)題的圖解法！第三章線性規(guī)劃及圖解法圖3-1(滿足約束條件的公共部分)0100200300400x1400300200100x2x2=2502xl+x2=400xl+x2=300同時(shí)滿足：2x1+x2

400x1+x2

300

x2

250x1

0x2

0的區(qū)域——可行域可行域第三章線性規(guī)劃及圖解法圖3-2線性規(guī)劃問(wèn)題的可行域0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)O(0,0)第三章線性規(guī)劃及圖解法線性規(guī)劃模型的可行域

可行域的幾何形狀可千變?nèi)f化，但幾何結(jié)構(gòu)都是凸集。第三章線性規(guī)劃及圖解法圖3-3最優(yōu)目標(biāo)函數(shù)值0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)z=0=50x1+100x2第三章線性規(guī)劃及圖解法圖3-3最優(yōu)目標(biāo)函數(shù)值0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)z=10000=50x1+100x2第三章線性規(guī)劃及圖解法圖3-3最優(yōu)目標(biāo)函數(shù)值0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)z=20000=50x1+100x2第三章線性規(guī)劃及圖解法圖3-3最優(yōu)目標(biāo)函數(shù)值0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)z=30000=50x1+100x2第三章線性規(guī)劃及圖解法圖3-3最優(yōu)目標(biāo)函數(shù)值0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)z=27500=50x1+100x2第三章線性規(guī)劃及圖解法最優(yōu)目標(biāo)函數(shù)值B點(diǎn)的坐標(biāo)為(50，250)，因此最佳決策為x1=50，

x2=250，此時(shí)z=27500。最優(yōu)生產(chǎn)計(jì)劃方案是生產(chǎn)產(chǎn)品I50單位，生產(chǎn)產(chǎn)品Ⅱ250單位，可得最大利潤(rùn)27500元。第三章線性規(guī)劃及圖解法二、線性規(guī)劃問(wèn)題的解1、在線性規(guī)劃問(wèn)題的解集合中，若約束條件能構(gòu)成一個(gè)封閉的可行域，則可行域的任意點(diǎn)都是問(wèn)題的一個(gè)可行解，這些可行解中必有最優(yōu)解。若最優(yōu)解是可行域中一個(gè)點(diǎn)，則這個(gè)解是線性規(guī)劃的唯一最優(yōu)解。唯一最優(yōu)解都必落在可行域的頂點(diǎn)上，可行域的所有頂點(diǎn)稱為基本可行解；對(duì)于求最大目標(biāo)的線性規(guī)劃問(wèn)題，取Z值最小的基本可行解為初始基本可行解，再依次迭代至最優(yōu)解。求最小目標(biāo)的情況，可選可行域中任意目標(biāo)初函數(shù)值較大的點(diǎn)為初始基本可行解，再依次迭代至最優(yōu)解。第三章線性規(guī)劃及圖解法線性規(guī)劃問(wèn)題的解（2）2、若可行域的某一個(gè)邊與目標(biāo)函數(shù)平行，則最優(yōu)解是這條邊上的所有點(diǎn)，所以是無(wú)窮多點(diǎn)，此時(shí)線性規(guī)劃問(wèn)題就有無(wú)窮多解（或最優(yōu)解不唯一）。3、對(duì)于目標(biāo)為求最大的線性規(guī)劃問(wèn)題，若約束條件不能構(gòu)成封閉（或有限）區(qū)域的可行域，如沿目標(biāo)函數(shù)值增大的方向無(wú)限擴(kuò)散而沒(méi)有邊界。這時(shí)的可行域是無(wú)界的，線性規(guī)劃問(wèn)題就有無(wú)界解。4、若約束條件雖構(gòu)成封閉區(qū)域，但是兩個(gè)及兩個(gè)以上的互不相連的區(qū)域，那么這些區(qū)域中的點(diǎn)都不能同時(shí)滿足約束要求，因此都不是可行域，則線性規(guī)劃問(wèn)題沒(méi)有可行域，即無(wú)可行解（或無(wú)解）。第三章線性規(guī)劃及圖解法三、剩余資源的松弛量

在線性規(guī)劃的解中，約束條件的實(shí)際值與常數(shù)項(xiàng)（資源限制量）不一定相等。設(shè)備臺(tái)時(shí)：1×50+1×250=300(kg

)

等于限制量原料A：2×50+1×250=350(kg)小于限制量原料B∶0×50+1×250＝250(kg)等于限制量

在線性規(guī)劃中，一個(gè)“≤”約束條件中沒(méi)使用的資源或能力被稱之為松弛量。第三章線性規(guī)劃及圖解法松弛變量松弛變量:代表沒(méi)使用的資源或能力的變量。約束條件實(shí)際值+松弛變量=資源限制量

在例1中引入三個(gè)松弛變量sl、s2、s3后，線性規(guī)劃數(shù)學(xué)模型描述為：約束條件：x1+x2+sl＝300，2x1+x2+s2＝400，x2+s3＝250，x1，x2，sl，s2，s3≥0例1中sl＝0s2＝50s3＝0maxz＝50x1+100x2+0sl+0s2+0s3；第三章線性規(guī)劃及圖解法四、最小化問(wèn)題的圖解法例2：下面給出一個(gè)求目標(biāo)函數(shù)最小化的線性規(guī)劃問(wèn)題。minf=11x1+8x2約束條件10x1+2x2≥203x1+3x2≥184x1+9x2≥36

x1，x2≥0第三章線性規(guī)劃及圖解法圖3-4例2的可行域及基本可行解可行域：以x1=0、AB、BC、CD和x2=0形成的半發(fā)散區(qū)域基本可行解：

A、B、C、D點(diǎn)為基本可行解。離原較遠(yuǎn)的基本可行解為初始基本可行解。

●●●●B(1,5)x28642x12468A(0,10)C(3.6,2.4)D(9,0)第三章線性規(guī)劃及圖解法圖3-5例2目標(biāo)函數(shù)的最優(yōu)解●●●●B(1,5)x28642x12468f=11x1+8x2

目標(biāo)函數(shù)f＝11x1+8x2

減小時(shí)，其代表的直線向左下方平移，當(dāng)移動(dòng)到B點(diǎn)，目標(biāo)函數(shù)在可行域內(nèi)取最小值。第三章線性規(guī)劃及圖解法圖3-5例2目標(biāo)函數(shù)的最優(yōu)解●●●●B(1,5)x28642x12468f=11x1+8x2

即獲得問(wèn)題的最優(yōu)解：x1=1,x2=5。最優(yōu)值：minf=11x1+8x2=51第三章線性規(guī)劃及圖解法五、多于資源低限的剩余量

把例2中x1=1，

x2＝5代入約束條件：10x1+2x2=20

3x1+3x2=18

4x1+9x2≥36

資源限制量資源利用實(shí)際值10×1+2×5=203×1+3×5=184×1+9×5=49“≥”約束條件中超過(guò)資源或能力最低限量被稱之為剩余量。第三章線性規(guī)劃及圖解法剩余變量剩余變量:代表沒(méi)超過(guò)資源或能力最低限的變量。約束條件實(shí)際值－剩余變量=資源限制量

約束條件：10x1+

2x2-sl＝20，3x1+3x2-s2＝18，4x1+9x2-s3＝36，x1，x2，sl，s2，s3≥0例2中sl＝0s2＝0s3＝13

例2引入三個(gè)剩余變量sl、s2、s3后，線性規(guī)劃數(shù)學(xué)模型描述為：

maxz＝11x1+8x2+0sl+0s2+0s3；第三章線性規(guī)劃及圖解法六、線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)形式

引入了松馳變量和剩余變量后，就可以將線性規(guī)劃數(shù)學(xué)模型用“≤”，“≥”和“=”建立的一般形式化為統(tǒng)一用“=”的標(biāo)準(zhǔn)形式：max(min)z=clxl+c2x2+…+cnxn；約束條件：

al1xl+a12x2+…+a1nxn=b1a21xl+a22x2+…+a2nxn=b2………am1xl+am2x2+…+amnxn=bmxl，x2，…，

xn≥0第三章線性規(guī)劃及圖解法線性規(guī)劃標(biāo)準(zhǔn)形式的特征：所有約束條件都是“=”關(guān)系若不是“=”關(guān)系，可以添加松弛變量或剩余變量，將不等號(hào)化為等號(hào)。決策變量的取值區(qū)間0≤xi≤+∞

若變量不在此區(qū)間，需要進(jìn)行數(shù)學(xué)代換，將其調(diào)整到這個(gè)區(qū)間；常數(shù)項(xiàng)bj都為大于或等于0的數(shù)；若是小于0的數(shù)時(shí)，可將等號(hào)兩端同乘一個(gè)-1。目標(biāo)函數(shù)即可求最大，也可求最小，最大和最小可以轉(zhuǎn)換，轉(zhuǎn)換的規(guī)則是：maxz=min(-z)第三章線性規(guī)劃及圖解法第三節(jié)線性規(guī)劃問(wèn)題的靈敏度分析靈敏度分析研究線性規(guī)劃的一些系數(shù)ci,aij,bj的微小變化對(duì)最優(yōu)解所產(chǎn)生的影響。靈敏度分析的意義：用確定的（一組理想的）環(huán)境數(shù)據(jù)建立模型，研究環(huán)境變化情況下不確定的（一系列現(xiàn)實(shí)的）問(wèn)題。第三章線性規(guī)劃及圖解法一、目標(biāo)函數(shù)中變量系數(shù)ci的取值范圍分析

ci代表廣義的產(chǎn)品價(jià)值，稱之為價(jià)值系統(tǒng)，價(jià)值或價(jià)格是經(jīng)營(yíng)的環(huán)境。

ci的靈敏度分析是研究經(jīng)營(yíng)環(huán)境的變化對(duì)最優(yōu)解的影響。ci的改變只是改變目標(biāo)函數(shù)直線的斜率，不改變可行域的形狀。第三章線性規(guī)劃及圖解法例1中ci的變化如何影響最優(yōu)解？

目前的生產(chǎn)條件下：生產(chǎn)50單位產(chǎn)品I、250單位產(chǎn)品Ⅱ可以獲得最大利潤(rùn)。當(dāng)產(chǎn)品I，Ⅱ中的某一產(chǎn)品的單位利潤(rùn)增加或減少時(shí)，為了獲取最大利潤(rùn)就應(yīng)該增加或減少這一產(chǎn)品的產(chǎn)量，即改變最優(yōu)解。如何精確地確定這一產(chǎn)品利潤(rùn)變化的上限與下限，使得利潤(rùn)在這個(gè)范圍內(nèi)變化時(shí)其最優(yōu)解不變，即仍然生產(chǎn)50單位的產(chǎn)品I和250單位的產(chǎn)品Ⅱ而使獲利最大？第三章線性規(guī)劃及圖解法圖3-6目標(biāo)函數(shù)直線斜率變化分析x10100200300x2300200100直線S3(原料A約束)直線z(目標(biāo)函數(shù))直線S1(原料B約束)直線S2(設(shè)備約束)ABDC第三章線性規(guī)劃及圖解法目標(biāo)函數(shù)系數(shù)的取值范圍當(dāng)時(shí)，B仍然是其最優(yōu)解。－1≤≤0

假設(shè)單位產(chǎn)品Ⅱ的利潤(rùn)為100元不變，即c2＝100，則有

即只要當(dāng)產(chǎn)品Ⅱ的利潤(rùn)為100元，產(chǎn)品I的利潤(rùn)在0-100元之間時(shí)，坐標(biāo)xl=50，x2=250的頂點(diǎn)B仍是最優(yōu)解。－1≤≤00≤cl≤100第三章線性規(guī)劃及圖解法

目標(biāo)函數(shù)系數(shù)的取值范圍假設(shè)單位產(chǎn)品I的利潤(rùn)為50元不變，即cl=50，得：－1≤≤050≤c2≤＋∞即當(dāng)產(chǎn)品I的利潤(rùn)為50元，而產(chǎn)品Ⅱ的利潤(rùn)只要大于等于50元時(shí)，頂點(diǎn)B仍為其最優(yōu)解。最低限當(dāng)前值最高限C1050100C250100不限

同樣在本問(wèn)題中使得最優(yōu)解放不變的目標(biāo)函數(shù)兩個(gè)系數(shù)的取值范圍如下表：第三章線性規(guī)劃及圖解法二、約束條件中常數(shù)項(xiàng)bj的取值范圍分析1、對(duì)偶價(jià)格

常數(shù)項(xiàng)bj代表的是廠房面積、生產(chǎn)總時(shí)間、設(shè)備數(shù)量等所提供給企業(yè)經(jīng)營(yíng)的資源限制量。bj的靈敏度分析是研究資源的變化對(duì)最優(yōu)解的影響。bj的改變是可行域某一邊的平行移動(dòng)，這種改變極有可能導(dǎo)致最優(yōu)解和最優(yōu)值的改變。第三章線性規(guī)劃及圖解法圖3-7常數(shù)項(xiàng)的變化改變可行域●BC直線Z(目標(biāo)函數(shù))100200300x2200100300x10ODA例1中的可行域是OABCD，最優(yōu)解是B（20，250），最優(yōu)值是27500。第三章線性規(guī)劃及圖解法圖3-7常數(shù)項(xiàng)的變化改變后的解

假設(shè)例1中的設(shè)備臺(tái)時(shí)數(shù)增加到310個(gè)臺(tái)時(shí)，則例1中的設(shè)備臺(tái)時(shí)數(shù)的約束條件變?yōu)椋?/p>

xl+x2≤310B’●BC直線Z(目標(biāo)函數(shù))C’100200300x2200100300x10ODA新的可行域變?yōu)镺AB’C’D，最優(yōu)解由B點(diǎn)變?yōu)锽’。B’點(diǎn)的坐標(biāo)為xl=60,x2=250，獲得的最大利潤(rùn)為28000（元）。第三章線性規(guī)劃及圖解法對(duì)偶價(jià)格

在約束條件常數(shù)中增加一個(gè)單位而使最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)的數(shù)量稱之為這個(gè)約束條件的對(duì)偶價(jià)格。第三章線性規(guī)劃及圖解法圖3-8100200300x2●BC直線Z(目標(biāo)函數(shù))C’D’200100300x10ODA原料A增加10kg，對(duì)最優(yōu)解產(chǎn)生的影響約束條件：2xl+x2≤410線性規(guī)劃的可行域變?yōu)镺ABC’D’，但它的最優(yōu)解仍是B點(diǎn)，它的最優(yōu)值仍然是27500。因此原料A的對(duì)偶價(jià)格為零。第三章線性規(guī)劃及圖解法對(duì)偶價(jià)格的進(jìn)一步解釋（1）如果對(duì)偶價(jià)格大于零，則其最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)，即求最大值時(shí)，常數(shù)項(xiàng)的增（減）使最優(yōu)目標(biāo)函數(shù)值變得更大（更小）；求最小值時(shí)，常數(shù)項(xiàng)的增（減）使最優(yōu)目標(biāo)函數(shù)值變得更小（更大）。（2）如果對(duì)偶價(jià)格小于零，則其最優(yōu)目標(biāo)函數(shù)值變壞，即求最大值時(shí)，常數(shù)項(xiàng)的增（減）使最優(yōu)目標(biāo)函數(shù)值變得更?。ǜ螅?；求最小值時(shí)，常數(shù)項(xiàng)的增（減）使最優(yōu)目標(biāo)函數(shù)值變得更大（更?。?。（3）如果對(duì)偶價(jià)格等于零，則常數(shù)項(xiàng)的增（減）不會(huì)使其最優(yōu)目標(biāo)函數(shù)值改變。（4）若約束條件的松馳量或剩余量不為0，則對(duì)偶價(jià)格必等于零。第三章線性規(guī)劃及圖解法2、常數(shù)項(xiàng)的上限與下限

常數(shù)項(xiàng)的改變，將使可行域的邊界發(fā)生平移，因此，最優(yōu)解和最優(yōu)值都必將發(fā)生改變。常數(shù)項(xiàng)的改變也會(huì)影響對(duì)偶價(jià)格的值。但在現(xiàn)有最優(yōu)解的前提下，并不是常數(shù)項(xiàng)的所有改變都會(huì)導(dǎo)致對(duì)偶價(jià)格的改變。確切地說(shuō)，常數(shù)項(xiàng)的改變肯定會(huì)改變可行域的形狀，也可能會(huì)改變可行域的結(jié)構(gòu)。只有可行域的結(jié)構(gòu)發(fā)生改變時(shí)才會(huì)使對(duì)偶價(jià)格改變。

我們關(guān)心的常數(shù)項(xiàng)的上限和下限是在現(xiàn)有最優(yōu)解的前提下，使對(duì)偶價(jià)格不變的常數(shù)項(xiàng)的取值范圍。第三章線性規(guī)劃及圖解法圖3-90100200300400x1400300200100x2可行域ACx2xl+x2=300=b1x2=250=b32xl+x2=400=b2最優(yōu)解目標(biāo)函數(shù)OB常數(shù)項(xiàng)沒(méi)變化的最優(yōu)解D第三章線性規(guī)劃及圖解法最優(yōu)解圖3-100100200300400x1400300200100x2x2=250=b32xl+x2=400=b2DBOCA目標(biāo)函數(shù)xl+x2=260=b1可行域常數(shù)項(xiàng)b1在改變（由300減小到260），使可行域形狀改變，而結(jié)構(gòu)不變，對(duì)偶價(jià)格就不變。第三章線性規(guī)劃及圖解法400300200100x2圖3-11最優(yōu)解0100200300400x1x2=250=b32xl+x2=400=b2DOCA目標(biāo)函數(shù)xl+x2=250=b1B可行域

常數(shù)項(xiàng)繼續(xù)減小，到可行域結(jié)構(gòu)開(kāi)始改變時(shí)的常數(shù)項(xiàng)值，就是這個(gè)約束條件常數(shù)項(xiàng)的下限值。即本例常數(shù)項(xiàng)b1的下限為250。第三章線性規(guī)劃及圖解法圖3-120100200300400x1400300200100x2可行域Ax2xl+x2=325=b1x2=250=b32xl+x2=400=b2最優(yōu)解目標(biāo)函數(shù)OBC

同樣，常數(shù)項(xiàng)增大，到可行域結(jié)構(gòu)開(kāi)始改變時(shí)的常數(shù)項(xiàng)值，就是這個(gè)約束條件常數(shù)項(xiàng)的上限值。即本例常數(shù)項(xiàng)b1的上限為325。第三章線性規(guī)劃及圖解法表3-6約束條件中常數(shù)項(xiàng)的取值范圍

最下限當(dāng)前值最高限b1250300325b2350400不限b3200250300用同樣的方法可以求得b2、b3的上下限。如下表：第三章線性規(guī)劃及圖解法三、約束條件中常數(shù)項(xiàng)amn的靈敏度分析

amn根據(jù)m,n的不同構(gòu)成決策變量的系數(shù)矩陣，它代表著企業(yè)資源的分配。資源分配系數(shù)矩陣的變化改變了可行域各邊界線段的斜率，即完全且不規(guī)則地改變了可行域的形狀。資源分配系數(shù)矩陣的變化對(duì)最優(yōu)解的影響太繁雜，也不具有共性，可視為完全改變了原有的數(shù)學(xué)模型，另外求解。第三章線性規(guī)劃及圖解法四、百分之一百法則

當(dāng)兩個(gè)或更多的系數(shù)同時(shí)發(fā)生變化時(shí)的靈敏度分析最低限當(dāng)前值最高限目標(biāo)函數(shù)系數(shù)c1050100c250100不限常數(shù)項(xiàng)b1250300325b2350400不限b3200250300

對(duì)于例1單個(gè)系數(shù)變化時(shí)目標(biāo)函數(shù)系數(shù)和約束條件中常數(shù)項(xiàng)的可變化范圍如下表，在此基礎(chǔ)上進(jìn)行多個(gè)系數(shù)同時(shí)變化的靈敏度分析。第三章線性規(guī)劃及圖解法1、多個(gè)目標(biāo)函數(shù)系數(shù)的百分之一百法則允許增加量——目標(biāo)函數(shù)的決策變量系數(shù)在上限范圍內(nèi)的最大增加量（最高限-當(dāng)前值）。

引入兩個(gè)述語(yǔ)：允許減少量

——目標(biāo)函數(shù)的決策變量系數(shù)在下限范圍內(nèi)的最大減少量（當(dāng)前值-最低限）。

目標(biāo)函數(shù)決策變量系數(shù)的百分之一百法則：對(duì)于所有變化的目標(biāo)函數(shù)決策變量系數(shù)，當(dāng)其所有實(shí)際增加量與允許增加量的百分比和所有實(shí)際減少量與允許減少量的百分比之和不超過(guò)百分之一百時(shí)，最優(yōu)解不變。即：第三章線性規(guī)劃及圖解法1、多個(gè)目標(biāo)函數(shù)系數(shù)的百分之一百法則

例1中，原來(lái)每件產(chǎn)品I和產(chǎn)品Ⅱ的利潤(rùn)分別為50和100元，現(xiàn)在每件產(chǎn)品I和產(chǎn)品Ⅱ的利潤(rùn)分別變?yōu)?0和80元，對(duì)其進(jìn)行靈敏度分析。x1的系數(shù)cl的允許增加量為：100－50＝50x2的系數(shù)c2的允許減少量也為：100－50＝50百分一百法則：（70-50）/50+（100-80）/50=80%最優(yōu)解不變，最優(yōu)值為23500第三章線性規(guī)劃及圖解法1、多個(gè)目標(biāo)函數(shù)系數(shù)的百分之一百法則

再如例1中，原來(lái)每件產(chǎn)品I和產(chǎn)品Ⅱ的利潤(rùn)分別為50和100元，現(xiàn)在每件產(chǎn)品I和產(chǎn)品Ⅱ的利潤(rùn)分別變?yōu)?0和70元，對(duì)其進(jìn)行靈敏度分析。x1的系數(shù)cl的允許增加量為：100－50＝50x2的系數(shù)c2的允許減少量也為：100－50＝50百分一百法則：（70-50）/50+（100-70）/50=100%最優(yōu)解不變，最優(yōu)值為21000第三章線性規(guī)劃及圖解法1、多個(gè)目標(biāo)函數(shù)系數(shù)的百分之一百法則

又如例1中，原來(lái)每件產(chǎn)品I和產(chǎn)品Ⅱ的利潤(rùn)分別為50和100元，現(xiàn)在每件產(chǎn)品I和產(chǎn)品Ⅱ的利潤(rùn)分別變?yōu)?0和69元，對(duì)其進(jìn)行靈敏度分析。x1的系數(shù)cl的允許增加量為：100－50＝50x2的系數(shù)c2的允許減少量也為：100－50＝50百分一百法則：（70-50）/50+（100-69）/50=102%此時(shí)最解由B點(diǎn)變?yōu)镃點(diǎn)，即x1＝100，x2＝200最優(yōu)值為20800第三章線性規(guī)劃及圖解法2、多個(gè)約束條件中常數(shù)項(xiàng)同時(shí)變化

約束條件中常數(shù)項(xiàng)的百分之一百法則：對(duì)于所有變化的約束條件中的常數(shù)項(xiàng)，當(dāng)其所有實(shí)際增加量與允許增加量的百分比和所有實(shí)際減少量與允許減少量的百分比之和不超過(guò)百分之一百時(shí)，則這些約束條件的對(duì)偶價(jià)格不變。即：第三章線性規(guī)劃及圖解法2、多個(gè)約束條件中常數(shù)項(xiàng)同時(shí)變化在例1中，設(shè)備臺(tái)時(shí)數(shù)從300臺(tái)時(shí)增加為315臺(tái)時(shí)（上限325），而原料A從400kg減少到390kg（下限350），原料B從250kg減少到240kg（下限200）可得：15/25+10/50+10/50=100%

沒(méi)有超過(guò)100%，所以三個(gè)約束條件的對(duì)偶價(jià)格：50，0，50，都不變。但最優(yōu)值變?yōu)椋?7750第三章線性規(guī)劃及圖解法2、多個(gè)約束條件中常數(shù)項(xiàng)同時(shí)變化而若再增加一個(gè)臺(tái)時(shí)，從300臺(tái)時(shí)增加為316臺(tái)時(shí)（上限325），而原料A從400kg減少到390kg（下限350），原料B從250kg減少到240kg（下限200），這樣我們可以得到：16/25+10/50+10/50=104%對(duì)偶價(jià)格由原來(lái)的50，0，50改變?yōu)?，25，75第三章線性規(guī)劃及圖解法百分之一百法則使用說(shuō)明：

（1）當(dāng)允許增(減)量為無(wú)窮大時(shí)，則對(duì)于任一個(gè)增(減)量，其允許增(減)的百分比都看成零。這時(shí)靈敏度的分析結(jié)果就只取決于減(增)量的百分比(即另一方向的變化)。（2）百分之一百法則是判斷最優(yōu)解或?qū)ε純r(jià)格是否發(fā)生變化的充分條件，但不是必要條件。也就是說(shuō)，當(dāng)其允許增(減)的百分比之和不超過(guò)(小于)100%時(shí)，其最優(yōu)解或?qū)ε純r(jià)格不變；但是當(dāng)其允許增(減)的百分比之和超過(guò)(大于)100%時(shí)，我們并不知道其最優(yōu)解或?qū)ε純r(jià)格是否發(fā)生變化。第三章線性規(guī)劃及圖解法（3）百分之一百法則不能應(yīng)用于目標(biāo)函數(shù)決策變量系數(shù)和約束條件中常數(shù)項(xiàng)同時(shí)變化的情況，在這種情況下，只有重新求解。（4）百分之一百法則不包括同步增加或同步減小的情況。百分之一百法則使用說(shuō)明：

第三章線性規(guī)劃及圖解法五目標(biāo)函數(shù)中變量系數(shù)ci的相差值分析

相差值----遞減成本的絕對(duì)值

產(chǎn)品資源III資源限制設(shè)備11300臺(tái)時(shí)原料A21400kg原料B01300kg

例3將本章例1中,原料B的限制量改變?yōu)?00kg，其它條件都不變,重新建立模型,重新求解。第三章線性規(guī)劃及圖解法五目標(biāo)函數(shù)中變量系數(shù)ci的相差值分析

根據(jù)例1建模過(guò)程可得本問(wèn)題的線性規(guī)劃模型為：maxz＝50xl+100x2；滿足條件：xl＋

x2≤3002xl+x2≤400

x2≤300

xl≥0，

x2≥0第三章線性規(guī)劃及圖解法0100200300400x1400300200100x2可行域ACx2xl+x2=300=b1x2=3002xl+x2=400=b2最優(yōu)解目標(biāo)函數(shù)OB五目標(biāo)函數(shù)中變量系數(shù)ci的相差值分析

第三章線性規(guī)劃及圖解法五目標(biāo)函數(shù)中變量系數(shù)ci的相差值分析

所謂目標(biāo)函數(shù)變量系數(shù)的相差值，是指最優(yōu)解中為0的變量，在其它變量系數(shù)保持不變的情況下，使最優(yōu)解中該變量的值不為0時(shí)，相應(yīng)目標(biāo)函數(shù)變量系數(shù)由現(xiàn)有值再改變的量。第三章線性規(guī)劃及圖解法五目標(biāo)函數(shù)中變量系數(shù)ci的相差值分析

注：

1、最優(yōu)解不為0的變量，相差值必為0，反之不然，因?yàn)橐灿锌赡苁峭庠诩s束所致；

2、對(duì)于相差值不為0的變量系數(shù)：當(dāng)目標(biāo)為求最大值時(shí)，當(dāng)前值加上這個(gè)相差值，必等于該變量系數(shù)的上限值，且該變量系數(shù)無(wú)下限；此時(shí)其相應(yīng)的變量值就會(huì)由原來(lái)為0變?yōu)榉?。當(dāng)目標(biāo)為求最小值時(shí)，當(dāng)前值減去這個(gè)相差值，必等于該變量系數(shù)的下限值，且該變量系數(shù)無(wú)上限；此時(shí)其相應(yīng)的變量值就會(huì)由原來(lái)為0變?yōu)榉?。

3、對(duì)于目標(biāo)求最大值時(shí)，遞減成本為負(fù)；對(duì)于目標(biāo)求最小值時(shí)，遞減成本為正。第三章線性規(guī)劃及圖解法用線性規(guī)劃解決實(shí)際問(wèn)題的概念總結(jié)

一、線性規(guī)劃數(shù)學(xué)模型三要素：決策變量、約束條件、目標(biāo)函數(shù)二、線性規(guī)劃問(wèn)題隱含的假定：

1、比例性假定------決策變量變化引起的目標(biāo)函數(shù)的改變量和決策變量的改變量成比例，同樣，每個(gè)決策變量的變化引起約束方程左端值的改變量和該變量的改變量成比例。

2、可加性假定------每個(gè)決策變量對(duì)目標(biāo)函數(shù)和約束方程的影響是獨(dú)立于其他變量的，目標(biāo)函數(shù)值是每個(gè)決策變量對(duì)目標(biāo)函數(shù)貢獻(xiàn)的總和。

3、連續(xù)性假定------線性規(guī)劃問(wèn)題中的決策變量應(yīng)取連續(xù)值。

4、確定性假定------線性規(guī)劃問(wèn)題中的所有參數(shù)都是確定的參數(shù)。線性規(guī)劃問(wèn)題不包含隨機(jī)因素。第三章線性規(guī)劃及圖解法用線性規(guī)劃解決實(shí)際問(wèn)題的概念總結(jié)

三、本節(jié)引入的基本概念

1、線性規(guī)劃問(wèn)題所謂線性規(guī)劃，是指求線性函數(shù)在線性(不等式或等式)約束下達(dá)最(小或大)值的決策問(wèn)題；（1）線性規(guī)劃的一般形式----------只有絕對(duì)變量，沒(méi)有松馳變量和剩余變量，約束條件為不等式；（2）線性規(guī)劃的標(biāo)準(zhǔn)形式--------除了絕對(duì)變量，還有松馳變量和剩余變量，約束條件為等式。第三章線性規(guī)劃及圖解法用線性規(guī)劃解決實(shí)際問(wèn)題的概念總結(jié)

三、本節(jié)引入的基本概念

2、基本術(shù)語(yǔ)（1）決策變量----------決策變量是指決策問(wèn)題需要控制的因素一般稱為決策變量（包括絕對(duì)變量、松馳變量和剩余變量）；（2）目標(biāo)函數(shù)（最大目標(biāo)或最小目標(biāo)）-------------用數(shù)學(xué)形式表示出來(lái)的實(shí)際系統(tǒng)的期望目標(biāo)稱為目標(biāo)函數(shù)（價(jià)值體現(xiàn)）；（3）約束條件----------約束條件是指對(duì)決策變量限定一變化空間，是決策決策問(wèn)題中關(guān)鍵因素受到的資源環(huán)境限制。（4）可行域---------------由約束條件所圍成的，符合所有約束條件要求的區(qū)域；第三章線性規(guī)劃及圖解法用線性規(guī)劃解決實(shí)際問(wèn)題的概念總結(jié)

三、本節(jié)引入的基本概念

2、基本術(shù)語(yǔ)（5）凸集合--------凸多邊形---------凸多面體凸多邊形----區(qū)域內(nèi)任意兩點(diǎn)間的連線，都在區(qū)域內(nèi)?；蛩噙呅蔚膬?nèi)角都小于π。（6）可行解---------------可行域中的任一點(diǎn)；（7）基本可行解----------或行域的凸多面體的頂點(diǎn)；（8）初始基本可行解---------初次迭代的基本可行解；（9）線性規(guī)劃的靈敏度分析--------線性規(guī)劃取得最優(yōu)解后，再分析相關(guān)資源限制或所處條件發(fā)生變化時(shí)對(duì)最優(yōu)解或?qū)ψ顑?yōu)值的影響。第三章線性規(guī)劃及圖解法用線性規(guī)劃解決實(shí)際問(wèn)題的概念總結(jié)

三、本節(jié)引入的基本概念

2、基本術(shù)語(yǔ)（10）相差值---------所謂目標(biāo)函數(shù)變量系數(shù)的相差值，是指最優(yōu)解中為0的變量，在其它變量系數(shù)保持不變的情況下，使最優(yōu)解中該變量的值不為0時(shí)，相應(yīng)目標(biāo)函數(shù)變量系數(shù)由現(xiàn)有值再改變的量。（11）目標(biāo)函數(shù)系數(shù)的取值范圍-------線性規(guī)劃取得最優(yōu)解后，目標(biāo)函數(shù)系數(shù)中，在其它系數(shù)都不變前提下，某一系數(shù)的變化不會(huì)改變最優(yōu)解的取值范圍。（12）常數(shù)項(xiàng)的取值范圍-------線性規(guī)劃取得最優(yōu)解后，在其它約束條件常數(shù)項(xiàng)都不變前提下，某一約束條件常數(shù)項(xiàng)的變化不會(huì)改變對(duì)偶價(jià)格的取值范圍。第三章線性規(guī)劃及圖解法用線性規(guī)劃解決實(shí)際問(wèn)題的概念總結(jié)

三、本節(jié)引入的基本概念

2、基本術(shù)語(yǔ)（13）對(duì)偶價(jià)格----------在約束條件中，增加一個(gè)單位的資源量而使最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)的數(shù)量，稱為這個(gè)給條件的對(duì)偶價(jià)格；（14）影子價(jià)格---------約束條件中資源對(duì)目標(biāo)極值的貢獻(xiàn)，是資源的單位價(jià)格，反映資源在企業(yè)內(nèi)部運(yùn)用的貢獻(xiàn)情況?；蛑纲Y源改變時(shí)對(duì)最優(yōu)收益產(chǎn)生的影響，所以又有人把它稱為資源的邊際產(chǎn)出或者資源的機(jī)會(huì)成本，它表示資源在最優(yōu)產(chǎn)品組合時(shí)所具有