《運(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ī)劃問題的目標(biāo)函數(shù)和約束條件都是線性的。但在許多實(shí)際問題中，往往會(huì)遇到目標(biāo)函數(shù)或約束條件是非線性的情況，這類規(guī)劃問題就是非線性規(guī)劃問題。在規(guī)劃問題中，如果目標(biāo)函數(shù)或約束條件中有一個(gè)是決策變量的非線性函數(shù)，則這類規(guī)劃問題稱為非線性規(guī)劃問題。本章將介紹其中一類比較簡單的情形，即目標(biāo)函數(shù)是決策變量的非線性函數(shù)，而約束條件是線性的。7.1非線性規(guī)劃的基本概念例7-1

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

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

，因此，門的每周凈利潤為375x1－25x12

；②窗的每周銷售毛利潤為700x2，每周營銷成本為60x22

，因此，窗的每周凈利潤為700x2－60x22

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

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

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

需要加班的例1-1。

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

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

x1O為加班時(shí)間內(nèi)門的每周產(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)品的總利潤最大。由于正常工作時(shí)間和加班時(shí)間生產(chǎn)的產(chǎn)品的單位利潤不同，所以在目標(biāo)函數(shù)中用的是新引入的決策變量。（3）約束條件①原有的例1-1的三個(gè)車間的約束還是有效的，只不過用（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)量總和，也就是說，有：x1=x1R+x1O，x2=x2R+x2O所以例7-4的數(shù)學(xué)模型也可以寫為：用原來的2個(gè)決策變量＋新引入的4個(gè)決策變量7.3.2邊際收益遞增的可分離規(guī)劃例7-5

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