運(yùn)籌學(xué)(第四版)清華大學(xué)出版社《運(yùn)籌學(xué)》教材編寫組-第5章 線性目標(biāo)規(guī)劃.ppt

1、清華大學(xué)出版社，第1，2章，線性規(guī)劃和目標(biāo)計(jì)劃，第1章線性規(guī)劃和簡(jiǎn)單法第2章對(duì)偶理論和敏感度分析第3章交通問(wèn)題第4章目標(biāo)計(jì)劃，清華大學(xué)出版社，第2，4章目標(biāo)計(jì)劃，理解第1節(jié)目標(biāo)計(jì)劃的數(shù)學(xué)模型第2節(jié)目標(biāo)計(jì)劃的圖3節(jié)應(yīng)用范例，清華大學(xué)出版社，第3，1節(jié)目標(biāo)計(jì)劃的數(shù)學(xué)模型，目標(biāo)，清華大學(xué)出版社，4，1節(jié)目標(biāo)計(jì)劃數(shù)學(xué)模型，例1某工廠生產(chǎn)，兩個(gè)茄子產(chǎn)品，相關(guān)資料見(jiàn)下表。試驗(yàn)利潤(rùn)最大的生產(chǎn)方案。解決方案：這是尋找最有利可圖的單一目標(biāo)的計(jì)劃問(wèn)題。x1、x2分別表示產(chǎn)品的產(chǎn)量，線性規(guī)劃型號(hào)顯示如下：清華大學(xué)出版社，第5，1節(jié)目標(biāo)計(jì)劃的數(shù)學(xué)模型，圖表得出最佳決策方案是x1 *=4，x2 *=3，清華大學(xué)出版社，

2、第6，1節(jié)目標(biāo)計(jì)劃的數(shù)學(xué)模型，實(shí)際上工廠在決策時(shí)需要考慮一系列條件，包括市場(chǎng)因素。例如，根據(jù)： (1)市場(chǎng)信息，產(chǎn)品銷售量有下降的趨勢(shì)，希望產(chǎn)品產(chǎn)量不要大于產(chǎn)品。(2)在計(jì)劃原材料供應(yīng)時(shí)，高價(jià)購(gòu)買的費(fèi)用可能會(huì)大幅增加。(3)要盡可能充分利用裝備臺(tái)，但不想加班進(jìn)行。(4)盡可能實(shí)現(xiàn)計(jì)劃效益指標(biāo)：56元，應(yīng)超額。清華大學(xué)出版社7，1節(jié)目標(biāo)計(jì)劃的數(shù)學(xué)模型，這種產(chǎn)品決策問(wèn)題構(gòu)成了多目標(biāo)決策問(wèn)題。目標(biāo)規(guī)劃方法就是解決這種決策問(wèn)題的方法之一。下面介紹與目標(biāo)計(jì)劃模型相關(guān)的概念。1.將x1，x2設(shè)定為決策變數(shù)，并引入正負(fù)偏差變數(shù)d，d。正偏差變量d表示決策值超出目標(biāo)值的部分。負(fù)偏差變量d表示決策值未達(dá)到目標(biāo)值

3、的部分。始終存在d d=0牙齒，因?yàn)闆Q策值不能超過(guò)目標(biāo)值，并且未達(dá)到目標(biāo)值。清華大學(xué)出版社，第8，1節(jié)目標(biāo)計(jì)劃的數(shù)學(xué)模型，2。絕對(duì)約束和目標(biāo)約束絕對(duì)約束是必須嚴(yán)格滿足的等式約束和不等式約束，例如線性規(guī)劃問(wèn)題中的所有約束。不滿足這些約束的解釋稱為不可行的解決方案。因此是硬性限制。目標(biāo)約束取決于目標(biāo)計(jì)劃，可以視為追求約束右端的目標(biāo)值。達(dá)到牙齒目標(biāo)值時(shí)，允許正偏差或負(fù)偏差。因此，將軟約束正負(fù)偏差變量添加到這些約束。線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)。指定目標(biāo)值，添加正偏差和負(fù)偏差變量，然后將其轉(zhuǎn)換為目標(biāo)約束條件。此外，可以根據(jù)問(wèn)題的需要將絕對(duì)約束轉(zhuǎn)換為目標(biāo)約束。例如，您可以將示例1中的目標(biāo)函數(shù)z=8x1 10

4、x轉(zhuǎn)換為目標(biāo)約束8x1 10 x2 d1d1=56約束2x1 x211目標(biāo)約束2x1 x2 d2d2=11。清華大學(xué)出版社，第9節(jié)，第1節(jié)目標(biāo)計(jì)劃數(shù)學(xué)模型，第3節(jié)。優(yōu)先級(jí)但決策者要求實(shí)現(xiàn)這些目標(biāo)時(shí)，優(yōu)先級(jí)或輕重緩急可能會(huì)有所不同。例如，將優(yōu)先級(jí)因子P1賦予第一個(gè)實(shí)現(xiàn)的目標(biāo)，將優(yōu)先級(jí)因子P2賦予輔助目標(biāo)，PkPk 1 k=1，2，K規(guī)定Pk的優(yōu)先級(jí)大于Pk 1。也就是說(shuō)，首先確保實(shí)現(xiàn)P1級(jí)別的目標(biāo)，此時(shí)不考慮輔助目標(biāo)。P2級(jí)目標(biāo)只考慮實(shí)現(xiàn)P1級(jí)目標(biāo)。以這種方式類推。為了區(qū)分具有相同優(yōu)先級(jí)系數(shù)的兩個(gè)目標(biāo)的差異，可以根據(jù)醫(yī)生確定者分別賦予不同的權(quán)重系數(shù)wj。清華大學(xué)出版社，第10，1節(jié)目標(biāo)計(jì)劃的數(shù)學(xué)

5、模型，4。目標(biāo)計(jì)劃的目標(biāo)函數(shù)目標(biāo)計(jì)劃的目標(biāo)函數(shù)(準(zhǔn)則函數(shù))是根據(jù)每個(gè)目標(biāo)約束的正負(fù)偏差變量、給定的優(yōu)先系數(shù)和權(quán)重來(lái)構(gòu)建的。確定每個(gè)目標(biāo)值后，醫(yī)生決定者的要求是最小化與目標(biāo)值的偏差。因此，目標(biāo)計(jì)劃的目標(biāo)函數(shù)格式通常有三種茄子形式：min z=f(d，d)。(1)如果要求精確達(dá)到目標(biāo)值，則正負(fù)偏差變量必須盡可能小。對(duì)于牙齒，目標(biāo)函數(shù)格式為min z=f (d d)(此時(shí)目標(biāo)函數(shù)格式為min z=f(d) (3)如果必須超過(guò)目標(biāo)值，則超出量沒(méi)有限制，但是負(fù)偏差變量必須盡可能小)，目標(biāo)函數(shù)格式為min z=f (d)，清華大學(xué)出版社，11，第1節(jié)目標(biāo)再一次，利潤(rùn)額在56韓元以上。尋求最佳決策方案。解決

6、方案：應(yīng)醫(yī)生決策者的要求，分別指定三個(gè)牙齒茄子目標(biāo)優(yōu)先級(jí)因子P1、P2和P3，并獲得牙齒問(wèn)題的數(shù)學(xué)模型：清華大學(xué)出版社，12，第1節(jié)目標(biāo)計(jì)劃的數(shù)學(xué)模型，目標(biāo)計(jì)劃的一般數(shù)學(xué)模型，權(quán)重因子。P127 5.1，作業(yè)，清華大學(xué)出版社，14，2節(jié)目標(biāo)計(jì)劃的示意圖，只有兩個(gè)決策變量的目標(biāo)計(jì)劃問(wèn)題可以通過(guò)示意圖解決(圖4-1)。清華大學(xué)出版社，第15，2節(jié)目標(biāo)計(jì)劃的示意圖法，注：在解決目標(biāo)計(jì)劃問(wèn)題時(shí)，將絕對(duì)約束作為最高優(yōu)先級(jí)考慮。在牙齒示例中，D1=0、D2 d2=0、d3=0是z*=0，因?yàn)榭梢园磧?yōu)先級(jí)滿足它們。但在大多數(shù)問(wèn)題上不是這樣。因?yàn)槲礉M足某些限制，所以目標(biāo)計(jì)劃問(wèn)題的最佳解決方案稱為滿意的解決方案

7、。清華大學(xué)出版社，16，2節(jié)目標(biāo)計(jì)劃的示意圖法，例3某電視機(jī)工廠組裝黑白和彩色電視兩種，每臺(tái)電視機(jī)一條裝配線一小時(shí)，裝配線計(jì)劃每周運(yùn)行40小時(shí)。預(yù)計(jì)市場(chǎng)每周的彩色電視銷售量為24臺(tái)，各能賺80元。黑白電視銷量30多歲，各能賺40元。牙齒工廠制定的目標(biāo)是第一優(yōu)先：充分利用裝配線，計(jì)劃每周運(yùn)行40小時(shí)。第二優(yōu)先事項(xiàng)：允許裝配線加班；但是加班時(shí)間盡量不超過(guò)每周10個(gè)小時(shí)。第三優(yōu)先：組裝的電視機(jī)數(shù)量最大限度地滿足市場(chǎng)需求。由于彩色電視利潤(rùn)高，其權(quán)重為2。構(gòu)建牙齒問(wèn)題的目標(biāo)規(guī)劃模型，解決黑白和彩色電視產(chǎn)量問(wèn)題。清華大學(xué)出版社，17，2節(jié)目標(biāo)計(jì)劃的簡(jiǎn)圖，解法：x1，x2分別表示黑白和彩色電視產(chǎn)量。牙齒問(wèn)題

8、的目標(biāo)計(jì)劃模型，由清華大學(xué)出版社，18，2節(jié)目標(biāo)計(jì)劃的簡(jiǎn)圖，用圖解法解決。請(qǐng)參閱圖4.2。清華大學(xué)出版社，19，2節(jié)目標(biāo)計(jì)劃的示意圖如圖4.2所示，考慮到具有優(yōu)先級(jí)元素P1，P2的目標(biāo)實(shí)現(xiàn)后，x1，x2的范圍為ABCD?？紤]P3層目標(biāo)時(shí)，首先考慮min D3牙齒，因?yàn)镈3的權(quán)重系數(shù)比D4大小。x1，x2的范圍縮小到ABEF區(qū)域。然后考慮D4。D4=0在區(qū)域ABEF中不滿足要求，因此可以在ABEF中只提取一個(gè)點(diǎn)，使D4盡可能小。這是e點(diǎn)。因此E點(diǎn)是滿意的解，其坐標(biāo)為(24，26)。也就是說(shuō)，牙齒工廠每周要組裝24臺(tái)彩色電視和26臺(tái)黑白電視。P127 5.2 (1)圖解法，工作，清華大學(xué)出版社，2

9、1，3節(jié)目標(biāo)計(jì)劃的單純形法，目標(biāo)計(jì)劃的數(shù)學(xué)模型結(jié)構(gòu)和線性規(guī)劃數(shù)學(xué)模型結(jié)構(gòu)上沒(méi)有本質(zhì)的差異，因此可以用單純形法解決。但是，根據(jù)目標(biāo)計(jì)劃的特點(diǎn)，必須有以下規(guī)定。(1)將目標(biāo)計(jì)劃問(wèn)題的目標(biāo)函數(shù)全部最小化，因此將cjzj0，j=1，2，N作為最佳判別標(biāo)準(zhǔn)。(2)非系統(tǒng)變量的檢查數(shù)包含不同等級(jí)的優(yōu)先級(jí)，即，由于P1P2PK，在每個(gè)檢查數(shù)的整個(gè)中檢查數(shù)的正、負(fù)首先由P1的系數(shù)1j的正、負(fù)確定。1j=0時(shí)，牙齒檢查數(shù)的正負(fù)由P2系數(shù)2j的正負(fù)確定。類推如下。，清華大學(xué)出版社，22，3節(jié)目標(biāo)計(jì)劃的單純形方法，解決目標(biāo)計(jì)劃問(wèn)題的單純形方法計(jì)算步驟：(1)創(chuàng)建初始單純形表，根據(jù)優(yōu)先級(jí)系數(shù)數(shù)將表中的檢驗(yàn)數(shù)行列為K行

10、，設(shè)置k=1。(2)檢查該行是否有負(fù)數(shù)，以及該行的第一個(gè)k1行的系數(shù)是否為零。如果負(fù)數(shù)中最小的變量是替換變量，則轉(zhuǎn)至(3)。如果沒(méi)有負(fù)數(shù)，則轉(zhuǎn)至(5)。(3)更換變量根據(jù)最小比率規(guī)則確定。如果有多個(gè)相同的最小百分比，請(qǐng)選擇優(yōu)先級(jí)較高的變量作為替代變量。(4)根據(jù)單純形法進(jìn)行基本轉(zhuǎn)換運(yùn)算，編制新的計(jì)算表，返回(2)。(5)當(dāng)k=K時(shí)，計(jì)算結(jié)束時(shí)，表中的解決方案是滿意的解決方案。否則，設(shè)置k=k 1，然后返回(2)。清華大學(xué)出版社，23，3節(jié)解決目標(biāo)計(jì)劃的單純形方法，實(shí)例4使用單純形方法解決實(shí)例2。解決方案：示例2中的數(shù)學(xué)模型：清華大學(xué)出版社，24，3節(jié)解目標(biāo)計(jì)劃的單純形方法，xs，D1，D2，D

11、3作為初始基本變量，參見(jiàn)列初始單純形表，表4-1。清華大學(xué)出版社，25，3節(jié)求解目標(biāo)計(jì)劃的簡(jiǎn)單方法，k=1，檢查檢查數(shù)的P1行，因?yàn)檠例X線沒(méi)有負(fù)檢查數(shù)，所以轉(zhuǎn)動(dòng)(5)。由于K(=1)K(=3)，因此設(shè)置k=k 1=2，然后返回(2)。檢查檢查數(shù)P2行中的1、2。采用Min(1，2)=2。對(duì)應(yīng)的變量x2是替換變量，被轉(zhuǎn)移到(3)中。在表4-1中，計(jì)算最小比率=min (11/1，0，10/2，56/10)=10/2相應(yīng)變量D2-change變量，轉(zhuǎn)入(4)。執(zhí)行基本轉(zhuǎn)換操作，計(jì)算結(jié)果見(jiàn)表4-2。返回(2)。直到以這種方式得到最后的票。請(qǐng)參閱表4-3。清華大學(xué)出版社，26，3節(jié)解決目標(biāo)計(jì)劃的簡(jiǎn)單法

12、，表4-2，清華大學(xué)出版社，27，3節(jié)解決目標(biāo)計(jì)劃的簡(jiǎn)單法，表4-3，清華大學(xué)出版社，28，3節(jié)解決目標(biāo)計(jì)劃的簡(jiǎn)單法，表，清華大學(xué)出版社，29在表4-3中，非基本變量D3作為交換變量，D1作為交換變量，反復(fù)得到表4-4。清華大學(xué)出版社，30，3節(jié)解目標(biāo)計(jì)劃的簡(jiǎn)單方法，相當(dāng)于表4-4中解的x1*=10/3，x2*=10/3，圖4-1中的D點(diǎn)。g，D 2點(diǎn)的凸線性組合都是示例2，P127 5.2 (1)單純形法、工作、清華大學(xué)出版社、32，4節(jié)適用示例，示例5某單位領(lǐng)導(dǎo)人在考慮本單位職員的升級(jí)曹征方案時(shí)，遵循了(1)年度工資總額不超過(guò)60，000韓元的規(guī)定。(2)各級(jí)人員不超過(guò)政編規(guī)定的人數(shù)。(3

13、)，等級(jí)的升級(jí)面盡可能達(dá)到現(xiàn)有人員的20%，沒(méi)有工資上升。(4)等級(jí)不足的人數(shù)可以聘用新員工，其他職工中有10%要退休。相關(guān)資料匯總在表4-8，問(wèn)牙齒領(lǐng)導(dǎo)人如何制定滿意的方案。清華大學(xué)出版社，33，4節(jié)app示例：x1，x2，x3分別表示晉升、等級(jí)、招聘的新員工數(shù)。為每個(gè)目標(biāo)確定的優(yōu)先級(jí)因素是不超過(guò)P1牙齒年度工資總額60，000韓元。每個(gè)P2水平的人數(shù)不超過(guò)政編規(guī)定的人數(shù)。P3，等級(jí)的升級(jí)面盡可能達(dá)到現(xiàn)有人員的20%。首先，單獨(dú)創(chuàng)建每個(gè)目標(biāo)約束。年薪總額不超過(guò)60000韓元2000(10100.1 x1)1500(12x 1x 2)1000(15x 2x 3)D1-D1=60000，清華大學(xué)

14、出版社，34，4節(jié)應(yīng)用實(shí)例。每個(gè)等級(jí)的人數(shù)不超過(guò)政編規(guī)定的人數(shù)。級(jí)別為10(1 0.1) x1 d2d2=12對(duì)級(jí)別為12 x1 x2 d3d3=15對(duì)級(jí)別為15 x2 x3 D4 D4=15，級(jí)別的升級(jí)面不超過(guò)現(xiàn)有人員的20%。但是，盡可能多地提到：x1 D5 D5=120.2對(duì)x2 D6 D6=150.2目標(biāo)函數(shù)：min z=P1d1 P2(d2 D3 D4) P3(d5 D6)以上的目標(biāo)計(jì)劃可以通過(guò)單純形方法解決，并且可以獲得多個(gè)解釋。將牙齒解法匯總到表4-9，單位領(lǐng)導(dǎo)根據(jù)具體情況從表4-9中選出執(zhí)行方案。，清華大學(xué)出版社，35，4節(jié)應(yīng)用示例，表4-9，清華大學(xué)出版社，36，4節(jié)應(yīng)用示例

15、，例6知道4個(gè)銷售地有3個(gè)產(chǎn)地供應(yīng)哪些產(chǎn)品。生產(chǎn)地之間的供應(yīng)和單位運(yùn)費(fèi)見(jiàn)表4-10。相關(guān)部門在研究運(yùn)輸方案時(shí)，會(huì)依次考慮下7個(gè)茄子目標(biāo)，并規(guī)定相應(yīng)的優(yōu)先順序。P1B4是重點(diǎn)保證單位，必須全部滿足其要求。P2A3為B1提供超過(guò)100個(gè)產(chǎn)量。P3各銷售地的供應(yīng)超過(guò)需求量的80%。P4規(guī)定的運(yùn)輸方案的總運(yùn)費(fèi)不超過(guò)最低運(yùn)輸方案的10%。由于P5公路部分的問(wèn)題，請(qǐng)盡量不要將A2產(chǎn)品部署到B4。P6 B1和B3的供應(yīng)率必須相同。P7應(yīng)該最珍惜總運(yùn)費(fèi)。試驗(yàn)滿意的運(yùn)輸方案。清華大學(xué)出版社，37，4節(jié)應(yīng)用實(shí)例，表工作法求最低運(yùn)費(fèi)的運(yùn)輸方案見(jiàn)表4-11。此時(shí)最低票價(jià)為2950韓元，要根據(jù)提出的每個(gè)目標(biāo)的要求制作目標(biāo)計(jì)劃的模型。表4-11