《管理運(yùn)籌學(xué)》(第2版)6-10章教案

PAGEPAGE60第六章單純形法的靈敏度分析與對(duì)偶§1單純形表的靈敏度分析§2線性規(guī)劃的對(duì)偶問(wèn)題§3對(duì)偶規(guī)劃的基本性質(zhì)§4對(duì)偶單純形法§1單純形表的靈敏度分析一、目標(biāo)函數(shù)中變量Ck系數(shù)靈敏度分析1.在最終的單純形表里，Xk是非基變量由于約束方程系數(shù)增廣矩陣在迭代中只是其本身的行的初等變換與Ck沒(méi)有任何關(guān)系，所以當(dāng)Ck變成Ck+ΔCk時(shí)，在最終單純形表中其系數(shù)的增廣矩陣不變，又因?yàn)閄k是非基變量，所以基變量的目標(biāo)函數(shù)的系數(shù)不變，即CB不變，可知Zk也不變，只是Ck變成了Ck+ΔCk。這時(shí)δK=Ck-Zk就變成了Ck+ΔCk-Zk=δK+ΔCk。要使原來(lái)的最優(yōu)解仍為最優(yōu)解，只要δK+ΔCk≤0即可，也就是Ck的增量ΔCk≤—δK。2.在最終的單純形表中，Xk是基變量當(dāng)Ck變成Ck+ΔCk時(shí)，最終單純形表中約束方程的增廣矩陣不變，但是基變量的目標(biāo)函數(shù)的系數(shù)CB變了，則ZJ(J=1,2,…,N)一般也變了，不妨設(shè)CB=(CB1,CB2…,Ck,…，CBm)，當(dāng)CB變成=(CB1,CB2…,Ck+ΔCk,…,CBm)，則：ZJ=(CB1,CB2…,Ck,…，CBm)(a’1j,a’2j,…,a’Kj,…,a’mj)Z’J=(CB1,CB2…,Ck+ΔCk,…，CBm)(a’1j,a’2j,…,a’Kj,…,a’mj)T=ZJ+ΔCka’Kj根據(jù)上式可知檢驗(yàn)數(shù)δJ(J=1,2,…..,M)變成了δ’J，有δ’J=CJ-Z’J=δJ+ΔCKa’Kj。要使最優(yōu)解不變，只要當(dāng)J≠K時(shí)，δ’J<=0例：目標(biāo)函數(shù)：MaxZ=50X1+100X2約束條件：X1+X2≤3002X1+X2≤400X2≤250X1，X2≥0最優(yōu)單純形表如下表6—1我們先對(duì)非基變量S1的目標(biāo)函數(shù)的系數(shù)C3進(jìn)行靈敏度分析。這里δ3=-50，所以當(dāng)c3的增量Δc3≤50，最優(yōu)解不變。再對(duì)基變量x1的目標(biāo)函數(shù)的系數(shù)c1進(jìn)行靈敏度分析。在a11?,a12?,a13?,a14?,a15?中，除了知道a11?和a13?大于0，a15?小于0，可知，有。同樣有。這樣可以知道當(dāng)-50≤Δc1≤50時(shí)，也就是x1的目標(biāo)函數(shù)c1＇在0≤c1＇≤100時(shí)最優(yōu)解不變。在最終的單純形表中，用C’1代替原來(lái)的C1=50，計(jì)算得表表6—2從δ3≤0，得到-c1’≤0,即c1’≥0，并且從δ5≤0，得到c1’≤100。那么如果c1’取值超出這個(gè)范圍，必然存在一個(gè)檢驗(yàn)數(shù)大于0，我們可以通過(guò)迭代來(lái)得到新的最優(yōu)解。二、約束方程中常數(shù)項(xiàng)的靈敏度分析表6—3從上表我們可以發(fā)現(xiàn)各個(gè)松弛變量的值，正好等于相應(yīng)變量的對(duì)偶價(jià)格。在最優(yōu)解中S2=50是基變量，即為，原料A有50千克沒(méi)用完，再增加A原料是不會(huì)增加利潤(rùn)的，A的對(duì)偶價(jià)格為0。對(duì)于任何為基變量的松弛變量所對(duì)應(yīng)的約束條件的對(duì)偶價(jià)格為0?？梢钥闯?，上題中對(duì)于設(shè)備臺(tái)時(shí)數(shù)約束來(lái)說(shuō)，當(dāng)其松弛變量在目標(biāo)函數(shù)中從0變到Z3=50時(shí)，也就是只要當(dāng)前余下一臺(tái)時(shí)數(shù)設(shè)備從不能獲利變成獲利50元時(shí)，譬如有人愿意出50元買一個(gè)設(shè)備時(shí)，我們就不必為生產(chǎn)Ι、П產(chǎn)品而使用完所有的設(shè)備臺(tái)時(shí)了，這說(shuō)明了設(shè)備臺(tái)時(shí)數(shù)的對(duì)偶價(jià)格就是Z3=50元。對(duì)于含有大于等于號(hào)的約束條件，添加剩余變量化為標(biāo)準(zhǔn)型。這時(shí)這個(gè)約束條件的對(duì)偶價(jià)格就和這個(gè)剩余變量的有關(guān)了。這將使得最優(yōu)目標(biāo)值特別“惡化”而不是改進(jìn)，故這時(shí)約束條件的對(duì)偶價(jià)格應(yīng)取值的相反數(shù)-。對(duì)于含有等于號(hào)的約束條件，其約束條件的對(duì)偶價(jià)格就和該約束方程的人工變量有關(guān)了。其約束條件的對(duì)偶價(jià)格就等于此約束方程的人工變量的值。下表給出了一個(gè)由最終單純形表對(duì)于不同約束類型的對(duì)偶價(jià)格的取值。表6-4從對(duì)偶價(jià)格的定義,可以知道當(dāng)對(duì)偶價(jià)格為正時(shí)它將改進(jìn)目標(biāo)函數(shù)的值，當(dāng)對(duì)偶價(jià)格為負(fù)時(shí)它將使得目標(biāo)函數(shù)朝著與最優(yōu)化相反的方向前進(jìn)。下面我們研究當(dāng)右端項(xiàng)bj發(fā)生變化時(shí)，在什么范圍內(nèi)其對(duì)偶價(jià)格不變。由于bj的變化并不影響系數(shù)矩陣的迭代，故其最終單純形表中的系數(shù)矩陣沒(méi)有變化。由此可見(jiàn)當(dāng)bj變化時(shí)，要使原來(lái)的基不變得到的基本可行解仍然是可行解，也就是所求的基變量的值一定要大于0。所謂使其對(duì)偶價(jià)格不變的bj的變化范圍，也就是使其最優(yōu)解的所有基變量不變，且所得的最優(yōu)解仍然是可行的bj的變化范圍。當(dāng)bj中的第k項(xiàng)bK變成時(shí)，也就是原來(lái)的初始單純形表中的b向量變成了b’向量這樣在最終單純形表中基變量XB的解就變成了如要使XB成為可行解，只要使上述等式的右邊>0，就可求出的取值范圍，也就是使得第K個(gè)約束條件的對(duì)偶價(jià)格不變的bk的變化范圍。，下面我們?nèi)砸缘诙吕?在最終單純形表上對(duì)bj進(jìn)行靈敏度分析。最終單純形表如下所示：表6-5我們對(duì)b1進(jìn)行靈敏度分析，因?yàn)樵诘谝粋€(gè)約束方程中含有松弛變量S1,實(shí)際意義可以描述為：當(dāng)設(shè)備臺(tái)時(shí)數(shù)的對(duì)偶價(jià)格不變，都為每設(shè)備臺(tái)時(shí)數(shù)在250與325之間變化，則設(shè)備臺(tái)時(shí)數(shù)的對(duì)偶價(jià)格不變，都為每臺(tái)設(shè)備臺(tái)時(shí)50元。三、約束方程系數(shù)矩陣A靈敏度分析下面分兩種情況討論1.在初始單純形表上的變量Xk的系數(shù)列Pk改變?yōu)镻’k經(jīng)過(guò)迭代后，在最終單純形表上Xk是非基變量。由于單純形表的迭代是約束方程的增廣矩陣的行變換，Pk變成Pk’僅僅影響最終單純形表上第k列數(shù)據(jù)，包括Xk的系數(shù)列、Zk以及δk，這時(shí)最終單純形表上的Xk的系數(shù)列就變成了B-1Pj’,而Zk就變成CBB-1Pk’，新的檢驗(yàn)數(shù)δk=Ck-CBB-1Pk’。若δk≤0，則原最優(yōu)解仍然為最優(yōu)解。若δk〉0，則繼續(xù)進(jìn)行迭代以求出最優(yōu)。例以第二章例1為基礎(chǔ)，設(shè)該廠除了生產(chǎn)Ι，Ⅱ種產(chǎn)品外，現(xiàn)在試制成一個(gè)新產(chǎn)品Ⅲ，已知生產(chǎn)產(chǎn)品Ⅲ,每件需要設(shè)備2臺(tái)時(shí)，并消耗A原料0.5公斤。B原料1.5公斤，獲利150元，問(wèn)該廠應(yīng)該生產(chǎn)該產(chǎn)品多少？解：這是一個(gè)增加新變量的問(wèn)題。我們可以把它認(rèn)為是一個(gè)改變變量X3在初始表上的系數(shù)列的問(wèn)題，表6-6例假設(shè)上例題中產(chǎn)品Ш的工藝結(jié)構(gòu)有了改進(jìn)，這時(shí)生產(chǎn)1件Ш產(chǎn)品需要使用1.5臺(tái)設(shè)備，消耗原料A為2千克，原料B為1千克，每件Ш產(chǎn)品的利潤(rùn)為160元，問(wèn)該廠的生產(chǎn)計(jì)劃是否要修改。解：首先求出X3在最終表上的系數(shù)列表6-7表6-8接下來(lái)又可以有新的迭代S3進(jìn)基，表6-9可知此規(guī)模的最優(yōu)解X1=0,X2=0,S1=0,S2=0,S3=50,X3=200,此時(shí)，最大目標(biāo)函數(shù)為32000元。也就是說(shuō)，該廠的新的生產(chǎn)計(jì)劃為不生產(chǎn)Ι、П產(chǎn)品，生產(chǎn)Ш產(chǎn)品200件,可獲得最大利潤(rùn)32000元。2.在初始表上的變量XK的系數(shù)PK改變?yōu)镻’K，經(jīng)過(guò)迭代后，在最終表上XK是基變量，在這種情況下原最優(yōu)解的可行性和最優(yōu)解都可能被破壞，問(wèn)題十分復(fù)雜，一般不去修改原表而是直接計(jì)算。四、增加一個(gè)約束條件的靈敏度分析在原線性規(guī)劃中增加一個(gè)約束條件時(shí),先將原問(wèn)題的最優(yōu)解的變量值代入新增的約束條件，如滿足則說(shuō)明新增的條件沒(méi)有起到限制作用，故原最優(yōu)解不變，否則將新增的約束添入原最終單純形表上進(jìn)一步求解。下面仍以第三章例1為例來(lái)加以說(shuō)明。例：假如該工廠除了在設(shè)備臺(tái)時(shí)，原材料A、B上對(duì)該廠的生產(chǎn)有限制外，還有電力供應(yīng)上的限制。最高供應(yīng)電量為5000度，而生產(chǎn)一個(gè)Ⅰ產(chǎn)品需要用電10度，而生產(chǎn)一個(gè)Ⅱ產(chǎn)品需要用電30度。試分析此時(shí)該廠獲得最大利潤(rùn)的生產(chǎn)計(jì)劃？解：先將原問(wèn)題的最優(yōu)解，X1=50，X2=250代入用電量的約束條件：得：10×50+30×250=500+7500>5000,所以原題的最優(yōu)解不是本題的最優(yōu)解。在用電量的約束條件中加入松馳變量S4后得：把這個(gè)約束條件加入到原最終單純形表上，其中S4為基變量，得表如下：表6-10在上表中的X1，X2不是單位向量，故進(jìn)行行的線性變換，得表6-11把上表中的S4行的約束可以寫為：上式兩邊乘以（-1），再加上人工變量a1得：用上式替換上表中的S4行，得下表：表6-12由上表可知，最優(yōu)解為：即該工廠在添加了用電限量以后的最優(yōu)生產(chǎn)計(jì)劃為Ⅰ產(chǎn)品生產(chǎn)140件，Ⅱ產(chǎn)品生產(chǎn)120件?！?線性規(guī)劃的對(duì)偶問(wèn)題每一個(gè)線性規(guī)劃問(wèn)題，都存在每一個(gè)與它密切相關(guān)的線性規(guī)劃的問(wèn)題，我們稱其為原問(wèn)題，另一個(gè)為對(duì)偶問(wèn)題。例題1某工廠在計(jì)劃期內(nèi)安排Ⅰ、Ⅱ兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需設(shè)備A、B、C臺(tái)時(shí)如表所示表6-13該工廠每生產(chǎn)一單位產(chǎn)品可獲利50元，每生產(chǎn)一單位產(chǎn)品Ⅱ可獲利100元，問(wèn)工廠應(yīng)分別生產(chǎn)多少產(chǎn)品和Ⅱ產(chǎn)品，才能使工廠獲利最多？解：設(shè)為產(chǎn)品的計(jì)劃產(chǎn)量，為產(chǎn)品Ⅱ的計(jì)劃產(chǎn)量，則有目標(biāo)函數(shù)：MaxZ=50+100約束條件：，現(xiàn)在我們從另一個(gè)角度來(lái)考慮這個(gè)問(wèn)題。假如有另外一個(gè)工廠要求租用該廠的設(shè)備A、B、C，那么該廠的廠長(zhǎng)應(yīng)該如何來(lái)確定合理的租金呢？設(shè)分別為設(shè)備A、B、C的每臺(tái)時(shí)的租金。為了敘述方便，這里把租金定義為扣除成本后的利潤(rùn)。作為出租者來(lái)說(shuō)，把生產(chǎn)單位Ⅰ產(chǎn)品所需各設(shè)備的臺(tái)時(shí)各總租金不應(yīng)低于原利潤(rùn)50元，即，否則就不出租還是用于生產(chǎn)Ⅰ產(chǎn)品以獲利50元；同樣把生產(chǎn)一單位Ⅱ產(chǎn)品所需各設(shè)備的臺(tái)時(shí)的總租金也不應(yīng)當(dāng)?shù)陀谠麧?rùn)100元，即，否則這些設(shè)備臺(tái)時(shí)就不出租，還是用于生產(chǎn)Ⅱ產(chǎn)品以獲利100元。但對(duì)于租用者來(lái)說(shuō)，他要求在滿足上述要求的前提下，也就是在出租者愿意出租的前提下盡量要求全部設(shè)備臺(tái)時(shí)的總租金越低越好，即min，這樣我們得到了該問(wèn)題的數(shù)學(xué)模型：目標(biāo)函數(shù)：約束條件：這樣從兩個(gè)不同的角度來(lái)考慮同一個(gè)工廠的最大利潤(rùn)（最小租金）的問(wèn)題，所建立起來(lái)的兩個(gè)線性模型就是一對(duì)對(duì)偶問(wèn)題，其中一個(gè)叫做原問(wèn)題，而另外一個(gè)叫對(duì)偶問(wèn)題。如果我們把求目標(biāo)函數(shù)最大值的線性規(guī)劃問(wèn)題看成原問(wèn)題，則求目標(biāo)函數(shù)最小值的線性規(guī)劃問(wèn)題看成對(duì)偶問(wèn)題。下面來(lái)研究這兩個(gè)問(wèn)題在數(shù)學(xué)模型上的關(guān)系。1求目標(biāo)函數(shù)最大值的線性規(guī)劃問(wèn)題中有n個(gè)變量m個(gè)約束條件，它的約束條件都是小于等于不等式。而其對(duì)偶則是求目標(biāo)函數(shù)為最小值的線性規(guī)劃問(wèn)題，有m個(gè)變量n個(gè)約束條件，其約束條件都為大于等于不等式。2原問(wèn)題的目標(biāo)函數(shù)中的變量系數(shù)為對(duì)偶問(wèn)題中的約束條件的右邊常數(shù)項(xiàng)，并且原問(wèn)題的目標(biāo)函數(shù)中的第i個(gè)變量的系數(shù)就等于對(duì)偶問(wèn)題中的第i個(gè)約束條件的右邊常數(shù)項(xiàng)。3原問(wèn)題的約束條件的右邊常數(shù)項(xiàng)為對(duì)偶問(wèn)題的目標(biāo)函數(shù)中的變量的系數(shù)。并且原問(wèn)題的第i個(gè)約束條件的右邊常數(shù)項(xiàng)就等于零對(duì)偶問(wèn)題的目標(biāo)函數(shù)中的第i個(gè)變量的系數(shù)。4對(duì)偶問(wèn)題的約束條件的系數(shù)矩陣A是原問(wèn)題約束矩陣的轉(zhuǎn)置。設(shè)A=則如果我們用矩陣形式來(lái)表示，則有原問(wèn)題：其中A是矩陣m*n，該問(wèn)題有m個(gè)約束條件n個(gè)變量，x=，b=,c=對(duì)偶問(wèn)題：其中是A的轉(zhuǎn)置，是b的轉(zhuǎn)置,是c的轉(zhuǎn)置,y=現(xiàn)在我們用單純形法求對(duì)偶問(wèn)題的解。加上剩余變量和人工變量，把此問(wèn)題化成標(biāo)準(zhǔn)型如下：把上述數(shù)據(jù)填入單純形表計(jì)算。表6-14由上表，最優(yōu)解：=50，，-f的最大值為-27500，即目標(biāo)函數(shù)f的最大值為f=27500元。從上面可知租金：A設(shè)備為50元，B設(shè)備為0元，C設(shè)備為50元。這樣把工廠的所有設(shè)備出租可共得租金27500元。對(duì)出租者來(lái)說(shuō)這租金是出租者愿意出租設(shè)備的最小費(fèi)用，因?yàn)檫@是目標(biāo)函數(shù)的最小值。通過(guò)比較，我們發(fā)現(xiàn)：對(duì)偶問(wèn)題的最優(yōu)解即最佳租金恰好等于原問(wèn)題各種設(shè)備的對(duì)偶價(jià)格，這在道理上也能講得通。對(duì)于兩個(gè)有對(duì)偶關(guān)系的線性規(guī)劃的問(wèn)題，我們只要求得了其中一個(gè)最優(yōu)解，就可以從這個(gè)問(wèn)題的對(duì)偶價(jià)格而求得其對(duì)偶問(wèn)題的最優(yōu)解，知道其中一個(gè)最優(yōu)值也就找到了其對(duì)偶問(wèn)題的最優(yōu)值，因?yàn)檫@兩個(gè)最優(yōu)值相等。下面來(lái)闡述如何寫出一個(gè)線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題。為了便于闡述，我們不妨以下面的線性規(guī)劃為例，寫出它的對(duì)偶問(wèn)題。S.T.這是一個(gè)求最大值的線性規(guī)劃問(wèn)題，為了寫出它的對(duì)偶問(wèn)題，我們不妨把它的約束條件都變換成取小于號(hào)的不等式。顯然第一個(gè)約束條件已符合要求，不要做任何變動(dòng)，而第二個(gè)約束條件，我們只要兩邊都乘以（-1），使不等號(hào)方向改變即可，得這樣第二個(gè)約束條件也就符合要求。對(duì)于第三個(gè)約束條件，我們可以用小于等于和大于等于兩個(gè)約束條件來(lái)替代它。即有顯然，這兩個(gè)約束條件與原來(lái)第三個(gè)約束條件是等價(jià)的，我們?cè)侔哑渲械膬蛇叾汲艘裕?1），得通過(guò)上面的一些變換，我們得到了一個(gè)和原線性規(guī)劃等價(jià)的線性規(guī)劃問(wèn)題：s.t.這個(gè)求最大值的線性規(guī)劃問(wèn)題的約束條件都取小于等于號(hào)，我們馬上可以寫出其對(duì)偶問(wèn)題：s.t.這里和一樣都是不同的決策變量，為了表示這兩個(gè)決策變量都來(lái)源于原問(wèn)題的第三個(gè)約束條件，記為。因?yàn)樵谠搶?duì)偶問(wèn)題中和的系數(shù)只相差一個(gè)符號(hào)，我們可以把上面的對(duì)偶問(wèn)題化為：s.t.進(jìn)一步，我們可以令，這時(shí)當(dāng)時(shí)，。當(dāng)時(shí)，。這也就是說(shuō)，盡管但的取值可以為正，可以為0，可以為負(fù)，即沒(méi)有非負(fù)限制。這樣我們把原規(guī)劃的對(duì)偶問(wèn)題化為s.t.沒(méi)有限制。對(duì)照原線性規(guī)劃問(wèn)題，我們可以知道：當(dāng)原線性規(guī)劃問(wèn)題的第i個(gè)約束條件取等號(hào)時(shí)，則其對(duì)偶問(wèn)題的i個(gè)決策變量沒(méi)有非負(fù)限制。如果當(dāng)原線性規(guī)劃問(wèn)題中的第i個(gè)決策變量沒(méi)有非負(fù)限制時(shí)，我們也可以用進(jìn)行替換，這里，，用類似的方法知道其對(duì)偶問(wèn)題中第i個(gè)約束條件取等號(hào)。另外，用大于等于0的兩個(gè)決策變量之差來(lái)代替無(wú)非負(fù)限制的決策變量也是求解含有無(wú)非負(fù)限制的決策變量的線性規(guī)劃問(wèn)題的一種方法。原線性規(guī)劃問(wèn)題為：s.t.無(wú)非負(fù)限制?！?對(duì)偶規(guī)劃的基本性質(zhì)對(duì)偶規(guī)劃的基本性質(zhì)1．對(duì)稱性。即對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。2．弱對(duì)偶性。即對(duì)于原問(wèn)題（Ⅰ）和對(duì)偶問(wèn)題（Ⅱ）的可行解都有C≤bT。由弱對(duì)偶性，可得出以下推論：（1）原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界；反之對(duì)偶問(wèn)題任一可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界。（2）如原問(wèn)題有可行解且目標(biāo)函數(shù)值無(wú)界（或具有無(wú)界解），則其對(duì)偶問(wèn)題無(wú)可行解；反之對(duì)偶問(wèn)題有可行解且目標(biāo)函數(shù)值無(wú)界，則其原問(wèn)題無(wú)可行解（注意：本點(diǎn)性質(zhì)的逆不成立，當(dāng)對(duì)偶問(wèn)題無(wú)可行解時(shí)，其原問(wèn)題或具有無(wú)界解或無(wú)可行解，反之亦然）。（3）若原問(wèn)題有可行解而其對(duì)偶問(wèn)題無(wú)可行解，則原問(wèn)題目標(biāo)函數(shù)值無(wú)界；反之對(duì)偶問(wèn)題有可行解而其原問(wèn)題無(wú)可行解，則對(duì)偶問(wèn)題的目標(biāo)函數(shù)值無(wú)界。3．最優(yōu)性。如果是原問(wèn)題(Ⅰ)的可行解，是對(duì)偶問(wèn)題(Ⅱ)的可行解，并且C=bT，則和分別為原問(wèn)題(Ⅰ)和對(duì)偶問(wèn)題(Ⅱ)的最優(yōu)解。4．強(qiáng)對(duì)偶性。即若原問(wèn)題(Ⅰ)及其對(duì)偶問(wèn)題(Ⅱ)都有可行解，則兩者都有最優(yōu)解；且它們的最優(yōu)解的目標(biāo)函數(shù)都相等。5．互補(bǔ)松弛性。在線性規(guī)劃問(wèn)題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；反之，如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零也即若yi*>0,則有若，則有yi*=0§4對(duì)偶單純形法對(duì)偶單純形法也是解決線性規(guī)劃問(wèn)題的一種方法。對(duì)偶單純形法是在保持原有問(wèn)題的所有檢驗(yàn)數(shù)都小于0的情況下，通過(guò)迭代使得所有的約束都大于等于0，最后求得最優(yōu)解。簡(jiǎn)化計(jì)算是對(duì)偶單純形法的優(yōu)點(diǎn)，但是它在使用上有很大的局限，這主要是大多數(shù)線性規(guī)劃問(wèn)題很難找到初始解使得其所有檢驗(yàn)數(shù)都小于0。但是在靈敏度分析中，有時(shí)需要對(duì)偶單純形法，這樣可以簡(jiǎn)化處理。下面以第二節(jié)例一為例。上節(jié)分析中已知當(dāng)250≤b’1≤325時(shí)第一個(gè)約束條件的對(duì)偶價(jià)格不變，現(xiàn)在b’1=300變成b’1=350，請(qǐng)問(wèn)這時(shí)第一個(gè)約束方程的對(duì)偶價(jià)格應(yīng)為多少呢？解：求出在第二次迭代表上的常數(shù)列1.確定出基變量，在常數(shù)列中找一個(gè)最小的負(fù)常量，把這個(gè)常量所在行作為出基變量表6-15表6-164.檢查常數(shù)列值，若已經(jīng)都非負(fù)結(jié)束迭代，即為最優(yōu)，如果還有負(fù)數(shù)重復(fù)1-4步。第七章運(yùn)輸問(wèn)題§1運(yùn)輸模型§2運(yùn)輸問(wèn)題的計(jì)算機(jī)求解§3運(yùn)輸問(wèn)題的應(yīng)用§4*運(yùn)輸問(wèn)題的表上作業(yè)法§1運(yùn)輸模型某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？解：產(chǎn)銷平衡問(wèn)題：總產(chǎn)量=總銷量設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：一般運(yùn)輸模型：產(chǎn)銷平衡A1、A2、…、Am表示某物資的m個(gè)產(chǎn)地；B1、B2、…、Bn表示某物質(zhì)的n個(gè)銷地；si表示產(chǎn)地Ai的產(chǎn)量；dj表示銷地Bj的銷量；cij表示把物資從產(chǎn)地Ai運(yùn)往銷地Bj的單位運(yùn)價(jià)。設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問(wèn)題的模型：mnMinf=cijxiji=1j=1ns.t.xij=sii=1,2,…,mj=1mxij=djj=1,2,…,ni=1xij≥0(i=1,2,…,m;j=1,2,…,n)變化：1）有時(shí)目標(biāo)函數(shù)求最大。如求利潤(rùn)最大或營(yíng)業(yè)額最大等；2）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，在模型中直接加入約束條件（等式或不等式約束)；3）產(chǎn)銷不平衡時(shí)，可加入假想的產(chǎn)地（銷大于產(chǎn)時(shí)）或銷地（產(chǎn)大于銷時(shí)）?！?運(yùn)輸問(wèn)題的計(jì)算機(jī)求解例2、某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？解：增加一個(gè)虛設(shè)的銷地運(yùn)輸費(fèi)用為0例3、某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？解：增加一個(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為0產(chǎn)銷不平衡的運(yùn)輸問(wèn)題例4、石家莊北方研究院有一、二、三三個(gè)區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，價(jià)格、質(zhì)量相同。供應(yīng)能力分別為1500、4000噸，運(yùn)價(jià)為：由于需大于供，經(jīng)院研究決定一區(qū)供應(yīng)量可減少0--300噸，二區(qū)必須滿足需求量，三區(qū)供應(yīng)量不少于1500噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。解：根據(jù)題意，作出產(chǎn)銷平衡與運(yùn)價(jià)表：這里M代表一個(gè)很大的正數(shù)，其作用是強(qiáng)迫相應(yīng)的x31、x33、x34取值為0。例5、設(shè)有A、B、C三個(gè)化肥廠供應(yīng)1、2、3、4四個(gè)地區(qū)的農(nóng)用化肥。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表：試求總費(fèi)用為最低的化肥調(diào)撥方案。解：根據(jù)題意，作出產(chǎn)銷平衡與運(yùn)價(jià)表：最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為M，而最高要求與最低要求的差允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為0。對(duì)應(yīng)4”的銷量50是考慮問(wèn)題本身適當(dāng)取的數(shù)據(jù)，根據(jù)產(chǎn)銷平衡要求確定D的產(chǎn)量為50。生產(chǎn)與儲(chǔ)存問(wèn)題例6、某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10、15、25、20臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如右表。如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用0.15萬(wàn)元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。解：設(shè)xij為第i季度生產(chǎn)的第j季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足：交貨：x11=10生產(chǎn)：x11+x12+x13+x14≤25x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10把第i季度生產(chǎn)的柴油機(jī)數(shù)目看作第i個(gè)生產(chǎn)廠的產(chǎn)量；把第j季度交貨的柴油機(jī)數(shù)目看作第j個(gè)銷售點(diǎn)的銷量；成本加儲(chǔ)存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)?？蓸?gòu)造下列產(chǎn)銷平衡問(wèn)題：目標(biāo)函數(shù)：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44二、生產(chǎn)與儲(chǔ)存問(wèn)題例7、光明儀器廠生產(chǎn)電腦繡花機(jī)是以產(chǎn)定銷的。已知1至6月份各月的生產(chǎn)能力、合同銷量和單臺(tái)電腦繡花機(jī)平均生產(chǎn)費(fèi)用見(jiàn)下表：已知上年末庫(kù)存103臺(tái)繡花機(jī)，如果當(dāng)月生產(chǎn)出來(lái)的機(jī)器當(dāng)月不交貨，則需要運(yùn)到分廠庫(kù)房，每臺(tái)增加運(yùn)輸成本0.1萬(wàn)元,每臺(tái)機(jī)器每月的平均倉(cāng)儲(chǔ)費(fèi)、維護(hù)費(fèi)為0.2萬(wàn)元。在7--8月份銷售淡季，全廠停產(chǎn)1個(gè)月，因此在6月份完成銷售合同后還要留出庫(kù)存80臺(tái)。加班生產(chǎn)機(jī)器每臺(tái)增加成本1萬(wàn)元。問(wèn)應(yīng)如何安排1--6月份的生產(chǎn)，可使總的生產(chǎn)費(fèi)用（包括運(yùn)輸、倉(cāng)儲(chǔ)、維護(hù)）最少？解：這個(gè)生產(chǎn)存儲(chǔ)問(wèn)題可化為運(yùn)輸問(wèn)題來(lái)做?？紤]：各月生產(chǎn)與交貨分別視為產(chǎn)地和銷地1）1--6月份合計(jì)生產(chǎn)能力（包括上年末儲(chǔ)存量）為743臺(tái)，銷量為707臺(tái)。設(shè)一假想銷地銷量為36；2）上年末庫(kù)存103臺(tái)，只有倉(cāng)儲(chǔ)費(fèi)和運(yùn)輸費(fèi)，把它列為第0行；3）6月份的需求除70臺(tái)銷量外，還要80臺(tái)庫(kù)存，其需求應(yīng)為70+80=150臺(tái)；4）1--6表示1--6月份正常生產(chǎn)情況，1’--6’表示1--6月份加班生產(chǎn)情況。產(chǎn)銷平衡與運(yùn)價(jià)表：用“管理運(yùn)籌學(xué)”軟件解得的結(jié)果是：1-6月最低生產(chǎn)費(fèi)用為8307.5萬(wàn)元，每月的銷售安排如下表所示三、轉(zhuǎn)運(yùn)問(wèn)題：例8、在原運(yùn)輸問(wèn)題上增加若干轉(zhuǎn)運(yùn)站。運(yùn)輸方式有：產(chǎn)地轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)站銷地、產(chǎn)地產(chǎn)地、產(chǎn)地銷地、銷地轉(zhuǎn)運(yùn)站、銷地產(chǎn)地等。例8、騰飛電子儀器公司在大連和廣州有兩個(gè)分廠生產(chǎn)同一種儀器，大連分廠每月生產(chǎn)400臺(tái)，廣州分廠每月生產(chǎn)600臺(tái)。該公司在上海和天津有兩個(gè)銷售公司負(fù)責(zé)對(duì)南京、濟(jì)南、南昌、青島四個(gè)城市的儀器供應(yīng)。另外因?yàn)榇筮B距離青島較近，公司同意大連分廠向青島直接供貨，運(yùn)輸費(fèi)用如圖，單位是百元。問(wèn)應(yīng)該如何調(diào)運(yùn)儀器，可使總運(yùn)輸費(fèi)用最低？圖中1-廣州、2-大連、3-上海、4-天津、5-南京、6-濟(jì)南、7-南昌、8-青島解：設(shè)xij為從i到j(luò)的運(yùn)輸量，可得到有下列特點(diǎn)的線性規(guī)劃模型：目標(biāo)函數(shù)：Minf=所有可能的運(yùn)輸費(fèi)用（運(yùn)輸單價(jià)與運(yùn)輸量乘積之和）約束條件：對(duì)產(chǎn)地（發(fā)點(diǎn)）i：輸出量-輸入量=產(chǎn)量對(duì)轉(zhuǎn)運(yùn)站（中轉(zhuǎn)點(diǎn)）：輸入量-輸出量=0對(duì)銷地（收點(diǎn)）j：輸入量-輸出量=銷量目標(biāo)函數(shù)：Minf=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48約束條件：s.t.x13+x14≤600(廣州分廠供應(yīng)量限制）x23+x24+x28≤400(大連分廠供應(yīng)量限制）-x13-x23+x35+x36+x37+x38=0（上海銷售公司，轉(zhuǎn)運(yùn)站）-x14-x24+x45+x46+x47+x48=0（天津銷售公司，轉(zhuǎn)運(yùn)站）x35+x45=200（南京的銷量）x36+x46=150（濟(jì)南的銷量）x37+x47=350（南昌的銷量）x38+x48+x28=300（青島的銷量）xij≥0,i,j=1,2,3,4,5,6,7,8用“管理運(yùn)籌學(xué)”軟件求得結(jié)果：x13=550x14=50；x23=0x24=100x28=300；x35=200x36=0x37=350x38=0；x45=0x46=150x47=0x48=0。最小運(yùn)輸費(fèi)用為：4600百元例9、某公司有A1、A2、A3三個(gè)分廠生產(chǎn)某種物資，分別供應(yīng)B1、B2、B3、B4四個(gè)地區(qū)的銷售公司銷售。假設(shè)質(zhì)量相同，有關(guān)數(shù)據(jù)如下表：試求總費(fèi)用為最少的調(diào)運(yùn)方案。假設(shè)：1.每個(gè)分廠的物資不一定直接發(fā)運(yùn)到銷地，可以從其中幾個(gè)產(chǎn)地集中一起運(yùn)；2.運(yùn)往各銷地的物資可以先運(yùn)給其中幾個(gè)銷地，再轉(zhuǎn)運(yùn)給其他銷地；3.除產(chǎn)銷地之外，還有幾個(gè)中轉(zhuǎn)站，在產(chǎn)地之間、銷地之間或在產(chǎn)地與銷地之間轉(zhuǎn)運(yùn)。運(yùn)價(jià)如下表：解：把此轉(zhuǎn)運(yùn)問(wèn)題轉(zhuǎn)化為一般運(yùn)輸問(wèn)題：1、把所有產(chǎn)地、銷地、轉(zhuǎn)運(yùn)站都同時(shí)看作產(chǎn)地和銷地；2、運(yùn)輸表中不可能方案的運(yùn)費(fèi)取作M，自身對(duì)自身的運(yùn)費(fèi)為0；3、Ai：產(chǎn)量為20+原產(chǎn)量，銷量為20；Ti：產(chǎn)量、銷量均為20；Bi：產(chǎn)量為20，銷量為20+原銷量，其中20為各點(diǎn)可能變化的最大流量；4、對(duì)于最優(yōu)方案，其中xii為自身對(duì)自身的運(yùn)量，實(shí)際上不進(jìn)行運(yùn)作。擴(kuò)大的運(yùn)輸問(wèn)題產(chǎn)銷平衡與運(yùn)價(jià)表：§4*運(yùn)輸問(wèn)題的表上作業(yè)法表上作業(yè)法是一種求解運(yùn)輸問(wèn)題的特殊方法，其實(shí)質(zhì)是單純形法。運(yùn)輸問(wèn)題都存在最優(yōu)解。計(jì)算過(guò)程（假設(shè)產(chǎn)銷平衡）：1.找出初始基本可行解。對(duì)于有m個(gè)產(chǎn)地n個(gè)銷地的產(chǎn)銷平衡問(wèn)題，則有m個(gè)關(guān)于產(chǎn)量的約束方程和n個(gè)關(guān)于銷量的約束方程。由于產(chǎn)銷平衡，其模型最多只有m+n-1個(gè)獨(dú)立的約束方程，即運(yùn)輸問(wèn)題有m+n-1個(gè)基變量。在m×n的產(chǎn)銷平衡表上給出m+n-1個(gè)數(shù)字格，其相對(duì)應(yīng)的調(diào)運(yùn)量的值即為基變量的值。2.求各非基變量的檢驗(yàn)數(shù)，即檢驗(yàn)除了上述m+n-1個(gè)基變量以外的空格的檢驗(yàn)數(shù)判別是否達(dá)到最優(yōu)解，如果已是最優(yōu)，停止計(jì)算，否則轉(zhuǎn)到下一步。3.確定入基變量和出基變量，找出新的基本可行解。在表上用閉回路法調(diào)整。4.重復(fù)2、3直到得到最優(yōu)解。例10、喜慶食品公司有三個(gè)生產(chǎn)面包的分廠A1，A2，A3，有四個(gè)銷售公司B1，B2，B3，B4，其各分廠每日的產(chǎn)量、各銷售公司每日的銷量以及各分廠到各銷售公司的單位運(yùn)價(jià)如表所示，在表中產(chǎn)量與銷量的單位為噸，運(yùn)價(jià)的單位為百元/噸。問(wèn)該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品在滿足各銷點(diǎn)的需求量的前提下總運(yùn)費(fèi)最少？這是一個(gè)產(chǎn)銷平衡的運(yùn)輸問(wèn)題，因此不需要再設(shè)假想產(chǎn)地和銷地了。一、確定初始基本可行解為了把初始基本可行解與運(yùn)價(jià)區(qū)分開(kāi)，我們把運(yùn)價(jià)放在每一欄的右上角，每一欄的中間寫上初始基本可行解（調(diào)運(yùn)量）。1.西北角法：先從表的左上角（即西北角）的變量x11開(kāi)始分配運(yùn)輸量，并使x11取盡可能大的值，即x11=min(7,3)=3,則x21與x31必為零。同時(shí)把B1的銷量與A1的產(chǎn)量都減去3填入銷量和產(chǎn)量處，劃去原來(lái)的銷量和產(chǎn)量。同理可得余下的初始基本可行解。2.最小元素法西北角法是對(duì)西北角的變量分配運(yùn)輸量，而最小元素法是就近供應(yīng)，即對(duì)單位運(yùn)價(jià)最小的變量分配運(yùn)輸量。在表上找到單位運(yùn)價(jià)最小的x21，并使x21取盡可能大的值，即x21=min(4,3)=3,把A1的產(chǎn)量改為1，B1的銷量改為0，并把B1列劃去。在剩下的3×3矩陣中再找最小運(yùn)價(jià)，同理可得其他的基本可行解。一般來(lái)說(shuō)用最小元素法求得的初始基本可行解比西北角法求得的總運(yùn)價(jià)要少。這樣從用最小元素法求得的初始基本可行解出發(fā)求最優(yōu)解的迭代次數(shù)可能少一些。在求初始基本可行解時(shí)要注意的兩個(gè)問(wèn)題：1.當(dāng)我們?nèi)《▁ij的值之后，會(huì)出現(xiàn)Ai的產(chǎn)量與Bj的銷量都改為零的情況，這時(shí)只能劃去Ai行或Bj列，但不能同時(shí)劃去Ai行與Bj列。2.用最小元素法時(shí)，可能會(huì)出現(xiàn)只剩下一行或一列的所有格均未填數(shù)或未被劃掉的情況，此時(shí)在這一行或者一列中除去已填上的數(shù)外均填上零，不能按空格劃掉。這樣可以保證填過(guò)數(shù)或零的格為m+n-1個(gè)，即保證基變量的個(gè)數(shù)為m+n-1個(gè)。二、最優(yōu)解的判別1.閉回路法所謂閉回路是在已給出的調(diào)運(yùn)方案的運(yùn)輸表上從一個(gè)代表非基變量的空格出發(fā)，沿水平或垂直方向前進(jìn)，只有遇到代表基變量的填入數(shù)字的格才能向左或右轉(zhuǎn)90度（當(dāng)然也可以不改變方向）繼續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)的那個(gè)空格，由此形成的封閉折線叫做閉回路。一個(gè)空格存在唯一的閉回路。所謂閉回路法，就是對(duì)于代表非基變量的空格（其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整為1，由于產(chǎn)銷平衡的要求,我們必須對(duì)這個(gè)空格的閉回路的頂點(diǎn)的調(diào)運(yùn)量加上或減少1。最后我們計(jì)算出由這些變化給整個(gè)運(yùn)輸方案的總運(yùn)輸費(fèi)帶來(lái)的變化。如果所有代表非基變量的空格的檢驗(yàn)數(shù)也即非基變量的檢驗(yàn)數(shù)都大于等于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解。從非基變量x11出發(fā)，找到一個(gè)閉回路如上表所示?；芈酚兴膫€(gè)頂點(diǎn)，除x11外，其余都為基變量?，F(xiàn)在把x11的調(diào)運(yùn)量從零增加為1噸，運(yùn)費(fèi)也增加了3元，為了使A1產(chǎn)量平衡，x13必須減少1噸，運(yùn)費(fèi)減少3元。為了B3的銷量平衡，x23必須增加1噸，運(yùn)費(fèi)增加2元。同理把x21減少1噸，運(yùn)費(fèi)減少1元。調(diào)整后，總運(yùn)費(fèi)增加了3-3+2-1=1元。說(shuō)明如果讓x11為基變量，運(yùn)費(fèi)就會(huì)增加，其增加值1作為x11的檢驗(yàn)數(shù)，為了區(qū)別調(diào)整量，我們把1加圈。用同樣的方法可以找出所有空格（即非基變量）的檢驗(yàn)數(shù)。2.位勢(shì)法所謂位勢(shì)法，我們對(duì)運(yùn)輸表上的每一行賦予一個(gè)數(shù)值ui，對(duì)每一列賦予一個(gè)數(shù)值vj，它們的數(shù)值是由基變量xij的檢驗(yàn)數(shù)所決定的，則非基變量xij的檢驗(yàn)數(shù)就可以用公式求出。我們先給u1賦個(gè)任意數(shù)值，不妨設(shè)u1=0，則從基變量x13的檢驗(yàn)數(shù)求得v3=c13-u1=3-0=3。同理可以求得v4=10，u2=-1等等見(jiàn)上表。檢驗(yàn)值的求法即用公式，如。三、改進(jìn)運(yùn)輸方案的辦法——閉回路調(diào)整法當(dāng)表中的某個(gè)檢驗(yàn)數(shù)小于零時(shí)，方案不為最優(yōu)，需要調(diào)整。方法是：選取所有負(fù)檢驗(yàn)數(shù)最小的非基變量作為入基變量，以求盡快實(shí)現(xiàn)最優(yōu)。本例中取，表明增加一個(gè)單位的x24運(yùn)輸量，可使得總運(yùn)費(fèi)減少1。在以x24為出發(fā)點(diǎn)的閉回路中，找出所有偶數(shù)的頂點(diǎn)的調(diào)運(yùn)量：x14=3，x23=1，x24=min(3,1)=1。把所有閉回路上為偶數(shù)頂點(diǎn)的運(yùn)輸量都減少這個(gè)值，奇數(shù)頂點(diǎn)的運(yùn)輸量都增加這個(gè)值(見(jiàn)下表)。對(duì)上表用位勢(shì)法進(jìn)行檢驗(yàn)如下表四、如何找多個(gè)最優(yōu)方案識(shí)別是否有多個(gè)最優(yōu)解的方法和單純形表法一樣，只需看最優(yōu)方案中是否存在非基變量的檢驗(yàn)數(shù)為零。如在本題中給出的最優(yōu)運(yùn)輸方案中x11的檢驗(yàn)數(shù)為0，可知此運(yùn)輸問(wèn)題有多個(gè)最優(yōu)解。只要把x11作為入基變量，調(diào)整運(yùn)輸方案，就可得到另一個(gè)最優(yōu)方案。第八章整數(shù)規(guī)劃§1整數(shù)規(guī)劃的圖解法§2整數(shù)規(guī)劃的計(jì)算機(jī)求解§3整數(shù)規(guī)劃的應(yīng)用§4整數(shù)規(guī)劃的分枝定界法求整數(shù)解的線性規(guī)劃問(wèn)題，不是用四舍五入法或去尾法對(duì)線性規(guī)劃的非整數(shù)解加以處理都能解決的，而要用整數(shù)規(guī)劃的方法加以解決。在整數(shù)規(guī)劃中，如果所有的變量都為非負(fù)整數(shù)，則稱為純整數(shù)規(guī)劃問(wèn)題；如果有一部分變量為負(fù)整數(shù)，則稱之為混合整數(shù)規(guī)劃問(wèn)題。在整數(shù)規(guī)劃中，如果變量的取值只限于0和1，這樣的變量我們稱之為0-1變量。在純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃問(wèn)題中，如果所有的變量都為0-1變量，則稱之為0-1規(guī)劃?！?整數(shù)規(guī)劃的圖解法例1.某公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表所示。表8-1甲種貨物至多托運(yùn)4件，問(wèn)兩種貨物各托運(yùn)多少件，可使獲得利潤(rùn)最大。解：設(shè)x1、x2分別為甲、乙兩種貨物托運(yùn)的件數(shù)，建立模型目標(biāo)函數(shù)：Maxz=2x1+3x2約束條件：s.t.195x1+273x2≤13654x1+40x2≤140x1≤4x1，x2≥0為整數(shù)。如果去掉最后一個(gè)約束，就是一個(gè)線性規(guī)劃問(wèn)題。利用圖解法，圖8-2得到線性規(guī)劃的最優(yōu)解為x1=2.44,x2=3.26,目標(biāo)函數(shù)值為14.66。由圖表可看出，整數(shù)規(guī)劃的最優(yōu)解為x1=4,x2=2,目標(biāo)函數(shù)值為14。性質(zhì)1：任何求最大目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標(biāo)函數(shù)值小于或等于相應(yīng)的線性規(guī)劃的最大目標(biāo)函數(shù)值；任何求最小目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標(biāo)函數(shù)值大于或等于相應(yīng)的線性規(guī)劃的最小目標(biāo)函數(shù)值。PAGEPAGE69§2整數(shù)規(guī)劃的計(jì)算機(jī)求解例2：Maxz=3x1+x2+3x3s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x1,x2,x3≥0為整數(shù)用《管理運(yùn)籌學(xué)》軟件求解得：x1=5x2=2x3=2例3：Maxz=3x1+x2+3x3s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x3≤1x1,x2,x3≥0x1，x3為整數(shù)x3為0-1變量用《管理運(yùn)籌學(xué)》軟件求解得：x1=4x2=1.25x3=1z=16.25§3整數(shù)規(guī)劃的應(yīng)用一、投資場(chǎng)所的選擇例4、京成畜產(chǎn)品公司計(jì)劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個(gè)位置Aj(j＝1，2，3，…，10)可供選擇，考慮到各地區(qū)居民的消費(fèi)水平及居民居住密集度，規(guī)定：在東區(qū)由A1，A2，A3三個(gè)點(diǎn)至多選擇兩個(gè)；在西區(qū)由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)由A6，A7兩個(gè)點(diǎn)中至少選一個(gè)；在北區(qū)由A8，A9，A10三個(gè)點(diǎn)中至少選兩個(gè)。表8-3Aj各點(diǎn)的設(shè)備投資及每年可獲利潤(rùn)由于地點(diǎn)不同都是不一樣的，預(yù)測(cè)情況見(jiàn)表所示(單位：萬(wàn)元)。但投資總額不能超過(guò)720萬(wàn)元，問(wèn)應(yīng)選擇哪幾個(gè)銷售點(diǎn)，可使年利潤(rùn)為最大?解：設(shè)：0--1變量Xi=1(Ai點(diǎn)被選用）或0(Ai點(diǎn)沒(méi)被選用）。這樣我們可建立如下的數(shù)學(xué)模型：MaxZ=36X1+0X2+50X3+22X4+20X5+30X6+25X7+48X8+58X9+61X10s.t.100X1+120X2+150X3+80X4+70X5+90X6+80X7+140X8+160X9+180X10≤720X1+X2+X3≤2X4+X5≥1X6+X7≥1X8+X9+X10≥2Xj≥0且xj為0--1變量，i=1,2,3,……,10二、固定成本問(wèn)題例5．高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器所需的各種資源的數(shù)量如表所示。不考慮固定費(fèi)用，每種容器售出一只所得的利潤(rùn)分別為4萬(wàn)元、5萬(wàn)元、6萬(wàn)元，可使用的金屬板有500噸，勞動(dòng)力有300人/月，機(jī)器有100臺(tái)/月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：小號(hào)是l00萬(wàn)元，中號(hào)為150萬(wàn)元，大號(hào)為200萬(wàn)元?，F(xiàn)在要制定一個(gè)生產(chǎn)計(jì)劃，使獲得的利潤(rùn)為最大。表8-4解：這是一個(gè)整數(shù)規(guī)劃的問(wèn)題。設(shè)x1，x2，x3分別為小號(hào)容器、中號(hào)容器和大號(hào)容器的生產(chǎn)數(shù)量。各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時(shí)才投入，為了說(shuō)明固定費(fèi)用的這種性質(zhì)，設(shè)yi=1(當(dāng)生產(chǎn)第i種容器,即xi＞0時(shí))或0（當(dāng)不生產(chǎn)第i種容器即xi=0時(shí)）。引入約束xi≤Myi，i=1，2，3，M充分大，以保證當(dāng)yi=0時(shí)，xi=0。這樣我們可建立如下的數(shù)學(xué)模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300x1+2x2+3x3≤100xi≤Myi，i=1，2，3，M充分大xj≥0yj為0--1變量，i=1,2,3三、指派問(wèn)題有n項(xiàng)不同的任務(wù)，恰好n個(gè)人可分別承擔(dān)這些任務(wù)，但由于每人特長(zhǎng)不同，完成各項(xiàng)任務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必須指派每個(gè)人去完成一項(xiàng)任務(wù)，怎樣把n項(xiàng)任務(wù)指派給n個(gè)人，使得完成n項(xiàng)任務(wù)的總的效率最高，這就是指派問(wèn)題。例6．有四個(gè)工人，要分別指派他們完成四項(xiàng)不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表所示，問(wèn)應(yīng)如何指派工作，才能使總的消耗時(shí)間為最少。表8-5解：引入0—1變量Xij，并令Xij=1(當(dāng)指派第i人去完成第j項(xiàng)工作時(shí))或0（當(dāng)不指派第i人去完成第j項(xiàng)工作時(shí))．這可以表示為一個(gè)0--1整數(shù)規(guī)劃問(wèn)題：Minz=15X11+18X12+21X13+24X14+19X21+23X22+22X23+18X24+26X31+17X32+16X33+19X34+19X41+21X42+23X43+17X44s.t.X11+X12+X13+X14=1(甲只能干一項(xiàng)工作)X21+X22+X23+X24=1(乙只能干一項(xiàng)工作)X31+X32+X33+X34=1(丙只能干一項(xiàng)工作)X41+X42+X43+X44=1(丁只能干一項(xiàng)工作)X11+X21+X31+X41=1(A工作只能一人干)X12+X22+X32+X42=1(B工作只能一人干)X13+X23+X33+X43=1(C工作只能一人干)X14+X24+X34+X44=1(D工作只能一人干)Xij為0--1變量，i,j=1,2,3,4***求解可用《管理運(yùn)籌學(xué)》軟件中整數(shù)規(guī)劃方法。四、分布系統(tǒng)設(shè)計(jì)例7．某企業(yè)在A1地已有一個(gè)工廠，其產(chǎn)品的生產(chǎn)能力為30千箱，為了擴(kuò)大生產(chǎn)，打算在A2，A3，A4，A5地中再選擇幾個(gè)地方建廠。已知在A2，A3，A4，A5地建廠的固定成本分別為175千元、300千元、375千元、500千元，另外，A1產(chǎn)量及A2，A3，A4，A5建成廠的產(chǎn)量，那時(shí)銷地的銷量以及產(chǎn)地到銷地的單位運(yùn)價(jià)(每千箱運(yùn)費(fèi))如下表所示。a)問(wèn)應(yīng)該在哪幾個(gè)地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運(yùn)輸費(fèi)用之和最小?b)如果由于政策要求必須在A2，A3地建一個(gè)廠，應(yīng)在哪幾個(gè)地方建廠?表8-6解：a)設(shè)Xij為從Ai運(yùn)往Bj的運(yùn)輸量(單位千箱)，Yk=1(當(dāng)Ak被選中時(shí))或0（當(dāng)Ak沒(méi)被選中時(shí)),k=2,3,4,5．這可以表示為一個(gè)整數(shù)規(guī)劃問(wèn)題：Minz=175Y2+300Y3+375Y4+500Y5+8X11+4X12+3X13+5X21+2X22+3X23+4X31+3X32+4X33+9X41+7X42+5X43+10X51+4X52+2X53其中前4項(xiàng)為固定投資額，后面的項(xiàng)為運(yùn)輸費(fèi)用。s.t.X11+X12+X13≤30(A1廠的產(chǎn)量限制)X21+X22+X23≤10Y2(A2廠的產(chǎn)量限制)X31+X32+X33≤20Yy3(A3廠的產(chǎn)量限制)X41+X42+X43≤30Y4(A4廠的產(chǎn)量限制)X51+X52+X53≤40Y5(A5廠的產(chǎn)量限制)X11+X21+X31+X41+X51=30(B1銷地的限制)X12+X22+X32+X42+X52=20(B2銷地的限制)X13+X23+X33+X43+X53=20(B3銷地的限制)Xij≥0，i=1,2,3,4,5；j=1,2,3，yk為0--1變量，k=2,3,4,5。***求解可用《管理運(yùn)籌學(xué)》軟件中整數(shù)規(guī)劃方法。五、投資問(wèn)題例8．某公司在今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第四年每年年初需要投資，并于次年末回收本利115%，但要求第一年投資最低金額為4萬(wàn)元，第二、三、四年不限；項(xiàng)目B：第三年初需要投資，到第五年末能回收本利128％，但規(guī)定最低投資金額為3萬(wàn)元，最高金額為5萬(wàn)元；項(xiàng)目C：第二年初需要投資，到第五年末能回收本利140%，但規(guī)定其投資額或?yàn)?萬(wàn)元或?yàn)?萬(wàn)元或?yàn)?萬(wàn)元或?yàn)?萬(wàn)元。項(xiàng)目D：五年內(nèi)每年初可購(gòu)買公債，于當(dāng)年末歸還，并加利息6%，此項(xiàng)投資金額不限。該部門現(xiàn)有資金10萬(wàn)元，問(wèn)它應(yīng)如何確定給這些項(xiàng)目的每年投資額，使到第五年末擁有的資金本利總額為最大?解：1)設(shè)XiA、XiB、XiC、XiD(i＝1，2，3，4，5)分別表示第i年年初給項(xiàng)目A，B，C，D的投資額；設(shè)yiA，yiB，是0—1變量，并規(guī)定取1時(shí)分別表示第i年給A、B投資，否則取0（i=1,2,3,4,5）。設(shè)yiC是非負(fù)整數(shù)變量，并規(guī)定：第2年投資C項(xiàng)目8萬(wàn)元時(shí)，取值為4；第2年投資C項(xiàng)目6萬(wàn)元時(shí)，取值3；第2年投資C項(xiàng)目4萬(wàn)元時(shí)，取值2；第2年投資C項(xiàng)目2萬(wàn)元時(shí)，取值1；第2年不投資C項(xiàng)目時(shí)，取值0；這樣我們建立如下的決策變量：第1年第2年第3年第4年第5年Ax1Ax2Ax3Ax4ABx3BCx2C=20000y2CDx1Dx2Dx3Dx4Dx5D2）約束條件：第一年：年初有100000元，D項(xiàng)目在年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是x1A+x1D=100000；第二年：A的投資第二年末才可收回，故第二年年初的資金為1.06x1D，于是x2A+x2C+x2D=1.06x1D；第三年：年初的資金為1.15x1A+1.06x2D，于是x3A+x3B+x3D=1.15x1A+1.06x2D；第四年：年初的資金為1.15x2A+1.06x3D，于是x4A+x4D=1.15x2A+1.06x3D；第五年：年初的資金為1.15x3A+1.06x4D，于是x5D=1.15x3A+1.06x4D。關(guān)于項(xiàng)目A的投資額規(guī)定:x1A≥40000y1A，x1A≤200000y1A，200000是足夠大的數(shù)；保證當(dāng)y1A=0時(shí)，x1A=0；當(dāng)y1A=1時(shí)，x1A≥40000。關(guān)于項(xiàng)目B的投資額規(guī)定:x3B≥30000y3B，x3B≤50000y3B；保證當(dāng)y3B=0時(shí)，x3B=0；當(dāng)y3B=1時(shí)，50000≥x3B≥30000。關(guān)于項(xiàng)目C的投資額規(guī)定:x2C=20000y2C，y2C=0，1，2，3，4。3）目標(biāo)函數(shù)及模型：Maxz=1.15x4A+1.40x2C+1.28x3B+1.06x5Ds.t.x1A+x1D=100000；x2A+x2C+x2D=1.06x1D；x3A+x3B+x3D=1.15x1A+1.06x2D；x4A+x4D=1.15x2A+1.06x3D；x5D=1.15x3A+1.06x4D；x1A≥40000y1A，x1A≤200000y1A，x3B≥30000y3B，x3B≤50000y3B；x2C=20000y2C，yiA，yiB=0或1，i=1,2,3,4,5y2C=0，1，2，3，4xiA，xiB，xiC，xiD≥0(i=1、2、3、4、5）§4整數(shù)規(guī)劃的分枝定界法分枝定界法是求解整數(shù)規(guī)劃的一種常用的有效的方法，它既能解決純整數(shù)規(guī)劃的問(wèn)題，又能解決混合整數(shù)規(guī)劃的問(wèn)題。大多數(shù)求解整數(shù)規(guī)劃的商用軟件就是基于分枝定界法而編制成的。分枝定界法是先求解整數(shù)規(guī)劃的線性規(guī)劃問(wèn)題。如果其最優(yōu)解不符合整數(shù)條件，則求出整數(shù)規(guī)劃的上下界，用增加約束條件的辦法，把相應(yīng)的線性規(guī)劃的可行域分成子區(qū)域（稱為分枝），再求解這些子區(qū)域上的線性規(guī)劃問(wèn)題，不斷縮小整數(shù)規(guī)劃的上下界的距離，最后得整數(shù)規(guī)劃的最優(yōu)解。下面以例9予以說(shuō)明。例9用分枝定界法求解整數(shù)規(guī)劃Max2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≤4x1,x2≥0且x1,x2為整數(shù)解:(一)先求出以下線性規(guī)劃的解：Max2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≤4x1,x2≥0得z1=14.66,x1=2.44,x2=3.26(二)確定整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)值z(mì)*初始上界和下界z。分析后，知道=14.66，由觀察法得下界z=13（當(dāng)x1=2,x2=3時(shí)）。(三)將一個(gè)線性規(guī)劃問(wèn)題分為兩枝，并求解?？捎蓌1≤2或x1≥3中取值。將線性規(guī)劃1分解為兩支，如下：線性規(guī)劃2：Max2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≤4x2≤2x1,x2≥0解得z2=13.90,x1=2,x2=3.30線性規(guī)劃3：Max2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≤4x1≥3x1,x2≥0解得z3=14.58,x1=3,x2=2.86(四)修改整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)的上下界。經(jīng)分析，將上界=14.66修改為=14.58，z=13。(五)在線性規(guī)劃2和線性規(guī)劃3中選擇一個(gè)上界最大的線性規(guī)劃，即線性規(guī)劃3，進(jìn)行分枝。線性規(guī)劃3分解為線性規(guī)劃4和線性規(guī)劃5，如下：線性規(guī)劃4：Max2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≤4x1≥3x2≤2x1,x2≥0解得z4=14,x1=4,x2=2線性規(guī)劃5：Max2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≥3x2≥3x1,x2≥0無(wú)可行解(六)進(jìn)一步修改整數(shù)規(guī)劃最優(yōu)目標(biāo)函數(shù)值z(mì)*的上下界。從線性規(guī)劃2，4，5中修改上下界。分析后，可得=14，z=14。都取線性規(guī)劃2，4，5中的整數(shù)可行解的目標(biāo)函數(shù)值的最大值。性質(zhì)2：當(dāng)整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)值z(mì)*的上界等于其下界z時(shí)，該整數(shù)規(guī)劃的最優(yōu)解已經(jīng)被求出。這個(gè)整數(shù)的最優(yōu)解即為其目標(biāo)函數(shù)值取此下界的對(duì)應(yīng)線性規(guī)劃的整數(shù)可行解。用圖8-2表示例9的求解過(guò)程與求解結(jié)果圖8-7從以上解題過(guò)程可得用分枝定界法求解目標(biāo)函數(shù)值最大的整數(shù)規(guī)劃的步驟，我們將求解的整數(shù)規(guī)劃問(wèn)題稱為A，將與其相對(duì)應(yīng)的線性規(guī)劃問(wèn)題稱為B：第一步：求解問(wèn)題B，可得以下情況之一：1.B沒(méi)有可行解，則A也沒(méi)有可行解，求解過(guò)程停止。2.B有最優(yōu)解，且符合問(wèn)題A的整數(shù)條件，則B的最優(yōu)解即為A的最優(yōu)解，求解過(guò)程停止。3.B有最優(yōu)解，但不符合A的整數(shù)條件，記其目標(biāo)函數(shù)值為z1。第二步：確定A的最優(yōu)目標(biāo)函數(shù)值z(mì)*的上下界，其上界即為z1,=z1,再用觀察法找到A的一個(gè)整數(shù)可行解，求其目標(biāo)函數(shù)值作為z*的下界，記為z。第三步：判斷是否等于z。若相等，則整數(shù)規(guī)劃最優(yōu)解即為其目標(biāo)函數(shù)值等于z的A的那個(gè)整數(shù)可行解；否則進(jìn)行第四步。第四步：在B的最優(yōu)解中選一個(gè)最遠(yuǎn)離整數(shù)要求的變量，不妨設(shè)此變量為xj，以[bj]表示小于bj的最大整數(shù)，構(gòu)造以下兩個(gè)約束條件，并加入問(wèn)題B，得到B的兩個(gè)分枝B1和B2。xj≤[bj]和xj≥[bj]+1第五步：求解B1和B2。修改A問(wèn)題的最優(yōu)目標(biāo)函數(shù)值z(mì)*的上下界，和z。第六步：比較和剪枝。各分枝的最優(yōu)目標(biāo)函數(shù)值中若有小于z者，則剪掉這枝（用打Х表示），即以后不再考慮了。若大于，則不符合整數(shù)條件，則重復(fù)第三步至第六步，直至=z，求出最優(yōu)解為止。對(duì)于求目標(biāo)函數(shù)值最小的整數(shù)規(guī)劃的求解步驟與上述步驟基本相似。第九章目標(biāo)規(guī)劃§1目標(biāo)規(guī)劃問(wèn)題舉例§2目標(biāo)規(guī)劃的圖解法§3復(fù)雜情況下的目標(biāo)規(guī)劃§4.加權(quán)目標(biāo)規(guī)劃§1目標(biāo)規(guī)劃問(wèn)題舉例例1．企業(yè)生產(chǎn)不同企業(yè)的生產(chǎn)目標(biāo)是不同的。多數(shù)企業(yè)追求最大的經(jīng)濟(jì)效益。但隨著環(huán)境問(wèn)題的日益突出，可持續(xù)發(fā)展已經(jīng)成為全社會(huì)所必須考慮的問(wèn)題。因此，企業(yè)生產(chǎn)就不能再如以往那樣只考慮企業(yè)利潤(rùn)，必須承擔(dān)起社會(huì)責(zé)任，要考慮環(huán)境污染、社會(huì)效益、公眾形象等多個(gè)方面。兼顧好這幾者關(guān)系，企業(yè)才可能保持長(zhǎng)期的發(fā)展。例2．商務(wù)活動(dòng)企業(yè)在進(jìn)行盈虧平衡預(yù)算時(shí)，不能只集中在一種產(chǎn)品上，因?yàn)槟骋环N產(chǎn)品的投入和產(chǎn)出僅僅是企業(yè)所有投入和產(chǎn)出的一部分。因此，需要用多產(chǎn)品的盈虧分析來(lái)解決具有多個(gè)盈虧平衡點(diǎn)的決策問(wèn)題（多產(chǎn)品的盈虧平衡點(diǎn)往往是不一致的）。例3．投資企業(yè)投資時(shí)不僅僅要考慮收益率，還要考慮風(fēng)險(xiǎn)。一般地，風(fēng)險(xiǎn)大的投資其收益率更高。因此，企業(yè)管理者只有在對(duì)收益率和風(fēng)險(xiǎn)承受水平有明確的期望值時(shí)，才能得到滿意的決策。例4．裁員同樣的，企業(yè)裁員時(shí)要考慮很多可能彼此矛盾的因素。裁員的首要目的是壓縮人員開(kāi)支，但在人人自危的同時(shí)員工的忠誠(chéng)度就很難保證，此外，員工的心理壓力、工作壓力等都會(huì)增加，可能產(chǎn)生負(fù)面影響。例5．營(yíng)銷營(yíng)銷方案的策劃和執(zhí)行存在多個(gè)目標(biāo)。既希望能達(dá)到立竿見(jiàn)影的效果，又希望營(yíng)銷的成本控制在某一個(gè)范圍內(nèi)。此外，營(yíng)銷活動(dòng)的深入程度也決定了營(yíng)銷效果的好壞和持續(xù)時(shí)間?！?目標(biāo)規(guī)劃的圖解法例6．一位投資商有一筆資金準(zhǔn)備購(gòu)買股票。資金總額為90000元，目前可選的股票有A和B兩種（可以同時(shí)投資于兩種股票）。其價(jià)格以及年收益率和風(fēng)險(xiǎn)系數(shù)如表9-1：表9-1從上表可知，A股票的收益率為（3／20）×100％＝15％，股票B的收益率為4／50×100％＝8％，A的收益率比B大，但同時(shí)A的風(fēng)險(xiǎn)也比B大。這也符合高風(fēng)險(xiǎn)高收益的規(guī)律。試求一種投資方案，使得一年的總投資風(fēng)險(xiǎn)不高于700，且投資收益不低于10000元。顯然，此問(wèn)題屬于目標(biāo)規(guī)劃問(wèn)題。它有兩個(gè)目標(biāo)變量：一是限制風(fēng)險(xiǎn)，一是確保收益。在求解之前，應(yīng)首先考慮兩個(gè)目標(biāo)的優(yōu)先權(quán)。假設(shè)第一個(gè)目標(biāo)（即限制風(fēng)險(xiǎn)）的優(yōu)先權(quán)比第二個(gè)目標(biāo)（確保收益）大，這意味著求解過(guò)程中必須首先滿足第一個(gè)目標(biāo)，然后在此基礎(chǔ)上再盡量滿足第二個(gè)目標(biāo)。建立模型：設(shè)x1、x2分別表示投資商所購(gòu)買的A股票和B股票的數(shù)量。首先考慮資金總額的約束：總投資額不能高于90000元。即20x1＋50x2≤90000。一、約束條件再來(lái)考慮風(fēng)險(xiǎn)約束：總風(fēng)險(xiǎn)不能超過(guò)700。投資的總風(fēng)險(xiǎn)為0.5x1＋0.2x2。引入兩個(gè)變量d1+和d1-,建立等式如下：0.5x1+0.2x2=700+d1+-d1-其中，d1+表示總風(fēng)險(xiǎn)高于700的部分，d1-表示總風(fēng)險(xiǎn)少于700的部分，d1+≥0。目標(biāo)規(guī)劃中把d1+、d1-這樣的變量稱為偏差變量。偏差變量的作用是允許約束條件不被精確滿足。把等式轉(zhuǎn)換，可得到0.5x1+0.2x2-d1++d1-=700。再來(lái)考慮年收入:年收入=3x1+4x2引入變量d2+和d2-，分別表示年收入超過(guò)與低于10000的數(shù)量。于是，第2個(gè)目標(biāo)可以表示為3x1+4x2-d2++d2-=10000。二、有優(yōu)先權(quán)的目標(biāo)函數(shù)本問(wèn)題中第一個(gè)目標(biāo)的優(yōu)先權(quán)比第二個(gè)目標(biāo)大。即最重要的目標(biāo)是滿足風(fēng)險(xiǎn)不超過(guò)700。分配給第一個(gè)目標(biāo)較高的優(yōu)先權(quán)P1,分配給第二個(gè)目標(biāo)較低的優(yōu)先權(quán)P2。針對(duì)每一個(gè)優(yōu)先權(quán)，應(yīng)當(dāng)建立一個(gè)單一目標(biāo)的線性規(guī)劃模型。首先建立具有最高優(yōu)先權(quán)的目標(biāo)的線性規(guī)劃模型，求解；然后再按照優(yōu)先權(quán)逐漸降低的順序分別建立單一目標(biāo)的線性規(guī)劃模型，方法是在原來(lái)模型的基礎(chǔ)上修改目標(biāo)函數(shù)，并把原來(lái)模型求解所得的目標(biāo)最優(yōu)值作為一個(gè)新的約束條件加入到當(dāng)前模型中，并求解。三、圖解法1．針對(duì)優(yōu)先權(quán)最高的目標(biāo)建立線性規(guī)劃建立線性規(guī)劃模型如下：Mind1+s.t.20x1＋50x2≤900000.5x1+0.2x2-d1++d1-=7003x1+4x2-d2++d2-=10000x1,x2,d1+,d1-≥02．針對(duì)優(yōu)先權(quán)次高的目標(biāo)建立線性規(guī)劃優(yōu)先權(quán)次高（P2）的目標(biāo)是總收益超過(guò)10000。建立線性規(guī)劃如下：Mind2-s.t.20x1＋50x2≤900000.5x1+0.2x2-d1++d1-=7003x1+4x2-d2++d2-=10000d1+＝0x1,x2,d1+,d1-,d2+,d2-≥0目標(biāo)規(guī)劃的這種求解方法可以表述如下：1．確定解的可行區(qū)域。2．對(duì)優(yōu)先權(quán)最高的目標(biāo)求解，如果找不到能滿足該目標(biāo)的解，則尋找最接近該目標(biāo)的解。3．對(duì)優(yōu)先權(quán)次之的目標(biāo)進(jìn)行求解。注意：必須保證優(yōu)先權(quán)高的目標(biāo)不變。4.重復(fù)第3步，直至所有優(yōu)先權(quán)的目標(biāo)求解完。四、目標(biāo)規(guī)劃模型的標(biāo)準(zhǔn)化例6中對(duì)兩個(gè)不同優(yōu)先權(quán)的目標(biāo)單獨(dú)建立線性規(guī)劃進(jìn)行求解。為簡(jiǎn)便，把它們用一個(gè)模型來(lái)表達(dá)，如下：MinP1（d1+）+P2（d2-）s.t.20x1＋50x2≤900000.5x1+0.2x2-d1++d1-=7003x1+4x2-d2++d2-=10000x1,x2,d1+,d1-,d2+,d2-≥0§3復(fù)雜情況下的目標(biāo)規(guī)劃例7．一工藝品廠商手工生產(chǎn)某兩種工藝品A、B，已知生產(chǎn)一件產(chǎn)品A需要耗費(fèi)人力2工時(shí)，生產(chǎn)一件產(chǎn)品B需要耗費(fèi)人力3工時(shí)。A、B產(chǎn)品的單位利潤(rùn)分別為250元和125元。為了最大效率地利用人力資源，確定生產(chǎn)的首要任務(wù)是保證人員高負(fù)荷生產(chǎn)，要求每周總耗費(fèi)人力資源不能低于600工時(shí)，但也不能超過(guò)680工時(shí)的極限；次要任務(wù)是要求每周的利潤(rùn)超過(guò)70000元；在前兩個(gè)任務(wù)的前提下，為了保證庫(kù)存需要，要求每周產(chǎn)品A和B的產(chǎn)量分別不低于200和120件，因?yàn)锽產(chǎn)品比A產(chǎn)品更重要，不妨假設(shè)B完成最低產(chǎn)量120件的重要性是A完成200件的重要性的1倍。試求如何安排生產(chǎn)？解：本問(wèn)題中有3個(gè)不同優(yōu)先權(quán)的目標(biāo)，不妨用P1、P2、P3表示從高至低的優(yōu)先權(quán)。對(duì)應(yīng)P1有兩個(gè)目標(biāo)：每周總耗費(fèi)人力資源不能低于600工時(shí),也不能超過(guò)680工時(shí)；對(duì)應(yīng)P2有一個(gè)目標(biāo)：每周的利潤(rùn)超過(guò)70000元；對(duì)應(yīng)P3有兩個(gè)目標(biāo)：每周產(chǎn)品A和B的產(chǎn)量分別不低于200和120件。采用簡(jiǎn)化模式，最終得到目標(biāo)線性規(guī)劃如下：MinP1(d1+)+P1(d2－)+P2(d3-)+P3(d4-)+P3(2d5-)s.t.2x1+3x2-d1++d1-=680對(duì)應(yīng)第1個(gè)目標(biāo)2x1+3x2-d2++d2-=600