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

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

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

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

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

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

6、50)，(0，250)最佳解決方案從點(diǎn)b到點(diǎn)c直線段上的所有點(diǎn)無(wú)限多，最佳值為15000。對(duì)于，17，(3)無(wú)限解，在示例1.5中，如果約束1，2的不等式符號(hào)發(fā)生變化，則線性編程模型將發(fā)生以下變化：目標(biāo)函數(shù)：Max z=50 x1 100 x2約束條件：x1x2300 2x12 400 x 2250、x20、18、x1、x2、可能的域?qū)⒊蔀闊o(wú)限區(qū)域。此時(shí)沒(méi)有限制的最佳解決方案。19，(4)如果沒(méi)有可行的解決方案，則在示例1.5中的線性編程模型中，增加約束x1 400會(huì)導(dǎo)致模型發(fā)生以下變化：目標(biāo)函數(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ū)域。此時(shí)沒(méi)有可行的解決方案，顯然沒(méi)有線性規(guī)劃問(wèn)題的解決方案。x1、x2、o、x1 x 2300、300、200、100、100、200、300、400、x 2250、2x1 x 2400但是因?yàn)閍，b兩種原料的規(guī)格不同，所以需要的加工時(shí)間也不同。加工1噸a原料需要2小時(shí)，加工1噸b原料需要1小時(shí)，公司總共有600小時(shí)的加工時(shí)間。還知道1噸a原料的價(jià)格為2萬(wàn)元，1噸b原料的價(jià)格為3萬(wàn)元，在滿足生產(chǎn)需求的前提下，如何在公司加工能力范圍內(nèi)購(gòu)買a，b兩種原料，使購(gòu)置費(fèi)最低？22，解決方案：目標(biāo)函數(shù)：Min f=2x1 3 x2約束：s.t.

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

9、具有相同的最佳解決方案：也就是說(shuō)，maxz=-c 1x1-c2x2-cnxn與上述兩個(gè)問(wèn)題的最佳解決方案相同，但需要注意的是，最佳解決方案的目標(biāo)函數(shù)值與Min f-Max z、26等符號(hào)不同。2、約束不是等式問(wèn)題。(1)當(dāng)約束為“”(松弛變量)時(shí)，如果將約束設(shè)置為ai1 x1 ai2 x2 ainxnbbi，則可以獲取新變量s，使其等于約束右和左之間的差異s=bi(ai1 x1 ai2 x2 ain xn)。顯然，s也有非負(fù)約束，即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此時(shí)，新約束變?yōu)閍i1 x1 ai2 x2 ain xn-s=bi，28，為使約束從不等式變?yōu)榈仁蕉氲淖兞縮在不等式小于或等于時(shí)稱為“松弛變量”。如果不等式“大于或等于”，則稱為“剩馀變量”。如果原始問(wèn)題中存在多個(gè)等式約束，則將它們轉(zhuǎn)換為標(biāo)準(zhǔn)形式時(shí)，必須徐璐為每個(gè)約束引入其他松弛變量。29，3。右端具有負(fù)值的問(wèn)題：標(biāo)準(zhǔn)要求每個(gè)元件在右端不能為負(fù)值。如果右端系數(shù)為負(fù)值(例如Bi0)，則方程式約束的兩端將乘以-1。-ai1x1-ai2x2-ainxn=-bi。30，示例1.3:將以下線性編程問(wèn)題轉(zhuǎn)換為標(biāo)準(zhǔ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解決方案：首先將目標(biāo)函數(shù)轉(zhuǎn)換為最大化：z第三個(gè)約束條件的右端值為負(fù)值，同時(shí)將等式兩側(cè)的-1相乘。通過(guò)31，3圖形方法的靈敏度分析，上述轉(zhuǎn)換，得到了以下標(biāo)準(zhǔn)形式的線性編程問(wè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變量無(wú)符號(hào)限制問(wèn)題要求每個(gè)變量具有非負(fù)約束。如果Xj變量沒(méi)有非負(fù)約束，則XJ=xj- XJ ，其中xj0，XJ 0可以表示兩個(gè)非負(fù)變量之差的無(wú)符號(hào)限制

12、變量。當(dāng)然，XJ的符號(hào)取決于XJ和XJ的大小。33，示例1.4將以下線性配置問(wèn)題轉(zhuǎn)換為標(biāo)準(zhǔn)格式min f=x12x 3x 3s . t . x1-x2x 34x 12x 8x 1x2x 32x 1 0、x20和34:答案：標(biāo)準(zhǔn)類型為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，目標(biāo)函數(shù)系數(shù)ci的靈敏度分析，系數(shù)ci的變化直接影響目標(biāo)函數(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最佳解決方案在點(diǎn)B(50，250)處發(fā)生更改，必須在直線x1 x2300和x2250之間保持目標(biāo)函數(shù)等高線的坡率。如果C150保持不變，則-1- C1/C2 0，38，-1- 50/C2 0為c250使用范圍中的值。如果C2 100保持不變，則-1-C1/100分析C2的值范圍為100 c10，39，教室練習(xí)，在以下模型中C1的值范圍與最佳解決方案之間的關(guān)系：maxz=C1 x1 9x12s.t.x1x26x12x10x1，x20，40，40x