運(yùn)籌學(xué)（第2版）課件 第一章 線性規(guī)劃

南京航空航天大學(xué)經(jīng)濟(jì)與管理學(xué)院運(yùn)籌學(xué)第一章線性規(guī)劃引子線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，它也是現(xiàn)代科學(xué)管理的重要手段之一，它可以幫助管理者做出科學(xué)決策的一個(gè)有效的方法，在許多領(lǐng)域都有成功的應(yīng)用案例。如生產(chǎn)計(jì)劃安排問(wèn)題，對(duì)于在計(jì)劃期內(nèi)安排生產(chǎn)多種產(chǎn)品生產(chǎn)，生產(chǎn)不同單位產(chǎn)品所需所需原材料及設(shè)備工時(shí)不同，同時(shí)不同產(chǎn)品的單位產(chǎn)品利潤(rùn)也不同，管理者如何安排各種產(chǎn)品的產(chǎn)量，使得在資源有限的情況下公司獲得最大利潤(rùn)？再如投資問(wèn)題，如何從不同的投資項(xiàng)目中選出一個(gè)投資方案使得投資的回報(bào)為最大？這些問(wèn)題都可以利用線性規(guī)劃方法進(jìn)行解決。1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型運(yùn)籌學(xué)是研究在給定的約束條件下，求所考察的目標(biāo)函數(shù)在某種意義下的極值問(wèn)題。自1947年美國(guó)數(shù)學(xué)家丹捷格（G.B.Dantzig）提出了求解線性規(guī)劃問(wèn)題的方法——單純形法之后，線性規(guī)劃在理論上趨于成熟，在實(shí)際中的應(yīng)用日益廣泛與深入。特別是在能用計(jì)算機(jī)來(lái)處理成千上萬(wàn)個(gè)約束條件和變量的大規(guī)模線性規(guī)劃問(wèn)題之后，它的適用領(lǐng)域更加廣泛。從解決技術(shù)問(wèn)題中的最優(yōu)化設(shè)計(jì)到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)、軍事、經(jīng)濟(jì)計(jì)劃與管理、決策等各個(gè)領(lǐng)域均可發(fā)揮重要作用；從范圍來(lái)看，小到一個(gè)小組的日常工作和計(jì)劃安排，大至整個(gè)部門(mén)以致國(guó)民經(jīng)濟(jì)計(jì)劃的最優(yōu)方案的提出，都有用武之地。它具有適應(yīng)性強(qiáng)、應(yīng)用廣泛、計(jì)算技術(shù)比較簡(jiǎn)單的特點(diǎn)，是現(xiàn)代管理科學(xué)的重要基礎(chǔ)和手段之一。1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型線性規(guī)劃發(fā)展簡(jiǎn)史：1939年：蘇聯(lián)數(shù)學(xué)家康托羅維奇（L.Kantorovich）出版《生產(chǎn)組織和計(jì)劃中的數(shù)學(xué)方法》一書(shū)。1947年：丹齊格提出了線性規(guī)劃問(wèn)題的單純形求解方法。1951年：美國(guó)經(jīng)濟(jì)學(xué)家?guī)炱章梗═.C.Koopmans）出版《生產(chǎn)與配置的活動(dòng)分析》一書(shū)。1950-1956年：線性規(guī)劃的對(duì)偶理論出現(xiàn)。1960年：丹齊格與沃爾夫（P.Wolfe）建立大規(guī)模線性規(guī)劃問(wèn)題的分解算法。1975年：康托羅維奇（L.Kantorovich）與庫(kù)普曼斯（T.C.Koopmans）因“最優(yōu)資源配置理論的貢獻(xiàn)”榮獲諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。1978年：蘇聯(lián)數(shù)學(xué)家哈奇揚(yáng)（L.G.Khachian）提出求解線性規(guī)劃問(wèn)題的多項(xiàng)式時(shí)間算法（內(nèi)點(diǎn)算法），具有重要理論意義。1984年：在美國(guó)貝爾實(shí)驗(yàn)室工作的印度裔數(shù)學(xué)家卡瑪卡（N.Karmarkar）提出可以有效求解實(shí)際線性規(guī)劃問(wèn)題的多項(xiàng)式時(shí)間算法——Karmarkar算法?，F(xiàn)已形成線性規(guī)劃多項(xiàng)式算法理論。1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型丹齊格的傳奇一生：1914年11月8日：生于美國(guó)俄勒岡州波特蘭市。1937-1939年：任美國(guó)勞工統(tǒng)計(jì)局統(tǒng)計(jì)員。二戰(zhàn)期間：擔(dān)任美國(guó)空軍總部統(tǒng)計(jì)控制的戰(zhàn)斗分析處主任，處理供應(yīng)鏈的補(bǔ)給和管理成千上萬(wàn)的人員和物資，工作使他開(kāi)始關(guān)注真實(shí)世界的問(wèn)題，就是線性規(guī)劃將要解決的問(wèn)題。1941～1952年：任美國(guó)空軍司令部數(shù)學(xué)顧問(wèn)、戰(zhàn)斗分析部和統(tǒng)計(jì)管理部主任。1946年：在伯克利加利福尼亞大學(xué)數(shù)學(xué)系獲哲學(xué)博士學(xué)位。在此之前已在馬里蘭大學(xué)獲數(shù)學(xué)和物理學(xué)學(xué)士學(xué)位，在密歇根大學(xué)獲數(shù)學(xué)碩士學(xué)位。1947年：在總結(jié)前人工作的基礎(chǔ)上創(chuàng)立了線性規(guī)劃,確定了這一學(xué)科的范圍,并提出了解決線性規(guī)劃問(wèn)題的單純形法。1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型丹齊格的傳奇一生：1952～1960年：加入蘭德公司的數(shù)學(xué)分部，任美國(guó)蘭德公司數(shù)學(xué)研究員。1960～1966年：回到加州大學(xué)克萊分校的工業(yè)工程學(xué)系擔(dān)任教授、運(yùn)籌學(xué)中心主任。1963年：出版專(zhuān)著《Linearprogrammingandextensions》，這本著作至今仍是線性規(guī)劃方面的標(biāo)準(zhǔn)參考書(shū)。1966年后：任斯坦福大學(xué)運(yùn)籌學(xué)和計(jì)算機(jī)科學(xué)教授。1990年：退休。

2005年5月13日：因糖尿病和心血管疾病的并發(fā)癥，在加利福尼亞州逝世。1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型丹齊格的趣聞?shì)W事：據(jù)說(shuō)，一次耶日·內(nèi)曼（J.Neyman）教授的課，丹齊格遲到了，仰頭看去，黑板上留了兩個(gè)題目，他就抄了一下，回家后埋頭苦做。在幾個(gè)星期之后，他疲憊的去找老師說(shuō)，這件事情真的對(duì)不起，作業(yè)太難了，所以我現(xiàn)在才交，言下很是慚愧。大約六周之后，內(nèi)曼跑去他的寢室找他，興奮之情溢于言表。丹齊格不知道發(fā)生什么事，后來(lái)才知道原來(lái)黑板上的題目根本就不是什么家庭作業(yè)，而是老師說(shuō)的本領(lǐng)域未解決的問(wèn)題，丹齊格給出的那個(gè)解法也就是單純形法，據(jù)說(shuō)這個(gè)方法是上個(gè)世紀(jì)前十位的算法。這個(gè)故事被不斷流傳，在電影《心靈捕手》中清潔工威爾隨意解答了數(shù)學(xué)系藍(lán)勃教授留下的數(shù)學(xué)難題的故事就是來(lái)源于丹齊格的經(jīng)歷。最后在內(nèi)曼協(xié)助下，第一道難題的答案在1940年發(fā)表。一年后，丹齊格為未想到博士論文題目感到擔(dān)憂，內(nèi)曼知道后告訴他，只要把兩條問(wèn)題的解答合起來(lái)，就會(huì)被接納作為其博士論文。他第二道“習(xí)題”的答案沒(méi)有立即發(fā)表在期刊上，直到1950年，著名數(shù)學(xué)家亞伯拉罕·瓦爾德（A.Wald)打算把新發(fā)現(xiàn)投稿到期刊，卻被告知結(jié)果跟丹齊格的發(fā)現(xiàn)類(lèi)似，于是，寫(xiě)信給丹齊格，雙方同意下論文聯(lián)名發(fā)表。1.1.1線性規(guī)劃問(wèn)題的數(shù)學(xué)模型在生產(chǎn)管理和經(jīng)濟(jì)活動(dòng)中，經(jīng)常會(huì)遇到線性規(guī)劃問(wèn)題，如何利用線性規(guī)劃的方法來(lái)進(jìn)行分析，下面舉例來(lái)加以說(shuō)明。例1.1（生產(chǎn)計(jì)劃問(wèn)題）某公司在計(jì)劃期內(nèi)安排生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)產(chǎn)品甲需原材料B，生產(chǎn)產(chǎn)品乙需原材料A，生產(chǎn)單位產(chǎn)品甲、乙所需原材料及設(shè)備工時(shí)和甲、乙兩種產(chǎn)品的單位產(chǎn)品利潤(rùn)等數(shù)據(jù)如表1.1所示；由于兩種產(chǎn)品生產(chǎn)都在一個(gè)設(shè)備上生產(chǎn)，且設(shè)備工時(shí)有限，公司管理者如何安排這兩種產(chǎn)品的生產(chǎn)量，使得在資源有限的情況下公司獲得最大利潤(rùn)。表1.1生產(chǎn)單位產(chǎn)品消耗原材料及占用設(shè)備工時(shí)甲乙資源限制原材料A(噸)0315原材料B(噸)4012設(shè)備(單位設(shè)備工時(shí))2214單位產(chǎn)品利潤(rùn)（萬(wàn)元）23現(xiàn)在我們需要確定這兩種產(chǎn)品的產(chǎn)量，使公司獲得最大利潤(rùn)。因此需要引入變量如下：設(shè)生產(chǎn)產(chǎn)品A和生產(chǎn)產(chǎn)品B的產(chǎn)量用變量x1、x2來(lái)表示，則稱(chēng)x1、x2為決策變量。若用Z表示該公司的利潤(rùn)，則該公司的利潤(rùn)值Z=2x1+3x2（萬(wàn)元）因?yàn)樵谟?jì)劃期內(nèi)原材料A有15噸可利用，所以在確定產(chǎn)品甲、乙的產(chǎn)量時(shí)，可用不等式表示為：同理，因在計(jì)劃期內(nèi)原材料B的限制，有不等式：設(shè)備工時(shí)的限制，有不等式：此外甲、乙兩種產(chǎn)品的產(chǎn)量不可能為負(fù)值，因此有對(duì)變量的非負(fù)約束：目標(biāo)函數(shù)MaxZ=2x1+3x2約束條件例1.2(成本問(wèn)題)某煉油廠每季度需供應(yīng)給合同單位汽油15萬(wàn)噸、煤油12萬(wàn)噸、重油12萬(wàn)噸。該廠計(jì)劃從A，B兩處運(yùn)回原油提煉，已知兩處的原油成分含量見(jiàn)表1.2；又已知從A處采購(gòu)的原油價(jià)格為每噸（包括運(yùn)費(fèi)）200元，B處采購(gòu)的原油價(jià)格為每噸（包括運(yùn)費(fèi)）290元,問(wèn)：該煉油廠該如何從A，B兩處采購(gòu)原油，在滿足供應(yīng)合同的條件下，使購(gòu)買(mǎi)成本最小。表1.2A、B兩處的原油成分含量

產(chǎn)品來(lái)源成分AB汽油15%50%煤油20%30%重油50%15%其它15%5%分析：很明顯，該廠可以有多種不同的方案從A，B兩處采購(gòu)原油，但最優(yōu)方案應(yīng)是使購(gòu)買(mǎi)成本最小的一個(gè)，即在滿足供應(yīng)合同單位的前提下，使成本最小的一個(gè)采購(gòu)方案。解設(shè)分別表示從A，B兩處采購(gòu)的原油量（單位：萬(wàn)噸），則所有的采購(gòu)方案均應(yīng)同時(shí)滿足采購(gòu)成本為的函數(shù)，即（萬(wàn)元）。而最終目標(biāo)是求滿足約束條件和使采購(gòu)成本最小時(shí)的解。由此，建立的數(shù)學(xué)模型為例1.3（人力資源分配問(wèn)題）某晝夜服務(wù)的公交公司的公交線路每天各時(shí)段內(nèi)所需司機(jī)人員如表1.3所示：表1.3各時(shí)段內(nèi)所需司機(jī)人員設(shè)司機(jī)人員分別在各時(shí)間段開(kāi)始時(shí)上班，并連續(xù)工作8小時(shí)。問(wèn)題：該公司公交各時(shí)段應(yīng)如何安排司機(jī)，既能滿足工作需要，又使配備司機(jī)人員的人數(shù)最少？班次時(shí)間所需人數(shù)16:00－10:0060210:00－14:0070314:00－18:0060418:00－22:0050522:00－2:002062:00－6:0030解：設(shè)表示第i班次開(kāi)始上班的司機(jī)人員人數(shù)，這樣可以知道在第i班工作的人數(shù)應(yīng)包括第i-1班次開(kāi)始上班的人數(shù)和第i班次開(kāi)始上班的人數(shù)，如，又要求這六個(gè)班次開(kāi)始上班的人數(shù)總和最少，即可以建立如下的數(shù)學(xué)模型：例1.4（連續(xù)投資問(wèn)題）某公司在今后5年內(nèi)考慮給下列項(xiàng)目投資，已知：項(xiàng)目A：從第一年到第四年每年年初需要投資，并于次年末回收本利115%；項(xiàng)目B：第三年年初需要投資，到第五年年末能回收本利125%，但規(guī)定最大投資額不超過(guò)4億元；項(xiàng)目C：第二年年初需要投資，到第五年年末能回收本利140%，但規(guī)定最大投資額不超過(guò)3億元；項(xiàng)目D：五年內(nèi)每年年初可購(gòu)買(mǎi)公債，于當(dāng)年年末歸還，并加利息6%。已知該公司現(xiàn)有資金10億元，問(wèn)它應(yīng)如何確定給這些項(xiàng)目每年的投資額，使到第五年年末擁有資金的本利總額為最大？解：(1)確定變量：這是一個(gè)連續(xù)投資問(wèn)題，與時(shí)間有關(guān)。但這里設(shè)法用線性規(guī)劃方法靜態(tài)地處理。設(shè)：xiA：表示第i

年年初給項(xiàng)目A的投資額（萬(wàn)元）i=1,···,5；xiB

：表示第i

年年初給項(xiàng)目B的投資額（萬(wàn)元）i=1,···,5；xiC：表示第i

年年初給項(xiàng)目C的投資額（萬(wàn)元）i=1,···,5；xiD：表示第i

年年初給項(xiàng)目D的投資額（萬(wàn)元）i=1,···,5；它們都是待定的未知變量。(2)投資額應(yīng)等于手中擁有的資金額。由于項(xiàng)目D每年都可以投資，并且當(dāng)年末即可收回本息，所以該部門(mén)每年應(yīng)把資金全部投出，手中不應(yīng)當(dāng)有剩余的呆滯資金。因此有：(3)目標(biāo)函數(shù)：目標(biāo)要求是在第五年年末該部門(mén)手中擁有的資金額達(dá)到最大。這個(gè)目標(biāo)函數(shù)可表示為：MaxZ=1.15x4A+1.25x3B+1.40x2C+1.06x5D(4)數(shù)學(xué)模型：MaxZ=1.15x4A+1.25x3B+1.40x2C+1.06x5D從以上幾個(gè)例子的數(shù)學(xué)模型可以看出，該類(lèi)數(shù)學(xué)模型具有如下特點(diǎn)：

(1)有一組非負(fù)的決策變量(decisionorcontrolvariable)，這組決策變量的值都代表一個(gè)具體方案；

(2)有一組約束條件：含有決策變量的線性不等式(或等式)組(linearfunctionconstraints)；

(3)有一個(gè)含有決策變量的線性目標(biāo)函數(shù)(objectivelinearfunction)，按研究問(wèn)題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。我們把滿足上述三個(gè)條件的數(shù)學(xué)模型稱(chēng)為線性規(guī)劃數(shù)學(xué)模型。如果目標(biāo)函數(shù)是決策變量的非線性函數(shù)，或約束條件含有決策變量的非線性不等式(或等式)，我們稱(chēng)這類(lèi)數(shù)學(xué)模型為非線性規(guī)劃數(shù)學(xué)模型。線性規(guī)劃數(shù)學(xué)模型的一般形式如下：在該數(shù)學(xué)模型中，方程(1.1)稱(chēng)為目標(biāo)函數(shù)；(1.2)稱(chēng)為約束條件；(1.3)稱(chēng)為變量的非負(fù)約束條件。1.1.2線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型由前面所舉的例子可知，線性規(guī)劃問(wèn)題可能有各種不同的形式。目標(biāo)函數(shù)根據(jù)實(shí)際問(wèn)題的要求可能是求最大化，也有可能求最小化；約束條件可以是“”形式、“”形式的不等式，也可以是等式的形式。決策變量有時(shí)有非負(fù)限制，有時(shí)沒(méi)有非負(fù)限制。這種多樣性給討論問(wèn)題帶來(lái)了不便。為了便于討論，我們規(guī)定線性規(guī)劃問(wèn)題描述為如下的標(biāo)準(zhǔn)形式：這里假設(shè)bi0(i=1,2,···,m)。以上模型的簡(jiǎn)寫(xiě)形式為用向量形式表達(dá)時(shí)，上述模型可以寫(xiě)為：用矩陣形式表達(dá)時(shí)，上述模型可以寫(xiě)為：其中：C=(c1,c2,···,cn)，X=(x1,x2,···,xn)T

，b=(b1,b2,···,bm)T,

，A=(P1,P2,···,Pn)，0=(0,0,···,0)T

，j=1,2,···,n

。我們稱(chēng)A為約束方程組的系數(shù)矩陣(m×n階)，一般情況下m<n,m,n

為正整數(shù)，分別表示約束條件的個(gè)數(shù)和決策變量的個(gè)數(shù)，C

為價(jià)值向量，X

為決策向量，通常aij

,bi,cj(i=1,2,···,m

，j=1,2,···,n)為已知常數(shù)。實(shí)際上，具體問(wèn)題的線性規(guī)劃數(shù)學(xué)模型是各式各樣的，需要把它們化成標(biāo)準(zhǔn)型，并借助于標(biāo)準(zhǔn)型的求解方法進(jìn)行求解。以下就具體討論如何把一般的線性規(guī)劃模型化成標(biāo)準(zhǔn)型。（1）目標(biāo)函數(shù)的轉(zhuǎn)化若原問(wèn)題的目標(biāo)函數(shù)是求最小化，即：minZ=CX這時(shí)只需要將目標(biāo)函數(shù)的最小值變換為求目標(biāo)函數(shù)的最大值，即。令，就是將目標(biāo)函數(shù)乘以（-1）后轉(zhuǎn)化為如下最大化問(wèn)題：

Max（2）不等式約束轉(zhuǎn)化為等式約束不等式約束有兩種情況：一是約束條件為“”形式的不等式，則在“”號(hào)的左邊加入非負(fù)的松弛變量，把原“”形式的不等式轉(zhuǎn)化為等式；另一種是約束條件為“”形式的不等式，則可在“”號(hào)的左邊減去一個(gè)非負(fù)的剩余變量，把原“”形式的不等式轉(zhuǎn)化為等式。同時(shí)相應(yīng)的松弛變量或剩余變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)取值為0。（3）變量約束的轉(zhuǎn)換若原線性規(guī)劃問(wèn)題中某個(gè)變量無(wú)非負(fù)要求的變量。即有某一個(gè)變量xj

取正值或負(fù)值都可以。這時(shí)為了滿足標(biāo)準(zhǔn)型對(duì)變量的非負(fù)要求，可令,其中：0，將其代入原問(wèn)題，即在原問(wèn)題中將xj用兩個(gè)非負(fù)變量之差代替。上述的標(biāo)準(zhǔn)型具有如下特點(diǎn)：（1）目標(biāo)函數(shù)求最大值；（2）所求的決策變量都要求是非負(fù)的；（3）所有的約束條件都是等式；（4）常數(shù)項(xiàng)為非負(fù)。綜合以上的討論，我們可以把任意形式的線性規(guī)劃問(wèn)題通過(guò)上述手段化成標(biāo)準(zhǔn)型的線性規(guī)劃問(wèn)題?，F(xiàn)舉例如下：例1.6

將例1.1的線性規(guī)劃數(shù)學(xué)模型化為標(biāo)準(zhǔn)型。解：引進(jìn)3個(gè)新的非負(fù)變量x3，x4，x5使不等式變?yōu)榈仁剑瑯?biāo)準(zhǔn)型為：

解：由于x3無(wú)限制，因此令x3=x4–x5,x4,x5

≥0,第1個(gè)約束不等式左端加上非負(fù)松弛變量x6,第2個(gè)約束不等式左端減去非負(fù)剩余變量x7,目標(biāo)函數(shù)由于求最小化，因此令，同時(shí)將目標(biāo)函數(shù)及約束條件中的x3換為x3=x4-x5，則可將上述線性規(guī)劃問(wèn)題化成如下的標(biāo)準(zhǔn)型:例1.7

試將如下線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)型1.2線性規(guī)劃問(wèn)題的圖解法及幾何意義1.2.1線性規(guī)劃問(wèn)題解的概念在討論線性規(guī)劃問(wèn)題的求解之前，要先了解線性規(guī)劃問(wèn)題解的概念。由前面討論可知線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型為(1.8)、(1.9)、(1.10)式所示：（1）可行解:滿足約束條件(1.9)，(1.10)的解X=(x1,x2,···,xn)T稱(chēng)為線性規(guī)劃問(wèn)題的可行解；所有可行解的集合稱(chēng)為可行解集或可行域。（2）最優(yōu)解:

滿足約束條件及目標(biāo)函數(shù)(1.8)的可行解稱(chēng)為線性規(guī)劃問(wèn)題的最優(yōu)解。（3）基假設(shè)A是約束方程組的階系數(shù)矩陣，其秩數(shù)為m

，B是矩陣A中由m

列構(gòu)成的非奇異子矩陣(B的行列式值不為0)，則稱(chēng)B是線性規(guī)劃問(wèn)題的一個(gè)基。這就是說(shuō)，矩陣B是由m

個(gè)線性無(wú)關(guān)的列向量組成。在例1.1中我們得到該問(wèn)題的數(shù)學(xué)模型MaxZ=2x1+3x2約束條件其標(biāo)準(zhǔn)型為該問(wèn)題有3個(gè)約束方程，它的系數(shù)矩陣為其中為系數(shù)矩陣A中第j列的列向量，在A中存在一個(gè)不為零的3階子式，在此例中與都是該線性規(guī)劃的一個(gè)基。（4）基向量與非基向量基B中的一列稱(chēng)為一個(gè)基向量?；鵅中共有m個(gè)基向量，在此例中，對(duì)于基

它的每一列向量都是基B的基向量。在A中除了基B之外的任意一列都稱(chēng)為非基向量。在此例中對(duì)與來(lái)說(shuō)，向量(3，0，2)T是基的基向量，同時(shí)還是基的非基向量。（5）基變量與非基變量與基向量對(duì)應(yīng)的變量稱(chēng)為基變量，基變量有m個(gè)，在此例中，都是的基變量，是的基變量。與非基向量對(duì)應(yīng)的變量稱(chēng)為非基變量，非基變量有n-m個(gè)，在此例中，是的非基變量，是的非基變量。（6）基本解與基本可行解由線性代數(shù)的知識(shí)知道，如果在約束方程組系數(shù)矩陣中找到一個(gè)基，令非基變量為零，這時(shí)線性方程組可以得到唯一解，這個(gè)解稱(chēng)為線性規(guī)劃的基本解。在此例中，是一個(gè)基，令這個(gè)基的非基變量，這時(shí)求得基變量的唯一解

這樣就求得一個(gè)基本解。由于基本解不能保證所有分量都大于等于零，也就是說(shuō)基本解不一定是可行解。若滿足非負(fù)條件的基本解稱(chēng)為基本可行解。上面得到的基本解就是基本可行解。此時(shí)對(duì)應(yīng)的基稱(chēng)為可行基。一般說(shuō)來(lái)，判斷一個(gè)基是否為可行基，只有在求出基本解以后，當(dāng)其基本解所有變量都大于等于零時(shí)，才能判定這個(gè)解是基本可行解，這個(gè)基是可行基。1.2.2線性規(guī)劃問(wèn)題的圖解法

對(duì)于簡(jiǎn)單的線性規(guī)劃問(wèn)題(只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題)，我們可以通過(guò)圖解法對(duì)它進(jìn)行求解。圖解法簡(jiǎn)單直觀，有助于幫助我們理解線性規(guī)劃問(wèn)題的基本原理。我們以例1.1為例，介紹具體的圖解法求解線性規(guī)劃的方法。

例1.8

用圖解法求解線性規(guī)劃問(wèn)題

maxZ=2x1+3x2解：對(duì)于上述只有兩個(gè)變量的線性規(guī)劃問(wèn)題，以x1和x2為坐標(biāo)軸建立直角坐標(biāo)系。從圖1.1中可知，同時(shí)滿足約束條件的點(diǎn)必然落在由兩個(gè)坐標(biāo)軸與三條直線所圍成的多邊形OABCD的區(qū)域內(nèi)或該多邊形的邊界上，該多邊形區(qū)域內(nèi)及邊界上的點(diǎn)就是滿足約束條件的解的集合，就是該線性規(guī)劃的可行域；畫(huà)兩條目標(biāo)函數(shù)Z=2x1+3x2的等值線，找出其遞增的方向，用虛線表示，用箭頭表示目標(biāo)函數(shù)值遞增的方向。沿箭頭方向移動(dòng)目標(biāo)函數(shù)的等值線，平移等值線直至與可行域OABCD相切或融合為一條直線，此時(shí)就得到最優(yōu)解為B點(diǎn)，其坐標(biāo)可通過(guò)解方程組得到：

圖1.1例1.8的可行域x2A52x1+3x2=0CBDO3x2=152x1+2x2=144x1=12x1求解方程組解得：點(diǎn)（2，5）就是該線性規(guī)劃問(wèn)題的最優(yōu)解。此時(shí)相應(yīng)的目標(biāo)函數(shù)的最大值為：

Z=2×2+3×5=19例1.9

用圖解法求解線性規(guī)劃問(wèn)題

maxZ=40x1+80x2解：以x1和x2為坐標(biāo)軸建立直角坐標(biāo)系。從圖1.2中可知，同時(shí)滿足約束條件的點(diǎn)必然落在多邊形OABCD的區(qū)域內(nèi)或該多邊形的邊界上；虛線為目標(biāo)函數(shù)Z=40x1+80x2的等值線，箭頭方向?yàn)槟繕?biāo)函數(shù)值遞增的方向。沿箭頭方向移動(dòng)目標(biāo)函數(shù)的等值線，平移等值線直至與可行域OABCD相切或融合為一條直線，此時(shí)就得到最優(yōu)解為B、C兩點(diǎn)，即最優(yōu)解為BC線段上任一點(diǎn)，其B、C兩點(diǎn)坐標(biāo)可分別通過(guò)解方程組得到：B點(diǎn)為X(1)=(6,12)；

C點(diǎn)為X(2)=(15,7.5)。3x1+2x2=60D20x22x2＝24x1+2x2=30oCBA12x1圖1.2例1.9的可行域例1.10

用圖解法求解線性規(guī)劃問(wèn)題

maxZ=2x1+4x2

圖1.3例1.10的可行域解：以x1和x2為坐標(biāo)軸建立直角坐標(biāo)系。由于該線性規(guī)劃的可行域是無(wú)界的，作目標(biāo)函數(shù)等值線，如圖1.3中虛線所示，并用箭頭標(biāo)出其函數(shù)值增加的方向，由此可以看出，該問(wèn)題無(wú)有限最優(yōu)解。若目標(biāo)函數(shù)由maxZ=2x1+4x2

改為minZ=2x1+4x2,雖然可行域是無(wú)界的，但該線性規(guī)劃問(wèn)題有最優(yōu)解x1=4，x2=0，即B(4,0)點(diǎn)。84BA0x1x2-2x1+x2＝22x1+x2＝8Z＝0圖解法求解只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題具體步驟如下：（1）以x1和x2為坐標(biāo)軸建立直角坐標(biāo)系。找出所有約束條件都同時(shí)滿足區(qū)域，即可行域。（2）給定目標(biāo)函數(shù)一個(gè)特定的值，畫(huà)出目標(biāo)函數(shù)等值線，對(duì)于目標(biāo)函數(shù)最大化問(wèn)題，找出目標(biāo)函數(shù)等值線增加的方向，沿目標(biāo)函數(shù)值遞增的方向平移等值線直至與可行域相切或融合為一條直線，此時(shí)交點(diǎn)就是所求的最優(yōu)解，交點(diǎn)坐標(biāo)由聯(lián)立方程組求得。通過(guò)以上各題圖解法可以得出：（1）線性規(guī)劃的所有可行解構(gòu)成的可行域一般是凸多邊形，有些可行域可能是無(wú)界的；（2）若存在最優(yōu)解，則一定在可行域的某頂點(diǎn)得到；（3）若在兩個(gè)頂點(diǎn)上同時(shí)得到最優(yōu)解，則在這兩點(diǎn)的連線內(nèi)的任一點(diǎn)都是最優(yōu)解。（4）若可行域無(wú)界，則可能發(fā)生最優(yōu)解無(wú)界的情況；（5）若可行域是空集，此時(shí)無(wú)最優(yōu)解。

圖解法雖然具有直觀、簡(jiǎn)便等優(yōu)點(diǎn)，但在變量多的情況下，即在多維的情況下，它就無(wú)能為力了。因此，需要介紹一種代數(shù)方法——單純形法。在沒(méi)有介紹單純形算法之前，先介紹線性規(guī)劃的基本定理。1.2.3線性規(guī)劃的基本定理定義1.1假設(shè)K是n維歐氏空間的一個(gè)點(diǎn)集，若對(duì)于K中的任意兩點(diǎn)X1、X2，其連線內(nèi)的所有點(diǎn)都在集合K中，即，則稱(chēng)K為凸集。從直觀上講，凸集無(wú)凹入部分，其內(nèi)部沒(méi)有洞。如實(shí)心圓、實(shí)心球、實(shí)心立方體等都是凸集。兩個(gè)凸集的交集仍是凸集，但兩個(gè)凸集的并集不一定是凸集。定義1.2

設(shè)X1，X2，···，Xk是n維歐氏空間En中的k個(gè)點(diǎn)，若存在且使則稱(chēng)X為由點(diǎn)X1，X2，···，Xk所構(gòu)成的凸組合。按照定義，凡是由x，y的凸組合表示的點(diǎn)都在x，y的連線內(nèi)，反之亦然。定義1.3

假設(shè)K是凸集，X

∈K；X若不能用K中不同的兩個(gè)點(diǎn)X1、X2∈K的線性組合表示為

則稱(chēng)X為凸集K的一個(gè)頂點(diǎn)（或稱(chēng)為極點(diǎn)）。頂點(diǎn)不位于凸集K中的任意不同兩點(diǎn)的連線內(nèi)。定理1.1

若線性規(guī)劃問(wèn)題存在可行域D，則其可行域

D={X|AX=b,X≥0}是凸集。定理1.2

線性規(guī)劃問(wèn)題的基本可行解X對(duì)應(yīng)于可行域D的頂點(diǎn)。定理1.3

若可行域有界，則線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)一定可以在其可行域的某個(gè)頂點(diǎn)上達(dá)到最優(yōu)解。即一定存在一個(gè)基本可行解是最優(yōu)解。定理1.4

若線性規(guī)劃問(wèn)題在k個(gè)頂點(diǎn)上達(dá)到最優(yōu)解（k≥2），則在這些頂點(diǎn)的凸組合上也達(dá)到最優(yōu)解。

根據(jù)以上討論可以得到如下的結(jié)論：(1)線性規(guī)劃問(wèn)題的所有可行解的集合是凸集，它可以是有界的區(qū)域，也可以是無(wú)界的區(qū)域；但僅有有限個(gè)頂點(diǎn)。(2)線性規(guī)劃問(wèn)題的每一個(gè)基本可行解對(duì)應(yīng)于可行域的一個(gè)頂點(diǎn)。若線性規(guī)劃問(wèn)題有最優(yōu)解，必定在可行域某頂點(diǎn)處取得。(3)如果一個(gè)線性規(guī)劃問(wèn)題存在多個(gè)最優(yōu)解，那么至少有兩個(gè)相鄰的頂點(diǎn)處是線性規(guī)劃的最優(yōu)解。(4)如果可行域?yàn)闊o(wú)界，則線性規(guī)劃問(wèn)題可能無(wú)最優(yōu)解，也可能有最優(yōu)解；若有最優(yōu)解，必定在可行域的某頂點(diǎn)處取得。雖然可行域的頂點(diǎn)個(gè)數(shù)是有限的(它不超過(guò)個(gè))，采用“枚舉法”可以找出所有基本可行解，然后一一比較它們的目標(biāo)函數(shù)值的大小，最終可以找到最優(yōu)解。但當(dāng)m、n的數(shù)目很大時(shí)，這種辦法實(shí)際上是行不通的。因此，我們需要討論一種方法，通過(guò)逐步迭代保證能逐步改進(jìn)并最終求出最優(yōu)解。

1.3線性規(guī)劃問(wèn)題的單純形算法

單純形算法的基本思路是：根據(jù)線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型，從可行域中某個(gè)基本可行解（頂點(diǎn)）開(kāi)始，判斷此基本可行解是否是最優(yōu)解，如果不是則再找另一個(gè)基本可行解（頂點(diǎn)）使得其目標(biāo)函數(shù)值更優(yōu)的基本可行解（頂點(diǎn)），稱(chēng)之為迭代，再判斷此基本可行解是否為最優(yōu)解，直到找到一個(gè)基本可行解為其最優(yōu)解，或者判斷該線性規(guī)劃問(wèn)題無(wú)最優(yōu)解為止。下面我們通過(guò)例1.1的求解來(lái)介紹單純形算法的具體求解過(guò)程。1.3.1確定初始基可行解

對(duì)于給出的線性規(guī)劃模型，如何找到可行域的一個(gè)頂點(diǎn)？這時(shí)可行域的頂點(diǎn)已不再像圖解法中那樣直接可以得到。在單純形法中找到的第一個(gè)可行域的頂點(diǎn)稱(chēng)為初始基本可行解。我們?nèi)绾卧谇蠼饩€性規(guī)劃之前就能找到一個(gè)基本可行解呢？由于線性規(guī)劃模型的標(biāo)準(zhǔn)型中要求常數(shù)項(xiàng)都大于等于零，如果我們能找到一個(gè)基，這個(gè)基是單位矩陣，或者說(shuō)一個(gè)基是由單位矩陣的各列向量所組成（各列向量的前后順序無(wú)關(guān)緊要），這時(shí)這個(gè)單位矩陣或由單位矩陣的各列向量所組成的基一定是可行基。實(shí)際上這個(gè)基本可行解中的各個(gè)變量或等于某個(gè)或等于零。如在例1.1中我們得到該問(wèn)題的數(shù)學(xué)模型標(biāo)準(zhǔn)型為

它的系數(shù)矩陣為其中為系數(shù)矩陣A中第j

列的列向量，在該例中我們就找到一個(gè)基它是一個(gè)單位矩陣，令B所對(duì)應(yīng)的非基變量為零，就得到該線性規(guī)劃的一個(gè)基本可行解。

像這樣第一次找可行基時(shí)，所找到的基由單位矩陣或由單位矩陣的各列向量所組成的基，稱(chēng)為初始基，其對(duì)應(yīng)的基本可行解稱(chēng)為初始基本可行解。1.3.2最優(yōu)性檢驗(yàn)所謂最優(yōu)性檢驗(yàn)就是判斷已求的基本可行解是否是最優(yōu)解。一般來(lái)說(shuō)，目標(biāo)函數(shù)中既包含基變量，又包含非基變量。現(xiàn)在我們要求只用非基變量來(lái)表示目標(biāo)函數(shù)，只要在約束等式中通過(guò)移項(xiàng)處理就可以用非基變量表示基變量，然后用非基變量表示式代替目標(biāo)函數(shù)中的基變量，這樣目標(biāo)函數(shù)中只含有非基變量了。或者說(shuō)目標(biāo)函數(shù)中的基變量系數(shù)都為零了。此時(shí)目標(biāo)函數(shù)中所有變量的系數(shù)即為各變量的檢驗(yàn)數(shù)，把變量的檢驗(yàn)數(shù)記為。顯然所有基變量的檢驗(yàn)數(shù)必為零。在本例中目標(biāo)函數(shù)為，由于初始基本可行解中為非基變量，所以此目標(biāo)函數(shù)已經(jīng)用非基變量表示了，不需要再換出基變量了，這樣我們可知其它檢驗(yàn)數(shù)為零。

對(duì)于求最大目標(biāo)函數(shù)的線性規(guī)劃問(wèn)題，對(duì)于某個(gè)基本可行解，如果所有檢驗(yàn)數(shù)，則這個(gè)基本可行解就是最優(yōu)解，這就是最優(yōu)解判別定理。下面我們來(lái)解釋最優(yōu)解判別定理。假設(shè)用非基變量表示的目標(biāo)函數(shù)為如下形式其中，為常數(shù)項(xiàng)，J為所有非基變量的下標(biāo)集。由于所有的取值范圍都大于等于零，因此當(dāng)所有時(shí)，目標(biāo)函數(shù)中的項(xiàng)是一個(gè)小于等于零的數(shù)，要使的值最大，顯然只有為零。我們把這些取為非基變量，所求得的基本可行解就使目標(biāo)函數(shù)值最大，為。在本例中，由于都大于零，說(shuō)明該基本可行解不是最優(yōu)解。以上討論的都是針對(duì)標(biāo)準(zhǔn)型的，即求目標(biāo)函數(shù)極大化問(wèn)題。當(dāng)求目標(biāo)函數(shù)極小化時(shí)，一種情況如前所述，將其化為標(biāo)準(zhǔn)型；另一種情況是將判別定理中的檢驗(yàn)數(shù)取反方向即可。1.3.3基變換

通過(guò)檢驗(yàn)，我們知道我們求的這個(gè)基本可行解不是最優(yōu)解，下面介紹如何進(jìn)行基變換找到一個(gè)新的可行基，具體的做法就是更換可行基中的一個(gè)列向量，得到一個(gè)新的可行基，使得求解得到的新的基本可行解使得目標(biāo)函數(shù)值更優(yōu)，為此我們需要確定換人基變量和換出基變量。（1）換入變量的確定由最優(yōu)解判定定理可知，當(dāng)某些非基變量的檢驗(yàn)數(shù)時(shí)，非基變量變?yōu)榛兞繒r(shí)，一般會(huì)使目標(biāo)函數(shù)值增大，因此我們選取檢驗(yàn)數(shù)大于零的非基變量換到基變量中去。當(dāng)有兩個(gè)或兩個(gè)以上時(shí)，為了使目標(biāo)函數(shù)值增加的最快，我們一般選擇中的最大者，即：所對(duì)應(yīng)的變量xj做為換入變量(就是下一個(gè)基的基變量)。在本例中，是檢驗(yàn)數(shù)中最大的正數(shù)，故選x2作為換入基變量。（2）換出變量的確定因?yàn)榛兞總€(gè)數(shù)總是為m，所以換入一個(gè)變量之后還必須換出一個(gè)變量。下面我們來(lái)考慮如何選擇換出變量。確定換出變量的原則是保持解的可行性。當(dāng)x2作為換入基變量后，我們要在原來(lái)3個(gè)基變量中確定一個(gè)換出基變量，我們確定那一個(gè)基變量變成非基變量呢？我們把已確定換入基變量在各約束方程中的正的系數(shù)除以其所在約束方程中的常數(shù)項(xiàng)的值，把其中比值最小所在的約束方程中的原基變量確定為換出基變量，這樣在下一步迭代中可以確保新得到的bj值都大于等于零。即則對(duì)應(yīng)的變量為換出變量。

（3）旋轉(zhuǎn)運(yùn)算（迭代運(yùn)算）在確定了換入變量與換出變量之后，要把和的位置對(duì)換，就是說(shuō)，要把所對(duì)應(yīng)的列向量pj變成單位向量。這時(shí)只需對(duì)系數(shù)矩陣的增廣矩陣進(jìn)行行變換即可。綜合以上的討論，單純形算法的計(jì)算步驟可歸結(jié)如下：第一步：找出初始可行基，確定初始基本可行解，建立初始單純形表；第二步：檢查對(duì)應(yīng)于非基變量的檢驗(yàn)數(shù)(IN為非基變量指標(biāo)集)，若所有，k∈IN

，則已得到最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下一步；第三步：在所有中，若有一個(gè)對(duì)應(yīng)的系數(shù)列向量的所有分量，則此問(wèn)題沒(méi)有有限最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下一步；

第四步：根據(jù)確定xj

為換入變量(即為新基的基變量)，再根據(jù)：確定為換出變量(即為新基的非基變量)，轉(zhuǎn)下一步；第五步：進(jìn)行基變換迭代，轉(zhuǎn)回第二步。

例1.8

利用單純形算法求解例1.1的線性規(guī)劃問(wèn)題。

解：（1）由標(biāo)準(zhǔn)型得到初始單純形表，如表1.5所示：表1.5初始單純形表

cj23000θiXBbx1x2x3x4x5x3150[3]1005x41240010

x514220017-Z023000（2），所以x2為換入變量。（3）因?yàn)槎即笥?，且p1,p2的坐標(biāo)有正分量存在因?yàn)棣龋?與x3那一行相對(duì)應(yīng)，所以x3為換出變量；故x2對(duì)應(yīng)列與x3對(duì)應(yīng)行的相交處的3為主元素；（4）以“3”為主元素進(jìn)行旋轉(zhuǎn)計(jì)算，對(duì)表1.5進(jìn)行相應(yīng)的行初等變換，得表1.6：

cj23000θiXBbx1x2x3x4x5x25011/300

x412400103x54[2]0-2/3012-Z-1520-100重復(fù)以上步驟得表1.7這時(shí)，檢驗(yàn)數(shù)全部小于等于0，即目標(biāo)函數(shù)已不可能再增大，于是得到最優(yōu)解：X*=(2,5,0,4,0)T目標(biāo)函數(shù)的最大值為：Z*=19

cj23000θiXBbx1x2x3x4x5x25011/300

x44004/31-2

x1210-1/301/2

-Z-1900-1/30-1單純形算法的步驟總結(jié)1.4線性規(guī)劃問(wèn)題的Excel求解1.4.1規(guī)劃求解工具概述Excel是可以用來(lái)求解并分析線性規(guī)劃問(wèn)題的工具，它不僅可以將線性規(guī)劃模型中所有的參數(shù)錄入電子表格，而且可以利用規(guī)劃求解工具迅速求出模型的解。Excel中的線性規(guī)劃求解功能并不能作為命令直接顯示在菜單選項(xiàng)中，因此，使用前需要先加載該功能。在Excel中的菜單欄中選擇“加載項(xiàng)”對(duì)話框，然后在對(duì)話框中選擇“規(guī)劃求解加載項(xiàng)”選項(xiàng)，并單擊“確定”按鈕，即可添加，如圖1.4所示。加載后打開(kāi)Excel表，在“數(shù)據(jù)”菜單項(xiàng)選擇“規(guī)劃求解”選項(xiàng)，如圖1.5所示。圖1.4Excel加載項(xiàng)模塊

圖1.5Excel規(guī)劃求解模塊

用Excel求解線性規(guī)劃問(wèn)題最優(yōu)解的基本步驟如下：(1)打開(kāi)Excel，在菜單欄中單擊“加載項(xiàng)”對(duì)話框，選擇“規(guī)劃求解加載項(xiàng)”選項(xiàng)，并單擊“確定”按鈕。(2)在Excel中建立表格模型，并用公式建立各個(gè)數(shù)據(jù)之間的聯(lián)系。(3)確定需要的決策變量，并且制定可變單元格顯示這些決策。(4)確定決策的約束條件，并將以數(shù)據(jù)和決策變量表示的被限制的結(jié)果放入輸出單元格。(5)選擇以數(shù)據(jù)和決策變量表示的決策目標(biāo)輸入目標(biāo)單元格。(6)選擇“數(shù)據(jù)/規(guī)劃求解”選項(xiàng)，依次單擊“目標(biāo)”→“選定可變單元格”→“輸入約束”選項(xiàng)，在“使無(wú)約束變量為非負(fù)數(shù)”選項(xiàng)處打鉤，選擇求解方法為“單純線性規(guī)劃”選項(xiàng)，最后單擊“求解”按鈕，完成整個(gè)問(wèn)題的求解。例1.11

用Excel求解例1.1中“生產(chǎn)計(jì)劃問(wèn)題”。步驟1：首先把線性規(guī)劃模型轉(zhuǎn)化為Excel電子表格數(shù)據(jù)。通常分為四個(gè)部分：基礎(chǔ)數(shù)據(jù)、決策變量、目標(biāo)函數(shù)以及約束條件系數(shù)矩陣。首先在Excel表中輸入四部分內(nèi)容（見(jiàn)圖1.6）。其中“變量”中的值是任意輸入的初始值。圖中最后1列是公式，其中SUMPRODUCT函數(shù)的功能是在給定的幾組數(shù)組中，將數(shù)組間對(duì)應(yīng)的元素相乘并相加。例如：SUMPRODUCT(B3:C3,B7:C7)=B3*B7+C3*C7=0+0=0。

圖1.6生產(chǎn)計(jì)劃問(wèn)題輸入表格

在使用EXCEL上機(jī)操作時(shí)在公式的計(jì)算格中看到的是計(jì)算結(jié)果而不是公式，如圖1.7所示。

圖1.7生產(chǎn)計(jì)劃問(wèn)題輸入表格

步驟2：數(shù)據(jù)輸入后，在菜單欄中選擇“數(shù)據(jù)/規(guī)劃求解”選項(xiàng)，便會(huì)彈出“規(guī)劃求解參數(shù)”對(duì)話框(見(jiàn)圖1.8)。在該對(duì)話框中，目標(biāo)單元格在開(kāi)始求解之前，需要在對(duì)話框中設(shè)置好各種參數(shù)，包括目標(biāo)單元格、問(wèn)題類(lèi)型(求最大值或最小值)、可變單元格以及約束條件等。目標(biāo)單元格為任意空白區(qū)域單元格。在此問(wèn)題中，目標(biāo)單元格選擇B7，問(wèn)題類(lèi)型是求最大值，可變單元格為B6到C6，單擊“添加”按鈕，使三個(gè)約束條件一一被添加。然后單擊“選項(xiàng)”菜單，在彈出的對(duì)話框中選擇采用線性模型和假定非負(fù)選項(xiàng)，最后單擊“確定”按鈕。

圖1.8“規(guī)劃求解參數(shù)”對(duì)話框

步驟3、設(shè)置完成后，點(diǎn)擊圖1.8中“求解”選項(xiàng)，彈出“規(guī)劃求解結(jié)果”對(duì)話框，如圖1.9所示。圖1.9規(guī)劃求解結(jié)果對(duì)話框

選擇“保留規(guī)劃求解的解”以及“運(yùn)算結(jié)果報(bào)告”選項(xiàng)，單擊“確定”按鈕。如果模型沒(méi)有最優(yōu)解，對(duì)話框?qū)@示“規(guī)劃求解找不到有用的解”或“設(shè)置目標(biāo)單元格的值未收斂”。上述案例的最優(yōu)解及“運(yùn)算結(jié)果報(bào)告”，如圖1.10、圖1.11所示。圖1.10生產(chǎn)計(jì)劃問(wèn)題最優(yōu)解

圖1.11生產(chǎn)計(jì)劃問(wèn)題“運(yùn)算結(jié)果報(bào)告”

如圖1.11所示，可變單元格部分的“終值”處的“(2,5)”代表是最優(yōu)解，工廠應(yīng)生產(chǎn)2件產(chǎn)品甲以及5件產(chǎn)品乙，可獲得最高利潤(rùn)19萬(wàn)元。此結(jié)果與使用圖解法的結(jié)果是一致的。下面就“運(yùn)算結(jié)果報(bào)告”進(jìn)行解釋?zhuān)@個(gè)報(bào)告分為三個(gè)部分：第一部分有關(guān)目標(biāo)函數(shù)，其中“初值”是求解以前單元格B7的值，等于0。“終值”是求得最優(yōu)解以后單元格B7的值，即目標(biāo)函數(shù)的最優(yōu)值，等于19；第二部分關(guān)于可變單元格，其中“初值”和“終值”的含義與前面相同；第三部分關(guān)于約束條件，其中“單元格”是指三個(gè)約束條件的左邊值的單元格，即D2、D3、D4?！皢卧裰怠笔侵盖蠼庖院笕齻€(gè)單元格的值，即原材料和設(shè)備的資源限制的值?！肮健笔侵溉齻€(gè)約束條件的關(guān)系符。“狀態(tài)”是指每個(gè)約束是否達(dá)到限制值，原材料B的占用能力沒(méi)有達(dá)到供應(yīng)量的限制值，其他兩個(gè)約束達(dá)到了限制值?！靶蛿?shù)值”是約束條件剩余差額，如原材料B還剩下4萬(wàn)噸沒(méi)有被利用。例1.14

用Excel求解例1.4中“連續(xù)投資問(wèn)題”。首先把線性規(guī)劃模型轉(zhuǎn)化為電腦上的Excel電子表格數(shù)據(jù)。由于該模型中有20個(gè)變量，便用第B列至第U列為各變量列，第V列為模型右端常數(shù)項(xiàng)，第W列為約束左端計(jì)算項(xiàng)，因此基礎(chǔ)數(shù)據(jù)放在第2行至第8行，第9行為對(duì)應(yīng)的目標(biāo)函數(shù)系數(shù)，第10行為決策變量行，初值賦值為0，B11單元格表示目標(biāo)函數(shù)值。其中第W列與B11單元格是SUMPRODUCT函數(shù)公式，具體數(shù)據(jù)輸入表格在此略去。數(shù)據(jù)輸入后，在菜單欄中選擇“數(shù)據(jù)/規(guī)劃求解”選項(xiàng)，彈出“規(guī)劃求解參數(shù)”對(duì)話框(見(jiàn)圖1.12)。在該對(duì)話框中，目標(biāo)單元格選擇B11，問(wèn)題類(lèi)型是求最大值，可變單元格為B10到U10，單擊“添加”按鈕使7個(gè)約束條件一一被添加。然后單擊“選項(xiàng)”按鈕，在彈出的對(duì)話框中選擇采用線性模型和假定非負(fù)選項(xiàng)，最后單擊“確定”按鈕。例1.14

用Excel求解例1.4中“連續(xù)投資問(wèn)題”。設(shè)置完成后，單擊如圖1.12所示中的“求解”按鈕，彈出“規(guī)劃求解結(jié)果”對(duì)話框，如圖1.13所示。該規(guī)劃約束條件未滿足線性模型，選擇“保留規(guī)劃求解的解”選項(xiàng)，單擊“確定”按鈕。 圖1.12“規(guī)劃求解參數(shù)”對(duì)話框

圖1.13

“規(guī)劃求解結(jié)果”對(duì)話框

這時(shí)在Excel電子表格中原始變量數(shù)據(jù)自動(dòng)轉(zhuǎn)換為滿足線性模型的約束條件。在菜單欄中選擇“工具/規(guī)劃求解”選項(xiàng)，彈出“規(guī)劃求解結(jié)果”對(duì)話框(見(jiàn)圖1.14)。選擇“保留規(guī)劃求解的解”以及“運(yùn)算結(jié)果報(bào)告”選項(xiàng)，單擊“確定”按鈕?！斑\(yùn)算結(jié)果報(bào)告”如圖1.15所示。

圖1.14“規(guī)劃求解結(jié)果”對(duì)話框(選擇“運(yùn)算結(jié)果報(bào)告”)

圖1.15連續(xù)投資問(wèn)題“運(yùn)算結(jié)果報(bào)告”

在圖1.15中可變單元格部分的“終值”下面就是最優(yōu)解，x1A=34783萬(wàn)元，x1D=65217萬(wàn)元，x2A=39130萬(wàn)元，x2C=30000萬(wàn)元，x2D=0，x3A=0，x3B=40000萬(wàn)元，x3D=0，x4A=45000萬(wàn)元，x4D=0，x5D=0，目標(biāo)單元格就是到第五年年末該部門(mén)擁有資金總額為143750萬(wàn)元，即盈利43.75%。例1.15

用Excel求解例1.5中“航班安排問(wèn)題”。首先把線性規(guī)劃模型轉(zhuǎn)化為電腦上的Excel電子表格數(shù)據(jù)，如圖1.16所示。

圖1.16航班安排問(wèn)題輸入表格

在菜單欄中選擇“工具/規(guī)劃求解”，便會(huì)彈出“規(guī)劃求解參數(shù)”對(duì)話框（如圖1.17）。在該對(duì)話框中，我們選擇目標(biāo)單元格選擇B19，問(wèn)題類(lèi)型是求最小值，可變單元格為B14到E16，點(diǎn)擊“添加”約束，使7個(gè)約束條件一一被添加。然后點(diǎn)擊“選項(xiàng)”，在彈出對(duì)話框中勾選采用線性模型和假定非負(fù)選項(xiàng)，最后單擊“確定”回到下列對(duì)話框。圖1.17航班安排問(wèn)題參數(shù)設(shè)置對(duì)話框

設(shè)置完成后，點(diǎn)擊圖1.17中“求解”選項(xiàng)，彈出“規(guī)劃求解結(jié)果”對(duì)話框，如圖1.18所示。選定“保存規(guī)劃求解結(jié)果”，“運(yùn)算結(jié)果報(bào)告”，點(diǎn)擊“確定”。圖1.18航班安排問(wèn)題規(guī)劃求解結(jié)果

航班安排問(wèn)題的最優(yōu)解及運(yùn)算結(jié)果報(bào)告，如圖1.19、圖1.20所示。圖1.19航班安排問(wèn)題最優(yōu)解

圖1.20航班安排問(wèn)題運(yùn)算結(jié)果報(bào)告

在圖1.19中方案安排中我們可以看到，波音737飛機(jī)安排C城市15個(gè)航班;空客320飛機(jī)安排A城市2個(gè)航班,安排D城市12個(gè)航班;ERJ-190飛機(jī)安排A城市8個(gè)航班,安排B城市12個(gè)航班。飛行總費(fèi)用為32150000元。從圖1.20可以看出，波音737與空客320沒(méi)有達(dá)到限制值，分別剩余6和18個(gè)小時(shí)飛行時(shí)間。ERJ-190飛機(jī)已達(dá)到限制值。1.5規(guī)劃求解的極限值報(bào)告和敏感性報(bào)告以例1.1生產(chǎn)計(jì)劃安排問(wèn)題為例介紹極限值報(bào)告與進(jìn)敏感性報(bào)告。利用Excel對(duì)其求解，在數(shù)據(jù)輸入完成后，點(diǎn)擊“工具-規(guī)劃求解”按鈕，彈出“規(guī)劃求解參數(shù)”對(duì)話框，在完成各參數(shù)的輸入后，點(diǎn)擊“選項(xiàng)”按鈕并設(shè)置規(guī)劃求解的條件。完成后，點(diǎn)擊“求解”按鈕。彈出的“規(guī)劃求解結(jié)果”對(duì)話框，如圖1.21所示。圖1.21生產(chǎn)計(jì)劃問(wèn)題“規(guī)劃求解結(jié)果”對(duì)話框1.5.1極限值報(bào)告利用Excel進(jìn)行“規(guī)劃求解”得到最優(yōu)解后，可以得到三個(gè)報(bào)告，除在前面介紹了運(yùn)算結(jié)果報(bào)告外，還有敏感性報(bào)告和極限值報(bào)告兩個(gè)工作表，下面先介紹“極限值報(bào)告”。在圖1.21選中極限值報(bào)告，然后點(diǎn)擊“確定”按鈕就會(huì)出現(xiàn)極限值報(bào)告，如圖1.22所示。

圖1.22生產(chǎn)計(jì)劃安排問(wèn)題的“極限值報(bào)告”“極限值報(bào)告”分為兩部分，第一部分是目標(biāo)函數(shù)單元格和目標(biāo)函數(shù)值。第二部分是變量，其中“單元格”是指決策變量所在的單元格，“變量名字”是指決策變量的名稱(chēng)，“值”是指決策變量最優(yōu)解的值，“下限極限”是指決策變量約束的最小值，“目標(biāo)式結(jié)果”是指當(dāng)該決策變量取“下限極限”，其它決策取最優(yōu)值時(shí)的目標(biāo)函數(shù)值?！吧舷迾O限”是指決策變量最優(yōu)解中的最大值，“目標(biāo)式結(jié)果”是指當(dāng)該決策變量取“上限極限”，其它決策取最優(yōu)值時(shí)的目標(biāo)函數(shù)值，這時(shí)很顯然，目標(biāo)函數(shù)值就是最優(yōu)值。1.5.2敏感性報(bào)告在圖1.21選中敏感性報(bào)告，然后點(diǎn)擊“確定”按鈕就會(huì)出現(xiàn)敏感性報(bào)告,如圖1.23所示。圖1.23生產(chǎn)計(jì)劃安排問(wèn)題的“敏感性報(bào)告”

“敏感性報(bào)告”分為可變單元格的敏感性分析與約束的敏感性分析兩部分，每一部分有5個(gè)欄目?？勺儐卧癫糠职ńK值、遞減成本、目標(biāo)式系數(shù)、允許的增量和允許的減量；約束部分包括終值、陰影價(jià)格、約束限制值、允許的增量和允許的減量。首先解釋可變單元格部分有關(guān)欄目。根據(jù)圖1.23可知，可變單元格中“終值”一欄對(duì)應(yīng)的數(shù)據(jù)為最優(yōu)解，即兩種產(chǎn)品的產(chǎn)量，其中產(chǎn)品甲和產(chǎn)品乙各生產(chǎn)2和5個(gè)單位，它代表了最優(yōu)生產(chǎn)方案。“遞減成本”一欄反映的是該決策變量每增加一個(gè)單位所導(dǎo)致的目標(biāo)函數(shù)的變化量?！澳繕?biāo)式系數(shù)”欄對(duì)應(yīng)目標(biāo)函數(shù)價(jià)值系數(shù)Cj

的值，在本題中的經(jīng)濟(jì)含義為各產(chǎn)品的單件利潤(rùn)?！霸试S的增量”和“允許的減量”兩欄代表的是在最優(yōu)解保持不變的前提下價(jià)值系數(shù)所允許的增量與減量。其中，“1E+30”代表1030，意味著無(wú)窮大。因此由“目標(biāo)式系數(shù)”、“允許的增量”與“允許的減量”三者共同確定價(jià)值系數(shù)的變化范圍。上述結(jié)果顯示，產(chǎn)品甲的單件利潤(rùn)c1的取值范圍是[0,3],在此區(qū)間內(nèi),c1的值變化不會(huì)對(duì)最優(yōu)解產(chǎn)生影響。同理，產(chǎn)品乙的單件利潤(rùn)c2的取值范圍分別在區(qū)間[2，∞）內(nèi)時(shí)，最優(yōu)解不發(fā)生變化。對(duì)約束部分，“終值”一欄對(duì)應(yīng)的數(shù)據(jù)為資源約束量b，即b=(15，12，14)T。最后兩欄代表在最優(yōu)解保持不變的前提下資源約束量bj所允許的增量與減量。同理可得，資源約束量bj的變化范圍為：

即當(dāng)原料A的供應(yīng)量b1和原料B的供應(yīng)量b2分別在區(qū)間[9,18]和(-∞,16]，設(shè)備的供應(yīng)量在[12，18]之間變化時(shí),最優(yōu)解不發(fā)生變化。圖1.23所示的敏感性分析報(bào)告中顯示出另一個(gè)重要信息就是影子價(jià)格。影子價(jià)格是指線性規(guī)劃的原問(wèn)題中某個(gè)資源約束常數(shù)增加或減少一個(gè)單位從而導(dǎo)致目標(biāo)函數(shù)值的增量或減量，也就是原材料或設(shè)備可利用能力的邊際利潤(rùn)。影子價(jià)格的大小客觀上反映資源在系統(tǒng)內(nèi)的稀缺程度，影子價(jià)格越高，資源在系統(tǒng)中越稀缺。“陰影價(jià)格”一欄顯示的就是影子價(jià)格，它意味著若每增加一個(gè)單位的原材料A，目標(biāo)函數(shù)值將增加個(gè)單位,每增加一個(gè)單位的原材料B，目標(biāo)函數(shù)值保持不變，這是由于在模型求解中，達(dá)到最優(yōu)解時(shí)，原材料B還有剩余，因此增加該原材料公司利潤(rùn)并不能增加。同理，若每增加一個(gè)單位的設(shè)備臺(tái)時(shí)，那么目標(biāo)函數(shù)值將增加1個(gè)單位。有關(guān)影子價(jià)格問(wèn)題我們將在后面具體介紹。1.6線性規(guī)劃問(wèn)題的靈敏度分析在實(shí)際問(wèn)題中，應(yīng)首先收集有關(guān)數(shù)據(jù)，建立線性規(guī)劃模型，用Excel或其它軟件求解。但管理者得到最優(yōu)解之后往往還需要開(kāi)展進(jìn)一步的工作。因?yàn)榫€性規(guī)劃模型是在一定的假設(shè)條件下建立起來(lái)的，得到的最優(yōu)解是在這一特定條件的最優(yōu)解，如果假設(shè)條件發(fā)生變化時(shí)，最優(yōu)方案是否改變以及如何改變，在不同條件下各種管理方法可能產(chǎn)生的結(jié)果如何，管理者通過(guò)各種結(jié)果對(duì)比分析，指導(dǎo)管理者進(jìn)行決策。因此在得到原始模型的最優(yōu)解之后，通過(guò)對(duì)最優(yōu)解的分析才能對(duì)問(wèn)題有更深刻的理解和認(rèn)識(shí)。對(duì)最優(yōu)解的分析主要涉及的問(wèn)題是如果未來(lái)情況發(fā)生變化，最優(yōu)解將如何變化。在前面的線性規(guī)劃問(wèn)題討論中，都是假定為常數(shù)，但實(shí)際工作中這些系數(shù)往往是估計(jì)值和預(yù)測(cè)值。如市場(chǎng)條件發(fā)生變化，價(jià)值系數(shù)就會(huì)發(fā)生變化；當(dāng)資源投入量發(fā)生改變時(shí)，也隨著發(fā)生變化；當(dāng)工藝條件發(fā)生改變時(shí)，也隨著工藝的變化而變化。因此當(dāng)這些系數(shù)有一個(gè)或幾個(gè)發(fā)生變化時(shí)，已求得的線性規(guī)劃問(wèn)題的最優(yōu)解會(huì)有什么變化？或者這些系數(shù)在什么范圍內(nèi)變化時(shí)，線性規(guī)劃問(wèn)題的最優(yōu)解不發(fā)生變化。

因此我們?cè)谶M(jìn)行靈敏度分析時(shí)，就是要弄清楚：1）系數(shù)在什么范圍內(nèi)變化時(shí)，最優(yōu)解不變；2）若系數(shù)的變化使最優(yōu)解發(fā)生變化時(shí)，如何求得新的最優(yōu)解。下面分別就各個(gè)參數(shù)改變的情形進(jìn)行討論。例1.14已知某企業(yè)計(jì)劃生產(chǎn)3種產(chǎn)品A、B、C，其資源消耗與利潤(rùn)如表1.8示問(wèn)：如何安排產(chǎn)品產(chǎn)量，可獲最大利潤(rùn)？產(chǎn)品A產(chǎn)品B產(chǎn)品C資源量資源甲（噸）11112資源乙（噸）12220單位產(chǎn)品利潤(rùn)（萬(wàn)元）586解：設(shè)三種產(chǎn)品的產(chǎn)量分別為x1、x2、x3。其數(shù)學(xué)模型的標(biāo)準(zhǔn)型為首先把線性規(guī)劃模型轉(zhuǎn)化為Excel電子表格數(shù)據(jù)，如圖1.24所示。圖1.24數(shù)據(jù)輸入表格數(shù)據(jù)輸入后，在菜單欄中選擇“工具/規(guī)劃求解”，彈出“規(guī)劃求解參數(shù)”對(duì)話框，如圖1.25所示。在該對(duì)話框中，在對(duì)話框中設(shè)置好各種參數(shù)。其中目標(biāo)單元格選擇B7，問(wèn)題類(lèi)型是求最大值，可變單元格為B6到D6，點(diǎn)擊“添加”約束，使三個(gè)約束條件一一被添加。然后點(diǎn)擊“選項(xiàng)”，在彈出對(duì)話框中勾選采用線性模型和假定非負(fù)選項(xiàng)，最后單擊“確定”。圖1.25“規(guī)劃求解參數(shù)”對(duì)話框設(shè)置完成后，點(diǎn)擊圖1.25中“求解”選項(xiàng)，彈出“規(guī)劃求解結(jié)果”對(duì)話框，如圖1.26所示。圖1.26規(guī)劃求解結(jié)果在圖圖1.26中選定“保存規(guī)劃求解結(jié)果”以及“運(yùn)算結(jié)果報(bào)告”，點(diǎn)擊“確定”，如圖1.27所示。圖1.27運(yùn)算結(jié)果報(bào)告這時(shí)最優(yōu)生產(chǎn)方案為X=(4,8,0)T,目標(biāo)函數(shù)最優(yōu)值為84。在圖1.26中選定“保存規(guī)劃求解結(jié)果”以及“靈敏性報(bào)告”，點(diǎn)擊“確定”,如圖1.28所示。圖1.28“靈敏性報(bào)告”從圖1.28中可以看到，目標(biāo)系數(shù)允許增加量為3，允許減少量為1，也就是說(shuō)可變單元格中“終值”一欄對(duì)應(yīng)的數(shù)據(jù)為最優(yōu)解，即X=(4,8,0)T，它代表了最優(yōu)生產(chǎn)方案。“遞減成本”一欄反映的是該變量每增加一個(gè)單位所導(dǎo)致的目標(biāo)函數(shù)的變化量。例如，產(chǎn)品C的遞減成本為-2，它的經(jīng)濟(jì)解釋為每增加一個(gè)單位產(chǎn)品C的生產(chǎn)，總利潤(rùn)將會(huì)減少2個(gè)單位，即產(chǎn)品C不宜生產(chǎn)。1.6.1目標(biāo)函數(shù)價(jià)值系數(shù)Cj的靈敏度分析圖1.28中“允許的增量”和“允許的減量”兩欄代表的是在最優(yōu)解保持不變的前提下目標(biāo)函數(shù)的價(jià)值系數(shù)cj

所允許的增量與減量。其中，“1E+30”代表1030，意味著無(wú)窮大。因此由“目標(biāo)式系數(shù)”、“允許的增量”與“允許的減量”三者共同確定價(jià)值系數(shù)的變化范圍。-1≤△≤3,即-1≤-5≤3，則4≤≤8；

-2≤△≤2,即-2≤-8≤2，則6≤≤10；-∞≤△≤2,即-∞≤-6≤2，則-∞≤≤8.上述結(jié)果顯示，產(chǎn)品A的單件利潤(rùn)c1的取值范圍是[4,8],在此區(qū)間內(nèi)，c1的值變化不會(huì)對(duì)最優(yōu)解產(chǎn)生影響。同理，產(chǎn)品B的單件利潤(rùn)c2和產(chǎn)品C的單件利潤(rùn)c2的取值范圍分別在區(qū)間[6,10]和（-∞，8]內(nèi)時(shí)，最優(yōu)解不發(fā)生變化。上述討論是假定某一個(gè)目標(biāo)函數(shù)的系數(shù)發(fā)生變化，其他系數(shù)不變的情況下進(jìn)行討論的。

另外如果目標(biāo)函數(shù)的系數(shù)變化范圍超過(guò)上述范圍，又將如何求最優(yōu)解呢？如果有多個(gè)目標(biāo)函數(shù)的價(jià)值系數(shù)發(fā)生變化，我們又將如何求最優(yōu)解呢？當(dāng)然最簡(jiǎn)單的方法就是仍運(yùn)用Excel表進(jìn)行求解。若單位產(chǎn)品C的利潤(rùn)C(jī)3為10時(shí)，最優(yōu)解與最優(yōu)值將如何變化呢？這時(shí)我們只需將變化后新的目標(biāo)函數(shù)價(jià)值系數(shù)代入Excel表格中，重新按下“規(guī)劃求解”，“求解”按鈕，馬上就可以得到答案，如圖1.29所示。圖1.29單位產(chǎn)品C的利潤(rùn)C(jī)3為10時(shí)最優(yōu)解則最優(yōu)生產(chǎn)方案調(diào)整為X=(0,0,10)T,目標(biāo)函數(shù)最優(yōu)值為100。如單位產(chǎn)品A的利潤(rùn)改變?yōu)?0時(shí)，得到答案如圖1.30所示。圖1.30單位產(chǎn)品A的利潤(rùn)改變?yōu)?0時(shí)最優(yōu)解單位產(chǎn)品A的利潤(rùn)為10時(shí)，則最優(yōu)生產(chǎn)方案調(diào)整為X=(12,0,0)T,目標(biāo)函數(shù)最優(yōu)值為120。當(dāng)有多個(gè)目標(biāo)函數(shù)價(jià)值系數(shù)發(fā)生變化時(shí)，與上面的方法類(lèi)似，只需將改變后的價(jià)值系數(shù)代入Excel表格中，重新按下“規(guī)劃求解”，“求解”按鈕，馬上就可以得到答案。若令，得如圖1.31所示的最優(yōu)解。單位產(chǎn)品A的利潤(rùn)改變?yōu)?，單位產(chǎn)品C的利潤(rùn)C(jī)3改變?yōu)?時(shí)時(shí)，則最優(yōu)生產(chǎn)方案調(diào)整為X=(4,0,8)T,目標(biāo)函數(shù)最優(yōu)值為96。1.6.2資源約束量b的靈敏度分析與影子價(jià)格（1）資源約束量b的靈敏度分析圖1.28的約束部分最后兩欄代表在最優(yōu)解保持不變的前提下資源約束量bj

所允許的增量與減量。資源約束量bj

的變化范圍為：-2≤△b1≤8,即-2≤b1-12≤8，則10≤b1≤20；-8≤△b2≤4,即-8≤b2-20≤4，則12≤b2≤24.即當(dāng)原材料甲的供應(yīng)量b1和原材料料乙的供應(yīng)量b2分別在區(qū)間[10,20]和[12,24]之間變化時(shí),最優(yōu)基不變（即生產(chǎn)產(chǎn)品的品種不變，但生產(chǎn)數(shù)量及最優(yōu)值會(huì)發(fā)生變化，即生產(chǎn)方案發(fā)生改變）。當(dāng)原材料甲的供應(yīng)量由12改變?yōu)闀r(shí)，最優(yōu)解與最優(yōu)值將如何變化呢？這時(shí)我們只需將變化后新的原材料甲的供應(yīng)量代入Excel表格中，重新按下“規(guī)劃求解”，“求解”按鈕，馬上就可以得到答案，如圖1.32所示。

圖1.32資源甲的供應(yīng)量由12改變?yōu)?8時(shí)的最優(yōu)解此時(shí)最優(yōu)生產(chǎn)方案調(diào)整為X=(16,2,0)T,目標(biāo)函數(shù)最優(yōu)值為96。若原材料的供應(yīng)量超過(guò)上述范圍時(shí)，最優(yōu)解與最優(yōu)值將如何變化呢？這時(shí)我們只需將變化后新的資源量代入Excel表格中，重新按下“規(guī)劃求解”，“求解”按鈕，馬上就可以得到答案，若將原材料甲的供應(yīng)量由12改變?yōu)?0時(shí)，最優(yōu)解如圖1.33所示。圖1.33資源甲的供應(yīng)量由12改變?yōu)?0時(shí)的最優(yōu)解則最優(yōu)生產(chǎn)方案調(diào)整為X=(20,0,0)T,目標(biāo)函數(shù)最優(yōu)值為100。（2）影子價(jià)格影子價(jià)格不是一種真實(shí)價(jià)格，而是系統(tǒng)資源價(jià)值的映象表現(xiàn)。但是可以通過(guò)影子價(jià)格對(duì)系統(tǒng)資源的利用情況做出客觀評(píng)價(jià)，從而決定企業(yè)的經(jīng)營(yíng)策略。因此影子價(jià)格是在最優(yōu)決策下對(duì)資源的一種估價(jià)，沒(méi)有最優(yōu)決策就沒(méi)有影子價(jià)格，所以影子價(jià)格又稱(chēng)“最優(yōu)計(jì)劃價(jià)格”，“預(yù)測(cè)價(jià)格”等等。圖1.28敏感性分析報(bào)告中顯示出影子價(jià)格，若每增加一個(gè)單位的原材料料甲，目標(biāo)函數(shù)值將增加2個(gè)單位，若每增加一個(gè)單位的原材料料乙，目標(biāo)函數(shù)值將增加3個(gè)單位。如原材料甲的供應(yīng)量由12改變?yōu)?8時(shí)，原材料甲的供應(yīng)量增加了6個(gè)單位，因此目標(biāo)函數(shù)值將增加12個(gè)單位，即目標(biāo)函數(shù)值由84增加到96。但當(dāng)原材料供應(yīng)量超過(guò)它所允許的范圍時(shí)，該資源的影子價(jià)格將發(fā)生改變，因?yàn)樗淖兞速Y源的稀缺性。如原材料甲的供應(yīng)量由12改變?yōu)?0時(shí)，原材料甲的供應(yīng)量增加了18個(gè)單位，但原材料甲的供應(yīng)量達(dá)到20時(shí)，該資源已經(jīng)得到飽和，再增加的部分的影子價(jià)格為0，因此此時(shí)目標(biāo)函數(shù)值將只能增加=16個(gè)單位，即目標(biāo)函數(shù)值由84增加到100。資源的影子價(jià)格定量的反映了單位資源在最優(yōu)生產(chǎn)方案中為總收益所做出的貢獻(xiàn)，因此，資源的影子價(jià)格也可稱(chēng)為在最優(yōu)方案中投入生產(chǎn)的機(jī)會(huì)成本。若第i種資源的單位市場(chǎng)價(jià)格為mi，當(dāng)>mi時(shí)，企業(yè)愿意購(gòu)進(jìn)這種資源，單位純利為-mi，則有利可圖；如果<mi，則企業(yè)有償轉(zhuǎn)讓這種資源，可獲單位純利mi-，否則，企業(yè)無(wú)利可圖，甚至虧損。影子價(jià)格在決策中有重要的作用，主要表現(xiàn)在以下幾個(gè)方面：（1）指出企業(yè)挖潛革新的途徑影子價(jià)格大于0，說(shuō)明該資源已耗盡，成為短線資源。影子價(jià)格等于0，說(shuō)明該資源有剩余，成為長(zhǎng)線資源。（2）對(duì)市場(chǎng)資源的最優(yōu)配置起著推進(jìn)作用即在配置資源時(shí)，對(duì)于影子價(jià)格大的企業(yè)，資源應(yīng)優(yōu)先供給（3）可以預(yù)測(cè)產(chǎn)品的價(jià)格產(chǎn)品的機(jī)會(huì)成本為CBB-1A-C，只有當(dāng)產(chǎn)品價(jià)格定在機(jī)會(huì)成本之上，企業(yè)才有利可圖。（4）可作為同類(lèi)企業(yè)經(jīng)濟(jì)效益評(píng)估指標(biāo)之一。對(duì)于資源影子價(jià)格越大的企業(yè)，資源的利用所帶來(lái)的收益就越大，經(jīng)濟(jì)效益就越好。通過(guò)以上討論可知，企業(yè)利用影子價(jià)格可以進(jìn)行經(jīng)營(yíng)決策。（1）某種資源的影子價(jià)格高于市場(chǎng)價(jià)格，表明該資源在系統(tǒng)中有獲利能力，應(yīng)該買(mǎi)入該資源；（2）某種資源的影子價(jià)格低于市場(chǎng)價(jià)格，表明該資源在系統(tǒng)中沒(méi)有獲利能力，應(yīng)該賣(mài)出該資源；（3）某種資源的影子價(jià)格等于市場(chǎng)價(jià)格，表明該資源在系統(tǒng)中處于均衡狀態(tài)，既不買(mǎi)入也不賣(mài)出該資源。1.6.3添加新變量的靈敏度分析在例1.14中，若新開(kāi)發(fā)出新產(chǎn)品D，生產(chǎn)該單位產(chǎn)品需要消耗原材料甲：3個(gè)單位，消耗原材料乙：2個(gè)單位，可以得利潤(rùn)10。問(wèn)：投產(chǎn)產(chǎn)品D是否有利？假設(shè)生產(chǎn)產(chǎn)品D的產(chǎn)量為，這時(shí)就相當(dāng)于在Excel表格增加一列，該列對(duì)應(yīng)數(shù)據(jù)為3，2，10。前2個(gè)表示單位產(chǎn)品的消耗，后一個(gè)表示單位產(chǎn)品利潤(rùn)。對(duì)應(yīng)于Excel表格就是增加E列，同時(shí)在F2格輸入函數(shù)=SUMPRODUCT(B2:E2,B5:E5)，F(xiàn)3格輸入函數(shù)=SUMPRODUCT(B3:E3,B5:E5)，B6格輸入函數(shù)=SUMPRODUCT(B4:E4,B5:E5)。重新按下“規(guī)劃求解”，對(duì)“規(guī)劃求解參數(shù)”對(duì)話框中各參數(shù)進(jìn)行設(shè)置，如圖1.34所示的最優(yōu)解。

圖1.34參數(shù)設(shè)置對(duì)話框點(diǎn)擊“求解”選項(xiàng)，得如圖1.35所示。圖1.35增加新產(chǎn)品后的最優(yōu)解這時(shí)，則最優(yōu)生產(chǎn)方案為X=(4,8,0,0)T,目標(biāo)函數(shù)最優(yōu)值為84。圖1.36增加新產(chǎn)品后的最優(yōu)解“敏感性報(bào)告”這時(shí)由圖1.36增加新產(chǎn)品后的最優(yōu)解靈敏度分析報(bào)告可以看出，產(chǎn)品D的檢驗(yàn)數(shù)為-2，檢驗(yàn)數(shù)小于等于0，因此最優(yōu)生產(chǎn)方案不變，不生產(chǎn)產(chǎn)品D。即投產(chǎn)產(chǎn)品D無(wú)利。單位產(chǎn)品D的利潤(rùn)為多少時(shí)，投產(chǎn)產(chǎn)品D有利？

圖1.36中可變單元格中“允許的增量”和“允許的減量”兩欄代表的是最優(yōu)解保持不變的前提下目標(biāo)函數(shù)的價(jià)值系數(shù)cj所允許的增量與減量。因此由“目標(biāo)式系數(shù)”、“允許的增量”與“允許的減量”三者共同確定價(jià)值系數(shù)的變化范圍。即，則。說(shuō)明產(chǎn)品D的單件利潤(rùn)大于或等于12時(shí)，投產(chǎn)產(chǎn)品D才有利。當(dāng)產(chǎn)品D的單件利潤(rùn)有10改變?yōu)?5時(shí)，最優(yōu)解與最優(yōu)值將如何變化呢？這時(shí)我們只需將變化后新的產(chǎn)品D的單件利潤(rùn)代入Excel表格中