9299.net
大學生考試網 讓學習變簡單
當前位置:首頁 >> >>

管理運籌學:管理科學方法講義【謝家平編著】_圖文

管理運籌學:管理科學方法講義【謝家平編著】_圖文

管理運籌學
-管理科學方法

教材與參考書籍
? 教材:
? 謝家平編著.管理運籌學:管理科學方法, 中國人民大學出版社,2010

? 參考書:
? 費雷德里克. 數據、模型與決策,中國財政經濟出版社,2001

2

OR:SM

講授提綱
? ? ? ? ? ? ? ? ? ? ? ? ?
3

緒 論 第一章 線性規劃 第二章 線性規劃討論 第三章 對偶規劃 第四章 整數規劃 第五章 目標規劃 第六章 動態規劃 第七章 網絡分析 第八章 網絡計劃 第九章 決策分析 第十章 方案排序 第十一章 庫存控制 第十二章 排隊理論

靜態規劃

淡化數學算法 計算機求解

動態優化 離散優化

隨機優化
OR:SM

考核方式
? 結課考試:
? 筆試 每章一題 70%

? 案例研究:
? 選擇合適方法結合企業實際進行應用 20%

? 平時成績:
? 上課情況 10%

4

OR:SM

管理運籌學的稱謂
? 管理運籌學是一門研究如何最優安排的學科。 ? Operations Research
? 日本譯作“運用學” ? 香港、臺灣譯為“作業研究” ? 我國譯作“運籌學”
? 源于古語“運籌帷幄之中,決勝千里之外” ? 取“運籌”二字,體現運心籌謀、策略取勝

? Management Science 管理科學
? 運用數學、統計學和運籌學中的量化分析原理和方法,建 立數學模型/計算機仿真,給管理決策提供科學依據。

5

OR:SM





? ? ? ? ? ?

一、發展歷史 二、學科作用 三、學科性質 四、工作程序 五、學科體系 六、學習要求

6

OR:SM

一、發展歷史
1. 早期的運籌思想
? 齊王賽馬 ? 沈括運軍糧 ? 渭修皇宮 ? 科學管理

2. 軍事運籌學階段
? 20世紀40年代誕生于英美 ? 1940年,英國為對付德國空軍的空襲,使用了雷達,但沒有科學布 局,效果不好。為解決這個問題,成立運籌學小組,稱 Operational Research,意為作戰研究。 ? 美國和加拿大也在軍隊設立運籌學小組,稱Operations Research, 協助指揮官研究戰略及戰術問題。

3. 管理運籌學階段
? 戰后許多從事運籌學研究的科學家轉向了民用問題的研究,使運籌 學在企業管理方面的應用得到了長足進展。
7 OR:SM

二、學科作用 理念的重要性
? 企業的成功要素中:
? 觀念意識更新 ? 人文文化 ? 技術優勢 47% 35% 18%

? 決策意識的科學性
? 成功決策 ? 正確決策
8 OR:SM

二、學科作用
1. 量化管理的重要性
? 管理科學是對與定量因素有關的管理問題通過應用科學 的方法進行輔助管理決策的一門學科。
? 目的:用科學方法分析管理問題,為管理者決策提供依據 ? 目標:在企業經營內外環境的限制下,實現資源效用最大

? 定性到定量分析,數量界限的重要性:量變引起質變
組織中存 在的問題 定性分析 評價與評估 定量分析 量化管理是第一步,它導致控制,并最終實現改進 如果不能量化某些事情,那么就不能理解它 如果不能理解它,那么就不能控制它 如果不能控制它,那么就不能改進它 ——H. James Harrington
9 OR:SM

決策

二、學科作用
2. 量化思考使人理性
? 冰淇淋實驗: ? 一杯A有70克,裝在50克的杯子里,看上去要溢出了 ? 一杯B是80克,裝在100克的杯子里,看上去還沒裝滿
單獨憑經驗判斷時,在相同的價格上,人們普遍選擇A

? 聽一場音樂會:網絡訂票的票價500元,不去可退票 ? 情況1:在你馬上要出發的時候,發現你把最近的價值 500元的電話卡弄丟了。你是否還會去聽這場音樂會?

實驗表明,大部分的回答者仍舊會去聽 ? 情況2:假設昨天花500元錢買一張今晚的音樂會取票單。 在你出發時,發現把票單丟了。如果去聽音樂會,就必 須再花500元錢買張票,去還會不去? 結果卻是,大部分人回答說不去了
10 OR:SM

二、學科作用
3. 量化分析輔助決策
160,000

盈虧平衡分析
Revenue = 900 x Profit

120,000 Cost = 50,000 + 400 x

80,000

Fixed cost

Loss 40,000

0

40

80 120 160 Break-even point = 100 units

200

x

? ? ? ? ? ?
11

利潤:I = ( P – Cm – Ch ) Q 策略1 ↑ ↑ ? ? ? ? 策略2 ↑ ? ? ? ↑ ? 策略3 ↑ ? ↓ ? ? ? 策略4 ↑ ? ? ↓ ? ? 策略5 ↑ ? ? ? ? ↓

F
差異化,領先者戰略 規;,大規模市場 機械化,第一利潤源 技能化,第二利潤源 信息化,第三利潤源
OR:SM

二、學科作用
? 量化輔助決策案例:盈虧平衡分析
? 例:某企業
總銷售額 物料成本 員工工資 管理費用 1100萬元 700萬元 200萬元 100萬元

? 現在利潤=100萬元,目標利潤150萬元 ? 利潤實現的方法有:
? 將銷售收入增加100% ? 將員工工資減少 25%

? 將管理費用減少 50%
? 將物料成本減少 7.1%
12 OR:SM

二、學科作用
4. 決策意識的重要性
甲 H 18 設備數 E F G G G4 F 10 裝配 G7 B G10 H7 C G 14 H 14 G20 乙 H6 F 10 裝配 E6 E 24

生產計劃決策

H 10 G7

一星期工作5天, 每天正常 工作8小時 ? 一周作業費用:11000 (直接人工成本與間接費用) ? 直接人工成本:10/1h (一臺機器需一位作業人員) ? 間接費用:人工成本2.5倍
?

H 13

E 15







原料 直接工時 直接人工 間接費用
A D

65

95

65 65分 10 25 100 170 70
OR:SM

65分 95分 12 30 107 173 66 14 35 144 233 89

H

H

總成本 售價 利潤

13

二、學科作用
?決策的科學性?方案 一
甲 單位產品總成本 單位產品售價 單位產品利潤 市場每周需求
107
173 66


144
233 89


100
170 70

40

80

40

? 甲產品產量40, 乙產品 80, 丙產品 40 ? 利潤=40×66+80×89+40×70=12560

? 人員有限如何實現?采取什么薪酬制度?
? 計件工資制,讓員工自愿加班

14

OR:SM

二、學科作用
?決策的科學性?方案 二
原料 運營費用 售價 市場每周需求 甲 65
173

乙 95 11000
233

丙 65
170

40

80

40

? ? ? ? ?

甲產品產量 40, 乙產品 80, 丙產品 40 總收入=40×173+80×233+40×170=32360 原料成本=40×65+80×95+40×65=12800 營運費用=11000 總利潤=32360-12800-11000=8560

? 人員有限如何實現?采取什么薪酬制度?
? 崗位工資制(定崗定員),讓員工自覺加班
15 OR:SM

二、學科作用
? 決策的科學性?產能符合計算
產品 市場需求 E 0 30 15 3000 2400 單位產品設備工時消耗 F G 10 31 20 21 0 21 2000 3760 2400 4800 H 31 13 24 3240 4800

40 甲 80 乙 40 丙 需求產能 可用產能

? 乙與丙哪一個產品比較賺錢?
甲 乙
144 233

E是瓶頸


100 170

總成本 售價 利潤
16

107 173

66

89

70
OR:SM

二、學科作用
? 方案 三:計時工資,且以單位利潤率高低為決策意識。
? 乙比較賺錢, 假如80個全部生產 ? 需用E產能2400分鐘,但是E只有2400分鐘可用 ? 因此只能生產80個乙 (2400/30),而丙無法生產

? ? ? ?

方案:甲產品 40個,乙產品80個,丙產品0個 總收入=40×173+80×233+0×170=25560 原料=40×65+80×95+0×65=10200 ,營運費用=11000 利潤=25560-10200-11000=4360

? 方案 四:計時工資,但以占用瓶頸資源大小為決策意識。
? 丙比較賺錢, 優先生產40個 ? 需用E產能600(40ⅹ15)分鐘 ? 剩下1800分鐘, 可生產60個乙 (1800/30) ? 方案:甲產品 40個,乙產品 60個,丙產品 40個 ? 總收入=40×173+60×233+40×170=27700 ? 原材料=40×65+60×95+40×6540=10900 ,營運費用=11000 ? 利潤=27700-10900-11000=5800
17 OR:SM

三、學科性質
1. 研究對象
? 經濟和管理活動中能用“數量關系”描述的 ? 如運營、規劃與組織管理問題 ? 解決的理論模型和優化方法實踐

2. 學科特點
? 強調科學性和定量分析 ? 強調應用性和實踐性 ? 強調從整體上進行把握

18

OR:SM

四、工作程序
管理運籌學的步驟: 明確問題環境分析

識別問題
確定目標制定準則 量化分析 控制 建立模型 軟件求解 收集資料數量關系 結構分析數學模型 算法求解方案優選

結果分析
管理者制定決策: 確定方案 管理者

解的分析 是
制定決策方案選擇 方案實施持續改進



實施方案

19

OR:SM

五、學科體系
1. 管理問題
需求預測 產品的市場需求量有多大,需求類別如何,對企業盈利有何影響? 生產計劃 在有限資源約束下,生產什么,生產多少,獲利最大? 資源配置 需要哪些資源,如何進行最優配置,資源緊缺性如何,以什么代價獲取? 作業排序 作業的重要次序如何,作業的順序安排如何? 市場營銷 廣告預算、媒介選擇、產品定價、銷售計劃等如何安排?

運輸問題 最佳運輸線路是哪條?物流配送集載如何優化?物流設施布局如何設置?
設施選址 運營點如何選擇,需要哪些運作設施,設施如何布局? 庫存控制 應保持多大庫存量,何時應進行訂貨,訂貨批量多少為宜? 項目規劃 項目完工工期多長為宜,哪些作業起關鍵性作用,資源如何分配? 設備更新 設備運轉狀況如何演進,運行可靠性如何,何時和如何更新或改造? 人力資源 人員需求預測,技能要求,編制與任務指派,績效測評,留用多長時間? 財務資金 資金投放的數量,從何處進行融資,資金成本是多少? 排隊問題 隊列多長,有無容量限制,多少服務臺為宜,能提供什么水平的服務?
20 OR:SM

五、學科體系
2. 學科內容
模型類型 線性規劃 整數規劃 目標規劃 動態規劃 網絡分析 網絡計劃 管理決策 方案排序 庫存模型 統計方法 排隊理論 仿真模擬
21

解決的典型辦法 在線性目標和約束條件間取得最優化結果 在線性目標和約束條件間尋求整數決策最優 在相對立的目標間尋得多目標妥協的滿意解 尋求多階段動態系統的整體決策優化問題 尋求網絡路徑、流量分布、網絡瓶頸及其改進 用各種作業和結點的網絡排列來說明項目實施計劃 依據決策準則權衡比較備選方案的決策結果 綜合各方案的優勢與不足尋求多指標排名次序 尋求訂貨、存儲和缺貨等庫存成本降至最低的經濟批量 從一個抽樣得到普遍結果的推論和曲線擬合 分析正在等待的隊列特點及其運行指標 動態觀察復雜的管理問題的行為,模擬管理系統的結構關系
OR:SM

五、學科體系
3. 學科應用
? 管理既是科學又是藝術
? 低層管理的科學成分較多,高層管理的藝術成分較多 ? 運營管理需較多管理科學,人力資源管理需較多管理藝術 ? 例行管理需要較多管理科學,例外管理需要較多管理藝術
問題導向 技術支持

M: 管理決策問題
管理者: 制定決策 戰略決策 營銷決策 生產安排 財務分析 人力資源 方案優選 ……

MC: 定量解決方法
應用統計 線性規劃 整數規劃 目標規劃 網絡計劃 網絡分析 決策分析 動態規劃 ……

方案選擇依據

管理科學: 運用合理的 分析來改善 決策的制定

22

OR:SM

六、學習要求
1. 學科地位

管理專業課 管理運籌學 管理學科基礎 技術科學 數學

戰略、運營、營銷、財務、人力…

離散、連續,靜態、動態的方法…
經濟學原理、管理學、行為科學… 加工技術、工程技術、信息技術… 高等數學、概率統計、線性代數…

23

OR:SM

六、學習要求
行業
經濟學

企業A

企業B

企業C

企業戰略、公司治理

商務1

商務2

商務3

會計學 財務管理

職能a

職能b

職能c

運營管理 市場營銷 質量管理 項目管理 ……
人力資源管理 組織行為學

信息管理 流程管理 物流管理 供應鏈管理 ……

管理 科學 方法 支持

小組i
24

小組ii

小組iii

OR:SM

六、學習要求
2. 如何學習
? ? ? ? ? 重點在結合實際的應用 發揮自己管理實踐經驗豐富和理論聯系實際的能力 強化結合實際問題建立管理優化模型的能力 強化解決問題的方案或模型的解的分析與應用能力 充分借用管理運籌學教學軟件

25

OR:SM

第1 章 線性規劃
內容提要 Sub title
?第一節

線性規劃的一般模型 ?一、線性規劃的三個要素 ?二、線性規劃模型的特征 ?三、線性規劃的圖解方法 ?四、線性規劃解的可能性 ?第二節 線性規劃的單純形法 ?一、線性規劃的標準型式 ?二、線性規劃之解的概念 ?三、單純形法的基本原理

26

OR:SM

第一節 線性規劃的一般模型
一、線性規劃的三個要素
? 決策變量 ? 決策問題待定的量值 ? 取值要求非負 ? 約束條件 ? 任何管理決策問題都是限定在一定的條件下求解 ? 把各種限制條件表示為一組等式或不等式稱約束條件 ? 約束條件是決策方案可行的保障 ? 約束條件是決策變量的線性函數 ? 目標函數 ? 衡量決策優劣的準則,如時間最省、利潤最大、成本最低 ? 目標函數是決策變量的線性函數 ? 有的目標要實現極大,有的則要求極小
27 OR:SM

第一節 線性規劃的一般模型
二、線性規劃模型的舉例
1、生產計劃問題
例. 某廠生產甲乙兩種產品,生產工藝路線為:各自的零部件分別在 設備A、B加工,最后都需在設備C上裝配。經測算得到相關數據如表 所示。應如何制定生產計劃,使總利潤為最大。 產品 工時消耗 工時成本 生產能力 h 設備 甲 乙 元/h A 2 0 20 16 B 0 2 15 10 C 3 4 10 32 據市場分析,單位甲乙產品的銷售價格分別為73和75元,試確定 獲利最大的產品生產計劃。

28

OR:SM

第一節 線性規劃的一般模型
(1)決策變量:設x1為甲產品的產量,x2為乙產品的產量。
(2)約束條件:生產受設備能力制約,能力需求不能突破有效供給量。
? 設備A的約束條件表達為

2 x1 ≤16
? 同理,設備B的加工能力約束條件表達為 2x2 ≤10 ? 設備C的裝配能力也有限,其約束條件為 3x1+ 4x2 ≤32

綜上的LP模型:

max Z ? 3x1 ? 5 x2 ?2 x1 ? 16 ?2 x ? 10 ? 2 s.t. ? ?3x1 ? 4 x2 ? 32 ? x1 , x2 ? 0 ?
OR:SM

(3)目標函數:目標是企業利潤最大化
max Z= 3x1 +5x2

(4)非負約束:甲乙產品的產量為非負
x1 ≥0, x2 ≥0
29

第一節 線性規劃的一般模型
二、線性規劃模型的舉例
2、物資運輸問題
例:某產品商有三個供貨源A1、A2、A3,其經銷商有4個(需求 市場)B1、B2、B3、B4。已知各廠的產量、各經銷商的銷售量及 從Ai 到Bj 的單位運費為Cij。為發揮集團優勢,公司要統一籌劃運 銷問題,求運費最小的調運方案。

銷地 產地 A1 A2 A3 銷量

B1
6 7 3 20

B2
3 5 2 30

B3
2 8 9 10

B4
5 4 7 40

產量
50 20 30

30

OR:SM

第一節 線性規劃的一般模型
(1)決策變量:設從Ai到Bj的運輸量為xij, (2)目標函數:運費最小的目標函數為
minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34

(3)約束條件:產量之和等于銷量之和,故要滿足:
? 供應平衡條件

x11+x12+x13+x14=50 x21+x22+x23+x24=20 x31+x32+x33+x34 =30
x11+x21+x31=20 x12+x22+x32=30 x13+x23+x33=10 x14+x24+x34=40
xij≥0 (i=1,2,3;j=1,2,3,4)
OR:SM

? 銷售平衡條件

? 非負性約束
31

第一節 線性規劃的一般模型
二、線性規劃模型的舉例
3、產品配比問題
例:用濃度45%和92%的硫酸配置100噸濃度80%的硫酸。

? 決策變量:取45%和92%的硫酸分別為 x1 和 x2 噸 ? 約束條件: ? x1 ? x2 ? 100 ? ?0.45x1 ? 0.92x2 ? 0.8 ? 100 ? 非負約束:
x1 ≥0, x2 ≥0

? 求解二元一次方程組得解
32 OR:SM

第一節 線性規劃的一般模型
若有5種不同濃度的硫酸可選(30%,45%,73%,85%,92%)會如何呢?

? 取這5種硫酸分別為 x1、x2、x3、x4、x5 ,有 ? x1 ? x2 ? x3 ? x4 ? x5 ? 100 ? ?0.3x1 ? 0.45x2 ? 0.73x3 ? 0.85x4 ? 0.92x5 ? 0.8 ? 100 ? 有多少種配比方案? ? 何為最好? 若5種硫酸價格分別為400, 700, 1400, 1900, 2500元/t,則:

min Z ? 400 x1 ? 700 x2 ? 1400 x3 ? 1900x4 ? 2500x5 ? x1 ? x2 ? x3 ? x4 ? x5 ? 100 ? s.t. ?0.3x1 ? 0.45 x2 ? 0.73x3 ? 0.85 x4 ? 0.92 x5 ? 0.8 ?100 ? x ? 0, j ? 1, 2,...5 ? j
33 OR:SM

第一節 線性規劃的一般模型
三、線性規劃模型的特征
1、模型隱含假定
(1)線性化假定
? 函數關系式f(x)= c1x1+c2x2+… +cnxn,稱線性函數。 ? 建模技巧:將非線性的函數進行分段線性化。

(2)同比例假定
? 決策變量變化引起目標函數和約束方程的改變量比例。

(3)可加性假定
? 決策變量對目標函數和約束方程的影響是獨立于其他變量的。 ? 目標函數值是決策變量對目標函數貢獻的總和。

(4)連續性假定
? 決策變量取值連續。

(5)確定性假定
? 所有參數都是確定的,不包含隨機因素。
34 OR:SM

第一節 線性規劃的一般模型
三、線性規劃模型的特征
2、一般數學模型
? 用一組非負決策變量表示的一個決策問題; ? 存在一組等式或不等式的線性約束條件; ? 有一個希望達到的目標,可表示成決策變量的極值線性函數。

max(min) Z ? c1 x1 ? c2 x2 ? ? ? cn xn ?a11 x1 ? a12 x2 ? ? ? a1n xn ? (?, ?)b1 ?a x ? a x ? ? ? a x ? (?, ?)b 2n n 2 ? 21 1 22 2 ? s.t. ? ???? ?a x ? a x ? ? ? a x ? (?, ?)b mn n m ? m1 1 m 2 2 ? x1 , x2 ,? xn ? 0 ?
35 OR:SM

第一節 線性規劃的一般模型
四、線性規劃的圖解方法
1、線性規劃的可行域
可行域:滿足所有約束條件的解的集合, 即所有約束條件共同圍城的區域。
x2
maxZ= 3x1 +5 x2 2 x1 ≤16 2x2 ≤10 S.t. 3x1 +4 x2 ≤32 x1 ≥0, x2 ≥0
9 2x1 =16

D
5

C B

2x2 =10

3

0
36

4

8A

10 3x1 +4 x2 =32
OR:SM

x1

第一節 線性規劃的一般模型
四、線性規劃的圖解方法
2、線性規劃的最優解
目標函數 Z= 3x1 +5 x2 代表以 Z 為參數的一族平行線。
x2
8

D
5 3

2x1 =16

C

2x2 =10

Z=30 Z=15
4

B Z=37
8A

0
37

10

x1

3x1 +4 x2 =32
OR:SM

第一節 線性規劃的一般模型
四、線性規劃的圖解方法
3、線性規劃解的特性
? 由線性不等式組成的可行域是凸多邊形(凸多邊形是凸集)
?凸集定義:集合內部任意兩點連線上的點都屬于這個集合

a

b

c

d

? 可行域有有限個頂點。 ? 目標函數最優值一定在可行域的邊界達到,而不可能在 其區域的內部。

38

OR:SM

第一節 線性規劃的一般模型
五、線性規劃解的可能性
1、唯一最優解:只有一個最優點 2、多重最優解:無窮多個最優解 當市場價格下降到74元,其數學模型變為
x2
8

max Z ? 3x1 ? 4 x2 ?2 x1 ? 16 ?2 x ? 10 ? 2 s.t. ? ?3x1 ? 4 x2 ? 32 ? x1 , x2 ? 0 ?

2x1 =16
5

D

C

2x2 =10 B Z=32 A x1
OR:SM

2

Z=24 Z=12

0
39

4

8

10

3x1 +4 x2 =32

第一節 線性規劃的一般模型
五、線性規劃解的可能性
3、無界解:可行域無界,目標值無限增大 (缺乏必要約束)

max Z ? 3 x1 ? 5 x2 ? 2 x1 ? 16 s.t. ? ? x1 , x2 ? 0

40

OR:SM

第一節 線性規劃的一般模型
五、線性規劃解的可能性
4、沒有可行解:線性規劃問題的可行域是空集 (約束條件相互矛盾)
x2

目標沖突 利害沖突

目標強沖突 利害弱沖突

max Z ? 3 x1 ? 5 x2 ? x1 ? x2 ? 5 ? s.t. ?3 x1 ? 4 x2 ? 24 ?x , x ? 0 ? 1 2
4 2 6

8

O

2

4

6

8

x1
OR:SM

41

第二節 線性規劃的一般模型
一、線性規劃的標準型式
1、標準型表達方式
(1)代數式
max Z ? ? c j x j
j ?1 n

(2)向量式
max Z ? CX ? n ?? p j x j ? b s.t. ? j ?1 ?x ? 0 ? j

? n ?? aij x j ? bi s.t. ? j ?1 ?x ? 0 ? j

(3)矩陣式

max Z ? CX ?AX = b ? ?X ? 0
42

A:技術系數矩陣,簡稱系數矩陣; B:可用的資源量,稱資源向量; C:決策變量對目標的貢獻,稱價值向量; X:決策向量。
OR:SM

第二節 線性規劃的一般模型
一、線性規劃的標準型式
2、標準型轉換方法
(1)如果極小化原問題minZ=CX,則令 Z'=-Z,轉為求 maxZ'=-CX (2)若某個bi<0,則以-1乘該約束兩端,使之滿足非負性的要求。 (3)對于≤型約束,則在左端加上一個非負松弛變量,使其為等式。

(4)對于≥型約束,則在左端減去一個非負剩余變量,使其為等式。 (5)若某決策變量xk無非負約束,令xk=x'k-x"k ,(x'k≥0,x"k ≥0) 。

max Z ? 3x1 ? 5 x2 ? 0 x3 ? 0 x4 ? 0 x5 ? 16 ?2 x1 ? 0 x2 ? x3 ?0 x ? 2 x ? x4 ? 10 ? 1 2 s.t. ? ? x5 ? 32 ?3x1 ? 4 x2 ? x1 , x2 , x3 , x4 , x5 ? 0 ?
43 OR:SM

第二節 線性規劃的一般模型
二、線性規劃之解的概念
1、線性規劃解之關系
基矩陣:一個非奇異的子矩陣(線性無關)。 ? 矩陣A中任意m列的線性無關子矩陣B ,稱為一個基。 ? 組成基B的列為基向量,用Pj表示(j=1,2,…,n) 。 基變量: ? 與基向量Pj 相對應的m個變量xj稱為基變量 ? 其余的n - m個變量為非基變量 基解:令所有非基變量等于零,得出基變量的唯一解 。
x3 x4 x5

?1 B ? ?0 ? ?0 ?
44

0 1 0

0? 0? ? 1? ?

? 基變量是x3, x4, x5 ? 非基變量是x1, x2 ? 令非基變量x1=x2=0,得到一個基解 x3=16,x4=10, x5=32
OR:SM

第二節 線性規劃的一般模型
二、線性規劃之解的概念
1、線性規劃解之關系
可行解:滿足約束條件AX=b, X≥0的解。 可行基:可行解對應的基矩陣。 基可行解:滿足非負性約束的基解稱為基可行解。 最優解:使目標函數最優的可行解,稱為最優解。 最優基:最優解對應的基矩陣,稱為最優基。 非 可 行 解
45

可 行 解

基 可 行 解

基 解

OR:SM

第二節 線性規劃的一般模型
二、線性規劃之解的概念
2、線性規劃基本原理
定理1. 若線性規劃問題存在可行域,則其可行域一定是凸集。 定理2. 線性規劃問題的基可行解對應可行域的頂點。 定理3. 若可行域有界,線性規劃的目標函數一定可以在可行域 的頂點上達到最優。 定理4. 線性規劃如果有可行解,則一定有基可行解;如果有最 優解,則一定有基可行解是最優解。

46

OR:SM

第二節 線性規劃的一般模型
二、線性規劃之解的概念
3、線性規劃解題思路
? 先找到一個初始基可行解,也就是找到一個初始可 行基,想辦法判斷這個基可行解是不是最優解。 ? 如果是最優解,就得到這個線性規劃問題的最優解; ? 如果判斷出不是最優解,就想法由這個可行基按一 定規則變化到下一個可行基,然后再判斷新得到的基 可行解是不是最優解; ? 如果還不是,再接著進行下一個可行基變化,直到 得到最優解。

47

OR:SM

maxZ=3x1 +5x2 +0x3 +0x4+0x5 2x1 +x3 =16 2x2 +x4 =10 3x1 + 4x2 +x5 =32 x3 =16-2x1 x4 =10-2x2 x5 = 32-3x1 -4 x2 maxZ=3x1 +5x2 +0x3 +0x4+0x5 x3 =16 x4 =10-2x2 ? 0 x5 = 32-4 x2 ? 0
48

?2 1 ? ? 16 ? ? ? ? ? 2 1 ? X ? ? 10 ? ? ? 3 4 1? ? 32 ? ? ? ? ?

X ? ? 0 0 16 10 32?

T

無關
x2 ? 5 x2 ? 8
OR:SM

第二節 線性規劃的一般模型
三、單純形法的基本原理
maxZ=3x1 +5 x2 +0x3 +0x4+0x5 =0 2x1 + x3 =16 2x2 + x4 =10 3x1 +4 x2 + x5 =32
Cj
CB XB x3 x4 x5

3

5
x2 0 2 4 5

0
x3 1 0 0 0

0
x4 0 1 0 0

0
x5 0 0 1 0

b
16 10 32 0
m

x1 2 0 3 3

比 值
-

0
0 0

10/2=5 32/4=8

檢驗數?j

' ? j ? C j ? ? CB ? aij

49

i ?1

i

OR:SM

第二節 線性規劃的一般模型
三、單純形法的基本原理
Cj CB 0 5 XB x3 3 5 0 0 0

b
16 5 12

x1
2 0 3 3

x2
0 1 0 0 0

x3
1 0 0 0 1

x4
0 1/2 -2 -5/2 4/3

x5
0 0 1 0 -2/3

比 值
5
4

x2
x5

0

檢驗數?j
0
5 3 x3 x2 8

0

5
4

0
1 0

1
0 0

0
0 0

1/2
-2/3 -1/2

0
1/3 -1
OR:SM

x1

檢驗數?j
50

最優解 :X*=(4,5,8,0,0)T,Z*=37

第二節 線性規劃的一般模型
三、單純形法的基本原理
? 單純形的管理啟示
x2 X1=(0,5,10,0,12)T 9
5

D

X1=(4,5,8,0,0)T 2x1=16 C(4,5) B

2x2 =10

X0=(0,0,10,10,32)T 0
4 8

A
12

x1

51

企業管理過程也是如此,把現有方案作為初始方案,找到最急需要 改進的某個問題和改進方向,一次做好某個主要問題的解決與改進; 一次只解決和改進一個問題的難度最;解決之后,再尋求可以改 進的其它地方,再次改進,不斷地追求完美。 OR:SM

3x1 +4 x2 =32

最優解解釋
max Z ? 3 x1 ? 4 x2 (1) ? 2 x1 ? 16 ? 2 x ? 10 (2) ? 2 s.t. ? (3) ?3 x1 ? 4 x2 ? 32 ? x1 , x2 ? 0 ?

最優解 :X*=(4,5,8,0,0)T 松弛變量解釋 X3=8, 設備A有8小時富裕 X4=0,條件(2)等式成立,設備B是瓶頸設備 X5=0,條件(3)等式成立,設備C是瓶頸設備
52 OR:SM

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
53

**********************最優解如下************** 目標函數最優值為 : 37 變量 最優解 相差值 --------------------x1 4 0 x2 5 0 約束 松弛/剩余變量 對偶價格 -------------------------1 8 0 2 0 .5 3 0 1 目標函數系數范圍 : 變量 下限 當前值 上限 ---------------------------x1 0 3 3.75 x2 4 5 無上限 常數項數范圍 : 約束 下限 當前值 上限 ---------------------------1 8 16 無上限 2 4 10 16 3 20 32 44
OR:SM

第2 章 線性規劃討論
內容提要 Sub title
?第一節 目標函數的描述技巧
?計件工資 ?崗位工資 ?計時工資

?第二節 線性規劃的適用層次 ?第三節 線性規劃的典型案例 ?第四節 線性規劃靈敏度分析
?價值系數的變動分析

?資源數量的變動分析
54 OR:SM

第一節 目標函數的描述技巧
一、計件工資
?

計件工資體系,目標是企業利潤最大化:

max Z ? 66x1 ? 89x2 ? 70x3
計件工資制薪酬體系下,工作時間不會完全受每天8小時工 作時間約束,但有產品市場需求約束,如下:
?

產品甲:

x1 ? 40

產品乙:
產品丙: 非負性約束
?

x2 ? 80 x3 ? 40
x1 , x2 , x3 ? 0

經軟件求解,得到最優解為Z=12560,產品甲x1=40,產品乙 x2=80,產品丙x3=40。
55 OR:SM

第一節 目標函數的描述技巧
二、崗位工資
? ?

崗位工資制薪酬體系,以計時工資制為基礎,實行定崗定員。 總收入=173x1+233x2+170x3,
原料成本=65x1+95x2+65x3,營運費用=11000, 則目標函數為maxZ= 108x1+138x2+105x3-11000

?

崗位工資制薪酬體系下,工作時間也不會完全受每天8小時工作 時間約束,但有產品市場需求約束,如下:
產品甲:

x1 ? 40

產品乙:
產品丙: 非負性約束
?

x2 ? 80 x3 ? 40
x1 , x2 , x3 ? 0

經軟件求解,得到最優解為Z=8560,x1=40,x2=80,x3=40。
OR:SM

56

第一節 目標函數的描述技巧
三、計時工資
? ?

目標函數為 市場需求約束

max Z ? 108x1 ? 138x2 ? 105x3 ?11000
產品甲: 產品乙: 產品丙:

x1 ? 40

x2 ? 80 x3 ? 40

?

設備能力約束

設備E: 設備F: 設備G:

0x1 ? 30x2 ? 15x3 ? 2400 10x1 ? 20x2 ? 0x3 ? 2400 31x1 ? 21x2 ? 21x3 ? 4800 31x1 ? 13x2 ? 24x3 ? 4800

設備H:
?
57

經軟件求解,得到最優解為Z=5800,x1=40,x2=60,x3=40。
OR:SM

第二節 線性規劃的適用層次
計劃鏈的層次
? 產值計劃 或 利潤計劃 ? 絕對數量 或 增長幅度 ? 期限:年度 單位:萬元 ? 大類產品年度生產計劃 當前條件 ? 確定產品的品種和數量 ? 期限:年度 單位:萬臺
庫存管理
物料需求計劃MRP 能力需求計劃
CRP
預測

經營計劃 銷售計劃 生產計劃大綱 主生產計劃MPS

? 大類產品銷售收入或臺套 ? 產品品種和數量如何確定 ? 期限:年度 單位:萬臺
粗能力計劃

物料清單

? 具體產品在具體 時段的出產計劃 ? 合同訂單和預測 轉換為生產任務

? 將產品出產計劃 轉換成物料需求表

不可行

可行否
成 品 、 在 制 品 信 息 可行

外購計劃
定單

車間作業計劃

供應商 58

作業統計與控制 OR:SM

第三節 線性規劃的典型案例
? 配送中心選擇
例:某企業存在兩個供貨源(產地),已知原有供貨源每月的供貨 能力是5萬臺產品,新增供貨源的生產能力可以滿足產品的需求,且 兩個貨源的價格相同。 有三個區域目標市場(銷地或銷售商),各銷地每月的市場需求量 為5萬臺、10萬臺、5萬臺。 在分銷渠道中,擬定在2個地點中選址設立分銷中心,執行產品的 轉運任務。各地之間的單位運輸物流成本(由距離和運輸方式決定)

59

OR:SM

第三節 線性規劃的典型案例

決策變量:設從供貨源到分銷中心的運輸量為 xij ,從分銷中 y jk 心到需求市場的運輸量為 。選址規劃在于二者的實際取值。 ? 如果 x11 ? x21 ? 0 ,則不設臵分銷中心; 反之,則設臵,其規模為 x11 ? x21 x ? x22 ? 0 ,則不設臵分銷中心; ? 如果 12 反之,則設臵,其規模為 x12 ? x22
?

目標函數:各條路段上的實際運輸量乘以物流運輸的單位費用 之總和最小,即
?

min Z ? 2x11 ? 5x12 ? 4x21 ? 2x22 ? 3 y11 ? 4 y12 ? 5 y13 ? 2 y21 ? 2 y22 ? 3 y23
?

存在供應能力約束、市場需求約束、配送中轉約束,如下:

60

OR:SM

第三節 線性規劃的典型案例

?

供應能力平衡約束:

x11 ? x12 ? 50000 x21 ? x22 ? 150000
y11 ? y21 ? 50000 y12 ? y22 ? 100000 y13 ? y23 ? 50000

?

市場需求平衡約束

?

配送中心不存留產品

x11 ? x21 ? y11 ? y12 ? y13 x12 ? x22 ? y21 ? y22 ? y23

?

所有變量大于等于零
x11 , x12 , x21, x22 , y11, y12 , y13 , y21, y22 , y23 ? 0

61

OR:SM

第四節 線性規劃靈敏度分析
一、靈敏度分析的必要性
? 線性規劃研究的是一定條件下的最優化問題
? 資源環境和市場條件是可變的 ? 基礎數據往往是測算估計的數值

? 靈敏度分析的概念
? 靈敏度分析又稱敏感性分析或優化后分析
? 研究基礎數據發生波動后對最優解的影響
? 最優解對數據變化的敏感程度 ? 在多大的范圍內波動才不影響最優基

? 靈敏度分析解決的問題:
? 價值系數C在什么范圍變化而最優基B不變 ? 資源系數B在什么范圍變化而最優解X不變

62

OR:SM

線性規劃軟件求解的靈敏度分析
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
63

**********************最優解如下************************* 目標函數最優值為 : 37 變量 最優解 相差值 --------------------x1 4 0 x2 5 0 約束 松弛/剩余變量 對偶價格 -------------------------1 8 0 2 0 .5 3 0 1 目標函數系數范圍 : 價值系數C的變動范圍 變量 下限 當前值 上限 ---------------------------x1 0 3 3.75 x2 4 5 無上限 常數項數范圍 : 資源系數B的變動范圍 約束 下限 當前值 上限 ---------------------------1 8 16 無上限 2 4 10 16 3 20 32 44

靈敏度分析

OR:SM

第四節 線性規劃靈敏度分析
一、價值系數的變動分析

? 參數Cj的變化范圍:價值系數Cj變化影響檢驗數
? 非基變量Cj的變化范圍
? 非基變量Cj變化,只影響它自己的檢驗數

? j ' ? C j ? ?C j ? CB B?1Pj ? 0
?C j ? CB B ?1 Pj ? C j ? ?? j
Cj CB 0 5 3
64
*

? ?C j ? ?? * j
5 x2 0 1 0 0 x3 1 0 0 0 x4 4/3 1/2 -2/3 0 x5 -2/3 0 1/3

3

XB x3 x2 x1

b
8 5 4

x1 0 0 1

比 值

檢驗數?j

0

0

0

-1/2

-1
OR:SM

第四節 線性規劃靈敏度分析
一、價值系數的變動分析
? 基變量CBl的變化范圍
Cj C1 5 0 0 0

CB
0 5 C1

XB
x3 x2 x1

b
8 5 4

x1
0 0 1 0

x2
0 1 0 0

x3
1 0 0 0

x4
4/3 1/2 -2/3 2C1/3-5/2

x5
-2/3 0 1/3 -C1/3

比 值

檢驗數?j

?j ?0
65

15 ? 0 ? c1 ? 4
OR:SM

第四節 線性規劃靈敏度分析
二、右端常量的變動分析

? 參數bi的變化范圍
第r個約束的右端項為br,增量?br,其它數據不變。新的基解為
? 0 ? ? a1r * ?br ? ? b1* ? ? a1r * ? ? ? ? * ? ? *? ? *? ? ? ? ? a2 r ?br ? ?1 ?1 ?1 ?1 ? b2 ? ? ?b ? a2 r ? X B ' ? B (b ? ?b) ? B b ? B ? ?br ? ? B b ? ? ? ?? ? r ? ? ? ? ? ? ? ? ? ? *? ? *? ? a * ?b ? ?b ? ?a ? ? ? ? r ? ? mr ? m ? ? mr ? ? 0 ? ? ?

只要X'B≥0 ,則可保持最優基不變。

66

bi* air* ? 0 ? ?br ? ? * air bi* * air ? 0 ? ?br ? ? * air

b b * * max{? i * | air ? 0} ? ?br ? min{? i * | air ? 0} i i air air
OR:SM

*

*

第3 章 對偶規劃
內容提要 Sub title
第一節 對偶規劃的數學模型
? 對偶問題的提出 ? 對偶規劃的性質

第二節 對偶規劃的經濟解釋
? 影子價值的內涵 ? 影子價值的應用

第三節 資源定價的決策案例

67

OR:SM

生產計劃問題
例. 某廠生產甲乙兩種產品,生產工藝路線為:各自的零部件分別在 設備A、B加工,最后都需在設備C上裝配。經測算得到相關數據如表 所示。應如何制定生產計劃,使總利潤為最大。 產品 工時消耗 生產能力 h 設備 甲 乙 A 2 0 16 B 0 2 10 C 3 4 32 據市場分析,單位甲乙產品的盈利水平分別為3和5元,試確定獲 利最大的產品生產計劃。

68

OR:SM

第一節 線性規劃的一般模型
(1)決策變量:設x1為甲產品的產量,x2為乙產品的產量。
(2)約束條件:生產受設備能力制約,能力需求不能突破有效供給量。
? 設備A的約束條件表達為

2 x1 ≤16
? 同理,設備B的加工能力約束條件表達為 2x2 ≤10 ? 設備C的裝配能力也有限,其約束條件為 3x1+ 4x2 ≤32

綜上的LP模型:

max Z ? 3x1 ? 5 x2 ?2 x1 ? 16 ?2 x ? 10 ? 2 s.t. ? ?3x1 ? 4 x2 ? 32 ? x1 , x2 ? 0 ?
OR:SM

(3)目標函數:目標是企業利潤最大化
max Z= 3x1 +5x2

(4)非負約束:甲乙產品的產量為非負
x1 ≥0, x2 ≥0
69

第一節 對偶規劃的數學模型
一、對偶問題的提出
? 若上例中該廠的產品平銷,現有另一企業想租賃其設備。廠方 為了在談判時心中有數,需掌握設備臺時費用的最低價碼,以 便衡量對方出價,對出租與否做出抉擇。 ? 在這個問題上廠長面臨著兩種選擇:自行生產或出租設備。首 先要弄清兩個問題: ? ①合理安排生產能取得多大利潤? ? ②為保持利潤水平不降低,資源轉讓的最低價格是多少?

? 問題 ①的最優解:x1=4,x2=5,Z*=37。

70

OR:SM

第一節 對偶規劃的數學模型
一、對偶問題的提出 出讓定價
? 假設出讓A、B、C設備所得利潤分別為y1、y2、y3 ? 原本用于生產甲產品的設備臺時,如若出讓,不應低于 自行生產帶來的利潤,否則寧愿自己生產。于是有 2y1+0y2+3y3≥ 3 ? 同理,對乙產品而言,則有 0y1+2y2+4y3≥ 5 ? 設備臺時出讓的收益(希望出讓的收益最少值) minw =16y1+10y2+32y3 ? 顯然還有 y1,y2,y3≥0
71 OR:SM

第一節 對偶規劃的數學模型
一、對偶問題的提出
例1的對偶問題的數學模型

maxZ= 3x1 +5 x2 2x1 ≤16 2x2 ≤10 S.t. 3x +4 x ≤32 1 2 x1 , x2 ≥0
? ? ? ?
72

minw =16y1+10y2+32y3 2y1+ 0y2+ 3y3≥ 3 S.t. 0y + 2y + 4y ≥ 5 1 2 3 y1,y2,y3≥0

對偶問題的最優解: y1=0,y2=1/2,y3=1,W* =37 兩個問題的目標函數值相等并非偶然 前者稱為線性規劃原問題,則后者為對偶問題,反之亦然。 對偶問題的最優解對應于原問題最優單純型法表中,初始基 變量的檢驗數的負值。
OR:SM

第一節 對偶規劃的數學模型
二、對偶規劃的性質
1、對稱性定理 對偶問題的對偶問題是原問題。 根據對偶規劃,很容易寫出對偶問題的對偶問題模型。 2、 最優性定理 設 X , Y 分別為原問題和對偶問題的可行解,且 C X ? bT Y 則 X , Y 分別為各自的最優解。 3. 對偶性定理 若原問題有最優解,那么對偶問題也有最優解,而且 兩者的目標函數值相等。 4. 互補松弛性 最優解的充分必要條件是 Y * X s ? 0 ,Ys X * ? 0
73 OR:SM

線性規劃軟件求解的靈敏度分析
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
74

**********************最優解如下************** 目標函數最優值為 : 37 變量 最優解 相差值 --------------------x1 4 0 x2 5 0 約束 松弛/剩余變量(XS) 對偶價格(Y*) -------------------------1 8 0 2 0 .5 3 0 1 目標函數系數范圍 : 變量 下限 當前值 上限 ---------------------------x1 0 3 3.75 x2 4 5 無上限 常數項數范圍 : 約束 下限 當前值 上限 ---------------------------1 8 16 無上限 2 4 10 16 3 20 32 44
OR:SM

第二節 對偶規劃的經濟解釋
一、影子價值的內涵

Z ? ? c j x j ? ? b i yi ? w
j ?1 i ?1

n

m

?Z ? yi ?bi

? 左邊是資源bi每增加一個單位對目標函數Z的貢獻; ? 對偶變量 yi在經濟上表示原問題第i種資源的邊際價值。 ? 對偶變量的值 yi*表示第i種資源的邊際價值,稱為影子價值。 ? 若原問題價值系數Cj表示單位產值,則yi 稱為影子價格。 ? 若原問題價值系數Cj表示單位利潤,則yi 稱為影子利潤。 ? 影子價格=資源成本+影子利潤
75 OR:SM

第二節 對偶規劃的經濟解釋
一、影子價值的內涵
? 影子價格不是資源的實際價格,反映了資源配置結構,
? 其它數據固定,某資源增加一單位導致目標函數的增量。

?

對資源i總存量的評估:購進 or 出讓 對資源i當前分配量的評估:增加 or 減少 ? 第一,影子利潤說明增加哪種資源對經濟效益最有利 ? 第二,影子價格告知以怎樣的代價去取得緊缺資源 ? 第三,影子價格是機會成本,提示資源出租/轉讓的基價 ? 第四,利用影子價格分析新品的資源效果:定價決策 ? 第五,利用影子價格分析現有產品價格變動的資源緊性 ? 第六,可以幫助分析工藝改變后對資源節約的收益 ? 第七,可以預知哪些資源是稀缺資源而哪些資源不稀缺

76

OR:SM

第三節 資源定價的決策方案
例:某廠生產甲乙產品,(1)如何安排每周的利潤為最大?
甲 原材料 (kg) 設備 (工時) 電力 (度) 銷售價格(元) 9 4 3 390 乙 4 5 10 352 資源成本 20 50 1 資源擁有量 360 200 300

(2)如果企業可以不生產,那資源出讓如何定價?

一、最優生產決策
max Z ? 7 x1 ? 12x2 ?9 x1 ? 4 x2 ? 360 ?4 x ? 5 x ? 200 ? 1 2 s.t.? ?3x1 ? 10x2 ? 300 ? x1 , x2 ? 0 ?
77

X * ? (20, 24,84,0,0)T

OR:SM

第三節 資源定價的決策方案
二、資源獲利決策
如果決策者考慮自己不生產甲乙兩種產品,而把原擬用于生產 這兩種產品的原材料、設備工時、電量資源全部出售給外單位, 或者做代加工,則應如何確定這三種資源的價格。 設原材料的單位出讓獲利為y1,設備工時的單位出讓獲利為y3, 電量的單位出讓獲利為y2 。 出讓決策的線性規劃模型:

min w ? 360 y1 ? 200 y2 ? 300 y3 ?9 y1 ? 4 y2 ? 3 y3 ? 7 ? s.t. ? 4 y1 ? 5 y2 ? 10 y3 ? 12 ?y , y , y ? 0 ? 1 2 3
* y1 ? 0 y* ? 1.36 y* ? 0.52 2 3

Z * ? 428

y* ? 0, y* ? 0 4 5
OR:SM

78

第4 章 整數規劃
內容提要 Sub title
第一節 整數規劃問題
? 純整數規劃 ?0-1規劃 ?混合整數規劃

第二節 整數規劃求解
? 分枝定界法

第三節 整數規劃應用

79

OR:SM

第一節 整數規劃問題

? 線性規劃的決策變量取值可以是任意非負實數,但許多 實際問題中,只有當決策變量的取值為整數時才有意義
? 例如,產品的件數、機器的臺數、裝貨的車數、完成工作的人 數等,分數或小數解顯然是不合理的。

? 要求全部或部分決策變量的取值為整數的線性規劃問題, 稱為整數規劃(Integer Programming)。
? 全部決策變量的取值都為整數,則稱為全整數規劃(All IP)

? 僅要求部分決策變量的取值為整數,則稱為混合整數規劃 (Mixed IP)
? 要求決策變量只取0或1值,則稱0-1規劃(0-1 Programming)
80 OR:SM

第一節 整數規劃問題
一、純整數規劃
例:某企業利用材料和設備生產甲乙產品,其工藝消耗系 數和單臺產品的獲利能力如下表所示:
資源 產品 甲 乙 現有量

A
B 單臺利潤

2
5 6

1
7 5

9
35

問如何安排甲、乙兩產品的產量,使利潤為最大。 解:設x1為甲產品的臺數,x2為乙產品的臺數。 maxZ= 6x1 +5 x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1, x2 ≥0 x1, x2 取整數
81 OR:SM

第一節 整數規劃問題
二、0-1規劃
序號
物品 重量

1
食品 5

2
氧氣 5

3
冰鎬 2

4
繩索 6

5
帳篷 12

6
相機 2

7
設備 4

重要性系數

31

15

18

14

8

4

10

登山隊員可攜帶最大重量為25公斤。問都帶哪些物品的重要性最大。 解:對于每一種物品無非有兩種狀態,帶或者不帶,不妨設 不帶此種物品 ?0 xj ? ? ?1 帶此種物品 0-1規劃的模型: max Z ? 31 x1 ? 15x 2 ? 18x 3 ? 14x 4 ? 8 x 5 ? 4 x 6 ? 10x 7 20
?5 x1 ? 5 x 2 ? 2 x 3 ? 6 x 4 ? 12x 5 ? 2 x 6 ? 4 x 7 ? 25 ? ? x j ? 0或1 ( j ? 1,2, ? 7)
82 OR:SM

第一節 整數規劃問題
三、混合整數規劃
例:某產品有n個區域市場,各區域市場的需求量為 bj噸/月;現擬 在m個地點中選址建生產廠,一個地方最多只能建一家工廠;若選 i 地建廠,生產能力為 ai噸/月,其運營固定費用為Fi元/月;已知址i至j 區域市場的運價為cij元/噸。如何選址和安排調運,可使總費用最? 解:選址建廠與否是個0-1型決策變量, m m n 假設 yi =1,選擇第 i 址建廠, min Z ? ? yi Fi ? ? ? cij xij i ?1 i ?1 j ?1 yi=0,不選擇第 i 址建廠; ? n 計劃從 i 址至區域市場 j 的運輸 i ? 1, 2,..., m ? ? xij ? yi ai 運量xij為實數型決策變量。 ? j ?1
? m ? s.t. ? ? xij ? b j ? i ?1 ? xij ? 0 ? ? yi ? 0,1 ? j ? 1, 2,..., n

83

OR:SM

第二節 整數規劃求解
一、舍入化整法
? 為了滿足整數解的要求,自然想到“舍入”或“截尾”處理,以

得到與最優解相近的整數解。 ? 這樣做除少數情況外,一般不可行,因為化整后的解有可能超出 了可行域,成為非可行解;或者雖是可行解,卻不是最優解。
不考慮整數約束則是一個LP問題,稱為原整數規劃的松弛問題 對于例1的數學模型,不考慮整數約束的最優解:

x1 *=28/9, x2 * =25/9,Z * =293/9
舍入化整 x1 =3, x2 =3,Z =33,不滿足約束條件5x1 +7 x2 ≤35,非可行解; x1 =3, x2 =2,Z =28,滿足約束條件,是可行解,但不是最優解; x1 =4, x2 =1,Z =29,滿足約束條件,才是最優解。
84 OR:SM

第二節 整數規劃求解
二、窮舉整數法
x2
5 4 3

2x1 + x2 =9

? ? ? ?
1

? ? ?
2

? (3,3) ? ?
3
(3 1 7 ,2 ) 9 9

2
1

?
4

5x1 +7 x2 =35

x1

對于決策變量少,可行的整數解又較少時,這種窮舉法有時是 可行的,并且也是有效的。 但對于大型的整數規劃問題,可行的整數解數量很多,用窮舉 法求解是不可能的。例如,指派問題 。
85 OR:SM

第二節 整數規劃求解
三、分支定界法

? 不考慮整數限制,先求出相應線性規劃 的最優解, ? 若求得的最優解符合整數要求,則是原IP的最優解; ? 若不滿足整數條件,則任選一個不滿足整數條件的變量來 構造新的約束,在原可行域中剔除部分非整數解。 ? 依次在縮小的可行域中求解新構造的線性規劃的最優解, 直到獲得原整數規劃的最優解。 ? 定界的含義: ? IP是在相應的LP基礎上增加整數約束 ? IP的最優解不會優于相應LP的最優解 ? 對MaxZ,相應LP的Z*是原IP的上界
86 OR:SM

第二節 整數規劃求解
LP 0 :

三、分支定界法

上界: 32 下界: 0

x1 ? 3

1 7 5 , x2 ? 2 , Z ? 32 9 9 9

5 9

x1≤3
LP1 : 6 2 x1 ? 3, x2 ? 2 , Z ? 32 7 7

x1 ≥4
LP2 : x1 ? 4, x2 ? 1, Z ? 29
上界: 32 下界: 29 2 7

x2≤2
LP3 : x1 ? 3, x2 ? 2, Z ? 28

x2 ≥3
LP 4: x1 ? 2 4 4 , x2 ? 3, Z ? 31 5 5
上界: 31 下界: 29 4 5

x1≤2
LP5: 4 6 x1 ? 2, x2 ? 3 , Z ? 29 7 7

x1 ≥3
LP 6: 無可行解
上界: 29 下界: 29 6 7

x2≤3
LP7: x1 ? 2, x2 ? 3, Z ? 27

x2 ≥4
LP8: 2 2 x1 ? 1 , x2 ? 4, Z ? 28 5 5
上界: 29 下界: 29

87

OR:SM

第三節 整數規劃應用
一、生產基地規劃
例:某公司擬建設A、B兩種類型的生產基地若干個,兩種類型的生產基地 每個占地面積,所需經費,建成后生產能力及現有資源情況如下表所示。問 A、B類型基地各建設多少個,可使總生產能力最大?
A 占地(萬平米) 費用(萬元) 生產能力(百件/年) 2 5 20 B 5 4 10 資源限制 13 24

解:設A、B兩類基地各建設 x1,x2 個,則其模型為:

max Z ? 20x1 ? 10x 2 ?2 x1 ? 5 x 2 ? 13 ? ?5 x1 ? 4 x 2 ? 24 ? x , x ? 0且為整數 ? 1 2

88

OR:SM

第三節 整數規劃應用
二、人員安排規劃
某服務部門各時段(每2小時為一時段)需要的服務人數如表: 時段 1 2 3 4 5 6 7 8 服務員最少數目 10 8 9 11 13 8 5 3 按規定,服務員連續工作8小時 (4個時段)為一班。請安排服務員 的工作時間,使服務員總數最少. 解:設第j 時段開始時上班的服務 員人數為xj 第 j 時段來上班的服務員將在第j+3 時段結束時下班,故決策變量有 x1,x2,x3,x4,x5 。
89

min Z ? x1 ? x2 ? x3 ? x4 ? x5 ? 10 ? x1 ? x ?x ?8 2 ? 1 ? x1 ? x2 ? x3 ?9 ? x1 ? x2 ? x3 ? x4 ? 11 ? x2 ? x3 ? x4 ? x5 ? 13 ? ? ? x3 ? x4 ? x5 ? 8 ? x4 ? x5 ? 5 ? ? x5 ? 3 ? ? x1 , x2 , x3 , x4 , x5 ? 0, ? ? x1 , x2 , x3 , x4 , x5皆為整數 OR:SM ?

s.t.

第三節 整數規劃應用
三、項目投資選擇
有600萬元投資5個項目,收益如表,求利潤最大的方案?
項目 I II III IV V 投資額 210 300 150 130 260 項目收益 160 210 60 80 180 項目 I、II、III 中選 1 項 項目 III、IV 之中選 1 項 選項目 V 必先選項目 I 約束條件

?1 xj ? ? ?0

選中第j個項目投資

不 選中第j個項目投資

max Z ? 160x1 ? 210x2 ? 60x3 ? 80x4 ? 180x5 ?210x1 ? 300x2 ? 150x3 ? 130x4 ? 260x5 ? 600 ? ? x1 ? x2 ? x3 ? 1 ? ? x3 ? x 4 ? 1 ?x ? x 1 ? 5 ? x1 , x2 , x3 , x4 , x5 ? 0或1 ?

90

OR:SM

91

OR:SM

? ***********最優解如下**********

? ? ? ? ? ? ? ? ? ? ? ? ? ?
92

目標函數最優值為 : 420 變量 最優解 -------------x1 1 x2 0 x3 0 x4 1 x5 1 約束 松弛/剩余 --------------1 0 2 0 3 0 4 0
OR:SM

第三節 整數規劃應用
四、互斥約束問題
? 例如關于煤資源的限制,其約束條件為: 4 x1 ? 5x2 ? 200
? 企業也可以考慮采用天然氣進行加熱處理:

3x1 ? 5x2 ? 180

? 這兩個條件是互相排斥的。引入0—1變量y,令

?1 采用煤加熱約束起作用 y?? 作用 ?0 采用天燃氣加熱約束起 ? 互斥問題可由下述的條件來代替,其中M是充分大的數。

4 x1 ? 5 x2 ? 200? (1 ? y) M 3x1 ? 5 x2 ? 180? yM

93

OR:SM

?例:某廠生產甲乙產品,(1)如何安排每周的銷售額為最大?
甲 原材料 (公斤) 機時 (小時) 煤 (公斤) 天然氣 (升) 銷售價格(元) 9 5 4 3 390 乙 4 2 5 5 352 資源擁有量 360 220 200 180

max Z ? 390 x1 ? 352 x2 ?9 x1 ? 4 x2 ? 360 ? ?5 x1 ? 2 x2 ? 220 ? s.t. ?4 x1 ? 5 x2 ? 200 ? (1 ? y ) M ?3x ? 5 x ? 180 ? yM 2 ? 1 ? x1 , x2 ? 0; y ? 0或1 ?
94 OR:SM

? ? ? ? ? ? ? ? ? ? ? ? ? ?
95

M=10000 最優解如下 目標函數最優值為 : 31680 變量 最優解 -------------x1 0 x2 90 x3 1 約束 松弛/剩余 --------------1 0 2 40 3 89750 4 9730

? M=100000 ? 最優解如下 ? 目標函數最優值為 : 31680 ? 變量 最優解 ? -------------? x1 0 ? x2 90 ? x3 1 ? 約束 松弛/剩余 ? --------------? 1 0 ? 2 40 ? 3 899750 ? 4 99730
OR:SM

第三節 整數規劃應用
五、租賃生產問題
服裝公司租用生產線擬生產T恤、襯衫和褲子。 每年可用勞動力8200h,布料8800m2。 T恤 襯衫 褲子 假設:yj=1,要租用生產線j 3 2 6 勞動力 yi=0,不租用生產線j 0.8 1.1 1.5 布料 250 400 600 售價 第j 種服裝生產量xj 100 180 300 可變成本 15 10 生產線租金(萬) 20
max Z ? 150x1 ? 220x 2 ? 300x3 ? 200000 1 ? 150000 2 ? 100000 3 y y y ?3x1 ? 2 x 2 ? 6 x3 ? 8200 ?0.8 x ? 1.1x ? 1.5 x ? 8800 ? 1 2 3 s.t.? ? x1 , x 2 , x3 ? 0, 且取整數 ? y , y , y ? 0或1 ? 1 2 3
x1 ? M 1 y1 x2 ? M 2 y 2

x3 ? M 3 y 3
OR:SM

96

第三節 整數規劃應用
六、任務指派問題
甲乙丙丁四個人,ABCD四項任務,如何指派總時間最短?
時間 人員 任務

A 3 6 2 9

B 5 8 5 2

C 8 5 8 5

D 4 4 5 2

甲 乙 丙 丁

? 一項任務只由一個人完成
x11 ? x21 ? x31 ? x41 ? 1 x12 ? x22 ? x32 ? x42 ? 1 x13 ? x23 ? x33 ? x43 ? 1 x14 ? x24 ? x34 ? x44 ? 1

解: 引入0-1變量xij ,

xij =1:任務j指派人員i去完成
xij =0:任務j不派人員i去完成

? 一人只能完成一項任務
x11 ? x12 ? x13 ? x14 ? 1 x21 ? x22 ? x23 ? x24 ? 1 x31 ? x32 ? x33 ? x34 ? 1 x41 ? x42 ? x43 ? x44 ? 1
OR:SM

min Z ? 3x11 ? 5x12 ? 8x13 ? 4 x14 ? 6 x21 ? 8x22 ? 5x23 ? 4 x24
97

?2 x31 ? 5x32 ? 8x33 ? 5x34 ? 9 x41 ? 2 x42 ? 5x43 ? 2 x44

98

OR:SM

? 最優解如下 工作 ? 人 1 2 3 4 ? -------- ----- ----- ----- ----? 1 0 0 0 1 ? 2 0 0 1 0 ? 3 1 0 0 0 ? 4 0 1 0 0 ? 此指派問題的最優值為: 13
99 OR:SM

第三節 整數規劃應用
七、設施選址問題
? 擬定在2個地點中選址設立分銷中心,執行產品的倉儲和轉運, 一個分銷中心擬定設立一個倉庫W1、W2。 ? 若設立倉庫W1,建設成本為10萬元,最大庫容為20萬臺,單位 產品的月庫存成本為2元; ? 若設立倉庫W2建造成本為20萬元,最大庫容為25萬臺,單位產 品的月庫存成本為3元。 ? 如何選址和安排調運,建造費用+運輸費用+倉儲費用為最? 解:設從供貨源Si到分銷中心Wj的運輸量為xij,從分銷中心 到需求市場Rk的運輸量為yjk。倉庫選址決策引入0-1變量wj :
?1 擬規劃建立倉庫 W j wj ? ? ?0 不規劃建立倉庫 W j
100 OR:SM

第三節 整數規劃應用
七、設施選址問題
min Z ? 2 x11 ? 5x12 ? 4 x21 ? 2 x22 ? 3 y11 ? 4 y12 ? 5 y13 ? 2 y21 ? 2 y22 ? 3 y23 ?10w1 ? 20w2 ? 2( x11 ? x12 ) ? 3( x21 ? x22 )
? 供應能力平衡約束: ? 市場需求平衡約束:

x11 ? x12 ? 50000 x21 ? x22 ? 150000

y11 ? y21 ? 50000 y12 ? y22 ? 100000 y13 ? y23 ? 50000
x11 ? x12 ? 200000w1 x21 ? x22 ? 250000w2

? 倉儲能力限制約束:

? 分銷中心不存留產品: x11 ? x21 ? y11 ? y12 ? y13 x12 ? x22 ? y21 ? y22 ? y23 ? 所有變量大于等于零: x11 , x12 , x21, x22 , y11, y12 , y13 , y21, y22 , y23 ? 0
101 OR:SM

第5 章 目標規劃
內容提要 Sub title
第一節 多目標規劃問題 第二節 目標規劃數學模型 ?目標的期望值 ?正負偏差變量 ?目標達成函數 ?目標優先級別 第三節 目標規劃的圖解法 第四節 目標規劃單純形法 第五節 目標規劃應用案例
102 OR:SM

第一節 多目標規劃問題
一、線性規劃的局限性
?

線性規劃的局限性
? 只能解決一組線性約束條件下,某一目標而且只能是一個目標 的最大或最小值的問題

?

實際決策中,衡量方案優劣考慮多個目標
? 生產計劃決策,通?紤]產值、利潤、滿足市場需求等 ? 生產布局決策,考慮運費、投資、供應、市場、污染等

?

?

這些目標中,有主要的,也有次要的;有最大的,有最小的; 有定量的,有定性的;有互相補充的,有互相對立的,LP則 無能為力 目標規劃(Goal Programming)
多目標線性規劃 ? 含有多個優化目標的線性規劃

103

OR:SM

第一節 多目標規劃問題
二、多目標規劃的提出
例:甲乙產品的最優生產計劃。
資源 產品 甲 乙 現有資源

設備A
設備B 設備C

2
0 3

0
2 4

16
10 32

單位利潤

3

5

解:線規劃模型: maxZ=3x1+5x2 2x1 ≤16 2x2 ≤10 3x1+4x2 ≤32 x1,x2 ≥0
這些目標之間 相互矛盾,一 般的線性規劃 方法不能求解

? 根據市場需求/合同規定:
? 希望盡量擴大甲產品 ? 減少乙產品產量。

maxZ1=3x1+5x2

maxZ2=x1 minZ3=x2
2x1

? 又增加二個目標:
104

≤16 2x2 ≤10 3x1+4x2 ≤32 x1,x2 ≥0

OR:SM

第一節 多目標規劃問題
三、多目標規劃的解法
? 加權系數法:
? 為每一目標賦一權數,把多目標轉化成單目標。 ? 但權系數難以科學確定。

? ?

優先等級法:
? 各目標按重要性歸不同優先級而化為單目標。

有效解法:
? 尋求能照顧到各目標而使決策者感到滿意的解。 ? 但可行域大時難以列出所有有效解的組合。

?

目標規劃法:
? 對每一個目標函數引入正的或負的偏差變量; ? 引入目標的優先等級和加權系數。

105

OR:SM

第二節 目標規劃的數學模型
一、目標期望值
? 每一個目標希望達到的期望值(或目標值、理想值)。 ? 根據歷史資料、市場需求或上級部門的布臵等來確定。

二、偏差變量
? ? ? ? 目標的實際值和期望值之間可能存在正的或負的偏差。 正偏差變量dk+ 表示第k個目標超過期望值的數值; 負偏差變量dk- 表示第k個目標未達到期望值的數值。 同一目標的dk+ 和dk- 中至少有一個必須為零。

目標約束 ? 引入正負偏差變量,對各個目標建立目標約束(軟約束)
? ? ckj x j ? d k ? d k ? E * ? j ?1 n

106

OR:SM

第二節 目標規劃的數學模型

上例中要求: ? 目標一是利潤最大,擬定利潤目標是30; ? 目標二是減少乙產品產量但希望不低于4件; ? 目標三是甲產品產量希望不少于6件 ; ? 對各目標引入正、負偏差變量: 3x1+5x2 +d1-- d1+ = 30 x2 +d2- - d2+ =4 x1 +d3– -d3+ = 6

107

OR:SM

第二節 目標規劃的數學模型
三、目標達成函數
目標達成函數:偏差變量之和為最小值。 ? 若要求盡可能達到規定的目標值 正負偏差變量dk+ , dk- 都盡可能小,即minSk=dk++dk? 若希望盡可能不低于期望值(允許超過) 負偏差變量dk- 盡可能小,不關心超出量dk+ :minSk= dk? 若允許某個目標低于期望值,但希望不超過 正偏差變量dk+盡可能小,不關心低于量dk- :minSk= dk+

四、優先等級權數
? ? ?

目標重要度不同,用優先等級因子Pk 表示第k等級目標。 優先等級因子Pk 是正的常數, Pk >> Pk+1 。 同一優先等級下目標的相對重要性賦以不同權數w。
OR:SM

108

第二節 目標規劃的數學模型

例如 ? P1 級目標實現利潤至少30元; ? P2級目標是甲乙產品的產量 假設:乙產品產量不少于4件比甲產品產量不少于6 件更重要,取其權重為2

minG= P1 d1- + P2(2d2- + d3+ ) 3x1+5x2 +d1-- d1+ = 30 x2 +d2- - d2+ = 4 x1 + d3- - d3+ = 6 x1 , x2 ,dk- , dk+ ≥0(k=1,2,3)

109

OR:SM

第三節 目標規劃的圖解法
目標規劃的圖解法 ?首先,按照絕對約束畫出可行域, ?其次,不考慮正負偏差變量,畫出目標約束的邊界線, ?最后。按優先級別和權重依次分析各級目標。
min G ? Pd1? ? P2 (2d 2 ? ? d3? ) 1 ?3x1 ? 5 x2 ? d1? ? d1? ? 30 ? ? ? ? x2 ? d 2 ? d 2 ? 4 ?x ? d ? ? d ? ? 6 3 ? 1 3 ?2 x ? 16 s.t. ? 1 ?2 x2 ? 10 ?3x ? 4 x ? 32 2 ? 1 ? x1 , x2 ? 0 ? ? ? ?dl , dl ? 0(l ? 1, 2,3) ? (1) (2) (3) (4) (5) (6) (7)

x2
6

x1=5, x2=4
d3? d3?
d2?

2x1 =16 2x2 =10

D 4

E

C H G

? d2

d1?

2
d1?

B
F A 3x1 +4 x2 =32 10

0
110

2

4

6

x1
OR:SM

軟件求解

111

OR:SM

運算結果
? step 1 ? step 2

? ? ? ? ? ? ? ? ? ? ?

目標函數值為 : 0 變量 解 -------------x1 1.667 x2 5 d10 d1+ 0 d20 d2+ 1 d34.333 d3+ 0

相差值 -------0 0 1 0 0 0 0 0

? ? ? ? ? ? ? ? ? ? ?

目標函數值為 : .667 變量 解 -------------x1 5.333 x2 4 d10 d1+ 6 d20 d2+ 0 d3.667 d3+ 0

相差值 -------0 0 0 0 .667 1.333 0 1

112

OR:SM

第四節 目標規劃的應用案例
一、無窮多滿意解
計劃生產兩種產品,首先要充分利用設備工時而不加班;然

后考慮利潤不低于100元。問應如何制定產品A、B的產量。

解:設x1,x2表示A、B產品的產量。兩個等級的目標:
P1:充分利用電量限額,正負偏差之和為最小 ? ? P (d1 ? d1 ) 目標達成函數 1

10x1 ? 12x2 ? d1 ? d1 ? 66 P2 :利潤額希望不能低于100元,負偏差最小 ? P2 d 2 目標達成函數

目標約束條件

?

?

目標約束條件
113

10x1 ? 20x2 ? d 2 ? d 2 ? 100
OR:SM

?

?

第四節 目標規劃的應用案例
一、無窮多滿意解
由于材料供應限量為8單位,所以有系統約束條件,如下
2 x1 ? x2 ? 8

該問題的目標規劃模型如下,圖解法求解如圖
x2 B
(1) (2) (3)

min G ? P (d1? ? d1? ) ? P2 d 2 ? 1 ?10 x1 ? 12 x2 ? d1? ? d1? ? 66 ? ? ? ?10 x1 ? 20 x2 ? d 2 ? d 2 ? 100 s.t. ? ?2 x1 ? x2 ? 8 ? x , x ? 0, d ? , d ? , d ? , d ? ? 0 ? 1 2 1 1 2 2

D 4 2
d1?

G C
d1?
? d2

d2?

2
114

A

6

8

10

x1
OR:SM

115

OR:SM

運算結果
? ? ? ? ? ? ? ? ? ? step 1 目標函數值為 : 0 變量 解 -------------x1 1.5 x2 4.25 d10 d1+ 0 d20 d2+ 0

相差值 -------0 0 1 1 0 0

? ? ? ? ? ? ? ? ? ?

step

2 目標函數值為 : 0 變量 解 -------------x1 1.5 x2 4.25 d10 d1+ 0 d20 d2+ 0

相差值 -------0 0 1 1 0 0

116

OR:SM

第四節 目標規劃的應用案例
二、加班時間問題
例:某音像店有5名全職售貨員和4名兼職售貨員,全職 售貨員每月工作160小時,兼職售貨員每月工作80小時。根 據記錄,全職每小時銷售CD25張,平均每小時工資15元, 加班工資每小時22.5元。兼職售貨員每小時銷售CD10張, 平均工資每小時10元,加班工資每小時10元,F在預測下 月CD銷售量為27500張,商店每周開門營業6天,所以可能 要加班。每出售一張CD盈利1.5元。 商店經理認為,保持穩定的就業水平加上必要的加班, 比不加班就業水平要好,但全職銷售員如果加班過多,就 會因為疲勞過度而造成效率下降,因此不允許每月加班超 過100小時,建立相應的目標規劃模型。
117 OR:SM

第四節 目標規劃的應用案例
二、加班時間問題
首先,確定目標約束的優先級。如下: P1:下月的CD銷售量達到27500張; P2:全職售貨員加班時間不超過100小時; P3:保持全體售貨員充分就業,對全職的要比兼職的 加倍優先考慮; P4:盡量減少加班時間,對兩種售貨員區別對待,權 重由他們對利潤的貢獻而定。 其次,建立目標約束函數 (1)銷售目標約束,設全體全職售貨員下月的工作時 間x1,全體兼職售貨員下月的工作時間 x2;達不到銷售 目標的偏差d1-,超過銷售目標的偏差 d1+。
min G1 ? Pd1? 1 25 x1 ? 10 x2 ? d1? ? d1? ? 27500
118 OR:SM

第四節 目標規劃的應用案例
二、加班時間問題
(2)正常工作時間約束。設全體全職售貨員下月的停工時間d2-, 加班時間d2+ ;全體兼職售貨員下月的停工時間d3-,加班時間d3+。
min G3 ? P3 (2d 2 ? ? d3? ) x1 ? d 2 ? ? d 2 ? ? 800 x2 ? d3? ? d3? ? 320

(3)加班時間的限制。設全體全職售貨員下月的加班不足100小時
的偏差d4-,加班超過100小時的偏差 d4+ 。

min G2 ? P2 d 4 ? x1 ? d 4 ? ? d 4 ? ? 900

兩類售貨員區別對待,權重比d2+:d3+ =1:3,另一加班目標約束為
min G4 ? P4 (d 2 ? ? 3d3? ) x1 ? d 2 ? ? d 2 ? ? 800
119

x2 ? d3? ? d3? ? 320

OR:SM

第四節 目標規劃的應用案例
二、加班時間問題
第三,按目標的優先級,寫出相應的目標規劃模型:
min G ? Pd1? ? P2 d 4? ? P3 (2d 2? ? d 3? ) ? P4 (d 2? ? 3d 3? ) 1 ?25 x1 ? 10 x2 ? d1? ? d1? ? 27500 ? ? ? ? x1 ? d 2 ? d 2 ? 800 ? x ? d ? ? d ? ? 320 ? 3 3 s.t. ? 2 ? ? ? x1 ? d 4 ? d 4 ? 900 ?x , x ? 0 ? 1 2 ?dl ? , d l ? ? 0 l ? 1, 2,3, 4 ?

運用LINGO軟件求解得 x1=900,x2=500,下月共銷售CD盤27500 張,獲利27500×1.5-800×15-100×22.5-500×10=22000。
120 OR:SM

第四節 目標規劃的應用案例
三、目標管理方案
例:某公司準備生產甲、乙產品,據市場調查:甲產品的最大 市場需求3臺,乙產品的最大市場需求2臺。

在滿足現有電力資源嚴格供給約束的前提下,該廠長考慮兩 個目標:一是總利潤不低于3600元;二是充分利用設備臺時, 但盡量少加班。問應如何制定產品甲、乙的產量,試建立其目 標規劃的數學模型。
121 OR:SM

第四節 目標規劃的應用案例
三、目標管理方案
1. 利潤期望優先
目標規劃數學模型:
min G ? Pd1? ? P2 (d 2 ? ? d 2 ? ) 1 ?300 x1 ? 400 x2 ? d ? d ? 3600 ? ? ? ?30 x1 ? 60 x2 ? d 2 ? d 2 ? 360 ?5 x ? 5 x ? 60 2 ? 1 ? s.t. ? x1 ? 8 ?x ? 6 ? 2 ? x1 , x2 ? 0 ? ? ? ?dl , dl ? 0 l ? 1, 2 ?
? 1 ? 1

運用圖解法進行求解

x2

10 8
D
4

d d1?

? 1

x1 =8 E
d2?

C B F G 6 A 10

x2 =6

d

? 2

x1 =8, x2 = 3
5x1 +5x2 =60 12 x1

2 0 2
0

4

122

OR:SM

第四節 目標規劃的應用案例
1. 利潤期望優先
?
? ?

滿意解:x1 =8, x2 = 3 設備能力:需求:30?8+60 ?3=420,實際:360 實現目標P1和P2,降低甲乙產品的設備消耗:降低率(420-360)/360=17%, 甲產品的設備消耗降為30 ?(1-17%)=25, 乙產品的設備消耗降為60 ?(1-17%)=50。
生產部目標 甲產品的產量:8,成本:900 乙產品的產量:3,成本:1400 總利潤:3600 單位甲:300 單位乙:400 技術部目標 甲的設備單耗25,需降低5工時 乙的設備單耗50,需降低10工時 銷售部目標 甲產品的銷量:8,單價:1200 乙產品的銷量:3,單價:1800

123

OR:SM

第四節 目標規劃的應用案例
三、目標管理方案
2. 設備工時優先
目標規劃數學模型:
? min G ? Pd 2 ? P (d 2 ? ? d 2 ? ) 1 1

運用圖解法進行求解

?300 x1 ? 400 x2 ? d ? d ? 3600 ? ? ? ?30 x1 ? 60 x2 ? d 2 ? d 2 ? 360 ?5 x ? 5 x ? 60 2 ? 1 ? s.t. ? x1 ? 8 ?x ? 6 ? 2 ? x1 , x2 ? 0 ? ? ? ?dl , dl ? 0 l ? 1, 2 ?
? 1 ? 1

x2

10 8
D
4

d d1?

? 1

x1 =8 E
d2?

C B F G 6 A 10

x2 =6

d

? 2

x1 =8, x2 = 2
5x1 +5x2 =60 12 x1

2 0 2
0

4

124

OR:SM

第四節 目標規劃的應用案例
2. 設備工時優先
?
? ? ?

滿意解:x1 =8, x2 = 2 利潤總額300?8+400?2=3200,目標:3600 不能提價,就必須降低成本以增加利潤,利潤增長率為12.5% 甲產品的成本需要降為1200-300?(1+12.5%)=862.5元/臺,降低幅度4.2% 乙產品的成本需要降為1800-400?(1+12.5%)=1350元/臺,降低幅度3.6%
生產部目標 甲產品的產量:8,成本:862.5 乙產品的產量:2 ,成本:1350 總利潤:3600 單位甲:337.5 技術部目標 保證設備的正常運行

單位乙:450

甲的設備單耗30 ,乙的單耗60
銷售部目標 甲產品的銷量:8,單價:1200 乙產品的銷量:2 ,單價:1800

125

OR:SM

第7 章 網絡分析
內容提要 Sub title
第一節 第二節 第三節 第四節 第五節 圖論的概念 最小樹問題 最短路問題 網絡最大流 最小費用流

126

OR:SM

第7 章 網絡分析
18世紀,哥尼斯堡城中有一條普雷格爾河,河上有七座橋將河中的 兩個小島與河岸連接起來。人們提出了這樣的問題:一個散步者能否 從某地出發,走遍七橋且每座橋恰好經過一次,最后回到原地? 陸地A 島C

A

·
島D D · · B ·C

陸地B

1736年瑞士數學家歐拉將兩岸和小島抽象為四個點,將橋抽 象為七條邊,此問題歸結為一筆畫問題。
127 OR:SM

第一節
一、圖的內涵
1、圖的定義

圖論的概念

? 圖論的圖與一般幾何圖形或代數函數圖形是完全不同的 ? 圖論中的圖:由一些點和連接點的線所組成的“圖形” ? 點和線的位置是任意的 ? 線的曲直、長短與實際無關,代表的只是點與點之間的相互關系
? 例:表示蘇州v1 、杭州v2 、上海v3 、南京v4倉儲網點之間的物流運輸線路關系 e5 e5 ·4 v ·4 v v2· v 2· e3 e1 e3 e4 · e4 e6 e6 e1 v1 e2 ·1 v e2 v3 · e3 ·3 v e2 e5

v1
128

·

e1

v2

·

e4

v3

·

e6

v4

·
OR:SM

第一節
一、圖的內涵
2、圖的分類

圖論的概念

? 不帶箭頭的連線稱為“邊”,如公路運輸線路; ? 帶箭頭的連線稱為“弧”,如供排水的管道運輸線路。

1、無向圖

2、有向圖

由點和邊的集合所構成

由點和弧的集合所構成

? 鏈:無向網絡中,前后相繼點和邊 ? 路徑:有向網絡圖中,前后相繼并且 的交替序列稱為一條鏈。 方向一致的點弧序列稱為一條路徑。 ? 圈:閉合的鏈稱為一個圈。 ? 回路:閉合的路徑稱為一個回路。
129 OR:SM

第二節

最小樹問題

? 無圈的連通圖就是一棵樹。 ? 權數總和為最小的那棵支撐樹,稱為最小樹。 ? 求解方法:
? ?

破圈法 避圈法

例:一家企業分別要在6間辦公室鋪設網線接入口,網線的可行 走線方式如下圖所示,如何鋪設網線才能使網線總長為最短?
v2 8 v1 2 v3 8 v4
OR:SM

4 5

v5 6

3

6 6

v6

最短網線總長度為最小樹權之和2+3+4+6+6=21
130

第三節
一、雙標號算法
狄克斯特拉(Dijkstra)算法
? ? ?

最短路問題

?

路權:弧(vi, vj)的權為wij;路權是路p中各條弧權之和 最短路:在所有從vs到vt 的路p中,求一條路權最短的路 算法說明: ? 1959年提出,目前公認的最短路算法 ? 適合于求解所有弧權wij ≥0的最短路問題 算法假設:有向圖D是完備圖 ? 圖D中任意兩點vi , vj 之間,恰有兩條弧(vi , vj)和(vj , vi) ? 若vi→vj 不存在弧, 可設想一條從vi →vj 的弧, 權wij=+∞; ? 若vi → vj 有重復的弧,則保留弧權最小的弧

131

OR:SM

第三節
一、雙標號算法
?

最短路問題

基本思路: ? 從始點vs 出發,逐步探尋,給每個點標號; ? 標號分永久標號P(vk)和臨時標號T(vk) 兩種:
? 永久標號P(vk) 是從點 vs → vk 的最短路權 ? 臨時標號T(vk) 是從點 vs → vk 最短路權的上界

?

? 算法的每一步從臨時標號集中選最小者變為永久標號; ? 經過逐次改變,就可以得到從點vs 到各點的最短路。 標號形式: ? 單標號法是對每一點賦予一個路權標號 ? 雙標號法是對每一點賦予兩個標號:路標、路權
OR:SM

132

第三節
一、雙標號算法

最短路問題

例:用雙標號法求下圖網絡最短路
v1

2 4

v5

3 7
vs

8 1
v4 vt

9

v2

1 3 2

7 6 1

10

4
v3

v6

133

OR:SM

vs

第三節
一、雙標號算法
第一步:
(vs ,3) v1

最短路問題

2 4

(vs , ?) v5

3 7

8 1
(vs , ?)

(vs , 0)

vs

9

v2

(vs ,9)

1
3 2

v4

7 6
1

vt

(vs , ?)

10

4
v3 (vs ,10)

v6 (vs , ?)

134

OR:SM

第三節
一、雙標號算法
第二步:
(vs ,3)
v1

最短路問題

(v1 ,5)

2 4

v5

3 7

8 1
(v1 , 7) v4

(vs , 0)

vs

9

v2

(vs ,9)

1
3 2

7 6
1

vt

(vs , ?)

10

4
v3 (vs ,10)

v6 (vs , ?)

135

OR:SM

第三節
一、雙標號算法
第三步:
(vs ,3)
v1

最短路問題

(v1 ,5)
2 4
v5

3 7

8 1 (v5 , 6)
v4

(vs , 0)

vs

9

v2

(vs ,9)

1
3 2

7 6
1

vt

(v5 ,13)

10

4
v3 (vs ,10)

v6 (vs , ?)

136

OR:SM

第三節
一、雙標號算法

最短路問題

最終:依此類推,重復上述標號過程。得最短路。
(vs ,3)
v1

(v1 ,5)
2 4
v5

3
7

8 1

(vs , 0)

vs

9

(vs ,9)
v2

(v5 , 6)
1 3
v4

7 6 1

vt

(v6 ,12)

10

4
v3

2

v6

(v4 ,9)
137

(v3 ,11)
OR:SM

第三節
二、最短路的應用
1、網絡的中心

最短路問題

所謂網絡的中心是指一個網絡中,選擇某一點,使之其 余各點到該中心點的距離之和為最小。 例:如果要在下表中6個銷售點中選一個作為倉庫所在地,應 該建在哪個經銷點,使其余各銷售點都離它較近?

138

OR:SM

第三節
二、最短路的應用
2、網絡的重心

最短路問題

引進點的權系數,將權系數與最短距離陣各列對應元素加權 求和,再從中選擇最小的即為網絡重心。

139

OR:SM

第四節
一、相關概念與定理
1、弧容量與容量網絡

網絡最大流

對于有向圖 D=(V,A),,弧 (vi , v j ) 的容量表示弧的最大流通能力。 在V中指定一點稱為發點(記為vs ),另一點稱收點(記為vt),其余點 叫中間點,這樣的賦權有向圖就稱為一個容量網絡,記N=(V,A,B)

弧的實際通過量稱為該弧的流量;〖疉上的流量集合 f ? ?xij ? 稱為網絡上的流。 滿足下述條件的流稱為可行流。 ? ①容量限制:對每條弧 (vi , v j ) ? A ,都有 0 ? xij ? bij

2、弧的流量與可行流

?
140

②平衡條件:中間點流出量=流入量
OR:SM

第四節
一、相關概念與定理
3、前向弧與后向弧

網絡最大流

μ是從vs 到vt 的鏈,方向從vs →vt ,則鏈μ上的弧分為兩類 ? 前向。夯〉姆较蚺c鏈μ的方向相同,記μ+ ? 后向。夯〉姆较蚺c鏈μ的方向相反,記μ-

4、飽和弧與非飽和弧
( 弧 vi , v j ) 的流量 xij 與之容量 bij 比較: ? 滿足 xij ? bij 的弧稱為飽和弧,弧的流量不能再擴充; ? 滿足 xij ? bij 的弧稱為非飽和弧,弧的流量允許再被擴大。

5、零弧與非零弧
? 滿足 xij ? 0 的弧稱為零弧。由于 xij ? 0 , 所以弧的流量不能減; ? 滿足 xij ? 0 的弧稱為非零弧;〉牧髁靠梢员粶p小, 但要滿足 xij ? 0。
141 OR:SM

第四節
一、相關概念與定理
6、流量可以擴充的路

f ? ?xij ?

網絡最大流

①μ上的所有前向弧為非飽和弧,即滿足 xij ? bij,可以擴充流量 ②μ上的所有后向弧為非零弧,即滿足 xij ? 0,可以減少流量;

是一可行流,μ是從vs 到vt 的鏈,若鏈μ滿足:

則稱是一條關于可行流 f 的可擴充流量的路,亦稱增廣鏈。

7、流量可以擴充的路
可行流中,網絡發點的流出量(或網絡收點的流入量)就 是網絡的流量。 一個容量網絡的諸可行流中,網絡流量最大的可行流,稱 為最大流

142

OR:SM

第四節
二、求最大流標號法

網絡最大流

1956年,福特和富爾克遜提出了尋求網絡最大流的基本方法, 稱為福特-富爾克遜算法(Fold-Fulkerson Algorithm)。

? 標號過程
? 給定可行流X={xij} ,標號判斷有無增廣鏈 ? ①先給vs 標上(vs, +),vs已標號尚未檢查,其余未標號 ? ②取一個已標號但未檢查的點vi進行檢查,對未標號點vj : ? 前向弧(vi, vj)可以擴充流量(xij<rij) ? vj尚未標號,則給vj 標號(vi,+),vj 成為己標號尚未檢查的點 ? 后向弧(vk, vi)可以減少流量(xki>0) ? vk尚未標號,則給vk 標號(vi, -),vk成為己標號尚未檢查的點 ? vi 成為已標號已檢查的點,在其標號下劃橫線 ? ③檢查收點vt 是否已標號: ? vt被標上號則找到增廣鏈,進行流量調整;否則轉第②步 ? 若所有標號都已檢查,vt又未標號,則不存在增廣鏈
143 OR:SM

第四節
二、求最大流標號法
? 流量調整過程

網絡最大流

? 反向追蹤找出vs 到vt 的增廣鏈μ ? 計算增廣鏈μ上可調整的流量θ
?rij ? xij ? ? ? min? ? xij ?
? xij ? ' xij ? ? xij ? ? ?x ?? ? ij

(vi , v j ) ? ? ? ? ? ? (vi , v j ) ? ? ? ? ?
(vi , v j ) ? ? (vi , v j ) ? ? ? (vi , v j ) ? ? ?

? 調整可行流的流量,得新的可行流xij ′

? 抹去所有標號,對新的可行流X ′ ={xij′},重新進入標號過程
144 OR:SM

第四節
二、求最大流標號法

網絡最大流

例:下圖表示了企業所處的供應市場(v1和v2)、配送中心(v3 和v4、以及銷售市場(v5、v6和 v7)組成的網絡,各弧上括號里的 前一個數字表示弧的容量,后一個數字是目前的實際流量。 試求這個供應-銷售網絡的最大流方案。
(4,4)
v1

(10,6)

v5

v3

(5,5) (4,3) (15,9)
v6

(6,3)
v4

v2

(6,6)
145

v7
OR:SM

第四節
二、求最大流標號法

網絡最大流

供應-銷售網絡的可行流
(4,4)
v1 v5

(10,6)

v3

(5,4) (5,5) (10,8)

(15,6)
vs

(4,3) (15,9)

v6

vt

(6,3)
v4

(12,12)
v2

(8,6) (6,6)
v7

146

OR:SM

第四節
二、求最大流標號法

網絡最大流

供應-銷售網絡的可擴充路
(+ v s ,9)
v1

(+ v1 ,4) (10,6)
v3

(4,4)

v5

(5,4) (5,5) (+ v 6 ,2)
v6

(15,6) (+ v s ,∞) v s (12,12)
v2

(10,8)

(4,3) (15,9)

vt

(6,3)
v4

(+ v 4 ,3) (8,6)
v7

(- v3 ,3)

(+ v 2 ,3) (6,6)

147

OR:SM

第四節
二、求最大流標號法

網絡最大流

調整后的可行流
(4,4)
v1 v5

(10,8)

v3

(5,4) (5,5) (10,10)

(15,8)
vs

(4,1) (15,11)

v6

vt

(6,5)
v4

(12,12)
v2

(8,6) (6,6)
v7

最大流量為 f ? ? xs1 ? xs 2 ? x5t ? x6t ? x7t ? 20
148 OR:SM

第四節
三、網絡的瓶頸識別
1、截集-截量與最小截集

網絡最大流

? 截集: ? 對于網絡N=(V,A,R),將V分為兩個非空集合S和S',使 發點vs∈S,收點vt∈S' ? 所有起點屬于S而終點屬于S'的弧的集合稱為截集 (S,S') ? 截量:截集(S,S') 中所有弧的容量之和 r(S,S') ? 最小截集:截量最小的截集

2、最大流-最小截量定理
? 網絡中,任一可行流的流量恒不超過任一截集的截量, 稱為流量-截量定理。 ? 最小截量的大小影響總流量的提高
149 OR:SM

第五節
一、調整法求解步驟

最小費用流

? 先不考慮費用問題,求得任一可行流X ? 據此構造賦權有向圖W(X)
? 弧(vi, vj)的流量可以增加,則照原方向畫弧,標上費用cij ? 弧(vi, vj)的流量可以減少,則照反方向畫弧,標上費用-cij ? 在賦權有向圖W(X)中尋找負回路(總權為負值的回路): ? 若沒有負回路,則得到最小費用流 ? 若存在負回路,則調整與負回路相對應的弧上的流量
? 頂點是原網絡N的頂點 ? 弧權根據可行流X確定

? 計算調整量θ,進行流量調整
? 若弧(vi,vj)與負回路方向一致,則其流量調整為xij +θ ? 若弧(vi,vj) 與負回路方向相反,則其流量調整為xij -θ

? 賦權有向圖→尋找負回路→調整流量…直到沒有負回路
150 OR:SM

第五節
二、調整法應用舉例

最小費用流

例:下圖表示了企業所處的供應市場(v1和v2)、配送中心 (v3和v4、以及銷售市場(v5、v6和 v7)組成的網絡。 弧旁的數字為 (bij , xij ) cij ,分別表示弧的容量、實際流量、費用。 試求這個供應-銷售網絡流的最小費用流
(4,4)
v1

(10,8) 5 6

v5

v3

10
(5,5) 10 1
v6

(5,4)

(15,8) 30
vs

(10,10) 1 1 (8,6)

(4,1)

vt

35 (12,12)
v2
151

(6,5) 8
v4

(15,11) 4

3 (6,6)

v7
OR:SM

第五節
二、調整法應用舉例
1、賦權有向圖 W ( f1 )

最小費用流

-10
v1 v3

v5

1 -1

30 -30
vs

-10 6

-6
4 -4

v6

-35
v2 v4

8 -8 -3
v7

-1
1 -1

vt

2、尋找負回路
? 在賦權有向圖 W ( f1 ) 中,尋找總權數為負的回路 ? 選取負權絕對值大的那條負回路進行流量分布調整
152 OR:SM

第五節
二、調整法應用舉例
3、調整弧流量

最小費用流

(4,4)
v1

(10,9)
5 6

v5

v3

10 (5,5) 10 1
v6

(5,4)

(15,9) 30
vs

(10,10) 1 1 (8,6)

(4,0)

vt

35 (12,11)
v2

(6,5) 8
v4

(15,11) 4

3 (6,6)

v7

? 重復上述步驟,直至找不到負回路 ? 最小費用為各弧上流量和單位費用的乘積之和,從左向右依次為 9?30+11?35+9?5+6?0+11?4+4?10+5?10+5?8+6?3+4?1+10?1+6?1=912。
153 OR:SM

第8 章 網絡計劃
內容提要 Sub title
第一節 網絡圖的繪制 第二節 關鍵路線法 ? 結點的時間參數 ? 作業的時間參數 ? 時差與關鍵路線 第三節 計劃評審技術 第四節 網絡計劃優化 ? 縮短工程工期 ? 工期-費用優化 ? 工期-資源優化 第五節 緩沖時間設置
154 OR:SM

第8 章 網絡計劃
? 網絡計劃的發展歷程
? ? ?

關鍵路線法(Critical Path Method,CPM ) 計劃評審技術(Program Evaluation and Review Technique,PERT ) 圖示評審技術(Graphic Evaluation and Review Technique,GERT )

?

風險評審技術(Venture Evaluation Review Technique,VERT )

? 網絡計劃技術的特性
網絡計劃技術只不過是反映和表達項目計劃安排的一種方法, 是被項目施工技術所決定的,它只能適應項目施工方法的要求。 是把工程進度安排通過網絡的形式直觀地反映出來。

155

OR:SM

第一節

網絡圖的繪制

一、網絡計劃的圖示形式
? 工序(作業):一項需要人財物或時間等資源的相對獨立的活動過程
? 在網絡圖中用箭線“→” 表示, ? 前面直接相連工序稱緊前工序,

? 直接相連的后繼工序為緊后工序。

? 結點(事項):相鄰工序的分界點
? 一般用圓圈來表示,每個結點編上順序號, ? 結點既不消耗人力、物力,也不占用時間。

? 網絡圖
? 由工序、事項及時間參數所構成的有向圖即為網絡圖。 ? 箭線表示工序,結點為工序間相互關系的網絡圖,稱箭線式網絡 ? 結點表示工序,箭線為工序間相互關系的網絡圖,稱結點式網絡
156 OR:SM

第一節

網絡圖的繪制

一、網絡計劃的圖示形式
1、箭線式網絡圖
1 A 2 B 5 3

i

N-作業名稱 t-作業時間

2

j C 3 4

D 5 E 5 5

2、結點式網絡圖
i N t

i-作業序號
N-作業名稱 t-作業時間

1 2

2 5

3 5 6 0

4 3
157

5 5
OR:SM

第一節
? 工序表示的規定

網絡圖的繪制

二、箭線式網絡圖的規則
? 一條箭線和它的相關事項只能代表一道工序,不能代表多道工序, ? 兩個結點之間只能有一條箭線相連。

? 不允許出現缺口與回路
? 網絡圖中只能有一個始點和一個終點,使得自網絡圖的始點經由任何路徑都 可以到達終點。

? 虛工序
? 虛工序是為了表達相鄰工序之間的邏輯關系而虛設的工序。 ? 不消耗時間、費用和資源,一般用虛箭線表示。

? 方向的規定
? 網絡圖是有方向的,工序應按工藝流程順序或工作邏輯關系從左向右排列。

? 編號的規定
? 編號應從始結點開始,按照時序依次從小到大對結點編號,直到終結點。 ? 編號時不允許箭頭編號小于箭尾編號。
158 OR:SM

第一節
三、箭線式網絡圖舉例

網絡圖的繪制

某工程的工程一覽表
工序 緊前工序 工序時間 a -6 b -3 c -4 4 b 3 1 4 3
159 OR:SM

d a 4

e a,c 5

f b 10

g b,d,e 8

f 10 d 4 e 5 5 g 8 6

a 6 c

2

第二節
一、結點的時間參數
? 結點的最早時間tE(j)

關鍵路線法

? tE(j)等于從始點開始到本結點的最長路線上各道工序時間之和。 ? 從始點事項開始,自左向右,順著箭線方向逐個計算 。

?t E (1) ? 0 ? ?t ( j ) ? max{t (i ) ? t (i, j )} E ?E i ?

? 結點的最遲時間 tL(j)
? 指以該結點為結束的各道工序最遲必須完工的時刻,否則將會影 響后續工序按時開工,以至推遲整個工程的完工時間。 ? 從終點開始,從右向左,逆箭線方向逐個計算。

?t L (n) ? t E (n) ? ?t (i ) ? min{t ( j ) ? t (i, j )} L ?L j ?
160 OR:SM

第二節
一、結點的時間參數
計算結點時間參數
3

關鍵路線法

9 4

b

f 3 6 2 d 4 e 5 11 11 g 8 6 10 19

0 0 1

6 a 6 c

19

4
3 6
161

5

6
OR:SM

第二節
二、作業的時間參數

關鍵路線法

? 最早可能開工時間tES(i, j)

? 一個作業必須在其各緊前作業都完工后才能開工, ? 作業最早可能開工時間等于其箭尾事項的最早時間。 ? tES(i, j)= tE(i) ? 從最早可能開工時間開工,完成本作業的時間 。 ? tEF(i, j)= tES(i, j) +t(i, j)

? 最早可能完工時間 tEF(i, j)
? 最遲必須開工時間 tLS(i, j)

? 在不影響工程如期完工的前提下,作業最遲必須開工的時刻。 ? 等于它的箭頭事項的最遲時間減去本作業的作業時間 tLS(i, j)= tL( j) - t(i, j) ? 在不影響工程如期完工的前提下,作業最遲必須完工的時刻 。 ? tLF(i, j)= tLS(i, j) +t(i, j) = tL( j)
OR:SM

? 最遲必須完工時間 tLF(i, j)
162

第二節
三、時差與關鍵路線

關鍵路線法

? 時差又稱寬裕時間:不影響如期完成任務的條件下,各道工序可以機 動使用的一段時間。 ? 總時差R(i, j):不影響其緊后工序最遲必須開工的前提下,本工序最 早可能完工時間可以推遲的時間。 ? R(i, j)= tLS(i, j) -tES(i, j) = tLF(i, j) -tEF(i, j) = tL( j) -tE(i) -t(i, j) ? 單時差r(i, j):不影響其緊后工序最早可能開工的前提下,本工序最早 可能完工時間可以推遲的時間。 ? r(i, j)= tE( j) -tE(i) -t(i, j) ? 總時差為零的工序稱為關鍵工序;關鍵工序組成關鍵路線。 tES tLS tEF r(i,j) tLF

tES
R(i,j)

tLS

tEF

tLF

163

OR:SM

第二節
三、時差與關鍵路線
路線
1 2 3

關鍵路線法

路線的組成
①→④→⑥ ①→④→⑤→⑥ ①→②→⑤→⑥

路線長度
3+10=13 3+0+8=11 6+4+8=18

3 4 b

9

4
5

①→②→③→⑤→⑥
①→③→⑤→⑥

6+0+5+8=19
4+5+8=17

f 3 6 2 d 4 e 5 3 5 11 11 g 8 6 10 19 19

0 0 1

6 a 6 c 4

6
164

6
OR:SM

第二節
四、時間參數算例

關鍵路線法

計算作業最早開始時間、最遲開始時間、最早結束時間、 最遲結束時間以及時差,從表中尋找總時差與單時差都為 零的作業,即為關鍵作業,將其連接起來就是關鍵路線。
作業 a b c
t (i , j )
tES (i, j ) tEF (i, j ) tLS (i, j ) tLF (i, j ) R (i , j )

r (i , j )

關鍵 作業 a e g
OR:SM

6 3 4

0 0 0 6 6 3 11

6 3 4 10 11 13 19

0 6 2 7

6 9 6 11

0 6 2 1

0 0 2 1

d
e f g
165

4
5 10 8

6
9 11

11
19 19

0
6 0

0
0 0

第三節
一、作業時間估計

計劃評審技術

? 工序時間的三種可能估計: ? 最樂觀時間:在最理想的情況下完成工序所需時間a; ? 最悲觀時間:在最不利的情況下完成工序所需時間b; ? 最可能時間:在正常情況下完成工序所需時間m。 ? 加權平均就是工序時間t
工序時間 t ?

二、計算期望工期
工期TE ? ? (
i

a ? 4m ? b b?a 2 ,方差 ? 2 ? ( ) 6 6

? 工程期望工期等于關鍵路線上各道工序的時間之和 。
ai ? 4mi ? bi b ? ai 2 ),方差? 2 ? ? ( i ) 6 6 i
Tk ? TE

? 設規定的工程完工時間為Tk,則完工時間的概率為 ? ( x) ?
166

?

OR:SM

第三節
三、PERT應用舉例

計劃評審技術

某項目的作業流程及其時間估計
作業 a b c 緊前作業 a,b 作業時間估計 樂觀時間 3 2 1 悲觀時間 可能時間 5 4 3 4 3 2 4 3 2 作業時間 期望 方差 1/9 1/9 1/9

d
e f g

a
c,d a e,f

3
2 7 2

11
10 13 10

4
9 10 6

5
8 10 6

16/9
16/9 1 16/9

若合同規定工期為20,求如期完工的概率;若要求有90%的把握如 期完工,求可接受的合同工期的為多少。
167 OR:SM

第三節
三、PERT應用舉例
4 0 0 4

計劃評審技術

a 4 b 3

2
f d 5 3
4 7 10

17 17

1

5 e 8 4
9
9

g 6

23 23

6

c 2

? 參數計算

? 工程期望工期 TE=23 ,關鍵工序的方差?2 =49/9,則 ? (x)=-1.29,查表知 P(x)=9.9% ? P(x)=90% ,查表知 ? (x)=1.3,則可接受的合同工期為TE+ ? ? (x) =26
168 OR:SM

第四節
一、縮短工程工期

網絡計劃優化

? ①改進工藝和技術裝備,壓縮關鍵工序的作業時間 ? ②合理組織平行作業、交叉作業 ? 平行作業指兩道以上相互獨立的工序同時進行 ? 交叉作業指將緊前工序完成的部分任務分期分批地轉 入下道工序 ? ③利用時差,合理調配資源等途徑實現

169

OR:SM

第四節
二、工期-費用優化

網絡計劃優化

1、工期與成本之間關系
? 工期的縮短與費用是密切相關的 ? 工程費用最低的完工時間(最低成本日程)
費用
直接費用 工程總費用

間接費用

極限完 工時間
170

最優完 工時間

正常完 工時間

時間
OR:SM

第四節
二、工期-費用優化

網絡計劃優化

? 尋求最低成本日程的思路:從網絡計劃的關鍵工序著手,對增加 直接費用做少的某些關鍵工序采取措施,縮短其作業時間。
直接 費用

極限完 工時間

正常完 工時間

時間

趕單位時間增加的直接 費用(費率) ?
171

趕進度極限完工費用 正常完工費用 正常完工作業時間 極限完工作業時間 OR:SM

第四節
2、工期-費用優化案例

網絡計劃優化

某工程作業流程及其費用統計資料
作業 A B C D E 緊前作業 B B 作業時間(天) 正常完工 3 5 5 6 5 極限完工 3 3 4 3 2 作業直接費用(萬元) 正常完工 8 16 20 20 5 極限完工 8 19 23 23 8.6 費率 1.5 3 1 1.2

F
G H

E
D A 合計 間接費用

3
4 5

3
3 2

10
9 20 88 2萬元/天

10
11 28

2 2

172

OR:SM

第四節

網絡計劃優化

方案I:各道作業正常完工
3 10 h

a 3

2

5

0 1 0

5 b d

11

11 g

15 6 15

3
5 5 5 c 5 10

4 6
e 5 12

4

f

3

工程費用=正常完工直接費用+間接費用=88+2×15=118萬元。
173 OR:SM

第四節

網絡計劃優化

方案2:關鍵路線d上趕進度
3 8 h 2 5

a 3

0 1

5 b 3 5 5 5 c 5 4 e d

9 4

9
g 4 6

13

0

13

5
10

f 3

10

工程費用=正常完工直接費用+趕進度增加的直接費用+間接費用 =88+2×1+2×13=116萬元。
174 OR:SM

第四節

網絡計劃優化

方案3:關鍵路線b上趕進度
3 6 2 h 5

a 3

0 1

3 b 3 3 3 5 c 5 4 e d

7 4

7
g 4 6

11

0

11

5
8

f 3

8

工程費用=正常完工直接費用+趕進度增加的直接費用+間接費用 =88+2×1+2×1.5+2×11=115萬元。
175 OR:SM

第四節

網絡計劃優化
3

方案4:關鍵路線b、e上趕進度
8 h 2 5 a 3

0 1 0

3 b 3 d

6 4 3 e 4 5

6 g 4 6

10

3 3 c 5

10

f 3 7

7

工程費用=正常完工直接費用+趕進度增加的直接費用+間接費用 =88+2×1+2×1.5+1×(1+1.2)+2×11=115.2萬元。
176 OR:SM

第四節
三、工期-資源優化
資源平衡準則:
?

網絡計劃優化

在壓縮工程時間及費用的同時,要分別考量每道作業所需資

源的用量與供應能力及時間限制,以便確定每道作業可壓縮時間 的限度及其進度安排。
? ?

優先保證關鍵路線上關鍵作業對資源的需求量。 對非關鍵作業要資源,利用時差調整非關鍵作業的開工時間

和完工時間,以達到與關鍵作業在占用資源的時間上錯開,拉平 資源需要量的高峰。
?

當資源絕對受限制時,在保證不推遲或盡量少推遲工程完工

時間的前提下,全面統籌安排,最大限度地利用資源。

177

OR:SM

第四節
工序 a b

網絡計劃優化
c d e f g

每天只有13臺設備可用,計劃10天完成,試合理安排生產進度

緊前工序
作業時間 每天所需設備數

-3 13
3

-1 5

a
2 8

a
3 2

b,c
4 6

e,d
1 12

a
5 5

0

a 3 1 b 1

2 c 2

3

0

d 3 e 4 4

g 5 f 1
0

5

10 10

3

178

5 5 9 9 ? 所需工作日:3×13+1×5 +2×8 +3×2 +4×6 +1×12 +5×5=127 ? 10天完成,則平均每天所需機器12.7臺,現有機器13臺,適當安排可以完工

OR:SM

第四節
三、工期-資源優化
3、制定初始方案
工 序 a b 相關 結點 ①?② ①?③ 作業 最早 時間 開工 時間 3 1 0 0

網絡計劃優化

以最早開工時間,安排初始進度如表

總 時 差 0 4

工程進度
1
13 5 8 2 8 2 2 6 6 6 6 12 5 5 5 5 5

2
13

3
13

4

5

6

7

8

9

10

c
d e f g
179

②?③
②?④ ③?④ ④?⑤ ②?⑤

2
3 4 1 5

3
3 5 9 3

0
3 0 0 2

每天所需人數合計

18 13 13 15 15 13 11 11 6

12
OR:SM

第四節
三、工期-資源優化
工 序
a b c d

網絡計劃優化
4、調整開工時間
總 時 差
0 4 0 3
1
13

第一次調整
5 6 7 8 9 10

相關 結點
①?② ①?③ ②?③ ②?④

作業 最早 時間 開工 時間
3 1 2 3 0 0 3 3

工程進度
2
13

3
13

4

5
8 8 2 2 6 2 6 6 6 12 5 5 5 5 5

e
f g

③?④
④?⑤ ②?⑤

4
1 5

5
9 3

0
0 2

13 13 13 13 15 13 13 11 11 12 每天所需人數合計 非關鍵作業b延至第4天開工,非關鍵作業d和g延至第5天開工。
180 OR:SM

第四節
三、工期-資源優化
工 序
a b c d

網絡計劃優化
4、調整開工時間
總 時 差
0 4 0 3
1
13

第二次調整
5 6 7 8 9 10

相關 結點
①?② ①?③ ②?③ ②?④

作業 最早 時間 開工 時間
3 1 2 3 0 0 3 3

工程進度
2
13

3
13

4

5 8 8 2 2 2

e
f g

③?④
④?⑤ ②?⑤

4
1 5

5
9 3

0
0 2
5

6

6

6

6
12

5

5

5

5

每天所需人數合計
181

13 13 13 13 13 13 13 13 11 12 將非關鍵作業d延至第6天開工
OR:SM

第五節

緩沖時間設置

具體的思路是:削減每道作業的預估時間,不為單道作業設 置安全緩沖時間,而將節省的時間建立一個任務緩沖(某項任 務的總體安全時間)
182 OR:SM

第五節
4 6

緩沖時間設置
3 5 18

任務1

任務2

任務3

任務4 將每項任務的預 估時間減去一半, 然后將減去時間 的和的一半作為 項目緩沖,共用, 所需時間為原來 的3/4

1
2

2
3

3
1.5

4
2.5

項目緩沖

4.5

13.5

183

OR:SM

第五節

緩沖時間設置

考慮資源沖突,使制約因素(瓶頸資源)不受非制約因 素的影響,在每條銜接路徑與關鍵路線匯合的地方插入銜 接時間緩沖,例如零件的供貨緩沖時間
A1 A2 銜接 緩沖

C1

C2

C3

C4

項目緩沖

B1

B2

銜接 緩沖
OR:SM

184

第9 章 決策分析
內容提要 Sub title
第一節 決策分析概論 第二節 不確定性決策 第三節 風險型決策 ? 決策準則 ? 決策樹法 ? 情報價值 第四節 貝葉斯決策 第五節 效用決策理論
? 悲觀決策準則 ? 樂觀決策準則 ? 樂觀系數準則 ? 等可能性準則 ? 最小后悔準則

185

OR:SM

第一節 決策分析概論
一、決策要素
對于任何決策應包括以下幾個基本決策要素:
?

決策目標 決策如果只有一個目標稱為單目標決策,如果決策 行動方案 為了實現預訂的目的,可以采取幾種不同的行動 自然狀態 決策環境可能出現的狀態 損益矩陣 決策的結果或者是收益或者是損失 決策準則 比較、選擇方案時的判決標準和評價規則 后果評估 通常采用損益或效用作為后果指標。

目標很多并形成目標體系,這類決策稱為多目標決策。
? ? ? ? ?

186

OR:SM

第一節 決策分析概論
二、決策程序
方 案 實 施 與 控 制

確 定 決 策 目 標

預 測 自 然 狀 態

擬 定 決 策 方 案

決 策 方 案 優 選

確定性決策:自然狀態的信息是確知的 風險性決策:已知狀態概率分布,但確知 不確定決策:未來狀態信息全無
187 OR:SM

第一節 決策分析概論
三、決策分類
1. 按決策方法的性質分類
?定性決策和定量決策

2. 按決策問題的層次分類
?不同管理層級決定不同層次的管理問題, ?分成戰略性決策、戰術性決策和運作層決策。

3. 按決策出現的頻率劃分
?程序性決策和非程序性決策

4. 按自然狀態的熟知度分
?按對自然狀態的認識程度可分為

?確定性決策、風險性決策和不確定性決策。

188

OR:SM

第二節 不確定性決策
?

悲觀準則
? 決策者對客觀情況持悲觀態度,將結果估計得比較保守 ? 基本想法是壞中求好

?

樂觀準則
? 決策者總是對客觀情況抱樂觀的態度 ? 基本思路是好中求好

?

樂觀系數準則
? 決策者對客觀情況既不那么樂觀,也不那么悲觀的“折衷準則” ? 根據以往經驗,確定樂觀系數

?

等可能準則
? 把各種自然狀態等同看待,認為各狀態發生的概率相等 ? 求出各方案的損益期望,選其中的最優方案

?

后悔值準則
? 決策者制定決策后,若未能符合理想,必將后悔 ? 遺憾當初的選擇不當,以“后悔值最小”為決策準則

189

OR:SM

第二節 不確定性決策
自然狀態 ?1 需求大 30 ?2 需求小 -6

行動方案
大批量生產

悲觀準則

樂觀準則

等可能性

-6

30

(30-6)/2=12

中批量生產
小批量生產

20
10

-2
5

-2
5

20
10

(20-2)/2=9
(10+5)/2=7.5

190

OR:SM

第二節 不確定性決策
? 最小后悔準則
自然狀態 ?1 需求大 ?2 ?1 需求小 需求大 ?2 需求小 11 7 0 最大后悔

行動方案 大批量生產
中批量生產 小批量生產 目標值

30
20 10 30

-6
-2 5 5

0 10 20

11
10 20

191

OR:SM

第三節 風險性決策
一、決策準則
? 最大可能準則
? 概率最大的狀態發生的可能性最大 ? 決策實質上就變成了確定型的決策

? 期望值準則
? 根據益損期望值進行決策,最大期望收益,最小期望損失 ? 適于程序性的重復決策,且決策者可以承受一次決策損失

? 期望值與標準差準則
? 決策者希望盡可能回避風險, ? 標準差刻劃各損益值數據與期望值偏離程度 ? 標準差越小則期望值實現的可靠性越大

192

OR:SM

第三節 風險性決策
二、決策樹
1. 單級決策樹
P(?1 ) ? 0.75

? a11 =30 ? a12 =-6 ? a21 =20

2

P(? 2 ) ? 0.25
P(?1 ) ? 0.75

A1 A2
1

3

P(? 2 ) ? 0.25 ? a =-2 22
P(?1 ) ? 0.75

A3
4

P(? 2 ) ? 0.25

? a31 =10
? a32 =5 結 損 果 益 結 值 點
OR:SM

決 策 結 點
193

方 案 分 枝

狀 態 結 點

概 率 分 析

第三節 風險性決策
二、決策樹
2. 序列決策樹
開發新 產品 存銀行 成功0.8 500 -1000 60 成功0.95 開發新 產品 存銀行 存銀行 8 失敗0.05 500 -1000 60

4

失敗0.2

2

5

不咨詢
1

6 咨詢 -10 3 宜開發 0.8 不宜開發 0.2
194

9

7

10

60
OR:SM

第三節 風險性決策
三、情報價值
1. 完全信息的價值
? ? ?

完全信息即對未來狀態完全準確的預報信息。 完全信息下,風險型決策就變成了確定性決策。 獲得全情報的成本應該小于全情報的價值。 自然狀態 開發成功 0.8 開發失敗 0.2 決策方案 500 -1000 開發新產品 60 60 用入存銀行

2. 測算全信息價值

?

? ? 195

計算未獲全信息的最大期望收益值。 ?開發新品的期望值:500?0.8 -1000?0.2=200 ?存入銀行的期望值:60?0.8+60 ?0.2=60 計算全信息的期望值:500?0.8+60?0.2=412 二者之差(212)獲得這項情報愿意付出代價的最高額
OR:SM

第四節 貝葉斯決策
一、先驗概率和后驗概率
例:某石油鉆探隊準備在一遠景區勘探石油,根據預測估計 鉆井出油的概率為0.3,可以自己鉆探或是出租。 ? 自己鉆探的費用為1000萬元,出油可收入4000萬元; ? 如果出租,租金為200萬元,若有油租金再增加100萬元。 為獲更多情報,可以先做地震試驗,再行決策。地震試驗將 有油區勘測為封閉構造的概率為0.8;將無油區勘測為開放構造 的概率為0.6。地震試驗費為300萬元。試用決策樹法進行決策。 由題意知,有油事件?1的概率P(?1)=0.3,無油事件?2的概率 P(?2)=0.7,這是先驗概率; 后驗概率則是封閉構造而有油的概率P(?1|I1)=0.8,開放構造而
無油的概率 P(?2|I2)=0.4。

196

OR:SM

第四節 貝葉斯決策
二、貝葉斯概率及其決策
?由聯合概率公式知, ?由全概率公式知, ?又由貝葉斯公式知,

P( I k ,? j ) ? P(? j ) ? P( I k ? j )
P( I k ) ? ? P(? j ) ? P( I k ? j )
j

P(? j I k ) ?

P( I k ? j ) ? P (? j ) P( I k )

利用貝葉斯公式可以計算補充信息條件下的后驗概率
狀態 ? 有油 ?1 無油 ? 2 先驗概率
P(? j )

條件概率
P(I1 ? j )

聯合概率
P( I1 ,? j )

P(I2 ? j )

P( I 2 ,? j )

后驗概率
P(? j I1 ) P(? j I2 )

0.3
0.7

0.8

0.6

0.24

0.06

0.46

0.13

0.2

0.4

0.28

0.42

0.54

0.87

197

OR:SM

第四節 貝葉斯決策
?

二、貝葉斯概率及其決策
P(?1)=0.3 自鉆 不做 實驗 4 P(?2)=0.7 P(?1)=0.3 出租 5 P(?2)=0.7 △ 3000 △-1000 △ 200 △ 300

? ? ? ? ? ? ? ? ?

2

1 自鉆 做實驗 封閉 3 開放 6 出租 9 8

結點4 0.3×3000+0.7×(-1000)=200 結點5 0.3×200+0.7×300=270 結點8 0.46×3000+0.54×(-1000)=840 結點9 0.46×200+0.54×300=252 結點10 0.13×3000+0.87×(-1000) =-480 結點11 0.13×200+0.87×300 =287 結點6 決策結點,期望值為840 結點7 決策結點,期望值為287 結點2 決策結點,期望值為270 結點3 840×0.52+287×0.48=574.56
△ 3000
?

P(?1)=0.46 P(?2)=0.54

△-1000
△ 200

結點1 做地震試驗期望474.56, 不做地震試驗期望270,

P(?1)=0.46
P(?2)=0.54 P(?1)=0.13 自鉆 10 P(?2)=0.87 P(?1)=0.13 11 P(?2)=0.87 △ 300

決策結論:先進行地震試驗, 如果地震試驗是 封閉構造,則自鉆 開放構造,則出租

△ 3000
△-1000

7

△ 200 △ 300

198

OR:SM

第五節 效用決策理論
一、效用與效用值
? ? ? ?

效用是主觀性的 效用是多屬性的 效用會因時而異 效用值是相對的

二、期望效用準則
1. 效用曲線
U(R) U(R) U(R)

風險規避 199

R

風險偏好

R

風險中性

R OR:SM

第五節 效用決策理論
二、期望效用準則
2. 效用決策
例:某公司是一個小型進出口公司,面臨著兩筆進口生意,項目 A和項目B,這兩筆生意都需要現金支付。鑒于公司財務不善,公 司至多做A、B中的一筆生意,根據以往的經驗,各自然狀態商品 需求量大、中、小的發生概率以及在各自然狀況下項目A或項目B 以及不做任何項目的收益都如下表所示(單位:萬元)。
進出口生意收益值數據
自然狀態 行動方案
A1

q1

需求量大 0.3 60 100 0

q2

需求量中 0.5 40 -40 0

q3 需求量小

0.2 -100 -60 0
OR:SM

(做項目A)

A2 (做項目B) A3(不做任何項目)
200

第五節 效用決策理論
二、期望效用準則
進出口生意效用值數據
自然狀態 行動方案
A1

q1

需求量大 0.3
0.95

q2

需求量中 0.5
0.9

q3 需求量小

0.2 0

(做項目A)

A2 (做項目B) A3(不做任何項目)

1
0.75

0.55
0.75

0.4
0.75

計算各方案的效用期望值,如下: EU ( A1 ) =0.3?0.95+0.5?0.9+0.2?0=0.735, EU ( A2 ) =0.3?1+0.5?0.55+0.2?0.4=0.6555, EU ( A3 ) =0.3?0.75+0.5?0.75+0.2?0.75=0.75。 可見方案3的效用期望值為最大
201 OR:SM


網站首頁 | 網站地圖 | 學霸百科 | 新詞新語
All rights reserved Powered by 大學生考試網 9299.net
文檔資料庫內容來自網絡,如有侵犯請聯系客服。[email protected]
甘肃快3综合走势图