運籌學
運籌學主要研究分配工作問題。由於工作任務的性質不同，每個人的工作能力不同，因而完成這些任務所需的時間和花費的代價也不同。我們希望通過合理分配工作，使所用時間最少或花費代價最小。
運籌學主要研究分配工作問題。由於工作任務的性質不同，每個人的工作能力不同，因而完成這些任務所需的時間和花費的代價也不同。我們希望通過合理分配工作，使所用時間最少或花費代價最小。
例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（套）。
因為甲廠 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人。
設每天加工乙種部件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，各點需要人數之和就是總共需要的最少人數。
分析與解：可用試探法。因為五個地點中需裝卸工最多的是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（根）。
分析與解：要想儘量多地截出甲、乙兩種管子，殘料應當儘量少。一根鋼管全部截成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）。
（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）。
沒有留言:
發佈留言