[管理學(xué)]管理運籌學(xué)第一章_線性規(guī)劃-閱讀頁
2025-02-03 07:41本頁面
【正文】 數(shù) ? 混合整數(shù)規(guī)劃：僅部分變量限制為整數(shù) ? 01整數(shù)規(guī)劃：變量的取值僅限于 0或 1 [例 ] 人力資源分配的問題 某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員數(shù)如下： 設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘務(wù)人員 ? 班次 時間 所需人數(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： 00 —— 2： 00 20 6 2： 00 —— 6： 00 30 解：設(shè) xi 表示第 i班次時開始上班的司機和乘務(wù)人員數(shù) ,于是 LP模型為 : 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 且為整數(shù) min z=x1 + x2 + x3 + x4 + x5 + x6 ?????班次 時間 所需人數(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 ： 00 —— 2 ： 00 20 6 2 ： 00 —— 6 ： 00 30 最優(yōu)解： X* =(60 ， 10， 50 ， 0 ， 30 ， 0）， Z*=150 二、 01整數(shù)規(guī)劃 ? 投資場所的選址問題 ? 指派問題 ? 背包問題 ? 消防隊問題 1. 投資場所的選址問題 某城市擬在東、西、南三區(qū)設(shè)立商業(yè)網(wǎng)點，備選位置有A1~A7共 7個，如果選 Ai，估計投資為 bi元，利潤為 ci元，要求總投資不超過 B元，規(guī)定 東區(qū)： A A A3中至多選 2個 西區(qū)： A A5中至少選一個 南區(qū)： A A7中至少選一個 問如何設(shè)點使總利潤最大？ 1， Ai被選中 0， Ai沒被選中 ?????解：令 xi= max z= ??71iiixcxi=0或 1， i=1, … ,7 ∑ bixi≤B i=1 7 x1+x2+x3≤2 x4+x5≥1 x6+x7≥1 ?????. 課堂練習(xí) 1: 某鉆井隊要從 S1~S10共 10個井位中確定五個鉆井探油，如果選 Si，估計鉆探費用為 ci元，并且井位選擇上要滿足下列條件： （ 1） 或選擇 S1和 S7，或選擇 S8 。 （ 3） 在 S5， S6 ， S7， S8中最多只能選兩個。 要求： 每人只能完成一項任務(wù)，每項任務(wù)只能由一人完成。為組成一個 4 100m混合泳接力隊，怎樣選派運動員，方使接力隊的游泳成績最好？ 運動員 仰泳 蛙泳 蝶泳 自由泳 甲 乙 丙 丁 3. 背包問題 問題描述 已知： 一個背包最大容量為 b公斤；有 m件物品供選擇，每件物品重 ai公斤，價值為 ci（ i=1,…,m ）。他最多能帶 115kg的物品，現(xiàn)有 5件物品，分別重 5 35 4 19kg，其價值依次為 3。下圖① ~④ 表示消防站， 1~11表示防火區(qū)域，圖中連線表示各地區(qū)由哪個消防站負責(zé)。已知備選校址代號及其能覆蓋的居民小區(qū)編號如表所示，問為覆蓋所有小區(qū)至少應(yīng)建多少所小學(xué)？ 備選校址代號 覆蓋的居民小區(qū)編號 ABCDEF 7 5 5 5 6 6 167。 B1 B2 B3 B4 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 3 6 5 6 3 1 3 4 6 3 根據(jù)閉回路計算空格的檢驗數(shù)： 檢驗數(shù) = 奇數(shù)頂點的單位運價之和 – 偶數(shù)頂點的單位運價之和 B1 B2 B3 B4 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 3 6 5 6 3 1 3 4 6 3 1 2 1 1 10 12 檢驗數(shù)的經(jīng)濟含義：當由產(chǎn)地Ai往銷地 Bj增運一個單位貨物時所引起的總運輸成本的變化數(shù) 結(jié)論：若所有檢驗數(shù)都大于等于 0，則當前方案最優(yōu) B1 B2 B3 B4 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 3 6 5 6 3 1 3 4 6 3 1 1 2 1 10 12 對現(xiàn)有方案進行調(diào)整 在負的檢驗數(shù)中選擇絕對值最大的空格，在方案表中從該空格出發(fā)，沿著其閉回路依次標上 “ +q‖、 “ q‖， +q q +q q 其中 q表示最大調(diào)整量，它的取值為標 “ q‖的數(shù)字中最小的數(shù)值。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如右表。 試求在完成合同的情況下，使該廠全年生產(chǎn)總費用為最小的決策方案。已知該廠各季度的生產(chǎn)能 力及生產(chǎn)每臺柴油機的成本如右表。 試求在完成合同的情況下，使該廠全年生產(chǎn)總費用為最小的決策方案
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1