運(yùn)籌學(xué) 整數(shù)規(guī)劃建模

1、第第6章章本章內(nèi)容要點(diǎn)本章內(nèi)容要點(diǎn) 整數(shù)規(guī)劃相關(guān)概念整數(shù)規(guī)劃相關(guān)概念 整數(shù)規(guī)劃問(wèn)題的一般特點(diǎn)整數(shù)規(guī)劃問(wèn)題的一般特點(diǎn) 整數(shù)規(guī)劃建模舉例整數(shù)規(guī)劃建模舉例引例引例經(jīng)濟(jì)管理當(dāng)中經(jīng)常存在人員分派問(wèn)題，企業(yè)中有經(jīng)濟(jì)管理當(dāng)中經(jīng)常存在人員分派問(wèn)題，企業(yè)中有4個(gè)個(gè)人可以勝任人可以勝任4項(xiàng)不同工作的任意一項(xiàng)，但是完成工作項(xiàng)不同工作的任意一項(xiàng)，但是完成工作的效率有所不同。如表所示：的效率有所不同。如表所示：為了使得企業(yè)獲得最好的經(jīng)濟(jì)效益，應(yīng)該如何分派這為了使得企業(yè)獲得最好的經(jīng)濟(jì)效益，應(yīng)該如何分派這四個(gè)人完成四項(xiàng)不同工作？四個(gè)人完成四項(xiàng)不同工作？ 6.1 整數(shù)規(guī)劃問(wèn)題的提出整數(shù)規(guī)劃問(wèn)題的提出6.1.1 問(wèn)題特征問(wèn)題特

2、征 變量取值范圍是離散的，經(jīng)典連變量取值范圍是離散的，經(jīng)典連續(xù)數(shù)學(xué)中的理論和方法一般無(wú)法續(xù)數(shù)學(xué)中的理論和方法一般無(wú)法直接用來(lái)求解整數(shù)規(guī)劃問(wèn)題。直接用來(lái)求解整數(shù)規(guī)劃問(wèn)題。 不考慮整數(shù)條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問(wèn)題稱為整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題。若松弛問(wèn)題是一個(gè)線性規(guī)劃問(wèn)題，則稱該整數(shù)規(guī)劃問(wèn)題為整數(shù)線性規(guī)劃問(wèn)題。 整數(shù)線性規(guī)劃問(wèn)題的分類：整數(shù)線性規(guī)劃問(wèn)題的分類：純整數(shù)線性規(guī)劃問(wèn)題：要求全部變量均取整數(shù)混合整數(shù)線性規(guī)劃問(wèn)題：要求部分變量取值為整數(shù)0-1整數(shù)線性規(guī)劃問(wèn)題：決策變量取值為0或16.1.2 整數(shù)規(guī)劃建模中常用的處理方法整數(shù)規(guī)劃建模中常用的處理方法（1）資本預(yù)算問(wèn)題）資本預(yù)算問(wèn)題

3、 設(shè)有設(shè)有n個(gè)投資方案，個(gè)投資方案，cj為第為第j個(gè)投資個(gè)投資方案的收益。投資過(guò)程共分為方案的收益。投資過(guò)程共分為m個(gè)個(gè)階段，階段，bi為第為第i個(gè)階段的投資總量，個(gè)階段的投資總量，aij為第為第i階段第階段第j項(xiàng)投資方案所需要項(xiàng)投資方案所需要的資金。目標(biāo)是在各階段資金限制的資金。目標(biāo)是在各階段資金限制下使整個(gè)投資的總收益最大。下使整個(gè)投資的總收益最大。設(shè)決策變量設(shè)決策變量xj為對(duì)第為對(duì)第j個(gè)方案的?。▊€(gè)方案的取（xj=1）或舍（或舍（xj=0），可得到下列整數(shù)規(guī)劃問(wèn)題，），可得到下列整數(shù)規(guī)劃問(wèn)題，是是01規(guī)劃。規(guī)劃。yjyjyjxxij 為整數(shù) 該問(wèn)題的約束反映了第該問(wèn)題的約束反映了第i個(gè)時(shí)

4、期資金增個(gè)時(shí)期資金增長(zhǎng)量的平衡。這里長(zhǎng)量的平衡。這里aij代表第代表第i時(shí)期內(nèi)第時(shí)期內(nèi)第j項(xiàng)投資的凈資金流量：項(xiàng)投資的凈資金流量：aij0，表示，表示需附加資金；需附加資金；aij0，表示有附加資金的數(shù)，表示有附加資金的數(shù)量；量；bi0，表示要抽回資金的數(shù)量。，表示要抽回資金的數(shù)量。9例某公司考慮今后五年內(nèi)給以下項(xiàng)目投資。例某公司考慮今后五年內(nèi)給以下項(xiàng)目投資。 項(xiàng)目項(xiàng)目A：每年年初可以投資，于次年末回收本利：每年年初可以投資，于次年末回收本利115% ，投資金額必須為，投資金額必須為1萬(wàn)元的整數(shù)倍；萬(wàn)元的整數(shù)倍； 項(xiàng)目項(xiàng)目 B ：每年初可購(gòu)買公債，于當(dāng)年末歸還，并加：每年初可購(gòu)買公債，于當(dāng)年末

5、歸還，并加利息利息6%，投資金額必須為，投資金額必須為1萬(wàn)元的整數(shù)倍；萬(wàn)元的整數(shù)倍； 項(xiàng)目項(xiàng)目 C：第：第2年初可以投資，到第年初可以投資，到第5年未能回收本利年未能回收本利140% ，投資金額必須為，投資金額必須為1萬(wàn)元的整數(shù)倍；萬(wàn)元的整數(shù)倍； 項(xiàng)目項(xiàng)目D：第：第3年初可以投資，到第年初可以投資，到第5年未能回收本利年未能回收本利128% ，如果投資金額必須大于，如果投資金額必須大于2萬(wàn)元；萬(wàn)元； 該部門現(xiàn)有資金該部門現(xiàn)有資金10萬(wàn)元，問(wèn)它應(yīng)如何確定給這萬(wàn)元，問(wèn)它應(yīng)如何確定給這些項(xiàng)目的每年投資額，使到第些項(xiàng)目的每年投資額，使到第 5 年末擁有的資年末擁有的資金本利總額為最大金本利總額為最大?

6、 10解：解：1) 設(shè)設(shè)xiA、xiB、xiC、xiD ( i 1，2，3，4，5)分別表分別表示第示第 i 年年初給項(xiàng)目年年初給項(xiàng)目A，B，C，D的投資額；的投資額；變量：變量： 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 A x1A x2A x3A x4A B x1B x2B x3B x4B x5B C x2C D x3D6.1.2 建模中常用的處理方法（續(xù)）建模中常用的處理方法（續(xù)）（2）指示變量：）指示變量：指示不同情況的出現(xiàn)指示不同情況的出現(xiàn)P139 例例.有有m個(gè)倉(cāng)庫(kù)，要決定動(dòng)用哪些倉(cāng)庫(kù)，滿足個(gè)倉(cāng)庫(kù)，要決定動(dòng)用哪些倉(cāng)庫(kù)，滿足n個(gè)顧客對(duì)貨物的需要，并決定從各倉(cāng)庫(kù)分別個(gè)

7、顧客對(duì)貨物的需要，并決定從各倉(cāng)庫(kù)分別向不同顧客運(yùn)送多少貨物？向不同顧客運(yùn)送多少貨物？11, 2,0():iiijiyimyxij動(dòng) 用倉(cāng) 庫(kù)令否 則為 指 示 變 量從 倉(cāng) 庫(kù) 到顧 客 運(yùn) 送 的 貨 物 量6.1.2 建模中常用的處理方法（續(xù)）建模中常用的處理方法（續(xù)）費(fèi)用費(fèi)用: fi:動(dòng)用動(dòng)用i倉(cāng)庫(kù)的固定運(yùn)營(yíng)費(fèi)（租金等）倉(cāng)庫(kù)的固定運(yùn)營(yíng)費(fèi)（租金等） cij:從倉(cāng)庫(kù)從倉(cāng)庫(kù)i到到j(luò)顧客運(yùn)送單位貨物的運(yùn)費(fèi)顧客運(yùn)送單位貨物的運(yùn)費(fèi)約束條件：約束條件： i)每個(gè)顧客的需要量每個(gè)顧客的需要量dj必須得到滿足；必須得到滿足； ii)只能從動(dòng)用的倉(cāng)庫(kù)運(yùn)出貨物。只能從動(dòng)用的倉(cāng)庫(kù)運(yùn)出貨物。6.1.2 建模中常用

8、的處理方法（續(xù)）建模中常用的處理方法（續(xù)） ,2,1 10,2,1 ,2,1 0,2,1 0,2,1 .min111111miynjmixmidyxnjdxtsyfxciijnjjinjijjmiijmimiiinjijij或取足夠大的數(shù)，取足夠大的數(shù)，迫使當(dāng)迫使當(dāng)yi=0時(shí)，時(shí)，xij必須為必須為06.1.2 建模中常用的處理方法（續(xù)）建模中常用的處理方法（續(xù)）（3）線性規(guī)劃模型的附加條件）線性規(guī)劃模型的附加條件 在許多實(shí)際問(wèn)題中，線性規(guī)劃模型中在許多實(shí)際問(wèn)題中，線性規(guī)劃模型中的約束條件允許一定范圍的放寬或?qū)Φ募s束條件允許一定范圍的放寬或?qū)€(gè)別因素有進(jìn)一步限制時(shí)，?？赏ㄟ^(guò)個(gè)別因素有進(jìn)一步限制

9、時(shí)，常可通過(guò)引入引入01變量來(lái)處理。下面介紹幾種變量來(lái)處理。下面介紹幾種情況，作為一種建模思路的啟示。情況，作為一種建模思路的啟示。不同時(shí)成立的約束條件。設(shè)某個(gè)模型不同時(shí)成立的約束條件。設(shè)某個(gè)模型問(wèn)題中的約束條件不必同時(shí)成立，有問(wèn)題中的約束條件不必同時(shí)成立，有m個(gè)線性不等式約束個(gè)線性不等式約束對(duì)每個(gè)約束引入一個(gè)指示變量對(duì)每個(gè)約束引入一個(gè)指示變量yi，并得，并得到每個(gè)約束左端的一個(gè)上界到每個(gè)約束左端的一個(gè)上界Mi(i=1,2,n)，建立下列不等式：，建立下列不等式：mibxainjjij, 2 , 1 1miMbyMxaiiiinjjij, 2 , 1 1 顯然，當(dāng)顯然，當(dāng)yi=1時(shí)，兩式等價(jià)；

10、當(dāng)時(shí)，兩式等價(jià)；當(dāng)yi=0時(shí)，第二個(gè)式子是恒成立，相時(shí)，第二個(gè)式子是恒成立，相當(dāng)于除去了這個(gè)限制。當(dāng)于除去了這個(gè)限制。 在實(shí)際問(wèn)題中，如果至少有在實(shí)際問(wèn)題中，如果至少有k個(gè)約個(gè)約束成立時(shí)，只需附加下列約束：束成立時(shí)，只需附加下列約束：kymii1最優(yōu)解中非零分量個(gè)數(shù)的限制。在許最優(yōu)解中非零分量個(gè)數(shù)的限制。在許多實(shí)際問(wèn)題中，對(duì)最優(yōu)解中的非零分量多實(shí)際問(wèn)題中，對(duì)最優(yōu)解中的非零分量個(gè)數(shù)有所限制。類似上述分析可對(duì)每個(gè)個(gè)數(shù)有所限制。類似上述分析可對(duì)每個(gè)決策變量決策變量xi找到其上界找到其上界Mi，并引入指示，并引入指示變量變量yi。附加下式。附加下式 （6-4） （6-5） 式（式（6-5）說(shuō)明，非零分

11、量至多有）說(shuō)明，非零分量至多有k個(gè)。個(gè)。niyMxiii, 2 , 1 0kymii 1離散的資源變化。實(shí)際問(wèn)題中常出現(xiàn)下列離散的資源變化。實(shí)際問(wèn)題中常出現(xiàn)下列情況：不等式約束情況：不等式約束 表示右端的值可以有表示右端的值可以有k個(gè)等級(jí)的違背，而個(gè)等級(jí)的違背，而 ，這里，這里b0為最低的限制，在這為最低的限制，在這個(gè)限制下，不需付出代價(jià)；其余的限制個(gè)限制下，不需付出代價(jià)；其余的限制bi（i=1,2,k）各需相應(yīng)付出代價(jià)各需相應(yīng)付出代價(jià)ci（i=1,2,k），），自然有：自然有：kibxainjjj,2, 1 1kbbbb210kccc21 某工廠擁有某工廠擁有A A、B B、C C 三種類型

12、的設(shè)備，生產(chǎn)甲三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三設(shè)備可利機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三設(shè)備可利用的時(shí)數(shù)如下表所示：用的時(shí)數(shù)如下表所示：?jiǎn)栴}：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤(rùn)？問(wèn)題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤(rùn)？案例案例 假設(shè)上表甲乙兩種產(chǎn)品利潤(rùn)中僅假設(shè)上表甲乙兩種產(chǎn)品利潤(rùn)中僅未去除用電成本未去除用電成本。已知：已知： 用電用電500度以內(nèi)總成本為度以內(nèi)總成本為0；用電；用電1千度以內(nèi)總成本為千度以內(nèi)總成本為100元；元；1-2千度總成本為千度總成本為300元；元；2

13、-3千度總成本為千度總成本為600元；元；3千度以上成本為千度以上成本為1500元。元。用電量8070 在這種情況下，可以引入在這種情況下，可以引入01變量變量yi來(lái)把上來(lái)把上述情況模型化：用式（述情況模型化：用式（6-7）和式（）和式（6-8）?。┤〈剑ù剑?-6） （6-7） （6-8） 在目標(biāo)函數(shù)上需加一項(xiàng)（求在目標(biāo)函數(shù)上需加一項(xiàng)（求min時(shí)）時(shí)） （6-9） 由此不難看出式（由此不難看出式（6-7）以及式（）以及式（6-8）決定）決定了式（了式（6-6）中的一個(gè)式子成立，而式（）中的一個(gè)式子成立，而式（6-9）表明把相應(yīng)的代價(jià)加到目標(biāo)函數(shù)中。表明把相應(yīng)的代價(jià)加到目標(biāo)函數(shù)中。001k

14、iiinjjjybxa11kiiykiiiyc16.2 6.2 整數(shù)規(guī)劃問(wèn)題建模整數(shù)規(guī)劃問(wèn)題建模整數(shù)規(guī)劃問(wèn)題的特征：整數(shù)規(guī)劃問(wèn)題的特征： 變量取值范圍是離散的，在變量取值范圍是離散的，在經(jīng)典連續(xù)數(shù)學(xué)中的理論和方法一經(jīng)典連續(xù)數(shù)學(xué)中的理論和方法一般無(wú)法直接用來(lái)求解整數(shù)規(guī)劃問(wèn)般無(wú)法直接用來(lái)求解整數(shù)規(guī)劃問(wèn)題，求解時(shí)需要技巧。題，求解時(shí)需要技巧。24整數(shù)規(guī)劃建模整數(shù)規(guī)劃建模P305P305例例P305 S2.1 京成畜產(chǎn)品公司計(jì)劃在市區(qū)的東、西、南、北四區(qū)京成畜產(chǎn)品公司計(jì)劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有建立銷售門市部，擬議中有10個(gè)位置個(gè)位置 Aj (j1，2，3，10)可供選擇，考

15、慮到各地區(qū)居民的消費(fèi)水可供選擇，考慮到各地區(qū)居民的消費(fèi)水平及居民居住密集度，規(guī)定：平及居民居住密集度，規(guī)定： 在東區(qū)在東區(qū) A1 ， A2 ，A3 , 3 個(gè)點(diǎn)至多選擇個(gè)點(diǎn)至多選擇 2 個(gè)；個(gè)； 在西區(qū)在西區(qū) A4 ， A5 ，2 個(gè)點(diǎn)中至少選個(gè)點(diǎn)中至少選 1 個(gè)；個(gè)； 在南區(qū)在南區(qū) A6 ， A7 ，2 個(gè)點(diǎn)中至少選個(gè)點(diǎn)中至少選 1 個(gè)；個(gè)； 在北區(qū)在北區(qū) A8 ， A9 ， A10 ，3 個(gè)點(diǎn)中至少選個(gè)點(diǎn)中至少選 2 個(gè)。個(gè)。 25整數(shù)規(guī)劃建模整數(shù)規(guī)劃建模P305P305例例P305 S2.1 Aj 各點(diǎn)的設(shè)備投資及每年可獲利潤(rùn)由于地點(diǎn)不各點(diǎn)的設(shè)備投資及每年可獲利潤(rùn)由于地點(diǎn)不同都是不一樣的

16、，預(yù)測(cè)情況見(jiàn)下表所示同都是不一樣的，預(yù)測(cè)情況見(jiàn)下表所示 (單位：萬(wàn)單位：萬(wàn)元元)。但投資總額不能超過(guò)。但投資總額不能超過(guò)720萬(wàn)元，問(wèn)應(yīng)選擇哪幾萬(wàn)元，問(wèn)應(yīng)選擇哪幾個(gè)銷售點(diǎn)，可使年利潤(rùn)為最大個(gè)銷售點(diǎn)，可使年利潤(rùn)為最大?26解：設(shè)：解：設(shè)：0-1變量變量 xi = 1 (Ai 點(diǎn)被選用）或點(diǎn)被選用）或 0 (Ai 點(diǎn)沒(méi)被選用）。點(diǎn)沒(méi)被選用）。 這樣我們可建立如下的數(shù)學(xué)模型：這樣我們可建立如下的數(shù)學(xué)模型：Max z =36x1+40 x2+50 x3+22x4+20 x5+30 x6 +25x7+48x8+58x9+61x10s.t. 100 x1+120 x2+150 x3+80 x4+70 x5

17、+90 x6 +80 x7+140 x8+160 x9+180 x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xj 為為0-1變量，變量， j = 1,2,3,10 軟件求解演示28例例P305 S2.2高壓容器公司制造小、中、大高壓容器公司制造小、中、大3種尺寸的金種尺寸的金屬容器，所用資源為金屬板、勞動(dòng)力和機(jī)器屬容器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器所需的各種資源的數(shù)量設(shè)備，制造一個(gè)容器所需的各種資源的數(shù)量如下表所示。每種容器售出所得的利潤(rùn)分別如下表所示。每種容器售出所得的利潤(rùn)分別為為 4萬(wàn)元、萬(wàn)元、5

18、萬(wàn)元、萬(wàn)元、6萬(wàn)元。可使用的金屬板萬(wàn)元。可使用的金屬板有有500噸，勞動(dòng)力有噸，勞動(dòng)力有300人月，機(jī)器有人月，機(jī)器有100臺(tái)臺(tái)月。此外，每種容器制造都要支付一筆固定月。此外，每種容器制造都要支付一筆固定的費(fèi)用：小號(hào)是的費(fèi)用：小號(hào)是l00萬(wàn)元，中號(hào)為萬(wàn)元，中號(hào)為 150 萬(wàn)元，萬(wàn)元，大號(hào)為大號(hào)為200萬(wàn)元。現(xiàn)在要制定一個(gè)生產(chǎn)計(jì)劃，萬(wàn)元?，F(xiàn)在要制定一個(gè)生產(chǎn)計(jì)劃，使獲得的利使獲得的利 潤(rùn)為最大。潤(rùn)為最大。 整數(shù)規(guī)劃建模整數(shù)規(guī)劃建模29解：設(shè)解：設(shè)x1，x2， x3 分別為小號(hào)容器、中號(hào)容器和大號(hào)容分別為小號(hào)容器、中號(hào)容器和大號(hào)容器的生產(chǎn)數(shù)量。器的生產(chǎn)數(shù)量。 各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時(shí)才

19、投入，各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時(shí)才投入，為了說(shuō)明固定費(fèi)用的這種性質(zhì)，設(shè)為了說(shuō)明固定費(fèi)用的這種性質(zhì)，設(shè) yi = 1(當(dāng)生產(chǎn)第當(dāng)生產(chǎn)第 i種容器種容器, 即即 xi 0 時(shí)時(shí)) 或或0（當(dāng)不生產(chǎn)第（當(dāng)不生產(chǎn)第 i種容器即種容器即 xi = 0 時(shí)）時(shí)） 引入約束引入約束 xi M yi ，i =1，2，3，M充分大，以保證充分大，以保證當(dāng)當(dāng) yi = 0 時(shí)，時(shí)，xi = 0 。數(shù)學(xué)模型：。數(shù)學(xué)模型：Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x

20、1 + 2x2 + 3x3 100 xi M yi ，i =1，2，3，M充分大充分大 xj 0 且為整數(shù)且為整數(shù) yj 為為0-1變量，變量，j = 1,2,3 軟件求解演示31整數(shù)規(guī)劃建模整數(shù)規(guī)劃建模指派問(wèn)題指派問(wèn)題 有有 n 項(xiàng)不同的任務(wù)，恰好項(xiàng)不同的任務(wù)，恰好 n 個(gè)人可分別個(gè)人可分別承擔(dān)這些任務(wù)，但由于每人特長(zhǎng)不同，完成各項(xiàng)任務(wù)承擔(dān)這些任務(wù)，但由于每人特長(zhǎng)不同，完成各項(xiàng)任務(wù)的效率等情況也不同。現(xiàn)假設(shè)必須指派每個(gè)人去完成的效率等情況也不同。現(xiàn)假設(shè)必須指派每個(gè)人去完成一項(xiàng)任務(wù)，怎樣把一項(xiàng)任務(wù)，怎樣把 n 項(xiàng)任務(wù)指派給項(xiàng)任務(wù)指派給 n 個(gè)人，使得完個(gè)人，使得完成成 n 項(xiàng)任務(wù)的總的效率最高

21、，這就是指派問(wèn)題。項(xiàng)任務(wù)的總的效率最高，這就是指派問(wèn)題。例有例有4個(gè)工人，要分別指派他們完成個(gè)工人，要分別指派他們完成4項(xiàng)不同的工作，項(xiàng)不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表所示，問(wèn)應(yīng)如何每人做各項(xiàng)工作所消耗的時(shí)間如下表所示，問(wèn)應(yīng)如何指派工作，才能使總的消耗時(shí)間為最少。指派工作，才能使總的消耗時(shí)間為最少。32解：解：令令 xij = 1(第第 i人完成第人完成第j項(xiàng)工作項(xiàng)工作)或或0（第（第 i人不進(jìn)行人不進(jìn)行第第j項(xiàng)工作項(xiàng)工作)于是得到一個(gè)于是得到一個(gè)0-1整數(shù)規(guī)劃問(wèn)題：整數(shù)規(guī)劃問(wèn)題：Min z=15x11+18x12+21x13+24x14+19x21+23x22 +22x23+18

22、x24+26x31+17x32+16x33+19x34 +19x41 +21x42+23x43+17x44s.t. x11+ x12+ x13+ x14= 1 (甲只能干一項(xiàng)工作甲只能干一項(xiàng)工作) x21+ x22+ x23+ x24= 1 (乙只能干一項(xiàng)工作乙只能干一項(xiàng)工作) x31+ x32+ x33+ x34= 1 (丙只能干一項(xiàng)工作丙只能干一項(xiàng)工作) x41+ x42+ x43+ x44= 1 (丁只能干一項(xiàng)工作丁只能干一項(xiàng)工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干工作只能一

23、人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干工作只能一人干) xij 為為0-1變量變量，i,j = 1,2,3,433例某企業(yè)在例某企業(yè)在 A1 地已有工廠，其產(chǎn)品的生產(chǎn)能地已有工廠，其產(chǎn)品的生產(chǎn)能力為力為30 萬(wàn)箱。為擴(kuò)大生產(chǎn)，擬在萬(wàn)箱。為擴(kuò)大生產(chǎn)，擬在 A2，A3，A4，A5地中再選擇若干地建廠。已知在地中再選擇若干地建廠。已知在 A2 ， A3，A4，A5地建廠的固定成本分別為地建廠的固定成本分別為17.5、30、37.5、50萬(wàn)元，另外，萬(wàn)元，另外， A1產(chǎn)量及產(chǎn)量及A2，A

24、3，A4，A5建成廠的產(chǎn)量，那時(shí)銷地的銷量以及產(chǎn)地到建成廠的產(chǎn)量，那時(shí)銷地的銷量以及產(chǎn)地到銷地的單位運(yùn)價(jià)銷地的單位運(yùn)價(jià)(每萬(wàn)箱運(yùn)費(fèi)每萬(wàn)箱運(yùn)費(fèi))如右下表所示。如右下表所示。問(wèn)應(yīng)該在哪些地方建廠，在滿足銷量的前提下，問(wèn)應(yīng)該在哪些地方建廠，在滿足銷量的前提下，使得其總的固定成使得其總的固定成 本和總的運(yùn)輸費(fèi)用本和總的運(yùn)輸費(fèi)用 之和最小之和最小? 整數(shù)規(guī)劃建模整數(shù)規(guī)劃建模34解：解： 設(shè)設(shè) xij為從為從Ai 運(yùn)往運(yùn)往Bj 的運(yùn)輸量的運(yùn)輸量(單位千箱單位千箱)， yi = 1(當(dāng)當(dāng)Ai 被選中時(shí)被選中時(shí))或或0（當(dāng)（當(dāng)Ai 沒(méi)被選中時(shí)沒(méi)被選中時(shí)) Min z = 8x11+4x12+3x13+5x21

25、+2x22+3x23+4x31+3x32 +4x33+9x41+7x42 +5x43+10 x51 +4x52+2x53 +17.5y2+30y3+37.5y4+50y5s.t. x11+ x12+ x13 30 ( A1 廠的產(chǎn)量限制廠的產(chǎn)量限制) x21+ x22+ x23 10y2 ( A2 廠的產(chǎn)量限制廠的產(chǎn)量限制) x31+ x32+ x33 20y3 ( A3 廠的產(chǎn)量限制廠的產(chǎn)量限制) x41+ x42+ x43 30y4 ( A4 廠的產(chǎn)量限制廠的產(chǎn)量限制) x51+ x52+ x53 40y5 ( A5 廠的產(chǎn)量限制廠的產(chǎn)量限制) x11+ x21+ x31+ x41 + x

26、51 = 30 ( B1 銷地的限制銷地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( B2 銷地的限制銷地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( B3 銷地的限制銷地的限制) xij 0 yi為為0-1變量變量，i = 1,2,3,4,5；j = 1,2,335例某公司考慮今后五年內(nèi)給以下項(xiàng)目投資。例某公司考慮今后五年內(nèi)給以下項(xiàng)目投資。 項(xiàng)目項(xiàng)目A：每年年初需要投資，于次年末回收本利：每年年初需要投資，于次年末回收本利115%，但要求第但要求第1年投資最低金額為年投資最低金額為4萬(wàn)元，第萬(wàn)元，第2、3、4年不年不限；限； 項(xiàng)目項(xiàng)目B

27、：第：第3年初投資，到第年初投資，到第5年未能回收本利年未能回收本利128，但規(guī)定最低投資金額為但規(guī)定最低投資金額為3萬(wàn)元，最高金額為萬(wàn)元，最高金額為5萬(wàn)元；萬(wàn)元； 項(xiàng)目項(xiàng)目 C：第：第2年初投資，到第年初投資，到第5年未能回收本利年未能回收本利140%，但規(guī)定其投資額只能為但規(guī)定其投資額只能為2、4、6或或8萬(wàn)元。萬(wàn)元。 項(xiàng)目項(xiàng)目 D：每年初可購(gòu)買公債，于當(dāng)年末歸還，并加利：每年初可購(gòu)買公債，于當(dāng)年末歸還，并加利息息6%，此項(xiàng)投資金額不限。，此項(xiàng)投資金額不限。 該部門現(xiàn)有資金該部門現(xiàn)有資金10萬(wàn)元，問(wèn)它應(yīng)如何確定萬(wàn)元，問(wèn)它應(yīng)如何確定給這些項(xiàng)目的每年投資額，使到第給這些項(xiàng)目的每年投資額，使到第

28、 5 年末擁有年末擁有的資金本利總額為最大的資金本利總額為最大? 36解：解：1) 設(shè)設(shè)xiA、xiB、xiC、xiD ( i 1，2，3，4，5)分別表分別表示第示第 i 年年初給項(xiàng)目年年初給項(xiàng)目A，B，C，D的投資額；的投資額； 設(shè)設(shè)yiA， yiB，是，是01變量，并規(guī)定取變量，并規(guī)定取 1 時(shí)分別表時(shí)分別表示第示第 i 年給年給A、B投資，否則取投資，否則取 0（ i = 1, 2, 3, 4, 5）。）。 設(shè)設(shè)yiC 是非負(fù)整數(shù)變量，并規(guī)定：是非負(fù)整數(shù)變量，并規(guī)定： 2年投資年投資C項(xiàng)目為項(xiàng)目為8萬(wàn)元、萬(wàn)元、6萬(wàn)元、萬(wàn)元、4萬(wàn)元、萬(wàn)元、2萬(wàn)元、不萬(wàn)元、不投資投資C項(xiàng)目時(shí)，分別取值為項(xiàng)目時(shí)，分別取值為4、3、2、1、0；變量：變量： 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 A x1A x2A x3A x4A B x3B C x2C (=20000y2C) D x1D x2D x3D x4D x5D 372）約束條件：）約束條件：第一年：年初有第一年：年初有10元，元，D項(xiàng)目在年末可收回投項(xiàng)目在年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是資，故第一年年初應(yīng)把全部資金投出去，于是 x1A+ x1D = 10；第二年：第二年：A次年末