MBA講義32課時管理運籌學(xué)(謝家平)-上海財大

管理理運運籌籌學(xué)學(xué)-管理理科科學(xué)學(xué)方方法法謝家家平平博博士士教教授授博士士生生導(dǎo)導(dǎo)師師研究究領(lǐng)領(lǐng)域域：：管理理科科學(xué)學(xué)、、運運營營管管理理、、供供應(yīng)應(yīng)鏈鏈管管理理講授授課課程程：：管理理運運籌籌學(xué)學(xué)-管管理理科科學(xué)學(xué)方方法法、、管管理理系系統(tǒng)統(tǒng)工工程程、、運營營管管理理、、供供應(yīng)應(yīng)鏈鏈管管理理、、ERP、、國國際際物物流流、、企業(yè)業(yè)物物流流管管理理、、管管理理決決策策模模型型與與方方法法單位位：：上海海財財經(jīng)經(jīng)大大學(xué)學(xué)工工商商學(xué)學(xué)院院物物流流管管理理系系E-mail：：jiaping@1教材與參參考書籍籍教材：謝家平編編著.管管理運籌籌學(xué)：管管理科學(xué)學(xué)方法，，中國人民民大學(xué)出出版社，，2010參考書：：Davidetal.數(shù)數(shù)據(jù)、模模型與決決策，機機械工業(yè)業(yè)出版社社，2004費雷德里里克.數(shù)數(shù)據(jù)、、模型與與決策，，中國財財政經(jīng)濟濟出版社社，2004Jamesetal.數(shù)數(shù)據(jù)據(jù)、模型型與決策策，中國國人民大大學(xué)出版版社，2006232課時時講授提提綱緒論論第一章線線性性規(guī)劃第二章線線性性規(guī)劃討討論第三章對對偶偶規(guī)劃靜態(tài)規(guī)劃劃第四章整整數(shù)數(shù)規(guī)劃第五章目目標(biāo)標(biāo)規(guī)劃第六章動動態(tài)態(tài)規(guī)劃動態(tài)優(yōu)化化第七章網(wǎng)網(wǎng)絡(luò)絡(luò)分析第八章網(wǎng)網(wǎng)絡(luò)絡(luò)計劃第九章決決策策分析第十章方方案案排序第十一章章庫庫存控制制第十二章章排排隊理論論離散優(yōu)化化隨機優(yōu)化化淡化數(shù)學(xué)學(xué)算法LINDO求解解3考核方式式結(jié)課考試試：筆試（開開卷or閉閉卷？））每章一題題80%案例研究究：選擇合適適方法結(jié)結(jié)合企業(yè)業(yè)實際進進行應(yīng)用用20%4管理運籌籌學(xué)的稱稱謂管理運籌籌學(xué)是一一門研究究如何最最優(yōu)安排排的學(xué)科科。OperationsResearch日本譯作作“運用用學(xué)”香港、臺臺灣譯為為“作業(yè)業(yè)研究””我國譯作作“運籌籌學(xué)”源于古語語“運籌籌帷幄之之中，決決勝千里里之外””取“運籌籌”二字字，體現(xiàn)現(xiàn)運心籌籌謀、策策略取勝勝ManagementScience管管理理科學(xué)運用數(shù)學(xué)學(xué)、統(tǒng)計計學(xué)和運運籌學(xué)中中的量化化分析原原理和方方法，建建立數(shù)學(xué)學(xué)模型/計算機機仿真，，給管理理決策提提供科學(xué)學(xué)依據(jù)。。5緒論一、發(fā)展展歷史二、學(xué)科科作用三、學(xué)科科性質(zhì)四、工作作程序五、學(xué)科科體系六、學(xué)習(xí)習(xí)要求6一、發(fā)展展歷史1.早早期的運運籌思想想齊王賽馬馬?渭修皇宮宮沈括運軍軍糧?科學(xué)管理理2.軍軍事運籌籌學(xué)階段段20世紀(jì)紀(jì)40年年代誕生生于英美美1940年，英英國為對對付德國國空軍的的空襲，，使用了了雷達，，但沒有有科學(xué)布布局，效效果不好好。為解解決這個個問題，，成立運運籌學(xué)小小組，稱稱OperationalResearch，意為作戰(zhàn)研究究。美國和加加拿大也也在軍隊隊設(shè)立運運籌學(xué)小小組，稱稱OperationsResearch，協(xié)助指指揮官研研究戰(zhàn)略略及戰(zhàn)術(shù)術(shù)問題。。3.管管理運籌籌學(xué)階段段戰(zhàn)后許多多從事運運籌學(xué)研研究的科科學(xué)家轉(zhuǎn)轉(zhuǎn)向了民民用問題題的研究究，使運運籌學(xué)在在企業(yè)管管理方面面的應(yīng)用用得到了了長足進進展。7企業(yè)的成成功要素素中：觀念意識識更新47％人文文化化35％技術(shù)優(yōu)勢勢18％決策意識識的科學(xué)學(xué)性成功決策策正確決策策二、學(xué)科科作用理念的重重要性？8二、學(xué)科科作用1.量量化管理理的重要要性管理科學(xué)學(xué)是對與與定量因素素有關(guān)的管管理問題題通過應(yīng)用科學(xué)學(xué)的方法法進行輔助管理理決策的一門學(xué)學(xué)科。目的：：用科科學(xué)方方法分分析管管理問問題，，為管管理者者決策策提供供依據(jù)據(jù)目標(biāo)：：在企企業(yè)經(jīng)經(jīng)營內(nèi)內(nèi)外環(huán)環(huán)境的的限制制下，，實現(xiàn)現(xiàn)資源源效用用最大大組織中存在的問題定量分析定性分析評價與評估決策量化管管理是是第一一步,它導(dǎo)導(dǎo)致控控制,并最最終實實現(xiàn)改改進如果不不能量量化某某些事事情，，那么么就不不能理理解它它如果不不能理理解它它，那那么就就不能能控制制它如果不不能控控制它它，那那么就就不能能改進進它——H.JamesHarrington定性到到定量量分析析，數(shù)數(shù)量界界限的的重要要性：：量變變引起起質(zhì)變變9聽一場場音樂樂會：：網(wǎng)絡(luò)訂訂票的的票價價500元元，不不去可可退票票情況1：在在你馬馬上要要出發(fā)發(fā)的時時候，，發(fā)現(xiàn)現(xiàn)你把把最近近的價價值500元的的電話話卡弄弄丟了了。你你是否否還會會去聽聽這場場音樂樂會？？情況2：假假設(shè)昨昨天花花500元元錢買買一張張今晚晚的音音樂會會取票票單。。在你你出發(fā)發(fā)時，，發(fā)現(xiàn)現(xiàn)把票票單丟丟了。。如果果去聽聽音樂樂會，，就必必須再再花500元錢錢買張張票，，去還還會不不去？？二、學(xué)學(xué)科作作用2.量量化化思考考使人人理性性冰淇淋淋實驗驗：一杯A有70克克，裝在在50克克的杯子子里，，看上上去要要溢出出了一杯B是80克克，裝在在100克的杯子子里，，看上上去還還沒裝裝滿單獨憑憑經(jīng)驗驗判斷斷時，，在相相同的的價格格上，，人們們普遍遍選擇擇A實驗表表明，，大部部分的的回答答者仍仍舊會會去聽聽結(jié)果卻卻是，，大部部分人人回答答說不不去了了10二、學(xué)學(xué)科作作用3.量量化化分析析輔助助決策策盈虧平平衡分分析40,00080,000120,000160,00004080120160200Revenue=900xFixedcostLossProfitCost=50,000+400xxBreak-evenpoint=100units利潤：：I=(P––Cm––Ch)Q-F策略1↑↑↑????????差異化化，領(lǐng)領(lǐng)先者者戰(zhàn)略略策略2↑??????↑↑??規(guī)?；蟠笠?guī)模模市場場策略3↑??↓↓??????機械化化，第第一利利潤源源策略4↑????↓↓????技能化化，第第二利利潤源源策略5↑????????↓↓信息化化，第第三利利潤源源11二、學(xué)學(xué)科作作用量化輔輔助決決策案案例：：盈虧虧平衡衡分析析例：某某企業(yè)業(yè)總銷售售額1100萬萬元物料成成本700萬萬元員工工工資200萬萬元管理費費用100萬萬元現(xiàn)在利利潤=100萬萬元，，目標(biāo)標(biāo)利潤潤150萬萬元利潤實實現(xiàn)的的方法法有：：將銷售售收入入增加加100%將員工工工資資減少少25%將管理理費用用減少少50%將物料料成本本減少少7.1%12二、學(xué)學(xué)科作作用4.決決策策意識識的重重要性性生產(chǎn)計計劃決決策一星期期工作作5天天,每每天天正常常工作作8小小時一周作業(yè)費費用：11000(直直接人工成成本與間接接費用)直接人工成成本：10/1h(一臺機機器需一位位作業(yè)人員員)間接費用：：人工成本本2.5倍倍甲乙丙原料659565直接工時65分95分65分直接人工121410間接費用303525總成本107144100售價173233170利潤668970H18H6H10甲設(shè)備數(shù)EGHFHGG20H13E6F10裝配E24E15G7DG14G10H7F10G7G4CBA裝配H14乙丙13二、學(xué)科作作用甲產(chǎn)品產(chǎn)量量40,乙乙產(chǎn)品80,丙丙產(chǎn)品40利潤=40×66+80×89+40×70=12560人員有限如如何實現(xiàn)?采取什么么薪酬制度度?計件工資制制，讓員工工自愿加班班甲乙丙單位產(chǎn)品總成本107144100單位產(chǎn)品售價173233170單位產(chǎn)品利潤668970市場每周需求408040決策的科學(xué)學(xué)性？方案一14二、學(xué)科作作用甲產(chǎn)品產(chǎn)量量40,乙產(chǎn)品品80,丙產(chǎn)品品40總收入=40×173+80×233+40××170=32360原料成本=40×65+80×95+40×65=12800營運費用=11000總利潤=32360-12800-11000=8560人員有限如如何實現(xiàn)?采取什么么薪酬制度度?崗位工資制制（定崗定定員），讓讓員工自覺覺加班甲乙丙原料659565運營費用11000售價173233170市場每周需求408040決策的科學(xué)學(xué)性？方案二15二、學(xué)科作作用決策的科學(xué)學(xué)性？產(chǎn)能能符合計算算甲乙丙總成本107144100售價173233170利潤668970乙與丙哪一一個產(chǎn)品比比較賺錢?產(chǎn)品市場需求單位產(chǎn)品設(shè)備工時消耗EFGH甲400103131乙8030202113丙401502124需求產(chǎn)能3000200037603240可用產(chǎn)能2400240048004800E是瓶頸16二、學(xué)科作作用方案三：計時工工資，且以以單位利潤潤率高低為為決策意識識。乙比較賺錢錢,假如如80個全全部生產(chǎn)需用E產(chǎn)能2400分鐘，但是是E只有2400分鐘可可用因此只能生生產(chǎn)80個乙(2400/30)，而丙無法法生產(chǎn)方案：甲產(chǎn)品40個，乙產(chǎn)品80個，丙產(chǎn)品0個總收入=40×173+80×233+0×170=25560原料=40×65+80××95+0×65=10200，營運費用=11000利潤=25560-10200-11000=4360方案四：計時工工資，但以以占用瓶頸頸資源大小小為決策意意識。丙比較賺錢錢,優(yōu)先先生產(chǎn)40個需用E產(chǎn)能600(40ⅹ15)分鐘剩下1800分鐘,可可生產(chǎn)60個乙(1800/30)方案：甲產(chǎn)產(chǎn)品40個，乙產(chǎn)產(chǎn)品60個，丙產(chǎn)產(chǎn)品40個總收入=40×173+60×233+40××170=27700原材料=40×65+60××95+40×6540=10900，營運費用用=11000利潤=27700-10900-11000=580017三、學(xué)科性性質(zhì)1.研研究究對對象象經(jīng)濟濟和和管管理理活活動動中中能能用用““數(shù)數(shù)量量關(guān)關(guān)系系””描描述述的的如運運營營、、規(guī)規(guī)劃劃與與組組織織管管理理問問題題解決決的的理理論論模模型型和和優(yōu)優(yōu)化化方方法法實實踐踐2.學(xué)學(xué)科科特特點點強調(diào)調(diào)科科學(xué)學(xué)性性和和定定量量分分析析強調(diào)調(diào)應(yīng)應(yīng)用用性性和和實實踐踐性性強調(diào)調(diào)從從整整體體上上進進行行把把握握18四、、工工作作程程序序管理者制定決策：管理運籌學(xué)的步驟：明確問題環(huán)境分析確定目標(biāo)制定準(zhǔn)則收集資料數(shù)量關(guān)系結(jié)構(gòu)分析數(shù)學(xué)模型制定決策方案選擇算法求解方案優(yōu)選否是方案實施持續(xù)改進識別問題量化分析建立模型軟件求解結(jié)果分析確定方案實施方案控制管理者解的分析19五、、學(xué)學(xué)科科體體系系1.管管理理問問題題需求預(yù)測產(chǎn)品的市場需求量有多大，需求類別如何，對企業(yè)盈利有何影響?生產(chǎn)計劃在有限資源約束下，生產(chǎn)什么，生產(chǎn)多少，獲利最大？資源配置需要哪些資源，如何進行最優(yōu)配置，資源緊缺性如何，以什么代價獲取?作業(yè)排序作業(yè)的重要次序如何，作業(yè)的順序安排如何?市場營銷廣告預(yù)算、媒介選擇、產(chǎn)品定價、銷售計劃等如何安排？運輸問題最佳運輸線路是哪條？物流配送集載如何優(yōu)化？物流設(shè)施布局如何設(shè)置？設(shè)施選址運營點如何選擇，需要哪些運作設(shè)施，設(shè)施如何布局?庫存控制應(yīng)保持多大庫存量，何時應(yīng)進行訂貨，訂貨批量多少為宜?項目規(guī)劃項目完工工期多長為宜，哪些作業(yè)起關(guān)鍵性作用，資源如何分配?設(shè)備更新設(shè)備運轉(zhuǎn)狀況如何演進，運行可靠性如何，何時和如何更新或改造?人力資源人員需求預(yù)測，技能要求，編制與任務(wù)指派，績效測評，留用多長時間?財務(wù)資金資金投放的數(shù)量，從何處進行融資，資金成本是多少?排隊問題隊列多長，有無容量限制，多少服務(wù)臺為宜，能提供什么水平的服務(wù)?20五、、學(xué)學(xué)科科體體系系2.學(xué)學(xué)科科內(nèi)內(nèi)容容模型類型解決的典型辦法線性規(guī)劃在線性目標(biāo)和約束條件間取得最優(yōu)化結(jié)果整數(shù)規(guī)劃在線性目標(biāo)和約束條件間尋求整數(shù)決策最優(yōu)目標(biāo)規(guī)劃在相對立的目標(biāo)間尋得多目標(biāo)妥協(xié)的滿意解動態(tài)規(guī)劃尋求多階段動態(tài)系統(tǒng)的整體決策優(yōu)化問題網(wǎng)絡(luò)分析尋求網(wǎng)絡(luò)路徑、流量分布、網(wǎng)絡(luò)瓶頸及其改進網(wǎng)絡(luò)計劃用各種作業(yè)和結(jié)點的網(wǎng)絡(luò)排列來說明項目實施計劃管理決策依據(jù)決策準(zhǔn)則權(quán)衡比較備選方案的決策結(jié)果方案排序綜合各方案的優(yōu)勢與不足尋求多指標(biāo)排名次序庫存模型尋求訂貨、存儲和缺貨等庫存成本降至最低的經(jīng)濟批量統(tǒng)計方法從一個抽樣得到普遍結(jié)果的推論和曲線擬合排隊理論分析正在等待的隊列特點及其運行指標(biāo)仿真模擬動態(tài)觀察復(fù)雜的管理問題的行為，模擬管理系統(tǒng)的結(jié)構(gòu)關(guān)系21五、、學(xué)學(xué)科科體體系系3.學(xué)學(xué)科科應(yīng)應(yīng)用用管理理既既是是科科學(xué)學(xué)又又是是藝藝術(shù)術(shù)低層層管管理理的的科科學(xué)學(xué)成成分分較較多多，，高高層層管管理理的的藝藝術(shù)術(shù)成成分分較較多多運營營管管理理需需較較多多管管理理科科學(xué)學(xué)，，人人力力資資源源管管理理需需較較多多管管理理藝藝術(shù)術(shù)例行行管管理理需需要要較較多多管管理理科科學(xué)學(xué)，，例例外外管管理理需需要要較較多多管管理理藝藝術(shù)術(shù)M:管理理決決策策問問題題MC:定量量解解決決方方法法方案案選選擇擇依依據(jù)據(jù)問題題導(dǎo)導(dǎo)向向技術(shù)術(shù)支支持持戰(zhàn)略略決決策策營銷銷決決策策生產(chǎn)產(chǎn)安安排排財務(wù)務(wù)分分析析人力力資資源源方案案優(yōu)優(yōu)選選………應(yīng)用用統(tǒng)統(tǒng)計計線性性規(guī)規(guī)劃劃整數(shù)數(shù)規(guī)規(guī)劃劃目標(biāo)標(biāo)規(guī)規(guī)劃劃網(wǎng)絡(luò)絡(luò)計計劃劃網(wǎng)絡(luò)絡(luò)分分析析決策策分分析析動態(tài)態(tài)規(guī)規(guī)劃劃………管理理科科學(xué)學(xué)：運運用用合合理理的的分分析析來來改改善善決決策策的的制制定定管理理者者:制定定決決策策22六、學(xué)習(xí)要求求1.學(xué)科地地位數(shù)學(xué)技術(shù)科學(xué)管理學(xué)科基礎(chǔ)管理運籌學(xué)管理專業(yè)課高等數(shù)學(xué)、概率統(tǒng)計、線性代數(shù)…加工技術(shù)、工程技術(shù)、信息技術(shù)…經(jīng)濟學(xué)原理、管理學(xué)、行為科學(xué)…離散、連續(xù)，靜態(tài)、動態(tài)的方法…戰(zhàn)略、運營、營銷、財務(wù)、人力…23六、學(xué)習(xí)要求求經(jīng)濟學(xué)企業(yè)戰(zhàn)略、公公司治理會計學(xué)財務(wù)管理人力資源管理理組織行為學(xué)學(xué)管理科學(xué)方法支持企業(yè)B行業(yè)企業(yè)C企業(yè)A商務(wù)2商務(wù)3商務(wù)1職能b職能c職能a小組ii小組iii小組i運營管理市場營銷質(zhì)量管理項目管理……信息管理流程管理物流管理供應(yīng)鏈管理……24六、學(xué)習(xí)要求求2.如何學(xué)學(xué)習(xí)重點在結(jié)合實實際的應(yīng)用發(fā)揮自己管理理實踐經(jīng)驗豐豐富和理論聯(lián)聯(lián)系實際的能能力強化結(jié)合實際際問題建立管管理優(yōu)化模型型的能力強化解決問題題的方案或模模型的解的分分析與應(yīng)用能能力充分借用管理理運籌學(xué)教學(xué)學(xué)軟件25第1章線性規(guī)規(guī)劃Subtitle內(nèi)容提要第一節(jié)線線性規(guī)劃的一一般模型一、線性規(guī)劃劃的三個要素素二、線性規(guī)劃劃模型的特征征三、線性規(guī)劃劃的圖解方法法四、線性規(guī)劃劃解的可能性性第二節(jié)線線性規(guī)劃的單單純形法一、線性規(guī)劃劃的標(biāo)準(zhǔn)型式式二、線性規(guī)劃劃之解的概念念三、單純形法法的基本原理理26一、線性規(guī)劃劃的三個要素素第一節(jié)線性性規(guī)劃的一般般模型決策變量決策問題待定定的量值取值要求非負負約束條件任何管理決策策問題都是限限定在一定的的條件下求解解把各種限制條條件表示為一一組等式或不不等式稱約束束條件約束條件是決決策方案可行行的保障約束條件是決決策變量的線線性函數(shù)目標(biāo)函數(shù)衡量決策優(yōu)劣劣的準(zhǔn)則，如如時間最省、、利潤最大、、成本最低目標(biāo)函數(shù)是決決策變量的線線性函數(shù)有的目標(biāo)要實實現(xiàn)極大，有有的則要求極極小27二、線性規(guī)劃劃模型的舉例例第一節(jié)線性性規(guī)劃的一般般模型1、生產(chǎn)計劃劃問題例.某廠生產(chǎn)甲乙乙兩種產(chǎn)品，，生產(chǎn)工藝路路線為：各自自的零部件分分別在設(shè)備A、B加工，，最后都需在在設(shè)備C上裝裝配。經(jīng)測算算得到相關(guān)數(shù)數(shù)據(jù)如表所示示。應(yīng)如何制制定生產(chǎn)計劃劃，使總利潤潤為最大。據(jù)市場分析，，單位甲乙產(chǎn)產(chǎn)品的銷售價價格分別為73和75元元，試確定獲獲利最大的產(chǎn)產(chǎn)品生產(chǎn)計劃劃。產(chǎn)品設(shè)備工時消耗甲乙工時成本元/h生產(chǎn)能力hABC20023420151016103228第一節(jié)線性性規(guī)劃的一般般模型(1)決策變量：設(shè)x1為甲產(chǎn)品的產(chǎn)產(chǎn)量，x2為乙產(chǎn)品的產(chǎn)產(chǎn)量。(2)約束條件：生產(chǎn)受設(shè)備能能力制約，能能力需求不能能突破有效供供給量。設(shè)備A的約束束條件表達為為2x1≤16同理，設(shè)備B的加工能力力約束條件表表達為2x2≤10設(shè)備C的裝配配能力也有限限，其約束條條件為3x1+4x2≤32(3)目標(biāo)函數(shù)：目標(biāo)是企業(yè)利利潤最大化maxZ=3x1+5x2(4)非負約束：甲乙產(chǎn)品的產(chǎn)產(chǎn)量為非負x1≥0，x2≥0綜上的LP模模型：29二、線性規(guī)劃劃模型的舉例例第一節(jié)線性性規(guī)劃的一般般模型2、物資運輸輸問題例：某產(chǎn)品商有三三個供貨源A1、A2、A3，其經(jīng)銷商有有4個（需求求市場）B1、B2、B3、B4。已知各廠的的產(chǎn)量、各經(jīng)經(jīng)銷商的銷售售量及從Ai到Bj的單位運費為為Cij。為發(fā)揮集團團優(yōu)勢，公司司要統(tǒng)一籌劃劃運銷問題，，求運費最小小的調(diào)運方案案。銷地產(chǎn)地B1B2B3B4產(chǎn)量A1632550A2758420A3329730銷量2030104030第一節(jié)線性性規(guī)劃的一般般模型(1)決策變變量：設(shè)從Ai到Bj的運輸量為xij，(2)目標(biāo)函函數(shù)：運費最小的目目標(biāo)函數(shù)為minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34(3)約束條條件：產(chǎn)量之和等于于銷量之和,故要滿足：：供應(yīng)平衡條件件x11+x12+x13+x14=50x21+x22+x23+x24=20x31+x32+x33+x34=30銷售平衡條件件x11+x21+x31=20x12+x22+x32=30x13+x23+x33=10x14+x24+x34=40非負性約束xij≥0(i=1,2,3；j=1,2,3,4)31二、線性規(guī)劃劃模型的舉例例第一節(jié)線性性規(guī)劃的一般般模型3、產(chǎn)品配比比問題例：用濃度45%和92%的的硫酸配置100噸濃度度80%的硫硫酸。決策變量：取45%和92%的硫酸酸分別為x1和x2噸約束條件：求解二元一次次方程組得解解非負約束：x1≥0，x2≥032第一節(jié)線性性規(guī)劃的一般般模型若有5種不同同濃度的硫酸酸可選(30%,45%,73%,85%,92%)會如如何呢？取這5種硫酸酸分別為x1、x2、x3、x4、x5，有有多少種配比比方案？何為最好？若5種硫酸價價格分別為400,700,1400,1900,2500元/t，則則：33三、線線性規(guī)規(guī)劃模模型的的特征征第一節(jié)節(jié)線線性規(guī)規(guī)劃的的一般般模型型1、模模型隱隱含假假定（1））線性性化假假定函數(shù)關(guān)關(guān)系式式f(x)=c1x1+c2x2+…+cnxn，稱線線性函函數(shù)。。建模技技巧：：將非非線性性的函函數(shù)進進行分分段線線性化化。（2））同比比例假假定決策變變量變變化引引起目目標(biāo)函函數(shù)和和約束束方程程的改改變量量比例例。（3））可加加性假假定決策變變量對對目標(biāo)標(biāo)函數(shù)數(shù)和約約束方方程的的影響響是獨獨立于于其他他變量量的。。目標(biāo)函函數(shù)值值是決決策變變量對對目標(biāo)標(biāo)函數(shù)數(shù)貢獻獻的總總和。。（4））連續(xù)續(xù)性假假定決策變變量取取值連連續(xù)。。（5））確定定性假假定所有參參數(shù)都都是確確定的的，不不包含含隨機機因素素。34三、線線性規(guī)規(guī)劃模模型的的特征征第一節(jié)節(jié)線線性規(guī)規(guī)劃的的一般般模型型2、一一般數(shù)數(shù)學(xué)模模型用一組組非負負決策策變量量表示示的一一個決決策問問題；；存在一一組等等式或或不等等式的的線性性約束束條件件；有一個個希望望達到到的目目標(biāo)，，可表表示成成決策策變量量的極極值線線性函函數(shù)。。35四、線線性規(guī)規(guī)劃的的圖解解方法法第一節(jié)節(jié)線線性規(guī)規(guī)劃的的一般般模型型1、線線性規(guī)規(guī)劃的的可行行域可行域域：滿足所所有約約束條條件的的解的的集合合，即所有有約束束條件件共同同圍城城的區(qū)區(qū)域。。maxZ=3x1+5x22x1≤162x2≤103x1+4x2≤32x1≥0,x2≥0S.t.2x1=162x2=103x1+4x2=32x1x248103590ABCD362x1=162x2=10x1x248103583x1+4x2

=320ABCD四、、線線性性規(guī)規(guī)劃劃的的圖圖解解方方法法第一一節(jié)節(jié)線線性性規(guī)規(guī)劃劃的的一一般般模模型型2、、線線性性規(guī)規(guī)劃劃的的最最優(yōu)優(yōu)解解目標(biāo)標(biāo)函函數(shù)數(shù)Z=3x1+5x2代表表以以Z為參參數(shù)數(shù)的的一一族族平平行行線線。。Z=30Z=37Z=1537四、、線線性性規(guī)規(guī)劃劃的的圖圖解解方方法法第一一節(jié)節(jié)線線性性規(guī)規(guī)劃劃的的一一般般模模型型3、、線線性性規(guī)規(guī)劃劃解解的的特特性性abcd由線線性性不不等等式式組組成成的的可可行行域域是是凸凸多多邊邊形形(凸凸多多邊邊形形是是凸凸集集)凸集集定定義義：：集集合合內(nèi)內(nèi)部部任任意意兩兩點點連連線線上上的的點點都都屬屬于于這這個個集集合合可行行域域有有有有限限個個頂頂點點。。目標(biāo)標(biāo)函函數(shù)數(shù)最最優(yōu)優(yōu)值值一一定定在在可可行行域域的的邊邊界界達達到到，，而而不不可可能能在在其其區(qū)區(qū)域域的的內(nèi)內(nèi)部部。。38五、、線線性性規(guī)規(guī)劃劃解解的的可可能能性性第一一節(jié)節(jié)線線性性規(guī)規(guī)劃劃的的一一般般模模型型1、、唯唯一一最最優(yōu)優(yōu)解解：：只只有有一一個個最最優(yōu)優(yōu)點點2、、多多重重最最優(yōu)優(yōu)解解：：無無窮窮多多個個最最優(yōu)優(yōu)解解當(dāng)市市場場價價格格下下降降到到74元元，，其其數(shù)數(shù)學(xué)學(xué)模模型型變變?yōu)闉?x1=162x2=103x1+4x2

=32x1x248102580ABCDZ=24Z=32Z=1239五、線性性規(guī)劃解解的可能能性第一節(jié)線線性規(guī)規(guī)劃的一一般模型型3、無界界解：可可行域無無界，目目標(biāo)值無無限增大大(缺乏必必要約束束)40五、線性性規(guī)劃解解的可能能性第一節(jié)線線性規(guī)規(guī)劃的一一般模型型4、沒有有可行解解：線性性規(guī)劃問問題的可可行域是是空集(約束條條件相互互矛盾)目標(biāo)沖突利害沖突目標(biāo)強沖突利害弱沖突41一、線性性規(guī)劃的的標(biāo)準(zhǔn)型型式第二節(jié)線線性規(guī)規(guī)劃的一一般模型型1、標(biāo)準(zhǔn)準(zhǔn)型表達達方式(1)代代數(shù)式(2)向向量式(3)矩矩陣式A：技術(shù)術(shù)系數(shù)矩矩陣，簡簡稱系數(shù)數(shù)矩陣；；B：可用用的資源源量，稱稱資源向向量；C：決策策變量對對目標(biāo)的的貢獻，，稱價值值向量；；X：決策策向量。。42一、線性性規(guī)劃的的標(biāo)準(zhǔn)型型式第二節(jié)線線性規(guī)規(guī)劃的一一般模型型2、標(biāo)準(zhǔn)準(zhǔn)型轉(zhuǎn)換換方法(1)如如果極小小化原問問題minZ=CX，，則令Z'=-Z，，轉(zhuǎn)為求求maxZ'=-CX(2)若若某個bi<0，則則以－1乘該約約束兩端端，使之之滿足非非負性的的要求。。(3)對對于≤型型約束，，則在左左端加上上一個非非負松弛弛變量，，使其為為等式。。(4)對對于≥型型約束，，則在左左端減去去一個非非負剩余余變量，，使其為為等式。。(5)若若某決策策變量xk無非負約約束，令令xk=x'k-x"k，(x'k≥0,x"k≥0)。。43二、線性性規(guī)劃之之解的概概念第二節(jié)線線性規(guī)規(guī)劃的一一般模型型基矩陣：：一個非奇奇異的子子矩陣（（線性無無關(guān)）。。矩陣A中中任意m列的線線性無關(guān)關(guān)子矩陣陣B，稱為一一個基。。組成基B的列為基基向量，，用Pj表示(j=1,2,…,n)?；兞浚海号c基向量量Pj相對應(yīng)的的m個變變量xj稱為基變變量其余的n-m個變變量為非非基變量量1、線性性規(guī)劃解解之關(guān)系系基解：令所有非非基變量量等于零零，得出出基變量量的唯一一解。。x3x4x5基變量是是x3,x4,x5非基變量量是x1,x2令非基變變量x1=x2=0，得得到一個個基解x3=16，x4=10，，x5=3244二、線性性規(guī)劃之之解的概概念第二節(jié)線線性規(guī)規(guī)劃的一一般模型型1、線性性規(guī)劃解解之關(guān)系系可行解：滿足約束束條件AX=b,X≥0的的解?？尚谢嚎尚薪鈱?yīng)的基基矩陣。?；尚薪饨猓簼M足非負負性約束束的基解解稱為基基可行解解。最優(yōu)解：：使目標(biāo)函函數(shù)最優(yōu)優(yōu)的可行行解，稱稱為最優(yōu)優(yōu)解。最優(yōu)基：：最優(yōu)解對對應(yīng)的基基矩陣，，稱為最最優(yōu)基。。非可行解可行解基解基可行解45二、線性性規(guī)劃之之解的概概念第二節(jié)線線性規(guī)規(guī)劃的一一般模型型2、線性性規(guī)劃基基本原理理定理1.若線性規(guī)規(guī)劃問題題存在可可行域，，則其可可行域一一定是凸凸集。定理2.線性規(guī)劃劃問題的的基可行行解對應(yīng)應(yīng)可行域域的頂點點。定理3.若可行域域有界，，線性規(guī)規(guī)劃的目目標(biāo)函數(shù)數(shù)一定可可以在可可行域的的頂點上上達到最最優(yōu)。定理4.線性規(guī)劃劃如果有有可行解解，則一一定有基基可行解解；如果果有最優(yōu)優(yōu)解，則則一定有有基可行行解是最最優(yōu)解。。46二、線性性規(guī)劃之之解的概概念第二節(jié)線線性規(guī)規(guī)劃的一一般模型型3、線性性規(guī)劃解解題思路路先找到一一個初始始基可行行解，也也就是找找到一個個初始可可行基，，想辦法法判斷這這個基可可行解是是不是最最優(yōu)解。。如果是最最優(yōu)解，，就得到到這個線線性規(guī)劃劃問題的的最優(yōu)解解；如果判斷出不不是最優(yōu)解，，就想法由這這個可行基按按一定規(guī)則變變化到下一個個可行基，然然后再判斷新新得到的基可可行解是不是是最優(yōu)解；如果還不是，，再接著進行行下一個可行行基變化，直直到得到最優(yōu)優(yōu)解。47三、單純形法法的基本原理理第二節(jié)線性性規(guī)劃的一般般模型maxZ=3x1+5x2+0x3+0x4+0x5=02x1+x3=162x2+x4=103x1+4x2+x5=32Cj比值CBXBb檢驗數(shù)jx1x2x3x4x535000162010010020103234001x3x4x5000035000-10/2=532/4=848三、單純形法法的基本原理理第二節(jié)線性性規(guī)劃的一般般模型162010050101/2012300-21x3x2x5050300-5/205-4Cj比值CBXBb檢驗數(shù)jx1x2x3x4x535000檢驗數(shù)j80014/3-2/350101/204100-2/31/3x3x2x1053000-1/2-1最優(yōu)解:X*=(4,5,8,0,0)T，Z*=3749三、單純形法法的基本原理理第二節(jié)線性性規(guī)劃的一般般模型單純形的管理理啟示2x1=162x2=103x1+4x2

=32x1x24812590ABC(4,5)DX0=(0,0,10,10,32)TX1=(0,5,10,0,12)TX1=(4,5,8,0,0)T企業(yè)管理過程程也是如此，，把現(xiàn)有方案案作為初始方方案，找到最最急需要改進進的某個問題題和改進方向向，一次做好好某個主要問問題的解決與與改進；一次次只解決和改改進一個問題題的難度最小?。唤鉀Q之后后，再尋求可可以改進的其其它地方，再再次改進，不不斷地追求完完美。50第2章線性規(guī)規(guī)劃討論Subtitle內(nèi)容提要第一節(jié)目目標(biāo)函數(shù)的描描述技巧計件工資崗位工資計時工資第二節(jié)線線性規(guī)劃的適適用層次第三節(jié)線線性規(guī)劃的典典型案例第四節(jié)線線性規(guī)劃靈敏敏度分析價值系數(shù)的變變動分析資源數(shù)量的變變動分析51計件工資體系系，目標(biāo)是企企業(yè)利潤最大大化：第一節(jié)目標(biāo)標(biāo)函數(shù)的描述述技巧一、計件工資資產(chǎn)品甲：產(chǎn)品乙：產(chǎn)品丙：非負性約束計件工資制薪薪酬體系下，，工作時間不不會完全受每每天8小時工工作時間約束束，但有產(chǎn)品品市場需求約約束，如下：：經(jīng)Lindo軟軟件件求求解解，，得得到到最最優(yōu)優(yōu)解解為為Z=12560，，產(chǎn)產(chǎn)品品甲甲x1=40，，產(chǎn)產(chǎn)品品乙乙x2=80，，產(chǎn)產(chǎn)品品丙丙x3=40。。52第一一節(jié)節(jié)目目標(biāo)標(biāo)函函數(shù)數(shù)的的描描述述技技巧巧二、、崗崗位位工工資資崗位位工工資資制制薪薪酬酬體體系系，，以以計計時時工工資資制制為為基基礎(chǔ)礎(chǔ)，，實實行行定定崗崗定定員員。?？偸帐杖肴?173x1+233x2+170x3，原料料成成本本=65x1+95x2+65x3，營營運運費費用用=11000，，則目目標(biāo)標(biāo)函函數(shù)數(shù)為為maxZ=108x1+138x2+105x3-11000崗位工資資制薪酬酬體系下下，工作作時間也也不會完完全受每每天8小小時工作作時間約約束，但但有產(chǎn)品品市場需需求約束束，如下下：產(chǎn)品甲：產(chǎn)品乙：產(chǎn)品丙：非負性約束經(jīng)Lindo軟軟件求解解，得到到最優(yōu)解解為Z=8560,x1=40,x2=80,x3=40。。53第一節(jié)目目標(biāo)函函數(shù)的描描述技巧巧三、計時時工資目標(biāo)函數(shù)數(shù)為經(jīng)Lindo軟軟件求解解，得到到最優(yōu)解解為Z=5800,x1=40,x2=60,x3=40。。設(shè)備E：設(shè)備F：設(shè)備G：設(shè)備H：產(chǎn)品甲：產(chǎn)品乙：產(chǎn)品丙：市場需求求約束設(shè)備能力力約束54第二節(jié)線線性規(guī)規(guī)劃的適適用層次次計劃鏈的的層次粗能力計劃定單可行不可行CRP主生產(chǎn)計劃MPS物料需求計劃MRP能力需求計劃車間作業(yè)計劃銷售計劃可行否作業(yè)統(tǒng)計與控制物料清單庫存管理外購計劃供應(yīng)商成品、在制品信息生產(chǎn)計劃大綱預(yù)測當(dāng)前條件經(jīng)營計劃產(chǎn)值計劃劃或利潤計劃劃絕對數(shù)量量或增長幅度度期限:年年度單單位位:萬元元大類產(chǎn)品品銷售收收入或臺套產(chǎn)品品種種和數(shù)量如何確定定期限:年年度單單位位:萬臺臺具體產(chǎn)品品在具體體時段的出出產(chǎn)計劃劃合同訂單單和預(yù)測測轉(zhuǎn)換為生生產(chǎn)任務(wù)務(wù)將產(chǎn)品出出產(chǎn)計劃劃轉(zhuǎn)換成成物料需需求表大類產(chǎn)品品年度生生產(chǎn)計劃劃確定產(chǎn)品品的品種種和數(shù)量期限:年年度單單位:萬臺55第三節(jié)線線性規(guī)規(guī)劃的典典型案例例配送中心心選擇例：某企業(yè)存存在兩個個供貨源源（產(chǎn)地地），已已知原有有供貨源源每月的的供貨能能力是5萬臺產(chǎn)產(chǎn)品，新新增供貨貨源的生生產(chǎn)能力力可以滿滿足產(chǎn)品品的需求求，且兩兩個貨源源的價格格相同。。有三個個區(qū)域域目標(biāo)標(biāo)市場場（銷銷地或或銷售售商）），各各銷地地每月月的市市場需需求量量為5萬臺臺、10萬萬臺、、5萬萬臺。。在分銷銷渠道道中，，擬定定在2個地地點中中選址址設(shè)立立分銷銷中心心，執(zhí)執(zhí)行產(chǎn)產(chǎn)品的的轉(zhuǎn)運運任務(wù)務(wù)。各各地之之間的的單位位運輸輸物流流成本本（由由距離離和運運輸方方式?jīng)Q決定））56第三節(jié)節(jié)線線性規(guī)規(guī)劃的的典型型案例例決策變變量：：設(shè)從從供貨貨源到到分銷銷中心心的運運輸量量為，，從從分銷銷中心心到需需求市市場的的運輸輸量為為。。選址址規(guī)劃劃在于于二者者的實實際取取值。。如果，，則則不設(shè)設(shè)置分分銷中中心；；反之，，則設(shè)設(shè)置,其規(guī)規(guī)模為為如果，，則則不設(shè)設(shè)置分分銷中中心；；反之，，則設(shè)設(shè)置，，其規(guī)規(guī)模為為目標(biāo)函函數(shù)：：各條條路段段上的的實際際運輸輸量乘乘以物物流運運輸?shù)牡膯挝晃毁M用用之總總和最最小，，即存在供供應(yīng)能能力約約束、、市場場需求求約束束、配配送中中轉(zhuǎn)約約束，，如下下：57第三節(jié)節(jié)線線性規(guī)規(guī)劃的的典型型案例例供應(yīng)能能力平平衡約約束：：市場需需求平平衡約約束配送中中心不不存留留產(chǎn)品品所有變變量大大于等等于零零58第四節(jié)節(jié)線線性規(guī)規(guī)劃靈靈敏度度分析析一、靈靈敏度度分析析的必必要性性線性規(guī)規(guī)劃研研究的的是一一定條條件下下的最最優(yōu)化化問題題資源環(huán)環(huán)境和和技術(shù)術(shù)條件件是可可變的的基礎(chǔ)數(shù)數(shù)據(jù)往往往是是測算算估計計的數(shù)數(shù)值靈敏度度分析析的概概念靈敏度度分析析又稱稱敏感感性分分析或或優(yōu)化化后分分析研究基基礎(chǔ)數(shù)數(shù)據(jù)發(fā)發(fā)生波波動后后對最最優(yōu)解解的影影響最優(yōu)解解對數(shù)數(shù)據(jù)變變化的的敏感感程度度在多大大的范范圍內(nèi)內(nèi)波動動才不不影響響最優(yōu)優(yōu)基靈敏度度分析析解決決的問問題：：參數(shù)在在什么么范圍圍變化化而最最優(yōu)基基不變變已知參參數(shù)的的變化化范圍圍，考考察最最優(yōu)解解(最最優(yōu)基基)是是否改改變59第四節(jié)節(jié)線線性規(guī)規(guī)劃靈靈敏度度分析析一、價價值系系數(shù)的的變動動分析析非基變變量Cj的變化化范圍圍非基變變量Cj變化，，只影影響它它自己己的檢檢驗數(shù)數(shù)Cj35000比值CBXBbx1x2x3x4x50x380014/3-2/35x250101/203x14100-2/31/3檢驗數(shù)j000-1/2-1參數(shù)Cj的變化化范圍圍：價值系系數(shù)Cj變化影影響檢檢驗數(shù)數(shù)60第四節(jié)節(jié)線線性規(guī)規(guī)劃靈靈敏度度分析析一、價價值系系數(shù)的的變動動分析析基變量量CBl的變化化范圍圍CjC15000比值CBXBbx1x2x3x4x50x380014/3-2/35x250101/20C1x14100-2/31/3檢驗數(shù)j0002C1/3-5/2-C1/361第四節(jié)節(jié)線線性規(guī)規(guī)劃靈靈敏度度分析析二、右右端常常量的的變動動分析析參數(shù)bi的變化化范圍圍第r個個約束束的右右端項項為br，增量量br，其它它數(shù)據(jù)據(jù)不變變。新新的基基解為為只要X'B≥0，則可可保持持最優(yōu)優(yōu)基不不變。。62第3章對對偶偶規(guī)劃劃Subtitle內(nèi)容提提要第一節(jié)節(jié)對對偶偶規(guī)劃劃的數(shù)數(shù)學(xué)模模型對偶問問題的的提出出對偶規(guī)規(guī)劃的的性質(zhì)質(zhì)第二節(jié)節(jié)對對偶偶規(guī)劃劃的經(jīng)經(jīng)濟解解釋影子價價值的的內(nèi)涵涵影子價價值的的應(yīng)用用第三節(jié)節(jié)資資源源定價價的決決策案案例63第一節(jié)節(jié)對對偶規(guī)規(guī)劃的一、對偶問問題的提出出若例1中該該廠的產(chǎn)品品平銷，現(xiàn)現(xiàn)有另一企企業(yè)想租賃賃其設(shè)備。。廠方為了了在談判時時心中有數(shù)數(shù)，需掌握握設(shè)備臺時時費用的最最低價碼，，以便衡量量對方出價價，對出租租與否做出出抉擇。在這個問題題上廠長面面臨著兩種種選擇：自自行生產(chǎn)或或出租設(shè)備備。首先要要弄清兩個個問題：①合理安排排生產(chǎn)能取取得多大利利潤?②為保持利利潤水平不不降低，資資源轉(zhuǎn)讓的的最低價格格是多少？？問題①的的最優(yōu)解：：x1=4，x2=5，Z*=37。64第一節(jié)對對偶規(guī)劃的的數(shù)學(xué)模型型一、對偶問問題的提出出出讓定價假設(shè)出讓A、B、C設(shè)備所得利利潤分別為為y1、y2、y3原本用于生生產(chǎn)甲產(chǎn)品品的設(shè)備臺臺時，如若若出讓，不不應(yīng)低于自自行生產(chǎn)帶帶來的利潤潤，否則寧寧愿自己生生產(chǎn)。于是是有2y1+0y2+3y3≥3同理，對乙乙產(chǎn)品而言言，則有0y1+2y2+4y3≥5設(shè)備臺時出出讓的收益益（希望出出讓的收益益最少值））min16y1+10y2+32y3顯然還有y1，y2，y3≥065第一節(jié)對對偶規(guī)劃的的數(shù)學(xué)模型型一、對偶問問題的提出出例1的對偶偶問題的數(shù)數(shù)學(xué)模型對偶問題的的最優(yōu)解：：y1=0，y2=1/2，，y3=1，W*=37兩個問題的的目標(biāo)函數(shù)數(shù)值相等并并非偶然前者稱為線線性規(guī)劃原原問題，則則后者為對對偶問題，，反之亦然然。對偶問題的的最優(yōu)解對對應(yīng)于原問問題最優(yōu)單單純型法表表中，初始始基變量的的檢驗數(shù)的的負值。min=16y1+10y2+32y3

2y1+0y2+3y3≥3

0y1+2y2+4y3≥5y1，y2，y3≥0

S.t.maxZ=

3x1+5x22x1≤162x2≤103x1+4x2≤32x1,x2≥0S.t.66第一節(jié)對對偶規(guī)劃的的數(shù)學(xué)模型型二、對偶規(guī)規(guī)劃的性質(zhì)質(zhì)1、對稱性性定理對偶問題的的對偶問題題是原問題題。根據(jù)對偶規(guī)規(guī)劃，很容容易寫出對對偶問題的的對偶問題題模型。2、最優(yōu)優(yōu)性定理設(shè)，，分分別別為原問問題和對對偶問題題的可行行解，且且則，，分分別為為各自的的最優(yōu)解解。3.對對偶性定定理若原問題題有最優(yōu)優(yōu)解，那那么對偶偶問題也也有最優(yōu)優(yōu)解，而而且兩者的目目標(biāo)函數(shù)數(shù)值相等等。4.互互補松弛弛性最優(yōu)解的的充分必必要條件件是，，67第二節(jié)對對偶規(guī)規(guī)劃的經(jīng)經(jīng)濟解釋釋一、影子子價值的的內(nèi)涵左邊是資資源bi每增加一一個單位位對目標(biāo)標(biāo)函數(shù)Z的貢獻獻；對偶變量量yi在經(jīng)濟上上表示原原問題第第i種資源的的邊際價值值。對偶變量量的值yi*表示第i種資源的的邊際價價值，稱稱為影子價值值。若原問題題價值系系數(shù)Cj表示單位位產(chǎn)值，，則yi稱為影子價格格。若原問題題價值系系數(shù)Cj表示單位位利潤，，則yi稱為影子利潤潤。影子價格格=資源源成本+影子利利潤68第二節(jié)對對偶規(guī)規(guī)劃的經(jīng)經(jīng)濟解釋釋一、影子子價值的的內(nèi)涵影子價格格不是資資源的實實際價格格，反映映了資源源配置結(jié)結(jié)構(gòu)，其它數(shù)據(jù)據(jù)固定，，某資源源增加一一單位導(dǎo)導(dǎo)致目標(biāo)標(biāo)函數(shù)的的增量。。對資源i總存量的的評估：：購進or出讓對資源i當(dāng)前分配配量的評評估：增加or減少第一，影影子利潤潤說明增增加哪種種資源對對經(jīng)濟效效益最有有利第二，影影子價格格告知以以怎樣的的代價去去取得緊緊缺資源源第三，影影子價格格是機會會成本，，提示資資源出租租/轉(zhuǎn)讓讓的基價價第四，利利用影子子價格分分析新品品的資源源效果：：定價決決策第五，利利用影子子價格分分析現(xiàn)有有產(chǎn)品價價格變動動的資源源緊性第六，可可以幫助助分析工工藝改變變后對資資源節(jié)約約的收益益第七，可可以預(yù)知知哪些資資源是稀稀缺資源源而哪些些資源不不稀缺69第三節(jié)資資源定定價的決決策方案案例：某廠生產(chǎn)產(chǎn)甲乙產(chǎn)產(chǎn)品，（1）如如何安排排每周的的利潤為為最大?（2）如果果企業(yè)可以以不生產(chǎn)，，那資源出出讓如何定定價？甲乙資源成本資源擁有量原材料(kg)設(shè)備(工時)電力(度)943451020501360200300銷售價格(元)390352一、最優(yōu)生生產(chǎn)決策70第三節(jié)資資源定價的的決策方案案二、資源獲獲利決策如果決策者者考慮自己己不生產(chǎn)甲甲乙兩種產(chǎn)產(chǎn)品，而把把原擬用于于生產(chǎn)這兩兩種產(chǎn)品的的原材料、、設(shè)備工時時、電量資資源全部出出售給外單單位，或者者做代加工工，則應(yīng)如如何確定這這三種資源源的價格。。設(shè)原材料的的單位出讓讓獲利為y1，設(shè)備工時時的單位出出讓獲利為為y3，電量的單單位出讓獲獲利為y2。出讓決策的的線性規(guī)劃劃模型：71第4章整數(shù)數(shù)規(guī)劃Subtitle內(nèi)容提要第一節(jié)整整數(shù)規(guī)劃劃問題純整數(shù)規(guī)劃劃0-1規(guī)劃劃混合整數(shù)規(guī)規(guī)劃第二節(jié)整整數(shù)規(guī)劃劃求解分枝定界法法第三節(jié)整整數(shù)規(guī)劃劃應(yīng)用72第一節(jié)整整數(shù)規(guī)劃問問題線性規(guī)劃的的決策變量量取值可以以是任意非非負實數(shù)，，但許多實實際問題中中，只有當(dāng)當(dāng)決策變量量的取值為為整數(shù)時才才有意義例如，產(chǎn)品品的件數(shù)、、機器的臺臺數(shù)、裝貨貨的車數(shù)、、完成工作作的人數(shù)等等，分?jǐn)?shù)或或小數(shù)解顯顯然是不合合理的。要求全部或或部分決策策變量的取取值為整數(shù)數(shù)的線性規(guī)規(guī)劃問題，，稱為整數(shù)數(shù)規(guī)劃(IntegerProgramming)。全部決策變變量的取值值都為整數(shù)數(shù)，則稱為為全整數(shù)規(guī)規(guī)劃(AllIP)僅要求部分分決策變量量的取值為為整數(shù)，則則稱為混合合整數(shù)規(guī)劃劃(MixedIP)要求決策變變量只取0或1值，，則稱0-1規(guī)劃(0-1Programming)73第一節(jié)整整數(shù)規(guī)劃問問題一、純整數(shù)數(shù)規(guī)劃產(chǎn)品資源甲乙現(xiàn)有量A219B5735單臺利潤65例：某企業(yè)利用用材料和設(shè)設(shè)備生產(chǎn)甲甲乙產(chǎn)品，，其工藝消消耗系數(shù)和和單臺產(chǎn)品品的獲利能能力如下表表所示：問如何安排排甲、乙兩兩產(chǎn)品的產(chǎn)產(chǎn)量，使利利潤為最大大。解：設(shè)x1為甲產(chǎn)品的的臺數(shù)，x2為乙產(chǎn)品的的臺數(shù)。maxZ=6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整數(shù)74第一節(jié)整整數(shù)規(guī)劃問問題二、0-1規(guī)劃登山隊員可可攜帶最大大重量為25公斤。。問都帶哪哪些物品的的重要性最最大。解：對于每每一種物品品無非有兩兩種狀態(tài)，，帶或者不不帶，不妨妨設(shè)序號1234567物品食品氧氣冰鎬繩索帳篷相機設(shè)備重量55261224重要性系數(shù)2015181484100-1規(guī)劃劃的模型：：75第一節(jié)整整數(shù)規(guī)劃問問題三、混合整整數(shù)規(guī)劃例：某產(chǎn)品有n個區(qū)域市市場，各區(qū)區(qū)域市場的的需求量為為bj噸/月；現(xiàn)現(xiàn)擬在m個個地點中選選址建生產(chǎn)產(chǎn)廠，一個個地方最多多只能建一一家工廠；；若選i地建廠，生生產(chǎn)能力為為ai噸/月，其其運營固定定費用為F元/月；；已知址i至j區(qū)域域市場的運運價為cij元/噸。如如何選址和和安排調(diào)運運，可使總總費用最小?。拷猓哼x址建廠與與否是個0-1型決決策變量，，假設(shè)yi=1，選擇擇第i址建廠，yi=0，不選選擇第i址建廠；計劃從i址至區(qū)域市市場j的運輸運量xij為實數(shù)型決決策變量。。76第二節(jié)整整數(shù)規(guī)劃求求解一、舍入化化整法為了滿足整整數(shù)解的要要求，自然然想到“舍舍入”或““截尾”處處理，以得得到與最優(yōu)優(yōu)解相近的的整數(shù)解。。這樣做除少少數(shù)情況外外，一般不不可行，因因為化整后后的解有可可能超出了了可行域，，成為非可可行解；或或者雖是可可行解，卻卻不是最優(yōu)優(yōu)解。不考慮整數(shù)數(shù)約束則是是一個LP問題,稱稱為原整數(shù)數(shù)規(guī)劃的松松弛問題對于例1的的數(shù)學(xué)模型型，不考慮慮整數(shù)約束束的最優(yōu)解解：x1*=28/9，x2*=25/9，Z*=293/9舍入化整x1=3，x2=3，Z=33，不不滿足約束束條件5x1+7x2≤35，非非可行解；；x1=3，x2=2，Z=28，滿足足約束條件，，是可行解，，但不是最優(yōu)優(yōu)解；x1=4，x2=1，Z=29，滿足足約束條件，，才是最優(yōu)解解。77第二節(jié)整數(shù)數(shù)規(guī)劃求解二、窮舉整數(shù)數(shù)法對于決策變量量少，可行的的整數(shù)解又較較少時，這種種窮舉法有時時是可行的，，并且也是有有效的。但對于大型的的整數(shù)規(guī)劃問問題，可行的的整數(shù)解數(shù)量量很多，用窮窮舉法求解是是不可能的。。例如，指派問問題。5x1+7x2=352x1+x2=9?(3,3)??????????x1x212312534478第二節(jié)整數(shù)數(shù)規(guī)劃求解三、分支定界界法不考慮整數(shù)限限制，先求出出相應(yīng)線性規(guī)規(guī)劃的最優(yōu)優(yōu)解，若求得的最優(yōu)優(yōu)解符合整數(shù)數(shù)要求，則是是原IP的最最優(yōu)解；若不滿足整數(shù)數(shù)條件，則任任選一個不滿滿足整數(shù)條件件的變量來構(gòu)構(gòu)造新的約束束，在原可行行域中剔除部部分非整數(shù)解解。依次在縮小的的可行域中求求解新構(gòu)造的的線性規(guī)劃的的最優(yōu)解，直直到獲得原整整數(shù)規(guī)劃的最最優(yōu)解。定界的含義：：IP是在相應(yīng)應(yīng)的LP基礎(chǔ)礎(chǔ)上增加整數(shù)數(shù)約束IP的最優(yōu)解解不會優(yōu)于相相應(yīng)LP的最最優(yōu)解對MaxZ，，相應(yīng)LP的的Z*是原IP的上上界79第二節(jié)整數(shù)數(shù)規(guī)劃求解三、分支定界界法x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3x2≤3x2≥480第三節(jié)整數(shù)數(shù)規(guī)劃應(yīng)用一、生產(chǎn)基地地規(guī)劃例：某公司擬建設(shè)設(shè)A、B兩種種類型的生產(chǎn)產(chǎn)基地若干個個，兩種類型型的生產(chǎn)基地地每個占地面面積，所需經(jīng)經(jīng)費，建成后后生產(chǎn)能力及及現(xiàn)有資源情情況如下表所所示。問A、、B類型基地地各建設(shè)多少少個，可使總總生產(chǎn)能力最最大？解：設(shè)A、B兩類基地各各建設(shè)x1,x2個，則其模型型為：81第三節(jié)整數(shù)數(shù)規(guī)劃應(yīng)用二、人員安排排規(guī)劃某服務(wù)部門各各時段(每2小時為一時時段)需要的的服務(wù)人數(shù)如如表：解：設(shè)第j時段開始時上上班的服務(wù)員員人數(shù)為xj第j時段來上班的的服務(wù)員將在在第j+3時時段結(jié)束時時下班，故決決策變量有x1,x2,x3,x4,x5。按規(guī)定，服務(wù)務(wù)員連續(xù)工作作8小時(4個時段)為為一班。請安安排服務(wù)員的的工作時間，，使服務(wù)員總總數(shù)最少.82第三節(jié)整數(shù)數(shù)規(guī)劃應(yīng)用三、項目投資資選擇有600萬元元投資5個項項目，收益如如表，求利潤潤最大的方案案？83第三節(jié)整數(shù)數(shù)規(guī)劃應(yīng)用四、互斥約束束問題例如關(guān)于煤資資源的限制，，其約束條件件為：企業(yè)也可以考考慮采用天然然氣進行加熱熱處理：這兩個條件是是互相排斥的的。引入0——1變量y，，令互斥問題可由由下述的條件件來代替，其其中M是充分分大的數(shù)。84第三節(jié)整數(shù)數(shù)規(guī)劃應(yīng)用五、租賃生產(chǎn)產(chǎn)問題服裝公司租用用生產(chǎn)線擬生生產(chǎn)T恤、襯襯衫和褲子。。每年可用勞動動力8200h，布料8800m2。T恤襯衫褲子勞動力326布料售價250400600可變成本100180300生產(chǎn)線租金(萬)201510假設(shè)：yj=1，要租用用生產(chǎn)線jyi=0，不租用用生產(chǎn)線j第j種服裝生產(chǎn)量量xj85第三節(jié)整數(shù)數(shù)規(guī)劃應(yīng)用六、任務(wù)指派派問題甲乙丙丁四個個人，ABCD四項任務(wù)務(wù)，如何指派派總時間最短短？解：引入0-1變量xij，xij=1：任務(wù)j指派人員i去完成xij=0：任務(wù)j不派人員i去完成一項任務(wù)只由由一個人完成成一人只能完成成一項任務(wù)86第三節(jié)整數(shù)數(shù)規(guī)劃應(yīng)用七、設(shè)施選址址問題擬定在2個地地點中選址設(shè)設(shè)立分銷中心心，執(zhí)行產(chǎn)品品的倉儲和轉(zhuǎn)轉(zhuǎn)運，一個分分銷中心擬定定設(shè)立一個倉倉庫W1、W2。若設(shè)立立倉庫庫W1，建設(shè)設(shè)成本本為10萬萬元，，最大大庫容容為20萬萬臺，，單位位產(chǎn)品品的月月庫存存成本本為2元；；若設(shè)立立倉庫庫W2建造成成本為為20萬元元，最最大庫庫容為為25萬臺臺，單單位產(chǎn)產(chǎn)品的的月庫庫存成成本為為3元元。如何選選址和和安排排調(diào)運運，建建造費費用+運輸輸費用用+倉倉儲費費用為為最小??？解：設(shè)設(shè)從供供貨源源Si到分銷銷中心心Wj的運輸輸量為為xij，從分分銷中中心到到需需求市市場Rk的運輸輸量為為yjk。倉庫庫選址址決策策引入入0-1變變量wj：87第三節(jié)節(jié)整整數(shù)規(guī)規(guī)劃應(yīng)應(yīng)用七、設(shè)設(shè)施選選址問問題供應(yīng)能能力平平衡約約束：：市場需需求平平衡約約束：：倉儲能能力限限制約約束：：分銷中中心不不存留留產(chǎn)品品：所有變變量大大于等等于零零：88第5章目目標(biāo)標(biāo)規(guī)劃劃Subtitle內(nèi)容提提要第一節(jié)節(jié)多多目目標(biāo)規(guī)規(guī)劃問問題第二節(jié)節(jié)目目標(biāo)標(biāo)規(guī)劃劃數(shù)學(xué)學(xué)模型型目標(biāo)的