在之前的幾節(jié)中,我們介紹了幾種數(shù)學(xué)規(guī)劃問題竖螃,解決的方式基本都是用Matlab,Matlab中也確實提供了很多的函數(shù)用來解決規(guī)劃問題逗余,但是用Matlab解決還是有一些弊端特咆,比如在構(gòu)造限制條件的時候需要構(gòu)造一個巨大的矩陣,這個巨大的矩陣在很多情況下是稀疏的录粱,這樣對空間是一種浪費腻格,而且在編程時代碼與規(guī)劃問題不夠形似,以至于代碼不夠直觀啥繁,那么有沒有更好的解決規(guī)劃問題的方法呢菜职。
所以這一節(jié)我們來介紹一款運籌學(xué)軟件——Lingo。
下面是一個下載和破解教程旗闽,請讀者先行安裝破解酬核,再閱讀下面的內(nèi)容。
1.Lingo入門
打開Lingo之后适室,就會出現(xiàn)以下的界面嫡意,下面的空白區(qū)域可以輸入代碼,用來解決數(shù)學(xué)規(guī)劃問題捣辆,我們將用一些例子來教大家如何使用這個軟件蔬螟。
例1.1 用Lingo解決下面線性規(guī)劃問題
由于LINGO中已假設(shè)所有的變量是非負的,所以非負約束不必再輸入到計算機中罪帖,LINGO也不區(qū)分變量中的大小寫字符(任何小寫字符將被轉(zhuǎn)換為大寫字符)促煮;約束條件中的”<=”及”>=”可用”<”及”>”代替。在模型窗口中輸入如下代碼:
min=2*x1+3*x2;
x1+x2>350;
x1>100;
2*x1+x2<600;
之后在左上角點擊如圖所示的準心按鍵整袁。
就會輸出問題的結(jié)果菠齿。
例1.2 利用Lingo解決最小運輸費用問題
運輸費用如下圖所示:
運輸費用
解:設(shè)為從
運到
的貨量。
表示從
運到
的運費坐昙,
表示
的銷量绳匀,
表示
地的產(chǎn)量。
s.t.
代碼如下:
炸客!代表注釋
首先設(shè)置變量疾棵,產(chǎn)地(warehouses),銷地(vendors)痹仙,產(chǎn)量(capacity)是尔,需求(demand)
運輸費用(cost),運輸量(volume)
之后設(shè)置目標函數(shù):cost*volume
之后設(shè)置約束:
從i地運出的總數(shù)不超過產(chǎn)量开仰。
運往j地的總數(shù)等于j地需求量拟枚。
之后設(shè)置數(shù)據(jù)薪铜。
于是整個模型設(shè)置完畢。
model:
!6發(fā)點8收點運輸問題;
sets:
warehouses/wh1..wh6/: capacity;
vendors/v1..v8/: demand;
links(warehouses,vendors): cost, volume;
endsets
!目標函數(shù);
min=@sum(links: cost*volume);
!需求約束;
@for(vendors(J):@sum(warehouses(I): volume(I,J))=demand(J));
!產(chǎn)量約束;
@for(warehouses(I):@sum(vendors(J): volume(I,J))<=capacity(I));
!下面是數(shù)據(jù);
data:
capacity=60 55 51 43 41 52;
demand=35 37 22 32 41 32 43 38;
cost=6 2 6 7 4 2 9 5
4 9 5 3 8 5 8 2
5 2 1 9 7 4 3 3
7 6 7 3 9 2 7 1
2 3 9 5 7 2 6 5
5 5 2 2 8 1 4 3;
enddata
end
輸出結(jié)果
Global optimal solution found.
Objective value: 664.0000 恩溅!目標函數(shù)值
Infeasibilities: 0.000000
Total solver iterations: 15
Model Class: LP
Total variables: 48
Nonlinear variables: 0
Integer variables: 0
Total constraints: 15
Nonlinear constraints: 0
Total nonzeros: 144
Nonlinear nonzeros: 0
隔箍!各變量值
Variable Value Reduced Cost
CAPACITY( WH1) 60.00000 0.000000
CAPACITY( WH2) 55.00000 0.000000
CAPACITY( WH3) 51.00000 0.000000
CAPACITY( WH4) 43.00000 0.000000
CAPACITY( WH5) 41.00000 0.000000
CAPACITY( WH6) 52.00000 0.000000
DEMAND( V1) 35.00000 0.000000
DEMAND( V2) 37.00000 0.000000
DEMAND( V3) 22.00000 0.000000
DEMAND( V4) 32.00000 0.000000
DEMAND( V5) 41.00000 0.000000
DEMAND( V6) 32.00000 0.000000
DEMAND( V7) 43.00000 0.000000
DEMAND( V8) 38.00000 0.000000
COST( WH1, V1) 6.000000 0.000000
COST( WH1, V2) 2.000000 0.000000
COST( WH1, V3) 6.000000 0.000000
COST( WH1, V4) 7.000000 0.000000
COST( WH1, V5) 4.000000 0.000000
COST( WH1, V6) 2.000000 0.000000
COST( WH1, V7) 9.000000 0.000000
COST( WH1, V8) 5.000000 0.000000
COST( WH2, V1) 4.000000 0.000000
COST( WH2, V2) 9.000000 0.000000
COST( WH2, V3) 5.000000 0.000000
COST( WH2, V4) 3.000000 0.000000
COST( WH2, V5) 8.000000 0.000000
COST( WH2, V6) 5.000000 0.000000
COST( WH2, V7) 8.000000 0.000000
COST( WH2, V8) 2.000000 0.000000
COST( WH3, V1) 5.000000 0.000000
COST( WH3, V2) 2.000000 0.000000
COST( WH3, V3) 1.000000 0.000000
COST( WH3, V4) 9.000000 0.000000
COST( WH3, V5) 7.000000 0.000000
COST( WH3, V6) 4.000000 0.000000
COST( WH3, V7) 3.000000 0.000000
COST( WH3, V8) 3.000000 0.000000
COST( WH4, V1) 7.000000 0.000000
COST( WH4, V2) 6.000000 0.000000
COST( WH4, V3) 7.000000 0.000000
COST( WH4, V4) 3.000000 0.000000
COST( WH4, V5) 9.000000 0.000000
COST( WH4, V6) 2.000000 0.000000
COST( WH4, V7) 7.000000 0.000000
COST( WH4, V8) 1.000000 0.000000
COST( WH5, V1) 2.000000 0.000000
COST( WH5, V2) 3.000000 0.000000
COST( WH5, V3) 9.000000 0.000000
COST( WH5, V4) 5.000000 0.000000
COST( WH5, V5) 7.000000 0.000000
COST( WH5, V6) 2.000000 0.000000
COST( WH5, V7) 6.000000 0.000000
COST( WH5, V8) 5.000000 0.000000
COST( WH6, V1) 5.000000 0.000000
COST( WH6, V2) 5.000000 0.000000
COST( WH6, V3) 2.000000 0.000000
COST( WH6, V4) 2.000000 0.000000
COST( WH6, V5) 8.000000 0.000000
COST( WH6, V6) 1.000000 0.000000
COST( WH6, V7) 4.000000 0.000000
COST( WH6, V8) 3.000000 0.000000
VOLUME( WH1, V1) 0.000000 5.000000
VOLUME( WH1, V2) 19.00000 0.000000
VOLUME( WH1, V3) 0.000000 5.000000
VOLUME( WH1, V4) 0.000000 7.000000
VOLUME( WH1, V5) 41.00000 0.000000
VOLUME( WH1, V6) 0.000000 2.000000
VOLUME( WH1, V7) 0.000000 6.000000
VOLUME( WH1, V8) 0.000000 6.000000
VOLUME( WH2, V1) 1.000000 0.000000
VOLUME( WH2, V2) 0.000000 4.000000
VOLUME( WH2, V3) 0.000000 1.000000
VOLUME( WH2, V4) 32.00000 0.000000
VOLUME( WH2, V5) 0.000000 1.000000
VOLUME( WH2, V6) 0.000000 2.000000
VOLUME( WH2, V7) 0.000000 2.000000
VOLUME( WH2, V8) 0.000000 0.000000
VOLUME( WH3, V1) 0.000000 4.000000
VOLUME( WH3, V2) 11.00000 0.000000
VOLUME( WH3, V3) 0.000000 0.000000
VOLUME( WH3, V4) 0.000000 9.000000
VOLUME( WH3, V5) 0.000000 3.000000
VOLUME( WH3, V6) 0.000000 4.000000
VOLUME( WH3, V7) 40.00000 0.000000
VOLUME( WH3, V8) 0.000000 4.000000
VOLUME( WH4, V1) 0.000000 4.000000
VOLUME( WH4, V2) 0.000000 2.000000
VOLUME( WH4, V3) 0.000000 4.000000
VOLUME( WH4, V4) 0.000000 1.000000
VOLUME( WH4, V5) 0.000000 3.000000
VOLUME( WH4, V6) 5.000000 0.000000
VOLUME( WH4, V7) 0.000000 2.000000
VOLUME( WH4, V8) 38.00000 0.000000
VOLUME( WH5, V1) 34.00000 0.000000
VOLUME( WH5, V2) 7.000000 0.000000
VOLUME( WH5, V3) 0.000000 7.000000
VOLUME( WH5, V4) 0.000000 4.000000
VOLUME( WH5, V5) 0.000000 2.000000
VOLUME( WH5, V6) 0.000000 1.000000
VOLUME( WH5, V7) 0.000000 2.000000
VOLUME( WH5, V8) 0.000000 5.000000
VOLUME( WH6, V1) 0.000000 3.000000
VOLUME( WH6, V2) 0.000000 2.000000
VOLUME( WH6, V3) 22.00000 0.000000
VOLUME( WH6, V4) 0.000000 1.000000
VOLUME( WH6, V5) 0.000000 3.000000
VOLUME( WH6, V6) 27.00000 0.000000
VOLUME( WH6, V7) 3.000000 0.000000
VOLUME( WH6, V8) 0.000000 3.000000
Row Slack or Surplus Dual Price
1 664.0000 -1.000000
2 0.000000 -4.000000
3 0.000000 -5.000000
4 0.000000 -4.000000
5 0.000000 -3.000000
6 0.000000 -7.000000
7 0.000000 -3.000000
8 0.000000 -6.000000
9 0.000000 -2.000000
10 0.000000 3.000000
11 22.00000 0.000000
12 0.000000 3.000000
13 0.000000 1.000000
14 0.000000 2.000000
15 0.000000 2.000000
以上是舉了兩個基本的例子,對Lingo的功能有一個基本的介紹脚乡。
接下來講具體介紹Lingo中的結(jié)構(gòu):
2.Lingo中的集
對實際問題建模的時候蜒滩,總會遇到一群或多群相聯(lián)系的對象,比如工廠奶稠、消費者群體俯艰、交通工具和雇工等等。LINGO允許把這些相聯(lián)系的對象聚合成集(sets)锌订。一旦把對象聚合成集蟆炊,就可以利用集來最大限度的發(fā)揮LINGO建模語言的優(yōu)勢。
2.1集的定義
集是一群相聯(lián)系的對象瀑志,這些對象也稱為集的成員。一個集可能是一系列產(chǎn)品污秆、卡車或雇員劈猪。每個集成員可能有一個或多個與之有關(guān)聯(lián)的特征,我們把這些特征稱為屬性良拼。屬性值可以預(yù)先給定战得,也可以是未知的,有待于LINGO求解庸推。例如常侦,產(chǎn)品集中的每個產(chǎn)品可以有一個價格屬性;卡車集中的每輛卡車可以有一個牽引力屬性贬媒;雇員集中的每位雇員可以有一個薪水屬性聋亡,也可以有一個生日屬性等等。
LINGO有兩種類型的集:原始集(primitive set)和派生集(derived set)际乘。
一個原始集是由一些最基本的對象組成的坡倔。
一個派生集是用一個或多個其它集來定義的,也就是說脖含,它的成員來自于其它已存在的集罪塔。
2.2模型的集
集部分是LINGO模型的一個可選部分。在LINGO模型中使用集之前养葵,必須在集部分事先定義征堪。集部分以關(guān)鍵字“sets:”開始,以“endsets”結(jié)束关拒。一個模型可以沒有集部分佃蚜,或有一個簡單的集部分庸娱,或有多個集部分。一個集部分可以放置于模型的任何地方爽锥,但是一個集及其屬性在模型約束中被引用之前必須定義了它們涌韩。
2.2.1定義原始集
定義一個原始集,用下面的語法:
setname[/member_list/][:attribute_list];
注意:用“[]”表示該部分內(nèi)容可選氯夷。下同臣樱,不再贅述。
Setname是你選擇的來標記集的名字腮考,最好具有較強的可讀性雇毫。集名字必須嚴格符合標準命名規(guī)則:以拉丁字母或下劃線(_)為首字符,其后由字母(A-Z)踩蔚、下劃線棚放、阿拉伯?dāng)?shù)字(0,1馅闽,…飘蚯,9)組成的總長度不超過32個字符的字符串,且不區(qū)分大小寫福也。
注意:該命名規(guī)則同樣適用于集成員名和屬性名等的命名局骤。
Member_list是集成員列表。如果集成員放在集定義中暴凑,那么對它們可采取顯式羅列和隱式羅列兩種方式峦甩。如果集成員不放在集定義中,那么可以在隨后的數(shù)據(jù)部分定義它們现喳。
1.當(dāng)顯式羅列成員時凯傲,必須為每個成員輸入一個不同的名字,中間用空格或逗號擱開嗦篱,允許混合使用冰单。
例2.1 可以定義一個名為students的原始集,它具有成員John灸促、Jill球凰、Rose和Mike,屬性有sex和age:
sets:
students/John Jill, Rose Mike/: sex, age;
endsets
2.當(dāng)隱式羅列成員時腿宰,不必羅列出每個集成員呕诉。可采用如下語法:
setname/member1..memberN/[: attribute_list];
這里的member1是集的第一個成員名吃度,memberN是集的最末一個成員名甩挫。LINGO將自動產(chǎn)生中間的所有成員名。LINGO也接受一些特定的首成員名和末成員名椿每,用于創(chuàng)建一些特殊的集伊者。
例2.2 隱式羅列成員舉例
隱式成員列表格式 | 示例 | 所產(chǎn)生集成員 |
---|---|---|
1..n | 1..5 | 1,2,3,4,5 |
StringM..StringN | Car3..Car14 | Car3,Car4,Car5...Car14 |
DayM..DayN | Mon..Fri | Mon,Tue,Wed,Thu,Fri |
MonthM..MonthN | Oct..Jan | Oct,Nov,Dec,Jan |
3.集成員不放在集定義中英遭,而在隨后的數(shù)據(jù)部分來定義。
例2.3
!集部分;
sets:
students:sex,age;
endsets
!數(shù)據(jù)部分;
data:
students,sex,age= John 1 16
Jill 0 14
Rose 0 17
Mike 1 13;
enddata
注意:開頭用感嘆號(!)亦渗,末尾用分號(;),!表示注釋挖诸,可跨多行。
在集部分只定義了一個集students法精,并未指定成員多律。在數(shù)據(jù)部分羅列了集成員John、Jill搂蜓、Rose和Mike狼荞,并對屬性sex和age分別給出了值。
集成員無論用何種字符標記,它的索引都是從1開始連續(xù)計數(shù)帮碰。在attribute_ list可以指定一個或多個集成員的屬性相味,屬性之間必須用逗號隔開。
可以把集殉挽、集成員和集屬性同C語言中的結(jié)構(gòu)體作個類比丰涉。如下所示:
集 ←→ 結(jié)構(gòu)體
集成員 ←→ 結(jié)構(gòu)體的域
集屬性 ←→ 結(jié)構(gòu)體實例
2.2.2 定義派生集
可用下面的語法定義一個派生集:
setname(parent_set_list)[/member_list/][:attribute_list];
setname是集的名字。parent_set_list是已定義的集的列表斯碌,多個時必須用逗號隔開昔搂。如果沒有指定成員列表,那么LINGO會自動創(chuàng)建父集成員的所有組合作為派生集的成員输拇。派生集的父集既可以是原始集,也可以是其它的派生集贤斜。
例2.4
sets:
product/A B/;
machine/M N/;
week/1..2/;
allowed(product,machine,week):x;
endsets
此例中定義了一個三個原始集(product,machine,week)策吠,一個派生集(allow),allow的父集是前三個原始集(product,machine,week)瘩绒。
此時該派生集中的成員如下:
編號 | 成員 |
---|---|
1 | (A,M,1) |
2 | (A,M,2) |
3 | (B,M,1) |
4 | (B,M,2) |
5 | (A,N,1) |
6 | (A,N,2) |
7 | (B,N,1) |
8 | (B.N,2) |
也可以簡單的這樣理解猴抹,未特殊說明派生類是原始類組成的矩陣。
成員列表被忽略時锁荔,派生集成員由父集成員所有的組合構(gòu)成蟀给,這樣的派生集成為稠密集。如果限制派生集的成員阳堕,使它成為父集成員所有組合構(gòu)成的集合的一個子集跋理,這樣的派生集成為稀疏集。同原始集一樣恬总,派生集成員的聲明也可以放在數(shù)據(jù)部分前普。一個派生集的成員列表有兩種方式生成:①顯式羅列;②設(shè)置成員資格過濾器壹堰。當(dāng)采用方式①時拭卿,必須顯式羅列出所有要包含在派生集中的成員骡湖,并且羅列的每個成員必須屬于稠密集。使用前面的例子峻厚,顯式羅列派生集的成員:
allowed(product,machine,week)/A M 1,A N 2,B N 1/;
如果需要生成一個大的响蕴、稀疏的集,那么顯式羅列就很討厭惠桃。幸運地是許多稀疏集的成員都滿足一些條件以和非成員相區(qū)分浦夷。我們可以把這些邏輯條件看作過濾器,在LINGO生成派生集的成員時把使邏輯條件為假的成員從稠密集中過濾掉刽射。
例2.5
sets:
!學(xué)生集:性別屬性sex军拟,1表示男性,0表示女性誓禁;年齡屬性age. ;
students/John,Jill,Rose,Mike/:sex,age;
!男學(xué)生和女學(xué)生的聯(lián)系集:友好程度屬性friend懈息,[0,1]之間的數(shù)摹恰。 ;
linkmf(students,students)|sex(&1) #eq# 1 #and# sex(&2) #eq# 0: friend;
!男學(xué)生和女學(xué)生的友好程度大于0.5的集;
linkmf2(linkmf) | friend(&1,&2) #gt# 0.5 : x;
endsets
data:
sex,age = 1 16
0 14
0 17
0 13;
friend = 0.3 0.5 0.6;
enddata
用豎線(|)來標記一個成員資格過濾器的開始辫继。#eq#是邏輯運算符,用來判斷是否“相等”,#gt#也是運算符俗慈,代表“大于”姑宽。 &1可看作派生集的第1個原始父集的索引源梭,它取遍該原始父集的所有成員繁成;&2可看作派生集的第2 個原始父集的索引,它取遍該原始父集的所有成員记焊;&3酣溃,&4瘦穆,……,以此類推赊豌。注意如果派生集B的父集是另外的派生集A扛或,那么上面所說的原始父集是集A向前回溯到最終的原始集,其順序保持不變碘饼,并且派生集A的過濾器對派生集B仍然有效熙兔。因此,派生集的索引個數(shù)是最終原始父集的個數(shù)艾恼,索引的取值是從原始父集到當(dāng)前派生集所作限制的總和住涉。
總的來說,LINGO可識別的集只有兩種類型:原始集和派生集钠绍。
在一個模型中秆吵,原始集是基本的對象,不能再被拆分成更小的組分五慈。原始集可以由顯式羅列和隱式羅列兩種方式來定義纳寂。當(dāng)用顯式羅列方式時主穗,需在集成員列表中逐個輸入每個成員。當(dāng)用隱式羅列方式時毙芜,只需在集成員列表中輸入首成員和末成員忽媒,而中間的成員由LINGO產(chǎn)生。
另一方面腋粥,派生集是由其它的集來創(chuàng)建晦雨。這些集被稱為該派生集的父集(原始集或其它的派生集)。一個派生集既可以是稀疏的隘冲,也可以是稠密的闹瞧。稠密集包含了父集成員的所有組合(有時也稱為父集的笛卡爾乘積)。稀疏集僅包含了父集的笛卡爾乘積的一個子集展辞,可通過顯式羅列和成員資格過濾器這兩種方式來定義奥邮。顯式羅列方法就是逐個羅列稀疏集的成員。成員資格過濾器方法通過使用稀疏集成員必須滿足的邏輯條件從稠密集成員中過濾出稀疏集的成員罗珍。
本部分對Lingo軟件的基本用法和基本元素:集洽腺,進行了介紹,由于內(nèi)容過多覆旱,我決定分成幾個部分來介紹蘸朋。