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

某機(jī)床廠生產(chǎn)甲、乙兩種機(jī)床，每臺銷售后的利潤分別為4000元與3000元。生產(chǎn)甲機(jī)床需用機(jī)器A,B加工，加工時間分別為每臺2小時和1小時；生產(chǎn)乙機(jī)床需用三種機(jī)器A,B,C加工，加工時間為每臺各一小時。若每天可用于加工的機(jī)器時數(shù)分別為機(jī)器10小時、機(jī)器8小時和機(jī)器7小時，問該廠應(yīng)生產(chǎn)甲、乙機(jī)床各幾臺，才能使總利潤最大？機(jī)床機(jī)器甲乙工作時數(shù)A2110B118C17利潤40003000數(shù)學(xué)建?！獌?yōu)化模型引例某機(jī)床廠生產(chǎn)甲、乙兩種機(jī)床，每臺5數(shù)學(xué)建模——優(yōu)化模型解：設(shè)該廠生產(chǎn)甲、乙機(jī)床x1,x2臺時利潤最大。使利潤最大，建立目標(biāo)函數(shù)各機(jī)床工作時長有限制，列出約束條件上面由目標(biāo)函數(shù)和約束條件確定的即是一個簡單的優(yōu)化模型，由于目標(biāo)函數(shù)和約束條件均是線性的，所以稱為線性規(guī)劃問題。數(shù)學(xué)建?！獌?yōu)化模型解：設(shè)該廠生產(chǎn)甲、乙機(jī)床x1,x2臺時利6數(shù)學(xué)建?！獌?yōu)化模型目標(biāo)函數(shù)為一組平行直線，其在可行域（黃色部分）內(nèi)有最大值時，取點（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ōu)化方法解決最優(yōu)化問題的一般方法步驟如下：①前期分析：分析問題，找出要解決的目標(biāo)，約束條件，并 確立最優(yōu)化的目標(biāo)。②定義變量，建立最優(yōu)化問題的數(shù)學(xué)模型，列出目標(biāo)函數(shù)和約束條件。③針對建立的模型，選擇合適的求解方法或數(shù)學(xué)軟件。④編寫程序，利用計算機(jī)求解。⑤對結(jié)果進(jìn)行分析，討論諸如：結(jié)果的合理性、正確性，算法的收斂性，模型的適用性和通用性，算法效率與誤差等。數(shù)學(xué)建模——優(yōu)化模型由引例可以總結(jié)8數(shù)學(xué)建模——優(yōu)化模型無約束的優(yōu)化問題Eg.有邊長為3m的正方形鐵板，在四個角剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？解：設(shè)減去正方形的邊長為x，則水槽容積為：建立無約束優(yōu)化模型

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

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

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

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

bi：第i車間的最大工作上限

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

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

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