PAGEPAGE40第十三章運(yùn)籌學(xué)問題的Excel建模及求解學(xué)習(xí)運(yùn)籌學(xué)的目的在于學(xué)會用運(yùn)籌學(xué)的方法解決實(shí)踐中的管理問題，注重學(xué)以致用.很多實(shí)際問題利用人工計算要經(jīng)過長時間的艱苦工作才能完成甚至根本無法求解，但若使用運(yùn)籌學(xué)軟件則瞬間就能解決.因此在學(xué)習(xí)過程中不僅要掌握運(yùn)籌學(xué)的基本理論和計算方法，還要充分利用現(xiàn)代化的手段和技術(shù).微軟的電子表格軟件（MicrosoftExcel）為展示和分析許多運(yùn)籌學(xué)問題提供了一個功能強(qiáng)大而直觀的工具，它現(xiàn)在已經(jīng)被應(yīng)用于管理實(shí)踐中.本章將重點(diǎn)介紹如何建立和求解規(guī)劃問題的電子表格模型，對于解決大量的中、小規(guī)模的實(shí)際規(guī)劃問題，電子表格軟件是遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)的代數(shù)算法的.第一節(jié)Excel中的規(guī)劃求解工具本節(jié)中，我們將舉例說明如何使用微軟Excel以電子表格的形式建立線性規(guī)劃模型，并利用Excel中的規(guī)劃求解工具對模型求解.一、在Excel中加載規(guī)劃求解工具圖13-1要使用Excel應(yīng)首先安裝MicrosoftOffice，然后從屏幕左下角的[開始]—[程序]中找到MicrosoftExcel并啟動.在Excel的主菜單中點(diǎn)擊[工具]—[加載宏]，選擇“規(guī)劃求解”，如圖13-1所示.點(diǎn)擊[確定]后，在工具菜單中將增加[規(guī)劃求解]選項.圖13-1二、在Excel中建立線性規(guī)劃模型我們以例2-1為例說明如何在電子表格中建立該問題的線性規(guī)劃模型.建立電子表格模型時既可以直接利用問題中所給的數(shù)據(jù)和信息，也可以利用已建立的代數(shù)模型.本例的代數(shù)模型為：目標(biāo)函數(shù)圖13-3圖13-3圖13-2圖13-2顯示了將該例的數(shù)據(jù)轉(zhuǎn)送到電子表格中后所建立的電子表格數(shù)學(xué)模型（本例是一個線性規(guī)劃模型）.其中顯示數(shù)據(jù)的單元格稱為數(shù)據(jù)單元格，包括生產(chǎn)每單位藥品Ⅰ和Ⅱ所需要的4種設(shè)備的臺時數(shù)（單元格C5：D8），藥品Ⅰ和Ⅱ的單位利潤（單元格C9：D9），4種設(shè)備可用的臺時數(shù)（單元格G5：G8）.我們要做的決策是兩種藥品各生產(chǎn)多少；對這一決策的約束條件是生產(chǎn)兩種藥品所需的4種設(shè)備臺時的限制；判斷這些決策的優(yōu)劣程度的指標(biāo)是生產(chǎn)這兩種藥品所獲得的總利潤（決策目標(biāo)）.如圖13-3所示，將決策變量（藥品Ⅰ、Ⅱ的產(chǎn)量）分別放入單元格C10和D10，正好在兩種藥品所在列的數(shù)據(jù)單元格的下面.由于不知道這些產(chǎn)量會是多少，故在圖13-3中均設(shè)為零（空白的單元格默認(rèn)取值為零.實(shí)際上，除負(fù)值外的任何一個試驗解都可以）.以后在尋找產(chǎn)量最佳組合時這些數(shù)值會被改變.因此，含有需要做出決策的單元格稱為可變單元格.兩種藥品所需的4種設(shè)備臺時總數(shù)分別放入單元格E5至E8，正好在對應(yīng)數(shù)據(jù)單元格的右邊.由于所需的各種設(shè)備臺時總數(shù)取決兩種藥品的實(shí)際產(chǎn)量，如：E5=C5×C10+D5×D10（可直接將公式寫入E5，也可利用SUMPRODUCT函數(shù)，E5=SUMPRODUCT（C5：D5，C10：D10），此函數(shù)可以計算若干維數(shù)相同的數(shù)組的彼此對應(yīng)元素乘積之和），因此當(dāng)產(chǎn)量為零時所需各種設(shè)備臺時的總數(shù)也為零.由于E5至E8單元格每個都給出了依賴于可變單元格（C10和D10）的輸出結(jié)果，它們因此被稱為輸出單元格.作為輸出單元格的結(jié)果，4種設(shè)備臺時數(shù)的總需求量不應(yīng)超過其可用臺時數(shù)的限制，所以用F列中的來表示.兩種藥品的總利潤作為決策目標(biāo)進(jìn)入單元格E9，正好位于用來幫助計算總利潤的數(shù)據(jù)單元格的右邊.類似于E列的其他輸出單元格，E9=C9×C10+D9×D10或E9=SUMPRODUCT（C9：D9，C10：D10）.由于它是在對產(chǎn)量做出決策時目標(biāo)值定為盡可能大的特殊單元格，所以被稱為目標(biāo)單元格.根據(jù)對上述建模過程的總結(jié)，在電子表格中建立線性規(guī)劃模型的步驟可歸納如下：1．收集問題的數(shù)據(jù)，并將數(shù)據(jù)輸入電子表格的數(shù)據(jù)單元格；2．確定需要做出的決策，并且指定可變單元格顯示這些決策；3．確定對這些決策的限制（約束條件），并將以數(shù)據(jù)和決策表示的被限制的結(jié)果放入輸出單元格；4．選擇要輸入目標(biāo)單元格的以數(shù)據(jù)和決策表示的決策目標(biāo).三、應(yīng)用電子表格求解線性規(guī)劃模型上例的求解過程可通過在Excel的工具菜單中選擇“規(guī)劃求解”開始.“規(guī)劃求解”對話框如圖13-4所示.圖13-4“規(guī)劃求解”開始前，可通過鍵入單元格地址或選中單元格的方式確定模型的每個組成部分設(shè)置在電子表格的何處（單擊暫時隱藏對話框，再從工作表中選定單元格，然后再次單擊）.如目標(biāo)單元格地址為E9，可變單元格地址范圍為C10：D10，并選中最大值（M）表示要最大化目標(biāo)單元格.圖13-4圖13-5約束條件的設(shè)定可通過點(diǎn)擊對話框中的“添加”按鈕，彈出圖13-5所示的添加約束對話框.由于各種設(shè)備臺時的總需求量均不應(yīng)超過可用臺時數(shù)的限制，故單元格E5到E8必須小于或等于對應(yīng)的單元格G5到G8.即在添加約束對話框的左端輸入范圍E5：E8（可用選中單元格的方式），中間選擇<=（點(diǎn)開下拉列表進(jìn)行選擇），右端輸入范圍G5：G8.如果模型中還包含其他類型的函數(shù)約束，則可點(diǎn)擊“添加”按鈕以彈出一個新的添加約束對話框，根據(jù)輸出單元格與約束值之間的關(guān)系在對話框中間的下拉列表中選擇適當(dāng)?shù)募s束類型，以增加新的約束.但本例中已無其他約束了，所以只要點(diǎn)擊“確定”按鈕返回“規(guī)劃求解”對話框.如果需要修改或刪除已添加的約束，可選中該約束后點(diǎn)擊“更改”或“刪除”按鈕圖13-5到現(xiàn)在為止“規(guī)劃求解”對話框已根據(jù)圖13-3的電子表格描述了整個模型（見圖13-4）.但在求解模型前還需要進(jìn)行最后一個程序，點(diǎn)擊“選項”按鈕彈出圖13-6所示的選項對話框，這個對話框中是一些關(guān)于如何求解問題的細(xì)節(jié)的選項.對于決策變量取值非負(fù)的線性規(guī)劃模型，最主要的選項是“采用線性模型”和“假定非負(fù)”選項，（見圖13-6）.關(guān)于其他選項，對小型問題來說接受圖中所示的默認(rèn)值通常比較合適，點(diǎn)擊“確定”按鈕返回“規(guī)劃求圖13-6解”對話框.圖13-6圖13-7現(xiàn)在可以點(diǎn)擊“規(guī)劃求解”對話框中的“求解”按鈕了，它會在后臺開始對問題進(jìn)行求解.對于一個小型問題，幾秒鐘之后“規(guī)劃求解”就會顯示運(yùn)行結(jié)果.如圖13-7所示，它會顯示已經(jīng)找到了一個最優(yōu)解.如果模型沒有可行解或沒有最優(yōu)解，對話框會顯示“規(guī)劃求解找不到可行解”或“設(shè)定的單元格值不能集中”.對話框還顯示了產(chǎn)生各種報告的選項，后面將會介紹.選擇“保存規(guī)劃求解結(jié)果”并點(diǎn)擊“確定”按鈕，返回電子表格模型.圖13-7圖13-8圖13-8圖13-9顯示的是例2-2的電子表格模型及求解過程.圖13-9圖13-9這個問題的電子表格模型建立與求解過程與例2-1描述的基本相同，數(shù)據(jù)單元格（C5：E8）、（C9：E9）和（H5：H8）分別存放三種原料B1、B2、B3每斤所含四種營養(yǎng)成分的數(shù)量、每斤原料的單價以及食品所要求的最低營養(yǎng)成分的含量限制，可變單元格（C10：E10）存放三種原料配比情況（圖13-9的左上部分）.輸出單元格（F5：F8）給出了食品中實(shí)際的營養(yǎng)成分含量，目標(biāo)單元格（F9）顯示了該種食品的總成本（圖13-9的左下部分）.圖13-9的右下角顯示了“規(guī)劃求解”對話框的主要部分，包括為目標(biāo)單元格和可變單元格設(shè)定的地址，約束條件F5H5，F(xiàn)6H6，F(xiàn)7H7和F8H8通過“添加約束”對話框顯示在“規(guī)劃求解”對話框中.由于目標(biāo)是最小化總成本，所以選擇了“最小值（N）”.圖13-9的右上角顯示了點(diǎn)擊“規(guī)劃求解”對話框的“選項”按鈕后所選擇的選項，“采用線性模型”先期定義了這個模型是線性規(guī)劃模型，“假定非負(fù)”選項定義了可變單元格必須是非負(fù)約束，因為食品的配比不可能出現(xiàn)負(fù)值.點(diǎn)擊“規(guī)劃求解”對話框的求解按鈕后，得到了圖13-9中電子表格的可變單元格中顯示的最優(yōu)解，即該食品配比為原料B1是1.94斤，原料B3是2.36斤，成本為109.72元.與單純形法人工求解不同，如果輸出單元格、可變單元格或目標(biāo)單元格結(jié)果不是整數(shù)，電子表格是以小數(shù)而非分?jǐn)?shù)形式顯示的，本例結(jié)果以四舍五入的方式保留了兩位小數(shù).第二節(jié)線性規(guī)劃的應(yīng)用問題一、合理用料問題這是第二章第五節(jié)的第一個問題，由于原料膠管的長度為15分米，而輸液管、止血帶和聽診器膠管分別長5.7、4.2和3.1分米，所以每根原料膠管最多可截三種材料依次為2根、3根和4根，即總的截法不超過3×4×5=60（種）.又由于每種截法的料頭不能超過2分米，所以可先通過電子表格進(jìn)行試算以選擇其中可行的幾種截法，再利用線性規(guī)劃的方法找出用料根數(shù)最少的方案.如圖13-10的左上部分所示，單元格C4至E4顯示三種膠管的長度；C5至E5輸入不同的方法截出每種膠管的根數(shù)；F4為對應(yīng)C5至E5的不同截法所剩料頭的長度，F(xiàn)5通過判斷剩余料頭的長度是否在0到2之間顯示出該種解法是否可行，單元格F4和F5的公式見圖13-10的左下部分.圖13-10圖13-10不斷變換C5至E5的可能取值并選擇其中可行的截法（共6種），在電子表格中建立該問題的線性規(guī)劃模型.數(shù)據(jù)單元格為C9：H11、C12：H12和K9：K12，分別顯示每種截法截一根原料膠管時得到三種不同材料的數(shù)量、每種截法截取一次所用膠管的數(shù)量和三種材料的需要量；可變單元格C13：H13顯示采用每種截法所截的膠管原料數(shù)；輸出單元格I9：I12列出了某一截取方案實(shí)際獲得的三種材料數(shù)量，每種材料的數(shù)量等于各種截法截得該材料數(shù)與對應(yīng)截法所截原料數(shù)的乘積之和，如輸液管的數(shù)量I9=SUMPRODUCT(C9:H9,C13:H13)；目標(biāo)單元格I12為總用料數(shù)，應(yīng)等于各種截法所截原料數(shù)之和,即I12=SUM(C13:H13).圖13-10的右半部分顯示了“規(guī)劃求解”對話框及“選項”對話框的內(nèi)容.該問題的目標(biāo)是所用的膠管原料的總根數(shù)最少，因此設(shè)置目標(biāo)單元格為I12等于最小值.由于實(shí)際獲得的材料數(shù)量必須滿足需求量的要求，考慮到最優(yōu)方案（各種截法的某一組合）不一定能使截出的三種材料數(shù)量恰好等于需要的數(shù)量，而某種材料超過需求量是允許的，故在添加約束時可設(shè)置實(shí)際截得的數(shù)量大于等于需求量，即I9：I12>=K9：K12（本題中，該約束取“>=”和“=”的結(jié)果是相同的）；又由于截出的各種材料數(shù)量均為整數(shù)，因此約束中應(yīng)包括決策變量取整數(shù)的限制，即C13:H13=整數(shù).圖13-10的左上部分顯示了該問題的最優(yōu)方案為：分別用第二種、第四種和第五種截法截取原料40、60和10根，共用原料110根，與第二章中用大法求解的結(jié)果一致.二、放射科的業(yè)務(wù)安排圖13-11圖13-11顯示了第二章問題二的電子表格模型及求解過程.該問題的數(shù)據(jù)包括：進(jìn)行三種檢查的單位時間（C5：E5），三種檢查設(shè)備每月的可用時間（C9：E9），三項業(yè)務(wù)每月最多提供量（H6）以及每項業(yè)務(wù)的單位利潤（C10：E10）.可變單元格為C6至E6，給出三項業(yè)務(wù)每月的實(shí)際發(fā)生數(shù)量.輸出單元格為C7至E7和F6，分別表示根據(jù)各項業(yè)務(wù)的實(shí)際發(fā)生數(shù)量產(chǎn)生的設(shè)備使用時間及實(shí)際的總業(yè)務(wù)量.目標(biāo)單元格F10顯示由每項業(yè)務(wù)的單位利潤及每月實(shí)際發(fā)生數(shù)量計算的總利潤.圖13-11的左下部分給出了輸出單元格及目標(biāo)單元格的公式.圖13-11圖13-11右下部分的“規(guī)劃求解”對話框顯示了求解時應(yīng)注意的問題：求目標(biāo)單元格的最大值（利潤最大）；約束為設(shè)備的實(shí)際使用時間小于等于設(shè)備的可用時間及實(shí)際總業(yè)務(wù)量小于等于總業(yè)務(wù)提供量的限制.打開“選項”對話框，仍選擇“采用線性模型”和“假定非負(fù)”，回到“規(guī)劃求解”并按“求解”按鈕，得到問題的最優(yōu)方案為：每月X線及CT檢查的業(yè)務(wù)量分別為1320人次和480人次，磁共振業(yè)務(wù)量為0，即不必購買該設(shè)備；按最優(yōu)方案安排業(yè)務(wù)每月可獲利55200元.在電子表格上建立線性規(guī)劃或其它問題模型的方式是非常靈活的，不必拘泥于一種固定的模式.本書僅提供了一種建立模型的思路，讀者可根據(jù)不同問題的特點(diǎn)以及個人的習(xí)慣或喜好建立不同風(fēng)格的電子表格模型.第三節(jié)線性規(guī)劃的靈敏度分析前面指出線性規(guī)劃模型的許多參數(shù)，都只是對實(shí)際數(shù)據(jù)的大致估計，而不可能在研究的時候就獲得精確的數(shù)值.通過靈敏度分析可以得出每一個估計的數(shù)據(jù)需要精確到何種程度，才能保持解的最優(yōu)性.回憶例2-1某制藥廠的生產(chǎn)計劃問題，其求解結(jié)果如圖13-8所示，即生產(chǎn)4公斤藥品Ⅰ和2公斤藥品Ⅱ，總利潤為1400元.但該最優(yōu)解是在假設(shè)所有的模型參數(shù)都準(zhǔn)確的前提下做出的，在此基礎(chǔ)上，管理層如果進(jìn)一步考慮下列問題：1．如果在該廠生產(chǎn)的藥品中，有一個單位利潤的估計值是不準(zhǔn)確的，將會發(fā)生怎樣的情況？2．如果該工廠兩種藥品的單位利潤的估計都是不準(zhǔn)確的，又將會怎樣？3．如果改變該廠某種設(shè)備可用于生產(chǎn)的時間，會對結(jié)果產(chǎn)生什么影響？4．如果四種設(shè)備可用于生產(chǎn)的時間同時改變，又會對結(jié)果產(chǎn)生何種影響？在本節(jié)中，我們將重點(diǎn)介紹如何利用“規(guī)劃求解”中的“敏感性報告”對目標(biāo)函數(shù)系數(shù)以及約束條件右端值的變動進(jìn)行靈敏度分析.分析的內(nèi)容主要是系數(shù)在什么范圍內(nèi)變化時，已得到的最優(yōu)解保持不變，即發(fā)現(xiàn)哪些系數(shù)不太敏感（由于在較大范圍內(nèi)變化時，最優(yōu)解保持不變，故可以進(jìn)行粗略估計），哪些系數(shù)比較敏感（即使微小的改變都會對最優(yōu)解產(chǎn)生影響，故必須對其精確定義）.一、目標(biāo)函數(shù)系數(shù)變動的靈敏度分析首先介紹目標(biāo)函數(shù)系數(shù)的靈敏度分析，回顧一下就可以知道，這些系數(shù)表示各種決策對總目標(biāo)的單位貢獻(xiàn).下面以例2-1某藥廠的生產(chǎn)計劃問題的目標(biāo)函數(shù)系數(shù)變動情況進(jìn)行討論.問題1：如果該藥廠一種藥品的單位利潤的估計是不精確的，結(jié)果怎樣？首先看一下，如果藥品Ⅱ的單位利潤300元的估計是不精確的情況，假設(shè)：藥品Ⅱ的單位利潤=電子表格中D9單元格中的數(shù)據(jù)現(xiàn)在，=300元，下面我們來分析一下在保持最優(yōu)解不變的條件下，可能的最大值與最小值.這樣，也就可以看出為300元的這一估計能夠在多大程度上偏離實(shí)際值而不會改變解的最優(yōu)性.（一）使用電子表格進(jìn)行靈敏度分析電子表格的一個強(qiáng)大的優(yōu)點(diǎn)就是可以方便互動地展開各種形式的靈敏度分析.通過運(yùn)用規(guī)劃求解工具來求解最優(yōu)解，模型參數(shù)值的改變所造成的影響一下子就可以顯示出來.圖13-13圖13-12為了說明這一點(diǎn)，圖13-12顯示了藥品Ⅱ的單位利潤從開始的=300元降到=250元的情況，與圖13-8相比，最優(yōu)解沒有絲毫的變化.事實(shí)上，該問題唯一的變動是電子表格中C9單元格中的數(shù)據(jù)從300元降到250元，以及E9單元格總利潤減少了100元（因為每單位藥品Ⅱ所提供的利潤減少了50元）.因為最優(yōu)解沒有變動，我們可以知道在不影響最優(yōu)解的前提下，藥品Ⅱ的單位利潤=300元的最初估計是較高的.圖13-13圖13-12那么，如果這一估計值較低又會怎樣呢？圖13-13表示了將=300元增加到=350元的情況.同樣，最優(yōu)解沒有發(fā)生變化.因為，增加或減少最初的=300元均不會對最優(yōu)解產(chǎn)生任何影響，就不是很敏感的系數(shù)，也就不需要為了保證最優(yōu)解不會改變，而花很大力氣去得到的更精確的值.但是對的研究至此并沒有結(jié)束，因為實(shí)際值很可能會超出250到350元這一范圍，那么在保持最優(yōu)解不變的條件下，到底可以在什么樣的范圍內(nèi)取值呢？當(dāng)然可以在電子表格中采取試驗的方法，不斷增加或減少的值，直到最優(yōu)解發(fā)生改變，以找到最優(yōu)解發(fā)生變化時對應(yīng)的值.但是，這樣計算太麻煩了，是否有簡便一些的方法呢？答案是肯定的.（二）利用敏感性報告進(jìn)行目標(biāo)系數(shù)的靈敏度分析如圖13-7所示，在求得最優(yōu)解之后，規(guī)劃求解工具會給出相應(yīng)的信息，同時，在其右邊列出了它可以提供的三個報告.選擇第二項敏感性報告的選項，就可以得到靈敏度的分析報告，它顯示在模型的工作表之前.圖13-14圖13-14顯示了本例敏感性報告中的一部分.終值一欄表明了問題的最優(yōu)解，第二欄給出了遞減成本，遞減成本提供了為使決策變量取正值，相應(yīng)的目標(biāo)系數(shù)需要減少的數(shù)量.對于本例，由于兩決策變量的取值均為正數(shù)，故遞減成本均為零.第三欄表示了目標(biāo)函數(shù)的現(xiàn)值，最后兩欄表示為使最優(yōu)解保持不變，目標(biāo)系數(shù)允許增加與減少的最大值.圖13-14例如，考慮決策變量X1的目標(biāo)系數(shù)，從圖13-14中表示產(chǎn)品Ⅰ的一行中可知，可以減少50，可以增加1E+30.在電子表格中1E+30是1030的縮寫，Excel使用這一極大的數(shù)值來表示無窮大.因此，從靈敏度的分析報告中可知： 的現(xiàn)值：200 的允許增加值：無窮大此時無上限 的允許減少值：50此時 的變化范圍：因此，只要在上面的變化范圍內(nèi)變動，并且不改變模型的其他任何內(nèi)容，最優(yōu)解將始終保持在不變.該藥廠的另一藥品的單位利潤的變化范圍也可以用同樣的方法得出，是藥品Ⅱ的單位利潤，表中表示藥品Ⅱ的第二行給出了下面關(guān)于的信息： 的現(xiàn)值：300 的允許增加值：100此時 的允許減少值：300此時 的變化范圍：目標(biāo)函數(shù)的兩個系數(shù)的允許變化范圍都很大，因此，盡管藥品Ⅰ和藥品Ⅱ的單位利潤可能僅僅是實(shí)際值的一個粗略估計，我們也可以相信，這個估計值對最優(yōu)解的正確性不會有影響.但在一些線性規(guī)劃模型中，目標(biāo)系數(shù)微小的變動都可能會影響最優(yōu)解.這樣的系數(shù)稱為敏感參數(shù).靈敏度的分析報告中會直接顯示目標(biāo)中哪些系數(shù)是敏感的，這些系數(shù)允許的變化區(qū)域很小，因此，必須格外小心，盡量取得這些數(shù)據(jù)的精確值.在求得模型的最優(yōu)解之后，目標(biāo)系數(shù)的允許變化范圍還有一個很重要的用途.在問題的線性規(guī)劃分析結(jié)束之后，如果外界的環(huán)境發(fā)生了一定的變化，靈敏度分析可以在無需重新求解的情況下，表明模型參數(shù)的變化是否造成了最優(yōu)解的改變.例如經(jīng)過一段時間以后，如果藥品的單位利潤發(fā)生了較大的變化，通過其允許變化范圍，可以一眼看出原來的最優(yōu)組合是否依然適用.有了目標(biāo)系數(shù)的允許變化范圍，在判斷問題時，就不需要重新建模與求解，這一點(diǎn)對線性規(guī)劃問題的解決是有很大幫助的，特別是在處理一個大型模型時.（三）目標(biāo)系數(shù)的同時變動因為存在許多不確定性因素，目標(biāo)函數(shù)系數(shù)的值，如單位利潤，通常都只是對實(shí)際值的估計.上面所討論的是只有一個系數(shù)變動時的情況，這類問題在求解一個系數(shù)的允許變化范圍時，假設(shè)其他所有系數(shù)都是正確的，研究的系數(shù)是唯一可能與實(shí)際值不符的變動的系數(shù).但事實(shí)上，所有的系數(shù)（至少一個以上）可能同時都是不準(zhǔn)確的，如果這樣的話，是否可能會導(dǎo)致求得的最優(yōu)解不正確呢？這是最關(guān)鍵的問題.如果可能對最后的結(jié)果產(chǎn)生影響，就必須對這些系數(shù)作進(jìn)一步的分析.另一方面，如果靈敏度分析表明目前的參數(shù)估計不會影響最優(yōu)解的正確性，那么，管理者可以增加對該模型及其所提供的解決方法的信心.以下將介紹如何在不重新求解模型的條件下，確定如果目標(biāo)函數(shù)的幾個系數(shù)同時變化，可能造成的對最優(yōu)解的影響．我們?nèi)岳美?-1提出如下問題：問題2：如果該藥廠兩種藥品的單位利潤的估計都是不準(zhǔn)確的，將會對結(jié)果產(chǎn)生怎樣的影響？例如，原來藥品Ⅰ和藥品Ⅱ的單位利潤分別為200元和300元，現(xiàn)在由于原料成本的變化，每公斤藥品Ⅰ和藥品Ⅱ的單位利潤分別變?yōu)?80元和355元，最優(yōu)解是否發(fā)生變化？在分析多個系數(shù)同時變動的情況時，仍然要使用敏感性報告中提供的每個系數(shù)的允許增加值和減少值數(shù)據(jù)，下面介紹多個系數(shù)同時變動的百分之百法則.首先定義的允許增加（減少）百分比為的增加量（減少量）除以的允許增加量（允許減少量）的值.這樣我們可以計算出的允許減少百分比為，的允許增加百分比為，的允許減少百分比與的允許增加百分比之和為.目標(biāo)函數(shù)系數(shù)同時變動的百分之百法則：如果目標(biāo)函數(shù)的系數(shù)同時變動，當(dāng)其所有允許增加百分比和允許減少百分比之和不超過百分之百時，最優(yōu)解不會改變，如果超過百分之百，則不能確定最優(yōu)解是否改變.圖13-15因為本例中的允許減少百分比與的允許增加百分比之和為95%不超過100%，所以當(dāng)每公斤藥品Ⅰ的利潤減少為180元，每公斤藥品Ⅱ的利潤增加為355元時，此線性規(guī)劃最優(yōu)解仍然為藥品Ⅰ生產(chǎn)4公斤和藥品Ⅱ生產(chǎn)2公斤（即），此時有最大利潤為（元），如圖13-15所示.圖13-15這一法則并沒有表示出，在變動百分比之和超過百分之百的情況下，可能的結(jié)果.這一結(jié)果還有賴于系數(shù)變動的方向.但是，只要變動百分比之和不超過百分之百，最優(yōu)解是肯定不會改變的.記住，我們可以讓單一的目標(biāo)函數(shù)系數(shù)在整個允許范圍內(nèi)變動，但這只有在其他目標(biāo)函數(shù)系數(shù)都不變的情況下才有效.如果多個系數(shù)同時變動，我們必須研究各個系數(shù)的變動百分比.二、約束右端值的靈敏度分析之所以要分析函數(shù)約束右端值變動的原因與前面一樣，因為在建模時，還不能得到模型的這些參數(shù)的精確值，只能對其作粗略的估計.因此，我們希望知道在這些估計不準(zhǔn)確的情況下會產(chǎn)生怎樣的后果.除此之外一個更主要的理由是因為，這些常數(shù)（通常代表資源的可用量）往往不是由外界決定的而是管理層的政策決策.因此管理者希望知道如果改變這些決策是否會提高最終的收益.影子價格分析就是為管理者提供這方面的信息.下面是關(guān)于例2-1的第三個問題：問題3：如果改變該廠某設(shè)備可用于生產(chǎn)的時間，結(jié)果將如何？（一）約束右端值的影子價格分析回憶第二章中關(guān)于影子價格的經(jīng)濟(jì)含義，我們知道影子價格代表單位資源在最優(yōu)利用的條件下所產(chǎn)生的經(jīng)濟(jì)效果.即在模型獲得最優(yōu)解的情況下，約束條件右端值在一定范圍內(nèi)每增加（減少）一個單位，使目標(biāo)函數(shù)值增加（減少）的量.其中，一定范圍是指保持影子價格不變的右端值變化范圍.在影子價格分析中，每次分析一個函數(shù)約束，可以將該函數(shù)約束右端值的常數(shù)增加一個單位后重新求解，觀察目標(biāo)函數(shù)值增加的量來確定影子價格，也可以利用靈敏度報告中提供的關(guān)于每一個函數(shù)約束的影子價格數(shù)據(jù).從一個約束的影子價格中就可以直接看出，決策改變而引起的約束常數(shù)的改變所造成的影響.只要約束常數(shù)的變動不大，那么目標(biāo)函數(shù)值的變動就等于約束常數(shù)的變動（正或負(fù)）乘以影子價格.為了說明影子價格的含義，我們以第二章第五節(jié)中的第二個應(yīng)用，即放射科的業(yè)務(wù)安排問題為例來加以討論.該問題最初的線性規(guī)劃模型如圖13-16上半部分所示.單元格H6及C9至E9中的值1800，300，120，圖13-16120分別表示總業(yè)務(wù)提供量以及三種設(shè)備的可用時間的限制.可變單元格C6至E6中的最優(yōu)解表明放射科每月安排1320人次的X線檢查和480次的CT檢查.目標(biāo)單元格F10顯示如此安排后每月的總利潤為55200元.圖13-16得到這些信息后，科室的領(lǐng)導(dǎo)可能希望知道增加一單位資源的可用量對總利潤的影響，即影子價格.首先從業(yè)務(wù)提供量H6開始分析，圖13-16的下半部分表示了放射科可以提供的業(yè)務(wù)量由1800增至1801時，對結(jié)果的影響.將圖13-16上下兩表中的目標(biāo)單元格H10進(jìn)行對比，可看出利潤的增加量為：利潤的變化量=55220元-55200元=20元從而計算出業(yè)務(wù)提供量的影子價格為20元/每人次，即增加1人次的業(yè)務(wù)提供量對總利潤的貢獻(xiàn)是20元.用上述方法計算影子價格簡單明了，但需要對每個約束進(jìn)行試算，且有時可能得到錯誤的結(jié)果（后面將討論）.此外，我們還可以采用“規(guī)劃求解”結(jié)果給出的敏感性報告直接得到各個約束的影子價格.圖13-17顯示了靈敏度分析中與函數(shù)約束有關(guān)的部分，其中的第四欄給出了各約束的影子價格.結(jié)果如下：業(yè)務(wù)提供量的影子價格=20元/人次X線檢查的影子價格=0元/小時CT檢查的影子價格=160元/小時磁共振檢查的影子價格=0元/小時圖13-17圖13-17這些影子價格都是資源增加一個單位引起的總利潤的增加量.為什么X線檢查的影子價格為0？可以通過比較圖13-16上表中C7和C9來說明.X線檢查設(shè)備的可用時間有300小時，而按最優(yōu)解的業(yè)務(wù)量使用該設(shè)備的時間僅為132小時，已有168小時的閑置.因此，即使再增加設(shè)備的可用時間也不會改變最優(yōu)解和總利潤，同樣可以解釋磁共振檢查的影子價格也為0的原因.（二）影子價格的靈敏度分析圖13-7的第六、七欄給出了每一約束限制值在什么范圍內(nèi)變化時，該約束的影子價格是不變的.這一范圍稱為影子價格的有效區(qū)域，可以看出：業(yè)務(wù)提供量的影子價格的有效區(qū)域的上限為：1800+1680=3480，下限為：1800-1320=480，其有效區(qū)域為：，即當(dāng)業(yè)務(wù)提供量在此范圍內(nèi)變化時，每增加（減少）一人次，總利潤也會相應(yīng)地增加（減少）20元；類似可得X線使用時間、CT使用時間以及磁共振使用時間的影子價格有效區(qū)域分別為：，，.圖13-18我們再來看第二章的例2-1，該問題最初的線性規(guī)劃模型如圖13-8所示.G欄中的常數(shù)（12，8，16，12）表示四種設(shè)備可用的臺時數(shù).當(dāng)我們將設(shè)備B的可用時間從8小時增加到9小時時，我們發(fā)現(xiàn)總利潤增加了100元（從1400元增加到了1500元），如圖13-18所示.但100元并不是設(shè)備B可用時間的影子價格.圖13-18圖13-16顯示了其敏感性報告的第二部分.終值欄給出了輸出單元格E5至E8的終值分別為12，8，16，8（如圖13-8的E欄所示）；約束限制值一欄即表13-8中G5至G8中的常數(shù).從陰影價格一欄中可以看出，設(shè)備B可用時間的影子價格為150元.通過分析其影子價格的有效區(qū)域可知，可用時間在4—8小時之間時，每增加（減少）一個小時的可用時間，總利潤會相應(yīng)增加（減少）150元.但由于設(shè)備B的可用時間正好為8小時，所以再繼續(xù)增加1個小時的可用時間后，約束限制值已經(jīng)超過了圖13-19影子價格的有效區(qū)域，故總利潤的增加值只有100元而不是150元.從圖13-9中還可以看出，設(shè)備A和設(shè)備D的影子價格均為0，設(shè)備C的影子價格為12.5元，有效區(qū)域分別為：，，.圖13-19（三）約束右端值同時變動的情況函數(shù)約束右端值的有效區(qū)域表示的是，約束右端值的變動在有效區(qū)域內(nèi)時，該約束的影子價格就可用于評估約束右端值改變造成的影響.但必須注意的是，只有在僅一個約束右端值變動而其他約束右端值均不變的情況下，該約束右端值的有效區(qū)域才是完全有效的.而實(shí)際上，由于管理層在約束右端值上的決策往往是相關(guān)的，因此約束右端值經(jīng)常會同時變動，如果多個約束右端值同時變動，那么如何評估可能造成的影響呢？仍以放射科的業(yè)務(wù)安排問題為例，我們已經(jīng)知道放射科已有X線及CT檢查設(shè)備，且CT檢查設(shè)備使用時間具有最大的影子價格為160元，X線使用時間的影子價格為0元，科室領(lǐng)導(dǎo)希望減少X線的可用時間而相應(yīng)增加CT檢查的可用時間.假設(shè)減少X線的可用時間3小時可相應(yīng)增加CT檢查的可用時間1小時.在這種同時變動的情況下，會產(chǎn)生怎樣的后果呢？根據(jù)影子價格分析，將X線的可用時間減少3小時，并將CT檢查時間增加1小時，所產(chǎn)生的結(jié)果如下：CT檢查時間：120→121總利潤的變化量=影子價格=160元X線檢查時間：300→297總利潤的變化量=-影子價格×3=-0×3=-0元總利潤的凈變化=160元但是，我們現(xiàn)在還不能確定，兩個約束右端值這樣改變以后，原先的影子價格是否依然有效.檢驗有效性的一種方便快捷的方法就是將這些數(shù)據(jù)代入電子表格的相應(yīng)單元格中去，重新求解.圖13-20所示的電子表格顯示出總利潤的凈增量確實(shí)為160元（從55200元增加到55360元），因此，影子價格在上面約束右端值同時變動的情況下是有效的.圖13-20如果我們繼續(xù)減少X線檢查時間而相應(yīng)增加CT檢查時間，結(jié)果會如何呢？當(dāng)然可以將數(shù)據(jù)代入電子表格后再重新求解，但這種方法是不切實(shí)際的，特別是有兩個以上的約束右端圖13-20約束右端值同時變動的百分之百法則：對于所有變化的約束條件右邊常數(shù)值，當(dāng)其所有允許增加百分比和允許減少百分比之和不超過百分之百時，其影子價格是有效的.其中約束右端值的允許增加（減少）百分比的定義同目標(biāo)系數(shù)的允許增加（減少）百分比一樣，為約束右端值的增加量（減少量）除以約束右端值的允許增加量（減少量）的值.為了解釋這一法則，仍然考慮圖13-20的情形，將X線的可用時間減少3小時，并將CT檢查時間增加1小時.按照百分之百法則，計算如下：CT檢查時間：120→121占允許增加量的百分比X線檢查時間：300→297占允許減少量的百分比總和因為變動百分比之和1.82%小于百分之百，所以用影子價格來預(yù)測這些變動的影響是有效的.上面求得的變動百分比之和為1.82%，表明即使將原先的變動擴(kuò)大50倍也不會使影子價格失效.第四節(jié)特殊形式的線性規(guī)劃問題在本節(jié)中，我們將重點(diǎn)討論三類特殊類型的線性規(guī)劃問題——運(yùn)輸問題、0-1規(guī)劃問題及指派問題的Excel模型及求解.一、運(yùn)輸問題（一）運(yùn)輸問題的模型及參數(shù)運(yùn)輸問題的描述見本教材第三章.一般的運(yùn)輸問題（表2-1）就是要解決把某種產(chǎn)品從若干個產(chǎn)地調(diào)運(yùn)到若干個銷地，在每個產(chǎn)地的供應(yīng)量與每個銷地的需求量已知，并知道各產(chǎn)銷地之間的運(yùn)輸單價的前提下，如何確定一個使得總的運(yùn)輸費(fèi)用最小的方案.實(shí)際上運(yùn)輸問題的模型在供應(yīng)量和需求量兩方面做出了如下的假設(shè)：產(chǎn)銷平衡假設(shè)：每一個產(chǎn)地都有一個固定的供應(yīng)量，所有的供應(yīng)量都必須運(yùn)輸?shù)戒N地；與之相類似，每一個銷地都有一個固定的需求量，整個需求量都必須由產(chǎn)地滿足，即總供應(yīng)量等于總需求量.對于運(yùn)輸問題而言，當(dāng)且僅當(dāng)供應(yīng)量的總和等于需求量的總和時，問題才有可行解.某些實(shí)際的問題并不符合產(chǎn)銷平衡的假設(shè)，供應(yīng)量實(shí)際上代表著所要運(yùn)輸?shù)漠a(chǎn)品的最大數(shù)量（而不是一個固定的數(shù)值），需求量實(shí)際上也是代表著所接受的最大數(shù)量（也不是一個固定的數(shù)值）.這些問題并不符合運(yùn)輸問題模型，所以它們是運(yùn)輸問題的變形.表3-1的中間部分給出了運(yùn)送貨物的單位運(yùn)費(fèi)，關(guān)于運(yùn)費(fèi)對于任何一個運(yùn)輸問題都有下面的一個基本假設(shè).運(yùn)輸費(fèi)用假設(shè)：從任何一個出發(fā)地到任何一個目的地的貨物運(yùn)費(fèi)與所運(yùn)輸?shù)臄?shù)量成線性比例關(guān)系，因此總運(yùn)費(fèi)就等于單位運(yùn)費(fèi)乘以所運(yùn)輸?shù)臄?shù)量.運(yùn)輸問題所需要的數(shù)據(jù)僅僅是供應(yīng)量、需求量和單位運(yùn)費(fèi).這些就是模型參數(shù)，所有的這些參數(shù)都可以總結(jié)在一個表格中，這個表格就叫做參數(shù)表.表3-1就是典型的運(yùn)輸問題的參數(shù)表，而表3-3則是運(yùn)輸問題例3-1的參數(shù)表.運(yùn)輸問題模型：如果一個問題可以完全描述成如表3-1所示的參數(shù)表形式，并且符合產(chǎn)銷平衡假設(shè)和運(yùn)輸費(fèi)用假設(shè)，那么這個問題（不管其中是否涉及到運(yùn)輸）都適用于運(yùn)輸問題模型，最終目標(biāo)都是要使總運(yùn)費(fèi)最小.這個模型的所有參數(shù)都包含在參數(shù)表中.（二）運(yùn)輸問題的Excel模型及求解在建立了運(yùn)輸問題的線性規(guī)劃模型之后，我們可以使用Excel來描述和解決運(yùn)輸問題.以例3-1為例.首先，我們需要在電子表格中輸入兩個表格.第一個表格是參數(shù)表，提供有關(guān)這一問題的所有參數(shù)；第二個就是求解表格，包含了從每個醫(yī)院到每個貧困縣的人員安排情況.圖13-21顯示了這兩個表格，以及求解本例所需要附加的公式.在這個電子表格中需要包含運(yùn)輸問題的兩類約束，即供應(yīng)約束和需求約束.對于供應(yīng)約束來說，圖13-21求解表格中的H列算出了每家醫(yī)院抽出的醫(yī)務(wù)人員總數(shù)，它是其相應(yīng)行所有決策變量單元格數(shù)據(jù)的總和.例如，在H15單元格中的等式就是“H15=D15+E15+F15+G15”或者是“H15=SUM（D15：G15）”.每家醫(yī)院所能抽出的人員數(shù)均包含在J列中，因此，H列的單元格中的數(shù)據(jù)應(yīng)該等于相應(yīng)的J列的單元格中的數(shù)據(jù).對于需求約束來說，向每一個貧困縣派出的醫(yī)務(wù)人員總數(shù)在電子表格的第18行列出，是其相應(yīng)列的所有決策變量單元格數(shù)據(jù)之和.例如，D18=SUM（D15：D17）.每縣的實(shí)際需要人數(shù)在第20行中給出.圖圖13-21注：某省醫(yī)療隊巡回醫(yī)療扶貧問題的Excel模型.圖中從第3行到第9行顯示了參數(shù)表，從第12行到第20行顯示了求解表格.本模型利用“規(guī)劃求解”處理得到了最優(yōu)的人員安排計劃，圖的底部及右側(cè)分別給出了輸出單元格的公式以及建立“規(guī)劃求解”所需要的說明.H18單元格計算出了總費(fèi)用.它是參數(shù)表和求解表主體部分每一相應(yīng)單元格乘積的和，即H18=SUMPRODUCT（D6：G8，D15：G17）.圖13-21的右上半部分是“規(guī)劃求解”對話框中輸入的內(nèi)容.這些內(nèi)容說明了“規(guī)劃求解”工具通過改變?nèi)藛T安排（決策變量單元格D15到G17），按照派到每一個貧困縣的人員數(shù)量等于它的總需求量（D18：G18=D20：G20）以及從每一所醫(yī)院抽出的總?cè)藬?shù)等于其所能抽出的人員數(shù)（H15：H17=J15：J17）的約束條件對總費(fèi)用進(jìn)行最小化處理（單元格H18計算出了結(jié)果）.圖13-21的右下半部分顯示了“規(guī)劃求解選項”，（采用線性模型）說明運(yùn)輸問題同樣也是一個線性規(guī)劃問題，（假定非負(fù)）說明所有的決策變量（派出人員數(shù)）必須是非負(fù)的.決策變量的值（派出人員數(shù)）在單元格（D15：G17）中.對于每一個單元格來說，可以先輸入任意數(shù)值（如0）或不輸入（默認(rèn)為0）.在按下“規(guī)劃求解”對話框的求解按鈕后，“規(guī)劃求解”工具就會確定出每一個決策變量的具體數(shù)值.最優(yōu)解及所得到的最小總費(fèi)用如圖13-21所示.（三）其他運(yùn)輸問題的處理前面的討論都是以供銷平衡為前提的.對于產(chǎn)銷不平衡的運(yùn)輸問題，即總需求量與總供應(yīng)量不相等的運(yùn)輸問題，顯然是沒有可行解的.因此，對于產(chǎn)銷不平衡的運(yùn)輸問題，我們可以先化為產(chǎn)銷平衡的運(yùn)輸問題然后再求解.將例3-1稍作修改，其參數(shù)表變?yōu)楸?3-1：表13-1修改后運(yùn)輸問題的人均費(fèi)用B1B2B3B4醫(yī)院抽出人數(shù)人均費(fèi)用（單位：百元）A1A2A3縣需求人數(shù)2910791342784257384621\23與例3-1比較，只是醫(yī)院A2的抽出人數(shù)增加了兩人，這樣一來總抽出人數(shù)為23人，大于總需求人數(shù)21人，是一個產(chǎn)大于銷的運(yùn)輸問題.為此再建立一個假想的縣B5，B5的需求人數(shù)為2人，而從A1、A2、A3派往B5不需要花費(fèi)，所以可令，即對應(yīng)的人均費(fèi)用為0.這樣就得到了修改后問題的產(chǎn)銷平衡的參數(shù)表，將產(chǎn)大于銷的運(yùn)輸問題化成了產(chǎn)銷平衡的運(yùn)輸問題（見表13-2）.表13-2修改后產(chǎn)銷平衡運(yùn)輸問題的人均費(fèi)用B1B2B3B4B5醫(yī)院抽出人數(shù)人均費(fèi)用（單位：百元）A1A2A3縣需求人數(shù)29107091342078425073846223利用電子表格對其求解，可得到如圖13-22所示的最優(yōu)解和最小總費(fèi)用.類似地，如果是銷大于產(chǎn)的運(yùn)輸問題，則可以采用增設(shè)虛擬產(chǎn)地的辦法使之化為產(chǎn)銷平衡的運(yùn)輸問題來處理.產(chǎn)銷不平衡的運(yùn)輸問題還有一種情況，一個銷地同時存在著最小需求和最大需求，于是所有在這兩個數(shù)值之間的數(shù)量都是可以接收的.圖圖13-22在例3-1中將問題的要求作如下變化：各醫(yī)院抽出的人員總數(shù)不變?yōu)?1人，而B1、B2、B3、B4四個縣的最小需求人數(shù)分別為3、6、2、4人，最大需求分別為5、9、5、6人，最大總需求人數(shù)為25人.由于總需求比可以抽出的人數(shù)多出4人，為了化成產(chǎn)銷平衡的運(yùn)輸問題，可在參數(shù)表中增加虛擬醫(yī)院A4這一行，可抽調(diào)人數(shù)為4人.另外，為了區(qū)別必須滿足的需求量（最小需求量）與可以不滿足的需求量，可將每個縣分為兩列.如B1縣的第一列為B11，它的需求量是必須要滿足的3人，第二列為B12，它的需求量是可以不滿足的2人.顯然，必須滿足的最小需求不能從虛擬的醫(yī)院抽調(diào)人員.為了必須滿足B11的3人，我們將虛擬醫(yī)院到B11的人均費(fèi)用定為M（是一個足夠大的正數(shù)）.如果虛擬醫(yī)院抽調(diào)到B11的員數(shù)為，則為此付出的費(fèi)用將為，是個很大的正數(shù)，這顯然不符合總費(fèi)用最小的目標(biāo)，這樣就保證了.但對于則可以定為0，因為虛擬的醫(yī)院并沒有抽出人員，人均費(fèi)用當(dāng)然為零，又因為B12的需求2人可以不滿足，所以可以為正數(shù).另外，，，.對其他的三個縣也進(jìn)行了同樣的處理.該問題的參數(shù)表見表13-3.表13-3有最小需求的運(yùn)輸問題的人均費(fèi)用表B11B12B21B22B31B32B41B42醫(yī)院抽出人數(shù)人均費(fèi)用（單位：百元）A1A2A3A4縣需求人數(shù)22991010779113344225884422557M0M0M0M0432632342在用電子表格對該問題建模及求解時，表中的M可以輸入一個足夠大的數(shù)，如10000，如圖13-23.圖圖13-23二、整數(shù)規(guī)劃及0—1規(guī)劃問題（一）整數(shù)規(guī)劃問題的計算機(jī)求解在線性規(guī)劃問題中，最優(yōu)解可能是整數(shù)，也可能不是整數(shù)，但對于某些實(shí)際問題，要求決策變量必須取整數(shù)，即整數(shù)規(guī)劃問題.如：例13-1利用電子表格對該整數(shù)規(guī)劃問題求解的方法與線性規(guī)劃問題類似，只是在“規(guī)劃求解”對話框的約束一欄中，增加對決策變量的整數(shù)約束.利用電子表格對該問題求解的結(jié)果見圖13-24.圖13-24（二）0—1圖13-24以例3-2為例，根據(jù)其代數(shù)模型可建立如圖13-5的電子表格模型：圖圖13-25該電子表格模型中可變單元格為（C7：F7），其取值為1（0）時表示攜帶（不攜帶）相應(yīng)的物品，即決策變量為0—1變量.因此，應(yīng)有決策變量為二進(jìn)制的約束限制（見圖13-25的左下部分）.該模型僅包含一個關(guān)于所攜帶物品重量的約束，該同學(xué)所攜帶物品的總重量（顯示在G5）為所攜帶的所有物品的重量之和，即G5=SUMPRODUCT(C5:F5,C7:F7)，其值不應(yīng)超過背包的重量限制5，故有G5≤I5.其攜帶物品的總價值（目標(biāo)單元格）為G8=SUMPRODUCT(C6:F6,C7:F7).在“規(guī)劃求解選項”對話框中，仍選擇“采用線性模型”和“假定非負(fù)”.讀者可將例3-3作為練習(xí).三、指派問題（一）指派問題的模型及計算機(jī)求解指派問題既是0-1規(guī)劃的特殊情況，也是與運(yùn)輸問題密切相關(guān)的一類特殊的線性規(guī)劃問題，其電子表格模型與運(yùn)輸問題類似.指派問題也需要滿足一些假設(shè)：1．被指派者的數(shù)量和任務(wù)的數(shù)量是相同的.2．每一個被指派者完成且只完成一項任務(wù).3．每一項任務(wù)必須且只能由一個被指派者來完成.4．每一個被指派者和每一項任務(wù)的組合都會有一個相關(guān)的成本（收益）.5．問題的目標(biāo)是要確定怎樣進(jìn)行指派才能使得總成本達(dá)到最小（總收益最大）.以例3-4為例，我們需要確定的是將哪項化驗任務(wù)指派給哪位化驗員，能夠使所需總時間最少？該問題的電子表格模型見圖13-26.與運(yùn)輸問題類似，指派問題的模型也需要在電子表格中輸入兩個表格，即參數(shù)表和求解表.參數(shù)表主體部分（D6：G9）給出了四位化驗員分別完成四種化驗所需要的時間，而求解表主體部分（D16：G19，初值均為0）給出了具體的人員安排情況，決策變量單元格取值為1或0時，分別表示指派或不指派某位化驗員完成某項化驗，如D18=1表示指派丙完成化驗A，而E16=0則表示不指派甲完圖圖13-26成化驗B（見圖13-26的左上部分）.指派問題也有兩類約束，提供量約束：根據(jù)第二條假設(shè)，每位化驗員只完成一項化驗任務(wù)，即求解表中每一行的四個單元格中，只能有一個為1，其余均為0，每行之和（列入單元格H16：H19）為1；需求量約束：根據(jù)第三條假設(shè)，每種化驗只能由一位化驗員完成，即求解表的每列之和（列入單元格D20：G20）為1.H20單元格計算出了總時間.它是參數(shù)表和求解表主體部分每一相應(yīng)單元格乘積的和，即H20=SUMPRODUCT（D6：G9，D16：G19）.圖13-26的右上半部分是“規(guī)劃求解”對話框中輸入的內(nèi)容.除提供量約束（H16：H19=J16：J19）和需求量約束（D20：G20=D22：G22）外，由于指派問題的決策變量也為0—1變量，應(yīng)有決策變量為二進(jìn)制的約束.指派問題也屬于線性規(guī)劃，故仍選擇“采用線性模型”和“假定非負(fù)”.問題的最優(yōu)解及所得到的最少時間如圖13-26所示.例3-5是一個最大化的指派問題，其電子表格模型與例3-4完全一致，區(qū)別僅在于“規(guī)劃求解”對話框中，設(shè)置目標(biāo)單元格等于“最大值”.（一）指派問題的變形我們經(jīng)常會遇到指派問題的變形.之所以稱它們?yōu)樽冃危驗樗鼈兌疾粷M足前述指派問題所有假設(shè)之中的一個或者多個，如：1．有一些被指派者并不能完成某一些任務(wù).2．雖然每一個被指派者完成一項任務(wù)，但是任務(wù)比被指派者多.所以其中某些任務(wù)并沒有得到執(zhí)行.3．雖然每一項任務(wù)只由一個被指派者完成，但是這里被指派者比要完成的任務(wù)多.所以，其中有一些被指派者沒有指派到任務(wù).4．每一個被指派者可以同時被指派給多于一個的任務(wù).5．每一項任務(wù)都可以由多個被指派者共同完成.在此，我們僅就情況2展開詳細(xì)討論，以例3-6為例.圖圖13-27該問題的電子表格模型與一般指派問題的不同之處在于，需求量約束不是嚴(yán)格的等式約束.由于研究人員少而課題任務(wù)多，且每人只能承擔(dān)一項研究，所以會出現(xiàn)有些課題無人承擔(dān)的情況，由于決策變量取值為0或1，某項課題無人承擔(dān)時，求解表中對應(yīng)列之和為0，有1人承擔(dān)時和為1.因此，可將需求約束設(shè)定為每列之和小于等于1（見圖13-27的左上部分）.如果指派問題中出現(xiàn)人員多而任務(wù)少的情況（情況3），則在模型的求解表中需求量約束仍保持嚴(yán)格的等式約束，即每項任務(wù)都必須指派一人完成，而提供量約束設(shè)定為每行之和小于等于1，即有些人員沒有被分配任務(wù).如果一個人可以被分配多于一個的任務(wù)（情況4），可取消模型中對于提供量的約束限制；如果一項任務(wù)可以由多個人共同承擔(dān)（情況5），則應(yīng)視具體情況建立模型.在指派問題中，也可能出現(xiàn)某人不能完成某項任務(wù)的情況（情況1），則在約束中應(yīng)加入相應(yīng)的決策變量等于零的限制.例如在例3-6中增加一條件：甲不能承擔(dān)課題B，則在圖13-27的模型參數(shù)表中，E6單元格中以“—”取代原來的數(shù)字“5”，而在“規(guī)劃求解”對話框中，添加約束“E15=0”.這樣可保證在最終求解結(jié)果中，不會出現(xiàn)指派甲承擔(dān)課題B的情況.第五節(jié)目標(biāo)規(guī)劃問題目標(biāo)規(guī)劃的電子表格模型在結(jié)構(gòu)及處理方式上與線性規(guī)劃模型是相同的，主要的區(qū)別一是目標(biāo)規(guī)劃中引入了正負(fù)偏差變量，這些偏差變量用于反映目標(biāo)的實(shí)現(xiàn)情況，在模型中可以作為決策變量處理；二是由于要按照一定的次序?qū)崿F(xiàn)多個目標(biāo)，于是在目標(biāo)函數(shù)中引入了優(yōu)先因子P1，P2，…，Pn并規(guī)定Pk?Pk+1，表示Pk比Pk+1具有絕對的優(yōu)先權(quán).但應(yīng)注意在電子表格中不能用字母來表示這種優(yōu)先因子，而只能由具體的數(shù)字去代替.為了保證Pk?Pk+1，可將Pk和Pk+1的取值相差10n倍以上，n可視具體情況取1，2或3等，如果各目標(biāo)約束的右端期望值相差不大，n可只取到1，如取Pk=10，取Pk+1=1.但是，由于各目標(biāo)期望值ei的單位不同，期望值ei之間可能相差懸殊，這種情況下為保證第k級目標(biāo)先于第k+1級目標(biāo)被滿足，n的取值就應(yīng)適當(dāng)放大.例如，例4-4的目標(biāo)規(guī)劃問題為其電子表格模型如圖13-28所示.圖中可變單元格C8：D8顯示的是決策變量的取值，輸出單元格E4表示約束條件的左端值，而單元格L4給出了第一個約束條件的右端值.在約束條件中后圖13-28圖13-28三個屬于目標(biāo)約束，E5：E7中的等式表示了在這些變量下，目標(biāo)約束中各目標(biāo)的實(shí)際值，可變單元格H5：I7表示的是各目標(biāo)實(shí)際值低于或超過期望目標(biāo)值的偏差值，L5：L7是各目標(biāo)約束右端的期望目標(biāo)值.第J列的公式表示目標(biāo)的實(shí)際值加未達(dá)到值再減超出值應(yīng)等于期望值.該問題的目標(biāo)分為三個優(yōu)先級來實(shí)現(xiàn)，單元格E10：E12中給出了優(yōu)先因子的取值，相鄰的兩個因子之間相差10倍，1.E+03是科學(xué)計數(shù)法，表示103.單元格G10：G12中的公式表示了各級的具體目標(biāo)是使哪個偏差值或哪些偏差值的組合達(dá)到最小.本例目標(biāo)函數(shù)中第一、二、三級目標(biāo)分別是使偏差值達(dá)到最小，因此在G10：G12中分別引用了可變單元格H5，I6和H7.目標(biāo)單元格J12=SUMPRODUCT（E10：E12，G10：G12）應(yīng)取最小值，并通過對優(yōu)先因子的控制保證目標(biāo)按優(yōu)先順序?qū)崿F(xiàn).該問題是一個線性規(guī)劃模型，所有的可變單元格數(shù)據(jù)都要求是非負(fù)的，這些可以通過“規(guī)劃求解”的選項對話框來實(shí)現(xiàn)，此外要滿足約束條件E4E6和J5：J7=L5：L7，但對輸出單元格E5：E7沒有限制，因為并不要求目標(biāo)約束中的實(shí)際值與期望值完全相等.按下“規(guī)劃求解”對話框的求解按鈕后，電子表格中顯示最優(yōu)解對應(yīng)的決策變量為，問題的三級目標(biāo)均得以實(shí)現(xiàn)，因此目標(biāo)函數(shù)值為0，但實(shí)際上，通過第四章對該問題用圖解法分析我們得知，其最優(yōu)解有無窮多個（其最優(yōu)解域為一個四邊形），但利用電子表格我們只能找到其中的一個最優(yōu)解.我們再來看例4-5，原問題的代數(shù)模型如下：該問題的電子表格模型及求解過程如圖13-29所示.圖圖13-29該問題的建模及求解過程，包括模型中所涉及的單元格公式的解釋與例3-4基本相同，但本模型中只有目標(biāo)約束而沒有普通約束.通過求解發(fā)現(xiàn)該問題的三級目標(biāo)中，只有第一級的目標(biāo)被實(shí)現(xiàn)，而其他兩級目標(biāo)均未實(shí)現(xiàn).當(dāng)決策變量的取值時，而取值最小為6.如果將目標(biāo)約束2的期望值由26降至14，再重新求解，則三級目標(biāo)均可實(shí)現(xiàn).此時問題的最優(yōu)解為，結(jié)果如圖13-30所示.圖圖13-30（五）目標(biāo)規(guī)劃問題Excel求解實(shí)驗?zāi)康?掌握在Excel中建立目標(biāo)規(guī)劃問題模型和求解的方法實(shí)驗內(nèi)容:求解課本P138（例2）的目標(biāo)規(guī)劃問題：實(shí)驗步驟第一步建模依次在相應(yīng)的單元格內(nèi)輸入數(shù)據(jù)和公式，建模如圖1注：權(quán)重的確定可根據(jù)需要自行定義，本題假定P1=100，P2=1，表明P1＞＞P2。圖1目標(biāo)規(guī)劃的Excel模型第二步設(shè)置規(guī)劃求解參數(shù)如圖2和圖3，其中，“選項”中選取“假定非負(fù)”和“采用線性模型”，其它采用默認(rèn)選項，如圖圖2規(guī)劃求解參數(shù)設(shè)置圖3選項設(shè)置第三步求解設(shè)置完畢后，單擊圖2中“求解”按鈕，出現(xiàn)如圖4規(guī)劃求解結(jié)果對話框圖4規(guī)劃求解結(jié)果對話框如圖4所示，共提供3類報告，選擇你想要的報告，單擊確定按鈕，完成運(yùn)算，最后計算結(jié)果如圖5圖5計算結(jié)果Ｅｘｃｅｌ在多目標(biāo)規(guī)劃求解和靈敏度分析中的應(yīng)用多目標(biāo)規(guī)劃被認(rèn)為是一種較之線性規(guī)劃更接近于實(shí)際決策過程的決策工具。多目標(biāo)規(guī)劃由線性規(guī)劃發(fā)展演變而來，因此，同線性規(guī)劃一樣，多目標(biāo)規(guī)劃在建立模型后也可以利用Ｅｘｃｅｌ中的［工具］［規(guī)劃求解］命令進(jìn)行求解。然而由于在建立多目標(biāo)規(guī)劃模型過程中引入了優(yōu)先級和權(quán)系數(shù)，使得利用Ｅｘｃｅｌ求解多目標(biāo)規(guī)劃模型比求解線性規(guī)劃更復(fù)雜，特別是用Ｅｘｃｅｌ求解多目標(biāo)規(guī)劃模型時輸出的敏感性報告沒有實(shí)際意義。因為各決策變量在目標(biāo)函數(shù)中的系數(shù)Ｐｌ僅是一種符號，表示優(yōu)先權(quán)等級，在用Ｅｘｃｅｌ求解時有兩種處理方法，一是將目標(biāo)函數(shù)表示為各偏差變量和的形式，然后根據(jù)實(shí)際需要賦予Ｐｌ具體的數(shù)字，但必須滿足Ｐｌ＞＞Ｐｌ＋１；二是將目標(biāo)規(guī)劃轉(zhuǎn)化為多步線性規(guī)劃問題來求解，Ｐｌ的值全部設(shè)為１。不論按哪種方法處理，Ｐｌ的值都是為計算方便而人為設(shè)定的，因此，用Ｅｘｃｅｌ求解的結(jié)果中分析Ｐｌ變化范圍的敏感性報告沒有實(shí)際的經(jīng)濟(jì)意義。另外，由于在各約束條件中引入了偏差變量，而目標(biāo)函數(shù)為求偏差變量的最小值，因此，用Ｅｘｃｅｌ求解的結(jié)果中分析ｂｉ變化范圍的敏感性報告也沒有實(shí)際的經(jīng)濟(jì)意義。但在現(xiàn)實(shí)中，靈敏度分析又十分重要，因為它可以回答管理者諸多“假如…，那么…”式的問題，以幫助管理者甄別多個決策方案。有關(guān)如何運(yùn)用Ｅｘｃｅｌ求解多目標(biāo)規(guī)劃問題已經(jīng)有不少文獻(xiàn)資料，無需贅述；本文的重點(diǎn)是探討如何利用Ｅｘｃｅｌ對多目標(biāo)規(guī)劃問題進(jìn)行靈敏度分析。筆者嘗試著運(yùn)用Ｅｘｃｅｌ中的菜單［工具］［方案］命令，輕松實(shí)現(xiàn)多目標(biāo)規(guī)劃問題的靈敏度分析。一、多目標(biāo)模型多目標(biāo)模型的數(shù)學(xué)模型的一般形式如下：二、應(yīng)用實(shí)例某化工廠生產(chǎn)兩種用于輪船上的黏合劑Ａ和Ｂ。這兩種黏合劑的強(qiáng)度不同，所需的加工時間也不同，生產(chǎn)１升的Ａ需要２０分鐘，生產(chǎn)１升的Ｂ需要２５分鐘。這兩種黏合劑都以一種樹脂作為原料，１升樹脂可以制造１升Ａ，或者１升Ｂ。樹脂的保質(zhì)期是２周，目前樹脂的庫存為３００升。已經(jīng)正常工作下每周有５個工作日，每個工作日有８個工時，工廠期望在未來兩周達(dá)到以下目標(biāo)：目標(biāo)１：保持工廠滿負(fù)荷運(yùn)轉(zhuǎn)；目標(biāo)２：加班時間控制在２０工時以內(nèi)；目標(biāo)３：至少生產(chǎn)１００升Ａ；目標(biāo)４：至少生產(chǎn)１２０升Ｂ；目標(biāo)５：使用完所有的樹脂。假設(shè)目標(biāo)１和目標(biāo)２的優(yōu)先權(quán)為Ｐ１，且重要程度相等；目標(biāo)３和目標(biāo)４的優(yōu)先權(quán)為Ｐ２，且重要程度相等；目標(biāo)５的優(yōu)先權(quán)為Ｐ３，建立目標(biāo)規(guī)劃模型并求解。如果設(shè)在未來兩周Ａ、Ｂ兩種黏合劑的生產(chǎn)數(shù)量分別為ｘ１和ｘ２，則對上述問題我們可以建立如下目標(biāo)規(guī)劃模型：為了便于用Ｅｘｃｅl中的［工具］［規(guī)劃求解］對上面的目標(biāo)規(guī)劃問題求解，我們采用了第