《運(yùn)籌學(xué)（第3版）》 課件 第7章 非線性規(guī)劃

實(shí)用運(yùn)籌學(xué)

－－運(yùn)用Excel建模和求解（第3版）第7章非線性規(guī)劃NonlinearProgramming本章內(nèi)容要點(diǎn)非線性規(guī)劃的基本概念二次規(guī)劃可分離規(guī)劃本章主要內(nèi)容框架圖7.1非線性規(guī)劃的基本概念前6章所涉及規(guī)劃問(wèn)題的目標(biāo)函數(shù)和約束條件都是線性的。但在許多實(shí)際問(wèn)題中，往往會(huì)遇到目標(biāo)函數(shù)或約束條件是非線性的情況，這類(lèi)規(guī)劃問(wèn)題就是非線性規(guī)劃問(wèn)題。在規(guī)劃問(wèn)題中，如果目標(biāo)函數(shù)或約束條件中有一個(gè)是決策變量的非線性函數(shù)，則這類(lèi)規(guī)劃問(wèn)題稱(chēng)為非線性規(guī)劃問(wèn)題。本章將介紹其中一類(lèi)比較簡(jiǎn)單的情形，即目標(biāo)函數(shù)是決策變量的非線性函數(shù)，而約束條件是線性的。7.1非線性規(guī)劃的基本概念例7-1

用一根長(zhǎng)度為400米的繩子，圍成一塊矩形的菜地，問(wèn)長(zhǎng)和寬各為多少米時(shí)菜地的面積最大？【解】本問(wèn)題是一個(gè)小學(xué)數(shù)學(xué)問(wèn)題，現(xiàn)在把它當(dāng)作一個(gè)規(guī)劃問(wèn)題來(lái)求解。（1）決策變量設(shè)矩形菜地的長(zhǎng)為x1米，寬為x2米。（2）目標(biāo)函數(shù)菜地的面積最大。（3）約束條件 ①繩子長(zhǎng)度為400米 ②非負(fù)7.1非線性規(guī)劃的基本概念例7-1的電子表格模型（采用“非線性GRG”求解方法）7.1.2非線性規(guī)劃的求解方法例7-2求解復(fù)雜的非線性規(guī)劃問(wèn)題：7.1.2非線性規(guī)劃的求解方法例7-2的電子表格模型（采用“非線性GRG”求解方法，與初始值有關(guān)）7.1.2非線性規(guī)劃的求解方法正是局部最優(yōu)解的存在，才使得非線性規(guī)劃問(wèn)題的求解要比線性規(guī)劃問(wèn)題的求解復(fù)雜得多。當(dāng)求得一個(gè)最優(yōu)解時(shí)，常常無(wú)法確定該最優(yōu)解是否為全局最優(yōu)解。處理復(fù)雜的有幾個(gè)局部極大值的非線性規(guī)劃問(wèn)題，一個(gè)方法就是重復(fù)應(yīng)用Excel的“規(guī)劃求解”（采用“非線性GRG”求解方法），用不同的初始值進(jìn)行測(cè)試，然后從這些局部最優(yōu)解中挑選出最優(yōu)的一個(gè)。雖然這種方法仍然不能保證找到全局最優(yōu)解，但它畢竟對(duì)找到一個(gè)相當(dāng)好的解給予了很大的可能。因此，對(duì)一些相對(duì)較小的問(wèn)題而言，這是一種合理的方法。Excel的“規(guī)劃求解”功能有一個(gè)搜索程序（算法），稱(chēng)為“演化”求解方法（EvolutionarySolver）。7.1.2非線性規(guī)劃的求解方法例7-2的電子表格模型（采用“演化”求解方法，與初始值無(wú)關(guān)）7.2二次規(guī)劃若某非線性規(guī)劃的目標(biāo)函數(shù)為決策變量的二次函數(shù)，而且是邊際收益遞減的，約束條件又都是線性的，那么稱(chēng)這種規(guī)劃為二次規(guī)劃。決策變量在有限域內(nèi)變動(dòng)的邊際收益遞減的二次規(guī)劃存在最優(yōu)解，且此最優(yōu)解與初始值無(wú)關(guān)，即局部最優(yōu)解就是全局最優(yōu)解。實(shí)際上，二次規(guī)劃是非線性規(guī)劃中比較簡(jiǎn)單的一種，只要問(wèn)題不是很復(fù)雜，Excel的“規(guī)劃求解”功能就能求解。7.2二次規(guī)劃在營(yíng)銷(xiāo)過(guò)程中，營(yíng)銷(xiāo)成本往往是非線性的，而且隨著銷(xiāo)量的增加，單位營(yíng)銷(xiāo)成本也在增加。也就是說(shuō)，單位利潤(rùn)隨著銷(xiāo)量的增加而減少（邊際收益遞減）。例7-3

考慮非線性營(yíng)銷(xiāo)成本的例1-1。在例1-1中，增加考慮新產(chǎn)品（門(mén)和窗）的營(yíng)銷(xiāo)成本。原來(lái)估計(jì)每扇門(mén)的營(yíng)銷(xiāo)成本是75元、每扇窗的營(yíng)銷(xiāo)成本是200元。因此，當(dāng)時(shí)估計(jì)的門(mén)和窗的單位利潤(rùn)分別是300元和500元。也就是說(shuō)，如果不考慮營(yíng)銷(xiāo)成本，每扇門(mén)的毛利潤(rùn)是375元，每扇窗的毛利潤(rùn)是700元。已知門(mén)和窗的營(yíng)銷(xiāo)成本隨著銷(xiāo)量的增加而呈現(xiàn)非線性增長(zhǎng)，若設(shè)x1為門(mén)的每周產(chǎn)量，x2為窗的每周產(chǎn)量，則門(mén)每周的營(yíng)銷(xiāo)成本為25x12，窗每周的營(yíng)銷(xiāo)成本為60x22。7.2二次規(guī)劃【解】新的模型考慮了非線性的營(yíng)銷(xiāo)成本，所以在原來(lái)模型的基礎(chǔ)上，需要修改目標(biāo)函數(shù)。（1）決策變量設(shè)x1為門(mén)的每周產(chǎn)量，x2為窗的每周產(chǎn)量。（2）目標(biāo)函數(shù)①門(mén)的每周銷(xiāo)售毛利潤(rùn)為375x1，每周營(yíng)銷(xiāo)成本為25x12

，因此，門(mén)的每周凈利潤(rùn)為375x1－25x12

；②窗的每周銷(xiāo)售毛利潤(rùn)為700x2，每周營(yíng)銷(xiāo)成本為60x22

，因此，窗的每周凈利潤(rùn)為700x2－60x22

。本問(wèn)題的目標(biāo)是兩種新產(chǎn)品的總利潤(rùn)最大。7.2二次規(guī)劃（3）約束條件

依舊是原有的三個(gè)車(chē)間每周可用工時(shí)限制和非負(fù)約束。

例7-3的二次規(guī)劃模型：7.2二次規(guī)劃例7-3的電子表格模型7.3可分離規(guī)劃當(dāng)利潤(rùn)（或成本）曲線是分段直線時(shí)，可分離規(guī)劃技術(shù)可將非線性規(guī)劃問(wèn)題轉(zhuǎn)化為相應(yīng)的線性規(guī)劃問(wèn)題。這有助于非常有效地求解問(wèn)題，并且可以對(duì)轉(zhuǎn)化后的線性規(guī)劃問(wèn)題進(jìn)行靈敏度分析。可分離規(guī)劃技術(shù)為利潤(rùn)（或成本）曲線上的每段直線引入新的決策變量，以代替原來(lái)單一的決策變量。也就是為利潤(rùn)（或成本）曲線的每個(gè)線段給出一個(gè)分離的決策變量。產(chǎn)品每周最大產(chǎn)量單位利潤(rùn)正常生產(chǎn)加班生產(chǎn)總計(jì)正常生產(chǎn)加班生產(chǎn)門(mén)314300200窗336500100車(chē)間3的約束條件：7.3.1邊際收益遞減的可分離規(guī)劃例7-4

需要加班的例1-1。

表7-1給出了車(chē)間1和車(chē)間2每周在正常工作時(shí)間和加班時(shí)間生產(chǎn)門(mén)和窗的最大數(shù)量及單位利潤(rùn)。車(chē)間3不需要加班，約束條件也不需要改變。7.3.1邊際收益遞減的可分離規(guī)劃【解】（1）決策變量例1-1中的決策變量是：門(mén)的每周產(chǎn)量x1，窗的每周產(chǎn)量x2。由于加班生產(chǎn)的產(chǎn)品單位利潤(rùn)減少，所以利用可分離規(guī)劃技術(shù)，將正常工作時(shí)間和加班時(shí)間的產(chǎn)量分開(kāi)，引入新的決策變量：

x1R為正常工作時(shí)間內(nèi)門(mén)的每周產(chǎn)量，

x1O為加班時(shí)間內(nèi)門(mén)的每周產(chǎn)量；

x2R為正常工作時(shí)間內(nèi)窗的每周產(chǎn)量，

x2O為加班時(shí)間內(nèi)窗的每周產(chǎn)量。并且有：x1=x1R+x1O

，

x2=x2R+x2O7.3.1邊際收益遞減的可分離規(guī)劃（2）目標(biāo)函數(shù)

兩種新產(chǎn)品的總利潤(rùn)最大。由于正常工作時(shí)間和加班時(shí)間生產(chǎn)的產(chǎn)品的單位利潤(rùn)不同，所以在目標(biāo)函數(shù)中用的是新引入的決策變量。（3）約束條件①原有的例1-1的三個(gè)車(chē)間的約束還是有效的，只不過(guò)用（x1R＋x1O）代替x1，用（x2R＋x2O）代替x2。②正常工作時(shí)間和加班時(shí)間的每周最大產(chǎn)量約束③非負(fù)用新引入的4個(gè)決策變量7.3.1邊際收益遞減的可分離規(guī)劃例7-4的電子表格模型7.3.1邊際收益遞減的可分離規(guī)劃由于總產(chǎn)量＝每種產(chǎn)品在正常工作時(shí)間內(nèi)和加班時(shí)間內(nèi)的產(chǎn)量總和，也就是說(shuō)，有：x1=x1R+x1O，x2=x2R+x2O所以例7-4的數(shù)學(xué)模型也可以寫(xiě)為：用原來(lái)的2個(gè)決策變量＋新引入的4個(gè)決策變量7.3.2邊際收益遞增的可分離規(guī)劃例7-5

原油采購(gòu)與加工問(wèn)題。某公司用兩種原油（A和B）混合加工成兩種汽油（甲和乙），甲和乙兩種汽油含原油A的最低比例分別為50%和60%，每噸售價(jià)分別為4800元和5600元。該公司現(xiàn)有原油A和B的庫(kù)存量分別為500噸和1000噸，還可以從市場(chǎng)上買(mǎi)到不超過(guò)1500噸的原油A。原油A的市場(chǎng)價(jià)為：購(gòu)買(mǎi)量不超過(guò)400噸時(shí)的單價(jià)為10000元/噸；購(gòu)買(mǎi)量超過(guò)400噸但不超過(guò)900噸時(shí)，超過(guò)400噸的部分單價(jià)為8000元/噸；購(gòu)買(mǎi)量超過(guò)900噸時(shí)，超過(guò)900噸的部分單價(jià)為6000元/噸。該公司應(yīng)如何安排原油的采購(gòu)和加工？7.3.2邊際收益遞增的可分離規(guī)劃例7-5的混合0-1規(guī)劃模型7.3.2邊際收益遞增的可分離規(guī)例7-5的電子表格模型補(bǔ)充：WPS表格WPS表格，也有“規(guī)劃求解”，在“數(shù)據(jù)”->“模擬分析”->“規(guī)劃求解”。WPS的“規(guī)劃求解”功能，可以完成：線性規(guī)劃的求解方法：?jiǎn)渭兙€性規(guī)劃，與Excel的“規(guī)劃求解”相同；非線性規(guī)劃的求解方法：非線性內(nèi)點(diǎn)法，與Excel的“規(guī)劃求解”求解方法（非線性GRG）不同。不同點(diǎn)：在“公式”中應(yīng)用名稱(chēng)，操作不同(Excel自動(dòng)引用名稱(chēng)，WPS表格需要手動(dòng)“粘貼”名稱(chēng)或手動(dòng)輸入名稱(chēng)）；在“規(guī)劃求解參數(shù)”對(duì)話框中應(yīng)用名稱(chēng)，操作相同（Excel自動(dòng)引用名稱(chēng)，但WPS表格第一次求解時(shí)目標(biāo)和可變單元格沒(méi)有自動(dòng)引用名稱(chēng)，第二次求解時(shí)才自動(dòng)引用名稱(chēng)）。Excel的“規(guī)劃求解”有“演化”求解方法，但WPS表格沒(méi)有。本章上機(jī)實(shí)驗(yàn)1．實(shí)驗(yàn)?zāi)康恼莆绽肊xcel求解非線性規(guī)劃問(wèn)題的操作方法。