【文章內(nèi)容簡(jiǎn)介】 ≤ 4000 （ 設(shè)備 B1 ） 4x122 + 11x322 ≤ 7000 （ 設(shè)備 B2 ） 7x123 ≤ 4000 （ 設(shè)備 B3 ） x111+ x112 x121 x122 x123 = 0 （ Ⅰ 產(chǎn)品在 A、 B工序加工的數(shù)量相等） x211+ x212 x221 = 0 （ Ⅱ 產(chǎn)品在 A、 B工序加工的數(shù)量相等） x312 x322 = 0 （ Ⅲ 產(chǎn)品在 A、 B工序加工的數(shù)量相等） xijk ≥ 0 , i = 1,2,3。 j = 1,2。 k = 1,2,3例：生產(chǎn)計(jì)劃的問(wèn)題（續(xù)）35例、某工廠要做 100套鋼架，每套用長(zhǎng)為 m, m, m的圓鋼各一根。已知原料每根長(zhǎng) m，問(wèn)：應(yīng)如何下料，可使所用原料最省？解： 設(shè)計(jì)下列 5 種下料方案假設(shè) x1,x2,x3,x4,x5 分別為上面前 5 種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)： Min x1 + x2 + x3 + x4 + x5 約束條件： . x1 + 2x2 + x4 ≥ 100 2x3 + 2x4 + x5 ≥ 100 3x1 + x2 + 2x3 + 3x5 ≥ 100 x1,x2,x3,x4,x5 ≥ 0例：套裁下料問(wèn)題36例 6．某工廠要用三種原料 3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下表。問(wèn)：該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大？例：配料問(wèn)題37例：配料問(wèn)題（續(xù)）解： 設(shè) xij 表示第 i 種（甲、乙、丙）產(chǎn)品中原料 j 的含量。這樣我們建立數(shù)學(xué)模型時(shí)，要考慮： 對(duì)于甲： x11， x12， x13； 對(duì)于乙： x21， x22， x23； 對(duì)于丙： x31， x32， x33； 對(duì)于原料 1： x11， x21， x31； 對(duì)于原料 2： x12， x22， x32； 對(duì)于原料 3： x13， x23， x33； 目標(biāo)函數(shù)： 利潤(rùn)最大，利潤(rùn) = 收入 原料支出 約束條件： 規(guī)格要求 4 個(gè)； 供應(yīng)量限制 3 個(gè)。38Max z = 15x11+25x12+15x1330x21+10x2240x3110x33 . x12 x13 ≥ 0 （原材料 1不少于 50%） + ≤ 0 （原材料 2不超過(guò) 25%） ≥ 0 （原材料 1不少于 25%） x21+ x22 x23 ≤ 0 （原材料 2不超過(guò) 50%） x11+ x21 + x31 ≤ 100 ( 供應(yīng)量限制） x12+ x22 + x32 ≤ 100 ( 供應(yīng)量限制） x13+ x23 + x33 ≤ 60 ( 供應(yīng)量限制） xij ≥ 0 , i = 1,2,3。 j = 1,2,3例：配料問(wèn)題（續(xù)）39 例 8．某部門現(xiàn)有資金 200萬(wàn)元，今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目 A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利 110%；項(xiàng)目 B：從第一年到第四年每年年初都可投資，次年末能收回本利 125%，但規(guī)定每年最大投資額不能超過(guò) 30萬(wàn)元；項(xiàng)目 C：需在第三年年初投資，第五年末能收回本利 140%，但規(guī)定最大投資額不能超過(guò) 80萬(wàn)元；項(xiàng)目 D：需在第二年年初投資，第五年末能收回本利 155%，但規(guī)定最大投資額不能超過(guò) 100萬(wàn)元； 據(jù)測(cè)定每萬(wàn)元每次投資的風(fēng)險(xiǎn)指數(shù)如右表：?jiǎn)枺篴）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利在 330萬(wàn)元的基礎(chǔ)上使得其投資總的風(fēng)險(xiǎn)系數(shù)為最??？ 解： 1） 確定決策變量：連續(xù)投資問(wèn)題 設(shè) xij ( i = 1 5， j = 4)表示第 i 年初投資于 A(j=1)、 B(j=2)、 C(j=3)、D(j=4)項(xiàng)目的金額。這樣我們建立如下的決策變量： A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24例：投資問(wèn)題402）約束條件：第一年： A當(dāng)年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是 x11+ x12 = 200；第二年： B次當(dāng)年末才可收回投資故第二年年初的資金為 x11，于是 x21 + x22+ x24 = ；第三年：年初的資金為 x21+x12，于是 x31 + x32+ x33 = + ；第四年：年初的資金為 x31+x22，于是 x41 + x42 = + ；第五年：年初的資金為 x41+x32，于是 x51 = + ； B、 C、 D的投資限制： xi2 ≤ 30 ( I =1 、 4 )， x33 ≤ 80 ， x24 ≤ 100 3）目標(biāo)函數(shù)及模型：a) Max z = + + + . x11+ x12 = 200 x21 + x22+ x24 = ； x31 + x32+ x33 = + ； x41 + x42 = + ； x51 = + ； xi2 ≤ 30 ( I =1 、 4 )， x33 ≤ 80 ， x24 ≤ 100 xij ≥ 0 ( i = 1 、 5； j = 4） b) Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+ . x11+ x12 = 200 x21 + x22+ x24 = ； x31 + x32+ x33 = + ； x41 + x42 = + ； x51 = + ； xi2 ≤ 30 ( I =1 、 4 )， x33 ≤ 80 ， x24 ≤ 100 + + + ≥ 330 xij ≥ 0 ( i = 1 、 5； j = 4）例：投資問(wèn)題（續(xù)）41線性規(guī)劃問(wèn)題的進(jìn)一步研究（ ）2. 1 對(duì)偶原理對(duì)偶問(wèn)題： 考慮前文例 1 若設(shè)備和原料都用于外協(xié)加工，工廠收取加工費(fèi)。試問(wèn)：設(shè)備工時(shí)和原料 A、 B 各如何收費(fèi)才最有競(jìng)爭(zhēng)力？ 設(shè) y1 ， y2 ， y3 分別為每設(shè)備工時(shí)、 原料 A、 B每單位的收取費(fèi)用Max z = 50 x1 + 100 x2 Min f = 300 y1 + 400 y2 + 250 y3 . x1 + x2 ≤ 300 . y1 + 2 y2 + ≥ 50 2 x1 + x2 ≤ 400 （不少于甲產(chǎn)品的利潤(rùn)） x2 ≤ 250 y1 + y2 + y3 ≥ 100 x1 , x2 ≥ 0 y1, y2 , y3 ≥ 042對(duì)偶定義? 對(duì)稱形式： 互為對(duì)偶 (LP) Max z = cT x ? (DP) Min f = bT y . Ax ≤ b . AT y ≥ c x ≥ 0 y ≥ 0 “Max ≤ ” “Min ≥”? 一般形式： 若一個(gè)問(wèn)題的某約束為等式，那么對(duì)應(yīng)的對(duì)偶問(wèn)題的相應(yīng)變量無(wú)非負(fù)限制；反之， 若一個(gè)問(wèn)題的某變量無(wú)非負(fù)限制，那么對(duì)應(yīng)的對(duì)偶問(wèn)題的相應(yīng)約束為等式。線性規(guī)劃問(wèn)題的進(jìn)一步研究（ ）43對(duì)偶定理 （原問(wèn)題與對(duì)偶問(wèn)題解的關(guān)系）考慮（ LP）和（ DP）定理 21 （弱對(duì)偶定理）若 x, y 分別為（ LP）和（ DP）的可行解，那么 cT x ≤ bT y 。推論 若（ LP）可行，那么（ LP）無(wú)有限最優(yōu)解的充分必要條件是（ LD）無(wú)可行解。定理 22 （最優(yōu)性準(zhǔn)則定理）若 x, y 分別為（ LP）和（ DP）的可行解，且 cT x = bT y ，那么 x, y分別為（ LP）和（ DP）的最優(yōu)解。定理 23 （主對(duì)偶定理）若（ LP）和（ DP）均可行，那么（LP）和（ DP）均有最優(yōu)解，且最優(yōu)值相等。以上定理、推論對(duì)任意形式的相應(yīng)線性規(guī)劃的對(duì)偶均有效**習(xí)題： p 99 習(xí)題 2 21線性規(guī)劃問(wèn)題的進(jìn)一步研究（ ）44影子價(jià)格 —— 是一個(gè)向量，它的分量表示最優(yōu)目標(biāo)值隨相應(yīng)資源數(shù)量變化的變化率。 若 x*, y* 分別為（ LP）和（ DP）的最優(yōu)解， 那么， cT x* = bT y* 。 根據(jù) f = bT y* = b1y1* + b2y2* + ?? + bmym* 可知 ?f / ?bi = yi* yi* 表示 bi 變化 1個(gè)單位對(duì)目標(biāo) f 產(chǎn)生的影響，稱 yi* 為 bi的影子價(jià)格。注意：若 B 是最優(yōu)基， y* = (BT)1 cB 為影子價(jià)格向量。線性規(guī)劃問(wèn)題的進(jìn)一步研究（ ）45由最優(yōu)單純形表求對(duì)偶問(wèn)題最優(yōu)解 第 1章例 1。化標(biāo)準(zhǔn)形式： Max z = 50 x1 + 100 x2 . x1 + x2 + x3 = 300 ， 2 x1 + x2 + x4 = 400 x2 + x5 = 250 ， x1 , x2 , x3 , x4 , x5 ≥ 0 I O B=(p1 , p4 , p2 ) (BT)1 cB B1最優(yōu)解 x1 = 50 x2 = 250 x4 = 50（松弛標(biāo)量，表示原料 A有 50個(gè)單位的剩余） 影子價(jià)格 y1 = 50 y2 = 0 y3 = 50 , B1對(duì)應(yīng)的檢驗(yàn)數(shù) (BT)1 cB 。線性規(guī)劃問(wèn)題的進(jìn)一步研究（ ）462. 2 對(duì)偶單純形法? 對(duì)偶單純形法在什么情況下使用 ： 應(yīng)用前提：有一個(gè)基，其對(duì)應(yīng)的基本