《管理運籌學》(第2版)15章教案

1、運籌學教案主講人：課程名稱：運籌學課程主講人：專業(yè)班級： 信息主講人所在單位：經(jīng)濟與管理學院信息管理學系目錄第一章緒論第二章線性規(guī)劃的圖解法第三章線性規(guī)劃問題的計算機求解第四章 線性規(guī)劃在工商管理中的應用第五章單純形法第六章 單純形法的靈敏度分析與對偶第七章運輸問題第八章整數(shù)規(guī)劃第九章目標規(guī)劃第十章動態(tài)視劃第十一章圖與網(wǎng)絡模型第十二章排序與統(tǒng)籌方法第十三章存貯論 第十四章排隊論 第十五章對策論 第十六章決策分析 第十七章預測第一章緒論? § 1決策、定量分析與管理運籌學? § 2運籌學的分支? § 3運籌學在工商管理中的應用? § 4學習運籌學必須使用相

2、應的計算機軟件，必須注重于學以致用的原則第一章緒論運籌學（Operational Research） 直譯為“運作研究”。運籌學是應用分析、試驗、量化的方法，對經(jīng)濟管理系統(tǒng)中的人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理。?運籌學的產(chǎn)生和發(fā)展運籌學產(chǎn)生于第二次世界大戰(zhàn)，主要用于解決如何在與德軍的對抗中最大限度地殺傷敵人，減少損失。二戰(zhàn)以后，運籌學得到了快速的發(fā)展，形成了許多分支，并且計算機的應用極大地推動了運籌學的應用與普及。?運籌學有廣泛應用運籌學不僅在軍事上，而且在生產(chǎn)、決策、運輸、存儲等經(jīng)濟管理領域有著廣泛的應用。§ 1決策、定量分析與管

3、理運籌學決策過程（問題解決的過程）：1）認清問題；2）找出一些可供選擇的方案；3）確定目標或評估方案的標準；4）評估各個方案：解的檢驗、靈敏性分析等；5）選出一個最優(yōu)的方案：決策；6）執(zhí)行此方案：回到實踐中；7）進行后評估：考察問題是否得到完滿解決；1 ） 2） 3）:形成問題；4）5）:分析問題：定性分析與定量分析。構成決策。§ 2運籌學的分支?線性規(guī)劃?整數(shù)線性規(guī)劃?動態(tài)規(guī)劃?圖與網(wǎng)絡模型?排隊論?排序與統(tǒng)籌方法?決策分析?對策論?非線形規(guī)劃組織應用Interface期刊號每年節(jié)支（美元）聯(lián)合航空公司滿足乘客需求前提下，以最低成本進行訂票及安排機場 工作班次1-2/1986600

4、萬Citgo石油優(yōu)化煉油程序及產(chǎn)品供應、配送及營銷1-2/19877000 萬荷馬特發(fā)展公司優(yōu)化商業(yè)區(qū)和辦公樓銷售程序1-2/19874000 萬AT&T優(yōu)化商業(yè)用戶的電話銷售中心選址1-2/19904.06億,更多銷售標準品牌公司控制成品庫存（制定最優(yōu)再訂購點和訂購量，確保安全 庫存）12/1981380萬施樂公司通過戰(zhàn)略調(diào)整，縮短維修機器的反應時間和改進維修人 員的生產(chǎn)率11/1975 第二部分生產(chǎn)率提高50蛆上寶潔公司重新設計北美生產(chǎn)和分銷系統(tǒng)以降低成本并加快了市 場進入速度1-2/19972億法國國家鐵路制定最優(yōu)鐵路時刻表并調(diào)整鐵路日運營量1-2/19981500萬更多年收入D

5、elta航空公司進行上千個國內(nèi)航線的飛機優(yōu)化配置來最大化利潤1-2/19941億IBM重組全球供應鏈，保持最小庫存的同時滿足客戶需求1-2/20001第一年7.5億Merit青銅制品公司安裝統(tǒng)計銷售預測和成品庫存管理系統(tǒng)，改進客戶服務11-2/1993更優(yōu)的服務?模糊數(shù)學§ 3運籌學在工商管理中的應用?生產(chǎn)計劃：生產(chǎn)作業(yè)的計劃、日程表的編排、合理下料、配料問題、物料管理等，追求利潤 最大化和成本最小化?庫存管理：多種物資庫存量的管理，庫存方式、庫存量等運輸問題：確定最小成本的運輸線路、物資的調(diào)撥、運輸工具的調(diào)度以及建廠地址的選擇等人事管理：對人員的需求和使用的預測，確定人員編制、人員

6、合理分配，建立人才評價體系等市場營銷：廣告預算、媒介選擇、定價、產(chǎn)品開發(fā)與銷售計劃制定等財務和會計：預測、貸款、成本分析、定價、證券管理、現(xiàn)金管理等*設備維修、更新，項目選擇、評價，工程優(yōu)化設計與管理等?由國際運籌與管理科學協(xié)會(INFORMS )和它的管理科學實踐學會(College for the Practice of the Management Sciences )主持評獎的負有盛名的弗蘭茨 厄 德曼(Frany Edlman )獎，就是為獎勵優(yōu)秀的運籌學在管理中的應用的成就設 立的，該獎每年舉行一次，在對大量富有競爭力的入闈者進行艱苦的評審后， 一般有六位優(yōu)勝者獲獎。關于這些獲獎項

7、目的文章都在第二年發(fā)表在著名刊物 Interface的第一期上，下面列表就是發(fā)表在Interface期刊的一些獲獎項目。運籌學方法使用情況(美1983)運籌學方法在中國使用情況（隨機抽樣）§4學習管理運籌學必須使用相應的計算機軟件，必須注重于學以致用的原則?學習運籌學要結(jié)合實際的應用，不要被一些概念、理論的困難嚇倒。?學習運籌學要把注意力放在“結(jié)合實際問題建立運籌學模型”和“解決問題的方案或模型的 解”兩頭，中間的計算過程盡可能讓計算機軟件去完成。?本書附有運籌學教學軟件，使用方法很簡單。學員必須盡快學會使用這個運籌學教學軟件， 并借助它來學好本課程。學習運籌學是為了用于實踐，解決實

8、際問題。以前重視人工計算是 因為沒有計算機，現(xiàn)在有了就應該好好利用。§4學習管理運籌學必須使用相應的計算機軟件，必須注重于學以致用的原則?例如，有人要從北京去烏魯木齊。在一百多年以前，我們應該告訴他如何配備糧草、銀兩、 衣物，如何選購馬匹、馬車，挑選馬夫和保鏢，如何根據(jù)天氣、地理條件和社會諸因素來確 定行車路線和行程，更重要的是如何在幾個月的行程中處理吃穿住行，應付突發(fā)事件等問題;但是現(xiàn)在我們只需告訴他如何去北京飛機場，如何在烏魯木齊下飛機后提取行李和坐車就可 以了，其余的問題交給航空公司和機組人員就行了。完全沒有必要為了一次旅行攻讀空氣動 力學、噴氣發(fā)動機設計和制造、飛行器駕駛手冊

9、等厚厚的教科書。?他山之石，可以攻玉本書配套的計算機軟件如同上例中的 飛機”，它可以為你節(jié)省出大量的時間和精力用在問題建模，以及解決方案的分析和完善上第二章 線性規(guī)劃的圖解法? § 1 問題的提出? § 2 圖解法? § 3 圖解法的靈敏度分析在管理中一些典型的線性規(guī)劃應用? 合理利用線材問題：如何在保證生產(chǎn)的條件下，下料最少? 配料問題：在原料供應量的限制下如何獲取最大利潤? 投資問題：從投資項目中選取方案，使投資回報最大? 產(chǎn)品生產(chǎn)計劃：合理利用人力、物力、財力等，使獲利最大? 勞動力安排：用最少的勞動力來滿足工作的需要? 運輸問題：如何制定調(diào)運方案，使總運費

10、最小線性規(guī)劃的組成：?目標函數(shù)Max F 或 Min F?約束條彳s.t. (subject to) 滿足于?決策變量用符號來表示可控制的因素§ 1問題的提出例1.某工廠在計劃期內(nèi)要安排I、產(chǎn)兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設備臺時及A、B兩種原材料的消耗、資源的限制，如下表：1II贄源限制設備11300臺時原料A21小千克原料H01期千克單位產(chǎn)品獲利30元元問題：工廠應分別生產(chǎn)多少單位I、n產(chǎn)品才能使工廠獲利最多？線性規(guī)劃模型：目標函數(shù)：Maxz = 50 xi + 100 x2約束條件：s.t.x1+x2 w 3002 x1 + x2 W 400x2 w 250xi , x

11、2 >0砒模過程1 .理解要解決的問題，了解解題的目標和條件；2 .定義決策變量(x1 , x2，xn ),每一組值表示一個方案；3 .用決策變量的線性函數(shù)形式寫出目標函數(shù)，確定最大化或最小化目標；4 .用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件? 一般形式目標函數(shù)：Max ( Min ) z = c 1x1 + c 2 x 2 + + c n x n約束條件：s.t.an x 1 + a 12 x 2 + + a1n x n <( =, > ) b 13 21 x 1 + a22 x 2 + + a2n xn <(=, >)b2a m1 x

12、 1 + a m2 x 2 + , + amn x n &(=, > )bmx1 , x2 , x n > 0對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標系上作圖表示線性規(guī)劃問題的有關概念，并求解。下面通過例1詳細講解其方法：例1.目標函數(shù)：Max z = 50 x 1 + 100 x 2約束條件：s.t.x1 +x2 <300(A)2 x1 +x2 <400(B)x2 <250(C)x1>0(D)X2(E)得到最優(yōu)解:xi = 50 , 最優(yōu)目標值X2 = 250 z = 27500(1)分別取決策變量Xi , X2為坐標向量建立直角坐標

13、系。在直角坐標系里，圖上任意一點的 坐標代表了決策變量的一組值，例1的每個約束條件都代表一個半平面。(2)對每個不等式(約束條件)，先取其等式在坐標系中作直線，然后確定不等式所決定的半平 面。(3)把五個圖合并成一個圖，取各約束條件的公共部分，如圖 2-1所示圖2.1(4)目標函數(shù)z=50xi+100X2,當z取某一固定值時得到一條直線，直線上的每一點都具有相同 的目標函數(shù)值，稱之為 等值線”。平行移動等值線，當移動到B點時，z在可行域內(nèi)實現(xiàn)了最 大化。A, B, C, D, E是可行域的頂點，對有限個約束條件則其可行域的頂點也是有限的。2F=10000=50X十 100x2J DOx?線性規(guī)

14、劃的標準化內(nèi)容之一： 引入松馳變量(含義是資源的剩余量)例1中引入s 1, s 2,S 3模型化為目標函數(shù)：Maxz = 50 x 1 + 100 x 2 +0 s 1+ 0 S2 + 0 S3約束條件：s.t.x1 +x2 +S1=3002 x1 +x2 +S2=400x2 +S3= 250x1 ,x2,S1 ,S2,S3 > 0對于取優(yōu)解x1 =50x2 = 250 ,S1 = 0S2=50S3 = 0說明：生產(chǎn)50單位I產(chǎn)品和250單位n產(chǎn)品將消耗完所有可能的設備臺時數(shù)及原料B,但對原料A則還剩余50千克重要結(jié)論：-如果線性規(guī)劃有最優(yōu)解，則一定有一個可行域的頂點對應一個最優(yōu)解；-無

15、窮多個最優(yōu)解。若將例1中的目標函數(shù)變?yōu)閙ax z=50x 1+50X2,則線段BC上的所有點都代表了最優(yōu)解；- 無界解。即可行域的范圍延伸到無窮遠，目標函數(shù)值可以無窮大或無窮小。一般來說， 這說明模型有錯，忽略了一些必要的約束條件；- 無可行解。若在例1的數(shù)學模型中再增加一個約束條件4x1+3x2>120Q則可行域為空域，不存在滿足約束條件的解，當然也就不存在最優(yōu)解了0- 進一步討論例2某公司由于生產(chǎn)需要，共需要A, B兩種原料至少350噸（A, B兩種材料有一定替代性） 其中A原料至少購進125噸。但由于A, B兩種原料的規(guī)格不同，各自所需的加工時間也是不同 的，加工每噸A®

16、料需要2個小時，加工每噸B原料需要1小時，而公司總共有600個加工小時 又知道每噸A原料的彳格為2萬元，每噸B原料的彳格為3萬元，試問在滿足生產(chǎn)需要的前提下, 在公司加工能力的范圍內(nèi)，如何購買 A, B兩種原料，使得購進成本最低？解：目標函數(shù)： Min f = 2x i + 3 x 2約束條件：s.t.xi + x2 > 350xi> 1252 x1 + x2 < 600x1 , x2 >0采用圖解法。如下圖：得 Q點坐標（250, 100）為最優(yōu)解。100 200 加血。唄0 6QQ-§ 3圖解法的靈敏度分析線性規(guī)劃的標準化? 一般形式目標函數(shù)：Max (M

17、in) z = C1 x1+ C2 x2+ +rcxn約束條件：s.t.a11 x1 + a12 x2 + a 1n xn <( =, > ) b1a21 x1 + a22 x2 + a2n xn <( =, > ) b2 am1 x1 + am2 x2 + amn xn &(二,>)bmx1 , x2 , xn > 0? 標準形式目標函數(shù)：MaX約束條件： s.t.C1 X1 + C2 X2 + +ncxnaii xi + ai2 x2 + ain xn=bia21 X1 + a22 X2 + a2n Xn=b2 ami Xi + am2 X2 +

18、 2mn Xn=bmXi , X2 , Xn> 0, bi >0可以看出，線性規(guī)劃的標準形式有如下四個特點：-目標最大化；-約束為等式；-決策變量均非負；-右端項非負。對于各種非標準形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標準形式:i. 極小化目標函數(shù)的問題：設目標函數(shù)為Min f = C1X1 + C2X2 + + c nX n(可以)令z = -f ,則該極小化問題與下面的極大化問題有相同的最優(yōu)解，即 MaX z = - c 1X 1 - C2X2 -c nX n但必須注意，盡管以上兩個問題的最優(yōu)解相同，但它們最優(yōu)解的目標函數(shù)值卻相差一個符號，即Min f = -

19、 MaX z2、約束條件不是等式的問題：設約束條件為an X1+ai2 X2+ + ain Xn w bi可以引進一個新的變量s ，使它等于約束右邊與左邊之差S=biai1 X 1 + ai2 X2 + + ain X n )顯然，s也具有非負約束，即s>0,這時新的約束條件成為an X1+ai2 X2+ + ain Xn+s = bi當約束條件為ai1 X1 + ai2 X2+ +ain Xn > bi 時，類似地令s=(ai1 X 1 + a i2 X2+ +ain X n)- bi顯然，s也具有非負約束，即SA0,這時新的約束條件成為ai1 X 1 + a i2 X2+ +a

20、in X n-s = bi為了使約束由不等式成為等式而引進的變量s, 當不等式為“小于等于”時稱為 “松弛變量 ”；當不等式為“大于等于”時稱為 “剩余變量 ”。如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標準形式時，必須對各個約束引進不同的松弛變量。例：將以下線性規(guī)劃問題轉(zhuǎn)化為標準形式Min f = 2 x1 -3x2 + 4 x3s.t.3 xi+ 4x2 - 5 x3 <62 xi+ X3>8x1+ x2+ x3 = -9xi , x2 , x3 > 0解：首先 , 將目標函數(shù)轉(zhuǎn)換成極大化：令 z= - f = -2 xi+3x2-4x3其次考慮約束，有2個不等式約束，

21、引進松弛變量x4, x5 >00第三個約束條件的右端值為負，在等式兩邊同時乘-i通過以上變換，可以得到以下標準形式的線性規(guī)劃問題：Max z = - 2xi + 3 x2 - 4x3s.t. 3xi+4x2-5x3+x4= 62xi +x3-x5= 8-xi -x2 -x3= 9xi ,x2 ,x3 ,x4 ,x5 > 0* 變量無符號限制的問題 * ：在標準形式中，必須每一個變量均有非負約束。當某一個變量xj 沒有非負約束時，可以令xj = xj - xj”其中xj"> 0 , xj"> 0即用兩個非負變量之差來表示一個無符號限制的變量，當然xj的

22、符號取決于xj'和xj”的大小。§ 3 圖解法的靈敏度分析靈敏度分析： 建立數(shù)學模型和求得最優(yōu)解后，研究線性規(guī)劃的一個或多個參數(shù)（系數(shù)）ci , aij , bj 變化時，對最優(yōu)解產(chǎn)生的影響。3.1 目標函數(shù)中的系數(shù)ci 的靈敏度分析考慮例 i 的情況，ci 的變化只影響目標函數(shù)等值線的斜率，目標函數(shù)z = 50 x i + i00x2在 z = x2 （x2 = z 斜率為 0 ） 到 z = x i + x2 （x2 = -xi + z 斜率為 -i ）之間時，原最優(yōu)解xi = 50 ， x2 = i00 仍是最優(yōu)解。? 一般情況：z = c1 x1 + c2 x2 寫成

23、斜截式x2 = - （c1 / c2 ） x1 + z / c2目標函數(shù)等值線的斜率為 - （c1 / c2 ） ，當 -1- （c1 / c2 ）0（*） 時，原最優(yōu)解仍是最優(yōu)解。?假設產(chǎn)品II的利潤100元不變，即C2 = 100,代到式（*）并整理得0c1100?假設產(chǎn)品I的利潤50元不變，即C1 = 50 ,代到式（*）并整理得50c2+?假若產(chǎn)品I、R的利潤均改變，則可直接用式（*）來判斷。?假設產(chǎn)品I、H的利潤分別為60元、55元，則- 2- （60 / 55）- 1那么， 最優(yōu)解為z = x1 + x2和 z = 2 x 1 + x2 的交點x1 = 100 ， x2 = 200

24、 。3.2 約束條件中右邊系數(shù)bj 的靈敏度分析當約束條件中右邊系數(shù)bj 變化時，線性規(guī)劃的可行域發(fā)生變化，可能引起最優(yōu)解的變化?？紤]例 1 的情況：假設設備臺時增加10個臺時，即bi變化為310,這時可行域擴大，最優(yōu)解為 x2 = 250 和 x1 + x2 = 310的交點x1 = 60， x2 = 250 。變化后的總利潤 - 變化前的總利潤 = 增加的利潤（50X60+ 100 X250）-（50 X 50+100 X 250） = 500 , 500 / 10 = 50 元說明在一定范圍內(nèi)每增加（減少） 1 個臺時的設備能力就可增加（減少） 50元利潤，稱為該約束條件的對偶價格。假設

25、原料A增加10千克時，即b2變化為410,這時可行域擴大，但最優(yōu)解仍為X2= 250 和 x1 + x2= 300 的交點x1 = 50 ， x2 = 250 。此變化對總利潤無影響，該約束條件的對偶價格為 0 。解釋： 原最優(yōu)解沒有把原料A 用盡， 有50千克的剩余， 因此增加 10千克值增加了庫存，而不會增加利潤。在一定范圍內(nèi)，當約束條件右邊常數(shù)增加 1個單位時（ 1 ）若約束條件的對偶價格大于0，則其最優(yōu)目標函數(shù)值得到改善（變好）；（ 2 ）若約束條件的對偶價格小于0，則其最優(yōu)目標函數(shù)值受到影響（變壞）；（ 3 ）若約束條件的對偶價格等于0，則最優(yōu)目標函數(shù)值不變。第三章 線性規(guī)劃問題的計

26、算機求解§ 1 “管理運籌學”軟件的操作方法§ 2 “管理運籌學”軟件的輸出信息分析隨書軟件為 管理運籌學” 2.版（Window版），是1.0版（DOS版）的升級版。它包括：線性規(guī)劃、運輸問題、整數(shù)規(guī)劃（ 0-1 整數(shù)規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃）、目標規(guī)劃、對策論、最短路徑、最小生成樹、最大流量、最小費用最大流、關鍵路徑、存儲論、排隊論、決策分析、預測問題和層次分析法，共15個子模塊。§ 1 “管理運籌學 ”軟件的操作方法1. 軟件使用演示：（演示例 1 ）第一步：點擊“開始”-> “程序”-> “管理運籌學 2.0 ”，彈出主窗口。第二步：選擇

27、所需子模塊，點擊主窗口中的相應按鈕。本題中選用線性規(guī)劃”方法。點擊按鈕彈出如下界面：X1 +x2300(A)2 xi +x2400(B)x2250(C)xi，0(D)x2，0(E)例1.目標函數(shù)：Max z = 50 xi + 100 x2 約束條件: s.t.第三步：點擊 新建”按鈕，輸入數(shù)據(jù)。本題中共有 2個變量，4個約束條件，目標函數(shù)取MAX。點擊 確定”后，在表中輸入Cj,bi和aj等值，并確定變量的正負約束。 輸入數(shù)值后的界面如下。第四步：點擊 解決”按鈕，得出計算結(jié)果。本題的運行結(jié)果界面如下第五步：分析運行結(jié)果-本題中目標函數(shù)的最優(yōu)值是 27500, xi=50, x2=250o使

28、得決策變量為正值，當決策變-相差值表示相應的決策變量的目標系數(shù)需要改進的數(shù)量,量已為正數(shù)時，相差數(shù)為零。-松弛/剩余變量的數(shù)值表示還有多少資源沒有被使用。如果為零，則表示與之相對應的資 源已經(jīng)全部用上。對偶價格表示其對應的資源每增加一個單位，將增加多少個單位的最優(yōu)值。目標函數(shù)系數(shù)范圍表示最優(yōu)解不變的情況下，目標函數(shù)的決策變量系數(shù)的變化范圍。 當前值是指當前的最優(yōu)解中的系數(shù)取值。常數(shù)項范圍是指約束條件的右端常量。 上限值和下限值是指當約束條件的右端常量在此范圍內(nèi)變化時，與其對應的約束條件的對偶價格不變。當前值是指現(xiàn)在的取值。以上計算機輸出的目標函數(shù)系數(shù)和約束條件右邊值的靈敏度分析都是在其他系數(shù)值

29、不變，只有一個系數(shù)變化的基礎上得出的！2.當有多個系數(shù)變化時，需要進一步討論。百分之一百法則：對于所有變化的目標函數(shù)決策系數(shù)（約束條件右邊常數(shù)值），當其所有允許增加的百分比與允許減少的百分比之和不超過100%時，最優(yōu)解不變（對偶價格不變，最優(yōu)解仍是原來幾個線性方程的解）。* 允許增加量=上限-現(xiàn)在值ci的允許增加量為 100 - 50 = 50bi的允許增加量為 325 - 300 = 25* 允許減少量=現(xiàn)在值-下限C2的允許減少量為 100 - 50 = 50b3的允許減少量為 250 - 200 = 50* 允許增加的百分比 =增加量/允許增加量* 允許減少的百分比 =減少量/允許減少量

30、例：ci 變?yōu)?74 , C2 變?yōu)?78,貝U （74 - 50） / 50 + （100 - 78 ） / 50 = 92%,故最優(yōu)解不變。bi 變?yōu)?315 , b3 變?yōu)?240,貝U （315 - 50） / 25 + （250 - 240 ） / 50 = 80%，故對偶價格不變（最優(yōu)解仍是原來幾個線性方程的解）。在使用百分之一百法則進行靈敏度分析時，要注意：1）當允許增加量（允許減少量）為無窮大時，則對任意增加量（減少量），其允許增加（減少）百分比均 看作0；2）百分之一百法則是充分條件，但非必要條件；也就是說超過100%并不一定變化；3）百分之一百法則不能用于目標函數(shù)決策變量系

31、數(shù)和約束條件右邊常數(shù)值同時變化的情況。這種情況下,只有重新求解。?下面用管理運籌學軟件來分析 第二章的例2,其數(shù)學模型如下:整結(jié)累*由EHE目標函數(shù)：Min f = 2x 1 + 3 x 2約束條件：s.t. x1 +x2 > 350X12 x1 + x2 < 600x1 , x2 >0從上圖可知，當購進原螃2 0 贏n崎Ml hi IM'lanl ” ”看乒丈彷材料 A 250t ，原料 B 100t 時，購進成本最低，為 800萬元。?在松弛/剩余變量欄中，約束條件2的值為125,它表示對原料A的最低需求，即對A的剩余變 量值為 125 ；同理可知約束條件1的剩余

32、變量值為0 ；約束條件3的松弛變量值為 0。? 在對偶價格欄中，約束條件3 的對偶價格為 1 萬元，也就是說如果把加工時數(shù)從600 小時增加到601小時， 則總成本將得到改進， 由800萬減少到 799萬。 也可知約束條件1的對偶條件為 -4萬元，也就是說如果把購進原料 A的下限從125t增加到126t,那么總成本將加大，由800萬增 力口到804萬。當然如果減少對原料A的下限，那么總成本將得到改進。? 在常數(shù)項范圍一欄中，知道當約束條件1 的常數(shù)項在 300 475范圍內(nèi)變化，且其他約束條件不變時，約束條件1 的對偶價格不變；當約束條件2 的常數(shù)項在負無窮到250 范圍內(nèi)變化，而其他約束條件

33、的常數(shù)項不變時，約束條件2 的對偶價格不變，仍為 0 ；當約束條件3 的常數(shù)項在475 700 內(nèi)變化，而其他約束條件的常數(shù)項不變時，約束條件 3的對偶價格不變，仍為 1。? 注意：? 當約束條件中的常數(shù)項增加一個單位時，最優(yōu)目標函數(shù)值增加的數(shù)量稱之為影子價格。在求目標函數(shù)最大時，當約束條件中的常數(shù)項增加一個單位時，目標函數(shù)值增加的數(shù)量就為改進的數(shù)量，所以影子價格等于對偶價格；在求目標函數(shù)值最小時，改進的數(shù)量就是減少 的數(shù)量，所以影子價格即為負的對偶價格。? “管理運籌學 ”軟件可以解決含有100個變量 50個約束方程的線性規(guī)劃問題， 可以解決工商管理中大量的問題。如果想要解決更大的線性規(guī)劃問

34、題，可以使用由芝加哥大學的L.E.Schrage開發(fā)的Lindo計算機軟件包的微型計算機版本 Lindo/PC。第四章 線性規(guī)劃在工商管理中的應用? § 1人力資源分配的問題;? §2生產(chǎn)計劃的問題；? §3套裁下料問題；? §4配料問題；? §5投資問題。§ 1人力資源分配的問題班次時間所需人數(shù)16： 0010, 00210： 0014： 00 :70314： 0018： 0060413； 00 22： 0050522： 00 21 002052； 00a 0030例1.某晝夜服務的公交線路每天各時間段內(nèi)所需司機和乘務人員數(shù)如下：設

35、司機和乘務人員分別在各時間段一開始時上班，并 連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務人 員，既能滿足工作需要，又配備最少司機和乘務人員？解：設Xi表示第i班次時開始上班的司機和 乘務人員數(shù)，這樣我們建立如下的數(shù)學模型。目標函數(shù)： Min Xi + X2 + X3 + X4 + X5 +約束條件：s.t.Xi + X6> 60Xi + X2> 70X2 + X3> 60X3 + X4> 50X4 + X5> 20X5 + X6> 30時間所需售貨員人數(shù)星期日2S星期一15r 星期二24星期三25星期四19星期五31星期六28Xi, X2, X3, X4

36、, X5, X6 > 0例2. 一家中型的百貨商場，它對 售貨員的需求經(jīng)過統(tǒng)計分析如下表所 示。為了保證售貨人員充分休息，售貨 人員每周工作5天，休息兩天，并要求 休息的兩天是連續(xù)的。問應該如何安排 售貨人員的作息，既滿足工作需要，又 使配備的售貨人員的人數(shù)最少？解：設Xi ( i = 1,2,7)表示星期一至日開始休息的人數(shù)，這樣我們 建立如下的數(shù)學模型。目標函數(shù): 約束條件:Min s.t.X1+ X2 + X3 + X4+ X5 + 】X1+X2 + X3 + X4 +X5 > 28X2 +X3 + X4 + X5 +X6 > 15X3 +X4 + X5 + X6 +X

37、7 > 24X4+X5 + X6 + X7 +X1 > 255+X6 + X7 + X1 +X2 > 196+X7 + X1 + X2 +X3 > 31X7 +X1 + X2 + X3 +X4 > 28X1, X2, X3, X4, X5, X6, X7 > 0+ X7§ 2生產(chǎn)計劃的問題例3.某公司面臨一個是外包協(xié)作還是自行生產(chǎn)的問題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品,都需要經(jīng)過鑄造、機加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自 行生產(chǎn)，但產(chǎn)品內(nèi)必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如表。問：公司為了獲得最大利潤，甲、 乙、丙三種產(chǎn)品各生

38、產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應 多少件？甲乙鹵資源限制鑄造工時（小時胖）510?goco機加工工時（小時解）$4SP L2而Q監(jiān)配工時（小時琳）322LOMu自產(chǎn)蹲件成本（元/件）354外切禱件成本（元作為36-機加工威本（元J件213裝配成本（元，件）322產(chǎn)品隹價（元j件）7二1916X4, X5分別為由外協(xié)鑄解：設X1,X2,X3分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù), 造再由本公司加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。求Xi的利潤：利潤=售價-各成本之和產(chǎn)品甲全部自制的利潤=23-（3+2+3）=15產(chǎn)品甲鑄造外協(xié)，其余自制的利潤=23-（5

39、+2+3）=13產(chǎn)品乙全部自制的利潤=18-（5+1+2）=10產(chǎn)品乙鑄造外協(xié)，其余自制的利潤=18-（6+1+2）=9產(chǎn)品丙的利潤=16-（4+3+2）=7可得到 Xi （i = 1,2,3,4,5）的利潤分別為15、10、7、13、9元。目標函數(shù)： 約束條件：63通過以上分析，可建立如下的數(shù)學模型：Max 15 Xi + 10 X2 + 7 X3 + 13 X4 + 9 X55 Xi + 10 X2 + 7 X3 < 8000X1 + 4 X2 + 8 X3 + 6 X4 + 4 X5 < 12000X1 + 2 X2 + 2 X3 + 3 X4 + 2 X5 < 100

40、001, X2, X3, X4, X5 > 0§ 2生產(chǎn)計劃的問題例4.永久機械廠生產(chǎn)I、H、田三種產(chǎn)品，均要經(jīng)過 A、B兩s.t. 5xiii + 10x211 6000(設備Ai )7xii2 + 9x212 + 12 x312工 10000(設備A2 )6xi2i + 8x2210 4000(設備Bi )4xi22+ 11x322工 7000(設備B2 )7xi230 4000(設備B3 )xiii +xi12-xi21-xi22-xi23 = 0（I產(chǎn)品在A、B工序加工的數(shù)量相等）x2ii+x212-x221二 0（n產(chǎn)品在A、B工序加工的數(shù)量相等）x312-x322=

41、0（出產(chǎn)品在A、BX序加工的數(shù)量相等）xijk >0 , i=1,2,3; j：=1,2; k = 1,2,3解：設Xijk 表木第道工序加工。設有兩種規(guī)格的設備 A、A2能完成A工序；有三種規(guī)格的設備B、詼R能完成 B工序。I可在A、B的任何規(guī)格的設備上加工；II可在任意規(guī)格的A設備上加工，但對B工序, 只能在B設備上加工；田只能在A與B2設備上加工。數(shù)據(jù)如表。問：為使該廠獲得最大利潤， 應如何制定產(chǎn)品加工方案？設備產(chǎn)品單件工時設備的 有效臺時滿負荷時的 設備費用IIIIII血1510 1一(5C003 CIO陽.7y1211)000321Bi8S4C002504117C007羽74C

42、00210原料（元厝）0.250.35Q.5O售價（元/中）J.252.00ISOi種產(chǎn)品，在第j種工序上的第k種設備上加工的數(shù)量。建立如下的數(shù)學模型目標函數(shù)為計算利潤最大化，利潤的計算公式為：的總臺時數(shù)）之和 這樣得到目標函數(shù)：Max（1.25-0.25）（x 300/6000（5x 250/4000（6x 經(jīng)整理可得：利潤=（銷售單價-原料單價）*產(chǎn)品件數(shù)之和-（每臺時的設備費用*設備實際使用iii+xii2)+(2-0.35)x 22i+(2.80-0.5)x312 11l + 10x211)-321/10000(7x ii2 + 92i2+i2x3i2)- i2i+8x22i)-783

43、/7000(4x i22+1 1x322)-200/4000(7x 123).Max0.75xiii+0.7753 xii2+1.15 x2ii+1.3611 x2i2+1.9148 x3i2-0.375 xi2i-0,5 x22i-0.4475 xi22-1.2304 x322-0.35 xi23方案1方案2方案3方案4方案52.9m12010工1 m02211,5m31203合計7.47 3P 7.27.16.6剩余料頭00 10.20.30.S§ 3套裁下料問題例5.某工廠要做100套鋼架，每套用長為2.9m,2.1 m,1.5 m的圓鋼各一根。已知原料每根長7.4 m,問：應

44、如何下料，可使所用原料最??？解：共可設計下列5種下料方案，見左表：?用管理運籌學'軟件計算得出最優(yōu)下料方案：按方案1下料30根；按方案2下料10根；按方案 4下料50根。即 xi=30;X2 = 10 ；X3=0；X4=50 ；X5=0；只需90根原材料就可制造出100套鋼架。?注意：在建立此類型數(shù)學模型時，約束條件用大于等于號比用等于號要好。因為有時在套用 一些下料方案時可能會多出一根某種規(guī)格的圓鋼，但它可能是最優(yōu)方案。如果用等于號，這 一方案就不是可行解了。§ 4配料問題例6.某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如右表。問：該廠應如何安

45、排生產(chǎn)，使利潤收入為最大？解：設Xj表示第i種（甲、乙、丙）產(chǎn)品中原料 j的 含量。這樣我們建立數(shù)學模型時，要考慮：產(chǎn)品g稱期帽總求W（元?。┘字挚?不少干50%，原的4 2襁過25M30二原楸11不少于班,搬旗IN榜過江帆不的T艮25對于甲： X11, X12, X13；對于乙:X21 , X22 , X23 ；對于丙：X31 , X32 ,X33 ；對于原料1：X11,X21 ,X31；對于原料2：X12,X22,X32 ；對于原料3 ：X13,X23,X33 ；目標函數(shù)：利潤最大，利潤 =收入-原料支出約束條件：規(guī)格要求4個；供應量限制 3個。每天域?qū)W網(wǎng)毆L100652100253印3

46、5從第2個表中，生產(chǎn)甲乙丙的原材料不能超過原材料的供應限額，故有(X11+X21+X31) < 100(X12+X22+X32) < 100(X13+X23+X33) < 60通過整理，得到以下模型：目標函數(shù)：MaX z = -15 X11+25X12+15X13-30 X21+10X22-40 X31-10 X33 約束條件：s.t. 0.5Xn-0.5X12 -0.5X13> 0 (原材料1不少于50%-0.25X11+0.75X12 -0.25X13< 0（原材料2不超過25%0.75X21-0.25X22 -0.25X23> 0（原材料1不少于25%

47、-0.5X21+0.5X22 -0.5X23< 0（原材料2不超過50%X11+X21 +X31< 100（供應量限制）X12+X22 +X32< 100（供應量限制）X13+X23 +X33< 60（ 供應量限制）Xij >0 , i = 1,2,3; j = 1,2,3例7.汽油混合問題。一種汽油的特性可用 兩種指標描述，用辛烷數(shù)”來定量描述其 點火特性，用“蒸汽壓力”來定量描述其 揮發(fā)性。某煉油廠有1、2、3、4種標準汽 油，其特性和庫存量列于表4-6中，將這 四種標準汽油混合，可得到標號為1,2的 兩種飛機汽油，這兩種汽油的性能指標及 產(chǎn)量需求列于表4-7

48、中。問應如何根據(jù)庫 存情況適量混合各種標準汽油，既滿足飛 機汽油的性能指標，又使2號汽油滿足需 求，并使得1號汽油產(chǎn)量最高？解：設xj為飛機汽油i中所用標準汽油j的數(shù)量（L）。目標函數(shù)為飛機汽油 1的總產(chǎn)量：,11 + ”21< 380000<265200< 408100場#汽油蒸汽壓力粵cnO庫存重CL）110757.11X1013SQ00D293.011.38 X1012(55200387,05.159X1040S1DO410SJ028.45 XI。士13U1D0飛機汽油產(chǎn)卻融1不小于91不大于9兆X10 32不“吁100不大于99(5 X10-3不少于25UU00產(chǎn)量約

49、束為飛機汽油v + x人1日七42的產(chǎn)量：<130100由物理中的分壓定律,x21x22PVx23 x24 250000n可得有關蒸汽壓力的約束條件:Pjvjj 12.85x11 1.42x122.85x21 1.42x22同樣可得有關辛烷數(shù)的約束條件為：4.27x13 18.49x144.27x23 18.49x2416.5x117.5xii2.0x127.0xi24.0為3 17.0x14 013.0x13 8.0x140max x11x12x13x14x21x22x23x24250000x11x21x12x22x13x23x14x242.85為11.42x1238000026520

50、04081001301004.27x13 18.49為42.85x211.42x224.27x23 18.49x2,16.5x112 x12 4x1317 x1407.5x217 x22 13x：238x240xj 0,(i1,2; j1,2,3, 4)14庫存量約束為：由管理運籌學軟件求解得:max（x11 x12 x13 x14） 933 399.938 x11 261966.078x12 265200x13 315672.219x14 90561.688x21 118033.906x220x23 92427.758x24 39538.309§ 5投資問題例8.某部門現(xiàn)有資金 2

51、00萬元，今后五年內(nèi)考慮給 以下的項目投資。已知：項目A :從第一年到第五年 每年年初都可投資，當年末能收回本利110%;項目B：從第一年到第四年每年年初都可投資，次年末能 收回本利125%,但規(guī)定每年最大投資額不能超過30萬元；項目C:需在第三年年初投資， 第五年末能收回本利 140%,但規(guī)定最大投資額不能 超過80萬元；項目D:需在第二年年初投資，第五 年末能收回本利155%,但規(guī)定最大投資額不能超過 100萬元。據(jù)測定每萬元每次投資的風險指數(shù)如右表：項目風險指數(shù)（次/萬元）A1B3C4D5.5問：a）應如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b）應如何確定這

52、些項目的每年投資額，使得第五年年末擁有資金的本利在330萬元的基礎上使得其投資總的風險系數(shù)為最??？2）約束條件：第一年：A當年末可收回投資，故第一年年初應把全部資金投出去，于是xn+ x12 = 200 ;第二年：B次年末才可收回投資，故第二年年初有資金1.1 x11 ,于是 x21 + x22+ x24 = 1.1 x11 ；第三年：年初有資金1.1x21+1.25x12,于是x31+x32+ x33= 1.1 *21+1.25»2 ；第四年：年初有資金1.1x31+1.25x22,于是x41+x42 = 1.1x31+ 1.25x22；第五年：年初有資金1.1x41+1.25x3

53、2,于是x51=1.1 x41 +1.25 x32；B、C D的投資限制：xi2 < 30 （ i =1、2、3、4 ） , x33 0 80 , x24 0 1003）目標函數(shù)及模型：a） Max z = 1.1x51+ 1.25 x42+ 1.4 x33 + 1.55 x24s.t.xn+ x12 = 200x21 + x22+ x24 = 1.1 x11 ；x31 + x32+ x33 = 1.1 x21+ 1.25 x12；x41 + x42 = 1.1 x31+ 1.25 x22；x51 = 1.1 x41+ 1.25 x32；Xi2 w 30 （ i =1、2、3、4 ） , X33 & 80, X24 & 100xu > 0 （ i = 1、2、3、4、5; j = 1