工程碩士運籌學課件及重點

1工程碩士運籌學

內(nèi)蒙古工業(yè)大學管理學院

課程內(nèi)容緒論線性規(guī)劃基礎(chǔ)線性規(guī)劃的圖解法、用Excel解LP問題整數(shù)規(guī)劃運輸問題目標規(guī)劃圖論動態(tài)規(guī)劃網(wǎng)絡計劃技術(shù)23第0章緒論

IntroductionstoOperationsResearch

運籌學的實用價值4

ZARA（全球1500家門店）、P&G（15億）5運籌學學科特點1-

科學性它是在科學方法論的指導下通過一系列規(guī)范化步驟。6運籌學學科特點2-實踐性運籌學以實際問題為分析對象；分析結(jié)果必須用于指導實際系統(tǒng)的運行。適應性和魯棒性Robustness，原是統(tǒng)計學中的一個專門術(shù)語，20世紀70年代初開始在控制理論的研究中流行起來，用以表征控制系統(tǒng)對特性或參數(shù)擾動的不敏感性。即當應用問題的背景受到一定程度的干擾時，最優(yōu)解能夠繼續(xù)正常運行的程度。7運籌學學科特點3-系統(tǒng)性用系統(tǒng)的觀點來分析研究對象，通過協(xié)調(diào)各組成部分之間的關(guān)系和利害沖突，使整個系統(tǒng)達到最優(yōu)狀態(tài)。實際問題的多目標“天性”，各目標沒有統(tǒng)一的度量標準。8運籌學學科特點4-優(yōu)化方案強調(diào)是最優(yōu)的解決方案，而不是任意的一個可行方案，或者只是對現(xiàn)狀的“改進”方案；當研究問題從數(shù)學分析上存在多個或無窮最優(yōu)解時，不刻意去搜索出所有最優(yōu)解，而是只需找出其中一個最優(yōu)解；當研究問題過于復雜時，運籌學更傾向于搜索出一個“效率解”。9運籌學學科特點5-

綜合性運籌學研究是一種綜合性的研究，它涉及問題的方方面面，應用多學科的知識，因此，要由一個各方面的專家組成的小組來完成。運籌學求解問題的一般思路1.明確問題，收集數(shù)據(jù)邊界、目標量化、變量、參數(shù)、約束2.建立模型，數(shù)學模型：模型檢驗3.選取方法，進行求解：遺傳算法等4.驗證方案，實施方案5.方案程序化，模塊化6.方案實施，效果分析10運籌學求解問題的一般思路1112第1章線性規(guī)劃基礎(chǔ)(IntroductiontoLinearProgramming)目標1.常見線性規(guī)劃問題的數(shù)學建模思路2.建模的適用范圍3.“解”的概念4.圖解法5.EXCEL求解一般線性規(guī)劃問題（練習）1314線性規(guī)劃的定義在滿足一組線性約束條件（等式或不等式）的前提下，使得某一個線性目標函數(shù)取得極值（最大值或最小值）。這類問題的模型及其優(yōu)化求解技術(shù)，被統(tǒng)稱為線性規(guī)劃(LinearProgramming,LP)。Inmathematics,LPproblemsareoptimizationproblemsinwhichtheobjectivefunction

andtheconstraints

arealllinear.線性規(guī)劃數(shù)學模型線性規(guī)劃問題的一般模型15線性規(guī)劃數(shù)學模型模型特點1-所有表達式均為線性表達式2-目標為求目標函數(shù)Z的最大值(max)或最小值(min)3-約束條件為”≥/≤/=”，沒有”>/<”！4-通常要求決策變量取值非負1617應用問題示例(1)-生產(chǎn)計劃

F公司每周根據(jù)原材料M1和M2的采購數(shù)量來安排其產(chǎn)品A、B和C的生產(chǎn)計劃。問：這3種產(chǎn)品各應生產(chǎn)多少，能使F公司獲得最大的利潤？應用問題示例(2)-生產(chǎn)計劃A公司用M1,M2,M3和M4四種原材料，生產(chǎn)產(chǎn)品P1,P2和P3。這三種產(chǎn)品由這四種原材料混合而成（產(chǎn)品重量為四種原材料重量之和）。18應用問題示例(2)原材料M3和M4采購量超過市場供應總量的一半。采購預算費用為25萬元人民幣。問：根據(jù)產(chǎn)品的市場價格以及原材料價格，公司應如何采購以獲得最多的利潤？19應用問題示例(2)建模思路1--20應用問題示例(2)正確的建模方法--21應用問題示例(2)22應用問題示例(3)-財務計劃某集團公司未來6年年初的現(xiàn)金需求（萬元）如下所示。為此，公司決定在今年年底一次性劃撥一筆資金，未來6年不再劃撥。23應用問題示例(3)公司可以通過多種投資形式減少資金的需求：1-銀行一年期的定期存款，年利率為3%；2-國債（只能在第1年年初購買；國債的實際購買價格要高于其票面價格，且只能在到期日按票面價格收回本金）問：集團公司最少需要劃撥多少資金，并如何投資，才能滿足未來6年的現(xiàn)金需求？24應用問題示例(3)由于6年內(nèi)不再追加投資，因此6年內(nèi)的投資（銀行定期存款方式）必然不能超過當年現(xiàn)金需求的余額。并且，由于投資總能夠獲得更多的回報（103%），所以投資等于當年現(xiàn)金需求的余額！25應用問題示例(3)采用表格形式更加直觀展示出投資與回報。年末的收益可以作為下一年年初的投資。26應用問題示例(3)27應用問題示例(3)完整問題模型如下：28應用問題示例(4)-生產(chǎn)計劃N公司生產(chǎn)兩種產(chǎn)品P1和P2，這2種產(chǎn)品都是由組件C1,C2和C3各1件裝配而成。需求為1600件P1和1000件P2。共有100個正常工時和最多60個加班工時，每個加班工時將額外增加12元的運營成本。問：如何安排生產(chǎn)和外購，才是最經(jīng)濟？29應用問題示例(4)根據(jù)問題描述，可以定義自行生產(chǎn)和外購的組件數(shù)量為決策變量。并且，外購組件的數(shù)量與生產(chǎn)能力也有關(guān)，因此需要定義實際加班工時為決策變量，即：30應用問題示例(4)31應用問題示例(5)-運輸與分銷運輸與分銷問題問：如何安排物流路線，實現(xiàn)總運輸成本最小。32應用問題示例(5)定義決策變量為各條路線上的運輸量，各變量對應的路線如下所示。33應用問題示例(5)對于此類以圖形方式給出的物流問題，存在以下函數(shù)關(guān)系，即圖中每個節(jié)點，都必須滿足“輸入=輸出”。34應用問題示例(5)源頭節(jié)點“工廠1～3”，關(guān)系為“產(chǎn)量+運入量=運出量”。35應用問題示例(5)中間節(jié)點“分銷中心”，關(guān)系為“運入量=運出量”。36應用問題示例(5)終止節(jié)點“倉庫1～2”，關(guān)系為“運入量=運出量+需求量”。37應用問題示例(6)-套裁下料問題某建筑公司需要鋼管規(guī)格和數(shù)量分別為：3m的600根、4m的300根、5m的200根。如果只能選擇購入長度為11m的鋼管自行切割，M公司至少應采購多少根11m的鋼管？38應用問題示例(6)某建筑公司需要鋼管規(guī)格和數(shù)量分別為：3m的600根、4m的300根、5m的200根。如果只能選擇購入長度為11m的鋼管自行切割，M公司至少應采購多少根11m的鋼管？39應用問題示例(6)40應用問題示例(6)思考題：如果目標函數(shù)改為“如果購入這些長度為11m的鋼管自行切割，RE公司應如何切割廢料最少？”4142線性規(guī)劃模型的假設(shè)條件比例性假定：要求目標函數(shù)值、約束條件左端取值與決策變量的取值呈嚴格的比例關(guān)系。線性規(guī)劃模型的假設(shè)條件4344線性規(guī)劃問題的標準圖解法對于只包含2個變量的線性規(guī)劃問題，可以通過標準圖解法來求解。其解題步驟為：45標準圖解法示例1用標準圖解法求下面的線性規(guī)劃問題（例1-8）標準圖解法示例146標準圖解法示例2應用標準圖解法求解線性規(guī)劃問題（例1-9）47標準圖解法示例24849線性規(guī)劃問題的重要推論1-如果線性規(guī)劃問題的可行域非空且有界，那么線性規(guī)劃問題一定有最優(yōu)解；2-如果線性規(guī)劃問題的可行域無界，那么該問題可能有無界解；3-如果線性規(guī)劃問題的最優(yōu)解在可行域的兩個頂點上同時得到，那么這兩個頂點連線上的所有點都是最優(yōu)解（有無窮多最優(yōu)解）；4-如果線性規(guī)劃問題的可行域為空，意味著該線性規(guī)劃問題無可行解。50簡化的圖解法對于可行域為封閉凸多邊形的兩變量線性規(guī)劃問題，可以采用簡化的圖解法求解：只需要窮舉出可行域的所有頂點，計算每一個頂點的目標函數(shù)值，就可以找出最優(yōu)解。簡化的圖解法示例1線性規(guī)劃問題（例1-8）5152Excel求解線性規(guī)劃問題“規(guī)劃求解”工具主界面Excel求解LP問題示例1線性規(guī)劃問題（例1-8）53練習題-圖解以下線性規(guī)劃問題5455某手工作坊生產(chǎn)的竹制座椅中需要用到3種規(guī)格楠竹片，每張椅子需要長度為60cm、40cm

和30cm的楠竹片2、6和2片。可以在市場上采購這些規(guī)格的現(xiàn)貨，也可以將作坊倉庫中長度

為110cm的楠竹片切割成所需的規(guī)格，但每切割1次會發(fā)生1cm的長度損耗。

問：如果要制作100張竹制座椅，該作坊的倉庫中至少要有多少條長度為110cm的楠竹片，

才不用去市場上采購？試建立本問題的線性規(guī)劃模型。

56575859第2章整數(shù)規(guī)劃(IntegerLinearProgramming)基本概念線性規(guī)劃模型中增加了決策變量的整數(shù)約束，這類數(shù)學規(guī)劃問題被稱為整數(shù)規(guī)劃(IntegerLinearProgramming,ILP)問題。整數(shù)規(guī)劃模型雖然只是在線性規(guī)劃模型中增加了決策變量的整數(shù)約束，但是其求解過程卻變得非常復雜。（簡單的四舍五入？？？）車輛調(diào)度、人員安排、產(chǎn)品產(chǎn)量60基本概念根據(jù)全部還是部分決策變量必須滿足整數(shù)約束，整數(shù)規(guī)劃問題可分為兩類：純整數(shù)規(guī)劃（PureIntegerProgramming,PIP）混合整數(shù)規(guī)劃（MixedIntegerProgramming,MIP）根據(jù)整數(shù)變量取值的范圍，整數(shù)規(guī)劃問題還可分為：一般整數(shù)規(guī)劃-整數(shù)變量的取值可以是任意非負整數(shù)0-1整數(shù)規(guī)劃（BinaryIntegerProgramming,BIP）-要求決策變量只能取值0或者161基本概念62一般整數(shù)規(guī)劃問題的數(shù)學模型基本概念630-1整數(shù)規(guī)劃問題的數(shù)學模型應用問題建模設(shè)施布點問題某市在其5個規(guī)劃片區(qū)規(guī)劃消防站設(shè)點，要求任意一個片區(qū)發(fā)生火警時，本片區(qū)或來自其它片區(qū)的消防車可以在15分鐘內(nèi)趕到。雖然在各片區(qū)各設(shè)一個消防站可以解決此問題，但為提高資源利用率，市政府提出消防站數(shù)量應盡可能少。64應用問題建模背包問題（0-1）某家庭計劃自駕野外露營，出發(fā)前需考慮攜帶的物品，各物品的壓縮體積及重要程度如表所示。由于其自駕車最大容納的物品體積為650升，不可能所有物品都能裝入車中。問：應選擇哪些物品出行？65應用問題建模指派問題有5項任務需要5個員工獨立完成，由于能力差異，不同員工完成同一任務的執(zhí)行成本不同。下表給出了員工i完成任務j的執(zhí)行成本cij。問：如何指派任務可以最經(jīng)濟地完成各項任務。66應用問題建模將n項任務分配給n個人，約定每人只能完成一項工作，每項工作也只能由一個人來完成，但由于每個人能力各不相同，完成各項工作的收益和成本不同。根據(jù)不同的問題背景，可要求得到總利潤最大或總成本最小的指派方案。這類問題在運籌學中被稱為一種專門的問題：指派問題(AssignmentProblem)。67應用問題建模68定義0-1變量xij(i,j=1,…,n)表示第i個人是否被指派完成第j項任務（0代表不指派，1代表指派），則指派問題的數(shù)學模型為：應用問題建模含有互斥項目的計劃1.如果攜帶食物，就必須同時攜帶野外廚具和洗漱用品；2.通信設(shè)備和應急醫(yī)療用品至少要攜帶1件；3.帳篷和防曬防雨最多只能選擇1項；4.野外廚具、攝影器材和通信設(shè)備最多選2項。69應用問題建模含有互斥約束條件的計劃某公司用兩種原料E1和E2生產(chǎn)A、B兩種產(chǎn)品，生產(chǎn)過程均需經(jīng)過甲、乙兩道工序。甲、乙兩道工序又各可以采取2種生產(chǎn)工藝。甲工序可以混合使用甲1和甲2兩種工藝，而乙工序只能在乙1和乙2中選擇其中一種工藝。問：該公司應如何安排生產(chǎn)可使利潤最大？70在建模中對互斥的約束處理時，可以引入Mi來實現(xiàn)使某個約束條件有效或者冗余，其中Mi為任意大的正數(shù)。71固定成本問題某工廠用兩條生產(chǎn)線??1和??2生產(chǎn)兩種產(chǎn)品A和B。這兩條生產(chǎn)線每個月的額定工時分別為600和800小時，生產(chǎn)線??1的生產(chǎn)率為產(chǎn)品A60件/小時或產(chǎn)品B45件/小時，生產(chǎn)線??2的生產(chǎn)率為產(chǎn)品A35件/小時或產(chǎn)品B40件/小時；產(chǎn)品A和B的單位售價分別為12元/件和16元/件，生產(chǎn)產(chǎn)品A和B的固定成本分別為60000元和80000元。

問：應如何安排生產(chǎn)可實現(xiàn)利潤最大化？試建立本問題的混合整數(shù)規(guī)劃模721）決策變量的定義：因為含有固定成本的問題，所以某產(chǎn)品的產(chǎn)量X和是否生產(chǎn)該產(chǎn)品的決策Y必須分別定義，而且它們必須是聯(lián)動的，即如果某產(chǎn)品的產(chǎn)量X大于0，那么Y必須為1；而產(chǎn)品的產(chǎn)量X為0時，Y必須為0.否則，就有可能出現(xiàn)未生產(chǎn)產(chǎn)品X卻減去了固定成本的問題，或者生產(chǎn)了卻未減去固定成本的問題。這類問題必須引入任意大的正數(shù)M。732）正數(shù)M的引入X≤M?Y其中M為任意大的正數(shù)，即，只要Y=0，則X必須為0，Y=1時，X可以取任意正整數(shù)。74所以，上題的決策變量定義如下：7576分枝定界法分枝定界技術(shù)是一種求解優(yōu)化問題的通用思想，其邏輯思路是：把原始問題分解成若干個足夠小的可以直接求解的子問題，此為分枝過程(Branching)；對于每個子集及其對應的子問題，考察其最優(yōu)解是否足夠好―是否可能包含原始問題的最優(yōu)解，此為定界過程(Bounding)；結(jié)束某些子問題的分枝過程，并根據(jù)定界過程的結(jié)果，放棄那些不可能包含原始問題最優(yōu)解的子集及子問題，此為剪枝過程(Fathoming)。77割平面法78習題1某大型社區(qū)臨街的中式快餐店每天的營業(yè)時間為8:00到24:00，根據(jù)社區(qū)居民對早餐、中餐、晚餐和夜宵的需求不同，一天中不同時段對服務員的需求如圖所示。

79該店的員工分為兩類。第一類是正式員工，分別在3個8小時時段上班：8:00-16:00、12:00-

20:00，以及16:00-

24:00，其工作時薪為14元/小時，且規(guī)定各時段正式員工數(shù)量不能少于3人；第二類是鐘點工，可在8:00到24:00的任意時間工作，其工作時薪為12元/小時。

問：應如何雇用正式員工和鐘點工，可在人力資源成本最小的基礎(chǔ)上滿足需求？試建立本問題的整數(shù)規(guī)劃模型。

808182習題2某公司計劃在東、西、南三個地區(qū)建立銷售網(wǎng)點，總共有7個備選地點????(??=1,···,7)可供選擇?，F(xiàn)要求所設(shè)立的銷售網(wǎng)點必須滿足以下條件：

?在東部地區(qū)，??1,??2,??3三個備選地點中至多選擇兩個地點設(shè)立銷售網(wǎng)點；

?在西部地區(qū)，??4,??5兩個備選地點中至少選擇一個地點設(shè)立銷售網(wǎng)點；

?在南部地區(qū)，??6,??7兩個備選地點只能選一個設(shè)立銷售網(wǎng)點；

?出于市場環(huán)境的考慮，如果方案中選擇了??2地點，必須選擇在??5同時設(shè)立銷售網(wǎng)點。若在備選地點????設(shè)立銷售網(wǎng)點需要投資????萬元，每年可獲得利潤????萬元。問：如果總投資預算為B萬元，在哪些備選地點設(shè)立網(wǎng)點可獲得最多的利潤？試建立本問題的數(shù)學模型。

8384習題3某短途航空公司有10條聯(lián)飛路線，可經(jīng)停9個城市，下表給出了這10條飛行路線經(jīng)停的城市和飛行總小時數(shù)（單位：小時）。

試從這10條路線中選擇3條路線，既能夠滿足飛行總時間最少的要求，又能夠經(jīng)停9個城市

至少1次。給出本問題的0-1整數(shù)規(guī)劃模型。

8586則其目標函數(shù)為：Min（Z）=？8788習題4某小提琴手作坊根據(jù)顧客提出的定制需求生產(chǎn)小提琴，價格和固定成本因定制需求而異。由于作坊的熟練技師有限(12人)，該手工作坊只能挑選部分訂單，甚至只能部分完成訂單所要求的數(shù)量。目前，作坊收到來自3家交響樂隊的小提琴訂單，下表給出了與此訂單相關(guān)的制作成本和價格（單位：元）。問：各訂單各應接受多少臺，可獲得最多的利潤？試建立本問題的整數(shù)規(guī)劃模型。

899091習題5某工廠生產(chǎn)A和B兩種型號的產(chǎn)品，其生產(chǎn)過程須經(jīng)過甲、乙、丙三個流水線車間加工，其中，乙車間有兩條加工效率不同的流水線乙1和乙2。已知乙車間的兩條流水線只能任選一條使用，問：如何安排生產(chǎn)可獲得最大的利潤。建立本問題的整數(shù)規(guī)劃模型。929394第5章運輸問題(TransportationProblems)基本概念將某種物資從若干個產(chǎn)地運輸?shù)搅硗馊舾蓚€銷地，要求總運費最小的問題，這一類問題及其衍生問題統(tǒng)稱為運輸問題(TransportationProblem)。95引例FreshFruit公司旗下有3個蘋果種植基地，預計年產(chǎn)量分別為75、125和100噸，近期該公司與4個不同地區(qū)的客戶簽訂了今年的蘋果供應合同，其銷量分別80、65、70和85噸。由于交通條件差異，從3個基地到4個客戶所在地的單位運費不同，其運價表如表所示。96運輸問題的數(shù)學模型97運輸問題通常為：從m個產(chǎn)地向n個銷地運輸某種物資，產(chǎn)地i到銷地j的單位運費是cij（呈比例關(guān)系），產(chǎn)地i的產(chǎn)量是ai，銷地j的銷量是bj，要求找到使得總運費最小的運輸方案。當問題滿足總產(chǎn)量與總銷量相等，這類問題稱為標準運輸問題，或者產(chǎn)銷平衡運輸問題。運輸問題的數(shù)學模型標準運輸問題的數(shù)學模型為：98標準運輸問題的表上作業(yè)法作為一種特殊的線性規(guī)劃問題，標準運輸問題模型并不包含天然的基變量和初始基本可行解，求解時需要在每個等式中引入人工變量，計算較為煩瑣。對于標準運輸問題，在某種特殊形式的表格上來應用單純形法，可使求解過程大大簡化，這種方法叫作運輸問題的表上作業(yè)法。需特別強調(diào)的是，用表上作業(yè)法求解運輸問題，產(chǎn)銷平衡是一個基本前提。99標準運輸問題的表上作業(yè)法解題步驟：1-初始化給出初始基本可行方案；2-迭代第1步基本可行方案的最優(yōu)判定，判斷當前基本可行方案是否最優(yōu)。如果不是，進入第2步；第2步基本可行方案的改進，然后返回第1步；100標準運輸問題的表上作業(yè)法運輸問題作業(yè)表/產(chǎn)銷平衡表101標準運輸問題的表上作業(yè)法102西北角法從作業(yè)表的西北角往東南角逐步填寫運輸量。西北角法示例1103西北角法示例1104標準運輸問題的表上作業(yè)法105最小元素法按照單位運費由低到高的次序來選擇每次迭代中指派運輸量的單元格。最小元素法示例1106最小元素法示例1107產(chǎn)銷不平衡的運輸問題示例108轉(zhuǎn)運問題(1)確定標準運輸問題中的產(chǎn)地和銷地：轉(zhuǎn)運點既是產(chǎn)地，又是銷地。也就是說，標準運輸問題中的產(chǎn)地為原始轉(zhuǎn)運問題中的產(chǎn)地和所有的轉(zhuǎn)運點，銷地為原始問題中的銷地和所有的轉(zhuǎn)運點。(2)確定各產(chǎn)地的產(chǎn)量和銷地的銷量：將原始轉(zhuǎn)運問題中產(chǎn)地的產(chǎn)量和銷地的銷量直接移植入標準運輸問題；轉(zhuǎn)運點的產(chǎn)量和銷量相同，數(shù)值都為經(jīng)過該轉(zhuǎn)運點的最大可能轉(zhuǎn)運量。109轉(zhuǎn)運問題(3)確定各產(chǎn)地與銷地之間的單位運輸費用：將原始問題中已知的兩地之間的單位運輸費用移植入標準運輸問題；各轉(zhuǎn)運點到其自身的單位運輸費用為0；對于原始轉(zhuǎn)運問題中不存在的運輸路線，單位運費為無窮大，用任意大的正數(shù)??表示。110轉(zhuǎn)運問題示例1111其它問題一些應用問題雖然與物資運輸、分銷沒有任何聯(lián)系，但是由于其問題背景與運輸問題有相似的形式，亦可將其抽象并建模為廣義的產(chǎn)銷平衡運輸問題，從而采用運輸問題的表上作業(yè)法進行求解。112習題1求解如下運輸問題：113習題2求解如下運輸問題：114習題3某水產(chǎn)品銷售公司每天從3個水產(chǎn)品養(yǎng)殖廠采購新鮮產(chǎn)品運往4個批發(fā)市場。3個養(yǎng)殖廠每天提供的水產(chǎn)品數(shù)量為2500、3000、4500公斤，4個批發(fā)市場每日的需求量分別為2000、2500、3000、2500公斤。根據(jù)表5所示3個養(yǎng)殖廠的采購成本價和4個批發(fā)市場的價格（單位：元/千克），公司應如何安排運輸可使得總利潤最大？

115習題4有3個牧業(yè)基地向4個城市提供鮮奶，4個城市每日的鮮奶需求量為16、30、24和30千升，3個基地的每日鮮奶供應量分別為30、40和50千升。已知運送每千升鮮奶的費用如表所示（單位：千元）。試確定最經(jīng)濟的鮮奶運輸方案，且求出最小總運費。116習題5假定習題3中城市A每天最低需求和總需求量分別為14和24千升，城市C每天最低需求和總需求量分別為25和40千升，其它城市需求量無變化，在最低需求必須滿足的前提下，求解該問題，且求出最小總運費。

117習題6某干果公司從3個水果生產(chǎn)基地進貨，在4個加工廠將水果加工成干果。假定3個水果基地的產(chǎn)量、4個加工廠的需求量，以及單位水果的運價如表所示。在最低需求必須滿足的前提下，求總成本最低的運輸方案。

118習題7已知2個供應方A1、A2以及3個需求方B1、B2、B3的運輸問題的運價表如表所示。由于違約成本比較低，供應方A1、A2在運輸成本較高的情景下可選擇違約；同樣，由于缺貨損失比較低，需求方B1、B2、B3也可以在運輸成本較低的情景下選擇違約。問：根據(jù)表所示的缺貨成本、違約成本，以及運輸成本，如何安排運輸可使得總運營成本最低？

119第6章目標規(guī)劃(GoalProgramming)120目標規(guī)劃的提出用線性規(guī)劃來解決實際問題時，除了要滿足比例性、可加性、可分性和確定性四個假設(shè)之外，通常還假設(shè)實際問題的求解目標是單一的，而且其約束條件是可以嚴格滿足的。

線性規(guī)劃的弊端：現(xiàn)實決策問題通常都有多重的、可能相互沖突的目標其約束條件也不一定必須全部嚴格滿足

目標規(guī)劃(GoalProgramming)的提出，正是為了消除或至少部分填補這種方法與實際應用之間的空白。1216.1.1引例-目標規(guī)劃的數(shù)學模型在例1-1中，F(xiàn)公司每周需要根據(jù)下表確定產(chǎn)品A、B、C的產(chǎn)量，以獲取最大的利潤其線性規(guī)劃數(shù)學模型為：本問題的求解目標是唯一的———利潤最大化。1226.1.1引例但現(xiàn)實問題往往會有多個目標，比如把上面這個例子變成：例6-1在滿足例1-1資源約束的前提下，按優(yōu)先次序滿足以下的目標：利潤最好不少于200元；產(chǎn)品B為產(chǎn)品A的補充件，其產(chǎn)量最好低于產(chǎn)品A的一半；產(chǎn)品C為戰(zhàn)略性產(chǎn)品，其產(chǎn)量最好不低于5件；原材料M2最好全部使用完且不超量；原材料M1比較稀缺，最好至少有10千克的剩余。問：F公司應如何安排生產(chǎn)計劃，能夠盡可能達成以上的經(jīng)營目標？1236.1.1引例問題的線性規(guī)劃模型變?yōu)橐韵虏坏仁浇M符合上述不等式組的解，就是本問題的解。經(jīng)過計算，該不等式組無解。而在實際背景下，該問題顯然是有解的。124

資源約束五個目標6.1.1引例實際上，本問題前3個優(yōu)先級的目標是可以完全達成的，第(4)、(5)個目標雖然無法完全達成，但是是允許妥協(xié)的———只需要在前幾個目標達成的基礎(chǔ)上，盡可能滿足即可。問題出在建模的方式上以上模型將5個原本有優(yōu)先次序的、允許妥協(xié)的目標變成了必須同時嚴格滿足的目標。因此，一個在現(xiàn)實中有解的多目標決策問題，以線性規(guī)劃的思路建?？赡芫蜔o解了。目標規(guī)劃的提出，正是針對這類線性規(guī)劃無法解決的實際問題。1256.1.2目標規(guī)劃的基本概念目標規(guī)劃問題是這樣一類問題：在滿足剛性約束的前提下，求解一組決策變量的取值，使得不同優(yōu)先級別目標的實現(xiàn)值與目標值之間的偏差盡可能小的線性規(guī)劃問題。概念實現(xiàn)值與目標值、偏差變量剛性約束與柔性約束達成函數(shù)優(yōu)先級與權(quán)重1266.1.2目標規(guī)劃的基本概念1、目標值、實現(xiàn)值與偏差變量在目標規(guī)劃中，描述各個目標的數(shù)學表達式稱為目標表達式。對某個目標表達式期望的取值水平（不論是不超過、不少于還是等于），稱為該目標的目標值。當決策變量xj

的取值確定以后，某個目標表達式的實際取值稱為該目標的實現(xiàn)值，又稱為決策值。例如，例6-1中第(1)個目標的目標表達式為5x1+4x2+2x3，對此目標的期望值為200，則其目標值為200；第(2)個目標的目標表達式可寫為x1

?2x2，此時目標值為0。第(3)個目標的表達式x3，目標值為5。1276.1.2目標規(guī)劃的基本概念實現(xiàn)值與目標值之間可能會存在差異，這種差異的大小在決策（確定決策變量取值）前是無法預知的，是隨決策變量變化而變化的，因此稱實現(xiàn)值與目標值之間的差異為偏差變量。因建模的需要以及適應線性規(guī)劃中對變量的非負要求，偏差變量又分為正偏差量，代表實現(xiàn)值超過目標值的偏差，記為d+負偏差量，代表實現(xiàn)值未達到目標值的偏差，記為d-滿足非負：滿足互斥：1286.1.2目標規(guī)劃的基本概念例如，例6-1中，如果某個滿足了約束條件式(6-1)的決策為x1=25;x2=13;x3=5;則第(1)個目標，其實現(xiàn)值為5x1+4x2+2x3=187，未達到目標值200，如果用

表示該目標的正負偏差量，有對于第(2)個目標，其實現(xiàn)值為x1

?2x2=?1，目標值為0，有同理，對于第(3)個目標，因為實現(xiàn)值等于目標值5，有1296.1.2目標規(guī)劃的基本概念2、剛性約束、柔性約束與達成函數(shù)在目標規(guī)劃中，必須嚴格滿足的約束條件稱為剛性約束或硬目標。剛性約束中不含偏差變量。目標規(guī)劃中，不滿足剛性約束的解為非可行解。與剛性約束相對，目標規(guī)劃中允許某些目標的決策值與目標值存在偏差，這類目標稱為軟目標，其所對應的約束條件稱為柔性約束。此即柔性約束的表達式。1306.1.2目標規(guī)劃的基本概念例如，對例6-1中的第(1)個目標，其柔性約束為：同理，對于第(2)、(3)個目標，其柔性約束分別為：1316.1.2目標規(guī)劃的基本概念對每個目標，決策者會表達出對決策值與目標值之間關(guān)系的期望———超過、不超過或恰好等于。但僅從柔性約束本身，無法判斷決策者究竟是期望達到哪一種。在此引入一個稱為達成函數(shù)的表達式來表示決策者的期望。由目標規(guī)劃問題的定義可知，對于任一目標，決策者的期望是使決策值與目標值的偏差盡可能小，因此達成函數(shù)是僅含偏差變量，且目標是使偏差變量取最小值的目標函數(shù)1326.1.2目標規(guī)劃的基本概念對于單一的目標，達成函數(shù)依決策者的期望分三種情況：超過目標值，則達成函數(shù)為

。可理解為希望有正偏差，不希望有負偏差。不超過目標值，則達成函數(shù)為

?？衫斫鉃橄Ｍ胸撈?，不希望有正偏差。恰好等于目標值，則有

，亦即正、負偏差量都要盡可能地小。結(jié)合柔性約束與達成函數(shù)，就可以寫出每個目標的目標表達式。1336.1.2目標規(guī)劃的基本概念例如，第(1)個目標的達成函數(shù)為利潤最好不少于200：第(2)個目標的表達式為產(chǎn)品B產(chǎn)量最好低于產(chǎn)品A一半：第(4)個目標的表達式為原材料M2最好全部使用完且不超量：1346.1.2目標規(guī)劃的基本概念3、優(yōu)先級與權(quán)重以上的分析只針對單一目標，當問題中有多個主次不同的目標，且各個目標之間可能存在矛盾時，就需要以某種方式將各個目標的達成函數(shù)合并成一個單一的達成函數(shù)。目標規(guī)劃通過引入優(yōu)先級來為不同目標的達成函數(shù)加權(quán)。具體為，在合并達成函數(shù)時，將目標按重要程度進行優(yōu)先級排序，第1優(yōu)先級目標的達成函數(shù)乘以優(yōu)先因子P1，第2優(yōu)先級目標的達成函數(shù)乘以P2，依次類推，第L優(yōu)先級目標的達成函數(shù)乘以優(yōu)先因子PL，且規(guī)定由此保證優(yōu)先實現(xiàn)P1

級的目標，在此基礎(chǔ)上再考慮P2

級目標的實現(xiàn)，然后依次類推。1356.1.2目標規(guī)劃的基本概念某些實際問題中同一優(yōu)先級下可能有多個目標，這些目標的重要程度還可以有差異，只不過這種差異不是數(shù)量級上的，目標規(guī)劃用權(quán)重來區(qū)分這種差異。在建模時，可以根據(jù)決策者的需求，對該優(yōu)先級Pl

下某個目標k的達成函數(shù)以權(quán)系數(shù)wlk

加權(quán)后再相加。注意：優(yōu)先級的劃分，以及同一優(yōu)先級下多個目標的權(quán)重的設(shè)定，沒有普適性的規(guī)則，而應根據(jù)決策者的需求和偏好來確定。------------主觀性在不同的問題背景或決策者偏好下，同一個目標的優(yōu)先級或其在某個優(yōu)先級中的權(quán)系數(shù)都可能有不同的設(shè)定。1366.1.2目標規(guī)劃的基本概念根據(jù)上述概念，可以寫出例6-1的目標規(guī)劃模型。整個問題的達成函數(shù)可以寫為上式所示的“和”的形式，也可以寫為“集合”的形式：1376.1.3目標規(guī)劃模型及建模步驟目標規(guī)劃問題的數(shù)學模型的一般形式為：自上而下分別是達成函數(shù)、剛性約束、柔性約束和所有變量的非負約束138

6.1.3目標規(guī)劃模型及建模步驟建模步驟：第1步設(shè)定問題的決策變量；第2步列出問題的剛性約束；第3步根據(jù)決策者的需求和偏好，設(shè)定各個目標的優(yōu)先級，當有多個目標同屬于一個優(yōu)先級下時，還需根據(jù)約定設(shè)定各個目標的權(quán)重；然后，寫出各個目標的柔性約束和各優(yōu)先級的達成函數(shù)；第4步用優(yōu)先因子和權(quán)系數(shù)為各個目標的達成函數(shù)加權(quán)，寫出整個問題的達成函數(shù)。第5步寫出決策變量與偏差變量的非負約束。139例6-2在例6-1中，假定不要求嚴格滿足資源約束，且各優(yōu)先級的目標依次如下：利潤最好不少于180元；產(chǎn)品A的產(chǎn)量最好不多于25件、產(chǎn)品B的產(chǎn)量最好不少于15件、產(chǎn)品C的產(chǎn)量最好不少于5件，且根據(jù)單位產(chǎn)品的利潤確定權(quán)系數(shù)；原材料M2最好全部使用完，不足時可購入，原材料M1比較稀缺，最好至少有10千克的剩余。問：F公司應如何安排生產(chǎn)計劃，能夠盡可能達成以上的經(jīng)營目標？140解：用x1，x2

和x3

表示產(chǎn)品A，B和C的產(chǎn)量。141例6-3電子產(chǎn)品生產(chǎn)企業(yè)HF公司通過采購半成品生產(chǎn)A、B、C三種型號的手機。這三種手機在同一流水線上生產(chǎn)，每件的生產(chǎn)工時消耗分別為5分鐘，7分鐘，12分鐘，利潤分別為每臺140元，210元，384元。生產(chǎn)線正常運轉(zhuǎn)時間為250小時/月，加班滿負荷運轉(zhuǎn)時最多有400小時/月。HF公司的決策者提出的月經(jīng)營目標按優(yōu)先級排序為：盡可能充分利用生產(chǎn)線的正常工時，工時不夠用時可以加班；希望A、B、C的產(chǎn)量至少達到700，750，500臺，根據(jù)單位工時的利潤比例設(shè)定權(quán)系數(shù)；加班工時最好不超過40小時/月；

希望A、B、C的產(chǎn)量盡可能超過月銷售量預測的最低水平800，900，550臺，根據(jù)單位工時的利潤比例設(shè)定權(quán)系數(shù)。問：各產(chǎn)品應生產(chǎn)多少才能達成上述經(jīng)營目標？建立本問題的其目標規(guī)劃模型。142解：設(shè)A、B、C的產(chǎn)量分別為x1,x2,x3。143例6-4SD公司下屬三個工廠生產(chǎn)某種產(chǎn)品來滿足四個地區(qū)的需求，各工廠的產(chǎn)量、各地的需求量以及從各工廠到四地的單位產(chǎn)品運輸費用如下表所示。如果僅要求運輸費用最小，在將該問題轉(zhuǎn)化為產(chǎn)銷平衡問題后，用運輸問題表上作業(yè)法求解得最低總運費為2750元。但是考慮到各地的不同情況和運輸中可能存在的問題，該公司在確定最后運輸方案時還需考慮其它幾個目標，按重要程度依次為：P1：地區(qū)3為重點銷售地區(qū)，其需求應優(yōu)先全部滿足；P2：用于供應地區(qū)2的產(chǎn)品中，工廠1的產(chǎn)品不少于80件；P3：為平衡各地需求，每個地區(qū)用戶需求的滿足率應不低于90%；P4：由于交通條件的限制，應盡量避免從工廠2運輸至地區(qū)2；P5：盡可能減少總運費。1441456.2兩變量目標規(guī)劃問題的圖解法

1466.2兩變量目標規(guī)劃問題的圖解法目標規(guī)劃模型中對目標進行了優(yōu)先級的區(qū)分，這決定了其求解過程是一個分級進行的過程：對于有L個優(yōu)先級的目標規(guī)劃問題，先在可行域內(nèi)尋找滿足P1級目標的解然后在保證P1級目標不被打破的前提下，再尋找滿足P2級目標的解依次類推如果用解空間的概念，求解過程又可以表述為：在可行域R0

內(nèi)找到滿足P1

級目標的解空間R1，再以R1

為可行域?qū)ふ覞M足P2

級目標的解空間R2，依次類推，直至在RL-1

內(nèi)尋找PL

級目標的解空間RL，其中目標規(guī)劃的最終求解結(jié)果通常只能稱為滿意解即只能保證優(yōu)先級較高的目標得以實現(xiàn)或部分實現(xiàn)，不保證優(yōu)先級低的目標能實現(xiàn)。1476.2兩變量目標規(guī)劃問題的圖解法步驟第1步在坐標平面第一象限表示出由剛性約束所確定的可行域，以此可行域為初始解空間R0；第2步選定P1優(yōu)先級的目標，進入第3步；第3步在Rl-1

中找到滿足Pl級目標的解空間進入第4步Rl；第4步當所有優(yōu)先級的目標都處理完時，求解結(jié)束，問題的滿意解就是目前得到的解空間；或者，如果Rl

為一個點，求解結(jié)束，問題的滿意解就是該點的坐標。如果上述條件皆不滿足，則轉(zhuǎn)到下一個優(yōu)先級，返回第3步。148圖解法示例例6-5用圖解法求解

149150151152153154155156157158圖解法示例例6-6

用圖解法求解1591601611621631641651666.2兩變量目標規(guī)劃問題的圖解法應用圖解法求解只有兩個決策變量、且一個優(yōu)先級Pl下有多個目標的目標規(guī)劃模型時，確定Pl優(yōu)先級的解空間Rl的過程就會變得比較復雜，見例6-7(略)。1676.4用Excel求解目標規(guī)劃問題掌握了序貫解法的原理，理解將目標規(guī)劃問題轉(zhuǎn)化為一系列線性規(guī)劃問題的方式，再進一步用Excel規(guī)劃求解工具完成。略。168169第9章網(wǎng)絡計劃技術(shù)(NetworkPlanningTechnique)基本概念網(wǎng)絡計劃技術(shù)（項目進度管理）它利用網(wǎng)絡圖的形式直觀表現(xiàn)出工程項目中各項任務之間的相互關(guān)系，從而找出決定項目總工期的關(guān)鍵路線和關(guān)鍵工序。進而，在一定工期、成本、資源等約束條件下通過各種技術(shù)手段獲得最佳的計劃安排，以達到縮短工期、提高工效、降低成本的目的。170引例17116分鐘引例17220分鐘發(fā)展歷程網(wǎng)絡計劃技術(shù)根據(jù)起源可以分為關(guān)鍵路徑法（CPM-CriticalPathMethod-WalkerandKelly）和計劃評審技術(shù)（PERT-ProgramEvaluationandReviewTechnic-U.S.Navy）兩個源頭。關(guān)鍵路徑法強調(diào)/要求所研究項目中每項任務的執(zhí)行時間必須是明確的，而計劃評審技術(shù)中每項任務的執(zhí)行時間可以是一個估計值/不確定值。因此，關(guān)鍵路徑法主要應用于一些有前期經(jīng)驗的工程項目，而計劃評審技術(shù)更多應用于研究與開發(fā)項目的計劃管理。1962,錢學森-華羅庚-“統(tǒng)籌法”173基本流程1-闡明問題，將項目分解為若干個可以獨立的工作單元，并明確各個工作單元的相關(guān)屬性（資源使用、時間消耗、成本計算等），以及工作單元之間的邏輯先后關(guān)系。2-根據(jù)分解后的工作單元，以及工作單元之間的邏輯先后關(guān)系，繪制網(wǎng)絡圖。174基本流程3-應用關(guān)鍵路徑法計算得到整個項目的最短完成時間，項目中每項工序的最遲開始時間、最早可能開始時間等時間參數(shù)，整個項目的關(guān)鍵路徑以及關(guān)鍵路徑上的各項關(guān)鍵工序。4-根據(jù)具體應用，對關(guān)鍵路徑上的關(guān)鍵工序進行資源的合理安排和優(yōu)化。175雙代號網(wǎng)絡圖的繪制方法工作單元用有向箭線來表示，箭線的方向表示工序進行的方向：箭線的箭尾表示該工序的開始，箭線的箭頭表示該工序的結(jié)束。工序的名稱或者代號標注在箭線的上方，工序所花費的時間標注在箭線的下方。176雙代號網(wǎng)絡圖的繪制方法多條箭線指向該節(jié)點代表著多條箭線所指的工序都完成之后，該節(jié)點之后的工序才可以開始E的緊后工序F，同理，C、D、E是F工序的緊前工序。多條箭線從該節(jié)點引出代表著該節(jié)點所代表的之前的工序結(jié)束后，可以同時開始多項工序。177雙代號網(wǎng)絡圖的繪制方法1-

網(wǎng)絡圖中箭線盡量從左指向右，從上至下，從小到大，節(jié)點的編號按順序編排，不允許重復。2-

兩個節(jié)點之間，如果有，只能有一條箭線。3-

網(wǎng)絡圖中只能有一個起始節(jié)點和一個終止節(jié)點。4-

不能有缺口和回路。除了起始點和終止點，任何節(jié)點都必須有至少一條箭線指向和引出該節(jié)點。178雙代號網(wǎng)絡圖的繪制方法如果節(jié)點之間需要包含兩個或兩個以上的箭線，即表示多個工序可以同時開始，并同時作為后續(xù)工序的緊前工序，那么需要使用虛工序（虛線的箭線）來幫助表示。179雙代號網(wǎng)絡圖的繪制方法180雙代號網(wǎng)絡圖的繪制方法181雙代號網(wǎng)絡圖的繪制方法182雙代號網(wǎng)絡圖示例1例9-1183雙代號網(wǎng)絡圖示例1184雙代號網(wǎng)絡圖示例2185單代號網(wǎng)絡圖的繪制方法節(jié)點表示工序，有向箭線描述工序之間的邏輯關(guān)系—緊前/緊后工序：箭尾連接的節(jié)點工序為箭頭連接的節(jié)點工序的緊前工序。單代號網(wǎng)絡不需要使用類似雙代號網(wǎng)絡中的虛工序。186單代號網(wǎng)絡圖的繪制方法187單代號網(wǎng)絡圖的繪制方法188單代號網(wǎng)絡圖的繪制方法189單代號網(wǎng)絡圖示例1例9-3190單代號網(wǎng)絡圖示例1例9-3191單代號網(wǎng)絡圖示例2192習題1193194195習題2196

197習題3198199習題4200201關(guān)鍵路徑法從開始節(jié)點出發(fā)，沿著不同的路徑到達終止節(jié)點所花費的時間也不盡相同。其中，花費時間最長的路經(jīng)稱為關(guān)鍵路徑，而關(guān)鍵路徑上的所有工序都被稱為關(guān)鍵工序。202關(guān)鍵路徑法基本特點1-關(guān)鍵路徑上的所有工序總花費時間決定了整個項目的總工期，即項目的總工期等于關(guān)鍵路徑上的所有工序持續(xù)時間的總和。2-關(guān)鍵路徑上的任一個關(guān)鍵工序發(fā)生了時間上的延遲，那么必然導致整個項目的工期時間上的延遲。203關(guān)鍵路徑法基本特點3-關(guān)鍵路徑上關(guān)鍵工序如果縮短了工期，那么整個項目的工期都會被縮短。相反，如果只是縮短非關(guān)鍵路徑上的工序—非關(guān)鍵工序的花費時間，整個項目的工期不會發(fā)生變化。4-

如果一個項目包含多條關(guān)鍵路徑，那么它們的工期一定都相同。并且，如果只是縮短其中一條關(guān)鍵路徑的工期，整個項目的工期并不能被縮短。204關(guān)鍵路徑法基本特點5-

關(guān)鍵路徑是相對的。如果關(guān)鍵路徑的工期被縮短，那么它有可能變?yōu)榉顷P(guān)鍵路徑，而非關(guān)鍵路徑則有可能變成關(guān)鍵路徑。205關(guān)鍵路徑法重要參數(shù)最早開始時間。一個工序的最早開始時間TES為該工序的所有緊前工序d最早結(jié)束時間中最晚的一個，即其所有緊前工序的最早結(jié)束時間的最大值。（前一個工序結(jié)束，后一個工序才能開始）最早結(jié)束時間。一個工序的最早結(jié)束時間TEF等于該工序的最早開始時間加上該工序的花費時間值。206關(guān)鍵路徑法重要參數(shù)最遲結(jié)束時間。一個工序的最遲結(jié)束時間TLF是指該工序在不影響整個項目的時間進度前提下能夠最遲結(jié)束的時間。它等于該工序所有緊后工序最遲開始時間最早的一個，即所有緊后工序的最遲開始時間的最小值。（取決于別的工序）最遲開始時間。一個工序的最遲開始時間TLS等于該工序的最遲結(jié)束時間減去該工序的花費時間值。207關(guān)鍵路徑法重要參數(shù)工序總時差。一個工序的總時差TTF是指該工序在不影響整個項目的時間進度前提下，工序最早開始時間可以推遲的時間，即該工序的最遲開始時間和最早開始時間的差值。LS-ES工序自由時差。一個工序的自由時差TFF是指該工序在不影響其它工序（其緊后工序）的最早開始時間前提下，工序最早開始時間可以推遲的時間。208技巧:工作最早時間的計算:

順著箭線