【正文】 與之相類似，每一個(gè)目的地都有一個(gè)固定的需求量，整個(gè)需求量都必須由出發(fā)地滿足。 。 ijx1v3v2v4v5vsv tv6v)5,5( )2,3( )2,4( )2,( )2,4( )4,5( )3,3( ),3( )0,3( )2,( )2,( ： 對(duì)每一弧上都有 ij ij0 x u?? ： 轉(zhuǎn)運(yùn)點(diǎn)：流出量 流入量 =0。 ，通過(guò)每一條弧的流的成本與流量成正比（ 費(fèi)用系數(shù) 是確定的）。 無(wú)限配送公司問(wèn)題 ? 無(wú)限配送公司有兩家工廠生產(chǎn)產(chǎn)品 ,這些產(chǎn)品需要運(yùn)到兩個(gè)倉(cāng)庫(kù)。否則，從圈上任意去掉一條邊，剩下的圖仍然滿足條件 ,并且成本更小。 ? 對(duì)于圖 G={V， E},如果任意兩個(gè)節(jié)點(diǎn)間都可以由一條或幾條邊連起來(lái)，則稱該圖為 連通圖 。 ? 問(wèn)題：確定一個(gè)運(yùn)輸方案（即每條路線運(yùn)送多少單位的產(chǎn)品），使得運(yùn)輸成本達(dá)到最小。 網(wǎng)絡(luò)所有弧 （ i,j） ∈ G上的流量 xij（一共 n個(gè)分量）組成的向量 X=[xij]稱為 網(wǎng)絡(luò)的一個(gè)流 。雖然它生產(chǎn)的汽車在所有發(fā)達(dá)國(guó)家銷量都不錯(cuò)，對(duì)它來(lái)講，出口到美國(guó)尤其重要。 7)( ?FD 中心問(wèn)題： 中心醫(yī)務(wù)室應(yīng)建在哪個(gè)景點(diǎn)，可使離醫(yī)務(wù)室最遠(yuǎn)的景點(diǎn)游客就診時(shí)所走的路程最近？ 重心問(wèn)題： 已知各景點(diǎn)的員工人數(shù)分別為 40,25,45,30,20, 35,，可使所有員工在參加會(huì)議 時(shí)間所走的總路程最短？ BADCFEG2 21 3 15754474 )(jvh由于 最小，所以會(huì)議中心應(yīng)建在 C 875)( ?h公園的重心 (各個(gè)景點(diǎn)員工人數(shù) 40,25,45,30,20,35,50.) 景點(diǎn)號(hào) A B C D E F G A 0 80 160 20 320 280 520 B 50 0 50 75 150 125 275 C 180 90 0 45 180 135 405 D 150 90 30 0 150 120 300 E 160 120 80 100 0 20 100 F 245 175 105 140 35 0 210 G 650 550 450 500 250 300 0 1435 1105 875 1060 1085 980 1810 有向網(wǎng)絡(luò) 最短路問(wèn)題的數(shù)學(xué)建模 設(shè)始點(diǎn)為 1，終點(diǎn)為 n，引入 0－ 1決策變量 ，如果弧 (i,j)在從始點(diǎn)到終點(diǎn)的某條路徑上，則 ，否則 。要求 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只能由一個(gè)人干 ) x12+x22+x32+x42 =1 (B2只能由一個(gè)人干 ) x13+x23+x33+x43 =1 (B3只能由一個(gè)人干 ) x14+x24+x34+x44 =1 (B4只能由一個(gè)人干 ) xij ＝ 0或 1 ????第件事個(gè)人不做第第件事個(gè)人去做第定義ji,0ji,1xij指派問(wèn)題的一般描述 有 n個(gè)人 A1, A2, ?A n,要分派去做 n件事 B1, B2? B n,要求每一件事都必須有一個(gè)人去做 ,而且不同的事由不同的人去做 .已知每個(gè)人 Ai做每件事 Bj的效率 (如勞動(dòng)工時(shí)或成本 ,或創(chuàng)造的價(jià)值等 )為 Cij,應(yīng)如何進(jìn)行指派 (哪個(gè)人做哪件事 ),才能使工作效益最好 (如工時(shí)最少 ,或成本最低 ,或創(chuàng)造的價(jià)值最大 )? 指派問(wèn)題的一般模型 min（ max） z= . ? ?01 1?? ?? ?ijninjijij cxc 1/0,2,1,1,2,1,111?????????ijniijnjijxnjxnix??指派問(wèn)題的計(jì)算機(jī)求解 ? 用整數(shù)規(guī)劃程序求解，輸入：目標(biāo)函數(shù)、約束條件 ? 直接用指派問(wèn)題程序求解，輸入：人數(shù)、任務(wù)數(shù)、效率矩陣。 從一個(gè)節(jié)點(diǎn)到另外一個(gè)節(jié)點(diǎn)的弧表示在第一個(gè)節(jié)點(diǎn)這個(gè)時(shí)間買車，然后在第二個(gè)節(jié)點(diǎn)的那個(gè)時(shí)間把車折價(jià)賣掉的活動(dòng)． 最短路網(wǎng)絡(luò) (O ri g i n) (D e s t i na t i on )432117 ,0 0010 ,5 0010 ,5 005, 50 0 5, 50 0 5, 50 0 5, 50 025 ,0 0017 ,0 0010 ,5 000弧長(zhǎng)＝買車的價(jià)格＋使用和保養(yǎng)的費(fèi)用－折價(jià)買出的價(jià)值。許多優(yōu) 化問(wèn)題都可以使用這個(gè)模型，如設(shè)備更新、管道的鋪設(shè)、 線路的安排、廠區(qū)的布局等。即： 。 弧 。 2個(gè)步驟，直到所有的節(jié)點(diǎn)都有一條邊（可能會(huì)有多于一條邊）與其相連 . 此時(shí)，就得到了最優(yōu)解 (最小支撐樹(shù) ) 其中第 2步的目的是為了保證每次生成的樹(shù)都是連接當(dāng)前子圖的所有頂點(diǎn)的成本最小的樹(shù)。第 5章 :網(wǎng)絡(luò)優(yōu)化 所謂網(wǎng)絡(luò)優(yōu)化，簡(jiǎn)單地說(shuō)，即對(duì)網(wǎng)絡(luò)進(jìn)行定性和定量分析，以便為實(shí)現(xiàn)某種優(yōu)化目標(biāo)而尋求最優(yōu)方案．這方面的典型問(wèn)題有：最小支撐樹(shù)問(wèn)題，最小費(fèi)用流問(wèn)