《運籌學(xué)（第3版）》 課件 第7章 非線性規(guī)劃；第8章 線性目標(biāo)規(guī)劃

實用運籌學(xué)

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

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

考慮非線性營銷成本的例1-1。在例1-1中，增加考慮新產(chǎn)品（門和窗）的營銷成本。原來估計每扇門的營銷成本是75元、每扇窗的營銷成本是200元。因此，當(dāng)時估計的門和窗的單位利潤分別是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）約束條件

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

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

需要加班的例1-1。

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

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

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

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

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

，

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

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

原油采購與加工問題。某公司用兩種原油（A和B）混合加工成兩種汽油（甲和乙），甲和乙兩種汽油含原油A的最低比例分別為50%和60%，每噸售價分別為4800元和5600元。該公司現(xiàn)有原油A和B的庫存量分別為500噸和1000噸，還可以從市場上買到不超過1500噸的原油A。原油A的市場價為：購買量不超過400噸時的單價為10000元/噸；購買量超過400噸但不超過900噸時，超過400噸的部分單價為8000元/噸；購買量超過900噸時，超過900噸的部分單價為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)點法，與Excel的“規(guī)劃求解”求解方法（非線性GRG）不同。不同點：在“公式”中應(yīng)用名稱，操作不同(Excel自動引用名稱，WPS表格需要手動“粘貼”名稱或手動輸入名稱）；在“規(guī)劃求解參數(shù)”對話框中應(yīng)用名稱，操作相同（Excel自動引用名稱，但WPS表格第一次求解時目標(biāo)和可變單元格沒有自動引用名稱，第二次求解時才自動引用名稱）。Excel的“規(guī)劃求解”有“演化”求解方法，但WPS表格沒有。本章上機(jī)實驗1．實驗?zāi)康恼莆绽肊xcel求解非線性規(guī)劃問題的操作方法。2．內(nèi)容和要求利用Excel求解二次規(guī)劃、可分離規(guī)劃等，題目自選。3．操作步驟（1）在Excel中建立非線性規(guī)劃問題的電子表格模型；（2）利用Excel中的“規(guī)劃求解”功能求解非線性規(guī)劃問題；（3）結(jié)果分析；（4）在Word文檔（或PowerPoint演示文稿）中撰寫實驗報告，包括非線性規(guī)劃的數(shù)學(xué)模型、電子表格模型和結(jié)果分析等。實用運籌學(xué)

－－運用Excel建模和求解（第3版）第8章線性目標(biāo)規(guī)劃LinearGoalProgramming本章內(nèi)容要點目標(biāo)規(guī)劃的基本概念和數(shù)學(xué)模型優(yōu)先目標(biāo)規(guī)劃加權(quán)目標(biāo)規(guī)劃本章主要內(nèi)容框架圖目標(biāo)規(guī)劃的提出線性規(guī)劃的特征是在滿足一組約束的條件下，優(yōu)化一個單一目標(biāo)（如總利潤最大或總成本最小）。而在現(xiàn)實生活中最優(yōu)只是相對的，或者說沒有絕對意義上的最優(yōu)，只有相對意義上的滿意。1978年諾貝爾經(jīng)濟(jì)學(xué)獎獲得者西蒙（H.A.Simon）教授提出“滿意行為模型要比最大化行為模型豐富得多”，否定了企業(yè)的決策者是“經(jīng)濟(jì)人”的概念和“最大化”的行為準(zhǔn)則，提出了“管理人”的概念和“令人滿意”的行為準(zhǔn)則，對現(xiàn)代企業(yè)管理的決策科學(xué)進(jìn)行了開創(chuàng)性的研究。8.1目標(biāo)規(guī)劃的基本概念和數(shù)學(xué)模型對于第1章的例1-1，現(xiàn)在工廠領(lǐng)導(dǎo)要考慮市場等一系列其他因素，提出如下三個目標(biāo)：（1）根據(jù)市場信息，窗的銷量有下降的趨勢，故希望窗的產(chǎn)量不超過門產(chǎn)量的2倍；(希望≤)（2）車間3另有新的生產(chǎn)任務(wù),因此希望車間3節(jié)省4個工時用于新的生產(chǎn)任務(wù);(希望＝)（3）應(yīng)盡可能達(dá)到并超過計劃的每周總利潤3000元。（希望≥）例8-1

在工廠三個車間的工時不能超計劃使用的前提下，考慮上述三個目標(biāo)，應(yīng)如何安排生產(chǎn)，才能使這些目標(biāo)依次實現(xiàn)？8.1目標(biāo)規(guī)劃的基本概念和數(shù)學(xué)模型【解】引入正偏差變量和負(fù)偏差變量目標(biāo)約束1：目標(biāo)約束2：目標(biāo)約束3：優(yōu)先目標(biāo)規(guī)劃的目標(biāo)函數(shù)依次為：8.1目標(biāo)規(guī)劃的基本概念和數(shù)學(xué)模型目標(biāo)規(guī)劃的基本思想是化多目標(biāo)為單一目標(biāo)，下面引入與建立目標(biāo)規(guī)劃數(shù)學(xué)模型有關(guān)的概念。1．決策變量和偏差變量2．絕對約束和目標(biāo)約束3．優(yōu)先因子（優(yōu)先級）與權(quán)系數(shù)4．目標(biāo)規(guī)劃的目標(biāo)函數(shù)是由各目標(biāo)約束的正、負(fù)偏差變量和賦予的相應(yīng)的優(yōu)先因子及權(quán)系數(shù)組成的。決策者的愿望是盡可能縮小與目標(biāo)值的偏差，因此目標(biāo)函數(shù)總是最小化。8.1目標(biāo)規(guī)劃的基本概念和數(shù)學(xué)模型對于例8-1，分別賦予三個目標(biāo)優(yōu)先因子P1、P2、P3，則例8-1的目標(biāo)規(guī)劃數(shù)學(xué)模型為：目標(biāo)約束偏差變量8.1目標(biāo)規(guī)劃的基本概念和數(shù)學(xué)模型目標(biāo)規(guī)劃的一般數(shù)學(xué)模型為：目標(biāo)約束偏差變量8.2優(yōu)先目標(biāo)規(guī)劃在多目標(biāo)決策問題中，決策者往往根據(jù)自己對目標(biāo)的重視程度，賦予每個目標(biāo)一定的優(yōu)先級，從而將所有目標(biāo)排序：優(yōu)先目標(biāo)規(guī)劃就是按照目標(biāo)的先后順序，逐一滿足優(yōu)先級較高的目標(biāo)，最終得到一個滿意解。假如所有目標(biāo)都得到滿足，滿意解就是最優(yōu)解。

8.2優(yōu)先目標(biāo)規(guī)劃對于例8-1，假設(shè)三個目標(biāo)的優(yōu)先級依次為目標(biāo)1（P1）、目標(biāo)2（P2）、目標(biāo)3（P3）。由于有三個目標(biāo)要依次考慮，所以求解要分三步進(jìn)行：第一步：首先盡可能實現(xiàn)P1級目標(biāo)，這時不考慮次級目標(biāo)。在Excel中建立以優(yōu)先級1的目標(biāo)（目標(biāo)1）的正偏差最小化為目標(biāo)函數(shù)的電子表格模型：8.2優(yōu)先目標(biāo)規(guī)劃例8-1優(yōu)先級1的線性規(guī)劃數(shù)學(xué)模型為：8.2優(yōu)先目標(biāo)規(guī)劃第二步：在保證已求得的P1級目標(biāo)正偏差不變的前提下考慮P2級目標(biāo)。以優(yōu)先級2的目標(biāo)（目標(biāo)2）的偏差最小化為目標(biāo)函數(shù)的電子表格模型（增加一個約束條件，修改了目標(biāo)函數(shù)）：8.2優(yōu)先目標(biāo)規(guī)劃例8-1優(yōu)先級2的線性規(guī)劃數(shù)學(xué)模型為（修改了目標(biāo)函數(shù)，增加了一個約束條件）：8.2優(yōu)先目標(biāo)規(guī)劃第三步：在保證已求得的P1級和P2級目標(biāo)偏差不變的前提下考慮P3級目標(biāo)。以優(yōu)先級3的目標(biāo)（目標(biāo)3）的負(fù)偏差最小化為目標(biāo)函數(shù)的電子表格模型（再增加一個約束條件，修改了目標(biāo)函數(shù)）：8.2優(yōu)先目標(biāo)規(guī)劃例8-1優(yōu)先級3的線性規(guī)劃數(shù)學(xué)模型為（修改了目標(biāo)函數(shù)，再增加一個約束條件）：8.2.2優(yōu)先目標(biāo)規(guī)劃的應(yīng)用舉例例8-2提級加薪問題。某公司的員工工資有四級，根據(jù)公司的業(yè)務(wù)發(fā)展需要，準(zhǔn)備招收部分新員工，并將部分在職員工的工資提升一級。該公司的員工工資（年薪）及提級前后的編制如表8-2所示。其中提級后的編制是計劃編制，允許有變化。公司領(lǐng)導(dǎo)在考慮員工的升級調(diào)資方案時，依次遵守以下規(guī)定：（1）提級后在職員工的年工資總額不超過900萬元；（2）提級后各級的人數(shù)不超過編制規(guī)定的人數(shù)；（3）級別2、3、4的升級人數(shù)盡可能達(dá)到現(xiàn)有人數(shù)的20％，且無越級提升；（4）級別4不足編制的人數(shù)可錄用新員工，另外，級別1的員工中有1人要退休。該公司領(lǐng)導(dǎo)應(yīng)如何擬定一個滿意的員工升級調(diào)資方案。級別1級別2級別3級別4每人工資（萬元/年）121086現(xiàn)有人數(shù)（人）10204030編制人數(shù)（人）102252308.2.2優(yōu)先目標(biāo)規(guī)劃的應(yīng)用舉例【解】設(shè)x1，x2，x3，x4分別表示提升到級別1，2，3和錄用到級別4的新員工人數(shù)（整數(shù)），則提級后各級的員工人數(shù)分別為：三個目標(biāo)約束分別為：（1）提級后在職員工的年工資總額不超過900萬元（2）提級后各級的人數(shù)不超過編制規(guī)定的人數(shù)（3）級別2、3、4的升級人數(shù)盡可能達(dá)到現(xiàn)有人數(shù)的20％目標(biāo)函數(shù)為：8.2.2優(yōu)先目標(biāo)規(guī)劃的應(yīng)用舉例對于例8-2，由于有三個目標(biāo)要依次考慮，所以求解要分多步進(jìn)行：第一步：首先盡可能實現(xiàn)P1級目標(biāo)，這時不考慮次級目標(biāo)。在Excel中建立以優(yōu)先級1的目標(biāo)（目標(biāo)1）的正偏差最小化為目標(biāo)函數(shù)的電子表格模型。第一次規(guī)劃求解，滿足了優(yōu)先級1的目標(biāo)的要求，即目標(biāo)1（第一目標(biāo)）可以實現(xiàn)。同時，目標(biāo)2（第二目標(biāo)）也實現(xiàn)了。第二步：在保證已求得的P1級和P2級目標(biāo)偏差不變的前提下考慮P3級目標(biāo)。以優(yōu)先級3的目標(biāo)（目標(biāo)3）的負(fù)偏差最小化為目標(biāo)函數(shù)的電子表格模型（增加了兩個約束條件，修改了目標(biāo)函數(shù)）。8.2.2優(yōu)先目標(biāo)規(guī)劃的應(yīng)用舉例例8-2，第一步：首先盡可能實現(xiàn)P1級目標(biāo)，這時不考慮次級目標(biāo)。在Excel中建立以優(yōu)先級1的目標(biāo)（目標(biāo)1）的正偏差最小化為目標(biāo)函數(shù)的電子表格模型。第一次規(guī)劃求解，滿足了優(yōu)先級1的目標(biāo)的要求，即目標(biāo)1（第一目標(biāo)）可以實現(xiàn)。同時，目標(biāo)2（第二目標(biāo)）也實現(xiàn)了。8.2.2優(yōu)先目標(biāo)規(guī)劃的應(yīng)用舉例例8-2，第二步：在保證已求得的P1級和P2級目標(biāo)偏差不變的前提下考慮P3級目標(biāo)。以優(yōu)先級3的目標(biāo)（目標(biāo)3）的負(fù)偏差最小化為目標(biāo)函數(shù)的電子表格模型（增加了兩個約束條件，修改了目標(biāo)函數(shù)）：8.3加權(quán)目標(biāo)規(guī)劃在加權(quán)目標(biāo)規(guī)劃中，各目標(biāo)沒有明確的優(yōu)先級；所有偏差（含正、負(fù)偏差）都有相應(yīng)的偏離系數(shù)（偏離各目標(biāo)嚴(yán)重程度的罰數(shù)權(quán)重）；以偏差加權(quán)和（所有偏差與其罰數(shù)權(quán)重乘積的總和）為目標(biāo)函數(shù)，求其最小值。因此，相對于優(yōu)先目標(biāo)規(guī)劃，加權(quán)目標(biāo)規(guī)劃得到的滿意解是全局的。這個滿意解其實可以算作最優(yōu)解，但為了避免與一般線性規(guī)劃的最優(yōu)解發(fā)生概念上的混淆，仍稱之為滿意解。8.3加權(quán)目標(biāo)規(guī)劃加權(quán)目標(biāo)規(guī)劃的數(shù)學(xué)模型8.3加權(quán)目標(biāo)規(guī)劃例8-3

某公司準(zhǔn)備投產(chǎn)三種新產(chǎn)品，現(xiàn)在的重點是確定三種新產(chǎn)品的生產(chǎn)計劃，但最好能實現(xiàn)管理層的三個目標(biāo)：目標(biāo)1：獲得較高利潤，希望總利潤不低于125萬元（希望

）。據(jù)估算，產(chǎn)品1、產(chǎn)品2、產(chǎn)品3的單位利潤分別為12元、9元、15元。目標(biāo)2：保持現(xiàn)有的40名工人（希望＝）。據(jù)推算，每生產(chǎn)1萬件產(chǎn)品1、產(chǎn)品2和產(chǎn)品3分別需要5名、3名和4名工人。目標(biāo)3：投資資金限制，希望總投資額不超過55萬元（希望

）。據(jù)測算，生產(chǎn)1件產(chǎn)品1、產(chǎn)品2和產(chǎn)品3分別需要投入5元、7元和8元。8.3加權(quán)目標(biāo)規(guī)劃例8-3（續(xù)）但是，公司管理層意識到要同時實現(xiàn)三個目標(biāo)是不太現(xiàn)實的，因此，他們對三個目標(biāo)的相對重要性做出了評價。三個目標(biāo)都很重要，但在重要程度上還是有些細(xì)小的差別，其重要性順序為：目標(biāo)1、目標(biāo)2的前半部分（避免工人下崗）、目標(biāo)3、目標(biāo)2的后半部分（避免增加工人）。另外，他們?yōu)槊總€目標(biāo)分配了表示偏離目標(biāo)嚴(yán)重程度的罰數(shù)權(quán)重，如表8-3所示。試制訂滿意的投產(chǎn)計劃。目標(biāo)因素偏離目標(biāo)的罰數(shù)權(quán)重（偏離系數(shù)）1總利潤5（低于目標(biāo)的每萬元）2工人4（低于目標(biāo)的每個人）2（超過目標(biāo)的每個人）3投資資金3（超過目標(biāo)的每萬元）8.3加權(quán)目標(biāo)規(guī)劃例8-3的加權(quán)目標(biāo)規(guī)劃數(shù)學(xué)模型8.3加權(quán)目標(biāo)規(guī)劃例8-3加權(quán)目標(biāo)規(guī)劃的電子表格模型8.3加權(quán)目標(biāo)規(guī)劃可以利用優(yōu)先目標(biāo)規(guī)劃對例8-3重新規(guī)劃求解，假設(shè)目標(biāo)優(yōu)先級順序為目標(biāo)1、目標(biāo)2、目標(biāo)3。例8-3優(yōu)先目標(biāo)規(guī)劃最后一步的電子表格模型：8.3.2加