生產(chǎn)作業(yè)計(jì)劃編制中數(shù)學(xué)方法的運(yùn)用

1、.第四節(jié) 生產(chǎn)作業(yè)計(jì)劃編制中數(shù)學(xué)方法的運(yùn)用一、 約翰遜-貝爾曼法則：在編制生產(chǎn)作業(yè)計(jì)劃時(shí)，計(jì)劃人員應(yīng)該合理規(guī)定各種產(chǎn)品在設(shè)備上的加工次序，使總的加工經(jīng)歷時(shí)間為最短。約翰遜-貝爾曼法則就是一種在兩臺(tái)不同機(jī)床加工幾種不同工件時(shí)尋找最優(yōu)加工順序的方法。例：有A、B、C、D四種零件，都需先后經(jīng)車床和銑床加工，其零件加工工序時(shí)間定額如下 零件工序ABCD車床加工（小時(shí)）30161224銑床加工（小時(shí)）8201014求最優(yōu)加工順序使總的加工經(jīng)歷時(shí)間為最短。如果不進(jìn)行加工順序的合理安排，若只按A-B-C-D的順序進(jìn)行加工，則全部加工完四種零件需96小時(shí)見下圖1：如果運(yùn)用約翰遜-貝爾曼法則，合理安排零件加工順

2、序，我們就可以求出最短的加工時(shí)間，具體程序如下：（1） 從四種零件加工工序時(shí)間定額中，找出最小值，其最小值為8。（2） 選出具有最小值的零件為A零件，它屬于后道工序應(yīng)最后安排，如屬于前到工序，則應(yīng)最先安排加工。（3） 把已經(jīng)安排的A零件剔除，再?gòu)氖Ｏ碌膸?種零件中 找出最小值，是10，屬于C的后道工序，應(yīng)在A零件之前加工，依次類推，最終可找出全部零件的最優(yōu)加工順序即B-D C-A，T=90，按這種加工順序加工，四種零件全部加工工序時(shí)間為最短T=90。練習(xí)題：有A、B、C、D、E五種零件，都需先后經(jīng)車床和銑床加工，其零件加工工序時(shí)間定額如下 單位：小時(shí) 零件工序ABCDE車床加工（小時(shí)）6812

3、37銑床加工（小時(shí)）118534求最優(yōu)加工順序使總的加工經(jīng)歷時(shí)間為最短。答案：D、A、B、C、E或A、B、C、E 、D。T=40約翰遜-貝爾曼法則可被推廣使用：用于計(jì)算三臺(tái)不同機(jī)床加工幾種不同工件時(shí)尋找最優(yōu)加工順序。此時(shí)應(yīng)用此法則必須具備下列條件其一就可：（1）第一臺(tái)機(jī)床最小的加工工序時(shí)間不小于第二臺(tái)機(jī)床的最大加工工序時(shí)間；（2）第三臺(tái)機(jī)床最小的加工工序時(shí)間不小于第二臺(tái)機(jī)床的最大加工工序時(shí)間；當(dāng)三臺(tái)機(jī)床加工幾種不同工件時(shí)，只要符合上述兩個(gè)條件中的一個(gè)，可以把三臺(tái)機(jī)床的問(wèn)題簡(jiǎn)化成兩臺(tái)機(jī)床的問(wèn)題，再運(yùn)用約翰遜-貝爾曼法則尋求最優(yōu)加工順序。具體程序如下：（1） 將第一臺(tái)機(jī)床和第二臺(tái)機(jī)床的各個(gè)加工零件

4、的工序時(shí)間定額依次相加，車床+銑床。（虛擬第四個(gè)機(jī)床）（2） 將第二臺(tái)機(jī)床和第三臺(tái)機(jī)床的各個(gè)加工零件的工序時(shí)間定額依次相加，銑床+磨床。（虛擬第五個(gè)機(jī)床）（3） 將問(wèn)題看作第四個(gè)機(jī)床和第五個(gè)機(jī)床加工零件。（4） 運(yùn)用約翰遜-貝爾曼法則尋求最優(yōu)加工順序。例題：有A、B、C、D、E五種零件，都需先后經(jīng)車床、銑床和磨床加工，其零件加工工序時(shí)間定額如下 （單位：小時(shí)） 零件工序ABCDE車床加工1217201122銑床加工7910108磨床加工1174513求最優(yōu)加工順序使總的加工經(jīng)歷時(shí)間為最短。解：判斷條件：T1min>T2max (滿足其一即可)第一步：T(車床+銑床)=T（虛擬第四機(jī)床）

5、T(銑床+磨床)=T（虛擬第五機(jī)床） 零件工序ABCDE第四機(jī)床加工（小時(shí)）1926302130第五機(jī)床加工（小時(shí)）1816141521運(yùn)用約翰遜-貝爾曼法則：最優(yōu)加工順序是E 、A、B、D、C。練習(xí)題：有A、B、C、D、E、F六種零件，都需先后經(jīng)車床、銑床和磨床加工，其零件加工工序時(shí)間定額如下 單位：小時(shí) 零件工序ABCDEF車床加工1148965銑床加工786658磨床加工11149162115求最優(yōu)加工順序使總的加工經(jīng)歷時(shí)間為最短。解：判斷條件：T3min>T2max (滿足其一即可)第一步：T(車床+銑床)=T（虛擬第四機(jī)床） T(銑床+磨床)=T（虛擬第五機(jī)床） 零件工序ABC

6、DEF第四機(jī)床加工（小時(shí)）181214151113第五機(jī)床加工（小時(shí)）182215222623運(yùn)用約翰遜-貝爾曼法則最優(yōu)加工順序是E 、B、F 、C、 D、A。T=97圖：作業(yè)題：1.有A、B、C、D、E、F、G、H、I、J十種零件，都需先后經(jīng)車床和銑床加工，其零件加工工序時(shí)間定額如下 單位：小時(shí) 零件工序ABCDEFGHIJ車床加工（小時(shí)）14192422640204125銑床加工（小時(shí)）21083235183063528求最優(yōu)加工順序使總的加工經(jīng)歷時(shí)間為最短。解：利用約翰遜貝爾曼法：找最小時(shí)間最優(yōu)加工順序：IHEGDJFBCA最短時(shí)間：圖：2.有A、B、C、D、E、五種零件，都需先后經(jīng)車床

7、、銑床和磨床加工，其零件加工工序時(shí)間定額如下 單位：小時(shí) 零件工序ABCDE車床加工15108711銑床加工34652磨床加工47386求最優(yōu)加工順序使總的加工經(jīng)歷時(shí)間為最短。解：判斷條件：T1min>T2max (滿足其一即可)第一步：T(車床+銑床)=T（虛擬第四機(jī)床） T(銑床+磨床)=T（虛擬第五機(jī)床）如圖：二、 生產(chǎn)任務(wù)分配法：匈牙利數(shù)學(xué)家奎涅克提出又叫匈牙利法，在管理運(yùn)籌學(xué)上叫指派問(wèn)題。作業(yè)順序只是解決生產(chǎn)任務(wù)加工先后順序的優(yōu)化方案問(wèn)題。在日常生產(chǎn)中還有一類問(wèn)題，就是生產(chǎn)的經(jīng)濟(jì)效益并不取決于任務(wù)加工的先后順序，而取決于任務(wù)如何分配。生產(chǎn)任務(wù)分配方案不同，生產(chǎn)的經(jīng)濟(jì)效益就不同。

8、生產(chǎn)任務(wù)分配問(wèn)題簡(jiǎn)便的求解方法由匈牙利數(shù)學(xué)家奎涅克提出了匈牙利法。例題：有四項(xiàng)任務(wù)可分配給四個(gè)小組加工，但各小組完成各項(xiàng)任務(wù)所需的工時(shí)不同，見下表。應(yīng)如何分配任務(wù)，才能使總的加工時(shí)間最小，效率最高。 任務(wù)小組ABCD2105715414813141211415139解：寫成矩陣n*n：4*4（1）逐行縮減矩陣：各行元素均減本行的最小元素 任務(wù)小組ABCD0835110104231001195（2）列縮減，沒有零的列，各列元素均減本列的最小元素，使每列都有零元素。 任務(wù)小組ABCD082511094230001185（3）用最少的行劃線或列劃線把所有的零劃掉。若行劃線和列劃線總數(shù)等于任務(wù)數(shù)，則該

9、矩陣有最優(yōu)解；若若行劃線和列劃線總數(shù)不等于任務(wù)數(shù)，再進(jìn)行第四步。（4）未被劃到的各元素，減去其中最小的元素，在本例中最小的元素為2，而行和列劃線交叉處的元素要加上該最小的元素2， 任務(wù)小組ABCD080311072450001163（5） 回到第三步，用最少的行劃線或列劃線把所有的零劃掉；（3）（4）不循環(huán)進(jìn)行，直至行劃線和列劃線總數(shù)等于任務(wù)數(shù)；本例中n=4。（6） 從零最少的行或列開始依次分配任務(wù)。如果選擇一種分配方案是按零元素所占位置進(jìn)行的，則這種分配方案就相當(dāng)于完工總時(shí)數(shù)最少的方案。本例分配方案是（C），（B），（D），（A）最小總工時(shí)為5+4+11+4=24（小時(shí)）練習(xí)題：1：有四項(xiàng)任

10、務(wù)可分配給四個(gè)小組加工，但各小組完成各項(xiàng)任務(wù)所需的工時(shí)不同，見下表。應(yīng)如何分配任務(wù)，才能使總的加工時(shí)間最小，效率最高。 任務(wù)小組ABCD453668127131611101217108解： 任務(wù)小組ABCD1003006134104720 任務(wù)小組ABCD1004006223003610分配方案是（B），（A），（C），（D）最小總工時(shí)為5+6+11+8=30（小時(shí)）作業(yè)：有五只船要在五個(gè)泊位卸貨。五個(gè)泊位有不同的設(shè)施，因而卸貨的成本也不同，具體數(shù)據(jù)如下（單位：千英鎊）如何安排各只船到各個(gè)泊位卸貨才能使卸貨總成本最低。 泊位船1234518109362781129324644477527510

11、810311分配方案是1船（5泊位），2船（4泊位），3船（1泊位），4船（3泊位），5船（2泊位）；總成本：23千英鎊。例題：2 人員任務(wù)甲乙丙丁A32-21B2-20-C-110上表所示效益矩陣中的元素表示四個(gè)銷售人員完成三項(xiàng)任務(wù)所創(chuàng)造的利潤(rùn)，其中甲不勝任C工作，丁不勝任B工作；應(yīng)如何分配工作，使總的利潤(rùn)最大。（單位：萬(wàn)元）解：用最大值3減去矩陣中的每一元素 人員任務(wù)甲乙丙丁A0152B153-C-423 人員任務(wù)甲乙丙丁A0152B153-+C-+423 人員任務(wù)甲乙丙丁A0152B153-+C-+423D（虛擬任務(wù)）0000練習(xí)題：2，一位銷售經(jīng)理要分派六個(gè)銷售人員負(fù)責(zé)不同地區(qū)的銷售。

12、這些銷售人員有不同的關(guān)系和能力，他們的 期望月銷售額（萬(wàn)元）如下表所示。如何分派才能使月銷售收入最大。 地區(qū)人員1234561172441193328222223114272639332526303142943458222053919173032306313727233710答案：銷售人員1負(fù)責(zé)地區(qū)3，銷售人員2負(fù)責(zé)地區(qū)6，銷售人員3負(fù)責(zé)地區(qū)4，銷售人員4負(fù)責(zé)地區(qū)2，銷售人員5負(fù)責(zé)地區(qū)1，銷售人員6負(fù)責(zé)地區(qū)5，最大銷售收入：212（萬(wàn)元）例題：3. 分派甲、乙、丙、丁四人去完成五項(xiàng)任務(wù)，每人完成各項(xiàng)任務(wù)時(shí)間如下表所示。由于任務(wù)數(shù)多于人數(shù)，故規(guī)定其中一人可兼完成兩項(xiàng)任務(wù)，其余三人每人完成一項(xiàng)任務(wù)

13、。試確定總花費(fèi)時(shí)間為最少的指派方案。（單位：小時(shí)） 任務(wù)人員ABCDE甲2529314237乙3938262033丙3427284032丁2442362345解：假定第五人是戊，他完成各項(xiàng)任務(wù)時(shí)間取甲、乙、丙、丁四人中最小者，構(gòu)造新的矩陣 任務(wù)人員ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊2427262032分配方案是甲（B），乙（C、D），丙（E）?。ˋ）131（小時(shí)）例題：4.從甲、乙、丙、丁、戊五人中挑選四人去完成四項(xiàng)任務(wù)，每人完成各項(xiàng)任務(wù)時(shí)間如下表所示。規(guī)定每項(xiàng)任務(wù)只能由一個(gè)人單獨(dú)，完成，每個(gè)人最多承擔(dān)一項(xiàng)任務(wù)。又假定對(duì)甲必須保

14、證分配一項(xiàng)任務(wù)，丁因某種原因決定不同意承擔(dān)第四項(xiàng)任務(wù)。 在滿足上述條件下，如何分配工作，使完成四項(xiàng)任務(wù)總的花費(fèi)時(shí)間為最少。任務(wù) 人員甲乙丙丁戊1102315925101524315514715420151368解：先增加一種假想任務(wù)，再根據(jù)題中給的條件構(gòu)造新的矩陣任務(wù) 人員甲乙丙丁戊11023159251015243155147154201513+85+0000甲（2）、乙（3）、丙（1）、?。?）、戊（4）練習(xí)題3.已知下列五名運(yùn)動(dòng)員各種姿勢(shì)的游泳成績(jī)（各為50米）如下表所示，試問(wèn)如何從中選拔一個(gè)參加200米混合泳的接力隊(duì)，使預(yù)期的比賽成績(jī)?yōu)樽詈?。任?wù) 人員甲乙丙丁戊仰泳37.739.233

15、.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1答案：甲（自由泳）、乙（蝶泳）、丙（仰泳）、丁（蛙泳）、戊（-）126.2秒練習(xí)題4.五人翻譯五種外文的速度（印刷符號(hào)/小時(shí)）如下表所示，若規(guī)定每人專門負(fù)責(zé)一個(gè)語(yǔ)種的翻譯工作，那么（1）應(yīng)如何分派，使總的翻譯效率最高？（2）若甲不懂德文，乙不懂日文，其他數(shù)字不變，應(yīng)如何分派？ 語(yǔ)種人員英俄日德法甲900400600800500乙8005009001000600丙900700300500800丁400800600900500戊100050030

16、0600800答案：（1）4300印刷符號(hào)/小時(shí)，（2）4200印刷符號(hào)/小時(shí)練習(xí)題5.某航空公司經(jīng)營(yíng)A、B、C三個(gè)城市之間的航線，這些航線每天班機(jī)起飛與到達(dá)時(shí)間如下表所示，設(shè)飛機(jī)在機(jī)場(chǎng)停留的損失費(fèi)用大致與停留時(shí)間的 平方成正比，又每架飛機(jī)從降落到起飛至少需2小時(shí)準(zhǔn)備時(shí)間，試確定一個(gè)使停留費(fèi)用損失為最小的飛行方案。（飛機(jī)在一個(gè)機(jī)場(chǎng)停留一小時(shí)損失費(fèi)用為a元）航班號(hào)起飛城市起飛時(shí)間到達(dá)城市到達(dá)時(shí)間101A9：00B12：00102A10：00B13：00103A15：00B18：00104A20：00C24：00105A22：00C2：00（次日）106B4：00A7：00107B11：00A14

17、：00108B15：00A18：00109C7：00A11：00110C15：00A19：00111B13：00C18：00112B18：00C23：00113C15：00B20：00114C7：00B12：00答案A城市飛行方案 起飛到達(dá)1011021031041051064a9a64a169a225a107361a400a625a36a64a108225a256a441a4a16a109484a529a16a81a121a110196a225a400a625a9aB城市飛行方案 起飛到達(dá)106107108111112101256a529a9a625a36a102225a484a4a576a

18、25a103100a289a441a361a576a11364a225a361a289a484a114256a529a9a625a36aC城市飛行方案 起飛到達(dá)10911011311410449a225a225a49a10525a169a169a25a111169a441a441a169a11264a256a256a64a練習(xí)題6、某運(yùn)輸隊(duì)有5輛汽車，待駛往三個(gè)目的地送貨。一目的地的貨物只需一輛汽車運(yùn)送，其運(yùn)費(fèi)（元）如下表所示：類別 2 3 4 5A10 12 14 11 13B13 20 23 15 21C8 6 10 7 51、 試求最優(yōu)調(diào)運(yùn)方案；2、 若表中數(shù)字表示所得利潤(rùn)，則應(yīng)如何調(diào)運(yùn)；3、 若汽車2載不下A地所需貨物，車5載貨時(shí)爬不上通往B地必由之路上的山坡，則對(duì)1、2之最優(yōu)解各有何影響。答案1：29，2：