優(yōu)化類(lèi)數(shù)學(xué)模型課件

優(yōu)化類(lèi)數(shù)學(xué)模型

線性規(guī)劃模型

非線性規(guī)劃模型

整數(shù)規(guī)劃模型優(yōu)化類(lèi)數(shù)學(xué)模型

線性規(guī)劃模型

非線性規(guī)劃模型

整數(shù)規(guī)劃§1最優(yōu)化問(wèn)題1．1最優(yōu)化問(wèn)題概念（1）最優(yōu)化問(wèn)題在工業(yè)、農(nóng)業(yè)、交通運(yùn)輸、商業(yè)、國(guó)防、建筑、通信、政府機(jī)關(guān)等各部門(mén)各領(lǐng)域的實(shí)際工作中，我們經(jīng)常會(huì)遇到求函數(shù)的極值或最大值最小值問(wèn)題，這一類(lèi)問(wèn)題我們稱(chēng)之為最優(yōu)化問(wèn)題。而求解最優(yōu)化問(wèn)題的數(shù)學(xué)方法被稱(chēng)為最優(yōu)化方法。它主要解決最優(yōu)生產(chǎn)計(jì)劃、最優(yōu)分配、最佳設(shè)計(jì)、最優(yōu)決策、最優(yōu)管理等求函數(shù)最大值最小值問(wèn)題。

最優(yōu)化問(wèn)題的目的有兩個(gè)：①求出滿足一定條件下，函數(shù)的極值或最大值最小值；②求出取得極值時(shí)變量的取值。最優(yōu)化問(wèn)題所涉及的內(nèi)容種類(lèi)繁多，有的十分復(fù)雜，但是它們都有共同的關(guān)鍵因素：變量，約束條件和目標(biāo)函數(shù)?！?最優(yōu)化問(wèn)題（2）變量變量是指最優(yōu)化問(wèn)題中所涉及的與約束條件和目標(biāo)函數(shù)有關(guān)的待確定的量。一般來(lái)說(shuō)，它們都有一些限制條件（約束條件），與目標(biāo)函數(shù)緊密關(guān)聯(lián)。設(shè)問(wèn)題中涉及的變量為x1,x2......xn；我們常常也用X=(x1,x2......xn)表示。（2）變量（3）約束條件在最優(yōu)化問(wèn)題中，求目標(biāo)函數(shù)的極值時(shí)，變量必須滿足的限制稱(chēng)為約束條件。例如，許多實(shí)際問(wèn)題變量要求必須非負(fù)，這是一種限制；在研究電路優(yōu)化設(shè)計(jì)問(wèn)題時(shí)，變量必須服從電路基本定律，這也是一種限制等等。在研究問(wèn)題時(shí)，這些限制我們必須用數(shù)學(xué)表達(dá)式準(zhǔn)確地描述它們。用數(shù)學(xué)語(yǔ)言描述約束條件一般來(lái)說(shuō)有兩種：等式約束條件不等式約束條件

注：在最優(yōu)化問(wèn)題研究中，由于解的存在性十分復(fù)雜，一般來(lái)說(shuō)，我們不考慮不等式約束條件。這兩種約束條件最優(yōu)化問(wèn)題最優(yōu)解的存在性較復(fù)雜。（3）約束條件（4）目標(biāo)函數(shù)在最優(yōu)化問(wèn)題中，與變量有關(guān)的待求其極值（或最大值最小值）的函數(shù)稱(chēng)為目標(biāo)函數(shù)。目標(biāo)函數(shù)常用表示F(x)=f(x1,x2......xn)表示。當(dāng)目標(biāo)函數(shù)為某問(wèn)題的效益函數(shù)時(shí)，問(wèn)題即為求極大值；當(dāng)目標(biāo)函數(shù)為某問(wèn)題的費(fèi)用函數(shù)時(shí)，問(wèn)題即為求極小值等等。求極大值和極小值問(wèn)題實(shí)際上沒(méi)有原則上的區(qū)別，因?yàn)榍蟮臉O小值，也就是要求的極大值，兩者的最優(yōu)值在同一點(diǎn)取到。（4）目標(biāo)函數(shù)1．2最優(yōu)化問(wèn)題分類(lèi)

最優(yōu)化問(wèn)題種類(lèi)繁多，因而分類(lèi)的方法也有許多?？梢园醋兞康男再|(zhì)分類(lèi)，按有無(wú)約束條件分類(lèi)，按目標(biāo)函數(shù)的個(gè)數(shù)分類(lèi)等等。一般來(lái)說(shuō)，變量可以分為確定性變量，隨機(jī)變量和系統(tǒng)變量等等，相對(duì)應(yīng)的最優(yōu)化問(wèn)題分別稱(chēng)為：普通最優(yōu)化問(wèn)題，統(tǒng)計(jì)最優(yōu)化問(wèn)題和系統(tǒng)最優(yōu)化問(wèn)題。

(1)按有無(wú)約束條件分類(lèi)：無(wú)約束最優(yōu)化問(wèn)題，有約束最優(yōu)化問(wèn)題。

(2)按目標(biāo)函數(shù)的個(gè)數(shù)分類(lèi)：?jiǎn)文繕?biāo)最優(yōu)化問(wèn)題，多目標(biāo)最優(yōu)化問(wèn)題。

(3)按約束條件和目標(biāo)函數(shù)是否是線性函數(shù)分類(lèi)：線性最優(yōu)化問(wèn)題（線性規(guī)劃），非線性最優(yōu)化問(wèn)題（非線性規(guī)劃）。

(4)按約束條件和目標(biāo)函數(shù)是否是時(shí)間的函數(shù)分類(lèi)：靜態(tài)最優(yōu)化問(wèn)題和動(dòng)態(tài)最優(yōu)化問(wèn)題（動(dòng)態(tài)規(guī)劃）。

1．2最優(yōu)化問(wèn)題分類(lèi)

最優(yōu)化問(wèn)題種類(lèi)繁多，因而．

3最優(yōu)化問(wèn)題的求解步驟和數(shù)學(xué)模型

（1）最優(yōu)化問(wèn)題的求解步驟

最優(yōu)化問(wèn)題的求解涉及到應(yīng)用數(shù)學(xué)，計(jì)算機(jī)科學(xué)以及各專(zhuān)業(yè)領(lǐng)域等等，是一個(gè)十分復(fù)雜的問(wèn)題，然而它卻是需要我們重點(diǎn)關(guān)心的問(wèn)題之一。怎樣研究分析求解這類(lèi)問(wèn)題呢？其中最關(guān)鍵的是建立數(shù)學(xué)模型和求解數(shù)學(xué)模型。一般來(lái)說(shuō)，應(yīng)用最優(yōu)化方法解決實(shí)際問(wèn)題可分為四個(gè)步驟進(jìn)行：．

3最優(yōu)化問(wèn)題的求解步驟和數(shù)學(xué)模型

求解步驟

步驟1：建立模型提出最優(yōu)化問(wèn)題，變量是什么？約束條件有那些？目標(biāo)函數(shù)是什么？建立最優(yōu)化問(wèn)題數(shù)學(xué)模型：確定變量，建立目標(biāo)函數(shù)，列出約束條件——建立模型。步驟2：確定求解方法分析模型，根據(jù)數(shù)學(xué)模型的性質(zhì)，選擇優(yōu)化求解方法——確定求解方法。步驟3：計(jì)算機(jī)求解編程序（或使用數(shù)學(xué)計(jì)算軟件），應(yīng)用計(jì)算機(jī)求最優(yōu)解——計(jì)算機(jī)求解。步驟4：結(jié)果分析對(duì)算法的可行性、收斂性、通用性、時(shí)效性、穩(wěn)定性、靈敏性和誤差等等作出評(píng)價(jià)——結(jié)果分析。求解步驟

步驟1：建立模型線性規(guī)劃（LinearProgramming）運(yùn)籌學(xué)的一個(gè)分支，主要用于生產(chǎn)計(jì)劃、物資運(yùn)輸、庫(kù)存、勞動(dòng)力分配以及最優(yōu)設(shè)計(jì)問(wèn)題等。類(lèi)似于條件極值問(wèn)題，只是其目標(biāo)函數(shù)和約束條件都是線性函數(shù)。線性規(guī)劃模型的特點(diǎn)1.比例性:每個(gè)決策變量對(duì)目標(biāo)函數(shù)和每個(gè)約束條件右端項(xiàng)的“貢獻(xiàn)”與該變量的取值成比例；2.可加性:每個(gè)決策變量對(duì)目標(biāo)函數(shù)和每個(gè)約束條件右端項(xiàng)的“貢獻(xiàn)”與其他變量的取值無(wú)關(guān)；3.連續(xù)性:每個(gè)決策變量的取值是連續(xù)的。線性規(guī)劃模型的三個(gè)要素決策變量：根據(jù)實(shí)際問(wèn)題所選擇的可以控制的因素；目標(biāo)函數(shù)：以線性函數(shù)形式表示所追求的目標(biāo)；約束條件：決策變量需要滿足的限定條件，一般是一組線性等式或不等式。線性規(guī)劃（LinearProgramming）二、線性規(guī)劃模型的求解（一）圖解法（n<=3時(shí)）（二）單純形法（三）數(shù)學(xué)軟件：如LINDO軟件二、線性規(guī)劃模型的求解（一）圖解法（n<=3時(shí)）（二）單純形例1某公司生產(chǎn)甲、乙兩種產(chǎn)品，每噸銷(xiāo)售后的利潤(rùn)分別為4000元與3000元。生產(chǎn)甲產(chǎn)品需要用A、B機(jī)器加工，加工時(shí)間分別為每噸2小時(shí)和1小時(shí)；生產(chǎn)乙產(chǎn)品需要用A、B、C三種機(jī)器加工，加工時(shí)間為每噸各1小時(shí)。若每天用于加工的機(jī)器時(shí)數(shù)分別為A機(jī)器10小時(shí)、B機(jī)器8小時(shí)、C機(jī)器7小時(shí)，問(wèn)該廠每天應(yīng)該生產(chǎn)甲、乙兩種產(chǎn)品各多少?lài)嵅拍苁估麧?rùn)最大？例1某公司生產(chǎn)甲、乙兩種產(chǎn)品，每噸銷(xiāo)售后的利潤(rùn)分別為400例2某工廠在計(jì)劃期內(nèi)安排生產(chǎn)甲、乙兩種產(chǎn)品。已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)數(shù)、A、B兩種原料的消耗以及單位利潤(rùn)如下表所示，問(wèn)應(yīng)該如何安排生產(chǎn)計(jì)劃使該工廠獲利最多？答案：生產(chǎn)甲4個(gè)，乙3個(gè)，獲利為17例2某工廠在計(jì)劃期內(nèi)安排生產(chǎn)甲、乙兩種產(chǎn)品。已知生產(chǎn)單位產(chǎn)自來(lái)水輸送與貨機(jī)裝運(yùn)生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤(rùn)最大；運(yùn)輸問(wèn)題各種類(lèi)型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少。自來(lái)水輸送與貨機(jī)裝運(yùn)生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求例1

居民用水調(diào)度問(wèn)題某市有甲、乙、丙、丁四個(gè)居民區(qū)，自來(lái)水由A、B、C三個(gè)水庫(kù)供應(yīng)．四個(gè)區(qū)每天必須得到保證的基本生活用水分別為30，70，10，10千噸，但由于水源緊張，三個(gè)水庫(kù)每天最多只能分別供應(yīng)50，60，50千噸自來(lái)水．由于地理位置的差別，自來(lái)水公司從各水庫(kù)向各區(qū)送水所需付出的引水管理費(fèi)不同(見(jiàn)下表，其中C水庫(kù)與丁區(qū)之間沒(méi)有輸水管道)，其他管理費(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)如何分配供水量，才能獲利最多？例1居民用水調(diào)度問(wèn)題某市有甲、乙、丙、丁四個(gè)居民區(qū)，自來(lái)其他費(fèi)用:450元/千噸

應(yīng)如何分配水庫(kù)供水量，公司才能獲利最多？

若水庫(kù)供水量都提高一倍，公司利潤(rùn)可增加到多少？元/千噸甲乙丙丁A160130220170B140130190150C190200230/引水管理費(fèi)例1自來(lái)水輸送收入：900元/千噸

支出A：50B：60C：50甲：30；50乙：70；70丙：10；20?。?0；40水庫(kù)供水量(千噸)小區(qū)基本用水量(千噸)小區(qū)額外用水量(千噸)（以天計(jì)）其他費(fèi)用:450元/千噸應(yīng)如何分配水庫(kù)供水量，公司才能獲供應(yīng)限制約束條件需求限制

線性規(guī)劃模型(LP)目標(biāo)函數(shù)

水庫(kù)i向j區(qū)的日供水量為xij（x34=0）決策變量

模型建立確定3個(gè)水庫(kù)向4個(gè)小區(qū)的供水量供應(yīng)限制約束條件需求限制線性規(guī)劃模型(LP)目標(biāo)函數(shù)水庫(kù)模型求解

OBJECTIVEFUNCTIONVALUE1)24400.00VARIABLEVALUEREDUCEDCOSTX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.000000X210.00000010.000000

X22

50.0000000.000000X230.00000020.000000X24

10.0000000.000000X31

40.0000000.000000X320.00000010.000000X33

10.0000000.000000利潤(rùn)=總收入-其它費(fèi)用-引水管理費(fèi)=144000-72000-24400=47600（元）

A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010引水管理費(fèi)24400(元)模型求解OBJECTIVEFUNCTIONVALUE利目標(biāo)函數(shù)

總供水量(320)>總需求量(300)每個(gè)水庫(kù)最大供水量都提高一倍利潤(rùn)=收入(900)–其它費(fèi)用(450)

–引水管理費(fèi)利潤(rùn)(元/千噸)甲乙丙丁A290320230280B310320260300C260250220/供應(yīng)限制B,C類(lèi)似處理問(wèn)題討論

確定送水方案使利潤(rùn)最大需求約束可以不變目標(biāo)函數(shù)總供水量(320)>總需求量(300)每個(gè)水庫(kù)求解OBJECTIVEFUNCTIONVALUE1)88700.00VARIABLEVALUEREDUCEDCOSTX110.00000020.000000X12100.0000000.000000X130.00000040.000000X140.00000020.000000

X21

30.0000000.000000X2240.0000000.000000

X230.00000010.000000X2450.0000000.000000

X31

50.0000000.000000X320.00000020.000000X33

30.0000000.000000這類(lèi)問(wèn)題一般稱(chēng)為“運(yùn)輸問(wèn)題”(TransportationProblem)總利潤(rùn)88700（元）

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030求解OBJECTIVEFUNCTIONVALUE這類(lèi)問(wèn)非線性規(guī)劃模型，可以用LINGO求解非線性規(guī)劃模型，可以用LINGO求解非線性規(guī)劃（None-linearProgramming）例4

板材切割問(wèn)題

某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按照顧客的要求切割后售出．從鋼管廠進(jìn)貨時(shí)得到的原料鋼管都是19m長(zhǎng)．(1)現(xiàn)有一個(gè)客戶需要50根4m、20根6m和15根8m長(zhǎng)的鋼管．應(yīng)如何下料最節(jié)省?(2)零售商如果采用的切割模式太多，將會(huì)導(dǎo)致生產(chǎn)過(guò)程的復(fù)雜性，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的不同切割模式不能超過(guò)3種．此外，該客戶除需要上述的三種鋼管外，還需要10根5m長(zhǎng)的鋼管，應(yīng)如何下料最節(jié)省?非線性規(guī)劃（None-linearProgramming）首先，應(yīng)當(dāng)確定哪些切割模式是可行的，所謂一個(gè)切割模式，是指按照客戶需要在原料鋼管上安排切割的一種組合．其次，應(yīng)當(dāng)確定哪些切割模式是合理的．通常假設(shè)一個(gè)合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸．在這種合理性假設(shè)下，切割模式一共有7種，如下表首先，應(yīng)當(dāng)確定哪些切割模式是可行的，所謂一個(gè)切割模式，是指按優(yōu)化類(lèi)數(shù)學(xué)模型課件LINGO中@GIN(r);表示變量r為整數(shù)LINGO中@GIN(r);表示變量r為整數(shù)第三講整數(shù)規(guī)劃建模方法一、從現(xiàn)實(shí)問(wèn)題到整數(shù)規(guī)劃模型二、整數(shù)規(guī)劃模型的求解三、整數(shù)規(guī)劃的建模實(shí)例第三講整數(shù)規(guī)劃建模方法一、從現(xiàn)實(shí)問(wèn)題到整數(shù)規(guī)劃模型二、整4.1整數(shù)規(guī)劃簡(jiǎn)介要求所有xj的解為整數(shù)，稱(chēng)為純整數(shù)規(guī)劃要求部分xj的解為整數(shù)，稱(chēng)為混合整數(shù)規(guī)劃對(duì)應(yīng)沒(méi)有整數(shù)解要求的線性規(guī)劃稱(chēng)之為松弛問(wèn)題整數(shù)規(guī)劃的解是可數(shù)個(gè)的，最優(yōu)解不一定發(fā)生在極點(diǎn)整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其松弛問(wèn)題的最優(yōu)解4.1整數(shù)規(guī)劃簡(jiǎn)介要求所有xj的解為整數(shù)，稱(chēng)為純整數(shù)規(guī)4.2整數(shù)規(guī)劃的分枝定界法3、求解分枝的松弛問(wèn)題—定界過(guò)程設(shè)兩個(gè)分枝的松弛問(wèn)題分別為問(wèn)題1和問(wèn)題2，它們的最優(yōu)解有如下情況

4.2.1思路與解題步驟只解松弛問(wèn)題1、在全部可行性域上解松弛問(wèn)題若松弛問(wèn)題最優(yōu)解為整數(shù)解，則其也是整數(shù)規(guī)劃的最優(yōu)解2、分枝過(guò)程若松弛問(wèn)題最優(yōu)解中某個(gè)xk=bk不是整數(shù)，令bk為bk

的整數(shù)部分構(gòu)造兩個(gè)新的約束條件xkbk和xkbk+1，分別加于原松弛問(wèn)題，形成兩個(gè)新的整數(shù)規(guī)劃4.2整數(shù)規(guī)劃的分枝定界法3、求解分枝的松弛問(wèn)題—定界4.2.2分枝定界法舉例

例4.1.1

解：松弛問(wèn)題的最優(yōu)解為x1=2.5,x2=2,OBJ=23

由x1=2.5得到兩個(gè)分枝如下：4.2.2分枝定界法舉例例4.1.1解表4.2.3分枝問(wèn)題的松弛解問(wèn)題II的解即原整數(shù)問(wèn)題的最優(yōu)解（X1=3，X2=1）

可能存在兩個(gè)分枝都是非整數(shù)解的情況，則需要兩邊同時(shí)繼續(xù)分枝，直到有整數(shù)解出現(xiàn)，就可以進(jìn)行定界過(guò)程當(dāng)存在很多變量有整數(shù)約束時(shí)，分枝即廣又深，在最壞情況下相當(dāng)于組合所有可能的整數(shù)解一般整數(shù)規(guī)劃問(wèn)題屬于一類(lèi)未解決的難題，NP-complete，只有少數(shù)特殊問(wèn)題有好的算法，如任務(wù)分配問(wèn)題、匹配問(wèn)題表4.2.3分枝問(wèn)題的松弛解問(wèn)題II的解即原整數(shù)問(wèn)例.某廠擬用集裝箱托運(yùn)甲,乙兩種貨物。已知問(wèn)：如何安排利潤(rùn)最大？設(shè)甲乙分別托運(yùn)x1,x2箱模型建立

IP(1)-(4)稱(chēng)為與(IP)相對(duì)應(yīng)的線性規(guī)劃(LP)求解(LP)得x1=4.81,x2=1.82,z=356例.某廠擬用集裝箱托運(yùn)甲,乙兩種貨物。已知問(wèn)：如何安排利潤(rùn)最分枝定界法(branchandboundmethod)(IP)x1*,x2*,z*(LP) x1=4.81,x2=1.82,z0=356(LP1)x1=4,x2=2.1,z0=349X1≤4X1≥5(LP2)x1=5,x2=1.57,z0=341(z*≤349定界)(LP3)x1=4,x2=2,z0=340X2≤2X2≥3(LP4)x2=3,x1=1.42,z0=327(z*≥340定界)(LP5)x2=1,x1=5.44,z0=308X2≤1(LP6)無(wú)可行解X2≥2X1≤4X1≥5分枝：分枝定界法(branchandboundmethod)設(shè)每月生產(chǎn)小、中、大型汽車(chē)的數(shù)量分別為x1,x2,x3汽車(chē)廠生產(chǎn)計(jì)劃,任一型號(hào)汽車(chē)要生產(chǎn)至少80輛模型建立

小型中型大型現(xiàn)有量鋼材1.535600時(shí)間28025040060000利潤(rùn)234線性規(guī)劃模型(LP)設(shè)每月生產(chǎn)小、中、大型汽車(chē)的數(shù)量分別為x1,x2,x3汽模型求解

3）

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

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

OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOST

X164.5161290.000000

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

但必須檢驗(yàn)它們是否滿足約束條件。為什么？模型求解3）模型中增加條件：x1,x2,x3均為IP可用LINDO直接求解整數(shù)規(guī)劃(IntegerProgramming,簡(jiǎn)記IP)“gin3”表示“前3個(gè)變量為整數(shù)”，等價(jià)于：ginx1ginx2ginx3IP的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z(mì)=632max2x1+3x2+4x3st1.5x1+3x2+5x3<600280x1+250x2+400x3<60000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解

IP結(jié)果輸出IP可用LINDO直接求解整數(shù)規(guī)劃(IntegerProg整數(shù)規(guī)劃例5最佳組隊(duì)問(wèn)題

有一場(chǎng)由四個(gè)項(xiàng)目(高低杠、平衡木、跳馬、自由體操)組成的女子體操團(tuán)體賽，賽程規(guī)定：每個(gè)隊(duì)至多允許10名運(yùn)動(dòng)員參賽，每一個(gè)項(xiàng)目可以有6名選手參加．每個(gè)選手參賽的成績(jī)?cè)u(píng)分從高到低依次為：10至0．每個(gè)代表隊(duì)的總分是參賽選手所得總分之和，總分最多的代表隊(duì)為優(yōu)勝者．此外，還規(guī)定每個(gè)運(yùn)動(dòng)員只能參加全能比賽(四項(xiàng)全參加)與單項(xiàng)比賽這兩類(lèi)中的一類(lèi)，參加單項(xiàng)比賽的每個(gè)運(yùn)動(dòng)員至多只能參加三項(xiàng)單項(xiàng)．每個(gè)隊(duì)?wèi)?yīng)有4人參加全能比賽，其余運(yùn)動(dòng)員參加單項(xiàng)比賽．現(xiàn)某代表隊(duì)的教練已經(jīng)對(duì)其所帶領(lǐng)的10名運(yùn)動(dòng)員參加各個(gè)項(xiàng)目的成績(jī)進(jìn)行了大量測(cè)試，教練發(fā)現(xiàn)每個(gè)運(yùn)動(dòng)員在每個(gè)單項(xiàng)上的成績(jī)得分期望值如下表所示．請(qǐng)建立模型為該隊(duì)排出一個(gè)出場(chǎng)陣容，使該隊(duì)團(tuán)體總分盡可能高．下表是運(yùn)動(dòng)員各項(xiàng)目得分期望表LINGO中@GIN(r);表示變量r為整數(shù)@BIN(r);表示變量r取值為0或1整數(shù)規(guī)劃例5最佳組隊(duì)問(wèn)題有一場(chǎng)由四個(gè)項(xiàng)目(高低杠、平衡優(yōu)化類(lèi)數(shù)學(xué)模型課件iMATLAB中線性規(guī)劃命令linprog非線性規(guī)劃命令fminconiMATLAB中線性規(guī)劃命令linprog優(yōu)化類(lèi)數(shù)學(xué)模型

線性規(guī)劃模型

非線性規(guī)劃模型

整數(shù)規(guī)劃模型優(yōu)化類(lèi)數(shù)學(xué)模型

線性規(guī)劃模型

非線性規(guī)劃模型

整數(shù)規(guī)劃§1最優(yōu)化問(wèn)題1．1最優(yōu)化問(wèn)題概念（1）最優(yōu)化問(wèn)題在工業(yè)、農(nóng)業(yè)、交通運(yùn)輸、商業(yè)、國(guó)防、建筑、通信、政府機(jī)關(guān)等各部門(mén)各領(lǐng)域的實(shí)際工作中，我們經(jīng)常會(huì)遇到求函數(shù)的極值或最大值最小值問(wèn)題，這一類(lèi)問(wèn)題我們稱(chēng)之為最優(yōu)化問(wèn)題。而求解最優(yōu)化問(wèn)題的數(shù)學(xué)方法被稱(chēng)為最優(yōu)化方法。它主要解決最優(yōu)生產(chǎn)計(jì)劃、最優(yōu)分配、最佳設(shè)計(jì)、最優(yōu)決策、最優(yōu)管理等求函數(shù)最大值最小值問(wèn)題。

最優(yōu)化問(wèn)題的目的有兩個(gè)：①求出滿足一定條件下，函數(shù)的極值或最大值最小值；②求出取得極值時(shí)變量的取值。最優(yōu)化問(wèn)題所涉及的內(nèi)容種類(lèi)繁多，有的十分復(fù)雜，但是它們都有共同的關(guān)鍵因素：變量，約束條件和目標(biāo)函數(shù)?！?最優(yōu)化問(wèn)題（2）變量變量是指最優(yōu)化問(wèn)題中所涉及的與約束條件和目標(biāo)函數(shù)有關(guān)的待確定的量。一般來(lái)說(shuō)，它們都有一些限制條件（約束條件），與目標(biāo)函數(shù)緊密關(guān)聯(lián)。設(shè)問(wèn)題中涉及的變量為x1,x2......xn；我們常常也用X=(x1,x2......xn)表示。（2）變量（3）約束條件在最優(yōu)化問(wèn)題中，求目標(biāo)函數(shù)的極值時(shí)，變量必須滿足的限制稱(chēng)為約束條件。例如，許多實(shí)際問(wèn)題變量要求必須非負(fù)，這是一種限制；在研究電路優(yōu)化設(shè)計(jì)問(wèn)題時(shí)，變量必須服從電路基本定律，這也是一種限制等等。在研究問(wèn)題時(shí)，這些限制我們必須用數(shù)學(xué)表達(dá)式準(zhǔn)確地描述它們。用數(shù)學(xué)語(yǔ)言描述約束條件一般來(lái)說(shuō)有兩種：等式約束條件不等式約束條件

注：在最優(yōu)化問(wèn)題研究中，由于解的存在性十分復(fù)雜，一般來(lái)說(shuō)，我們不考慮不等式約束條件。這兩種約束條件最優(yōu)化問(wèn)題最優(yōu)解的存在性較復(fù)雜。（3）約束條件（4）目標(biāo)函數(shù)在最優(yōu)化問(wèn)題中，與變量有關(guān)的待求其極值（或最大值最小值）的函數(shù)稱(chēng)為目標(biāo)函數(shù)。目標(biāo)函數(shù)常用表示F(x)=f(x1,x2......xn)表示。當(dāng)目標(biāo)函數(shù)為某問(wèn)題的效益函數(shù)時(shí)，問(wèn)題即為求極大值；當(dāng)目標(biāo)函數(shù)為某問(wèn)題的費(fèi)用函數(shù)時(shí)，問(wèn)題即為求極小值等等。求極大值和極小值問(wèn)題實(shí)際上沒(méi)有原則上的區(qū)別，因?yàn)榍蟮臉O小值，也就是要求的極大值，兩者的最優(yōu)值在同一點(diǎn)取到。（4）目標(biāo)函數(shù)1．2最優(yōu)化問(wèn)題分類(lèi)

最優(yōu)化問(wèn)題種類(lèi)繁多，因而分類(lèi)的方法也有許多?？梢园醋兞康男再|(zhì)分類(lèi)，按有無(wú)約束條件分類(lèi)，按目標(biāo)函數(shù)的個(gè)數(shù)分類(lèi)等等。一般來(lái)說(shuō)，變量可以分為確定性變量，隨機(jī)變量和系統(tǒng)變量等等，相對(duì)應(yīng)的最優(yōu)化問(wèn)題分別稱(chēng)為：普通最優(yōu)化問(wèn)題，統(tǒng)計(jì)最優(yōu)化問(wèn)題和系統(tǒng)最優(yōu)化問(wèn)題。

(1)按有無(wú)約束條件分類(lèi)：無(wú)約束最優(yōu)化問(wèn)題，有約束最優(yōu)化問(wèn)題。

(2)按目標(biāo)函數(shù)的個(gè)數(shù)分類(lèi)：?jiǎn)文繕?biāo)最優(yōu)化問(wèn)題，多目標(biāo)最優(yōu)化問(wèn)題。

(3)按約束條件和目標(biāo)函數(shù)是否是線性函數(shù)分類(lèi)：線性最優(yōu)化問(wèn)題（線性規(guī)劃），非線性最優(yōu)化問(wèn)題（非線性規(guī)劃）。

(4)按約束條件和目標(biāo)函數(shù)是否是時(shí)間的函數(shù)分類(lèi)：靜態(tài)最優(yōu)化問(wèn)題和動(dòng)態(tài)最優(yōu)化問(wèn)題（動(dòng)態(tài)規(guī)劃）。

1．2最優(yōu)化問(wèn)題分類(lèi)

最優(yōu)化問(wèn)題種類(lèi)繁多，因而．

3最優(yōu)化問(wèn)題的求解步驟和數(shù)學(xué)模型

（1）最優(yōu)化問(wèn)題的求解步驟

最優(yōu)化問(wèn)題的求解涉及到應(yīng)用數(shù)學(xué)，計(jì)算機(jī)科學(xué)以及各專(zhuān)業(yè)領(lǐng)域等等，是一個(gè)十分復(fù)雜的問(wèn)題，然而它卻是需要我們重點(diǎn)關(guān)心的問(wèn)題之一。怎樣研究分析求解這類(lèi)問(wèn)題呢？其中最關(guān)鍵的是建立數(shù)學(xué)模型和求解數(shù)學(xué)模型。一般來(lái)說(shuō)，應(yīng)用最優(yōu)化方法解決實(shí)際問(wèn)題可分為四個(gè)步驟進(jìn)行：．

3最優(yōu)化問(wèn)題的求解步驟和數(shù)學(xué)模型

求解步驟

步驟1：建立模型提出最優(yōu)化問(wèn)題，變量是什么？約束條件有那些？目標(biāo)函數(shù)是什么？建立最優(yōu)化問(wèn)題數(shù)學(xué)模型：確定變量，建立目標(biāo)函數(shù)，列出約束條件——建立模型。步驟2：確定求解方法分析模型，根據(jù)數(shù)學(xué)模型的性質(zhì)，選擇優(yōu)化求解方法——確定求解方法。步驟3：計(jì)算機(jī)求解編程序（或使用數(shù)學(xué)計(jì)算軟件），應(yīng)用計(jì)算機(jī)求最優(yōu)解——計(jì)算機(jī)求解。步驟4：結(jié)果分析對(duì)算法的可行性、收斂性、通用性、時(shí)效性、穩(wěn)定性、靈敏性和誤差等等作出評(píng)價(jià)——結(jié)果分析。求解步驟

步驟1：建立模型線性規(guī)劃（LinearProgramming）運(yùn)籌學(xué)的一個(gè)分支，主要用于生產(chǎn)計(jì)劃、物資運(yùn)輸、庫(kù)存、勞動(dòng)力分配以及最優(yōu)設(shè)計(jì)問(wèn)題等。類(lèi)似于條件極值問(wèn)題，只是其目標(biāo)函數(shù)和約束條件都是線性函數(shù)。線性規(guī)劃模型的特點(diǎn)1.比例性:每個(gè)決策變量對(duì)目標(biāo)函數(shù)和每個(gè)約束條件右端項(xiàng)的“貢獻(xiàn)”與該變量的取值成比例；2.可加性:每個(gè)決策變量對(duì)目標(biāo)函數(shù)和每個(gè)約束條件右端項(xiàng)的“貢獻(xiàn)”與其他變量的取值無(wú)關(guān)；3.連續(xù)性:每個(gè)決策變量的取值是連續(xù)的。線性規(guī)劃模型的三個(gè)要素決策變量：根據(jù)實(shí)際問(wèn)題所選擇的可以控制的因素；目標(biāo)函數(shù)：以線性函數(shù)形式表示所追求的目標(biāo)；約束條件：決策變量需要滿足的限定條件，一般是一組線性等式或不等式。線性規(guī)劃（LinearProgramming）二、線性規(guī)劃模型的求解（一）圖解法（n<=3時(shí)）（二）單純形法（三）數(shù)學(xué)軟件：如LINDO軟件二、線性規(guī)劃模型的求解（一）圖解法（n<=3時(shí)）（二）單純形例1某公司生產(chǎn)甲、乙兩種產(chǎn)品，每噸銷(xiāo)售后的利潤(rùn)分別為4000元與3000元。生產(chǎn)甲產(chǎn)品需要用A、B機(jī)器加工，加工時(shí)間分別為每噸2小時(shí)和1小時(shí)；生產(chǎn)乙產(chǎn)品需要用A、B、C三種機(jī)器加工，加工時(shí)間為每噸各1小時(shí)。若每天用于加工的機(jī)器時(shí)數(shù)分別為A機(jī)器10小時(shí)、B機(jī)器8小時(shí)、C機(jī)器7小時(shí)，問(wèn)該廠每天應(yīng)該生產(chǎn)甲、乙兩種產(chǎn)品各多少?lài)嵅拍苁估麧?rùn)最大？例1某公司生產(chǎn)甲、乙兩種產(chǎn)品，每噸銷(xiāo)售后的利潤(rùn)分別為400例2某工廠在計(jì)劃期內(nèi)安排生產(chǎn)甲、乙兩種產(chǎn)品。已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)數(shù)、A、B兩種原料的消耗以及單位利潤(rùn)如下表所示，問(wèn)應(yīng)該如何安排生產(chǎn)計(jì)劃使該工廠獲利最多？答案：生產(chǎn)甲4個(gè)，乙3個(gè)，獲利為17例2某工廠在計(jì)劃期內(nèi)安排生產(chǎn)甲、乙兩種產(chǎn)品。已知生產(chǎn)單位產(chǎn)自來(lái)水輸送與貨機(jī)裝運(yùn)生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤(rùn)最大；運(yùn)輸問(wèn)題各種類(lèi)型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少。自來(lái)水輸送與貨機(jī)裝運(yùn)生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求例1

居民用水調(diào)度問(wèn)題某市有甲、乙、丙、丁四個(gè)居民區(qū)，自來(lái)水由A、B、C三個(gè)水庫(kù)供應(yīng)．四個(gè)區(qū)每天必須得到保證的基本生活用水分別為30，70，10，10千噸，但由于水源緊張，三個(gè)水庫(kù)每天最多只能分別供應(yīng)50，60，50千噸自來(lái)水．由于地理位置的差別，自來(lái)水公司從各水庫(kù)向各區(qū)送水所需付出的引水管理費(fèi)不同(見(jiàn)下表，其中C水庫(kù)與丁區(qū)之間沒(méi)有輸水管道)，其他管理費(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)如何分配供水量，才能獲利最多？例1居民用水調(diào)度問(wèn)題某市有甲、乙、丙、丁四個(gè)居民區(qū)，自來(lái)其他費(fèi)用:450元/千噸

應(yīng)如何分配水庫(kù)供水量，公司才能獲利最多？

若水庫(kù)供水量都提高一倍，公司利潤(rùn)可增加到多少？元/千噸甲乙丙丁A160130220170B140130190150C190200230/引水管理費(fèi)例1自來(lái)水輸送收入：900元/千噸

支出A：50B：60C：50甲：30；50乙：70；70丙：10；20?。?0；40水庫(kù)供水量(千噸)小區(qū)基本用水量(千噸)小區(qū)額外用水量(千噸)（以天計(jì)）其他費(fèi)用:450元/千噸應(yīng)如何分配水庫(kù)供水量，公司才能獲供應(yīng)限制約束條件需求限制

線性規(guī)劃模型(LP)目標(biāo)函數(shù)

水庫(kù)i向j區(qū)的日供水量為xij（x34=0）決策變量

模型建立確定3個(gè)水庫(kù)向4個(gè)小區(qū)的供水量供應(yīng)限制約束條件需求限制線性規(guī)劃模型(LP)目標(biāo)函數(shù)水庫(kù)模型求解

OBJECTIVEFUNCTIONVALUE1)24400.00VARIABLEVALUEREDUCEDCOSTX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.000000X210.00000010.000000

X22

50.0000000.000000X230.00000020.000000X24

10.0000000.000000X31

40.0000000.000000X320.00000010.000000X33

10.0000000.000000利潤(rùn)=總收入-其它費(fèi)用-引水管理費(fèi)=144000-72000-24400=47600（元）

A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010引水管理費(fèi)24400(元)模型求解OBJECTIVEFUNCTIONVALUE利目標(biāo)函數(shù)

總供水量(320)>總需求量(300)每個(gè)水庫(kù)最大供水量都提高一倍利潤(rùn)=收入(900)–其它費(fèi)用(450)

–引水管理費(fèi)利潤(rùn)(元/千噸)甲乙丙丁A290320230280B310320260300C260250220/供應(yīng)限制B,C類(lèi)似處理問(wèn)題討論

確定送水方案使利潤(rùn)最大需求約束可以不變目標(biāo)函數(shù)總供水量(320)>總需求量(300)每個(gè)水庫(kù)求解OBJECTIVEFUNCTIONVALUE1)88700.00VARIABLEVALUEREDUCEDCOSTX110.00000020.000000X12100.0000000.000000X130.00000040.000000X140.00000020.000000

X21

30.0000000.000000X2240.0000000.000000

X230.00000010.000000X2450.0000000.000000

X31

50.0000000.000000X320.00000020.000000X33

30.0000000.000000這類(lèi)問(wèn)題一般稱(chēng)為“運(yùn)輸問(wèn)題”(TransportationProblem)總利潤(rùn)88700（元）

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030求解OBJECTIVEFUNCTIONVALUE這類(lèi)問(wèn)非線性規(guī)劃模型，可以用LINGO求解非線性規(guī)劃模型，可以用LINGO求解非線性規(guī)劃（None-linearProgramming）例4

板材切割問(wèn)題

某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按照顧客的要求切割后售出．從鋼管廠進(jìn)貨時(shí)得到的原料鋼管都是19m長(zhǎng)．(1)現(xiàn)有一個(gè)客戶需要50根4m、20根6m和15根8m長(zhǎng)的鋼管．應(yīng)如何下料最節(jié)省?(2)零售商如果采用的切割模式太多，將會(huì)導(dǎo)致生產(chǎn)過(guò)程的復(fù)雜性，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的不同切割模式不能超過(guò)3種．此外，該客戶除需要上述的三種鋼管外，還需要10根5m長(zhǎng)的鋼管，應(yīng)如何下料最節(jié)省?非線性規(guī)劃（None-linearProgramming）首先，應(yīng)當(dāng)確定哪些切割模式是可行的，所謂一個(gè)切割模式，是指按照客戶需要在原料鋼管上安排切割的一種組合．其次，應(yīng)當(dāng)確定哪些切割模式是合理的．通常假設(shè)一個(gè)合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸．在這種合理性假設(shè)下，切割模式一共有7種，如下表首先，應(yīng)當(dāng)確定哪些切割模式是可行的，所謂一個(gè)切割模式，是指按優(yōu)化類(lèi)數(shù)學(xué)模型課件LINGO中@GIN(r);表示變量r為整數(shù)LINGO中@GIN(r);表示變量r為整數(shù)第三講整數(shù)規(guī)劃建模方法一、從現(xiàn)實(shí)問(wèn)題到整數(shù)規(guī)劃模型二、整數(shù)規(guī)劃模型的求解三、整數(shù)規(guī)劃的建模實(shí)例第三講整數(shù)規(guī)劃建模方法一、從現(xiàn)實(shí)問(wèn)題到整數(shù)規(guī)劃模型二、整4.1整數(shù)規(guī)劃簡(jiǎn)介要求所有xj的解為整數(shù)，稱(chēng)為純整數(shù)規(guī)劃要求部分xj的解為整數(shù)，稱(chēng)為混合整數(shù)規(guī)劃對(duì)應(yīng)沒(méi)有整數(shù)解要求的線性規(guī)劃稱(chēng)之為松弛問(wèn)題整數(shù)規(guī)劃的解是可數(shù)個(gè)的，最優(yōu)解不一定發(fā)生在極點(diǎn)整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其松弛問(wèn)題的最優(yōu)解4.1整數(shù)規(guī)劃簡(jiǎn)介要求所有xj的解為整數(shù)，稱(chēng)為純整數(shù)規(guī)4.2整數(shù)規(guī)劃的分枝定界法3、求解分枝的松弛問(wèn)題—定界過(guò)程設(shè)兩個(gè)分枝的松弛問(wèn)題分別為問(wèn)題1和問(wèn)題2，它們的最優(yōu)解有如下情況

4.2.1思路與解題步驟只解松弛問(wèn)題1、在全部可行性域上解松弛問(wèn)題若松弛問(wèn)題最優(yōu)解為整數(shù)解，則其也是整數(shù)規(guī)劃的最優(yōu)解2、分枝過(guò)程若松弛問(wèn)題最優(yōu)解中某個(gè)xk=bk不是整數(shù)，令bk為bk

的整數(shù)部分構(gòu)造兩個(gè)新的約束條件xkbk和xkbk+1，分別加于原松弛問(wèn)題，形成兩個(gè)新的整數(shù)規(guī)劃4.2整數(shù)規(guī)劃的分枝定界法3、求解分枝的松弛問(wèn)題—定界4.2.2分枝定界法舉例

例4.1.1

解：松弛問(wèn)題的最優(yōu)解為x1=2.5,x2=2,OBJ=23

由x1=2.5得到兩個(gè)分枝如下：4.2.2分枝定界法舉例例4.1.1解表4.2.3分枝問(wèn)題的松弛解問(wèn)題II的解即原整數(shù)問(wèn)題的最優(yōu)解（X1=3，X2=1）

可能存在兩個(gè)分枝都是非整數(shù)解的情況，則需要兩邊同時(shí)繼續(xù)分枝，直到有整數(shù)解出現(xiàn)，就可以進(jìn)行定界過(guò)程當(dāng)存在很多變量有整數(shù)約束時(shí)，分枝即廣又深，在最壞情況下相當(dāng)于組合所有可能的整數(shù)解一般整數(shù)規(guī)劃問(wèn)題屬于一類(lèi)未解決的難題，NP-complete，只有少數(shù)特殊問(wèn)題有好的算法，如任務(wù)分配問(wèn)題、匹配問(wèn)題表4.2.3分枝問(wèn)題的松弛解問(wèn)題II的解即原整數(shù)問(wèn)例.某廠擬用集裝箱托運(yùn)甲,乙兩種貨物。已知問(wèn)：如何安排利潤(rùn)最大？設(shè)甲乙分別托運(yùn)x1,x2箱模型建立

IP(1)-(4)稱(chēng)為與(IP)相對(duì)應(yīng)的線性規(guī)劃(LP)求解(LP)得x1=4.81,x2=1.82,z=356例.某廠擬用集裝箱托運(yùn)甲,乙兩種貨物。已知問(wèn)：如何安排利潤(rùn)最分枝定界法(branchandboundmethod)(IP)x1*,x2*,z*(LP) x1=4.81,x2=1.82,z0=356(LP1)x1=4,x2=2.1,z0=349X1≤4X1≥5(LP2)x1=5,x2=1.57,z0=341(z*≤349定界)(LP3)x1=4,x2=2,z0=340X2≤2X2≥3(LP4)x2=3,x1=1.42,z0=327(z*≥340定界)(LP5)x2=1,x1=5.44,z0=308X2≤1(LP6)無(wú)可行解X2≥2X1≤4X1≥5分枝：分枝定界法(branchandboundmethod)設(shè)每月生產(chǎn)小、中、大型汽車(chē)的數(shù)量分別為x1,x2,x3汽車(chē)廠生產(chǎn)計(jì)劃,任一型號(hào)汽車(chē)要生產(chǎn)至少80輛模型建立

小型中型大型現(xiàn)有量鋼材1.535600時(shí)間280250