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

實用運籌學

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

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

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

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

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

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

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

依舊是原有的三個車間每周可用工時限制和非負約束。

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

需要加班的例1-1。

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

x1R為正常工作時間內門的每周產量，

x1O為加班時間內門的每周產量；

x2R為正常工作時間內窗的每周產量，

x2O為加班時間內窗的每周產量。并且有：x1=x1R+x1O

，

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

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

原油采購與加工問題。某公司用兩種原油（A和B）混合加工成兩種汽油（甲和乙），甲和乙兩種汽油含原油A的最低比例分別為50%和60%，每噸售價分別為4800元和5600元。該公司現有原油A和B的庫存量分別為500噸和1000噸，還可以從市場上買到不超過1500噸的原油A。原油A的市場價為：購買量不超過400噸時的單價為10000元/噸；購買量超過400噸但不超過900噸時，超過400噸的部分單價為8000元/噸；購買量超過900噸時，超過900噸的部分單價為6000元/噸。該公司應如何安排原油的采購和加工？7.3.2邊際收益遞增的可分離規(guī)劃例7-5的混合0-1規(guī)劃模型7.3.2邊際收益遞增的可分離規(guī)例7-5的電子表格模型補充：WPS表格WPS表格，也有“規(guī)劃求解”，在“數據”->“模擬分析”->“規(guī)劃求解”。WPS的“規(guī)劃求解”功能，可以完成：線性規(guī)劃的求解方法：單純線性規(guī)劃，與Excel的“規(guī)劃求解”相同；非線性規(guī)劃的求解方法：非線性內點法，與Excel的“規(guī)劃求解”求解方法（非線性GRG）不同。不同點：在“公式”中應用名稱，操作不同(Excel自動引用名稱，WPS表格需要手動“粘貼”名稱或手動輸入名稱）；在“規(guī)劃求解參數”對話框中應用名稱，操作相同（Excel自動引用名稱，但WPS表格第一次求解時目標和可變單元格沒有自動引用名稱，第二次求解時才自動引用名稱）。Excel的“規(guī)劃求解”有“演化”求解方法，但WPS表格沒有。本章上機實驗1．實驗目的掌握利用Excel求解非線性規(guī)劃問題的操作方法。