整數(shù)規(guī)劃的課程設計

1、<p>　　《實用運籌學》課程設計</p><p>　　整數(shù)規(guī)劃問題及其應用</p><p>　　院（系）名稱 信息工程學院 </p><p>　　專 業(yè) 班 級 10普本信計一班 </p><p>　　學 號 </p><p&g

2、t;　　學 生 姓 名 </p><p>　　指 導 教 師 </p><p>　　2013 年 06 月 16日</p><p><b>　　課程設計任務書</b></p><p>　　2012—2013學年第二學期</p><p>

3、　　課程設計名稱： 實用運籌學 </p><p>　　設計題目： 整數(shù)規(guī)劃問題及其應用 </p><p>　　完成期限：自 2013 年 06月 10 日至2013年06 月16日共 7天</p><p>　　設計依據(jù)、要求及主要內(nèi)容：</p><p>　　一、設計目的

4、 </p><p>　　熟練掌握整數(shù)規(guī)劃問題的基本原理以及整數(shù)規(guī)劃的求解方法、0-1整數(shù)規(guī)劃的求解方法，以及關(guān)于這些方法的分析和綜合應用，并應用LINGO軟件得到了結(jié)果，并對結(jié)果進行分析.以學習更多的運籌學知識. </p><p>　　二、設計內(nèi)容

5、 </p><p>　?。?）詳細介紹整數(shù)規(guī)劃問題產(chǎn)生的背景及求解方法．（2）運用運籌學知識，編寫整數(shù)規(guī)劃數(shù)學模型.（3）運用LINGO軟件，對模型進行求解，并對結(jié)果進行分析. &l

6、t;/p><p>　　三、設計要求 </p><p>　　1．介紹整數(shù)規(guī)劃問題產(chǎn)生的背景及求解整數(shù)規(guī)劃問題的各種算法． </p>&l

7、t;p>　　2．學會使用LINGO軟件，求解實際的運籌學問題. </p><p>　　3．熟練掌握運籌學求解實際問題的步驟，并進行結(jié)果分析. </p><p>　　計劃答辯時間：2013年 06 月 16 日</p>

8、;<p>　　工作任務與工作量要求： </p><p>　　查閱文獻資料不少于3篇，課程設計報告1篇不少于3000字．</p><p>　　指導教師（簽字）： 教研室主任（簽字）： </p><p>　　批準日期： 2013 年 06 月 09 日</p><p>　　整數(shù)規(guī)

9、劃問題及其應用</p><p><b>　　摘 要</b></p><p>　　運籌學是運用代數(shù)學、統(tǒng)計學等現(xiàn)代應用數(shù)學的方法和技術(shù)，通過建立數(shù)學模型分析研究各種資源的運用、籌劃及相關(guān)決策等問題的一門新興學科。其目的是根據(jù)實際問題的具體要求，通過定量的分析與運算，對資源運用、規(guī)劃及其相關(guān)決策等問題作出綜合最有的合理安排，以使有限的資源發(fā)揮更大的效益或作用。LIN

10、GO是一款解決線性規(guī)劃、整數(shù)規(guī)劃、二次規(guī)劃的強大工具軟件，它的使用減少了大量的人工計算。在運籌學的研究中，LINGO如見扮演著重要的角色。</p><p>　　本文主要研究整數(shù)規(guī)劃，建立整數(shù)規(guī)劃數(shù)學模型，運用LINGO軟件求解整數(shù)規(guī)劃的最優(yōu)解，從而獲得最優(yōu)方案。很多實際問題中，變量的取值必須是整數(shù)。因此，整數(shù)規(guī)劃的模型對研究運籌學問題有重要的意義。</p><p>　　關(guān)鍵詞：運籌學，整數(shù)

11、規(guī)劃，LINGO，最優(yōu)解.</p><p><b>　　目 錄</b></p><p><b>　　1 前言1</b></p><p>　　2 整數(shù)規(guī)劃問題的理論基礎1</p><p>　　2.1分支定界法2</p><p>　　2.2 割平面法3<

12、/p><p>　　2.3 0-1整數(shù)規(guī)劃的數(shù)學模型4</p><p>　　3 整數(shù)規(guī)劃問題的LINGO求解方法6</p><p>　　3.1一般整數(shù)規(guī)劃的解法6</p><p>　　3.2一般0-1規(guī)劃的解法7</p><p><b>　　4 實例應用8</b></p>&

13、lt;p>　　4.1 一般整數(shù)規(guī)劃問題實例分析8</p><p>　　4.2 0-1整數(shù)規(guī)劃的實例分析12</p><p><b>　　總 結(jié)18</b></p><p><b>　　參考文獻18</b></p><p><b>　　1 前言 </b>

14、</p><p>　　整數(shù)規(guī)劃是指一類要求問題中的全部或一部分變量為整數(shù)的數(shù)學規(guī)劃。是近三十年來發(fā)展起來的、規(guī)劃論的一個分支. 整數(shù)規(guī)劃問題是要求決策變量取整數(shù)值的線性規(guī)劃或非線性規(guī)劃問題。</p><p>　　一般認為非線性的整數(shù)規(guī)劃可分成線性部分和整數(shù)部分，因此常常把整數(shù)規(guī)劃作為線性規(guī)劃的特殊部分。在線性規(guī)劃問題中，有些最優(yōu)解可能是分數(shù)或小數(shù)，但對于某些具體問題，常要求解答必須是整數(shù)。

15、例如，所求解是機器的臺數(shù)，工作的人數(shù)或裝貨的車數(shù)等。為了滿足整數(shù)的要求，初看起來似乎只要把已得的非整數(shù)解舍入化整就可以了。實際上化整后的數(shù)不見得是可行解和最優(yōu)解，所以應該有特殊的方法來求解整數(shù)規(guī)劃。在整數(shù)規(guī)劃中，如果所有變量都限制為整數(shù)，則稱為純整數(shù)規(guī)劃；如果僅一部分變量限制為整數(shù)，則稱為混合整數(shù)規(guī)劃。整數(shù)規(guī)劃的一種特殊情形是01規(guī)劃，它的變數(shù)僅限于0或1。</p><p>　　整數(shù)規(guī)劃是從1958年由R.E.戈

16、莫里提出割平面法之后形成獨立分支的 ，30多年來發(fā)展出很多方法解決各種問題。解整數(shù)規(guī)劃最典型的做法是逐步生成一個相關(guān)的問題，稱它是原問題的衍生問題。對每個衍生問題又伴隨一個比它更易于求解的松弛問題（衍生問題稱為松弛問題的源問題）。通過松弛問題的解來確定它的源問題的歸宿，即源問題應被舍棄，還是再生成一個或多個它本身的衍生問題來替代它。隨即 ，再選擇一個尚未被舍棄的或替代的原問題的衍生問題，重復以上步驟直至不再剩有未解決的衍生問題為止。目前

17、比較成功又流行的方法是分枝定界法和割平面法，它們都是在上述框架下形成的。</p><p>　　2 整數(shù)規(guī)劃問題的理論基礎</p><p>　　在整數(shù)規(guī)劃問題中，如果整數(shù)規(guī)劃的目標函數(shù)和約束條件都是線性的，則稱此問題為整數(shù)線性規(guī)劃問題. 目前所流行的求解整數(shù)規(guī)劃的方法，往往只適用于整數(shù)線性規(guī)劃.本文我們主要討論整數(shù)線性規(guī)劃問題.</p><p>　　整數(shù)線性規(guī)劃的一

18、般形式為</p><p><b>　?。?.1）</b></p><p>　　整數(shù)規(guī)劃求解方法總的思想是：松弛模型（2.1）中的約束條件（譬如去掉整數(shù)約束條件），使構(gòu)成易于求解的新問題——松弛問題（A），即</p><p><b>　?。ˋ） </b></p><p>　　如果問題（A）的最優(yōu)解

19、是原問題（2.1）的可行解，則就是原問題（2.1）的最優(yōu)解；否則，在保證不改變松弛問題（A）的可行性的條件下，修正松弛問題（A）的可行域（增加新的約束），變成新的問題（B），再求問題（B）的解，重復這一過程直到修正問題的最優(yōu)解在原問題（2.1）的可行域內(nèi)為止，即得到了原問題的最優(yōu)解.</p><p><b>　　2.1分支定界法</b></p><p>　　對有約束條

20、件的最優(yōu)化問題（其可行解為有限數(shù)）的可行解空間恰當?shù)剡M行系統(tǒng)搜索，這就是分枝與定界內(nèi)容.通常，把全部可行解空間反復地分割為越來越小的子集，稱為分枝；并且對每個子集內(nèi)的解集計算一個目標下界（對于最小值問題），這稱為定界.在每次分枝后，凡是界限不優(yōu)于已知可行解集目標值的那些子集不再進一步分枝，這樣，許多子集可不予考慮，這稱剪枝.這就是分枝定界法的主要思路.</p><p>　　分枝定界法可用于解純整數(shù)或混合的整數(shù)規(guī)劃

21、問題.在二十世紀六十年代初由Land Doig和Dakin等人提出.由于這方法靈活且便于用計算機求解，所以現(xiàn)在它已是解整數(shù)規(guī)劃的重要方法.目前已成功地應用于求解生產(chǎn)進度問題、旅行推銷員問題、工廠選址問題、背包問題及分配問題等.設有最大化的整數(shù)規(guī)劃問題，與它相應的線性規(guī)劃為問題，從解問題開始，若其最優(yōu)解不符合的整數(shù)條件，那么的最優(yōu)目標函數(shù)必是的最優(yōu)目標函數(shù)的上界，記作；而的任意可行解的目標函數(shù)值將是的一個下界.分枝定界法就是將的可行域分成

22、子區(qū)域再求其最大值的方法.逐步減小和增大，最終求到.</p><p>　　用分枝定界法求解整數(shù)規(guī)劃（最大化）問題的步驟為：</p><p>　　開始，將要求解的整數(shù)規(guī)劃問題稱為問題，將與它相應的線性規(guī)劃問題稱為問題.</p><p>　　1、解問題可能得到以下情況之一：</p><p>　?。?）沒有可行解，這時也沒有可行解，則停止．<

23、/p><p>　?。?）有最優(yōu)解，并符合問題的整數(shù)條件，的最優(yōu)解即為的最優(yōu)解，則停止.</p><p>　　（3）有最優(yōu)解，但不符合問題的整數(shù)條件，記它的目標函數(shù)值為.</p><p>　　2、用觀察法找問題的一個整數(shù)可行解，一般可取，試探，求得其目標函數(shù)值，并記作.以表示問題的最優(yōu)目標函數(shù)值；這時有</p><p><b>　　進行迭

24、代.</b></p><p>　　第一步：分枝，在的最優(yōu)解中任選一個不符合整數(shù)條件的變量，其值為，以表示小于的最大整數(shù).構(gòu)造兩個約束條件</p><p><b>　　和 </b></p><p>　　將這兩個約束條件，分別加入問題，求兩個后繼規(guī)劃問題和.不考慮整數(shù)條件求解這兩個后繼問題.</p><p>　　

25、定界，以每個后繼問題為一分枝標明求解的結(jié)果，與其它問題的解的結(jié)果中，找出最優(yōu)目標函數(shù)值最大者作為新的上界.從已符合整數(shù)條件的各分支中，找出目標函數(shù)值為最大者作為新的下界，若無作用.</p><p>　　第二步：比較與剪枝，各分枝的最優(yōu)目標函數(shù)中若有小于者，則剪掉這枝，即以后不再考慮了.若大于，且不符合整數(shù)條件，則重復第一步驟.一直到最后得到為止.得最優(yōu)整數(shù)解.</p><p><b&

26、gt;　　2.2 割平面法</b></p><p>　　用割平面法求解整數(shù)規(guī)劃的基本思路是：先不考慮整數(shù)約束條件，求松弛問題的最優(yōu)解，如果獲得整數(shù)最優(yōu)解，即為所求，運算停止.如果所得到最優(yōu)解不滿足整數(shù)約束條件，則在此非整數(shù)解的基礎上增加新的約束條件重新求解.這個新增加的約束條件的作用就是去切割相應松弛問題的可行域，即割去松弛問題的部分非整數(shù)解(包括原已得到的非整數(shù)最優(yōu)解).而把所有的整數(shù)解都保留下來

27、，故稱新增加的約束條件為割平面.當經(jīng)過多次切割后，就會使被切割后保留下來的可行域上有一個坐標均為整數(shù)的頂點，它恰好就是所求問題的整數(shù)最優(yōu)解.即切割后所對應的松弛問題，與原整數(shù)規(guī)劃問題具有相同的最優(yōu)解.</p><p>　　割平面法的基本步驟：(1)先不考慮變量的取整約束，用單純形法求解相應的線性規(guī)劃問題，如果該問題沒有可行解或最優(yōu)解已是整數(shù)則停止，否則轉(zhuǎn)下步. </p><p>　　在求解

28、相應的線性規(guī)劃時，首先要將原問題的數(shù)學模型進行標準化.這里的“標準化”有兩個含義：第一是將所有的不等式約束全部轉(zhuǎn)化成等式約束，這是因為要采用單純形表進行計算的緣故.第二是將整數(shù)規(guī)劃中所有非整數(shù)系數(shù)全部轉(zhuǎn)換成整數(shù)，這是出于構(gòu)造“切割不等式”的需要. </p><p>　　(2)求一個“切割不等式”及添加到整數(shù)規(guī)劃的約束條件中去，即對上述線性規(guī)劃問題的可行域進行“切割”，然后返回步驟1. </p>&l

29、t;p>　　2.3 0-1整數(shù)規(guī)劃的數(shù)學模型</p><p>　　如果整數(shù)規(guī)劃中的所有決策變量僅限于取或兩個值，則稱此問題為0-1整數(shù)規(guī)劃，簡稱0-1規(guī)劃.其變量稱為0-1變量，或二進制變量.相應的決策變量的取值約束變?yōu)榛?，等價于和，且為整數(shù).線性規(guī)劃的一般模型為</p><p><b>　?。?.2）</b></p><p>　　2.3

30、.1 0-1規(guī)劃的求解方法</p><p>　　1、 0-1規(guī)劃的隱枚舉法</p><p>　　0-1整數(shù)規(guī)劃模型的解法一般為顯枚舉法（窮舉法）或隱枚舉法.窮舉法指的是對決策變量 的的每一個或值，均比較其目標函數(shù)值的大小，以從中求出最優(yōu)解．這種方法一般適用于決策變量個數(shù)較小的情況，當較大時，由于個、的可能組合數(shù)為，故此時即便用計算機進行窮舉來求最優(yōu)解，也幾乎是不可能的．求解0-1整數(shù)規(guī)劃

31、問題的解法均是隱枚舉法或稱為部分枚舉法．隱枚舉法是增加了過濾條件的一類窮舉法．</p><p>　　2、 指派問題的匈牙利方法</p><p>　　指派問題的模型：一般地，有項任務、個完成人，第人完成第項任務的代價為．為了求得總代價最小的指派方案，引入型變量，并令</p><p><b>　?。?.3）</b></p><p

32、>　　這樣，問題的數(shù)學模型可寫成</p><p><b>　?。?.4）</b></p><p>　　可見指派問題是型整數(shù)規(guī)劃的特例．</p><p>　　匈牙利算法的基本步驟為：</p><p>　　步驟1 對效益矩陣進行變換，使每行每列都出現(xiàn)0元素．</p><p>　　(1)從效益

33、矩陣c中每一行減去該行的最小元素；</p><p>　　(2)再在所得矩陣中每一列減去該列的最小元素，所得矩陣記為D一(d.)..</p><p>　　步驟2將矩陣D中0元素置為1元素，非零元素置為0元素，記此矩陣為E．</p><p>　　步驟3確定獨立1元素組．</p><p>　　(1)在矩陣E含有1元素的各行中選擇1元素最少的行，比較

34、該行中各1元素所在的列中1元素的個數(shù)，選擇1元素的個數(shù)最少的一列的那個1元素；</p><p>　　(2)將所選的1元素所在的行和列清0；</p><p>　　(3)重復第2步和第3步，直到?jīng)]有1元素為止，即得到一個獨立1元素組．</p><p>　　步驟4 判斷是否為最大獨立1元素組．</p><p>　　(1)如果所得獨立1元素組是原效益

35、矩陣的最大獨立1元素組(即1元素的個數(shù)等于矩陣的階數(shù))，則已得到最優(yōu)解，停止計算．</p><p>　　(2)如果所得獨立1元素組還不是原效益矩陣的最大獨立1元素組，那么利用尋找可擴路的方法對其進行擴張，進行下一步．</p><p>　　步驟5 利用尋找可擴路方法確定最大獨立1元素組．</p><p>　　(1)做最少的直線覆蓋矩陣D的所有0元素；．</p&g

36、t;<p>　　(2)在沒有被直線覆蓋的部分找出最小元素，在沒有被直線覆蓋的各行減去此最小元素，在沒被直線覆蓋的各列加上此最小元素，得到一個新的矩陣，返回第2步．</p><p>　　3 整數(shù)規(guī)劃問題的LINGO求解方法</p><p>　　LINGO可以用于求解非線性規(guī)劃，也可以用于一些線性和非線性方程組的求解等，功能十分強大，是求解優(yōu)化模型的最佳選擇.目前，利用LING

37、O軟件求解整數(shù)規(guī)劃問題是一種比較有效的方法.</p><p>　　3.1一般整數(shù)規(guī)劃的解法</p><p>　　一般的整數(shù)規(guī)劃模型程序如下：</p><p><b>　　MODEL:</b></p><p><b>　　sets:</b></p><p>　　num_i/1.

38、.m/:b;</p><p>　　num_j/1..n/:x,c;</p><p>　　link(num_i,num_j):a;</p><p><b>　　endsets</b></p><p><b>　　data:</b></p><p>　　b=b(1),b(2),.

39、..b(m);</p><p>　　c=c(1),c(2),...c(n);</p><p>　　a=a(1,1),a(1,2),...,a(1,n),</p><p>　　a(2,1),a(2,2),...,a(2,n),</p><p><b>　　...</b></p><p>　　a(m,

40、1),a(m,2),...,a(m,n);</p><p><b>　　enddata</b></p><p>　　[OBJ]max=@sum(num_j(j):c(j)*x(j));</p><p>　　@for(num_i(i):@sum(num_j(j):a(i,j)*x(j))<=b(i););</p><p&

41、gt;　　@for(num_j(j):x(j)>=0;);</p><p>　　@for(num_j(j):@GIN(x(j)););</p><p><b>　　END</b></p><p>　　3.2一般0-1規(guī)劃的解法</p><p>　　針對一般的規(guī)劃模型編寫LINGO程序，在這里仍假設目標函數(shù)為最大化問

42、題，約束條件都為“小于等于”的情況．</p><p><b>　　具體程序如下：</b></p><p><b>　　MODEL</b></p><p><b>　　sets:</b></p><p>　　num_i/1..m/:b;</p><p>　

43、　num_j/1..n/:x,c;</p><p>　　link(num_i,num_j):a;</p><p><b>　　endsets</b></p><p><b>　　data:</b></p><p>　　b=b(1),b(2),...,b(m);</p><p>

44、;　　c=c(1),c(2),...,c(n);</p><p>　　a=a(1,1),a(1,2),...,a(1,n),</p><p>　　a(2,1),a(2,2),...,a(2,n),</p><p><b>　　...</b></p><p>　　a(m,1),a(m,2),...,a(m,n);</

45、p><p><b>　　enddata</b></p><p>　　[OBJ]max=@sum(num_j(j):c(j)*x(j));</p><p>　　@for(num_i(i):@sum(num_j(j):a(i,j)*x(j))<=b(i););</p><p>　　@for(num_j(j):@sumBIN

46、(x(j)););</p><p><b>　　END</b></p><p><b>　　4 實例應用</b></p><p>　　4.1 一般整數(shù)規(guī)劃問題實例分析</p><p><b>　　例、連續(xù)投資問題</b></p><p>　　某公司現(xiàn)

47、有資金10萬元,擬在今后五年內(nèi)考慮用于下列項目的投資:</p><p>　　項目A:從第一年到第四年每年年初需要投資,并于次年收回本利115%,但要求第一年投資最低金額為4萬元,第二.三.四年不限.</p><p>　　項目B:第三年初需要投資,到第五年末能收回本利128%,但規(guī)定最低投資金額為3萬元,最高金額為5萬元.</p><p>　　項目C:第二年初需要投資

48、,到第五年末能收回本利140%,但規(guī)定其投資金額或為2萬元,或為4萬元,或為6萬元,或為8萬元.</p><p>　　項目D:五年內(nèi)每年年初都可購買公債,于當年末歸還,并獲利6%,此項目投資金額不限.</p><p>　　試問該公司應圖和確定這些項目的每年投資金額,使到第五年末擁有最大的資金收益.</p><p>　　(1) 為項目各年月初投入向量。</p&g

49、t;<p>　　(2) 為 i 種項目j年的月初的投入。</p><p>　　(3) 向量c中的元素為i年末j種項目收回本例的百分比。</p><p>　　(4) 矩陣A中元素為約束條件中每個變量的系數(shù)。</p><p>　　(5) Z為第5年末能擁有的資金本利最大總額。</p><p><b>　　因此目標函數(shù)為&l

50、t;/b></p><p>　　束條件應是每年年初的投資額應等于該投資者年初所擁有的資金.</p><p>　　第1年年初該投資者擁有10萬元資金,故有</p><p><b>　　.</b></p><p>　　第2年年初該投資者手中擁有資金只有,故有</p><p><b>　

51、　.</b></p><p>　　第3年年初該投資者擁有資金為從項目收回的本金: ,及從項目中第1年投資收回的本金: ,故有</p><p>　　同理第4年、第5年有約束為</p><p><b>　　,</b></p><p>　　max=1.15*x4a+1.28*x3b+1.4*x2c+1.06*x5d

52、;</p><p>　　x1a+x1d=100000;</p><p>　　-1.06*x1d+x2a+x2c+x2d=0;</p><p>　　-1.15*x1a-1.06*x2d+x3a+x3b+x3d=0;</p><p>　　-1.15*x2a-1.06*x3d+x4a+x4d=0;</p><p>　　-1.

53、15*x3a-1.06*x4d+x5d=0;</p><p>　　x2c=40000 ;</p><p>　　x2c=60000;</p><p>　　x2c=80000;</p><p>　　x2c=20000;</p><p>　　x3b>=30000;</p><p>　　x3b&l

54、t;=50000;</p><p>　　x1a>=0;x2a>=0;x3a>=0;x4a>=0;x5a>=0;</p><p>　　x1b>=0;x2b>=0;x3b>=0;x4b>=0;x5b>=0;</p><p>　　x1c>=0;x2c>=0;x3c>=0;x4c>=0;x5

55、c>=0;</p><p>　　x1d>=0;x2d>=0;x3d>=0;x4d>=0;x5d>=0;</p><p>　　Variable Value Reduced Cost</p><p>　　X4A 22900.00 0.000000</p>

56、<p>　　X3B 50000.00 0.000000</p><p>　　X2C 40000.00 0.000000</p><p>　　X5D 0.000000 0.000000</p><p>　　X1A 62264.15

57、 0.000000</p><p>　　X1D 37735.85 0.000000</p><p>　　X2A 0.000000 0.000000</p><p>　　X2D 0.000000 0.3036000E-01</p>

58、<p>　　X3A 0.000000 0.000000</p><p>　　X3D 21603.77 0.000000</p><p>　　X4D 0.000000 0.2640000E-01</p><p>　　X5A 0.000000

59、 0.000000</p><p>　　X1B 0.000000 0.000000</p><p>　　X2B 0.000000 0.000000</p><p>　　X4B 0.000000 0.000000</p>&l

60、t;p>　　X5B 0.000000 0.000000</p><p>　　X1C 0.000000 0.000000</p><p>　　X3C 0.000000 0.000000</p><p>　　X4C 0.000000

61、 0.000000</p><p>　　X5C 0.000000 0.000000</p><p>　　Row Slack or Surplus Dual Price</p><p>　　1 80000.00 1.000000</p><p>　

62、　2 0.000000 1.401850</p><p>　　3 0.000000 1.322500</p><p>　　4 0.000000 1.219000</p><p>　　5 0.000000 1.150000&l

63、t;/p><p>　　6 0.000000 1.060000</p><p>　　7 0.000000 -0.8388608E+18</p><p>　　8 -20000.00 -0.1280000E+10</p><p>　　9 -40

64、000.00 -0.1280000E+10</p><p>　　10 -20000.00 0.1280000E+10</p><p>　　11 20000.00 0.000000</p><p>　　12 0.000000 0.6100000E-0

65、1</p><p>　　13 62264.15 0.000000</p><p>　　14 0.000000 0.000000</p><p>　　15 0.000000 0.000000</p><p>　　16 229

66、00.00 0.000000</p><p>　　17 0.000000 0.000000</p><p>　　18 0.000000 0.000000</p><p>　　19 0.000000 0.000000</p>

67、<p>　　20 50000.00 0.000000</p><p>　　21 0.000000 0.000000</p><p>　　22 0.000000 0.000000</p><p>　　23 0.000000

68、 0.000000</p><p>　　24 40000.00 0.000000</p><p>　　25 0.000000 0.000000</p><p>　　26 0.000000 0.000000</p><p>　　27

69、 0.000000 0.000000</p><p>　　28 37735.85 0.000000</p><p>　　29 0.000000 0.000000</p><p>　　30 21603.77 0.000000&

70、lt;/p><p>　　31 0.000000 0.000000</p><p>　　32 0.000000 0.000000</p><p>　　4.2 0-1整數(shù)規(guī)劃的實例分析</p><p><b>　　例、消防站問題</b></p>

71、<p>　　某城市的消防總站將全市劃分為11個防火區(qū)，現(xiàn)有4個消防站，圖4-11給出的是該城市各防火區(qū)域和防火站的示意圖，其中1,2,3,4，表示消防站1，2，…11表示防火區(qū)域，根據(jù)歷史資料證實，各消防站可在事先規(guī)定允許的時間內(nèi)對所負責的區(qū)域內(nèi)的火災予以撲滅，圖中沒有虛線連接的就表示不負責，現(xiàn)在總部提出：能否減少消防站的數(shù)目，仍能保證負責各地區(qū)的防火任務？如果可以的話，應該關(guān)閉哪個？</p><p&g

72、t;　　某城市的消防站總部將全市劃分為11個防火區(qū)，現(xiàn)有四的。。。。。。</p><p>　　解：根據(jù)題意，用xi表示第i個消防站的關(guān)系的打開關(guān)閉情況</p><p>　　X=1； 第i個消防站不關(guān)閉</p><p>　　0； 第i個消防站關(guān)閉</p><p>　　用y代表第i個消防站到第j個防火區(qū)域的到達情況，0表示不可達，1表示可達，Y

73、=[1,1,1,1,0,1,1,1,0,0,0;</p><p>　　1,1,0,1,0,0,0,1,1,0,0;</p><p>　　0,0,0,1,1,1,0,0,0,0,1;</p><p>　　0,0,0,0,0,1,1,1,1,1,1;]</p><p>　　則問題可歸結(jié)為0—1整數(shù)規(guī)劃模型。</p><p>

74、;　　min z=sum x（i）;</p><p>　　St ： x（i）*y（i，j）>=1；j=1,2,3...11</p><p><b>　　x（i）<=3；</b></p><p><b>　　X=0或1</b></p><p><b>　　利用lingo求解<

75、;/b></p><p><b>　　model:</b></p><p><b>　　sets:</b></p><p>　　n_i/1..4/:x;</p><p>　　n_j/1..11/;</p><p>　　link(n_i,n_j):y;</p>

76、<p><b>　　endsets</b></p><p><b>　　data:</b></p><p>　　y=1,1,1,1,0,1,1,1,0,0,0,1,1,0,1,0,0,0,1,1,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,1,1,1,1,1,1;</p><p>

77、<b>　　enddata</b></p><p>　　[obj]min=@sum(n_i(i):x(i));</p><p>　　@for(n_j(j):@sum(n_i(i):x(i)*y(i,j))>=1;);</p><p>　　@for(n_j(j):@sum(n_i(i):x(i))<=3;);</p>&

78、lt;p>　　@for(n_i(i):@bin(x(i));x(i)>=0;);</p><p><b>　　end</b></p><p><b>　　運行結(jié)果：</b></p><p>　　Global optimal solution found.</p><p>　　Object

79、ive value: 3.000000</p><p>　　Extended solver steps: 0</p><p>　　Total solver iterations: 0</p><p&

80、gt;　　Variable Value Reduced Cost</p><p>　　X( 1) 1.000000 1.000000</p><p>　　X( 2) 0.000000 1.000000</p><p>　　X( 3) 1.00000

81、0 1.000000</p><p>　　X( 4) 1.000000 1.000000</p><p>　　Y( 1, 1) 1.000000 0.000000</p><p>　　Y( 1, 2) 1.000000 0.000000&

82、lt;/p><p>　　Y( 1, 3) 1.000000 0.000000</p><p>　　Y( 1, 4) 1.000000 0.000000</p><p>　　Y( 1, 5) 0.000000 0.000000</p><p>

83、;　　Y( 1, 6) 1.000000 0.000000</p><p>　　Y( 1, 7) 1.000000 0.000000</p><p>　　Y( 1, 8) 1.000000 0.000000</p><p>　　Y( 1, 9)

84、0.000000 0.000000</p><p>　　Y( 1, 10) 0.000000 0.000000</p><p>　　Y( 1, 11) 0.000000 0.000000</p><p>　　Y( 2, 1) 1.000000

85、 0.000000</p><p>　　Y( 2, 2) 1.000000 0.000000</p><p>　　Y( 2, 3) 0.000000 0.000000</p><p>　　Y( 2, 4) 1.000000 0.000000</p&g

86、t;<p>　　Y( 2, 5) 0.000000 0.000000</p><p>　　Y( 2, 6) 0.000000 0.000000</p><p>　　Y( 2, 7) 0.000000 0.000000</p><p>　　Y( 2

87、, 8) 1.000000 0.000000</p><p>　　Y( 2, 9) 1.000000 0.000000</p><p>　　Y( 2, 10) 0.000000 0.000000</p><p>　　Y( 2, 11) 0.000

88、000 0.000000</p><p>　　Y( 3, 1) 0.000000 0.000000</p><p>　　Y( 3, 2) 0.000000 0.000000</p><p>　　Y( 3, 3) 0.000000 0.00

89、0000</p><p>　　Y( 3, 4) 1.000000 0.000000</p><p>　　Y( 3, 5) 1.000000 0.000000</p><p>　　Y( 3, 6) 1.000000 0.000000</p><

90、;p>　　Y( 3, 7) 0.000000 0.000000</p><p>　　Y( 3, 8) 0.000000 0.000000</p><p>　　Y( 3, 9) 0.000000 0.000000</p><p>　　Y( 3, 10)

91、 0.000000 0.000000</p><p>　　Y( 3, 11) 1.000000 0.000000</p><p>　　Y( 4, 1) 0.000000 0.000000</p><p>　　Y( 4, 2) 0.000000

92、 0.000000</p><p>　　Y( 4, 3) 0.000000 0.000000</p><p>　　Y( 4, 4) 0.000000 0.000000</p><p>　　Y( 4, 5) 0.000000 0.000000<

93、;/p><p>　　Y( 4, 6) 1.000000 0.000000</p><p>　　Y( 4, 7) 1.000000 0.000000</p><p>　　Y( 4, 8) 1.000000 0.000000</p><p>　

94、　Y( 4, 9) 1.000000 0.000000</p><p>　　Y( 4, 10) 1.000000 0.000000</p><p>　　Y( 4, 11) 1.000000 0.000000</p><p>　　Row Slack or

95、Surplus Dual Price</p><p>　　OBJ 3.000000 -1.000000</p><p>　　2 0.000000 0.000000</p><p>　　3 0.000000 0.000000</p><

96、;p>　　4 0.000000 0.000000</p><p>　　5 1.000000 0.000000</p><p>　　6 0.000000 0.000000</p><p>　　7 2.000000 0.0

97、00000</p><p>　　8 1.000000 0.000000</p><p>　　9 1.000000 0.000000</p><p>　　10 0.000000 0.000000</p><p>　　11 0

98、.000000 0.000000</p><p>　　12 1.000000 0.000000</p><p>　　13 0.000000 0.000000</p><p>　　14 0.000000 0.000000</p>

99、<p>　　15 0.000000 0.000000</p><p>　　16 0.000000 0.000000</p><p>　　17 0.000000 0.000000</p><p>　　18 0.000000

100、 0.000000</p><p>　　19 0.000000 0.000000</p><p>　　20 0.000000 0.000000</p><p>　　21 0.000000 0.000000</p><p>　　

101、22 0.000000 0.000000</p><p>　　23 0.000000 0.000000</p><p>　　24 1.000000 0.000000</p><p>　　25 0.000000 0.00000

102、0</p><p>　　26 1.000000 0.000000</p><p>　　27 1.000000 0.000000</p><p><b>　　結(jié)果如下： </b></p><p>　　X= X=X=1，X=0；即應關(guān)閉2號消防站。<

103、;/p><p><b>　　總 結(jié)</b></p><p>　　經(jīng)過一周的時間，實用運籌學課程設計終于完成了．在這期間，我收獲了很多，也學到了很多.通過本次課程設計，我更深刻的體會到了運籌學的思維及精髓，學會了運用運籌學的思維思考問題，即：應用分析、試驗、量化的方法，對實際中的人、財、物等有限的資源進行統(tǒng)籌安排.對于整數(shù)規(guī)劃模型更加有了深刻的認識，并且學會了建立相關(guān)

104、模型求解實際問題，以得到想要的結(jié)果.并且在建立模型，求解模型的過程中也認識到了整數(shù)規(guī)劃的重要性，它也應用到了生活的方方面面.在使用LINGO軟件求解的同時，更加熟練的掌握了LINGO軟件，讓我能更好的使用LINGO軟件來求解實際問題.在以后的生活中，我應該學以致用來解決更多的問題.</p><p><b>　　參考文獻</b></p><p>　　[1] 韓中庚．實用

105、運籌學[M]．北京：清華大學出版社，2007．</p><p>　　[2] 謝金星. 薛毅．優(yōu)化建模LINGO/LINDO軟件[M]．北京：清華大學出版社，2005．</p><p>　　[3] 胡運權(quán)．運籌學基礎及其應用[M]．北京：高等教育出版社，2004．</p><p>　　[4] 周華任．運籌學解題指導[M]．北京：清華大學出版社，2006．</p&