優(yōu)化模型特殊的整數(shù)規(guī)劃課件

數(shù)學(xué)建?！獌?yōu)化模型從徐州到宿遷怎么走最快到達(dá)？Findtheoptimalsolution尋找最優(yōu)解——Jiang數(shù)學(xué)建模——優(yōu)化模型從徐州到宿遷怎么走最快到達(dá)？Findt1數(shù)學(xué)建?！獌?yōu)化模型points1、什么是優(yōu)化模型 1.1優(yōu)化模型的問(wèn)題及方法 1.2引例及優(yōu)化模型的解題步驟2、無(wú)約束和有約束的優(yōu)化模型3、優(yōu)化問(wèn)題的常用方法 3.1線性規(guī)劃 3.2整數(shù)規(guī)劃 3.2.10—1規(guī)劃 3.3非線性規(guī)劃 3.4多目標(biāo)規(guī)劃

數(shù)學(xué)建模——優(yōu)化模型points2數(shù)學(xué)建?！獌?yōu)化模型什么是優(yōu)化模型？

優(yōu)化模型主要用來(lái)解決決策問(wèn)題的模型，決策是有目的的選擇行為，即是從一系列可選擇的方案中選擇能達(dá)到自己目的的方案。將這個(gè)目的定量成一個(gè)函數(shù)表達(dá)式，這個(gè)函數(shù)表達(dá)式稱(chēng)為目標(biāo)函數(shù)。決策通?？紤]一定的限制，這些限制稱(chēng)為約束條件。最優(yōu)化已經(jīng)廣泛的滲透到工程、經(jīng)濟(jì)、電子技術(shù)等領(lǐng)域計(jì)算機(jī)技術(shù)的出現(xiàn)，使得數(shù)學(xué)家研究出了許多最優(yōu)化方法和算法用以解決以前難以解決的問(wèn)題。數(shù)學(xué)建?！獌?yōu)化模型什么是優(yōu)化模型？3數(shù)學(xué)建?！獌?yōu)化模型優(yōu)化問(wèn)題主要討論的問(wèn)題無(wú)約束極值問(wèn)題一元與多元函數(shù)無(wú)約束優(yōu)化線性與非線性有約束優(yōu)化靜態(tài)與動(dòng)態(tài)優(yōu)化優(yōu)化問(wèn)題的方法1、函數(shù)極值（微積分）2、線性規(guī)劃3、整數(shù)規(guī)劃（0—1規(guī)劃）4、非線性規(guī)劃5、動(dòng)態(tài)規(guī)劃6、多目標(biāo)規(guī)劃7、對(duì)策論有約束無(wú)約束數(shù)學(xué)建?！獌?yōu)化模型優(yōu)化問(wèn)題主要討論的問(wèn)題優(yōu)化問(wèn)題的方法有約4數(shù)學(xué)建?！獌?yōu)化模型引例

某機(jī)床廠生產(chǎn)甲、乙兩種機(jī)床，每臺(tái)銷(xiāo)售后的利潤(rùn)分別為4000元與3000元。生產(chǎn)甲機(jī)床需用機(jī)器A,B加工，加工時(shí)間分別為每臺(tái)2小時(shí)和1小時(shí)；生產(chǎn)乙機(jī)床需用三種機(jī)器A,B,C加工，加工時(shí)間為每臺(tái)各一小時(shí)。若每天可用于加工的機(jī)器時(shí)數(shù)分別為機(jī)器10小時(shí)、機(jī)器8小時(shí)和機(jī)器7小時(shí)，問(wèn)該廠應(yīng)生產(chǎn)甲、乙機(jī)床各幾臺(tái)，才能使總利潤(rùn)最大？機(jī)床機(jī)器甲乙工作時(shí)數(shù)A2110B118C17利潤(rùn)40003000數(shù)學(xué)建?！獌?yōu)化模型引例某機(jī)床廠生產(chǎn)甲、乙兩種機(jī)床，每臺(tái)5數(shù)學(xué)建模——優(yōu)化模型解：設(shè)該廠生產(chǎn)甲、乙機(jī)床x1,x2臺(tái)時(shí)利潤(rùn)最大。使利潤(rùn)最大，建立目標(biāo)函數(shù)各機(jī)床工作時(shí)長(zhǎng)有限制，列出約束條件上面由目標(biāo)函數(shù)和約束條件確定的即是一個(gè)簡(jiǎn)單的優(yōu)化模型，由于目標(biāo)函數(shù)和約束條件均是線性的，所以稱(chēng)為線性規(guī)劃問(wèn)題。數(shù)學(xué)建模——優(yōu)化模型解：設(shè)該廠生產(chǎn)甲、乙機(jī)床x1,x2臺(tái)時(shí)利6數(shù)學(xué)建?！獌?yōu)化模型目標(biāo)函數(shù)為一組平行直線，其在可行域（黃色部分）內(nèi)有最大值時(shí)，取點(diǎn)（2,6），最大值為2600001、圖解法2、Matlab編程f=[4000;3000];A=[21;11;01];b=[10;8;7];lb=zeros(2,1);[x,fval,exitflag,output,lambda]=linprog(f,A,b,[],[],lb)數(shù)學(xué)建?！獌?yōu)化模型目標(biāo)函數(shù)為一組平行直線，其在7數(shù)學(xué)建?！獌?yōu)化模型

由引例可以總結(jié)運(yùn)用最優(yōu)化方法解決最優(yōu)化問(wèn)題的一般方法步驟如下：①前期分析：分析問(wèn)題，找出要解決的目標(biāo)，約束條件，并 確立最優(yōu)化的目標(biāo)。②定義變量，建立最優(yōu)化問(wèn)題的數(shù)學(xué)模型，列出目標(biāo)函數(shù)和約束條件。③針對(duì)建立的模型，選擇合適的求解方法或數(shù)學(xué)軟件。④編寫(xiě)程序，利用計(jì)算機(jī)求解。⑤對(duì)結(jié)果進(jìn)行分析，討論諸如：結(jié)果的合理性、正確性，算法的收斂性，模型的適用性和通用性，算法效率與誤差等。數(shù)學(xué)建模——優(yōu)化模型由引例可以總結(jié)8數(shù)學(xué)建?！獌?yōu)化模型無(wú)約束的優(yōu)化問(wèn)題Eg.有邊長(zhǎng)為3m的正方形鐵板，在四個(gè)角剪去相等的正方形以制成方形無(wú)蓋水槽，問(wèn)如何剪法使水槽的容積最大？解：設(shè)減去正方形的邊長(zhǎng)為x，則水槽容積為：建立無(wú)約束優(yōu)化模型

無(wú)約束優(yōu)化模型通常用求導(dǎo)求極值的方法，由于人工計(jì)算較為復(fù)雜，這里我們用軟件進(jìn)行求解：數(shù)學(xué)建?！獌?yōu)化模型無(wú)約束的優(yōu)化問(wèn)題建立無(wú)約束優(yōu)化模型9數(shù)學(xué)建?！獌?yōu)化模型先編寫(xiě)M文件fun0.m如下:functionf=fun0(x)f=-(3-2*x).^2*x;主程序?yàn)閣liti2.m:[x,fval]=fminbnd('fun0',0,1.5);xmax=xfmax=-fval運(yùn)算結(jié)果為:xmax=0.5000,fmax=2.0000.即剪掉的正方形的邊長(zhǎng)為0.5m時(shí)水槽的容積最大,最大容積為2m3.數(shù)學(xué)建?！獌?yōu)化模型先編寫(xiě)M文件fun0.m如下:運(yùn)算結(jié)果為10數(shù)學(xué)建模——優(yōu)化模型有約束的優(yōu)化問(wèn)題的數(shù)學(xué)模型一般形式為：為目標(biāo)函數(shù)，即是對(duì)目標(biāo)函數(shù)的約束條件數(shù)學(xué)建模——優(yōu)化模型有約束的優(yōu)化問(wèn)題的數(shù)學(xué)模型為目標(biāo)11數(shù)學(xué)建?！獌?yōu)化模型下面介紹有約束優(yōu)化問(wèn)題的幾種常用方法線性規(guī)劃1、概念線性規(guī)劃是研究目標(biāo)函數(shù)與約束條件均為線性的一類(lèi)優(yōu)化問(wèn)題的數(shù)學(xué)方法。2、基本結(jié)構(gòu)2.1決策變量——未知數(shù)。它是通過(guò)模型計(jì)算來(lái)確定的決策因素。又分為實(shí)際變量——求解的變量和計(jì)算變量，計(jì)算變量又分松弛變量（上限）和人工變量（下限）。2.2目標(biāo)函數(shù)——目標(biāo)的數(shù)學(xué)表達(dá)式。目標(biāo)函數(shù)是求變量的線性函數(shù)的極大值和極小值這樣一個(gè)極值問(wèn)題。2.3約束條件——實(shí)現(xiàn)目標(biāo)的制約因素。它包括：客觀約束條件、主觀約束條件和非負(fù)限制數(shù)學(xué)建?！獌?yōu)化模型下面介紹有約束優(yōu)化問(wèn)題的幾種常用方法12數(shù)學(xué)建?！獌?yōu)化模型線性規(guī)劃3、標(biāo)準(zhǔn)模型左式的決策變量為x；目標(biāo)函數(shù)為極大值函數(shù)，也可是極小值即min；約束條件不止一個(gè)且均為線性，這個(gè)基本的線性規(guī)劃模型包含了這三個(gè)要素。單從模型的形式上不容易理解，下面結(jié)合實(shí)例加深記憶和理解。求和符號(hào)展開(kāi)數(shù)學(xué)建?！獌?yōu)化模型線性規(guī)劃左式的決策變量為x；目標(biāo)函數(shù)為極13數(shù)學(xué)建?！獌?yōu)化模型4、例子

設(shè)某工廠有甲、乙、丙、丁四個(gè)車(chē)間，生產(chǎn)A、B、C、D、E、F六種產(chǎn)品。根據(jù)機(jī)床性能和以前的生產(chǎn)情況，得知每單位產(chǎn)品所需車(chē)間的工作小時(shí)數(shù)、每個(gè)車(chē)間在一個(gè)季度工作小時(shí)的上限以及單位產(chǎn)品的利潤(rùn)，如下表所示(例如，生產(chǎn)一個(gè)單位的A產(chǎn)品，需要甲、乙、丙三個(gè)車(chē)間分別工作1小時(shí)、2小時(shí)和4小時(shí))問(wèn)：每種產(chǎn)品各應(yīng)該每季度生產(chǎn)多少，才能使這個(gè)工廠每季度生產(chǎn)利潤(rùn)達(dá)到最大。

數(shù)學(xué)建?！獌?yōu)化模型4、例子14數(shù)學(xué)建?！獌?yōu)化模型生產(chǎn)單位產(chǎn)品所需車(chē)間的工作小時(shí)數(shù)ABCDEF每個(gè)車(chē)間一個(gè)季度工作小時(shí)的上限甲111323500乙255500丙425500丁138500利潤(rùn)(百元)4.02.45.55.04.58.5數(shù)學(xué)建?！獌?yōu)化模型生產(chǎn)單位產(chǎn)品所需車(chē)間的工作小時(shí)數(shù)ABC15數(shù)學(xué)建?！獌?yōu)化模型這是一個(gè)典型的最優(yōu)化問(wèn)題，屬線性規(guī)劃。假設(shè)：產(chǎn)品合格且能及時(shí)銷(xiāo)售出去；工作無(wú)等待情況等變量說(shuō)明：xj：第j種產(chǎn)品的生產(chǎn)量（j=1,2,……,6）

aij：第i車(chē)間生產(chǎn)單位第j種產(chǎn)品所需工作小時(shí)數(shù)（i=1,2,3,4;j=1,2,……,6）

bi：第i車(chē)間的最大工作上限

cj：第j種產(chǎn)品的單位利潤(rùn)則：cjxj為第j種產(chǎn)品的利潤(rùn)總額；

aijxj表示第i車(chē)間生產(chǎn)第j種產(chǎn)品所花時(shí)間總數(shù)；數(shù)學(xué)建?！獌?yōu)化模型這是一個(gè)典型的最優(yōu)化問(wèn)題，屬線性規(guī)劃。16數(shù)學(xué)建?！獌?yōu)化模型為使總利潤(rùn)最大，可根據(jù)上面的決策變量確定其目標(biāo)函數(shù)為：s.t.每個(gè)車(chē)間一季度的工作時(shí)長(zhǎng)有上限：s.t.對(duì)于第j個(gè)車(chē)間，每種產(chǎn)品均不能大于其生產(chǎn)上限：數(shù)學(xué)建?！獌?yōu)化模型為使總利潤(rùn)最大，可根據(jù)上面的決策變量確定17數(shù)學(xué)建?！獌?yōu)化模型整數(shù)規(guī)劃1、概述最優(yōu)化問(wèn)題中的所有變量均為整數(shù)時(shí)，這類(lèi)問(wèn)題稱(chēng)為整數(shù)規(guī)劃問(wèn)題。如果線性規(guī)劃中的所有變量均為整數(shù)時(shí)，稱(chēng)這類(lèi)問(wèn)題為線性整數(shù)規(guī)劃問(wèn)題。整數(shù)規(guī)劃可分為線性整數(shù)規(guī)劃和非線性整數(shù)規(guī)劃，以及混合整數(shù)規(guī)劃等。如果決策變量的取值要么為0，要么為1，則這樣的規(guī)劃問(wèn)題稱(chēng)為0－1規(guī)劃。數(shù)學(xué)建?！獌?yōu)化模型整數(shù)規(guī)劃18數(shù)學(xué)建?！獌?yōu)化模型2、基本模型整數(shù)規(guī)劃要求所有的變量均為整數(shù)，所以目標(biāo)函數(shù)形式與優(yōu)化類(lèi)問(wèn)題的模型相同，只是在約束條件上添加條件：決策變量為整數(shù)，具體形式如下：數(shù)學(xué)建?！獌?yōu)化模型2、基本模型19數(shù)學(xué)建?！獌?yōu)化模型3、通常用整數(shù)規(guī)劃方法求解的問(wèn)題

集裝箱運(yùn)貨問(wèn)題資源分配問(wèn)題產(chǎn)品生產(chǎn)問(wèn)題等等…變量為整數(shù)4、整數(shù)規(guī)劃的特點(diǎn)（i）原線性規(guī)劃有最優(yōu)解，當(dāng)自變量限制為整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況：①原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。②整數(shù)規(guī)劃無(wú)可行解。③有可行解（當(dāng)然就存在最優(yōu)解），但最優(yōu)解值變差。（ii）整數(shù)規(guī)劃最優(yōu)解不能按照實(shí)數(shù)最優(yōu)解簡(jiǎn)單取整而獲得。數(shù)學(xué)建模——優(yōu)化模型3、通常用整數(shù)規(guī)劃方法求解的問(wèn)題變量為整20數(shù)學(xué)建?！獌?yōu)化模型特殊的整數(shù)規(guī)劃——0—1規(guī)劃1、模型介紹型整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變量?jī)H取值0或1。這時(shí)稱(chēng)為變量，或稱(chēng)二進(jìn)制變量。僅取值0或1這個(gè)條件可由下述約束條件：x取0或1.2、基本模型限制變量取0和1數(shù)學(xué)建模——優(yōu)化模型特殊的整數(shù)規(guī)劃——0—1規(guī)劃2、基本模型21數(shù)學(xué)建模——優(yōu)化模型3、問(wèn)題舉例背包問(wèn)題—將下列物品裝入包中，使包的利用價(jià)值最大。背包可再裝入8單位重量，10單位體積物品。物品名稱(chēng)重量體積價(jià)值1書(shū)52202攝像頭31303枕頭14104休閑食品23185衣物4515數(shù)學(xué)建模——優(yōu)化模型3、問(wèn)題舉例物品名稱(chēng)重量體積價(jià)值1書(shū)5222數(shù)學(xué)建?！獌?yōu)化模型分析：顯然，從多種不同的裝包方案中選擇使包的利用價(jià)值最大的方案，這是一個(gè)優(yōu)化類(lèi)問(wèn)題，目標(biāo)函數(shù)即裝入價(jià)值最大，但是裝入哪種物品需要討論，為避免這種討論，我們引進(jìn)0—1變量進(jìn)行約束，具體如下：為方便表示，我們?cè)僖胱兞浚琣i表示第i種物品的價(jià)值，bi表示第i種物品的質(zhì)量，ci表示第i種物品的體積，k表示最大質(zhì)量，m表示最大體積。這樣，我們便可列出以總價(jià)值最大的目標(biāo)函數(shù)：數(shù)學(xué)建?！獌?yōu)化模型分析：顯然，從多種不同的裝包方案中選擇使23數(shù)學(xué)建模——優(yōu)化模型下面是對(duì)目標(biāo)函數(shù)的約束：裝入質(zhì)量不大于最大質(zhì)量，裝入體積不大于最大體積，則約束條件表示為：上面便是一個(gè)簡(jiǎn)單的0—1規(guī)劃實(shí)例。0—1規(guī)劃其最大的好處就是避免了分類(lèi)討論，將多種情況用0和1來(lái)約束，統(tǒng)一起來(lái)討論。0—1規(guī)劃中0和1應(yīng)是對(duì)立關(guān)系的變量，其所表示量可以自己定義，如一張紙上有兩種顏色紅和黃，可以定義紅色為0黃色為1，同樣可以定義黃色為0，黃色為1進(jìn)行討論。在優(yōu)化問(wèn)題中適當(dāng)?shù)倪x取0—1變量可以大大減小討論的情況，使模型變得簡(jiǎn)潔。數(shù)學(xué)建?！獌?yōu)化模型下面是對(duì)目標(biāo)函數(shù)的約束：上面便是24數(shù)學(xué)建模——優(yōu)化模型非線性規(guī)劃如果目標(biāo)函數(shù)或約束條件中包含非線性函數(shù)，就稱(chēng)這種規(guī)劃問(wèn)題為非線性規(guī)劃問(wèn)題。對(duì)于一個(gè)實(shí)際問(wèn)題，在把它歸結(jié)成非線性規(guī)劃問(wèn)題時(shí)，一般要注意如下幾點(diǎn)：a.確定供選方案：首先要收集同問(wèn)題有關(guān)的資料和數(shù)據(jù)，在全面熟悉問(wèn)題的基礎(chǔ)上，確認(rèn)什么是問(wèn)題的可供選擇的方案，并用一組變量來(lái)表示它們。b.提出追求目標(biāo)：經(jīng)過(guò)資料分析，根據(jù)實(shí)際需要和可能，提出要追求極小化或極大化的目標(biāo)。并且，運(yùn)用各種科學(xué)和技術(shù)原理，把它表示成數(shù)學(xué)關(guān)系式。c.給出價(jià)值標(biāo)準(zhǔn)：在提出要追求的目標(biāo)之后，要確立所考慮目標(biāo)的“好”或“壞”的價(jià)值標(biāo)準(zhǔn)，并用某種數(shù)量形式來(lái)描述它。d.尋求限制條件：由于所追求的目標(biāo)一般都要在一定的條件下取得極小化或極大化效果，因此還需要尋找出問(wèn)題的所有限制條件，這些條件通常用變量之間的一些不等式或等式來(lái)表示。數(shù)學(xué)建?！獌?yōu)化模型非線性規(guī)劃25數(shù)學(xué)建?！獌?yōu)化模型非線性規(guī)劃線性規(guī)劃與非線性規(guī)劃的區(qū)別如果線性規(guī)劃的最優(yōu)解存在，其最優(yōu)解只能在其可行域的邊界上達(dá)到（特別是可行域的頂點(diǎn)上達(dá)到）；而非線性規(guī)劃的最優(yōu)解（如果最優(yōu)解存在）則可能在其可行域的任意一點(diǎn)達(dá)到。在引例中，該線性規(guī)劃在（2,6）處去到最值，（2,6）為其邊界點(diǎn)，而在非線性規(guī)劃中，比如一元三次函數(shù)對(duì)自變量和因變量均有限制，來(lái)討論極值問(wèn)題，此時(shí)最優(yōu)解可能在駐點(diǎn)處取得。由于這種不確定性，非線性規(guī)劃問(wèn)題還沒(méi)有一種系統(tǒng)的解法，往往認(rèn)為得到滿意解就算得到結(jié)果，一般說(shuō)來(lái)，解非線性規(guī)劃要比解線性規(guī)劃問(wèn)題困難得多。非線性規(guī)劃目前還沒(méi)有適于各種問(wèn)題的一般算法，各個(gè)方法都有自己特定的適用范圍，線性規(guī)劃問(wèn)題解法已經(jīng)比較成熟了。單純形法數(shù)學(xué)建模——優(yōu)化模型非線性規(guī)劃單純形法26數(shù)學(xué)建?！獌?yōu)化模型多目標(biāo)規(guī)劃1、概述在決策過(guò)程中，決策者想同時(shí)達(dá)到多個(gè)目標(biāo)而選擇最佳方案，屬于優(yōu)化范疇，我們稱(chēng)這個(gè)過(guò)程稱(chēng)為多目標(biāo)規(guī)劃，直觀來(lái)講，即目標(biāo)函數(shù)有多個(gè)（一般兩個(gè)）的優(yōu)化問(wèn)題?，F(xiàn)實(shí)生活中，常用到多目標(biāo)規(guī)劃的問(wèn)題很多，比如在投資問(wèn)題中，