第28講運籌學初步（2）
實際工作中經常會碰到分配工作的問題。由於工作任務的性質不同，每個人的工作能力不同，因而完成這些任務所需的時間和花費的代價也不同。我們希望通過合理分配工作，使所用時間最少或花費代價最小。
例1 甲、乙兩廠生產同一規格的上衣和褲子，甲廠每月用16天生產上衣，14天做褲子，共生產448套衣服（每套上衣、褲子各一件）；乙廠每月用12天生產上衣，18天生產褲子，共生產720套衣服。兩廠合併後，每月（按30天計算）最多能生產多少套衣服？
分析與解：應讓善於生產上衣或褲子的廠充分發揮特長。甲廠生產上衣和褲子的時間比為8∶7，乙廠為2∶3，可見甲廠善於生產褲子，乙廠善於生產上衣。
因為甲廠 30天可生產褲子 448÷14×30＝960（條），乙廠30天可生產上衣720÷12×30=1800（件），960＜1800，所以甲廠應專門生產褲子，剩下的衣褲由乙廠生產。
設乙廠用x天生產褲子，用（30-x）天生產上衣。由甲、乙兩廠生產的上衣與褲子一樣多，可得方程
960＋720÷18×x=720÷12×（30-x），
960＋40x＝1800-60x，
100x＝840，
x=8.4（天）。
兩廠合併後每月最多可生產衣服
960＋40×8.4＝1296（套）。
例2 某縣農機廠金工車間共有77個工人。已知每天每個工人平均可加工甲種部件5個，或乙種部件4個，或丙種部件3個。每3個甲種部件、1個乙種部件和9個丙種部件恰好配成一套。
問：分別安排多少人加工甲、乙、丙三種部件時，才能使生產出來的甲、乙、丙三種部件恰好都配套？
分析與解：如果採用直接假設，那麼就要用三個字母分別代替加工甲、乙、丙三種部件的人數，這已經超出了我們的知識範圍。由題目條件看出，每套成品中，甲、乙、丙三種部件的件數之比是3∶1∶9，因為是配套生產，所以生產出的甲、乙、丙三種部件的數量之比也應是3∶1∶9。
設每天加工乙種部件x個，則加工甲種部件3x個，丙種部件9x個。從而
加工甲、乙、丙三種部件應分別安排12人、5人和60人。
例3 有4輛汽車要派往五個地點運送貨物，右圖○中的數字分別表示五個地點完成任務需要的裝卸工人數，五個地點共需裝卸工20人。如果有些裝卸工可以跟車走，那麼應如何安排跟車人數及各點的裝卸工人數，使完成任務所用的裝卸工總人數最少？
分析與解：可用試探法。因為五個地點中需裝卸工最多的是5個人，所以如果每輛車跟5個工人，那麼每輛車到達任何乙個地點，都能正常進行裝卸。由此得到，跟車人數的試探範圍是1～5個人。
若每車跟車5人，則各點不用安排人，共需20人；
若每車跟車4人，則原來需5人的點還需各安排1人，共需18人；
若每車跟車3人，則原來需5人的點還需各安排2人，原來需4人的點還需各安排1人，共需17人；
同理可求出，每車跟車2人，共需18人；每車跟車1人，共需19人。
可見，安排每車跟車3人，原來需5人的兩個點各安排2人，原來需4人的點安排1人，這時所用的裝卸工總人數最少，需17人。
在例3中，我們採用試探法，逐一試算，比較選優。事實上，此類題目有更簡捷的解法。假設有m個地點n輛車（n≤m），m個地點需要的人數按從多到少排列為
a1≥a2≥a3≥…≥am，
則需要的最少總人數就是前n個數之和，即
a1＋a2＋…＋an。
這時每車的跟車人數可以是an＋1 至an 之間的任一數。具體到例3，5個點4輛車，5個點中需要人數最多的4個數之和，即5＋5＋4＋3=17（人）就是需要的最少總人數，因為a4=a5=3，所以每車跟車3人。若在例3中只有2輛車，其它條件不變，則最少需要 5＋5=10（人），因為a2=5，a3=4，所以每車跟車5人或4人。
當每車跟車5人時，所有點不再安排人；當每車跟車4人時，需要5人的兩個點各安排1人，其餘點不安排人。
注：如果車輛數大於地點數，即n＞m，則跟車人數是0，各點需要人數之和就是總共需要的最少人數。
例4 有17根11.1公尺長的鋼管，要截成1.0公尺和0.7公尺的甲、乙兩種長度的管子，要求截成的甲、乙兩種管子的數量一樣多。問：最多能截出甲、乙兩種管子各多少根？
分析與解：要想盡量多地截出甲、乙兩種管子，殘料應當盡量少。一根鋼管全部截成1.
0公尺的，餘下0.1公尺，全部截成0.7公尺的，餘下0.
6公尺。如果這樣截，再要求甲、乙管數量相等，那麼殘料較多。
怎樣才能減少殘料，甚至無殘料呢？我們可以將1.0公尺的和0.7公尺的在一根鋼管上搭配著截，所得殘料長度（單位：公尺）見下表：
由上表看出，方法3和方法10沒有殘料，如果能把這兩種方法配合起來，使截出的甲、乙兩種管子數量相等，那麼就是殘料最少的下料方案了。
設按方法3截x根鋼管，按方法 10截 y根鋼管。這樣共截得甲管（9x＋2y）根，乙管（3x＋13y）根。由甲、乙管數量相等，得到
9x＋2y＝3x＋13y，
9x-3x＝13y-2y，
6x=11y。
由此得到x∶y= 11∶6。用方法3截11根鋼管，用方法10截6根鋼管是符合題意的截法，共可截得甲、乙管各
9×11＋2×6=111（根），
或3×11＋13×6=111（根）。
例5 給甲、乙二人分配a，b兩項工作，他們完成這兩項工作所需要的時間如下表：
怎樣分配工作才能使完成這兩項工作所需的總時間最少？
分析與解：因為不同的人要做不同的工作，所以上表中不同行、不同列的兩數之和對應一種方案，共兩種：
（1）甲做 a、乙做 b，需要 7＋6=13（時）；
（2）甲做 b、乙做 a，需要 4＋8=12（時）。
顯然後一種方案優於前一種方案。
為了能夠處理更複雜的問題，我們將上例的數量關係盡量簡化。
如果把表中第一行的兩數都減去該行的最小數7，變成0和1，那麼上面（1）（2）各式也各減少7，不影響它們之間的大小關係，即不影響最優方案的確定。
同理，第二行都減去該行的最小數4，變成0和2，也不影響最優方案的確定。
經上述變換後，原表變成左下表：
此時，再將第二列都減去該列的最小數1，變成0和1，同樣不影響最優方案的確定，原表變為右上表。
不同行、不同列的兩個數之和代表一種方案，因為
0＋0＜0+1，
所以最優方案為乙做a、甲做b。上面的化簡過程可表示為：
總結上面的方法：對於n個人n項工作的合理分配問題：
（1）先將各行都減去該行中最小的數；
（2）再將各列都減去該列中最小的數；
（3）最後選擇不在同一行，也不在同一列的n個0即可。
在實施上述變換後，如果仍選不出n個不同行也不同列的0，因為我們的目的是選取一組不同行、不同列的n個數，使這n個數之和盡量小，既然得不到n個0，可用表中最小的數代替0（見例6）。
例6 給甲、乙、丙三人分配a，b，c三項工作，他們完成這三項工作的時間如下表：
完成這三項工作所需總時間最少是多少？
分析與解：
因為沒有三個不同行也不同列的0，我們用右下角的1代替0，此時，○內的三個數就是我們要找的最佳方案，即甲做b、乙做a、丙做c。所需總時間為
9＋7＋9=25（時）。
練習28
1.某種健身球由乙個黑球和乙個白球組成一套。已知兩個車間都生產這種
現在兩個車間聯合起來生產，每月最多能生產多少套健身球？
2.某車間有銑床5臺、車床3臺、自動工具機1臺，生產一種由甲、乙兩種零件各 1個組成的產品。每台銑床每天生產甲零件10個，或者生產乙零件20個；每台車床每天生產甲零件20個，或者生產乙零件30個；每台自動工具機每天生產甲零件30個，或者生產乙零件80個。
這些機器每天最多可生產多少套產品？
3.車過河交渡費3元，馬過河交渡費2元，人過河交渡費1元。某天過河的車、馬數目的比為2∶9，馬、人數目的比為3∶7，共收得渡費945元。
問：這天渡河的車、馬、人的數目各多少？
4.有4輛汽車要派往七個地點運送貨物，右圖中的數字分別表示這七個地點完成任務需要的裝卸工人數。如果裝卸工可以跟車，那麼最少要安排多少名裝卸工才能完成任務？
5.有一批長4.3公尺的條形鋼材，要截成0.7公尺和0.4公尺的甲、乙兩種毛坯，要求截出的甲、乙兩種毛坯數量相同。如何下料才能使殘料最少？
6.用10公尺長的鋼筋做原材料，擷取3公尺和4公尺長的鋼筋各100根，至少要用多少根原材料？
7.給甲、乙、丙分配a，b，c三項工作，他們完成這三項工作的時間如下表。怎樣分配工作才能使完成這三項工作所需總時間最少？最少用多少時間？
運籌學介紹
運籌學 operation research or operation research原意是操作研究 作業研究 運用研究 作戰研究，譯作運籌學，是借用了 史記 運籌策於帷幄之中，決勝於千里之外 一語中 運籌 二字，既顯示其軍事的起源，也表明它在我國已 早有萌芽。運籌學作為一門現代科學，是在第二次世...
運籌學基礎
填空題一1決策過程的第一步即是觀察問題所處的環境，一般而言，問題域所處的環境有內部環境和外部環境兩方面。2簡單移動平均法的計算公式為而加權移動平均的計算公式為 3悲觀主義遠側也稱最大最小原則，樂觀主義原則也稱最大最大原則。4安全庫存量也可稱為保險庫存量，是為了預防缺貨而儲存的額外庫存量。5網路圖中乙...
運籌學基礎
第一章導論 1.1概述 1.1.1運籌學與管理決策 運籌學是一門研究如何有效地組織和管理人機系統的科學。分析程式有兩種基本形式 定性的和定量的。定性分析的技巧是企業領導固有的，隨著經驗的積累而增強。運籌學的定義 運籌學利用計畫方法和有關多學科的要求，把複雜功能關係表示成數學模型，其目的是通過定量分析...