數(shù)學(xué)建模題目

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

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

3、策科學(xué)化、定量化的呼聲日益高漲的今天，用數(shù)學(xué)建模方法求解優(yōu)化問(wèn)題，無(wú)疑是符合時(shí)代潮流和形勢(shì)發(fā)展需要的。數(shù)學(xué)規(guī)劃模型一般有三個(gè)要素：一是決策變量，通常是該問(wèn)題要求解的那些未知量，不妨用n維向量x=(x1,x2,xn)t表示；二是目標(biāo)函數(shù)，通常是該問(wèn)題要優(yōu)化（最小或最大）的那個(gè)目標(biāo)的數(shù)學(xué)表達(dá)式，它是決策變量x的函數(shù)，這里抽象地記作 f(x)；三是約束條件，由該問(wèn)題對(duì)決策變量的限制條件給出，即x允許取值的范圍x,稱可行域，常用一組關(guān)于x的不等式（也可以有等式）gi(x)0(i=1,2,m)來(lái)界定。一般地，這類模型可表示成如下形式：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稱為可行解，同時(shí)滿足（1）式，（2）式的解x*稱為最優(yōu)解。模型（1），（2）是微積分中多元函數(shù)的條件極值問(wèn)題。當(dāng)約束條件（2）比較簡(jiǎn)單（如全為等式）時(shí)，多元微積分中介紹過(guò)求解析解的基本原理和方法，即令目標(biāo)函數(shù)（對(duì)等式約束需要加上與其對(duì)應(yīng)的拉格朗日乘子的乘積項(xiàng)）的偏導(dǎo)數(shù)為零，求出駐點(diǎn)后再比較駐點(diǎn)上的函數(shù)值。但是，大多數(shù)實(shí)際問(wèn)題歸結(jié)的上述形式的模型很難用這種方法求解，因?yàn)椋旱谝?，解析方法只能處理目?biāo)函數(shù)f和約束條件gi，

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

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

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

8、時(shí)間，付給臨時(shí)工人的工資最多是每小時(shí)幾元？3）由于市場(chǎng)需求變化，每公斤a1的獲利增加到30元，應(yīng)否改變生產(chǎn)計(jì)劃？數(shù)學(xué)模型 設(shè)每天用x1桶牛奶生產(chǎn)a1 ，用x2桶牛奶生產(chǎn)a2 目標(biāo)函數(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的原料（牛奶）總量不超過(guò)每天的供應(yīng)50桶，即 x1+x250勞動(dòng)時(shí)間 生產(chǎn)a1、a2的總加工時(shí)間不超過(guò)每天正式工人總的勞動(dòng)時(shí)間480小時(shí)，即 12x1+8x2480設(shè)備能力 a1的產(chǎn)量不得超過(guò)設(shè)備甲每天的加工能力100小時(shí)，即 3x110

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

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

11、lt;=100end 用鼠標(biāo)單擊菜單中的求解命令（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一個(gè)問(wèn)

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

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

14、 iterations= 2”表示用單純形法進(jìn)行了兩次迭代（旋轉(zhuǎn)）。 如果對(duì)上面的“是否需要做敏感性分析”的詢問(wèn)回答“y”（yes），則lindo還會(huì)輸出以下結(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以上顯示的是當(dāng)前最優(yōu)基（矩陣）保持不變的充分條件（ranges in which the basis is unchanged），包括目標(biāo)函數(shù)中決策變量應(yīng)的系數(shù)的變化范圍（obj coefficient ranges）和約束的右端項(xiàng)的變化范圍（righthand side ranges）兩部分。例如：前一部分的輸出行x

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

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

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

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

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

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

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

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

24、類是水庫(kù)的供應(yīng)量限制，另一類是各區(qū)的需求量限制. 由于供水量總能賣出并獲利，水庫(kù)的供應(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)成一個(gè)線性規(guī)劃模型(當(dāng)然要加上xij的非負(fù)約束). 輸入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為各變量下界約束的影子價(jià)格. 例如對(duì)x11，若其下界從0提高到e，則目標(biāo)z的最優(yōu)值會(huì)提高30e，其“價(jià)格”為30e/e = 30.) 送水方案為: a水庫(kù)向乙區(qū)供水50千噸，b水庫(kù)向乙、丁區(qū)分別供水50, 10 千噸，c水庫(kù)向甲、丙分別供水40, 10千噸. 引水管理費(fèi)為24400元. 利潤(rùn)為 144000 - 72000 - 24400 = 47600元 討論 如果a, b, c三個(gè)水

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

28、+ 260x31 + 250x32 + 220x33 (9) 由于水庫(kù)供水量不能全部賣出，所以上面約束(2)(4)的右端增加一倍的同時(shí)，應(yīng)將等號(hào)改成小于、等于號(hào)，即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水庫(kù)向乙區(qū)供水100千噸，b水庫(kù)向甲、乙、丁區(qū)分別供水30, 40, 50千噸，c水庫(kù)向甲、

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

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

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

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

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

35、7 (1) 若以切割原料鋼管的總根數(shù)最少為目標(biāo)，則有表3 鋼管下料問(wèn)題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)當(dāng)是非負(fù)整數(shù)（用z表示整數(shù)集合，z+表示非負(fù)整數(shù)集合）：xi z+ ， i=1,2,7 (6)于是，問(wèn)題1）歸結(jié)為在約束條件（3）（6）下，

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

37、i，r4i。僅以使用的原料總根數(shù)最少為目標(biāo)，即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)每一種切割模式必須可行、合理，所以每根原料鋼管的成品量不能超過(guò)19m，也不能少于16m（余料不能大于3m），于是 164r11+5r21+6r31+8r41 19 (12)164r12+5r22+6r32+8r42 19 (13)164r13+5r23+6r33+8r43 19 (14)最后，加上非負(fù)

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

39、由輸入決定，該順序可在輸出結(jié)果中查證）。0-1型的變量由integer(可簡(jiǎn)寫為int)來(lái)標(biāo)識(shí)： int vname或int n前者只將變量vname標(biāo)識(shí)為0-1型，后者將模型中前n個(gè)變量標(biāo)識(shí)為0-1型。例2 求解下列整數(shù)規(guī)劃問(wèn)題 max 5x1+8x2 st x1+x2<=6 5x1+9x2<=45 end gin 2運(yùn)行后在結(jié)束窗口的前半部顯示了一些有關(guān)分枝定界的計(jì)算信息，后半部才是我們有用的結(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ī)劃（無(wú)論是連續(xù)規(guī)劃還是整數(shù)規(guī)劃），因此包含了lindo的功能。在lingo中，輸入總是以model:開(kāi)始

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

42、解為x1=0，x2=5，最優(yōu)值為40。說(shuō)明，即使是線性規(guī)劃，在lindo中書寫格式非常嚴(yán)格，約束也只能一個(gè)一個(gè)輸入，因此輸入一個(gè)大規(guī)模的模型是比較困難的。而lingo不僅能解非線性模型，書寫格式相當(dāng)自由，而且有一個(gè)非常大的優(yōu)點(diǎn)，即lingo實(shí)際上提供了數(shù)學(xué)規(guī)劃模型的一種建模描述語(yǔ)言，輸入一個(gè)大規(guī)模的模型也是很方便的。lingo中還包括相當(dāng)豐富的數(shù)學(xué)函數(shù)和控制語(yǔ)句，并可以直接利用其他應(yīng)用系統(tǒng)提供的數(shù)據(jù)文件或數(shù)據(jù)庫(kù)。鋼管下料問(wèn)題（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。顯然，在總余料量最小的目標(biāo)下，最優(yōu)解將是使用余料盡可能小的切割模式（模式2和模式5的余料為1m），這會(huì)導(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根，在余料沒(méi)有什么用途的情況下，通常選擇總根數(shù)最少為目標(biāo)。鋼管下料問(wèn)題（2）的求解非線性整數(shù)規(guī)劃模型（7）（15）雖然用lingo軟件可以直接求解，但為了減少運(yùn)行時(shí)間，可以增加一些顯然的約束條件，從而縮小可行解的搜索范圍。例如，由于3種切割模式的排列順序是無(wú)關(guān)要緊的，所以不妨增加以下約束： x1x2x3 （16）又如，注意到所需原料鋼管的總根數(shù)有明顯的上界和下界。首先，原料鋼管的根數(shù)不可能少于（根）。其次，考慮一種非常特殊的生產(chǎn)計(jì)劃：第一種切