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