高项 运筹学2
??在學習高項的運籌學的時候，對學的內(nèi)容做一個記錄。
運籌學中常考的題型有:
最短和最長路徑問題、線性規(guī)劃的問題、最小生成樹的問題、對策論問題、人員分配問題等等。
對策論、博弈的問題
某公司需要根據(jù)下一年度宏觀經(jīng)濟的增長趨勢預測決定投資策略。宏觀經(jīng)濟增長趨.勢有不景氣、不變和景氣3種，投資策略有積極、穩(wěn)健和保守3種，各種狀態(tài)的收益如下表所示。
①基于樂觀主義準則（maxmax）的最佳決策是（A）
②基于悲觀主義準則（maxmin）的最佳決策是（C）
③基于后悔值準則（minmax）的最佳決策是（B）
A.積極投資
B.穩(wěn)健投資
C.保守投資
D.不投資
?解題思路：
①樂觀主義準則（maxmax 大中取大）：每行選出最大值，然后從選出來的值當中再選出最大值，這個值對應的策略，就是此準則的最優(yōu)方案。
????????第一行積極：最大值是500
????????第二行穩(wěn)健：最大值是300
????????第三行保守：最大值是400
????????以上三行的最大值是500，這時候選擇A
②悲觀主義準則（maxmin 小中取大）：每行選出最小值，然后從選出來的值當中再選出最大值，這個值對應的策略，就是此準則的最優(yōu)方案。
????????第一行積極：最小值是50
????????第二行穩(wěn)健：最小值是150
????????第三行保守：最小值是200
????????以上三行的最大值是200，這時候選擇C
③后悔值準則（minmax -- 大中取小）：分兩步
第一步：計算每個方案在各種情況下的后悔值；（后悔值=各個方案在該情況下的最優(yōu)收益-該情況下該方案的收益） 。
????????第一行不景氣是保守400最大，
????????????????積極的后悔值：400-50=350
????????????????穩(wěn)健的后悔值：400-250=150
????????????????保守的后悔值：400-400=0
?????????以此類推
第二步：找出每行的最大后悔值。然后從選出來的值當中再選出最小值，這個值對應的策略，就是此準則的最優(yōu)方案。
????????第一行積極：最大值是350
????????第二行穩(wěn)健：最大值是250
????????第三行保守：最大值是300
????????以上三行的最小值是250，這時候選擇B
?
人員分配的問題
????????某項目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四項不同任務，恰有甲、乙、丙、丁四個人去完成各項不同的任務。由于任務性質(zhì)及每人的技術(shù)水平不同。他們完成各項任務所需時間也不同。具體如下表所示:
項目要求每個人只能完成一項任務，為了使項目花費的總時間最短，應該指派丁完成()任務。
A. I
B. Ⅱ
C. Ⅲ
D. Ⅳ
解答：用匈牙利法
第一步：找出每行里面的最小值，然后在這一行分別減去這個數(shù)，得表1。
?????????????????????????????????????????????????????????表1
第二步：找出表1種每列中最小的數(shù)，然后在這一列里分別減去這個數(shù)，得表2。
?????????????????????????????????????????????????表2
第三步：在表2中按行找0，是0的就說明這個人可以做這項任務，
甲可以做任務1和4。
乙可以做任務2。
丙可以做任務1。
丁可以做任務1、3、4。
先安排唯一的，乙2、丙1，然后甲4，最后丁3。
所以答案C，丁做任務3的時候，項目花費的總時間最短
流量問題
例題：下圖標出了某產(chǎn)品從產(chǎn)地Vs到銷地Vt的運輸網(wǎng)，箭線上的數(shù)字表示這條運輸線的最大通過能力(流量)(單位:萬噸/小時)。產(chǎn)品經(jīng)過該運輸網(wǎng)從Vs到Vt的最大運輸能力可以達到（ ）萬噸/小時。
A.5
B.6
C.7
D.8
?解題第一步，找出他的所有路徑： 并找出每條路徑的流量瓶頸（最小值）
????????Vs-V2-V4-Vt，最大運力是3，
????????Vs-V2-V1-V3-V2-V4-Vt，最大運力是3，
????????Vs-V2-V1-V3-V4-Vt，最大運力是1，
????????Vs-V2-V1-V3-Vt，最大運力是1，
????????Vs-V1-V3-V2-V4-Vt，最大運力是1，
????????Vs-V1-V3-V4-Vt，最大運力是2，
????????Vs-V1-V3-Vt，最大運力是2。
第二步，從最大流量瓶頸值(路徑中的最小流量值)的路徑開始斷，即：該路徑上各段線路上的流量減去流量瓶頸值，得出剩余流量。剩余流量為0的線段應將其斷開。之后，斷流量瓶頸值排名第二大的路徑，然后重復。一直到?jīng)]有通路，過程見下圖:
??? Vs-V2-V4-Vt 這條路徑，這條路徑最大運力（流量瓶頸）為3，該路徑上各段線路上的流量減去3，得出剩余流量0-1-2，斷開流量為0的線段，得到下圖（2）
?????????Vs-V1-V3-Vt （或Vs-V1-V3-V4-Vt，這兩條路路最大運力都是2，選哪一條都可以 ）這條路徑，這條路徑最大運力（流量瓶頸）為2，該路徑上各段線路上的流量減去2，得出剩余流量3-0-0，斷開流量為0的線段，得到下圖（3）。此時已經(jīng)沒有通路。 所以最大運力為2+3=5
?
車床銑床最短時間安排的問題
例題1：
????????某車間需要用一臺車床和一臺銑床加工 A、B、C、D 四個零件。每個零件都需要先用車床加工，再用銑床加工。車床與銑床加工每個零件所需的工時（包括加工前的準備時間以及加工后的
處理時間）如下表：
?若以 A、B、C、D 零件順序安排加工，則共需 32 小時。適當調(diào)整零件加工順序，可使所需總工時最短。在這種最短總工時方案中，四個零件加工共需（）小時。
A.21
B.22
C.23
D.24
????????以順序安排加工 A、B、C、D 這四個零件為例，可以用甘特圖將工作進度計劃描述如下：
這樣安排，D最后，時間就很浪費
這種題目的調(diào)整原則如下:
第一步：將車床（第一道工序）耗時最短的活動放在第一位。
第二步：將銑床（最后一道工序）耗時最短的活動放在最后一位。
用窮舉法來做的話，一共的排序方案=4*3*2*1=24種，太多，優(yōu)化后，就兩種做法，方案 C、A、D、B，或者方案 C、D、A、B
? 以方案 C、A、D、B 零件的順序來加工，甘特圖如下： 加工共需27小時
以方案 C、D、A、B 零件的順序來加工，甘特圖如下：加工共需22小時
例題2：
????????某企業(yè)計劃研發(fā)甲、乙、丙、丁四種產(chǎn)品。每種產(chǎn)品必須依次由設(shè)計部門、制造部門和檢驗部門進行設(shè)計、制造和檢驗，而每個部門必須按同樣的順序處理這幾種產(chǎn)品。各種產(chǎn)品的各項工作所需的時間如下表所示。
只要適當安排好產(chǎn)品研究的順序，企業(yè)最快可以在() 天內(nèi)全部完成這四種產(chǎn)品的研發(fā)。.
A. 84
B. 86
C. 91
D. 93
這種題目的調(diào)整原則如下:
第一步：將設(shè)計（第一道工序）耗時最短的活動放在第一位。
第二步：將檢驗（最后一道工序）耗時最短的活動放在最后一位。
執(zhí)行方案有：
? 丁、甲、乙、丙
?丁、乙、甲、丙
以最優(yōu)方案 丁、甲、乙、丙產(chǎn)品的順序來加工，甘特圖如下：
?
從如圖所示的可以看出，該企業(yè)按照“丁、甲、乙、丙”的產(chǎn)品研發(fā)順序，
總共需要8+13+15+20+18+10=84天。
總結(jié)：
????????車床銑床最短時間安排的問題，這樣會難算一些，需要耐心一些。
總結(jié)
- 上一篇： 从线报群看短链接技术
- 下一篇： Jmeter面试题