第四章數(shù)學(xué)規(guī)劃方法建模

第4章數(shù)學(xué)規(guī)劃方法建模數(shù)學(xué)規(guī)劃的一般形式：線性規(guī)劃（LinearProgramming，簡稱LP）非線性規(guī)劃（Nonlinearprogramming，簡稱NLP）整數(shù)規(guī)劃（Integerprogramming，簡稱IP）4.1線性規(guī)劃方法建模4.1.1線性規(guī)劃方法簡介4.1線性規(guī)劃方法建模4.1.2線性規(guī)劃方法建模的基本技巧簡單上界和下界約束流約束

簡單資源約束

物料平衡約束

質(zhì)量要求約束

4.1線性規(guī)劃方法建模4.1.3線性規(guī)劃的Lingo實現(xiàn)

例1求解線性規(guī)劃4.1線性規(guī)劃方法建模model:sets:row/1..4/:b;col/1..3/:c,x;

matrix(row,col):A;

endsetsmax=@sum(col:c*x);@for(row(i):@sum(col(j):A(i,j)*x(j))<=b(i));data:c=60,30,20;b=48,20,8,5;A=8,6,14,2,1.52,1.5,0.50,2,0;

enddata

end4.1線性規(guī)劃方法建模4.1.4線性規(guī)劃方法建模示例示例1棋子問題有一個木匠作坊制作兩種不同大小的黃楊木棋子．小型棋子一套需要車床加工3小時，大型棋子一套需要2小時．木匠作坊內(nèi)有4個車床和4名熟練操作員，每人每周工作40小時．小型棋子一套需要1千克黃楊木，大型棋子一套需要3千克黃楊木．黃楊木每周只能得到200千克．如果售出，每套大型棋子能夠得到20元利潤，每套小型棋子能夠得到5元利潤．確定加工兩種棋子的數(shù)量，使得總利潤最大．4.1線性規(guī)劃方法建模問題的最優(yōu)解及最優(yōu)值為：

4.1線性規(guī)劃方法建模示例2連續(xù)投資問題某部們在今后五年內(nèi)考慮給下列項目投資，并已知：項目A，從第一年到第四年每年年初需要投資，并于次年末回收本利115%；項目B，第三年初需要投資，到第五年末能回收本利125%，但規(guī)定最大投資額不超過4萬元；項目C，第二年初需要投資，到第五年末能回收本利140%，但規(guī)定最大投資額不超過3萬元；項目D，五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加利息6%．該部們現(xiàn)在有資金10萬元，問它應(yīng)如何確定給這些項目每年的投資額，使得第五年末擁有的資金的本利總額為最大？

4.1線性規(guī)劃方法建模4.1線性規(guī)劃方法建模問題的最優(yōu)結(jié)果為：

第1年投資：A項目34782.61元，D項目65217.39元

第2年投資：A項目39130.43元，C項目30000元，D項目0元

第3年投資：A項目0元，B項目40000元，D項目0元

第4年投資：A項目45000元，D項目0元

第5年投資：D項目0元

第五年末該部們擁有資金總額為143750元，即盈利43.75%

4.1線性規(guī)劃方法建模示例3貨機裝運問題

某運貨機有三個機艙：前艙，中艙，后艙．三個貨艙所能載的貨物的最大體積和最大重量如表4-1所示．為了保證飛機的平衡，三個貨艙中實際裝載貨物的重量必須與其最大容量成比例．現(xiàn)有四類貨物需飛行裝運，有關(guān)運送數(shù)據(jù)見表4-2,試建立數(shù)學(xué)模型，合理安排裝運，使貨機本次飛行獲利最大．4.1線性規(guī)劃方法建模

表4-1三個貨倉裝載貨物的最大容許重量和體積

前倉中倉后倉重量限制（噸）10168體積限制（立方米）680087005300表4-2四類貨物的裝運數(shù)據(jù)

重量（噸）空間（立方米/噸）利潤（元/噸）貨物1184803100貨物2156503800貨物3235803500貨物41239028504.1線性規(guī)劃方法建模4.1線性規(guī)劃方法建模問題的最優(yōu)結(jié)果為：第1個貨艙裝第2種貨物10噸；第2個貨艙裝第3種貨物12.79412噸；第3個貨艙裝第2種貨物5噸，第3種貨物2.794118噸；最大獲利為111558.8元．

4.1線性規(guī)劃方法建模示例4動物飼料制造問題某飼料公司要生產(chǎn)兩種類型的動物飼料：粉狀飼料和顆粒飼料．生產(chǎn)這些飼料需要的原料為：燕麥，玉米和糖渣．生產(chǎn)過程中，首先需要將燕麥和玉米磨碎，然后將所有原料混合形成飼料產(chǎn)品，最后將半成品制成顆粒狀或粉末狀，從而得到最終產(chǎn)品．每種飼料產(chǎn)品都需要滿足規(guī)定的營養(yǎng)需求，見表4-3．每天各種原料的可用量也有限制，其限定值及原料的價格見表4-4．加工飼料的各道工序的成本見表4-5．如果每天需求量為9噸顆粒飼料，12噸粉狀飼料，則各種原材料應(yīng)分別使用多少，并應(yīng)怎樣混合才能使得總成本最低．4.1線性規(guī)劃方法建模表4-3營養(yǎng)成分含量百分比

原料蛋白質(zhì)脂肪纖維素燕麥玉米糖渣13.64.157.12.40.373.725要求含量9.52

6表4-4原材料可用量與價格原料可用量（千克）價格（元/千克）燕麥玉米糖渣11900235007500.130.170.12表4-5加工成本（元/千克）磨碎混合結(jié)粒篩粉0.250.050.420.174.1線性規(guī)劃方法建模4.1線性規(guī)劃方法建模問題的最優(yōu)結(jié)果為：生產(chǎn)9噸顆粒狀飼料需要燕麥288.8889千克，玉米8711.1111千克，糖渣0千克；生產(chǎn)12噸粉狀飼料需要燕麥11611.11千克，玉米0千克，糖渣388.8889千克．所需的最低成本為15097.33元．4.1線性規(guī)劃方法建模示例5自行車生產(chǎn)規(guī)劃問題某公司生產(chǎn)自行車，表4-6給出了明年各月預(yù)期的銷售量．此公司的月生產(chǎn)能力為3千輛，通過工人加班，可以將產(chǎn)量提高50%，但是會將每輛自行車的生產(chǎn)成本從30元提高到40元．當(dāng)前自行車的庫存量為2千輛，對庫存中的每輛自行車，每個月月底都需支出5元的存儲費用，假定此公司的庫存能力是無限的．現(xiàn)在是1月1日，在下面的12個月里應(yīng)生產(chǎn)和存儲多少輛自行車才能夠滿足此銷售預(yù)期，并使得總成本最少？4.1線性規(guī)劃方法建模表4-6：明年的銷售預(yù)期（千輛）

1月2月3月4月5月6月7月8月9月10月11月12月3015152533404545261425304.1線性規(guī)劃方法建模問題的最優(yōu)結(jié)果見表4-7．生產(chǎn)和庫存的最小總成本為1064500元。

表4-7自行車生產(chǎn)規(guī)劃最優(yōu)結(jié)果表（千輛）月份1月2月3月4月5月6月7月8月9月10月11月12月預(yù)期需求301515253340454526142530正常生產(chǎn)281515283030

30

3026142530加班生產(chǎn)000001015150000倉庫存儲0004000000004.1線性規(guī)劃方法建模示例6體育館建設(shè)問題某市政府打算修建一個小型體育館．通過競標(biāo)，一家建筑公司獲得了此合同．表4-8列出了工程的主要任務(wù)，需時均以星期計．有些任務(wù)只有在某些其他任務(wù)完成之后才能進行．（1）試給出各項任務(wù)的施工次序，使得這項工程能盡早完成．（2）市政府希望能夠再提前一些時間完工．為此，市政府決定工期每縮短一周，便向此公司支付30千元的獎勵．為縮短工期，建筑公司每周需要支付額外費用，見表4-8第5列．問如何施工才能使得建筑公司的利潤最大．4.1線性規(guī)劃方法建模表4-8體育館施工數(shù)據(jù)表任務(wù)描述耗時先決任務(wù)最大縮短時間每周額外開支1工地布置2沒有0－2場地平整1613303打地基921264通路及其它道路網(wǎng)絡(luò)822125底層施工1032176主場地施工64，51157劃分更衣室24188看臺電器布置260－9頂部施工94，624210照明系統(tǒng)5412111安裝階梯看臺3611812封頂290－13更衣室170－14建造售票處7222215第二通路44，1421216信號設(shè)施38，11，141617草坪與附屬運動設(shè)施91231618交付使用1170－4.1線性規(guī)劃方法建模問題（1）的數(shù)學(xué)模型：

4.1線性規(guī)劃方法建模問題的最優(yōu)解，即各個任務(wù)的開工周次為:0，2，18，29，27，37，37，44，43，37，43，52，39，30，37，46，54，63，相應(yīng)各個任務(wù)的完工周次為：2，18，27，37，37，43，39，46，52，42，46，54，40，37，41，49，63，64．最優(yōu)施工時間安排圖，見圖4.1（其中橫坐標(biāo)為施工周次，縱坐標(biāo)為施工項目），最早完工時間為第64周．

圖4.1問題（1）的最優(yōu)施工時間安排圖

4.1線性規(guī)劃方法建模問題（2）的數(shù)學(xué)模型：

4.1線性規(guī)劃方法建模

問題的最優(yōu)解，即各個任務(wù)的開工周次為:0，2，18，18，26，34，26，39，39，26，39，48，28，19，26，42，50，56；相應(yīng)各個任務(wù)的完工周次為：2,18,26,26,34,39,28,41,48,31,42,50,29,26,30,45,56,57；較原先施工方案共計提前了7周；各個任務(wù)實際縮短的周次為：0，0，1，0，2，1，0，0，0，0，0，0，0，0，0，0，3，0．最優(yōu)施工時間安排圖，見圖4.2（其中橫坐標(biāo)為施工周次，縱坐標(biāo)為施工項目），建筑公司最多可獲益87千元．

圖4.2問題（2）的最優(yōu)施工時間安排圖

4.1線性規(guī)劃方法建模示例7農(nóng)作物種植問題

某農(nóng)場有625畝的土地可以用來種植農(nóng)作物．可以種植的農(nóng)作物有玉米、小麥和高粱．預(yù)計有1000畝-尺的灌溉用水可用，農(nóng)場農(nóng)民每周可以投入的時間為300小時．這三種農(nóng)作物每畝的收益分別為400元，200元和250元．每畝農(nóng)作物所需的資源見表4-9．試確定各種農(nóng)作物的種植量，使得農(nóng)場的獲益最大．進一步討論以下3個問題：（1）若用50元可以買到1畝-尺的灌溉用水，應(yīng)否做此項投資？若投資最多每周購買多少畝-尺的灌溉用水？（2）若可以購買土地增加種植面積，購買1畝土地的費用最多是多少元？（3）由于市場需求變化，每畝高粱的獲利增加到300元，應(yīng)否改變生產(chǎn)計劃？

4.1線性規(guī)劃方法建模表4-9農(nóng)場每畝農(nóng)作物所需的資源數(shù)據(jù)

所需資源（每畝）玉米小麥高粱灌溉用水（畝-尺）3.01.01.5勞動時間（小時/周）0.80.20.34.1線性規(guī)劃方法建模線性規(guī)劃模型：

問題的最優(yōu)方案為：種植玉米41.6667畝，種植小麥0畝，種植高粱583.3333畝，最大收益為162500元．4.1線性規(guī)劃方法建模

對Lingo模型進行靈敏度分析可得下面報告：（1）土地和灌溉用水這兩種資源全部用完，而勞動時間這種資源還剩余91.6667；（2）土地、灌溉用水和勞動時間的影子價格分別為100元、100元和0元，即增加1個單位的土地量、灌溉用水量和勞動時間，總收益會分別增加100元、100元和0元．（3）最優(yōu)解不變條件下目標(biāo)函數(shù)系數(shù)的變化范圍分別為[250,400]、[0,200]和[250,400]，即當(dāng)每畝玉米的收益在[250,400]，每畝小麥的收益在[0,200]，每畝高粱的收益在[250,400]變化時，不需要改變生產(chǎn)計劃．（4）土地、灌溉用水和勞動時間這三種資源影子價格有意義條件下約束右端的限制范圍分別為[333.3333,666.6667]、[937.5,1275]和[208.3333,]，要保證前面給定的影子價格有意義，土地量、灌溉用水量和勞動時間只能在上述范圍內(nèi)取值．4.1線性規(guī)劃方法建模根據(jù)上述報告可以回答前面的三個問題：問題（1）應(yīng)該做此項投資，若投資每周最多1275購買畝-尺的灌溉用水；問題（2）可以購買土地，購買1畝土地的費用最多是100元；問題（3）每畝高粱的獲利為300元時，仍小于其變化上限400元，所以不需要改變生產(chǎn)計劃．

4.1線性規(guī)劃方法建模4.1.5課后練習(xí)

1．某公司承諾為某建設(shè)項目從2003年起的4年中每年初分別提供以下數(shù)額貸款：2003年100萬，2004年150萬，2005年120萬，2006年110萬．貸款資金需于2002年底前籌集齊．為了充分發(fā)揮這筆資金的作用，在滿足每年貸款額情況下，可將多余資金分別用于下列投資項目：（1）于2003年初購買A種債券，期限3年，到期后本息合計為投資額的140％，但限購60萬；（2）于2003年初購買B種債券，期限2年，到期后本息合計為投資額的125％，且限購90萬；（3）于2004年初購買C種債券，期限2年，到期后本息合計為投資額的130％，且限購50萬；（4）于每年初將任意數(shù)額的資金存放于銀行，年息4％，于每年底取出．問此公司如何運用這筆籌集到的資金滿足貸款要求，并使得2002年底籌集到的資金數(shù)額最少．4.2整數(shù)規(guī)劃方法建模4.2.1整數(shù)規(guī)劃方法簡介線性整數(shù)規(guī)劃、純整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、0-1規(guī)劃4.2整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模需要的一些特殊變量：

0-1變量：定義變量的取值要么為0，要么為1。部分整數(shù)變量：定義變量如果其值小于用戶指定的限制L，則其取值必須為整數(shù)值；否則可取任意值。半連續(xù)變量：定義變量的取值要么為0，要么位于某限定范圍內(nèi)。半連續(xù)整數(shù)變量：定義變量的取值要么為0，要么位于某限定范圍內(nèi)的整數(shù)值。

4.2整數(shù)規(guī)劃方法建模4.2.2整數(shù)規(guī)劃方法建模的基本技巧處理是/否邏輯問題問題只有兩種選擇，要么做某件事，要么不做某件事．對此可以借助0-1變量來處理。處理邏輯條件問題問題有一組項目，不妨記為A，B，C，D，E，F(xiàn)，G，和H，每個項目都可以選擇做還是不做，可借助0-1變量加以處理。具體問題要求不同，處理的方式也不相同，常見的情況如下：

1.在多個選項中進行選擇

4.2整數(shù)規(guī)劃方法建模如“這些項目中至多選一個”：

再如，“選且僅能選擇二個項目”：

4.2整數(shù)規(guī)劃方法建模2.簡單蘊含式

比如“如果選擇項目A，則必須也選擇項目B”：

再如“如果選擇項目A，則不能選擇項目B”：

再如“如果不選擇項目A，則必須選擇項目B”：

4.2整數(shù)規(guī)劃方法建模3.含有三個變量的蘊涵式

如“如果選擇項目A，則必須也選擇項目B和項目C”:

再如“如果選擇項目A，則必須也選擇項目B或項目C”:

“如果同時選擇項目B和項目C，則必須選擇項目A”:

4.2整數(shù)規(guī)劃方法建模4.一般蘊涵式

比如“如果選擇項目B，C,D和E中的兩個或兩個以上，則必須也選擇A”:

處理0-1變量乘積問題

對式，可用借助下面三個不等式將其線性化

4.2整數(shù)規(guī)劃方法建模對乘積等式約束,可利用下面四個不等式約束將其線性化

處理“或”約束問題

比如下面問題:

4.2整數(shù)規(guī)劃方法建模定義0-1變量,表示采用第1個約束條件，否則采用第2個約束條件

處理半連續(xù)整數(shù)變量問題

如某自行車廠采用流水線作業(yè)生產(chǎn)某種自行車，對這種自行車，要么不生產(chǎn)，要生產(chǎn)要求至少生產(chǎn)1500輛。

4.2整數(shù)規(guī)劃方法建模處理固定成本問題

如某手機生產(chǎn)廠打算生產(chǎn)一種新型的手機，如果生產(chǎn)則需要投資固定成本10萬元，如果不生產(chǎn)，則此項成本為0。

引入0-1輔助變量，表示生產(chǎn)此種手機，否則為0。

4.2整數(shù)規(guī)劃方法建模處理0-1變量和實數(shù)變量的乘積問題

用整數(shù)規(guī)劃方法建模時，有時會遇到實數(shù)變量和0-1變量相乘的問題．如，其中為0-1變量，可用下面不等式將其線性化

處理“或”約束問題

數(shù)學(xué)規(guī)劃中的約束條件一般都是必須同時滿足，但有時對其中的某兩個約束條件只須滿足一個即可，比如

4.2整數(shù)規(guī)劃方法建模定義0-1變量，令表示采用第1個約束條件，采用第2個條件，則取值為0

4.2整數(shù)規(guī)劃方法建模處理半連續(xù)整數(shù)變量問題

如某自行車廠采用流水線作業(yè)生產(chǎn)某種自行車，對這種自行車，要么不生產(chǎn)，要生產(chǎn)要求至少生產(chǎn)1500輛．定義變量表示生產(chǎn)這種自行車的輛數(shù)，則顯然為半連續(xù)整數(shù)變量.定義0-1變量，則有

處理固定成本問題

如某手機生產(chǎn)廠打算生產(chǎn)一種新型的手機，如果生產(chǎn)則需要投資固定成本10萬元，如果不生產(chǎn)，則此項成本為0．記

表示生產(chǎn)此種新型手機的個數(shù)，

表示投資固定資產(chǎn)的費用，

4.2整數(shù)規(guī)劃方法建模引入0-1輔助變量

表示生產(chǎn)此種手機，否則為0，則

處理0-1變量和實數(shù)變量的乘積問題

如為實數(shù)變量，而為0-1變量，且有，則

4.2整數(shù)規(guī)劃方法建模4.2.3整數(shù)規(guī)劃方法的Lingo軟件實現(xiàn)例

用Lingo軟件求解整數(shù)規(guī)劃4.2整數(shù)規(guī)劃方法建模解：在Lingo指令窗中輸入下面指令：

model:sets:row/1..2/:b;col/1..2/:c,x;matrix(row,col):A;endsetsmax=@sum(col:c*x);@for(col:@gin(x));@for(row(i):@sum(col(j):A(i,j)*x(j))<=b(i));data:c=1,1;b=1,4;A=-1,1,3,1;enddataend4.2整數(shù)規(guī)劃方法建模4.2.4整數(shù)規(guī)劃方法建模示例示例1指派問題

有一份中文說明書，需翻譯成英、日、德、俄四種文字，分別記作E、J、G、R．現(xiàn)有甲、乙、丙、丁、戊五人，他們將中文說明書翻譯成不同語種的說明書所需的時間見表4-15．請從這五人中指派四人完成這項工作，使得所需的總時間最少．4.2整數(shù)規(guī)劃方法建模表4-15各人對每項任務(wù)所需時間表

語種EJGR甲乙丙丁戊2109751541486131416111241513974.2整數(shù)規(guī)劃方法建模建立指派問題的數(shù)學(xué)模型如下：

問題的最優(yōu)解為:，其余變量為0，最優(yōu)值為24，即甲翻譯俄文，乙翻譯日文，丁翻譯德文，戊翻譯英文所需的總時間最少，為24小時．

4.2整數(shù)規(guī)劃方法建模示例2汽車廠生產(chǎn)計劃問題某汽車廠生產(chǎn)小、中、大三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤以及每月工廠鋼材、勞動時間的現(xiàn)有量如表4-16所示．由于條件限制，規(guī)定如果生產(chǎn)某一類型的汽車，則至少要生產(chǎn)80輛，試制定月生產(chǎn)計劃，使工廠的利潤最大．表4-16汽車廠相關(guān)數(shù)據(jù)表小型中型大型現(xiàn)有量鋼材（噸）1.535600勞動時間（小時）

28025040060000利潤（萬元）

2344.2整數(shù)規(guī)劃方法建模問題的最優(yōu)解為:

,即生產(chǎn)小型汽車80輛，中型汽車150輛，大型汽車0輛，工廠獲得的最大利潤為610萬元．4.2整數(shù)規(guī)劃方法建模示例3露天采礦問題某地發(fā)現(xiàn)了一個露天鈾礦．根據(jù)探測鉆探的結(jié)果，發(fā)現(xiàn)這個礦可以分為若干個可開采區(qū)．礦坑需要挖掘成階梯形，以方便卡車開到礦坑底部．鈾礦呈東西方向分布，如圖4.3所示．鈾礦確定有18個可開采區(qū)，呈三層分布．為挖掘一個可開采區(qū)，首先需要掘開它上方的三個區(qū)：正上方的區(qū)，左上方的區(qū)和右上方的區(qū)．挖第一層的區(qū)塊每噸需要耗費100元，挖的第二層每噸需要耗費200元，挖第三層每噸需要耗費300元．如果區(qū)塊是由含有很多石英的石頭組成（斜線區(qū)域），則每噸需要多耗費1000元．只有灰色顯示的區(qū)才含有鈾（即1，7，10，12，17，18區(qū)）．其市場價值分別為200，300，500，1000,1200和1400元/噸．第18區(qū)，盡管也含有大量礦石，但也同時含有大量非常硬的石頭．為使總收益達到最大，應(yīng)挖掘哪些礦區(qū)?4.2整數(shù)規(guī)劃方法建模123456789101112131415161718第1層第2層第3層圖4.3：露天礦山結(jié)構(gòu)圖4.2整數(shù)規(guī)劃方法建模問題的最優(yōu)解為:

，其余變量為0，最大收益為1400．即挖掘礦區(qū)1，2，3，4，5，6，7，10，11，12，13，17可使得總收益達到最大．4.2整數(shù)規(guī)劃方法建模示例4蔗糖生產(chǎn)問題在澳大利亞，甘蔗的收割已經(jīng)實現(xiàn)了高度機械化．甘蔗在砍下之后將馬上通過運行于小型鐵路網(wǎng)上的貨車運送到蔗糖廠．一輛貨車的運量能夠生產(chǎn)的蔗糖量取決于甘蔗收購的地點以及甘蔗成熟的程度．在收割之后，甘蔗中的含糖量由于發(fā)酵而迅速下降，一段時間之后，所含糖份將完全流失．現(xiàn)在有11輛貨車到達了蔗糖廠，每輛貨車運載的甘蔗量都相同．對每輛貨車每小時的損失量以及剩余時間測量的數(shù)據(jù)見表4-17：

表4-17：每車甘蔗屬性貨車編號1234567891011損失率（千克/小時）4326372813546249192830剩余時間882848888884.2整數(shù)規(guī)劃方法建模在蔗糖廠有三條生產(chǎn)線，每輛貨車都可以選擇在哪條生產(chǎn)線上進行加工．一車甘蔗的加工時間為兩個小時．必須在這車甘蔗的質(zhì)量壽命結(jié)束之前完成加工．蔗糖廠的經(jīng)理希望找出一個生產(chǎn)計劃，使總的蔗糖損失降到最低．4.2整數(shù)規(guī)劃方法建模問題的最優(yōu)解為:,其余變量為0，各個貨車蔗糖的損失量(單位：千克)分別為：172，208，74，168，52，108，124，196，152，168，180，蔗糖的最小總損失量為1602（千克）．于是得問題的最優(yōu)加工方案見表4-18．

表4-18最優(yōu)加工方案表

時間段1時間段2時間段3時間段4貨車3貨車1貨車4貨車2貨車6貨車5貨車10貨車9貨車7貨車8貨車114.2整數(shù)規(guī)劃方法建模示例5文件備份問題某公司希望將一些重要的文件備份到軟盤上．每張空白軟盤的容量是1.44MB．一共需要備份16個文件，其大小(單位：KB)分別為：46，55，62，87，108，114，137，164，253,364,372,388,406,432,461和851．假定無法使用壓縮文件，但軟盤的數(shù)量足夠，問如何備份這些文件才能使得使用的軟盤數(shù)目最少？

4.2整數(shù)規(guī)劃方法建模文件備份問題的數(shù)學(xué)模型：

問題的最優(yōu)分配方案:

軟盤文件大小（KB）使用空間（MB）146,62,87,137,364,372,3881.42192108,406,432,4611.3740355,114,164,253,8511.40034.2整數(shù)規(guī)劃方法建模示例6鋼管切割問題某鋼管零售商從鋼管廠進貨，將鋼管按照顧客的要求切割后售出，從鋼管廠進貨時得到的原料鋼管都是19m．（1）現(xiàn)有一客戶需要50根4m，20根6m和15根8m的鋼管，應(yīng)如何下料最節(jié)??？（2）零售商如果采用不同切割模式太多，將會導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用不同的切割模式不能超過3種．此外，該客戶除需要（1）中的三種鋼管外，還需要10根5m的鋼管，應(yīng)如何下料最省？4.2整數(shù)規(guī)劃方法建模表4-20鋼管的合理切割模式表模式1模式2模式3模式4模式5模式6模式74m鋼管根數(shù)43211006m鋼管根數(shù)01021308m鋼管根數(shù)0010102問題（1）的數(shù)學(xué)模型：

4.2整數(shù)規(guī)劃方法建模結(jié)果：按照模式1切割5根原料鋼管，按照模式2切割5根原料鋼管，按照模式5切割15根原料鋼管，最少需要切割25根原料鋼管．

問題（2）的數(shù)學(xué)模型：

4.2整數(shù)規(guī)劃方法建模運行得切割所需的模式分別為：模式1，將原料鋼管切割成4m鋼管3根，5m鋼管0根，6m鋼管1根，8m鋼管0根；模式2，將原料鋼管切割成4m鋼管0根，5m鋼管0根，6m鋼管0根，8m鋼管2根；模式3，將原料鋼管切割成4m鋼管2根，5m鋼管1根，6m鋼管1根，8m鋼管0根．最少需要切割19m的原料鋼管28根．模型結(jié)果：4.2整數(shù)規(guī)劃方法建模示例7倉庫位置設(shè)置某公司希望開設(shè)一些新倉庫，向銷售中心供貨．每開設(shè)一個新倉庫都有一些固定費用．貨物將從倉庫運輸?shù)礁浇匿N售中心，每次運輸?shù)倪\費取決于運輸?shù)木嚯x．目前有12個位置可以建造新倉庫，這些倉庫可以向12個銷售中心供貨．表4-21給出了每個倉庫完全滿足每個客戶（銷售中心）需求所需的總成本（單位：元），如果無法進行送貨，取對應(yīng)的成本為100000．此外，每個倉庫的固定建設(shè)費用和倉庫的容量上限見表4-22．倉庫在任何時候都要保證滿足客戶需求，每個客戶的需求量見表4-23．

問此公司應(yīng)在哪些位置開辦倉庫才能使得建設(shè)成本和運輸成本的總費用最低？4.2整數(shù)規(guī)劃方法建模表4-21完全滿足客戶需求所需的運輸總成本客戶1客戶2客戶3客戶4客戶5客戶6客戶7客戶8客戶9客戶10客戶11客戶12倉庫1倉庫2倉庫3倉庫4倉庫5倉庫6倉庫7倉庫8倉庫9倉庫10倉庫11倉庫121008050506010012090607065110120906070651101401108080751301401108080751301601251001008015016012510010080150190150130100000100000

100000190150130100000100000

100000200180150100000100000

100000200180150100000100000

100000100805050601001008050506010012090607065110120906070651101401108080751301401108080751301601251001008015016012510010080150190150130100000100000

100000190150130100000100000

100000200180150100000100000

100000200180150100000100000

100000100805050601004.2整數(shù)規(guī)劃方法建模表4-22倉庫的固定建設(shè)費用和倉庫的容量上限表倉庫123456789101112固定建設(shè)費用350090001000040003000900090003000400010000900035000容量上限300250100180275300200220270250230180表4-23客戶的貨物需求量表客戶123456789101112需求量1208075100110100906030150951204.2整數(shù)規(guī)劃方法建模運行得最低總成本為18713.19元，開設(shè)的倉庫位置分別為：1，4，5，8，9，開設(shè)倉庫的總費用為17500元，運輸?shù)目傎M用為1213.194元．相應(yīng)的最優(yōu)運輸方案見表4-24．4.2整數(shù)規(guī)劃方法建模表4-24最優(yōu)運輸方案表

客戶1客戶2客戶3客戶4客戶5客戶6客戶7客戶8客戶9客戶10客戶11客戶12倉庫1倉庫4倉庫5倉庫8倉庫900050085603000120000701100000000120350000500000045750010000000000025000001509504.2整數(shù)規(guī)劃方法建模示例8求職面試問題

有4名同學(xué)到一家公司參加三個階段的面試．公司要求每個同學(xué)都必須首先找公司秘書初試，然后到主管部門復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊（即在任何一個階段4名同學(xué)的順序是一樣的）．由于4名同學(xué)的專業(yè)背景不同，所以每人在三個階段的面試時間也不同，如表4-25所示（單位：分鐘）．4名同學(xué)約定他們?nèi)棵嬖囃暌院笠黄痣x開公司．假定現(xiàn)在時間是早晨8:00，問他們最早何時能離開公司．

4.2整數(shù)規(guī)劃方法建模表4-25四名同學(xué)各階段的面試時間表秘書初試主管復(fù)試經(jīng)理面試同學(xué)甲131520同學(xué)乙102018同學(xué)丙201610同學(xué)丁810154.2整數(shù)規(guī)劃方法建模求職面試問題的數(shù)學(xué)模型：

4.2整數(shù)規(guī)劃方法建模表4-26四名同學(xué)面試時間表秘書初試主管復(fù)試經(jīng)理面試同學(xué)甲8:08～8:218:21～8:368:36～8:56同學(xué)乙8:21～8:318:36～8:568:56～9:14同學(xué)丙8:31～8:518:56～9:129:14～9:24同學(xué)丁8:00～8:088:11～8:218:21～8:364.2整數(shù)規(guī)劃方法建模4.2整數(shù)規(guī)劃方法建模4.2整數(shù)規(guī)劃方法建模4.2整數(shù)規(guī)劃方法建模4.2整數(shù)規(guī)劃方法建模4.2整數(shù)規(guī)劃方法建模4.2整數(shù)規(guī)劃方法建模模型：課堂練習(xí):某鉆井隊要從以下十個可供選擇的井位：中確定5個鉆井探油。十個井位的鉆探費用估計分別為。且井位選擇必須滿足如下限制條件：（1）或選擇和，或選擇；（2）在三個井位最多只能選擇一個；（3）在中最多只能選兩個；試建立數(shù)學(xué)模型使總的鉆探費用為最小。課堂練習(xí):混合泳接力隊的選拔問題：某班準(zhǔn)備從5名游泳隊員中選擇4人組成接力隊，參加學(xué)校的4100m混合泳接力比賽。5名隊員4種泳姿的百米平均成績?nèi)缦卤硭荆瑔枒?yīng)如何選拔隊員組成接力隊？如果最近隊員丁的蛙泳成績有較大退步，只有75.2秒;而隊員戊經(jīng)過艱苦訓(xùn)練自由泳成績有所進步,達到57.5秒,組成接力隊的方案是否應(yīng)該調(diào)整?甲

乙

丙

丁

戊蝶泳（秒）

66.857.2787067.4仰泳（秒）

75.66667.874.271蛙泳（秒）

8766.484.669.683.8自由泳（秒）

58.65359.457.262.4示例4選課策略某學(xué)校規(guī)定，運籌學(xué)專業(yè)的學(xué)生畢業(yè)時必須至少學(xué)習(xí)過兩門數(shù)學(xué)課、三門運籌學(xué)課和兩門計算機課。這些課程的編號、名稱、所屬類別和先修課要求如表1所示。那么，畢業(yè)時學(xué)生最少可以學(xué)習(xí)這些課程中的哪些中的哪些課程。表1運籌學(xué)專業(yè)的課程屬性表課程編號課程名稱所屬類別先修課要求1微積分數(shù)學(xué)2線性代數(shù)數(shù)學(xué)3最優(yōu)化方法數(shù)學(xué)；運籌學(xué)微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)數(shù)學(xué)；計算機計算機編程5應(yīng)用統(tǒng)計數(shù)學(xué)；運籌學(xué)微積分；線性代數(shù)6計算機模擬計算機；運籌學(xué)計算機編程7計算機編程計算機8預(yù)測理論運籌學(xué)應(yīng)用統(tǒng)計9數(shù)學(xué)實驗運籌學(xué)；計算機微積分；線性代數(shù)模型與結(jié)果：示例5銷售代理的開發(fā)與中斷模型

某公司正在考慮在某城市開發(fā)一些銷售代理業(yè)務(wù)。經(jīng)過預(yù)測，該公司已經(jīng)確定了該城市未來5年的業(yè)務(wù)量，分別為400，500，600，700和800。該公司已經(jīng)初步物色了4家銷售公司作為其代理候選企業(yè)，下表給出了該公司與每個候選企業(yè)建立代理關(guān)系的一次性費用（萬元），以及每個候選企業(yè)每年所能承攬的最大業(yè)務(wù)量和年運行費用（萬元）。該公司應(yīng)該與哪些候選企業(yè)建立代理關(guān)系。候選代理1候選代理2候選代理3候選代理4年最大業(yè)務(wù)量

350250300200一次性費用

100809070年運行費用

7.54.06.53.0模型與結(jié)果：，其它變量為0，最優(yōu)值為313.5萬元若該公司目前已經(jīng)與上述4個代理建立了代理關(guān)系并且都處于運行狀態(tài)，但每年初可以決定臨時中斷或重新恢復(fù)代理關(guān)系，每次臨時中斷或重新恢復(fù)代理關(guān)系的費用（萬元）如下表所示。該公司應(yīng)如何對這些代理進行業(yè)務(wù)調(diào)整？

代理1代理2代理3代理4臨時中斷費用

5342重新恢復(fù)費用

5419模型與結(jié)果：，即公司應(yīng)在第1年初臨時中斷與代理2和代理3的關(guān)系，而在第3年初重新恢復(fù)與代理2得代理關(guān)系。最小總費用為86.5萬元。練習(xí)：汽車廠生產(chǎn)計劃問題

一汽車廠生產(chǎn)小、中、大三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤以及每月工廠鋼材、勞動時間的現(xiàn)有量如下表所示。試制定月生產(chǎn)計劃，使工廠的利潤最大。由于條件限制，只能生產(chǎn)某一類型汽車，且至少要生產(chǎn)80輛，那么最優(yōu)的生產(chǎn)計劃應(yīng)作如何改變。小型

中型

大型現(xiàn)有量鋼材（噸）1.535600勞動時間（小時）

28025040060000利潤（萬元）234例6

飲料廠的生產(chǎn)與檢修計劃某飲料廠生產(chǎn)一種飲料用以滿足市場需求。該廠銷售科根據(jù)市場預(yù)測，已經(jīng)確定了未來四周該飲料的需求量。計劃科根據(jù)本廠實際情況給出了未來四周的生產(chǎn)能力和生產(chǎn)成本，如下表所示。每周當(dāng)飲料滿足需求后有剩余時，要支出存貯費，為每周每千箱飲料0.2千元。問應(yīng)如何安排生產(chǎn)計劃，在滿足市場需求的條件下，使四周的總費用最??？如果工廠必須在未來四周的某一周中安排一次設(shè)備檢修，檢修將占用當(dāng)周15千箱的生產(chǎn)能力，但會使檢修以后每周的生產(chǎn)能力提高5千箱，則檢修應(yīng)安排在哪一周。

周次需求量（千箱）生產(chǎn)能力（千箱）成本（千元/千箱）115305.02

25405.13

35455.4425205.5合計100135表：飲料的生產(chǎn)和需求數(shù)據(jù)表模型與結(jié)果：千元模型與結(jié)果：千元例7飲料廠的生產(chǎn)批量問題某飲料廠使用同一條生產(chǎn)線輪流生產(chǎn)多種飲料以滿足市場需求。如果某周開工生產(chǎn)其中一種飲料，就要清洗設(shè)備和更換部分部件，于是需支出生產(chǎn)準(zhǔn)備費8千元?，F(xiàn)在只考慮生產(chǎn)一種飲料的生產(chǎn)，假設(shè)其未來四周的需求量，生產(chǎn)能力，生產(chǎn)成本和存貯費與例6的完全相同。問應(yīng)如何安排這種飲料的生產(chǎn)計劃，在按時滿足市場需求的條件下，使生產(chǎn)該種飲料的總費用最?。磕Ｐ团c結(jié)果：千元例8鋼管問題某鋼管零售商從鋼管廠進貨，將鋼管按照顧客的要求切割后售出，從鋼管廠進貨時得到的原料鋼管都是19m?，F(xiàn)有一客戶需要50根4m，20根6m和15根8m的鋼管，應(yīng)如何下料最節(jié)??？（2）零售商如果采用不同切割模式太多，將會導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用不同的切割模式不能超過3種。此外，該客戶除需要（1）中的三種鋼管外，還需要10根5m的鋼管，應(yīng)如何下料最省？表：鋼管下料的合理切割模式4m鋼管根數(shù)6m鋼管根數(shù)8m鋼管根數(shù)模式1400模式2310模式3201模式4120模式5111模式6030模式7002模型與結(jié)果：模型與結(jié)果：例9求職面試問題有4名同學(xué)到一家公司參加三個階段的面試：公司要求每個同學(xué)都必須首先找公司秘書初試，然后到主管部門復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊（即在任何一個階段4名同學(xué)的順序是一樣的）。由于4名同學(xué)的專業(yè)背景不同，所以每人在三個階段的面試時間也不同，如下表所示（單位：分鐘）：這4名同學(xué)約定他們?nèi)棵嬖囃暌院笠黄痣x開公司。假定現(xiàn)在時間是早晨8:00，問他們最早何時能離開公司。秘書初試主管復(fù)試經(jīng)理面試同學(xué)甲131520同學(xué)乙102018同學(xué)丙201610同學(xué)丁81015表：面試情況例10蔗糖加工問題在澳大利亞，甘蔗的收割已經(jīng)實現(xiàn)了高度機械化。甘蔗在砍下之后將馬上通過運行于小型鐵路網(wǎng)上的貨車運送到蔗糖廠。一輛貨車的運量能夠生產(chǎn)的蔗糖量取決于甘蔗收購的地點以及甘蔗成熟的程度。在收割之后，甘蔗中的含糖量由于發(fā)酵而迅速下降，一段時間之后，所含糖份將完全流失?，F(xiàn)在有11輛貨車到達了蔗糖廠，每輛貨車運載的甘蔗量都相同。對每輛貨車每小時的損失量以及剩余時間測量的數(shù)據(jù)見下表：在蔗糖廠有三條生產(chǎn)線，每輛貨車都可以選擇在哪條生產(chǎn)線上進行加工。一車甘蔗的加工時間為兩個小時。必須在這車甘蔗的質(zhì)量壽命結(jié)束之前完成加工。蔗糖廠的經(jīng)理希望找出一個生產(chǎn)計劃，使總的蔗糖損失降到最低。貨車編號

1234567891011損失率（千克/小時）4326372813546249192830剩余時間

88284888888例11電力生產(chǎn)問題為滿足每日電力需求（單位為兆瓦），可以選用四種不同類型的發(fā)電機。每日電力需求如表1所示。每種發(fā)電機都有一個最大發(fā)電能力，當(dāng)接入電網(wǎng)時，其輸出功率不應(yīng)低于某一最小輸出功率。所有發(fā)電機都存在一個啟動成本，以及工作于最小功率狀態(tài)時的固定的每小時成本，并且如果功率高于最小功率，則超出部分的功率每兆瓦每小時還存在一個成本，即邊際成本。這些數(shù)據(jù)均列于表2中。只有在每個時段開始時才允許啟動或關(guān)閉發(fā)電機。與啟動發(fā)電機不同，關(guān)閉發(fā)電機不需要付出任何代價。在任意時刻，正在工作的發(fā)電機組必須留出20％的發(fā)電能力余量，以防用電量突然上升。問題：在每個時段應(yīng)分別使用哪些發(fā)電機才能夠使每天的總成本最??？表1每日用電需求（兆瓦）

時段0am-6am6am-9am9am-12pm12pm-2pm2pm-6pm6pm-10pm10pm-12am需求12000320002500036000250003000018000表2發(fā)電機描述數(shù)據(jù)

型號可用量最小輸出功率最大輸出功率固定成本每兆瓦邊際成本啟動成本（臺）（MW）（MW）（歐元/小時）（歐元/小時）（歐元）1234

10750175022502.7500041000150018002.2160081200200037501.8240031800350048003.81200例12體育館建設(shè)問題為了向本市提供更好的服務(wù)，某市政府決定修建一個小型體育館。通過競標(biāo)，一家本地的建筑公司獲得了此合同，希望盡快完成此工程。在下表中列出了工程中的主要任務(wù)。需時均以星期計。有些任務(wù)只有在某些其他任務(wù)完成之后才能進行。此表格的最后兩列對應(yīng)于問題2。問題1：最早能在什么時候完成此工程？問題2：市政府希望能夠提前完工（比問題1的答案提前）。為此，市政府決定工期每縮短一周，則向此公司支付30千歐元的獎勵。為縮短工期，建筑公司需要雇用更多工人，并租借更多設(shè)備，以及相關(guān)的每周額外支出。如果建筑公司希望使利潤最大，那么應(yīng)在何時完成此工程？表：體育館施工數(shù)據(jù)任務(wù)描述耗時先決任務(wù)最大縮短時間每周額外開支1工地布置2沒有0－2場地平整1613303打地基921264通路及其它道路網(wǎng)絡(luò)822125底層施工1032176主場地施工64，51157劃分更衣室24188看臺電器布置260－9頂部施工94，624210照明系統(tǒng)5412111安裝階梯看臺3611812封頂290－13更衣室170－14建造售票處7222215第二通路44，1421216信號設(shè)施38，11，141617草坪與附屬運動設(shè)施91231618交付使用1170－例9原油采購與加工原油采購與加工問題：某公司用兩種原油（和）混合加工成兩種汽油（甲和乙）。甲、乙兩種汽油含原油的最低比例分別為50%和60%，每噸售價分別為4800元和5600元。該公司現(xiàn)有原油和的庫存量分別為500噸和1000噸，還可以從市場上買到不超過1500噸的原油。原油的市場價為：購買量不超過500噸時的單價為10000元/噸；購買量超過500噸但不超過1000頓時，超過500噸的部分8000元/噸；購買量超過1000噸時，超過1000噸的部分6000元/噸。該公司應(yīng)如何安排原油的采購和加工？模型與結(jié)果：例10易拉罐下料某公司采用一套沖壓設(shè)備生產(chǎn)一種罐裝飲料的易拉罐,這種易拉罐是用鍍錫板沖壓制成的.易拉罐為圓柱形,包括罐身,上蓋和下底,罐身高10cm,上蓋和下底的直徑均為5cm.該公司使用兩種不同規(guī)格的鍍錫板原料:規(guī)格1的鍍錫板為正方形,邊長24cm;規(guī)格2的鍍錫板為長方形,長和寬分別為32cm和28cm.由于生產(chǎn)設(shè)備和生產(chǎn)工藝的限制,對規(guī)格1的鍍錫板原理,只可以按照下圖中的模式1,模式2或模式3進行沖壓;對于規(guī)格2的鍍錫板原料只能按照模式4進行沖壓.使用模式1,2,3,4進行沖壓所需的時間分別為1.5秒,2秒,1秒和3秒.該廠每周工作40小時,每周可供使用的規(guī)格1,2的鍍錫板原料分別為5萬張和2萬張.目前每只易拉罐的利潤為0.1元,原料余料損失為0.001元/厘米(如果周末有罐身,上蓋或下底不能配套組裝成易拉罐出售,也視作原料余料損失).問工廠應(yīng)如何安排每周的生產(chǎn)?習(xí)題課1.自行車生產(chǎn)規(guī)劃問題某公司生產(chǎn)兒童自行車。下表中給出了明年預(yù)期的銷售量（以千輛為單位計）。此公司的生產(chǎn)能力為每個月30000輛自行車。通過工人加班，可以將產(chǎn)量提高50%，但是會將每輛自行車的生產(chǎn)成本從30歐元提高到40歐元。當(dāng)前自行車的庫存量為2000輛。對于庫存中的每輛自行車，在每個月月底都需要支出5歐元的存儲費用。假定此公司的庫存能力是無限的?，F(xiàn)在是1月1日，在下面的12個月里應(yīng)生產(chǎn)和存儲多少量自行車才能夠滿足此銷售預(yù)期，并最小化總成本？表：明年的銷售預(yù)期（千輛）1月2月3月4月5月6月7月8月9月10月11月12月3015152533404545261425302.鉆井問題某鉆井隊要從以下十個可供選擇的井位：中確定5個鉆井探油。十個井位的鉆探費用估計分別為。且井位選擇必須滿足如下限制條件：（1）或選擇和，或選擇；（2）在三個井位最多只能選擇一個；（3）在中最多只能選兩個；試建立數(shù)學(xué)模型使總的鉆探費用為最小。3.混合泳接力隊的選拔問題某班準(zhǔn)備從5名游泳隊員中選擇4人組成接力隊，參加學(xué)校的4100m混合泳接力比賽。5名隊員4種泳姿的百米平均成績?nèi)缦卤硭?，問?yīng)如何選拔隊員組成接力隊？如果最近隊員丁的蛙泳成績有較大退步，只有75.2秒;而隊員戊經(jīng)過艱苦訓(xùn)練自由泳成績有所進步,達到57.5秒,組成接力隊的方案是否應(yīng)該調(diào)整?甲

乙

丙

丁

戊蝶泳（秒）

66.857.2787067.4仰泳（秒）

75.6