2014運籌學上機例題

1、,東 北 林 業(yè) 大 學,§1.1線性規(guī)劃問題及其數學模型,經整理,得到該問題的數學模型為:,maxZ = 6X1 + 4X2 2X1 + 3X2 ≤ 100 4X1 + 2X2 ≤ 120 X1≥0, X2 ≥0,,s.t.,對模型經求解后, 可得到X1,X2的值,即該問題的最優(yōu)生產計

2、劃方案. X1,X2稱為決策變量.,,§1.6應用舉例,東 北 林 業(yè) 大 學,一、套裁下料問題,問題的提出：某木工廠要做100套木架，每套用長為2.9 m, 2.1m, 1.5m的木方各一根。已知原料每根長7.4 m，問：應如何下料，可使所用原料最??？,2.1m,2.9m,1.5m,,7.4,2.9+2.1+1.5=6.5，7.4 - 6.5=0.9,,解:考慮套裁可列出各種下料方案,,,,§1.6應用舉例,東 北

3、 林 業(yè) 大 學,2.1m,2.9m,1.5m,把各種下料方案按剩余料頭從小到大順序列出,設 xj 為第j 種下料方案使用的原料根數。以料頭最省為目標，則模型為:(最優(yōu)方案）,min z = 0.1 x2+ 0.2x3+0.3 x4+0.8 x5 + 0.9 x6+1.1 x7 +1.4x8 x1 + 2x2 + x4 + x6

4、 ≥100 s.t. 2x3 + 2x4 + x5 + x6 + 3x7 ≥100 3x1+ x2 + 2x3 + 3x5 + x6 + +4x8 ≥100

5、 xj ≥0,,,東 北 林 業(yè) 大 學,min z = 0.1 x2+ 0.2x3+0.3 x4+0.8 x5 x1 + 2x2 + x4 ≥100 s.t. 2x3 + 2x4 + x5≥100 3x1+ x2 + 2x3 + 3x5≥100

6、 x1, x2, x3, x4, x5 ≥0,設 xj 為第j 種下料方案使用的原料根數。以料頭最省為目標，則模型為:,,X*=( 30，10，0，50，0 )T ，Z*=16,(次優(yōu)方案）,,問題的提出：某晝夜服務的公交線路每天各時間段內所需司機和乘務人員數如下： 設司機和乘務人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務人員，既能滿足

7、工作需要，又配備最少司機和乘務人員?,二、人力資源分配的問題,東 北 林 業(yè) 大 學,解：設 xi 表示第i班次時開始上班的司機和乘務人員數 目標函數： Minz=x1 + x2 + x3 + x4 + x5 + x6 約束條件：s.t. x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60

8、 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0,東 北 林 業(yè) 大 學,,§1.6應用舉例,東 北 林 業(yè) 大 學,問題的提出：某部門在今后5年內考慮給以下幾個項目投資。

9、 項目A：從第一年到第四年初可投資，并于次年末收回本利115%； 項目B：第三年初可投資，到第五年末能收回本利125%，但規(guī)定最大投資額不超過4萬元；項目C：第二年初可投資，到第5年末收回本利140%，但規(guī)定最大投資額不超過3萬；項目D：每年初都可投資，于當年末歸還，并加利息6%。該部門現(xiàn)有資金10萬元，問應如何確定該項目的投資，使到第五年末資金本利總額最大。,四、連續(xù)投資問題,解：設 xij分別表示給第

10、i 年年初項目A、B、C、D的投資額。根據已知條件將有意義的變量列表中:,,§1.6應用舉例,東 北 林 業(yè) 大 學,約束條件為:,(1)投資額等于擁有的資金額,第1年: x11 +x14=100000,第2年: x21 +x23 +x24 =1.06x14,第3年: x31 +x32 +x34 =1.15x11 +1.06x24,第4年: x41 +x44 =1.15x21 +1.06x34,第5年: x54 =

11、1.15x31 +1.06x44,(2)投資風險限制,x32≤40000,x23≤30000,(3)變量非負限制,xij≥0,目標函數:,max z =1.15x41+1.25x32+1.4x23+1.06x54,(z*=143750元),,東 北 林 業(yè) 大 學,§2.6靈敏度分析,二、靈敏度分析的具體內容1.cj變化對最優(yōu)解的影響2.bi變化對最優(yōu)解的影響3.增加或減少一個變量4.增加或減少一個約束5.aij變化

12、對最優(yōu)解的影響,四、靈敏度分析,例題：已知某企業(yè)計劃生產3種產品A,B,C，其資源消耗和利潤情況如表，問如何安排產品產量，可獲得最大利潤？,,,東 北 林 業(yè) 大 學,,,初始單純形表 表1,四、靈敏度分析,東 北 林 業(yè) 大 學,最優(yōu)單純形表 表2,四、靈敏度分析,東 北 林 業(yè) 大 學,四、靈敏度分析,1.目標函數價值系數Cj的靈敏度分析,第一，非基變量的價值系數靈敏度分析,分析：由于非基變量的價值系數的改

13、變只對最優(yōu)解的檢驗數起作用，因此Cj的改變，只使非基變量檢驗數發(fā)生變化，其他（最優(yōu)解和目標函數值）不變。,問題（1）如果例題中C3發(fā)生改變，求保持原最優(yōu)生產方 不變的C3的取值范圍。 （2） 如果C3=10，求解最優(yōu)的生產方案。,作法：直接將新的價值系數反應到最終的單純形中，計算檢驗數。,東 北 林 業(yè) 大 學,解：（1）,1.目標函數價值系數Cj的靈敏度分析,,,,即,時，原最優(yōu)生產方案就

14、不會發(fā)生改變。,,表3,東 北 林 業(yè) 大 學,,表 4,1.目標函數價值系數Cj的靈敏度分析,解：（2）,,,不是最優(yōu)的生產方案,東 北 林 業(yè) 大 學,表 5,1.目標函數價值系數Cj的靈敏度分析,經計算得，,,東 北 林 業(yè) 大 學,四、靈敏度分析,1.目標函數價值系數Cj的靈敏度分析,第二，基變量的價值系數靈敏度分析,分析：由于基變量價值系數的改變使所有的檢驗數發(fā)生改變，若所有的檢驗數仍小于等于0，對最優(yōu)方案沒有影響，但目標值發(fā)

15、生變化。,問題（1）如果例題中C1發(fā)生改變，求保持原最優(yōu)生產方案不變的C1的取值范圍。 （2） 如果C1=10，求解最優(yōu)的生產方案。,作法：直接將新的價值系數反映到最終的單純形中，計算檢驗數。,東 北 林 業(yè) 大 學,表 6,解：（1）,將新的價值系數反應到最終的單純形中，計算檢驗數。,解得,,,1.目標函數價值系數Cj的靈敏度分析,東 北 林 業(yè) 大 學,,表 7,解：（2）,1.目標函數價值系數Cj的靈敏度分析,,不是最優(yōu)的

16、生產方案。,東 北 林 業(yè) 大 學,表 8,經計算得，,,1.目標函數價值系數Cj的靈敏度分析,東 北 林 業(yè) 大 學,,1.求使最優(yōu)解保持不變的c1的取值范圍？2.求使最優(yōu)基保持不變的b1的取值范圍？3.欲增加產品D，單件利潤為c6=5千元，工時消耗與材料消耗為2和3 ，問是否應投產D產品？4.增加約束：2x1+2x2+x3≤5,問該公司的生產方案是否應改變？,練習,最終單純形表,,東 北 林 業(yè) 大 學,練習1： 在例1.1[

17、某企業(yè)（企業(yè)Ⅰ）生產兩種產品，需要兩種原料，有關數據見表。如何安排生產計劃可使總的收益最大。]的基礎上提出如下要求: (1)求使原最優(yōu)解不變的c2變化范圍; (2)若c1變?yōu)?2,求新的最優(yōu)解.,maxZ = 6x1 + 4x2 2x1 + 3x2 ≤100 4x1 + 2x2 ≤ 120 x1≥0, x2 ≥0X1=20, x2=20, Z=200,,s.t.,解:(1) △c2變化范圍

18、,,,東 北 林 業(yè) 大 學,,,6 4 0 0,θ,,,,,,46,20,1 0 -1/4 3/8,0 1 1/2 -1/4,20,0 0 -1/2 -5/4,例1.1的最終單純形表,,,東 北 林 業(yè) 大 學,,,6 c2 0

19、 0,θ,,,,,,6,20,1 0 -1/4 3/8,0 1 1/2 -1/4,20,0 0,c2,=0-[(c2)×1/2+6×(-1/4)],=0-[(c2)×(-1/4)+6×3/8],要使最優(yōu)解不變,應有:,≤0,≤0,也就是c2在3到9之間變化,最優(yōu)解不變.,,,,,6

20、4 0 0,θ,,,,,,46,20,1 0 -1/4 3/8,0 1 1/2 -1/4,20,0 0 -1/2 -5/4,例1.1的最終單純形表,解:(2)c1變?yōu)?2,,,12 4 0 0,θ,,,,,,412,20,1

21、 0 -1/4 3/8,0 1 1/2 -1/4,20,0 0,,,東 北 林 業(yè) 大 學,,,12 4 0 0,θ,,,,,,,,,412,20,1 0 -1/4 3/8,0 1 1/2 -1/4,20,0

22、 0,1,-7/2,,0 2 1 -1/2,012,40,30,1 1/2 0 1/4,0 -2 0 -3,最優(yōu)解為：x1=30,x3=40,x2=x4=0 z=360,2. 資源約束量b的靈敏度分析,四、靈敏度分析,問題（1）如果例題中b1發(fā)生改變，求保持原最優(yōu)基不變的b1的取值范圍。（2）如果b1=30，求解最優(yōu)的生產方案。,,,分析： 資源約束量

23、b的變化只影響最優(yōu)解的變化和最優(yōu)值的變化。因此，當 時，最優(yōu)基不變（即生產產品的品種不變，但生產數量和最優(yōu)值會發(fā)生變化）。,,作法： 求解不等式 ，從中可以解得b的變化范圍，若 中有小于0的分量，則需用對偶單純形法迭代，以求出新的最優(yōu)方案。,東 北 林 業(yè) 大 學,,資源約束量b的靈敏度分析,解： (1),,東 北 林 業(yè) 大 學,資源約束量b的靈敏度分析,即,,解得,原材料甲的供應量

24、 在之間變化時，并不影響最優(yōu)基，即生產品種不發(fā)生改變，但生產方案發(fā)生改變。,最優(yōu)的生產方案調整為,東 北 林 業(yè) 大 學,資源約束量b的靈敏度分析,解： (2),,,由于第2個分量小于0，這時需要利用對偶單純形法進行迭代，以求出新的最優(yōu)生產方案。這時單純形表變?yōu)?表9,東 北 林 業(yè) 大 學,資源約束量b的靈敏度分析,對偶單純形法的步驟,第一，列出初始單純性表。檢查b列的數字，若都為非負，且檢驗數都為非正，則得到最優(yōu)解，停止

25、運算。若b列的數字，至少還有一個負分量，檢驗數保持非正，轉第二。,,,第二，確定換出變量。按 對應的基變量 為換出變量 幻燈片 90,東 北 林 業(yè) 大 學,資源約束量b的靈敏度分析,,,,,第三，確定換入變量。在單純表中檢查出基變量所在的行的系數，若所有的系數 ，則無可行解，停止計算。,,第四，以 為主元素，按照單純形法進行換基迭代，得到新的單純形表?；脽羝?/p>

26、 92,東 北 林 業(yè) 大 學,若存在 ，計算,所對應的列變量的非基變量 為換入變量?；脽羝?91,表 10,經計算得，,資源約束量b的靈敏度分析,當 時，最優(yōu)的生產方案調整為,東 北 林 業(yè) 大 學,,1.求使最優(yōu)解保持不變的c1的取值范圍？2.求使最優(yōu)基保持不變的b1的取值范圍？3.欲增加產品D，單件利潤為c6=5千元，工時消耗與材料消耗為2和3 ，問是否應投產D產品？4.增加約束：2x1+2x2

27、+x3≤5,問該公司的生產方案是否應改變？,練習,最終單純形表,,東 北 林 業(yè) 大 學,運輸問題一般表述為：某種物資有產地m個, 其產量分別為ai(i=1,2,…,m), 有需求地(也稱銷地)n個，其需求量(也稱銷量)分別為bj(j=1,2,…,n), 從產地Ai到銷地Bj的每單位物資的運費為Cij。如何組織調運（擬定調運方案）才能使總運輸費用最小。,一、什么是運輸問題,例3.1 問題的提出,,有三個林業(yè)局，木材產量分別為70、40

28、和90萬立方米，準備向四個木材加工廠供應原木。各木材加工廠的原木需求量分別為30、60、50和60萬立方米，運輸價格見下表。現(xiàn)需擬定總運費最小的木材調運方案 。,§3.1運輸問題及其數學模型,,東 北 林 業(yè) 大 學,§3.1運輸問題及其數學模型,運輸問題數據表（小方格內的數字是運價,單位：元／立方米）,,東 北 林 業(yè) 大 學,二、運輸問題的數學模型,分析：目的-- …… 目標-- ……,設置變量：,x

29、ij表示從第i個林業(yè)局（產地）調運給第j個木材加工廠（銷地）的木材（物資）數量。,目標函數：,,Ａ1、Ａ2、Ａ3調運給B1、B2 、B3、B4 的運費分別為：,,,,東 北 林 業(yè) 大 學,約束條件：,（1）產地的木材應全部運出，,Ａ1：,Ａ2：,Ａ3：,,,,,即某產地運出的總量與產量相等。,,東 北 林 業(yè) 大 學,（2）銷地的需求應得到滿足，,即調運給銷地的總量與其需求量相等。,B1：B2：B3：B4：,,,,,

30、,（3）變量非負限制。,,東 北 林 業(yè) 大 學,§3.1運輸問題及其數學模型,整理得到該問題的數學模型為:,,s.t.,,東 北 林 業(yè) 大 學,§4.2 分配問題與匈牙利法,一、問題的提出與數學模型 分配問題也稱指派問題：假定有n項任務，恰好n個人承擔，第i人完成第j項任務的花費(時間或費用等)為cij （cij≥0），如何指派使總花費最省？,例 問題的提出　　有５個工程隊，準備完成５項任務，

31、由于工程隊的設備、人力等各不相同， 各項任務的條件也不相同，因此每個工程隊完成不同任務所需要的時間也不相同，見下表。如何分配任務才能使完成任務的總時間最少。,可行的分配方案：每人一項任務，每項任務由一個人承擔。,,東 北 林 業(yè) 大 學,§4.2 分配問題與匈牙利法,分析：目的—　　　　　目標—,設置變量：,目標函數：,… … … … …,,,單位:天,,東

32、 北 林 業(yè) 大 學,§4.2 分配問題與匈牙利法,約束條件：,（１）每個工程隊只能去完成一項任務,… … … … … …,1工隊,5工隊,,,,（2）每項任務只能一個工程隊來完成,… … … … … …,1工作,5工作,,,,,東 北 林 業(yè) 大 學,§4.2

33、分配問題與匈牙利法,（3）每一個工程隊只有完成或不完成某項任務兩種可能,整理得該分配問題的數學模型:,,s.t.,運動員選拔問題某校藍球隊準備從以下6名預備隊員中選拔3名為正式隊員，并使平均身高盡可能高，這6名預備隊員情況如下表所示，試建立數學模型。隊員的挑選要滿足下列條件：（1）至少補充一名后衛(wèi)隊員；（2）大李或小田中間最多入選一名；（3）最多補充一名中鋒；（4）如果大李或小趙入選，小周就不能入選。,設 為

34、各隊員是否被選上（j=1,2,…6）(1-是，0-否）,,東 北 林 業(yè) 大 學,物流問題：（某集裝箱運輸公司的箱型標準體積24m3，重量13t,現(xiàn)有兩種貨物可以裝運，甲貨物體積5m3、重量2t、每件利潤2000元；乙貨物體積4m3、重量5t、每件利潤1000元。如何裝運獲利最多？）中，設集裝箱有車運和船運兩種方式，如果用船運時重量20t .試確定集裝箱托運甲和乙貨物的數量及運輸方式,使總利潤最大.,y=,1 車運 0 船運,,兩種

35、運輸方式只能選其一，為了統(tǒng)一在一個問題中，引入0-1變量,則模型為：,,東 北 林 業(yè) 大 學,maxZ=2000x1+1000x2 5x1+4x2≤24 2x1+5x2≤13 +（1-y)M 2x1+5x2≤20 + yM x1 ≥,x2 ≥0,且為整數 其中，M是相當大的正數,,s.t.,,相互排斥的約束條件,生產計劃問題：教材p102-4.13,

36、設 為在第j種設備加工的產品數（j=1,2,3）,東 北 林 業(yè) 大 學,,,營銷問題： 某公司打算向它的三個營業(yè)區(qū)增設6個銷售店，每個營業(yè)區(qū)至少增設一個。從各區(qū)賺取的利潤與增設的銷售點個數有關，其數據如表所示。問各區(qū)應分配幾個增設的銷售店，才能使總利潤最大。,東 北 林 業(yè) 大 學,,,東 北 林 業(yè) 大 學,,東 北 林 業(yè) 大 學,某大學管理科學與工程專業(yè)碩士生要求課程計劃中必須選修兩門數學類、兩門運籌學類和兩門計算機類

37、課程。課程中有一些只歸屬某一類，如微積分歸屬數學類，計算機程序歸屬計算機類；但有些課程是跨類的，如運籌學可歸為運籌學類和數學類，數據結構可歸為計算機類和運籌學類，管理統(tǒng)計歸屬為數學和運籌學類，計算機模擬歸屬為計算機類和運籌學類，預測歸屬為運籌學類和數學類，凡歸屬兩類的課程選學后可認為兩類中各學了一門課。此外有些課程要求先學習先修課，如學計算機模擬或數據結構必須先修計算機程序，學管理統(tǒng)計必先修微積分，學預測必須先修管理統(tǒng)計。問一個碩士生最

38、少應學幾門及哪幾門，才能滿足上述要求。,對微積分、運籌學、數據結構、管理統(tǒng)計、計算機模擬、計算機程序和預測7門課程的編號為1,2，…7。,,每類課程至少選2門,選修課程要求,,§5.1 問題的提出與目標規(guī)劃模型,東 北 林 業(yè) 大 學,二、目標規(guī)劃模型,例5.1 問題的提出：對例1.1[某企業(yè)生產兩種產品，需要兩種原料,有關數據見表。如何安排生產計劃可使總的收益最大。]企業(yè)管理人員又提出如下目標要求:,第三目標P3：A資源要

39、充分利用，但不能超額。B資源可超額利用，但最多不能超額8個單位。A、B資源的權系數分別為7和3。,由市場預測可知，甲、乙的產量不能超過40和30件。如何制定滿足上述目標要求的生產計劃方案.,第一目標P1：收益不低于180千元；,第二目標P2：甲乙的產量盡量滿足5:3的關系；,試建立該問題的目標規(guī)劃模型。,,§5.1 問題的提出與目標規(guī)劃模型,東 北 林 業(yè) 大 學,目的 -- 制定一個生產計劃方案。,（甲乙各生產多少件）,目標

40、 -- 管理目標和實際可能完成的目標之間的偏差最小。（目標規(guī)劃模型中的目標均如此表示）,設置變量：,①決策變量，x1 , x2分別表示產品甲、乙的產量。,②偏差變量，偏差變量有正負之分，用正偏差d+和負偏差d-表示。d+表示超過目標值的部分；d-表示不足目標值的部分。,顯然有d-×d+=,0。,解：,,東 北 林 業(yè) 大 學,目標規(guī)劃練習：某電視機廠裝配彩色和黑白兩種電視機，每裝配一臺電視機需占用裝配線1小時， 裝配線每周計劃

41、開動40小時。 預計市場每周彩色電視機的銷量是24臺，每臺可獲利80元； 黑白電視機的銷量是30臺，每臺可獲利40元。該廠確定的目標為：,p1：充分利用裝配線每周計劃開動40小時；p2：允許裝配線加班，但加班時間每周盡量不超過10小時；p3：裝配電視機的數量盡量滿足市場需要。因彩色電視機利潤高，取其權系數為2。 試建立這問題的目標規(guī)劃模型，并求解彩色和黑白電視機的產量。,,東 北 林 業(yè) 大 學,解：設x1，x2分別表示彩色和黑