數(shù)據(jù)模型決策05網絡優(yōu)化-資料下載頁
2025-03-09 11:33本頁面
【正文】 nj jmjjjnjbxbxxx11 101002011 )...(?????njjmii ba11從而有 運輸問題的變形 ? 總供應量 ≠ 總需求量的情形 ? 供＞求， LP模型中把約束 ∑ xij＝ ai改為 ∑ xij≤a i即可 ? 供＜求， LP模型中把約束 ∑ xij＝ bj改為 ∑ xij≤b j即可 ? 目標函數(shù)最大化的情形，如目標是追求利潤或收入時，只需將目標函數(shù)改為 max即可 ? 某些路線的運輸能力有一定限制的情形 如從 A2到 B3受到運輸能力限制，最多只能運送 150時，只需在原 LP模型上添加 x23≤150 即可 運輸問題的計算機求解 ? 用線性規(guī)劃程序求解，輸出部分信息多，且變量和約束輸入較麻煩。 ? 用運輸問題程序求解，只需輸入產地個數(shù)、銷地個數(shù)、各產地的產量、各銷地的銷量、各產地到各銷地的單位運價。前例輸入后，得到的最優(yōu)運輸方案為： 銷地產地 B1 B2 B3 產量 A1 50 150 0 200 A2 100 0 200 300 銷量 150 150 200 指派問題 有 4個工人 ,要指派他們分別 完成 4項工作 ,每人做各項工作所消耗的時間如下表。要求 1人只做 1件事 ，如何指派使總成本最少 ? 人 工作 B1 B2 B3 B4 工資 A1 35 41 27 40 14 A2 47 45 32 51 12 A3 39 56 36 43 13 A4 32 51 25 46 15 模型 用 01變量表示“是非”決策： min z=14*35x11+14*41 x12 +14*27 x13+14*40 x14 +12* 47x21+ 12*45 x22+ 12*32x23 +12*51x24 +13*39x31 +13*56x32 + 13*36x33 + 13*43 x34 +15*32x41 +15*51x42 +15*25x43 +15*46x44 . x11+x12+x13+x14 =1 (A1只能干一件事 ) x21+x22+x23+x24 =1 (A2只能干一件事 ) x31+x32+x33+x34 =1 (A3只能干一件事 ) x41+x42+x43+x44 =1 (A4只能干一件事 ) x11+x21+x31+x41 =1 (B1只能由一個人干 ) x12+x22+x32+x42 =1 (B2只能由一個人干 ) x13+x23+x33+x43 =1 (B3只能由一個人干 ) x14+x24+x34+x44 =1 (B4只能由一個人干 ) xij ＝ 0或 1 ????第件事個人不做第第件事個人去做第定義ji,0ji,1xij指派問題的一般描述 有 n個人 A1, A2, ?A n,要分派去做 n件事 B1, B2? B n,要求每一件事都必須有一個人去做 ,而且不同的事由不同的人去做 .已知每個人 Ai做每件事 Bj的效率 (如勞動工時或成本 ,或創(chuàng)造的價值等 )為 Cij,應如何進行指派 (哪個人做哪件事 ),才能使工作效益最好 (如工時最少 ,或成本最低 ,或創(chuàng)造的價值最大 )? 指派問題的一般模型 min（ max） z= . ? ?01 1?? ?? ?ijninjijij cxc 1/0,2,1,1,2,1,111?????????ijniijnjijxnjxnix??指派問題的計算機求解 ? 用整數(shù)規(guī)劃程序求解，輸入：目標函數(shù)、約束條件 ? 直接用指派問題程序求解，輸入：人數(shù)、任務數(shù)、效率矩陣。 指派問題的假設 ? 每一個指派者和每項任務的組合都會有一個相關的成本 ? 每一個指派者只能完成一項任務 ? 每項任務只能由一個指派者來完成 ? 被指派者的數(shù)量和任務數(shù)量是相同的 ? 問題的目標是進行怎樣的指派才能使得總成本最小 前三個假設在通常情況下并不滿足 . 例 :某市準備在五年內投資三個項目 ,現(xiàn)有可供選擇的項目五個 ,有四個開發(fā)商前來投標 . 問 :應該選擇那三家開發(fā)商來開發(fā)哪三個項目所需要的總時間最少 ? 項目 開發(fā)商 1 2 3 4 5 A 4 6 9 8 12 B 6 10 11 12 M C 8 7 5 3 12 D 9 8 6 5 10 ij ij45ij iji 1 j 1i 1 i 2 i 5 i1 j 2 j 4 j j4ii15jj1ij i jx i j y izjm in z c xs . t .x x ... x y ( i 1 , 2 , 3 , 4 )x x ... x z ( j 1 , 2 , 3 , 4 , 5 )y3z3x , y , z 0 1 i 1 , 2 , 3 , 4 j 1 , 2 , 3 , 4 , 5??????? ? ? ? ??? ? ? ? ? ??????? ? ?????解 ： 設 表 示 第 個 開 發(fā) 商 是 否 開 發(fā) 第 個 項 目 ， 表 示 第 個 開 發(fā) 商是 否 參 加 開 發(fā) ， 表 示 第 個 項 目 是 否 被 開 發(fā)或 （ 。 ）?????多重指派：一個人可以被分派做幾件事 ??????????????????? ???? ?），（或的總時間量為可分配給工人所需要的時間，工作完成表示工人，否則取時取分配給工人變量，當工作為設njmixnjaxcmixtsxczjaijcjixijmijijijnjijminjijijjijij,... ,2,1,... ,2,110),... ,2,1(),... ,2,1(1..min0110111 1
教學課件相關推薦
鄂ICP備17016276號-1