目標(biāo)規(guī)劃培訓(xùn)課件VIP

1、1 了解目標(biāo)規(guī)劃與線性規(guī)劃的異同了解目標(biāo)規(guī)劃與線性規(guī)劃的異同 理解目標(biāo)約束中的正負(fù)偏差變量理解目標(biāo)約束中的正負(fù)偏差變量 思考目標(biāo)約束與系統(tǒng)約束的差異思考目標(biāo)約束與系統(tǒng)約束的差異 理解目標(biāo)的優(yōu)先級(jí)和目標(biāo)權(quán)系數(shù)理解目標(biāo)的優(yōu)先級(jí)和目標(biāo)權(quán)系數(shù) 了解目標(biāo)規(guī)劃圖解法和單純形法了解目標(biāo)規(guī)劃圖解法和單純形法本章內(nèi)容重點(diǎn)本章內(nèi)容重點(diǎn)目標(biāo)規(guī)劃模型目標(biāo)規(guī)劃模型目標(biāo)規(guī)劃的幾何意義目標(biāo)規(guī)劃的幾何意義目標(biāo)規(guī)劃的單純形方法目標(biāo)規(guī)劃的單純形方法線性規(guī)劃的局限性線性規(guī)劃的局限性線性規(guī)劃只研究在滿足一定條件下，單一目標(biāo)函數(shù)取線性規(guī)劃只研究在滿足一定條件下，單一目標(biāo)函數(shù)取得最優(yōu)解，而在企業(yè)管理中，經(jīng)常遇到多目標(biāo)決策問得最優(yōu)解，而在

2、企業(yè)管理中，經(jīng)常遇到多目標(biāo)決策問題，如擬訂生產(chǎn)計(jì)劃時(shí)，不僅考慮總產(chǎn)值，同時(shí)要考題，如擬訂生產(chǎn)計(jì)劃時(shí)，不僅考慮總產(chǎn)值，同時(shí)要考慮利潤，產(chǎn)品質(zhì)量和設(shè)備利用率等。這些指標(biāo)之間的慮利潤，產(chǎn)品質(zhì)量和設(shè)備利用率等。這些指標(biāo)之間的重要程度重要程度(即優(yōu)先順序即優(yōu)先順序)也不相同，有些目標(biāo)之間往往也不相同，有些目標(biāo)之間往往相互發(fā)生矛盾。相互發(fā)生矛盾。線性規(guī)劃致力于某個(gè)目標(biāo)函數(shù)的最優(yōu)解，這個(gè)最優(yōu)解線性規(guī)劃致力于某個(gè)目標(biāo)函數(shù)的最優(yōu)解，這個(gè)最優(yōu)解若是超過了實(shí)際的需要，很可能是以過分地消耗了約若是超過了實(shí)際的需要，很可能是以過分地消耗了約束條件中的某些資源作為代價(jià)。束條件中的某些資源作為代價(jià)。線性規(guī)劃把各個(gè)約束條件的

3、重要性都不分主次地等同看待，線性規(guī)劃把各個(gè)約束條件的重要性都不分主次地等同看待，這也不符合實(shí)際情況。這也不符合實(shí)際情況。求解線性規(guī)劃問題，首先要求約束條件必須相容，如果約束求解線性規(guī)劃問題，首先要求約束條件必須相容，如果約束條件中，由于人力，設(shè)備等資源條件的限制，使約束條件之條件中，由于人力，設(shè)備等資源條件的限制，使約束條件之間出現(xiàn)了矛盾，就得不到問題的可行解，但生產(chǎn)還得繼續(xù)進(jìn)間出現(xiàn)了矛盾，就得不到問題的可行解，但生產(chǎn)還得繼續(xù)進(jìn)行，這將給人們進(jìn)一步應(yīng)用線性規(guī)劃方法帶來困難。行，這將給人們進(jìn)一步應(yīng)用線性規(guī)劃方法帶來困難。為了彌補(bǔ)線性規(guī)劃問題的局限性，解決有限資源和計(jì)劃指標(biāo)為了彌補(bǔ)線性規(guī)劃問題的局

4、限性，解決有限資源和計(jì)劃指標(biāo)之間的矛盾，在線性規(guī)劃基礎(chǔ)上，建立目標(biāo)規(guī)劃方法，從而之間的矛盾，在線性規(guī)劃基礎(chǔ)上，建立目標(biāo)規(guī)劃方法，從而使一些線性規(guī)劃無法解決的問題得到滿意的解答。使一些線性規(guī)劃無法解決的問題得到滿意的解答。5第一節(jié)第一節(jié) 多目標(biāo)規(guī)劃問題多目標(biāo)規(guī)劃問題一、線性規(guī)劃的局限性一、線性規(guī)劃的局限性線性規(guī)劃的局限性線性規(guī)劃的局限性 只能解決一組線性約束條件下，某一目標(biāo)而且只能是一個(gè)目標(biāo)只能解決一組線性約束條件下，某一目標(biāo)而且只能是一個(gè)目標(biāo)的最大或最小值的問題的最大或最小值的問題實(shí)際決策中，衡量方案優(yōu)劣考慮多個(gè)目標(biāo)實(shí)際決策中，衡量方案優(yōu)劣考慮多個(gè)目標(biāo) 生產(chǎn)計(jì)劃決策，通?？紤]產(chǎn)值、利潤、滿足市

5、場需求等生產(chǎn)計(jì)劃決策，通?？紤]產(chǎn)值、利潤、滿足市場需求等 生產(chǎn)布局決策，考慮運(yùn)費(fèi)、投資、供應(yīng)、市場、污染等生產(chǎn)布局決策，考慮運(yùn)費(fèi)、投資、供應(yīng)、市場、污染等 這些目標(biāo)中，有主要的，也有次要的；有最大的，有最小的；這些目標(biāo)中，有主要的，也有次要的；有最大的，有最小的；有定量的，有定性的；有互相補(bǔ)充的，有互相對(duì)立的，有定量的，有定性的；有互相補(bǔ)充的，有互相對(duì)立的，LP則則無能為力無能為力目標(biāo)規(guī)劃（目標(biāo)規(guī)劃（Goal Programming） 多目標(biāo)線性規(guī)劃多目標(biāo)線性規(guī)劃 含有多個(gè)優(yōu)化目標(biāo)的線性規(guī)劃含有多個(gè)優(yōu)化目標(biāo)的線性規(guī)劃線性規(guī)劃只討論一個(gè)線性目標(biāo)函數(shù)在一組線性約束條線性規(guī)劃只討論一個(gè)線性目標(biāo)函數(shù)在

6、一組線性約束條件下的極值問題；而目標(biāo)規(guī)劃是多個(gè)目標(biāo)決策，可求件下的極值問題；而目標(biāo)規(guī)劃是多個(gè)目標(biāo)決策，可求得更切合實(shí)際的解。得更切合實(shí)際的解。線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個(gè)滿意解。線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個(gè)滿意解。線性規(guī)劃中的約束條件是同等重要的，是硬約束；而線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目標(biāo)規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。目標(biāo)規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。線性規(guī)劃的最優(yōu)解是絕對(duì)意義下的最優(yōu)，但需花去大線性規(guī)劃的最優(yōu)解是絕對(duì)意義下的最優(yōu)，但需花去大量的人力、物力、財(cái)力才能得到；實(shí)際過程中，只要量的人力、物力、財(cái)力才能得到；實(shí)際過程中，只要求得滿

7、意解，就能滿足需要求得滿意解，就能滿足需要(或更能滿足需要或更能滿足需要)。例例5-1：某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)：某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計(jì)劃，使獲得的利品，已知資料如表所示。試制定生產(chǎn)計(jì)劃，使獲得的利潤最大？同時(shí)，根據(jù)市場預(yù)測，甲的銷路不是太好，應(yīng)潤最大？同時(shí)，根據(jù)市場預(yù)測，甲的銷路不是太好，應(yīng)盡可能少生產(chǎn)；乙的銷路較好，可以擴(kuò)大生產(chǎn)。試建立盡可能少生產(chǎn)；乙的銷路較好，可以擴(kuò)大生產(chǎn)。試建立此問題的數(shù)學(xué)模型。此問題的數(shù)學(xué)模型。12070單件利潤單件利潤3000103設(shè)備臺(tái)時(shí)設(shè)備臺(tái)時(shí)200054煤炭煤炭360049鋼材鋼材資源限

8、制資源限制乙乙甲甲單位單位 產(chǎn)品產(chǎn)品資源資源 消耗消耗設(shè)：甲產(chǎn)品設(shè)：甲產(chǎn)品x1 ，乙產(chǎn)品，乙產(chǎn)品 x2 根據(jù)市場預(yù)測：根據(jù)市場預(yù)測：maxZ=70 x1 + 120 x2 9 x1 +4 x2 3600 4 x1 +5 x2 2000 3 x1 +10 x2 3000 x1 ， x2 0maxZ1=70 x1 + 120 x2 minZ2= x1 maxZ3= x2 9 x1 +4 x2 3600 4 x1 +5 x2 2000 3 x1 +10 x2 3000 x1 ， x2 0這些目標(biāo)之間這些目標(biāo)之間相互矛盾，一相互矛盾，一般的線性規(guī)劃般的線性規(guī)劃方法不能求解方法不能求解 9第一節(jié)第一節(jié)

9、多目標(biāo)規(guī)劃問題多目標(biāo)規(guī)劃問題二、多目標(biāo)規(guī)劃的提出二、多目標(biāo)規(guī)劃的提出111 11221221 122221 122ln11 11221121 1222221 122max(min) max(min) max(min) ( , )( , )s.t. nnnnlllnnnnnmmGc xc xc xGc xc xc xGc xc xc xa xa xa xba xa xa xba xax 12( , ),0mnnmnaxbx xx 多目標(biāo)線性規(guī)劃模型的原始一般形式如下：多目標(biāo)線性規(guī)劃模型的原始一般形式如下： n n個(gè)決策變量，個(gè)決策變量，m m個(gè)約束條件，個(gè)約束條件，L L個(gè)目標(biāo)函數(shù)。個(gè)目標(biāo)函數(shù)。

10、當(dāng)當(dāng)L L=1=1時(shí)，即為我們熟悉的單目標(biāo)線性規(guī)劃模型。時(shí)，即為我們熟悉的單目標(biāo)線性規(guī)劃模型。OR:SM10二、多目標(biāo)規(guī)劃的提出二、多目標(biāo)規(guī)劃的提出OR:SM11OR:SM12OR:SM13OR:SM14上述上述OR:SM15OR:SM16OR:SM17OR:SM18OR:SM19OR:SM20OR:SM21OR:SM22第一節(jié)第一節(jié) 多目標(biāo)規(guī)劃問題多目標(biāo)規(guī)劃問題三、多目標(biāo)的處理方法三、多目標(biāo)的處理方法 加權(quán)系數(shù)法：加權(quán)系數(shù)法： 為每一目標(biāo)賦一權(quán)數(shù)，把多目標(biāo)轉(zhuǎn)化成單目標(biāo)。 但權(quán)系數(shù)難以科學(xué)確定。 優(yōu)先等級(jí)法：優(yōu)先等級(jí)法： 各目標(biāo)按重要性歸不同優(yōu)先級(jí)而化為單目標(biāo)。 有效解法：有效解法： 尋求能照

11、顧到各目標(biāo)而使決策者感到滿意的解。 但可行域大時(shí)難以列出所有有效解的組合。 目標(biāo)規(guī)劃法：目標(biāo)規(guī)劃法： 對(duì)每一個(gè)目標(biāo)函數(shù)引入正的或負(fù)的偏差變量； 引入目標(biāo)的優(yōu)先等級(jí)和加權(quán)系數(shù)。OR:SM23第二節(jié)第二節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的數(shù)學(xué)模型1.目標(biāo)期望值目標(biāo)期望值 每一個(gè)目標(biāo)希望達(dá)到的每一個(gè)目標(biāo)希望達(dá)到的期望值期望值(或目標(biāo)值、理想值或目標(biāo)值、理想值)。 根據(jù)歷史資料、市場需求或上級(jí)部門的布置等來確定。根據(jù)歷史資料、市場需求或上級(jí)部門的布置等來確定。一、一、目標(biāo)值和偏差變量目標(biāo)值和偏差變量目標(biāo)規(guī)劃通過引入目標(biāo)值和偏差變量，可目標(biāo)規(guī)劃通過引入目標(biāo)值和偏差變量，可以將目標(biāo)函數(shù)轉(zhuǎn)化為目標(biāo)約束。以將目標(biāo)

12、函數(shù)轉(zhuǎn)化為目標(biāo)約束。實(shí)現(xiàn)值或決策值：實(shí)現(xiàn)值或決策值：是指當(dāng)決策變量是指當(dāng)決策變量xj選定以后，選定以后，目標(biāo)函數(shù)的對(duì)應(yīng)值。目標(biāo)函數(shù)的對(duì)應(yīng)值。24第二節(jié)第二節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的數(shù)學(xué)模型2 2、偏差變量、偏差變量 正偏差變量正偏差變量dk+ 表示第k個(gè)目標(biāo)超過期望值的數(shù)值； 負(fù)偏差變量負(fù)偏差變量dk- 表示第k個(gè)目標(biāo)未達(dá)到期望值的數(shù)值。 同一目標(biāo)的dk+ 和dk- 中至少有一個(gè)必須為零。偏差變量偏差變量(事先無法確定的未知數(shù)事先無法確定的未知數(shù))：是指實(shí)現(xiàn)值和目標(biāo)值：是指實(shí)現(xiàn)值和目標(biāo)值之間的差異之間的差異,記為記為 d 。偏差可能存在正的或負(fù)的。正偏差變量正偏差變量:表示實(shí)現(xiàn)值超過目標(biāo)

13、值的部分，記為表示實(shí)現(xiàn)值超過目標(biāo)值的部分，記為d。負(fù)偏差變量負(fù)偏差變量:表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分，記為表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分，記為d。在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值，故有到目標(biāo)值，故有dd0,并規(guī)定并規(guī)定d0, d0當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：d0, d0當(dāng)未完成規(guī)定的指標(biāo)則表示：當(dāng)未完成規(guī)定的指標(biāo)則表示： d0, d0當(dāng)恰好完成指標(biāo)時(shí)則表示：當(dāng)恰好完成指標(biāo)時(shí)則表示： d0, d0二二.目標(biāo)約束和絕對(duì)約束目標(biāo)約束和絕對(duì)約束引入了目標(biāo)值和正、負(fù)偏差變量后，就對(duì)某一問題有了引入了目標(biāo)

14、值和正、負(fù)偏差變量后，就對(duì)某一問題有了新的限制，既目標(biāo)約束。新的限制，既目標(biāo)約束。目標(biāo)約束即可對(duì)原目標(biāo)函數(shù)起作用，也可對(duì)原約束起作目標(biāo)約束即可對(duì)原目標(biāo)函數(shù)起作用，也可對(duì)原約束起作用。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。用。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。絕對(duì)約束絕對(duì)約束(系統(tǒng)約束系統(tǒng)約束)是指必須嚴(yán)格滿足的等式或不等式是指必須嚴(yán)格滿足的等式或不等式約束。如線性規(guī)劃中的所有約束條件都是絕對(duì)約束，否約束。如線性規(guī)劃中的所有約束條件都是絕對(duì)約束，否則無可行解。所以，絕對(duì)約束是硬約束。則無可行解。所以，絕對(duì)約束是硬約束。例如：在例一中，規(guī)定例如：在例一中，規(guī)定Z1的目標(biāo)值為的目標(biāo)值為 5000

15、0,正、負(fù)偏差正、負(fù)偏差為為d、d ,則目標(biāo)函數(shù)可以轉(zhuǎn)換為目標(biāo)約束，既則目標(biāo)函數(shù)可以轉(zhuǎn)換為目標(biāo)約束，既:50000120701121 - - - -ddxx若規(guī)定若規(guī)定3600的鋼材必須用完，原式的鋼材必須用完，原式9x1 +4x2 3600變?yōu)樽優(yōu)?600494421 - - - -ddxx28第二節(jié)第二節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的數(shù)學(xué)模型-njkkjkjEddxc1* 引入正負(fù)偏差變量，對(duì)各個(gè)目標(biāo)建立目標(biāo)約束(軟約束)1.目標(biāo)約束表示目標(biāo)約束表示29例：例：甲乙產(chǎn)品的最優(yōu)生產(chǎn)計(jì)劃。甲乙產(chǎn)品的最優(yōu)生產(chǎn)計(jì)劃。產(chǎn)品產(chǎn)品資源資源甲甲乙乙現(xiàn)有資源現(xiàn)有資源 設(shè)備設(shè)備A2016設(shè)備設(shè)備B0210設(shè)備

16、設(shè)備C3432單位利潤單位利潤 35根據(jù)市場需求根據(jù)市場需求/合同規(guī)定：合同規(guī)定： 希望盡量擴(kuò)大甲產(chǎn)品希望盡量擴(kuò)大甲產(chǎn)品 減少乙產(chǎn)品產(chǎn)量。減少乙產(chǎn)品產(chǎn)量。又增加二個(gè)目標(biāo)：又增加二個(gè)目標(biāo)： maxZ1=3x1+5x2 maxZ2=x1minZ3=x2 2x1 16 2x2 10 3x1+4x2 32 x1，x2 0 30第二節(jié)第二節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的數(shù)學(xué)模型 要求：要求：l目標(biāo)一是利潤最大，擬定利潤目標(biāo)是目標(biāo)一是利潤最大，擬定利潤目標(biāo)是30；l目標(biāo)二是減少乙產(chǎn)品產(chǎn)量但希望不低于目標(biāo)二是減少乙產(chǎn)品產(chǎn)量但希望不低于4件；件；l目標(biāo)三是目標(biāo)三是甲產(chǎn)品產(chǎn)量希望不少于甲產(chǎn)品產(chǎn)量希望不少于6件件

17、 ；l對(duì)各目標(biāo)引入正、負(fù)偏差變量：對(duì)各目標(biāo)引入正、負(fù)偏差變量： 3x1+5x2 +d1- d1+ = 30 x2 +d2- - d2+ =4 x1 +d3 -d3+ = 6三三.優(yōu)先因子優(yōu)先因子(優(yōu)先等級(jí)優(yōu)先等級(jí))與優(yōu)先權(quán)系數(shù)與優(yōu)先權(quán)系數(shù)目標(biāo)等級(jí)化目標(biāo)等級(jí)化:將目標(biāo)按重要性程度不同依次分成一級(jí)目將目標(biāo)按重要性程度不同依次分成一級(jí)目標(biāo)、二級(jí)目標(biāo)標(biāo)、二級(jí)目標(biāo).。最次要的目標(biāo)放在次要的等級(jí)中。最次要的目標(biāo)放在次要的等級(jí)中。(1)對(duì)同一目標(biāo)而言，若有幾個(gè)決策方案都能使其達(dá)到，對(duì)同一目標(biāo)而言，若有幾個(gè)決策方案都能使其達(dá)到，可認(rèn)為這些方案就這個(gè)目標(biāo)而言都是最優(yōu)方案；若達(dá)可認(rèn)為這些方案就這個(gè)目標(biāo)而言都是最優(yōu)

18、方案；若達(dá)不到，則與目標(biāo)差距越小的越好。不到，則與目標(biāo)差距越小的越好。(2)不同級(jí)別的目標(biāo)的重要性是不可比的。即較高級(jí)別不同級(jí)別的目標(biāo)的重要性是不可比的。即較高級(jí)別的目標(biāo)沒有達(dá)到的損失，任何較低級(jí)別目標(biāo)上的收獲的目標(biāo)沒有達(dá)到的損失，任何較低級(jí)別目標(biāo)上的收獲不可彌補(bǔ)。故在判斷最優(yōu)方案時(shí)，首先從較高級(jí)別的不可彌補(bǔ)。故在判斷最優(yōu)方案時(shí)，首先從較高級(jí)別的目標(biāo)達(dá)到的程度來決策，然后再其次級(jí)目標(biāo)的判斷。目標(biāo)達(dá)到的程度來決策，然后再其次級(jí)目標(biāo)的判斷。(3)同一級(jí)別的目標(biāo)可以是多個(gè)。各自之間的重要程度同一級(jí)別的目標(biāo)可以是多個(gè)。各自之間的重要程度可用數(shù)量（權(quán)數(shù)）來描述。因此，同一級(jí)別的目標(biāo)的可用數(shù)量（權(quán)數(shù)）來描

19、述。因此，同一級(jí)別的目標(biāo)的其中一個(gè)的損失，可有其余目標(biāo)的適當(dāng)收獲來彌補(bǔ)。其中一個(gè)的損失，可有其余目標(biāo)的適當(dāng)收獲來彌補(bǔ)。三三.優(yōu)先因子優(yōu)先因子(優(yōu)先等級(jí)優(yōu)先等級(jí))與優(yōu)先權(quán)系數(shù)與優(yōu)先權(quán)系數(shù)優(yōu)先因子優(yōu)先因子Pk是將決策目標(biāo)按其重要程度排序并表示出是將決策目標(biāo)按其重要程度排序并表示出來。來。P1P2PkPk+1PK ，k=1,2,K。表。表示示Pk比比Pk+1有更大的優(yōu)先權(quán)。即首先保證有更大的優(yōu)先權(quán)。即首先保證P1級(jí)目標(biāo)的實(shí)級(jí)目標(biāo)的實(shí)現(xiàn)，這時(shí)可不考慮次級(jí)目標(biāo)；而現(xiàn)，這時(shí)可不考慮次級(jí)目標(biāo)；而P2級(jí)目標(biāo)是在實(shí)現(xiàn)級(jí)目標(biāo)是在實(shí)現(xiàn)P1級(jí)級(jí)目標(biāo)的基礎(chǔ)上考慮的；依此類推。目標(biāo)的基礎(chǔ)上考慮的；依此類推。若要區(qū)別具有相

20、同優(yōu)先因子的兩個(gè)目標(biāo)的差別，這時(shí)若要區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，這時(shí)可分別賦予它們不同的權(quán)系數(shù)可分別賦予它們不同的權(quán)系數(shù)j,這些都由決策者按具這些都由決策者按具體情況而定。體情況而定。 四四.達(dá)成函數(shù)達(dá)成函數(shù)(即目標(biāo)規(guī)劃中的目標(biāo)函數(shù)即目標(biāo)規(guī)劃中的目標(biāo)函數(shù))目標(biāo)規(guī)劃的目標(biāo)函數(shù)目標(biāo)規(guī)劃的目標(biāo)函數(shù)(準(zhǔn)則函數(shù)準(zhǔn)則函數(shù))是按各目標(biāo)約束的正、負(fù)是按各目標(biāo)約束的正、負(fù)偏差變量和賦予相應(yīng)的優(yōu)先因子及權(quán)系數(shù)而構(gòu)造的。當(dāng)每偏差變量和賦予相應(yīng)的優(yōu)先因子及權(quán)系數(shù)而構(gòu)造的。當(dāng)每一目標(biāo)值確定后，決策者的要求是盡可能縮小偏離目標(biāo)值。一目標(biāo)值確定后，決策者的要求是盡可能縮小偏離目標(biāo)值。因此目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是因

21、此目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是minZ = f(d、d)。一般說來，有以下三種情況，但只能出現(xiàn)其中之一：一般說來，有以下三種情況，但只能出現(xiàn)其中之一：(1)要求恰好達(dá)到規(guī)定的目標(biāo)值，即正、負(fù)偏差變量要盡要求恰好達(dá)到規(guī)定的目標(biāo)值，即正、負(fù)偏差變量要盡可能小，則可能小，則minZ = f(d d)。(2)要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，也就是正要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，也就是正偏差變量盡可能小，則偏差變量盡可能小，則minZ = f(d)。(3)要求超過目標(biāo)值，即超過量不限，但不低于目標(biāo)值，要求超過目標(biāo)值，即超過量不限，但不低于目標(biāo)值，也就是負(fù)偏差變量盡可能小，則也就是負(fù)偏差變量盡可

22、能小，則minZ = f(d)。對(duì)由絕對(duì)約束轉(zhuǎn)化而來的目標(biāo)函數(shù)，也照上述處理即可。對(duì)由絕對(duì)約束轉(zhuǎn)化而來的目標(biāo)函數(shù)，也照上述處理即可。34例：例：甲乙產(chǎn)品的最優(yōu)生產(chǎn)計(jì)劃。甲乙產(chǎn)品的最優(yōu)生產(chǎn)計(jì)劃。產(chǎn)品產(chǎn)品資源資源甲甲乙乙現(xiàn)有資源現(xiàn)有資源 設(shè)備設(shè)備A2016設(shè)備設(shè)備B0210設(shè)備設(shè)備C3432單位利潤單位利潤 35根據(jù)市場需求根據(jù)市場需求/合同規(guī)定：合同規(guī)定： 希望盡量擴(kuò)大甲產(chǎn)品希望盡量擴(kuò)大甲產(chǎn)品 減少乙產(chǎn)品產(chǎn)量。減少乙產(chǎn)品產(chǎn)量。又增加二個(gè)目標(biāo)：又增加二個(gè)目標(biāo)： maxZ1=3x1+5x2 maxZ2=x1minZ3=x2 2x1 16 2x2 10 3x1+4x2 32 x1，x2 0 35第二節(jié)

23、第二節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的數(shù)學(xué)模型例如例如 P1 級(jí)目標(biāo)實(shí)現(xiàn)利潤至少30元； P2級(jí)目標(biāo)是甲乙產(chǎn)品的產(chǎn)量 假設(shè)：乙產(chǎn)品產(chǎn)量不少于4件比甲產(chǎn)品產(chǎn)量不少于6件更重要，取其權(quán)重為2 minG= P1 d1- + P2(2d2- + d3- ) 3x1+5x2 +d1- d1+ = 30 x2 +d2- - d2+ = 4 x1 + d3- - d3+ = 6 x1 , x2 ,dk- , dk+ 0(k=1,2,3)五五.多目標(biāo)規(guī)劃的解多目標(biāo)規(guī)劃的解(1)若多目標(biāo)規(guī)劃問題的解能使所有的目標(biāo)都達(dá)到，若多目標(biāo)規(guī)劃問題的解能使所有的目標(biāo)都達(dá)到，就稱該解為多目標(biāo)規(guī)劃的最優(yōu)解；就稱該解為多目標(biāo)規(guī)劃的

24、最優(yōu)解；(2)若解只能滿足部分目標(biāo)，就稱該解為多目標(biāo)規(guī)劃若解只能滿足部分目標(biāo)，就稱該解為多目標(biāo)規(guī)劃的次優(yōu)解；的次優(yōu)解；(3)若找不到滿足任何一個(gè)目標(biāo)的解，就稱該問題為若找不到滿足任何一個(gè)目標(biāo)的解，就稱該問題為無解。無解。(4)前面的目標(biāo)可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，而后面的前面的目標(biāo)可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，有些可能就目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，有些可能就不能實(shí)現(xiàn)，就稱該解為多目標(biāo)規(guī)劃的不能實(shí)現(xiàn)，就稱該解為多目標(biāo)規(guī)劃的滿意解滿意解(具有層具有層次意義的解次意義的解)例例5-2:某工廠生產(chǎn)某工廠生產(chǎn)A，B兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下。實(shí)現(xiàn)目兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下

25、。實(shí)現(xiàn)目標(biāo)利潤為標(biāo)利潤為140萬元的最優(yōu)生產(chǎn)方案萬元的最優(yōu)生產(chǎn)方案AB可用量可用量設(shè)備設(shè)備(臺(tái)時(shí)臺(tái)時(shí))4260原材料原材料(KG)2448利潤利潤(萬元萬元)86從決策者的角度看，他希望超過利潤目標(biāo)值，若達(dá)不從決策者的角度看，他希望超過利潤目標(biāo)值，若達(dá)不到，也希望盡可能接近，即負(fù)偏差最小到，也希望盡可能接近，即負(fù)偏差最小 - - 0, 0,21ddxx 484221xx 602421xx - - - - 1406821ddxx st - -mindZ例例5-3：若上例中假設(shè)決策者根據(jù)市場預(yù)測，產(chǎn)品：若上例中假設(shè)決策者根據(jù)市場預(yù)測，產(chǎn)品A的銷的銷售量有下降的趨勢，故考慮實(shí)現(xiàn)下列兩個(gè)目標(biāo)：售量有下

26、降的趨勢，故考慮實(shí)現(xiàn)下列兩個(gè)目標(biāo)：(1)實(shí)現(xiàn)利潤目標(biāo)實(shí)現(xiàn)利潤目標(biāo)122萬元萬元(2)產(chǎn)品產(chǎn)品A的產(chǎn)量不多于的產(chǎn)量不多于10分析分析:兩個(gè)目標(biāo)級(jí)別相等，即兩個(gè)目標(biāo)的重要程度一樣，兩個(gè)目標(biāo)級(jí)別相等，即兩個(gè)目標(biāo)的重要程度一樣，不存在誰優(yōu)先的問題不存在誰優(yōu)先的問題設(shè)設(shè)d，d-分別為超過目標(biāo)值的部分，以及未完成目分別為超過目標(biāo)值的部分，以及未完成目標(biāo)值的部分，于是兩個(gè)目標(biāo)可以等價(jià)表示為：標(biāo)值的部分，于是兩個(gè)目標(biāo)可以等價(jià)表示為：10122681211121 - - - - - - - -ddxddxxx1=10，x2=7，d10，d+20，利潤為，利潤為122，兩個(gè)目標(biāo)均，兩個(gè)目標(biāo)均已經(jīng)實(shí)現(xiàn)已經(jīng)實(shí)現(xiàn) -

27、- - - - - - - - - - - - -0,4842602410122682211212121221112121ddddxxxxxxddxddxxstddMinZ對(duì)于多個(gè)目標(biāo)，如果有一定的優(yōu)先順序，即第一位重對(duì)于多個(gè)目標(biāo)，如果有一定的優(yōu)先順序，即第一位重要的目標(biāo)，其優(yōu)先因子為要的目標(biāo)，其優(yōu)先因子為P1，第二位重要的目標(biāo)，其，第二位重要的目標(biāo)，其優(yōu)先因子為優(yōu)先因子為P2，并規(guī)定，并規(guī)定P1P2優(yōu)先保證優(yōu)先保證P1級(jí)目標(biāo)的實(shí)現(xiàn)，此時(shí)不考慮次級(jí)目標(biāo)；次級(jí)目標(biāo)的實(shí)現(xiàn)，此時(shí)不考慮次級(jí)目標(biāo)；次級(jí)目標(biāo)級(jí)目標(biāo)P2在實(shí)現(xiàn)了在實(shí)現(xiàn)了P1級(jí)目標(biāo)的基礎(chǔ)上再予以考慮。如級(jí)目標(biāo)的基礎(chǔ)上再予以考慮。如果無法實(shí)現(xiàn)果

28、無法實(shí)現(xiàn)P1目標(biāo)，則不考慮目標(biāo)，則不考慮P2目標(biāo)能否取得最優(yōu)目標(biāo)能否取得最優(yōu)若有若有k個(gè)不同優(yōu)先順序的目標(biāo)，則有個(gè)不同優(yōu)先順序的目標(biāo)，則有P1P2Pk將權(quán)重與偏差相乘構(gòu)成目標(biāo)函數(shù)，這樣，權(quán)重越大，將權(quán)重與偏差相乘構(gòu)成目標(biāo)函數(shù)，這樣，權(quán)重越大，越先迫使相應(yīng)的偏差等于零，這樣可保證優(yōu)先級(jí)高的越先迫使相應(yīng)的偏差等于零，這樣可保證優(yōu)先級(jí)高的目標(biāo)首先實(shí)現(xiàn)。目標(biāo)首先實(shí)現(xiàn)。例例5-4：若上例中決策者擬訂下列經(jīng)營目標(biāo)，并確定了目：若上例中決策者擬訂下列經(jīng)營目標(biāo)，并確定了目標(biāo)之間的優(yōu)先順序標(biāo)之間的優(yōu)先順序P1級(jí)目標(biāo)：充分利用設(shè)備有效臺(tái)時(shí)，不加班；級(jí)目標(biāo)：充分利用設(shè)備有效臺(tái)時(shí)，不加班；P2級(jí)目標(biāo)：產(chǎn)品級(jí)目標(biāo)：產(chǎn)品

29、B的產(chǎn)量不多于的產(chǎn)量不多于4；P3級(jí)目標(biāo)：實(shí)現(xiàn)利潤值級(jí)目標(biāo)：實(shí)現(xiàn)利潤值130萬元萬元分析：題目有三個(gè)目標(biāo)層次，包含三個(gè)目標(biāo)值。分析：題目有三個(gè)目標(biāo)層次，包含三個(gè)目標(biāo)值。 第一目標(biāo)：第一目標(biāo)： P1(d1+d1-) 第二目標(biāo)：第二目標(biāo)：P2d2 第二目標(biāo)：第二目標(biāo)：P3d3 - - - - - - - - - - - - - - - - - -0,48421306846024)(2121332122211213322111iiddxxxxddxxddxddxxstdPdPddPMinZ例例5-5：某廠計(jì)劃下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，：某廠計(jì)劃下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如

30、表所示。制定生產(chǎn)計(jì)劃，滿足下列目標(biāo)：已知資料如表所示。制定生產(chǎn)計(jì)劃，滿足下列目標(biāo)： P1級(jí)目標(biāo)：完成或超額完成利潤指標(biāo)級(jí)目標(biāo)：完成或超額完成利潤指標(biāo) 50000元；元；P2級(jí)目標(biāo)：產(chǎn)品甲不超過級(jí)目標(biāo)：產(chǎn)品甲不超過 200件，產(chǎn)品乙不低于件，產(chǎn)品乙不低于 250件；件；P3級(jí)目標(biāo)：現(xiàn)有鋼材級(jí)目標(biāo)：現(xiàn)有鋼材 3600噸必須用完噸必須用完12070單件利潤單件利潤3000103設(shè)備臺(tái)時(shí)設(shè)備臺(tái)時(shí)200054煤炭煤炭360049鋼材鋼材資源限制資源限制乙乙甲甲單位單位 產(chǎn)品產(chǎn)品資源資源 消耗消耗分析：題目有三個(gè)目標(biāo)層次，包含四個(gè)目標(biāo)值。分析：題目有三個(gè)目標(biāo)層次，包含四個(gè)目標(biāo)值。 第一目標(biāo)：第一目標(biāo)： P

31、1d1- 第二目標(biāo)：有兩個(gè)要求即甲第二目標(biāo)：有兩個(gè)要求即甲d2，乙，乙d3-，但兩個(gè)具，但兩個(gè)具有相同的優(yōu)先因子，需要確定權(quán)系數(shù)。本題可用單件利有相同的優(yōu)先因子，需要確定權(quán)系數(shù)。本題可用單件利潤比作為權(quán)系數(shù)即潤比作為權(quán)系數(shù)即70:120，化簡為，化簡為7:12，P2(7d2+12d3 -) 第三目標(biāo)：第三目標(biāo)：P3(d4+d4 -) - - - - - - - - - - - - - - - - - - - - - - -0,30001032000543600492502005000012070)()127(2121214421332221112144332211iiddxxxxxxddxxd

32、dxddxddxxstddPddPdPMinZ - - - - - - - - - - - - - - - - - - - - )55(3 , 2 , 1, 0,)45(, 1, 0)35(, 1,),()25(, 1,) 15()(min1111kddnjxmibxaKkgddxcddPzkkjijnjijkkkjnjkjklkkKklkLll滿足約束條件：滿足約束條件：目標(biāo)函數(shù)目標(biāo)函數(shù)：w ww w其中其中Pl為優(yōu)先因子，為優(yōu)先因子， w w- -lk，w w lk為優(yōu)先系數(shù)為優(yōu)先系數(shù)根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約

33、束與絕對(duì)約束；值，列出目標(biāo)約束與絕對(duì)約束； 可根據(jù)決策者的需要，將某些或全部絕對(duì)約束轉(zhuǎn)化為可根據(jù)決策者的需要，將某些或全部絕對(duì)約束轉(zhuǎn)化為目標(biāo)約束。這時(shí)只需要給絕對(duì)約束加上負(fù)偏差變量和目標(biāo)約束。這時(shí)只需要給絕對(duì)約束加上負(fù)偏差變量和減去正偏差變量即可。減去正偏差變量即可。給各目標(biāo)賦予相應(yīng)的優(yōu)先因子給各目標(biāo)賦予相應(yīng)的優(yōu)先因子 Pk對(duì)同一優(yōu)先等級(jí)中的各偏差變量，若需要可按其重要對(duì)同一優(yōu)先等級(jí)中的各偏差變量，若需要可按其重要程度的不同，賦予相應(yīng)的權(quán)系數(shù)程度的不同，賦予相應(yīng)的權(quán)系數(shù) kl+和和kl- 。根據(jù)決策者的要求，構(gòu)造一個(gè)由優(yōu)先因子和權(quán)系數(shù)相根據(jù)決策者的要求，構(gòu)造一個(gè)由優(yōu)先因子和權(quán)系數(shù)相對(duì)應(yīng)的偏差變

34、量組成的，要求實(shí)現(xiàn)極小化的目標(biāo)函數(shù)，對(duì)應(yīng)的偏差變量組成的，要求實(shí)現(xiàn)極小化的目標(biāo)函數(shù)，即達(dá)成函數(shù)。即達(dá)成函數(shù)。464748線性規(guī)劃線性規(guī)劃LP目標(biāo)規(guī)劃目標(biāo)規(guī)劃GP目標(biāo)函數(shù)目標(biāo)函數(shù)min, max系數(shù)可正負(fù)系數(shù)可正負(fù)min , 偏差變量偏差變量系數(shù)系數(shù)0變量變量xi , xs , xa xi , xs , xa , d約束條件約束條件系統(tǒng)約束系統(tǒng)約束(絕對(duì)約束絕對(duì)約束)目標(biāo)約束目標(biāo)約束系統(tǒng)約束系統(tǒng)約束解解最優(yōu)最優(yōu)滿意滿意OR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SM

35、OR:SMOR:SMOR:SMOR:SM73112231211222133121212min(2)3530(1)4(2)(3)6(4)216s.t.(5)210(6)3432(7),0,0(1,2,3)llGPdPddxxddxddxddxxxxx xddl-F2x1 =162x2 =10BCx14A103x1 +4 x2 =326x20D2642EGH1d-1d2d-2d3d-3d滿意解：滿意解：x1=5, x2=4OR:SM74第三節(jié)第三節(jié) 目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的圖解法n首先，按照絕對(duì)約束畫出可行域，首先，按照絕對(duì)約束畫出可行域，n其次，不考慮正負(fù)偏差變

36、量，畫出目標(biāo)約束的邊界線，其次，不考慮正負(fù)偏差變量，畫出目標(biāo)約束的邊界線，n最后。按優(yōu)先級(jí)別和權(quán)重依次分析各級(jí)目標(biāo)。最后。按優(yōu)先級(jí)別和權(quán)重依次分析各級(jí)目標(biāo)。112231211222133121212min(2)3530(1)4(2)(3)6(4)216s.t.(5)210(6)3432(7),0,0(1,2,3)llGPdPddxxddxddxddxxxxx xddl-F2x1 =162x2 =10BCx14A103x1 +4 x2 =326x20D2642EGH1d-1d2d-2d3d-3d滿意解：滿意解：x1=5, x2=4 - - - - - - - - - - - - - - )2 .

37、 1(0, 08 2 102 5 .621210)(min21212221112122111lddxxxddxxddxxdPddPZll01 2 3 4 5 6 7 8 1 2 3 4 5 6 Ax2 x1B-1d1d2d-2dCB (0.6250 , 4.6875) C (0 , 5.2083) ， B、C 線段上的所有點(diǎn)線段上的所有點(diǎn)均是該問題的解均是該問題的解 (無窮多最優(yōu)解無窮多最優(yōu)解)。第三節(jié)第三節(jié) 目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的圖解法 - - - - - - - - - - - - - - - - - - - - - -)4 . 3 . 2 . 1(0, 010060140225001

38、230)5 . 2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll 0 x2 0(1)x11401201008060402020 40 60 80 100(2)(3)(4)-2d2d-1d1d-3d3d-4d4dABCD結(jié)論：結(jié)論：C(60 ,58.3)為所求的滿意解。為所求的滿意解。圖解法解題步驟如下：圖解法解題步驟如下：1.確定各約束條件的可行域，即將所有約束條件確定各約束條件的可行域，即將所有約束條件(包括包括目標(biāo)約束和絕對(duì)約束，暫不考慮正負(fù)偏差變量目標(biāo)約束和絕對(duì)約束，暫不考慮正負(fù)偏差變量)在坐在坐標(biāo)平面上表示出來；標(biāo)平面上表

39、示出來；2.在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向；差變量值增大的方向；3.求滿足最高優(yōu)先等級(jí)目標(biāo)的解；求滿足最高優(yōu)先等級(jí)目標(biāo)的解；4.轉(zhuǎn)到下一個(gè)優(yōu)先等級(jí)的目標(biāo)，在不破壞所有較高優(yōu)先轉(zhuǎn)到下一個(gè)優(yōu)先等級(jí)的目標(biāo)，在不破壞所有較高優(yōu)先等級(jí)目標(biāo)的前提下，求出該優(yōu)先等級(jí)目標(biāo)的解；等級(jí)目標(biāo)的前提下，求出該優(yōu)先等級(jí)目標(biāo)的解；5.重復(fù)重復(fù)4，直到所有優(yōu)先等級(jí)目標(biāo)都已審查完畢為止；，直到所有優(yōu)先等級(jí)目標(biāo)都已審查完畢為止；6.確定最優(yōu)解和滿意解。確定最優(yōu)解和滿意解。OR:SM78 目標(biāo)規(guī)劃與線性規(guī)劃的數(shù)學(xué)模型的結(jié)構(gòu)相似目標(biāo)規(guī)劃與線性規(guī)劃的數(shù)學(xué)

40、模型的結(jié)構(gòu)相似 可用前述單純形算法求解目標(biāo)規(guī)劃模型：可用前述單純形算法求解目標(biāo)規(guī)劃模型： 將優(yōu)先等級(jí)Pk視為正常數(shù)(大法 ) 正負(fù)偏差變量dk+、dk-視為松弛變量 以負(fù)偏差變量dk-為初始基變量，建立初始單純形表 檢驗(yàn)數(shù)的計(jì)算與LP單純形法相同，即j= cj - CBi Pj 最優(yōu)性判別準(zhǔn)則類似于LP的單純形算法：檢驗(yàn)數(shù)一般是各優(yōu)先等級(jí)因子的代數(shù)和檢驗(yàn)數(shù)一般是各優(yōu)先等級(jí)因子的代數(shù)和判斷檢驗(yàn)數(shù)的正負(fù)和大小判斷檢驗(yàn)數(shù)的正負(fù)和大小 目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)形目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)形式上沒有本質(zhì)的區(qū)別，所以可用單純形法求解。但要考慮目式上沒有本質(zhì)的區(qū)別，

41、所以可用單純形法求解。但要考慮目標(biāo)規(guī)劃的數(shù)學(xué)模型一些特點(diǎn)，作以下規(guī)定：標(biāo)規(guī)劃的數(shù)學(xué)模型一些特點(diǎn)，作以下規(guī)定：(1) 因目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求最小化，所以以因目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求最小化，所以以cj-zj0，j=1,2,，n為最優(yōu)準(zhǔn)則。為最優(yōu)準(zhǔn)則。(2)因非基變量的檢驗(yàn)數(shù)中含有不同等級(jí)的優(yōu)先因子，即因非基變量的檢驗(yàn)數(shù)中含有不同等級(jí)的優(yōu)先因子，即KknjPazckkjjj, 2 , 1;, 2 , 1 - - 因因P1P2PK；從每個(gè)檢驗(yàn)數(shù)的整體來看：檢驗(yàn)數(shù)；從每個(gè)檢驗(yàn)數(shù)的整體來看：檢驗(yàn)數(shù)的正、負(fù)首先決定于的正、負(fù)首先決定于P1的系數(shù)的系數(shù)1j的正、負(fù)。若的正、負(fù)。若1j=0，這時(shí)此，

42、這時(shí)此檢驗(yàn)數(shù)的正、負(fù)就決定于檢驗(yàn)數(shù)的正、負(fù)就決定于P2的系數(shù)的系數(shù)2j的正、負(fù)。的正、負(fù)。OR:SM例例OR:SMOR:SMOR:SMOR:SMOR:SM見表見表4-13.OR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SMOR:SM例例 ：用單純形法求解下列目標(biāo)規(guī)劃問題：用單純形法求解下列目標(biāo)規(guī)劃問題 MinZ=P1 d1- + P2(d2-+d2+)+P3(3d3-+5d4-) 5x1+4x2 +d1- d1+ = 20 4x1+3x2 +d2- - d2+= 24 x1 +d3- - d3+ = 3 - x1 + x2 +d4- - d4+

43、 = 2 x1 , x2 ,dk- , dk+ 0cj 值值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+檢驗(yàn)數(shù)檢驗(yàn)數(shù)jP1P2P300P10 P2P23P305P3020541-10000002443001-1000031000001-1002-110000001-1d1-d2-d3-d4-5-401000-4-322-535463-檢驗(yàn)數(shù)檢驗(yàn)數(shù)jP1P2P3d1-d2-x1d4-P1P205P331000001-1005041-100-55001203001-1-440050100001-11-10-40105-50-324-4-5-25513-P1 P23P35P3c

44、j00P10 P2P23P305P30 值值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+檢驗(yàn)數(shù)檢驗(yàn)數(shù)jP1P2P3d3+d2-x1d4-0P205P3104/51/5-1/500-110080-1/5-4/54/51-10000414/51/5-1/5000000609/51/5-1/500001-1010001/54/5-4/52-9-1135-10-檢驗(yàn)數(shù)檢驗(yàn)數(shù)jP1P2P3d3+d1+x1d4-0005P3100-1/4-115/4-5/40000303/4001/4-1/4-1100613/4001/4-1/40000807/4001/4-1/4001-10100

45、011-35/4-5/45/4354-832/7cj00P10 P2P23P305P30 值值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+檢驗(yàn)數(shù)檢驗(yàn)數(shù)jP1P2P3x2d1+x1d4-0005P3401001/3-1/3 -4/34/3001100-114/3-4/3 -1/31/3003100000-110010000-1/31/37/3-7/31-10010 0115/3-5/3-26/335/35-3檢驗(yàn)數(shù)檢驗(yàn)數(shù)jP1P2P3x2d1+x1d3-0003P33/70000-1/71/71-13/7-3/732/701001/7-1/7004/7-4/778/700-

46、119/7-9/7001/7-1/718/710001/7-1/700-3/73/700100 0113/7-3/7326/79/7例：用單純形法求解下列目標(biāo)規(guī)劃問題例：用單純形法求解下列目標(biāo)規(guī)劃問題 minZ=P1 d1+P2(d2-+d2+)+P3d3- 2x1+ x2 + x3 = 11 x1 - x2 +d1- - d1+= 0 x1 + 2x2 +d2- - d2+ = 10 8x1 + 10 x2 +d3- - d3+ = 56 xi,dk- , dk+ 0OR:SM104第五節(jié)第五節(jié) 目標(biāo)規(guī)劃的應(yīng)用案例目標(biāo)規(guī)劃的應(yīng)用案例一、無窮多滿意解一、無窮多滿意解解：設(shè)解：設(shè)x1,x2表示表

47、示A、B產(chǎn)品的產(chǎn)量。兩個(gè)等級(jí)的目標(biāo)：產(chǎn)品的產(chǎn)量。兩個(gè)等級(jí)的目標(biāo)：P1：充分利用電量限額，正負(fù)偏差之和為最小 目標(biāo)達(dá)成函數(shù)目標(biāo)達(dá)成函數(shù) 目標(biāo)約束條件目標(biāo)約束條件 P2 ：利潤額希望不能低于100元，負(fù)偏差最小 目標(biāo)達(dá)成函數(shù)目標(biāo)達(dá)成函數(shù) 目標(biāo)約束條件目標(biāo)約束條件 )(111- ddP6612101121-ddxx-22dP10020102221-ddxx計(jì)劃生產(chǎn)兩種產(chǎn)品，計(jì)劃生產(chǎn)兩種產(chǎn)品，首先要充分利用設(shè)備工時(shí)而不加班；然首先要充分利用設(shè)備工時(shí)而不加班；然后考慮利潤不低于后考慮利潤不低于100元。問應(yīng)如何制定產(chǎn)品元。問應(yīng)如何制定產(chǎn)品A、B的產(chǎn)量。的產(chǎn)量。OR:SM1052A24BDx26810 x

48、1第五節(jié)第五節(jié) 目標(biāo)規(guī)劃的應(yīng)用案例目標(biāo)規(guī)劃的應(yīng)用案例一、無窮多滿意解一、無窮多滿意解由于材料供應(yīng)限量為由于材料供應(yīng)限量為8單位，所以有系統(tǒng)約束條件，如下單位，所以有系統(tǒng)約束條件，如下8221 xx該問題的目標(biāo)規(guī)劃模型如下，圖解法求解如圖該問題的目標(biāo)規(guī)劃模型如下，圖解法求解如圖111221211122212121122min()101266(1)(2)1020100s.t.(3)28,0,0GP ddP dxxddxxddxxx xdddd-CG1d-1d2d-2dOR:SM106第五節(jié)第五節(jié) 目標(biāo)規(guī)劃的應(yīng)用案例目標(biāo)規(guī)劃的應(yīng)用案例二、加班時(shí)間問題二、加班時(shí)間問題例：例：某音像店有某音像店有5名全

49、職售貨員和名全職售貨員和4名兼職售貨員，全職名兼職售貨員，全職售貨員每月工作售貨員每月工作160小時(shí)，兼職售貨員每月工作小時(shí)，兼職售貨員每月工作80小時(shí)。根小時(shí)。根據(jù)記錄，全職每小時(shí)銷售據(jù)記錄，全職每小時(shí)銷售CD25張，平均每小時(shí)工資張，平均每小時(shí)工資15元，元，加班工資每小時(shí)加班工資每小時(shí)22.5元。兼職售貨員每小時(shí)銷售元。兼職售貨員每小時(shí)銷售CD10張，張，平均工資每小時(shí)平均工資每小時(shí)10元，加班工資每小時(shí)元，加班工資每小時(shí)10元?，F(xiàn)在預(yù)測下元?，F(xiàn)在預(yù)測下月月CD銷售量為銷售量為27500張，商店每周開門營業(yè)張，商店每周開門營業(yè)6天，所以可能天，所以可能要加班。每出售一張要加班。每出售一張

50、CD盈利盈利1.5元。元。 商店經(jīng)理認(rèn)為，保持穩(wěn)定的就業(yè)水平加上必要的加班，商店經(jīng)理認(rèn)為，保持穩(wěn)定的就業(yè)水平加上必要的加班，比不加班就業(yè)水平要好，但全職銷售員如果加班過多，就比不加班就業(yè)水平要好，但全職銷售員如果加班過多，就會(huì)因?yàn)槠谶^度而造成效率下降，因此不允許每月加班超會(huì)因?yàn)槠谶^度而造成效率下降，因此不允許每月加班超過過100小時(shí)，建立相應(yīng)的目標(biāo)規(guī)劃模型。小時(shí)，建立相應(yīng)的目標(biāo)規(guī)劃模型。OR:SM107第五節(jié)第五節(jié) 目標(biāo)規(guī)劃的應(yīng)用案例目標(biāo)規(guī)劃的應(yīng)用案例二、加班時(shí)間問題二、加班時(shí)間問題首先，確定目標(biāo)約束的優(yōu)先級(jí)。首先，確定目標(biāo)約束的優(yōu)先級(jí)。如下：如下：P1：下月的：下月的CD銷售量達(dá)到銷售量

51、達(dá)到27500張；張；P2：全職售貨員加班時(shí)間不超過：全職售貨員加班時(shí)間不超過100小時(shí)；小時(shí)；P3：保持全體售貨員充分就業(yè)，對(duì)全職的要比兼職的：保持全體售貨員充分就業(yè)，對(duì)全職的要比兼職的加倍優(yōu)先考慮；加倍優(yōu)先考慮；P4：盡量減少加班時(shí)間，對(duì)兩種售貨員區(qū)別對(duì)待，權(quán)：盡量減少加班時(shí)間，對(duì)兩種售貨員區(qū)別對(duì)待，權(quán)重由他們對(duì)利潤的貢獻(xiàn)而定。重由他們對(duì)利潤的貢獻(xiàn)而定。其次，建立目標(biāo)約束函數(shù)其次，建立目標(biāo)約束函數(shù)（1）銷售目標(biāo)約束銷售目標(biāo)約束，設(shè)全體全職售貨員下月的工作時(shí)，設(shè)全體全職售貨員下月的工作時(shí)間間x1，全體兼職售貨員下月的工作時(shí)間，全體兼職售貨員下月的工作時(shí)間 x2；達(dá)不到銷售；達(dá)不到銷售目標(biāo)的偏

52、差目標(biāo)的偏差d1-，超過銷售目標(biāo)的偏差，超過銷售目標(biāo)的偏差 d1+。 1111211min251027500GPdxxdd- OR:SM108第五節(jié)第五節(jié) 目標(biāo)規(guī)劃的應(yīng)用案例目標(biāo)規(guī)劃的應(yīng)用案例二、加班時(shí)間問題二、加班時(shí)間問題 （2）正常工作時(shí)間約束正常工作時(shí)間約束。設(shè)全體全職售貨員下月的停工時(shí)間。設(shè)全體全職售貨員下月的停工時(shí)間d2-，加班時(shí)間加班時(shí)間d2+ ；全體兼職售貨員下月的停工時(shí)間；全體兼職售貨員下月的停工時(shí)間d3-，加班時(shí)間，加班時(shí)間d3+。（3）加班時(shí)間的限制。加班時(shí)間的限制。設(shè)全體全職售貨員下月的加班不足設(shè)全體全職售貨員下月的加班不足100小時(shí)小時(shí)的偏差的偏差d4-，加班超過，加班

53、超過100小時(shí)的偏差小時(shí)的偏差 d4+ 。兩類售貨員區(qū)別對(duì)待，權(quán)重比兩類售貨員區(qū)別對(duì)待，權(quán)重比d2+:d3+ =1:3，另一加班目標(biāo)約束為，另一加班目標(biāo)約束為3323122233min(2)800320GPddxddxdd-224144min900GP dxdd-4423122233min(3)800320GP ddxddxdd-OR:SM109第五節(jié)第五節(jié) 目標(biāo)規(guī)劃的應(yīng)用案例目標(biāo)規(guī)劃的應(yīng)用案例二、加班時(shí)間問題二、加班時(shí)間問題 第三，按目標(biāo)的優(yōu)先級(jí)，寫出相應(yīng)的目標(biāo)規(guī)劃模型：第三，按目標(biāo)的優(yōu)先級(jí)，寫出相應(yīng)的目標(biāo)規(guī)劃模型：1124323423121112223314412min(2)(3)2510

54、27500800320s.t.900,0,01,2,3,4llGPdP dPddP ddxxddxddxddxddx xddl-運(yùn)用運(yùn)用LINGO軟件求解得軟件求解得 x1=900,x2=500，下月共銷售，下月共銷售CD盤盤27500張，獲利張，獲利275001.5-80015-10022.5-50010=22000。OR:SM110第五節(jié)第五節(jié) 目標(biāo)規(guī)劃的應(yīng)用案例目標(biāo)規(guī)劃的應(yīng)用案例三、目標(biāo)管理方案三、目標(biāo)管理方案 例：例：某公司準(zhǔn)備生產(chǎn)甲、乙產(chǎn)品，據(jù)市場調(diào)查：甲產(chǎn)品的最大某公司準(zhǔn)備生產(chǎn)甲、乙產(chǎn)品，據(jù)市場調(diào)查：甲產(chǎn)品的最大市場需求市場需求3臺(tái)，乙產(chǎn)品的最大市場需求臺(tái)，乙產(chǎn)品的最大市場需求2臺(tái)

55、。臺(tái)。 在滿足現(xiàn)有電力資源嚴(yán)格供給約束的前提下，該廠長考慮兩在滿足現(xiàn)有電力資源嚴(yán)格供給約束的前提下，該廠長考慮兩個(gè)目標(biāo)：個(gè)目標(biāo)：一是總利潤不低于一是總利潤不低于36003600元；二是充分利用設(shè)備臺(tái)時(shí)，元；二是充分利用設(shè)備臺(tái)時(shí)，但盡量少加班。但盡量少加班。問應(yīng)如何制定產(chǎn)品甲、乙的產(chǎn)量，試建立其目問應(yīng)如何制定產(chǎn)品甲、乙的產(chǎn)量，試建立其目標(biāo)規(guī)劃的數(shù)學(xué)模型。標(biāo)規(guī)劃的數(shù)學(xué)模型。OR:SM111第五節(jié)第五節(jié) 目標(biāo)規(guī)劃的應(yīng)用案例目標(biāo)規(guī)劃的應(yīng)用案例三、目標(biāo)管理方案三、目標(biāo)管理方案 1. 利潤期望優(yōu)先利潤期望優(yōu)先目標(biāo)規(guī)劃數(shù)學(xué)模型：目標(biāo)規(guī)劃數(shù)學(xué)模型： 1122212111222121212min()300400

56、360030603605560s.t.86,0,01,2llGPdP ddxxddxxddxxxxx xddl-運(yùn)用圖解法進(jìn)行求解運(yùn)用圖解法進(jìn)行求解 FECx1 =8x2 =65x1 +5x2 =600 x12410126ABx20842D10G1d-1d2d-2dx1 =8, x2 = 3OR:SM112第五節(jié)第五節(jié) 目標(biāo)規(guī)劃的應(yīng)用案例目標(biāo)規(guī)劃的應(yīng)用案例1. 利潤期望優(yōu)先利潤期望優(yōu)先 總利潤總利潤：3600單位甲單位甲：300單位乙單位乙：400生產(chǎn)部目標(biāo)生產(chǎn)部目標(biāo)甲產(chǎn)品的產(chǎn)量：甲產(chǎn)品的產(chǎn)量：8，成本：，成本：900乙產(chǎn)品的產(chǎn)量：乙產(chǎn)品的產(chǎn)量：3，成本：，成本：1400技術(shù)部目標(biāo)技術(shù)部目標(biāo)甲

57、的設(shè)備單耗甲的設(shè)備單耗25，需降低，需降低5工時(shí)工時(shí) 乙的設(shè)備單耗乙的設(shè)備單耗50，需降低，需降低10工時(shí)工時(shí) 銷售部目標(biāo)銷售部目標(biāo)甲產(chǎn)品的銷量：甲產(chǎn)品的銷量：8，單價(jià)：，單價(jià)：1200乙產(chǎn)品的銷量：乙產(chǎn)品的銷量：3，單價(jià)：，單價(jià)：1800滿意解：滿意解：x1 =8, x2 = 3設(shè)備能力：需求：設(shè)備能力：需求：30 8+60 3=420，實(shí)際：，實(shí)際：360實(shí)現(xiàn)實(shí)現(xiàn)目標(biāo)目標(biāo)P1和和P2，降低甲乙產(chǎn)品的設(shè)備消耗，降低甲乙產(chǎn)品的設(shè)備消耗:降低率降低率(420-360)/360=17%， 甲產(chǎn)品的設(shè)備消耗降為甲產(chǎn)品的設(shè)備消耗降為30 (1-17%)=25, 乙產(chǎn)品的設(shè)備消耗降為乙產(chǎn)品的設(shè)備消耗降為

58、60 (1-17%)=50。OR:SM113第五節(jié)第五節(jié) 目標(biāo)規(guī)劃的應(yīng)用案例目標(biāo)規(guī)劃的應(yīng)用案例三、目標(biāo)管理方案三、目標(biāo)管理方案 2. 設(shè)備工時(shí)優(yōu)先設(shè)備工時(shí)優(yōu)先目標(biāo)規(guī)劃數(shù)學(xué)模型：目標(biāo)規(guī)劃數(shù)學(xué)模型： 1212212111222121212min()300400360030603605560s.t.86,0,01,2llGPdP ddxxddxxddxxxxx xddl-運(yùn)用圖解法進(jìn)行求解運(yùn)用圖解法進(jìn)行求解 FECx1 =8x2 =65x1 +5x2 =600 x12410126ABx20842D10G1d-1d2d-2dx1 =8, x2 = 2OR:SM114第五節(jié)第五節(jié) 目標(biāo)規(guī)劃的應(yīng)用案例目標(biāo)

59、規(guī)劃的應(yīng)用案例2. 設(shè)備工時(shí)優(yōu)先設(shè)備工時(shí)優(yōu)先 總利潤總利潤：3600單位甲單位甲：337.5單位乙單位乙：450 生產(chǎn)部目標(biāo)生產(chǎn)部目標(biāo)甲產(chǎn)品的產(chǎn)量：甲產(chǎn)品的產(chǎn)量：8，成本：，成本：862.5 乙產(chǎn)品的產(chǎn)量：乙產(chǎn)品的產(chǎn)量：2 ，成本：，成本：1350 技術(shù)部目標(biāo)技術(shù)部目標(biāo)保證設(shè)備的正常運(yùn)行保證設(shè)備的正常運(yùn)行甲的設(shè)備單耗甲的設(shè)備單耗30 ，乙的單耗，乙的單耗60 銷售部目標(biāo)銷售部目標(biāo)甲產(chǎn)品的銷量：甲產(chǎn)品的銷量：8，單價(jià)：，單價(jià)：1200乙產(chǎn)品的銷量：乙產(chǎn)品的銷量：2 ，單價(jià)：，單價(jià)：1800滿意解：滿意解：x1 =8, x2 = 2利潤總額利潤總額300 8+400 2=3200，目標(biāo)：，目標(biāo)：3

60、600不能提價(jià)，就必須降低成本以增加利潤，利潤增長率為不能提價(jià)，就必須降低成本以增加利潤，利潤增長率為12.5% 甲產(chǎn)品的甲產(chǎn)品的成本需要降為成本需要降為1200-300 (1+12.5%)=862.5元元/臺(tái)，降低幅度臺(tái)，降低幅度4.2% 乙產(chǎn)品的乙產(chǎn)品的成本需要降為成本需要降為1800-400 (1+12.5%)=1350元元/臺(tái)，降低幅度臺(tái)，降低幅度3.6% 例例5-10：已知一個(gè)生產(chǎn)計(jì)劃的線性：已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型，經(jīng)營目標(biāo)：規(guī)劃模型，經(jīng)營目標(biāo)：P1：總利潤不低于：總利潤不低于40P2：充分利用設(shè)備能力，且盡量：充分利用設(shè)備能力，且盡量不超過不超過140如何安排生產(chǎn)？如何安排