數(shù)據(jù)模型決策05網(wǎng)絡(luò)優(yōu)化（64頁(yè))ppt課件

1、第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)化目的而尋求最優(yōu)方案這方面的典型問(wèn)題有：最小支撐樹(shù)問(wèn)題，最小費(fèi)用流問(wèn)題、最大流問(wèn)題、最短路問(wèn)題，中心問(wèn)題，重心問(wèn)題、運(yùn)輸問(wèn)題、指派問(wèn)題等等樹(shù)圖構(gòu)造：最小支撐樹(shù)問(wèn)題光纜通訊銜接問(wèn)題 某公園決議鋪設(shè)最先進(jìn)的光纖網(wǎng)絡(luò)，為它的主要景點(diǎn)之間提供高速通訊(數(shù)據(jù)，聲音和錄像)。 為了利用光纖技術(shù)在景點(diǎn)之間高速通訊的優(yōu)勢(shì)，不需求在每?jī)蓚€(gè)景點(diǎn)之間都用一條光纜把他們直接聯(lián)絡(luò)起來(lái)。問(wèn)題：確定需求鋪設(shè)那些光纜使得提供應(yīng)每個(gè)景點(diǎn)之間的高速通訊的本錢(qián)最低。公園光纜通訊問(wèn)題的途徑系統(tǒng)圖中虛線表示可供選擇的邊最正確的處理方法 由于恣意兩個(gè)節(jié)

2、點(diǎn)之間均可以通訊，這個(gè)圖必需是連通圖。并且，這個(gè)圖必需是無(wú)圈的。否那么，從圈上恣意去掉一條邊，剩下的圖依然滿足條件,并且本錢(qián)更小。樹(shù)、圖的專有名詞 圖G定義為點(diǎn)和邊的集合,記為G=V，E,其中，是點(diǎn)的集合，是邊的集合。有向圖區(qū)別于無(wú)向圖的關(guān)鍵，在于它的邊此時(shí)也稱弧是有方向的。一個(gè)圖連同定義在其邊集上的實(shí)函數(shù)一同稱為一個(gè)網(wǎng)絡(luò)，我們把定義在邊集上的實(shí)函數(shù)稱為邊的權(quán)數(shù)。該網(wǎng)絡(luò)記為V，E，W。 對(duì)于圖G=V，E,假設(shè)恣意兩個(gè)節(jié)點(diǎn)間都可以由一條或幾條邊連起來(lái)，那么稱該圖為連通圖。連通并且不含圈的無(wú)向圖稱為樹(shù)。假設(shè)樹(shù)中點(diǎn)的集合等于圖的點(diǎn)的集合，樹(shù)中邊的集合是圖的邊的集合的子集，稱樹(shù)為圖的支撐樹(shù)。在一切的支

3、撐樹(shù)中總本錢(qián)最小的樹(shù)稱為最小支撐樹(shù)。最小支撐樹(shù)問(wèn)題的算法 選擇第一條邊：選擇本錢(qián)最低的備選邊圖中虛線。 選擇下一條邊：在一個(gè)曾經(jīng)有一條邊銜接的節(jié)點(diǎn)和另一個(gè)還沒(méi)有邊銜接的節(jié)點(diǎn)之間選擇本錢(qián)最低的備選邊。 反復(fù)第2個(gè)步驟，直到一切的節(jié)點(diǎn)都有一條邊能夠會(huì)有多于一條邊與其相連 . 此時(shí)，就得到了最優(yōu)解(最小支撐樹(shù))其中第2步的目的是為了保證每次生成的樹(shù)都是銜接當(dāng)前子圖的一切頂點(diǎn)的本錢(qián)最小的樹(shù)。算法的運(yùn)用： 初次銜接 V=C，D W=A，B，E，F(xiàn)，G從V中的節(jié)點(diǎn)連向W中節(jié)點(diǎn)的備選邊中選擇本錢(qián)最小的一條邊算法的運(yùn)用： 第二次銜接 V=B，C，D W=A，E，F(xiàn)，G算法的運(yùn)用： 第三次銜接 V=A，B，C，

4、D W=E，F(xiàn)，G算法的運(yùn)用： 第四次銜接 V=A，B，C，D，F(xiàn) W=E，G算法的運(yùn)用： 第五次銜接 V=A，B，C，D，E，F(xiàn) W=G算法的運(yùn)用： 最后的銜接 V=A，B，C，D，E，F(xiàn)，G最小費(fèi)用流問(wèn)題 這里的流是一個(gè)廣泛的概念，例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流、供水系統(tǒng)中有水流，金融系統(tǒng)中有現(xiàn)金流，通訊系統(tǒng)中有信息流，等等。 問(wèn)題的提出：在一個(gè)關(guān)于流的網(wǎng)絡(luò)中，每一個(gè)流量都有一定的費(fèi)用，流所走的道路不一樣，單位費(fèi)用不一樣。同樣數(shù)量的流量，由于走的道路不一樣，總的費(fèi)用也不一樣。從而我們希望確定在給定網(wǎng)絡(luò)流量的根底上，讓流沿著怎樣的道路走，能使總的費(fèi)用最小。無(wú)限配送公司問(wèn)題 無(wú)限配送

5、公司有兩家工廠消費(fèi)產(chǎn)品,這些產(chǎn)品需求運(yùn)到兩個(gè)倉(cāng)庫(kù)。工廠1消費(fèi)80個(gè)單位；工廠2消費(fèi)70個(gè)單位。 倉(cāng)庫(kù)1需求60個(gè)單位；倉(cāng)庫(kù)2需求90個(gè)單位 。工廠1和倉(cāng)庫(kù)1之間以及工廠2和倉(cāng)庫(kù)2之間各有一條鐵路運(yùn)輸軌道。卡車司機(jī)總共可以從每家工廠運(yùn)輸50個(gè)單位到配送中心，然后可以從配送中心運(yùn)輸50個(gè)單位到每個(gè)倉(cāng)庫(kù) 任何運(yùn)輸?shù)脚渌椭行牡漠a(chǎn)品必需隨后運(yùn)送到倉(cāng)庫(kù)。問(wèn)題：確定一個(gè)運(yùn)輸方案即每條道路運(yùn)送多少單位的產(chǎn)品，使得運(yùn)輸本錢(qián)到達(dá)最小。網(wǎng)絡(luò)模型 凈流量=流出-流入最小費(fèi)用流的專有名詞 網(wǎng)絡(luò)中的圓圈被稱為節(jié)點(diǎn)。 假設(shè)節(jié)點(diǎn)要求的凈流量(流出減去流入) 是一個(gè)確定的正數(shù)的話，這個(gè)點(diǎn)就是一個(gè)供應(yīng)點(diǎn)。 假設(shè)節(jié)點(diǎn)要求的凈流量(

6、流出減去流入) 是一個(gè)確定的負(fù)數(shù)的話，這個(gè)點(diǎn)就是一個(gè)需求點(diǎn)。假設(shè)節(jié)點(diǎn)要求的凈流量恒為0，這個(gè)點(diǎn)稱為轉(zhuǎn)運(yùn)點(diǎn)。我們把流出接點(diǎn)的量等于流入節(jié)點(diǎn)的量稱為流量守恒。在網(wǎng)絡(luò)里的箭頭被稱為弧。 允許經(jīng)過(guò)某一條弧的最大流量被稱為該弧的容量。 最小費(fèi)用流問(wèn)題的假定 至少有一個(gè)節(jié)點(diǎn)是供應(yīng)點(diǎn)；至少有一個(gè)節(jié)點(diǎn)是需求點(diǎn)；一切剩下的節(jié)點(diǎn)都是轉(zhuǎn)運(yùn)點(diǎn)。 經(jīng)過(guò)弧的流只允許沿著箭頭的方向流動(dòng)，經(jīng)過(guò)弧的最大流量取決于該弧的容量。網(wǎng)絡(luò)中有足夠的弧提供足夠的容量，使得一切在供應(yīng)點(diǎn)產(chǎn)生的流都可以到達(dá)需求點(diǎn)。 在流的單位本錢(qián)知的前提下，經(jīng)過(guò)每一條弧的流的本錢(qián)與流量成正比費(fèi)用系數(shù)是確定的。 最小費(fèi)用流問(wèn)題的目的是在給定需求的條件下，使經(jīng)過(guò)網(wǎng)

7、絡(luò)供應(yīng)的總本錢(qián)最小。一個(gè)網(wǎng)絡(luò)模型 凈流量=流出-流入數(shù)學(xué)模型最正確的處理方法 最小費(fèi)用流問(wèn)題的數(shù)學(xué)建模 設(shè)一個(gè)有n個(gè)節(jié)點(diǎn)，m條弧的網(wǎng)絡(luò)圖, ，每一個(gè)節(jié)點(diǎn)i都對(duì)應(yīng)于一個(gè)數(shù)bi，表示該節(jié)點(diǎn)要求的凈流量。 假設(shè)bi0，節(jié)點(diǎn)i為供應(yīng)節(jié)點(diǎn)，供應(yīng)量為bi；假設(shè)bi0，那么為需求節(jié)點(diǎn)，需求量為-bi； 假設(shè)bi=0，該節(jié)點(diǎn)為轉(zhuǎn)運(yùn)點(diǎn)。 對(duì)于一個(gè)網(wǎng)絡(luò)，假設(shè)有 ，稱為供求平衡的網(wǎng)絡(luò)。 網(wǎng)絡(luò)一切弧i,jG上的流量xij一共n個(gè)分量組成的向量X=xij稱為網(wǎng)絡(luò)的一個(gè)流。網(wǎng)絡(luò)中求流量分配使總流量到達(dá)一定要求，而總費(fèi)用最低假設(shè)網(wǎng)絡(luò)的一個(gè)流滿足以下條件，那么這樣的流稱為可行流。a、平衡條件：對(duì)網(wǎng)絡(luò)中的任一節(jié)點(diǎn)i，在網(wǎng)絡(luò)中從

8、節(jié)點(diǎn)i經(jīng)過(guò)弧(i,j)流向關(guān)聯(lián)的他節(jié)點(diǎn)j的流量xij之和減去與節(jié)點(diǎn)i關(guān)聯(lián)的其他節(jié)點(diǎn)j經(jīng)過(guò)弧(j,i)流入i的流量xji之和 與該節(jié)點(diǎn)要求的凈流量平衡。即：b、容量限制條件：數(shù)學(xué)模型：網(wǎng)絡(luò)的每一弧(i,j),都有一個(gè)單位流量的費(fèi)用系數(shù)cij與它對(duì)應(yīng)，假設(shè)弧(i,j)上的流量為xij，那么該弧上這些流量引起的費(fèi)用為cijxij。網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題就是找到使總費(fèi)用最小的可行流。模型有可行解的必要條件是：該網(wǎng)絡(luò)是供求平衡的網(wǎng)絡(luò)。即： 。為什么？最小費(fèi)用流問(wèn)題的數(shù)學(xué)建模2另一類最小費(fèi)用流問(wèn)題是在預(yù)算費(fèi)用C給定的情況下，求流量分配，使得從 可以保送的總流量到達(dá)最大。 仍用決策變量 表示經(jīng)過(guò)弧(i,j)的流

9、量， 表示弧(i,j)的費(fèi)用系數(shù)， 表示弧(i,j)上的容量，那么數(shù)學(xué)模型為：最大流問(wèn)題一、 有關(guān)概念：例：以下圖是輸油管道網(wǎng)， 為起點(diǎn)， 為終點(diǎn)， ， ， ， 為中轉(zhuǎn)站，弧上的數(shù)字表示該管道的最大輸油能 力也稱容量，記為 ，問(wèn)應(yīng)如何安排各管道輸油量，才干使從 到 的總輸油量最大？ 分別稱 為發(fā)點(diǎn)、收點(diǎn)。其他的點(diǎn)稱為轉(zhuǎn)運(yùn)點(diǎn)。 每一個(gè)弧上都給定一個(gè)容量的網(wǎng)絡(luò)稱為容量網(wǎng)絡(luò)，記 的每一個(gè)弧上都給定一個(gè)實(shí)踐流量 的網(wǎng)絡(luò)稱為給定了網(wǎng)絡(luò)一個(gè)流。b.容量限制條件： 對(duì)每一弧上都有 a.平衡條件： 轉(zhuǎn)運(yùn)點(diǎn)：流出量-流入量=0。 發(fā)收點(diǎn)：發(fā)點(diǎn)流出量=收點(diǎn)流入量=網(wǎng)絡(luò)總流量。 假設(shè) ，稱弧 是飽和弧。使網(wǎng)絡(luò)總流量

10、到達(dá)最大的可行流稱為最大流 。假設(shè)網(wǎng)絡(luò)的一個(gè)流滿足以下條件，那么這樣的流稱為可行流:最大流問(wèn)題的數(shù)學(xué)建模 用決策變量 表示經(jīng)過(guò)弧(i,j)的流量， 表示弧(i,j)的容量，那么數(shù)學(xué)模型為：BMZ公司的最大流問(wèn)題 BMZ公司是歐洲一家消費(fèi)奢華汽車的制造商。雖然它消費(fèi)的汽車在一切興隆國(guó)家銷量都不錯(cuò)，對(duì)它來(lái)講，出口到美國(guó)尤其重要。BMZ汽車正在加利福尼亞變得特別受歡迎，因此保證洛杉磯中心良好的供應(yīng)顯得特別的重要。 大部分汽車配件以及新車是在該公司位于德國(guó)的斯圖加特的總廠消費(fèi)的，BMZ公司需求制定一個(gè)方案，使得下個(gè)月從總廠運(yùn)送到洛杉磯配送中心的配件流盡能夠大。 可以運(yùn)送多少配件的限制條件就是該公司配送

11、網(wǎng)絡(luò)的容量。 問(wèn)題：經(jīng)過(guò)每條運(yùn)輸?shù)缆房梢赃\(yùn)送多少貨物，使得從總廠運(yùn)送到洛杉磯配送中心的配件流最大。 BMZ 銷售網(wǎng) BMZ的一個(gè)網(wǎng)絡(luò)模型 ACBFEG708070604050305040D數(shù)學(xué)模型最短路問(wèn)題最短路問(wèn)題是網(wǎng)絡(luò)實(shí)際中運(yùn)用最廣泛的問(wèn)題之一。許多優(yōu)化問(wèn)題都可以運(yùn)用這個(gè)模型，如設(shè)備更新、管道的鋪設(shè)、線路的安排、廠區(qū)的規(guī)劃等。最短路問(wèn)題的普通提法是：設(shè) 為連通圖，圖中各邊或弧 有權(quán) ( 表示 ， 間沒(méi)有邊或弧, 為圖中恣意兩點(diǎn)，求一條道路 ，使它是從 到 的一切路中總權(quán)最小的路。即： 最小。最短路問(wèn)題的假定 在網(wǎng)絡(luò)中選擇一條路，這條路始于某一節(jié)點(diǎn)，叫做始點(diǎn)，并且終于另一個(gè)節(jié)點(diǎn)，叫終點(diǎn)。 連

12、結(jié)兩個(gè)節(jié)點(diǎn)的連線通常叫做邊(允許任一方向的行進(jìn),也允許存在弧(只允許朝一個(gè)方向行進(jìn))。 與每條邊相關(guān)的一個(gè)非負(fù)數(shù)稱為該邊的長(zhǎng)度。(留意，邊和弧也能夠代表其他類型的活動(dòng)) 目的是為了選擇從始點(diǎn)到終點(diǎn)的最短路(總長(zhǎng)度最小的路) 。 一個(gè)最短路問(wèn)題的運(yùn)用：為了實(shí)現(xiàn)更加人性化的效力,公園管理層需求面向游客出一本旅游線路指南的小冊(cè)子。 在該小冊(cè)子中要通知旅客從公園入口,各個(gè)景點(diǎn)之間以及入口之間的最短線路。問(wèn)題:首先思索從公園入口到公園出口的最短線路.景點(diǎn)號(hào)A B C D E F GA0 2 4 5 8 7 1313B2 0 2 3 6 5 1111C4 2 0 1 4 3 99D5 3 1 0 5 4

13、1010E8 6 4 5 0 1 58F7 5 3 4 1 0 67G13 11 9 10 5 6 013由于 最小，所以醫(yī)院應(yīng)建在F ，此時(shí)離醫(yī)院最遠(yuǎn)的景點(diǎn)A 間隔為7。 中心問(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,50.那么會(huì)議中心應(yīng)建在哪個(gè)景點(diǎn)，可使一切員工在參與會(huì)議時(shí)間所走的總路程最短？ 由于 最小，所以會(huì)議中心應(yīng)建在C公園的重心(各個(gè)景點(diǎn)員工人數(shù)40,25,45,30,20,35,50.)景點(diǎn)號(hào)ABCDEFGA08016020320280520B50050751501252

14、75C18090045180135405D15090300150120300E16012080100020100F245175105140350210G650550450500250300014351105875106010859801810有向網(wǎng)絡(luò)最短路問(wèn)題的數(shù)學(xué)建模 設(shè)始點(diǎn)為1，終點(diǎn)為n，引入01決策變量 ，假設(shè)弧(i,j)在從始點(diǎn)到終點(diǎn)的某條途徑上，那么 ，否那么 。那么數(shù)學(xué)模型為：使總本錢(qián)最小的最短路問(wèn)題薩拉剛剛高中畢業(yè)。在畢業(yè)儀式上，她父母給了她21000美圓的汽車基金協(xié)助她購(gòu)買(mǎi)并保養(yǎng)一輛運(yùn)用了3年的二手車，以供她上大學(xué)。 由于開(kāi)車費(fèi)用，維修費(fèi)用隨著汽車的老化而飛速上漲，薩拉可以一次

15、或者幾次折價(jià)將她的汽車置換為其他運(yùn)用了3年的二手車，在四年大學(xué)畢業(yè)后，她父母將送給她一輛新車，到那時(shí)她一定方案把舊車折價(jià)買(mǎi)出。問(wèn)題：在接下來(lái)的3個(gè)暑期，薩拉什么時(shí)候應(yīng)該折價(jià)買(mǎi)掉她的汽車(假設(shè)必要的話)可以使得她在大學(xué)四年的開(kāi)車，買(mǎi)車，保養(yǎng)汽車的總費(fèi)用最?。?薩拉破費(fèi)數(shù)據(jù) 擁有年份的開(kāi)車和維修費(fèi) 最后一年買(mǎi)出的價(jià)值 購(gòu)買(mǎi) 價(jià)格 1234123412，000 美元 2，000 美元 3，000 美元 4，500 美元 6，500 美元 8，500 美元 6，500 美元 4，500 美元 3，000 美元 問(wèn)題：在接下來(lái)的3個(gè)暑期，薩拉什么時(shí)候應(yīng)該折價(jià)買(mǎi)掉她的汽車(假設(shè)必要的話)可以使得她在大學(xué)四

16、年的開(kāi)車，買(mǎi)車，保養(yǎng)汽車的總費(fèi)用最小？ 最短路網(wǎng)絡(luò) 解：把這個(gè)問(wèn)題化為最短路問(wèn)題。節(jié)點(diǎn)表示如今(入學(xué))，節(jié)點(diǎn)，分別表示第一年年末，第二年年末，第三年年末，第四年年末。從一個(gè)節(jié)點(diǎn)到另外一個(gè)節(jié)點(diǎn)的弧表示在第一個(gè)節(jié)點(diǎn)這個(gè)時(shí)間買(mǎi)車，然后在第二個(gè)節(jié)點(diǎn)的那個(gè)時(shí)間把車折價(jià)賣(mài)掉的活動(dòng)最短路網(wǎng)絡(luò) 弧長(zhǎng)買(mǎi)車的價(jià)錢(qián)運(yùn)用和保養(yǎng)的費(fèi)用折價(jià)買(mǎi)出的價(jià)值。這樣該問(wèn)題就變?yōu)椋呵髲墓?jié)點(diǎn)到節(jié)點(diǎn)的最短路問(wèn)題.數(shù)學(xué)模型最短路問(wèn)題也可看成最小費(fèi)用流問(wèn)題的特例當(dāng)確定從任一節(jié)點(diǎn)i至另一節(jié)點(diǎn)j的最短路時(shí)，只需作以下假定：(1)當(dāng)網(wǎng)絡(luò)中恣意兩個(gè)節(jié)點(diǎn)之間存在銜接的弧時(shí)，弧上的費(fèi)用系數(shù)等于該弧的長(zhǎng)度；(2)作為起點(diǎn)的節(jié)點(diǎn)i為供應(yīng)節(jié)點(diǎn)且其凈流出量為1

17、，作為終點(diǎn)的節(jié)點(diǎn)j為需求節(jié)點(diǎn)且其凈流出量為-1，一切其他節(jié)點(diǎn)的凈流出量為零；(3) 總費(fèi)用等于從節(jié)點(diǎn)i起點(diǎn)到節(jié)點(diǎn)j終點(diǎn)所經(jīng)過(guò)的各條弧的長(zhǎng)度之和，目的函數(shù)是總費(fèi)用最小，也就是從節(jié)點(diǎn)i到節(jié)點(diǎn)j的途徑最短。運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題的普通提法是：設(shè)某種物資有 個(gè)產(chǎn)地各產(chǎn)地的產(chǎn)量是有 個(gè)銷地各銷地的銷量是假定從產(chǎn)地 到銷地運(yùn)輸單位物品的運(yùn)價(jià)是 ，問(wèn)怎樣調(diào)運(yùn)這些物品才干使總運(yùn)費(fèi)最小？運(yùn)輸問(wèn)題例：某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量及各產(chǎn)地運(yùn)往各銷地的單位運(yùn)費(fèi)如表所示。如何調(diào)運(yùn)，使總運(yùn)費(fèi)最少？銷地產(chǎn)地B1B2B3產(chǎn)量A1646200A2655300銷量150150

18、200500500單位運(yùn)費(fèi) x11 x12 x13 x21 x22 x23 運(yùn)輸問(wèn)題的假設(shè)需求假設(shè)： 每一個(gè)出發(fā)地產(chǎn)地都有一個(gè)固定的供應(yīng)量，一切的供應(yīng)量都必需配送到目的地銷地。與之相類似，每一個(gè)目的地都有一個(gè)固定的需求量，整個(gè)需求量都必需由出發(fā)地滿足。 本錢(qián)假設(shè)： 從任何一個(gè)出發(fā)地到任何一個(gè)目的地的貨物配送本錢(qián) 和所配送的數(shù)量成線性比例關(guān)系，因此這個(gè)本錢(qián)就等于配 送的單位本錢(qián)乘以所配送的數(shù)量。上例運(yùn)輸問(wèn)題的線性模型 min z=6 x11+4 x12+6 x13+6 x21+5 x22+5 x23 s.t. x11+ x12+ x13=200 x21+ x22+ x23=300 x11+ x2

19、1=150 x12+ x22=150 x13+ x23=200 xij0推行為普通： 銷地B1B2Bn供應(yīng)量 產(chǎn)地A1C11 x11C12x12 C1nx1na1AmCm1xm1Cm2xm2Cmn xmnam需求量b1b2bnai =bj(平衡)運(yùn)輸問(wèn)題的線性規(guī)劃模型Min z=S.t.定理：假設(shè)(平衡)運(yùn)輸問(wèn)題有可行解,那么證 :設(shè)運(yùn)輸問(wèn)題有可行解那么應(yīng)滿足約束從而有運(yùn)輸問(wèn)題的變形總供應(yīng)量總需求量的情形供求，LP模型中把約束xijai改為xijai即可供求，LP模型中把約束xijbj改為xijbj即可目的函數(shù)最大化的情形，如目的是追求利潤(rùn)或收入時(shí)，只需將目的函數(shù)改為max即可某些道路的運(yùn)輸才

20、干有一定限制的情形如從A2到B3遭到運(yùn)輸才干限制，最多只能運(yùn)送150時(shí)，只需在原LP模型上添加x23150即可運(yùn)輸問(wèn)題的計(jì)算機(jī)求解用線性規(guī)劃程序求解，輸出部分信息多，且變量和約束輸入較費(fèi)事。用運(yùn)輸問(wèn)題程序求解，只需輸入產(chǎn)地個(gè)數(shù)、銷地個(gè)數(shù)、各產(chǎn)地的產(chǎn)量、各銷地的銷量、各產(chǎn)地到各銷地的單位運(yùn)價(jià)。前例輸入后，得到的最優(yōu)運(yùn)輸方案為：銷地產(chǎn)地B1B2B3產(chǎn)量A1501500200A21000200300銷量150150200指派問(wèn)題有4個(gè)工人,要指派他們分別完成4項(xiàng)任務(wù),每人做各項(xiàng)任務(wù)所耗費(fèi)的時(shí)間如下表。要求1人只做1件事，如何指派使總本錢(qián)最少?人 工作B1B2B3B4工資24745325112A33956364313A43251254615模型用0-1變量表示“是非決策：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 s.t. x11+x12+x13+x14 =1 (A1只能干一件事) x21+x22+x