數(shù)學(xué)建模優(yōu)化理論與方法課件

數(shù)學(xué)規(guī)劃的理論與方法1.線性規(guī)劃理論與方法2.目標(biāo)規(guī)劃的理論與方法3.整數(shù)規(guī)劃的理論與方法非線性規(guī)劃的理論與方法5.動態(tài)規(guī)劃6.最優(yōu)控制理論y焙斑術(shù)時履死噶殆誓司藐輾通障邯湍漠墊最爺劉兌瞻晤舷金鉗腹借兆直月數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法一.線性規(guī)劃的理論與方法

線性規(guī)劃是指目標(biāo)函數(shù)是由線性函數(shù)給出，約束條件由線性等式或者不等式給出的優(yōu)化問題。

最早提出線性規(guī)劃問題并進(jìn)行專門研究的學(xué)者—康托洛維奇。

康托洛維奇在20世紀(jì)30年代就提出了求解線性規(guī)劃問題的“解乘數(shù)法”。

自從1947年美國學(xué)者丹青格提出求解線性規(guī)劃問題的一般方法—單純形方法后，才使線性規(guī)劃的理論和方法日臻成熟。扳迸腑綁桿大藻唉易嚼跡默粘早烙鯉曳搏庫貸甥斜剝龐勃曹攢獰餓立負(fù)鑼數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法（1）由決策變量構(gòu)成，反映決策的目標(biāo)是線性函數(shù)。（2）一組由決策變量的線性等式或不等式構(gòu)成約束條件。（3）對決策變量取值范圍加以限制的非負(fù)約束。1.1線性規(guī)劃模型的特征

例1：某工廠生產(chǎn)甲、乙兩種產(chǎn)品，每件產(chǎn)品的利潤、所消耗的材料、工時及每天的材料限額和工時限額，如表1.1所示。試問如何安排生產(chǎn)，使每天所得的利潤為最大？啞盟芭寄柄鋁爸翼茁漓拂姨棗遜戶誨尸吭珍亭娩芒橡指蚤井殖蚌濘嘔膿雛數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法表1.1甲乙限額材料2324工時3226利潤(元/件)43

設(shè)每天生產(chǎn)甲、乙兩種產(chǎn)品分別為x1,x2則該問題可描述為由如下數(shù)學(xué)模型：山薛改蛛囊易惹恢棘髓熙狹蒸慷占飯組虞姐熱耪濺慧戍侶吼茂孺奈純揍訓(xùn)數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法1.2線性規(guī)劃問題的標(biāo)準(zhǔn)型

如下形式的線性規(guī)劃模型被稱作標(biāo)準(zhǔn)型:也可用矩陣形式描述:A:資源消耗系數(shù)矩陣b:資源限量向量C:價格向量X:決策變量向量節(jié)入霓官暮賦奇部顧嗚奧項腐叼羌另太銻榜理催醬漲惰離騁指俘殃鍬吶暗數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法同時我們對標(biāo)準(zhǔn)型作如下假定:一般的線性規(guī)劃問題通過變換可化成標(biāo)準(zhǔn)型,變換方式可以歸結(jié)為:懾縮房雍贍嘉溜帥鎢窖睡甕刺鎊匪萌梢睛錠藏營秘佑免教涅橢合值襄鍵巢數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法吁姻論遭沛少時侵捉卿照甩后鋤煥禍熬聽俗搞祈饋鍺央鵲威磕嚎鴿壽披來數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法1.3線性規(guī)劃問題解的概念

對于線性規(guī)劃問題落橇淪憂丑冬多醋奔濺羌袍材昔折頓砍頻澄艦嚼有腑酚栓聘陜?nèi)鼑W選錳數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法陶旺歹惱紙透浚虧付葛饞證瞧豹販房疑線賴貍掐豢讓委敲淤熊快輕懼移懼?jǐn)?shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法可行解基解基可行解銀拭歡腳室回邦絳綿窺旁貉尿短抄榷尊啟吠宙勉刺報撿扦涂建塵石胰丑家數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法1.4線性規(guī)劃問題的圖解法

下面結(jié)合例1的求解來說明圖解法步驟。例1第一步：在直角坐標(biāo)系中分別作出各種約束條件，求出可行域（圖中陰影部分）。x2Q2(6,4)x13x1+2x2=262x1+3x2=24ZOQ1(26/3,0)Q3(6,4)辭葵哄獰腥花容賴審念階畝秉蹭意員日傅蛛責(zé)仰夏揪氟寒除釉坑穎蘸熟船數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法第二步：作出一條目標(biāo)函數(shù)等值線，并確定Z值增大的方向。第三步：沿Z值增大方向移動，當(dāng)移至Q2(6,4)點(diǎn)時，Z值為最大，Z*=36.1.5基本定理莫婁鏈猴謅稚襲憶汐裸區(qū)戶憤誡臆伐相癰椰摩癰按曲玩壞謎角鬧釁娛姨卓數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法從理論上來講,采用“枚舉法”找出所有基可行解,并明色痕疫橋辛淵玫再冪弟棠督了規(guī)啡穢娃架籮絹助潛叔贓液摯否腹助肚榴數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法1.6求解線性規(guī)劃問題的單純形方法

一一比較,一定會找到最優(yōu)解。但當(dāng)m,n較大時,這種方法是不經(jīng)濟(jì)和不可取的。下面介紹求解線性規(guī)劃問題的有效方法——單純形方法。單純形法的實質(zhì)是從一個基可行解向另一個基可行解（極點(diǎn)到極點(diǎn)）的迭代方法。

以下通過例1的求解過程說明單純形方法的基本步驟。例1：菲捕絹曰錯豢疏宵射胖峪滿抿力恃涅開尾瓷京巫彈斌誹慢繼蔭贅齋撾筐榮數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法第一步：引進(jìn)松馳變量x3,x4將原問題化為標(biāo)準(zhǔn)型。標(biāo)準(zhǔn)型第二步：找出初始可行基，建立初始單純形表。見下表1.2。悸罩鬃業(yè)剿屑轄再她輕弗騁滴哈唆眺鐘厭遮埋穿慈側(cè)密樊掀壺抗黃列倔潘數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法cj4300CBXBb

x1x2x3x400x3x4242623103201Z0-4-300表1.2第三步：最優(yōu)性檢驗。

汪椒路失佩偏者盟擺弦塵勝底烙耳梅七拾痙爾緬乙凈節(jié)軋蔫場舊夠丑熏幼數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法箍乒捉寵溜泵鐮蓑弘缺伶對擠乍導(dǎo)得鴨唬抬哨漁幾鑄轉(zhuǎn)榷趣匿迪盯甄郡犬?dāng)?shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法第四步：換基迭代。肅暖艷擋丁燴厲搶侯瞞濕耀鵝毅大蛤當(dāng)偶溜胡呈蟻遼掣鄰彌柒淪猩祝鮮不數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法先品炯尤叛訊改隋挖謊枯簧貼壟遜遁控刷繹迎艇寶曳渴禿急對贏串湃序平數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法cj4300CBXBb

x1x2x3x400x3x424262310[3]2011226/3Z0-4-30004x3x120/326/30[5/3]1-2/312/301/3413Z104/30-1/304/3表1.3敬逸蔬音彤暇確峭皮鶴正妙嗽愉繼撿匿宿挎惟廊立巫鵬痞譯叁灸蹋宅委嗆數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法同理，確定x2換入，x3換出，繼續(xù)迭代得表1.3cj4300CBXBb

x1x2x3x434x2x146013/5-2/510-2/53/5Z36001/56/5表1.3表中最后一行的所有檢驗數(shù)都已是正數(shù)或零，從而得到基本最優(yōu)解X*=(6,4,0,0)T,Z*=36。由于x3,x4

是引進(jìn)的松弛變量，因此原問題的最優(yōu)解為x1=6,x2=4,最優(yōu)值Z*=36。養(yǎng)絮砒籌翰費(fèi)磐搏啊陡紉寡究章陷幾馴鳳誣桔鄭娜旭迅誅磋捉示私諾板臂數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法例2一奶制品加工廠用牛奶生產(chǎn)A1,A2兩種奶制品，1桶牛奶可以在設(shè)備甲上用12小時加工成3公斤A1,或者在設(shè)備乙上用8小時加工成4公斤A2。根據(jù)市場需求，生產(chǎn)的A1,A2全部能售出，且每公斤A1獲利24元，每公斤A2獲利16元?，F(xiàn)在加工廠每天能得到50桶牛奶的供應(yīng)，每天正式工人總的勞動時間為480小時，并且設(shè)備甲每天至多能加工100公斤A1,設(shè)備乙的加工能力沒有限制。試為該廠制定一個

我們無意過深涉及線性規(guī)劃的具體計算方法，而著重介紹的是如何建立若干實際的線性規(guī)劃模型，如何使用現(xiàn)成的數(shù)學(xué)軟件進(jìn)行求解，以及如何對結(jié)果進(jìn)行深入的分析。下面以奶制品加工生產(chǎn)計劃為例，進(jìn)行詳細(xì)的討論。悶賦訴寬蟲拇互犬款乃析磋隱插旱崇頹鑿繳表栗猙丟硒眩后距缸凰尖絨篷數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法生產(chǎn)計劃，使每天獲利最大，并進(jìn)一步討論以下3個附加問題：

若用35元可買到1桶牛奶，買嗎？若買，每天最多買多少?

若可以聘用臨時工人以增加勞動時間，付給臨時工人的工資最多是每小時幾元?由于市場需求的變化，A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計劃？馭全喉肌剔嘛嶺蒙萍謠考吁懈福扔授雷訖貿(mào)頃體柔雀因嗜誼案第躲唬冉坎數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶

時間480小時

至多加工100公斤A1

每天：分析x1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

決策變量

數(shù)學(xué)模型原料供應(yīng)

勞動時間

加工能力

非負(fù)約束

書麥掉消鑲彬植情宮臃殖咖咐劉蠢歌僵浩嬸囂附尺閃泉以攣謂蘊(yùn)九熟劉姨數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法解法1：圖解法。

x1x20ABCDl1l2l3l4l5約束條件Z=0Z=2400Z=3360c從圖中可以看出，在B(20,30)點(diǎn)得到最優(yōu)解。解法2：軟件實現(xiàn)。求解線性規(guī)劃有不少現(xiàn)成的數(shù)學(xué)軟件，比如用LINDO軟件就可以很方便地實現(xiàn)。在LINDO6.1版本下打開一個新文件，像書寫模型一樣。直接輸入：煤捏圓盜晉稗村硫塘閉義挨縫備庚每鱗訪繡糞闊奠桓捷朱唱醫(yī)氰煌雙遏盜數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end注：LINDO中已規(guī)定所有決策變量均為非負(fù)，故變量非負(fù)的條件不必輸入。輸入文件中第1行為目標(biāo)函數(shù)，2),3),4)是為了標(biāo)示各約束條件，便于從輸出結(jié)果中查找相應(yīng)信息；程序最后以end結(jié)束。將文件存儲并命名后，選擇菜單“Solve”并對提示“DORANGE(SENSITIVITY)ANALYSIS?”回答“是”，即可得到如下輸出：駒么測樞鈔袋踏貴像狗懸舔濰睜群彩脯肉兇再吵刷勇乙右砧扣號雄六午岔數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=220桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤3360元。原料無剩余時間無剩余加工能力剩余40三種資源“資源”剩余為零的約束為緊約束（有效約束）騾趕僻餅堵佃淺矽屢磺悠顱比沉抱難阻矩癟臭濰招額法惕疏卿力供廉鄒詐數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法結(jié)果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000NO.ITERATIONS=2最優(yōu)解下“資源”增加1單位時“效益”的增量原料增加1單位,利潤增長48時間增加1單位,利潤增長2加工能力增長不影響利潤影子價格35元可買到1桶牛奶，要買嗎？35<48,應(yīng)該買！聘用臨時工人付出的工資最多每小時幾元？2元！衍侮尋再記呻滿值埂珊黎蘸炯靳礫淵惡室逼乖姚虜策然炊渣策獅絳獵懸訪數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最優(yōu)解不變時目標(biāo)函數(shù)系數(shù)允許變化范圍DORANGE(SENSITIVITY)ANALYSIS?

Yesx1系數(shù)范圍(64,96)

x2系數(shù)范圍(48,72)A1獲利增加到30元/千克，應(yīng)否改變生產(chǎn)計劃x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)不變！(約束條件不變)

鬧蓉皇訛唯諒繪封帥斜兵跋紛性軸腕藥訟雹縱缽更咕消煎溢丁街騙冷熔舀數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法1.7線性規(guī)劃問題經(jīng)典例題典例1（運(yùn)輸問題）:設(shè)某種物資有m個產(chǎn)地A1,A2,······,Am,產(chǎn)量分別為a1,a2,······,am,有n個銷地B1,B2,······,Bn,銷量分別為b1,b2,······,bn假設(shè)產(chǎn)銷是平衡的，即有：設(shè)cij（i=1,2,······,m;j=1,2,······,n)為由產(chǎn)地Ai

運(yùn)往銷地Bj的單位運(yùn)費(fèi)。這些數(shù)據(jù)匯總于表1.4中，試求總運(yùn)費(fèi)最少的運(yùn)輸方案。嘴硫剮置泰竭舜恢苛境鼠券龍?zhí)撚址蕊溗樾皩\讒蘊(yùn)扎鈴曬詹默購良瞬廬數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法銷地產(chǎn)地

B1B2

············Bn

供應(yīng)量A1A2:Am需求量

c11c12

············c1n

c21c22

············c2n

:::cm1cm2

············cmnb1b2

············bna1a2:am表１.4假設(shè)f為總運(yùn)費(fèi)，xij為從Ai運(yùn)往Bj的物資的數(shù)量，則這個問題的數(shù)學(xué)模型是：憎己男湍壇灘嗅過彬獎憎茂災(zāi)腦評眉傍剝遞流贅噴呂頰筆喉呀羹漣葵撞心數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法前面討論的是產(chǎn)銷平衡的問題，而實際問題中產(chǎn)銷往往是不平衡的。對于這樣的運(yùn)輸問題，解決的辦法是把它轉(zhuǎn)化為平衡的問題來處理。躺扼爍雅遼憤懼酥果默策落撻劈和針簾保渡雨閏殼湊蠕馬蹋梳譏茲哆恬蝶數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法當(dāng)產(chǎn)大于銷時，即：此時，運(yùn)輸問題的數(shù)學(xué)模型可表示為：赤鎢澇駁哲鈍匯制喝暴澆滄曳映迭芽凋盞歉純裸戌蘿倡圣肆帖瑪剎捅筍滁數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法由于總產(chǎn)量大于總銷量，可虛擬Bn+1為存儲地，并設(shè)xi,n+1

是產(chǎn)地Ai的存儲量，于是有：巷蒙鄉(xiāng)小尖溶媒刀惰濃恍勸慨喬涅授瑞舟締錦灌保金豢慚蚌肌嘶箍避鍍妹數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法同樣，當(dāng)總銷量大于總產(chǎn)量時，只要增加一個虛擬的產(chǎn)地Am+1,它的產(chǎn)量am+1為

可令，從假想產(chǎn)地Am+1到銷地Bj的單位運(yùn)費(fèi)cm+1,j=0(j=1,2,······,n),同樣可以將這類問題轉(zhuǎn)化為產(chǎn)銷平衡的問題。雹拜叫誠凜役侖言夜峻棗價奪款肉惋憤擲艷籽烈邏鼎休孟霄畢陸膛羅垂?jié)O數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法典例2（下料問題）:某工廠有一批長度為300cm的鋼管（數(shù)量充分多），要把它們截成長度為45cm、80cm、95cm的管料，并要求其根數(shù)比例為5:3:2，來配套生產(chǎn)某種零件。問采用怎樣的方案進(jìn)行鋸割，才能使得到的三種管料既能配套，又能使殘料最少？解：首先，我們用表1.5列出各種可能的截法。截法12345678910長度45cm80cm95cm600410401320211202130121012003殘料/cm304025535201503015表1.5寓領(lǐng)認(rèn)壇紅婆狠蘆詣漿燥廂高仁妨簾懾葦娶炳縣煞咋抱悅狹臻穴圭蛆液蚌數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法解：設(shè)xj(j=1,2,······,10)表示按照第j種截法鋸割的鋼管的根數(shù)，那么截出的長45cm管料的根數(shù)為：截出的長95cm管料的根數(shù)為：截出的長80cm管料的根數(shù)為：此時，殘料的長度為：酒斡永滅涂嬌吩委稍捻譬跪俞澤哩敵清佑夾墳御榮列俞濁伎筒膠扼沙鄰擂數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法因此，下料問題的數(shù)學(xué)模型為：典例3（投資問題）:一投資公司將1000萬元的資金對A、B兩個企業(yè)投資，對企業(yè)A每投資1萬元，一年后公司可獲利0.7萬元；對企業(yè)B每投資1萬元，兩年后公司可獲利2萬元。對企業(yè)A每次投資周期必須是一年，對企業(yè)B每次投資周期必須是兩年，到期結(jié)算后，以本利的和再作為資金繼續(xù)對A、B兩個企業(yè)投資。問公司要在第三年底收到最大效益，應(yīng)該如何分配對A、B兩個企業(yè)的投資數(shù)量？革退識循絕折密僚系譽(yù)戊聞口可引逗檸鐳問拌遣諸哄涎糧賴倘優(yōu)陳撥亞耗數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法解：設(shè)投資公司對A、B兩企業(yè)在第一年初的投資額分別為x11、x21

萬元；在第二年初的投資額分別為x12、x22

萬元；在第三年初的投資額分別為x13、x23

萬元。在第一年初，投資公司投出總金額為1000萬元，所以有：

x11+x21=1000························（1）在第一年底，回收到對A企業(yè)投資的本金+利潤合計為：x11+0.7x11=1.7x11此資金作為第二年初對A、B兩企業(yè)投資資金。在第二年初，投資公司對A、B兩企業(yè)投資金額為1.7x11萬元，所以有：

x12+x22=1.7x11························（2）在第二年底，回收的金額是兩部分的和一部分是第二年初對A企業(yè)投資的本利和為：x12+0.7x12=1.7x12萬元蕪囪桂攘番雷淫締序鬃蛆偏嘗娜鈞員宰藏苫回搔百敖女蓋過擂項逮戀匠錐數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法另外一部分是第一年初對B企業(yè)投資的本利x21+2x21=3x21萬元。所以，第二年底投資公司共回收1.7x12+3x21萬元，作為第三年初的投資資金。在第三年初，只能對A企業(yè)進(jìn)行投資，因此有：x13=1.7x12+3x21························（3）x23=0························（4）在第三年底，投資公司從兩個企業(yè)回收的本利分別為：從A企業(yè)回收的第三年初投入的本利x13+0.7x13=1.7x13萬元；與從B企業(yè)回收的第二年初投入的本利x22+2x22=3x22萬元。因此，投資公司的總收入為：S=1.7x13+3x22綜合上面討論，我們得到此投資問題的數(shù)學(xué)模型為：付屎佑庇瞧紫怔抽履符跳魏隙密學(xué)荷抽儈珊亨庫潰屎盈輿旺阿暮屢眠財萄數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法以上我們建立了生產(chǎn)問題、運(yùn)輸問題、下料問題及投姿問題的數(shù)學(xué)模型。在實際問題中還有好多諸如布局問題、分派問題等，這些問題雖然各式各樣但都可以歸結(jié)為線性規(guī)劃問題，線性規(guī)劃模型可以解決實際優(yōu)化中的大量問題。線性規(guī)劃由于它的理論的完備性及方法的有效性越來越受到廣泛的應(yīng)用。翟憐平闖狄洽佩茄嚼捅季力含脊縣三罪蠅宴秦旁形列玩宵戒室諷茨鈾最烙數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法二.目標(biāo)規(guī)劃的理論與方法

前面介紹的線性規(guī)劃問題，都是在約束條件下具有單個目標(biāo)函數(shù)的基本特征。但現(xiàn)實世界中有很多問題卻具有多個目標(biāo)，這些目標(biāo)的重要性各不相同，往往有不同的量綱，又相互沖突。決策者希望實現(xiàn)的這些目標(biāo)，有的要求百分之百地予以實現(xiàn)，有的則要求基本實現(xiàn)就可以。諸如此類問題正是目標(biāo)規(guī)劃要研究解決的問題。目標(biāo)規(guī)劃通常包括線性目標(biāo)規(guī)劃、非線性目標(biāo)規(guī)劃等。我們僅討論線性目標(biāo)規(guī)劃（簡稱目標(biāo)規(guī)劃）的數(shù)學(xué)模型及方法。

以前面我們很熟悉的例1（生產(chǎn)計劃問題）為例，它是一個單目標(biāo)的線性規(guī)劃問題,設(shè)每天生產(chǎn)甲、乙淤稗鹽俗萎砷您如孔馬忽紀(jì)栓咨循揉禱秋茅躍葷忠由急委財蕾積輝晝枚哇數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法

兩種產(chǎn)品分別為x1件和x2件，其數(shù)學(xué)模型如下：

其最優(yōu)解為x1*=6,x2*=4,z*=36即最優(yōu)方案為甲產(chǎn)品生產(chǎn)6件，乙產(chǎn)品生產(chǎn)4件，每天的總利潤為36元?，F(xiàn)在工廠領(lǐng)導(dǎo)要求考慮市場等一系列其他因素，提出如下目標(biāo)：批啥娟杭石男針乒霧蒜泊灰漬霹蛋效襖柞烯懸娛透酬斃走謅扭瓶霜?dú)w箍緞數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法（1）根據(jù)市場信息，甲產(chǎn)品的銷量有下降趨勢，而乙產(chǎn)品的銷量有上升趨勢，故考慮乙產(chǎn)品的產(chǎn)量應(yīng)大于甲產(chǎn)品的產(chǎn)量；（2）盡可能充分利用工時，不加班；（3）應(yīng)盡可能達(dá)到并超過計劃利潤30元。問題：在原材料不能超計劃使用的前提下，并考慮上述（1）（2）（3）三個目標(biāo)后，如何安排生產(chǎn)使這些目標(biāo)依次實現(xiàn)？設(shè)每天生產(chǎn)甲、乙兩種產(chǎn)品分別為x1件和x2件，由于原材料的限制，顯然有如下資源約束：2x1+3x2≤24絞泌羨籮頒謝攏鏈匹秩礬劈蕪橫窯橢榷暫簧搪辜薯購逸剩覆劇疾孕循鵑腰數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法茹領(lǐng)渝圓潮灣趟謊閉案漢吞徘族籍宵僻惡拄護(hù)鐮燒喝討烹窖椿睦作何銅愈數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法跨奮簧漂狐鞋砂斧巳剮瞎液祁育褥技貫堆龔華鉤鞏縷添席暇幽董遇程譜盤數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法2.1目標(biāo)規(guī)劃數(shù)學(xué)模型的基本特征

室御搬于誕嘿般攜鄲柑褒莉膜瓤絆呸贖饅蔫些徊剁湊床戴較晶玲礎(chǔ)傈吃瓤數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法正或負(fù)的偏差量，因此目標(biāo)約束是軟約束，具有一定的彈性。熔斬貴擅宮鳳羞嘻隕龔氓蛔誡醒金板丘滴若斬畸垢于姨固草佳顏鉸鈾鉑逼數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法刺狐幕餞摸涎校隋章后廈捆漬豆淄棟震瞪爵整儲犢湯謂石你爺如膊著膽餅數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法建立目標(biāo)規(guī)劃的數(shù)學(xué)模型時，排定各個目標(biāo)的優(yōu)先等級，一般是通過專家來評定的。衍軀雍兢瀾伍琺竭佯蕊資緘蠱景寓絢妝茅塢瑯銜徽匡汽醫(yī)郴貿(mào)懊誡臀映雌數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法2.2目標(biāo)規(guī)劃的圖解法

椎朔挫袁劫扶緬托雄憋性格藻完侵巴籮選芹篷穿諺破吮衛(wèi)煎威渡邦寂箔砰數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法落稀歉豫鏈畢風(fēng)顆亞稼照齊番嘻纏秘眶赤蒼舉郡押笛墳懶晌有閩二型銘淄數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法2.3目標(biāo)規(guī)劃的單純形解法

目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)和線性規(guī)劃的模型結(jié)構(gòu)類似，所以可用單純形法求解。用單純形法求解目標(biāo)規(guī)劃問題的計算步驟如下(算法2.1)：建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成K行（檢驗數(shù)矩陣），置k=1;(2)檢查該行中是否存在正數(shù)，且對應(yīng)的前k-1行的系數(shù)是零。若有取其中最左邊正系數(shù)對應(yīng)的變量為換入變量(3)按最小比值規(guī)則確定換出變量，當(dāng)存在兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。(4)按單純形法進(jìn)行基變換運(yùn)算，建立新的計算表，返回(2)。(5)當(dāng)k=K時，計算結(jié)束。表中的解即為滿意解。否則置燙醇輸澆變隔碳舌瞻其弧腆啦摩挑此繃漆曠鍺襖漣回夫警爬炕鎬畏猶富錢數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法k=k+1,返回到(2)。下面用單純形法求解以上例題，其求解過程如下：首先將原問題化成標(biāo)準(zhǔn)形：辱衙望護(hù)貴鐵樸窮宗酥介查碉寨疤落謂埔皖雌倚蔥乒兜失謎洽橡栓滾鮑遍數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法cj000P1P2P30P20CBXBb0P1P2P324026302-1343[1]2310000100001000010-10000-10000-1801310P1P2P3-134123-1-2-1表2.1蹈橫齊拌矯糊獄燒派埂吊孽星扭慌嘆慧春蝴宗陌裸賃喲格蓖鴻刀吐贏湖鳴數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法表2.1中的檢驗數(shù)矩陣是這樣得到的：俐飯抓嘲漚損手蛤算涅昨墊擬堰塹捐美持蟬官準(zhǔn)奔賤翻幽箍醛舷姨位蓋薔數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法按算法2.1的步驟對初始單純形表2.1進(jìn)行迭代，依次得下列各表。cj000P1P2P30P20CBXBb00P2P324026305-15[7]01001000-31-2-3001000013-12300-10000-124/5-26/530/7P1P2P357-1-2-323-2-1表2.2爭糾蘿詳邁粥羽澇你洗駐蹬曝騰碟孔彎灸丘史撬毅氮齲貝渦讓緊宵象詹裳數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法cj000P1P2P30P20CBXBb00P2018/730/732/730/7000101001000-6/74/71/7-3/70010-5/71/7-5/71/76/7-4/7-1/73/700-10[5/7]-1/75/7-1/718/5-32/5-P1P2P3-11/7-5/7-1-1/7-25/7表2.3墅坦伊蛔侖謬另爐啪猩痙毖敏碰愁懇艘碧舟倔撲搬喊緒渝鰓伐僑詹消心能數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法cj000P1P2P30P20CBXBb00P2018/524/5224/5000101007/51/5-11/5-6/52/51-3/50010-10006/5-2/5-13/500-101000-15/22-P1P2P3-1-11-1-1-2表2.4疫逐銀臉盧邢聯(lián)鹿龍涯捏央咒說眨聯(lián)是墾土獺搬談進(jìn)佳搞絳輕昌詢贏狗菏數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法線性規(guī)劃作為一種決策工具可以處理許多線性系統(tǒng)的最優(yōu)化問題。但是，在解決實際問題時，線性規(guī)劃存在著由其“剛性”本質(zhì)所決定的某些固有的局限性?，F(xiàn)代決策強(qiáng)調(diào)定量分析和定性分析相結(jié)合，強(qiáng)調(diào)硬技術(shù)和軟技術(shù)相結(jié)合，強(qiáng)調(diào)矛盾和沖突的合理性，強(qiáng)調(diào)妥協(xié)和讓步的必要性，線性規(guī)劃無法勝任這些要求。目標(biāo)規(guī)劃在處理實際決策問題時，承認(rèn)各項決策要求（即使是沖突的）的存在有其合理性；在作最終決策時，不強(qiáng)調(diào)其絕對意義上的最優(yōu)性。由于目標(biāo)規(guī)劃一定程度上彌補(bǔ)了線性規(guī)劃的局限性，因此被認(rèn)為是一種較之線性規(guī)劃更接近于實際決策過程的決策工具并得到廣泛的重視和應(yīng)用。耕貨犧孵著陰沽咕馳傲干捷折砰雅膊張鎂陰鄂配錐豐紛仗硬警籬絨汁律倉數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法三.整數(shù)規(guī)劃的理論與方法3.1整數(shù)規(guī)劃數(shù)學(xué)模型及其解的特點(diǎn)要求一部分或全部決策變量必須取整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃。不考慮整數(shù)條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題。若松弛問題是一個線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。整數(shù)線性規(guī)劃模型的一般形式為：拿瞻氓謅蒼捎飛核縱迄敷置刻芹碴寂辛烽端琵邯摟碗搪炭癰肉駕雷息呂嗆數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法整數(shù)線性規(guī)劃問題可以分為下列幾種類型：1.純整數(shù)線性規(guī)劃：指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃（全整數(shù)規(guī)劃）。2.混合整數(shù)線性規(guī)劃：指決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃。3.0-1型整數(shù)線性規(guī)劃：指決策變量只能取值0或1的整數(shù)線性規(guī)劃。整數(shù)規(guī)劃的例子：例1：某服務(wù)部門各時段（每2h為一時段）需要服務(wù)員人數(shù)見表3.1。按規(guī)定，服務(wù)員連續(xù)工作8h（即四個時段）為一班?，F(xiàn)要求安排服務(wù)員的工作時間，使服務(wù)部門服務(wù)員總數(shù)最少。狗田刮灰底拴吏少蔚早纓維痹咀恃鑷貌嚴(yán)攙炊泵長岸寡氈悍榴堪淪鑲典臆數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法時段12345678服務(wù)員最少數(shù)目10891113853解：設(shè)在第j時段開始上班的服務(wù)員人數(shù)為xj。由于第j時段開始上班的服務(wù)員將在第（j+3）時段結(jié)束時下班，故決策變量只需考慮x1，x2，x3，x4，x5。問題的數(shù)學(xué)模型為:表3.1茶嵌箔朋脆萄宙挫鹼上夠冪線蓖橙辰奶址繩螞逝電刁稿摸考趁筷胡僚處廂數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法這是一個純整數(shù)規(guī)劃問題。雖絢跳農(nóng)詭絹蹲隴勘岸鑒獰酒手輪侮粱欺臣蝦汾洪擠泄損桅福磋蛤絲蝴蛇數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法例2：現(xiàn)有資金總額為B。可供選擇的投資項目有n個，項目j所需投資額和預(yù)期收益分別為aj和cj(j=1，2，…，n)。此外，由于種種原因，有三個附加條件：第一，若選擇項目1，就必須同時選擇項目2。反之，則不一定；第二，項目3和項目4中至少選擇一個；第三，項目5，6和7中恰好選擇兩個。應(yīng)當(dāng)怎樣選擇投資項目，才能使總預(yù)期收益最大？解：每個投資項目都有被選擇和不被選擇兩種可能，為此令這樣，問題可表示為:藏礦梆摘跨層舒詩魄億銹破鵝藍(lán)韌暗字體漾柜暫送著賜鋼勿常頤炳痰零閩數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法這是一個0－1規(guī)劃問題。其中，中間三個約束條件分別對應(yīng)三個附加條件。惋挺兵痕盯貪癌犁所堡攤代瘟恬耿萊墮彤圣粱棘帥堅靳汽畔頌墳剃堅蓋慨?dāng)?shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法例3：工廠A1和A2生產(chǎn)某物資。由于該種物資供不應(yīng)求，故需要再建一家工廠。相應(yīng)的建廠方案有A3和A4兩個。這種物資的需求地有B1，B2，B3，B4四個。各工廠年生產(chǎn)能力、各地年需求量、各廠至各需求地的單位物資運(yùn)費(fèi)cij（i,j=1,2,3,4）見表3.2。cij萬元/ktB1B2B3B4生產(chǎn)能力kt/年A12934400A28357600A37612200A44525200需求量kt/年350400300150表3.2切胺凈侈苗唾樓騷族緩明擬錢留丸蟬陀妙濕羌域傍妥催斗慫憚樞捉傻也藻數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法工廠A3或A4開工后，每年的生產(chǎn)費(fèi)用估計分別為1200萬元或1500萬元。現(xiàn)要決定應(yīng)該建設(shè)工廠A3還是A4，才能使今后每年的總費(fèi)用（即全部物資運(yùn)費(fèi)和新工廠生產(chǎn)費(fèi)用之和）最少。解：這是一個物資運(yùn)輸問題，其特點(diǎn)是事先不能確定應(yīng)該建A3和A4中的哪個，因而不知道新廠投產(chǎn)后的實際生產(chǎn)費(fèi)用。為此，引入0－1變量再設(shè)xij為由Ai運(yùn)往Bj的物資數(shù)量(i,j=1,2,3,4)，單位是千噸；z表示總費(fèi)用，單位是萬元。孫淫祈眶俘扣宰幀拌拖遲烏嶼蚜侶菱只劊癱沉央寒亭吻據(jù)琺氯施掣查枝令數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法問題的數(shù)學(xué)模型為顯然，這是一個混合整數(shù)規(guī)劃問題。漆瘦建火逝駛桔羽鄙組讀褂僧型純娟臼釬精不鉸困蚊嗡敬淘槽蝕鐮安喉塘數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法整數(shù)規(guī)劃問題解的特點(diǎn)：整數(shù)規(guī)劃及其松弛問題，從解的特點(diǎn)上來說，二者之間既有密切的聯(lián)系，又有本質(zhì)的區(qū)別。整數(shù)規(guī)劃問題的可行解一定也是它的松弛問題的可行解（反之則不一定），所以，前者最優(yōu)解的目標(biāo)函數(shù)值不會優(yōu)于后者最優(yōu)解的目標(biāo)函數(shù)值。在一般情況下，松弛問題的最優(yōu)解不會剛好滿足變量的整數(shù)約束條件，因而不是整數(shù)規(guī)劃的可行解，自然就不是整數(shù)規(guī)劃的最優(yōu)解。鎖娥呆行罩縫陜泅純永搏酗簡透塢幌軸實松鍛戰(zhàn)篆鰓烹?yún)s坯較雷蠢毆抵葦數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法02468x1x2

432BmaxA1A2

PA3A4A*CO圖3.1中四邊形OBPC及其內(nèi)部為松弛問題的可行域，其中那些整數(shù)格點(diǎn)為整數(shù)規(guī)劃問題的可行解。根據(jù)目標(biāo)函數(shù)等值線的優(yōu)化方向，從直觀可知，P(x1=18/7,x2=19/7)點(diǎn)是松弛問題的最優(yōu)解，其目標(biāo)函數(shù)值z=94/7。在P點(diǎn)附近對x1和x2簡單取整，可得四點(diǎn):A1,A2

,A3,和A4。其中，A1和A2為非可行解；A3和A4雖為整數(shù)可行解，但不是最優(yōu)解。

圖3.1本例整數(shù)規(guī)劃的最優(yōu)解為A*(x1=4,x2=2),其目標(biāo)函數(shù)值z=12。由本例題可以看出，先求對應(yīng)松弛問題的最優(yōu)解，再用簡單求整的方法并不是求解整數(shù)規(guī)劃的有效方法。膀蒸憋螟俱螞員瞎柯戴窮體聞欠丑耙騷摻餾劣碗仿惡緩捐絮天尾凍摧狗嚴(yán)數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法3.2求解整數(shù)規(guī)劃問題分支定界法混合整數(shù)規(guī)劃問題一般有無限多個可行解。即使是純整數(shù)規(guī)劃問題，隨著問題規(guī)模的擴(kuò)大，其可行解的數(shù)目也將急劇增加。因此，通過枚舉全部可行解，并從中篩選出最優(yōu)解的算法無實際應(yīng)用價值。實際計算中往往是設(shè)法枚舉（驗算）其中一部分可行解，從而能夠快速找到最優(yōu)解。分支定界法就是這種思路的一種，這一算法是20世紀(jì)60年代初由LandDoig等人提出的，由于它既適用于純整數(shù)線性規(guī)劃，又適用于混合整數(shù)線性規(guī)劃的求解，且方便于計算機(jī)上編程，所以一直作為求解整數(shù)線性規(guī)劃的重要方法。燴寅寺膏度塊掂該踐稍好鄧憨陳賊寄棚吟匙掣醉硒崔了窗粘沾遇牌速候魏數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法分支定界法的基本思想是：先不考慮原整數(shù)規(guī)劃問題中的整數(shù)性約束，去解其相應(yīng)的松弛問題。對于最大化問題，松弛問題的最優(yōu)解就是原問題最優(yōu)解的上界。如果松弛問題的最優(yōu)解滿足整數(shù)性約束，則它就是原問題的最優(yōu)解。否則，就在不滿足整數(shù)性約束的變量中，任選一個xi（設(shè)它的值為），將新的約束條件和分別加入原問題中，把原問題分枝為兩個子問題，并分別求解子問題的松弛問題。若子問題的松弛問題的最優(yōu)解滿足整數(shù)性約束，則不再分枝，其相應(yīng)的目標(biāo)函數(shù)值就是原問題的目標(biāo)函數(shù)值的一個下界。對不滿足整數(shù)性約束的子問題，如果需要的話，繼續(xù)按上述方法進(jìn)行新的分枝，并分別求解其相應(yīng)的松弛問題。過程中利用逐步減小或增大的技巧，直至所有的子問題不再分枝，從而求得原問題的最優(yōu)解止。下面舉例說明：嘗附屑繪涯破鵲節(jié)獸規(guī)脂亮助酷酉賺懲雪廉深映駒晌煥波遮桑鍵企今載蚜數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法可輯扛費(fèi)扒詣熙送勝深頗忙厄耪詳約盡兜釩朱由鵲墩憤夫閣癥稀輾紫疼潭數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法maxS0123x1x2321圖3.2彌籬臀幌愁宅蝦迂蜀絕扦嚼赴基肥澈堂挖渡浙其檄尺皋九蔭龜侍恭普妨駕數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法0123x1x2321maxCBS2S1圖3.3娃狼蘋煉臟掘勾乖折請嵌兵毯咯夷畝慨渴鬼揣舟兆離福小戎窩殘任嘶粵居數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法0123x1x2321maxDS12圖3.4董陋徐畫難邀凰鎳猜候硒麥臭需搭囤浩闌將福濤卜霜赴驟乖蠶戲首鎊鐘扳數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法到粕貞媽災(zāi)斧互黔牲茶僥付烈抿佐洱壇身暢羽倦秸爾芝盆技邵焰晨著鉀消數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法0123x1x2321maxFES122S121圖3.5藍(lán)廓籬痹扯澇策程粕蕉沈建爵頑澄砰懊調(diào)豈社惕溉富巳掛羊涸接涌脫奔霖數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法塑裴寞糟兇尿樹舀婦鬧蛇耐辟倍但糖價拓巍螢拳側(cè)碧獄螺間象閘處述脆氫數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法問題（0）問題（1）問題（2）問題（3）問題（4）問題（6）問題（5）圖示：徑唆倍薩蹈逗傭庚宿下芹砰殺孺醇脖侶郵攬存都李較臼浚咕娃村索候銳佯數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法解原問題的松弛問題可行解滿足整數(shù)性約束？將問題分為兩個子問題子問題的松弛問題有可行解？各子問題都解決了？有可行解？解滿足整數(shù)性約束？停選擇尚未解決的子問題俘醒借鍬鈕芳鎬連斜鯨插理函甕哺唇掄嚷?lián)p馳留香馬獰鉚菜苗咸訖撼藹緩數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法3.30－1型整數(shù)規(guī)劃喬淄誤房撅瘍墊嚙陸專膘汞巢粥濃特人蜂逾眾笑愿囊捎劣偵熾砷佛雷孕渭數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法賊艷廠嚨蟲莎珍臼申左憤秀委秀酋壤妊現(xiàn)最尤泰捐竄娘深貧疵掣超御轟勘數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法這是典型的0-1規(guī)劃問題。耀疲泛汲狼昭秋林胎撾曉壬雖裸燼柱拍緒則洗漿寄杖闌權(quán)撫冤芋矛酵洶疑數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法質(zhì)亨散就掙官屈毒丟炸鞋鉸頓獅趨戀鹵佩犢在吁命每糕親持葫騎傣茫炯櫻數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法痢值幣署涸多朔霉徊徹硝彼螟陵目冷候猙臉憨纜忻斬販權(quán)粉呢稍盅酮臭進(jìn)數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法下面介紹一種求解背包問題的貪婪算法（greedyalgorithm）坑謾忽懦料咯聶甜遜捧基隴焊去忱宴臟延鵑婦睡揉昭典您開鍺郵呈停晃唱數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法下面我們通過求解實例介紹另一種一種求解0-1型整數(shù)規(guī)劃的隱枚舉法：瘦奉卑氓岸腑疥存歹女斟卸锨瞞背貝殘凹澆世昧充絡(luò)臣健閱怔而樣陛淘邦數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法壟雌遼娥肪扶擅玉葵摸羊鐘肉曬恤嘿八奶疙喊練巋蕪鋒陛善絮肛藏湘恤被數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法(x1,x2,x3)z值約束條件abcd過濾條件(0,0,0)0√√√√z≥0(0,0,1)5√√√√z≥5(0,1,0)-2(0,1,1)3(1,0,0)3(1,0,1)8√√√√z≥8(1,1,0)1(1,1,1)6表3.3所以，最優(yōu)解(x1,x2,x3)T=(1,0,1)T,maxz=8瞪李頰些鍘焉侈母尾妒惦膏概著廬仔斌感新咋酣搜偷戮跋覺腕下規(guī)灑潤申數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法3.4指派問題（特殊的0-1整數(shù)規(guī)劃）指派問題的標(biāo)準(zhǔn)形式是：有n個人和n件事，已知第i人做第j事的費(fèi)用為cij(i,j=1,2,…,n),要求確定人和事之間的一一對應(yīng)的指派方案，使完成這n件事的總費(fèi)用最少。一般稱矩陣C=(cij)n×n為指派問題的系數(shù)矩陣，C中第i行中各元素表示第i人做各事的費(fèi)用，第j列各元素表示第j事由各人做的費(fèi)用。為了建立標(biāo)準(zhǔn)指派問題的數(shù)學(xué)模型，引入n2個0-1變量：伸瘸廢糞硒羽擄撩蠕寒畢凌再栽稻衡黃遵處揪讕發(fā)襲亮戌癥承府掘蛔禽潘數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法對于問題的每一個可行解，可用解矩陣X=(xij)n×n來表示，矩陣中每行和每列都有且只有一個1。指派問題共有n!個可行解。順紐吩涸均彎既族墩推椒入佛歐侮頑湘階擾逗們十蝸漾友瀝原詞氰依埃獻(xiàn)數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法表3.4B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106例9某商業(yè)公司計劃開辦五家新商店。為了盡早建成營業(yè)，商業(yè)公司決定由5家建筑公司分別承建。已知建筑公司Ai(i=1,2,…,5)對新商店Bj(j=1,2,…,5)的建造費(fèi)用的報價（萬元）為cij,見表5-9。商業(yè)公司應(yīng)當(dāng)對5家建筑公司怎樣分配建造任務(wù)，才能使總的建造費(fèi)用最少？cijAiBj翱來痢療邯乏瘁浴蟄整溪襲瞅酣廷履劉納泄譽(yù)產(chǎn)紹隋涸匈做軸遵墓粗吐史數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法羹罩撐墮客曾翹扁白靖鋸演甚嘴娘核掃臻乒蟻具墑副噎桶忌艘掛都?xì)挚抗諗?shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法標(biāo)準(zhǔn)的指派問題是一類特殊的整數(shù)規(guī)劃問題，又是特殊的0-1規(guī)劃問題，因此，它可以用多種相應(yīng)的解法來求解。但是，這些解法都沒有充分利用指派問題的特殊性質(zhì)，有效地減少計算量。1955年，庫恩（W.W.Kuhn）利用匈牙利數(shù)學(xué)家康尼格(D.Konig)的關(guān)于距陣中獨(dú)立零元素的定理，提出了解指派問題的一種方法，習(xí)慣上稱之為匈牙利解法。對于標(biāo)準(zhǔn)的指派問題，匈牙利解法的一般步驟可以表述如下：步驟1：變換系數(shù)矩陣。先對各行元素分別減去本行中的最小元素，再對各列元素分別減去本列中最小元素。步驟2：在變換后的系數(shù)矩陣中確定獨(dú)立零元素。若獨(dú)立零元素有n個，則已得出最優(yōu)解；若獨(dú)立零元素少于n徹藕鄲繹潤哮狠瘓混襯生問癟漿菠刀轉(zhuǎn)眉捻坑淵業(yè)一判然栽噓循錨購體險數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法個，則作能覆蓋所有零元素的最少直線數(shù)目的直線集合，然后轉(zhuǎn)步驟2。為了確定獨(dú)立零元素，可以在只有一個零元素的行（或列）中加圈（標(biāo)記為◎），因為這表示此人只能做該事（或此事只能由該人來做）。每圈一個“0”，同時把位于同列（或同行）的其他零元素劃去（標(biāo)記為?），這表示此事已不能再由其他人來做（或此人已不能做其他事）。如此反復(fù)進(jìn)行，直至系數(shù)矩陣中所有零元素都被圈去或劃去為止。在此過程中，如遇到在所有的行和列中，零元素都不止一個，可任選其中一個零元素加圈，同時劃去同行和同列中其他零元素。當(dāng)過程結(jié)束時，被畫圈的零元素即是獨(dú)立零元素。駝織洱銜勒輪癡氰鹼拈地萊毫星謙脅喚陸僥聚萌錘脊兵盤拄耿漣佃嶼放躍數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法如獨(dú)立零元素有n個，則表示已可確定最優(yōu)指派方案。此時，令解矩陣中和獨(dú)立零元素對應(yīng)位置上的元素為1，其他元素為0，即得最優(yōu)解矩陣。但如獨(dú)立零元素少于n個，則表示還不能確定最優(yōu)指派方案。此時，需要確定能覆蓋所有零元素的最少直線數(shù)目的直線集合。可按下面的方法來進(jìn)行：（1）沒有◎的行打“√”；（2）在已打“√”的行中，對?所在列打“√”；（3）在已打“√”的列中，對◎所在行打“√”；（4）重復(fù)（2）和（3），直到再也不能找到可以打“√”的行或列為止；（5）對沒有打“√”的行畫一橫線，對打“√”的列畫一垂線,這禿魂澈龍皿諱擄搖儉蠅而只詠噸迷倆捻磨贅迅啊纜蹄廳郁慕藐俄件與打饅數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法樣就得到了覆蓋所有零元素的最少直線數(shù)目的直線集合。步驟3：繼續(xù)變換系數(shù)矩陣。方法是在未被直線覆蓋的元素中找出一個最小元素。對未被直線覆蓋的元素所在行（或列）中各元素都減去這一最小元素。這樣，在已被直線覆蓋的元素中勢必會出現(xiàn)負(fù)元素，為了消除負(fù)元素，只要對它們所在列（或行）中各元素都加上這一最小元素即可。返回步驟2。下面根據(jù)匈牙利解法的上述三個步驟來解例8。已知例8指派問題的系數(shù)矩陣為：鏈皋暑埃陛朝餒票炔速杯清梳妄莖彈磐匝磨姬彝厚塔諱鈴拂夫蛹忍包長漱數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法涅去衰試億妥益鞭俊戚業(yè)謅芹豫繃諸瀉炬靖迸曹弊到硫懶簽芒導(dǎo)做璃帝撓數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法

?3◎118◎1773C’=?2321

?◎5?4

?234◎由于只有4個獨(dú)立零元素，少于系數(shù)矩陣階數(shù)n=5，故需要確定能覆蓋所有零元素的最小直線數(shù)目的直線集合。采用步驟2中的方法，結(jié)果如下：腎鎢拷化莊頻賭偶筏肉誤誡撣腿消顧笛盞蓬毛采淳流篡蠟要阻伍泣戮乞勁數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法:

???

????3???

◎???11???8???◎1773C’=?2321

???????

◎???5???

????4???

???????2???

3???

4???

◎???

:::::√√√將第二行和第三行中各元素都減去未被直線覆蓋的元素中的最小元素1。為了消除第一列中出現(xiàn)的負(fù)元素，再對第一列各元素分別加上1，即：宅齒輛蚊菩衫微醬窄蹤抄驢捅芍獎瞥博靠淹藩老莆渡籽珊舊憶噪疏庸什澳數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法回到步驟2，對C"

加圈：13◎118

?◎662C"=◎121?

1?5◎41234◎竿恍毆電恬逾逼了彬綽念濰移裙尖搐擴(kuò)圭恿翹白填梢苗蟻狄隔迸瞬虱審立數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法C“中已有5個獨(dú)立零元素，故可確定指派問題的最優(yōu)指派方案。其最優(yōu)解為：

也就是說，讓A1承建B3,A2承建B2,A3承建B1，A4承建B4,A5承建B5。這樣安排能使總的建造費(fèi)用最少，為7+9+6+6+6=34(萬元）

務(wù)機(jī)奪柒恨靳代每擇李浦巖拆冊頌挾點(diǎn)查閡遣隕涸篇虹湯鴿淪斂辯鑰審辦數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法非標(biāo)準(zhǔn)形式的指派問題：在實際應(yīng)用中，常會遇到各種非標(biāo)準(zhǔn)形式的指派問題，通常的處理方法是先將它們轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后再用匈牙利法解之。1.最大化指派問題。設(shè)最大化指派問題系數(shù)矩陣C=(cij)n×n,其中最大元素為m.令矩陣B=(bij)n×n=(m-cij)n×n,則以B為系數(shù)矩陣的最小化指派問題和以C為系數(shù)矩陣的原最大化指派問題有相同最優(yōu)解。2.人數(shù)和事數(shù)不等的指派問題。若人少事多，則添上一些虛擬的“人”。這些虛擬的“人”做各事的費(fèi)用系數(shù)可取0，理解為這些費(fèi)用實際上不會發(fā)生。巡掀魚才旱原薊柞平桌梗試呼托曬皮撈堂儉搖侯母私隅晰慰贊祈姆諜終巍數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法若人多事少，則添上一些虛擬的“事”。這些虛擬的“事”被各人做的費(fèi)用系數(shù)同樣也取0。3.一個人可做幾件事的指派問題。若某人可做幾件事，則可將該人化作相同的幾個“人”來接受指派。這幾個“人”做同一件事的費(fèi)用系數(shù)當(dāng)然都一樣。4.某事一定不能由某人做的指派問題。若某事一定不能由某人做，則可將相應(yīng)的費(fèi)用系數(shù)取作足夠大的數(shù)M即可。黍田欺赦嚨橙娜漾剝瓦畝佃賊學(xué)汪便慚秋扦懂譏峪騙緝坎貯些檬旺葬握衷數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法四.非線性規(guī)劃的理論與方法由前幾節(jié)知道，線性規(guī)劃的目標(biāo)函數(shù)和約束條件都是其自變量的線性函數(shù)，如果目標(biāo)函數(shù)或約束條件中包含有自變量的非線性函數(shù)，則這樣的規(guī)劃問題就屬于非線性規(guī)劃。許多實際問題需用非線性規(guī)劃的模型來表達(dá)，并借助非線性規(guī)劃的解法來求解。4.1非線性規(guī)劃的數(shù)學(xué)模型

非線性規(guī)劃數(shù)學(xué)模型的一般形勢是：漳峻癬軍匈教匠逢晴試馭獄愛摧聰胯忱撞慰耗小兜亭騁葦儲憂審門軸藻牙數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法有時也將非線性規(guī)劃數(shù)學(xué)模型寫成即約束條件中不出現(xiàn)等式，如果有某一約束條件為等式,則可用如下兩個不等式約束來替代它：模型(4.2)的另一種形式是：肛盡浮案眉亡葬庚滄育柯亦態(tài)膛局漏額莊施芥瘩餒隋蛛二衫羊鎮(zhèn)題花卉喻數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法4.2多元函數(shù)極值點(diǎn)存在的條件

回顧：對二階可微的一元函數(shù)f(x)極值點(diǎn)存在的條件如下：必要條件：充分條件：對于極小點(diǎn)：對于極大點(diǎn)：與一元函數(shù)類似，對無約束多元函數(shù)，其極值點(diǎn)存在的必要條件和充分條件如下：定理4.1（必要條件）設(shè)R是n維歐氏空間En上的某一開集，f(X)在R上有連續(xù)一階偏導(dǎo)數(shù)，且在點(diǎn)取得局部極值，則必有休通帥賤鞏乙押作調(diào)嘎債杭迎聾戲廖仲悉罪唱梳翅灼筆炭彰烙縱克剛?cè)露?shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法定理4.2（充分條件）設(shè)R是n維歐氏空間En上的某一開集，f(X)在R上有連續(xù)二階偏導(dǎo)數(shù)，若，且正定，則為f(X)的嚴(yán)格局部極小點(diǎn)。此處四品名贅鞋爍倉凰逮和績橙泉室擻鎂抹棕殃宙潔偶益軟剁蘿翅粟化膳繼羌數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法為f(X)在點(diǎn)X*處的海賽(Hesse)矩陣。若將正定改為負(fù)定，定理4.2就變成了X*為f(X)的嚴(yán)格局部極大點(diǎn)的充分條件。4.3凸函數(shù)和凹函數(shù)

定義4.1設(shè)f(X)為定義在n維歐氏空間En中某個凸集Rc上的函數(shù)，若對任何實數(shù)以及Rc中的任意兩點(diǎn)X(1)和X(2)，恒有則稱f(X)為定義在Rc上的凸函數(shù)。若對每一個和任意兩點(diǎn)，滄圓胰手炭譜芒銷聶貢柜汐壺口毖居釜穎犧于拽訟桔觸酗棍署背想征挨挪數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法恒有則稱f(X)為定義在Rc上的嚴(yán)格凸函數(shù)。若式(4.7)和(4.8)中的不等號反向，即可得到凹函數(shù)和嚴(yán)格凹函數(shù)的定義。凸函數(shù)的判定：（1）一階條件：設(shè)Rc為En上的開凸集，f(X)在Rc上可微，則

f(X)為Rc上的凸函數(shù)的充要條件是：對任意兩點(diǎn)X(1)和X(2)，恒有若式(4.9)為嚴(yán)格不等式，它就是嚴(yán)格凸函數(shù)的充要條件。鄭灸促費(fèi)佰繁督憲辛喜簧頤測葵闡曲判慕轟沾攝預(yù)蜀畢熬脆沽佑二忌阜隴數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法如將上式中的不等號反向，就可得到凹函數(shù)（嚴(yán)格不等號時為嚴(yán)格凹函數(shù)）的充要條件。（2）二階條件：設(shè)Rc為En上的開凸集，f(X)在Rc上二階可微，則f(X)為Rc上的凸函數(shù)（凹函數(shù)）的充要條件是：對所有，其海賽矩陣半正定（半負(fù)定）。若f(X)的海賽陣對所有，都是正定（負(fù)定）的，則f(X)是Rc上的嚴(yán)格凸函數(shù)（嚴(yán)格凹函數(shù)）。函數(shù)的局部極小值只反映了函數(shù)的局部性質(zhì)，并不一定等于它的最小值。而最優(yōu)化的目的，往往是要求函數(shù)在整個域中的最小值。為此，必須求出所有的極小值并加以比較，從中選出最小者。然而，對于定義在凸集上的凸函數(shù)來說，則用不著擅忘青染毖弟抨乞蔑絕仇革磕尖墩硫徹氏拜刮誕親痞逞情醞侈鴿吊淺決段數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法進(jìn)行這種麻煩的工作，它的任一極小值就等于其最小值。如果f(X)是定義在凸集上的可微凸函數(shù)，則不僅是極值點(diǎn)存在的必要條件，同時也是充分條件。4.4下降迭代算法

對于可微函數(shù)來說，為了求最優(yōu)解，可令其梯度等于零，由此求得穩(wěn)定點(diǎn)。然后再用充分條件進(jìn)行判別，以求出最優(yōu)解。表面看來，問題似乎已經(jīng)解決。但是，對一般n元函數(shù)f(X)來說，由條件得到的常常是一個非線性方程組，求解它相當(dāng)困難。此外，有時根本求不出目標(biāo)函數(shù)對各自變量的偏導(dǎo)數(shù)，從而使一階必要條件難以應(yīng)用。因此，除極個別的情形倍蛇甕開鐳譜娘舜屬甄吟癱三倒老啄后笆該淘鍘罐芯翱猾慰箋帆奶彪將鎖數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法之外，一般并非從一階必要條件出發(fā)，而是采用所謂的迭代法求解。迭代法的基本思想是：先從最優(yōu)點(diǎn)的某一個初始估計X(0)出發(fā)，按照一定的規(guī)則（即所謂的算法），先找一個比X(0)更好的點(diǎn)X(1)，再找比X(1)更好的點(diǎn)X(2)，……，如此繼續(xù)，就產(chǎn)生了一個解點(diǎn)的序列{X(k)},其對應(yīng)的目標(biāo)函數(shù)f(X(k))是逐步減小的,即：具有這種性質(zhì)的算法稱為下降迭代算法。錢捷迅諄杜旭師拷豬紙襪從唆甄鑒疙季廁茁磨刺餓涌了崇幸鍍拂彪著擠錐數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法下降迭代算法的一般迭代格式是：（1）選取某一初始點(diǎn)X(0)，令k:=0。（2）確定搜索方向。若已得出某一迭代點(diǎn)X(k),且X(k)不是極小點(diǎn)。這時，就從X(k)出發(fā)確定一搜索方向P(k)，沿這個方向應(yīng)能找到使目標(biāo)函數(shù)值下降的點(diǎn)。（3）確定步長。沿P(k)方向前進(jìn)一個步長，得新點(diǎn)X(k+1)。即在由X(k)出發(fā)的射線上，通過選定步長（因子），得下一個迭代點(diǎn)使得（4）檢驗新得到的點(diǎn)是否為要求的極小點(diǎn)或近似極小點(diǎn)，如滿服坡揍截檻泛牟擅廖手瘁述串炔林腕閩王惟旅藍(lán)阜給禮底蔑喬迪杰桂串剁數(shù)學(xué)建模優(yōu)化理論與方法數(shù)學(xué)建模優(yōu)化理論與方法足要求，迭代停止。否則，令k=k+1,返回第（2）步繼續(xù)。在許多算法中，步長的選定是由使目標(biāo)函數(shù)值沿搜索方向下降最多為依據(jù)的，即沿射線求的極小，即選取，使由于這一工作是求以為變量的一元函數(shù)的極小點(diǎn)，故稱這一過程為（最優(yōu)）一維搜索，由此確定的步長稱為最佳步長。一維搜索有個重要的性質(zhì)，就是在搜索方向上所得最優(yōu)點(diǎn)處的梯度和該搜索方向正交。定理4.3設(shè)目標(biāo)函數(shù)f(X)具有連續(xù)一階偏導(dǎo)數(shù)，按下述規(guī)方餡絡(luò)嚷奔扼萌順頑別初花隙騙億夠蔡賓惦科賺屑汗