【正文】 運籌學模型（ 1） [ 生產計劃模型 ] 國內某手機產商考慮生產甲、乙、丙、丁型號的四款手機，每款手機都需要依次經過 A 、 B 、 C 三個車間加工完成。假設每款手機需要各車間加工的工時（單位：小時）、每個車間的最大生產能力以及每款手機預期的利潤都已知，具體數據參見表 2 4 1 。 表 2 4 1 手機 車間 甲 乙 丙 丁 車間最大生產能力 A 1 . 5 3 1 3 1200 小時 B 8 20 3 12 3000 小時 C 3 8 3 5 2400 小時 單位利潤 200 元 1200 元 100 元 400 元 — 如果你是主管，應該投產那幾種手機，各生產多少，才能獲得盡可能多的利潤？ 運籌學模型（ 2） 【七橋問題】 在哥雷斯堡（ Konigsbe rg ）有一條名叫普雷爾（ P r e g e l ）的河流從城市中間流過，普雷爾河的中央有一大一小兩座島嶼，河岸和兩座島由七座橋相互連接，如圖 3 53 所示 : 圖 3 53 于是在居民們每天散步的時候就產生了一項有趣的消遣活動：從 A 岸、 B 島、 C島、 D 岸這四個地方任選一處出發(fā)，走過所有七座橋，最后回到出發(fā)的地方，而且要求每座橋只能經過一次，不得重復。 B C A D 運籌學模型（ 3） 【合理下料問題】 某工地要求做 100 套鋼筋，每套為 3 根，它們的長度分別 為 米， 米和 米；原材料長為 米，為應當怎樣截割鋼筋，才能使所需的原材料根數為最少？ 提示 1：如果只需要截 100根，如何下料？ 提示 2：如果需要截 100根，又如何下料？ 有八種方法截取 ? 1 2 3 4 5 6 7 8 2 1 1 1 0 0 0 0 0 2 1 0 3 2 1 0 0 0 1 3 0 1 3 4 x1 x2 x3 x4 x5 x6 x7 x8 ? Mf=x1+x2+x3+x4+x5+x6+x7+x8 ? 2x1+x2+x3+x4=100 ? 2x2+3x3 +3x5+2x6+x7=100 ? x3+3x4 +x6+3x7+x8=100 ? Xj=0且為整數 j=1,2,3,……8 運籌學模型（ 4） 【排班問題】 某工廠的中心調度室，每晝夜 24 小時都要有人員值班，已知每個時間段（每 4 小時為一個時間段）所需要的值班人員如表 1 . 6 。又知每一調度人員在任 1 時段開始上班后，要連續(xù)工作 8 小時（包括輪流吃飯時間）才能滿足調度值班工作需要。為使參加值班的總人數最少，試列出數學模型 J段 時間段 需人數 1 26 2 2 610 5 3 1014 10 4 1418 12 5 1822 6 6 222 7 ? Xjj時段初形成得人數 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 運籌學模型（ 5） 【運輸問題】 現(xiàn)有兩個倉庫（發(fā)點）運送庫存原棉來滿足三個紡織廠（收點）的需要。三個紡織廠所需數量和兩個倉庫現(xiàn)有庫存量，以及每噸原棉從各個倉庫運送到各個紡織廠所需的運費見表 1 . 3 表 1 . 3 運輸費 工廠 1* 工廠 2* 工廠 3* 庫存量 （噸） 倉庫 1 2 1 3 50 倉庫 2 2 2 4 30 需求量（噸） 40 15 25 如何 調運 ， 才能 使 總 成本 最省 ？ 第一章 線性規(guī)劃 圖解法 單純型法 兩階段法 對偶規(guī)劃 對偶單純型法 靈敏度分析 目標規(guī)劃 圖解法（ 1） ——唯一最優(yōu)解 ???????????????)(08234..52m a x212121jxxxxxtsxxsj圖解法（ 2） ——基本概念 可行解 —— 不可行解 可行解集 （ 可行區(qū)域 ） 最優(yōu)解 最優(yōu)目標函數值 基本可行解 基本最優(yōu)解 圖解法（ 3） ——無窮多最優(yōu)解 ???????????????)(08234..2m a x212121jxxxxxtsxxsj圖解法（ 4） ——解無界 ?????????????0021..22m a x2,1212121xxxxxtsxxs圖解法（ 5） ——無可行解 ??????????????021..22m i n2,1212121xxxxxtsxxs圖解法（ 6） —— 結論 線性規(guī)劃問題的解有四種情況 1．有唯一最優(yōu)解 2．有無窮多最優(yōu)解 3．有可行解，但無最優(yōu)解（解無界） 4．無可行解 單純型法 標準化 單純型法 線性規(guī)劃問題的標準形式 (一 ) 1．目標函數求最大 2．約束條件取等號 3．變量為非負 11( 1 )m a x( 1 , 2 , ..., ).0 ( 1 , 2 , ..., )njjjnij j ijjf c xa x b i mstx j n????????? ?????標 準 形 的 代 數 表 示 ? ?? ?? ?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ī) 劃 問 題 化 為 標 準 形， ，單純型法（一） 某工廠計劃在一個生產周期內生產甲、乙兩種產品，這兩種產品分別需要經過 A、 B兩道工序加工。已知每件產品在每道工序上加工所需的機時及生產每件產品可以獲得的利潤如下表，如何安排生產，才能使總利潤最大？ 甲 乙 可用機時 工序 A 2 4 80 工序 B 3 2 60 單位利潤 60 50 單純型法（二） 80. . 6 0012121212ma x f = 6 0 x +5 0 x2 x +4 xs t 3 x +2 xx 0 , x?????? ???（ 0， 20） C B（ 10， 15） （ 0， 0） O A （ 20， 0） 2x1x單純型法（三） 3480. . 6 01 2 3 41121212ma x f = 6 0 x +50 x2 x +4x xs t 3 x +2x xx 0 , j? ??????? ??? ， ， ，（ 0， 20） C B（ 10， 15） （ 0， 0） O A （ 20， 0） 2x單純型法（四） 3480. . 6 01 2 3 41121212ma x f = 6 0 x +50 x2 x +4x xs t 3 x +2x xx 0 , j? ??????? ??? ， ， ，???????????????????432102031324032382022120042143242,j,xxxxxxx.xxfma xj????????????????????43210302123402425151 5 0 042143141,j,xxxxxxx.xxfm a xj??????????????????432104021260234321432,j,xxxxxxx.fma xj??????????????????4,3,2,1,020212204121..225351000m a x43132131jxxxxxxxtsxxfj???????????????????4,3,2,1,0154183102141..2354151350m a x43243143jxxxxxxxtsxxfj單純型法（五） 基變量 ————“非自由變量”，記號 xB 非基變量 ————“自由變量”，記號 基 —— 所有基變量下標的集合，記號 B 典式 —— 約束等式是基變量由非基變量表示； 目標函數中不含有基變量 單純形表 ——基可行解典式的表格化 ? 檢驗數 ? 入基變量 ? 出基變量 ? 轉軸點 Bx單純型法（六） ?????????????)2,1(08234..52m a x212121jxxxxxtsxxfj解：引進松弛變量 x3 , x4 , x5，把線性規(guī)劃問題化為標準形 ??????????????????)51(08234..52m a x521423121?jxxxxxxxxtsxxfj單純型法（七） 基變量 XB=(x3 , x4 , x5)，可以得到對應的單純形表如下： CxB x1 x2 x3 x4 x5 x3 1 0 1 0 0 4 x4 0 1 0 1 0 3 x5 1 2 0 0 1 8 ? 2 5 0 0 0 0 b[1] 單純型法（八） 單純表矩陣計算公式： X b XB 1?BAA 1?BAb c