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

蘭州大學管理學院運籌學

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

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

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

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

例1某工廠在計劃期內要安排I，Ⅱ兩種產品的生產。生產單位產品所需的設備臺時及A，B兩種原材料的消耗以及資源的限制如下表所示。工廠每生產一個單位產品I可獲利50元，每生產一個單位產品Ⅱ可獲利100元，問工廠應分別生產多少單位產品I和產品Ⅱ才能使獲利最多？

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

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

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

x2≤3002xl+x2≤400

x2≤250

xl≥0，

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

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

例2：營養(yǎng)配餐問題

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

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

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

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

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

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

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

x1，

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

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

400x1+x2

300

x2

250x1

0x2

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

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

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

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

)

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

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

在例1中引入三個松弛變量sl、s2、s3后，線性規(guī)劃數(shù)學模型描述為：約束條件：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ī)劃及圖解法四、最小化問題的圖解法例2：下面給出一個求目標函數(shù)最小化的線性規(guī)劃問題。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點為基本可行解。離原較遠的基本可行解為初始基本可行解。

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

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

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

即獲得問題的最優(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

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

約束條件：10x1+

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

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

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

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

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

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

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

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

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

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

假設單位產品Ⅱ的利潤為100元不變，即c2＝100，則有

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

引入兩個述語：允許減少量

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

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

例1中，原來每件產品I和產品Ⅱ的利潤分別為50和100元，現(xiàn)在每件產品I和產品Ⅱ的利潤分別變?yōu)?0和80元，對其進行靈敏度分析。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、多個目標函數(shù)系數(shù)的百分之一百法則

再如例1中，原來每件產品I和產品Ⅱ的利潤分別為50和100元，現(xiàn)在每件產品I和產品Ⅱ的利潤分別變?yōu)?0和70元，對其進行靈敏度分析。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、多個目標函數(shù)系數(shù)的百分之一百法則

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

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

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

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

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

相差值----遞減成本的絕對值

產品資源III資源限制設備11300臺時原料A21400kg原料B01300kg

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

根據(jù)例1建模過程可得本問題的線性規(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)解目標函數(shù)OB五目標函數(shù)中變量系數(shù)ci的相差值分析

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

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

注：

1、最優(yōu)解不為0的變量，相差值必為0，反之不然，因為也有可能是外在約束所致；

2、對于相差值不為0的變量系數(shù)：當目標為求最大值時，當前值加上這個相差值，必等于該變量系數(shù)的上限值，且該變量系數(shù)無下限；此時其相應的變量值就會由原來為0變?yōu)榉?。當目標為求最小值時，當前值減去這個相差值，必等于該變量系數(shù)的下限值，且該變量系數(shù)無上限；此時其相應的變量值就會由原來為0變?yōu)榉?。

3、對于目標求最大值時，遞減成本為負；對于目標求最小值時，遞減成本為正。第三章線性規(guī)劃及圖解法用線性規(guī)劃解決實際問題的概念總結

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

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

2、可加性假定------每個決策變量對目標函數(shù)和約束方程的影響是獨立于其他變量的，目標函數(shù)值是每個決策變量對目標函數(shù)貢獻的總和。

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

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

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

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

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

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

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

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

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

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

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

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