運(yùn)籌學(xué)48學(xué)時(shí)參考課件new chapter1線(xiàn)性規(guī)劃基礎(chǔ)

1、建模實(shí)例 圖解法 線(xiàn)性部分內(nèi)容及要求(Linear program) 是運(yùn)籌學(xué)中研究較早，發(fā)展較快，應(yīng)線(xiàn)性用較廣, 比較成 一個(gè)分支。它實(shí)質(zhì)上是解決稀缺 在有競(jìng)爭(zhēng)的使用方向中如何進(jìn)行最優(yōu)分配的問(wèn)題，即尋求整個(gè)問(wèn)題的某個(gè)整體指標(biāo) 最優(yōu)的問(wèn)題。比如，經(jīng)營(yíng)管理中的:生產(chǎn)組織與計(jì)劃安排問(wèn)題合理下料問(wèn)題配料問(wèn)題問(wèn)題 布局問(wèn)題等第一章第二章第三章第四章線(xiàn)性線(xiàn)性線(xiàn)性整數(shù)基礎(chǔ)的單純形解法的對(duì)偶理論關(guān)于用軟件求解線(xiàn)性問(wèn)題，將在中間適時(shí)穿插。建模實(shí)例 圖解法內(nèi)容分布建模實(shí)例 圖解法第一章線(xiàn)性基礎(chǔ)建模實(shí)例 圖解法1.1 線(xiàn)性建模實(shí)例建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例從模型的角度：線(xiàn)性問(wèn)題就是求一個(gè)線(xiàn)性函數(shù)在滿(mǎn)足一組線(xiàn)性

2、等式或不等式在變量為非負(fù)條件下的極值問(wèn)題的總稱(chēng)。建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例從模型的角度：線(xiàn)性問(wèn)題就是求一個(gè)線(xiàn)性函數(shù)在滿(mǎn)足一組線(xiàn)性等式或不等式在變量為非負(fù)條件下的極值問(wèn)題的總稱(chēng)。其一般形式 為：max / minZ = c1x1 + c2x2 + · · · + cnxn a11x1 + a12x2 + · · · + a1nxn= (>, 6)b1= (>, 6)b2s.t.a21x1 + a22x2 + · · · + a2nxn. . .am1x1 + am2x2 + · &

3、#183; · + amnxn = (>, 6)bmx1, x2, · · · , xn > 0建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例從模型的角度：線(xiàn)性問(wèn)題就是求一個(gè)線(xiàn)性函數(shù)在滿(mǎn)足一組線(xiàn)性等式或不等式在變量為非負(fù)條件下的極值問(wèn)題的總稱(chēng)。其一般形式 為：Z = c1x1 + c2x2 + · · · + cnxna11x1 + a12x2 + · · · + a1nxn= (>, 6)b1= (>, 6)b2s.t.a21x1 + a22x2 + · ·

4、83; + a2nxn. . .am1x1 + am2x2 + · · · + amnxn = (>, 6)bmx1, x2, · · · , xn > 0目標(biāo)函數(shù)max / min建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例從模型的角度：線(xiàn)性問(wèn)題就是求一個(gè)線(xiàn)性函數(shù)在滿(mǎn)足一組線(xiàn)性等式或不等式在變量為非負(fù)條件下的極值問(wèn)題的總稱(chēng)。其一般形式 為：Z = c1x1 + c2x2 + · · · + cnxn a11x1 + a12x2 + · · · + a1nxn= (>,

5、6)b1= (>, 6)b2s.t.a21x1 + a22x2 + · · · + a2nxn. . .am1x1 + am2x2 + · · · + amnxn = (>, 6)bmx1, x2, · · · , xn > 0目標(biāo)函數(shù)的評(píng)價(jià)標(biāo)準(zhǔn)max 或 min 二選一。max / min建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例從模型的角度：線(xiàn)性問(wèn)題就是求一個(gè)線(xiàn)性函數(shù)在滿(mǎn)足一組線(xiàn)性等式或不等式在變量為非負(fù)條件下的極值問(wèn)題的總稱(chēng)。其一般形式 為：max / mins.t.Z = c1x1 + c2

6、x2 + · · · + cnxna11x1 + a12x2 + · · · + a1nxn= (>, 6)b1= (>, 6)b2a21x1 + a22x2 + · · · + a2nxn. . .am1x1 + am2x2 + · · · + amnxn = (>, 6)bmx1, x2, · · · , xn > 0目標(biāo)函數(shù)中的多項(xiàng)式必須為線(xiàn)性函數(shù)，其中 xj 為決策變量，cj 稱(chēng)為 xj 的目標(biāo)函數(shù)系數(shù)。建模實(shí)例

7、圖解法 線(xiàn)性建模實(shí)例從模型的角度：線(xiàn)性問(wèn)題就是求一個(gè)線(xiàn)性函數(shù)在滿(mǎn)足一組線(xiàn)性等式或不等式在變量為非負(fù)條件下的極值問(wèn)題的總稱(chēng)。其一般形式 為：max / min s.t. Z = c1x1 + c2x2 + · · · + cnxnx1, x2, · · · , xn > 0約束條件a11x1 + a12x2 + · · · + a1nxn = (>, 6)b1a21x1 + a22x2 + · · · + a2nxn = (>, 6)b2. . .am1x1

8、+ am2x2 + · · · + amnxn = (>, 6)bm建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例從模型的角度：線(xiàn)性問(wèn)題就是求一個(gè)線(xiàn)性函數(shù)在滿(mǎn)足一組線(xiàn)性等式或不等式在變量為非負(fù)條件下的極值問(wèn)題的總稱(chēng)。其一般形式 為：max / minZ = c1x1 + c2x2 + · · · + cnxn a11x1 + a12x2 + · · · + a1nxn= (>, 6)b1= (>, 6)b2 s.t. a21x1 + a22x2 + · · · + a2nx

9、n. . .am1x1 + am2x2 + · · · + amnxn = (>, 6)bmx1, x2, · · · , xn > 0subject to 的縮寫(xiě)，表示目標(biāo)函數(shù)的實(shí)現(xiàn)必須滿(mǎn)足后續(xù)的約束建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例從模型的角度：線(xiàn)性問(wèn)題就是求一個(gè)線(xiàn)性函數(shù)在滿(mǎn)足一組線(xiàn)性等式或不等式在變量為非負(fù)條件下的極值問(wèn)題的總稱(chēng)。其一般形式 為：max / mins.t.Z = c1x1 + c2x2 + · · · + cnxnx1, x2, · · · ,

10、xn > 0線(xiàn)性約束方程或不等式組對(duì)于約束不等式，其不等號(hào)必須為 > 或 6 。a11x1 + a12x2 + · · · + a1nxn = (>, 6)b1a21x1 + a22x2 + · · · + a2nxn = (>, 6)b2. . .am1x1 + am2x2 + · · · + amnxn = (>, 6)bm建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例從模型的角度：線(xiàn)性問(wèn)題就是求一個(gè)線(xiàn)性函數(shù)在滿(mǎn)足一組線(xiàn)性等式或不等式在變量為非負(fù)條件下的極值問(wèn)題的總稱(chēng)。其一般形式 為：m

11、ax / minZ = c1x1 + c2x2 + · · · + cnxn a11x1 + a12x2 + · · · + a1nxn= (>, 6)b1= (>, 6)b2s.t.a21x1 + a22x2 + · · · + a2nxn. . .am1x1 + am2x2 + · · · + amnxn = (>, 6)bmx1, x2, · · · , xn > 0決策變量的非負(fù)約束建模實(shí)例 圖解法線(xiàn)性規(guī)劃建模步驟

12、建立實(shí)際問(wèn)題的線(xiàn)性規(guī)劃模型的基本步驟：第一步 選擇合適的決策變量；第二步 根據(jù)決策目標(biāo)（評(píng)價(jià)標(biāo)準(zhǔn)）寫(xiě)出線(xiàn)性目標(biāo)函數(shù)；第三步 寫(xiě)出問(wèn)題中所有（顯式或隱含的）線(xiàn)性約束條件，包括變量的非負(fù)約束。建模實(shí)例 圖解法 線(xiàn)性建模建立實(shí)際問(wèn)題的線(xiàn)性模型的基本步驟：第一步 選擇合適的決策變量；第二步 根據(jù)決策目標(biāo)（評(píng)價(jià)標(biāo)準(zhǔn)）寫(xiě)出線(xiàn)性目標(biāo)函數(shù)；第三步 寫(xiě)出問(wèn)題中所有（顯式或隱含的）線(xiàn)性約束條件，包括變量的非負(fù)約束。注正確、科學(xué)地選擇了決策變量，則建模工作就完成了一半。步驟建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例例1-1 生產(chǎn)計(jì)劃問(wèn)題F 公司每周根據(jù)原材料 M1 和 M2 的采購(gòu)數(shù)量來(lái)安排其A、B和 C 的生產(chǎn)計(jì)劃。已知各的

13、消耗、預(yù)期的利潤(rùn)水平以及本周的可用原材料數(shù)量如表1-1所示。表 1-1: 三種的基本信息表問(wèn)：這 3 種各應(yīng)生產(chǎn)多少，能使 F 公司獲得最大的利潤(rùn)？消耗ABC可用原材料原材料M1 M2824251320100利潤(rùn)542建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例max Z = 5x1 + 4x2 + 2x3 s.t. 8x1 + 4x2 + 5x3 6 3202x1 + 2x2 + x3 6 100x1, x2, x3 > 0建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例例 1-3 財(cái)務(wù)計(jì)劃問(wèn)題某公司未來(lái) 6 年年初的現(xiàn)金需求如表1-4所示。表 1-4: 某未來(lái) 6 年的現(xiàn)金需求（：萬(wàn)元）該公司管理層決定在今年年底劃

14、撥一筆資金，要求在確保各年的資金需求得到保障的同時(shí)，實(shí)現(xiàn)資金的有效利用。目前可選擇一年期定期存款和國(guó)債兩種投資方式。一年期的定期存款方式，年利率為 3%；如果選擇如果選擇國(guó)債，雖然能獲得高于一年期的定期存款的利率，但受到以下限制：國(guó)債只能在第 1 年年初；國(guó)債的實(shí)際價(jià)格要高于其票面價(jià)格，且只能在到期日按票面價(jià) 格收回本金。年份123456現(xiàn)金350405355260215230建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例續(xù)上已知第 1 年年初可選擇的國(guó)債有兩種，其基本情況如表1-5所示。表 1-5: 國(guó)債基本數(shù)據(jù)信息表問(wèn)：公司最少需要?jiǎng)潛芏嗌儋Y金，并如何投資，才能滿(mǎn)足未來(lái) 6 年的現(xiàn)金需求？債券票面價(jià)格（元

15、）實(shí)際價(jià)格（元）年利率（%）到期年限110,00012,0007.84210,00014,30010.75建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例解：決策變量：設(shè)劃撥資金總額為 y 萬(wàn)元，第 1 年年初所的 1、2一年期型債券的票面總金額分別為 xa, xa 萬(wàn)元，每年年初存入的1 2bb。定期存款金額分別為 x , · · · , x16目標(biāo)函數(shù)：本問(wèn)題的目標(biāo)為劃撥資金總額最少，根據(jù)決策變量的設(shè)定，目標(biāo)函數(shù)為：min Z = y建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例約束條件：這一類(lèi)問(wèn)題約束條件常常用投資與余額表來(lái)分析。對(duì) 于本例，各年的現(xiàn)金使用與余額如表1-6所示，為萬(wàn)元。表 1

16、-6:這類(lèi)問(wèn)題中隱含的約束條件是，每年年初可使用的金額，不能超 出上一年年末的余額。又因 例的特殊性，每年年初可使用的金額應(yīng)等于上一年年末的余額。年份年初現(xiàn)金需求 + 年初投資額年末現(xiàn)金余額1350 + 1.2xa + 1.43xa + xb1210.078xa + 0.107xa + 1.03xb1212405 + xb20.078xa + 0.107xa + 1.03xb1223355 + xb30.078xa + 0.107xa + 1.03xb1234260 + xb41.078xa + 0.107xa + 1.03xb1245215 + xb51.107xa + 1.03xb2562

17、30 + xb61.03xb6建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例本問(wèn)題的線(xiàn)性模型為：mins.t.Z = yaaxby 1.2x 1.43x = 350= 405= 355= 260= 215= 230121aabb0.078x+ 0107x + 1.03x x.1212aabb0.078x+ 0107x + 1.03x x.1223aabb0.078x+ 0107x + 1.03x x.1234aabb1.078x+ 0107x + 1.03x x.1245abb1107x + 1.03x x.256y, xa, xb > 0, i = 1, 2; j = 1, · ·

18、 · , 6ij建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例例 1-4 生產(chǎn)計(jì)劃問(wèn)題N 公司收到P1 和 P2 的限時(shí)訂單 1600 件和 1000 件。這兩種都是由組件 C1, C2 和 C3 各一件組裝而成，組件可自行生產(chǎn)，也可外購(gòu)。但不同的相同組件的生產(chǎn)和外購(gòu)成本均不同。如下表。表 1-7: 各組件的生產(chǎn)工時(shí)（分鐘）、生產(chǎn)成本及外購(gòu)成本由于現(xiàn)有正常生產(chǎn)能力無(wú)法完成訂單，公司考慮結(jié)合加班生產(chǎn)和 外購(gòu)組件兩種策略。目前公司總共有 100 小時(shí)正常工時(shí)和最多 60 小時(shí)加班工時(shí)（每個(gè)加班工時(shí)增加 12 元的運(yùn)營(yíng)成本）。問(wèn)：公司應(yīng)如何安排生產(chǎn)和外購(gòu)組件的數(shù)量，能夠以最低的成本 完成訂單生產(chǎn)？組件生產(chǎn)

19、工時(shí)生產(chǎn)成本外購(gòu)成本C11.511.2C2P1488.5P2367C3P121.52P231.82.1建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例解：公司可以在充分利用現(xiàn)有工時(shí)的前提下，結(jié)合加班生產(chǎn)和外購(gòu)組 件兩種策略以保證按時(shí)交貨。根據(jù)下表來(lái)設(shè)置決策變量：另外，定義x0為實(shí)際使用的加班工時(shí)。組件生產(chǎn)外購(gòu)生產(chǎn)工時(shí)生產(chǎn)成本生產(chǎn)數(shù)量外購(gòu)成本外購(gòu)數(shù)量C11.51x11.2y1C2P148x218.5y21P236x227y22C3P121.5x312y31P231.8x322.1y32建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例本問(wèn)題的線(xiàn)性模型為：minZ = x1 + 1.2y1 + 8x21 + 8.5y21 + 6x22

20、 + 7y22+ 1.5x31 + 2y31 + 1.8x32 + 2.1y32 + 12x0x1 + y1 = 2600 x21 + y21 = 1600 x22 + y22 = 1000 x31 + y31 = 1600 x32 + y32 = 1000 x0 6 60s.t.1.5x1 + 4x21 + 3x22 + 2x31 + 3x32 60x0 6 6000x1, y1, x21, y21, x22, y22, x31, y31, x32, y32, x0 > 0建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例例1-5與分銷(xiāo)問(wèn)題DG 有 3 個(gè)工廠(chǎng)同時(shí)生產(chǎn)某種，在生產(chǎn)后將運(yùn)往 2 個(gè)倉(cāng)成本如圖

21、1-1所示。本月該公司計(jì)庫(kù)，其分銷(xiāo)網(wǎng)絡(luò)及各條路線(xiàn)上的劃在 3 個(gè)工廠(chǎng)各生產(chǎn) 50、70 和 20 件，在兩個(gè)倉(cāng)庫(kù)各入庫(kù) 80 和60 件。800/50180300/100/7026065350/20圖 1-1: DG 公司的分銷(xiāo)網(wǎng)絡(luò)300/150/ 10100/200/3 21建模實(shí)例 圖解法線(xiàn)性建模實(shí)例解：800/501 80100/300/702 6065350/20圖 1-2:300/150/ 10100/200/3 21建模實(shí)例 圖解法線(xiàn)性建模實(shí)例解：按下圖定義 x1 x10 為各條路線(xiàn)上的量。800/501 80x1300/x4100/702 6065x8350/20x7圖 1-2:

22、300/x9100/x5150/ 10x3200/x103 21建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例解：按下圖定義 x1 x10 為各條路線(xiàn)上的min量。10Z =c xi ii=1s.t.x3 6 10800/x1501 80x8 6 65x1 + x2 + x3 = 50 x4 + x5 x1 = 70 x6 + x7 x5 = 20 x1 + x10 x9 = 80x7 + x8 + x9 x10 = 60300/x4100/702 6065x8x2 + x4 + x6 x8 = 0350/x720xi > 0, i = 1, · · · , 10圖 1-2

23、:300/x9100/x5150/ 10x3200/x103 21建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例例 1-6 套裁下料問(wèn)題RE公司需要使用直徑 48mm 的長(zhǎng)度為 3m、4m 和 5m 的鋼管，具體為：3m 的 600 根、4m 的 300 根、5m 的 200 根?，F(xiàn)該公司決定用長(zhǎng)度為 11m 的 自行切割來(lái)滿(mǎn)足需求 (假設(shè)切割中不發(fā)生長(zhǎng)度損耗)。問(wèn)：應(yīng)如何切割，既可滿(mǎn)足需求，又使邊角料最少？建模實(shí)例 圖解法線(xiàn)性規(guī)劃建模實(shí)例解：解決這一類(lèi)問(wèn)題的常用思路是，先窮舉出所有可能的下料方法：建模實(shí)例 圖解法線(xiàn)性規(guī)劃建模實(shí)例解：解決這一類(lèi)問(wèn)題的常用思路是，先窮舉出所有可能的下料方法： 將 11 米的鋼管

24、切割出長(zhǎng)度為 3m、4m 和 5m 的方法共有 6 種。建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例解：解決這一類(lèi)問(wèn)題的常用思路是，先窮舉出所有可能的下料方法： 將 11 米的切割出長(zhǎng)度為 3m、4m 和 5m 的方法共有 6 種。圖 1-3: 切割出指定長(zhǎng)度的所有方法 線(xiàn)性建模實(shí)例解：解決這一類(lèi)問(wèn)題的常用思路是，先窮舉出所有可能的下料方法： 將 11 米的切割出長(zhǎng)度為 3m、4m 和 5m 的方法共有 6 種。圖 1-3: 切割出指定長(zhǎng)度的所有方法然后以不同方法使用的次數(shù)為決策變量進(jìn)行建模：設(shè) xi 表示用第i 種方法切割的的數(shù)量 (i = 1, 2 · · · , 6)。建

25、模實(shí)例 圖解法建模實(shí)例 圖解法線(xiàn)性規(guī)劃建模實(shí)例線(xiàn)性規(guī)劃模型為：6min Z =xii=1s.t.2x1 + x2 + x3> 2002x3 + x4 + 2x5 + 3x6 > 600x2+ 2x4 + x5 xi > 0, i = 1, · · · , 6> 300建模實(shí)例 圖解法 線(xiàn)性建模實(shí)例線(xiàn)性模型為：6mins.t.Z =xii=12x1 + x2 + x3> 2002x3 + x4 + 2x5 + 3x6 > 600+ 2x4 + x5x2> 300xi > 0, i = 1, · ·

26、· , 6問(wèn)題為什么目標(biāo)函數(shù)不能寫(xiě)為：min Z = x1 + 2x2 + x5 + 2x6建模實(shí)例 圖解法1.2 兩變量線(xiàn)性問(wèn)題的圖解法建模實(shí)例 圖解法 兩變量線(xiàn)性問(wèn)題的圖解法 線(xiàn)性“解” 的情形首先需了解線(xiàn)性“解” 的若干可能情形：建模實(shí)例 圖解法 兩變量線(xiàn)性問(wèn)題的圖解法 線(xiàn)性“解” 的情形首先需了解線(xiàn)性“解” 的若干可能情形：可行解 滿(mǎn)足線(xiàn)性問(wèn)題所有約束條件（包括非負(fù)約束在內(nèi)）的解，反之為非可行解。建模實(shí)例 圖解法 兩變量線(xiàn)性問(wèn)題的圖解法 線(xiàn)性“解” 的情形首先需了解線(xiàn)性“解” 的若干可能情形：可行解 滿(mǎn)足線(xiàn)性問(wèn)題所有約束條件（包括非負(fù)約束在內(nèi)）的解，反之為非可行解?？尚杏?所

27、有可行解組成的集合。建模實(shí)例 圖解法 兩變量線(xiàn)性問(wèn)題的圖解法 線(xiàn)性“解” 的情形首先需了解線(xiàn)性“解” 的若干可能情形：可行解 滿(mǎn)足線(xiàn)性問(wèn)題所有約束條件（包括非負(fù)約束在內(nèi)）的解，反之為非可行解。可行域 所有可行解組成的集合。最優(yōu)解 使得線(xiàn)性問(wèn)題取得最優(yōu)值的可行解。建模實(shí)例 圖解法 兩變量線(xiàn)性問(wèn)題的圖解法 線(xiàn)性“解” 的情形首先需了解線(xiàn)性“解” 的若干可能情形：可行解 滿(mǎn)足線(xiàn)性問(wèn)題所有約束條件（包括非負(fù)約束在內(nèi)）的解，反之為非可行解?？尚杏?所有可行解組成的集合。最優(yōu)解 使得線(xiàn)性問(wèn)題取得最優(yōu)值的可行解。多最優(yōu)解 最優(yōu)解不唯一。建模實(shí)例 圖解法 兩變量線(xiàn)性問(wèn)題的圖解法 線(xiàn)性“解” 的情形首先需了解線(xiàn)

28、性“解” 的若干可能情形：可行解 滿(mǎn)足線(xiàn)性問(wèn)題所有約束條件（包括非負(fù)約束在內(nèi)）的解，反之為非可行解?？尚杏?所有可行解組成的集合。最優(yōu)解 使得線(xiàn)性問(wèn)題取得最優(yōu)值的可行解。多最優(yōu)解 最優(yōu)解不唯一。無(wú)可行解 問(wèn)題不存在可行解，亦稱(chēng)為無(wú)解。 兩變量線(xiàn)性問(wèn)題的圖解法 線(xiàn)性“解” 的情形首先需了解線(xiàn)性“解” 的若干可能情形：可行解 滿(mǎn)足線(xiàn)性問(wèn)題所有約束條件（包括非負(fù)約束在內(nèi)）的解，反之為非可行解?？尚杏?所有可行解組成的集合。最優(yōu)解 使得線(xiàn)性問(wèn)題取得最優(yōu)值的可行解。多最優(yōu)解 最優(yōu)解不唯一。無(wú)可行解 問(wèn)題不存在可行解，亦稱(chēng)為無(wú)解。有解 問(wèn)題有可行解，但目標(biāo)函數(shù)值可以取無(wú)窮大或者負(fù)無(wú)窮大，亦稱(chēng)為無(wú)最優(yōu)解。建

29、模實(shí)例 圖解法建模實(shí)例 圖解法 兩變量線(xiàn)性問(wèn)題的圖解法只包含兩個(gè)變量的線(xiàn)性問(wèn)題可以通過(guò)圖解法來(lái)求解。步驟為：步驟建模實(shí)例 圖解法 兩變量線(xiàn)性問(wèn)題的圖解法只包含兩個(gè)變量的線(xiàn)性問(wèn)題可以通過(guò)圖解法來(lái)求解。步驟為：第 1 步 找出可行域 以 x1 和 x2 為橫軸和縱軸，根據(jù)約束條件在直角坐標(biāo)系的第一象限確定問(wèn)題的可行域；步驟建模實(shí)例 圖解法 兩變量線(xiàn)性問(wèn)題的圖解法只包含兩個(gè)變量的線(xiàn)性問(wèn)題可以通過(guò)圖解法來(lái)求解。步驟為：第 1 步 找出可行域 以 x1 和 x2 為橫軸和縱軸，根據(jù)約束條件在直角坐標(biāo)系的第一象限確定問(wèn)題的可行域；第 2 步 確定目標(biāo)函數(shù)優(yōu)化方向 通過(guò)畫(huà)出若干 Z 取值不同的目標(biāo)函數(shù)線(xiàn)，確

30、定 Z 優(yōu)化時(shí)目標(biāo)函數(shù)線(xiàn)的移動(dòng)方向；步驟 兩變量線(xiàn)性問(wèn)題的圖解法只包含兩個(gè)變量的線(xiàn)性問(wèn)題可以通過(guò)圖解法來(lái)求解。步驟為：第 1 步 找出可行域 以 x1 和 x2 為橫軸和縱軸，根據(jù)約束條件在直角坐標(biāo)系的第一象限確定問(wèn)題的可行域；第 2 步 確定目標(biāo)函數(shù)優(yōu)化方向 通過(guò)畫(huà)出若干 Z 取值不同的目標(biāo)函數(shù)線(xiàn)，確定 Z 優(yōu)化時(shí)目標(biāo)函數(shù)線(xiàn)的移動(dòng)方向；第 3 步 找到最優(yōu)解 使目標(biāo)函數(shù)線(xiàn)沿著使 Z 優(yōu)化的方向移動(dòng)，直到目標(biāo)函數(shù)線(xiàn)與可行域僅有一點(diǎn)（或一 條邊）相交時(shí)，該點(diǎn)（邊）就是問(wèn)題的最優(yōu)解。步驟建模實(shí)例 圖解法建模實(shí)例 圖解法 兩變量線(xiàn)性問(wèn)題的圖解法例1-8應(yīng)用圖解法求解線(xiàn)性問(wèn)題max Z = 3x1 +

31、 5x2s.t.x16 4x2 6 63x1 + 2x2 6 18x1, x2 > 0建模實(shí)例 圖解法兩變量線(xiàn)性規(guī)劃問(wèn)題的圖解法x28max s.t.Z = 3x1 + 5x2x16 46x2 6 643x1 + 2x2 6 18x1, x2 > 02x1A2 4 6用圖解法來(lái)求解兩變量線(xiàn)性規(guī)劃問(wèn)題時(shí)，首先要在坐標(biāo)平面上畫(huà) 出可行域。在本例中，可行域是由三個(gè)約束條件在第一象限所圍成的 多邊形組成。建模實(shí)例 圖解法兩變量線(xiàn)性規(guī)劃問(wèn)題的圖解法x2x1=48Emax s.t.Z = 3x1 + 5x2Hx16 4x2=6x2 6 643x1 + 2x2 6 18x1, x2 > 0

32、2Bx1A2 46x1 6 4 要求可行解都在直線(xiàn) x1 = 4 的左側(cè)；x2 6 6 ，要求可行解都在直線(xiàn) x2 = 6 的下方；建模實(shí)例 圖解法 兩變量線(xiàn)性問(wèn)題的圖解法x2x1=4Fmax s.t.Z = 3x1 + 5x2EDHx16 4x2=6x2 6 643x1 + 2x2 6 18x1, x2 > 0C23x1+2x2=18BG46x1A23x1 + 2x2 6 18 要求所有的可行解在直線(xiàn) 3x1 + 2x2 = 18 的左下方。建模實(shí)例 圖解法兩變量線(xiàn)性規(guī)劃問(wèn)題的圖解法x2max s.t.Z = 3x1 + 5x2EDx16 4x2 6 643x1 + 2x2 6 18x

33、1, x2 > 0C2B4 6x1A2于是，可行域在圖中由陰影部分的多邊形 ABCDE 構(gòu)成。建模實(shí)例 圖解法兩變量線(xiàn)性規(guī)劃問(wèn)題的圖解法x2max s.t.Z = 3x1 + 5x2EDx16 4x2 6 643x1 + 2x2 6 18x1, x2 > 0C3x1+2x2=302Bx1A24 63x1+2x2=15觀(guān)察目標(biāo)函數(shù) Z，若固定 Z 值，則目標(biāo)方程 Z = 3x1 + 5x2 代表一條直線(xiàn)。當(dāng) Z 取不同值的時(shí)候，就形成了一系列斜率相同的直線(xiàn)簇。建模實(shí)例 圖解法兩變量線(xiàn)性規(guī)劃問(wèn)題的圖解法x2max s.t.Z = 3x1 + 5x2EDx16 4x2 6 643x1 +

34、 2x2 6 18x1, x2 > 0C3x1+2x2=302Bx1A24 63x1+2x2=15觀(guān)察目標(biāo)函數(shù) Z，若固定 Z 值，則目標(biāo)方程 Z = 3x1 + 5x2 代表一條直線(xiàn)。當(dāng) Z 取不同值的時(shí)候，就形成了一系列斜率相同的直線(xiàn)簇。例如，當(dāng) Z = 0 時(shí)，Z = 3x1 + 5x2 代表一條通過(guò)原點(diǎn) A 的直線(xiàn)。通常可畫(huà)出兩條 Z 值不同的直線(xiàn)，以確定 Z 值增大的方向。建模實(shí)例 圖解法兩變量線(xiàn)性規(guī)劃問(wèn)題的圖解法x2max s.t.Z = 3x1 + 5x2EDx16 4x2 6 643x1 + 2x2 6 18x1, x2 > 0C3x1+2x2=302Bx1A24

35、63x1+2x2=15通過(guò)變換 Z 值可知，要使 Z 取得最大值，必須使直線(xiàn) Z = 3x1+5x2向遠(yuǎn)離原點(diǎn)的方向（右、上）平移。建模實(shí)例 圖解法兩變量線(xiàn)性規(guī)劃問(wèn)題的圖解法x2max s.t.Z = 3x1 + 5x2EDx16 4x2 6 643x1+2x2=363x1+2x2=303x1 + 2x2 6 18x1, x2 > 0C2Bx1A24 63x1+2x2=15當(dāng)直線(xiàn)移動(dòng)到點(diǎn)D(2,6)時(shí)，直線(xiàn) Z = 3x1 + 5x2 即將離開(kāi)可行域的臨界狀態(tài)，再向外移動(dòng)就會(huì)導(dǎo)致目標(biāo)函數(shù)與可行域沒(méi)有重合的部分。建模實(shí)例 圖解法兩變量線(xiàn)性規(guī)劃問(wèn)題的圖解法x2max s.t.Z = 3x1

36、+ 5x2EDx16 4x2 6 643x1+2x2=363x1+2x2=303x1 + 2x2 6 18x1, x2 > 0C2Bx1A24 63x1+2x2=15當(dāng)直線(xiàn)移動(dòng)到點(diǎn)D(2,6)時(shí)，直線(xiàn) Z = 3x1 + 5x2 即將離開(kāi)可行域的臨界狀態(tài)，再向外移動(dòng)就會(huì)導(dǎo)致目標(biāo)函數(shù)與可行域沒(méi)有重合的部分。此時(shí)，x1 = 2，x2 = 6，Z 取得最大值 36。解畢。建模實(shí)例 圖解法 兩變量線(xiàn)性問(wèn)題的圖解法例1-9應(yīng)用圖解法求解線(xiàn)性問(wèn)題max Z = x1 + x2s.t.x1 x2 > 1x1 + 2x2 6 0x1, x2 > 0建模實(shí)例 圖解法 兩變量線(xiàn)性問(wèn)題的圖解法解：x242x24目標(biāo)函數(shù)等值線(xiàn)可以無(wú)限向右、上方移動(dòng)而且離開(kāi)可行域，因此目標(biāo)函數(shù)可以取無(wú)窮大，所以，本線(xiàn)性問(wèn)題無(wú)最優(yōu)解，或者有 “解”。建模實(shí)例 圖解法兩變量線(xiàn)性規(guī)劃問(wèn)題的圖解法理論意義從理論上，圖解法的意義在于引出以下兩個(gè)重要的定理：建模實(shí)例 圖解法兩變量線(xiàn)性規(guī)劃問(wèn)題的圖解法理論意義從理論上，圖解法的意義在于引出以下兩個(gè)重要的定理：定理 1.1線(xiàn)性規(guī)劃問(wèn)題的可行域如果存在，則問(wèn)題的可行域一定是一個(gè)凸集。建模實(shí)例 圖解法 兩變量線(xiàn)性問(wèn)題的圖解法從理論上