第二十六章 經(jīng)濟(jì)與金融中的優(yōu)化問(wèn)題

1、 第二十六章經(jīng)濟(jì)與金融中的優(yōu)化問(wèn)題本章主要介紹用 LINGO 軟件求解經(jīng)濟(jì)、金融和市場(chǎng)營(yíng)銷方面的幾個(gè)優(yōu)化問(wèn)題的案 例。 1 經(jīng)濟(jì)均衡問(wèn)題及其應(yīng)用 在市場(chǎng)經(jīng)濟(jì)活動(dòng)中，當(dāng)市場(chǎng)上某種產(chǎn)品的價(jià)格越高時(shí)，生產(chǎn)商越是愿意擴(kuò)大生產(chǎn)能力（供應(yīng)能力），提供更多的產(chǎn)品滿足市場(chǎng)需求；但市場(chǎng)價(jià)格太高時(shí)，消費(fèi)者的消費(fèi)欲望（需求能力）會(huì)下降。反之，當(dāng)市場(chǎng)上某種商品的價(jià)格越低時(shí)，消費(fèi)者的消費(fèi)欲望 （需求能力）會(huì)上升，但生產(chǎn)商的供應(yīng)能力會(huì)下降。如果生產(chǎn)商的供應(yīng)能力和消費(fèi)者的需求能力長(zhǎng)期不匹配，就會(huì)導(dǎo)致經(jīng)濟(jì)不穩(wěn)定。在完全市場(chǎng)競(jìng)爭(zhēng)的環(huán)境中，我們總是認(rèn)為經(jīng)濟(jì)活動(dòng)應(yīng)當(dāng)達(dá)到均衡（equilibrium），即生產(chǎn)和消費(fèi)（供應(yīng)能力和需求能

2、力）達(dá)到平衡，不再發(fā)生變化，這時(shí)該商品的價(jià)格就是市場(chǎng)的價(jià)格。 下面考慮兩個(gè)簡(jiǎn)單的單一市場(chǎng)及雙邊市場(chǎng)的具體實(shí)例，并介紹經(jīng)濟(jì)均衡思想在拍賣與投標(biāo)問(wèn)題、交通流分配問(wèn)題中的應(yīng)用案例。 1.1單一生產(chǎn)商、單一消費(fèi)者的情形 例 1 假設(shè)市場(chǎng)上只有一個(gè)生產(chǎn)商（記為甲）和一個(gè)消費(fèi)者（記為乙）。對(duì)某種商品，他們?cè)诓煌瑑r(jià)格下的供應(yīng)能力和需求能力如表 1 所示。舉例來(lái)說(shuō)，表中數(shù)據(jù)的含義是：當(dāng)單價(jià)低于 2 萬(wàn)元但大于或等于 1 萬(wàn)元時(shí)，甲愿意生產(chǎn) 2t 產(chǎn)品，乙愿意購(gòu)買 8t 產(chǎn)品；當(dāng)單價(jià)等于或低于 9 萬(wàn)元但大于 4.5 萬(wàn)元時(shí)，乙愿意購(gòu)買 2t 產(chǎn)品，甲愿意生產(chǎn) 8t產(chǎn)品；依次類推。那么的市場(chǎng)價(jià)格應(yīng)該是多少？ 表

3、 1 不同價(jià)格下的供應(yīng)能力和需求能力 生產(chǎn)商（甲）消費(fèi)者（乙）單價(jià)（萬(wàn)元/t）供應(yīng)能力（t）單價(jià)（萬(wàn)元/t）需求能力（t）1234246894.532.252468（1）問(wèn)題分析 仔細(xì)觀察一下表1 就可以看出來(lái)，這個(gè)具體問(wèn)題的解是一目了然的：價(jià)格顯 然應(yīng)該是 3 萬(wàn)元/t，因?yàn)榇藭r(shí)供需平衡（都是 6t）。為了能夠處理一般情況，下面通過(guò)建立優(yōu)化模型來(lái)解決這個(gè)問(wèn)題。 這個(gè)問(wèn)題給人的第一印象似乎沒(méi)有明確的目標(biāo)函數(shù)，不太像是一個(gè)優(yōu)化問(wèn)題。不過(guò)，我們可以換一個(gè)角度來(lái)想問(wèn)題：假設(shè)市場(chǎng)上還有一個(gè)虛擬的經(jīng)銷商，他是甲乙進(jìn)行交易的中介。那么，為了使自己獲得的利潤(rùn)最大，他將總是以可能的最低價(jià)格從甲購(gòu)買產(chǎn)品，再以可

4、能的最高價(jià)格賣給乙，直到進(jìn)一步的交易無(wú)利可圖為止。例如，最開始的 -348- 2t 產(chǎn)品他將會(huì)以 1 萬(wàn)元的單價(jià)從甲購(gòu)買，以 9 萬(wàn)元的單價(jià)賣給乙；接下來(lái)的 2t 產(chǎn)品他會(huì)以 2 萬(wàn)元的單價(jià)從甲購(gòu)買，再以 4.5 萬(wàn)元的單價(jià)賣給乙；再接下來(lái)的 2t 產(chǎn)品他只能以3 萬(wàn)元的單價(jià)從甲購(gòu)買，再以 3 萬(wàn)元的單價(jià)賣給乙（其實(shí)這次交易他已經(jīng)只是保本，但我們?nèi)匀患僭O(shè)這筆交易會(huì)發(fā)生，例如他為了使自己的營(yíng)業(yè)額盡量大）；最后，如果他繼續(xù)購(gòu)買甲的產(chǎn)品賣給乙，他一定會(huì)虧本，所以他肯定不會(huì)交易。因此，市場(chǎng)3 萬(wàn)元。根據(jù)這個(gè)想法，我們就可以建立這個(gè)問(wèn)題的線性規(guī)劃模型。 （2）模型建立 價(jià)格就是 決策變量：設(shè)甲以 1 萬(wàn)

5、元，2 萬(wàn)元，3 萬(wàn)元，4 萬(wàn)元的單價(jià)售出的產(chǎn)品數(shù)量（單位： t）分別是 x1 , x2 , x3 , x4 ，乙以 9 萬(wàn)元，4.5 萬(wàn)元，3 萬(wàn)元，2.25 萬(wàn)元的單價(jià)購(gòu)買的產(chǎn)品數(shù)量（單位：t）分別是 y1 , y2 , y3 , y4 。 目標(biāo)函數(shù)：就是虛擬經(jīng)銷商的總利潤(rùn)，即9 y1 + 4.5 y2 + 3y3 + 2.5 y4 - x1 - 2x2 - 3x3 - 4x4（1）約束條件：44 ix=yi供需平衡（2）i=1i=1供應(yīng)限制 xi 2 ，i = 1,2,3,4（3）消費(fèi)限制 yi 2 ，i = 1,2,3,4（4）非負(fù)限制 xi , yi 0 ，i = 1,2,3,4（3

6、）模型求解 式（1）（5）是一個(gè)線性規(guī)劃模型，可以用 LINGO 求解，對(duì)應(yīng)的 LINGO 程序如下： model:sets:gx/1.4/:c1,c2,x,y; endsetsdata:c1=1 2 3 4; c2=9,4.5,3,2.5;enddata max=sum(gx:c2*y-c1*x); sum(gx:x)=sum(gx:y);for(gx:bnd(0,x,2);bnd(0,y,2);-349-（5） end求解這個(gè)模型，得到如下解答：Global optimal solution foundatiteration:5Objectivevalue:21.00000Reduced

7、Cost 0.0000000.0000000.0000000.0000000.0000000.0000000.0000000.000000-2.000000-1.0000000.0000001.000000-6.000000-1.5000000.0000000.5000000VariableValue 1.0000002.0000003.0000004.0000009.0000004.5000003.0000002.5000002.0000002.0000000.0000000.0000002.0000002.0000000.0000000.000000C1(C1(C1(C1(C2(C2(C2

8、(C2(X(X(X(X(Y(Y(Y(Y(1)2)3)4)1)2)3)4)1)2)3)4)1)2)3)4)Row 12Slack or Surplus 21.000000.000000Dual Price 1.000000-3.000000（4）結(jié)果解釋 可以看出，最優(yōu)解為 x1 = x2 = y1 = y2 = 2 ， x3 = x4= y3 = y4 = 0 。但你肯定覺(jué) 得這還是沒(méi)有解決問(wèn)題，甚至認(rèn)為這個(gè)模型錯(cuò)了，因?yàn)檫@個(gè)解法沒(méi)有包括 3 萬(wàn)元單價(jià)的 2t 交易量。雖然容易驗(yàn)證 x1 = x2 = x3 = y1 = y2 = y3 = 0 ， x4 = y4 = 0 也是最優(yōu)解， 但在一

9、般情況下是難以保證一定求出這個(gè)解的。 那么如何才能確定價(jià)格呢？請(qǐng)仔細(xì)思考一下供需平衡約束（2）的對(duì)偶價(jià)格 （dual prices）的含義。對(duì)偶價(jià)格又稱價(jià)格，表示的是對(duì)應(yīng)約束的右端項(xiàng)的價(jià)值。供需平衡約束目前的右端項(xiàng)為 0，價(jià)格為3，意思就是說(shuō)如果右端項(xiàng)增加一個(gè)很小的量（即甲的供應(yīng)量增加一個(gè)很小的量），引起的經(jīng)銷商的損失就是這個(gè)小量的 3 倍。 可見(jiàn)，此時(shí)的銷售單價(jià)就是 3 萬(wàn)元，這就是（5）模型擴(kuò)展 一般地，可以假設(shè)甲的供應(yīng)能力隨價(jià)格的變化情況分為 K 段，即價(jià)格位于區(qū)間 -350- 價(jià)格。 pk , pk+1) 時(shí)，供應(yīng)量最多為 ck （ k = 1,2,L, K ； 0 p1 p2 L p

10、K +1 = ； 0 = c0 c1 c2 L L qL qL+1 = 0 ；0 = d0 d1 LdL ），我們把這個(gè)函數(shù)關(guān)系稱為需求函數(shù)（這里它也是一個(gè)階梯函數(shù)）。 設(shè)甲以 pk 的價(jià)格售出的產(chǎn)品數(shù)量為 xk （ k = 1,2,L, K ），乙以 q j 的價(jià)格購(gòu)入的產(chǎn) 品數(shù)量為 y j （ j = 1,2,L, L ）。記c0 = d0= 0 ，則可以建立如下所示的線性規(guī)劃模型： LK q j y j - pk xkmax（6）j=1k =1KLk =1k - y j = 0xs.t.（7）j=10 xk ck - ck -1 ，k = 1,2,L, K（8）0 y j d j - d

11、 j-1 ， j = 1,2,L, L1.2兩個(gè)生產(chǎn)商、兩個(gè)消費(fèi)者的情形 例 2假設(shè)市場(chǎng)上除了例 1 中的甲和乙外，還有另一個(gè)生產(chǎn)商（記為丙）和另一個(gè)消費(fèi)者（記為?。?，他們?cè)诓煌瑑r(jià)格下的供應(yīng)能力和需求能力如表 2 所示。此外，從甲 銷售到丁的每噸產(chǎn)品的運(yùn)輸成本是 1.5 萬(wàn)元，從丙銷售到乙的每噸產(chǎn)品的運(yùn)輸成本是 2（9）萬(wàn)元，而甲、乙之間沒(méi)有運(yùn)輸成本，丙、丁之間沒(méi)有運(yùn)輸成本。這時(shí)，市場(chǎng)的該是多少？甲和丙分別生產(chǎn)多少？乙和丁分別購(gòu)買多少？ 價(jià)格應(yīng)表 2 不同價(jià)格下的供應(yīng)能力和消費(fèi)能力 生產(chǎn)商（丙）生產(chǎn)商（丁）單價(jià)（萬(wàn)元/t）供應(yīng)能力（t）單價(jià)（萬(wàn)元/t）供應(yīng)能力（t）24681481215853

12、13610（1）問(wèn)題分析-351- 首先，我們看看為什么要考慮從甲銷售到丁的產(chǎn)品的運(yùn)輸成本和從丙銷售到乙的產(chǎn)品的運(yùn)輸成本。如果不考慮這些運(yùn)輸成本，我們就可以認(rèn)為甲乙丙丁處于同一個(gè)市場(chǎng)上，因此可以將兩個(gè)生產(chǎn)商（甲和丙）的供應(yīng)函數(shù)合并成一個(gè)供應(yīng)函數(shù)，合并后就可以認(rèn)為市場(chǎng)上仍然只有一個(gè)供應(yīng)商。類似地，乙和丁的需求函數(shù)也可以合并成一個(gè)需求函數(shù)，合并后就可以認(rèn)為市場(chǎng)上仍然只有一個(gè)消費(fèi)者。這樣，就回到了例 1 的情形。 也就是說(shuō)，考慮運(yùn)輸成本在經(jīng)濟(jì)學(xué)上的含義，應(yīng)當(dāng)是認(rèn)為甲乙是一個(gè)市場(chǎng)（地區(qū)或國(guó)家），而丙丁是另一個(gè)市場(chǎng)（地區(qū)或國(guó)家）。運(yùn)輸成本也可能還包括關(guān)稅等成本，由于這個(gè)成本的存在，兩個(gè)市場(chǎng)的價(jià)可能是不同

13、的。 仍然按照例 1 的思路，可以建立這個(gè)問(wèn)題的線性規(guī)劃模型。 （2）模型的建立和求解 設(shè)甲以 1，2，3，4（萬(wàn)元）的單價(jià)售出的產(chǎn)品數(shù)量（單位：t）分別是 A1, A2 , A3, A4 ，乙以 9，4.5，3，2.25（萬(wàn)元）的單價(jià)購(gòu)買的產(chǎn)品數(shù)量（單位：t）分別是 X1, X 2 , X 3 , X 4 ；丙以 2，4，6，8（萬(wàn)元）的單價(jià)售出的產(chǎn)品數(shù)量（單位：t）分別是 B1, B2 , B3 , B4 ，丁以 15，8，5，3（萬(wàn)元）的單價(jià)購(gòu)買的產(chǎn)品數(shù)量（單位：t）分別是Y1,Y2 ,Y3 ,Y4 。此外，假設(shè) AX 和 AY 分別是甲向乙和丁的供貨量， BX 和 BY 分別是丙向乙和

14、丁的供貨量。這些決策變量之間的關(guān)系參見(jiàn)示意圖 1。 圖 1 決策變量之間的關(guān)系 目標(biāo)函數(shù)仍然是虛擬經(jīng)銷商的總利潤(rùn)，約束條件仍然是四類（供需平衡、供應(yīng)限制、需求限制和非負(fù)限制），不過(guò)這時(shí)應(yīng)注意供需平衡約束應(yīng)該是包括圖 1 所示的決策變量 之間的關(guān)系： AX + AY = A1 + A2 + A3 + A4（10）BX + BY = B1 + B2 + B3 + B4（11）AX + BX = X1 + X 2 + X 3 + X 4（12）-352- AY + BY = Y1 + Y2 + Y3 + Y4此外的其它約束實(shí)際上只是一個(gè)簡(jiǎn)單的變量上界約束。下面直接給出 LINGO 程序： model

15、:sets: num1/1.4/:c1,c2,c3,c4,d1,d2,A,B,X,Y; num2/1,2/:AXY,BXY;endsets data:c1=9 4.5 3 2.25;c2=15 8 5 3;（13）c3=1 c4=2 d1=1d2=1243236434;8;4;4;enddatamax=sum(num1:c1*x+c2*y-c3*A-c4*B)-2*BXY(1)-1.5*AXY(2); sum(num1:A)-sum(num2:AXY)=0;sum(num1:B)-sum(num2:BXY)=0; AXY(1)+BXY(1)-sum(num1:X)=0;AXY(2)+BXY(2

16、)-sum(num1:Y)=0;for(num1:bnd(0,A,2);bnd(0,X,2);bnd(0,B,d1);bnd(0,Y,d2); end求解這個(gè)模型，得到如下解答： Global optimal solution found Objective value:Variableatiteration:044.00000Reduced Cost 0.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.000000Value 9.0000004.5000003.0000002.25

17、000015.000008.0000005.0000003.0000001.0000002.0000003.000000C1(C1(C1(C1(C2(C2(C2(C2(C3(C3(C3(1)2)3)4)1)2)3)4)1)2)3)-353- C3(C4(C4(C4(C4(D1(D1(D1(D1(D2(D2(D2(D2(A(A(A(A(B(B(B(B(X(X(X(X(Y(Y(Y(Y(4)1)2)3)4)1)2)3)4)1)2)3)4)1)2)3)4)1)2)3)4)1)2)3)4)1)2)3)4)1)4.0000002.0000004.0000006.0000008.0000001.000000

18、3.0000004.0000004.0000001.0000002.0000003.0000004.0000002.0000002.0000002.0000000.0000001.0000003.0000000.0000000.0000002.0000002.0000000.0000000.0000001.0000002.0000003.0000000.0000004.0000002.0000000.0000004.000000Slack or Surplus 44.000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0

19、000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.000000-2.000000-1.0000000.0000001.000000-2.500000-0.50000001.5000003.500000-6.000000-1.5000000.0000000.7500000-10.50000-3.500000-0.50000001.5000000.0000000.0000003.5000000.000000Dual Price 1.000000-3.000000-4.500000-3.000000-4.50

20、0000AXY( 2)1)AXY( 2)Row 12345-354- （3）結(jié)果解釋 可以看到，最優(yōu)解為 A1= A2 = A3 = X1 = X 2 = 2 ， B1 = 1， B2 = 3 ， Y1= 1， Y2 = 3 ，Y3 = 3 ，AX = BY = 4 ，AY = 2 ，A4 = B3 = B4 = X 3 = X 4 = Y4 = BX = 0 。 也就是說(shuō)，甲將向丁銷售2t產(chǎn)品，丙不會(huì)向乙銷售。 那么如何才能確定價(jià)格呢？與例1類似，約束（2）是針對(duì)生產(chǎn)商甲的供需平衡條件，目前的右端項(xiàng)為0，價(jià)格為3，意思就是說(shuō)如果右端項(xiàng)增加一個(gè)很少的量（即甲的供應(yīng)量增加一個(gè)很少的量），引起的經(jīng)

21、銷商的損失就是這個(gè)小量的3.5倍。可見(jiàn)，此時(shí)甲的銷售單價(jià)就是3萬(wàn)元，這就是甲面對(duì)的價(jià)格。 完全類似地，可以知道生產(chǎn)商丙面對(duì)的價(jià)格為4.5。自然地，乙面對(duì)的價(jià)格也是3，丁面對(duì)的價(jià)格也是4.5，因?yàn)榧滓椅挥谕粋€(gè)市場(chǎng)，而丙丁也位于同一個(gè)市場(chǎng)。這兩個(gè)市場(chǎng)的是非常合理的。 （4）模型擴(kuò)展 價(jià)之差正好等于從甲、乙到丙、丁的運(yùn)輸成本（1.5），這可以和1.1一樣，將上面的具體模型一般化，即考慮供應(yīng)函數(shù)和需求函數(shù)的分段數(shù)不是固定為4，而是任意有限正整數(shù)的情形。 很自然地，上面的方法很容易推廣到不僅僅是2個(gè)市場(chǎng)，而是任意有限個(gè)市場(chǎng)的情形。理論上看這當(dāng)然沒(méi)有什么難度，只是這時(shí)變量會(huì)更多，數(shù)學(xué)表達(dá)式變得更復(fù)雜一些

22、。 1.3拍賣與投標(biāo)問(wèn)題 例3假設(shè)一家拍賣行對(duì)委托的5類藝術(shù)品對(duì)外拍賣，采用在規(guī)定日期前投標(biāo)人提交投標(biāo)書的方式進(jìn)行，最后收到了來(lái)自4個(gè)投標(biāo)人的投標(biāo)書。每類項(xiàng)目的數(shù)量、投標(biāo)人對(duì)每個(gè)項(xiàng)目的投標(biāo)價(jià)格如表3中所示。例如，有3件第4類藝術(shù)品；對(duì)每件第4類藝術(shù)品， 投標(biāo)人1，2，3愿意出的最高價(jià)分別為6，1，3，2（貨幣單位，如萬(wàn)元）。此外，假設(shè)每個(gè)投標(biāo)人對(duì)每類藝術(shù)品最多只能購(gòu)買1件，并且每個(gè)投標(biāo)人購(gòu)買的藝術(shù)品的總數(shù)不能超過(guò)3件。那么，哪些藝術(shù)品能夠賣出去？賣給誰(shuí)？這個(gè)拍賣和投標(biāo)問(wèn)題中每類物品 的價(jià)應(yīng)該是多少？ 表3 拍賣與投標(biāo)信息（1）問(wèn)題分析 這個(gè)具體問(wèn)題在實(shí)際中可能可以通過(guò)對(duì)所有投標(biāo)的報(bào)價(jià)進(jìn)行排序來(lái)

23、解決，例如可以總是將藝術(shù)品優(yōu)先賣給出價(jià)最高的投標(biāo)人。但這種方法不太好確定每類藝術(shù)品的-355-招標(biāo)項(xiàng)目類型 12345招標(biāo)項(xiàng)目的數(shù)量 12334投標(biāo)價(jià)格 投標(biāo)人192863投標(biāo)人267915投標(biāo)人378634投標(biāo)人454321 價(jià)，所以我們這里還是借用前面兩個(gè)例子中的方法，即假設(shè)有一個(gè)中間商希望最大化自己的利潤(rùn)，從而建立這個(gè)問(wèn)題的線性規(guī)劃模型。 （2）問(wèn)題的一般提法和假設(shè) 先建立一般的模型，然后求解本例的具體問(wèn)題，設(shè)有 n 類物品需要拍賣，第 j 類物品的數(shù)量為 s j （ j = 1,2,L, n ）；有 m 個(gè)投標(biāo)者，投標(biāo)者i （ i = 1,2,Lm ）對(duì)第 j 類物品的投標(biāo)價(jià)格為bij

24、 （假設(shè)非負(fù)）。投標(biāo)者i 對(duì)每類物品最多購(gòu)買一件，且總件數(shù)不能超過(guò)ci 。我們的目標(biāo)之一是要確定第 j 類物品的件： 價(jià)格 p j ，它應(yīng)當(dāng)滿足下列假設(shè)條i） 成交的第 j 類物品的數(shù)量不超過(guò) s j （ j = 1,2,L, n ）； ii） 對(duì)第 j 類物品的報(bào)價(jià)低于 p j 的投標(biāo)人將不能獲得第 j 類物品； iii）如果成交的第 j 類物品的數(shù)量少于 s j （ j = 1,2,L, n ）可以認(rèn)為 p j = 0（除非拍賣方另外指定一個(gè)最低的保護(hù)價(jià)）； iv）對(duì)第 j 類物品的報(bào)價(jià)高于 p j 的投標(biāo)人有權(quán)獲得第 j 類物品，但如果他有權(quán)獲得的物品超過(guò)3件，那么我們假設(shè)他總是希望使自

25、己的滿意度最大（滿意度可以用他的報(bào)價(jià)與市場(chǎng)價(jià)之差來(lái)衡量）。 （3）優(yōu)化模型 用0 - 1變量 xij 表示是否分配一件第 j 類物品給投標(biāo)者i ，即 xij = 1表示分配，而= 0 表示不分配。目標(biāo)函數(shù)仍然是虛擬的中間商的總利潤(rùn)（認(rèn)為這些利潤(rùn)全部是拍 xij賣行的利潤(rùn)也可以），即mnbij xij（14）i=1 j=1除變量取值為0或1的約束外，問(wèn)題的約束條件主要是兩類：每類物品的數(shù)量限制 和每個(gè)投標(biāo)人所能分到的物品的數(shù)量限制，即 m ijx s j ，j = 1,2,L, n（15）i=1n ijx ci ，i = 1,2,L, m(16)j=1-356- 模型就是在約束（15）、（16）

26、下最大化目標(biāo)函數(shù)（14）。（4）模型求解 編寫的LINGO程序如下： MODEL:TITLE 拍賣與投標(biāo); SETS:AUCTION/1.5/: S;BIDDER/1.4/ : C;LINK(BIDDER,AUCTION): ENDSETSDATA:S=1 2 3 3 4;C=3 3 3 3; B=B, X; ENDDATAMAX=SUM(LINK: B*X); FOR(AUCTION(J):AUC_LIM SUM(BIDDER(I): X(I,J) S(J) ); FOR(BIDDER(I):BID_LIM SUM(AUCTION(J): X(I,J) C(I) ); FOR(LINK: B

27、ND(0,X,1);END需要指出的是，上面程序中DATA語(yǔ)句的數(shù)據(jù)表是直接從WORD文檔中復(fù)制（Ctrl+C）后粘貼（Ctrl+V）過(guò)來(lái)的，所以顯示格式繼續(xù)保持了WORD文檔的風(fēng)格。 （5）求解結(jié)果解釋 可以看到，最優(yōu)解為：投標(biāo)人1得到藝術(shù)品1，3，4，投標(biāo)人2，3都得到藝術(shù)品2，3，5，投標(biāo)人4得到藝術(shù)品4，5。結(jié)果，第4，5類藝術(shù)品各剩下1件沒(méi)有成交。 那么如何才能確定價(jià)格呢？與例1和例2類似，約束“AUC_LIM”是針對(duì)每類藝術(shù)品的數(shù)量限制的，對(duì)應(yīng)的價(jià)格就是其價(jià)格：即5類藝術(shù)品的價(jià)格分別是5，5，3，0，0。第4，5類藝術(shù)品有剩余，所以的。 價(jià)格為0，這是符合前面的假設(shè)可以指出的是：即

28、使上面模型中不要求 xij 為0 - 1變量（即只要求取01之間的實(shí)-357-92863679157863454321 數(shù)），由于這個(gè)問(wèn)題的特殊性，最優(yōu)解中 xij 也會(huì)要么取0，要么取1，不可能取01之 間的其它數(shù)，所以可以將LINGO模型中“BIN(X)”改為“BND(0,X,1)”，這個(gè)線性規(guī)劃的結(jié)果將與0 - 1整數(shù)線性規(guī)劃得到的結(jié)果相同。 最后，大學(xué)生的選課問(wèn)題與此是類似的，即把課程看成招標(biāo)（拍賣）項(xiàng)目，而把學(xué)生愿意付出的選課費(fèi)看成投標(biāo)。據(jù)說(shuō)國(guó)外有些大學(xué)的選課系統(tǒng)就是使用這個(gè)模型確定每門課程的 價(jià)格（選課費(fèi)用）的，而且取得了成功。 1.4 交通流均衡問(wèn)題 例4 某地有如圖2所示的一個(gè)

29、公路網(wǎng)，每天上班時(shí)間有6千輛小汽車要從居民區(qū) A 前往工作區(qū) D 。經(jīng)過(guò)長(zhǎng)期觀察，我們得到了圖中5條道路上每輛汽車的平均行駛時(shí)間和汽車流量之間的關(guān)系，如表4所示，那么，長(zhǎng)期來(lái)看，這些汽車將如何在每條道路上分 布？ 圖2 一個(gè)公路網(wǎng)示意圖表4 平均行駛時(shí)間和汽車流量之間的關(guān)系（1） 問(wèn)題分析 這個(gè)問(wèn)題看起來(lái)似乎與前面幾個(gè)例子完全不同，但實(shí)際上交通流與市場(chǎng)經(jīng)濟(jì)活動(dòng)類似，也存在著均衡。 我們可以想象有一個(gè)協(xié)調(diào)者，正如前面幾個(gè)例子中的所謂中間商可以理解為市場(chǎng)規(guī)律一樣，實(shí)際上這里的所謂協(xié)調(diào)者也可以認(rèn)為是交通流的規(guī)律。交通流的規(guī)律就是每輛汽車都將選擇使自己從 A 到 D 運(yùn)行時(shí)間最少的路線，其必然的結(jié)果是

30、無(wú)論走哪條路線從 A 到 D ，最終花費(fèi)的時(shí)間應(yīng)該是一樣的（否則，花費(fèi)時(shí)間較長(zhǎng)的那條線路上的部分汽車就會(huì)改變自己的路線，以縮短自己的行駛時(shí)間）。 也就是說(shuō)，長(zhǎng)期來(lái)看，這些汽車在每條道路上的分布將達(dá)到均衡狀態(tài)（所謂均衡， 這里的含義就是每輛汽車都不能僅僅通過(guò)自身獨(dú)自改變道路，節(jié)省其行駛時(shí)間）。在這種想法下，我們來(lái)建立線性規(guī)劃模型。 （2） 優(yōu)化模型 交通流的規(guī)律要求所有道路上的流量達(dá)到均衡，我們?nèi)匀活愃评?和例2來(lái)考慮問(wèn)題。如果車流量是一輛車一輛車增加的，那么在每條道路上車流量小于2時(shí)，車流量會(huì) -358- 道路 ABACBCBDCD行駛時(shí)間 （min） 流量 220521252202 流量 3

31、30531353303 流量 44054145440 有一個(gè)分布規(guī)律；當(dāng)某條道路上流量正好超過(guò)2時(shí)，新加入的一輛車需要選擇使自己堵 塞時(shí)間最短的道路。這就提示我們把同一條道路上的流量分布分解成不同性質(zhì)的三個(gè)部 分。也就是說(shuō)，我們用Y ( AB) 表示道路 AB 上的總的流量，并進(jìn)一步把它分解成三部分：i）道路 AB 上的流量不超過(guò)2時(shí)的流量，用 X (2, AB) 表示；ii）道路 AB 上的流量超過(guò)2但不超過(guò)3時(shí)，超過(guò)2的流量部分用 X (3, AB) 表示；iii）道路 AB 上的流量超過(guò)3但不超過(guò)4時(shí)，超過(guò)3的流量部分用 X (4, AB) 表示。依次類推，對(duì)道路 AC, BC, BD,

32、 CD 上同理可以定義類似的決策變量。因此，問(wèn)題 中總共有20個(gè)決策變量Y ( j) 和 X (i, j) （ i = 2,3,4 ， j = AB, AC, BC, BD, CD ）。問(wèn)題的目標(biāo)應(yīng)當(dāng)是使總的堵塞時(shí)間最小。用T (i, j) 表示流量 X (i, j) 對(duì)應(yīng)的堵塞時(shí)間（即表3中的數(shù)據(jù)，是對(duì)每輛車而言的），我們看看用 T (i, j) X (i, j) 作為i=2,3,4 j為道路 總堵塞時(shí)間是否合適。很容易理解：后面加入道路的車輛可能又會(huì)造成前面進(jìn)入道路的 車輛的進(jìn)一步堵塞，如流量為3時(shí)，原先流量為2的車輛實(shí)際上也只能按T (3, j) 的時(shí)間通過(guò)，而不是T (2, j) 。也

33、就是說(shuō)， T (i, j) X (i, j) 并不是總堵塞時(shí)間。但是i=2,3,4 j為道路 我們也可以發(fā)現(xiàn)，T (i, j) 關(guān)于i 是單調(diào)增加的，即不斷增加的車流只會(huì)使以前的堵塞加 劇而不 可 能使以 前 的堵塞 減 緩。所 以 ，關(guān)于 決 策變量 X (i, j) 而言 ， T (i, j) X (i, j) 與我們希望優(yōu)化的目標(biāo)的單調(diào)性是一致的。因此，可以用 i=2,3,4j為道路 T (i, j) X (i, j) 作為目標(biāo)函數(shù)進(jìn)行優(yōu)化。 i=2,3,4j為道路約束條件有三類： i） 每條道路上的總流量Y 等于該道路上的分流量 X 的和； ii） 道路交匯處 A, B, C, D（一

34、般稱為節(jié)點(diǎn)）的流量守恒（即進(jìn)入量等于流出iii）決策變量的上限限制，如 X (2, AB) 2 ， X (3, AB) 1， X (4, AB) 1 等。于是對(duì)應(yīng)的優(yōu)化模型很容易直接寫出（略）。 -359- （3）模型求解 編寫LINGO程序如下： MODEL:TITLE 交通流均衡; SETS:ROAD/AB,AC,BC,BD,CD/:Y; CAR/2,3,4/; LINK(CAR,ROAD): T, X;ENDSETS DATA:! 行駛時(shí)間(分鐘) ;T=20,52,12,52,20 30,53,13,53,3040,54,14,54,40;ENDDATAOBJ MUM(LINK: T*

35、X);! 目標(biāo)函數(shù);! 四個(gè)節(jié)點(diǎn)的流量守恒條件;NODE_A NODE_B NODE_CNODE_DY(INDEX(AB)+Y(INDEX(AC) = 6; Y(INDEX(AB)=Y(INDEX(BC)+Y(INDEX(BD);Y(INDEX(AC)+Y(INDEX(BC)=Y(INDEX(CD);Y(INDEX(BD)+Y(INDEX(CD)=6;! 每條道路上的總流量Y等于該道路上的分流量X的和; FOR( ROAD(I): ROAD_LIM SUM(CAR(J): X(J,I) = Y(I);! 每 條 道 路 的 分 流 量 X 的 上 下 界 設(shè) 定 ; FOR(LINK(I,J)

36、|I#EQ#1: BND(0,X(I,J),2) );FOR(LINK(I,J)|I#GT#1: BND(0,X(I,J),1) ); END可以指出的是，上面4個(gè)節(jié)點(diǎn)的流量守恒條件中，其實(shí)只有3個(gè)是獨(dú)立的（也就是說(shuō)，第4個(gè)條件總可以從其它3個(gè)方程推導(dǎo)出來(lái)），因此從中去掉任何一個(gè)都不會(huì)影響到計(jì)算結(jié)果。 （4）結(jié)果解釋 LINGO的運(yùn)行結(jié)果表明，均衡時(shí)道路 AB, AC, BC, BD, CD 的流量分別是4，2，2， 2，4（千輛）車。但是要注意，正如我們建立目標(biāo)函數(shù)時(shí)所討論過(guò)的，這時(shí)得到的目標(biāo)函數(shù)值452并不是真正的總運(yùn)行和堵塞時(shí)間，而是一個(gè)用來(lái)表示目標(biāo)函數(shù)趨勢(shì)的虛擬 的量，沒(méi)有太多實(shí)際物理

37、意義。事實(shí)上，可以求出這時(shí)的真正運(yùn)行時(shí)間是：每輛車通過(guò) AB, AC, BC, BD, CD 道路分別需要40，52，12，52，40（min），也就是在圖中三-360- 條路線 ABD, ACD, ABCD 上都需要92min，所以這也說(shuō)明交通流確實(shí)達(dá)到了均衡。于是，均衡時(shí)真正的總運(yùn)行時(shí)間應(yīng)該是6 92 = 552 （千輛車min）。 （5）模型討論 仔細(xì)想想就會(huì)發(fā)現(xiàn)，上面的解并不是最優(yōu)解，即均衡解并不一定是最優(yōu)的流量分配方案。為了求出使所有汽車的總運(yùn)行時(shí)間最小的交通流，應(yīng)該如何做呢？也就是說(shuō)，這相當(dāng)于假設(shè)有一個(gè)權(quán)威的機(jī)構(gòu)來(lái)統(tǒng)籌安排，最優(yōu)地分配這些交通流，而不是像求均衡解時(shí)那樣認(rèn)為各個(gè)個(gè)體（

38、每輛車）都可以自己選擇道路，自然達(dá)到平衡狀態(tài)。 為了進(jìn)行 統(tǒng)籌規(guī)劃 ，我們需 要把新增 的流量 X (i, j) （ i = 2,3,4 ， j = AB, AC, BC, BD, CD ）造成的實(shí)際堵塞時(shí)間計(jì)算出來(lái)（仍按每輛車計(jì)算），而不是像上面那樣不考慮對(duì)原有車流造成的堵塞效應(yīng)。以道路 AB 為例。 i） 當(dāng)流量為2千輛時(shí)，每輛車的通過(guò)時(shí)間為20min，所以總通過(guò)時(shí)間是40（千輛車min）； ii） 當(dāng)流量增加一個(gè)單位（本題中一個(gè)單位就是1千輛）達(dá)到3千輛時(shí)，每輛車的通過(guò)時(shí)間為30min，所以總通過(guò)時(shí)間是90（千輛車min）； iii） 當(dāng)流量再增加一個(gè)單位達(dá)到4千輛時(shí)，每輛車的通過(guò)時(shí)間為

39、40min，所以總通過(guò)時(shí)間是160（千輛車min）。 由此可見(jiàn)，流量超過(guò)2而不超過(guò)3時(shí)，單位流量的增加導(dǎo)致的總通過(guò)時(shí)間的變化為904050（千輛車min）；流量超過(guò)3而不超過(guò)4時(shí)，單位流量的增加導(dǎo)致的總通過(guò)時(shí)間的變化為1609070（千輛車min）。 類似地，對(duì)所有道路，都可以得到單位流量的增加導(dǎo)致總行駛時(shí)間的增量和汽車流量之間的關(guān)系（參加表5）。 表5 單位流量的增加導(dǎo)致總行駛時(shí)間的增量和汽車流量之間的關(guān)系用表5 中的總行駛時(shí)間的增量數(shù)據(jù)代替前面模型中的每輛車的行駛時(shí)間數(shù)據(jù)T (i, j) ，模型的其它部分完全不用變。重新求解LINGO模型，LINGO程序如下： MODEL:TITLE 交通流均衡; SETS:ROAD/AB,AC,BC,BD,CD/:Y; CAR/2,3,4/;-