網(wǎng)絡(luò)優(yōu)化例與lingo程序

1、網(wǎng)絡(luò)優(yōu)化例與計算LINGO程序例 裝配線平衡模型 一條裝配線含有一系列的工作站,在最終產(chǎn)品的加工過程中每個工作站執(zhí)行一種或幾種特定的任務(wù)。 裝配線周期是指所有工作站完成分配給它們各自的 任務(wù)所化費時間中的最大值。 平衡裝配線的目標(biāo)是為每個工作站分配加工任務(wù), 盡可能使每 個工作站執(zhí)行相同數(shù)量的任務(wù), 其最終標(biāo)準(zhǔn)是裝配線周期最短。 不適當(dāng)?shù)钠胶庋b配線將會產(chǎn) 生瓶頸有較少任務(wù)的工作站將被迫等待其前面分配了較多任務(wù)的工作站。問題會因為眾多任務(wù)間存在優(yōu)先關(guān)系而變得更復(fù)雜,任務(wù)的分配必須服從這種優(yōu)先關(guān) 系。這個模型的目標(biāo)是最小化裝配線周期。有2類約束: 要保證每件任務(wù)只能也必須分配至一個工作站來加工;

2、要保證滿足任務(wù)間的所有優(yōu)先關(guān)系。例 有11件任務(wù)(AK分配到4個工作站(14,任務(wù)的優(yōu)先次序如下圖。每件任 務(wù)所花費的時間如下表。任務(wù) A B C D E F G H I J K 時間 4511950151212121289(F(A(B(C(G(J(K(H(D(E(I計算程序:MODEL :!裝配線平衡模型;SETS :!任務(wù)集合,有一個完成時間屬性T;TASK/A B C D E F G H I J K/:T;!任務(wù)之間的優(yōu)先關(guān)系集合(A必須完成才能開始B,等等;PRED(TASK, TASK/A,B B,C C,F C,G F,J G,JJ,K D,E E,H E,I H,J I,J /;

3、! 工作站集合;STATION/1.4/;TXS(TASK, STATION:X;! X是派生集合TXS的一個屬性。如果X(I,K=1,則表示第I個任務(wù)指派給第K個工作站完成;ENDSETSDATA :!任務(wù)A B C D E F G H I J K的完成時間估計如下;T =4511950151212121289;ENDDATA! 當(dāng)任務(wù)超過15個時,模型的求解將變得很慢;!每一個作業(yè)必須指派到一個工作站,即滿足約束;FOR(TASK(I:SUM(STATION(K:X(I, K =1;!對于每一個存在優(yōu)先關(guān)系的作業(yè)對來說,前者對應(yīng)的工作站I必須小于后者對應(yīng)的工作站J,即滿足約束;FOR(PR

4、ED(I, J:SUM(STATION(K:K *X(J, K -K *X(I, K >=0; !對于每一個工作站來說,其花費時間必須不大于裝配線周期;FOR(STATION(K:SUM(TXS(I, K:T(I *X(I, K <=CYCTIME;!目標(biāo)函數(shù)是最小化轉(zhuǎn)配線周期;MIN =CYCTIME;!指定X(I,J為0/1變量;FOR(TXS:BIN(X;END計算的部分結(jié)果為Global optimal solution found at iteration:1255Objective value:50.00000Variable Value Reduced CostCYC

5、TIME 50.000000.000000X(A, 1 1.0000000.000000X(A, 2 0.0000000.000000X(A, 3 0.00000045.00000X(A, 4 0.0000000.000000X(B, 1 0.0000000.000000X(B, 2 0.0000000.000000X(B, 3 1.00000011.00000X(B, 4 0.0000000.000000X(C, 1 0.0000000.000000X(C, 2 0.0000000.000000X(C, 3 0.0000009.000000X(C, 4 1.0000000.000000X(D

6、, 1 0.0000000.000000X(D, 2 1.0000000.000000X(D, 3 0.00000050.00000X(D, 4 0.0000000.000000X(E, 1 0.0000000.000000X(E, 2 0.0000000.000000X(E, 3 1.00000015.00000X(E, 4 0.0000000.000000X(F, 1 0.0000000.000000X(F, 2 0.0000000.000000X(F, 3 0.00000012.00000X(F, 4 1.0000000.000000X(G, 1 0.0000000.000000X(G,

7、 2 0.0000000.000000X(G, 3 0.00000012.00000X(G, 4 1.0000000.000000X(H, 1 0.0000000.000000X(H, 2 0.0000000.00000045X(H, 3 1.00000012.00000X(H, 4 0.0000000.000000X(I, 1 0.0000000.000000X(I, 2 0.0000000.000000X(I, 3 1.00000012.00000X(I, 4 0.0000000.000000X(J, 1 0.0000000.000000X(J, 2 0.0000000.000000X(J

8、, 3 0.0000008.000000X(J, 4 1.0000000.000000X(K, 1 0.0000000.000000X(K, 2 0.0000000.000000X(K, 3 0.0000009.000000X(K, 4 1.0000000.000000例 旅行售貨員問題(又稱貨郎擔(dān)問題,Traveling Salesman Problem有一個推銷員,從城市1出發(fā),要遍訪城市2,3,n 各一次,最后返回城市1。已 知從城市i到j(luò) 的旅費為 ij c ,問他應(yīng)按怎樣的次序訪問這些城市,使得總旅費最少? 可以用多種方法把TSP表示成整數(shù)規(guī)劃模型。這里介紹的一種建立模型的方法,是把

9、該 問題的每個解(不一定是最優(yōu)的看作是一次“巡回”。 在下述意義下,引入一些0-1整數(shù)變量:=其他情況 且 到 巡回路線是從 , 0, 1j i , j i ij x 其目標(biāo)只是使=nj i ij ijx c1, 為最小。這里有兩個明顯的必須滿足的條件:訪問城市 i 后必須要有一個即將訪問的確切城市;訪問城市 j 前必須要有一個剛剛訪問 過的確切城市。用下面的兩組約束分別實現(xiàn)上面的兩個條件。ni xnj ij, , 2, 111 =nj xni ij, , 2, 111=到此我們得到了一個模型,它是一個指派問題的整數(shù)規(guī)劃模型。但以上兩個條件對于TSP 來說并不充分,僅僅是必要條件。例如:123

10、1464以上兩個條件都滿足,但它顯然不是TSP的解,它存在兩個子巡回。這里,我們將敘述一種在原模型上附加充分的約束條件以避免產(chǎn)生子巡回的方法。把額 外變量 u i (i =2, 3, , n 附加到問題中?？砂堰@些變量看作是連續(xù)的(最然這些變量在最 優(yōu)解中取普通的整數(shù)值?，F(xiàn)在附加下面形式的約束條件nj i n nx u u ij j i -+-2,1為了證明該約束條件有預(yù)期的效果,必須證明:(1任何含子巡回的路線都不滿足該約 束條件;(2全部巡回都滿足該約束條件。(證明略 這樣我們把 TSP 轉(zhuǎn)化成了一個混合整數(shù)線性規(guī)劃問題。=-+-=n i u n j i x n j i n nx u u

11、n i x n j x t s x c z i ij ij j i n j ij n i ij nj i j i ijij , , 2, 0, , 2, 1, 1, 02, 1, , 2, 11, , 2, 11. min 111, 顯然,當(dāng)城市個數(shù)較大(大于30時,該混合整數(shù)線性規(guī)劃問題的規(guī)模會很大,從而給求解帶來很大問題。TSP 已被證明是NP 難問題,目前還沒有發(fā)現(xiàn)多項式時間的算法。對 于小規(guī)模問題,我們求解這個混合整數(shù)線性規(guī)劃問題的方式還是有效的。TSP 是一個重要的組合優(yōu)化問題,除了有直觀的應(yīng)用外,許多其它看似無聯(lián)系的優(yōu)化問 題也可轉(zhuǎn)化為 TSP。例如:n=5時 LINGO 程序:!

12、 旅行售貨員問題 ; model :sets :city /1. 5/:u; link(city, city:dist, ! 距離矩陣 ; x; endsetsn =size(city;data :! 距離矩陣,它并不需要是對稱的 ;dist =qrand(1;! 隨機產(chǎn)生,這里可改為你要解決的問題的數(shù)據(jù) ; enddata! 目標(biāo)函數(shù) ;min =sum(link:dist *x;FOR(city(K:! 進入城市 K;sum(city(I|I #ne#K:x(I, K =1;! 離開城市 K;sum(city(J|J #ne#K:x(K, J =1;! 保證不出現(xiàn)子圈 ;for(city(

13、I|I#gt#1:for(city(J|J#gt#1#and#I #ne#J:u(I-u(J+n*x(I,J<=n-1;! 限制 u 的范圍以加速模型的求解,保證所加限制并不排除掉 TSP 問題的最優(yōu)解 ; for(city(I|I #gt#1:u(I<=n-2;! 定義 X 為 01變量 ;for(link:bin(x;end計算的部分結(jié)果為:Global optimal solution found at iteration:77 Objective value:1.692489Variable Value Reduced CostN 5.0000000.000000U(1 0

14、.0000000.000000U(2 1.0000000.000000U(3 3.0000000.000000U(4 2.0000000.000000U(5 0.0000000.000000DIST(1, 1 0.44917740.000000DIST(1, 2 0.27245060.000000DIST(1, 3 0.12404300.000000DIST(1, 4 0.92468480.000000DIST(1, 5 0.40217060.000000DIST(2, 1 0.70914690.000000DIST(2, 2 0.16851990.00000048DIST(2, 3 0.89

15、896460.000000DIST(2, 4 0.25027470.000000DIST(2, 5 0.89475710.000000DIST(3, 1 0.8648940E-010.000000DIST(3, 2 0.60205910.000000DIST(3, 3 0.33808840.000000DIST(3, 4 0.68131640.000000DIST(3, 5 0.22362710.000000DIST(4, 1 0.97629870.000000DIST(4, 2 0.88663430.000000DIST( 4, 3 0.7139008 0.000000 DIST( 4, 4

16、 0.2288770 0.000000 DIST( 4, 5 0.7134250 0.000000 DIST( 5, 1 0.8524679 0.000000 DIST( 5, 2 0.2396538 0.000000 DIST( 5, 3 0.5735525 0.000000 DIST( 5, 4 0.1403314 0.000000 DIST( 5, 5 0.6919708 0.000000 X( 1, 1 0.000000 0.4491774 X( 1, 2 0.000000 0.2724506 X( 1, 3 0.000000 0.1240430 X( 1, 4 0.000000 0.

17、9246848 X( 1, 5 1.000000 0.4021706 X( 2, 1 0.000000 0.7091469 X( 2, 2 0.000000 0.1685199 X( 2, 3 0.000000 0.8989646 X( 2, 4 1.000000 0.2502747 X( 2, 5 0.000000 0.8947571 X( 3, 2 0.000000 0.6020591 X( 3, 3 0.000000 0.3380884 X( 3, 4 0.000000 0.6813164 X( 3, 5 0.000000 0.2236271 X( 4, 1 0.000000 0.976

18、2987 X( 4, 2 0.000000 0.8866343 X( 4, 3 1.000000 0.7139008 X( 4, 4 0.000000 0.2288770 X( 4, 5 0.000000 0.7134250 X( 5, 1 0.000000 0.8524679 X( 5, 2 1.000000 0.2396538 X( 5, 3 0.000000 0.5735525 X( 5, 4 0.000000 0.1403314 X( 5, 5 0.000000 0.6919708 X( 3, 1 1.000000 0.8648940E-01 例 有4 名同學(xué)到一家公司參加三個階段的面

19、試：公司要求每個同學(xué)都必須首先找公司秘書 初試，然后到部門主管處復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊（即在任何一個階 段4 名同學(xué)的順序是一樣的）。由于4 名同學(xué)的專業(yè)背景不同，所以每人在三個階段的面試 時間也不同，如下表所示（單位：分鐘）： 秘書初試 同學(xué)甲 同學(xué)乙 同學(xué)丙 13 10 20 主管復(fù)試 15 20 16 經(jīng)理面試 20 18 10 同學(xué)丁 8 10 15 這4 名同學(xué)約定他們?nèi)棵嬖囃暌院笠黄痣x開公司。 假定現(xiàn)在時間是早晨8:00， 問他們最早 何時能離開公司?（建立規(guī)劃模型求解） 本問題是一個排列排序問題。 對于階段數(shù)不小于3 的問題沒有有效算法， 也就是說對于 學(xué)生

20、數(shù)稍多一點兒（比如20）的情況是無法精確求解的。為此人們找到了很多近似算法。 這里我們建立的規(guī)劃模型可以實現(xiàn)該問題的精確求解， 但你會看到它的變量和約束是學(xué)生數(shù) 的平方。因此，當(dāng)學(xué)生數(shù)稍多一點兒規(guī)劃模型的規(guī)模經(jīng)很大，求解會花費很長時間。 LINGO 程序 !三階段面試模型; model: sets: students; !學(xué)生集三階段面試模型; phases; !階段集; sp(students,phases:t,x; endsets data: ss(students,students | &1 #LT# &2:y; students = s1.s4; phases = p1

21、.p3; t= 13 15 20 10 20 18 20 16 10 8 10 15; enddata ns=size(students; !學(xué)生數(shù); np=size(phases; !階段數(shù); !單個學(xué)生面試時間先后次序的約束; for(sp(I,J | J #LT# np: x(I,J+t(I,J<=x(I,J+1 ; !學(xué)生間的面試先后次序保持不變的約束; for(ss(I,K: for(phases(J: x(I,J+t(I,J-x(K,J<=200*y(I,K; x(K,J+t(K,J-x(I,J<=200*(1-y(I,K; ; !目標(biāo)函數(shù); min=TMAX; for(students(I: ; x(I,3+t(I,3<=TMAX !把Y 定義0-1變量;