【正文】 法（ 6） —— 結(jié)論 線性規(guī)劃問題的解有四種情況 1．有唯一最優(yōu)解 2．有無窮多最優(yōu)解 3．有可行解，但無最優(yōu)解（解無界） 4．無可行解 單純型法 標準化 單純型法 線性規(guī)劃問題的標準形式 (一 ) 1．目標函數(shù)求最大 2．約束條件取等號 3．變量為非負 11( 1 )m a x( 1 , 2 , ..., ).0 ( 1 , 2 , ..., )njjjnij j ijjf c xa x b i mstx j n????????? ?????標 準 形 的 代 數(shù) 表 示 ? ?? ?? ?121212, , ..., , ..., , ...,Tij m nTnTnTnmax f = c xA x = b .x0Aac c c cb b b bx x x x?????????（ 2 ） 標 準 形 的 矩 陣 表 示其 中 （ ）線性規(guī)劃問題的標準形式（二） 12121212m i n 23 2 674..20 1 2j1. 5 f x xxxxxstxxxj?????????????? ???例 將 下 列 線 性 規(guī) 劃 問 題 化 為 標 準 形， ，單純型法（一） 某工廠計劃在一個生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品分別需要經(jīng)過 A、 B兩道工序加工。 對偶單純形法（ 2） ?????????????????????????????5102263433252142132121, .. . ,i,xxxxxxxxxx.xxffm a xi39。 （二）第 i 種資源的影子價格又代表對一個單位第 i 種資源的估價，這種估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻而作的估價。當某種資源的市場價格低于影子價格時，企業(yè)應(yīng)當買進該種資源用于擴大生產(chǎn)；當某種資源的市場價格高于影子價格時，企業(yè)的決策者應(yīng)當把已有的該種資源賣掉。 數(shù)學模型為?????????????????2,102406180221002..m a x21212121jxxxxxxxtsxxfj 其解的最優(yōu)基對應(yīng)的單純形表為（見表 1 .56 ） B x 1 x 2 x 3 x 4 x 5 b 1 1 0 3/ 2 0 1/ 2 30 4 0 0 2/ 5 1 1/ 2 50 2 0 1 1/ 4 0 1/ 4 35 C 0 0 3/ 4 0 1/ 4 135 靈敏度分析（ 1） 一、 約束條件右邊常數(shù) b 的靈敏度分析 二、 目標函數(shù)變量系數(shù) c 的靈敏度分析 ( 1) 非基變量系數(shù)的靈敏度分析 ( 2) 基變量系數(shù)的靈敏度分析 靈敏度分析（ 2） 單位產(chǎn)品 產(chǎn)品 消耗工時 工序 A B C 有效工時 （小時） 零件加工（小時 / 件） 1. 0 1. 2 1. 4 4800 電 鍍（小時 / 件） 0. 5 0. 6 0. 6 1800 裝 配（小時 / 件） 0. 7 0. 7 0. 8 2400 利 潤（元 / 件） 12 15 8 解：設(shè) x1, x2, x3 設(shè)分別表示產(chǎn)品 A , B , C 一周的計劃生產(chǎn)件數(shù)。如設(shè)備 B必要時可以加班，當然不希望加班； 設(shè)備 A既要充分利用，又盡可能不加班； 企業(yè)決策者認識到不考慮附加條件，才使利潤指標達到 14。 第三步：檢驗調(diào)運方案是否是最優(yōu)方案； 如果已經(jīng)是最優(yōu)，則算法結(jié)束，問題已經(jīng)解決； 如果還不是最優(yōu)，則進入第四步； 第四步：調(diào)整非最優(yōu)的調(diào)運方案，獲得更好的調(diào)運方案，也就是進行換基迭代； ? 改進調(diào)運方案，一般采用 閉回路調(diào)整法 。 第三節(jié) 0—1規(guī)劃 某公司準備投資 100 萬元在甲、乙兩座城市修建健身中心，經(jīng)過多方考察，最后選定 A 1 , A 2 , A 3 , A 4 和 A 5 五個位置，并且決定在甲城市的 A 1 、 A 2 、 A 3 三個位置中最多投建兩個；在乙城市的 A 4 、 A 5 兩個位置中最少投建一個。甲、乙、丙、丁四名隊員各自游什么姿勢，才最有可能取得好成績？ 成績 自由泳 蛙 泳 蝶 泳 仰 泳 甲 56 ? 74 ? 61 ? 63 ? 乙 63 ? 69 ? 65 ? 71 ? 丙 57 ? 77 ? 63 ? 67 ? 丁 55 ? 76 ? 62 ? 62 ? 解：設(shè)????種姿勢個人不游第第種姿勢個人游第第jijixij01 ?????????????????????????????????????????????????????????????????4321101111111162627655676377577165696363617456443424144333231342322212413121114443424134333231242322211413121144434241343332312423222114131211，或 jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.xxxxxxxxxxxxxxxxfmi nij 匹 配 某游泳隊擬選用甲、乙、丙、丁四名游泳運動員組成一個 4 ? 100 米混合接力隊，參加今年的錦標賽?，F(xiàn)有甲 , 乙 , 丙 , 丁四人，他們將中文說明書翻譯成不同語種的說明書所需的時間有表 3. 7 給出，問應(yīng)分配何人去完成何工作，使所需時間最少？ 表 3 . 7 任務(wù) 人員 E J G R 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9 ??????????????9118713161491514410413152分配問題的匈牙利解法 79429118713161491514410413152??????????????????2424104750111006211130??????????????????????????????001023509606017130? ? ??????????????0010235096*06017130????????????????001235*096*0601713?????????????????*01235*096*001713???????????????*23096*017 分配問題的匈牙利解法 ??????????????541100032450115280分配問題的匈牙利解法 第一步：給系數(shù)矩陣“制造” 0元素： ； 2. 從系數(shù)矩陣的每列元素減去該列的最小元素。 分配問題的匈牙利解法 最大值問題 匈牙利法實質(zhì)上一種求最小值的方法，如果給我們的是系數(shù)矩陣， a ij表示 的是第 i 個人員完成第 j 項任務(wù)的收益，則要求我們?nèi)绾畏峙淠橙送瓿赡稠椚蝿?wù)，使總收益最大。 分配問題的匈牙利解法 某工廠訂購了三臺機器（ A,B,C），有四各位置可供機器安裝（位置一，二，三，四），但 B機器不能安裝在第二號位置。 分配問題的匈牙利解法 系數(shù)矩陣不是方陣 在實際問題中，往往遇到有些任務(wù)沒有人去做，或某些人沒有分配到任務(wù)的情況。 第三步 增加系數(shù)矩陣中的 0元素： 1. 找最少直線覆蓋效率矩陣中的所有 0元素 （ 1）對沒有 0*行的行打 ?， （ 2）對打 ?的行上所有有 0元素的列打 ?， （ 3）對打 ?列的上所有有 0*元素的行打 ?， （ 4）重復（ 2）（ 3）步，到過程結(jié)束 （ 5）對沒有打 ?的行畫橫線，所有打 ?的列畫垂線，找到了覆蓋所有 0元素的最少直線。甲、乙、丙、丁四名隊員各自游什么姿勢，才最有可能取得好成績？ 成績 自由泳 蛙 泳 蝶 泳 仰 泳 甲 56 ? 74 ? 61 ? 63 ? 乙 63 ? 69 ? 65 ? 71 ? 丙 57 ? 77 ? 63 ? 67 ? 丁 55 ? 76 ? 62 ? 62 ? 甲 —— 蝶泳 乙 —— 蛙泳 丙 —— 自由泳 丁 —— 仰泳 甲 —— 蛙泳 乙 —— 自由泳 丙 —— 蝶泳 丁 —— 仰泳 分配問題的匈牙利解法 例 3 . 10 有一份中文說明書，需譯成英，日，德，俄四種文字。 如何確定符合要求的出場陣容？ 解：設(shè) ????? 82101,jjjx ?否則號球員出場第???????????????????????????????????????821105121178180183185186188190192187654321626418762187654321,j,xxxxxxxxxxxxxxxxxxx. xj? 求解： 1 、 3 、 4 、 5 號和 7 號隊員，平均身高 6 米 第四節(jié) 分配問題