【正文】 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à)值最大 )? 指派問題的一般模型 min（ max） z= . ? ?01 1?? ?? ?ijninjijij cxc 1/0,2,1,1,2,1,111?????????ijniijnjijxnjxnix??指派問題的計(jì)算機(jī)求解 ? 用整數(shù)規(guī)劃程序求解，輸入：目標(biāo)函數(shù)、約束條件 ? 直接用指派問題程序求解，輸入：人數(shù)、任務(wù)數(shù)、效率矩陣。 運(yùn)輸問題 運(yùn)輸問題的一般提法是：設(shè)某種物資有 個(gè)產(chǎn)地 m ,1A ,2,?,mA各產(chǎn)地的產(chǎn)量是 。 7)( ?FD 中心問題： 中心醫(yī)務(wù)室應(yīng)建在哪個(gè)景點(diǎn)，可使離醫(yī)務(wù)室最遠(yuǎn)的景點(diǎn)游客就診時(shí)所走的路程最近？ 重心問題： 已知各景點(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ò) 最短路問題的數(shù)學(xué)建模 設(shè)始點(diǎn)為 1，終點(diǎn)為 n，引入 0－ 1決策變量 ，如果弧 (i,j)在從始點(diǎn)到終點(diǎn)的某條路徑上，則 ，否則 。即： ),( EVG ?),( ji vvijl ??ijl iv,sv jvt ?svt ? ?? ?? )v,v( ijjil)(L最小。雖然它生產(chǎn)的汽車在所有發(fā)達(dá)國家銷量都不錯(cuò)，對(duì)它來講，出口到美國尤其重要。 仍用決策變量 表示通過弧 (i,j)的流量， 表示弧 (i,j)的費(fèi)用系數(shù)， 表示弧 (i,j)上的容量，則數(shù)學(xué)模型為： ts vv ?ijx ijcijuij ij( i , j ) Esij ji s t( i , j ) E ( j , i ) Etij ijm ax z fc x Cf , ( i v )s .t . x x 0 , ( i v , v )f , ( i v )0 x u ( ( i , j ) E )????? ????????? ? ?????????? ? ? ??????最大流問題 一、 有關(guān)概念： 例：下圖是輸油管道網(wǎng)， 為起點(diǎn)， 為終點(diǎn)， ， ， ， 為中轉(zhuǎn)站，弧上的數(shù)字表示該管道的最大輸油能 力（也稱容量），記為 ，問應(yīng)如何安排各管道輸油量， 才能使從 到 的總輸油量最大？ 1v3v2,4v5 sv tv6v iju1v3v2v4v5vsv tv6v2333554svt1v3v2v4v5vsv tv6v2333554① 分別稱 為 發(fā)點(diǎn)、收點(diǎn) 。 網(wǎng)絡(luò)所有弧 （ i,j） ∈ G上的流量 xij（一共 n個(gè)分量）組成的向量 X=[xij]稱為 網(wǎng)絡(luò)的一個(gè)流 。 最小費(fèi)用流問題的假定 ；至少有一個(gè)節(jié)點(diǎn)是需求點(diǎn)；所有剩下的節(jié)點(diǎn)都是轉(zhuǎn)運(yùn)點(diǎn)。 ? 問題：確定一個(gè)運(yùn)輸方案（即每條路線運(yùn)送多少單位的產(chǎn)品），使得運(yùn)輸成本達(dá)到最小。 問題的提出： 在一個(gè)關(guān)于流的網(wǎng)絡(luò)中，每一個(gè)流量都有一定的費(fèi)用，流所走的路線不一樣，單位費(fèi)用不一樣。 ? 對(duì)于圖 G={V， E},如果任意兩個(gè)節(jié)點(diǎn)間都可以由一條或幾條邊連起來，則稱該圖為 連通圖 。 ? 問題：確定需要鋪設(shè)那些光纜使得提供給每個(gè)景點(diǎn)之間的高速通信的成本最低。否則，從圈上任意去掉一條邊，剩下的圖仍然滿足條件 ,并且成本更小。 ? 在所有的支撐樹中總成本最小的樹稱為 最小支撐樹 。 無限配送公司問題 ? 無限配送公司有兩家工廠生產(chǎn)產(chǎn)品 ,這些產(chǎn)品需要運(yùn)到兩個(gè)倉庫。 要求的凈流量 (流出減去流入 ) 是一個(gè)確定的負(fù)數(shù)的話，這個(gè)點(diǎn)就是一個(gè) 需求點(diǎn) 。 ，通過每一條弧的流的成本與流量成正比（ 費(fèi)用系數(shù) 是確定的）。即： ij( i, j ) E x?? ij ji i( i , j ) E ( j , i ) Ex x b , i 1 , 2 , ..., n??? ? ???b、 容量限制條件 ： ij ij0 x u , i , j 1 , 2 , ..., n? ? ?ji( j ,i ) E x?數(shù)學(xué)模型： 網(wǎng)絡(luò)的每一弧 (i,j),都有一個(gè)單位流量的費(fèi)用系數(shù) cij與它對(duì)應(yīng)，如果弧 (i,j)上的流量為 xij，則該弧上這些流量引起的費(fèi)用為 cijxij。 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。 ? 可以運(yùn)送多少配件的限制條件就是該公司配送網(wǎng)絡(luò)的容量。 。 ? 由于開車費(fèi)用，維修費(fèi)用隨著汽車的老化而飛速上漲，薩拉可以一次或者幾次折價(jià)將她的汽車置換為其他使用了 3年的二手車，在四年大學(xué)畢業(yè)后，她父母將送給她一輛新車，到那時(shí)她肯定計(jì)劃把舊車折價(jià)買出。與之相類似，每一個(gè)目的地都有一個(gè)固定的需求量，整個(gè)需求量都必須由出發(fā)地