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

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

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

3、的部分。始終存在d d=0牙齒，因為決策值不能超過目標(biāo)值，并且未達(dá)到目標(biāo)值。清華大學(xué)出版社，第8，1節(jié)目標(biāo)計劃的數(shù)學(xué)模型，2。絕對約束和目標(biāo)約束絕對約束是必須嚴(yán)格滿足的等式約束和不等式約束，例如線性規(guī)劃問題中的所有約束。不滿足這些約束的解釋稱為不可行的解決方案。因此是硬性限制。目標(biāo)約束取決于目標(biāo)計劃，可以視為追求約束右端的目標(biāo)值。達(dá)到牙齒目標(biāo)值時，允許正偏差或負(fù)偏差。因此，將軟約束正負(fù)偏差變量添加到這些約束。線性規(guī)劃問題的目標(biāo)函數(shù)。指定目標(biāo)值，添加正偏差和負(fù)偏差變量，然后將其轉(zhuǎn)換為目標(biāo)約束條件。此外，可以根據(jù)問題的需要將絕對約束轉(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)計劃數(shù)學(xué)模型，第3節(jié)。優(yōu)先級但決策者要求實現(xiàn)這些目標(biāo)時，優(yōu)先級或輕重緩急可能會有所不同。例如，將優(yōu)先級因子P1賦予第一個實現(xiàn)的目標(biāo)，將優(yōu)先級因子P2賦予輔助目標(biāo)，PkPk 1 k=1，2，K規(guī)定Pk的優(yōu)先級大于Pk 1。也就是說，首先確保實現(xiàn)P1級別的目標(biāo)，此時不考慮輔助目標(biāo)。P2級目標(biāo)只考慮實現(xiàn)P1級目標(biāo)。以這種方式類推。為了區(qū)分具有相同優(yōu)先級系數(shù)的兩個目標(biāo)的差異，可以根據(jù)醫(yī)生確定者分別賦予不同的權(quán)重系數(shù)wj。清華大學(xué)出版社，第10，1節(jié)目標(biāo)計劃的數(shù)學(xué)

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

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

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

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

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

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

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

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

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

14、出版社，34，4節(jié)應(yīng)用實例。每個等級的人數(shù)不超過政編規(guī)定的人數(shù)。級別為10(1 0.1) x1 d2d2=12對級別為12 x1 x2 d3d3=15對級別為15 x2 x3 D4 D4=15，級別的升級面不超過現(xiàn)有人員的20%。但是，盡可能多地提到：x1 D5 D5=120.2對x2 D6 D6=150.2目標(biāo)函數(shù)：min z=P1d1 P2(d2 D3 D4) P3(d5 D6)以上的目標(biāo)計劃可以通過單純形方法解決，并且可以獲得多個解釋。將牙齒解法匯總到表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個銷售地有3個產(chǎn)地供應(yīng)哪些產(chǎn)品。生產(chǎn)地之間的供應(yīng)和單位運費見表4-10。相關(guān)部門在研究運輸方案時，會依次考慮下7個茄子目標(biāo)，并規(guī)定相應(yīng)的優(yōu)先順序。P1B4是重點保證單位，必須全部滿足其要求。P2A3為B1提供超過100個產(chǎn)量。P3各銷售地的供應(yīng)超過需求量的80%。P4規(guī)定的運輸方案的總運費不超過最低運輸方案的10%。由于P5公路部分的問題，請盡量不要將A2產(chǎn)品部署到B4。P6 B1和B3的供應(yīng)率必須相同。P7應(yīng)該最珍惜總運費。試驗滿意的運輸方案。清華大學(xué)出版社，37，4節(jié)應(yīng)用實例，表工作法求最低運費的運輸方案見表4-11。此時最低票價為2950韓元，要根據(jù)提出的每個目標(biāo)的要求制作目標(biāo)計劃的模型。表4-11