第2章 線性規(guī)劃的圖解法.ppt

1、第一、二章線性規(guī)劃的圖形方法，第一問題建議第二章圖形3圖形方法的靈敏度分析，第二章、第二章線性規(guī)劃的圖形方法，管理的一些典型線性規(guī)劃應用中導線的合理利用問題：生產(chǎn)保證條件下的最小材料問題：從原材料供應的限制中獲取最大利益投資問題的方法：在投資項目中選擇方案，投資回報最大化產(chǎn)品生產(chǎn)計劃：人力、物力、 合理利用財力等以最大限度地提高利潤的人員配置：以最少的人員滿足業(yè)務需要的運輸問題：如何開發(fā)最大限度地減少總運費的運輸程序；3，線性編程的配置：適合使用目標函數(shù)Max F或Min F約束s.t. (subject to)決策變量符號表示可控制因素；4，1問題建議；實例1。 工廠在計劃期間準備、生產(chǎn)兩種

2、產(chǎn)品、生產(chǎn)單位產(chǎn)品所需的設備臺和a、b兩種原材料的消耗、資源限制(下表：問題：為了在工廠中獲得最多的利潤，需要分別生產(chǎn)多少單位、產(chǎn)品？5，線性編程模型：目標函數(shù)：Max z=50 x1 100 x2約束：s.t.x1x2300 2x2x400 x2250 x1，x20，6，1問題建議，建模過程1。了解要解決的問題，了解解決問題的目標和條件；每個值集定義表示方案的決策變量(x1、x2、xn)。3.作為決策變量的線性函數(shù)編寫目的函數(shù)，以確定最大化或最小化目標。4.表示解決問題時要遵循的約束為一系列決策變量的等式或不等式。7，一般格式目的函數(shù)：max (min) z=c11c2x2xn限制條件：s.

3、t.a11a12x12 a1n xn (=，)B1 a21 x1 a22 x2 a2n xn (=，)B2 am1 x1目標函數(shù)：Max z=50 x1 100 x2約束：s . t . x1x 2300(a)2x2x 400(b)x 2250(c)X10(d)x20(e)最佳解決方案：xx通過實例1詳細說明了9，2圖解決方案，(1)分別取決定變量x1，并使用x2為坐標矢量設置正交坐標系。直角坐標系中任意點的坐標表示確定變量的一組值，示例1中的每個約束條件表示半平面。10，2圖解，(2)對于每個不等式(約束)，首先在坐標系中使該方程直線，然后確定不等式確定的半平面。11，2圖解決方案，(3)組

4、合5個圖以聚合每個約束的公共部分，如圖2-1所示。12，2圖解，(4)目標函數(shù)z=50 x1 100 x2，z獲取固定值時得到直線。吳宣儀的每個點都有相同的目標函數(shù)值，稱為“等值線”。平行移動等值線，移動到b點時z在可行域內(nèi)最大化。a、b、c、d、e是可執(zhí)行域的頂點，受限制約束的可執(zhí)行域的頂點也受到限制。13、重要結(jié)論：有最優(yōu)解。必須存在與最佳解決方案相對應的可行域(P12)的頂點。無限多個最優(yōu)解。如果將示例1中的目標函數(shù)更改為max z=50 x1 50 x2，則線段BC上的所有點都表示最佳解決方案。無限解決方案。行字段的范圍可以無限擴展，目標函數(shù)值可以無限擴展或無限擴展。通常，這表示模型中

5、存在錯誤，并忽略某些必需的約束條件；沒有可行的解決方案。如果在示例1的數(shù)學模型中再添加一個約束條件4x1 3x21200，則可執(zhí)行域為空域，不存在滿足約束條件的解決方案，并且不存在最佳解決方案。14，(1)存在唯一最佳解決方案。示例1.5在此不再作進一步說明。如果存在線性規(guī)劃問題的最優(yōu)解，那么可能域中的頂點對應于最優(yōu)解，唯一最優(yōu)解必須來自可能域中的頂點。，15，示例1。在5的線性編程模型中，目標函數(shù)：Max z=50 x1 100 x2約束：x1 x 2300 2x2400 x 2250 X10，x2 0目標函數(shù)更改為max z=50 x150x2，則(2)對于無限多最優(yōu)解，為16，A(0，2

6、50)，(0，250)最佳解決方案從點b到點c直線段上的所有點無限多，最佳值為15000。對于，17，(3)無限解，在示例1.5中，如果約束1，2的不等式符號發(fā)生變化，則線性編程模型將發(fā)生以下變化：目標函數(shù)：Max z=50 x1 100 x2約束條件：x1x2300 2x12 400 x 2250、x20、18、x1、x2、可能的域?qū)⒊蔀闊o限區(qū)域。此時沒有限制的最佳解決方案。19，(4)如果沒有可行的解決方案，則在示例1.5中的線性編程模型中，增加約束x1 400會導致模型發(fā)生以下變化：目標函數(shù)：Max z=50 x1 100 x2約束條件：x1 x 23002 x1 x 2400 x 22

7、50 x1400 x10，x20，20，20，可執(zhí)行域變?yōu)榭諈^(qū)域。此時沒有可行的解決方案，顯然沒有線性規(guī)劃問題的解決方案。x1、x2、o、x1 x 2300、300、200、100、100、200、300、400、x 2250、2x1 x 2400但是因為a，b兩種原料的規(guī)格不同，所以需要的加工時間也不同。加工1噸a原料需要2小時，加工1噸b原料需要1小時，公司總共有600小時的加工時間。還知道1噸a原料的價格為2萬元，1噸b原料的價格為3萬元，在滿足生產(chǎn)需求的前提下，如何在公司加工能力范圍內(nèi)購買a，b兩種原料，使購置費最低？22，解決方案：目標函數(shù)：Min f=2x1 3 x2約束：s.t.

8、x1x2350 x1125 2x12 600x1，x20使用圖形方法。下圖：qpoint坐標(250，100)是最佳解決方案。23，3圖形方式的靈敏度分析，線性編程的標準化通用格式目標函數(shù)：max (min) z=c11c2x2cn xn約束：s.t.a11a12xa1n xn (=，)B1 a21 x1 a22 x2 a2n xn (=，)約束是方程式。決定變量不是負數(shù)。右端不是負值。對于各種非標準形式的線性編程問題，始終通過以下轉(zhuǎn)換確定標準格式：25，1:目標函數(shù)最小化問題：可以通過將目標函數(shù)設置為Min f=c1x1 c2x2 cnxn(可能)來創(chuàng)建z -f。此最小化問題與以下最大化問題

9、具有相同的最佳解決方案：也就是說，maxz=-c 1x1-c2x2-cnxn與上述兩個問題的最佳解決方案相同，但需要注意的是，最佳解決方案的目標函數(shù)值與Min f-Max z、26等符號不同。2、約束不是等式問題。(1)當約束為“”(松弛變量)時，如果將約束設置為ai1 x1 ai2 x2 ainxnbbi，則可以獲取新變量s，使其等于約束右和左之間的差異s=bi(ai1 x1 ai2 x2 ain xn)。顯然，s也有非負約束，即s0。如果新約束條件為ai1 x1 ai2 x2 ain xn s=bi，27，(1)約束條件為“”(-剩馀變量)，則約束條件為ai1 x1 ai2 x2 ain

10、xn bi，則s=(ai1 x1 ai2 x2 ain此時，新約束變?yōu)閍i1 x1 ai2 x2 ain xn-s=bi，28，為使約束從不等式變?yōu)榈仁蕉氲淖兞縮在不等式小于或等于時稱為“松弛變量”。如果不等式“大于或等于”，則稱為“剩馀變量”。如果原始問題中存在多個等式約束，則將它們轉(zhuǎn)換為標準形式時，必須徐璐為每個約束引入其他松弛變量。29，3。右端具有負值的問題：標準要求每個元件在右端不能為負值。如果右端系數(shù)為負值(例如Bi0)，則方程式約束的兩端將乘以-1。-ai1x1-ai2x2-ainxn=-bi。30，示例1.3:將以下線性編程問題轉(zhuǎn)換為標準形式min f=2 x1-3x 24

11、 x4x 3s . t . 3x 14x 2-5x 62 xx1x 38x 12 xx 3=-9x 1，x2，x30解決方案：首先將目標函數(shù)轉(zhuǎn)換為最大化：z第三個約束條件的右端值為負值，同時將等式兩側(cè)的-1相乘。通過31，3圖形方法的靈敏度分析，上述轉(zhuǎn)換，得到了以下標準形式的線性編程問題：max z=-2x 13x 2-4x3s . t . 3x 14x 2-5x3x 4=62xx 3-X5=8-x1-x2-x3=9x 1，x2，x3，x4，X5變量無符號限制問題要求每個變量具有非負約束。如果Xj變量沒有非負約束，則XJ=xj- XJ ，其中xj0，XJ 0可以表示兩個非負變量之差的無符號限制

12、變量。當然，XJ的符號取決于XJ和XJ的大小。33，示例1.4將以下線性配置問題轉(zhuǎn)換為標準格式min f=x12x 3x 3s . t . x1-x2x 34x 12x 8x 1x2x 32x 1 0、x20和34:答案：標準類型為maxz=-x12x 2-3x 30 S10 S2 0 s3s . t . x1x2x 3 S1=4x x12 x32 x3 s32 x1，x2，x3，x3，S1，S2，S1，36，1，目標函數(shù)系數(shù)ci的靈敏度分析，系數(shù)ci的變化直接影響目標函數(shù)等值線的斜率k。KBCkkAB，最佳解決方案不變。x1、x2、o、x1 x 2300、300、200、100、200、300、400、x 2250、2xx1 x 2400、b、a要防止maxz C1 x1 C2 x2最佳解決方案在點B(50，250)處發(fā)生更改，必須在直線x1 x2300和x2250之間保持目標函數(shù)等高線的坡率。如果C150保持不變，則-1- C1/C2 0，38，-1- 50/C2 0為c250使用范圍中的值。如果C2 100保持不變，則-1-C1/100分析C2的值范圍為100 c10，39，教室練習，在以下模型中C1的值范圍與最佳解決方案之間的關(guān)系：maxz=C1 x1 9x12s.t.x1x26x12x10x1，x20，40，40x