數(shù)學建模題目

1、數(shù)學規(guī)劃在工程技術(shù)、經(jīng)濟管理、科學研究和日常生活等許多領(lǐng)域中，人們經(jīng)常遇到的一類決策問題是：在一系列客觀或主觀限制條件下，尋求使關(guān)注的某個或多個指標達到最大（或最?。┑臎Q策。例如，結(jié)構(gòu)設(shè)計要在滿足強度要求條件下選擇材料的尺寸，使其總重量最輕；資源分配要在有限資源約束下制定各用戶的分配數(shù)量，使資源產(chǎn)生的總效益最大；運輸方案要在滿足物資需求和裝載條件下安排從各供應(yīng)點到各需求點的運量和路線，使運輸總費用最低；生產(chǎn)計劃要按照產(chǎn)品工藝流程和顧客需求，制定原料、零件、部件等訂購、投產(chǎn)的日程和數(shù)量，盡量降低成本使利潤最高。上述這種決策問題通常稱為優(yōu)化問題。人們解決這些優(yōu)化問題的手段大致有以下幾種：1依賴過去

2、的經(jīng)驗判斷面臨的問題。這似乎切實可行，并且沒有太大的風險，但是其處理過程會融入決策者太多的主觀因素，常常難以客觀地加以描述，從而無法確認結(jié)果的最優(yōu)性。2做大量的試驗反復(fù)比較。這固然比較真實可靠，但是常要花費太多的資金和人力，而且得到的最優(yōu)結(jié)果基本上離不開開始設(shè)計的試驗范圍。用數(shù)學建模的方法建立數(shù)學規(guī)劃模型求解最優(yōu)決策。雖然由于建模時要作適當?shù)暮喕?，可能使得結(jié)果不一定完全可行或達到實際上的最優(yōu)，但是它基于客觀規(guī)律和數(shù)據(jù)，又不需要多大的費用，具有前兩種手段無可比擬的優(yōu)點。如果在次基礎(chǔ)上再輔之以適當?shù)慕?jīng)驗和試驗，就可以期望得到實際問題的一個比較圓滿的回答，是解決這種問題最有效、最常用的方法之一。在決

3、策科學化、定量化的呼聲日益高漲的今天，用數(shù)學建模方法求解優(yōu)化問題，無疑是符合時代潮流和形勢發(fā)展需要的。數(shù)學規(guī)劃模型一般有三個要素：一是決策變量，通常是該問題要求解的那些未知量，不妨用n維向量x=(x1,x2,xn)t表示；二是目標函數(shù)，通常是該問題要優(yōu)化（最小或最大）的那個目標的數(shù)學表達式，它是決策變量x的函數(shù)，這里抽象地記作 f(x)；三是約束條件，由該問題對決策變量的限制條件給出，即x允許取值的范圍x,稱可行域，常用一組關(guān)于x的不等式（也可以有等式）gi(x)0(i=1,2,m)來界定。一般地，這類模型可表示成如下形式：opt z=f(x) （1）s.t. gi(x)0 （2）這里opt(

4、optimize)是最優(yōu)化的意思，可以是求極小min(minimize)或求極大max(maximize)；s.t.(subject to)是“受約束于”的意思，滿足（2）式的解x稱為可行解，同時滿足（1）式，（2）式的解x*稱為最優(yōu)解。模型（1），（2）是微積分中多元函數(shù)的條件極值問題。當約束條件（2）比較簡單（如全為等式）時，多元微積分中介紹過求解析解的基本原理和方法，即令目標函數(shù)（對等式約束需要加上與其對應(yīng)的拉格朗日乘子的乘積項）的偏導(dǎo)數(shù)為零，求出駐點后再比較駐點上的函數(shù)值。但是，大多數(shù)實際問題歸結(jié)的上述形式的模型很難用這種方法求解，因為：第一，解析方法只能處理目標函數(shù)f和約束條件gi，

5、并且決策變量個數(shù)n，約束條件個數(shù)m比較小的情形，當f，gi稍微復(fù)雜時通常至少需要求解比較復(fù)雜的非線性方程（組），很難得到解析解；第二，當最優(yōu)解在可行域的邊界上取得時（不少實際問題正是如此），就不能用原有的求條件極值的方法求解，所以對于優(yōu)化問題的這類模型必須尋求有效的數(shù)值解法。當模型（1），（2）中決策變量x的所有分量xi( i =1,n)均為實數(shù)，且f,gi( i =1,m)都是線性函數(shù)時，稱為線性規(guī)劃。若f,gi至少有一個非線性函數(shù)，則稱為非線性規(guī)劃。若x至少有一個分量只取整數(shù)，則稱為整數(shù)規(guī)劃。線性規(guī)劃和非線性規(guī)劃是連續(xù)規(guī)劃，而整數(shù)規(guī)劃是離散優(yōu)化（組合優(yōu)化），它們統(tǒng)稱為數(shù)學規(guī)劃。本實驗指導(dǎo)書

6、包括數(shù)學規(guī)劃方面的兩個實驗：線性規(guī)劃，整數(shù)規(guī)劃。用lindo和lingo解線性規(guī)劃和整數(shù)規(guī)劃：lindo(linear interactive and discrete optimizer)和lingo(linear interactive and generai optimizer)是由美國芝加哥大學的linus schrage 于1986年開發(fā)的優(yōu)化計算軟件包，lindo可以用來求解線性規(guī)劃、線性整數(shù)規(guī)劃、二次規(guī)劃和整數(shù)二次規(guī)劃，而lingo除此之外還可以解非線性規(guī)劃和非線性整數(shù)規(guī)劃。從lindo公司的主頁（）上同學們可以了解更多的有關(guān)信息，并可以下載軟件的試用版。實驗一 線性規(guī)劃（lp）

7、1 實例及數(shù)學模型例1加工奶制品的生產(chǎn)計劃問題 一奶制品加工廠用牛奶生產(chǎn)a1、a2兩種奶制品，1桶牛奶可以在設(shè)備甲上用12小時加工成3公斤a1，或者在設(shè)備乙上用8小時加工成4公斤a2。根據(jù)市場需求，生產(chǎn)的a1、a2能全部售出，且每公斤a1獲利24元，每公斤a2獲利16元?，F(xiàn)在加工廠每天能得到50桶牛奶的供應(yīng)，每天正式工人總的勞動時間為480小時，并且設(shè)備甲每天至多能加工100公斤a1，設(shè)備乙的加工能力沒有限制。試為該廠制定一個生產(chǎn)計劃，使每天獲利最大，并進一步討論以下3個附加問題：1）若用35元可以購買到1桶牛奶，應(yīng)否作這項投資？若投資，每天最多購買多少桶牛奶？2）若可以聘用臨時工人以增加勞動

8、時間，付給臨時工人的工資最多是每小時幾元？3）由于市場需求變化，每公斤a1的獲利增加到30元，應(yīng)否改變生產(chǎn)計劃？數(shù)學模型 設(shè)每天用x1桶牛奶生產(chǎn)a1 ，用x2桶牛奶生產(chǎn)a2 目標函數(shù) 設(shè)每天獲利為z元。 x1桶牛奶可生產(chǎn)3x1公斤a1，獲利24*3x1，x2桶牛奶可生產(chǎn)4x2公斤a2，獲利16*4x2，故z=72x1+64x2約束條件 原料供應(yīng) 生產(chǎn)a1、a2的原料（牛奶）總量不超過每天的供應(yīng)50桶，即 x1+x250勞動時間 生產(chǎn)a1、a2的總加工時間不超過每天正式工人總的勞動時間480小時，即 12x1+8x2480設(shè)備能力 a1的產(chǎn)量不得超過設(shè)備甲每天的加工能力100小時，即 3x110

9、0非負約束 x1、x2均不能為負值，即x10，x20綜上所述可得max z=72x1+64x2 (1)s.t. x1+x250 (2)12x1+8x2480 (3)3x1100 (4)x10，x20 (5)顯然，目標函數(shù)和約束條件都是線性的，這是一個線性規(guī)劃（linear programming,lp），求出的最優(yōu)解將給出使凈利潤最大的生產(chǎn)計劃，要討論的問題需要考慮參數(shù)的變化對最優(yōu)解和影響，一般稱為敏感性（或靈敏度）分析。用lindo求解線性規(guī)劃 用lindi求解線性規(guī)劃(lp)時，首先在lindo軟件的模型窗口輸入一個lp模型，模型以max或min開始，按線性規(guī)劃問題的自然形式輸入（見下面例

10、子所示）。輸入結(jié)束時只需鍵入end。以下解加工奶制品的生產(chǎn)計劃問題：max z=72x1+64x2 (1)s.t. x1+x250 (2)12x1+8x2480 (3)3x1100 (4)x10，x20 (5)由于lindo中已假設(shè)所有的變量都是非負的，所以非負約束條件不必輸入；lindo也不區(qū)分變量中的大小寫字符（實際上任何小寫字符將被轉(zhuǎn)換為大寫字符）；約束條件中的“=”及“=”可用“”及“”代替。在lindo模型窗口輸入如下：max 72x1+64x2 st !說明：st以下為約束條件x1+x2<=50 12x1+8x2<=480 ！說明：一個約束條件分成兩行寫也沒關(guān)系3x1&

11、lt;=100end 用鼠標單擊菜單中的求解命令（solve）就可以得到解答，結(jié)果窗口顯示如下：lp optimum found at step2objective function value 1) 3360.000 variable value reduced cost x1 20.000000 0.000000 x2 30.000000 0.000000 row slack or surplus dual prices 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 no. iterations= 2一個問

12、題解答之后，lindo會詢問是否需要做敏感性分析（do range(sensitvity) analysis?）如果你不需要，應(yīng)回答”n”(n)。計算結(jié)果表明：“l(fā)p optimum found at step2”表示單純形法在兩次迭代（旋轉(zhuǎn)）后得到最優(yōu)解。“objective function value 1) 3360.000”表示最優(yōu)目標值為3360.000（lindo中將目標函數(shù)自動看作第1行，從第二行開始才是真正的約束條件）?！皏alue”給出最優(yōu)解中各變量（variable）的值：x1=20.000000，x2=30.000000?！皉educed cost”的含義是（對max型問

13、題）：基變量的reduced cost值為0，對于非基變量，相應(yīng)的reduced cost值表示當非基變量增加一個單位時（其它非基變量保持不變）目標函數(shù)減少的量。本例中兩個變量都是基變量?！皊lack or surplus”給出松弛（或剩余）變量的值，表示約束是否取等式約束；第2、第3行松弛變量均為0，說明對于最優(yōu)解而言，兩個約束均取等式約束；第4行松弛變量為40.000000，說明對于最優(yōu)解而言，這個約束取不等式約束?！癲ual prices”給出約束的影子價格（也稱為對偶價格）的值：第2、第3、第4行（約束）對應(yīng)的影子價格分別48.000000，2.000000，0.000000。“no.

14、 iterations= 2”表示用單純形法進行了兩次迭代（旋轉(zhuǎn)）。 如果對上面的“是否需要做敏感性分析”的詢問回答“y”（yes），則lindo還會輸出以下結(jié)果：ranges in which the basis is unchanged: obj coefficient ranges variable current allowable allowable coef increase decrease x1 72.000000 24.000000 8.000000 x2 64.000000 8.000000 16.000000 righthand side ranges row curre

15、nt allowable allowable rhs increase decrease 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 infinity 40.000000以上顯示的是當前最優(yōu)基（矩陣）保持不變的充分條件（ranges in which the basis is unchanged），包括目標函數(shù)中決策變量應(yīng)的系數(shù)的變化范圍（obj coefficient ranges）和約束的右端項的變化范圍（righthand side ranges）兩部分。例如：前一部分的輸出行x

16、1 72.000000 24.000000 8.000000表示決策變量x1當前在目標函數(shù)中對應(yīng)的系數(shù)為72，允許增加24和減少8。也就是說，當該系數(shù)在區(qū)間64，96上變化時（假設(shè)其它條件均不變），當前最優(yōu)基矩陣保持不變。對x2對應(yīng)的輸出行也可以類似地解釋。由于此時約束沒有任何改變，所以最優(yōu)基矩陣保持不變意味著最優(yōu)解不變（當然，由于目標函數(shù)中的系數(shù)發(fā)生變化，最優(yōu)值還是會變的）。后一部分的輸出行2 50.000000 10.000000 6.666667表示約束2當前右端項為50，允許增加10和減少6.666667。也就是說，當該系數(shù)在區(qū)間43.333333，60上變化時（假設(shè)其它條件均不變），

17、當前最優(yōu)基矩陣保持不變。對約束3、約束4對應(yīng)的輸出行也可以類似地解釋。由于此時約束已經(jīng)改變，雖然最優(yōu)基矩陣保持不變，最優(yōu)解和最優(yōu)值還是會變的。但是，由于最優(yōu)基矩陣保持不變，所以前面的“dual prices”給出的約束的影子價格此時仍然是有效的。用lindo求解加工奶制品的生產(chǎn)計劃，結(jié)果如下：20桶牛奶生產(chǎn)a1, 30桶生產(chǎn)a2，利潤3360元。1）35元可買到1桶牛奶，要買嗎？由于原料的影子價格為48，35 <48, 應(yīng)該買！2）聘用臨時工人付出的工資最多每小時幾元？ 由于工時的影子價格為2，聘用臨時工人付出的工資最多每小時2元3）a1獲利增加到 30元/千克，應(yīng)否改變生產(chǎn)計劃 由于要

18、使最優(yōu)解保持不變，x1系數(shù)的允許變化范圍為64，96。x1系數(shù)由24*3=72增加為30*3=90，在允許范圍內(nèi)。所以不改變生產(chǎn)計劃。用lindo求解lp問題時，應(yīng)注意以下幾個問題：1）模型以max或min開始定義目標函數(shù)（注意不需要等號）；目標函數(shù)及約束條件之間一定要有st或s.t或subject to或such that分開；end語句表示約束條件輸入結(jié)束。2）約束中>(或<)號與>=(或<=)功能相同.3)變量名不能超過8個字符,并且以字母開頭；變量名(包括lindo中的關(guān)鍵字也不區(qū)分大小寫)。4）變量與其系數(shù)間可以有空格（甚至回車），但不能有任何運算符號（如乘號

19、*等）。5）lindo不允許變量出現(xiàn)在一個約束條件的右端。6）lindo中不能接受括號“（ ）”和逗號“，”，例如：400(x1+x2)需寫為400x1+400x2等。7）表達式應(yīng)當已經(jīng)經(jīng)過化簡，如不能出現(xiàn)2x1+3x2+5x1,而應(yīng)寫為7x1+3x2等。8）lindo已假設(shè)所有變量非負?？稍趀nd語句后用free vname命令將變量vname的非負假設(shè)取消；還可以用sub，slb命令設(shè)定變量的上界、下界。9）lindo將目標函數(shù)所在行作為第一行，從第二行起為約束條件。行號自動產(chǎn)生，也可以人為定義行號或行名，行號或行名放在該行前面，以“）”結(jié)束。行名和變量名一樣，不能超過8個字符。10）li

20、ndo文件中常有注釋間雜于各命令之中，前面注有！符號。例如：this is a comment.11)在模型的任何地方都可以用title對模型命名或標識（最多72個字符），如： titlethis model is only an example例2自來水輸送鋼鐵、煤炭、水電等生產(chǎn)、生活物資從若干供應(yīng)點運送到一些需求點，怎樣安排輸送方案使運費最小，或者利潤最大? 各種類型的貨物裝箱，由于受體積、重量等的限制，如何相互搭配裝載，使獲利最高，或者裝箱數(shù)量最少? 本例將討論用數(shù)學規(guī)劃模型解決這類問題的方法.問題 某市有甲、乙、丙、丁四個居民區(qū)，自來水由a，b，c三個水庫供應(yīng). 四個區(qū)每天必須得到保證

21、的基本生活用水量分別為30，70，10，10千噸，但由于水源緊張，三個水庫每天最多只能分別供應(yīng)50，60，50千噸自來水. 由于地理位置的差別，自來水公司從各水庫向各區(qū)送水所需付出的引水管理費不同(見表1，其中c水庫與丁區(qū)之間沒有輸水管道)，其他管理費用都是450元千噸. 根據(jù)公司規(guī)定，各區(qū)用戶按照統(tǒng)一標準900元千噸收費此外，四個區(qū)都向公司申請了額外用水量，分別為每天50，70，20，40千噸該公司應(yīng)如何分配供水量，才能獲利最多? 引水管理費(元/千噸)甲乙丙丁a160130220170b140130190150c190200230/為了增加供水量，自來水公司正在考慮進行水庫改造，使三個水庫

22、每天的最大供水量都提高一倍，問那時供水方案應(yīng)如何改變? 公司利潤可增加到多少? 問題分析 分配供水量就是安排從三個水庫向四個區(qū)送水的方案，目標是獲利最多而從題目給出的數(shù)據(jù)看，a, b, c三個水庫的供水量160千噸，不超過四個區(qū)的基本生活用水量與額外用水量之和300千噸，因而總能全部賣出并獲利，于是自來水公司每天的總收入是900 ´ (50 + 60 + 50) = 144000元，與送水方案無關(guān). 同樣，公司每天的其它管理費用450 ´ (50 + 60 + 50) = 72000元也與送水方案無關(guān). 所以，要使利潤最大，只需使引水管理費最小即可. 另外，送水方案自然要受

23、三個水庫的供應(yīng)量和四個區(qū)的需求量的限制. 模型建立 很明顯，決策變量為a, b, c三個水庫(i = 1, 2, 3)分別向甲、乙、丙、丁四個區(qū)(j = 1, 2, 3, 4)的供水量. 設(shè)水庫i向j區(qū)的日供水量為xij，由于c水庫與丁區(qū)之間沒有輸水管道，即x34 = 0，因此只有11個決策變量. 由上分析，問題的目標可以從獲利最多轉(zhuǎn)化為引水管理費最少，于是有min z = 160x11 + 130x12 + 220x13 + 170x14 + 140x21 + 130x22 + 190x23 + 150x24 + 190x31 + 200x32 + 230x33 (1) 約束條件有兩類: 一

24、類是水庫的供應(yīng)量限制，另一類是各區(qū)的需求量限制. 由于供水量總能賣出并獲利，水庫的供應(yīng)量限制可以表示為x11 + x12 + x13 + x14 = 50 (2)x21 + x22 + x23 + x24 = 60 (3)x31 + x32 + x33 = 50 (4) 考慮到各區(qū)的基本生活用水量與額外用水量，需求量限制可以表示為30 £ x11 + x21 + x31 £ 80 (5)70 £ x12 + x22 + x32 £ 140 (6)10 £ x13 + x23 + x33 £ 30 (7)10 £ x14 +

25、x24 £ 50 (8) 模型求解 (1) (8)構(gòu)成一個線性規(guī)劃模型(當然要加上xij的非負約束). 輸入lindo求解，得到如下輸出:objective function value1) 2440000 variable value reduced cost x11 0.000000 30.000000 x12 50.000000 0.000000 x13 0.000000 50.000000 x14 0.000000 20.000000 x21 0.000000 10.000000 x22 50.000000 0.000000 x23 0.000000 20.000000 x2

26、4 10.000000 0.000000 x31 40.000000 0.000000 x32 0.000000 10.000000 x33 10.000000 0.000000 (注：reduced cost為各變量下界約束的影子價格. 例如對x11，若其下界從0提高到e，則目標z的最優(yōu)值會提高30e，其“價格”為30e/e = 30.) 送水方案為: a水庫向乙區(qū)供水50千噸，b水庫向乙、丁區(qū)分別供水50, 10 千噸，c水庫向甲、丙分別供水40, 10千噸. 引水管理費為24400元. 利潤為 144000 - 72000 - 24400 = 47600元 討論 如果a, b, c三個水

27、庫每天的最大供水量都提高一倍，則公司總供 水能力為320千噸，大于總需求量300千噸，水庫供水量不能全部賣出，因而不能像前面那樣，將獲利最多轉(zhuǎn)化為引水管理費最少. 此時我們首先需要計算a, b, c三個水庫分別向甲、乙、丙、丁四個區(qū)供應(yīng)每千噸水的凈利潤，即從收入900元中減去其它管理費450元，再減去表1中的引水管理費，得表2 凈利潤(元/千噸)甲乙丙丁a290320230280b310320260300c260250220/于是決策目標為max z = 290x11 + 320x12 + 230x13 + 280xl4 + 310x21 + 320x22 + 260x23 + 300x24

28、+ 260x31 + 250x32 + 220x33 (9) 由于水庫供水量不能全部賣出，所以上面約束(2)(4)的右端增加一倍的同時，應(yīng)將等號改成小于、等于號，即x11 + x12 + x13 + x14 £ 100 (10)x21 + x22 + x23 + x24 £ 120 (11)x31 + x32 + x33 £ 100 (12) 約束(5)(8)不變將(5)(12)構(gòu)成的線性規(guī)劃模型輸入lindo求解得到: objective function value 1) 88700.00 variable value reduced cost x11 0.0

29、00000 20.000000 x12 100.000000 0.000000 x13 0.000000 40.000000 x14 0.000000 20.000000 x21 30.000000 0.000000 x22 40.000000 0.000000 x23 0.000000 10.000000 x24 50.000000 0.000000 x31 50.000000 0.000000 x32 0.000000 20.000000 x33 30.000000 0.000000 送水方案為：a水庫向乙區(qū)供水100千噸，b水庫向甲、乙、丁區(qū)分別供水30, 40, 50千噸，c水庫向甲、

30、丙區(qū)分別供水50，30千噸總利潤為88700元 其實，由于每個區(qū)的供水量都能完全滿足，所以上面(5)(8)每個式子左邊的約束可以去掉，右邊的小于、等于號可以改寫成等號. 作這樣的簡化后得到的解沒有任何變化. 評注 本題考慮的是將某種物質(zhì)從若干供應(yīng)點運往一些需求點，在供需量約束條件下使總費用最小，或總利潤最大. 這類問題一般稱為運輸問題，是線性規(guī)劃應(yīng)用最廣泛的領(lǐng)域之一. 在標準的運輸問題中，供需量通常是平衡的，即供應(yīng)點的總供應(yīng)量等于需求點的總需求量. 本題中供需量不平衡，但這并不會引起本質(zhì)的區(qū)別，一樣可以方便地建立線性規(guī)劃模型求解. 3實驗練習實驗?zāi)康? 練習建立實際問題的線性規(guī)劃模型。2 掌握

31、用lindo軟件求解線性規(guī)劃問題。實驗內(nèi)容1 用lindo求解下列線性規(guī)劃問題1）min z=+st 2) max z=5(2)st2 某銀行經(jīng)理計劃用一筆資金進行有價證券的投資，可供購進的證券以及信用等級、到期年限、收益如表2所示。按照規(guī)定，市政證券的收益可以免稅，其他證券的收益需按50%的稅率納稅。此外還有以下限制：（1）政府及代辦機構(gòu)的證券總共至少要夠進400萬元；（2）所購證券的平均信用等級不超過1.4（信用等級數(shù)字越小，信用程度越高）；（3）所購證券的平均年限不超過5年；表2證券以及信用等級、到期年限、收益證券名稱種類信用等級到期年限到期收益%a市政294.3b代辦機構(gòu)2155.4c

32、政府145.0d政府134.4e市政524.5(1)若該經(jīng)理擁有1000萬元資金，應(yīng)如何投資？(2)如果能夠以2.75%的利率借到不超過100萬元資金，該經(jīng)理應(yīng)如何操作？(3)在1000萬元資金情況下，若證券a的稅前收益增加為4.5%，投資應(yīng)否改變？若證券c的稅前收益減少為4.8%，投資應(yīng)否改變？實驗二 整數(shù)規(guī)劃(ip)1 實例及數(shù)學模型例1.鋼管下料問題問題 某鋼管零售商從鋼管廠進貨，將鋼管按照顧客要求的長度進行切割，稱為下料。假定進貨時得到的原料鋼管長度都是19m。1）現(xiàn)有一客戶需要50根長4m、20根長6m和15根長8m的鋼管。應(yīng)如何下料最節(jié)??？2）零售商如果采用的不同切割模式太多，將會

33、導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本。所以該零售商規(guī)定采用的不同切割模式不能超過3種。此外。該客戶除需要1）中的3種鋼管外，還要10根長5m的鋼管。應(yīng)如何下料最節(jié)?。繂栴}分析 對于下料問題首先要確定采用哪些切割模式。所謂切割模式，是指按照顧客要求的長度在原料鋼管上安排切割的一種組合。例如，我們可以將19m的鋼管切割成3根長4m的鋼管，余料為7m；或者將長19m的鋼管切割成長4m、6m和8m的鋼管各1根，余料為1m。顯然，可行的切割模式是很多的。其次，應(yīng)當明確哪些切割模式是合理的。合理的切割模式通常還假設(shè)余料不應(yīng)大于或等于客戶需要鋼管的最小尺寸。例如，將長19m的鋼管切割成3根4m的鋼管

34、是可行的，但余料為7m，可進一步將7m的余料切割成4m鋼管（余料為3m），或者將7m的余料切割成6m鋼管（余料為1m）。經(jīng)過簡單的計算可知，問題1）的合理切割模式一共有7種，如表3所示：于是問題化為在滿足客戶需要的條件下，按照哪幾種合理的模式，每種模式切割多少根原料鋼管最為節(jié)省。而所謂節(jié)省，可以有兩種標準，一是切割后剩余的總余料量最小，二是切割原料鋼管的總根數(shù)最少。下面將對這兩個目標分別討論。模型 問題1） 用xi表示按照表3第i種模式（i=1,2,7）切割的原料鋼管的根數(shù)，若以切割后剩余的總余料量最小為目標，則按照表3最后一列可得minz1 = 3x1+x2+3x3+3x4+x5+x6+3x

35、7 (1) 若以切割原料鋼管的總根數(shù)最少為目標，則有表3 鋼管下料問題1）的合理切割模式模式4m鋼管根數(shù)6m鋼管根數(shù)8m鋼管根數(shù)余料/m14003231013201341203511116030170022minz2 = x1+x2+x3+x4+x5+x6+x7 (2)約束條件為客戶的需求，按照表3應(yīng)有4x1+3x2+2x3+x4+x5 50 (3)x2+2x4+x5+3x6 20 (4)x3+x5+2x7 15 (5)最后，切割的原料鋼管的根數(shù)xi顯然應(yīng)當是非負整數(shù)（用z表示整數(shù)集合，z+表示非負整數(shù)集合）：xi z+ ， i=1,2,7 (6)于是，問題1）歸結(jié)為在約束條件（3）（6）下，

36、使目標（1）或目標（2）達到最小。顯然這是線性整數(shù)規(guī)劃模型。問題2） 如果按照問題1）的辦法處理，首先要通過枚舉法確定哪些切割模式是合理的，并從中選出不超過3種模式。而由于需求的鋼管規(guī)格增加到4種，所以枚舉法的工作量較大。下面介紹一種帶有普遍性的方法，可以同時確定切割模式和切割數(shù)量。同問題1）一樣，只使用合理的切割模式，其余料不應(yīng)大于3m（因為客戶需要的鋼管最小尺寸為4m，而本題中參數(shù)都是整數(shù)）。由于不同切割模式不能超過3種，可以用用xi表示按照第i種模式（i=1,2,3）切割的原料鋼管的根數(shù)。又設(shè)使用第i種切割模式下每根原料鋼管生產(chǎn)長4m、5m、6m和8m的鋼管數(shù)量分別為r1i，r2i，r3

37、i，r4i。僅以使用的原料總根數(shù)最少為目標，即min x1+x2+x3 (7)滿足客戶需求的約束條件為r11x1+r12x2+r13x3 50 (8)r21x1+r22x2+r23x3 10 (9)r31x1+r32x2+r33x3 20 (10)r41x1+r42x2+r43x3 15 (11)每一種切割模式必須可行、合理，所以每根原料鋼管的成品量不能超過19m，也不能少于16m（余料不能大于3m），于是 164r11+5r21+6r31+8r41 19 (12)164r12+5r22+6r32+8r42 19 (13)164r13+5r23+6r33+8r43 19 (14)最后，加上非負

38、整數(shù)約束：xi，rji z+ ， i=1,2,3, j=1,2,3,4 (15)于是，問題2）歸結(jié)為在在約束條件（8）（15）下，求xi和r1i，r2i，r3i，r4i（i=1,2,3）使目標（7）達到最小。顯然這是線性整數(shù)規(guī)劃模型。2用lindo求解整數(shù)規(guī)劃lindo可用于求解單純的或混合型的整數(shù)規(guī)劃。lindo求解ip問題用的是分枝定界法。但目前尚無完善的敏感性分析理論，因此敏感性分析在整數(shù)規(guī)劃中沒有意義。ip問題的輸入與lp問題類似，但在end語句標志后需定義整型變量，用gin來標識；gin vname或gin n前者只將變量vname標識為整型，后者模型中前n個變量標識為整型（變量順序

39、由輸入決定，該順序可在輸出結(jié)果中查證）。0-1型的變量由integer(可簡寫為int)來標識： int vname或int n前者只將變量vname標識為0-1型，后者將模型中前n個變量標識為0-1型。例2 求解下列整數(shù)規(guī)劃問題 max 5x1+8x2 st x1+x2<=6 5x1+9x2<=45 end gin 2運行后在結(jié)束窗口的前半部顯示了一些有關(guān)分枝定界的計算信息，后半部才是我們有用的結(jié)果：last integer solution is the best foundre-installign best solutionobjective function value1

40、) 40.00000variable value reduced costx1 0.000000 5.000000 x2 5.000000 8.000000 row slack or surplus dual prices 2) 1.000000 0.000000 3) 0.000000 0.000000 no iterations=12 branches=3 determ=1.000e 0即最優(yōu)解為 x1=0，x2=5，最優(yōu)值為403用lingo求解整數(shù)規(guī)劃lingo軟件用于線性或非線性規(guī)劃（無論是連續(xù)規(guī)劃還是整數(shù)規(guī)劃），因此包含了lindo的功能。在lingo中，輸入總是以model:開始

41、，以end結(jié)束；中間的語句之間必須以“；”分開；目標函數(shù)用max=；或min=；給出（注意有等號“=”）。在lindo中所有的函數(shù)均以“”符號開始，如約束中g(shù)in(x1)表示x1為整數(shù)，用bin(x1)表示x1為0-1整數(shù)。在現(xiàn)在的lindo中，默認設(shè)置假定所有變量非負。例如，例2中的整數(shù)規(guī)劃模型在lindo中可以如下輸入：model:x1+x2<=6； !約束條件和目標函數(shù)可以寫在model：與end之間的任何位置max=5*x1+8*x2； ！*號不能省略5*x1<=45-9*x2；gin(x1)；gin(x2)； ！和lindo不同，不能寫在end之后end運行后同樣得到最優(yōu)

42、解為x1=0，x2=5，最優(yōu)值為40。說明，即使是線性規(guī)劃，在lindo中書寫格式非常嚴格，約束也只能一個一個輸入，因此輸入一個大規(guī)模的模型是比較困難的。而lingo不僅能解非線性模型，書寫格式相當自由，而且有一個非常大的優(yōu)點，即lingo實際上提供了數(shù)學規(guī)劃模型的一種建模描述語言，輸入一個大規(guī)模的模型也是很方便的。lingo中還包括相當豐富的數(shù)學函數(shù)和控制語句，并可以直接利用其他應(yīng)用系統(tǒng)提供的數(shù)據(jù)文件或數(shù)據(jù)庫。鋼管下料問題（1）的求解將式（1），式（3）（6）構(gòu)成的線性整數(shù)規(guī)劃模型輸入lindo如下：min 3x1+x2+3x3+3x4+x5+x6+3x7 s.t4x1+3x2+2x3+x4

43、+x5>=50 x2+2x4+x5+3x6>=20 x3+x5+2x7>=15 endgin7求解可以得到最優(yōu)解如下：objective function value1) 27.00000variable value reduced costx1 0.000000 3.000000 x2 12.000000 1.000000x3 0.000000 3.000000x4 0.000000 3.000000x5 15.000000 1.000000x6 0.000000 1.000000x7 0.000000 3.000000即按照模式2切割12根原料鋼管，按照模式5切割15根原

44、料鋼管，共27根，總余料量27m。顯然，在總余料量最小的目標下，最優(yōu)解將是使用余料盡可能小的切割模式（模式2和模式5的余料為1m），這會導(dǎo)致切割原料鋼管的總根數(shù)較多。將式（2）（6）構(gòu)成的線性整數(shù)規(guī)劃模型輸入lindo求解，可以得到最優(yōu)解如下：objective function value1) 25.00000variable value reduced costx1 0.000000 1.000000 x2 15.000000 1.000000x3 0.000000 1.000000x4 0.000000 1.000000x5 5.000000 1.000000x6 0.000000 1.

45、000000x7 5.000000 1.000000即按照模式2切割15根原料鋼管，按照模式5切割5根原料鋼管，按照模式7切割5根原料鋼管，共25根，總余料量35m。與上面得到的結(jié)果相比，總余料量增加了8m，但是所用的原料鋼管的總根數(shù)減少了2根，在余料沒有什么用途的情況下，通常選擇總根數(shù)最少為目標。鋼管下料問題（2）的求解非線性整數(shù)規(guī)劃模型（7）（15）雖然用lingo軟件可以直接求解，但為了減少運行時間，可以增加一些顯然的約束條件，從而縮小可行解的搜索范圍。例如，由于3種切割模式的排列順序是無關(guān)要緊的，所以不妨增加以下約束： x1x2x3 （16）又如，注意到所需原料鋼管的總根數(shù)有明顯的上界和下界。首先，原料鋼管的根數(shù)不可能少于（根）。其次，考慮一種非常特殊的生產(chǎn)計劃：第一種切