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

1、第第6章章整數(shù)規(guī)劃整數(shù)規(guī)劃北京理工大學(xué)珠海學(xué)北京理工大學(xué)珠海學(xué)院院廖愛(ài)紅廖愛(ài)紅aihongliao126本章內(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)不同任務(wù)的恣意一項(xiàng)，但是完成任務(wù)項(xiàng)不同任務(wù)的恣意一項(xiàng)，但是完成任務(wù)的效率有所不同。如表所示：的效率有所不同。如表所示：為了使得企業(yè)獲得最好的經(jīng)濟(jì)效益，應(yīng)該如何分派這為了使得企業(yè)獲得最好的經(jīng)濟(jì)效益，應(yīng)該如何分派這四個(gè)人完成四項(xiàng)不同任務(wù)？四

2、個(gè)人完成四項(xiàng)不同任務(wù)？ 6.1 整數(shù)規(guī)劃問(wèn)題的提出整數(shù)規(guī)劃問(wèn)題的提出6.1.1 問(wèn)題特征問(wèn)題特征 變量取值范圍是離散的，經(jīng)典延續(xù)變量取值范圍是離散的，經(jīng)典延續(xù)數(shù)學(xué)中的實(shí)際和方法普通無(wú)法直接數(shù)學(xué)中的實(shí)際和方法普通無(wú)法直接用來(lái)求解整數(shù)規(guī)劃問(wèn)題。用來(lái)求解整數(shù)規(guī)劃問(wèn)題。 不思索整數(shù)條件，由余下的目的函數(shù)和約束條件構(gòu)成的規(guī)劃問(wèn)題稱(chēng)為整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題。假設(shè)松弛問(wèn)題是一個(gè)線性規(guī)劃問(wèn)題，那么稱(chēng)該整數(shù)規(guī)劃問(wèn)題為整數(shù)線性規(guī)劃問(wèn)題。 整數(shù)線性規(guī)劃問(wèn)題的分類(lèi)： 純整數(shù)線性規(guī)劃問(wèn)題：要求全部變量均取整數(shù) 混合整數(shù)線性規(guī)劃問(wèn)題：要求部分變量取值為整數(shù) 0-1整數(shù)線性規(guī)劃問(wèn)題：決策變量取值為0或16.1.2 整數(shù)規(guī)劃

3、建模中常用的處置方法整數(shù)規(guī)劃建模中常用的處置方法1資本預(yù)算問(wèn)題資本預(yù)算問(wèn)題 設(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)投資方案所需求的資金。目的是在各階段資金限制的資金。目的是在各階段資金限制下使整個(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ī)劃。yjyjyjxxi

4、j 為整數(shù) 該問(wèn)題的約束反映了第該問(wèn)題的約束反映了第i個(gè)時(shí)期資金增個(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)給以下工程投資。例某公司思索今后五年內(nèi)給以下工程投資。工程工程A：每年年初可以投資，于次年末回收本利：每年年初可以投資，于次年末回收本利115% ，投資金額必需為，投資金額必需為1萬(wàn)元的整數(shù)倍；萬(wàn)元的整數(shù)倍；工程工程 B ：每年初可購(gòu)

5、買(mǎi)公債，于當(dāng)年末歸還，：每年初可購(gòu)買(mǎi)公債，于當(dāng)年末歸還，并加利息并加利息6%，投資金額必需為，投資金額必需為1萬(wàn)元的整數(shù)倍；萬(wàn)元的整數(shù)倍；工程工程 C：第：第2年初可以投資，到第年初可以投資，到第5年未能回收本年未能回收本利利140% ，投資金額必需為，投資金額必需為1萬(wàn)元的整數(shù)倍；萬(wàn)元的整數(shù)倍；工程工程D：第：第3年初可以投資，到第年初可以投資，到第5年未能回收本年未能回收本利利128% ，假設(shè)投資金額必需大于，假設(shè)投資金額必需大于2萬(wàn)元；萬(wàn)元；該部門(mén)現(xiàn)有資金該部門(mén)現(xiàn)有資金10萬(wàn)元，問(wèn)它應(yīng)如何確定給這些萬(wàn)元，問(wèn)它應(yīng)如何確定給這些工程的每年投資額，使到第工程的每年投資額，使到第 5 年末擁有的

6、資金年末擁有的資金本利總額為最大本利總額為最大? 10解：解：1) 設(shè)設(shè)xiA、xiB、xiC、xiD ( i 1，2，3，4，5)分別表示第分別表示第 i 年年初給工程年年初給工程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)P 例例.有有m個(gè)倉(cāng)庫(kù)，要決議動(dòng)用哪些倉(cāng)個(gè)倉(cāng)庫(kù)，要決議動(dòng)用哪些倉(cāng)庫(kù)，滿(mǎn)足庫(kù)，滿(mǎn)足n個(gè)顧客對(duì)貨物

7、的需求，并個(gè)顧客對(duì)貨物的需求，并決議從各倉(cāng)庫(kù)分別向不同顧客運(yùn)送決議從各倉(cāng)庫(kù)分別向不同顧客運(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)送單位貨物的運(yùn)費(fèi)的運(yùn)費(fèi)約束條件：約束條件： i)每個(gè)顧客的需求量每個(gè)顧客的需求量dj必需得到滿(mǎn)必需得到滿(mǎn)足；足； 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ū)€(gè)別要素有進(jìn)一步的放寬或?qū)€(gè)別要素有進(jìn)一步限制時(shí)，?？山?jīng)過(guò)引入限制時(shí)，常可

9、經(jīng)過(guò)引入01變變量來(lái)處置。下面引見(jiàn)幾種情況，量來(lái)處置。下面引見(jiàn)幾種情況，作為一種建模思緒的啟示。作為一種建模思緒的啟示。不同時(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à)；當(dāng)時(shí)，兩式等

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

11、有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à)；其他的限制bii=1,2,k各需相應(yīng)付出代價(jià)各需相應(yīng)付出代價(jià)cii=1,2,k，自然有：，自然有：kibxainjjj,2, 1 1kbbbb210kccc21 某工廠擁有某工廠擁有A A、B B、C C 三種類(lèi)型的設(shè)備，消費(fèi)甲三種類(lèi)型的設(shè)備，消費(fèi)甲、

12、乙兩種產(chǎn)品。每件產(chǎn)品在消費(fèi)中需求占用的設(shè)備、乙兩種產(chǎn)品。每件產(chǎn)品在消費(fèi)中需求占用的設(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)如何安排消費(fèi)可獲得最大的總利潤(rùn)？問(wèn)題：工廠應(yīng)如何安排消費(fèi)可獲得最大的總利潤(rùn)？案例案例 假設(shè)上表甲乙兩種產(chǎn)品利潤(rùn)中僅未去除用電本錢(qián)。假設(shè)上表甲乙兩種產(chǎn)品利潤(rùn)中僅未去除用電本錢(qián)。知：知： 用電用電500度以?xún)?nèi)總本錢(qián)為度以?xún)?nèi)總本錢(qián)為0；用電；用電1千度以?xún)?nèi)總本錢(qián)為千度以?xún)?nèi)總本錢(qián)為100元；元；1-2千度總本錢(qián)為千度總本錢(qián)為300元；元；2-3千度總本錢(qián)為千度總本錢(qián)為600元；元

13、；3千度以上本錢(qián)為千度以上本錢(qián)為1500元。元。用電量8070 在這種情況下，可以引入在這種情況下，可以引入01變量變量yi來(lái)把上來(lái)把上述情況模型化：用式述情況模型化：用式6-7和式和式6-8取取代式代式6-6 6-7 6-8 在目的函數(shù)上需加一項(xiàng)求在目的函數(shù)上需加一項(xiàng)求min時(shí)時(shí) 6-9 由此不難看出式由此不難看出式6-7以及式以及式6-8決議決議了式了式6-6中的一個(gè)式子成立，而式中的一個(gè)式子成立，而式6-9闡明把相應(yīng)的代價(jià)加到目的函數(shù)中。闡明把相應(yīng)的代價(jià)加到目的函數(shù)中。001kiiinjjjybxa11kiiykiiiyc16.2 6.2 整數(shù)規(guī)劃問(wèn)題建模整數(shù)規(guī)劃問(wèn)題建模整數(shù)規(guī)劃問(wèn)題的特

14、征：整數(shù)規(guī)劃問(wèn)題的特征： 變量取值范圍是離散的，變量取值范圍是離散的，在經(jīng)典延續(xù)數(shù)學(xué)中的實(shí)際和方法在經(jīng)典延續(xù)數(shù)學(xué)中的實(shí)際和方法普通無(wú)法直接用來(lái)求解整數(shù)規(guī)劃普通無(wú)法直接用來(lái)求解整數(shù)規(guī)劃問(wèn)題，求解時(shí)需求技巧。問(wèn)題，求解時(shí)需求技巧。24整數(shù)規(guī)劃建模整數(shù)規(guī)劃建模P305P305例例P305 S2.1 京成畜產(chǎn)品公司方案在市區(qū)的東、西、南、北四區(qū)京成畜產(chǎn)品公司方案在市區(qū)的東、西、南、北四區(qū)建立銷(xiāo)售門(mén)市部，擬議中有建立銷(xiāo)售門(mén)市部，擬議中有10個(gè)位置個(gè)位置 Aj (j1，2，3，10)可供選擇，思索到各地域居民的消費(fèi)程可供選擇，思索到各地域居民的消費(fèi)程度及居民居住密集度，規(guī)定：度及居民居住密集度，規(guī)定： 在

15、東區(qū)在東區(qū) A1 ， A2 ，A3 , 3 個(gè)點(diǎn)至多項(xiàng)選擇擇個(gè)點(diǎn)至多項(xiàng)選擇擇 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)不同都是不一樣的，預(yù)測(cè)情況見(jiàn)下表所示同都是不一樣的，預(yù)測(cè)情況見(jiàn)下表所示 (單位：萬(wàn)單位：萬(wàn)元元)。但投資總額不能超越。但

16、投資總額不能超越720萬(wàn)元，問(wèn)應(yīng)選擇哪幾萬(wàn)元，問(wèn)應(yīng)選擇哪幾個(gè)銷(xiāo)售點(diǎn)，可使年利潤(rùn)為最大個(gè)銷(xiāo)售點(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+90 x6 +80 x7+140 x8+160 x9+180 x10 720 x1 + x2 + x3 2 x

17、4 + 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萬(wàn)元、萬(wàn)元、6萬(wàn)元?？蛇\(yùn)用的金屬板萬(wàn)元?？蛇\(yùn)用的金屬板有有500噸，勞動(dòng)力有噸，勞動(dòng)力有300人月，機(jī)器有人月，

18、機(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)元。如今要制定一個(gè)消費(fèi)方案，萬(wàn)元。如今要制定一個(gè)消費(fèi)方案，使獲得的利使獲得的利 潤(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)容器的消費(fèi)數(shù)量。器的消費(fèi)數(shù)量。 各種容器的固定費(fèi)用只需在消費(fèi)該種容器時(shí)才投入，各種容器的固定費(fèi)用只需在消費(fèi)該種容器時(shí)才投入，為了闡明固定費(fèi)用的這種性質(zhì)，設(shè)為了闡明固定費(fèi)用的這種性質(zhì)，設(shè)

19、 yi = 1(當(dāng)消費(fèi)第當(dāng)消費(fèi)第 i種容器種容器, 即即 xi 0 時(shí)時(shí)) 或或0當(dāng)不消費(fèi)第當(dāng)不消費(fèi)第 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 x1 + 2x2 + 3x3 100 xi M yi ，i =1，2，3，M充分大充分大 xj 0 且為整數(shù)且為整數(shù) yj

20、 為為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āng)這些義務(wù)，但由于每人專(zhuān)長(zhǎng)不同，完成各項(xiàng)義務(wù)承當(dāng)這些義務(wù)，但由于每人專(zhuān)長(zhǎng)不同，完成各項(xiàng)義務(wù)的效率等情況也不同。現(xiàn)假設(shè)必需指派每個(gè)人去完成的效率等情況也不同?，F(xiàn)假設(shè)必需指派每個(gè)人去完成一項(xiàng)義務(wù)，怎樣把一項(xiàng)義務(wù)，怎樣把 n 項(xiàng)義務(wù)指派給項(xiàng)義務(wù)指派給 n 個(gè)人，使得完個(gè)人，使得完成成 n 項(xiàng)義務(wù)的總的效率最高，這就是指派問(wèn)題。項(xiàng)義務(wù)的總的效率最高，這就是指派問(wèn)題。例有例有4個(gè)工人，要分別指派他們完成個(gè)工人，要分別指派他們完成4

21、項(xiàng)不同的任務(wù)，項(xiàng)不同的任務(wù)，每人做各項(xiàng)任務(wù)所耗費(fèi)的時(shí)間如下表所示，問(wèn)應(yīng)如何每人做各項(xiàng)任務(wù)所耗費(fèi)的時(shí)間如下表所示，問(wèn)應(yīng)如何指派任務(wù)，才干使總的耗費(fèi)時(shí)間為最少。指派任務(wù)，才干使總的耗費(fèi)時(shí)間為最少。32解：令解：令 xij = 1(第第 i人完成第人完成第j項(xiàng)任務(wù)項(xiàng)任務(wù))或或0第第 i人人不進(jìn)展第不進(jìn)展第j項(xiàng)任務(wù)項(xiàng)任務(wù))于是得到一個(gè)于是得到一個(gè)0-1整數(shù)規(guī)整數(shù)規(guī)劃問(wèn)題：劃問(wèn)題：Min z=15x11+18x12+21x13+24x14+19x21+23x22 +22x23+18x24+26x31+17x32+16x33+19x34 +19x41 +21x42+23x43+17x44s.t. x11+

22、 x12+ x13+ x14= 1 (甲只能干一項(xiàng)任務(wù)甲只能干一項(xiàng)任務(wù)) x21+ x22+ x23+ x24= 1 (乙只能干一項(xiàng)任務(wù)乙只能干一項(xiàng)任務(wù)) x31+ x32+ x33+ x34= 1 (丙只能干一項(xiàng)任務(wù)丙只能干一項(xiàng)任務(wù)) x41+ x42+ x43+ x44= 1 (丁只能干一項(xiàng)任務(wù)丁只能干一項(xiàng)任務(wù)) x11+ x21+ x31+ x41= 1 ( A任務(wù)只能一人干任務(wù)只能一人干) x12+ x22+ x32+ x42= 1 ( B任務(wù)只能一人干任務(wù)只能一人干) x13+ x23+ x33+ x43= 1 ( C任務(wù)只能一人干任務(wù)只能一人干) x14+ x24+ x34+ x4

23、4= 1 ( D任務(wù)只能一人干任務(wù)只能一人干) xij 為為0-1變量，變量，i,j = 1,2,3,433例某企業(yè)在例某企業(yè)在 A1 地已有工廠，其產(chǎn)品的消費(fèi)才地已有工廠，其產(chǎn)品的消費(fèi)才干為干為30 萬(wàn)箱。為擴(kuò)展消費(fèi)，擬在萬(wàn)箱。為擴(kuò)展消費(fèi)，擬在 A2，A3，A4，A5地中再選擇假設(shè)干地建廠。知在地中再選擇假設(shè)干地建廠。知在 A2 ， A3，A4，A5地建廠的固定本錢(qián)分別為地建廠的固定本錢(qián)分別為17.5、30、37.5、50萬(wàn)元，另外，萬(wàn)元，另外， A1產(chǎn)量及產(chǎn)量及A2，A3，A4，A5建成廠的產(chǎn)量，那時(shí)銷(xiāo)地的銷(xiāo)量以及建成廠的產(chǎn)量，那時(shí)銷(xiāo)地的銷(xiāo)量以及產(chǎn)地到銷(xiāo)地的單位運(yùn)價(jià)產(chǎn)地到銷(xiāo)地的單位運(yùn)價(jià)(每

24、萬(wàn)箱運(yùn)費(fèi)每萬(wàn)箱運(yùn)費(fèi))如右下表如右下表所示。所示。問(wèn)應(yīng)該在哪些地方建廠，在滿(mǎn)足銷(xiāo)量的前提下，問(wèn)應(yīng)該在哪些地方建廠，在滿(mǎn)足銷(xiāo)量的前提下，使得其總的固定成使得其總的固定成 本和總的運(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+2x22+3x23+4x31+3x32 +4x33+9x41+7x42 +5x43+10 x51 +4x52+2x53 +1

25、7.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 + x51 = 30 ( B1 銷(xiāo)地的限制銷(xiāo)地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( B2 銷(xiāo)地的

26、限制銷(xiāo)地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( B3 銷(xiāo)地的限制銷(xiāo)地的限制) xij 0 yi為為0-1變量，變量，i = 1,2,3,4,5；j = 1,2,335例某公司思索今后五年內(nèi)給以下工程投資。例某公司思索今后五年內(nèi)給以下工程投資。工程工程A：每年年初需求投資，于次年末回收本利：每年年初需求投資，于次年末回收本利115%，但要求第，但要求第1年投資最低金額為年投資最低金額為4萬(wàn)元，萬(wàn)元，第第2、3、4年不限；年不限；工程工程B：第：第3年初投資，到第年初投資，到第5年未能回收本利年未能回收本利128，但規(guī)定最低投資金額為，但規(guī)定最低投資金額為3萬(wàn)元，

27、最高金萬(wàn)元，最高金額為額為5萬(wàn)元；萬(wàn)元；工程工程 C：第：第2年初投資，到第年初投資，到第5年未能回收本利年未能回收本利140%，但規(guī)定其投資額只能為，但規(guī)定其投資額只能為2、4、6或或8萬(wàn)萬(wàn)元。元。工程工程 D：每年初可購(gòu)買(mǎi)公債，于當(dāng)年末歸還，并：每年初可購(gòu)買(mǎi)公債，于當(dāng)年末歸還，并加利息加利息6%，此項(xiàng)投資金額不限。，此項(xiàng)投資金額不限。 該部門(mén)現(xiàn)有資金該部門(mén)現(xiàn)有資金10萬(wàn)元，問(wèn)它應(yīng)如何確定萬(wàn)元，問(wèn)它應(yīng)如何確定給這些工程的每年投資額，使到第給這些工程的每年投資額，使到第 5 年末擁有年末擁有的資金本利總額為最大的資金本利總額為最大? 36解：解：1) 設(shè)設(shè)xiA、xiB、xiC、xiD ( i

28、 1，2，3，4，5)分別表示第分別表示第 i 年年初給工程年年初給工程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工程為工程為8萬(wàn)元、萬(wàn)元、6萬(wàn)元、萬(wàn)元、4萬(wàn)元、萬(wàn)元、2萬(wàn)元、不萬(wàn)元、不投資投資C工程時(shí)，分別取值為工程時(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工程在年末可收回投工程在年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是資，故第一年年初應(yīng)把全部資金投出去，于是 x1A+ x1D = 10；第二年：第二年：A次年末