目標規劃本章內容重點目標規劃模型目標規劃的幾何意義目標規劃的單純形方法目標規劃本章內容重點問題的提出線性規劃只研究在滿足一定條件下，單一目標函數取得最優解，而在企業管理中，經常遇到多目標決策問題，如擬訂生產計劃時，不僅考慮總產值，同時要考慮利潤，產品質量和設備利用率等。這些指標之間的重要程度(即優先順序)也不相同，有些目標之間往往相互發生矛盾。線性規劃致力于某個目標函數的最優解，這個最優解若是超過了實際的需要，很可能是以過分地消耗了約束條件中的某些資源作為代價。問題的提出線性規劃只研究在滿足一定條件下，單一目標函數取得線性規劃把各個約束條件的重要性都不分主次地等同看待，這也不符合實際情況。求解線性規劃問題，首先要求約束條件必須相容，如果約束條件中，由于人力，設備等資源條件的限制，使約束條件之間出現了矛盾，就得不到問題的可行解，但生產還得繼續進行，這將給人們進一步應用線性規劃方法帶來困難。為了彌補線性規劃問題的局限性，解決有限資源和計劃指標之間的矛盾，在線性規劃基礎上，建立目標規劃方法，從而使一些線性規劃無法解決的問題得到滿意的解答。問題的提出線性規劃把各個約束條件的重要性都不分主次地等同看待，這也不符目標規劃與線性規劃的比較線性規劃只討論一個線性目標函數在一組線性約束條件下的極值問題；而目標規劃是多個目標決策，可求得更切合實際的解。線性規劃求最優解；目標規劃是找到一個滿意解。線性規劃中的約束條件是同等重要的，是硬約束；而目標規劃中有輕重緩急和主次之分，即有優先權。線性規劃的最優解是絕對意義下的最優，但需花去大量的人力、物力、財力才能得到；實際過程中，只要求得滿意解，就能滿足需要(或更能滿足需要)。目標規劃與線性規劃的比較線性規劃只討論一個線性目標函數在一組目標規劃與線性規劃的比較例5-1：某廠計劃在下一個生產周期內生產甲、乙兩種產品，已知資料如表所示。試制定生產計劃，使獲得的利潤最大？同時，根據市場預測，甲的銷路不是太好，應盡可能少生產；乙的銷路較好，可以擴大生產。試建立此問題的數學模型。12070單件利潤3000103設備臺時200054煤炭360049鋼材資源限制乙甲單位產品資源消耗目標規劃與線性規劃的比較例5-1：某廠計劃在下一個生產周期內目標規劃數學模型設：甲產品x1

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

Pk對同一優先等級中的各偏差變量，若需要可按其重要程度的不同，賦予相應的權系數

ωkl+和ωkl-。根據決策者的要求，構造一個由優先因子和權系數相對應的偏差變量組成的，要求實現極小化的目標函數，即達成函數。建模的步驟根據要研究的問題所提出的各目標與條件，確定目標值，線性規劃與目標規劃線性規劃LP目標規劃GP目標函數min,max系數可正負min,偏差變量系數≥0變量xi,xs,xa

xi,xs,xa

,

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

2

102

5.621210)(min21212221112122111lddxxxddxxddxxdPddPZll012345678123456⑴⑵⑶Ax2

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

0x2

0(1)x11401201008060402020406080100(2)(3)(4)ABCD結論：C(60,58.3)為所求的滿意解。目標規劃的圖解法???????íì=33=-+=-+=-++=-+++++=目標規劃的單純形法目標規劃的數學模型結構與線性規劃的數學模型結構形式上沒有本質的區別，所以可用單純形法求解。但要考慮目標規劃的數學模型一些特點，作以下規定：(1)因目標規劃問題的目標函數都是求最小化，所以以cj-zj≥0，j=1,2,…，n為最優準則。(2)因非基變量的檢驗數中含有不同等級的優先因子，即KknjPazckkjjj,,2,1;,,2,1LL===-?因P1>>P2>>…>>PK；從每個檢驗數的整體來看：檢驗數的正、負首先決定于P1的系數α1j的正、負。若α1j=0，這時此檢驗數的正、負就決定于P2的系數α2j的正、負。目標規劃的單純形法目標規劃的數學模型結構與線性規劃的數學模型目標規劃的單純形法(1)建立初始單純形表，在表中將檢驗數行按優先因子個數分別列成K行，置k=1。(2)檢查該行中是否存在負數，且對應的前k-1行的系數是零。若有負數取其中最小者對應的變量為換入變量，轉(3)。若無負數，則轉(5)。(3)按最小比值規則確定換出變量，當存在兩個或以上相同的最小比值時，選取具有較高優先級別變量為換出變量。(4)按單純形法進行基變換運算，建立新的計算表，返回(2)。(5)當k=K時，計算結束。表中的解即為滿意解。否則置k=k+1，返回到(2)。目標規劃的單純形法(1)建立初始單純形表，在表中將檢驗數行按目標規劃的單純形法例5-8：用單純形法求解下列目標規劃問題

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目標規劃的單純形法例5-8：用單純形法求解下列目標規劃問題目標規劃的單純形法cj

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

值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+檢驗數λ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--檢驗數λ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目標規劃的單純形法cj00P10P2P23P305P30目標規劃的單純形法cj00P10P2P23P305P30

值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+檢驗數λ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檢驗數λ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目標規劃的單純形法cj00P10P2P23P305P30目標規劃的單純形法例5-9：用單純形法求解下列目標規劃問題

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目標規劃的單純形法例5-9：用單純形法求解下列目標規劃問題目標規劃的應用例5-10：已知一個生產計劃的線性規劃模型，經營目標：P1：總利潤不低于40P2：充分利用設備能力，且盡量不超過140如何安排生產？產品資源甲乙現有資源設備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)目標規劃的應用例5-10：已知一個生產計劃的線性規劃模型，經滿意解:x1=6，x2=5設備能力:需求206+105=170，實際140實現目標P1和P2，降低甲乙產品的設備消耗:降低率(170-140)/170=18%，甲產品的設備消耗降為20(1-18%)=16.4，乙產品的設備消耗降為10(1-18%)=8.2。總利潤：40單位甲：5單位乙：2生產部目標甲產品的產量：6，成本：5乙產品的產量：5，成本：6技術部目標甲產品的設備單耗：16.4乙產品的設備單耗：8.2銷售部目標甲產品的銷量：6，單價：10乙產品的銷量：5，單價：8目標規劃的應用滿意解:x1=6，x2=5總利潤：40生產部目標技術部降低設備消耗很困難，則調整經營目標的次序P1：充分利用設備能力，且盡量不超過140，P2：總利潤不低于40如何安排生產？產品資源甲乙現有資源設備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目標規劃的應用降低設備消耗很困難，則調整經營目標的次序產品甲乙現有資源設備滿意解：x1=6,x2=2利潤指標：實際5×6+2×2=34，期望40實現目標P1和P2，增加甲乙產品的單位利潤:增長率(40-34)/34=18%產品售價由市場決定，為提高利潤，應從降低成本入手：甲產品的成本由5降為10-5(1+18%)=4.12,乙產品的成本由6降為8-2(1+18%)=5.63?？偫麧櫍?0單位甲：5.88單位乙：2.36生產部目標甲產品的產量：6，成本：4.12乙產品的產量：2，成本：5.63技術部目標甲產品的設備單耗：20乙產品的設備單耗：10銷售部目標甲產品的銷量：6，單價：10乙產品的銷量：2，單價：8目標規劃的應用滿意解：x1=6,x2=2總利潤：40生產部目標技術某副食品批發店預測某商品今后4月的購進與售出價格如表。假設:(1)該商品供不應求，最大銷量受倉庫容量限制；(2)正常庫容3噸，機動庫容2噸；(3)月初批發銷貨，月中采購進貨，進貨所需資金完全來銷售收入；(4)1月初庫存量2噸，成本2.5千元/噸，該月初無現金。經營目標：(1)每月都使用正常庫容，盡量不超容；(2)每月下旬都應儲備1千元以備急用；(3)4個月總盈利最大。月份1234成本(購價+庫存)2.62.52.72.8售價2.92.73.13.3目標規劃的應用某副食品批發店預測某商品今后4月的購進與售出價格如表。月份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