運(yùn)籌學(xué)復(fù)習(xí)例題

1、1.某制藥廠在計劃期內(nèi)要安排生產(chǎn)、兩種藥品，這些藥品分別需要在四種不同的設(shè)備上加工按工藝規(guī)定，每千克藥品和在各臺設(shè)備上所需要的加工臺時數(shù)如表1已知各設(shè)備在計劃期內(nèi)有效臺時數(shù)（1臺設(shè)備工作1小時稱為1臺時）分別是12、8、16和12該制藥廠每生產(chǎn)1千克藥品可得利潤200元，每生產(chǎn)1千克藥品可得利潤300元表1 兩種藥品每千克在各臺設(shè)備上所需的加工臺時數(shù)藥品21402204（1）問應(yīng)如何安排生產(chǎn)計劃，才能使制藥廠利潤最大？分別利用軟件和最終單純型表回答剩余問題。解 設(shè)，分別表示在計劃期內(nèi)藥品和的產(chǎn)量（千克），表示這個期間的制藥廠利潤則計劃期內(nèi)生產(chǎn)、兩種藥品的利潤總額為（元）但是生產(chǎn)、兩種藥品在設(shè)備

2、上的加工臺時數(shù)必須滿足；在設(shè)備上的加工臺時數(shù)必須滿足；在設(shè)備上的加工臺時數(shù)必須滿足；在設(shè)備上的加工臺時數(shù)必須滿足；生產(chǎn)、兩種藥品的數(shù)量應(yīng)是非負(fù)的數(shù)，即于是上述的問題歸結(jié)為：目標(biāo)函數(shù) 約束條件 單純型法求解：首先將線性規(guī)劃問題標(biāo)準(zhǔn)化，即在約束條件中引入松弛變量、，則標(biāo)準(zhǔn)化后的線性規(guī)劃模型為： 此時約束方程組已為典型方程組，根據(jù)上述線性規(guī)劃模型可以列出初始單純形表（表2-4）：表2-4 單純形法求解例2-1（1）2003000000022100012601201008404000101600400011232003000000=0表2-4中： 為典型方程組中變量的系數(shù)，為規(guī)劃中出現(xiàn)的變量，為變量在

3、目標(biāo)函數(shù)中的系數(shù)，為基本變量，為基本變量在目標(biāo)函數(shù)中的系數(shù)，為典型方程組右端常數(shù)項（非負(fù)值），為確定出基變量的商值， （），為變量的檢驗數(shù)，為此時目標(biāo)函數(shù)值，根據(jù)初始單純形表可以看出：初始基本可行解是，此時目標(biāo)函數(shù)值0檢驗數(shù)200200 300300 =0（基本變量的檢驗數(shù)總等于零）由于，所以初始基本可行解非最優(yōu)解又由于，所以確定為進(jìn)基變量進(jìn)一步求最小值：即從第4個方程中算出的商值最小，而第4個方程中的基本變量是，于是為出基變量表中給第4個約束方程中的系數(shù)4加上方括號以突出其為樞元接下去的工作是將取代，表2-4中的約束方程化為以、和為基本變量，和為非基本變量的典型方程，以便求出新的基本可行解從

4、表2-4中可以看到，只需對方程組實行初等變換，使樞元位置變成1，而樞列中的其它元素變?yōu)榱悖匆詷性獮橹行牡某醯茸儞Q）就可以了此處可先將第4個方程除以4，使樞元位置變成1；然后用新得到的第4個方程乘以（-2）后分別加到第1個和第2個方程上，使樞列中的第1個和第二個方程所在位變?yōu)榱氵@樣我們可以得到新的單純形表（表2-5）表2-5給出的新的基本可行解是0，3，6，2，16，0此時目標(biāo)函數(shù)值900檢驗數(shù)200-200 0- =0（基本變量的檢驗數(shù)總等于零）表2-5 單純形法求解例2-1（2）2003000000020100630100102204000101643000100032000000-75=

5、900由于，所以此時基本可行解非最優(yōu)解，確定為進(jìn)基變量進(jìn)一步計算最小值：即從第2個方程中算出的商值最小，而第2個方程中的基本變量是，于是為出基變量接著進(jìn)行第二次迭代，將取代，表2-5中的約束方程化為以、和為基本變量，和為非基本變量的典型方程，以便求出新的單純形表重復(fù)單純形法計算第2 步第5步，一直到?jīng)]有新的非基本變量可以改善目標(biāo)函數(shù)為止（見表2-6和表2-7）表2-6 單純形法求解例2-1（3）20030000000001-20242001001020000-4128430001000312000-200025=1300表2-7 單純形法求解例2-1（4）20030000000001-1002

6、001000040000-21430001002000-1500=1400表2-7中：目標(biāo)函數(shù)值=1400檢驗數(shù)=0-=-150 =0-= =0（基本變量的檢驗數(shù)總等于零）由于，所以此基本可行解，即為最優(yōu)解，最優(yōu)值為Z*1400與前面圖解法求解結(jié)果一致為了加深對單純形法基本思想的理解，不妨將表2-4、表2-5、表2-6、表2-7和圖2-1進(jìn)行對照，可以發(fā)現(xiàn)表2-4給出的基本可行解對應(yīng)于圖中可行域頂點(diǎn)0，表2-5給出的基本可行解對應(yīng)于頂點(diǎn)，表2-6給出的基本可行解對應(yīng)于頂點(diǎn)，表2-7給出的最優(yōu)解對應(yīng)于頂點(diǎn)線性規(guī)劃問題有無窮多個可行解，應(yīng)用單純形法可以高效率地求解此類問題（2）藥品的價格在什么范圍

7、內(nèi)變動，不影響原來的生產(chǎn)計劃安排，但制藥廠收益變化了設(shè)基本變量在目標(biāo)函數(shù)中的系數(shù)變化了；這時表2-7的最終計算表便成為表2-16所示表2-16 基本變量利潤系數(shù)變化的靈敏度分析20030000000001-1002001000040000-214300010020000=14002這時要保持最優(yōu)解不變，則必須滿足下列不等式：-150-=-150-0-=-0 即可在0,400間變動，不影響原來的生產(chǎn)計劃安排，但制藥廠收益變化了（3）設(shè)備C在計劃期內(nèi)有效臺時數(shù)在什么范圍內(nèi)變動時，原來最優(yōu)解的基本變量不變，但最優(yōu)解的值發(fā)生變化第三個約束條件發(fā)生變化，變化量為，為了使最后的解仍為可行解，應(yīng)滿足下列不等

8、式：所以在8,0之間變動時（即的變化范圍在8,16時），原來最優(yōu)解的基本變量不變，但最優(yōu)解的值發(fā)生變化例如，為2時（即14），則最優(yōu)解*，最優(yōu)值*1375，見表2-17表2-17 右端常數(shù)變化后的最優(yōu)解20030000000001-10200100000000-2133000100000-1500=1375如果的變化超出了8,0的范圍，這時最優(yōu)解的基本變量就發(fā)生變化在這種情況下要用對偶單純形法繼續(xù)求出新的最優(yōu)解例如為2時（即18），則則最終單純形表變?yōu)楸?-18表2-18 右端常數(shù)變化后的對偶單純形法求解20030000000001-10200100000000-2153000100000-1

9、500=142515050000-44102200101-10040002-401430001100200-50-10000=1400新的最優(yōu)解*，最優(yōu)值Z*1400（4）若計劃生產(chǎn)的藥品的工藝結(jié)構(gòu)有了改進(jìn)，相應(yīng)地生產(chǎn)單位藥品所需設(shè)備的臺時改為（3,2,5,2），它的利潤也提高到每千克400元試分析已求得的最優(yōu)計劃有何變化？解 當(dāng)?shù)南禂?shù)列向量變化后,原最終單純形表（表2-7）中的系數(shù)列向量變成: =原最終單純形表變成表2-19：表2-19 決策變量系數(shù)改變對最優(yōu)解的影響（1）4003000000001-10040000004000-2143001002由的系數(shù)列向量可知，到此尚未完成行變換，所

10、以需繼續(xù)使的系數(shù)列向量變成單位列向量，于是得到表2-20表2-20 決策變量系數(shù)改變對最優(yōu)解的影響（2）40030000000001-10400100000000-213000100000-150-200=1520因為0，所以新的最優(yōu)解，最優(yōu)值*1520元.（5）設(shè)該制藥廠除生產(chǎn)藥品、以外，還有第三種藥品可供選擇生產(chǎn)藥品每千克需要使用設(shè)備的臺時分別為3，2，6，3；每千克可得利潤500元問該制藥廠的計劃中要不要安排這種藥品的生產(chǎn)，若要安排，應(yīng)當(dāng)生產(chǎn)多少？解 設(shè)表示計劃期內(nèi)生產(chǎn)藥品的數(shù)量（單位為千克），則原最終單純形表（表2-7）中增加了一列,這新的一列為：= 將新增一列列入原最終單純形表中，計

11、算檢驗數(shù)，見表2-21由于此時相應(yīng)的檢驗數(shù)為正值，所以此單純形表給出的基本可行解不是最優(yōu)解，繼續(xù)用單純形法求解結(jié)果，最后得最優(yōu)解，最優(yōu)值*1650元，比原計劃增加了利潤250元表2-21 增加變量的靈敏度分析20030000005000001-1002001000040000-21242300010028000-1500125=140000010120010001500000-1123000100000-250=1650（6）若制藥廠為了提高藥品質(zhì)量，考慮給藥品、增加一道精加工工序，并在設(shè)備上進(jìn)行、兩種藥品分別需要的加工臺時數(shù)為（2，2.4）已知設(shè)備的計劃工作時間為12個臺時，試問增加一道精加

12、工工序后，對原計劃有何影響？解 上述問題相當(dāng)于在原問題的基礎(chǔ)上增加了一個約束條件 設(shè)為新增的松弛變量，則得到原最終單純形表（表2-7）新增一行和一列，見表2-22此時原最終單純形表中的和的系數(shù)列向量不再是單位向量了，所以繼續(xù)進(jìn)行行變換在行變換后得到的新單純形表中，檢驗數(shù)均小于等于零，但右端項出現(xiàn)負(fù)值，所以可用對偶單純形法繼續(xù)運(yùn)算最后得最優(yōu)解，最優(yōu)值*1350元表2-22 增加約束條件的靈敏度分析200300000000001-100020010000040000-21043000100020200001120001-100020010000040000-21043000100020000010

13、00-1500012500010012001000030000-5012300010000000610-54000-7500=13502. 某醫(yī)院有一批長度為15分米的膠皮管原料為了作輸液管、止血帶和聽診器膠管，需要截成長度分別為5.7分米，4.2分米和3.1分米的短管各100根，100根和200根試問應(yīng)如何安排截法，所用的膠管原材的總根數(shù)最少，而且每根料頭不能超過2分米？解 先分析一下截取短管的方法如果先考慮盡輸液管截，然后考慮盡止血帶截，再考慮盡聽診器膠管截，則截取的方法如下表2-23：表2-23 短管截取方法截法輸液管止血帶聽診器膠管總長（分米）料頭（分米）5.7（分米）4.2（分米）3

14、.1（分米）120114.50.5212014.10.9311113.02.0410315.00.0502214.60.4601313.51.5為了得到短管5.7分米100根，4.2分米100根和3.1分米200根，需混合截取原料令表示第種截法所用原材的根數(shù)，得到如下線性規(guī)劃模型： ，且為整數(shù)在上述約束條件中添加人工變量、，得到其典型方程組： ，且為整數(shù)用大法求解，如表2-24因為非基本變量的檢驗數(shù)為0，所以有多重最優(yōu)解，其中一個最優(yōu)解為*，最優(yōu)值為*=110即按第2種方法截取40根原材，按第4種方法截取60根原材，按第5種方法截取10根原材，總共截取110根原材表2-24 大法求解短管截取問

15、題 1111112111001001001000210210101001013230012001-3M1-3M1-3M1-4M1-4M1-4M000=400M10-11002102101100501011001-3M0000=M110-10003110101101000 01-3M0=100+M11100401-10011011010600000*=1103. 醫(yī)院放射科目前可以開展線平片檢查和檢查業(yè)務(wù)，現(xiàn)擬購買磁共振儀，以增設(shè)磁共振檢查業(yè)務(wù)為此醫(yī)院收集了有關(guān)信息，以決策是否購買磁共振儀經(jīng)過資料收集，醫(yī)院估計今后放射科如果開展此3項業(yè)務(wù)，在現(xiàn)有放射科醫(yī)務(wù)人員力量和病人需求的情況下，每月此3項業(yè)

16、務(wù)的最多提供量為1800人次平均每人次檢查時間、每月機(jī)器實際可使用時間、平均每人次檢查利潤如下表2表2 放射科3項檢查時間與利潤及機(jī)器可使用時間放射科業(yè)務(wù)項 目線平片檢查檢查磁共振檢查平均每人次檢查時間（小時/次）0.10.250.5每月機(jī)器實際可使用時間（小時）300120120平均每人次檢查利潤（元/次）206010設(shè)每月線平片檢查、檢查和磁共振檢查的業(yè)務(wù)量分別為,和人次，則使醫(yī)院放射科此3項業(yè)務(wù)收入最多的線性規(guī)劃模型如下： 利用單純形法可得最終單純形表（見表2-26）表2-26 放射科業(yè)務(wù)安排最終單純形表20601000000x4001016860x201004004800x600001

17、012020x11010-401132000-100-1600-20*=55200最優(yōu)解*，最優(yōu)值*55200從最終單純形表上可讀出如下信息：1醫(yī)院從放射科收益的角度考慮，不應(yīng)購買磁共振機(jī).2在每月線平片檢查和檢查業(yè)務(wù)量各為1320人次和480人次時，放射科利潤最大，達(dá)55200元3在最優(yōu)業(yè)務(wù)安排情況下，每月光機(jī)仍有168小時未實際利用，故它的影子價格為0元/小時；每月機(jī)可使用的時間已完全利用，它的影子價格為160元/小時，如果市場上能租到機(jī)的價格低于影子價格160元/小時，那么就應(yīng)當(dāng)租用機(jī)，增加檢查業(yè)務(wù)，以求得更高的利潤如果醫(yī)院購買了磁共振機(jī)，而在最優(yōu)業(yè)務(wù)安排情況下，并無利用，所以其影子價格

18、為0元/小時4在最優(yōu)業(yè)務(wù)安排情況下，每月線平片檢查和檢查的服務(wù)量已達(dá)到現(xiàn)有醫(yī)務(wù)人員服務(wù)提供和病人需求的最大量醫(yī)院如果想通過從人才市場上聘用醫(yī)務(wù)人員以增加放射科的服務(wù)能力，并通過宣傳擴(kuò)大病人對其醫(yī)院醫(yī)療服務(wù)（包括放射科業(yè)務(wù)）的需求，則只有當(dāng)增加一個病人的服務(wù)量所需額外增加的人員招聘費(fèi)和宣傳費(fèi)低于20元時，才是適宜的，可使放射科的利潤更高4. 某省醫(yī)療隊從A1、 A2 、A3三所省級醫(yī)院抽調(diào)骨干醫(yī)護(hù)人員配備必要設(shè)備去B1、B2、B3、B4四個貧困縣進(jìn)行巡回醫(yī)療扶貧，各醫(yī)院抽調(diào)的人數(shù)、各縣需要人數(shù)、以及從醫(yī)院到各縣的人均（包括設(shè)備交通）費(fèi)用如表3所示，問如何安排可使總費(fèi)用最小？表3 運(yùn)輸問題的人均費(fèi)

19、用表B1 B2 B3 B4醫(yī)院抽出人數(shù)人均費(fèi)用（單位：百元） A1 A2 A3 縣需求人數(shù)2 9 10 7 9 1 3 4 2 58 4 2 5 73 8 4 6 （1）西北角法 所謂西北角法就是從表3-4的左上角第一格開始安排運(yùn)輸計劃 方法是：取其對應(yīng)醫(yī)院抽出數(shù)與縣城需要數(shù)的最小值作為初始基本可行解的第一個分量值（） 這樣第一列的需求已經(jīng)滿足，用線劃去第一列，再看第二列、第一行，由于抽出數(shù)還有9-3=6，與B2的需求數(shù)8比較，取最小值6（）填入該格 依此次序進(jìn)行，即可得到第一個基本可行解，見表3-4 表3-4 運(yùn)輸問題作業(yè)表西北角法縣城醫(yī)院B1B2B3B4醫(yī)院抽出人數(shù)A132691079A2

20、1342523A38425716縣需人數(shù)3846（2）最小費(fèi)用法 西北角法的優(yōu)點(diǎn)是簡單、易實現(xiàn)，但沒有考慮最小費(fèi)用 可能要經(jīng)過許多次迭代才能得到最優(yōu)解 而最小費(fèi)用法的基本思想是就近供應(yīng)， 優(yōu)先考慮最小單位運(yùn)費(fèi)對應(yīng)的， 這樣得到的方案會更接近最優(yōu)方案以例3-1來說明具體步驟表3-5 運(yùn)輸問題作業(yè)表最小費(fèi)用法縣城醫(yī)院B1B2B3B4醫(yī)院抽出人數(shù)A1291079A213425A38 4257縣需人數(shù)3846在運(yùn)輸表3-5中，單位運(yùn)費(fèi)最小的是. 這個格子處于A2行B1列，因而最多可供5人，但需求量為3人，于是，在這個格子里填上盡可能大的數(shù)是. 這個格子填上數(shù)后，B1的要求滿足了，可用線劃去該列.于是只

21、需考慮B2、B3、B4的需求. 從表3-5看到，在未劃線的格子中最小者是. 任選一個，比如考慮所在的格子. 此處的供求情況是：最多可供7，但最多需要4. 于是應(yīng)填入的數(shù)是. 這樣B3的需求也滿足了，用線劃去該列.后面只需考慮B2和B4的需求. 這時最小的cij（c11，c13）是c24=2. 此處，最大可供量為53=2（c21處已占用了），需求量為6，從而應(yīng)令. 這時A2的供應(yīng)量用完了，用線劃去該行. 后面只需考慮A1和A3的供應(yīng)、B2和B4需求了，這樣依次分析下去，便得到：將上述六個數(shù)填在運(yùn)輸表內(nèi)（為了與其它數(shù)字相區(qū)別，用圈號標(biāo)記），其余為非基變量取0值，就可作為初始調(diào)運(yùn)方案（見表3-5）.

22、 從表3-5容易算出，這個初始方案的總運(yùn)費(fèi)是 59+47+31+22+34+42 =100（百元）， 即10000元. （3）以上兩種方法在求初始基可行解時，均會遇到一些特殊情況，一般稱為“退化”. 大致有兩種情況：當(dāng)選定元素后，發(fā)現(xiàn)該元素所在行的供給量等于需求量時，此時只能劃去一行或一列，不能同時劃去. 當(dāng)選定元素后，發(fā)現(xiàn)對應(yīng)供給量和需求量均為0，那么，此時仍應(yīng)把作為基變量，把0值填入相應(yīng)格子中（即基變量取0，退化）. （二）最優(yōu)性檢驗上面已經(jīng)得到初始基可行解，那是否為最優(yōu)解呢？需要驗證. 依單純形法原理，要求出各變量的檢驗數(shù)；由于基變量的檢驗數(shù)恒為0，所以只要求出非基變量的檢驗數(shù). 另外運(yùn)

23、輸問題是極小化的線性規(guī)劃問題，只要檢驗數(shù)全部非負(fù)即達(dá)最優(yōu)解. 在表上作業(yè)法中常有閉回路法和位勢法. （1）閉回路法 我們試從定義出發(fā)計算檢驗數(shù). 先看的檢驗數(shù)，分析一個閉回路（表3-6中虛線所示）. 由于供求條件的限制，當(dāng)從0增加到1時，將引起連鎖反應(yīng)：減少1，增加1，減少1. 于是根據(jù)檢驗數(shù)的定義得到=1c11+（-1）c21+1c24+（-1）c14= c11-c21+c24-c14=2-1+2-7= -4，即每增加1個單位，將使運(yùn)費(fèi)減少4個單位，這說明初始解非最優(yōu). 類似地，我們可以求出其他非基變量的檢驗數(shù)，但是，一般說來這種求檢驗數(shù)的方法是比較繁瑣的. 例如，求的檢驗數(shù)時，必須考慮下面

24、那樣的復(fù)雜閉回路(表3-6中實線所示)表3-6 運(yùn)輸問題作業(yè)表縣城醫(yī)院B1B2B3B4醫(yī)院抽出人數(shù)A1x11291079A213425A3 x318 4257縣需人數(shù)3846（2） 用位勢法 位勢法又叫U-V法，它是由解運(yùn)輸問題的對偶問題引出來的. 平衡型運(yùn)輸問題的對偶問題為：對偶模型里的變量與個供應(yīng)約束方程對應(yīng)，與個需求約束方程對應(yīng)，分別稱它們?yōu)樵瓎栴}變量的行位勢和列位勢. 定理3-2 運(yùn)輸問題的決策變量的檢驗數(shù). (證明略)由于基變量的檢驗數(shù)等于0，所以對于基變量有： . 而平衡型運(yùn)輸問題中的基變量個數(shù)為，從而得到個類似這樣方程構(gòu)成的方程組. 但它有個未知量，要解出這個方程組，必須給其中一

25、個自由未知量賦值，比如令（這樣不會影響結(jié)果），就可求出所有變量的位勢，進(jìn)而算出所有非基變量的檢驗數(shù). 仍用例3-1來說明具體求法. 對于最小費(fèi)用法得到的初始基本可行解（見表3-5），得到方程組 令 ，解得：計算非基變量的檢驗數(shù)：，與閉回路法結(jié)果一致，其它檢驗數(shù)可類似求出填入作業(yè)表中，用（ ）圈起來，見表3-7. 表3-7 運(yùn)輸問題作業(yè)表位勢法求檢驗數(shù)縣城醫(yī)院6977醫(yī)院抽出人數(shù) B1 B2B3B40 A1（-4）291079（3）-5 A213425（-1）（2）-5 A3（7）8 4257（3）縣需人數(shù)3846從表3-7可以看出，x11的檢驗數(shù)=-4（與前面用定義求得的結(jié)果是一致的）是所有檢

26、驗數(shù)中負(fù)值最小者. 這說明應(yīng)當(dāng)讓x11進(jìn)基，以改進(jìn)表3-5中的初始方案. （三）用閉回路法調(diào)整運(yùn)輸方案改進(jìn)基本可行解 如果經(jīng)過檢驗所得的解不是最優(yōu)的，就需要對基變量進(jìn)行迭代. 前面已經(jīng)有選取進(jìn)基變量的規(guī)則，即在所有非基變量中取檢驗數(shù)是負(fù)值最小者為進(jìn)基變量. 下面，用閉回路法選取出基變量及基變量取值的調(diào)整量，以實現(xiàn)解的改進(jìn). 步驟是： 找出入基變量所在的閉回路，并以該變量所在格為起點(diǎn)，沿閉回路頂點(diǎn)依次交替把它們所取的值前面加“+”、“-”號. 如表3-8所示； 所有被標(biāo)“-”號格子中變量取值最小者作為出基變量，即被標(biāo)“-”號的圓圈中數(shù)字最小者：. 在表3-8中. 表3-8 基變量迭代調(diào)整表縣城醫(yī)

27、院6977醫(yī)院抽出人數(shù) B1 B2B3B40 A1+（-4）291079（3）- -5 A213425- （-1）（2）+ -5 A3（7）8 4257（3）縣需人數(shù)3846表3-9 迭代后的運(yùn)輸方案表縣城醫(yī)院2977醫(yī)院抽出人數(shù) B1 B2B3B40 A1291079（3） -5 A213425 （4）（-1）（2） -5 A3（11）8 4257（3）縣需人數(shù)3846 進(jìn)行基的迭代,出基變量當(dāng)然取值為0，即將所有帶“+” 號的格子原取值加，帶“-”號的格子原取值減,就得到一個新的調(diào)運(yùn)方案（閉回路不涉及的基變量取值不變動，見表3-9）. 再求檢驗數(shù)，重復(fù)上述步驟，直至最優(yōu). 從表3-9中容易

28、算出，這個方案的總運(yùn)費(fèi)是 32+59+17+52+34+42 =88（百元）， 即8800元. 比初始表的方案優(yōu)秀了，但在表中求出各非基變量的檢驗數(shù)顯示，它還不是最優(yōu)的. 要作為入基變量. 再經(jīng)過迭代得到調(diào)運(yùn)方案如表3-10所示. 表3-10 再次迭代后的運(yùn)輸方案表縣城醫(yī)院2977醫(yī)院抽出人數(shù) B1 B2B3B40 A12-91079（3）+-5 A21+3425 （4）（-1） （2） -5 A3（11）8 4257（3）縣需人數(shù)3846從表3-10容易得出，其它非基變量為0；這時的總費(fèi)用為：32+67+53+34+42 =83（百元）， 即8300元. 這時算出非基變量的所有檢驗數(shù)均非負(fù)，

29、從而是最優(yōu)的運(yùn)輸方案. 在計算過程中需要注意的是，可能會有非基變量（空格）的檢驗數(shù)為0的情況，這時，該供銷平衡的運(yùn)輸問題存在無窮多最優(yōu)解. 在已得到的一個最優(yōu)解的表格中，從這樣的空格出發(fā)做閉回路重新進(jìn)行調(diào)整，可以得到另一個最優(yōu)解. 5. 某衛(wèi)生防疫站準(zhǔn)備選拔防疫科、食品科、總務(wù)科的三名科長. 幾經(jīng)篩選，僅剩下趙、錢、孫三名候選人. 根據(jù)民主評議的統(tǒng)計結(jié)果，他們主持各個科的工作能力（以得分多少來衡量）如表4所示. 試從工作能力出發(fā)，確定各科長的指定方案，使總體效能最大. 表4 工作能力表防疫食品總務(wù)工 作 能 力（分）趙353027錢373529孫382832分析： 用i=1,2,3 分別表示趙

30、、錢、孫三人；用j=1,2,3 分別表示防疫、食品、總務(wù)三個科. 則可以設(shè)于是數(shù)學(xué)模型為實際上，只要找出效率矩陣中的最大元素，用減去矩陣中的每個元素，得到的矩陣我們稱為原矩陣對應(yīng)的縮減矩陣（）. 易見越小表示原效率矩陣中第i個人去作第j項任務(wù)的收益越大，反之則收益越小. 因此求的最大化問題解，等價于求它對應(yīng)的縮減矩陣最小化問題的解. 解由于中的最大元素為:,所以它對應(yīng)的縮減矩陣為. 用匈牙利法求的最優(yōu)解-3-1 -2 -7可見最優(yōu)解為，這也是原最大化指派問題的最優(yōu)解，即派趙、錢、孫分別擔(dān)任防疫科、食品科和總務(wù)科的科長，這樣可使總的工作能效達(dá)到最大值102分. 2. 效率矩陣不是方陣 在實踐中，

31、往往出現(xiàn)人少任務(wù)多或人多任務(wù)少的情況. 對效率矩陣來說，表現(xiàn)為矩陣不是方陣. 甚至要求某人不能完成某項任務(wù)或某項工作不能由某人去作. 這都需要作適當(dāng)改進(jìn)，再應(yīng)用匈牙利法去解決. 對于效率矩陣不是方陣，可以虛設(shè)幾行或幾列，使其構(gòu)成方陣，虛設(shè)的行（列）的元素要根據(jù)目標(biāo)函數(shù)的具體情況確定. 對于后一問題，只要將效率矩陣相應(yīng)的元素取得充分大（極小問題）或充分?。O大化問題），使得最優(yōu)指派方案不可能取在該元素上. 6. 某公司生產(chǎn)A、B兩種藥品，這兩種藥品每小時的產(chǎn)量均為1000盒，該公司每天采用兩班制生產(chǎn)，每周最大工作時間為80小時，按預(yù)測每周市場最大銷量分別為70000盒和45000盒A種藥每盒的利

32、潤為2.5元，B種為15元試確定公司每周A、B兩種藥品生產(chǎn)量x1和x2（單位：千盒），使公司的下列目標(biāo)得以實現(xiàn)：P1：避免每周80小時生產(chǎn)能力的過少使用 P2：加班的時間限制在10小時以內(nèi) P3：A、B兩種藥品的每周產(chǎn)量盡量分別達(dá)到70,000盒和45,000盒，但不得超出，其權(quán)系數(shù)依它們每盒的利潤為準(zhǔn) P4：盡量減少加班時間 解 先建立這個問題的線性規(guī)劃模型，依題意分別建立各項目標(biāo)約束權(quán)系數(shù)是指它們在目標(biāo)函數(shù)中的重要程度，由2.51.5=53，故：目標(biāo)函數(shù)為：建立單純形表運(yùn)算如下：表4-5 單純形表cj00P15P33P30P4P2CBXBx1x2bP1111000-10805P310010

33、00 0 703P3010010004500000011-110 -1 -1000010P100000001P2-5-3000000P300000010P4P1011-100-1 0 100x110010000703P3010010004500000011-1100 -1 010010P100000001P20-3050000P300000010P40x2011-100-10100x110010000703P300-1110103500000011 -1 1000100000P100000001P2003200 -3 0P300000010P40x2011-1010-1200x11001000

34、0703P300-111-10125P40000011-1 1000100000P100000001P20032030-3P300000-101P4至此，由于P1 P2 P3P4 ，可知各檢驗數(shù)均非負(fù)，從而得最優(yōu)解為：x1=70，x2=20，, , , , ,即生產(chǎn)A種藥品70 000盒，B種藥品20 000盒，P1，P2級目標(biāo)可完全實現(xiàn)因，故每周需加班10小時，每周利潤為：7000025+2000015=205000（元）7. 某高校有各類教職員工如下：助教、助研、講師、教授助理、副教授、教授、兼職教師、專家及職工, 各類人員所承擔(dān)的工作性質(zhì)、工作量和工資各不相同，預(yù)計在下一學(xué)年要招收一定數(shù)

35、量的本科生與研究生，現(xiàn)應(yīng)用目標(biāo)規(guī)劃來確定聘用各類人員的人數(shù)，既要保持各類人員之間的適當(dāng)比例，完成學(xué)校的各項工作，同時又要取得最好的經(jīng)濟(jì)效益設(shè)聘用各類人員的人數(shù)如下：x1助研（可由研究生兼任） y1教授助理（有博士學(xué)位）x2助教（可由研究生兼任） y2副教授（有博士學(xué)位）x3講師 y3教授（有博士學(xué)位）x4教授助理（無博士學(xué)位） y4兼職教師（有博士學(xué)位）x5副教授（無博士學(xué)位） y5專家（有博士學(xué)位）x6教授（無博士學(xué)位） w1所有教職工的工資總基數(shù)x7兼職教師（無博士學(xué)位） w2所有教職工的工資比上一年的總增加數(shù)x8專家（無博士學(xué)位）x9職工現(xiàn)各類人員承擔(dān)的工作量，工資及所占比例見表5 校方

36、確定的各級決策目標(biāo)為：P1：要求教師有一定的學(xué)術(shù)水平，即75%的教師是專職的，擔(dān)任本科生教學(xué)工作的教師中，至少有40%的人具有博士學(xué)位擔(dān)任研究生教學(xué)的至少有75%的人具有博士學(xué)位 P2：要求各類人員增加工資的總額不得超過176000美元，其中x1，x2和x9增加的工資數(shù)為其原工資數(shù)的6%，而其它人員為8% P3：要求能完成學(xué)校的各項教學(xué)工作，即學(xué)校計劃招收本科生1820名、研究生100名要求為本科生每周開課共910學(xué)時，研究生每周開課100學(xué)時，并要求本科生教師與學(xué)生人數(shù)比為120，研究生教師與學(xué)生人數(shù)比為110 表5 各類人員工作量，工資及所占比例表變 量承擔(dān)的教學(xué)工作量（學(xué)時/周）所占教師

37、的百分比（%）年工資（美元）本科生研究生最大最小x100-3000 x2607-3000x31207-8000x49015-13000x5905-15000x6602-17000x7301-2000x803-130000x9-4000y163-2113000y263-1415000y333-2317000y4032-2000y503-230000P4：要求各類教學(xué)人員之間有適當(dāng)?shù)谋壤?，即x2所占全體教師比例不超過7%，x3不超過7%，x4不超過15%，x5不超過5%，x6不超過2%，x7不超過1%，x8不低于1%，y1不低于21%，y2不低于14%，y3不低于23%，y4不超過2%，y5不低于

38、2% P5：要求教師與行政管理職工x9之比不超過41P6：要求教師與助研x1的比不超過51 P7：要求所有人員總工資基數(shù)盡可能地小 （1） 75%的的教師是專職的:本科生教學(xué)中至少40%有博士學(xué)位：研究生教學(xué)中至少75%有博士學(xué)位：（2） 教學(xué)任務(wù)本科生：研究生：教師數(shù)：， （3） 教學(xué)人員比例：令T=（4） 教師與職工（x9）之比不超過41 ： （5） 教師與助研（x1）之比不超過51 ： （6） 全體人員工資增加總額 這里助研x1,助教x2和職工x9的工資增長率為6%，其它人員的工資增長率為8%，為目標(biāo)期望值 （7） 全體人員工資總基數(shù)約束其中為目標(biāo)期望值 目標(biāo)優(yōu)先級別如前面要求，在P3級中，校方認(rèn)為有關(guān)研究生開設(shè)的課與師生之比的重要性是本科生的2倍，建立目標(biāo)函數(shù)如下經(jīng)計算可得這個問題的解為各級目標(biāo)實現(xiàn)情況：P1級：（基本實現(xiàn)）教師的學(xué)術(shù)水平實現(xiàn)P2級：增加工資總額實現(xiàn)P3級：完成學(xué)校的各項教學(xué)工作目標(biāo)實現(xiàn)，師生數(shù)比例實現(xiàn) P4級：各類教師之間的比例實現(xiàn)P5級：教師與行政人員之比目標(biāo)實現(xiàn)P6級：教師與助研人員之比例目標(biāo)實現(xiàn)P7級：全體人員工資總基數(shù)超過了預(yù)期目標(biāo) （未實現(xiàn)）這時，學(xué)校只要能爭取到充分的經(jīng)費(fèi)，達(dá)到2 471 000美元，則以上7個目標(biāo)都能實現(xiàn)如校方無法得到比1 850