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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.公司是否該生產(chǎn)這兩個(gè)產(chǎn)品?2如果生產(chǎn),產(chǎn)品生產(chǎn)組合如何?(各生產(chǎn)多少?)資源分配問題這是一個(gè)定量問題決策目標(biāo)---利潤(rùn)最大化步驟1---收集相關(guān)數(shù)據(jù)如下:(見P10)甲乙資源總量原料A104原料B028設(shè)備工時(shí)2318單位利潤(rùn)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è)備工時(shí)約束)x1,x2≥0(非負(fù)約束)建立數(shù)學(xué)規(guī)劃模型的四個(gè)步驟

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

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

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

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

使用的資源數(shù)量

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

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

完成的水平

最低可接受的水平成本效益平衡問題某飼料公司希望用玉米、紅薯兩種原料配制一種混合飼料，各種原料包含的營(yíng)養(yǎng)成份和采購成本都不相同，公司管理層希望能夠確定混合飼料中各種原料的數(shù)量，使得飼料能夠以最低的成本達(dá)到一定的營(yíng)養(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)養(yǎng)要求的約束，這些約束條件是：碳水化合物需求：8x1+4x2≥20蛋白質(zhì)需求：3x1+6x2≥18維他命需求：x1+5x2≥16另有非負(fù)約束：x1≥0，x2≥0成本效益平衡問題因此，這個(gè)問題的線性規(guī)劃模型為：物流網(wǎng)絡(luò)配送問題偉達(dá)物流公司需將甲、乙、丙三個(gè)工廠生產(chǎn)的一種新產(chǎn)品運(yùn)送到A、B兩個(gè)倉庫，甲、乙兩個(gè)工廠的產(chǎn)品可以通過鐵路運(yùn)送到倉庫A，數(shù)量不限；丙工廠的產(chǎn)品可以通過鐵路運(yùn)送到倉庫B，同樣，產(chǎn)品數(shù)量不限。由于鐵路運(yùn)輸成本較高，公司也可考慮由獨(dú)立的卡車來運(yùn)輸，可將多達(dá)80個(gè)單位的產(chǎn)品由甲、乙、丙三個(gè)工廠運(yùn)到一個(gè)配送中心，再從配送中心以最多90單位的載貨量運(yùn)到各個(gè)倉庫。公司管理層希望以最小的成本來運(yùn)送所需的貨物。物流網(wǎng)絡(luò)配送問題需要收集每條線路上的單位運(yùn)輸成本和各工廠產(chǎn)品的產(chǎn)量以及各倉庫分配量等數(shù)據(jù)：

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

f15+f14=100

f25+f24=80

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

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

f15+f25+f45=120

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

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

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

最小化。對(duì)于第i種效益，我們有

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

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

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

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

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

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

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

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

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

1.5x32+x33≤5500(農(nóng)場(chǎng)3)2x41+1.5x42+x43≤5000(農(nóng)場(chǎng)4)例1.農(nóng)場(chǎ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)場(chǎng)灌溉問題4)種植作物面積占總耕地面積比例約束即各農(nóng)場(chǎng)種植作物面積（灌溉面積）占總耕地面積的比例相同。5)決策變量的非負(fù)約束xij

≥0，i=1，2，3，4；j=1，2，3。例1.農(nóng)場(chǎng)灌溉問題例2.證券投資問題一證券投資者將1000萬元資金用于證券投資，已知各種證券（A、B、C、D、E、F）的評(píng)級(jí)、到期年限、每年稅后收益如表所示。管理層對(duì)該投資者提出下列要求：國(guó)債投資額不能少于300萬元；投資證券的平均評(píng)級(jí)不超過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國(guó)債投資額約束：

xC+xD≥300例2.證券投資問題證券平均評(píng)級(jí)約束：

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

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

它等價(jià)于線性約束：

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

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

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

xj≥0,Ij≥0，j=1，2，3，4，5，6目標(biāo)為總成本最小化:例4.多階段生產(chǎn)安排問題例5.下料問題某工廠要做100套鋼架，每套用長(zhǎng)為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長(zhǎng)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ī)藥公司考慮配制一種中成藥;市場(chǎng)上有八種中草藥材包含該中成藥所需要的特定成份,公司準(zhǔn)備采購一些中草藥來配制這種中成藥，要求配制后的中成藥所包含三種特定成份(不妨設(shè)為成份A、成份B和成份C)分別為39、36、38。由于每種中草藥材包含的成份不同,采購成本也不同;公司管理層希望以最低的成本來完成中成藥的配制;各個(gè)中草藥材(每單位)包含的三種成份含量及單位采購成本數(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í)上,由于這個(gè)問題只有三個(gè)函數(shù)約束(成份A、成份B和成份C),三個(gè)等式約束看作一個(gè)線性方程組: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種草藥三種成份含量看作一個(gè)三維向量Pi則:由線性代數(shù)知識(shí)我們知道向量組P1,P2,P7

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

Maximize-Z=-c1x1

-c2x2-...–cnxn

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

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

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

≥b1

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

0

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

xi=x’i–x’’I,

x’I≥

0,

x’’i≥

0.

代入原問題，即在原問題中將用兩個(gè)非負(fù)變量之差代替

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

首先將最小化問題乘以-1，轉(zhuǎn)化為最大化問題,在第一約束中引入松弛變量x4，第二個(gè)約束中引入剩余變量x5，再令自由變量x2=x’2–x”2，并將第三約束方程兩邊同乘以（-1),得到與原問題等價(jià)的線性規(guī)劃標(biāo)準(zhǔn)形式：?jiǎ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,即:約束個(gè)數(shù)小于變量個(gè)數(shù)單純形法由上章討論可知,最優(yōu)解里,x1,x2,x3,…xn,中一般會(huì)有m個(gè)不為0(我們稱為基變量,用xB),其余n-m個(gè)必須為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個(gè),(同時(shí)也確定xN包含,x1,x2,…xn,中剩余的n-m個(gè))

然后令xN=0,

在約束方程組中解出xB

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

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

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

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

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

x2,=

0,對(duì)應(yīng)可行區(qū)域頂點(diǎn)O(0,0)

基陣（

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

基陣（

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

基陣（

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

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

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

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

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

Excel電子表格進(jìn)行靈敏度分析

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

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

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

>yi

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

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

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

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

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

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

≥82X1-X2+3X2

≥132X1+2X3

≥5非負(fù)約束X1≥0,X2≥0,X3

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

L食品公司的運(yùn)輸問題例1

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

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

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

；

——第銷地的需求量，j

=1，2，…，n；

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

=1，2，…，m，j

=1，2，…，n；

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

=1，2，…，m，j

=1，2，…，n。

則該問題為求解最佳運(yùn)輸方案，即求解所有的值，使總的運(yùn)輸費(fèi)用達(dá)到最少。決策變量為

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