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

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

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

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

年年初給項目A的投資額（萬元）i=1,···,5；xiB

：表示第i

年年初給項目B的投資額（萬元）i=1,···,5；xiC：表示第i

年年初給項目C的投資額（萬元）i=1,···,5；xiD：表示第i

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

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

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

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

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

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

為價值向量，X

為決策向量，通常aij

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

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

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

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

將例1.1的線性規(guī)劃數(shù)學(xué)模型化為標準型。解：引進3個新的非負變量x3，x4，x5使不等式變?yōu)榈仁剑瑯藴市蜑椋?/p>

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

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

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

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

，B是矩陣A中由m

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

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

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

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

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

例1.8

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

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

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

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

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

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

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

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

maxZ=2x1+4x2

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

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

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

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

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

∈K；X若不能用K中不同的兩個點X1、X2∈K的線性組合表示為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例1.8

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

解：（1）由標準型得到初始單純形表，如表1.5所示：表1.5初始單純形表

cj23000θiXBbx1x2x3x4x5x3150[3]1005x41240010

x514220017-Z023000（2），所以x2為換入變量。（3）因為都大于0，且p1,p2的坐標有正分量存在因為θ＝5與x3那一行相對應(yīng)，所以x3為換出變量；故x2對應(yīng)列與x3對應(yīng)行的相交處的3為主元素；（4）以“3”為主元素進行旋轉(zhuǎn)計算，對表1.5進行相應(yīng)的行初等變換，得表1.6：

cj23000θiXBbx1x2x3x4x5x25011/300

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

cj23000θiXBbx1x2x3x4x5x25011/300

x44004/31-2

x1210-1/301/2

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

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

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

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

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

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

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

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

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

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

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

圖1.11生產(chǎn)計劃問題“運算結(jié)果報告”

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

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

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

圖1.13

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

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

圖1.14“規(guī)劃求解結(jié)果”對話框(選擇“運算結(jié)果報告”)

圖1.15連續(xù)投資問題“運算結(jié)果報告”

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

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

圖1.16航班安排問題輸入表格

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

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

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

圖1.20航班安排問題運算結(jié)果報告

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

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

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

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

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

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

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

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

另外如果目標函數(shù)的系數(shù)變化范圍超過上述范圍，又將如何求最優(yōu)解呢？如果有多個目標函數(shù)的價值系數(shù)發(fā)生變化，我們又將如何求最優(yōu)解呢？當然最簡單的方法就是仍運用Excel表進行求解。若單位產(chǎn)品C的利潤C3為10時，最優(yōu)解與最優(yōu)值將如何變化呢？這時我們只需將變化后新的目標函數(shù)價值系數(shù)代入Excel表格中，重新按下“規(guī)劃求解”，“求解”按鈕，馬上就可以得到答案，如圖1.29所示。圖1.29單位產(chǎn)品C的利潤C3為10時最優(yōu)解則最優(yōu)生產(chǎn)方案調(diào)整為X=(0,0,10)T,目標函數(shù)最優(yōu)值為100。如單位產(chǎn)品A的利潤改變?yōu)?0時，得到答案如圖1.30所示。圖1.30單位產(chǎn)品A的利潤改變?yōu)?0時最優(yōu)解單位產(chǎn)品A的利潤為10時，則最優(yōu)生產(chǎn)方案調(diào)整為X=(12,0,0)T,目標函數(shù)最優(yōu)值為120。當有多個目標函數(shù)價值系數(shù)發(fā)生變化時，與上面的方法類似，只需將改變后的價值系數(shù)代入Excel表格中，重新按下“規(guī)劃求解”，“求解”按鈕，馬上就可以得到答案。若令，得如圖1.31所示的最優(yōu)解。單位產(chǎn)品A的利潤改變?yōu)?，單位產(chǎn)品C的利潤C3改變?yōu)?時時，則最優(yōu)生產(chǎn)方案調(diào)整為X=(4,0,8)T,目標函數(shù)最優(yōu)值為96。1.6.2資源約束量b的靈敏度分析與影子價格（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.即當原材料甲的供應(yīng)量b1和原材料料乙的供應(yīng)量b2分別在區(qū)間[10,20]和[12,24]之間變化時,最優(yōu)基不變（即生產(chǎn)產(chǎn)品的品種不變，但生產(chǎn)數(shù)量及最優(yōu)值會發(fā)生變化，即生產(chǎn)方案發(fā)生改變）。當原材料甲的供應(yīng)量由12改變?yōu)闀r，最優(yōu)解與最優(yōu)值將如何變化呢？這時我們只需將變化后新的原材料甲的供應(yīng)量代入Excel表格中，重新按下“規(guī)劃求解”，“求解”按鈕，馬上就可以得到答案，如圖1.32所示。

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

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

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