數(shù)學(xué)建模-線性規(guī)劃

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第八章 線性規(guī)劃8.1 引言 有一個(gè)關(guān)于偉大數(shù)學(xué)家歐拉（Euler）的故事是這樣說的，因?yàn)闆]有足夠的籬笆，小歐拉的父親為修建羊圈而發(fā)愁，小歐拉問父親：為什么不將羊圈建成方的，這樣不就能用更少的籬笆圍成更大的面積嗎？這個(gè)三百年前出自一個(gè)小兒之口的問題道出了一大類的科學(xué)問題：最優(yōu)化問題。這類問題是如此的普遍，它遍及宇宙的每一個(gè)角落，也滲透在人們的每一根神經(jīng)之中。 這類問題的特點(diǎn)是有一個(gè)目標(biāo)，這個(gè)目標(biāo)，在一定的條件下可以用函數(shù)表達(dá)出來，比如上面的面積是矩形的長(zhǎng)和寬的函數(shù)。我們的目的就是使目標(biāo)函數(shù)達(dá)到最大或者最小。但是面積并不能無限的大，因?yàn)槭艿交h笆長(zhǎng)度（周長(zhǎng)）的限制。也就是

2、說最大化的同時(shí)要受到約束條件的限制。 通過分析上面的例子可以發(fā)現(xiàn)，描述最優(yōu)化問題有三個(gè)基本要素，即決策變量、目標(biāo)函數(shù)和約束條件。 決策變量：確定問題目標(biāo)值大小的眾多因素中，其中決策者可以控制的量稱為決策變量。決策變量的取值確定了系統(tǒng)的最終性能，也是決策者采用決策的依據(jù)。應(yīng)該注意，在系統(tǒng)中還有一些量，它們不能由決策者所控制，而是由系統(tǒng)所處的環(huán)境所決定，我們稱之為參數(shù)。在一些問題的建模過程中，確定變量經(jīng)常是第一步的同時(shí)也可能是最困難的工作。 目標(biāo)函數(shù)：它代表決策者希望對(duì)其進(jìn)行優(yōu)化的那個(gè)指標(biāo)。目標(biāo)函數(shù)是決策變量的函數(shù)。對(duì)應(yīng)決策者而言，對(duì)其有利的程度必須定量的測(cè)度, 在商業(yè)應(yīng)用中，有效性的測(cè)度經(jīng)常是利

3、潤(rùn)或者成本, 但對(duì)于政府，更經(jīng)常的使用投入產(chǎn)出率來測(cè)度。表示有效性測(cè)度的經(jīng)常稱為目標(biāo)函數(shù)。大部分的模型中，確實(shí)目標(biāo)函數(shù)比較簡(jiǎn)單，因此，我們建模是往往從這里尋找思路。 約束條件：它們是決策變量在現(xiàn)實(shí)世界中所受到的限制，約束條件決定了決策變量和參數(shù)之間的關(guān)系。約束集界定決策變量可以取某些值而不能取其他的值。在實(shí)際問題中，決策變量帶有約束是普遍的。有時(shí)一些問題的約束可能非常復(fù)雜。 一般地，建立最優(yōu)化模型遵循如下的過程：（1）明確問題的目標(biāo)，找到確定目標(biāo)性能的主要因素，從而確定決策變量；（2）分析上面給出的決策變量和目標(biāo)之間的函數(shù)關(guān)系，確定目標(biāo)函數(shù)；（3）確定決策變量和參數(shù)之間的關(guān)系和限制，確定約束條

4、件。8.2 引例 線性規(guī)劃在實(shí)際生產(chǎn)和生活中有非常廣泛的應(yīng)用，比如生產(chǎn)計(jì)劃問題，交通運(yùn)輸問題，管理調(diào)度問題等等，下面以三個(gè)例子作為線性規(guī)劃問題的典型例子加以說明。例1：（生產(chǎn)計(jì)劃問題）某工廠生產(chǎn)甲乙丙三種產(chǎn)品，單位產(chǎn)品分別可為工廠帶來4元、3元和2元的利潤(rùn)。同時(shí)生產(chǎn)這些產(chǎn)品的過程中，需要耗費(fèi)原材料和人力：?jiǎn)挝划a(chǎn)品耗費(fèi)的原材料A為2、3和1個(gè)單位，而可用于生產(chǎn)的原材料A總數(shù)為34個(gè)單位；同時(shí)消耗原材料B均為1個(gè)單位，而可用于生產(chǎn)的原材料B總數(shù)為20個(gè)單位，而且材料B不能保存只能用完；單位產(chǎn)品需要的工時(shí)數(shù)為3、2和1.5，而可供使用的工時(shí)數(shù)不超過36；。問如何組織生產(chǎn)，可以獲得最大的利潤(rùn)？（選擇原

5、因：題目簡(jiǎn)單，適合作為入門級(jí)的例子，同時(shí)生產(chǎn)計(jì)劃問題是線性規(guī)劃問題最常見的例子之一）分析：按照題目，容易知道，問題的目標(biāo)非常明確，就是利潤(rùn)最大，而和決定利潤(rùn)的因素在單個(gè)產(chǎn)品利潤(rùn)給定的情形下，決定總利潤(rùn)的因素?zé)o非是生產(chǎn)的數(shù)量，更確切的說就是甲乙丙三種產(chǎn)品的生產(chǎn)數(shù)量，因此可以確定規(guī)劃問題的決策變量是三種產(chǎn)品的生產(chǎn)數(shù)量，分別記為x1, x2和x3。在此基礎(chǔ)上，我們能容易的寫出目標(biāo)函數(shù)為利潤(rùn)P = 4 x1 + 3 x2 + 2 x3。再看看這些決策變量有沒有受到什么限制，根據(jù)題意，生產(chǎn)產(chǎn)品需要消耗原材料和工時(shí)，而這兩種資源都有一定的限制，當(dāng)生產(chǎn)x1, x2和x3個(gè)甲乙丙產(chǎn)品時(shí)，耗費(fèi)的原材料A為2 x

6、1 + 3 x2 + x3，由于可用于生產(chǎn)的原材料A為34，所以有約束2 x1 + 3 x2 + x3 34.對(duì)于原材料B，有約束x1 + x2 + x3 = 20.同樣地，生產(chǎn)過程中受到工時(shí)的限制，有3 x1 + 2 x2 + 1.5 x3 36.最后，注意到生產(chǎn)的產(chǎn)品數(shù)量不可能是負(fù)數(shù)，也就是x1, x2和x3是非負(fù)的，因此我們得到如下的規(guī)劃問題： （8.1）注意：這個(gè)分析過程很好的給出了建立模型的思維過程，即明確目標(biāo)，尋求決定目標(biāo)的因素，確定問題的決策變量，使用決策變量寫成目標(biāo)函數(shù)，然后分析這些決策變量受到什么樣的約束，逐個(gè)的給出決策變量受到的約束并用或不等式的方式表達(dá)出來。例2. （運(yùn)輸

7、問題）永輝超市有限公司在重慶地區(qū)有n家超市，這些超市的蔬菜主要來自m家蔬菜生產(chǎn)基地。第j家超市每天蔬菜的銷量為aj頓（j = 1, 2, ., n），第i家生產(chǎn)基地每天的產(chǎn)量為bi（i = 1, 2, ., m）。假設(shè)從第i家基地到第j家超市的距離為cij公里（i = 1, 2, ., m，j = 1, 2, ., n）。為簡(jiǎn)單起見，假定每天基地生產(chǎn)蔬菜的總量和超市需求的總量相等，即。問如何制定調(diào)運(yùn)方案，既可以滿足供需關(guān)系，又使運(yùn)輸?shù)念D公里數(shù)達(dá)到最少。（選擇原因：運(yùn)輸問題是線性規(guī)劃最常見的例子之一，也是可以擴(kuò)充的任何使用的例子的基礎(chǔ)，實(shí)際上這個(gè)例子中可以向很多方向擴(kuò)展，比如蔬菜的種類有多種多樣

8、，蔬菜基地可以具有短暫的儲(chǔ)存功能，超市也有一定的儲(chǔ)存功能，但是蔬菜可能有較大的損壞，此外，超市的銷售量也可能是隨機(jī)的，所以，容易擴(kuò)展到各種各樣的和運(yùn)輸相關(guān)的問題）分析：同樣地，我們明確我們的目標(biāo)是運(yùn)輸?shù)膰嵐铮ㄓ袝r(shí)也稱為運(yùn)費(fèi)）最小，這個(gè)值和蔬菜基地和超市之間的距離和運(yùn)輸?shù)牧抗餐瑳Q定，其中蔬菜基地和超市的距離是確定的常量，而不同基地和超市之間的運(yùn)輸量是可控的量并且決定了最終的運(yùn)費(fèi)，因此應(yīng)該選擇基地i到超市j的運(yùn)量xij作為決策變量（i = 1, 2, ., m， j = 1, 2, ., n）。這樣可以寫出運(yùn)輸?shù)膰嵐飻?shù).這些運(yùn)輸量顯然的受到一些限制，比如從一個(gè)產(chǎn)地運(yùn)向各個(gè)超市的運(yùn)量之和不能超過

9、該基地的產(chǎn)量，這類約束我們稱為產(chǎn)地約束，于是有.此外，對(duì)于任何一家超市，來自與不同產(chǎn)地的蔬菜總量應(yīng)該能夠滿足該超市的銷售量，因此又有如下的約束.同時(shí)，注意到所有的運(yùn)輸量是非負(fù)的變量，于是可以得到下面的線性規(guī)劃模型 （8.2）（關(guān)于問題的擴(kuò)充：可以在練習(xí)題里面體現(xiàn)，比如兩種貨物，又比如一些基地和超市的對(duì)接限制等，又比如怎么確定如果一家基地最多只能為幾家超市供貨等。）例3. （人員組織安排）隨著電話銀行等業(yè)務(wù)的開展，香港匯豐銀行在美國(guó)的服務(wù)中心需要雇傭一批話務(wù)員處理相關(guān)業(yè)務(wù)。通過對(duì)以往數(shù)據(jù)的分析，發(fā)現(xiàn)一天中不同的時(shí)段打進(jìn)電話的數(shù)量是不同的，通過估計(jì)從上午9時(shí)到下午5時(shí)每個(gè)小時(shí)的話務(wù)員需要量分別是1

10、0，12，14，16，18，17，15和10人。話務(wù)員可以使用全職雇員和臨時(shí)雇員，全職雇員的薪水是每天120美元，臨時(shí)雇員是每小時(shí)10美元。全職雇員從上午9時(shí)工作到下午5時(shí)，但中間有一個(gè)小時(shí)的休息時(shí)間。一般地，一半的雇員在11時(shí)開始休息，一半的雇員在12時(shí)休息。臨時(shí)雇員每次是工作連續(xù)的四小時(shí)，中間沒有休息時(shí)間。公司可用的全職雇員不超過12人。同時(shí)要求一半以上的工作由全職雇員完成。試給出一個(gè)人員的雇傭方案，使得公司所支付的薪水總數(shù)最少。（選擇原因：難度適中的題目，處理中決策變量的選擇需要適當(dāng)?shù)姆治?，此外全職雇員占一半的條件也是需要處理的。此外，例子的可擴(kuò)充性也是選擇的重要原因，比如可以僅僅給出每

11、天打入電話的記錄，估計(jì)需要的話務(wù)員的數(shù)量。）分析：雇傭的人員的多少?zèng)Q定了公司所支付的薪水?dāng)?shù)量，本題的目標(biāo)是設(shè)計(jì)適當(dāng)?shù)墓蛡蚍桨?，使得所支付的薪水最少。決定這個(gè)目標(biāo)值的量就是兩類雇員的數(shù)量，全職雇員的數(shù)量假設(shè)為x1，而臨時(shí)雇員的數(shù)量為x2，目標(biāo)函數(shù)可以容易的表達(dá)出來，即為120 x1 + 10 x2。當(dāng)進(jìn)一步考慮這些變量受到的約束時(shí)，我們發(fā)現(xiàn)有很大的困難，主要的原因就是臨時(shí)雇員什么時(shí)候開始工作不能確定，而這個(gè)不能確定時(shí)，在不同時(shí)段人員需求的要求就不能滿足。由于臨時(shí)雇員時(shí)工作連續(xù)的四個(gè)小時(shí)，如果我們假定從9點(diǎn)開始上班的臨時(shí)雇員數(shù)為x2，10點(diǎn)開始上班的臨時(shí)雇員數(shù)為x3，11點(diǎn)開始上班的臨時(shí)雇員數(shù)為x

12、4，12點(diǎn)開始上班的臨時(shí)雇員數(shù)為x5，下午1點(diǎn)開始上班的臨時(shí)雇員數(shù)為x6，這時(shí)目標(biāo)函數(shù)仍然能簡(jiǎn)單的表達(dá)出來，為.每一個(gè)時(shí)段的人數(shù)為：在9-10時(shí)人數(shù)：x1 + x2; 在10-11時(shí)人數(shù)：x1 + x2 + x3; 在11-12時(shí)人數(shù)：x1/2 + x2 + x3+ x4; 在12-1時(shí)人數(shù)：x1/2 + x2 + x3+ x4 + x5; 在1-2時(shí)人數(shù)：x1 + x3+ x4 + x5 + x6; 在2-3時(shí)人數(shù)：x1 + x4 + x5 + x6; 在3-4時(shí)人數(shù)：x1 + x5 + x6; 在4-5時(shí)人數(shù)：x1 + x6。因此關(guān)于滿足不同時(shí)段人數(shù)要求的約束可以表達(dá)為還有一個(gè)約束是全職雇

13、員人數(shù)不超過12人，也就是x1 12。對(duì)于全職雇員完成一半以上的工作的約束，注意到總工作量為112人小時(shí)，而全職雇員平均工作時(shí)間為7小時(shí)，所以有x1 8.當(dāng)然，各種雇員的人數(shù)是非負(fù)的，因此還有一個(gè)非負(fù)約束。綜上所述，我們可以得到本問題的線性規(guī)劃模型如下： （8.3）8.3 線性規(guī)劃模型及求解 在上一節(jié)中，我們通過幾個(gè)例子說明線性規(guī)劃模型的特點(diǎn)和建模過程，也清楚了規(guī)劃問題的基本結(jié)構(gòu)：線性規(guī)劃具有一個(gè)目標(biāo)函數(shù)，可以是尋找最大值（比如例題1）也可能是尋求最小值（比如例題2和3）；其次，問題包括若干個(gè)約束條件。這些目標(biāo)函數(shù)和約束條件都是關(guān)于決策變量的線性函數(shù)，約束中可能還包括一類特殊的約束，比如三個(gè)例

14、子中的最后一個(gè)約束，還有(8.3)的倒數(shù)第二個(gè)約束，稱為決策變量的下界或上界。這類問題統(tǒng)稱為線性規(guī)劃問題。如果使用矩陣表達(dá)這些例子，比如例1，只要記，。則規(guī)劃問題（8.1）可以表達(dá)為 （8.4）對(duì)于一般的線性規(guī)劃問題，有如下的形式： （8.5）其中Aeq和Beq是對(duì)應(yīng)于線性等式約束的矩陣和右端向量，lb和ub是向量的下界和上界向量。 解決上述問題的最常用的算法稱為單純型法（simplex algorithm），該算法在1947年由美國(guó)數(shù)學(xué)家Danzig提出，被稱為二十世紀(jì)最著名的十大算法之一。其基本思想如下：?jiǎn)栴}（8.5）的所有滿足約束條件的點(diǎn)構(gòu)成一個(gè)集合，稱為問題的可行集。由于約束是一系列的

15、線性等式和不等式構(gòu)成，在幾何上形成空間的一個(gè)凸的超立方體，問題的最優(yōu)解如果存在，則一定可以在立方體的頂點(diǎn)取得。求解的過程是從立方體的一個(gè)頂點(diǎn)開始（稱為初始點(diǎn)），在剩余的頂點(diǎn)中找目標(biāo)函數(shù)值減小的頂點(diǎn)，這樣就完成一次迭代，一直的重復(fù)這個(gè)過程直到不能目標(biāo)值不能減小為止。關(guān)于算法的理論和具體的步驟，有興趣的同學(xué)可以參考線性規(guī)劃的相關(guān)著作。 能解決線性規(guī)劃問題的軟件有多種，本書僅對(duì)兩種非常常用的軟件加以介紹，其中一個(gè)是Matlab，另一個(gè)是Lingo。本節(jié)主要介紹Matlab軟件解決線性規(guī)劃。Matlab使用Linprog.m程序求解線性規(guī)劃問題（8.5）的解。下面是Matlab軟件的幫助文件對(duì)于該程序

16、的說明： linprog min cTx s.t. Axb Aeqx beq lb x ub Solve a linear programming problem where c, x, b, beq, lb, and ub are vectors and A and Aeq are matrices. 調(diào)用格式:x = linprog(c,A,b,Aeq,beq) x = linprog(c,A,b,Aeq,beq,lb,ub) x = linprog(c,A,b,Aeq,beq,lb,ub,x0) x = linprog(c,A,b,Aeq,beq,lb,ub,x0,options) x,

17、fval = linprog(.) x,fval,exitflag = linprog(.) x,fval,exitflag,output = linprog(.) x,fval,exitflag,output,lambda = linprog(.)上面的x,c,x,beq,lb,ub,A,Aeq的意義已經(jīng)說明，這里的x0是迭代的初始點(diǎn)（可以給也可以不給），求解的結(jié)果x就是最優(yōu)解，fval是對(duì)應(yīng)的最優(yōu)值。需要特別指出的是，Matlab對(duì)上述參數(shù)采用對(duì)號(hào)入座的形式，當(dāng)你所要處理的問題中沒有靠前的參數(shù)時(shí)，在對(duì)應(yīng)的位置上用“ ”占位。當(dāng)處理的問題是最大值問題時(shí)，可以通過目標(biāo)函數(shù)乘以-1轉(zhuǎn)變成為最小值

18、問題。而在不等式約束中是”“的形式時(shí)，也用同樣的方法統(tǒng)一成“”的形式。下面是前述三個(gè)例子的求解程序。例1：c=-4 3 2;A=2 3 1;3 2 1.5;b=34;36;Aeq=1 1 1;Beq=20;x,fval=linprog(c,A,b，Aeq，beq)輸出的結(jié)果為：Optimization terminated.x = 2.0000 6.0000 12.0000fval = -50.0000注意：由于問題是計(jì)算最大值，所以將c乘上-1，轉(zhuǎn)換成最小化問題，最優(yōu)值是-50，也就是最大利潤(rùn)為50元。此外，應(yīng)當(dāng)注意，該Linprog在缺省情況下假定所以變量非負(fù)，所以最后一個(gè)約束不需要寫出來

19、。例3c=120 40 40 40 40 40;A=-1 1 0 0 0 0;1 1 1 0 0 0;1 1 1 1 0 0;0.5 1 1 1 1 0;0.5 0 1 1 1 1;1 0 0 1 1 1;1 0 0 0 1 1;1 0 0 0 0 1;b=-10;12;14;16;18;17;15;10;lb=8;0;0;0;0;0;ub=12;inf;inf;inf;inf;inf;x,fval=linprog(c,A,b,lb,ub)輸出結(jié)果為：Optimization terminated.x = 8.0000 2.0000 4.1069 2.4839 3.4256 3.9836fva

20、l = 1.6000e+003 本題給出的結(jié)果并不非常滿意，因?yàn)楣蛦T的人員應(yīng)該是整數(shù)，但上面的結(jié)果是小數(shù)。也就是說，實(shí)際上決策變量除了上面的限制之外，應(yīng)該還有必須是整數(shù)的限制，否則就可能得到小數(shù)的結(jié)果。遺憾的是，現(xiàn)有版本的Matlab沒有求解整數(shù)規(guī)劃的功能，一個(gè)不規(guī)范但有時(shí)是有效的方法是固定一些量取成整數(shù)的方法繼續(xù)求解，比如x6接近與4，因此固定x6 = 4，也就是增加一組等式約束的條件，重新求解，實(shí)際發(fā)現(xiàn)，問題的最優(yōu)值不變，x3,x4,x5仍然是小數(shù)，再使用同樣的方法可以得到整數(shù)解。具體的過程希望讀者自己完成。但顯然上面的方法沒有一般性，特別是問題規(guī)模很大時(shí)。Lingo軟件具有求解整數(shù)規(guī)劃的

21、功能，我們?cè)诤竺鎸⑦M(jìn)行介紹。8.4 Lingo軟件的線性規(guī)劃解法 解決線性規(guī)劃問題，除了Matlab之外，Lingo是一款很優(yōu)秀的軟件。實(shí)際上，Lingo能解決的規(guī)劃問問遠(yuǎn)遠(yuǎn)不只是線性規(guī)劃問題。相比于Matlab，Lingo有下面的一些有點(diǎn)和特點(diǎn)：（1）對(duì)于大規(guī)模問題，Lingo輸入更加方便；（2）可以進(jìn)行靈敏性分析；（3）適合求解整數(shù)規(guī)劃問題；（4）求解問題的規(guī)模更大更快；（5），對(duì)于非線性，有時(shí)候得到的解優(yōu)于Matlab。8.4.1 Lingo的描述線性規(guī)劃問題 要了解Lingo程序，我們先從規(guī)劃問題的特點(diǎn)出發(fā)。前面說過，規(guī)劃問題包括決策變量，目標(biāo)函數(shù)和約束條件，當(dāng)然還有一些已知數(shù)據(jù)。編程

22、的目的就是告訴計(jì)算機(jī)我們需要求解的問題具體形式是怎樣的。也就是說要告訴計(jì)算機(jī)有那些已知數(shù)據(jù)，決策變量是什么，目標(biāo)函數(shù)是什么，約束條件是什么。 比如我們來看前面的例1，只要在Lingo的編輯窗口中輸入如下內(nèi)容：圖1這里基本上按照原始模型的數(shù)學(xué)表達(dá)直接輸入，比如（1）對(duì)于計(jì)算最大值問題用“max”，當(dāng)計(jì)算最小值問題時(shí)用“min”；（2）約束條件直接寫在下面，一般每條語句占一行，以“；”結(jié)束；（3）對(duì)于不等式約束，大于等于直接使用“>”，對(duì)于小于等于直接使用“<”。（4）缺省情況下，決策變量為非負(fù)。 點(diǎn)擊執(zhí)行按鈕，就可以得到下面的結(jié)果界面：圖2第一行得到的結(jié)果是問題的全局最優(yōu)解；第二行表

23、示的目標(biāo)函數(shù)的最優(yōu)值是50；第三行說明問題經(jīng)過2次的迭代得到最優(yōu)解；隨后的四行指明問題的最優(yōu)解：x1，x2和x3分別取2，6和12時(shí)達(dá)到最大值50，此外，當(dāng)變量是基變量時(shí)”Reduced Cost“值為0，反之，如果某個(gè)變量的值非0，則表示該變量增加一個(gè)單位是對(duì)于目標(biāo)函數(shù)的增加值；最后的五行主要說明松緊性，其中最后三行分別說明三個(gè)約束都是緊約束（也就是松弛變量取值為0），”Dual Price“稱為對(duì)偶價(jià)格， 表示右端向量的值增加是可以導(dǎo)致目標(biāo)值的增加量。 上面的例子主要針對(duì)小規(guī)模的規(guī)劃問題，但是在實(shí)際的計(jì)算中，Lingo提供了一種非常高效的描述規(guī)劃問題的方式。 實(shí)際上，最優(yōu)化問題都有非常規(guī)范

24、的結(jié)構(gòu)，包括目標(biāo)函數(shù)和約束條件，而對(duì)于線性規(guī)劃問題，目標(biāo)函數(shù)和約束條件在形式上的規(guī)范性使得這樣的問題容易用類似與程序的方式描述。下面是用另外一種方式描述的例子。也就是說，因?yàn)槟繕?biāo)函數(shù)是價(jià)格參數(shù)和決策變量的線性和，因此在Lingo需要一個(gè)求和的運(yùn)算，使用函數(shù)“sum()”。上面的第十二行表示需要計(jì)算的問題是最大化問題，目標(biāo)函數(shù)是c(i)*x(i)關(guān)于i求和。這個(gè)對(duì)應(yīng)于上面提到的目標(biāo)函數(shù)。為了描述問題的三個(gè)約束條件，這里分別用第十三、十四和十五行語句分布描述。注意每一個(gè)約束的形式，比如第一個(gè)是線性和小于一個(gè)量的形式，因此仍然使用sum()語句，就是矩陣A的第一行元素乘以x的三個(gè)元素然后對(duì)i求和，求

25、和的結(jié)果小于b(1)。后面的兩個(gè)語句有類似的解釋。因?yàn)橛玫綆в薪Y(jié)果的變量形式，因此需要定義數(shù)據(jù)集（相當(dāng)數(shù)據(jù)類型）。這一部分由第二到第六五行語句定義，由“sets:”和“endsets”開頭和結(jié)尾。第三行定義了一個(gè)數(shù)據(jù)集叫做price，這個(gè)數(shù)據(jù)集由三個(gè)分量構(gòu)成（由“/1.3/”所定義），具體定義的變量有兩個(gè)，即c和x。第四行定義了一個(gè)叫做rhs的數(shù)據(jù)集，也是一個(gè)三個(gè)分量構(gòu)成，用于存放三個(gè)約束條件右端的元素，具體定義的變量為b。這里的另外一個(gè)數(shù)據(jù)集是“mat”，它由前面的兩個(gè)數(shù)據(jù)集派生而成，其維數(shù)為前面兩個(gè)數(shù)據(jù)集維數(shù)的乘積，具體定義的變量A，用以存放約束中的矩陣。第七到第十一行稱為數(shù)據(jù)段，用以為模

26、型的參數(shù)賦值。需要注意的是，所有的參數(shù)作為一個(gè)向量的形式賦值，不管是行向量，列向量還是矩陣（注意，矩陣的賦值是先第一行，然后第二行，一直到最后一行）。 上述看似復(fù)雜化的輸入方式對(duì)于大型的問題極其的方便，實(shí)際上，這是對(duì)應(yīng)與另一種方便的數(shù)學(xué)書寫形式，即： （8.5）當(dāng)約束的個(gè)數(shù)較多時(shí)，由于形式上的相似性，可以使用類似于循環(huán)語句的形式進(jìn)行描述，所以在Lingo中引入了一個(gè)函數(shù)“for()”，用以描述類似于這樣的信息。下面用問題（8.2）的程序進(jìn)一步說明這種結(jié)構(gòu)的高效性。8.4.2 Lingo求解線性規(guī)劃問題的例子 前面的例2，我們給出具體的數(shù)據(jù)，比如：超市的數(shù)量為3個(gè)，蔬菜基地的數(shù)量為5個(gè)，分別記為

27、S1，S2，S3和B1，B2，B3，B4，B5，它們的坐標(biāo)位置為(5,8), (2,4), (8,2.5), (2.1,9), (8,7.5), (5,5.2), (1.3,1.7), (7.7,0.9)，并假定任意兩點(diǎn)之間有直線的道路相連。三個(gè)超市的需求量為28噸，15噸和9噸。幾個(gè)蔬菜基地的最大可提供的蔬菜數(shù)量為7，14，5，9，19噸。相應(yīng)的程序如下：model:sets: base/1.5/:xb,yb,supply; super/1.3/:xs,ys,demand; mat(base,super):c,n;endsetsdata: xb=2.1 8 5 1.3 7.7; yb=9 7

28、.5 5.2 1.7 0.9; supply=7 14 5 9 19; xs=5 2 8; ys=8 4 2.5; demand=28 15 9;enddatacalc: for(mat(i,j):c(i,j)=(yb(i)-ys(j)2+(xb(i)-xs(j)2)0.5);endcalcmin=sum(mat(i,j):c(i,j)*n(i,j);for(base(i):sum(super(j):n(i,j)<supply(i);for(super(j):sum(base(i):n(i,j)=demand(j);end注意：程序中使用了計(jì)算段，用“calc”開頭以“endcalc”結(jié)

29、束，用來計(jì)算距離矩陣c。得到的解報(bào)告如下：Global optimal solution found. Objective value: 168.4636 Total solver iterations: 5 Variable Value Reduced Cost XB( 1) 2. 0. XB( 2) 8. 0. XB( 3) 5. 0. XB( 4) 1. 0. XB( 5) 7. 0. YB( 1) 9. 0. YB( 2) 7. 0. YB( 3) 5. 0. YB( 4) 1. 0. YB( 5) 0. 0. SUPPLY( 1) 7. 0. SUPPLY( 2) 14.00000

30、0. SUPPLY( 3) 5. 0. SUPPLY( 4) 9. 0. SUPPLY( 5) 19.00000 0. XS( 1) 5. 0. XS( 2) 2. 0. XS( 3) 8. 0. YS( 1) 8. 0. YS( 2) 4. 0. YS( 3) 2. 0. DEMAND( 1) 28.00000 0. DEMAND( 2) 15.00000 0. DEMAND( 3) 9. 0. C( 1, 1) 3. 0. C( 1, 2) 5. 0. C( 1, 3) 8. 0. C( 2, 1) 3. 0. C( 2, 2) 6. 0. C( 2, 3) 5. 0. C( 3, 1) 2. 0. C( 3, 2) 3. 0. C( 3, 3) 4. 0. C( 4, 1) 7. 0. C( 4, 2) 2. 0. C( 4, 3) 6. 0. C( 5, 1) 7. 0. C( 5, 2