【文章內(nèi)容簡(jiǎn)介】 z 35 3 3 8 0 0 01 x53 1/5 ( 7/5) 0 0 1 3/5 15/70 x34 2/5 1/5 1 0 0 1/5 200 x410 3/5 6/5 0 1 0 4/5 25/3z 3 1/5 7/5 0 0 0 8/50 x215/7 1/7 1 0 0 5/7 3/70 x325/7 3/7 0 1 0 1/7 2/7 25/30 x452/7 3/7 0 0 1 6/7 2/7z 0 0 0 0 0 1 1?第一階段 （ LP 1） ? 得到原問(wèn)題的基本可行解： (0， 15/7， 25/7， 52/7)T 27 線 性 規(guī) 劃 （續(xù) ）兩階段法例 5 2 3 1CBXB x 1 x 2 x 3 x 4 θ i2 x215/7 1/7 1 0 03 x325/7 ( 3/7) 0 1 0 25/31 x452/7 3/7 0 0 1z 53/7 25/7 0 0 02 x210/3 0 1 1/3 05 x125/3 1 0 7/3 01 x411 0 0 1 1z 1 12/3 0 0 25/3 0?第二階段 把基本可行解填入表中 ? 得到原問(wèn)題的最優(yōu)解： (25/3， 10/3， 0， 11)T ?最優(yōu)目標(biāo)值： 112/3 28 線 性 規(guī) 劃 （續(xù) ） 矩陣描述 —— 此段為選讀，有困難者可不看。 段單純形迭代過(guò)程中的幾點(diǎn)注意事項(xiàng)是對(duì)有關(guān)內(nèi)容的強(qiáng)調(diào)和補(bǔ)充，要認(rèn)真學(xué)習(xí)、理解。 **習(xí)題： p7071 習(xí)題 1 15， 16 29 1. 4 線性規(guī)劃應(yīng)用 —— 建模（ p5568） 本節(jié)介紹了些線性規(guī)劃應(yīng)用的例子，這些例子從多個(gè)方面介紹建模對(duì)未來(lái)是很有用的，應(yīng)認(rèn)真對(duì)待。 除了教材上的例子之外，還有許多其它應(yīng)用： * 合理利用線材問(wèn)題：如何下料使用材最少 * 配料問(wèn)題：在原料供應(yīng)量的限制下如何獲取最大利潤(rùn) * 投資問(wèn)題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大 * 產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，使獲利最大 * 勞動(dòng)力安排：用最少的勞動(dòng)力來(lái)滿足工作的需要 * 運(yùn)輸問(wèn)題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小 **下面是一些建模的例子，有興趣者，可作為練習(xí)。這些例子有一定的難度，做起來(lái)會(huì)有一些困難。 **習(xí)題： p7273 習(xí)題 1 17， 18， 19， 110 線 性 規(guī) 劃 （續(xù) ） 返回目錄 30 例．某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下： 設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開(kāi)始時(shí)上班，并連續(xù)工作八小時(shí)，問(wèn)該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員 ? 班次 時(shí)間 所需人數(shù)1 6 ： 00 —— 10 ： 00 602 10 ： 00 —— 14 ： 00 703 14 ： 00 —— 18 ： 00 604 18 ： 00 —— 22 ： 00 505 22 ： —— 2 ： 00 206 2 ： 00 —— 6 ： 00 30例：人力資源分配的問(wèn)題 31 解：設(shè) xi 表示第 i班次時(shí)開(kāi)始上班的司機(jī)和乘務(wù)人員數(shù) ,這樣我們建立如下的數(shù)學(xué)模型。 目標(biāo)函數(shù)： Min x1 + x2 + x3 + x4 + x5 + x6 約束條件： . x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0 例：人力資源分配的問(wèn)題（續(xù)） 32 例、 明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過(guò)鑄造、機(jī)加工和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如下表。問(wèn)：公司為了獲得最大利潤(rùn)，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？ 甲 乙 丙 資源限制鑄造工時(shí) ( 小時(shí) / 件 ) 5 10 7 8000機(jī)加工工時(shí) ( 小時(shí) / 件 ) 6 4 8 12022裝配工時(shí) ( 小時(shí) / 件 ) 3 2 2 10000自產(chǎn)鑄件成本 ( 元 / 件 ) 3 5 4外協(xié)鑄件成本 ( 元 / 件 ) 5 6 機(jī)加工成本 ( 元 / 件 ) 2 1 3裝配成本 ( 元 / 件 ) 3 2 2產(chǎn)品售價(jià) ( 元 / 件 ) 23 18 16例：生產(chǎn)計(jì)劃的問(wèn)題 33 解：設(shè) x1,x2,x3 分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)， x4,x5 分別為由外協(xié)鑄造再由本公司機(jī)加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。 求 xi 的利潤(rùn)：利潤(rùn) = 售價(jià) 各成本之和 可得到 xi（ i=1,2,3,4,5）的利潤(rùn)分別為 1 1 9元。 這樣我們建立如下的數(shù)學(xué)模型。 目標(biāo)函數(shù)： Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5 約束條件： . 5x1 + 10x2 + 7x3 ≤ 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 ≤ 12022 3x1 + 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000 x1,x2,x3,x4,x5 ≥ 0 例：生產(chǎn)計(jì)劃的問(wèn)題（續(xù)） 34 例、 永久機(jī)械廠生產(chǎn) Ⅰ 、 Ⅱ 、 Ⅲ 三種產(chǎn)品，均要經(jīng)過(guò) A、 B 兩道工序加工。假設(shè)有兩種規(guī)格的設(shè)備 A A2能完成 A 工序；有三種規(guī)格的設(shè)備 B B B3能完成 B 工序。 Ⅰ 可在 A、 B的任何規(guī)格的設(shè)備上加工； Ⅱ 可在任意規(guī)格的 A設(shè)備上加工，但對(duì) B工序，只能在 B1設(shè)備上加工； Ⅲ 只能在 A2與 B2設(shè)備上加工；數(shù)據(jù)如下表。問(wèn)：為使該廠獲得最大利潤(rùn)，應(yīng)如何制定產(chǎn)品加工方案？ 產(chǎn)品單件工時(shí) 設(shè)備 Ⅰ Ⅱ Ⅲ設(shè)備的有效臺(tái)時(shí)滿負(fù)荷時(shí)的設(shè)備費(fèi)用A15 10 6000 300A27 9 12 10000 321B16 8 4000 50B24 11 7000 783B37 4000 200原料 （元 / 件） 0. 25 0. 35 0. 50售價(jià) （元 / 件） 1. 25 2. 00 2. 80例：生產(chǎn)計(jì)劃的問(wèn)題（續(xù)） 35 解：設(shè) xijk 表示第 i 種產(chǎn)品，在第 j 種工序上的第 k 種設(shè)備上加工的數(shù)量。 利潤(rùn) = [（銷售單價(jià) 原料單價(jià)） * 產(chǎn)品件數(shù) ]之和 （每臺(tái)時(shí)的設(shè)備費(fèi)用 *設(shè)備實(shí)際使用的總臺(tái)時(shí)數(shù)）之和。 這樣我們建立如下的數(shù)學(xué)模型 : Max ++++ . 5x111 + 10x211 ≤ 6000 （ 設(shè)備 A1 ） 7x112 + 9x212 + 12x312 ≤ 10000 （ 設(shè)備 A2 ） 6x121 + 8x221 ≤ 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ù)） 36 例、某工廠要做 100套鋼架，每套用長(zhǎng)為 m, m, m的圓鋼各一根。已知原料每根長(zhǎng) m，問(wèn)：應(yīng)如何下料，可使所用原料最?。? 解： 設(shè)計(jì)下列 5 種下料方案 方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 方案 7 方案 82. 9 m 1 2 0 1 0 1 0 02. 1 m 0 0 2 2 1 1 3 01. 5 m 3 1 2 0 3 1 0 4合計(jì) 7. 4 7. 3 7. 2 7. 1 6. 6 6. 5 6. 3 6. 0剩余料頭 0 0. 1 0. 2 0. 3 0. 8 0. 9 1. 1 1 . 4假設(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)題 37 例 6．某工廠要用三種原料 3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下表。問(wèn)：該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大？ 產(chǎn)品名稱 規(guī)格要求 單價(jià) （元 /kg ）甲 原材料 1 不少于 50 % ，原材料 2 不超過(guò) 25% 50乙 原材料 1 不少于 25 % ，原材料 2 不超過(guò) 50% 35丙 不限 25原材料名稱 每天最多供應(yīng)量 單價(jià) （元 /kg ）1 100 652 100 253 60 35例：配料問(wèn)題 38 例：配料問(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è)。 39 Max 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ù)） 40 例 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ù)如右表： 問(wèn)： a）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利金額為最大？ b）應(yīng)如何確定這些項(xiàng)目的每年投資額，