數(shù)學(xué)建模教材(第四章)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)第4章 數(shù)學(xué)規(guī)劃模型本章研究數(shù)學(xué)規(guī)劃模型，其中包括：線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、多目標(biāo)規(guī)劃與動(dòng)態(tài)規(guī)劃等內(nèi)容4.1線性規(guī)劃模型線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，隨著計(jì)算機(jī)技術(shù)的發(fā)展，線性規(guī)劃不僅在理論上已趨向成熟，而且在實(shí)際應(yīng)用中也日益廣泛與深入本節(jié)將借助Lingo數(shù)學(xué)軟件對(duì)線性規(guī)劃模型進(jìn)行求解4.1.1問題的提出在生產(chǎn)管理和經(jīng)營(yíng)活動(dòng)中經(jīng)常提出一類問題，即如何合理地利用有限的人力、物力、財(cái)力等資源，以便得到最好的經(jīng)濟(jì)效果引例1 普通生產(chǎn)計(jì)劃安排問題某工廠在計(jì)劃期內(nèi)要安排

2、生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及、兩種原材料的消耗，如表4-1所示該工廠每生產(chǎn)一件產(chǎn)品可獲利2元，每生產(chǎn)一件產(chǎn)品可獲利3元，問應(yīng)該如何安排計(jì)劃使該工廠獲利最多？表4.1普通生產(chǎn)計(jì)劃安排問題設(shè)備原材料原材料利潤(rùn)140220438臺(tái)時(shí)16kg12kg引例2 奶制品的生產(chǎn)計(jì)劃問題一奶品加工廠用牛奶生產(chǎn)、兩種奶制品，1桶牛奶可以在甲類設(shè)備上用12小時(shí)加工成3公斤，或者在乙類設(shè)備上用8小時(shí)加工成4公斤，根據(jù)市場(chǎng)需求，生產(chǎn)的、全部能售出，且每公斤獲利24元，每公斤獲利16元現(xiàn)在加工廠每天能得到50桶牛奶的供應(yīng)，每天正式工人總的勞動(dòng)時(shí)間為480小時(shí)，并且甲類設(shè)備每天最多能加工100公斤，乙類

3、設(shè)備的加工能力沒有限制試為該廠制定一個(gè)生產(chǎn)計(jì)劃，使每天獲利最大，并進(jìn)一步討論以下個(gè)附加問題：若用35元可以買到1桶牛奶，應(yīng)否做這項(xiàng)投資？若投資，每天最多購買多少桶牛奶？若可以聘用臨時(shí)工人以增加勞動(dòng)時(shí)間，付給臨時(shí)工人的工資最多是每小時(shí)幾元？由于市場(chǎng)需求變化，每公斤的獲利增加到30元，應(yīng)否改變生產(chǎn)計(jì)劃？4.1.2模型建立1.引例1普通生產(chǎn)計(jì)劃安排問題的模型建立對(duì)于引例1，可以設(shè)、分別表示在計(jì)劃期內(nèi)產(chǎn)品、的產(chǎn)量若用表示利潤(rùn)，這時(shí)，因?yàn)樵O(shè)備的有效臺(tái)時(shí)為8，因此應(yīng)有限制條件：；同理考慮原材料的不同限制，可得如下限制條件：，綜上所述，該計(jì)劃問題可用數(shù)學(xué)模型表示為：目標(biāo)函數(shù)：約束條件：2.引例2奶制品生產(chǎn)計(jì)

4、劃問題的模型建立對(duì)于引例2，可以設(shè)每天用桶牛奶生產(chǎn)，用桶牛奶生產(chǎn)類似引例1可得奶制品生產(chǎn)計(jì)劃問題的數(shù)學(xué)模型：目標(biāo)函數(shù)：約束條件：從以上兩例可以看出，他們都屬于同一類優(yōu)化問題，他們的共同特征：每一個(gè)問題都用一組決策變量表示某一方案；這組決策變量的值就代表一個(gè)具體方案，一般這些變量取值都是非負(fù)的；存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示；都有一個(gè)要求達(dá)到的目標(biāo)，它可用決策變量的線性函數(shù)來表示，這個(gè)函數(shù)稱為目標(biāo)函數(shù)滿足以上三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃數(shù)學(xué)模型其一般形式為：目標(biāo)函數(shù)：約束條件：4.1.3模型求解1.引例1普通生產(chǎn)計(jì)劃安排問題的模型求解使用Lingo數(shù)學(xué)軟件

5、對(duì)引例進(jìn)行求解，編寫程序如下：max=2*x+3*y;x+2*y8;4*x16;4*y12;end求解結(jié)果為：目標(biāo)函數(shù)的最大值，即可獲得最大利潤(rùn)元；最優(yōu)生產(chǎn)計(jì)劃方案是：生產(chǎn)產(chǎn)品4件，生產(chǎn)產(chǎn)品2件2.引例2奶制品生產(chǎn)計(jì)劃問題的模型求解使用Lingo數(shù)學(xué)軟件對(duì)引例2進(jìn)行求解，編寫程序如下：max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100;end求解結(jié)果為：每天用20桶牛奶生產(chǎn)，用30桶牛奶生產(chǎn)，最大利潤(rùn)是3360元下面來回答三個(gè)附加問題： 針對(duì)附加問題1，可假設(shè)應(yīng)投資購買桶牛奶，目標(biāo)函數(shù)應(yīng)修改為：關(guān)于牛奶的約束條件也應(yīng)作相應(yīng)的修改：通過編程求解得：最大利潤(rùn)

6、增加到3490元，因此，應(yīng)作該項(xiàng)投資，每天最多購買10桶牛奶 針對(duì)附加問題2，首先將勞動(dòng)時(shí)間480小時(shí)增加1個(gè)小時(shí)，對(duì)原問題進(jìn)行求解，可得最大利潤(rùn)由3360元增加到3362元，其中增加的2元就是勞動(dòng)時(shí)間的影子價(jià)格因此，若可以聘用臨時(shí)工人以增加勞動(dòng)時(shí)間，付給臨時(shí)工人的工資最多是每小時(shí)2元其次，若還想知道以低于每小時(shí)2元的價(jià)格增加勞動(dòng)時(shí)間，最多可購買多少勞動(dòng)時(shí)間？可以對(duì)目標(biāo)函數(shù)以及關(guān)于勞動(dòng)時(shí)間的約束條件作類似的修改，然后進(jìn)行求解例如，若以每小時(shí)1.5元的價(jià)格聘用臨時(shí)工人，最多可購買53.333小時(shí)針對(duì)附加問題3，只需改變目標(biāo)函數(shù)中的系數(shù)即可將原來的目標(biāo)函數(shù)改為：，約束條件不變通過求解可得：最大利潤(rùn)

7、有所增加，由原來的3360元增加到3720元，但生產(chǎn)計(jì)劃沒有改變，仍然是每天用20桶牛奶生產(chǎn)，用30桶牛奶生產(chǎn)4.1.4應(yīng)用實(shí)例例1一個(gè)家庭有625英畝的土地可以用來種植農(nóng)作物，這個(gè)家庭考慮種植的農(nóng)作物有玉米、小麥和燕麥，預(yù)計(jì)可以有1000英畝-英尺的灌溉用水，農(nóng)場(chǎng)工人每周可以投入的工作時(shí)間為300小時(shí)，其他的數(shù)據(jù)在表4-2中給出，為能夠獲得最大收益，每種作物應(yīng)該種植多少？表4.2農(nóng)場(chǎng)問題的有關(guān)數(shù)據(jù)玉 米小 麥燕 麥現(xiàn)有量灌溉用水（英畝-英尺）勞力（人-小時(shí)/周）收益（美元）3.00.84001.00.22001.50.32501000300解設(shè)應(yīng)種植玉米英畝，小麥英畝和燕麥英畝可得如下線性規(guī)

8、劃模型：目標(biāo)函數(shù)：約束條件：使用Lingo數(shù)學(xué)軟件進(jìn)行求解，編寫程序如下：max=400*x1+200*x2+250*x3;x1+x2+x3625;0.8*x1+0.2*x2+0.3*x3300;3*x1+x2+1.5*x31000;end程序運(yùn)行結(jié)果為：應(yīng)分別種植玉米187.5英畝，小麥437.5英畝和燕麥0英畝，獲最大收益美元例2 某市有甲、乙、丙、丁四個(gè)居民區(qū)，自來水由、三個(gè)水庫供應(yīng)四個(gè)區(qū)每天必須得到保證的基本生活用水量分別為30，70，10，10千噸，但由于水源緊張，三個(gè)水庫每天最多只能供應(yīng)50，60，50千噸自來水由于地理位置的差別，自來水公式從各水庫向各地區(qū)送水所需付出的引水管理費(fèi)

9、不同（見表4-3，其中水庫與丁地區(qū)之間沒有輸水管道），其它管理費(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)如何分配供水量，才能獲利最多？為了增加供水量，自來水公司正在考慮進(jìn)行水庫改造，使三個(gè)水庫每天的最大供水量都提高一倍，問那時(shí)供水方案應(yīng)如何改變？公司利潤(rùn)可增加多少？表4.3引水管理費(fèi)引水管理費(fèi)（元千噸）甲乙丙丁160140190130130200220190230170150解決策變量應(yīng)為、三個(gè)水庫分別向甲、乙、丙、丁四個(gè)區(qū)的供水量設(shè)水庫向區(qū)的日供水量為千噸，由于水庫與丁區(qū)之間沒有輸水

10、管道，即，因此只有11個(gè)決策變量于是可得如下線性規(guī)劃模型：目標(biāo)函數(shù)：約束條件：水庫供應(yīng)量限制可以表示為：各區(qū)基本用水量與額外用水量限制為：使用Lingo數(shù)學(xué)軟件進(jìn)行求解，編寫程序如下：max=(450-160)*x11+(450-130)*x12+(450-220)*x13+(450-170)*x14+(450-140)*x21+(450-130)*x22+(450-190)*x23+(450-150)*x24+(450-190)*x31+(450-200)*x32+(450-230)*x33;x11+x12+x13+x1450;x21+x22+x23+x2460;x31+x32+x3350;

11、x11+x21+x3130;x12+x22+x3270;x13+x23+x3310;x14+x2410;end程序運(yùn)行結(jié)果為：水庫向乙區(qū)供水50千噸；水庫向乙、丁區(qū)分別供水50，10千噸；水庫向甲、丙分別供水40，10千噸最大利潤(rùn)為47600元對(duì)于本例來說，無論是目標(biāo)函數(shù)還是約束條件都顯得比較麻煩，特別是目標(biāo)函數(shù)為多項(xiàng)相加隨著水庫與居民區(qū)個(gè)數(shù)的增加，程序會(huì)更加復(fù)雜下面來研究更一般的編程方法為此，需假定水庫向丁地區(qū)的引入管理費(fèi)用為無窮大，本例可用1000元千噸來代替使用Lingo數(shù)學(xué)軟件中的高級(jí)編程技巧進(jìn)行求解，編寫程序如下：model:sets:sk/1.3/:g;dq/1.4/:sl1,sl

12、2;link(sk,dq):c,x;endsetsdata:c=160 130 220 170140 130 190 150190 200 230 1000;g=50 60 50;sl1=30 70 10 10;sl2=80 140 30 50;enddataobj max=sum(link(i,j):x(i,j)*(450-c(i,j);for(sk(i):sum(dq(j):x(i,j)sl1(j);for(dq(j):sum(sk(i):x(i,j)sl2(j);end程序運(yùn)行結(jié)果完全相同如果三個(gè)水庫每天的最大供水量都提高一倍，只需將數(shù)據(jù)段中的供水量修改成：g=100 120 100；或

13、者對(duì)第一個(gè)約束條件作簡(jiǎn)單修改，在小于號(hào)后面將供水量擴(kuò)大2倍，其它條件不變最后的運(yùn)行結(jié)果為：水庫向乙區(qū)供水100千噸；水庫向甲、乙、丁區(qū)分別供水30，40，50千噸；水庫向甲、丙分別供水50，30千噸總利潤(rùn)為88700元評(píng)注：本例考慮的是將某種物資從若干供應(yīng)點(diǎn)運(yùn)往一些需求點(diǎn)，在供需量約束條件下使總費(fèi)用最少，或總利潤(rùn)最大這類問題一般稱為運(yùn)輸問題注意：本例目標(biāo)函數(shù)采用的是最大利潤(rùn)，而非最小成本一般來說，成本最小，未必利潤(rùn)最大當(dāng)總收入是常數(shù)時(shí)，最小成本與最大利潤(rùn)是等價(jià)的；若總收入隨決策變量的改變而變化時(shí)，最小成本與最大利潤(rùn)并不等價(jià)通常追求的目標(biāo)應(yīng)該是最大利潤(rùn)，而非最小成本4.2非線性規(guī)劃在工程技術(shù)、經(jīng)

14、濟(jì)管理、交通運(yùn)輸和日常生活等諸多領(lǐng)域中，很多實(shí)際問題可以歸結(jié)為線性規(guī)劃問題，其目標(biāo)函數(shù)和約束條件都是自變量（決策變量）的一次函數(shù)（線性函數(shù)）但是，還有另外一些問題，其目標(biāo)函數(shù)和（或）約束條件很難用線性函數(shù)表達(dá)如果目標(biāo)函數(shù)或約束條件中包含有非線性函數(shù)，就稱這種規(guī)劃問題為非線性規(guī)劃問題由于計(jì)算機(jī)技術(shù)的快速發(fā)展，使非線性規(guī)劃的理論及其應(yīng)用在近幾十年來得以長(zhǎng)驅(qū)進(jìn)展特別是Lingo數(shù)學(xué)軟件的開發(fā)與應(yīng)用，對(duì)非線性規(guī)劃模型的求解提供了很大的幫助4.2.1問題的提出1.引例1液體原料混合問題某公司將4種不同含硫量的液體原料（分別記為甲、乙、丙、丁）混合生產(chǎn)兩種產(chǎn)品（分別記為、）按照生產(chǎn)工藝的要求，原料甲、乙、

15、丁必須首先倒入混合池中混合，混合后的液體再分別與原料丙混合生產(chǎn)和已知原料甲、乙、丙、丁的含硫量分別是3，1，2，1（%），進(jìn)貨價(jià)格分別為6，16，10，15（千元噸）；產(chǎn)品、的含硫量分別不能超過2.5，1.5（%），售價(jià)分別為9，15（千元噸）根據(jù)市場(chǎng)信息，原料甲、乙、丙的供應(yīng)沒有限制，原料丁的供應(yīng)量最多為50噸；產(chǎn)品、的市場(chǎng)需求量分別為100、200（噸），問應(yīng)如何安排生產(chǎn)？2.引例2最佳選址問題某鄉(xiāng)鎮(zhèn)由12個(gè)主要的自然村組成，每個(gè)自然村的位置（用平面坐標(biāo)x，y表示，距離單位：km）和自然村的人口數(shù)（R）如表4-4所示試根據(jù)需要解決如下問題：目前準(zhǔn)備在該鄉(xiāng)鎮(zhèn)建一個(gè)服務(wù)網(wǎng)點(diǎn)為各村提供各種服務(wù)，

16、那么服務(wù)網(wǎng)點(diǎn)應(yīng)該建在何處？假設(shè)各村人口增長(zhǎng)了一倍，需要建兩個(gè)服務(wù)網(wǎng)點(diǎn)，確定其位置表4.4最佳選址問題0123456789101112XyR006008.200.5010000.504.908005.705.0014000.776.4912002.878.767004.433.266002.589.328000.729.9610009.763.1612003.197.2010005.557.8811004.2.2模型建立1.引例1液體原料混合問題的模型建立設(shè)分別是產(chǎn)品中來自混合池和原料丙的噸數(shù)；分別是產(chǎn)品中來自混合池和原料丙的噸數(shù)；混合池中原料甲、乙、丁所占的比例分別為，優(yōu)化目標(biāo)是總利潤(rùn)（）最大

17、 目標(biāo)函數(shù)為：約束條件為：原料最大供應(yīng)限制：產(chǎn)品最大需求限制：產(chǎn)品最大含硫量限制：其它限制：2.引例2最佳選址問題的模型建立（1）模型一的建立設(shè)服務(wù)網(wǎng)點(diǎn)的坐標(biāo)為：；自然村的位置坐標(biāo)：；自然村的人口數(shù)：，服務(wù)網(wǎng)點(diǎn)到各自然村的距離為：以自然村的人口數(shù)作為距離的權(quán)重，優(yōu)化的目標(biāo)為總距離最小目標(biāo)函數(shù)為：約束條件為：（2）模型二的建立設(shè)兩個(gè)服務(wù)網(wǎng)點(diǎn)的坐標(biāo)分別為：；自然村的位置坐標(biāo)：，；自然村的人口數(shù)：；服務(wù)網(wǎng)點(diǎn)到自然村的距離為：；服務(wù)網(wǎng)點(diǎn)對(duì)自然村服務(wù)的人口數(shù)為：； ；表示第個(gè)服務(wù)網(wǎng)點(diǎn)服務(wù)的人口數(shù)占人口總數(shù)的比例以服務(wù)網(wǎng)點(diǎn)對(duì)自然村服務(wù)的人口數(shù)作為距離的權(quán)重，優(yōu)化的目標(biāo)為總距離最小目標(biāo)函數(shù)為：約束條件：從以

18、上兩個(gè)引例可以總結(jié)出非線性規(guī)劃的一般模型：目標(biāo)函數(shù)：約束條件：目標(biāo)函數(shù)為一般非線性函數(shù)，約束條件為一般非線性等式或非線性不等式一般來說，目標(biāo)函數(shù)與約束條件中只要有非線性項(xiàng)存在，即為非線性規(guī)劃特別地，若某非線性規(guī)劃的目標(biāo)函數(shù)為決策變量的二次函數(shù)，約束條件又全是線性的，就稱這種規(guī)劃為二次規(guī)劃4.2.3模型求解1.引例1液體原料混合問題的模型求解使用Lingo數(shù)學(xué)軟件進(jìn)行求解，編寫程序如下：max=(9-6*x1-16*x2-15*x4)*y1+(15-6*x1-16*x2-15*x4)*y2+(1-10)*z1+(15-10)*z2;x4*(y1+y2)50;y1+z1100;y2+z2200;(

19、3*x1+x2+x4)*y1+2*z1)/(y1+z1)2.5;(3*x1+x2+x4)*y2+2*z2)/(y2+z2)1.5;x1+x2+x4=1;end用Lingo求解時(shí)，如果懷疑不是全局最優(yōu)解，用LINGO|OPTIONS菜單命令啟動(dòng)Global Solver選項(xiàng)卡上的Use Global Solver選項(xiàng)，然后求解，可以得到全局最優(yōu)解如下：，其余為0；目標(biāo)函數(shù)值為450如果將產(chǎn)品最大含硫量限制的約束條件作簡(jiǎn)單修改后，也可直接進(jìn)行求解，并得到相同的結(jié)果修改后的程序如下：max=(9-6*x1-16*x2-15*x4)*y1+(15-6*x1-16*x2-15*x4)*y2+(1-10)

20、*z1+(15-10)*z2;x4*(y1+y2)50;y1+z1100;y2+z2200;!(3*x1+x2+x4)*y1+2*z1)/(y1+z1)2.5;(3*x1+x2+x4-2.5)*y1-0.5*z10;!(3*x1+x2+x4)*y2+2*z2)/(y2+z2)1.5;(3*x1+x2+x4-1.5)*y2+0.5*z22*r(j);endsubmodelcalc:e(1)=sum(point:r);e(2)=sum(point:r);solve(xuanzhi);ole(選址.xls,最佳位置a)=a;ole(選址.xls,最佳位置b)=b;ole(選址.xls,最優(yōu)方案)=c

21、;EndcalcEnd用Lingo求解得到結(jié)果為：兩個(gè)服務(wù)網(wǎng)點(diǎn)的位置坐標(biāo)為：；各服務(wù)網(wǎng)點(diǎn)服務(wù)人數(shù)對(duì)照表見表4-5表4.5服務(wù)人數(shù)對(duì)照表（限制服務(wù)網(wǎng)點(diǎn)的服務(wù)人數(shù)相同）123456789101112人口總數(shù)（千人）網(wǎng)點(diǎn)1網(wǎng)點(diǎn)20.40.8021.6002.82.401.4001.21.602002.42002.211.411.4針對(duì)模型二，若不考慮服務(wù)網(wǎng)點(diǎn)服務(wù)人數(shù)的限制，使用Lingo數(shù)學(xué)軟件進(jìn)行求解，編寫程序如下：model:title:最佳選址（一）;sets:point/1.12/:x,y,r;weizhi/1.2/:a,b,e;link(weizhi,point):c;endsetsdat

22、a:X=0 8.20 0.50 5.70 0.77 2.87 4.43 2.58 0.72 9.76 3.19 5.55;Y=0 0.50 4.90 5.00 6.49 8.76 3.26 9.32 9.96 3.16 7.20 7.88;r=600 1000 800 1400 1200 700 600 800 1000 1200 1000 1100;enddatasubmodel xuanzhi:min=sum(link(i,j): c(i,j)*(a(i)-x(j)2+(b(i)-y(j)2)(1/2);!for(weizhi(i): sum(point(j):c(i,j)=e(i);fo

23、r(point(j): sum(weizhi(i):c(i,j)2*r(j);endsubmodelcalc:!e(1)=sum(point:r);!e(2)=sum(point:r);solve(xuanzhi);ole(選址.xls,最佳位置a)=a;ole(選址.xls,最佳位置b)=b;ole(選址.xls,最優(yōu)方案)=c;endcalc用Lingo求解得到結(jié)果為：兩個(gè)服務(wù)網(wǎng)點(diǎn)的位置坐標(biāo)為：；，各服務(wù)網(wǎng)點(diǎn)服務(wù)人數(shù)對(duì)照表見表4-6 表4.6服務(wù)人數(shù)對(duì)照表（服務(wù)網(wǎng)點(diǎn)服務(wù)人數(shù)不限制）123456789101112人口總數(shù)（千人）網(wǎng)點(diǎn)1網(wǎng)點(diǎn)201.2021.6002.82.401.4001.2

24、1.602002.4202.2013.29.64.2.4應(yīng)用實(shí)例例1求解二次規(guī)劃：解本例編寫簡(jiǎn)單的Lingo程序即可求解，編寫Lingo程序如下：max=8*x1+10*x2-x12-x22;3*x1+2*x2=0 b(i,j)=atan(x12/x11); elseif x12=0 b(i,j)=pi+atan(x12/x11); elseif x12=0 b(i,j)=b(i,j)-atan(x22/x21); elseif x22=0 b(i,j)=b(i,j)-atan(x22/x21)-pi; elseif x22pi b(i,j)=b(i,j)-2*pi; elseif b(i,j

25、)alpha(i,j););for(link:bnd(0,alpha,90);for(plane:bnd(-30,d_cita,30);objmin=sum(plane:(d_cita)2);end5.結(jié)果檢驗(yàn)對(duì)題目所給實(shí)例進(jìn)行計(jì)算得如下調(diào)整方案：， ， ， ， 各飛行方向角按此方案調(diào)整后，系統(tǒng)各架飛機(jī)均滿足（即不會(huì)相撞）其中有些飛機(jī)對(duì)可能會(huì)有（0.01是題目要求的計(jì)算精度）如果希望，只須將模型中的用代替即可6.模型評(píng)價(jià)與改進(jìn)此模型采用圓狀模型分析碰撞問題是合理的，同時(shí)采用相對(duì)速度作為判斷標(biāo)準(zhǔn)，既體現(xiàn)了碰撞的本質(zhì)（相對(duì)運(yùn)動(dòng)），又簡(jiǎn)化了模型的計(jì)算題目要求飛機(jī)飛行方向角調(diào)整的幅度盡量小，這個(gè)盡量小

26、是針對(duì)每架飛機(jī)而言的，同時(shí)也要求整體滿意程度（即對(duì)管理層而言，應(yīng)使每架飛機(jī)的調(diào)整都盡量的小）因此構(gòu)造目標(biāo)函數(shù)時(shí)，也可以認(rèn)為若對(duì)方向角調(diào)整量最大的飛機(jī)而言，其調(diào)整量可滿意，則由假設(shè)（5）對(duì)其余飛機(jī)調(diào)整量均可滿意即要求每架飛機(jī)的調(diào)整量都小于某個(gè)數(shù)故目標(biāo)函數(shù)也可取：于是可得如下線性規(guī)劃模型：目標(biāo)函數(shù)：約束條件：模型二： 最短距離模型.問題分析目標(biāo)函數(shù)的選取與模型一相同進(jìn)入該區(qū)域的飛機(jī)在到達(dá)該區(qū)域邊緣時(shí)，與區(qū)域內(nèi)的飛機(jī)的距離應(yīng)在60km以內(nèi)，很容易驗(yàn)證目前所給數(shù)據(jù)是滿足的，因此，約束條件只需要限制任意兩架位于該區(qū)域內(nèi)的飛機(jī)的距離應(yīng)大于8km但這個(gè)問題的難點(diǎn)在于飛機(jī)是動(dòng)態(tài)的，這個(gè)約束不好直接描述為此，可

27、以考慮在飛行過程中任意兩架飛機(jī)的最短距離大于8km即可飛行時(shí)間可以只考慮一架飛機(jī)飛越該區(qū)域所需的最長(zhǎng)時(shí)間，若超過這個(gè)時(shí)間，即使兩架飛機(jī)的最短距離小于8km，由于飛機(jī)已經(jīng)離開該區(qū)域，因此不再予以考慮2.模型假設(shè)與模型一相同3.模型的建立符號(hào)說明：表示第架飛機(jī)的飛行方向與x軸正向的夾角（轉(zhuǎn)角）；表示第架飛機(jī)在調(diào)整前的位置坐標(biāo)；表示第架飛機(jī)時(shí)刻的位置坐標(biāo)；表示飛機(jī)的飛行時(shí)間；表示飛機(jī)的飛行速度；表示第架飛機(jī)飛出區(qū)域的時(shí)刻；表示任意一架飛機(jī)在該區(qū)域內(nèi)停留的最長(zhǎng)時(shí)間；表示第架飛機(jī)與第架飛機(jī)距離最短的時(shí)刻；表示第架飛機(jī)的飛行方表示第架飛機(jī)與第架飛機(jī)的距離；記飛機(jī)飛行速率為，以當(dāng)前時(shí)刻為0時(shí)刻，設(shè)第架飛機(jī)在

28、調(diào)整前的位置坐標(biāo)為，時(shí)刻的位置坐標(biāo)，即如果要嚴(yán)格表示兩架位于該區(qū)域內(nèi)的飛機(jī)的距離應(yīng)大于8km，則需要考慮每架飛機(jī)在區(qū)域內(nèi)到為飛行時(shí)間的長(zhǎng)度記為第架飛機(jī)飛出區(qū)域的時(shí)刻，即記時(shí)刻第架飛機(jī)與第架飛機(jī)的距離為，并記，這時(shí)在區(qū)域內(nèi)飛機(jī)不相撞的約束條件就變成了其中此外，經(jīng)過計(jì)算可以得到：其中所以，是一個(gè)關(guān)于的二次函數(shù)，當(dāng)，即（記為）時(shí)，函數(shù)取最小值若，只要初始時(shí)刻不相撞即可，此時(shí)滿足條件，不需要限制；若，只需要即可；若，即可，即實(shí)際上，在時(shí)也成立，因此，可以不再附加的條件，于是可得如下非線性規(guī)劃模型：目標(biāo)函數(shù)：約束條件：4.模型求解由于的計(jì)算相當(dāng)復(fù)雜，求解時(shí)可進(jìn)一步簡(jiǎn)化：不單獨(dú)考慮每架飛機(jī)在區(qū)域內(nèi)停留的時(shí)

29、間，而以最大時(shí)間代替，此時(shí)所有實(shí)際上強(qiáng)化了問題的要求，即考慮了有些飛機(jī)可能已經(jīng)飛出區(qū)域，但仍不允許兩架飛機(jī)的距離小于8km這個(gè)簡(jiǎn)化的模型可以如下輸入Lingo軟件：model:title: 飛行管理問題的非線性規(guī)劃模型二;sets:plane/1.6/:x0,y0,cita0,cita1,d_cita;!cita0表示初始角度，cita1為調(diào)整后的角度，d_cita為調(diào)整的角度;link(plane,plane)|&1#lt#&2:b,c;endsetsdata:x0,y0,cita0= 150 140 243 85 85 236 150 155 220.5 145 50 159 130 15

30、0 230 0 0 52;max_cita=30;t_max=0.283;v=800;pi=3.;enddatainit:d_cita=0 0 0 0 0 0;endinitfor(plane:cita1-cita0=d_cita);for(link(i,j):b(i,j)=-2*(x0(i)-x0(j)*sin(cita1(i)+cita1(j)*pi/360)+2*(y0(i)-y0(j)*cos(cita1(i)+cita1(j)*pi/360);c(i,j)=(x0(i)-x0(j)2+(y0(i)-y0(j)2-64;);!避免碰撞的條件;!右端點(diǎn)非負(fù);for(link(i,j):r

31、ight(2*v*t_max*sin(cita1(i)-cita1(j)*pi/360)2+b(i,j)*(2*v*t_max*sin(cita1(i)-cita1(j)*pi/360)+c(i,j)0);!左端點(diǎn)非負(fù);for(link(i,j):c(i,j)0);!最小點(diǎn)非負(fù);for(link(i,j):minimumif(-b(i,j)/4/v/sin(cita1(i)-cita1(j)*pi/360)#gt#0#and#-b(i,j)/4/v/sin(cita1(i)-cita1(j)*pi/360)#lt#t_max,b(i,j)2-4*c(i,j),-1)0);!for(link(i

32、,j):b(i,j)2-4*c(i,j)0);for(link:free(b);!調(diào)整角度上下限，單位為角度;for(plane:bnd(-max_cita,d_cita,max_cita);objmin=sum(plane:(d_cita)2);end使用Lingo全局求解程序求解該模型，得到的結(jié)果與模型一幾乎是一樣的調(diào)整方案如下：， ， ， ， 4.3整數(shù)規(guī)劃在線性規(guī)劃或非線性規(guī)劃模型中，經(jīng)常會(huì)遇到?jīng)Q策變量必須是整數(shù)的限制，例如，當(dāng)決策變量表示人數(shù)、機(jī)器設(shè)備的臺(tái)數(shù)、機(jī)械車輛數(shù)等的時(shí)候，顯然，這些量必須取整數(shù)一般地，包含有整數(shù)決策變量的數(shù)學(xué)模型稱為整數(shù)規(guī)劃模型在研究實(shí)際問題時(shí)，有時(shí)還會(huì)遇到?jīng)Q

33、策變量是0-1變量的情形，即決策變量只能取0或1兩個(gè)值，這種特殊的整數(shù)規(guī)劃模型稱為0-1規(guī)劃模型，0-1規(guī)劃模型是整數(shù)規(guī)劃模型中非常重要的一類模型4.3.1問題的提出1.引例1 汽車廠的生產(chǎn)計(jì)劃問題一汽車廠生產(chǎn)小、中、大三種類型的汽車，已知各類型每輛車對(duì)鋼材、勞動(dòng)時(shí)間的需求量，利潤(rùn)以及每月工廠鋼材、勞動(dòng)時(shí)間的現(xiàn)有量如表4-8所示試制訂月生產(chǎn)計(jì)劃，使工廠的利潤(rùn)最大進(jìn)一步討論：由于各種條件的限制，如果生產(chǎn)某一類型的汽車，則至少要生產(chǎn)80輛，那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？表4.8汽車廠的生產(chǎn)數(shù)據(jù)小型中型大型現(xiàn)有量鋼材（噸）勞動(dòng)時(shí)間（小時(shí)）利潤(rùn)（萬元）1.52802325035400460060000

34、2.引例2 混合泳接力隊(duì)的選拔問題某班計(jì)劃從5名游泳隊(duì)員中選擇4人組成接力隊(duì)，參加學(xué)校的4100m混合泳接力比賽5名隊(duì)員4種泳姿的百米平均成績(jī)?nèi)绫?-9所示，問應(yīng)如何選拔隊(duì)員組成接力隊(duì)？如果最近隊(duì)員丁的蛙泳成績(jī)有較大退步，只有1152；而隊(duì)員戊經(jīng)過艱苦訓(xùn)練自由泳成績(jī)有所進(jìn)步，達(dá)到575，組成接力隊(duì)的方案是否應(yīng)該調(diào)整？表4.9各隊(duì)員4種泳姿的百米平均成績(jī)甲乙丙丁戊蝶泳仰泳蛙泳自由泳1068115612758657210610645311810781246594110114210965721074111123810243.引例3 原油的采購與加工問題某公司用兩種原油（A和B）混合加工成兩種汽油（甲

35、和乙），甲、乙兩種汽油含原油A的最低比例分別為50%和60%，每噸售價(jià)分別為4800元和5600元該公司現(xiàn)有原油A和B的庫存量分別為500噸和1000噸，還可以從市場(chǎng)上買到不超過1500噸的原油A原油A的市場(chǎng)價(jià)為：購買量不超過500噸時(shí)的單價(jià)為10000元/噸；購買量超過500噸但不超過1000噸時(shí)，其超過500噸的部分8000元/噸；購買量超過1000噸時(shí)，超過1000噸的部分6000元/噸該公司應(yīng)如何安排原油的采購和加工？4.3.2 模型的建立與求解1.模型一的建立與求解針對(duì)模型一，顯然決策變量應(yīng)為生產(chǎn)小、中、大三種類型汽車的數(shù)量，分別設(shè)為，于是可得如下的線性規(guī)劃模型：目標(biāo)函數(shù)：約束條件：

36、使用Lingo求解，得到輸出：目標(biāo)函數(shù)值為632.2581；決策變量的值分別為：最優(yōu)解中出現(xiàn)了小數(shù)，顯然不合適如果在上述模型中再加入整數(shù)約束，即可解決此類問題求解Lingo程序如下：ax=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x360000;gin(x1);gin(x2);gin(x3);end程序最后一行是3個(gè)變量均為整數(shù)的約束運(yùn)行該程序可得如下輸出結(jié)果：目標(biāo)函數(shù)值為632；決策變量的值分別為：即問題要求的月生產(chǎn)計(jì)劃為：生產(chǎn)小型車64輛、中型車168輛，不生產(chǎn)大型車討論：對(duì)于問題中提出的如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80

37、輛的限制，上面得到的最優(yōu)解并不滿足這個(gè)條件這種類型的要求是實(shí)際生產(chǎn)中經(jīng)常提出的為此，我們提出兩種方法來處理這類問題 引入0-1變量，化為0-1規(guī)劃問題設(shè)只取0，1兩個(gè)值，則或等價(jià)于其中為相當(dāng)大的正數(shù)，本例可取1000（根據(jù)約束條件可知：都不可能超過1000）類似的有：其中都是0-1變量，編寫Lingo程序如下：max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x360000;x180*y1;x280*y2;x380*y3;gin(x1);gin(x2);gin(x3);bin(y1);bin(y2);bin(y3);end程序最后

38、一行是3個(gè)變量均為0-1變量的約束運(yùn)行該程序可得如下輸出結(jié)果：目標(biāo)函數(shù)值為610；決策變量的值分別為：即問題要求的月生產(chǎn)計(jì)劃為：生產(chǎn)小型車80輛、中型車150輛，不生產(chǎn)大型車 化為非線性規(guī)劃問題如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛等價(jià)于：式子左端是決策變量的非線性函數(shù)，加上這些約束條件構(gòu)成非線性規(guī)劃模型編寫Lingo程序如下：max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x30;x2*(x2-80)0;x3*(x3-80)0;gin(x1);gin(x2);gin(x3);end求解結(jié)果與0-1規(guī)劃模型的結(jié)果完全一致由于非

39、線性規(guī)劃模型的結(jié)果常依賴于初值的選擇，且運(yùn)行時(shí)間相對(duì)較長(zhǎng)，因此，一般盡量不用非線性規(guī)劃來求解2.模型二的建立與求解針對(duì)模型二，決策變量可以考慮0-1變量，建立0-1規(guī)劃模型記甲乙丙丁戊分別為隊(duì)員；記蝶泳、仰泳、蛙泳、自由泳分別為泳姿；記隊(duì)員的第種泳姿的百米平均成績(jī)?yōu)?；設(shè)為0-1變量，取值0表示隊(duì)員不參加第種泳姿的比賽，取值1表示隊(duì)員參加第種泳姿的比賽，于是可得如下的0-1規(guī)劃模型：目標(biāo)函數(shù)：約束條件：首先將題目所給數(shù)據(jù)標(biāo)準(zhǔn)化（單位：秒），編寫Lingo程序如下：model:title:混合泳接力隊(duì)的選拔;sets:duiyuan/1.5/:;yongzi/1.4/:;link(duiyuan,

40、yongzi):c,x;endsetsdata:c=66.8 75.6 87 58.6 57.2 66 66.4 53 78 67.8 84.6 59.4 70 74.2 69.6 57.2 67.4 71 83.8 62.4; enddatamin=sum(link:c*x);for(duiyuan(i):sum(yongzi(j):x(i,j)1;);for(yongzi(j):sum(duiyuan(i):x(i,j)=1;);for(link:bin(x););end求解得到結(jié)果為：，其它變量為0，成績(jī)?yōu)椋?53.2秒，即應(yīng)當(dāng)選派甲乙丙丁4人組成接力隊(duì)，分別參加自由泳、蝶泳、仰泳、蛙泳

41、的比賽討論：如果最近隊(duì)員丁的蛙泳成績(jī)有較大退步，只有1152；而隊(duì)員戊經(jīng)過艱苦訓(xùn)練自由泳成績(jī)有所進(jìn)步，達(dá)到575，則將由原來的69.6秒修改為75.2秒；將由原來的62.4秒改為57.5秒使用修改后的新數(shù)據(jù)代入模型再次求解，得到如下結(jié)果：，其它變量為0，成績(jī)?yōu)椋?57.7秒，即應(yīng)當(dāng)選派乙丙丁戊4人組成接力隊(duì)，分別參加蝶泳、仰泳、蛙泳、自由泳的比賽評(píng)注：本例屬于這樣一類分派問題：有若干項(xiàng)任務(wù)，每項(xiàng)任務(wù)必須有一人且只能有一人承擔(dān)，每人也只能承擔(dān)其中一項(xiàng)，不同人員承擔(dān)不同任務(wù)的收益（或成本）不同，問題是怎樣分派各項(xiàng)任務(wù)使總收益最大（或總成本最?。┧址Q為指派問題由本例的研究可知，當(dāng)遇到諸如是否參加、

42、是否選擇、是否成立等二值問題時(shí)，可采用0-1變量，建立0-1規(guī)劃模型進(jìn)行求解3.模型三的建立與求解問題分析安排原油采購、加工的目的是利潤(rùn)最大，題目中給出的是兩種汽油的售價(jià)和原油A的采購價(jià)，利潤(rùn)為銷售汽油的收入與購買原油A的支出之差這里的難點(diǎn)在于原油A的采購價(jià)與購買量的關(guān)系比較復(fù)雜，是分段函數(shù)關(guān)系，能否及如何用線性規(guī)劃、整數(shù)規(guī)劃模型加以處理是關(guān)鍵所在在實(shí)際問題中，目標(biāo)函數(shù)中經(jīng)常遇到包含分段函數(shù)的情形，對(duì)這類問題的討論研究是十分必要的針對(duì)模型三，設(shè)原油A的購買量為，根據(jù)題目所給數(shù)據(jù)，采購的支出可表示為如下的分段函數(shù)（以下價(jià)格以千元噸為單位）：設(shè)原油A用于生產(chǎn)甲、乙兩種汽油的數(shù)量分別為：和；原油B用

43、于生產(chǎn)甲、乙兩種汽油的數(shù)量分別為：和，則總收入為：，于是目標(biāo)函數(shù)為：約束條件包括兩種汽油用的原油A、原油B庫存量的限制，和原油A購買量的限制，以及兩種汽油含原油A的比例，它們表示為：0-1規(guī)劃模型的建立與求解由于目標(biāo)函數(shù)中包含分段函數(shù)，因此，上面的模型不是線性規(guī)劃模型，事實(shí)上，使用一般的非線性規(guī)劃也很難求解該問題為了解決這類問題，可以考慮引入0-1變量，建立0-1規(guī)劃模型進(jìn)行求解設(shè)是0-1變量，價(jià)格區(qū)間、與分別對(duì)應(yīng)：表示在第個(gè)價(jià)格區(qū)間購買原油A；表示在第個(gè)價(jià)格區(qū)間不購買原油A購買量對(duì)應(yīng)于于是有：應(yīng)該注意到，只有當(dāng)以10千元噸的價(jià)格購買滿500噸時(shí)，才能以8千元噸的價(jià)格購買；只有當(dāng)以10千元噸的

44、價(jià)格購買滿500噸，而且以8千元噸的價(jià)格購買也滿500噸時(shí)，才能以6千元噸的價(jià)格購買因此，需要增加如下的線性約束：由上面的約束可以看出：，顯然滿足購買原油A的價(jià)格要求編寫Lingo程序如下：max=4.8*x11+4.8*x21+5.6*x12+5.6*x22-10*x1-8*x2-6*x3;x-x1-x2-x3=0;x11+x12-x500;x21+x221000;x0;0.4*x12-0.6*x220;x1500*y1;500*y2x1;x2500*y2;500*y3x2;x3500*y3;bin(y1);bin(y2);bin(y3);end運(yùn)行該程序可得如下輸出結(jié)果：目標(biāo)函數(shù)值為500

45、0千元；決策變量的值分別為：，其它都是0即用原油A1500噸（包括庫存的500噸以及以10千元價(jià)格購買的500噸和以8千元價(jià)格購買的500噸），原油B1000噸，生產(chǎn)2500噸的汽油乙，獲利5000千元設(shè)原油A用于生產(chǎn)甲、乙兩種汽油的數(shù)量分別為：和；原油B用于生產(chǎn)甲、乙兩種汽油的數(shù)量分別為：和，則總收入為：，于是目標(biāo)函數(shù)為：非線性規(guī)劃模型的建立與求解與0-1規(guī)劃模型類似，首先引入變量分別表示以10千元噸、8千元噸、6千元噸采購的原油A的噸數(shù)，總支出，且 為了限制先用高價(jià)格購買，在以較低價(jià)格購買，可使用下面的非線性約束條件： 同理可得：編寫Lingo程序如下：max=4.8*x11+4.8*x2

46、1+5.6*x12+5.6*x22-10*x1-8*x2-6*x3;x-x1-x2-x3=0;x11+x12-x500;x21+x221000;x0;0.4*x12-0.6*x220;(x1-500)*x2=0;(x2-500)*x3=0;x1500;x2500;x3500;end運(yùn)行該程序可得如下輸出結(jié)果：目標(biāo)函數(shù)值為4800千元；決策變量的值分別為：，其它都是0即用庫存的原油A500噸，原油B500噸，生產(chǎn)1000噸的汽油甲，獲利4800千元，該方案不需要購買原油A若使用Lingo全局求解程序求解該程序，得到的結(jié)果與0-1規(guī)劃模型的結(jié)果幾乎完全一致4.3.3 應(yīng)用實(shí)例例1飛行計(jì)劃安排問題甲

47、乙雙方的一場(chǎng)戰(zhàn)爭(zhēng)中，一部分甲方部隊(duì)被乙方部隊(duì)包圍長(zhǎng)達(dá)4個(gè)月由于乙方封鎖了所有水陸交通通道，被包圍的甲方部隊(duì)只能依靠空中交通維持供給運(yùn)送4個(gè)月的供給分別需要2次，3次，3次，4次飛行，每次飛行編隊(duì)由50架飛機(jī)組成（每架飛機(jī)需要3名飛行員），可以運(yùn)送10萬噸物質(zhì)每架飛機(jī)每個(gè)月只能飛行一次，每名飛行員每個(gè)月也只能飛行一次在執(zhí)行完運(yùn)輸任務(wù)后的返回途中有20%的飛機(jī)會(huì)被乙方部隊(duì)擊落，相應(yīng)的飛行員也因此犧牲或失蹤在第一個(gè)月開始時(shí)，甲方擁有110架飛機(jī)和330名熟練的飛行員在每個(gè)月開始時(shí)，甲方可以招聘新飛行員和購買新飛機(jī)新飛機(jī)必須經(jīng)過一個(gè)月的訓(xùn)練才能投入飛行每名熟練飛行員可以作為教練每個(gè)月指導(dǎo)20名飛行員（

48、包括他自己在內(nèi)）進(jìn)行訓(xùn)練每名飛行員在完成一個(gè)月的飛行任務(wù)后，必須有一個(gè)月的帶薪假期，假期結(jié)束后才能再投入飛行已知各項(xiàng)費(fèi)用（單位略去）如表4-10所示，請(qǐng)你為甲方安排一個(gè)飛行計(jì)劃表4.10飛行計(jì)劃的有關(guān)數(shù)據(jù)第1個(gè)月第2個(gè)月第3個(gè)月第4個(gè)月新飛機(jī)價(jià)格閑置的熟練飛行員報(bào)酬教練和新飛行員報(bào)酬（包括訓(xùn)練費(fèi)用）執(zhí)行飛行任務(wù)的熟練飛行員報(bào)酬休假期間的熟練飛行員報(bào)酬200.07.010.09.05.0195.06.99.98.94.9190.06.89.89.84.8185.06.79.79.74.7如果每名熟練飛行員可以作為教練每個(gè)月指導(dǎo)不超過20名飛行員（包括他自己在內(nèi)）進(jìn)行訓(xùn)練，模型和結(jié)果有哪些改變？解

49、這個(gè)問題看起來很復(fù)雜，但只要理解了這個(gè)例子中所描述的事實(shí)，其實(shí)建立優(yōu)化模型并不困難首先可以看出，執(zhí)行飛行任務(wù)以及執(zhí)行飛行任務(wù)后休假的熟練飛行員數(shù)量是常數(shù)，所以這部分費(fèi)用（報(bào)酬）是固定的，在優(yōu)化目標(biāo)中可以不考慮設(shè)4個(gè)月開始時(shí)甲方新購買的飛機(jī)數(shù)量分別為架；閑置的飛機(jī)數(shù)量分別為架；4個(gè)月中，教練和新飛行員數(shù)量分別為；閑置的熟練飛行員數(shù)量分別為人于是可得如下整數(shù)規(guī)劃模型：目標(biāo)函數(shù)：約束條件：飛機(jī)數(shù)量限制：4個(gè)月中執(zhí)行飛行任務(wù)的飛機(jī)分別為100，150，150，200（架），但只有80，120，120，160（架）能夠返回供下個(gè)月使用第1個(gè)月 第2個(gè)月 第3個(gè)月 第4個(gè)月 飛行員數(shù)量限制：4個(gè)月中執(zhí)行飛

50、行任務(wù)的熟練飛行員分別為300，450，450，600（人），但只有240，360，360，480能返回（下個(gè)月一定休假）第1個(gè)月 第2個(gè)月 第3個(gè)月 第4個(gè)月 所有變量都要求非負(fù)，且為整數(shù)編寫程序Lingo如下：min=200*x1+195*x2+190*x3+185*x4+10*u1+9.9*u2+9.8*u3+9.7*u4+7*v1+6.9*v2+6.8*v3+6.7*v4;y1=10;y1+x1-y2=70;y2+x2-y3=30;y3+x3-y4=80;0.05*u1+v1=30;u1+v1-0.05*u2-v2=450;u2+v2-0.05*u3-v3=210;u3+v3-0.05

51、*u4-v4=240;gin(x1);gin(x2);gin(x3);gin(x4);gin(y1);gin(y2);gin(y3);gin(y4);gin(u1);gin(u2);gin(u3);gin(u4);gin(v1);gin(v2);gin(v3);gin(v4);end運(yùn)行該程序可得如下輸出結(jié)果：目標(biāo)函數(shù)值為42324.40；決策變量的值分別為：；討論：如果每名熟練飛行員可以作為教練每個(gè)月指導(dǎo)不超過20名飛行員（包括他自己在內(nèi)）進(jìn)行訓(xùn)練，此時(shí)可將教練與新飛行員分開設(shè)4個(gè)月教練的數(shù)量分別為，新飛行員的數(shù)量分別為，其它決策變量不變飛行員的數(shù)量限制約束為：第1個(gè)月 第2個(gè)月 第3個(gè)月

52、第4個(gè)月 另外還需要加上教練與新飛行員的數(shù)量關(guān)系約束：編寫程序Lingo如下：min=200*x1+195*x2+190*x3+185*x4+10*u1+9.9*u2+9.8*u3+9.7*u4+7*v1+6.9*v2+6.8*v3+6.7*v4+10*w1+9.9*w2+9.8*w3+9.7*w4;y1=10;y1+x1-y2=70;y2+x2-y3=30;y3+x3-y4=80;u1+v1=30;u1+v1+w1-u2-v2=450;u2+v2+w2-u3-v3=210;u3+v3+w3-u4-v4=240;w1-19*u10;w2-19*u20;w3-19*u30;w4-19*u4sum

53、(xfz(i):c1(i,1)*x(i,1);sum(xfz(i):c1(i,4)*x(i,4)sum(xfz(i):c1(i,3)*x(i,3);sum(xfz(i):c1(i,6)*x(i,6)sum(xfz(i):c1(i,5)*x(i,5);sum(xfz(i):c1(i,7)*x(i,7)sum(xfz(i):c1(i,6)*x(i,6);for(link:bin(x););end求解得到如下結(jié)果：決策變量的值分別為：，其它變量為0；目標(biāo)函數(shù)值為335.00即消防站1應(yīng)向火警地點(diǎn)2派2輛車，向火警地點(diǎn)3派1輛車；消防站2應(yīng)向火警地點(diǎn)1派2輛車；消防站3應(yīng)向火警地點(diǎn)3派2輛車；最小總損

54、失為335.00經(jīng)過檢驗(yàn)可以發(fā)現(xiàn)，此時(shí)的派車方案是合理的例2面試順序問題有4名同學(xué)到一家公司參加三個(gè)階段的面試：公司要求每個(gè)同學(xué)都必須首先找公司秘書初試，然后到部門主管處復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊(duì)（即在任何一個(gè)階段4名同學(xué)的順序是一樣的）由于4名同學(xué)的專業(yè)背景不同，所以每人在三個(gè)階段的面試時(shí)間也不同，如表4-12所示這4名同學(xué)約定他們?nèi)棵嬖囃暌院笠黄痣x開公司，假定現(xiàn)在是早晨8:00，請(qǐng)問他們最早何時(shí)能離開公司？表4.12面試時(shí)間要求秘書初試主管復(fù)試經(jīng)理面試同學(xué)甲同學(xué)乙同學(xué)丙同學(xué)丁13102081520161020181015解實(shí)際上，這個(gè)問題就是要安排4名同學(xué)的面試順序，使完

55、成全部面試所花費(fèi)的時(shí)間最少設(shè)表示第名同學(xué)參加第階段面試需要的時(shí)間，表示第名同學(xué)參加第階段面試的開始時(shí)刻（不妨記早上8:00面試開始為0時(shí)刻），（；），為完成全部面試所花費(fèi)的最少時(shí)間；用0-1變量表示第名同學(xué)是否排在第名同學(xué)前面（1表示是，0表示否）優(yōu)化目標(biāo)為：約束條件：時(shí)間先后次序約束（每人只有參加完前一個(gè)階段的面試后才能進(jìn)入下一個(gè)階段）：每個(gè)階段同一時(shí)間只能面試1名同學(xué)當(dāng)時(shí)，即當(dāng)?shù)诿瑢W(xué)排在第名同學(xué)前面時(shí)，則有：；當(dāng)時(shí)，即當(dāng)?shù)诿瑢W(xué)排在第名同學(xué)后面時(shí)，則有：這類約束條件是條件約束，為此，可利用0-1變量，將條件約束改為無條件約束：（）等價(jià)于無條件約束：（）等價(jià)于無條件約束：目標(biāo)函數(shù)的處理方法

56、是將非線性的優(yōu)化目標(biāo)改寫成如下線性優(yōu)化目標(biāo)：目標(biāo)函數(shù)為；增加約束條件：編寫程序Lingo如下：model:title:面試順序問題;sets:tongxue/1.4/:;mianshi/1.3/:;link1(tongxue,tongxue)|&1#lt#&2:y;link(tongxue,mianshi):t,x;endsetsdata:t=13 15 20 10 20 18 20 16 10 8 10 15;enddataOBJmin=tt;for(tongxue(i):x(i,3)+t(i,3)tt;);for(link(i,j)|j#lt#3:x(i,j)+t(i,j)x(i,j+1)

57、;for(link(i,j):for(tongxue(k)|k#gt#i:x(i,j)+t(i,j)-x(k,j)tt*y(i,k););for(link(i,j):for(tongxue(k)|k#gt#i:x(k,j)+t(k,j)-x(i,j)tt*(1-y(i,k););for(link1:bin(y););End求解得到如下結(jié)果：目標(biāo)函數(shù)值為84；決策變量的值分別為：，即所有面試完成至少需要84分鐘，面試順序是丁、甲、乙、丙，早上8:00面試開始，最早9:24面試可以全部結(jié)束4.4目標(biāo)規(guī)劃目標(biāo)規(guī)劃是由線性規(guī)劃發(fā)展演變而來的線性規(guī)劃考慮的是只有一個(gè)目標(biāo)函數(shù)的問題，而實(shí)際問題中往往需要考

58、慮多個(gè)目標(biāo)函數(shù)，這些目標(biāo)不僅有主次關(guān)系，而且有的還互相矛盾這些問題用線性規(guī)劃求解比較困難，因而提出了目標(biāo)規(guī)劃4.4.1問題的提出1.引例 生產(chǎn)安排問題某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，需要用到，三種設(shè)備，關(guān)于產(chǎn)品的盈利與使用設(shè)備的工時(shí)及限制如表4-13所示問：該企業(yè)應(yīng)如何安排生產(chǎn)，使得在計(jì)劃期內(nèi)總利潤(rùn)最大？表4.13生產(chǎn)產(chǎn)品使用設(shè)備的工時(shí)、限制和產(chǎn)品的盈利甲乙設(shè)備的生產(chǎn)能力h(h/件)(h/件)(h/件)盈利(元/件)240200205300121615企業(yè)的經(jīng)營(yíng)目標(biāo)不僅僅是利潤(rùn)，還需要考慮下面的因素（目標(biāo)）：力求利潤(rùn)指標(biāo)不低于1500元；考慮到市場(chǎng)需求，甲、乙兩種產(chǎn)品的產(chǎn)量比應(yīng)盡量保持1:2；設(shè)備為

59、貴重設(shè)備，嚴(yán)格禁止超時(shí)使用；設(shè)備可以適當(dāng)加班，但要控制；設(shè)備既要求充分利用，又盡可能不加班在重要性上，設(shè)備是設(shè)備的3倍從上述問題可以看出，僅用線性規(guī)劃方法是不夠的，需要借助于目標(biāo)規(guī)劃的方法進(jìn)行建模求解2.線性規(guī)劃建模的局限性一般來說，在求解實(shí)際問題時(shí)，線性規(guī)劃模型存在以下局限性：線性規(guī)劃要求所求解的問題必須滿足全部的約束，而實(shí)際問題中并非所有約束都需要嚴(yán)格的滿足；線性規(guī)劃只能處理單目標(biāo)的優(yōu)化問題，而對(duì)一些次目標(biāo)只能轉(zhuǎn)化為約束處理，而在實(shí)際問題中，目標(biāo)和約束是可以互相轉(zhuǎn)化的，處理時(shí)不一定嚴(yán)格區(qū)分；線性規(guī)劃在處理問題時(shí)，將各個(gè)約束（也可以看做目標(biāo)）的地位看成同等重要，而在實(shí)際問題中，各個(gè)目標(biāo)的重要

60、性既有層次上的差別，也有在同一層次上不同權(quán)重的差別；線性規(guī)劃尋找最優(yōu)解，而許多實(shí)際問題只需要找到滿意解就可以了4.4.2目標(biāo)規(guī)劃的基本概念1.設(shè)置偏差變量用偏差變量來表示實(shí)際值與目標(biāo)值之間的差異，令表示超出目標(biāo)的差值，稱為正偏差變量；表示未達(dá)到目標(biāo)的差值，稱為負(fù)偏差變量其中與至少有一個(gè)為0當(dāng)實(shí)際值超過目標(biāo)值時(shí)，有；當(dāng)實(shí)際值未達(dá)到目標(biāo)值時(shí)，有；當(dāng)實(shí)際值與目標(biāo)值一致時(shí)，有2.統(tǒng)一處理目標(biāo)與約束在目標(biāo)規(guī)劃中，約束條件有兩類：一類是對(duì)資源有嚴(yán)格限制，同線性規(guī)劃的處理方法相同，用嚴(yán)格的等式或不等式約束來處理，這類約束稱為剛性約束；另一類約束是可以不嚴(yán)格限制的，連同原線性規(guī)劃的目標(biāo)，構(gòu)成柔性約束在引例中，