線性規(guī)劃數(shù)學(xué)模型課件

目標(biāo)規(guī)劃本章內(nèi)容重點(diǎn)目標(biāo)規(guī)劃模型目標(biāo)規(guī)劃的幾何意義目標(biāo)規(guī)劃的單純形方法目標(biāo)規(guī)劃本章內(nèi)容重點(diǎn)問題的提出線性規(guī)劃只研究在滿足一定條件下，單一目標(biāo)函數(shù)取得最優(yōu)解，而在企業(yè)管理中，經(jīng)常遇到多目標(biāo)決策問題，如擬訂生產(chǎn)計(jì)劃時(shí)，不僅考慮總產(chǎn)值，同時(shí)要考慮利潤，產(chǎn)品質(zhì)量和設(shè)備利用率等。這些指標(biāo)之間的重要程度(即優(yōu)先順序)也不相同，有些目標(biāo)之間往往相互發(fā)生矛盾。線性規(guī)劃致力于某個(gè)目標(biāo)函數(shù)的最優(yōu)解，這個(gè)最優(yōu)解若是超過了實(shí)際的需要，很可能是以過分地消耗了約束條件中的某些資源作為代價(jià)。問題的提出線性規(guī)劃只研究在滿足一定條件下，單一目標(biāo)函數(shù)取得線性規(guī)劃把各個(gè)約束條件的重要性都不分主次地等同看待，這也不符合實(shí)際情況。求解線性規(guī)劃問題，首先要求約束條件必須相容，如果約束條件中，由于人力，設(shè)備等資源條件的限制，使約束條件之間出現(xiàn)了矛盾，就得不到問題的可行解，但生產(chǎn)還得繼續(xù)進(jìn)行，這將給人們進(jìn)一步應(yīng)用線性規(guī)劃方法帶來困難。為了彌補(bǔ)線性規(guī)劃問題的局限性，解決有限資源和計(jì)劃指標(biāo)之間的矛盾，在線性規(guī)劃基礎(chǔ)上，建立目標(biāo)規(guī)劃方法，從而使一些線性規(guī)劃無法解決的問題得到滿意的解答。問題的提出線性規(guī)劃把各個(gè)約束條件的重要性都不分主次地等同看待，這也不符目標(biāo)規(guī)劃與線性規(guī)劃的比較線性規(guī)劃只討論一個(gè)線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題；而目標(biāo)規(guī)劃是多個(gè)目標(biāo)決策，可求得更切合實(shí)際的解。線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個(gè)滿意解。線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目標(biāo)規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。線性規(guī)劃的最優(yōu)解是絕對意義下的最優(yōu)，但需花去大量的人力、物力、財(cái)力才能得到；實(shí)際過程中，只要求得滿意解，就能滿足需要(或更能滿足需要)。目標(biāo)規(guī)劃與線性規(guī)劃的比較線性規(guī)劃只討論一個(gè)線性目標(biāo)函數(shù)在一組目標(biāo)規(guī)劃與線性規(guī)劃的比較例5-1：某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計(jì)劃，使獲得的利潤最大？同時(shí)，根據(jù)市場預(yù)測，甲的銷路不是太好，應(yīng)盡可能少生產(chǎn)；乙的銷路較好，可以擴(kuò)大生產(chǎn)。試建立此問題的數(shù)學(xué)模型。12070單件利潤3000103設(shè)備臺時(shí)200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗目標(biāo)規(guī)劃與線性規(guī)劃的比較例5-1：某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)目標(biāo)規(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目標(biāo)規(guī)劃數(shù)學(xué)模型設(shè)：甲產(chǎn)品x1，乙產(chǎn)品x2根據(jù)市場預(yù)測目標(biāo)規(guī)劃的數(shù)學(xué)模型1.目標(biāo)值和偏差變量目標(biāo)規(guī)劃通過引入目標(biāo)值和偏差變量，可以將目標(biāo)函數(shù)轉(zhuǎn)化為目標(biāo)約束。目標(biāo)值：是指預(yù)先給定的某個(gè)目標(biāo)的一個(gè)期望值。實(shí)現(xiàn)值或決策值：是指當(dāng)決策變量xj選定以后，目標(biāo)函數(shù)的對應(yīng)值。偏差變量(事先無法確定的未知數(shù))：是指實(shí)現(xiàn)值和目標(biāo)值之間的差異,記為d。正偏差變量:表示實(shí)現(xiàn)值超過目標(biāo)值的部分，記為d＋。負(fù)偏差變量:表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分，記為d－。目標(biāo)規(guī)劃的數(shù)學(xué)模型1.目標(biāo)值和偏差變量目標(biāo)規(guī)劃的數(shù)學(xué)模型在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值，故有d＋×d－＝0,并規(guī)定d＋≥0,d－≥0當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：d＋≥0,d－＝0當(dāng)未完成規(guī)定的指標(biāo)則表示：d＋＝0,d－≥0當(dāng)恰好完成指標(biāo)時(shí)則表示：d＋＝0,d－＝0目標(biāo)規(guī)劃的數(shù)學(xué)模型在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未目標(biāo)規(guī)劃的數(shù)學(xué)模型2.目標(biāo)約束和絕對約束引入了目標(biāo)值和正、負(fù)偏差變量后，就對某一問題有了新的限制，既目標(biāo)約束。目標(biāo)約束即可對原目標(biāo)函數(shù)起作用，也可對原約束起作用。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。絕對約束(系統(tǒng)約束)是指必須嚴(yán)格滿足的等式或不等式約束。如線性規(guī)劃中的所有約束條件都是絕對約束，否則無可行解。所以，絕對約束是硬約束。目標(biāo)規(guī)劃的數(shù)學(xué)模型2.目標(biāo)約束和絕對約束目標(biāo)規(guī)劃的數(shù)學(xué)模型例如：在例一中，規(guī)定Z1的目標(biāo)值為50000,正、負(fù)偏差為d＋、d－,則目標(biāo)函數(shù)可以轉(zhuǎn)換為目標(biāo)約束，既:50000120701121=-+++-ddxx若規(guī)定3600的鋼材必須用完，原式9x1+4x2≤3600變?yōu)?600494421=-+++-ddxx目標(biāo)規(guī)劃的數(shù)學(xué)模型例如：在例一中，規(guī)定Z1的目標(biāo)值為500目標(biāo)規(guī)劃的數(shù)學(xué)模型3.優(yōu)先因子(優(yōu)先等級)與優(yōu)先權(quán)系數(shù)目標(biāo)等級化:將目標(biāo)按重要性程度不同依次分成一級目標(biāo)、二級目標(biāo)…..。最次要的目標(biāo)放在次要的等級中。(1)對同一目標(biāo)而言，若有幾個(gè)決策方案都能使其達(dá)到，可認(rèn)為這些方案就這個(gè)目標(biāo)而言都是最優(yōu)方案；若達(dá)不到，則與目標(biāo)差距越小的越好。(2)不同級別的目標(biāo)的重要性是不可比的。即較高級別的目標(biāo)沒有達(dá)到的損失，任何較低級別目標(biāo)上的收獲不可彌補(bǔ)。故在判斷最優(yōu)方案時(shí)，首先從較高級別的目標(biāo)達(dá)到的程度來決策，然后再其次級目標(biāo)的判斷。(3)同一級別的目標(biāo)可以是多個(gè)。各自之間的重要程度可用數(shù)量（權(quán)數(shù)）來描述。因此，同一級別的目標(biāo)的其中一個(gè)的損失，可有其余目標(biāo)的適當(dāng)收獲來彌補(bǔ)。目標(biāo)規(guī)劃的數(shù)學(xué)模型3.優(yōu)先因子(優(yōu)先等級)與優(yōu)先權(quán)系數(shù)目標(biāo)規(guī)劃的數(shù)學(xué)模型3.優(yōu)先因子(優(yōu)先等級)與優(yōu)先權(quán)系數(shù)優(yōu)先因子Pk是將決策目標(biāo)按其重要程度排序并表示出來。P1>>P2>>…>>Pk>>Pk+1>>…>>PK，k=1,2…,K。表示Pk比Pk+1有更大的優(yōu)先權(quán)。即首先保證P1級目標(biāo)的實(shí)現(xiàn)，這時(shí)可不考慮次級目標(biāo)；而P2級目標(biāo)是在實(shí)現(xiàn)P1級目標(biāo)的基礎(chǔ)上考慮的；依此類推。若要區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，這時(shí)可分別賦予它們不同的權(quán)系數(shù)ωj,這些都由決策者按具體情況而定。目標(biāo)規(guī)劃的數(shù)學(xué)模型3.優(yōu)先因子(優(yōu)先等級)與優(yōu)先權(quán)系數(shù)目標(biāo)規(guī)劃的數(shù)學(xué)模型4.達(dá)成函數(shù)(即目標(biāo)規(guī)劃中的目標(biāo)函數(shù))目標(biāo)規(guī)劃的目標(biāo)函數(shù)(準(zhǔn)則函數(shù))是按各目標(biāo)約束的正、負(fù)偏差變量和賦予相應(yīng)的優(yōu)先因子及權(quán)系數(shù)而構(gòu)造的。當(dāng)每一目標(biāo)值確定后，決策者的要求是盡可能縮小偏離目標(biāo)值。因此目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是minZ=f(d＋、d－)。一般說來，有以下三種情況，但只能出現(xiàn)其中之一：(1)要求恰好達(dá)到規(guī)定的目標(biāo)值，即正、負(fù)偏差變量要盡可能小，則minZ=f(d＋＋d－)。(2)要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，也就是正偏差變量盡可能小，則minZ=f(d＋)。(3)要求超過目標(biāo)值，即超過量不限，但不低于目標(biāo)值，也就是負(fù)偏差變量盡可能小，則minZ=f(d－)。對由絕對約束轉(zhuǎn)化而來的目標(biāo)函數(shù)，也照上述處理即可。目標(biāo)規(guī)劃的數(shù)學(xué)模型4.達(dá)成函數(shù)(即目標(biāo)規(guī)劃中的目標(biāo)函數(shù))目標(biāo)規(guī)劃的數(shù)學(xué)模型5.多目標(biāo)規(guī)劃的解(1)若多目標(biāo)規(guī)劃問題的解能使所有的目標(biāo)都達(dá)到，就稱該解為多目標(biāo)規(guī)劃的最優(yōu)解；(2)若解只能滿足部分目標(biāo)，就稱該解為多目標(biāo)規(guī)劃的次優(yōu)解；(3)若找不到滿足任何一個(gè)目標(biāo)的解，就稱該問題為無解。(4)前面的目標(biāo)可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，有些可能就不能實(shí)現(xiàn)，就稱該解為多目標(biāo)規(guī)劃的滿意解(具有層次意義的解)目標(biāo)規(guī)劃的數(shù)學(xué)模型5.多目標(biāo)規(guī)劃的解單目標(biāo)規(guī)劃例5-2:某工廠生產(chǎn)A，B兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下。實(shí)現(xiàn)目標(biāo)利潤為140萬元的最優(yōu)生產(chǎn)方案AB可用量設(shè)備(臺時(shí))4260原材料(KG)2448利潤(萬元)86從決策者的角度看，他希望超過利潤目標(biāo)值，若達(dá)不到，也希望盡可能接近，即負(fù)偏差最小33-+0,,0,21ddxx￡+484221xx￡+602421xx=+-+-+1406821ddxx?????íìst=-mindZ單目標(biāo)規(guī)劃例5-2:某工廠生產(chǎn)A，B兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下。級別相等的多目標(biāo)規(guī)劃例5-3：若上例中假設(shè)決策者根據(jù)市場預(yù)測，產(chǎn)品A的銷售量有下降的趨勢，故考慮實(shí)現(xiàn)下列兩個(gè)目標(biāo)：(1)實(shí)現(xiàn)利潤目標(biāo)122萬元(2)產(chǎn)品A的產(chǎn)量不多于10分析:兩個(gè)目標(biāo)級別相等，即兩個(gè)目標(biāo)的重要程度一樣，不存在誰優(yōu)先的問題設(shè)d＋，d-分別為超過目標(biāo)值的部分，以及未完成目標(biāo)值的部分，于是兩個(gè)目標(biāo)可以等價(jià)表示為：10122681211121=-+=-+++-+-ddxddxx級別相等的多目標(biāo)規(guī)劃例5-3：若上例中假設(shè)決策者根據(jù)市場預(yù)測級別相等的多目標(biāo)規(guī)劃x1=10，x2=7，d－1＝0，d+2＝0，利潤為122，兩個(gè)目標(biāo)均已經(jīng)實(shí)現(xiàn)?????íì3￡+￡+=-+=-+++=+-+-+-+-+-0,,,,,4842602410122682211212121221112121ddddxxxxxxddxddxxstddMinZ級別相等的多目標(biāo)規(guī)劃x1=10，x2=7，d－1＝0，d+2具有優(yōu)先級別的多目標(biāo)規(guī)劃對于多個(gè)目標(biāo)，如果有一定的優(yōu)先順序，即第一位重要的目標(biāo)，其優(yōu)先因子為P1，第二位重要的目標(biāo)，其優(yōu)先因子為P2，并規(guī)定P1>>P2優(yōu)先保證P1級目標(biāo)的實(shí)現(xiàn)，此時(shí)不考慮次級目標(biāo)；次級目標(biāo)P2在實(shí)現(xiàn)了P1級目標(biāo)的基礎(chǔ)上再予以考慮。如果無法實(shí)現(xiàn)P1目標(biāo)，則不考慮P2目標(biāo)能否取得最優(yōu)若有k個(gè)不同優(yōu)先順序的目標(biāo)，則有P1>>P2>>…>>Pk將權(quán)重與偏差相乘構(gòu)成目標(biāo)函數(shù)，這樣，權(quán)重越大，越先迫使相應(yīng)的偏差等于零，這樣可保證優(yōu)先級高的目標(biāo)首先實(shí)現(xiàn)。具有優(yōu)先級別的多目標(biāo)規(guī)劃對于多個(gè)目標(biāo)，如果有一定的優(yōu)先順序，具有優(yōu)先級別的多目標(biāo)規(guī)劃例5-4：若上例中決策者擬訂下列經(jīng)營目標(biāo)，并確定了目標(biāo)之間的優(yōu)先順序P1級目標(biāo)：充分利用設(shè)備有效臺時(shí)，不加班；P2級目標(biāo)：產(chǎn)品B的產(chǎn)量不多于4；P3級目標(biāo)：實(shí)現(xiàn)利潤值130萬元分析：題目有三個(gè)目標(biāo)層次，包含三個(gè)目標(biāo)值。第一目標(biāo)：P1(d1＋+d1-)第二目標(biāo)：P2d2＋第二目標(biāo)：P3d3-?????íì3￡+=-++=-+=-+++++=+-+-+-+--++-0,,,48421306846024)(2121332122211213322111iiddxxxxddxxddxddxxstdPdPddPMinZ具有優(yōu)先級別的多目標(biāo)規(guī)劃例5-4：若上例中決策者擬訂下列經(jīng)營具有優(yōu)先級別的多目標(biāo)規(guī)劃例5-5：某廠計(jì)劃下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。制定生產(chǎn)計(jì)劃，滿足下列目標(biāo)：P1級目標(biāo)：完成或超額完成利潤指標(biāo)50000元；P2級目標(biāo)：產(chǎn)品甲不超過200件，產(chǎn)品乙不低于250件；P3級目標(biāo)：現(xiàn)有鋼材3600噸必須用完12070單件利潤3000103設(shè)備臺時(shí)200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗具有優(yōu)先級別的多目標(biāo)規(guī)劃例5-5：某廠計(jì)劃下一個(gè)生產(chǎn)周期內(nèi)生具有優(yōu)先級別的多目標(biāo)規(guī)劃分析：題目有三個(gè)目標(biāo)層次，包含四個(gè)目標(biāo)值。第一目標(biāo)：P1d1＋第二目標(biāo)：有兩個(gè)要求即甲d2＋，乙d3-，但兩個(gè)具有相同的優(yōu)先因子，需要確定權(quán)系數(shù)。本題可用單件利潤比作為權(quán)系數(shù)即70:120，化簡為7:12，P2(7d2＋+12d2-)第二目標(biāo)：P3(d4＋+d4-)?????????íì3￡+￡+=-++=-+=-+=-++++++=+-+-+-+-+-+--+-0,,,30001032000543600492502005000012070)()127(2121214421332221112144332211iiddxxxxxxddxxddxddxddxxstddPddPdPMinZ具有優(yōu)先級別的多目標(biāo)規(guī)劃分析：題目有三個(gè)目標(biāo)層次，包含四個(gè)目數(shù)學(xué)模型的一般形式?????????íì-=3-=3-=3=￡-==-+-+=+-=+-=++-=-=????)55(3,2,1,0,)45(,,1,0)35(,,1,),()25(,,1,)15()(min1111kddnjxmibxaKkgddxcddPzkkjijnjijkkkjnjkjklkkKklkLllLLL滿足約束條件：目標(biāo)函數(shù)：ww其中Pl為優(yōu)先因子，w-lk，w+lk為優(yōu)先系數(shù)數(shù)學(xué)模型的一般形式?????????íì-=3-=3-=3=建模的步驟根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對約束；可根據(jù)決策者的需要，將某些或全部絕對約束轉(zhuǎn)化為目標(biāo)約束。這時(shí)只需要給絕對約束加上負(fù)偏差變量和減去正偏差變量即可。給各目標(biāo)賦予相應(yīng)的優(yōu)先因子

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

ωkl+和ωkl-。根據(jù)決策者的要求，構(gòu)造一個(gè)由優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量組成的，要求實(shí)現(xiàn)極小化的目標(biāo)函數(shù)，即達(dá)成函數(shù)。建模的步驟根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，線性規(guī)劃與目標(biāo)規(guī)劃線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min,max系數(shù)可正負(fù)min,偏差變量系數(shù)≥0變量xi,xs,xa

xi,xs,xa

,

d約束條件系統(tǒng)約束(絕對約束)目標(biāo)約束系統(tǒng)約束解最優(yōu)滿意線性規(guī)劃與目標(biāo)規(guī)劃線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min,目標(biāo)規(guī)劃的圖解法圖解法解題步驟如下：1.確定各約束條件的可行域，即將所有約束條件(包括目標(biāo)約束和絕對約束，暫不考慮正負(fù)偏差變量)在坐標(biāo)平面上表示出來；2.在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向；3.求滿足最高優(yōu)先等級目標(biāo)的解；4.轉(zhuǎn)到下一個(gè)優(yōu)先等級的目標(biāo)，再不破壞所有較高優(yōu)先等級目標(biāo)的前提下，求出該優(yōu)先等級目標(biāo)的解；5.重復(fù)4，直到所有優(yōu)先等級目標(biāo)都已審查完畢為止；6.確定最優(yōu)解和滿意解。目標(biāo)規(guī)劃的圖解法圖解法解題步驟如下：目標(biāo)規(guī)劃的圖解法?????íì=33￡+=-++=-++++=-+-+-+---+)2.1(0,08

2

102

5.621210)(min21212221112122111lddxxxddxxddxxdPddPZll012345678123456⑴⑵⑶Ax2

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

0x2

0(1)x11401201008060402020406080100(2)(3)(4)ABCD結(jié)論：C(60,58.3)為所求的滿意解。目標(biāo)規(guī)劃的圖解法???????íì=33=-+=-+=-++=-+++++=目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)形式上沒有本質(zhì)的區(qū)別，所以可用單純形法求解。但要考慮目標(biāo)規(guī)劃的數(shù)學(xué)模型一些特點(diǎn)，作以下規(guī)定：(1)因目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求最小化，所以以cj-zj≥0，j=1,2,…，n為最優(yōu)準(zhǔn)則。(2)因非基變量的檢驗(yàn)數(shù)中含有不同等級的優(yōu)先因子，即KknjPazckkjjj,,2,1;,,2,1LL===-?因P1>>P2>>…>>PK；從每個(gè)檢驗(yàn)數(shù)的整體來看：檢驗(yàn)數(shù)的正、負(fù)首先決定于P1的系數(shù)α1j的正、負(fù)。若α1j=0，這時(shí)此檢驗(yàn)數(shù)的正、負(fù)就決定于P2的系數(shù)α2j的正、負(fù)。目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的單純形法(1)建立初始單純形表，在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個(gè)數(shù)分別列成K行，置k=1。(2)檢查該行中是否存在負(fù)數(shù)，且對應(yīng)的前k-1行的系數(shù)是零。若有負(fù)數(shù)取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)(3)。若無負(fù)數(shù)，則轉(zhuǎn)(5)。(3)按最小比值規(guī)則確定換出變量，當(dāng)存在兩個(gè)或以上相同的最小比值時(shí)，選取具有較高優(yōu)先級別變量為換出變量。(4)按單純形法進(jìn)行基變換運(yùn)算，建立新的計(jì)算表，返回(2)。(5)當(dāng)k=K時(shí)，計(jì)算結(jié)束。表中的解即為滿意解。否則置k=k+1，返回到(2)。目標(biāo)規(guī)劃的單純形法(1)建立初始單純形表，在表中將檢驗(yàn)數(shù)行按目標(biāo)規(guī)劃的單純形法例5-8：用單純形法求解下列目標(biāo)規(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目標(biāo)規(guī)劃的單純形法例5-8：用單純形法求解下列目標(biāo)規(guī)劃問題目標(biāo)規(guī)劃的單純形法cj值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+檢驗(yàn)數(shù)λjP1P2P300P10P2P23P305P3020541-10000002443001-1000031000001-1002-110000001-1d1-d2-d3-d4--5-401000-4-322-535463-檢驗(yàn)數(shù)λjP1P2P3d1-d2-x1d4-P1P205P331000001-1005041-100-55001203001-1-440050100001-11-10-40105-50-324-4-5-25513--P1P23P35P3目標(biāo)規(guī)劃的單純形法cjCBXBbx1x2d1-d1+d2-目標(biāo)規(guī)劃的單純形法cj00P10P2P23P305P30值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+檢驗(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ù)λ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目標(biāo)規(guī)劃的單純形法cj00P10P2P23P305P30目標(biāo)規(guī)劃的單純形法cj00P10P2P23P305P30值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+檢驗(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-100100115/3-5/3-26/335/35---3檢驗(yàn)數(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目標(biāo)規(guī)劃的單純形法cj00P10P2P23P305P30目標(biāo)規(guī)劃的單純形法例5-9：用單純形法求解下列目標(biāo)規(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目標(biāo)規(guī)劃的單純形法例5-9：用單純形法求解下列目標(biāo)規(guī)劃問題目標(biāo)規(guī)劃的應(yīng)用例5-10：已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型，經(jīng)營目標(biāo)：P1：總利潤不低于40P2：充分利用設(shè)備能力，且盡量不超過140如何安排生產(chǎn)？產(chǎn)品資源甲乙現(xiàn)有資源設(shè)備2010140售價(jià)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)目標(biāo)規(guī)劃的應(yīng)用例5-10：已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型，經(jīng)滿意解:x1=6，x2=5設(shè)備能力:需求206+105=170，實(shí)際140實(shí)現(xiàn)目標(biāo)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)部目標(biāo)甲產(chǎn)品的產(chǎn)量：6，成本：5乙產(chǎn)品的產(chǎn)量：5，成本：6技術(shù)部目標(biāo)甲產(chǎn)品的設(shè)備單耗：16.4乙產(chǎn)品的設(shè)備單耗：8.2銷售部目標(biāo)甲產(chǎn)品的銷量：6，單價(jià)：10乙產(chǎn)品的銷量：5，單價(jià)：8目標(biāo)規(guī)劃的應(yīng)用滿意解:x1=6，x2=5總利潤：40生產(chǎn)部目標(biāo)技術(shù)部降低設(shè)備消耗很困難，則調(diào)整經(jīng)營目標(biāo)的次序P1：充分利用設(shè)備能力，且盡量不超過140，P2：總利潤不低于40如何安排生產(chǎn)？產(chǎn)品資源甲乙現(xiàn)有資源設(shè)備2010140售價(jià)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目標(biāo)規(guī)劃的應(yīng)用降低設(shè)備消耗很困難，則調(diào)整經(jīng)營目標(biāo)的次序產(chǎn)品甲乙現(xiàn)有資源設(shè)備滿意解：x1=6,x2=2利潤指標(biāo)：實(shí)際5×6+2×2=34，期望40實(shí)現(xiàn)目標(biāo)P1和P2，增加甲乙產(chǎn)品的單位利潤:增長率(40-34)/34=18%產(chǎn)品售價(jià)由市場決定，為提高利潤，應(yīng)從降低成本入手：甲產(chǎn)品的成本由5降為10-5(1+18%)=4.12,乙產(chǎn)品的成本由6降為8-2(1+18%)=5.63。總利潤：40單位甲：5.88單位乙：2.36生產(chǎn)部目標(biāo)甲產(chǎn)品的產(chǎn)量：6，成本：4.12乙產(chǎn)品的產(chǎn)量：2，成本：5.63技術(shù)部目標(biāo)甲產(chǎn)品的設(shè)備單耗：20乙產(chǎn)品的設(shè)備單耗：10銷售部目標(biāo)甲產(chǎn)品的銷量：6，單價(jià)：10乙產(chǎn)品的銷量：2，單價(jià)：8目標(biāo)規(guī)劃的應(yīng)用滿意解：x1=6,x2=2總利潤：40生產(chǎn)部目標(biāo)技術(shù)某副食品批發(fā)店預(yù)測某商品今后4月的購進(jìn)與售出價(jià)格如表。假設(shè):(1)該商品供不應(yīng)求，最大銷量受倉庫容量限制；(2)正常庫容3噸，機(jī)動庫容2噸；(3)月初批發(fā)銷貨，月中采購進(jìn)貨，進(jìn)貨所需資金完全來銷售收入；(4)1月初庫存量2噸，成本2.5千元/噸，該月初無現(xiàn)金。經(jīng)營目標(biāo)：(1)每月都使用正常庫容，盡量不超容；(2)每月下旬都應(yīng)儲備1千元以備急用；(3)4個(gè)月總盈利最大。月份1234成本(購價(jià)+庫存)2.62.52.72.8售價(jià)2.92.73.13.3目標(biāo)規(guī)劃的應(yīng)用某副食品批發(fā)店預(yù)測某商品今后4月的購進(jìn)與售出價(jià)格如表。月份1決策變量：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+y3+y4

–x1

–x2–x3≤2各月采購量約束:每月采購量依賴月初的售貨收入。1月2.6x1

≤2.9y1→–

2.9y1+

2.6x1

≤02月–

2.9y1–2.7y2

+

2.6x1+2.5x2

≤0

3月–

2.9y1–2.7y2–3.1y3

+

2.6x1+2.5x2+2.7x3

≤04月–

2.9y1–2.7y2–3.1y3–3.3y4+

2.6x1+2.5x2+2.7x3+2.8x4≤0目標(biāo)規(guī)劃的應(yīng)用決策變量：xj第j月的采購量，yj第j月的銷售量目目標(biāo)約束條件正常庫容約束1月2–y1+

x1

≤3→–y1+

x1

+d1-

–d1+=12月–y1–y2+

x1+

x2+d2-

–d2+=1

3月–y1–y2–y3+

x1+

x2+

x3+d3-

–d3+=14月–y1–y2–y3–y4+

x1+

x2+

x3+

x4+d4-

–d4+=1各月儲備金約束1月

2.9y1-2.6x1

+d5-

–d5+=12月2.9y1+2.7y2

-

2.6x1-2.5x2+d6-

–d6+=1

3月2.9y1+2.7y2+3.1y3

-

2.6x1-2.5x2-2.7x3+d7-

–d7+=14月

2.9y1+2.7y2+3.1y3+3.3y4-

2.6x1-2.5x2-2.7x3-2.8x4+d8-

–d8+=1總盈利約束：期望利潤(3.3-2.5)×(3+2)×4=16

銷售收入:2.9y1+2.7y2+3.1y3+3.3y4

銷售成本:

2.5×2+2.6x1+2.5x2+2.7x3

2.9y1+2.7y2+3.1y3+3.3y4-2.6x1-2.5x2-2.7x3+d9-

–d9+=21目標(biāo)達(dá)成函數(shù)

minZ=P1(d1+

+d2+

+d3+

+d4+

)+P2(d5-

+d6-

+d7-

+d8-

)+P3

d9-

目標(biāo)規(guī)劃的應(yīng)用目標(biāo)約束條件目標(biāo)規(guī)劃的應(yīng)用目標(biāo)規(guī)劃本章內(nèi)容重點(diǎn)目標(biāo)規(guī)劃模型目標(biāo)規(guī)劃的幾何意義目標(biāo)規(guī)劃的單純形方法目標(biāo)規(guī)劃本章內(nèi)容重點(diǎn)問題的提出線性規(guī)劃只研究在滿足一定條件下，單一目標(biāo)函數(shù)取得最優(yōu)解，而在企業(yè)管理中，經(jīng)常遇到多目標(biāo)決策問題，如擬訂生產(chǎn)計(jì)劃時(shí)，不僅考慮總產(chǎn)值，同時(shí)要考慮利潤，產(chǎn)品質(zhì)量和設(shè)備利用率等。這些指標(biāo)之間的重要程度(即優(yōu)先順序)也不相同，有些目標(biāo)之間往往相互發(fā)生矛盾。線性規(guī)劃致力于某個(gè)目標(biāo)函數(shù)的最優(yōu)解，這個(gè)最優(yōu)解若是超過了實(shí)際的需要，很可能是以過分地消耗了約束條件中的某些資源作為代價(jià)。問題的提出線性規(guī)劃只研究在滿足一定條件下，單一目標(biāo)函數(shù)取得線性規(guī)劃把各個(gè)約束條件的重要性都不分主次地等同看待，這也不符合實(shí)際情況。求解線性規(guī)劃問題，首先要求約束條件必須相容，如果約束條件中，由于人力，設(shè)備等資源條件的限制，使約束條件之間出現(xiàn)了矛盾，就得不到問題的可行解，但生產(chǎn)還得繼續(xù)進(jìn)行，這將給人們進(jìn)一步應(yīng)用線性規(guī)劃方法帶來困難。為了彌補(bǔ)線性規(guī)劃問題的局限性，解決有限資源和計(jì)劃指標(biāo)之間的矛盾，在線性規(guī)劃基礎(chǔ)上，建立目標(biāo)規(guī)劃方法，從而使一些線性規(guī)劃無法解決的問題得到滿意的解答。問題的提出線性規(guī)劃把各個(gè)約束條件的重要性都不分主次地等同看待，這也不符目標(biāo)規(guī)劃與線性規(guī)劃的比較線性規(guī)劃只討論一個(gè)線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題；而目標(biāo)規(guī)劃是多個(gè)目標(biāo)決策，可求得更切合實(shí)際的解。線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個(gè)滿意解。線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目標(biāo)規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。線性規(guī)劃的最優(yōu)解是絕對意義下的最優(yōu)，但需花去大量的人力、物力、財(cái)力才能得到；實(shí)際過程中，只要求得滿意解，就能滿足需要(或更能滿足需要)。目標(biāo)規(guī)劃與線性規(guī)劃的比較線性規(guī)劃只討論一個(gè)線性目標(biāo)函數(shù)在一組目標(biāo)規(guī)劃與線性規(guī)劃的比較例5-1：某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計(jì)劃，使獲得的利潤最大？同時(shí)，根據(jù)市場預(yù)測，甲的銷路不是太好，應(yīng)盡可能少生產(chǎn)；乙的銷路較好，可以擴(kuò)大生產(chǎn)。試建立此問題的數(shù)學(xué)模型。12070單件利潤3000103設(shè)備臺時(shí)200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗目標(biāo)規(guī)劃與線性規(guī)劃的比較例5-1：某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)目標(biāo)規(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目標(biāo)規(guī)劃數(shù)學(xué)模型設(shè)：甲產(chǎn)品x1，乙產(chǎn)品x2根據(jù)市場預(yù)測目標(biāo)規(guī)劃的數(shù)學(xué)模型1.目標(biāo)值和偏差變量目標(biāo)規(guī)劃通過引入目標(biāo)值和偏差變量，可以將目標(biāo)函數(shù)轉(zhuǎn)化為目標(biāo)約束。目標(biāo)值：是指預(yù)先給定的某個(gè)目標(biāo)的一個(gè)期望值。實(shí)現(xiàn)值或決策值：是指當(dāng)決策變量xj選定以后，目標(biāo)函數(shù)的對應(yīng)值。偏差變量(事先無法確定的未知數(shù))：是指實(shí)現(xiàn)值和目標(biāo)值之間的差異,記為d。正偏差變量:表示實(shí)現(xiàn)值超過目標(biāo)值的部分，記為d＋。負(fù)偏差變量:表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分，記為d－。目標(biāo)規(guī)劃的數(shù)學(xué)模型1.目標(biāo)值和偏差變量目標(biāo)規(guī)劃的數(shù)學(xué)模型在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值，故有d＋×d－＝0,并規(guī)定d＋≥0,d－≥0當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：d＋≥0,d－＝0當(dāng)未完成規(guī)定的指標(biāo)則表示：d＋＝0,d－≥0當(dāng)恰好完成指標(biāo)時(shí)則表示：d＋＝0,d－＝0目標(biāo)規(guī)劃的數(shù)學(xué)模型在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未目標(biāo)規(guī)劃的數(shù)學(xué)模型2.目標(biāo)約束和絕對約束引入了目標(biāo)值和正、負(fù)偏差變量后，就對某一問題有了新的限制，既目標(biāo)約束。目標(biāo)約束即可對原目標(biāo)函數(shù)起作用，也可對原約束起作用。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。絕對約束(系統(tǒng)約束)是指必須嚴(yán)格滿足的等式或不等式約束。如線性規(guī)劃中的所有約束條件都是絕對約束，否則無可行解。所以，絕對約束是硬約束。目標(biāo)規(guī)劃的數(shù)學(xué)模型2.目標(biāo)約束和絕對約束目標(biāo)規(guī)劃的數(shù)學(xué)模型例如：在例一中，規(guī)定Z1的目標(biāo)值為50000,正、負(fù)偏差為d＋、d－,則目標(biāo)函數(shù)可以轉(zhuǎn)換為目標(biāo)約束，既:50000120701121=-+++-ddxx若規(guī)定3600的鋼材必須用完，原式9x1+4x2≤3600變?yōu)?600494421=-+++-ddxx目標(biāo)規(guī)劃的數(shù)學(xué)模型例如：在例一中，規(guī)定Z1的目標(biāo)值為500目標(biāo)規(guī)劃的數(shù)學(xué)模型3.優(yōu)先因子(優(yōu)先等級)與優(yōu)先權(quán)系數(shù)目標(biāo)等級化:將目標(biāo)按重要性程度不同依次分成一級目標(biāo)、二級目標(biāo)…..。最次要的目標(biāo)放在次要的等級中。(1)對同一目標(biāo)而言，若有幾個(gè)決策方案都能使其達(dá)到，可認(rèn)為這些方案就這個(gè)目標(biāo)而言都是最優(yōu)方案；若達(dá)不到，則與目標(biāo)差距越小的越好。(2)不同級別的目標(biāo)的重要性是不可比的。即較高級別的目標(biāo)沒有達(dá)到的損失，任何較低級別目標(biāo)上的收獲不可彌補(bǔ)。故在判斷最優(yōu)方案時(shí)，首先從較高級別的目標(biāo)達(dá)到的程度來決策，然后再其次級目標(biāo)的判斷。(3)同一級別的目標(biāo)可以是多個(gè)。各自之間的重要程度可用數(shù)量（權(quán)數(shù)）來描述。因此，同一級別的目標(biāo)的其中一個(gè)的損失，可有其余目標(biāo)的適當(dāng)收獲來彌補(bǔ)。目標(biāo)規(guī)劃的數(shù)學(xué)模型3.優(yōu)先因子(優(yōu)先等級)與優(yōu)先權(quán)系數(shù)目標(biāo)規(guī)劃的數(shù)學(xué)模型3.優(yōu)先因子(優(yōu)先等級)與優(yōu)先權(quán)系數(shù)優(yōu)先因子Pk是將決策目標(biāo)按其重要程度排序并表示出來。P1>>P2>>…>>Pk>>Pk+1>>…>>PK，k=1,2…,K。表示Pk比Pk+1有更大的優(yōu)先權(quán)。即首先保證P1級目標(biāo)的實(shí)現(xiàn)，這時(shí)可不考慮次級目標(biāo)；而P2級目標(biāo)是在實(shí)現(xiàn)P1級目標(biāo)的基礎(chǔ)上考慮的；依此類推。若要區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，這時(shí)可分別賦予它們不同的權(quán)系數(shù)ωj,這些都由決策者按具體情況而定。目標(biāo)規(guī)劃的數(shù)學(xué)模型3.優(yōu)先因子(優(yōu)先等級)與優(yōu)先權(quán)系數(shù)目標(biāo)規(guī)劃的數(shù)學(xué)模型4.達(dá)成函數(shù)(即目標(biāo)規(guī)劃中的目標(biāo)函數(shù))目標(biāo)規(guī)劃的目標(biāo)函數(shù)(準(zhǔn)則函數(shù))是按各目標(biāo)約束的正、負(fù)偏差變量和賦予相應(yīng)的優(yōu)先因子及權(quán)系數(shù)而構(gòu)造的。當(dāng)每一目標(biāo)值確定后，決策者的要求是盡可能縮小偏離目標(biāo)值。因此目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是minZ=f(d＋、d－)。一般說來，有以下三種情況，但只能出現(xiàn)其中之一：(1)要求恰好達(dá)到規(guī)定的目標(biāo)值，即正、負(fù)偏差變量要盡可能小，則minZ=f(d＋＋d－)。(2)要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，也就是正偏差變量盡可能小，則minZ=f(d＋)。(3)要求超過目標(biāo)值，即超過量不限，但不低于目標(biāo)值，也就是負(fù)偏差變量盡可能小，則minZ=f(d－)。對由絕對約束轉(zhuǎn)化而來的目標(biāo)函數(shù)，也照上述處理即可。目標(biāo)規(guī)劃的數(shù)學(xué)模型4.達(dá)成函數(shù)(即目標(biāo)規(guī)劃中的目標(biāo)函數(shù))目標(biāo)規(guī)劃的數(shù)學(xué)模型5.多目標(biāo)規(guī)劃的解(1)若多目標(biāo)規(guī)劃問題的解能使所有的目標(biāo)都達(dá)到，就稱該解為多目標(biāo)規(guī)劃的最優(yōu)解；(2)若解只能滿足部分目標(biāo)，就稱該解為多目標(biāo)規(guī)劃的次優(yōu)解；(3)若找不到滿足任何一個(gè)目標(biāo)的解，就稱該問題為無解。(4)前面的目標(biāo)可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，有些可能就不能實(shí)現(xiàn)，就稱該解為多目標(biāo)規(guī)劃的滿意解(具有層次意義的解)目標(biāo)規(guī)劃的數(shù)學(xué)模型5.多目標(biāo)規(guī)劃的解單目標(biāo)規(guī)劃例5-2:某工廠生產(chǎn)A，B兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下。實(shí)現(xiàn)目標(biāo)利潤為140萬元的最優(yōu)生產(chǎn)方案AB可用量設(shè)備(臺時(shí))4260原材料(KG)2448利潤(萬元)86從決策者的角度看，他希望超過利潤目標(biāo)值，若達(dá)不到，也希望盡可能接近，即負(fù)偏差最小33-+0,,0,21ddxx￡+484221xx￡+602421xx=+-+-+1406821ddxx?????íìst=-mindZ單目標(biāo)規(guī)劃例5-2:某工廠生產(chǎn)A，B兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下。級別相等的多目標(biāo)規(guī)劃例5-3：若上例中假設(shè)決策者根據(jù)市場預(yù)測，產(chǎn)品A的銷售量有下降的趨勢，故考慮實(shí)現(xiàn)下列兩個(gè)目標(biāo)：(1)實(shí)現(xiàn)利潤目標(biāo)122萬元(2)產(chǎn)品A的產(chǎn)量不多于10分析:兩個(gè)目標(biāo)級別相等，即兩個(gè)目標(biāo)的重要程度一樣，不存在誰優(yōu)先的問題設(shè)d＋，d-分別為超過目標(biāo)值的部分，以及未完成目標(biāo)值的部分，于是兩個(gè)目標(biāo)可以等價(jià)表示為：10122681211121=-+=-+++-+-ddxddxx級別相等的多目標(biāo)規(guī)劃例5-3：若上例中假設(shè)決策者根據(jù)市場預(yù)測級別相等的多目標(biāo)規(guī)劃x1=10，x2=7，d－1＝0，d+2＝0，利潤為122，兩個(gè)目標(biāo)均已經(jīng)實(shí)現(xiàn)?????íì3￡+￡+=-+=-+++=+-+-+-+-+-0,,,,,4842602410122682211212121221112121ddddxxxxxxddxddxxstddMinZ級別相等的多目標(biāo)規(guī)劃x1=10，x2=7，d－1＝0，d+2具有優(yōu)先級別的多目標(biāo)規(guī)劃對于多個(gè)目標(biāo)，如果有一定的優(yōu)先順序，即第一位重要的目標(biāo)，其優(yōu)先因子為P1，第二位重要的目標(biāo)，其優(yōu)先因子為P2，并規(guī)定P1>>P2優(yōu)先保證P1級目標(biāo)的實(shí)現(xiàn)，此時(shí)不考慮次級目標(biāo)；次級目標(biāo)P2在實(shí)現(xiàn)了P1級目標(biāo)的基礎(chǔ)上再予以考慮。如果無法實(shí)現(xiàn)P1目標(biāo)，則不考慮P2目標(biāo)能否取得最優(yōu)若有k個(gè)不同優(yōu)先順序的目標(biāo)，則有P1>>P2>>…>>Pk將權(quán)重與偏差相乘構(gòu)成目標(biāo)函數(shù)，這樣，權(quán)重越大，越先迫使相應(yīng)的偏差等于零，這樣可保證優(yōu)先級高的目標(biāo)首先實(shí)現(xiàn)。具有優(yōu)先級別的多目標(biāo)規(guī)劃對于多個(gè)目標(biāo)，如果有一定的優(yōu)先順序，具有優(yōu)先級別的多目標(biāo)規(guī)劃例5-4：若上例中決策者擬訂下列經(jīng)營目標(biāo)，并確定了目標(biāo)之間的優(yōu)先順序P1級目標(biāo)：充分利用設(shè)備有效臺時(shí)，不加班；P2級目標(biāo)：產(chǎn)品B的產(chǎn)量不多于4；P3級目標(biāo)：實(shí)現(xiàn)利潤值130萬元分析：題目有三個(gè)目標(biāo)層次，包含三個(gè)目標(biāo)值。第一目標(biāo)：P1(d1＋+d1-)第二目標(biāo)：P2d2＋第二目標(biāo)：P3d3-?????íì3￡+=-++=-+=-+++++=+-+-+-+--++-0,,,48421306846024)(2121332122211213322111iiddxxxxddxxddxddxxstdPdPddPMinZ具有優(yōu)先級別的多目標(biāo)規(guī)劃例5-4：若上例中決策者擬訂下列經(jīng)營具有優(yōu)先級別的多目標(biāo)規(guī)劃例5-5：某廠計(jì)劃下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。制定生產(chǎn)計(jì)劃，滿足下列目標(biāo)：P1級目標(biāo)：完成或超額完成利潤指標(biāo)50000元；P2級目標(biāo)：產(chǎn)品甲不超過200件，產(chǎn)品乙不低于250件；P3級目標(biāo)：現(xiàn)有鋼材3600噸必須用完12070單件利潤3000103設(shè)備臺時(shí)200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗具有優(yōu)先級別的多目標(biāo)規(guī)劃例5-5：某廠計(jì)劃下一個(gè)生產(chǎn)周期內(nèi)生具有優(yōu)先級別的多目標(biāo)規(guī)劃分析：題目有三個(gè)目標(biāo)層次，包含四個(gè)目標(biāo)值。第一目標(biāo)：P1d1＋第二目標(biāo)：有兩個(gè)要求即甲d2＋，乙d3-，但兩個(gè)具有相同的優(yōu)先因子，需要確定權(quán)系數(shù)。本題可用單件利潤比作為權(quán)系數(shù)即70:120，化簡為7:12，P2(7d2＋+12d2-)第二目標(biāo)：P3(d4＋+d4-)?????????íì3￡+￡+=-++=-+=-+=-++++++=+-+-+-+-+-+--+-0,,,30001032000543600492502005000012070)()127(2121214421332221112144332211iiddxxxxxxddxxddxddxddxxstddPddPdPMinZ具有優(yōu)先級別的多目標(biāo)規(guī)劃分析：題目有三個(gè)目標(biāo)層次，包含四個(gè)目數(shù)學(xué)模型的一般形式?????????íì-=3-=3-=3=￡-==-+-+=+-=+-=++-=-=????)55(3,2,1,0,)45(,,1,0)35(,,1,),()25(,,1,)15()(min1111kddnjxmibxaKkgddxcddPzkkjijnjijkkkjnjkjklkkKklkLllLLL滿足約束條件：目標(biāo)函數(shù)：ww其中Pl為優(yōu)先因子，w-lk，w+lk為優(yōu)先系數(shù)數(shù)學(xué)模型的一般形式?????????íì-=3-=3-=3=建模的步驟根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對約束；可根據(jù)決策者的需要，將某些或全部絕對約束轉(zhuǎn)化為目標(biāo)約束。這時(shí)只需要給絕對約束加上負(fù)偏差變量和減去正偏差變量即可。給各目標(biāo)賦予相應(yīng)的優(yōu)先因子

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

ωkl+和ωkl-。根據(jù)決策者的要求，構(gòu)造一個(gè)由優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量組成的，要求實(shí)現(xiàn)極小化的目標(biāo)函數(shù)，即達(dá)成函數(shù)。建模的步驟根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，線性規(guī)劃與目標(biāo)規(guī)劃線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min,max系數(shù)可正負(fù)min,偏差變量系數(shù)≥0變量xi,xs,xa

xi,xs,xa

,

d約束條件系統(tǒng)約束(絕對約束)目標(biāo)約束系統(tǒng)約束解最優(yōu)滿意線性規(guī)劃與目標(biāo)規(guī)劃線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min,目標(biāo)規(guī)劃的圖解法圖解法解題步驟如下：1.確定各約束條件的可行域，即將所有約束條件(包括目標(biāo)約束和絕對約束，暫不考慮正負(fù)偏差變量)在坐標(biāo)平面上表示出來；2.在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向；3.求滿足最高優(yōu)先等級目標(biāo)的解；4.轉(zhuǎn)到下一個(gè)優(yōu)先等級的目標(biāo)，再不破壞所有較高優(yōu)先等級目標(biāo)的前提下，求出該優(yōu)先等級目標(biāo)的解；5.重復(fù)4，直到所有優(yōu)先等級目標(biāo)都已審查完畢為止；6.確定最優(yōu)解和滿意解。目標(biāo)規(guī)劃的圖解法圖解法解題步驟如下：目標(biāo)規(guī)劃的圖解法?????íì=33￡+=-++=-++++=-+-+-+---+)2.1(0,08

2

102

5.621210)(min21212221112122111lddxxxddxxddxxdPddPZll012345678123456⑴⑵⑶Ax2

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

0x2

0(1)x11401201008060402020406080100(2)(3)(4)ABCD結(jié)論：C(60,58.3)為所求的滿意解。目標(biāo)規(guī)劃的圖解法???????íì=33=-+=-+=-++=-+++++=目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)形式上沒有本質(zhì)的區(qū)別，所以可用單純形法求解。但要考慮目標(biāo)規(guī)劃的數(shù)學(xué)模型一些特點(diǎn)，作以下規(guī)定：(1)因目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求最小化，所以以cj-zj≥0，j=1,2,…，n為最優(yōu)準(zhǔn)則。(2)因非基變量的檢驗(yàn)數(shù)中含有不同等級的優(yōu)先因子，即KknjPazckkjjj,,2,1;,,2,1LL===-?因P1>>P2>>…>>PK；從每個(gè)檢驗(yàn)數(shù)的整體來看：檢驗(yàn)數(shù)的正、負(fù)首先決定于P1的系數(shù)α1j的正、負(fù)。若α1j=0，這時(shí)此檢驗(yàn)數(shù)的正、負(fù)就決定于P2的系數(shù)α2j的正、負(fù)。目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的單純形法(1)建立初始單純形表，在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個(gè)數(shù)分別列成K行，置k=1。(2)檢查該行中是否存在負(fù)數(shù)，且對應(yīng)的前k-1行的系數(shù)是零。若有負(fù)數(shù)取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)(3)。若無負(fù)數(shù)，則轉(zhuǎn)(5)。(3)按最小比值規(guī)則確定換出變量，當(dāng)存在兩個(gè)或以上相同的最小比值時(shí)，選取具有較高優(yōu)先級別變量為換出變量。(4)按單純形法進(jìn)行基變換運(yùn)算，建立新的計(jì)算表，返回(2)。(5)當(dāng)k=K時(shí)，計(jì)算結(jié)束。表中的解即為滿意解。否則置k=k+1，返回到(2)。目標(biāo)規(guī)劃的單純形法(1)建立初始單純形表，在表中將檢驗(yàn)數(shù)行按目標(biāo)規(guī)劃的單純形法例5-8：用單純形法求解下列目標(biāo)規(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目標(biāo)規(guī)劃的單純形法例5-8：用單純形法求解下列目標(biāo)規(guī)劃問題目標(biāo)規(guī)劃的單純形法cj值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+檢驗(yàn)數(shù)λjP1P2P300P10P2P23P305P3020541-10000002443001-1000031000001-1002-110000001-1d1-d2-d3-d4--5-401000-4-322-535463-檢驗(yàn)數(shù)λjP1P2P3d1-d2-x1d4-P1P205P331000001-1005041-100-55001203001-1-440050100001-11-10-40105-50-324-4-5-25513--P1P23P35P3目標(biāo)規(guī)劃的單純形法cjCBXBbx1x2d1-d1+d2-目標(biāo)規(guī)劃的單純形法cj00P10P2P23P305P30值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+檢驗(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ù)λ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目標(biāo)規(guī)劃的單純形法cj00P10P2P23P305P30目標(biāo)規(guī)劃的單純形法cj00P10P2P23P305P30值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+檢驗(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-100100115/3-5/3-26/335/35---3檢驗(yàn)數(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目標(biāo)規(guī)劃的單純形法cj00P10P2P23P305P30目標(biāo)規(guī)劃的單純形法例5-9：用單純形法求解下列目標(biāo)規(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目標(biāo)規(guī)劃的單純形法例5-9：用單純形法求解下列目標(biāo)規(guī)劃問題目標(biāo)規(guī)劃的應(yīng)用例5-10：已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型，經(jīng)營目標(biāo)：P1：總利潤不低于40P2：充分利用設(shè)備能力，且盡量不超過140如何安排生產(chǎn)？產(chǎn)品資源甲乙現(xiàn)有資源設(shè)備2010140售價(jià)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)目標(biāo)規(guī)劃的應(yīng)用例5-10：已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型，經(jīng)滿意解:x1=6，x2=5設(shè)備能力:需求206+105=170，實(shí)際140實(shí)現(xiàn)目標(biāo)P1和P2，降低甲乙產(chǎn)品的設(shè)備消耗:降低率(170-140)/170=18%，甲產(chǎn)品的設(shè)備消耗降為20(1-18%)=16.4，乙產(chǎn)品的設(shè)備消耗降為