【正文】 對系數(shù)矩陣來說，表現(xiàn)為系數(shù)矩陣不是方陣，而用匈牙利法求解時，系數(shù)矩陣為方陣是必要條件。 分配問題的匈牙利解法 分配問題的匈牙利解法 2. 增加 0元素 （ 1）在系數(shù)矩陣中沒有被覆蓋的元素中找最小元素 ?； （ 2）對沒有被直線覆蓋的行，減去最小元素 ?，對被直線覆蓋的列，加上最小元素 ?； 轉(zhuǎn)第二步。分別記作 E , J, G , R 。他們的 100 米自由泳、蛙泳、蝶泳、仰泳的成績?nèi)绫硭?。甲、乙、丙、丁四名隊員各自游什么姿勢，才最有可能取得好成績？ 成績 自由泳 蛙 泳 蝶 泳 仰 泳 甲 56 ? 74 ? 61 ? 63 ? 乙 63 ? 69 ? 65 ? 71 ? 丙 57 ? 77 ? 63 ? 67 ? 丁 55 ? 76 ? 62 ? 62 ? 解：設(shè)????種姿勢個人不游第第種姿勢個人游第第jijixij01 ?????????????????????????????????????????????????????????????????4321101111111162627655676377577165696363617456443424144333231342322212413121114443424134333231242322211413121144434241343332312423222114131211，或 jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.xxxxxxxxxxxxxxxxfmi nij 解得結(jié)果如下： 甲 —— 蝶泳 乙 —— 蛙泳 丙 —— 自由泳 丁 —— 仰泳 總成績 = 61+ 69+ 57 + 62= 249 （秒）。 第二步：求出相對應(yīng)的檢驗數(shù)； ? 求檢驗數(shù)的方法也不止一種，本書主要介紹 位勢法 和 閉回路法 。問如何安排生產(chǎn)，使獲得的總利潤最大？ 單位產(chǎn)品 占用設(shè)備臺時 產(chǎn)品甲 產(chǎn)品乙 設(shè)備工作 臺 時 設(shè)備 A 2 2 12 設(shè)備 B 1 2 8 設(shè)備 C 4 0 16 設(shè)備 D 0 4 12 利潤（百元 / 個） 2 3 m a x. .,f x xs tx xx xxxx x? ?? ?? ?????????????2 32 2 122 84 164 1201 21 21 2121 2它的解為 x1 * = 4 , x2* =2 ；最大目標函數(shù)值： f * = 14 從市場信息反饋可知，對甲、乙兩種產(chǎn)品需要量的比例大致是 1∶ 1； 計劃期內(nèi)的設(shè)備能力有一點機動的余地。 表 5 產(chǎn)品 單位消耗 資源 I I I 現(xiàn)有資源 鋼 材（噸） 1 2 100 （噸） 煤（噸） 2 2 180 （噸） 機械加工時間（小時） 1 6 240 （小時） 利 潤（萬元） 1 3 設(shè)： x 1 ， x 2 表示產(chǎn)品 I 和 I I 的計劃產(chǎn)量。 （三）資源的影子價格實際上又是一種機會成本。 因為如 f* 為上述線性規(guī)劃的最優(yōu)目標函數(shù)值，則 f * = C BTAB 1b = ( y *) b ，**iiybf??? 它表示在第 i 種資源數(shù)量 b i 附近的某個閉區(qū)間內(nèi)，該種資源數(shù)量增加一個單位（此時其他資源數(shù)量不變），生產(chǎn)計劃的最大利潤 f* 將增加 y i * 個單位。問應(yīng)如何配合使用這些肥料，既能滿足作物對氮，磷，鉀的需要，又使施肥成本最低？ 表 1 . 5 含量 肥料 成分 甲 乙 丙 丁 氮磷鉀肥的需要量（公斤） 氮 0. 03 0. 03 0 0. 15 32 磷 0. 05 0 0. 2 0. 1 24 鉀 0. 14 0 0 0. 07 42 價格 元 /公斤 0. 04 0. 15 0. 1 0. 13 對偶規(guī)劃（ 2） 設(shè)： x1, x2, x3, x4,分別表示甲，乙，丙，丁四種復(fù)合肥的用量 分析： ( 1 ) 表示購買的四種復(fù)合肥中含氮量不能小于作物對氮的需求量； ( 2 ) 表示購買的四種復(fù)合肥中含磷量不能小于作物對磷的需求量； ( 3 ) 表示購買的四種復(fù)合肥中含鉀量不能小于作物對鉀的需求量； ( 4 ) 表示購買的四種復(fù)合肥的量非負 ??????????????????)4(4,3,2`,0)3()2()1(.. i n414314214321????????jxxxxxxxxxtsxxxxfj對偶規(guī)劃（ 3） ???????????????3,2,1012526..52415m i n32132321jxxxxxxtsxxxfj????????????????0052426155..2m a x212121221yyyyyyytsyyg???????????????????4,3,2,101023421085..4335m i n432143214321jxxxxxxxxxtsxxxxfj ???????????????????????????無限制43214321432143214321,0,32417281473672..4765m i nxxxxxxxxxxxxxxxxtsxxxxf對偶規(guī)劃（ 4） 原問題 對偶問題 有最優(yōu)解 解無界 無可行解 有最優(yōu)解 √ － － 解無界 － － √ 無可行解 － √ √ 對偶單純形法（ 1） ????????????????0226343322121212121x,xxxxxxx.xxfm i n 解：引進松弛變量，化成標準型 ???????????????????????5102263433252142132121,. .. ,i,xxxxxxxxxx.xxffm a xi39。為使參加值班的總?cè)藬?shù)最少，試列出數(shù)學(xué)模型 J段 時間段 需人數(shù) 1 26 2 2 610 5 3 1014 10 4 1418 12 5 1822 6 6 222 7 ? Xjj時段初形成得人數(shù) j=1,2,3,4,5,6 ? Minf=x1+x2+x3+x4+x5+x6 ? X1+x6=2 ? X1+x2=5 ? X2+x3=10 ? X3+x4=12 ? X4+x5=6 ? X5+x6=7 運籌學(xué)模型（ 5） 【運輸問題】 現(xiàn)有兩個倉庫（發(fā)點）運送庫存原棉來滿足三個紡織廠（收點）的需要。假設(shè)每款手機需要各車間加工的工時（單位：小時）、每個車間的最大生產(chǎn)能力以及每款手機預(yù)期的利潤都已知，具體數(shù)據(jù)參見表 2 4 1 。 表 2 4 1 手機 車間 甲 乙 丙 丁 車間最大生產(chǎn)能力 A 1 . 5 3 1 3 1200 小時 B 8 20 3 12 3000 小時 C 3 8 3 5 2400 小時 單位利潤 200 元 1200 元 100 元 400 元 — 如果你是主管，應(yīng)該投產(chǎn)那幾種手機，各生產(chǎn)多少，才能獲得盡可能多的利潤？ 運籌學(xué)模型（ 2） 【七橋問題】 在哥雷斯堡（ Konigsbe rg ）有一條名叫普雷爾（ P r e g e l ）的河流從城市中間流過，普雷爾河的中央有一大一小兩座島嶼，河岸和兩座島由七座橋相互連接，如圖 3 53 所示 : 圖 3 53 于是在居民們每天散步的時候就產(chǎn)生了一項有趣的消遣活動：從 A 岸、 B 島、 C島、 D 岸這四個地方任選一處出發(fā)，走過所有七座橋，最后回到出發(fā)的地方，而且要求每座橋只能經(jīng)過一次，不得重復(fù)。三個紡織廠所需數(shù)量和兩個倉庫現(xiàn)有庫存量，以及每噸原棉從各個倉庫運送到各個紡織廠所需的運費見表 1 . 3 表 1 . 3 運輸費 工廠 1* 工廠 2* 工廠 3* 庫存量 （噸） 倉庫 1 2 1 3 50 倉庫 2 2 2 4 30 需求量（噸） 40 15 25 如何 調(diào)運 ， 才能 使 總 成本 最省 ？ 第一章 線性規(guī)劃 圖解法 單純型法 兩階段法 對偶規(guī)劃 對偶單純型法 靈敏度分析 目標規(guī)劃 圖解法（ 1） ——唯一最優(yōu)解 ???????????????)(08234..52m a x212121jxxxxxtsxxsj圖解法（ 2） ——基本概念 可行解 —— 不可行解 可行解集 （ 可行區(qū)域 ） 最優(yōu)解 最優(yōu)目標函數(shù)值 基本可行解 基本最優(yōu)解 圖解法（ 3） ——無窮多最優(yōu)解 ???????????????)(08234..2m a x212121jxxxxxtsxxsj圖解法（ 4） ——解無界 ?????????????0021..22m a x2,1212121xxxxxtsxxs圖解法（ 5） ——無可行解 ??????????????021..22m i n2,1212121xxxxxtsxxs圖解