最優(yōu)化理論在數(shù)學(xué)建模中的應(yīng)用數(shù)學(xué)規(guī)劃模型

實(shí)際問(wèn)題中的優(yōu)化模型x~決策變量f(x)~目標(biāo)函數(shù)gi(x)0~約束條件多元函數(shù)條件極值決策變量個(gè)數(shù)n和約束條件個(gè)數(shù)m較大最優(yōu)解在可行域的邊界上取得數(shù)學(xué)規(guī)劃線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃(0-1)重點(diǎn)在模型的建立和結(jié)果的分析最優(yōu)化理論線性規(guī)劃（LP）整數(shù)規(guī)劃（IP）０－１規(guī)劃線性規(guī)劃模型

引例（產(chǎn)品組合問(wèn)題）

某公司現(xiàn)有三條生產(chǎn)線來(lái)生產(chǎn)兩種新產(chǎn)品,問(wèn)如何生產(chǎn)可以讓公司每周利潤(rùn)最大?生產(chǎn)線生產(chǎn)每批產(chǎn)品所需時(shí)間生產(chǎn)線每周可利用時(shí)間

產(chǎn)品一產(chǎn)品二123

10

02

3241218每批產(chǎn)品利潤(rùn)

35將產(chǎn)品組合問(wèn)題抽象為數(shù)學(xué)模型、為每周生產(chǎn)產(chǎn)品一和產(chǎn)品二的產(chǎn)量為每周利潤(rùn)x1X20線性規(guī)劃問(wèn)題三要素約束條件決策變量取值時(shí)受到的各種資源條件的限制，通常表達(dá)為含決策變量的線性等式或不等式變量確定稱為決策變量，是問(wèn)題中要確定的未知量，決策變量為可控的連續(xù)變量目標(biāo)函數(shù)

決策變量的線性函數(shù)，按優(yōu)化目標(biāo)分別在目標(biāo)函數(shù)前加上或?qū)嶋H問(wèn)題中線性的含義嚴(yán)格的比例性如：生產(chǎn)某產(chǎn)品對(duì)資源的消耗量和可獲取的利潤(rùn)同其生產(chǎn)數(shù)量嚴(yán)格成比例可疊加性如：生產(chǎn)多種產(chǎn)品時(shí)對(duì)某項(xiàng)資源的消耗量應(yīng)等于各產(chǎn)品對(duì)該項(xiàng)資源的消耗量之和線性規(guī)劃標(biāo)準(zhǔn)形式資源單位活動(dòng)對(duì)資源的使用量資源可利用量12…12………單位活動(dòng)對(duì)的貢獻(xiàn)模型簡(jiǎn)寫(xiě)形式如何裝運(yùn)，使本次飛行獲利最大？

三個(gè)貨艙最大載重(噸),最大容積(米3)

例1貨機(jī)裝運(yùn)

重量（噸）空間(米3/噸）利潤(rùn)（元/噸）貨物1184803100貨物2156503800貨物3235803500貨物4123902850三個(gè)貨艙中實(shí)際載重必須與其最大載重成比例

前倉(cāng)：10；6800中倉(cāng)：16；8700后倉(cāng)：8；5300飛機(jī)平衡決策變量

xij--第i種貨物裝入第j個(gè)貨艙的重量(噸）i=1,2,3,4,

j=1,2,3(分別代表前、中、后倉(cāng))模型假設(shè)每種貨物可以分割到任意??；貨機(jī)裝運(yùn)每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；多種貨物可以混裝，并保證不留空隙；模型建立貨艙容積

目標(biāo)函數(shù)(利潤(rùn))約束條件貨機(jī)裝運(yùn)模型建立貨艙重量

10；680016；87008；5300xij--第i種貨物裝入第j個(gè)貨艙的重量約束條件平衡要求

貨物供應(yīng)

貨機(jī)裝運(yùn)模型建立10；680016；87008；5300xij--第i種貨物裝入第j個(gè)貨艙的重量OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOST

X32

X33

X430.000000650.000000貨物2：前倉(cāng)10,后倉(cāng)5；

貨物3:中倉(cāng)13,后倉(cāng)3；貨物4:中倉(cāng)3。貨機(jī)裝運(yùn)模型求解最大利潤(rùn)約121516元貨物~供應(yīng)點(diǎn)貨艙~需求點(diǎn)平衡要求運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題的擴(kuò)展整數(shù)規(guī)劃模型

整數(shù)規(guī)劃模型比線性規(guī)劃增加了某些約束條件，來(lái)限制全部或部分決策變量必須取整數(shù)值，與線性規(guī)劃相比決策變量是離散的變量。

如果生產(chǎn)某一類型汽車(chē)，則至少要生產(chǎn)80輛，那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？例2汽車(chē)廠生產(chǎn)計(jì)劃汽車(chē)廠生產(chǎn)三種類型的汽車(chē)，已知各類型每輛車(chē)對(duì)鋼材、勞動(dòng)時(shí)間的需求，利潤(rùn)及工廠每月的現(xiàn)有量。

小型中型大型現(xiàn)有量鋼材（噸）1.535600勞動(dòng)時(shí)間（小時(shí)）28025040060000利潤(rùn)（萬(wàn)元）234

制訂月生產(chǎn)計(jì)劃，使工廠的利潤(rùn)最大。設(shè)每月生產(chǎn)小、中、大型汽車(chē)的數(shù)量分別為x1,x2,x3汽車(chē)廠生產(chǎn)計(jì)劃模型建立

小型中型大型現(xiàn)有量鋼材1.535600時(shí)間28025040060000利潤(rùn)234線性規(guī)劃模型(LP)模型求解

3）

模型中增加條件：x1,x2,x3

均為整數(shù)，重新求解。

OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOST

ROWSLACKORSURPLUSDUALPRICES結(jié)果為小數(shù)，怎么辦？1）舍去小數(shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值z(mì)=629，與LP最優(yōu)值相差不大。2）試探：如取x1=65，x2=167；x1=64，x2=168等，計(jì)算函數(shù)值z(mì)，通過(guò)比較可能得到更優(yōu)的解。

但必須檢驗(yàn)它們是否滿足約束條件。為什么？IP可用LINGO直接求解整數(shù)規(guī)劃(IntegerProgramming,簡(jiǎn)記IP)IP的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z(mì)=632Model:Max=2x1+3x2+4x3;1.5x1+3x2+5x3<600;280x1+250x2+400x3<60000;@ginx1;@ginx2;@ginx3;endOBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTX30.000000-4.000000模型求解

IP結(jié)果輸出其中3個(gè)子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：方法1：分解為8個(gè)LP子模型汽車(chē)廠生產(chǎn)計(jì)劃

若生產(chǎn)某類汽車(chē)，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。x1,x2,,x3=0或80x1=80，x2=150，x3=0，最優(yōu)值z(mì)=610LINGO中對(duì)0-1變量的限定：@biny1@biny2@biny3方法2：引入0-1變量，化為整數(shù)規(guī)劃

M為大的正數(shù)，可取1000OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOST

Y30.0000000.000000

若生產(chǎn)某類汽車(chē)，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。x1=0或

80x2=0或

80x3=0或

80最優(yōu)解同前

NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(如LINGO,MATLAB)，但是其結(jié)果常依賴于初值的選擇。方法3：化為非線性規(guī)劃

非線性規(guī)劃（Non-LinearProgramming，簡(jiǎn)記NLP）

實(shí)踐表明，本例僅當(dāng)初值非常接近上面方法算出的最優(yōu)解時(shí)，才能得到正確的結(jié)果。

若生產(chǎn)某類汽車(chē)，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。x1=0或

80x2=0或

80x3=0或

80０－１規(guī)劃當(dāng)問(wèn)題含有多項(xiàng)要素，而每項(xiàng)要素皆有兩種選擇時(shí)，可用一組0-1變量來(lái)描述。0-1變量作為邏輯變量，常被用來(lái)表示系統(tǒng)是否處于某個(gè)特定狀態(tài)，或者決策時(shí)是否取某個(gè)特定方案。如何選拔隊(duì)員組成4100米混合泳接力隊(duì)?例3混合泳接力隊(duì)的選拔

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候選人的百米成績(jī)窮舉法：組成接力隊(duì)的方案共有5!=120種。目標(biāo)函數(shù)若選擇隊(duì)員i參加泳姿j的比賽，記xij=1,否則記xij=0

0-1規(guī)劃模型

cij(秒)~隊(duì)員i

第j種泳姿的百米成績(jī)約束條件每人最多入選泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每種泳姿有且只有1人模型求解

最優(yōu)解：x14=x21=x32=x43=1,其它變量為0;成績(jī)?yōu)?秒)=4’13”2Model:+……s.t.x11+x12+x13+x14<=1

……x41+x42+x43+x44<=1x11+x21+x31+x41+x51=1