《運(yùn)籌學(xué)（第3版）》 課件 第8章 線(xiàn)性目標(biāo)規(guī)劃

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

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

在工廠(chǎng)三個(gè)車(chē)間的工時(shí)不能超計(jì)劃使用的前提下，考慮上述三個(gè)目標(biāo)，應(yīng)如何安排生產(chǎn)，才能使這些目標(biāo)依次實(shí)現(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．絕對(duì)約束和目標(biāo)約束3．優(yōu)先因子（優(yōu)先級(jí)）與權(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é)模型對(duì)于例8-1，分別賦予三個(gè)目標(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)決策問(wèn)題中，決策者往往根據(jù)自己對(duì)目標(biāo)的重視程度，賦予每個(gè)目標(biāo)一定的優(yōu)先級(jí)，從而將所有目標(biāo)排序：優(yōu)先目標(biāo)規(guī)劃就是按照目標(biāo)的先后順序，逐一滿(mǎn)足優(yōu)先級(jí)較高的目標(biāo)，最終得到一個(gè)滿(mǎn)意解。假如所有目標(biāo)都得到滿(mǎn)足，滿(mǎn)意解就是最優(yōu)解。

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

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

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

某大學(xué)規(guī)定，運(yùn)籌學(xué)專(zhuān)業(yè)的學(xué)生畢業(yè)時(shí)必須至少學(xué)習(xí)過(guò)2門(mén)數(shù)學(xué)類(lèi)課程、3門(mén)運(yùn)籌學(xué)類(lèi)課程和2門(mén)計(jì)算機(jī)類(lèi)課程。這些課程的編號(hào)、名稱(chēng)、學(xué)分、所屬類(lèi)別和先修課要求如表8-5所示。（1）畢業(yè)時(shí)學(xué)生最少可以學(xué)習(xí)這些課程中的哪些課程？請(qǐng)寫(xiě)出一般的0-1規(guī)劃模型并求解。編號(hào)課程名稱(chēng)學(xué)分所屬類(lèi)別先修課要求1微積分5數(shù)學(xué)

2線(xiàn)性代數(shù)4數(shù)學(xué)

3最優(yōu)化方法4數(shù)學(xué)；運(yùn)籌學(xué)微積分；線(xiàn)性代數(shù)4數(shù)據(jù)結(jié)構(gòu)3數(shù)學(xué)；計(jì)算機(jī)計(jì)算機(jī)編程5應(yīng)用統(tǒng)計(jì)4數(shù)學(xué)；運(yùn)籌學(xué)微積分；線(xiàn)性代數(shù)6計(jì)算機(jī)模擬3運(yùn)籌學(xué)；計(jì)算機(jī)計(jì)算機(jī)編程7計(jì)算機(jī)編程2計(jì)算機(jī)

8預(yù)測(cè)理論2運(yùn)籌學(xué)應(yīng)用統(tǒng)計(jì)9數(shù)學(xué)實(shí)驗(yàn)3運(yùn)籌學(xué)；計(jì)算機(jī)微積分；線(xiàn)性代數(shù)（2）如果某個(gè)學(xué)生既希望選修的課程數(shù)少，又希望所獲得的學(xué)分多，他可以選修哪些課程？請(qǐng)寫(xiě)出加權(quán)目標(biāo)規(guī)劃模型并求解。假設(shè)兩個(gè)目標(biāo)及偏離目標(biāo)嚴(yán)重性的罰數(shù)權(quán)重如下：①最多選修6門(mén)課程，多選修1門(mén)課程罰7個(gè)單位；②最少獲得26個(gè)學(xué)分，少修1個(gè)學(xué)分罰3個(gè)單位。8.3.2加權(quán)目標(biāo)規(guī)劃的應(yīng)用舉例【解】例8-4問(wèn)題（1）的0-1規(guī)劃模型和電子表格模型8.3.2加權(quán)目標(biāo)規(guī)劃的應(yīng)用舉例【解】例8-4問(wèn)題（2）的加權(quán)目標(biāo)規(guī)劃模型8.3.2加權(quán)目標(biāo)規(guī)劃的應(yīng)用舉例【解】例8-4問(wèn)題（2）的電子表格模型本章上機(jī)實(shí)驗(yàn)1