【正文】 50 B 2 4 11 7000 783 B 3 7 4000 200 原料（元 / 件） 0 . 2 5 0 . 3 5 0 . 5 0 售價(jià)（元 / 件） 1 . 2 5 2 . 0 0 2 . 8 0 167。 Ⅰ 可在 A、 B的任何規(guī)格的設(shè)備上加工； Ⅱ 可在任意規(guī)格的 A設(shè)備上加工 ， 但對(duì) B工序 ， 只能在 B1設(shè)備上加工；Ⅲ 只能在 A2與 B2設(shè)備上加工 。 生產(chǎn)計(jì)劃問(wèn)題 例 4． 永久機(jī)械廠生產(chǎn) Ⅰ 、 Ⅱ 、 Ⅲ 三種產(chǎn)品 ， 均要經(jīng)過(guò) A、 B兩道工序加工 。 167。 生產(chǎn)計(jì)劃問(wèn)題 解： 設(shè) x1,x2,x3 分別為三道工序都由本公司加工的甲、乙、丙三種 產(chǎn)品的件數(shù)， x4,x5 分別為由外協(xié)鑄造再由本公司加工和裝配的甲、乙兩 種產(chǎn)品的件數(shù)。 數(shù)據(jù)如表 。 該公司生產(chǎn)甲 、乙 、 丙三種產(chǎn)品 ， 都需要經(jīng)過(guò)鑄造 、 機(jī)加工和裝配三個(gè)車(chē)間 。 目標(biāo)函數(shù) ： Min x1 + x2 + x3 + x4 + x5 + x6 + x7 約束條件 ： . x1 + x2 + x3 + x4 + x5 ≥ 28 x2 + x3 + x4 + x5 + x6 ≥ 15 x3 + x4 + x5 + x6 + x7 ≥ 24 x4 + x5 + x6 + x7 + x1 ≥ 25 x5 + x6 + x7 + x1 + x2 ≥ 19 x6 + x7 + x1 + x2 + x3 ≥ 31 x7 + x1 + x2 + x3 + x4 ≥ 28 x1,x2,x3,x4,x5,x6,x7 ≥ 0 167。問(wèn)應(yīng)該如何安排售貨人員的作息，既滿足工作需要，又使配備的售貨人員的人數(shù)最少？ 時(shí)間 所需售貨員人數(shù)星期日 28星期一 15星期二 24星期三 25星期四 19星期五 31星期六 28167。 人力資源分配的問(wèn)題 例 2．一家中型的百貨商場(chǎng)，它對(duì)售貨員的需求經(jīng)過(guò)統(tǒng)計(jì)分析如下表所示。 人力資源分配的問(wèn)題 例 1．某晝夜服務(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 60 2 10 ： 00 —— 14 ： 00 70 3 14 ： 00 —— 18 ： 00 60 4 18 ： 00 —— 22 ： 00 50 5 22 ： 0 0 —— 2 ： 00 20 6 2 ： 00 —— 6 ： 00 30 解 ：設(shè) xi 表示第 i班次時(shí)開(kāi)始上班的司機(jī)和乘務(wù)人員數(shù) , 這樣我們建立如下的數(shù)學(xué)模型。 配料問(wèn)題 167。 人力資源分配的問(wèn)題 167。 Cj→ 31 22 0 0 0 θi CB XB b x1 x2 x3 x4 x5 31 x1 20 1 0 5/24 0 1/12 0 x4 20 0 0 5/12 1 13/6 22 x2 30 0 1 1/8 0 1/4 z 1280 0 0 89/24 0 35/12 以 4為主元作旋轉(zhuǎn)變換得下表： 25 167。合之，知主元為 4。 Cj→ 31 22 0 0 0 θi CB XB b x1 x2 x3 x4 x5 0 x3 180 [6] 2 1 0 0 180/6 0 x4 400 4 10 0 1 0 400/4 0 x5 210 3 5 0 0 1 210/3 z 0 31 22 0 0 0 表 14 31 180/6 23 Cj→ 31 22 0 0 0 θi CB XB b x1 x2 x3 x4 x5 31 x1 30 1 1/3 1/6 0 0 90 0 x4 280 0 26/3 2/3 1 0 420/13 0 x5 120 0 [4] 1/2 0 1 30 z 930 0 35/3 31/6 0 0 作旋轉(zhuǎn)變換得新單純形表： 2 1 0100534 0 00101041 8 0001262101005340001010430006/13/112 1 0100532 8 0013/23/26030006/13/11?第 1行 =第 1行 /6 第 2行 =第 2行 4 第 1行 1 2 0102/1402 8 0013/23/26030006/13/11??第 3行 =第 3行 3 第 1行 得新基可行解 X(1) = (30, 0, 0, 280, 120)T (此可行解對(duì)應(yīng)圖形法中的 D點(diǎn) ,參見(jiàn)教材 p17)。 ? ?????????????????????5,2,102105340010418026.2231m a x52142132121?jxxxxxxxxxxtsxxzj22 建立初始單純形表 (表 14)： 因 σ j行中， σ 1 = 31為最大正檢驗(yàn)數(shù)，故選x1為入基變量；又因 θ i列中最小比值在第一行，故定 x3為出基變量。1 對(duì)線性規(guī)劃的回顧 21 例 6 用單純形表求解例 1。否則 ,若有 akj0 則選 ?=min{?j / akj┃ akj0}=?r/akr那么 xr為進(jìn)基變量 ,轉(zhuǎn) 4； 4. 以 akr為轉(zhuǎn)軸元 ,作矩陣行變換使其變?yōu)?1,該列其他元變?yōu)?0,轉(zhuǎn) 2。 對(duì)偶單純形法求解線性規(guī)劃問(wèn)題過(guò)程： 1. 建立初始對(duì)偶單純形表 ,對(duì)應(yīng)一個(gè)基本解 ,所有檢驗(yàn)數(shù)均非正 ,轉(zhuǎn) 2； 2. 若 b≥0, 則得到最優(yōu)解 ,停止 。 如果得到的基本解的分量皆非負(fù)則該基本解為最優(yōu)解 。 1 對(duì)線性規(guī)劃的回顧 原規(guī)劃（ P） 對(duì)偶規(guī)劃（ D） 可行 可行 不可行 可行（無(wú)界） 可行（無(wú)界） 不可行 不可行 不可行 對(duì)偶單純形法 167。 推論⑶ .在一對(duì)對(duì)偶問(wèn)題（ P）和（ D）中，若一個(gè)可行（如 P），而另一個(gè)不可行，（如 D），則該可行的問(wèn)題無(wú)界。 推論⑵ .在一對(duì)對(duì)偶問(wèn)題（ P）和（ D）中，若其中一個(gè)問(wèn)題可行但目標(biāo)函數(shù)無(wú)界，則另一個(gè)問(wèn)題不可行；反之不成立。 【 性質(zhì) 6】 (基解對(duì)應(yīng)性 ) 原規(guī)劃單純形表中檢驗(yàn)數(shù)行對(duì)應(yīng)對(duì)偶規(guī)劃的一個(gè)基解。 【 性質(zhì) 4】 (強(qiáng)對(duì)偶性 ) 原規(guī)劃與對(duì)偶規(guī)劃同有最優(yōu)解，且兩者最優(yōu)值相等。 1 對(duì)線性規(guī)劃的回顧 對(duì)偶問(wèn)題的性質(zhì) 【 性質(zhì) 1】 對(duì)稱(chēng)性定理 ：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。 1 對(duì)線性規(guī)劃的回顧 線性規(guī)劃的對(duì)偶理論 167。 120010kkklkmkaaPaa?? ???? ???? ???? ?????? ???? ???? ???? ??????????單純形法 (單純形法的解題 步驟 ) 單純形法小結(jié) 單純形表中解的表示形式 唯一最優(yōu)解：最終單純形表中，所有非基變量檢驗(yàn)數(shù) δ j＜ 0 無(wú)窮多最優(yōu)解：最終單純形表中，某非基變量檢驗(yàn)數(shù) δ j＝ 0 無(wú)界解：某檢驗(yàn)數(shù) δ j＞ 0對(duì)應(yīng)變量的系數(shù)列向量 Pk≤0 退化基可行解：一個(gè)或幾個(gè)基變量取值‘＝ 0’ 的基可行解 出現(xiàn)退化基可行解，可能導(dǎo)致從某個(gè)基開(kāi)始，經(jīng)過(guò)若干次迭代后又回到原來(lái)的基，即單純形法出現(xiàn)了循環(huán)，永遠(yuǎn)達(dá)不到最優(yōu)解，導(dǎo)致計(jì)算失敗。