運籌學(xué)（課堂PPT）

1、1運籌學(xué)華南熱帶農(nóng)業(yè)大學(xué)基礎(chǔ)學(xué)院舒興明TeL：mail：2必備知識 基礎(chǔ)微積分知識：極限，一元函數(shù)微分積分基本知識，多元函數(shù)的微分、重積分基本知識； 線性代數(shù)知識：行列式，矩陣的相關(guān)知識，向量相關(guān)知識，方程組求解； 概率統(tǒng)計知識：概率的概念及其計算方法，隨機變量及其特征，一般分布的特征及其概率的計算方法，基本統(tǒng)計知識。3文獻(xiàn)資料運籌學(xué)手冊（1999） 徐光輝.北京：科學(xué)出版社優(yōu)化建模與LINDO/LINGO軟件 謝金星.薛毅.北京：清華大學(xué)出版社數(shù)學(xué)模型 譚永基等.上海：復(fù)旦大學(xué)出版社4數(shù)學(xué)模型.姜啟源.北京：高等教育出版社管理科學(xué)（運籌學(xué)） （加）Peter C.B

2、ell.北京：機械工業(yè)出版社MATLAB7基礎(chǔ)與提高 飛思科技產(chǎn)品研發(fā)中心.北京：電子工業(yè)出版社Introduction to Operations Research Fredrick S.Hillier &Gerald J.Lieberman 北京：機械工業(yè)出版社5生產(chǎn)與運作管理制造與服務(wù)Production and Operations Management Manufacturing and Services Richard B.Chase&Nicholas J.Aquilano&F.Robert Jacobs 北京：機械工業(yè)出版社管理科學(xué)導(dǎo)論 An Introd

3、uction to Management Science Quantitative Approaches to Decision Making David R. Anderson & Dennis J. Sveeney Thomas A. Williams 北京：機械工業(yè)出版社6目錄線性規(guī)劃規(guī)劃軟件的應(yīng)用庫存論對策分析圖與網(wǎng)絡(luò)組合分析排隊論多目標(biāo)規(guī)劃管理信息系統(tǒng)隨機規(guī)劃計算機隨機模擬序7序一、運籌學(xué)性質(zhì) 運籌學(xué)是從上世紀(jì)三四十年代發(fā)展起來的一門新興學(xué)科，它的研究對象是人類對各種資源的運用及籌劃活動，目的在于了解和發(fā)現(xiàn)這種運用以及籌劃活動的基本規(guī)律，以便發(fā)揮有限資源的最大效益，達(dá)到總體、

4、全局最優(yōu)的目標(biāo)。 運籌學(xué)研究的特點有三個：一是強調(diào)研究過程的完整性，從問題開始，到構(gòu)建模型、提出解案、進(jìn)行檢驗、建立控制，直到付諸實施為止的所有環(huán)節(jié)構(gòu)成了運籌學(xué)研究過程的全過程。二是運籌學(xué)研究的多學(xué)科交叉性，一個復(fù)雜的研究對象，需要物理學(xué)家、化學(xué)家、數(shù)學(xué)家、經(jīng)濟(jì)學(xué)家、工程師等組成聯(lián)合研究隊伍，才能了解和完成研究工作。三是運籌學(xué)研究強調(diào)理論與實踐的結(jié)合，從這個意義看，研究過程需要從實際出發(fā)，不要太過于強調(diào)“最優(yōu)”，必要時先求可行“解”，在看有沒有“尋優(yōu)”的必要。8二、我國古代運籌思想斗馬術(shù) 齊將田忌與齊王經(jīng)常賽馬，孫臏發(fā)現(xiàn)田忌的馬雖然不如齊王的，但相差不多，于是在一次賽馬中給田忌獻(xiàn)策：以下馬對齊

5、王的上馬，以上馬對齊王的中馬，以中馬對齊王的下馬，結(jié)果田忌以一負(fù)兩勝而獲勝。這就是現(xiàn)代運籌學(xué)的對策論分支的基本分析方法：從不利的設(shè)想出發(fā)，不求能大勝，但保不大敗，顧全大局。軍事后勤 北宋時期大科學(xué)家、軍事家沈括（1031-1095年）關(guān)于軍事后勤問題，通過分析計算從軍各類人員可以背負(fù)糧食的基本數(shù)據(jù)出發(fā)，計算了后勤人員與作戰(zhàn)士兵在不同行軍天數(shù)中的比例關(guān)系，同時也分析了各種畜牲運糧與人力運糧的比例利弊，最后得出“因糧于敵”的重要決策。即應(yīng)該從敵國就地征糧，保障前方供應(yīng)，以便減少后勤人員的比例，提高軍隊的作戰(zhàn)能力。城市規(guī)劃宋真宗祥符年間（1008-1017年）宮廷失火，需要重建，當(dāng)時采用了一個取土、

6、棄土、材料運輸，以及施工次序統(tǒng)籌安排的綜合方案：先在需要重建的通衢大道上就近取土，取土后，通衢變成深溝，于是引卞水，成為一條人工小河，因此基建材料便可以由水路運入工地；宮殿修成后，又將基建費料棄置溝中，重新建成通衢大道。這樣的方案取土、棄土近，運輸便，一舉三得，節(jié)省巨額費用。作物輪作我國北魏時期科學(xué)家賈思勰齊民要術(shù)（533-544年）記載了我國古代勞動人民在耕作、播種、選種、育種、肥田等方面的經(jīng)驗：書中按照不同的作物把播種時間分為上、中、下三時；不同的作物連作時。茬口也安排為上、中、下三等，并指出許多作物之間的先后關(guān)系，如種谷“二月上旬為上時，三月下旬為中時，四月上旬為下時.”。以“綠豆、小豆

7、底（即前茬作物）為上，麻黍、胡麻次之，蕪青、大豆為下.”且谷田不可連作，“必須歲易”。這就是現(xiàn)代運籌學(xué)的多階段決策問題的典范。9三、現(xiàn)代運籌學(xué)發(fā)展史1908年丹麥電話工程師Erlang關(guān)于電話局中繼線數(shù)目的話務(wù)理論是現(xiàn)代排隊論研究的起源；英國的Lanchester關(guān)于戰(zhàn)爭中兵力部署的理論是現(xiàn)代軍事運籌學(xué)最早的模型；20年代美國的Levinson關(guān)于最優(yōu)發(fā)貨量的研究是現(xiàn)代庫存論和決策論發(fā)展的最初啟示；30年代末蘇聯(lián)的康托諾維奇(Konterovitch)總結(jié)他研究工作而寫成的小冊子生產(chǎn)組織與計劃中的數(shù)學(xué)方法是線性規(guī)劃對工業(yè)生產(chǎn)問題的典型應(yīng)用；30年代中后期英國應(yīng)用新雷達(dá)系統(tǒng)對付德國飛機的騷擾的成

8、功，促使了在英美兩國各個軍事部門都相繼成立了運籌小組，直到二戰(zhàn)結(jié)束，相繼轉(zhuǎn)入民用部門。 1949年著名的RAND公司成立；1959年，由英、美、法三國運籌學(xué)學(xué)會發(fā)起成立了國際運籌學(xué)會聯(lián)合會（IFORS）；我國1982年加入該運籌學(xué)會聯(lián)合會。10線性規(guī)劃 線性規(guī)劃是運籌學(xué)中最基本的模型，從數(shù)學(xué)上說，是一個特殊的條件極值問題：尋求一個線性函數(shù)在一組線性不等式條件下的最大值或最小值。 1939年Konterovitch首先提出生產(chǎn)配套問題；接著Hitchcok和Koopmans等分別提出運輸問題(1940)和有限資源分配問題(1941)；1947年，Dantzig提出了單純形方法(simplex m

9、ethod)后，線性規(guī)劃變成為一個獨立學(xué)科，迅猛發(fā)展。1975年， Konterovitch和Koopmans由于創(chuàng)建了經(jīng)濟(jì)模型，經(jīng)濟(jì)理論以及數(shù)理經(jīng)濟(jì)方法，獲得了Nobel經(jīng)濟(jì)學(xué)獎。其中包含他們對線性規(guī)劃的卓越貢獻(xiàn)。 線性規(guī)劃由于廣泛的應(yīng)用和強有力的算法，是目前最成熟最成功的運籌學(xué)分支之一。11案例1 生產(chǎn)決策 某企業(yè)用四種資源生產(chǎn)三種產(chǎn)品，工藝系數(shù)、資源限量及價值系數(shù)如下表所示，問如制訂生產(chǎn)計劃，使得該企業(yè)獲利最大。資源 產(chǎn)品ABC資源限量I986500II547450832300764550每件產(chǎn)品利潤100807012問題理解：1對該企業(yè)來說，什么是生產(chǎn)計劃？當(dāng)前資料和條件是不是制定生產(chǎn)

10、計劃的確定和必須條件？有沒有需要補充的條件？本企業(yè)追求利潤最大，與什么有關(guān)？成本、產(chǎn)量、銷售量、收益、利潤的關(guān)系是什么？234你是否清楚該企業(yè)的目標(biāo)和實際約束（困難）？如何表述（表達(dá)）你所希望的目標(biāo)和約束？假設(shè)：該企業(yè)產(chǎn)品都能夠銷售出去，即產(chǎn)量等于銷售量。13分析問題：1變量設(shè)置設(shè)A、B、C三種產(chǎn)品的產(chǎn)量分別為123,x x x資源 產(chǎn)品ABC資源限量I986500II547450832300764550每件產(chǎn)品利潤1008070根據(jù)問題，利潤表達(dá)為1231008070yxxx（產(chǎn)品單位）企業(yè)所獲得的總利潤為y（貨幣單位）。三種產(chǎn)品消耗每種資源的總量不應(yīng)該超過資源限量，即123986500 x

11、xx第I種資源限制條件123547450 xxx第II種資源限制條件123832300 xxx第III種資源限制條件123764550 xxx第IV種資源限制條件14資源 產(chǎn)品ABC資源限量I986500II547450832300764550每件產(chǎn)品利潤1008070特別注意，由于A、B、C的產(chǎn)量為絕對產(chǎn)量，故不為負(fù)，即123,0 xxx那么該問題轉(zhuǎn)化為數(shù)學(xué)問題就是求三元函數(shù)y在多個約束條件下的最大值，表達(dá)為123max1008070yxxxs.tsubject to123123123123123986500547450832300764550,0 xxxxxxxxxxxxxxx目標(biāo)函數(shù)條件

12、約束變量約束15我們稱123max1008070yxxx123123323123123986500547450832300764550,0 xxxxxxxxxxxxxxx 其中，max表示企業(yè)目標(biāo)欲望（利潤越大越好，如果是成本等，可能是越小越好，用min表示）。x1，x2，x3表示企業(yè)的決策變量，企業(yè)的一切行為和結(jié)果都與這些決策變量有關(guān)。該實際問題的數(shù)學(xué)模型。1162 注意到，目標(biāo)函數(shù)和所有約束不等式（等于，大于等于，小于等于）都是決策變量x1，x2，x3的一次函數(shù)表達(dá)式，在代數(shù)上稱為線性關(guān)系表達(dá)式，所以，這個數(shù)學(xué)模型又稱為線性規(guī)劃數(shù)學(xué)模型。3 目標(biāo)函數(shù)是決策變量的一次和函數(shù)，表示目標(biāo)利潤（成

13、本，效率，時間等）可以由各個決策變量所代表的產(chǎn)品各自利潤的和（按比例貢獻(xiàn)）；第i個線性約束（決策變量的一次和函數(shù)）表示每種產(chǎn)品對第i種資源的消耗是按照比例分配的，且這種消耗的累積不超過該種資源要求。 如果一個問題的目標(biāo)是由各個決策變量對應(yīng)的產(chǎn)品按照比例累積（和），且各種產(chǎn)品對每種資源的消耗都是嚴(yán)格按照比例分配的，那么該問題就可以描述為線性規(guī)劃模型。17模型求解利用目前最好的優(yōu)化軟件lingo8.0，輸入模型可以直接求解。模型輸入完畢，并且沒有錯誤，按這個按鈕就可以。18求解結(jié)果： Global optimal solution found at iteration: 3 Objective v

14、alue: 5712.121 Variable Value Reduced Cost X1 24.24242 0.000000 X2 0.000000 8.484848 X3 46.96970 0.000000 Row Slack or Surplus Dual Price 1 5712.121 1.000000 2 0.000000 10.60606 3 0.000000 0.9090909 4 12.12121 0.000000 5 192.4242 0.000000決策變量非零分量的個數(shù)不超過條件約束的個數(shù)，且等于獨立的條件約束的個數(shù)。在建立模型時，盡量寫出全部獨立的約束不等式。約束越全

15、面，非零分量就越多，也就是，市場信息越復(fù)雜，產(chǎn)品就越應(yīng)該多樣化。針對這個求解結(jié)果，還應(yīng)該做解可行性分析，靈敏度分析等，這些都放在對偶分析中講解。19本問題，建立更全面的模型如下：資源 產(chǎn)品A(x1)B(x2)C(x3)資源限量I9(r11)8(r12)6(r13)500(b1)II5(r21)4(r22)7(r23)450(b2)8(r31)3(r32)2(r33)300(b3)7(r41)6(r42)4(r43)550(b4)每件產(chǎn)品利潤 100(c1)80(c2)70(c3)設(shè)x1，x2，x3表示A、B、C三種產(chǎn)品的產(chǎn)量；c1，c2，c3表示A、B、C三種產(chǎn)品的市場利潤；b1，b2，b3，

16、b4表示I、II、III、IV四種原材料的限量；rij表示第j種產(chǎn)品消耗第i種資源的比例系數(shù)(j=1,2,3;i=1,2,3,4)。則數(shù)學(xué)模型為1 1223311 1122133121 1222233231 1322333341 14224334max.0,1,2,3jyc xc xc xr xr xr xbr xr xr xbstr xr xr xbr xr xr xbxj20引入向量和矩陣記法，有31m ax.0jjjyc xA xbs tx其中，資源 產(chǎn)品A(x1)B(x2)C(x3)資源限量I9(r11)8(r12)6(r13)500(b1)II5(r21)4(r22)7(r23)45

17、0(b2)8(r31)3(r32)2(r33)300(b3)7(r41)6(r42)4(r43)550(b4)每件產(chǎn)品利潤100(c1)80(c2)70(c3)123(,)(1 0 0, 8 0, 7 0 )cccc1234(,)(500, 450,300,550)TTbbbbb123(,)Txxxx 4 39 8 65 4 78 3 27 64ijAr價值向量決策向量資源向量技術(shù)系數(shù)矩陣2131max.0jjjyc xAxbstx線性規(guī)劃模型的向量寫法sets:juece/1.3/:x,c;ziyuan/1.4/:b;jishu(ziyuan,juece):a;endsetsmax=sum(

18、juece:c*x);for(ziyuan(i):sum(juece(j):a(i,j)*x(j)=b(i);data:c=100,80,70;b=500,450,300,550;a=9,8,6 5,4,7 8,3,2 7,6,4;enddata這種輸入模型的方法叫做集合式輸入法，真對大型模型有利22 Global optimal solution found at iteration: 0 Objective value: 5712.121 Variable Value Reduced Cost X( 1) 24.24242 0.000000 X( 2) 0.000000 8.484848

19、X( 3) 46.96970 0.000000 C( 1) 100.0000 0.000000 C( 2) 80.00000 0.000000 C( 3) 70.00000 0.000000 B( 1) 500.0000 0.000000 B( 2) 450.0000 0.000000 B( 3) 300.0000 0.000000 B( 4) 550.0000 0.000000問題的解23 A( 1, 1) 9.000000 0.000000 A( 1, 2) 8.000000 0.000000 A( 1, 3) 6.000000 0.000000 A( 2, 1) 5.000000 0.0

20、00000 A( 2, 2) 4.000000 0.000000 A( 2, 3) 7.000000 0.000000 A( 3, 1) 8.000000 0.000000 A( 3, 2) 3.000000 0.000000 A( 3, 3) 2.000000 0.000000 A( 4, 1) 7.000000 0.000000 A( 4, 2) 6.000000 0.000000 A( 4, 3) 4.000000 0.000000 Row Slack or Surplus Dual Price 1 5712.121 1.000000 2 0.000000 10.60606 3 0.00

21、0000 0.9090909 4 12.12121 0.000000 5 192.4242 0.00000024sets:juece/1.3/:x,c;ziyuan/1.4/:b;jishu(ziyuan,juece):a;endsetsdata:c=100,80,70;b=500,450,300,550;a=9,8,6 5,4,7 8,3,2 7,6,4;enddatamax=sum(juece:c*x);for(ziyuan(i):sum(juece(j):a(i,j)*x(j)=b(i);集合段模型段數(shù)據(jù)段集合段以sets：開始，以endsets結(jié)束。給出下標(biāo)集合名稱，下標(biāo)范圍，以及與此

22、下標(biāo)有關(guān)的符號變量。數(shù)據(jù)段是以data：開始，enddata結(jié)束；注意向量都是行寫法，每個向量間用“；”隔開；注意矩陣的寫法，先行后列輸入方式，每行間回車，完畢用分號。模型段主要書寫目標(biāo)函數(shù)和約束函數(shù)，各行之間用分號隔開，變量默認(rèn)非負(fù)。25案例2 運輸問題 某部門有3個生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由4個銷售點（銷地）出售，各工廠的生產(chǎn)量、各銷售地的銷售量（單位：噸）以及各個工廠到各個銷售點的單位運價（元/噸）表示在下表中，要求研究產(chǎn)品如何調(diào)運，才能使得總運費最小。產(chǎn)地銷地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量814121426問題理解1什么叫

23、做一個完整的調(diào)運方案？2產(chǎn)地的總產(chǎn)量和銷售地的總銷售量的關(guān)系如何？3總運費與什么有關(guān)？4產(chǎn)地的調(diào)出量和銷地的銷售量應(yīng)該有什么限制？分析問題并建立模型設(shè)xij表示從第i產(chǎn)地調(diào)往第j銷地的調(diào)運量；i=1,2,3;j=1,2,3,4，cij表示從第i產(chǎn)地調(diào)往第j銷地的單位運費（運價）；ai表示第i產(chǎn)地的產(chǎn)量；bj表示第j銷地的銷量；y表示總運費。27A1A2A3B4B3B2B1a1a2a3b1b2b3b4x11x21x31x12x22x32x13x23x33x14x24x34運輸問題的網(wǎng)絡(luò)示意圖1 12 13 11xxxb1222322xxxb1323333xxxb1424344xxxb111213

24、141xxxxa212223242xxxxa313233343xxxxa28產(chǎn)地銷地B1B2B3B4產(chǎn)量A14(c11)12(c12)4(c13)11(c14)16(a1)A22(c21)10(c22)3(c23)9(c24)10(a2)A38(c31)5(c32)11(c33)6(c34)22(a3)銷量8(b1)14(b2)12(b3)14(b4)該問題的總產(chǎn)量等于總銷售量，所以有311,2,3,4ijjixbj411, 2, 3ijijxai3411ijijijyc x 每個銷地的銷量約束每個產(chǎn)地的產(chǎn)量約束各條可能路線運費總和即該運輸問題的數(shù)學(xué)模型為34113141min,1, 2,3,

25、 4.,1, 2,30,1, 2,3;1, 2,3, 4ijijijijjiijijijyc xxbjs txaixij 29運輸問題的進(jìn)一步討論1產(chǎn)銷不平衡產(chǎn)大于銷，即11mnijijab這時，數(shù)學(xué)模型為34113141min,1,2,3,4.,1,2,30,1,2,3;1,2,3,4ijijijijjiijijijyc xxbjstxa ixij30產(chǎn)小于銷，即11mnijijab34113141min,1,2,3,4.,1,2,30,1,2,3;1,2,3,4ijijijijjiijijijyc xxbjstxa ixij2計算程序編寫注意本問題所涉及的不同下標(biāo)范圍，不同下標(biāo)形式的字符變

26、量有哪些？單下標(biāo)和雙下標(biāo)的不同定義方式。a書寫集合段31單下標(biāo)集合有產(chǎn)地產(chǎn)量集合和銷地銷量集合，與這兩個集合有關(guān)的是運價和運量兩個集合，稱為派生集合（生成集合），或者稱為由產(chǎn)量集合和銷量集合組合成的笛卡爾集合，定義如下：endsetschanliang/1.3/:a;表示生成產(chǎn)量a(1),a(2),a(3);xiaoliang/1.4/:b；表示生成銷量b(1),b(2),b(3),b(4)值得注意的是，這里的1,2,3,4表示變量下標(biāo)自然順序，不因為書寫而改變。sets:chanliang/1,2,3/:a;xiaoliang/1,2,3,4/:b;yunjia(chanliang,xiao

27、liang):c,x;集合初始語句與前兩個變量的下標(biāo)都有關(guān)系的是運價和運量，所以，派生集合yunjia是雙下標(biāo)，第一個下標(biāo)是chanliang集合的下標(biāo)，第二下標(biāo)是xiaoliang集合的下標(biāo),決策變量x和價值系數(shù)c都與此集合下標(biāo)有關(guān)，表示為c(i,j),i=1,2,3;j=1,2,3,4;x(i,j),i=1,2,3;j=1,2,3,4。表示集合定義結(jié)束。注意，集合定義中，每個集合定義后，都用分號結(jié)束，每個集合有關(guān)的變量之間用逗號隔開。32b 書寫模型段3411maxijijijyc x 把所有的c(i,j)*x(i,j),求和，則用如下表達(dá)方式c(1,1)*x(1,1)+c(1,2)*x(

28、1,2)+c(1,3)*x(1,3)+c(1,4)*x(1,4)+c(3,1)*x(3,1)+c(3,4)*x(3,4)。min=sum(yunjia(i,j):c(i,j)*x(i,j);min=sum(yunjia:c*x);對yunjia集合中每個元素(i,j),對c(i,j)*x(i,j)求和，表示如果對每對下標(biāo)都求和，則上述兩種表達(dá)方式一樣。333141,1,2,3,4,1,2,3ijjiijijxbjxa i對每個銷地，所有產(chǎn)地運來的貨物量恰好等于銷售量：for(xiaoliang(j):sum(chanliang(i):x(i,j)=b(j);對每個產(chǎn)地，運出的貨物量總合恰好等于

29、該產(chǎn)地的產(chǎn)量：for(chanliang(i):sum(xiaoliang(j):x(i,j)=a(i);34產(chǎn)地銷地B1B2B3B4產(chǎn)量A14(c11)12(c12)4(c13)11(c14) 16(a1)A22(c21)10(c22)3(c23)9(c24)10(a2)A38(c31)5(c32)11(c33)6(c34)22(a3)銷量8(b1)14(b2)12(b3)14(b4)data:a=16,10,22;B=8,14,12,14;C=4,12,4,11 2,10,3,9 8,5,11,6;enddata35sets:chanliang/1.3/:a;xiaoliang/1.4/:

30、b;yunjia(chanliang,xiaoliang):c,x;endsetsmin=sum(yunjia:c*x);for(chanliang(i):sum(xiaoliang(j):x(I,j)=a(i);for(xiaoliang(j):sum(chanliang(i):x(I,j)=b(j);data:a=16,10,22;B=8,14,12,14;C=4,12,4,11 2,10,3,9 8,5,11,6;enddata程序組合及調(diào)試：注意：這三個模塊，在lingo中放置與順序無關(guān)。且，lingo讀取程序與字母大小寫無關(guān)。如果是產(chǎn)銷不平衡，把某些=改成，即可。36sets:cha

31、nliang/1.3/:a;xiaoliang/1.4/:b;yunjia(chanliang,xiaoliang):c,x;endsetsdata:a=16,10,22;B=8,14,12,14;C=4,12,4,11 2,10,3,9 8,5,11,6;enddatamin=sum(yunjia:c*x);for(chanliang(i):sum(xiaoliang(j):x(I,j)=a(i);for(xiaoliang(j):sum(chanliang(i):x(I,j)=b(j);37 Global optimal solution found at iteration: 6 Obj

32、ective value: 244.0000 Variable Value Reduced Cost X( 1, 1) 4.000000 0.000000 X( 1, 2) 0.000000 2.000000 X( 1, 3) 12.00000 0.000000 X( 1, 4) 0.000000 0.000000 X( 2, 1) 4.000000 0.000000 X( 2, 2) 0.000000 2.000000 X( 2, 3) 0.000000 1.000000 X( 2, 4) 6.000000 0.000000 X( 3, 1) 0.000000 9.000000 X( 3,

33、2) 14.00000 0.000000 X( 3, 3) 0.000000 12.00000 X( 3, 4) 8.000000 0.00000038與運輸問題有關(guān)的進(jìn)一步思考：12該問題一般從生產(chǎn)銷售單位考慮，如果從運輸公司出發(fā)，會怎么樣？有這類現(xiàn)象嗎？那種場合會出現(xiàn)？ Variable Value Reduced Cost X( 1, 1) 4.000000 0.000000 X( 1, 2) 0.000000 2.000000觀察這組最優(yōu)解，如果想要直接從產(chǎn)地1運輸貨物到銷地2，應(yīng)該有什么政策？如何實施。3如果運送的貨物有若干種類，怎么辦？這些貨物有些可以混合運輸，有些則不能混合運送，

34、怎么辦？如果有不同的交通運輸工具怎么分配？如果貨物有運輸時間限制，怎么辦？壟斷39案例3 貨物裝載問題 一艘輪船分前、中、后三個艙位，它們的容積與最大允載重量如表1。現(xiàn)有三種貨物待運，已知有關(guān)數(shù)據(jù)列在表2。又為了安全，前、中、后的實際載重量大體保持各艙最大允許載重量的比例關(guān)系。具體要求：前、后艙分別與中艙之間的載重量比例上偏差不超過15%，前、后艙之間不超過10%。問輪船應(yīng)裝載A、B、C各多少件才能使運費收入最大？表1 三艙的允載重量與體積約束 前 艙中 艙后 艙最大允載重量（t）容 積（m3）2000 4000300054001500150040表2 三種貨物的數(shù)量指標(biāo) 問題理解1一個完整的

35、貨物裝載方案是什么？2如何理解“為了安全，前、中、后的實際載重量大體保持各艙最大允許載重量的比例關(guān)系。”41建立模型設(shè)xij表示第i種商品裝入第j 艙的件數(shù)，其中，i=1,2,3表示A、B、C三種商品；j=1,2,3表示前、中、后三個艙位。商品參數(shù)符合變量：ai表示第i商品的數(shù)量上限；i=1,2,3vi表示第i商品的單位體積；wi表示第i商品的單位重量；pi表示第i商品的運輸單價；船的裝載參數(shù)約束：uj表示第j 艙位的體積上限；mj表示第j 艙位的重量上限；J=1,2,3;艙位間的重量比利系數(shù)：t1表示中艙與前、后艙位的載重比利系數(shù)；t2表示前后艙位之間載重比利系數(shù)。423311max()ii

36、jijypx31,1,2,3ijijxa is.t31,1,2,3iijjiwxmj311,2,3i ijjivxuj3321113210.15iiiiiiiiiw xw xw x裝入三個艙位的商品帶來的總運費。裝入的每種商品的總件數(shù)不超過商品總數(shù)。每個艙位，裝入的三種商品重量總和不超過艙位最大載重量。每個艙位，裝入的三種商品總體積不超過艙位最大體積容量。前艙的實際載重量和中艙的實際載重量的偏差不超過0.15%3321113213332121113321110.150.150.85iiiiiiiiiiiiiiiiiiiiiiiiw xw xw xw xw xw xw xw x3321110.8

37、5iiiiiiwxwx433323113210.15iiiiiiiiiw xw xw x3313113110.10iiiiiiiiiw xw xw x后艙載重量與中艙載重量的偏差不超過0.15后艙與前艙載重量的偏差不超過10%。0,1,2,3;1,2,3ijxij3323110.85iiiiiiw xw x3313110.90iiiiiiwxwx44計算程序sets:shangpin/1.3/:a,w,v,p;cangwei/1.3/:u,m;fenpei(shangpin,cangwei):x;endsetsdata:a=600,1000,800;v=10,5,7;w=8,6,5;p=100

38、0,700,600;m=2000,3000,1500;u=4000,5400,1500;t1=0.15;t2=0.10;enddata45max=sum(shangpin(i):p(i)*sum(cangwei(j):x(i,j);for(shangpin(i):sum(cangwei(j):x(i,j)=a(i);for(cangwei(j):sum(shangpin(i):w(i)*x(i,j)=m(j);for(cangwei(j):sum(shangpin(i):v(i)*x(i,j)=u(j);(1-t1)*sum(shangpin(i):w(i)*x(i,2)=sum(shangp

39、in(i):w(i)*x(i,1);(1-t1)*sum(shangpin(i):w(i)*x(i,2)=sum(shangpin(i):w(i)*x(i,3);(1-t2)*sum(shangpin(i):w(i)*x(i,1)=sum(shangpin(i):w(i)*x(i,3);46 Global optimal solution found at iteration: 5 Objective value: 608921.6 Variable Value Reduced Cost X( 1, 1) 208.3333 0.000000 X( 1, 2) 220.5882 0.000000

40、 X( 1, 3) 75.00000 0.000000 X( 2, 1) 0.000000 50.00000 X( 2, 2) 0.000000 50.00000 X( 2, 3) 150.0000 0.000000 X( 3, 1) 0.000000 25.00000 X( 3, 2) 0.000000 25.00000 X( 3, 3) 0.000000 40.0000047特別注意，模型在lingo中的輸入方式：3311max()iijijypxMax=sum(shangpin(i):p(i)*sum(cangwei(j):x(i,j);3321110.85iiiiiiw xw x0.8

41、5*sum(shangpin(i):w(i)*x(i,2)=sum(shangpin(i):w(i)*x(i,1);0.85*sum(fenpei(i,j)|j#eq#2:w(i)*x(i,j)=sum(shangpin(i)|j#eq#1:w(i)*x(i,j);48優(yōu)化軟件介紹Lingo的優(yōu)化軟件的使用方法Lingo安裝完成，啟動后，可以看到如下界面49 +(加法） -（減法） *（乘法） /(除法）(乘冪）#AND#(與) #OR#(或) #NOT#(非) #EQ#(等于) #NE#(不等于) #GT#(大于) #GE#(大于等于) #LT#(小于) #LE#(小于等于) (=)大于等于

42、算術(shù)運算符號邏輯運算符號 邏輯運算的結(jié)果只有“真”（TRUE)和“假”（FALES)，lingo用1表示True,其它的都是False。關(guān)系運算符號在lingo程序下字母的大小寫是沒有區(qū)別的Lingo8.0的基本運算符號50常見運算函數(shù)abs cos exp floor(取整） lgm(自變量的gama函數(shù)的自然對數(shù)） smax(list)（返回列數(shù)的最大值） smin sin tan sign(示性函數(shù)）變量約束函數(shù)gin（取整約束） bin（0-1變量約束） free（自由變量約束） bnd（上下界約束函數(shù)） Lingo基本函數(shù)51function(setname(set_index_li

43、st)|condition：expression_list);集合循環(huán)函數(shù) for對集合setname的每個元素獨立生成約束，約束由expression_list描述。max、min、sum依次返回集合setname上的表達(dá)式的最大值、最小值、和。0.85*sum(fenpei(i,j)|j#eq#2:w(i)*x(i,j)=sum(shangpin(i)|j#eq#1:w(i)*x(i,j); 其中，function是集合函數(shù)名，有for,max,min,sum四種；setname是集合名；set_index_list是集合索引列表；condition是邏輯表達(dá)式描述的條件；expressi

44、on_list是一個表達(dá)式 ，對for函數(shù)可以有一組表達(dá)式 。 52for(jihe1(i)|i#LE#5#and#i#GE#2:x(i)=2); 利用sets建立一個序列的下標(biāo)集合，這個問題就是建立了x1-x6,y1-y7這13個變量，Z11-z67由前面兩個集合的下標(biāo)共同生成了42個變量。由sets:開始，endsets結(jié)束。sets:jihe1/1.6/:x;jihe2/1.7/:y;link(jihe1,jihe2):z;endsets表示的意義為5,4,3,22ixi基本運算、集合、函數(shù)的表達(dá)53sum(jihe2(j)|j#NE#3:y(j)=4;for(jihe1(k)|k#GE

45、#2:gin(x);for(jihe1:bnd(1,x,10)）;for(jihe2:bnd(0,y,20);表示3471jyjj表示xk取整數(shù)，yk取0-1變量，k2表示對所有i，xi滿足 1 xi10 對所有j，yj滿足 0 yi20 for(jihe2(k)|k#GE#2:bin(y);54求和的表達(dá)ax101ii51i84jijijxcwminsets:subnb/1.10/:x;endsetssum(subnb(i):x(i)=a;sets:subnb1/1.5/:;subnb2/4,5,6,7,8/:;link(subnb1,subnb2):c,x;endsetsMin=sum(l

46、ink(i,j):c(i,j)*x(i,j);或?qū)懗蒑in=sum(link:c*x);55寫出下列l(wèi)ingo程序表示的意義sets:sub1/1.5/:x,y;sub2/3,4,5,9/:z;link(sub1,sub2):p,q;endsetsmax=sum(link:p*q+10);for(sub2(i)|i#ne#4:z(i)=3;y(j)=3);for(link(i,j):x(i)*z(j)=10-p(i,j);y(i)*Z(j)0;建立模型333111maxiiiiiiiiizc xe xd ys.t311, 2, 3ijijif xbj661,2,3iixy Mi其中，M為產(chǎn)品的

47、最大產(chǎn)量，根據(jù)問題，產(chǎn)品的最大產(chǎn)量不超過100件，故設(shè)M=100；0,11,2,3iyi0,1, 2, 3ixi計算程序：sets:ziyuan/1.3/:b;chanpin/1.3/:c,x,y,d,e;link(chanpin,ziyuan):f;endsetsdata:b=500,300,100;c=8,10,12;e=4,5,6;d=100,150,200;f=2,2,1 4,3,2 8,4,3;M=100;enddata67max=sum(chanpin:c*x)-sum(chanpin:e*x)-sum(chanpin:d*y);for(ziyuan(j):sum(chanpin(

48、i):f(i,j)*x(i)=b(j);for(chanpin:x=M*y);for(chanpin:bin(y); Global optimal solution found at iteration: 4 Objective value: 300.0000 Variable Value Reduced Cost X( 1) 100.0000 0.000000 X( 2) 0.000000 0.000000 X( 3) 0.000000 1.500000 Y( 1) 1.000000 -50.00000 Y( 2) 0.000000 150.0000 Y( 3) 0.000000 200.0

49、000計算結(jié)果： 根據(jù)計算結(jié)果，只需要安排生產(chǎn)第1種產(chǎn)品，可以獲得最大利潤300。68案例6 混合配料問題 某糖果廠用原料A，B，C加工成三種不同牌號的糖果甲、乙、丙。已知各種牌號糖果中A，B，C含量、原料成本、各種原料的每月限制用量、三種牌號糖果的單位加工費及售價如下表所示。問該廠每月生產(chǎn)這三種牌號的糖果各多少kg，使該廠獲利最大。試建立這個問題的線性規(guī)劃的數(shù)學(xué)模型。69分析問題設(shè)xi表示第i種糖果的產(chǎn)量(kg)，i=1,2,3;yij表示第i種糖果中原料j的含量；i=1,2,3,j=1,2,3qi表示每種糖果的加工費；pi表示每種糖果的售價；dj表示每種原料的單價；bj表示每種原料的每月限

50、用量；cij表示第i種糖果中原料j的含量要求（%）。7033331111max()iiiijijiijizp xq xdys.t31,1, 2,3iijjxyi31,1, 2,3ijjiybj1,2,3;1,2ijijiycijx,1,2,3;3ijijiycijx0,1,2,3;1,2,3ijyij71max=sum(tangguo:p*x)-sum(tangguo:q*x)-sum(yuanliao(j):d(j)*sum(tangguo(i):y(i,j);for(tangguo(i):x(i)=sum(yuanliao(j):y(i,j);for(yuanliao(j):sum(tan

51、gguo(i):y(i,j)=x(i)*c(i,j);for(link(i,j)|j#ge#3:y(i,j)=c(j);sum(moshi:y)=3;for(moshi:x/100=y);for(moshi:y=c(j);for(moshi(i):16=sum(yonghu(j):b(j)*x(i,j);for(moshi(i):sum(yonghu(j):b(j)*x(i,j)=c(j);for(moshi(i):sum(yonghu(j):b(j)*x(i,j)=16);for(moshi(i):sum(yonghu(j):b(j)*x(i,j)=19);for(link:gin(x);f

52、or(moshi:gin(y);for(moshi:y=15);for(link:x=3);在解決第1個問題基礎(chǔ)上，增加這兩個條件，計算收斂速度快10倍。否則，可能存不可行。這個上界不宜太小，也不宜太大！89 Global optimal solution found at iteration: 4862 Objective value: 0.000000 Variable Value Reduced Cost Y( 1) 14.00000 0.000000 Y( 2) 15.00000 0.000000 Y( 3) 11.00000 0.000000 X( 1, 1) 2.000000 0.

53、2596895E-07 X( 1, 2) 1.000000 0.000000 X( 1, 3) 1.000000 0.1517287E-06 X( 2, 2) 1.000000 0.000000 X( 2, 3) 1.000000 0.1067591E-06 X( 2, 4) 1.000000 0.4043221E-07 X( 3, 1) 2.000000 0.000000 X( 3, 2) 1.000000 0.000000 X( 3, 3) 1.000000 0.00000090航班編排問題 某航空公司經(jīng)營A，B，C三個城市的航線，這些航線每天班次起飛與到達(dá)時間如下表所示。 設(shè)飛機在機場停留的損失費大致與停留時間的平方成正比，又每架飛機從降落到下班起飛至少需2小時準(zhǔn)備時間，試決定一個使停留費用損失為最小的分派飛行方案。航班號 起飛城市 起飛時間 到達(dá)城市 到達(dá)時間101 A 9：00 B 12：00102 A