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

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

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

整體性特征科學性特征廣泛性特征最優性特征綜合性特征管理科學的影響

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

提出問題，并根據需要收錄有關數據信息。向管理者咨詢、鑒別所要考慮的問題以確定合理的目標，然后根據要求收集一些關鍵數據，并對數據作相應的分析。管理科學求解問題步驟步驟2

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

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

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

從模型中形成一個對問題求解的算法。管理科學小組要在計算機上運行數學程序對模型進行求解，一般情況下能找到對模型求解的標準軟件。例如，對線性規劃問題已有Excel、Cplex、Lingo等標準軟件求解。有時要自己編寫程序。管理科學求解問題步驟步驟4.

測試模型并在必要時修正。在模型求解后，管理科學小組需要對模型進行檢驗，以保證該模型能準確反映實際問題，需要檢驗模型提供的解是否合理，所有主要相關因素是否已考慮，當有些條件變化時，解如何變化等。管理科學求解問題步驟步驟5.

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

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

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

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

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

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

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

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

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

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

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

步驟2---建立數學模型

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

x1=產品甲的生產數量

x2=產品乙的生產數量

2)目標函數---衡量決策效果(優劣)的指標

Z=4x1+3x2

求最大值

3)約束條件

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

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

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

用決策變量的函數表示目標，并確定是求極大（Max）、極小（Min）還是特定值；

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

使用的資源數量

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

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

完成的水平

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

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

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

f15+f14=100

f25+f24=80

f34+f36=70物流網絡配送問題對配送中心v4，運進的產品數量等于運出的產品數量：

f14+f24+f34=f45+f46對倉庫v5、v6，運進的產品數量等于其需求量

f15+f25+f45=120

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

≥0，i=1，2，3，4；j=1，2，3。例1.農場灌溉問題例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的投資金額（單位：萬元），相應的目標函數（稅后收益）為：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.證券投資問題證券平均評級約束：

這是一個非線性約束，容易轉化為以下線性約束：

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

例3.話務員排班問題例4.多階段生產安排問題

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

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

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假設x1,x2,x3,x4,x5,x6,x7,x8分別為上面前8種方案下料的原材料根數。我們建立如下的數學模型。目標函數：

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，整數模型2假設x1,x2,x3,x4,x5,x6,x7,x8分別為上面前8種方案下料的原材料根數。我們建立如下的數學模型。目標函數：

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，整數模型3例6醫藥公司的中草藥配方問題

安康醫藥公司考慮配制一種中成藥;市場上有八種中草藥材包含該中成藥所需要的特定成份,公司準備采購一些中草藥來配制這種中成藥，要求配制后的中成藥所包含三種特定成份(不妨設為成份A、成份B和成份C)分別為39、36、38。由于每種中草藥材包含的成份不同,采購成本也不同;公司管理層希望以最低的成本來完成中成藥的配制;各個中草藥材(每單位)包含的三種成份含量及單位采購成本數學建模決策變量Xi表示第種草藥在中成藥中的使用量（i=1，2，3，4，5，6,7,8）。為了使成本最低我們有:目標函數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.安康醫藥公司的中草藥配方問題的Excel規劃求解

討論:為什么8種中草藥,最優方案只選了三種呢?(草藥1,草藥2和草藥7)事實上,由于這個問題只有三個函數約束(成份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種中草藥,最優方案只選了三種呢?若將第i種草藥三種成份含量看作一個三維向量Pi則:由線性代數知識我們知道向量組P1,P2,P7

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

+c2x2+...+cnxn,

a11x1+a12x2+...+a1nxn=b1

a21x1+a22x2+...+a2nxn=

b2

.........

am1x1+am2x2+...+amnxn=bm

x1

>0,x2>0,

...

,xn>0.單純形法1)目標函數的轉化若原問題的目標函數是求最小化，即:minimizeZ=c1x1

+c2x2+...+cnxn,

則可將目標函數乘以-1，等價轉化為求如下最大化問題：

Maximize-Z=-c1x1

-c2x2-...–cnxn

轉化后的問題與原問題有相同的最優解單純形法2)不等式約束轉化為等式約束

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

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

≥b1

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

0

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

xi=x’i–x’’I,

x’I≥

0,

x’’i≥

0.

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

單純形法例：將下列線性規劃問題化為標準形式:

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

+c2x2+...+cnxn,

a11x1+a12x2+...+a1nxn=b1

a21x1+a22x2+...+a2nxn=

b2

.........

am1x1+am2x2+...+amnxn=bm

x1

>0,x2>0,

...

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

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

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

單純形法我們希望找到最優的xB

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

然后令xN=0,

在約束方程組中解出xB

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

，x3,x4,x5是基變量，x1,x2,是非基變量。單純形法由于P2,P3,P4,線性無關,也是線性規劃的一個基。對于基基B1，x2,x3,x4,是基變量，x1,x5是非基變量單純形法因此，約束方程組變為單純形法由于B可逆，將左乘以上式的兩邊得:令xN=0，則

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

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

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

x2,=

0,對應可行區域頂點O(0,0)

基陣（

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

基陣（

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

基陣（

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

）和（P1,P3,P5）不可逆，不能構成基陣.單純形法事實上，對于一般的線性規劃問題（m個約束，n個決策變量）有類似的特性：每個基本可行解對應于可行域的頂點。可行域中相鄰的兩個頂點對應基陣中只有一個基向量不同，其余的個基向量相同。由于線性規劃的最優解是在可行域的頂點獲得，由頂點與基可行解的對應關系，我們有以下線性規劃的基本定理：線性規劃問題如果存在最優解，則一定存在一個基本可行解是最優解。單純形法單純形法一般從可行域一個頂點（通常是原點）出發，試圖在其相鄰的可行域頂點中找目標函數值更好的頂點，若在某頂點的相鄰的頂點中找不出使目標函數有改進的頂點，則現有頂點就是最優解。單純形法新的基陣變為B=（

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

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

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

1)目標函數系數C的變化；

2)右端常數的b變化；

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

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

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

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

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

>yi

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

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

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

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

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

則:目標函數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)屬于線性規劃問題，是線性規劃的兩類常見問題，并且這兩類問題具有特殊的數學性質，使得管理科學家能夠開發出多種高效獨特的求解算法，所以我們專門用一章來研究。本章內容§6.1案例研究：L食品公司的運輸問題§6.2運輸問題的模型與性質§6.3應用EXCEL和LINGO求解運輸問題§6.4運輸問題變形的一些應用§6.5指派問題§6.1

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

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

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

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

；

——第銷地的需求量，j

=1，2，…，n；

——從產地到銷地的單位運費，i

=1，2，…，m，j

=1，2，…，n；

——產地到銷地的運輸數量，i

=1，2，…，m，j

=1，2，…，n。

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

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