運籌學(xué)-目標規(guī)劃

2024/3/13運籌學(xué)-目標規(guī)劃目標規(guī)劃本章內(nèi)容重點目標規(guī)劃模型目標規(guī)劃的幾何意義目標規(guī)劃的單純形方法問題的提出線性規(guī)劃的局限性線性規(guī)劃只研究在滿足一定條件下，單一目標函數(shù)取得最優(yōu)解，而在企業(yè)管理中，經(jīng)常遇到多目標決策問題，如擬訂生產(chǎn)計劃時，不僅考慮總產(chǎn)值，同時要考慮利潤，產(chǎn)品質(zhì)量和設(shè)備利用率等。這些指標之間的重要程度(即優(yōu)先順序)也不相同，有些目標之間往往相互發(fā)生矛盾。線性規(guī)劃致力于某個目標函數(shù)的最優(yōu)解，這個最優(yōu)解若是超過了實際的需要，很可能是以過分地消耗了約束條件中的某些資源作為代價。線性規(guī)劃把各個約束條件的重要性都不分主次地等同看待，這也不符合實際情況。求解線性規(guī)劃問題，首先要求約束條件必須相容，如果約束條件中，由于人力，設(shè)備等資源條件的限制，使約束條件之間出現(xiàn)了矛盾，就得不到問題的可行解，但生產(chǎn)還得繼續(xù)進行，這將給人們進一步應(yīng)用線性規(guī)劃方法帶來困難。為了彌補線性規(guī)劃問題的局限性，解決有限資源和計劃指標之間的矛盾，在線性規(guī)劃基礎(chǔ)上，建立目標規(guī)劃方法，從而使一些線性規(guī)劃無法解決的問題得到滿意的解答。問題的提出第一節(jié)多目標規(guī)劃問題一、線性規(guī)劃的局限性線性規(guī)劃的局限性只能解決一組線性約束條件下，某一目標而且只能是一個目標的最大或最小值的問題實際決策中，衡量方案優(yōu)劣考慮多個目標生產(chǎn)計劃決策，通?？紤]產(chǎn)值、利潤、滿足市場需求等生產(chǎn)布局決策，考慮運費、投資、供應(yīng)、市場、污染等

這些目標中，有主要的，也有次要的；有最大的，有最小的；有定量的，有定性的；有互相補充的，有互相對立的，LP則無能為力目標規(guī)劃（GoalProgramming）

多目標線性規(guī)劃含有多個優(yōu)化目標的線性規(guī)劃目標規(guī)劃與線性規(guī)劃的比較線性規(guī)劃只討論一個線性目標函數(shù)在一組線性約束條件下的極值問題；而目標規(guī)劃是多個目標決策，可求得更切合實際的解。線性規(guī)劃求最優(yōu)解；目標規(guī)劃是找到一個滿意解。線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目標規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。線性規(guī)劃的最優(yōu)解是絕對意義下的最優(yōu)，但需花去大量的人力、物力、財力才能得到；實際過程中，只要求得滿意解，就能滿足需要(或更能滿足需要)。目標規(guī)劃與線性規(guī)劃的比較例5-1：某廠計劃在下一個生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計劃，使獲得的利潤最大？同時，根據(jù)市場預(yù)測，甲的銷路不是太好，應(yīng)盡可能少生產(chǎn)；乙的銷路較好，可以擴大生產(chǎn)。試建立此問題的數(shù)學(xué)模型。12070單件利潤3000103設(shè)備臺時200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗目標規(guī)劃數(shù)學(xué)模型設(shè)：甲產(chǎn)品x1

，乙產(chǎn)品x2根據(jù)市場預(yù)測：maxZ=70x1

+120x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000

x1，

x2≥0maxZ1=70x1

+120x2

minZ2=x1

maxZ3=x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000

x1，

x2≥0這些目標之間相互矛盾，一般的線性規(guī)劃方法不能求解第一節(jié)多目標規(guī)劃問題二、多目標規(guī)劃的提出多目標線性規(guī)劃模型的原始一般形式如下：n個決策變量，m個約束條件，L個目標函數(shù)。當L=1時，即為我們熟悉的單目標線性規(guī)劃模型。二、多目標規(guī)劃的提出10111213上述1415161718192021第一節(jié)多目標規(guī)劃問題三、多目標的處理方法加權(quán)系數(shù)法：為每一目標賦一權(quán)數(shù)，把多目標轉(zhuǎn)化成單目標。但權(quán)系數(shù)難以科學(xué)確定。

優(yōu)先等級法：各目標按重要性歸不同優(yōu)先級而化為單目標。

有效解法：尋求能照顧到各目標而使決策者感到滿意的解。但可行域大時難以列出所有有效解的組合。

目標規(guī)劃法：對每一個目標函數(shù)引入正的或負的偏差變量；引入目標的優(yōu)先等級和加權(quán)系數(shù)。22第二節(jié)目標規(guī)劃的數(shù)學(xué)模型1.目標期望值每一個目標希望達到的期望值(或目標值、理想值)。根據(jù)歷史資料、市場需求或上級部門的布置等來確定。一、目標值和偏差變量目標規(guī)劃通過引入目標值和偏差變量，可以將目標函數(shù)轉(zhuǎn)化為目標約束。實現(xiàn)值或決策值：是指當決策變量xj選定以后，目標函數(shù)的對應(yīng)值。23第二節(jié)目標規(guī)劃的數(shù)學(xué)模型2、偏差變量正偏差變量dk+表示第k個目標超過期望值的數(shù)值；負偏差變量dk-表示第k個目標未達到期望值的數(shù)值。同一目標的dk+和dk-中至少有一個必須為零。偏差變量(事先無法確定的未知數(shù))：是指實現(xiàn)值和目標值之間的差異,記為d。偏差可能存在正的或負的。正偏差變量:表示實現(xiàn)值超過目標值的部分，記為d＋。負偏差變量:表示實現(xiàn)值未達到目標值的部分，記為d－。目標規(guī)劃的數(shù)學(xué)模型在一次決策中，實現(xiàn)值不可能既超過目標值又未達到目標值，故有d＋×d－＝0,并規(guī)定d＋≥0,d－≥0當完成或超額完成規(guī)定的指標則表示：d＋≥0,d－＝0當未完成規(guī)定的指標則表示：d＋＝0,d－≥0當恰好完成指標時則表示：d＋＝0,d－＝0目標規(guī)劃的數(shù)學(xué)模型二.目標約束和絕對約束引入了目標值和正、負偏差變量后，就對某一問題有了新的限制，既目標約束。目標約束即可對原目標函數(shù)起作用，也可對原約束起作用。目標約束是目標規(guī)劃中特有的，是軟約束。絕對約束(系統(tǒng)約束)是指必須嚴格滿足的等式或不等式約束。如線性規(guī)劃中的所有約束條件都是絕對約束，否則無可行解。所以，絕對約束是硬約束。目標規(guī)劃的數(shù)學(xué)模型例如：在例一中，規(guī)定Z1的目標值為50000,正、負偏差為d＋、d－,則目標函數(shù)可以轉(zhuǎn)換為目標約束，既:50000120701121=-+++-ddxx若規(guī)定3600的鋼材必須用完，原式9x1+4x2≤3600變?yōu)?600494421=-+++-ddxx第二節(jié)目標規(guī)劃的數(shù)學(xué)模型引入正負偏差變量，對各個目標建立目標約束(軟約束)1.目標約束表示例：甲乙產(chǎn)品的最優(yōu)生產(chǎn)計劃。產(chǎn)品資源甲乙現(xiàn)有資源設(shè)備A2016設(shè)備B0210設(shè)備C3432單位利潤35根據(jù)市場需求/合同規(guī)定：希望盡量擴大甲產(chǎn)品減少乙產(chǎn)品產(chǎn)量。又增加二個目標：

maxZ1=3x1+5x2

maxZ2=x1minZ3=x22x1≤162x2≤103x1+4x2≤32

x1，x2≥0

第二節(jié)目標規(guī)劃的數(shù)學(xué)模型要求：目標一是利潤最大，擬定利潤目標是30；目標二是減少乙產(chǎn)品產(chǎn)量但希望不低于4件；目標三是甲產(chǎn)品產(chǎn)量希望不少于6件；對各目標引入正、負偏差變量：3x1+5x2+d1--d1+=30x2

+d2--d2+=4x1+d3–-d3+=6目標規(guī)劃的數(shù)學(xué)模型三.優(yōu)先因子(優(yōu)先等級)與優(yōu)先權(quán)系數(shù)目標等級化:將目標按重要性程度不同依次分成一級目標、二級目標…..。最次要的目標放在次要的等級中。(1)對同一目標而言，若有幾個決策方案都能使其達到，可認為這些方案就這個目標而言都是最優(yōu)方案；若達不到，則與目標差距越小的越好。(2)不同級別的目標的重要性是不可比的。即較高級別的目標沒有達到的損失，任何較低級別目標上的收獲不可彌補。故在判斷最優(yōu)方案時，首先從較高級別的目標達到的程度來決策，然后再其次級目標的判斷。(3)同一級別的目標可以是多個。各自之間的重要程度可用數(shù)量（權(quán)數(shù)）來描述。因此，同一級別的目標的其中一個的損失，可有其余目標的適當收獲來彌補。目標規(guī)劃的數(shù)學(xué)模型三.優(yōu)先因子(優(yōu)先等級)與優(yōu)先權(quán)系數(shù)優(yōu)先因子Pk是將決策目標按其重要程度排序并表示出來。P1>>P2>>…>>Pk>>Pk+1>>…>>PK，k=1,2…,K。表示Pk比Pk+1有更大的優(yōu)先權(quán)。即首先保證P1級目標的實現(xiàn)，這時可不考慮次級目標；而P2級目標是在實現(xiàn)P1級目標的基礎(chǔ)上考慮的；依此類推。若要區(qū)別具有相同優(yōu)先因子的兩個目標的差別，這時可分別賦予它們不同的權(quán)系數(shù)ωj,這些都由決策者按具體情況而定。目標規(guī)劃的數(shù)學(xué)模型四.達成函數(shù)(即目標規(guī)劃中的目標函數(shù))目標規(guī)劃的目標函數(shù)(準則函數(shù))是按各目標約束的正、負偏差變量和賦予相應(yīng)的優(yōu)先因子及權(quán)系數(shù)而構(gòu)造的。當每一目標值確定后，決策者的要求是盡可能縮小偏離目標值。因此目標規(guī)劃的目標函數(shù)只能是minZ=f(d＋、d－)。一般說來，有以下三種情況，但只能出現(xiàn)其中之一：(1)要求恰好達到規(guī)定的目標值，即正、負偏差變量要盡可能小，則minZ=f(d＋＋d－)。(2)要求不超過目標值，即允許達不到目標值，也就是正偏差變量盡可能小，則minZ=f(d＋)。(3)要求超過目標值，即超過量不限，但不低于目標值，也就是負偏差變量盡可能小，則minZ=f(d－)。對由絕對約束轉(zhuǎn)化而來的目標函數(shù)，也照上述處理即可。例：甲乙產(chǎn)品的最優(yōu)生產(chǎn)計劃。產(chǎn)品資源甲乙現(xiàn)有資源設(shè)備A2016設(shè)備B0210設(shè)備C3432單位利潤35根據(jù)市場需求/合同規(guī)定：希望盡量擴大甲產(chǎn)品減少乙產(chǎn)品產(chǎn)量。又增加二個目標：

maxZ1=3x1+5x2

maxZ2=x1minZ3=x22x1≤162x2≤103x1+4x2≤32

x1，x2≥0

第二節(jié)目標規(guī)劃的數(shù)學(xué)模型例如P1級目標實現(xiàn)利潤至少30元；P2級目標是甲乙產(chǎn)品的產(chǎn)量假設(shè)：乙產(chǎn)品產(chǎn)量不少于4件比甲產(chǎn)品產(chǎn)量不少于6件更重要，取其權(quán)重為2minG=P1d1-+P2(2d2-+d3-

)3x1+5x2+d1--d1+=30

x2

+d2--d2+=4

x1+d3--d3+=6x1,x2,dk-,dk+≥0(k=1,2,3)目標規(guī)劃的數(shù)學(xué)模型五.多目標規(guī)劃的解(1)若多目標規(guī)劃問題的解能使所有的目標都達到，就稱該解為多目標規(guī)劃的最優(yōu)解；(2)若解只能滿足部分目標，就稱該解為多目標規(guī)劃的次優(yōu)解；(3)若找不到滿足任何一個目標的解，就稱該問題為無解。(4)前面的目標可以保證實現(xiàn)或部分實現(xiàn)，而后面的目標就不一定能保證實現(xiàn)或部分實現(xiàn)，有些可能就不能實現(xiàn)，就稱該解為多目標規(guī)劃的滿意解(具有層次意義的解)單目標規(guī)劃例5-2:某工廠生產(chǎn)A，B兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下。實現(xiàn)目標利潤為140萬元的最優(yōu)生產(chǎn)方案AB可用量設(shè)備(臺時)4260原材料(KG)2448利潤(萬元)86從決策者的角度看，他希望超過利潤目標值，若達不到，也希望盡可能接近，即負偏差最小33-+0,,0,21ddxx￡+484221xx￡+602421xx=+-+-+1406821ddxx?????íìst=-mindZ級別相等的多目標規(guī)劃例5-3：若上例中假設(shè)決策者根據(jù)市場預(yù)測，產(chǎn)品A的銷售量有下降的趨勢，故考慮實現(xiàn)下列兩個目標：(1)實現(xiàn)利潤目標122萬元(2)產(chǎn)品A的產(chǎn)量不多于10分析:兩個目標級別相等，即兩個目標的重要程度一樣，不存在誰優(yōu)先的問題設(shè)d＋，d-分別為超過目標值的部分，以及未完成目標值的部分，于是兩個目標可以等價表示為：10122681211121=-+=-+++-+-ddxddxx級別相等的多目標規(guī)劃x1=10，x2=7，d－1＝0，d+2＝0，利潤為122，兩個目標均已經(jīng)實現(xiàn)?????íì3￡+￡+=-+=-+++=+-+-+-+-+-0,,,,,4842602410122682211212121221112121ddddxxxxxxddxddxxstddMinZ具有優(yōu)先級別的多目標規(guī)劃對于多個目標，如果有一定的優(yōu)先順序，即第一位重要的目標，其優(yōu)先因子為P1，第二位重要的目標，其優(yōu)先因子為P2，并規(guī)定P1>>P2優(yōu)先保證P1級目標的實現(xiàn)，此時不考慮次級目標；次級目標P2在實現(xiàn)了P1級目標的基礎(chǔ)上再予以考慮。如果無法實現(xiàn)P1目標，則不考慮P2目標能否取得最優(yōu)若有k個不同優(yōu)先順序的目標，則有P1>>P2>>…>>Pk將權(quán)重與偏差相乘構(gòu)成目標函數(shù)，這樣，權(quán)重越大，越先迫使相應(yīng)的偏差等于零，這樣可保證優(yōu)先級高的目標首先實現(xiàn)。具有優(yōu)先級別的多目標規(guī)劃例5-4：若上例中決策者擬訂下列經(jīng)營目標，并確定了目標之間的優(yōu)先順序P1級目標：充分利用設(shè)備有效臺時，不加班；P2級目標：產(chǎn)品B的產(chǎn)量不多于4；P3級目標：實現(xiàn)利潤值130萬元分析：題目有三個目標層次，包含三個目標值。第一目標：P1(d1＋+d1-)第二目標：P2d2＋第二目標：P3d3-?????íì3￡+=-++=-+=-+++++=+-+-+-+--++-0,,,48421306846024)(2121332122211213322111iiddxxxxddxxddxddxxstdPdPddPMinZ具有優(yōu)先級別的多目標規(guī)劃例5-5：某廠計劃下一個生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。制定生產(chǎn)計劃，滿足下列目標：P1級目標：完成或超額完成利潤指標50000元；P2級目標：產(chǎn)品甲不超過200件，產(chǎn)品乙不低于250件；P3級目標：現(xiàn)有鋼材3600噸必須用完12070單件利潤3000103設(shè)備臺時200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗具有優(yōu)先級別的多目標規(guī)劃分析：題目有三個目標層次，包含四個目標值。第一目標：P1d1-第二目標：有兩個要求即甲d2＋，乙d3-，但兩個具有相同的優(yōu)先因子，需要確定權(quán)系數(shù)。本題可用單件利潤比作為權(quán)系數(shù)即70:120，化簡為7:12，P2(7d2＋+12d3

-)第三目標：P3(d4＋+d4-)?????????íì3￡+￡+=-++=-+=-+=-++++++=+-+-+-+-+-+--+-0,,,30001032000543600492502005000012070)()127(2121214421332221112144332211iiddxxxxxxddxxddxddxddxxstddPddPdPMinZ六、目標規(guī)劃數(shù)學(xué)模型的一般形式?????????íì-=3-=3-=3=￡-==-+-+=+-=+-=++-=-=????)55(3,2,1,0,)45(,,1,0)35(,,1,),()25(,,1,)15()(min1111kddnjxmibxaKkgddxcddPzkkjijnjijkkkjnjkjklkkKklkLllLLL滿足約束條件：目標函數(shù)：ww其中Pl為優(yōu)先因子，w-lk，w+lk為優(yōu)先系數(shù)七、建模的步驟根據(jù)要研究的問題所提出的各目標與條件，確定目標值，列出目標約束與絕對約束；可根據(jù)決策者的需要，將某些或全部絕對約束轉(zhuǎn)化為目標約束。這時只需要給絕對約束加上負偏差變量和減去正偏差變量即可。給各目標賦予相應(yīng)的優(yōu)先因子

Pk對同一優(yōu)先等級中的各偏差變量，若需要可按其重要程度的不同，賦予相應(yīng)的權(quán)系數(shù)

ωkl+和ωkl-。根據(jù)決策者的要求，構(gòu)造一個由優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量組成的，要求實現(xiàn)極小化的目標函數(shù)，即達成函數(shù)。線性規(guī)劃與目標規(guī)劃線性規(guī)劃LP目標規(guī)劃GP目標函數(shù)min,max系數(shù)可正負min,偏差變量系數(shù)≥0變量xi,xs,xa

xi,xs,xa

,

d約束條件系統(tǒng)約束(絕對約束)目標約束系統(tǒng)約束解最優(yōu)滿意第三節(jié)目標規(guī)劃的圖解法F2x1=162x2=10BCx14A103x1+4x2=326x20D2642EGH滿意解：x1=5,x2=473第三節(jié)目標規(guī)劃的圖解法目標規(guī)劃的圖解法首先，按照絕對約束畫出可行域，其次，不考慮正負偏差變量，畫出目標約束的邊界線，最后。按優(yōu)先級別和權(quán)重依次分析各級目標。F2x1=162x2=10BCx14A103x1+4x2=326x20D2642EGH滿意解：x1=5,x2=474?????íì=33￡+=-++=-++++=-+-+-+---+)2.1(0,08

2

102

5.621210)(min21212221112122111lddxxxddxxddxxdPddPZll012345678123456⑴⑵⑶Ax2

x1BCB(0.6250,4.6875)C(0,5.2083)，B、C線段上的所有點均是該問題的解(無窮多最優(yōu)解)。第三節(jié)目標規(guī)劃的圖解法???????íì=33=-+=-+=-++=-+++++=-+-+-+-+-+-+++-)4.3.2.1(0,,010060140225001230)5.2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll

0x2

0(1)x11401201008060402020406080100(2)(3)(4)ABCD結(jié)論：C(60,58.3)為所求的滿意解。目標規(guī)劃的圖解法目標規(guī)劃的圖解法圖解法解題步驟如下：1.確定各約束條件的可行域，即將所有約束條件(包括目標約束和絕對約束，暫不考慮正負偏差變量)在坐標平面上表示出來；2.在目標約束所代表的邊界線上，用箭頭標出正、負偏差變量值增大的方向；3.求滿足最高優(yōu)先等級目標的解；4.轉(zhuǎn)到下一個優(yōu)先等級的目標，在不破壞所有較高優(yōu)先等級目標的前提下，求出該優(yōu)先等級目標的解；5.重復(fù)4，直到所有優(yōu)先等級目標都已審查完畢為止；6.確定最優(yōu)解和滿意解。第四節(jié)目標規(guī)劃的單純形法目標規(guī)劃與線性規(guī)劃的數(shù)學(xué)模型的結(jié)構(gòu)相似可用前述單純形算法求解目標規(guī)劃模型：

將優(yōu)先等級Pk視為正常數(shù)(大Ｍ法)正負偏差變量dk+、dk-視為松弛變量以負偏差變量dk-為初始基變量，建立初始單純形表檢驗數(shù)的計算與LP單純形法相同，即

j=cj-CBiPj最優(yōu)性判別準則類似于LP的單純形算法：檢驗數(shù)一般是各優(yōu)先等級因子的代數(shù)和判斷檢驗數(shù)的正負和大小

78目標規(guī)劃的單純形法目標規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)形式上沒有本質(zhì)的區(qū)別，所以可用單純形法求解。但要考慮目標規(guī)劃的數(shù)學(xué)模型一些特點，作以下規(guī)定：(1)因目標規(guī)劃問題的目標函數(shù)都是求最小化，所以以cj-zj≥0，j=1,2,…，n為最優(yōu)準則。(2)因非基變量的檢驗數(shù)中含有不同等級的優(yōu)先因子，即KknjPazckkjjj,,2,1;,,2,1LL===-?因P1>>P2>>…>>PK；從每個檢驗數(shù)的整體來看：檢驗數(shù)的正、負首先決定于P1的系數(shù)α1j的正、負。若α1j=0，這時此檢驗數(shù)的正、負就決定于P2的系數(shù)α2j的正、負。例見表4-13.目標規(guī)劃的單純形法例：用單純形法求解下列目標規(guī)劃問題

MinZ=P1

d1-+P2(d2-+d2+)+P3(3d3-+5d4-)5x1+4x2

+d1--d1+=204x1+3x2

+d2--d2+=24x1

+d3--d3+=3-x1

+x2

+d4--d4+=2x1

,x2

,dk-,dk+≥0目標規(guī)劃的單純形法cj

值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+檢驗數(shù)λjP1P2P300P10P2P23P305P3020541-10000002443001-1000031000001-1002-110000001-1d1-d2-d3-d4--5-401000-4-322-535463-檢驗數(shù)λjP1P2P3d1-d2-x1d4-P1P205P331000001-1005041-100-55001203001-1-440050100001-11-10-40105-50-324-4-5-25513--P1P23P35P3目標規(guī)劃的單純形法cj00P10P2P23P305P30

值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+檢驗數(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--檢驗數(shù)λjP1P2P3d3+d1+x1d4-0005P3100-1/4-115/4-5/40000303/4001/4-1/4-1100613/4001/4-1/40000807/4001/4-1/4001-10100011-35/4-5/45/4354-832/7目標規(guī)劃的單純形法cj00P10P2P23P305P30

值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+檢驗數(shù)λjP1P2P3x2d1+x1d4-0005P3401001/3-1/3-4/34/3001100-114/3-4/3-1/31/3003100000-110010000-1/31/37/3-7/31-100100115/3-5/3-26/335/35---3檢驗數(shù)λjP1P2P3x2d1+x1d3-0003P33/70000-1/71/71-13/7-3/732/701001/7-1/7004/7-4/778/700-119/7-9/7001/7-1/718/710001/7-1/700-3/73/7001000113/7-3/7326/79/7目標規(guī)劃的單純形法例：用單純形法求解下列目標規(guī)劃問題

minZ=P1d1++P2(d2-+d2+)+P3d3-2x1+x2

+x3=11x1-x2+d1-

-d1+=0x1+2x2

+d2-

-d2+=108x1

+10x2+d3-

-d3+=56xi,dk-,dk+

≥0目標規(guī)劃的單純形法第五節(jié)目標規(guī)劃的應(yīng)用案例一、無窮多滿意解解：設(shè)x1,x2表示A、B產(chǎn)品的產(chǎn)量。兩個等級的目標：P1：充分利用電量限額，正負偏差之和為最小目標達成函數(shù)目標約束條件P2：利潤額希望不能低于100元，負偏差最小目標達成函數(shù)目標約束條件計劃生產(chǎn)兩種產(chǎn)品，首先要充分利用設(shè)備工時而不加班；然后考慮利潤不低于100元。問應(yīng)如何制定產(chǎn)品A、B的產(chǎn)量。1042A24BDx26810x1第五節(jié)目標規(guī)劃的應(yīng)用案例一、無窮多滿意解由于材料供應(yīng)限量為8單位，所以有系統(tǒng)約束條件，如下該問題的目標規(guī)劃模型如下，圖解法求解如圖CG105第五節(jié)目標規(guī)劃的應(yīng)用案例二、加班時間問題例：某音像店有5名全職售貨員和4名兼職售貨員，全職售貨員每月工作160小時，兼職售貨員每月工作80小時。根據(jù)記錄，全職每小時銷售CD25張，平均每小時工資15元，加班工資每小時22.5元。兼職售貨員每小時銷售CD10張，平均工資每小時10元，加班工資每小時10元?，F(xiàn)在預(yù)測下月CD銷售量為27500張，商店每周開門營業(yè)6天，所以可能要加班。每出售一張CD盈利1.5元。

商店經(jīng)理認為，保持穩(wěn)定的就業(yè)水平加上必要的加班，比不加班就業(yè)水平要好，但全職銷售員如果加班過多，就會因為疲勞過度而造成效率下降，因此不允許每月加班超過100小時，建立相應(yīng)的目標規(guī)劃模型。106第五節(jié)目標規(guī)劃的應(yīng)用案例二、加班時間問題首先，確定目標約束的優(yōu)先級。如下：P1：下月的CD銷售量達到27500張；P2：全職售貨員加班時間不超過100小時；P3：保持全體售貨員充分就業(yè)，對全職的要比兼職的加倍優(yōu)先考慮；P4：盡量減少加班時間，對兩種售貨員區(qū)別對待，權(quán)重由他們對利潤的貢獻而定。其次，建立目標約束函數(shù)（1）銷售目標約束，設(shè)全體全職售貨員下月的工作時間x1，全體兼職售貨員下月的工作時間x2；達不到銷售目標的偏差d1-，超過銷售目標的偏差d1+。

107第五節(jié)目標規(guī)劃的應(yīng)用案例二、加班時間問題

（2）正常工作時間約束。設(shè)全體全職售貨員下月的停工時間d2-，加班時間d2+

；全體兼職售貨員下月的停工時間d3-，加班時間d3+。（3）加班時間的限制。設(shè)全體全職售貨員下月的加班不足100小時的偏差d4-，加班超過100小時的偏差d4+。兩類售貨員區(qū)別對待，權(quán)重比d2+:d3+=1:3，另一加班目標約束為108第五節(jié)目標規(guī)劃的應(yīng)用案例二、加班時間問題

第三，按目標的優(yōu)先級，寫出相應(yīng)的目標規(guī)劃模型：運用LINGO軟件求解得x1=900,x2=500，下月共銷售CD盤27500張，獲利27500×1.5-800×15-100×22.5-500×10=22000。109第五節(jié)目標規(guī)劃的應(yīng)用案例三、目標管理方案

例：某公司準備生產(chǎn)甲、乙產(chǎn)品，據(jù)市場調(diào)查：甲產(chǎn)品的最大市場需求3臺，乙產(chǎn)品的最大市場需求2臺。

在滿足現(xiàn)有電力資源嚴格供給約束的前提下，該廠長考慮兩個目標：一是總利潤不低于3600元；二是充分利用設(shè)備臺時，但盡量少加班。問應(yīng)如何制定產(chǎn)品甲、乙的產(chǎn)量，試建立其目標規(guī)劃的數(shù)學(xué)模型。110第五節(jié)目標規(guī)劃的應(yīng)用案例三、目標管理方案

1.利潤期望優(yōu)先目標規(guī)劃數(shù)學(xué)模型：運用圖解法進行求解FECx1=8x2=65x1+5x2=600x12410126ABx20842D10Gx1=8,x2

=3111第五節(jié)目標規(guī)劃的應(yīng)用案例1.利潤期望優(yōu)先

總利潤：3600單位甲：300單位乙：400生產(chǎn)部目標甲產(chǎn)品的產(chǎn)量：8，成本：900乙產(chǎn)品的產(chǎn)量：3，成本：1400技術(shù)部目標甲的設(shè)備單耗25，需降低5工時乙的設(shè)備單耗50，需降低10工時

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

乙產(chǎn)品的設(shè)備消耗降為60(1-17%)=50。112第五節(jié)目標規(guī)劃的應(yīng)用案例三、目標管理方案

2.設(shè)備工時優(yōu)先目標規(guī)劃數(shù)學(xué)模型：運用圖解法進行求解FECx1=8x2=65x1+5x2=600x12410126ABx20842D10Gx1=8,x2

=2113第五節(jié)目標規(guī)劃的應(yīng)用案例2.設(shè)備工時優(yōu)先

總利潤：3600單位甲：337.5單位乙：450

生產(chǎn)部目標甲產(chǎn)品的產(chǎn)量：8，成本：862.5乙產(chǎn)品的產(chǎn)量：2，成本：1350技術(shù)部目標保證設(shè)備的正常運行甲的設(shè)備單耗30，乙的單耗60

銷售部目標甲產(chǎn)品的銷量：8，單價：1200乙產(chǎn)品的銷量：2，單價：1800滿意解：x1=8,x2=2利潤總額300

8+400

2=3200，目標：3600不能提價，就必須降低成本以增加利潤，利潤增長率為12.5%甲產(chǎn)品的成本需要降為1200-300

(1+12.5%)=862.5元/臺，降低幅度4.2%乙產(chǎn)品的成本需要降為1800-400(1+12.5%)=1350元/臺，降低幅度3.6%114第五節(jié)目標規(guī)劃的應(yīng)用例5-10：已知一個生產(chǎn)計劃的線性規(guī)劃模型，經(jīng)營目標：P1：總利潤不低于40P2：充分利用設(shè)備能力，且盡量不超過140如何安排生產(chǎn)？產(chǎn)品資源甲乙現(xiàn)有資源設(shè)備2010140售價108成本56最大需求量610minZ=P1d1-+P2(d2-+d2+)x1≤6x2≤105x1+2x2+d1--d1+=4020x1+10x2+d2--d2+=140x1,x2,d1-,d1+,d2-,d2+≥0x1x2x1=6x2=10③④d1+d1-d2+d2-CBD(6,5)滿意解:x1=6，x2=5設(shè)備能力:需求206+105=170，實際140實現(xiàn)目標P1和P2，降低甲乙產(chǎn)品的設(shè)備消耗:降低率(170-140)/170=18%，甲產(chǎn)品的設(shè)備消耗降為20(1-18%)=16.4，乙產(chǎn)品的設(shè)備消耗降為10(1-18%)=8.2?？偫麧櫍?0單位甲：5單位乙：2生產(chǎn)部目標甲產(chǎn)品的產(chǎn)量：6，成本：5乙產(chǎn)品的產(chǎn)量：5，成本：6技術(shù)部目標甲產(chǎn)品的設(shè)備單耗：16.4乙產(chǎn)品的設(shè)備單耗：8.2銷售部目標甲產(chǎn)品的銷量：6，單價：10乙產(chǎn)品的銷量：5，單價：8第五節(jié)目標規(guī)劃的應(yīng)用降低設(shè)備消耗很困難，則調(diào)整經(jīng)營目標的次序P1：充分利用設(shè)備能力，且盡量不超過140，P2：總利潤不低于40如何安排生產(chǎn)？產(chǎn)品資源甲乙現(xiàn)有資源設(shè)備2010140售價108成本56最大需求量610minZ=P2d1-+P1(d2-+d2+)x1≤6①x2≤10②5x1+2x2+d1--d1+=40③20x1+10x2+d2--d2+=140④x1,x2,d1-,d1+,d2-,d2+≥0x1x2x1=6x2=10④A(6,2)③d1+d1-d2+d2-E第五節(jié)目標規(guī)劃的應(yīng)用滿意解：x1=6,x2=2利潤指標：實際5×6+2×2=34，期望40實現(xiàn)目標P1和P2，增加甲乙產(chǎn)品的單位利潤:增長率(40-34)/34=18%產(chǎn)品售價由市場決定，為提高利潤，應(yīng)從降低成本入手：甲產(chǎn)品的成本由5降為10-5(1+18%)=4.12,乙產(chǎn)品的成本由6降為8-2(1+18%)=5.63?？偫麧櫍?0單位甲：5.88單位乙：2.36生產(chǎn)部目標甲產(chǎn)品的產(chǎn)量：6，成本：4.12乙產(chǎn)品的產(chǎn)量：2，成本：5.63技術(shù)部目標甲產(chǎn)品的設(shè)備單耗：20乙產(chǎn)品的設(shè)備單耗：10銷售部目標甲產(chǎn)品的銷量：6，單價：10乙產(chǎn)品的銷量：2，單價：8第五節(jié)目標規(guī)劃的應(yīng)用例：某副食品批發(fā)店預(yù)測某商品今后4月的購進與售出價格如表。假設(shè):(1)該商品供不應(yīng)求，最大銷量受倉庫容量限制；(2)正常庫容3噸，機動庫容2噸；(3)月初批發(fā)銷貨，月中采購進貨，進貨所需資金完全來銷售收入；(4)1月初庫存量2噸，成本2.5千元/噸，該月初無現(xiàn)金。經(jīng)營目標：(1)每月都使用正常庫容，盡量不超容；(2)每月下旬都應(yīng)儲備1千元以備急用；(3)4個月總盈利最大。月份1234成本(購價+庫存)2.62.52.72.8售價2.92.73.13.3第五節(jié)目標規(guī)劃的應(yīng)用決策變量：xj

第j月的采購量，yj

第j月的銷售量絕對約束條件各月銷量約束:月初售貨，各月銷量不多于其期初庫存量。1月y1

≤22月y2

≤2–y1

+x1

→

y1

+y2

–x1

≤23月y3

≤2–y1

+x1

–y2

+x2

→y1+y2+y3

–x1

–x2

≤24月y4≤2–y1

+x1

–y2+x2–y3+x3→y1+y2