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

第三章線性規(guī)劃及圖解法第三章線性規(guī)劃及圖解法確定型決策——線性規(guī)劃方法線性規(guī)劃——所有資源限制條件式和目標(biāo)式都是自變量的一次方關(guān)系。描述的是在一定資源限制下(自然狀態(tài))，給出了很多個(gè)可以選擇的不方案(運(yùn)行方案)，從這些方案中找到一個(gè)最好的方案來執(zhí)行。第一節(jié)問題的提出

一、線性規(guī)劃數(shù)學(xué)模型二、線性規(guī)劃模型的三個(gè)基本要素三、線性規(guī)劃數(shù)學(xué)模型的一般形式一、線性規(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元，問工廠應(yīng)分別生產(chǎn)多少單位產(chǎn)品I和產(chǎn)品Ⅱ才能使獲利最多？產(chǎn)品資源III資源限制設(shè)備11300臺(tái)時(shí)原料A21400kg原料B01250kg建立問題的數(shù)學(xué)關(guān)系2、用xl和x2以線性函數(shù)形式表達(dá)工廠所要求的最大利潤的目標(biāo):單位產(chǎn)品I和Ⅱ的利潤

3、以xl和

x2的線性不等式來表示問題中相應(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)量。例1的線性規(guī)劃數(shù)學(xué)模型

maxz＝50xl+100x2滿足條件：xl＋

x2≤3002xl+x2≤400

x2≤250

xl≥0，

x2≥0即：這一類問題都可以用這種語言、這種方式來表達(dá)。

二、線性規(guī)劃模型的三個(gè)基本要素（1）決策變量（約束變量）：用符號(hào)來表示可控制的因素，如xi。（2）目標(biāo)函數(shù)：Maxz

或Minf，用來計(jì)算和實(shí)現(xiàn)問題目標(biāo)。（3）約束條件：s.t.(subjectto)滿足于（一個(gè)等式或不等式組），一般是問題的資源限制條件。例2：營養(yǎng)配餐問題假定一個(gè)成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場上只有四種食品可供選擇，它們每千克所含的熱量和營養(yǎng)成分及市場價(jià)格見下表。問如何選購才能在滿足營養(yǎng)的前提下使購買食品的費(fèi)用最??？序號(hào)食品名稱熱量(kcal/kg)蛋白質(zhì)(g/kg)鈣(mg/kg)價(jià)格(元/kg)1雞肉100050400142雞蛋8006020063大米9002030034白菜200105002解：（1）確定決策變量設(shè)xi為第i種食品每天的購入量；（3）確定約束條件食品的熱量、蛋白質(zhì)和鈣的單位含量構(gòu)成和總含量應(yīng)滿足最低要求。（2）確定目標(biāo)函數(shù)購買食品的費(fèi)用為最小，總費(fèi)用為：14x1+6x2+3x3+2x4配餐問題的線性規(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ī)劃問題的建模過程（1）理解要解決的問題。明確在什么條件下，要追求什么目標(biāo)。（2）定義決策變量。每個(gè)問題都用一組決策變量(x1,x2,…,xn)表示，當(dāng)這組決策變量取具體值時(shí)就代表一個(gè)具體方案，一般這些變量取值是非負(fù)的。（3）用決策變量的線性函數(shù)形式寫出所要追求的目標(biāo)，即目標(biāo)函數(shù)，按問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。（4）用一組決策變量的等式或不等式來表示在解決問題過程中所必須遵循的約束條件（決策分析中的自然狀態(tài)）。三、線性規(guī)劃數(shù)學(xué)模型的一般形式

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

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

xn≥0

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

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

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

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

x1，

x2的一組值，也就代表了一個(gè)具體的決策方案。一、最大化問題的圖解法

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

400x1+x2

300

x2

250x1

0x2

0的區(qū)域——可行域可行域圖3-2線性規(guī)劃問題的可行域0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)O(0,0)線性規(guī)劃模型的可行域可行域的幾何形狀可千變?nèi)f化，但幾何結(jié)構(gòu)都是凸集。圖3-3最優(yōu)目標(biāo)函數(shù)值0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)z=0=50x1+100x2圖3-3最優(yōu)目標(biāo)函數(shù)值0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)z=10000=50x1+100x2圖3-3最優(yōu)目標(biāo)函數(shù)值0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)z=20000=50x1+100x2圖3-3最優(yōu)目標(biāo)函數(shù)值0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)z=30000=50x1+100x2圖3-3最優(yōu)目標(biāo)函數(shù)值0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)z=27500=50x1+100x2最優(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單位，可得最大利潤27500元。二、線性規(guī)劃問題的解1、在線性規(guī)劃問題的解集合中，若約束條件能構(gòu)成一個(gè)封閉的可行域，則可行域的任意點(diǎn)都是問題的一個(gè)可行解，這些可行解中必有最優(yōu)解。若最優(yōu)解是可行域中一個(gè)點(diǎn)，則這個(gè)解是線性規(guī)劃的唯一最優(yōu)解。唯一最優(yōu)解都必落在可行域的頂點(diǎn)上，可行域的所有頂點(diǎn)稱為基本可行解；對(duì)于求最大目標(biāo)的線性規(guī)劃問題，取Z值最小的基本可行解為初始基本可行解，再依次迭代至最優(yōu)解。求最小目標(biāo)的情況，可選可行域中任意目標(biāo)初函數(shù)值較大的點(diǎn)為初始基本可行解，再依次迭代至最優(yōu)解。線性規(guī)劃問題的解（2）2、若可行域的某一個(gè)邊與目標(biāo)函數(shù)平行，則最優(yōu)解是這條邊上的所有點(diǎn)，所以是無窮多點(diǎn)，此時(shí)線性規(guī)劃問題就有無窮多解（或最優(yōu)解不唯一）。3、對(duì)于目標(biāo)為求最大的線性規(guī)劃問題，若約束條件不能構(gòu)成封閉（或有限）區(qū)域的可行域，如沿目標(biāo)函數(shù)值增大的方向無限擴(kuò)散而沒有邊界。這時(shí)的可行域是無界的，線性規(guī)劃問題就有無界解。4、若約束條件雖構(gòu)成封閉區(qū)域，但是兩個(gè)及兩個(gè)以上的互不相連的區(qū)域，那么這些區(qū)域中的點(diǎn)都不能同時(shí)滿足約束要求，因此都不是可行域，則線性規(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è)“≤”約束條件中沒使用的資源或能力被稱之為松弛量。松弛變量松弛變量:代表沒使用的資源或能力的變量。約束條件實(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+0

sl+0s2+0s3；四、最小化問題的圖解法例2：下面給出一個(gè)求目標(biāo)函數(shù)最小化的線性規(guī)劃問題。

minf=11x1+8x2約束條件10x1+2x2≥203x1+3x2≥184x1+9x2≥36

x1，x2≥0圖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)圖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)取最小值。圖3-5例2目標(biāo)函數(shù)的最優(yōu)解●●●●B(1,5)x28642x12468f=11x1+8x2

即獲得問題的最優(yōu)解：x1=1,x2=5。最優(yōu)值：minf=11x1+8x2=51五、多于資源低限的剩余量

把例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“≥”約束條件中超過資源或能力最低限量被稱之為剩余量。剩余變量剩余變量:代表沒超過資源或能力最低限的變量。約束條件實(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+0

sl+0s2+0s3；六、線性規(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ī)劃標(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)第三節(jié)線性規(guī)劃問題的靈敏度分析靈敏度分析研究線性規(guī)劃的一些系數(shù)ci,

aij,

bj的微小變化對(duì)最優(yōu)解所產(chǎn)生的影響。靈敏度分析的意義：用確定的（一組理想的）環(huán)境數(shù)據(jù)建立模型，研究環(huán)境變化情況下不確定的（一系列現(xiàn)實(shí)的）問題。一、目標(biāo)函數(shù)中變量系數(shù)ci的取值范圍分析

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

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

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

即只要當(dāng)產(chǎn)品Ⅱ的利潤為100元，產(chǎn)品I的利潤在0-100元之間時(shí)，坐標(biāo)xl=50，x2=250的頂點(diǎn)B仍是最優(yōu)解。－1≤≤0

0≤cl≤100

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

050100C2

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

常數(shù)項(xiàng)bj代表的是廠房面積、生產(chǎn)總時(shí)間、設(shè)備數(shù)量等所提供給企業(yè)經(jīng)營的資源限制量。bj的靈敏度分析是研究資源的變化對(duì)最優(yōu)解的影響。bj的改變是可行域某一邊的平行移動(dòng)，這種改變必將導(dǎo)致最優(yōu)解和最優(yōu)值的改變。圖3-7常數(shù)項(xiàng)的變化改變可行域●BC直線Z(目標(biāo)函數(shù))100200300x2200100300x10ODA例1中的可行域是OABCD，最優(yōu)解是B（20，250），最優(yōu)值是27500。圖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，獲得的最大利潤為28000（元）。對(duì)偶價(jià)格在約束條件常數(shù)中增加一個(gè)單位而使最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)的數(shù)量稱之為這個(gè)約束條件的對(duì)偶價(jià)格。圖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à)格為零。對(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ù)值變得更?。ǜ螅磺笞钚≈禃r(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à)格必等于零。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à)格的改變。確切地說，常數(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)的取值范圍。圖3-90100200300400x1400300200100x2可行域ACx2xl+x2=300=b1x2=250=b32xl+x2=400=b2最優(yōu)解目標(biāo)函數(shù)OB常數(shù)項(xiàng)沒變化的最優(yōu)解D最優(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à)格就不變。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)開始改變時(shí)的常數(shù)項(xiàng)值，就是這個(gè)約束條件常數(shù)項(xiàng)的下限值。即本例常數(shù)項(xiàng)b1的下限為250。圖3-120100200300400x1400300200100x2可行域Ax2xl+x2=325=b1x2=250=b32xl+x2=400=b2最優(yōu)解目標(biāo)函數(shù)OBC同樣，常數(shù)項(xiàng)增大，到可行域結(jié)構(gòu)開始改變時(shí)的常數(shù)項(xiàng)值，就是這個(gè)約束條件常數(shù)項(xiàng)的上限值。即本例常數(shù)項(xiàng)b1的上限為325。表3-6約束條件中常數(shù)項(xiàng)的取值范圍

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

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

當(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í)變化的靈敏度分析。1、多個(gè)目標(biāo)函數(shù)系數(shù)的百分之一百法則允許增加量——目標(biāo)函數(shù)的決策變量系數(shù)在上限范圍內(nèi)的最大增加量（最高限-當(dāng)前值）。引入兩個(gè)述語：允許減少量

——目標(biāo)函數(shù)的決策變量系數(shù)在下限范圍內(nèi)的最大減少量（當(dāng)前值-最低限）。目標(biāo)函數(shù)決策變量系數(shù)的百分之一百法則：對(duì)于所有變化的目標(biāo)函數(shù)決策變量系數(shù)，當(dāng)其所有實(shí)際增加量與允許增加量的百分比和所有實(shí)際減少量與允許減少量的百分比之和不超過百分之一百時(shí)，最優(yōu)解不變。即：1、多個(gè)目標(biāo)函數(shù)系數(shù)的百分之一百法則例1中，原來每件產(chǎn)品I和產(chǎn)品Ⅱ的利潤分別為50和100元，現(xiàn)在每件產(chǎn)品I和產(chǎ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)值為235001、多個(gè)目標(biāo)函數(shù)系數(shù)的百分之一百法則再如例1中，原來每件產(chǎn)品I和產(chǎn)品Ⅱ的利潤分別為50和100元，現(xiàn)在每件產(chǎn)品I和產(chǎ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)值為210001、多個(gè)目標(biāo)函數(shù)系數(shù)的百分之一百法則又如例1中，原來每件產(chǎn)品I和產(chǎn)品Ⅱ的利潤分別為50和100元，現(xiàn)在每件產(chǎn)品I和產(chǎ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)值為208002、多個(gè)約束條件中常數(shù)項(xiàng)同時(shí)變化約束條件中常數(shù)項(xiàng)的百分之一百法則：對(duì)于所有變化的約束條件中的常數(shù)項(xiàng)，當(dāng)其所有實(shí)際增加量與允許增加量的百分比和所有實(shí)際減少量與允許減少量的百分比之和不超過百分之一百時(shí)，則這些約束條件的對(duì)偶價(jià)格不變。即：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%沒有超過100%，所以三個(gè)約束條件的對(duì)偶價(jià)格：50，0，50，都不變。但最優(yōu)值變?yōu)椋?77502、多個(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à)格由原來的50，0，50改變?yōu)?，25，75百分之一百使用說明：

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

五目標(biāo)函數(shù)中變量系數(shù)ci的相差值分析

相差值----遞減成本的絕對(duì)值產(chǎn)品資源III資源限制設(shè)備11300臺(tái)時(shí)原料A21400kg原料B01300kg例3將本章例1中,原料B的限制量改變?yōu)?00kg，其它條件都不變,重新建立模型,重新求解。

五目標(biāo)函數(shù)中變量系數(shù)ci的相差值分析

根據(jù)例1建模過程可得本問題的線性規(guī)劃模型為：

maxz＝50xl+100x2；滿足條件：xl＋

x2≤3002xl+x2≤400

x2≤300

xl≥0，

x2≥00100200300400x1400300200100x2可行域ACx2xl+x2=300=b1x2=3002xl+x2=400=b2最優(yōu)解目標(biāo)函數(shù)OB五目標(biāo)函數(shù)中變量系數(shù)ci的相差值分析

五目標(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)有值再改變的量。五目標(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ù)無下限；此時(shí)其相應(yīng)的變量值就會(huì)由原來為0變?yōu)榉?。當(dāng)目標(biāo)為求最小值時(shí)，當(dāng)前值減去這個(gè)相差值，必等于該變量系數(shù)的下限值，且該變量系數(shù)無上限；此時(shí)其相應(yīng)的變量值就會(huì)由原來為0變?yōu)榉?。

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

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

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ī)劃問題中的決策變量應(yīng)取連續(xù)值。

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

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

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

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

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

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

2、基本術(shù)語（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ī)劃