教學(xué)課件-MBA數(shù)據(jù)模型與決策

管理科學(xué)概論管理科學(xué)的定義管理科學(xué)是對與定量因素有關(guān)的管理問題通過科學(xué)的方法進行輔助管理決策制定的一門學(xué)科.管理科學(xué)定義要點:1.定量因素有關(guān)的管理問題(研究范圍)2.科學(xué)的方法(研究的方法與手段)3.輔助管理決策制定(學(xué)科的地位)與管理學(xué)區(qū)別與聯(lián)系管理科學(xué)與管理學(xué)區(qū)別與聯(lián)系管理科學(xué)解決以定量為主,局部的,微觀層面的管理問題;

管理學(xué)是一個更大學(xué)科門類,通常解決以定性為主,全局的,宏觀層面的管理問題;兩者之間互相支持,不是對立的,實際問題往往需要定性與定量相結(jié)合.管理科學(xué)的歷史

管理科學(xué)通常又稱為運籌學(xué)(OperationsResearch)，它產(chǎn)生和快速發(fā)展的動力首先來自于第二次世界大戰(zhàn)的軍事活動。1940年英國召集了一些數(shù)學(xué)家、物理學(xué)家和工程專家等成立了第一個OperationResearch小組，研究一些武器的有效使用問題。后來，美國1942年也成立了17人的OperationsResearch小組。成功地解決了戰(zhàn)爭中的協(xié)調(diào)策略、武器效用和物資運輸?shù)葐栴}。正是由于OR產(chǎn)生的軍事背景和我國有“運籌帷幄”一詞，OperationResearch被譯為“運籌學(xué)”。管理科學(xué)的歷史戰(zhàn)后，運籌小組的專家們將戰(zhàn)時研究的理論和方法成功地應(yīng)用于解決經(jīng)濟管理中各類問題取得了很好的效果，一個歷程碑事件是G.B,Dantzig在1947年提出了解線性規(guī)劃的單純形法.運籌學(xué)的應(yīng)用范圍越來越廣，作用也越來越大，在企業(yè)管理、物資存貯、交通運輸、公共服務(wù)等領(lǐng)域都有運籌學(xué)應(yīng)用的成功范例。管理科學(xué)的歷史計算機的普及和發(fā)展加快了其應(yīng)用步伐運籌學(xué)與管理科學(xué)的主要國際性專業(yè)組織是運籌學(xué)與管理科學(xué)協(xié)會（INFORMS）,總部在美國，每年都舉辦大型研討會，還出版幾本著名的刊物。另外，幾十個成員國組成了國際運籌學(xué)聯(lián)盟(IFORS),所有成員國都在其國內(nèi)有運籌學(xué)組織。管理科學(xué)的特征

整體性特征科學(xué)性特征廣泛性特征最優(yōu)性特征綜合性特征管理科學(xué)的影響

管理科學(xué)已廣泛應(yīng)用于生產(chǎn)、交通、通訊、銷售和軍事等各個領(lǐng)域,包括中國在內(nèi)的世界上大多數(shù)國家和組織已成功運用管理科學(xué)方法解決了各個領(lǐng)域的實際問題,取得了很好的經(jīng)濟效益與社會效益。國際運籌學(xué)與管理科學(xué)協(xié)會(INFORMS)為管理科學(xué)成功應(yīng)用者而設(shè)立了弗蘭茨.厄德曼(FranzEdelman)獎,每年頒發(fā)一次,獎項授予全世界年度管理科學(xué)最佳應(yīng)用.管理科學(xué)的影響經(jīng)典的應(yīng)用包括:AT&T公司為公司商業(yè)用戶的電話銷售中心選址、IBM公司整合備件庫存的全國網(wǎng)絡(luò)以改進服務(wù)支持、Delta航空公司國內(nèi)航線的飛機類型優(yōu)化配置中國政府為滿足能源需求進行的大型項目優(yōu)化和排序等。(INFORMS)下屬的國際重要期刊Interfaces每年都有專門發(fā)表文章詳細介紹這些應(yīng)用成果,其它重要期刊如OperationResearch,ManagementScience等也有介紹一些管理科學(xué)應(yīng)用成果。管理科學(xué)的研究方法管理科學(xué)解決實際問題的核心方法是首先建立反映實際問題的模型，這種模型是實際問題的抽象描述，然后用數(shù)學(xué)或其它科學(xué)的方法給出模型的求解算法，再用計算機實現(xiàn)算法求解過程數(shù)學(xué)模型模型是實際問題某一方面的描述和抽象概括，以便人們?nèi)菀桌斫狻Ｋ豢紤]實際問題的若干主要因素，而忽略次要因素，比現(xiàn)實問題簡單，從而更能夠反映問題的本質(zhì)和各因素的內(nèi)在聯(lián)系模型有三種基本形式：形象模型、模擬模型和數(shù)學(xué)模型，管理科學(xué)中主要采用數(shù)學(xué)模型.數(shù)學(xué)模型數(shù)學(xué)模型首先將要進行的決策量化，引入一組決策變量，決策變量取不同的值代表不同的決策。根據(jù)決策的目的建立一個目標(biāo)函數(shù)以反映決策效果，并將實際問題的各因素及其相互關(guān)系歸納成一組數(shù)學(xué)表達式。管理科學(xué)求解問題步驟運用管理科學(xué)方法解決實際問題的過程如下：步驟1.

提出問題，并根據(jù)需要收錄有關(guān)數(shù)據(jù)信息。向管理者咨詢、鑒別所要考慮的問題以確定合理的目標(biāo)，然后根據(jù)要求收集一些關(guān)鍵數(shù)據(jù)，并對數(shù)據(jù)作相應(yīng)的分析。管理科學(xué)求解問題步驟步驟2

建立模型，引入決策變量，確定目標(biāo)函數(shù)（約束條件）。建模過程是一項創(chuàng)造性的工作，在處理實際問題時，一般沒有一個唯一正確的模型，而是有多種不同的方案。建模是一個演進過程，從一個初始模型往往需要不斷的完善漸漸演化成一個完整的數(shù)學(xué)模型。管理科學(xué)求解問題步驟我們對數(shù)學(xué)模型有兩個基本要求一是準(zhǔn)確性:

所建立的模型應(yīng)盡可能準(zhǔn)確地反映或描述所研究的問題(準(zhǔn)確性)；二是簡單性:

數(shù)學(xué)模型盡可能簡單，即模型能用已有方法求解。管理科學(xué)求解問題步驟步驟3.

從模型中形成一個對問題求解的算法。管理科學(xué)小組要在計算機上運行數(shù)學(xué)程序?qū)δＰ瓦M行求解，一般情況下能找到對模型求解的標(biāo)準(zhǔn)軟件。例如，對線性規(guī)劃問題已有Excel、Cplex、Lingo等標(biāo)準(zhǔn)軟件求解。有時要自己編寫程序。管理科學(xué)求解問題步驟步驟4.

測試模型并在必要時修正。在模型求解后，管理科學(xué)小組需要對模型進行檢驗，以保證該模型能準(zhǔn)確反映實際問題，需要檢驗?zāi)Ｐ吞峁┑慕馐欠窈侠?，所有主要相關(guān)因素是否已考慮，當(dāng)有些條件變化時，解如何變化等。管理科學(xué)求解問題步驟步驟5.

應(yīng)用模型分析問題以及提出管理建議。管理科學(xué)小組對模型求解并分析后，將相應(yīng)的最優(yōu)方案提交給管理者，由管理者做出決策。管理科學(xué)小組并不作管理決策，其研究只是對涉及的問題進行分析并向管理者提出建議。管理者還要考慮管理科學(xué)以外的眾多因素才能做出決策。管理科學(xué)求解問題步驟步驟6.

幫助實施管理決策。管理科學(xué)小組的建議被管理者采納以后，一旦做出管理決策一般要求管理科學(xué)小組幫助監(jiān)督?jīng)Q策方案的實施。管理科學(xué)小組必須和管理人員密切合作，隨時解決可能出現(xiàn)的新問題。數(shù)學(xué)規(guī)劃的建模原則之一:簡單性原則容易理解建立的模型不但要求建模者理解，還應(yīng)當(dāng)讓有關(guān)人員理解。這樣便于考察實際問題與模型的關(guān)系，使得到的結(jié)論能夠更好地應(yīng)用于解決實際問題。容易查找模型中的錯誤這個原則的目的顯然與(1)相關(guān)。常出現(xiàn)的錯誤有：書寫錯誤、公式錯誤。容易求解對線性規(guī)劃來說，容易求解問題主要是控制問題的規(guī)模，包括決策變量的個數(shù)和約束條件的個數(shù)。這條原則的實現(xiàn)往往會與(1)發(fā)生矛盾，在實現(xiàn)時需要對兩條原則進行統(tǒng)籌考慮。一個案例-盈虧平衡分析

特殊產(chǎn)品公司生產(chǎn)在商店銷售的昂貴而不常見的禮品，禮品是為那些已經(jīng)幾乎什么都有的富人生產(chǎn)的。公司管理部門需要決定是否生產(chǎn)這個新產(chǎn)品，如果生產(chǎn)的話要生產(chǎn)多少。盈虧平衡分析定量問題,相關(guān)數(shù)據(jù);固定成本c1=100萬元,變動成本c2=2600元,市場需求量s=?,單位收入w=4600元,生產(chǎn)能力,……建立數(shù)學(xué)模型:

決策變量X=產(chǎn)品的生產(chǎn)數(shù)量成本函數(shù)=c1+2600x(x>0)=0(x=0)盈虧平衡分析利潤C(x)=收入-成本

=4600x-(1000000+2600x)=2000x-1000000(x>0)決策目標(biāo):利潤最大化maxZ=C(x)

約束條件(1)X≥0(2)X≤S(3)生產(chǎn)能力約束

…….盈虧平衡分析盈虧平衡點x=500件若S>500,最優(yōu)解X=S

若S<500,最優(yōu)解X=0,不生產(chǎn)繼續(xù)考慮生產(chǎn)能力約束…..簡單案例與復(fù)雜案例方法思路一樣簡單問題-不需建模,經(jīng)驗重要,復(fù)雜問題經(jīng)驗失效..例如.某人做剪線實驗:

選10人,每人分別憑經(jīng)驗各剪1米,10米,30米…最后發(fā)現(xiàn)l米誤差小,30米誤差大.線性規(guī)劃線性規(guī)劃是一種幫助管理者制定決策的方法;在許多領(lǐng)域都有成功的應(yīng)用案例,它在模型上表現(xiàn)為一個線性的函數(shù)在一組線性約束條件下的求極大值或求極小值問題;最常見的三類問題是:資源分配問題;成本效益平衡問題和物流網(wǎng)絡(luò)配送問題.資源分配問題紅星重型機械廠的產(chǎn)品組合問題產(chǎn)品甲:需要原料A,原料B,設(shè)備工時;

產(chǎn)品乙:也需要原料A,原料B,設(shè)備工時;由于原料A,原料B,設(shè)備工時的數(shù)量有限,如何安排生產(chǎn),使獲利最大?問題

1.公司是否該生產(chǎn)這兩個產(chǎn)品?2如果生產(chǎn),產(chǎn)品生產(chǎn)組合如何?(各生產(chǎn)多少?)資源分配問題這是一個定量問題決策目標(biāo)---利潤最大化步驟1---收集相關(guān)數(shù)據(jù)如下:(見P10)甲乙資源總量原料A104原料B028設(shè)備工時2318單位利潤4萬元3萬元資源分配問題

步驟2---建立數(shù)學(xué)模型

1)決策變量—決策量化的手段

x1=產(chǎn)品甲的生產(chǎn)數(shù)量

x2=產(chǎn)品乙的生產(chǎn)數(shù)量

2)目標(biāo)函數(shù)---衡量決策效果(優(yōu)劣)的指標(biāo)

Z=4x1+3x2

求最大值

3)約束條件

x1≤6(原料A數(shù)量約束)2x2≤8(原料B數(shù)量約束)2x1+3x2≤18(設(shè)備工時約束)x1,x2≥0(非負約束)建立數(shù)學(xué)規(guī)劃模型的四個步驟

明確問題，確定決策變量；決策變量是構(gòu)成解決方案的要素或單元，決策變量的組合構(gòu)成一個可行解決方案。

明確約束條件并用決策變量的等式或不等式表示；盡可能分類描述，防止差錯和遺漏

用決策變量的函數(shù)表示目標(biāo)，并確定是求極大（Max）、極?。∕in）還是特定值；

根據(jù)決策變量的物理性質(zhì)研究變量是否有非負性或上下界。資源分配問題資源分配（resource-allocation）問題是將有限的資源分配到各種活動中去的線性規(guī)劃問題。這一類問題的共性是在線性規(guī)劃模型中每一個函數(shù)限制均為資源限制(resourceconstraint),并且每一種有限資源都可以表現(xiàn)為如下的形式：

使用的資源數(shù)量

可用的資源數(shù)量資源分配問題例1的數(shù)學(xué)模型可以用代數(shù)形式描述如下：這實際上是求一個線性函數(shù)在一組線性約束條件下的最大值問題，我們稱之為線性規(guī)劃問題模型。資源分配問題我們稱x1、x2為決策變量，Z=4x1+3x2為目標(biāo)函數(shù)，約束（1.1）-（1.3）為函數(shù)約束，約束（1.4）為非負約束。決策變量的任何一個取值稱為模型的一個解，若解滿足所有約束條件，則稱為可行解，反之（至少違反一個約束條件），稱其為非可行解，使目標(biāo)函數(shù)值最大化的可行解稱為最優(yōu)解。成本收益平衡問題成本收益平衡問題（Cost-benefit-trade-offProblem

）是一類線性規(guī)劃問題，這類問題中，通過選擇各種活動水平的組合，從而以最小的成本來實現(xiàn)最低可接受的各種收益的水平。這類問題的共性是，所有的函數(shù)約束均為收益約束，并具有如下的形式：

完成的水平

最低可接受的水平成本效益平衡問題某飼料公司希望用玉米、紅薯兩種原料配制一種混合飼料，各種原料包含的營養(yǎng)成份和采購成本都不相同，公司管理層希望能夠確定混合飼料中各種原料的數(shù)量，使得飼料能夠以最低的成本達到一定的營養(yǎng)要求。研究者根據(jù)這一目標(biāo)收集到的有關(guān)數(shù)據(jù)如下：

成本效益平衡問題為建立線性規(guī)劃模型，我們引入變量如下：x1=混合飼料中玉米的數(shù)量x2=混合飼料中紅薯的數(shù)量成本效益平衡問題目標(biāo)函數(shù)是Z=0.8x1+0.5x2，表示飼料的成本函數(shù)，即如何確定x1、x2使得成本Z=0.8x1+0.5x2最低且滿足最低營養(yǎng)要求的約束，這些約束條件是：碳水化合物需求：8x1+4x2≥20蛋白質(zhì)需求：3x1+6x2≥18維他命需求：x1+5x2≥16另有非負約束：x1≥0，x2≥0成本效益平衡問題因此，這個問題的線性規(guī)劃模型為：物流網(wǎng)絡(luò)配送問題偉達物流公司需將甲、乙、丙三個工廠生產(chǎn)的一種新產(chǎn)品運送到A、B兩個倉庫，甲、乙兩個工廠的產(chǎn)品可以通過鐵路運送到倉庫A，數(shù)量不限；丙工廠的產(chǎn)品可以通過鐵路運送到倉庫B，同樣，產(chǎn)品數(shù)量不限。由于鐵路運輸成本較高，公司也可考慮由獨立的卡車來運輸，可將多達80個單位的產(chǎn)品由甲、乙、丙三個工廠運到一個配送中心，再從配送中心以最多90單位的載貨量運到各個倉庫。公司管理層希望以最小的成本來運送所需的貨物。物流網(wǎng)絡(luò)配送問題需要收集每條線路上的單位運輸成本和各工廠產(chǎn)品的產(chǎn)量以及各倉庫分配量等數(shù)據(jù)：

物流網(wǎng)絡(luò)配送問題為了更清楚地說明這個問題，我們用一個網(wǎng)絡(luò)圖來表示該網(wǎng)絡(luò)配送問題（見圖2-1）。圖中節(jié)點v1、v2、v3表示甲、乙、丙三個工廠，節(jié)點v4表示配送中心，節(jié)點v5、v6表示兩個倉庫；每一條箭線表示一條可能的運輸路線，并給出了相應(yīng)的單位運輸成本，對運輸量有限制的路線的最大運輸能力也同時給出。物流網(wǎng)絡(luò)配送問題物流網(wǎng)絡(luò)配送問題我們要解決的是各條路線最優(yōu)運輸量，引入變量fij表示由vi經(jīng)過路線(vi,vj)運輸?shù)絭j的產(chǎn)品數(shù)。問題的目標(biāo)是總運輸成本最小化，總運輸成本可表示為：總運輸成本=7.5f15+3f14+8.2f25+3.5f24+2.3f45+3.4f34+2.3f46+9.2f36物流網(wǎng)絡(luò)配送問題相應(yīng)的約束條件包括對網(wǎng)絡(luò)中的每個節(jié)點的供求平衡約束。對生產(chǎn)節(jié)點v1、v2、v3來說，由某一節(jié)點運出的產(chǎn)品數(shù)量等于其產(chǎn)量，即：

f15+f14=100

f25+f24=80

f34+f36=70物流網(wǎng)絡(luò)配送問題對配送中心v4，運進的產(chǎn)品數(shù)量等于運出的產(chǎn)品數(shù)量：

f14+f24+f34=f45+f46對倉庫v5、v6，運進的產(chǎn)品數(shù)量等于其需求量

f15+f25+f45=120

f46+f36=130物流網(wǎng)絡(luò)配送問題此外，對網(wǎng)絡(luò)中有運輸容量限制的路線的約束是：該路線上的運輸產(chǎn)品數(shù)量不超過該線路的運輸能力，即：f14≤80，f24≤80，f34≤80，f45≤90，

f46≤90。并且，所有fij≥0（非負約束）。物流網(wǎng)絡(luò)配送問題共同的特征從以上幾個例子可以看出，線性規(guī)劃問題有如下共同的特征：每個問題都用一組決策變量（x1,x2,...,xn

），這組決策變量的值都代表一個具體方案；有一個衡量決策方案優(yōu)劣的函數(shù)，它是決策變量的線性函數(shù)，稱為目標(biāo)函數(shù)。按問題不同，要求目標(biāo)函數(shù)實現(xiàn)最大化或最小化；存在一些約束條件，這些約束條件包括①函數(shù)約束，可以用一組決策變量的線性函數(shù)（稱為約束函數(shù)）大于等于“≥”、小于等于“≤”或等于“=”一個給定常數(shù)（稱為右端項）；②決策變量的非負約束。一般形式線性規(guī)劃的一般形式為：資源分配問題一般形式資源分配問題是將有限的資源分配從事各種活動的線性規(guī)劃問題，其一般形式可以描述為：管理層計劃用m種資源去從事n種活動，通過收集每種資源的總量和每種活動單位資源使用量以及單位貢獻等數(shù)據(jù)如下表所示，來確定活動的數(shù)量使得在資源許可的條件下貢獻最大。資源分配問題一般形式資源分配問題一般形式我們用表示xj第j種活動的數(shù)量(水平)，則目標(biāo)函數(shù)最大化。對于第i種資源，我們有約束條件：即資源消耗量不超過的資源總量資源分配問題一般形式因此，這類問題的數(shù)學(xué)模型為：成本效益平衡問題一般形式以上所討論的成本效益平衡問題是通過選擇各種活動水平的組合，從而以最小的成本實現(xiàn)最低可接受的各種效益水平。該問題的一般形式可描述為：管理層計劃用n種活動去提高m種效益的水平，通過調(diào)查得知每種活動對各種效益的單位貢獻、每種活動的單位成本以及每種效益的最低可接受水平如表成本效益平衡問題一般形式成本效益平衡問題一般形式我們用表示xj第j種活動的數(shù)量(水平)，則目標(biāo)函數(shù)

最小化。對于第i種效益，我們有

成本效益平衡問題一般形式因此，這類問題的數(shù)學(xué)模型為：

物流網(wǎng)絡(luò)配送問題一般形式物流網(wǎng)絡(luò)配送問題一般形式可描述為：假定在一n個頂點m條?。ň€路）的運輸網(wǎng)絡(luò)中，有若干發(fā)點發(fā)送一定數(shù)量的物資流，同時又有若干收點接收這些物資流。由于每條弧運輸費用不同，運輸能力也有一定限制，管理者希望以最小的運輸成本完成由發(fā)點到收點的運輸配送。物流網(wǎng)絡(luò)配送問題一般形式我們用fij表示由vi經(jīng)過路線(vi,vj)運輸?shù)絭j的流量，

Cij表示線路(vi,vj)的最大運輸能力（容量限制），

wij表示由頂點vi沿線路(vi,vj)流向vj的單位流量成本。物流網(wǎng)絡(luò)配送問題一般形式物流網(wǎng)絡(luò)配送問題模型為:線性規(guī)劃問題的圖解法

當(dāng)決策變量只有兩個時，線性規(guī)劃問題可以用在平面上作圖的方法求解，這種方法稱為圖解法。由于這種方法簡單、直觀、容易理解，所以有助于了解線性規(guī)劃問題的實質(zhì)和求解的原理?，F(xiàn)用紅星重型機械廠的產(chǎn)品組合問題中的線性規(guī)劃來說明圖解法線性規(guī)劃問題的圖解法

紅星重型機械廠的產(chǎn)品組合問題的線性規(guī)劃問題：線性規(guī)劃問題的圖解法我們首先建立x1Ox2坐標(biāo)平面（見圖2-2），坐標(biāo)系上橫軸是x1軸，縱軸是x2軸。由非負約束x1≥0，x2≥0可知，所有可行解的集合（稱為可行域）應(yīng)在第一象限。然后，我們要逐個地查看每個函數(shù)約束都允許的非負解，再考慮所有的約束條件。第一個函數(shù)約束x1≤6，截取x1軸的直線x1=6的線上或線左邊的解是滿足這個約束條件的；第二個約束2x2≤8，有相似的結(jié)果，即x2=4線及下方的解滿足這個約束。我們將函數(shù)約束條件的邊界直線稱為約束邊界，相應(yīng)的方程稱為約束邊界方程

線性規(guī)劃問題的圖解法線性規(guī)劃問題的圖解法例1確定了可行域以后，我們希望找出哪些解是最優(yōu)解，即使目標(biāo)函數(shù)Z=4x1+3x2盡可能大的可行解。我們給目標(biāo)函數(shù)一個值，例如給定Z=12，可以在圖上畫出一條直線4x1+3x2=12（見圖1-3），在直線上的任一點處，對應(yīng)的目標(biāo)函數(shù)值均為12，故稱該直線為目標(biāo)函數(shù)的等值線。Z=12只是目標(biāo)函數(shù)的一個給定值，對于其它Z的給定值，如Z=15也可在圖上畫出一條直線4x1+3x2=15，顯然，對于Z的不同給定值k，4x1+3x2=k是一組平行的直線族，當(dāng)k的值由小變大時，目標(biāo)函數(shù)的等值線平等移動，它與可行域的最后一個交點（一般是可行域的一個頂點）就是所求的最優(yōu)點，即圖2-3中的B點線性規(guī)劃問題的圖解法線性規(guī)劃問題的圖解法由上可以看出，線性規(guī)劃問題的最優(yōu)解出現(xiàn)在可行域的一個頂點上，此時線性規(guī)劃問題有唯一最優(yōu)解。但有時線性規(guī)劃問題還可能出現(xiàn)有無窮多個最優(yōu)解、無有限最優(yōu)解、甚至沒有可行解的情況，我們?nèi)酝ㄟ^例子說明。線性規(guī)劃問題的圖解法（1）無窮多最優(yōu)解。若將上例中的目標(biāo)函數(shù)變?yōu)榍驧axZ=4x1+6x2，則目標(biāo)函數(shù)的等值線與邊界線2x1+3x2=18平行，線段BC上的任意一點都使Z取得相同的最大值，此時線性規(guī)劃問題有無窮多最優(yōu)解2-4所示。線性規(guī)劃問題的圖解法線性規(guī)劃問題的圖解法線性規(guī)劃問題的圖解法無可行解線性規(guī)劃的計算機求解Excel是分析和求解線性規(guī)劃問題一個很好的工具，它不僅可以很方便地將線性規(guī)劃模型所有的參數(shù)錄入電子表格，而且可以利用規(guī)劃求解工具迅速找到模型的解。最重要的是，在解好的模型中，任何參數(shù)的改變都可以立即反映到模型的解中，在不重新應(yīng)用求解工具的情況下就可以知道許多信息，當(dāng)然，即使重新求解也只是點一下鼠標(biāo)就可以了線性規(guī)劃的計算機求解作為office家族的一員，Excel的普及性和易學(xué)性也會讓讀者感到利用計算機求解線性規(guī)劃十分容易。當(dāng)然，除Excel外還有很多求解線性規(guī)劃的計算機軟件，但Excel強大的功能、普及性和易學(xué)性足以滿足學(xué)習(xí)運籌學(xué)的讀者理解線性規(guī)劃的計算機求解方法、幫助讀者們學(xué)習(xí)解決線性規(guī)劃問題的要求。線性規(guī)劃的計算機求解線性規(guī)劃的計算機求解線性規(guī)劃的計算機求解線性規(guī)劃的計算機求解線性規(guī)劃的計算機求解線性規(guī)劃的計算機求解線性規(guī)劃的計算機求解線性規(guī)劃的計算機求解線性規(guī)劃的計算機求解農(nóng)場灌溉問題某公司有四個農(nóng)場，每個農(nóng)場的耕地作物需要用水灌溉，因灌溉條件限制，農(nóng)場的最大水資源供應(yīng)量有一定限制，各農(nóng)場的總耕地面積與最大水資源供應(yīng)量如表3-1所示。該地區(qū)種植的作物有棉花、玉米和高粱，三種農(nóng)作物每種作物每單位種植面積的凈收入和耗水量以及每種作物最大允許種植面積如表3-2所示。由于水資源短，公司規(guī)定每個農(nóng)場受灌溉面積占農(nóng)場總耕地面積的比例相同，公司決策問題還是如何確定各農(nóng)場種植各種作物的面積，使得公司總收入最大。例1.農(nóng)場灌溉問題例1.農(nóng)場灌溉問題

我們首先建立此問題的線性規(guī)劃模型。由于此問題是決定四個農(nóng)場中每個農(nóng)場種植三種農(nóng)作物的面積，我們引入決策變量xij（i=1，2，3，4；j=1，2，3）表示第i個農(nóng)場種植第j種作物的面積，目標(biāo)是使總收入Z=800(x11+x21+x31+x41)+600(x12+x22+x32+x42)+450(x13+x23+x33+x43)最大化例1.農(nóng)場灌溉問題滿足下列約束條件：1).農(nóng)場的耕地面積約束x11+x12+x13≤4000(農(nóng)場1)x21+x22+x23≤6000(農(nóng)場2)x31+x32+x33≤5000(農(nóng)場3)x41+x42+x43≤4500(農(nóng)場4)例1.農(nóng)場灌溉問題2).農(nóng)場最大供水量約束2x11+

1.5x12+x13≤6000(農(nóng)場1)2x21+1.5x22+x23≤9000(農(nóng)場2)2x31+

1.5x32+x33≤5500(農(nóng)場3)2x41+1.5x42+x43≤5000(農(nóng)場4)例1.農(nóng)場灌溉問題3)農(nóng)作物的種植面積約束x11+x21+x31+x41≤6000（農(nóng)作物1，棉花）x12+x22+x32+x42≤5500（農(nóng)作物2，玉米）x13+x23+x33+x43≤5000（農(nóng)作物3，高粱）即各農(nóng)作物種植面積不超過最大允許種植面積。

例1.農(nóng)場灌溉問題4)種植作物面積占總耕地面積比例約束即各農(nóng)場種植作物面積（灌溉面積）占總耕地面積的比例相同。5)決策變量的非負約束xij

≥0，i=1，2，3，4；j=1，2，3。例1.農(nóng)場灌溉問題例2.證券投資問題一證券投資者將1000萬元資金用于證券投資，已知各種證券（A、B、C、D、E、F）的評級、到期年限、每年稅后收益如表所示。管理層對該投資者提出下列要求：國債投資額不能少于300萬元；投資證券的平均評級不超過1.5；投資證券的平均到期年限不超過5年。問：每種證券投資多少可以使得稅后收益最大？例2.證券投資問題例2.證券投資問題引入決策變量xA、xB、xC、xD、xE、xF分別表示證券A、B、C、D、E、F的投資金額（單位：萬元），相應(yīng)的目標(biāo)函數(shù)（稅后收益）為：Z=9×0.043xA+12×0.044xB+5×0.032xC+4×0.03xD+3×0.032xE+4×0.045xF約束條件為：資金總額約束：

xA+xB+xC+xD+xE+xF≤1000國債投資額約束：

xC+xD≥300例2.證券投資問題證券平均評級約束：

這是一個非線性約束，容易轉(zhuǎn)化為以下線性約束：

0.5xA+0.5xB–0.5xC–0.5xD+2.5xE+3.5xF≤0證券平均到期年限約束：

它等價于線性約束：

4xA+7xB–xD–2xE–xF≤0非負約束:xA≥0，xB≥0，xC≥0，xD≥0，xE≥0xF≥0例2.證券投資問題例3.話務(wù)員排班問題某尋呼公司雇用了多名話務(wù)員工作，他們每天工作3節(jié)，每節(jié)3小時，每節(jié)開始時間為午夜、凌晨3點鐘、凌晨6點鐘，上午9點、中午12點、下午3點、6點、9點，為方便話務(wù)員上下班，管理層安排每位話務(wù)員每天連續(xù)工作3節(jié)，根據(jù)調(diào)查，對于不同的時間，由于業(yè)務(wù)量不同，需要的話務(wù)員的人數(shù)也不相同，公司付的薪水也不相同，有關(guān)數(shù)據(jù)見表。例3.話務(wù)員排班問題問：如何安排話務(wù)員才能保證服務(wù)人數(shù)，又使總成本最低？例3.話務(wù)員排班問題解：這個問題實際上是一個成本效益平衡問題。管理層在向客戶提供滿意服務(wù)水平的同時要控制成本，因此必須尋找成本與效益的平衡。由于每節(jié)工作時間為3小時，一天被分為8班，每人連續(xù)工作3節(jié)，各班時間安排如下表：例3.話務(wù)員排班問題例3.話務(wù)員排班問題為了建立數(shù)學(xué)模型，對應(yīng)于一般成本效益平衡問題，我們首先必須明確包含的活動數(shù)目，活動一個單位是對應(yīng)于分派一個話務(wù)員到該班次收，效益的水平對應(yīng)于時段。收益水平就是該時段里上下班的話務(wù)員數(shù)目，各活動的單位效益貢獻就是在該時間內(nèi)增加的在崗位話務(wù)員數(shù)目。我們給出下列成本效益平衡問題參數(shù)表：例3.話務(wù)員排班問題例3.話務(wù)員排班問題決策變量Xi表示分派到第班的話務(wù)員人數(shù)（i=1，2，3，4，5，6，7，8），約束條件為：0-3時間段：3-6時間段：6-9時間段：9-12時間段：12-15時間段：例3.話務(wù)員排班問題15-18時間段：18-21時間段：21-0時間段：非負約束：目標(biāo)函數(shù)為最小化成本：

例3.話務(wù)員排班問題例4.多階段生產(chǎn)安排問題

南方機電制造公司為全國各地生產(chǎn)一種大型機電設(shè)備，按照公司的訂單合同，不久要交付使用一定數(shù)量的機電設(shè)備，所以有必要制定為期6個月的設(shè)備生產(chǎn)計劃。根據(jù)合同，公司必須在未來6個月中每個月底交付一定數(shù)量的機電設(shè)備，由于原料價格、生產(chǎn)條件、保修和維修工作等安排不同，每月的生產(chǎn)能力和生產(chǎn)成本也不同，當(dāng)然，可以在成本較低的月份多生產(chǎn)一些設(shè)備，但在供給客戶之前必須存放，需要付一定的存貯費用。管理層需要制定出一個逐月生產(chǎn)計劃，使生產(chǎn)和存貯的總成本達到最小。例4.多階段生產(chǎn)安排問題管理科學(xué)小組通過調(diào)查收集到每單位生產(chǎn)成本、每月單位存貯費、每月需求量、最大生產(chǎn)能力等數(shù)據(jù)（見表)。例4.多階段生產(chǎn)安排問題解：管理層需要作出的決策是每個月生產(chǎn)多少臺設(shè)備，因此我們引入決策變量xj表示第個月生產(chǎn)機電設(shè)備的臺數(shù)（j=1，2，3，4，5，6）。為了建立此問題的一般數(shù)學(xué)模型，我們用dj表示第j月的需求量；用lj表示第j月的最大生產(chǎn)能力；用cj表示第j月的單位生產(chǎn)成本；用hj表示第j月的單位存貯成本；用fj表示第j月的最大存貯量。例4.多階段生產(chǎn)安排問題由最大生產(chǎn)能力限制，我們?nèi)菀椎玫郊s束：xj≤lj,j=1，2，3，4，5，6用Ij表示第月底的庫存量（j=1，2，3，4，5，6），由最大存貯量約束，我們有：Ij≤fj,j=1，2，3，4，5，6各個月份之間生產(chǎn)量、需求量和存貯量之間的關(guān)系可由下圖（圖2-15）表示：例4.多階段生產(chǎn)安排問題容易得到下列約束：例4.多階段生產(chǎn)安排問題另外有非負約束：

xj≥0,Ij≥0，j=1，2，3，4，5，6目標(biāo)為總成本最小化:例4.多階段生產(chǎn)安排問題例5.下料問題某工廠要做100套鋼架，每套用長為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長7.4m，問：應(yīng)如何下料，可使所用原料最省？解:考慮下列各種下料方案（按一種邏輯順序給出）把各種下料方案按剩余料頭從小到大順序列出假設(shè)x1,x2,x3,x4,x5分別為上面前5種方案下料的原材料根數(shù)。我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：

Minz=x1+x2+x3+x4+x5

約束條件：s.t.

x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0模型1假設(shè)x1,x2,x3,x4,x5,x6,x7,x8分別為上面前8種方案下料的原材料根數(shù)。我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：

Minz=0.1x1+0.3x2+0.9x3+1.1x5+0.2x6+0.8x7+1.4x8約束條件：

s.t.2x1+x2+x3+x4≥1002x2+x3+3x5+2x6+x7≥100

x1+x3+3x4+2x6+3x7+4x8≥100x1,x2,x3,x4,x5,x6,x7,x8≥0，整數(shù)模型2假設(shè)x1,x2,x3,x4,x5,x6,x7,x8分別為上面前8種方案下料的原材料根數(shù)。我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：

Minz=x1+x2+x3+x5+x6+x7+x8約束條件：

s.t.2x1+x2+x3+x4≥1002x2+x3+3x5+2x6+x7≥100

x1+x3+3x4+2x6+3x7+4x8≥100x1,x2,x3,x4,x5,x6,x7,x8≥0，整數(shù)模型3例6醫(yī)藥公司的中草藥配方問題

安康醫(yī)藥公司考慮配制一種中成藥;市場上有八種中草藥材包含該中成藥所需要的特定成份,公司準(zhǔn)備采購一些中草藥來配制這種中成藥，要求配制后的中成藥所包含三種特定成份(不妨設(shè)為成份A、成份B和成份C)分別為39、36、38。由于每種中草藥材包含的成份不同,采購成本也不同;公司管理層希望以最低的成本來完成中成藥的配制;各個中草藥材(每單位)包含的三種成份含量及單位采購成本數(shù)學(xué)建模決策變量Xi表示第種草藥在中成藥中的使用量（i=1，2，3，4，5，6,7,8）。為了使成本最低我們有:目標(biāo)函數(shù)Z=10x1+8x2+16x3+11x4+15x5+10x6+9x7+12x8求極小化約束條件2x1+5x2+5x3+4x4+5x5+4x6+3x7+7x8=393x1+3x2+2x3+2x4+4x5+2x6+2x7+3x8=364x1+3x2+3x3+3x4+4x5+3x6+x7+2x8=38Xi

≥0

,i=1,2,3…..8.安康醫(yī)藥公司的中草藥配方問題的Excel規(guī)劃求解

討論:為什么8種中草藥,最優(yōu)方案只選了三種呢?(草藥1,草藥2和草藥7)事實上,由于這個問題只有三個函數(shù)約束(成份A、成份B和成份C),三個等式約束看作一個線性方程組:2x1+5x2+5x3+4x4+5x5+4x6+3x7+7x8=393x1+3x2+2x3+2x4+4x5+2x6+2x7+3x8=364x1+3x2+3x3+3x4+4x5+3x6+x7+2x8=38討論:為什么8種中草藥,最優(yōu)方案只選了三種呢?若將第i種草藥三種成份含量看作一個三維向量Pi則:由線性代數(shù)知識我們知道向量組P1,P2,P7

線性無關(guān)且構(gòu)成三維向量空間的一個極大無關(guān)組;任何一個三維向量P可由的線性組合來表示出來,即:存在唯一的一組數(shù),k1,k2,k3,使得:P=k1P1+k2P2+k3P3討論例如:對于第5種草藥三種成份含量,可以表示為一個三維向量P5,討論這就意味著一個單位的第5種草藥,其成份等價于0.5個單位的第1種草藥+0.5個單位的第2種草藥+0.5個單位的第7種草藥;即:一個單位的第5種草藥,可由0.5個單位的第1種草藥,0.5個單位的第2種草藥和0.5個單位的第7種草藥組合而成;由于這種組合的成本為0.5X10+0.5X8+0.5X9=13.5元,低于第5種草藥的單位成本(15元);因此,從成本最低的角度出發(fā)中成藥的最優(yōu)方案中不會選用第5種草藥.討論由于此問題的約束條件個數(shù)為3,方程組每個變量系數(shù)向量的維數(shù)為3,因而,極大無關(guān)組包含向量的個數(shù)一定是3個;不管有多少候選草藥,最終只需要選3種,其它草藥的成份都可以由這三種“組合”而成.在方程組中，只要選定了哪三種，意味著同時確定了其余的均不在選擇之列討論令沒有入選的其余5種草藥在中成藥中的數(shù)量為零，即:x3=x4=x5=x6=x8=0此時方程組變?yōu)橹缓齻€變量的方程組:2x1+5x2+3x7=393x1+3x2+2x7=364x1+3x2+x7=38討論可以求解得到其唯一解:X1=6.5,x2=2.5,x7=4.5.這就是我們的最優(yōu)配方.因此,只要我們能確定是哪三種中草藥入圍最優(yōu)配方,通過解一個方程組就可以得到最優(yōu)方案了.但是,我們有8種候選草藥,如果選三種來“組合”,最多可能有種,為什么最優(yōu)的方案是第1種草藥、第2種草藥和第7種草藥,而不是其它的三種呢?討論其它草藥i成份含量向量由線性組合來表出后,組合代替的成本不高于草藥i的單位采購成本.例如:本例中第5種草藥的單位成本為12元時(低于13.5元的組合成本),第1種草藥、第2種草藥和第7種草藥這種“組合”就不是為最優(yōu)的選擇了;我們重新用Excel“規(guī)劃求解”來解這個問題,得到最優(yōu)解，x1=4,x5=5,x7=2最優(yōu)的方案是第一種草藥4單位、第五種草藥5單位和第七種草藥2單位就可以滿足三種成份需要，這樣的方案成本可達到最低，是118元。單純形法線性規(guī)劃問題是求一個線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題。目標(biāo)函數(shù)根據(jù)實際問題的要求可能求最大化也可能是求最小化；每一個函數(shù)約束分為等價約束即約束函數(shù)=右端項和不等式約束即約束函數(shù)右端項或約束函數(shù)右端項。因此，線性規(guī)劃問題的形式有許多種，它們之間也可以相互轉(zhuǎn)化.單純形法為了方便討論，我們將選擇線性規(guī)劃問題的如下形式為標(biāo)準(zhǔn)形式：MaximizeZ=c1x1

+c2x2+...+cnxn,

a11x1+a12x2+...+a1nxn=b1

a21x1+a22x2+...+a2nxn=

b2

.........

am1x1+am2x2+...+amnxn=bm

x1

>0,x2>0,

...

,xn>0.單純形法1)目標(biāo)函數(shù)的轉(zhuǎn)化若原問題的目標(biāo)函數(shù)是求最小化，即:minimizeZ=c1x1

+c2x2+...+cnxn,

則可將目標(biāo)函數(shù)乘以-1，等價轉(zhuǎn)化為求如下最大化問題：

Maximize-Z=-c1x1

-c2x2-...–cnxn

轉(zhuǎn)化后的問題與原問題有相同的最優(yōu)解單純形法2)不等式約束轉(zhuǎn)化為等式約束

(1)如果約束條件是線性不等式:a11x1+a12x2+...+a1nxn≤b1

則通過引入松弛變量xn+1，將其轉(zhuǎn)化為等價的等式約束條件:a11x1+a12x2+...+a1nxn+xn+1=b1單純形法(2)如果約束條件是線性不等式:a11x1+a12x2+...+a1nxn

≥b1

則通過引入剩余變量xn+1≥

0

，將其轉(zhuǎn)化為等價的等式約束條件:a11x1+a12x2+...+a1nxn-xn+1=b1單純形法3)變量約束的轉(zhuǎn)換在標(biāo)準(zhǔn)形式中，我們要求每個決策變量滿足非負約束，如果原問題中某個變量是自由變量（即無非負限制）則可令

xi=x’i–x’’I,

x’I≥

0,

x’’i≥

0.

代入原問題，即在原問題中將用兩個非負變量之差代替

單純形法例：將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式:

首先將最小化問題乘以-1，轉(zhuǎn)化為最大化問題,在第一約束中引入松弛變量x4，第二個約束中引入剩余變量x5，再令自由變量x2=x’2–x”2，并將第三約束方程兩邊同乘以（-1),得到與原問題等價的線性規(guī)劃標(biāo)準(zhǔn)形式：單純形法單純形法化為標(biāo)準(zhǔn)型后:MaximizeZ=c1x1

+c2x2+...+cnxn,

a11x1+a12x2+...+a1nxn=b1

a21x1+a22x2+...+a2nxn=

b2

.........

am1x1+am2x2+...+amnxn=bm

x1

>0,x2>0,

...

,xn>0.一般來說,m<..<n,即:約束個數(shù)小于變量個數(shù)單純形法由上章討論可知,最優(yōu)解里,x1,x2,x3,…xn,中一般會有m個不為0(我們稱為基變量,用xB),其余n-m個必須為0(我們稱其為非基變量xN),將約束方程組系數(shù)矩陣A分為兩塊(B,N),

其中B為基變量xB系數(shù)子矩陣,為mXm方陣

N為非基變量xN系數(shù)子矩陣,為mX(n-m)矩陣

單純形法我們希望找到最優(yōu)的xB

即:確定xB包含,x1,x2,x3,…xn,中哪m個,(同時也確定xN包含,x1,x2,…xn,中剩余的n-m個)

然后令xN=0,

在約束方程組中解出xB

可以枚舉,最多有組合數(shù)單純形法例紅星重型機械廠的產(chǎn)品組合問題的線性規(guī)劃問題引入松弛變量化為如下標(biāo)準(zhǔn)形式：單純形法故約束系數(shù)矩陣單純形法由于P3,P4,P5線性無關(guān),故B0是線性規(guī)劃的一個基。對于基B0

，x3,x4,x5是基變量，x1,x2,是非基變量。單純形法由于P2,P3,P4,線性無關(guān),也是線性規(guī)劃的一個基。對于基基B1，x2,x3,x4,是基變量，x1,x5是非基變量單純形法因此，約束方程組變?yōu)閱渭冃畏ㄓ捎贐可逆，將左乘以上式的兩邊得:令xN=0，則

此時約束方程組有一個特殊形式的解,稱為線性規(guī)劃的基本解

單純形法下面我們給出例2中基陣、基本解、基本可行解以及可行區(qū)域頂點之間的對應(yīng)關(guān)系基陣(P3,P4,P5）基本可行解x3,=6,

x4,=8,x5=18,x1,=

x2,=

0,對應(yīng)可行區(qū)域頂點O(0,0)

基陣（

P2P3,P5）基本可行解(0,4,6,0,6)對應(yīng)可行區(qū)域頂點E(0,4)

基陣（

P1P2P4,）基本可行解(6,2,0,4,0)對應(yīng)可行區(qū)域頂點B(6,2)

基陣（

P1P3,P4,）,基本解(9,0,-3,8,0)對應(yīng)頂點A(9,0)……………….另外，A的另外兩個m=3階子矩陣（P2,P4,P5

）和（P1,P3,P5）不可逆，不能構(gòu)成基陣.單純形法事實上，對于一般的線性規(guī)劃問題（m個約束，n個決策變量）有類似的特性：每個基本可行解對應(yīng)于可行域的頂點?？尚杏蛑邢噜彽膬蓚€頂點對應(yīng)基陣中只有一個基向量不同，其余的個基向量相同。由于線性規(guī)劃的最優(yōu)解是在可行域的頂點獲得，由頂點與基可行解的對應(yīng)關(guān)系，我們有以下線性規(guī)劃的基本定理：線性規(guī)劃問題如果存在最優(yōu)解，則一定存在一個基本可行解是最優(yōu)解。單純形法單純形法一般從可行域一個頂點（通常是原點）出發(fā)，試圖在其相鄰的可行域頂點中找目標(biāo)函數(shù)值更好的頂點，若在某頂點的相鄰的頂點中找不出使目標(biāo)函數(shù)有改進的頂點，則現(xiàn)有頂點就是最優(yōu)解。單純形法新的基陣變?yōu)锽=（

P1,P2,P4,），xB=(x1,x2,x4）為基變量,x3,x5將看作自由變量，用高斯消元法將原約束方程組寫為:單純形法將上式代入Z=4x1+3x2中得:Z=30-2x3–x5令xN=(x3,x5)=0,得基本可行解X=(6,2,0,4,0),Z’=30

由于非基變量在目標(biāo)函數(shù)中系數(shù)均為小于等于零，故X=(6,2,0,4,0)是線性規(guī)劃問題最優(yōu)解.

線性規(guī)劃應(yīng)用線性規(guī)劃在很多領(lǐng)域都有應(yīng)用,除經(jīng)典應(yīng)用模型外,一些較為復(fù)雜應(yīng)用案例來進一步說明線性規(guī)劃建模技術(shù)與用Excel求解方法.混合問題在生產(chǎn)安排問題中,管理層有時必須決定怎么混合兩類以上的資源來生產(chǎn)多種產(chǎn)品,最終產(chǎn)品中包含資源中一種以上的基本成份,而且成品包含一定比例的各類資源;因此,管理層要決定每類資源的采購量,使得在成本最低的條件下滿足產(chǎn)品規(guī)格以及生產(chǎn)該產(chǎn)品的需求:這類問題通常稱之為混合問題,廣泛應(yīng)用于石油、化工和食品等行業(yè).巨斯特石油公司混合問題巨斯特石油公司要生產(chǎn)兩種汽油產(chǎn)品,一種是一般的汽油,另一種是特殊的汽油,公司煉油廠希望通過合成4類石油成份來生產(chǎn)這兩種汽油產(chǎn)品;這些汽油的售價不同,4種石油成份成本也不同;公司希望確定一種混合這4類石油成份以生產(chǎn)兩種汽油產(chǎn)品的方案來獲取最大的利潤.巨斯特石油公司混合問題這類混合問題是要決定一般汽油和特殊汽油的每類石油成份的用量分別是多少.明顯是與定量因素有關(guān)的決策問題;希望通過調(diào)研收集如下相關(guān)數(shù)據(jù):(1)每類石油成份單位成本及供應(yīng)量;(2)每種汽油產(chǎn)品售價以及對各類石油成份的要求;巨斯特石油公司混合問題我們建立此問題的線性規(guī)劃模型。由于此問題是決定兩個汽油產(chǎn)品中每個汽油產(chǎn)品中各類成分的含量，我們引入決策變量xij（i=1，2，3，4；j=1，2）表示第j種汽油產(chǎn)品中成份i的含量（這里，j=1，2分別表示般汽油產(chǎn)品和特殊汽油產(chǎn)品）,具體模型與求解見P76勞動力分配問題勞動力分配問題屬于資源分配問題，在求得最優(yōu)方案后發(fā)現(xiàn)某些資源相對過剩，而有些資源又相對緊缺；假設(shè)在一些條件下，不同種類資源量在一定條件下可以置換或可以共享；我們可以把相對過剩的資源“置換”成相對緊缺的資源以達到擴大生產(chǎn)規(guī)模增加利潤的目的。具體案例如美克制造公司的勞動力分配問題線性規(guī)劃在不同領(lǐng)域的應(yīng)用線性規(guī)劃在很多領(lǐng)域都有應(yīng)用,除前面的經(jīng)典應(yīng)用模型外,本章繼續(xù)舉例研究一些較為復(fù)雜應(yīng)用案例:如航線安排問題P80,水力發(fā)電問題P82,用來進一步說明線性規(guī)劃建模技術(shù)與用Excel求解方法.這里不再一一列舉.靈敏度分析(what-if分析)在實際問題中，我們首先收集有關(guān)數(shù)據(jù)，建立線性規(guī)劃模型，用Excel求解.管理科學(xué)人員在向管理層提出該問題的最優(yōu)解（最優(yōu)方案）之后，任務(wù)并未完全結(jié)束.管理層還希望知道，當(dāng)各種假設(shè)條件變化時，各種管理方法可能產(chǎn)生的結(jié)果，并通過對各種結(jié)果進行分析，來指導(dǎo)管理層做出最終決策。靈敏度分析(what-if分析)如果未來的情況有變化的話，最優(yōu)解將會如何變化？(實際問題中獲得所需的數(shù)據(jù)是相當(dāng)困難的，有時只能得到所需的數(shù)據(jù)的估計值)。管理層在做出最終決策之前，必然想知道如果這些估計量與實際情況有一定的誤差時最優(yōu)解將會如何變化，或估計值在什么范圍內(nèi)變化時，不會影響最優(yōu)解靈敏度分析(what-if分析)分別討論下列數(shù)據(jù)或條件變化時對于最優(yōu)基（最優(yōu)解）的靈敏度分析：

1)目標(biāo)函數(shù)系數(shù)C的變化；

2)右端常數(shù)的b變化；

3)增加新變量和新的約束條件的變化；使用

Excel電子表格進行靈敏度分析

靈敏度分析(what-if分析)電子表格的一個很大的優(yōu)點是方便展開各種靈敏度分析，當(dāng)某一參數(shù)發(fā)生變化時，只需要改變電子表格中相應(yīng)的數(shù)據(jù)，重新按“規(guī)劃求解”按鈕求出新的解。例如:靈敏度分析(what-if分析)目標(biāo)系數(shù)同時變動

在分析多個系數(shù)同時變動的情況時，可同樣使用這些數(shù)據(jù)，且有下列法則：目標(biāo)系數(shù)同時變動的百分之百法則：如果若干個目標(biāo)函數(shù)系數(shù)同時變動，計算出每一系數(shù)變動量占該系數(shù)允許變動量的百分比，再將所有系數(shù)變動百分比相加，若所得之和不超過百分之一百，則最優(yōu)解不會改變，若所得之和超過了百分之一百，則不能確定最優(yōu)解是否改變。靈敏度分析(what-if分析)右端項的靈敏度分析

(影子價格)我們來討論以資源分配問題為背景的線性規(guī)劃模型中資源的價格問題。由于資源分配問題是分配m種資源做n種活動，相應(yīng)的約束形式為：約束函數(shù)≤右端項bi(i=1,2,...,m)bi表示第i種資源的現(xiàn)有數(shù)量；當(dāng)?shù)趇種資源的數(shù)量由bi變?yōu)閎i+1時（其余參數(shù)不變）最優(yōu)目標(biāo)函數(shù)值的改變量稱為（第i種資源或第i個約束函數(shù)的）影子價格或邊際價格。靈敏度分析(what-if分析)尋找影子價格較簡易的方法還是使用電子表格，增加約束右端值一個單位，接著按下規(guī)劃求解按鈕，就可以看到目標(biāo)函數(shù)值增加的數(shù)量。同時Excel求解靈敏度報告也提供每個函數(shù)約束的影子價格。靈敏度分析(what-if分析)管理者想要了解增加（或減少）第i種資源的數(shù)量對目標(biāo)函數(shù)值增加或減少的影響程度。將影子價格yi稱為第i種資源的機會成本（機會損失），在現(xiàn)有資源量的基礎(chǔ)上，若增加一個單位的第i種資源，企業(yè)獲利將增加yi，反之若減少一個單位的第i種資源，企業(yè)獲利將減少yi，。靈敏度分析(what-if分析)因此管理者可以根據(jù)第i種資源的市場價格li來決策是否應(yīng)調(diào)整原來的生產(chǎn)規(guī)模；如果li<yi（第i種資源市場價格低于影子價格），可從市場上采購第i種資源若干單位，擴大生產(chǎn)規(guī)模；若li

>yi

，可以減少生產(chǎn)規(guī)模（變賣資源獲利更大）除了用Excel求影子價格外，對于只有兩個決策變量的線性規(guī)劃問題也可以用圖解法求第i種資源的影子價格.靈敏度分析(what-if分析)類似地，我們有右端項同時變動的百分之百法則如下：同時改變?nèi)舾蓚€右端項值，計算每個右端項變動占所允許增加值或減少值的百分比，若所有百分比之和沒有超過百分之百，那么影子價格還是有效的（最優(yōu)基不變），若所有百分比之和超過100%，那么，無法確定影子價格是否有效。靈敏度分析(what-if分析)增加新的決策變量

在實際問題中經(jīng)常會碰到由于生產(chǎn)條件或市場行業(yè)變化需要在原線性規(guī)劃模型上增加新的決策變量的情況。(例如在第二章例1的資源分配問題中，假如又有一種新產(chǎn)品丙可以生產(chǎn))增加新的約束條件在原問題線性規(guī)劃求解之后，由于自然條件或工藝要求的變化，有時需要增加一個新的約束條件，此種情況經(jīng)常發(fā)生。靈敏度分析(what-if分析)案例分析:麗欣公司廣告投入與收益均衡問題(P14)

廣告運動推銷三種產(chǎn)品兒童奶粉---目標(biāo):增加市場份額8%鮮牛奶---目標(biāo):增加市場份額13%成人奶粉---目標(biāo):增加市場份額5%

廣告手段(1)促銷會-----單位成本100萬(2)電視-------單位成本210萬元(3)印刷媒體-------單位成本160萬元靈敏度分析(what-if分析)相關(guān)數(shù)據(jù)(如表)用X1表示促銷會次數(shù)用X2表示電視廣告次(套)數(shù),

用X3表示印刷媒體廣告次(套)數(shù),

則:目標(biāo)函數(shù)Z=100x1+210x2+160x3最小化促銷會每單位電視每單位印刷媒體每單位兒童奶粉132鮮奶2-13成人奶粉202靈敏度分析(what-if分析)約束條件:X1+3X2+2X2

≥82X1-X2+3X2

≥132X1+2X3

≥5非負約束X1≥0,X2≥0,X3

≥0用Excel求解,見P43,并作敏感性分析報告.第六章運輸問題與指派問題運輸問題(TransportationProblem)和指派問題(AssignmentProblem)屬于線性規(guī)劃問題，是線性規(guī)劃的兩類常見問題，并且這兩類問題具有特殊的數(shù)學(xué)性質(zhì)，使得管理科學(xué)家能夠開發(fā)出多種高效獨特的求解算法，所以我們專門用一章來研究。本章內(nèi)容§6.1案例研究：L食品公司的運輸問題§6.2運輸問題的模型與性質(zhì)§6.3應(yīng)用EXCEL和LINGO求解運輸問題§6.4運輸問題變形的一些應(yīng)用§6.5指派問題§6.1

L食品公司的運輸問題例1

湖南L食品公司是生產(chǎn)食品罐頭的企業(yè)，有桔子、竹筍、野山菌三個罐頭廠，三個工廠的廠址分別在A、B、C三個靠近不同原料產(chǎn)地的城鎮(zhèn)，每個工廠都能生產(chǎn)不同品種的罐頭，但每個工廠生產(chǎn)不同品種罐頭的產(chǎn)能不同，各工廠生產(chǎn)與廠名相同的罐頭的設(shè)計產(chǎn)能要大一些。2009年6月份來自深圳、武漢、成都和西安的四個配送中心的野山菌罐頭訂單和各工廠的野山菌罐頭的計劃產(chǎn)量如表6-1所示。2009年6月每箱野山菌罐頭從各個工廠到各個配送中心的具體運價如表6-2所示。廠址（廠名）產(chǎn)量配送中心訂單需求A(桔子)80深圳85B(竹筍)100武漢110C(野山菌)220成都75西安130合計400合計400表6-1罐頭的產(chǎn)能和配送中心需求（單位：箱）表6-2各工廠到配送中心的野山菌罐頭運價（單位：元/箱）罐頭廠配送中心深圳武漢成都西安A(桔子)784586110B(竹筍)844179103C(野山菌)805376118表6-1、表6-2可以用下圖表示：小張的運輸方案

（單位：箱）小張的運輸方案需要運費成本是：罐頭廠（供應(yīng)）配送中心（需求）合計深圳武漢成都西安A(桔子)8000080B(竹筍)59500100C(野山菌)01575130220合計8511075130400小劉的運輸方案

（單位：箱）小劉的運輸方案需要運費成本是：罐頭廠（供應(yīng)）配送中心（需求）合計深圳武漢成都西安A(桔子)70100080B(竹筍)010000100C(野山菌計8511075130400楊經(jīng)理的思考……小劉的運輸方案比小張的節(jié)約了140元，于是，楊經(jīng)理決定用小劉的方案。但是，會不會還有更節(jié)約的運輸方案呢？楊經(jīng)理開始琢磨這個問題，或許以后能找到更好的方案吧，不管怎么樣，以后要在運輸方案安排上多用點心思了，因為每隔幾天運輸部都要為公司不同的產(chǎn)品訂單集中安排一次運輸，如果每次都能用最好的方案，一年下來也是一筆可觀的費用呢?！?.2運輸問題的模型與性質(zhì)1運輸問題的模型例1中提到的湖南某食品公司的問題就是一個典型的運輸問題。在運輸問題中，尋求從產(chǎn)地到銷地的最小的運輸成本。運輸問題的一般提法是這樣的：某種物資有若干個產(chǎn)地和銷地，若已知各個產(chǎn)地的產(chǎn)量、各個銷地的銷量以及各產(chǎn)地到各銷地的單位運價（或運輸距離）。問應(yīng)如何組織運輸，才能使總運費（或總的運輸量）最??？假定有m個產(chǎn)地，n個銷地，我們定義如下變量：——第產(chǎn)地的供應(yīng)量，i=1，2，…，m

；

——第銷地的需求量，j

=1，2，…，n；

——從產(chǎn)地到銷地的單位運費，i

=1，2，…，m，j

=1，2，…，n；

——產(chǎn)地到銷地的運輸數(shù)量，i

=1，2，…，m，j

=1，2，…，n。

則該問題為求解最佳運輸方案，即求解所有的值，使總的運輸費用達到最少。決策變量為

該問題的數(shù)學(xué)模型形式為：把例1的問題用數(shù)學(xué)模型表達出來就是：2運輸問題的性質(zhì)運輸問題中每一個產(chǎn)地都有一定的供應(yīng)量（supply）配送到銷地，每一個銷地都有一定的需求量（demand），接收從產(chǎn)地發(fā)出的產(chǎn)品，基本的運輸問題有如下性質(zhì)：1）需求假設(shè)（TheRequirementsAssumption）每一個產(chǎn)地都有一個固定的供應(yīng)量，所有的供應(yīng)量都必須配送到銷地。與之相類似，每一個銷地都有一個固定的需求量，整個需求量都必須由產(chǎn)地滿足。2）可行解特性（TheFeasibleSolutionsProperty）當(dāng)且僅當(dāng)供應(yīng)量的總和等于需求量的總和，也就是產(chǎn)銷平衡時，運輸問題才有可行解。3）成本假設(shè)（TheCostAssumption）：從任何一個產(chǎn)地到任何一個銷地的貨物配送成本和所配送的數(shù)量成線性比例關(guān)系，因此這個成本就等于配送的單位成本乘以配送的數(shù)量。4）整數(shù)解性質(zhì)（IntegerSolutionsPr