運籌學(xué)（廣東外語外貿(mào)大學(xué)）

現(xiàn)代管理科學(xué)的重要基礎(chǔ)和手段經(jīng)濟(jì)和管理的重要工具具有適用性強(qiáng),應(yīng)用面廣的特點廣東外語外貿(mào)大學(xué)GuangdongUniversityofForeignStudies課程目的我們學(xué)習(xí)這門課程的目的是要樹立優(yōu)化思想,認(rèn)識運籌學(xué)對實現(xiàn)管理的科學(xué)化和現(xiàn)代化的重要意義和作用,掌握運籌學(xué)的基本思想和方法,并能結(jié)合相關(guān)軟件的使用解決管理中的實際問題。運籌學(xué)主導(dǎo)教材和主要參考書主導(dǎo)教材:《管理運籌學(xué)》（第2版）,韓伯棠編著,高等教育出版社。主要參考書:ll></a>.《運籌學(xué)》（修訂版）,錢頌迪主編,清華大學(xué)出版社;.《數(shù)據(jù)模型與決策》（第11版）,DavidR.Anderson,etc.,侯文華等譯，機(jī)械工業(yè)出版社;.《運籌學(xué)教程》,胡運權(quán)主編,清華大學(xué)出版社.《運籌學(xué)模型與方法教程》,程理民等,清華大學(xué)出版社;.《運籌學(xué)應(yīng)用案例集》，胡運權(quán)主編,清華大學(xué)出版社;.《運籌學(xué)模型與方法教程例題分析與解題》，劉滿鳳等,清華大學(xué)出版社;.《運籌學(xué)方法及其微機(jī)實現(xiàn)》,汪遐昌,電子科技大學(xué)出版社。主要參考期刊及網(wǎng)站《運籌與管理》,中國運籌學(xué)會《運籌學(xué)學(xué)報》，中國運籌學(xué)會《系統(tǒng)工程理論與實踐》,中國系統(tǒng)工程學(xué)會《系統(tǒng)工程》，湖北省系統(tǒng)工程學(xué)會中國運籌學(xué)會運籌學(xué)網(wǎng)絡(luò)資源導(dǎo)航OperationsResearchEuropeanJournalofOperationalResearchhttp://J/is/Navigation/Mathematics/operations.htmhttp://.ors43x/a>/第一章緒論§1決策、定量分析與管理運籌學(xué)§2運籌學(xué)的分支§3運籌學(xué)在工商管理中的應(yīng)用§4學(xué)習(xí)運籌學(xué)必須使用相應(yīng)的計算機(jī)軟件,必須注重于學(xué)以致用的原則第一章緒論“運籌學(xué)”的釋義運籌學(xué)（OperationalResearch（英式）；OperationsResearch（美式））直譯為“運作研究”、“作業(yè)研究”或“運用研究”,簡稱0R。中文“運籌”二字取自《史記??高祖本記》中,劉邦“夫運籌帷幄之中，決勝于千里之外,吾不如子房”。運籌學(xué)是ー門決策科學(xué),優(yōu)化科學(xué)。第一章緒論我國古代運籌思想運用的典故.“田忌賽馬”“田忌賽馬”是家喻戶曉的歷史故事。戰(zhàn)國時齊威王與齊相田忌賽馬,雙方各出三匹馬比賽,每勝…場贏得一千金。由于王府的馬比相府的馬好,所以田忌每次比賽都要輸?shù)羧Ы?。后來田忌的謀士孫臏獻(xiàn)了一計:在每次開賽前要求對方先報馬名,由此區(qū)分對方參賽的是上馬、中馬還是下馬;然后以自己的上馬對對方的中馬、自己的中馬對對方和下馬、自己的下馬對對方的上馬。這樣,兩勝?負(fù)反而贏得一千金。第一章緒論我國古代運籌思想運用的典故.晉國公重建皇城晉國公重建皇城的施工方案,體現(xiàn)了運籌學(xué)的樸素思想。要使重建工程的各個エ序,在時間、空間上彼此協(xié)調(diào),環(huán)環(huán)相扣,就需要運用行列式的相關(guān)知識,進(jìn)行精確計算.點擊圖連接相關(guān)網(wǎng)頁第一章緒論運籌學(xué)的產(chǎn)生和發(fā)展運籌學(xué)作為ー門系統(tǒng)的科學(xué),產(chǎn)生的背景為第二次世界大戰(zhàn)。主要用于解決如何在與德軍的對抗中最大限度地殺傷敵人,減少損失。二戰(zhàn)期間英國為解決空襲的早期預(yù)警,作好反侵略戰(zhàn)爭準(zhǔn)備,積極進(jìn)行‘‘雷達(dá)”的研究。但隨著雷達(dá)性能的改善和配置數(shù)量的增多,出現(xiàn)了來自不同雷達(dá)站的信息以及雷達(dá)站同整個作戰(zhàn)系統(tǒng)的協(xié)調(diào)配合問題。第一章緒論1938年7月,波得塞(Bawdsey)雷達(dá)站的負(fù)責(zé)人羅伊(A.P.Rowe)提出立即進(jìn)行整個防空作戰(zhàn)系統(tǒng)運行的研究,并用“OperationalResearch"ー詞作為這方面研究的描述,這就是OR名詞的起源。1940年9月英國成立了由物理學(xué)家布萊克特(P.M.S.Blackett)領(lǐng)導(dǎo)的第一個運籌學(xué)小組，后來發(fā)展到每ー個英軍指揮部都成立運籌學(xué)小組。1942年美國和加拿大也都相繼成立運籌學(xué)小組。這些小組在確定擴(kuò)建艦隊規(guī)模、開展反潛艇戰(zhàn)偵察和組織有效對敵轟炸等方面作了大量研究,為取得反法西斯戰(zhàn)爭的勝利及運籌學(xué)有關(guān)分支的建立作出了貢獻(xiàn)。第一章緒論運籌學(xué)在第二次世界大戰(zhàn)中成功運用的例子:如雷達(dá)的設(shè)置、運輸船隊的護(hù)航、反潛作戰(zhàn)中深水炸彈的深度、飛行員的編組、軍事物資的存儲等。典型戰(zhàn)例:.不列顛之戰(zhàn).盟軍封鎖直布羅陀海峽第一章緒論不列顛之戰(zhàn)1941年,希特勒為了實施在英倫三島登陸的計劃,命令德國空軍輪番對英國進(jìn)行狂轟濫炸。當(dāng)時英國皇家空軍以ー比七的數(shù)量劣勢迎戰(zhàn),為此需要盡可能地保持飛機(jī)處于飛行狀態(tài)。于是,空軍司令部規(guī)定保持70%的飛機(jī)在天上巡邏。但是,英軍很快發(fā)現(xiàn)要保持這么高的飛行比例有困難,因為飛機(jī)的被擊落的、有需要維修的,飛行員也有傷亡。這ー決策的后果是在空中飛行的飛機(jī)數(shù)量越來越少。第一章緒論不列顛之戰(zhàn)究竟保持多大比例的飛機(jī)在巡邏才能持久作戰(zhàn)呢?OR小組的專家紛紛研究這個問題,這個問題最后被生物學(xué)家康頓解決了。他根據(jù)計算生物平均壽命的方法,運用飛機(jī)飛行時間、維修時間、空戰(zhàn)特點和飛機(jī)被落擊傷狀況等數(shù)據(jù),得出的結(jié)論是:只要保持35%的飛機(jī)在飛行狀態(tài),就能使全部飛機(jī)的飛行戰(zhàn)斗時間最多。這?研究成果為取得不列顛之戰(zhàn)的勝利作出了貢獻(xiàn)。盟軍封鎖直布羅陀海峽（獵潛戰(zhàn)例）1944年初,為幫助美國海軍在連接大西洋和地中海的直布羅陀海峽封鎖過往的德軍潛艇,美軍OR小組的約翰?佩芝姆博士提出了一種“屏障巡邏”飛行戰(zhàn)術(shù)。第一章緒論盟軍封鎖直布羅陀海峽（獵潛戰(zhàn)例）在深水航道的最窄處劃出ー個4英里長、1英里寬的長方形,兩架飛機(jī)保持在長方形兩邊線的對稱位置上，同時以115英里/小時的速度繞長方形飛行。這樣,在長方形上的每一點,每隔3分鐘就有ー架飛機(jī)巡邏通過。潛艇通過這個區(qū)域時,巡邏的飛機(jī)至少有兩次機(jī)會去發(fā)現(xiàn)它。就這樣,在2月24日到3月16日短短三個星期內(nèi),ー個巡邏機(jī)中隊擊沉擊傷德軍潛艇3艘,自己無一傷亡。第一章緒論第一章緒論二戰(zhàn)以后,運籌學(xué)得到了快速的發(fā)展,形成了許多分支,并且計算機(jī)的應(yīng)用極大地推動了運籌學(xué)的應(yīng)用與普及。運籌學(xué)有廣泛應(yīng)用運籌學(xué)不僅在軍事上,而且在生產(chǎn)、決策、運輸、存儲等經(jīng)濟(jì)管理領(lǐng)域有著廣泛的應(yīng)用。第一章緒論運籌學(xué)的定義運籌學(xué)是運用分析，試驗,量化的方法,對經(jīng)濟(jì)管理系統(tǒng)中人、財、物（時間）等有限資源,進(jìn)行統(tǒng)籌安排,為決策者提供有依據(jù)的最優(yōu)方案（滿意方案），以實現(xiàn)最有效地管理?！吨袊髽I(yè)管理百科全書》《辭?！穼\籌學(xué)解釋為:“二十世紀(jì)四十年代開始形成的一門科學(xué)，主要研究經(jīng)濟(jì)活動與軍事活動中能用數(shù)量來表達(dá)的有關(guān)運用,籌劃與管理方面的問題,它根據(jù)問題的要求,通過數(shù)學(xué)的分析與運算，作出綜合性的合理的安排,以達(dá)到較經(jīng)濟(jì)、較有效地使用人カ、物力。近年來,它在理論與應(yīng)用方面都有較大發(fā)展。其主要分支有規(guī)劃論、對策論、排隊論及質(zhì)量控制等?！钡谝徽戮w論運籌學(xué)的特點⑴科學(xué)性:運籌學(xué)是以研究事物內(nèi)在規(guī)律,并從定量分析的角度探求更好地解決問題的?門科學(xué)。第一章緒論運籌學(xué)的特點⑵應(yīng)用性:運籌學(xué)既對各種經(jīng)營進(jìn)行創(chuàng)造性的科學(xué)研究,又涉及到組織的實際管理問題,它具有很強(qiáng)的實踐性，最終應(yīng)能向決策者提供建設(shè)性意見,并應(yīng)收到實效;第一章緒論運籌學(xué)的特點⑶多學(xué)科的交叉性、綜合性:運籌學(xué)研究中吸收了來自不同領(lǐng)域的經(jīng)驗,并被廣泛應(yīng)用于工商企業(yè)、軍事部門、民政事業(yè)等研究組織內(nèi)的統(tǒng)籌協(xié)調(diào)問題,故其應(yīng)用不受行業(yè)、部門之限制;第一章緒論運籌學(xué)的特點⑷系統(tǒng)性和最優(yōu)性:它以整體最優(yōu)為目標(biāo),從系統(tǒng)的觀點出發(fā),力圖以整個系統(tǒng)最佳的方式來解決該系統(tǒng)各部門之間的利害沖突。對所研究的問題求出最優(yōu)解,尋求最佳的行動方案,所以它也可看成是ー門優(yōu)化技術(shù),提供的是解決各類問題的優(yōu)化方法。策、定量分析與管理運籌學(xué)決策的定義ーー現(xiàn)代管理科學(xué)創(chuàng)始人,諾貝爾獎金獲得者世界著名經(jīng)濟(jì)學(xué)家西蒙（H.A.Simon）：管理就是決策?！袊鐣茖W(xué)院副院長于光遠(yuǎn):決策就是作決定。ー為了實現(xiàn)一定目標(biāo),運用科學(xué)的理論和方法,系統(tǒng)地分析主、客觀條件,在掌握大量有關(guān)信息的基礎(chǔ)上,提出若干預(yù)選方案并從中選擇出最優(yōu)方案（滿意方案）的分析判斷過程（科學(xué)的決策）。1.1決策、定量分析與管理運籌學(xué)決策方法定性分析方法——借助決策者的知識、經(jīng)驗、分析和判斷能力等進(jìn)行決策的方法。定量分析方法——量化決策問題并建立數(shù)學(xué)模型進(jìn)行決策的方法。定性與定量相結(jié)合的分析方法學(xué)習(xí)運籌學(xué)能夠培養(yǎng)和提高定量分析能力解決問題與制定決策明確問題確定目標(biāo)提出方案分析方案選擇方案實施方案分析結(jié)果解決問題決策決策結(jié)果評估各個方案:解的檢驗、靈敏性分析等。確定目標(biāo)或評估方案的標(biāo)準(zhǔn)執(zhí)行此方案:回到實踐中進(jìn)行后評估：考察問題是否得到圓滿解決.不滿意檢查運籌學(xué)的分支線性規(guī)劃整數(shù)（線性）規(guī)劃目標(biāo)規(guī)劃圖與網(wǎng)絡(luò)模型排序與統(tǒng)籌方法存儲論決策分析排隊論對策論動態(tài)規(guī)劃預(yù)測?非線性規(guī)劃、多目標(biāo)規(guī)劃、隨機(jī)規(guī)劃、模糊規(guī)劃等運籌學(xué)在工商管理中的應(yīng)用生產(chǎn)計劃:生產(chǎn)作業(yè)的計劃、日程表的編排、合理下料、配料問題、物料管理等;庫存管理:多種物資庫存量的管理,庫存方式、庫存量等;運輸問題:確定最小成本的運輸線路、物資的調(diào)撥、運輸工具的調(diào)度以及建廠地址的選擇等;人事管理:對人員的需求和使用的預(yù)測,確定人員編制、人員合理分配,建立人オ評價體系等;運籌學(xué)在工商管理中的應(yīng)用市場營銷:廣告預(yù)算、媒介選擇、定價、產(chǎn)品開發(fā)與銷售計劃制定等；財務(wù)和會計:預(yù)測、貸款、成本分析、定價、證券管理、現(xiàn)金管理等;***設(shè)備維修、更新,項目選擇、評價,工程優(yōu)化設(shè)計與管理等;§1.3運籌學(xué)在工商管理中的應(yīng)用由國際運籌與管理科學(xué)協(xié)會(INFORMS)和它的管理科學(xué)實踐學(xué)會(CollegeforthePracticeoftheManagementSciences)主持評獎的負(fù)有盛名的弗蘭茨?厄德曼(FranyEdlman)獎,就是為獎勵優(yōu)秀的運籌學(xué)在管理中的應(yīng)用的成就設(shè)立的,該獎每年舉行ー次,在對大量富有競爭力的入闈者進(jìn)行艱苦的評審后,一般有六位優(yōu)勝者獲獎。關(guān)于這些獲獎項目的文章都在第二年發(fā)表在著名刊物Interface的第一期上,下面列表就是發(fā)表在Interface期刊的ー些獲獎項目。更優(yōu)的服務(wù)1ーレ1993安裝統(tǒng)計銷售預(yù)測和成品庫存管理系統(tǒng),改進(jìn)客戶服務(wù)Merit青銅制品公司第一年7.5億1-2/2000重組全球供應(yīng)鏈,保持最小庫存的同時滿足客戶需求IBM1億1-M994進(jìn)行上千個國內(nèi)航線的飛機(jī)優(yōu)化配置來最大化利潤Delta航空公司1500萬更多年收入101998制定最優(yōu)鐵路時刻表并調(diào)整鐵路日運營量法國國家鐵路2億1-M997重新設(shè)計北美生產(chǎn)和分銷系統(tǒng)以降低成本并加快了市場進(jìn)入速度寶潔公司生產(chǎn)率提高50%以上11/1975第二部分通過戰(zhàn)略調(diào)整,縮短維修機(jī)器的反應(yīng)時間,改進(jìn)維修人員的生產(chǎn)率施樂公司380萬17/1981控制成品庫存（制定最優(yōu)再訂購點和訂購量,確保安全庫存）標(biāo)準(zhǔn)品牌公司4.06億,更多銷售1ーレ1990優(yōu)化商業(yè)用戶的電話銷售中心選址AT&T4000萬121987優(yōu)化商業(yè)區(qū)和辦公樓銷售程序荷馬特發(fā)展公司7000萬1-7/1987優(yōu)化煉油程序及產(chǎn)品供應(yīng)、配送及營銷Citgo石油600萬1-y1986滿足乘客需求前提下,以最低成本進(jìn)行訂票及安排機(jī)場工作班次聯(lián)合航空公司每年節(jié)支（美元）Interface應(yīng)用組織運籌學(xué)方法使用情況（美1983）運籌學(xué)方法在中國使用情況（隨機(jī)抽樣）運籌學(xué)的發(fā)展趨勢面向問題服務(wù)行業(yè)中的應(yīng)用金融服務(wù)業(yè)信息、電信服務(wù)業(yè)醫(yī)院管理后勤（Logistics）全球供應(yīng)鏈管理電子商務(wù):集成特性§1.3運籌學(xué)在工商管理中的應(yīng)用運籌學(xué)的發(fā)展趨勢運籌學(xué)與行為科學(xué)結(jié)合群決策和談判對策理論多層規(guī)劃合理性分析隨機(jī)和模糊OR問題本身的不確定性人類知識的局限性§1.3運籌學(xué)在工商管理中的應(yīng)用運籌學(xué)的發(fā)展趨勢軟計算面向強(qiáng)復(fù)雜系統(tǒng)的計算、實時控制、知識推理智能算法:模擬退火、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)、戒律算法等系統(tǒng)仿真IT對運籌學(xué)的影響MIS,DSS,MRP-II,CIMS,ERPORDept.->Dept.OfOR&IS§1.3運籌學(xué)在工商管理中的應(yīng)用§1.4學(xué)習(xí)管理運籌學(xué)必須使用相應(yīng)的計算機(jī)軟件,必須注重于學(xué)以致用的原則學(xué)習(xí)運籌學(xué)要結(jié)合實際的應(yīng)用,不要被ー些概念、理論的困難嚇倒。學(xué)習(xí)運籌學(xué)要把注意力放在“結(jié)合實際問題建立運籌學(xué)模型”和“解決問題的方案或模型的解”兩頭,中間的計算過程盡可能讓計算機(jī)軟件去完成。本書附有運籌學(xué)教學(xué)軟件,使用方法很簡單。學(xué)員必須盡快學(xué)會使用這個運籌學(xué)教學(xué)軟件,并借助它來學(xué)好本課程。學(xué)習(xí)運籌學(xué)是為了用于實踐,解決實際問題。以前重視人工計算是因為沒有計算機(jī),現(xiàn)在有了就應(yīng)該好好利用。謝謝大家第一章緒論廣東外語外貿(mào)大學(xué)GuangdongUniversityofForeignStudies的提出解法解法的靈敏度分析第二章線性規(guī)劃的圖解法第二章線性規(guī)劃的圖解法解決以下兩類問題資源一定 產(chǎn)出最大（產(chǎn)出:如產(chǎn)量、銷售量、利潤等）任務(wù)一定 投入最?。ㄍ度?如資金、人員、時間、原材料等）線性規(guī)劃（Linearprogram,LP）在工商管理,生產(chǎn)計劃安排,交通運輸,財貿(mào)工作等各項經(jīng)濟(jì)活動中，如何應(yīng)用科學(xué)的方法統(tǒng)籌安排，合理利用資源（包括人力、物力、財力等資源）,并使其經(jīng)濟(jì)效益達(dá)到最優(yōu),這些正是現(xiàn)代社會生產(chǎn)規(guī)模日益擴(kuò)大以及各部門和各系統(tǒng)之間的關(guān)系日益復(fù)雜所面臨的新問題。1939年前蘇聯(lián)數(shù)學(xué)家康托洛維奇提出了生產(chǎn)組織與計劃中的線性規(guī)劃（LinearProgramming簡寫為:LP）模型，為以上問題的解決提出了一種可行的方法。四十年代末旦茨基和查恩斯等人提出的線性規(guī)劃問題求解方法一單純形法,為線性規(guī)劃的理論和應(yīng)用奠定了基礎(chǔ),這些都是線性規(guī)劃的最卓著的開創(chuàng)性工作?！?.1線性規(guī)劃問題的提出線性規(guī)劃是研究在線性不等式或等式的限制條件下,使得某ー個線性目標(biāo)函數(shù)取得最大（或最?。┑膯栴}。常見的線性規(guī)劃問題有：（―）運輸問題（二）生產(chǎn)的組織與計劃問題（三）合理下料問題（四）配料問題（五）布局問題（六）分派問題線性規(guī)劃研究的內(nèi)容和問題§2.1線性規(guī)劃問題的提出線性規(guī)劃與其它現(xiàn)代技術(shù)或方法相結(jié)合產(chǎn)生新的定量分析的技術(shù)已成為當(dāng)前出現(xiàn)的ー個極為重要的發(fā)展趨勢。特別是隨著計算機(jī)的出現(xiàn),線性規(guī)劃與計算機(jī)結(jié)合形成的應(yīng)用軟件已成為了流行的“商業(yè)工具”。據(jù)美國商業(yè)和科學(xué)計算中心的研究可知,線性規(guī)劃的計算機(jī)應(yīng)用軟件已獲得了數(shù)十億的經(jīng)濟(jì)效益,有很高的市場價值。預(yù)計在下ー個十年里,線性規(guī)劃與計算機(jī)的分界線將會逐漸消失，并將脫離各自原來的領(lǐng)域,組合成更通用和應(yīng)用面更廣泛的應(yīng)用科學(xué)的形式。線性規(guī)劃發(fā)展前景§2.1線性規(guī)劃問題的提出另一方面,以線性規(guī)劃為基礎(chǔ)而發(fā)展起來的多部門的線性規(guī)劃,多時期的線性規(guī)劃,模糊線性規(guī)劃,隨機(jī)線性規(guī)劃,以及整數(shù)規(guī)劃,非線性規(guī)劃,目標(biāo)規(guī)劃等等,為現(xiàn)代管理中各類實際問題的解決提供了科學(xué)的方法。目前線性規(guī)劃的理論研究仍十分活躍,其應(yīng)用前景也越來越廣闊,它已成為國家重點推廣的現(xiàn)代管理方法之…。線性規(guī)劃發(fā)展前景§2.1線性規(guī)劃問題的提出例1.某工廠在計劃期內(nèi)要安排I、II兩種產(chǎn)品的生產(chǎn),已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、資源的限制，如下表:問題:エ廠應(yīng)分別生產(chǎn)多少單位I、II產(chǎn)品才能使工廠獲利最多?問題分析:如何安排I、II兩種產(chǎn)品的生產(chǎn)使得エ廠獲利最大?設(shè)定決策變量:設(shè)I、II產(chǎn)品的產(chǎn)量分別為xl,x2目標(biāo):獲利最大的利潤制約條件：生產(chǎn)能力和原材料的供給量例1.某工廠在計劃期內(nèi)要安排I、II兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、資源的限制,如下表:問題:エ廠應(yīng)分別生產(chǎn)多少單位i、n產(chǎn)品才能使工廠獲利最多?線性規(guī)劃模型（I、H產(chǎn)品的產(chǎn)量分別為xl,x2）：目標(biāo)函數(shù):Maxz=50xl+100x2約束條件:s.t. xl+x2W3002x1+x2く400x2く250xl,x2三0LP模型三要素?決策變量ー約束條件（線性等式或線性不等式）?目標(biāo)函數(shù)（線性函數(shù),最大化或最小化）§2.1線性規(guī)劃問題的提出生產(chǎn)組織與決策問題例2.某汽車エ廠可生產(chǎn)大轎車和載重汽車,已知生產(chǎn)每輛汽車所用的鋼材均為2噸,該廠每年供應(yīng)的鋼材為1600噸,生產(chǎn)能力為每2.5小時生產(chǎn)ー?輛載重汽車,每5小時生產(chǎn)ーー輛大汽車,工廠全年有效工時為2500小時;已知供應(yīng)給該廠大轎車用的座椅每年可裝配400輛。據(jù)市場調(diào)查,出售ー輛大轎車可獲利4千元,出售ー輛載重車可獲利3千元。問在這些條件下,如何安排生產(chǎn)使得エ廠獲利最大?§2.1線性規(guī)劃問題的提出分析：問題是如何安排生產(chǎn)使得エ廠獲利最大?設(shè)大轎車和載重車的產(chǎn)量分別為xl和x2（輛）,則34利潤（千元??輛）（噸??輛）2.5（小時??輛）載重車1600（噸）2500（小時??年）提供量4002（噸??輛）5（小時??輛）大轎車裝配座椅（輛??年）鋼材生產(chǎn)能力項目產(chǎn)品解:原材料的限制:工時的限制:大轎車座椅的限制:非負(fù)限制:分析：問題是如何安排生產(chǎn)使得エ廠獲利最大?3利潤（千元??輛）22.5（小時??輛）載重車16002500（小時??年）提供量40025（小時??輛）大轎車裝配座椅（輛??年）鋼材（噸）生產(chǎn)能力項目產(chǎn)品目標(biāo):利潤最大因此該問題的數(shù)學(xué)模型為:目標(biāo)函數(shù)約束條件§2.1線性規(guī)劃問題的提出實際問題LP模型最優(yōu)解線性規(guī)劃問題的提出建模過程.理解要解決的問題,了解解題的目標(biāo)和條件;.定義決策變量（xl,x2，…，xn）,每ー組值表示-?個方案;.用決策變量的線性函數(shù)形式寫出目標(biāo)函數(shù),確定最大化或最小化目標(biāo);.用ー組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件一般形式目標(biāo)函數(shù): Max（Min）z=clxl+c2x2+???+cnxn約束條件:s.t.allxl+al2x2+???+alnxnく（=,2）bla21xl+a22x2+…+a2nxnく（ラ2）b2amixl+am2x2+,,,+amnxnW(ラ2)bmxl,x2,???,xn20線性規(guī)劃問題的提出2.2圖解法例1.目標(biāo)函數(shù)：Maxz=50x1+100x2約束條件：xl+x2W300(A)2x1+x2く400(B)x2.250(〇xl20 (D)(E)x220(E)得到最優(yōu)解:xl=50,x2=250最優(yōu)目標(biāo)值z=27500對于只有兩個決策變量的線性規(guī)劃問題,可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問題的有關(guān)概念,并求解。下面通過例1詳細(xì)講解其方法:100元50元單位產(chǎn)品獲利250千克10原料B400千克12原料A300臺時11設(shè)備資源限制III§2.2圖解法(1)分別取決策變量XI,X2為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里,圖上任意一點的坐標(biāo)代表了決策變量的ー組值,例1的每個約束條件都代表ー個半平面。x2xlX220X2=0x2xlXl^OX1=O§2.2圖解法（2）對每個不等式（約束條件）,先取其等式在坐標(biāo)系中作直線,然后確定不等式所決定的半平面。100200300100200300xl+x2<300xl+x2=3001001002002xl+x2く4002xl+x2=400300200300400§2.2圖解法（3）把五個圖合并成一個圖,取各約束條件的公共部分,如圖2-1所示。100x2く250x2=250200300200300xlx2x2=0xl=0x2=250xl+x2=3002xl+x2=400圖2-1(4)目標(biāo)函數(shù)z=50xl+100x2,當(dāng)z取某ー固定值時得到一條直線,直線上的每一點都具有相同的目標(biāo)函數(shù)值,稱之為“等值線”。平行移動等值線,當(dāng)移動到B點時,z在可行域內(nèi)實現(xiàn)了最大化。A,B,C,D,E是可行域的頂點,對有限個約束條件則其可行域的頂點也是有限的。xlx2z=20000=50xl+100x2圖2-2z=27500=50xl+100x22=0=50x1+100x2z=10000=50xl+100x2CBAD圖解法的運算步驟0xlx2別以L.P.模型中的兩個變量為橫軸和豎軸建立平面直角坐標(biāo)系（例如可以以例1中的xl為橫軸,以x2為豎軸）。2圖解法2.2圖解法例1.maxZ=xl+3x2s.t.xl+x2く6?xl+2x2く8xl20,x220可行域64-860xlx22.在所建立的平面坐標(biāo)系中畫出約束條件所圍成的區(qū)域圖形ーー可行（解集）域（thefeasibleregion）,并將其用陰影表示出來。例1.maxZ=xl+3x2s.t.xl+x2く6?xl+2x2く8xl20,x220可行域640xlx2Z=xl+3x2=03.畫出目標(biāo)函數(shù)的圖形（通?？僧嫵霎?dāng)目標(biāo)函數(shù)值為零時的（基準(zhǔn)）目標(biāo)函數(shù)圖）,確定目標(biāo)函數(shù)平行移動的方向,并沿目標(biāo)函數(shù)直線的法向用小箭頭標(biāo)出?！?.2圖解法.將（基準(zhǔn)）目標(biāo)函數(shù)直線沿所標(biāo)示的方向平行移動直至可行域的邊界,若這時目標(biāo)函數(shù)的直線與可行域的邊界點或邊界線重合,則其重合點或重合線段上的點即為此L.P.問題的最優(yōu)解,當(dāng)重合部分為一點,則該點的坐標(biāo)即為原L.P.的唯一解，當(dāng)重合部分為一條線段時,則該線段上的任一點的坐標(biāo)即為原L.P.的解,這時原L.P.問題有無窮多個解;否則,原LP.問題無解。2.2圖解法xl+2x2=8可行域目標(biāo)函數(shù)等值線最優(yōu)解64860xlx2目標(biāo)函數(shù)基準(zhǔn)線Z=xl+3x2=0Pxl+x2=6設(shè)點P的坐標(biāo)為（xl,x2）,則可由以下方程解得xl,x2：xl+x2=6-xl+2x2=8解得:xl=明x2=14/3maxZ=xl+3x2maxZ=xl+3x2最優(yōu)值為: maxZ=xl+3x2=轉(zhuǎn)+3X14/3=4^3-xl+2x2=8可行域目標(biāo)函數(shù)等值線最優(yōu)解64860xlx2目標(biāo)函數(shù)基準(zhǔn)線Z=xl+3x2=0Pxl+x2=6故最優(yōu)解為: xl=鉆,x2=14/3§2.2圖解法例2.求解L.P.問題:maxZ=xl+x2s.t.xl+x2W6?xl+2x2W8xl20,x220解:以xl為橫軸,以x2為豎軸建立直角坐標(biāo)系,并根據(jù)題意畫圖。maxZ=xl+x2xl+x2=6可行域目標(biāo)函數(shù)等值線最優(yōu)解64-860xlx2目標(biāo)函數(shù)基準(zhǔn)線Z=xl+x2=0PQ-xl+2x2=8由圖可知例2的目標(biāo)函數(shù)在線段PQ上任一點處均取最大值,原問題有無窮多個最優(yōu)解。設(shè)點P的坐標(biāo)為(xl,x2),則可解得點P的坐標(biāo)為(利,1%)。故原問題的一ー個最優(yōu)解為:xl=明，x2=l轉(zhuǎn)其最優(yōu)值為:maxZ=xl+3x2=*+1必=6例3.§2.2圖解法maxZ=xl+x2s.t.2xl-x222-xl+2x2く8x!20,x220目標(biāo)函數(shù)等值線-810xlx2Z=xl+x2=0可行域目標(biāo)函數(shù)無上界,無最優(yōu)解例4.解法minZ=xl+x2s.t.2xl-x222?xl+2x2W8xlNO,x2さ0-24-810xlx2Z=xl+x2=0可行域最優(yōu)解目標(biāo)函數(shù)等值線§2.2圖解法重要結(jié)論:如果線性規(guī)劃有最優(yōu)解,則一定有一個可行域的頂點對應(yīng)一個最優(yōu)解;無窮多個最優(yōu)解。如例3,線段PQ上的所有點都代表了最優(yōu)解;無界解。即可行域的范圍延伸到無窮遠(yuǎn),目標(biāo)函數(shù)值可以無窮大或無窮小,如例4。一般來說,在實際問題中,這說明模型有錯,忽略了一些必要的約束條件;無可行解。若在例1的數(shù)學(xué)模型中再增加一個約束條件4x1+3x221200,則可行域為空域,不存在滿足約束條件的解,當(dāng)然也就不存在最優(yōu)解了?！?.2圖解法練習(xí).maxZ=-xl+2x2s.t.xl<3xl-x220xl20,x220可行域30xlx2Z=-xl+2x2=0解得P點坐標(biāo)為:xl=3,x2=3最優(yōu)值為:maxZ=3最優(yōu)解P線性規(guī)劃模型一般形式目標(biāo)函數(shù): Max(Min)z=clxl+c2x2+...+cnxn約束條件:s.t.allxl+al2x2+…+alnxn<(=,2)bla21xl+a22x2+ +a2nxnW(=,2)amixl+am2x2+,,,+amnxnく（ラユ）bmxl,x2,…,xn20標(biāo)準(zhǔn)形式目標(biāo)函數(shù): Maxz=clxl+c2x2+…+cnxn約束條件:s.t.allxl+al2x2+…+alnxn=bla21xl+a22x2+...+a2nxn=b2amixl+am2x2+...+amnxn=bmxl,x2,…,xn20,bi20§2.3圖解法的靈敏度分析§2.3圖解法的靈敏度分析靈敏度分析:建立數(shù)學(xué)模型和求得最優(yōu)解后,研究線性規(guī)劃的?個或多個參數(shù)(系數(shù))ci,aij,bj變化時,對最優(yōu)解產(chǎn)生的影響。3.1目標(biāo)函數(shù)系數(shù)ci的靈敏度分析考慮例1的情況,顯然,ci的變化只影響目標(biāo)函數(shù)等值線的斜率。z=0=50x1+100x2目標(biāo)函數(shù)z=50xl+100x2在z=x2(x2=z斜率為〇)到z=xl+x2(x2=-xl+z斜率為ー1)之間時，原最優(yōu)解xl=50,x2=250仍是最優(yōu)解。一般情況:z=clxl+c2x2寫成斜截式:x2=-(cl/c2)xl+z/c2目標(biāo)函數(shù)等值線的斜率為:-(cl/c2),當(dāng)ー1??-(cl/c2)??0(*)時,原最優(yōu)解仍是最優(yōu)解。z=0=50xl+100x2§2.3圖解法的靈敏度分析假設(shè)產(chǎn)品H的利潤100元不變,即c2=100,代到式(*)并整理得0 ??cl??100假設(shè)產(chǎn)品I的利潤50元不變,即cl=50,代到式（*）并整理得50 ??C2??+??假若產(chǎn)品I、II的利潤均改變,則可直接用式（*）來判斷?！?.3圖解法的靈敏度分析假設(shè)產(chǎn)品I、II的利潤分別為60元、55元,貝リ-2??-（60/55）??-1那么,最優(yōu)解為z=xl+x2和z=2xl+x2的交點:xl=100,x2=200§2.3圖解法的靈敏度分析3.2約束條件中右邊系數(shù)bj的靈敏度分析當(dāng)約束條件中右邊系數(shù)bj變化時,線性規(guī)劃的可行域也變化,可能引起最優(yōu)解的變化?？紤]例1的情況:假設(shè)設(shè)備臺時增加10個臺時,即bl變化為310,這時可行域擴(kuò)大,最優(yōu)解為x2=250和xl+x2=310的交點xl=60,x2=250〇xl+x2=310最優(yōu)解§2.3圖解法的靈敏度分析變化后總利潤ー變化前總利潤=增加的利潤（50X60+100X250）-（50X50+100X250）=500500/10=50元說明在一定范圍內(nèi)每增加（減少）1個臺時的設(shè)備能力就可增加（減少）50元利潤,稱為該約束條件的對偶價格。§2.3圖解法的靈敏度分析假設(shè)原料A增加10千克時,即b2變化為410,這時可行域擴(kuò)大,但最優(yōu)解仍為x2=250和xl+x2=300的交點xl=50,x2=250〇2xl+x2=410此變化對總利潤無影響,該約束條件的對偶價格為〇.解釋:原最優(yōu)解沒有把原料A用盡,有5千克的剩余，因此增加10千克值增加了庫存,而不會增加利潤。z=0=50xl+100x2最優(yōu)解§2.3圖解法的靈敏度分析在一定范圍內(nèi),當(dāng)約束條件右邊常數(shù)增加1個單位時（1）若約束條件的對偶價格大于0I則其最優(yōu)目標(biāo)函數(shù)值得到改善（變好）；（2）若約束條件的對偶價格小于0,則其最優(yōu)目標(biāo)函數(shù)值受到影響（變壞）；（3）若約束條件的對偶價格等于〇,則最優(yōu)目標(biāo)函數(shù)值不變。作業(yè)第二章作業(yè):P23.2.（1）、（2）、（5）；P25.6.（1）-（4）第三章線性規(guī)劃問題的計算機(jī)求解廣東外語外貿(mào)大學(xué)GuangdongUniversityofForeignStudies運籌學(xué)第三章線性規(guī)劃問題的計算機(jī)求解§1“管理運籌學(xué)”軟件的操作方法§2“管理運籌學(xué)”軟件的輸出信息分析第三章線性規(guī)劃問題的計算機(jī)求解隨書軟件為“管理運籌學(xué)”2.0版（Window版）,是1.0版（DOS版）的升級版。它包括;線性規(guī)劃、運輸問題、整數(shù)規(guī)劃（0-1整數(shù)規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃）、目標(biāo)規(guī)劃、對策論、最短路徑、最小生成樹、最大流量、最小費用最大流、關(guān)鍵路徑、存儲論、排隊論、決策分析、預(yù)測問題和層次分析法,共15個子模塊。§1“管理運籌學(xué)”軟件的操作方法1.軟件使用演示:（演示例1）第一步:點擊“開始”->；“程序”->；"管理運籌學(xué)2.0”,彈出主窗口.例1.目標(biāo)函數(shù):Maxz=50xl+100x2約束條件:s.t.TOC\o"1-5"\h\zxl+x2く300 (A)2xl+x2く400 (B)x2く250 (C)xl20 (D)x2N0 (E)§1“管理運籌學(xué)”軟件的操作方法第二步：選擇所需子模塊,點擊主窗口中的相應(yīng)按鈕。本題中選用“線性規(guī)劃”方法。點擊按鈕彈出如下界面：例1.目標(biāo)函數(shù):Maxz=50xl+100x2約束條件：s.t.TOC\o"1-5"\h\zxl+x2く300 (A)2xl+x2W400 (B)x2く250 (C)xl20 (D)x220 (E)§1“管理運籌學(xué)”軟件的操作方法第三步:點擊“新建”按鈕,輸入數(shù)據(jù)。本題中共有2個變量,4個約束條件,目標(biāo)函數(shù)取MAX。點擊“確定”后,在表中輸入Cj,bi和aij等值,并確定變量的正負(fù)約束。輸入數(shù)值后的界面如下。例1.目標(biāo)函數(shù):Maxz=50xl+100x2約束條件:TOC\o"1-5"\h\zxl+x2W300 (A)2xl+x2く400 (B)x2く250 (C)xl20 (D)x2N0 (E)“管理運籌學(xué)”軟件的操作方法第四步:點擊“解決”按鈕,得出計算結(jié)果。本題的運行結(jié)果界面如下。相差值表示相應(yīng)的決策變量的目標(biāo)系數(shù)需要改進(jìn)的數(shù)量,使得決策變量為正值,當(dāng)決策變量已為正數(shù)時,相差數(shù)為零。例1.目標(biāo)函數(shù)：Maxz=50xl+100x2約束條件：s.t.TOC\o"1-5"\h\zxl+x2<300 (A)2xl+x2W400 (B)x2W250 (C)xl20 (D)x220 (E)松弛/剩余變量的數(shù)值表示還有多少資源沒有被使用。如果為零,則表示與之相對應(yīng)的資源已經(jīng)全部用上。例1.目標(biāo)函數(shù)：Maxz=50xl+100x2約束條件:TOC\o"1-5"\h\zxl+x2<300 (A)2xl+x2<400 (B)x2<250 (C)xlNO (D)x220 (E)對偶價格表示其對應(yīng)的資源每增加一?個單位,將增加多少個單位的最優(yōu)值。例1.目標(biāo)函數(shù):Maxz=50xl+100x2約束條件:s.t.TOC\o"1-5"\h\zxl+x2<300 (A)2xl+x2<400 (B)x2く250 (C)xlNO (D)x220 (E)目標(biāo)函數(shù)系數(shù)范圍表示最優(yōu)解不變的情況下,目標(biāo)函數(shù)的決策變量系數(shù)的變化范圍.當(dāng)前值是指當(dāng)前的最優(yōu)解中的系數(shù)取值.例1.目標(biāo)函數(shù)：Maxz=50xl+100x2約束條件：s.t.TOC\o"1-5"\h\zxl+x2く300 (A)2xl+x2W400 (B)x2<250 (C)xl20 (D)x220 (E)常數(shù)項范圍是指約束條件的右端常量。上限值和下限值是指當(dāng)約束條件的右端常量在此范圍內(nèi)變化時,與其對應(yīng)的約束條件的對偶價格不變。當(dāng)前值是指現(xiàn)在的取值。例1.目標(biāo)函數(shù):Maxz=50xl+100x2約束條件:s.t.TOC\o"1-5"\h\zX1+X2く300 (A)2xl+x2W400 (B)x2<250 (C)xl20 (D)x2川 (E)”管理運籌學(xué)”軟件的輸出信息分析第五步:分析運行結(jié)果。以上計算機(jī)輸出的目標(biāo)函數(shù)系數(shù)和約束條件右邊值的靈敏度分析都是在其他系數(shù)值不變,只有一個系數(shù)變化的基礎(chǔ)上得出的!2.當(dāng)有多個系數(shù)變化時,需要進(jìn)?步討論。百分之一百法則:對于所有變化的目標(biāo)函數(shù)決策系數(shù)(約束條件右邊常數(shù)值),當(dāng)其所有允許增加的百分比與允許減少的百分比之和不超過100%時,最優(yōu)解不變(對偶價格不變,最優(yōu)解仍是原來幾個線性方程的解)?！?“管理運籌學(xué)”軟件的輸出信息分析允許增加量=上限ー現(xiàn)在值cl的允許增加量為100-50=50bl的允許增加量為325-300=25允許減少量=現(xiàn)在值一下限c2的允許減少量為100-50=50b3的允許減少量為250-200=50允許增加的百分比=增加量/允許增加量允許減少的百分比=減少量/允許減少量例:cl變?yōu)?4,c2變?yōu)?8,則（74-50）/50+（100-78酒〇=92%故最優(yōu)解不變。b!變?yōu)?15,b3變?yōu)?40,則（315-300）/25+（250-240）/50=80%故對偶價格不變（最優(yōu)解仍是原來兒個線性方程的解）?！?.2“管理運籌學(xué)”軟件的輸出信息分析在使用百分之一百法則進(jìn)行靈敏度分析時,要注意:1）當(dāng)允許增加量（允許減少量）為無窮大時,則對任意增加量（減少量），其允許增加（減少）百分比均看作〇;2）百分之一百法則是充分條件，但非必要條件;也就是說超過100%并不一定變化；3）百分之一百法則不能用于目標(biāo)函數(shù)決策變量系數(shù)和約束條件右邊常數(shù)值同時變化的情況。這種情況下,只有重新求解?！?.2“管理運籌學(xué)”軟件的輸出信息分析下面用“管理運籌學(xué)”軟件來分析第二章的例2,其數(shù)學(xué)模型如下目標(biāo)函數(shù);Minf=2x1+3x2約束條件:s.t.xl+x22350xl 21252x1+x2く600xl,x220從上圖可知,當(dāng)購進(jìn)原材料A2503原料B100t時,購進(jìn)成本最低,為800萬元?！?.2“管理運籌學(xué)”軟件的輸出信息分析在松弛/剩余變量欄中,約束條件2的值為125I它表示對原料A的最低需求，即對A的剩余變量值為125;同理可知約束條件1的剩余變量值為〇;約束條件3的松弛變量值為0.在對偶價格欄中,約束條件3的對偶價格為1萬元,也就是說如果把加工時數(shù)從600小時增加到601小時,則總成本將得到改進(jìn),由800萬減少到フ99萬。也可知約束條件1的對偶條件為ー4萬元,也就是說如果把購進(jìn)原料A的下限從125t增加到126t,那么總成本將加大,由800萬增加到804萬。當(dāng)然如果減少對原料A的下限,那么總成本將得到改進(jìn)。在常數(shù)項范圍?欄中,知道當(dāng)約束條件1的常數(shù)項在300—475范圍內(nèi)變化,且其他約束條件不變時，約束條件1的對偶價格不變;當(dāng)約束條件2的常數(shù)項在負(fù)無窮到250范圍內(nèi)變化,而其他約束條件的常數(shù)項不變時，約束條件2的對偶價格不變,仍為0:當(dāng)約束條件3的常數(shù)項在475—700內(nèi)變化,而其他約束條件的常數(shù)項不變時,約束條件3的對偶價格不變,仍為1?！?.2“管理運籌學(xué)”軟件的輸出信息分析注意:當(dāng)約束條件中的常數(shù)項增加一個單位時,最優(yōu)目標(biāo)函數(shù)值增加的數(shù)量稱之為影子價格。在求目標(biāo)函數(shù)最大時,當(dāng)約束條件中的常數(shù)項增加一個單位時,目標(biāo)函數(shù)值增加的數(shù)量就為改進(jìn)的數(shù)量，所以影子價格等于對偶價格;在求目標(biāo)函數(shù)值最小時,改進(jìn)的數(shù)量就是減少的數(shù)量,所以影子價格即為負(fù)的對偶價格。§3.2”管理運籌學(xué)”軟件的輸出信息分析注意:2.“管理運籌學(xué)”軟件可以解決含有100個變量50個約束方程的線性規(guī)劃問題,可以解決工商管理中大量的問題。如果想要解決更大的線性規(guī)劃問題，可以使用由芝加哥大學(xué)的L.E.Schrage開發(fā)的Lindo計算機(jī)軟件包的微型計算機(jī)版本Lindo/PCo第三章線性規(guī)劃問題的計算機(jī)求解第四章線性規(guī)劃在工商管理中的應(yīng)用廣東外語外貿(mào)大學(xué)GuangdongUniversityofForeignStudies運籌學(xué)第四章線性規(guī)劃在工商管理中的應(yīng)用§!人力資源分配的問題;§2生產(chǎn)計劃的問題;§3套裁下料問題;§4配料問題;§5投資問題?！?人力資源分配的問題例1.某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下:設(shè)司機(jī)和乘務(wù)人員分別在各時間段ー開始時上班,并連續(xù)工作八小時,問該公交線路怎樣安排司機(jī)和乘務(wù)人員,既能滿足工作需要,又配備最少司機(jī)和乘務(wù)人員?解:設(shè)xi表示第i(i=l,2,…，6)班次時開始上班的司機(jī)和乘務(wù)人員數(shù),建立數(shù)學(xué)模型:目標(biāo)函數(shù)：Minz=xl+x2+x3+x4+x5+x6約束條件: s.t.xl+x6260xl+x2270x2+x3260x3+x4250x4+x5220x5+x6230xl,x2,x3,x4,x5,x620302:00—6:002022:00—2:0055018:00—22:0046014:00-18:0037010:00—14:002606:00—10:001所需人數(shù)時間班次*****************ム支角年女口下ー******************目標(biāo)函數(shù)最優(yōu)值為:150變量最優(yōu)解相差值X1600x2100x3500x400x5300x601§2生產(chǎn)計劃的問題例3.某公司面臨ー個是外包協(xié)作還是自行生產(chǎn)的問題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品,都需要經(jīng)過鑄造、機(jī)加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作,亦可以自行生產(chǎn),但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如表。問:公司為了獲得最大利潤,甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件?甲、乙兩種產(chǎn)品的鑄造中,由本公司鑄造和由外包協(xié)作各應(yīng)多少件?161823產(chǎn)品售價（元/件）223裝配成本（元/件）312機(jī)加工成本（元/件）65外協(xié)鑄件成本（元/件）453自產(chǎn)鑄件成本（元/件）100002裝配エ時（小時/件）12000846機(jī)加工エ時（小時/件）80007105鑄造エ時（小時/件）限制丙乙甲解:設(shè)xl,x2,x3分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù),x4,x5分別為由外協(xié)鑄造再由本公司加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。求xi的利潤:利潤=售價-各成本之和1823產(chǎn)品售價（元/件）223裝配成本（元/件）3機(jī)加工成本（元/件）65外協(xié)鑄件成本（元/件）453自產(chǎn)鑄件成本（元/件）10000223裝配エ吋（小時/件）12000846機(jī)加工エ時（小時/件）80007105鑄造エ時（小時/件）資源限制丙乙甲產(chǎn)品甲全部自制的利潤=23-（3+2+3）=15產(chǎn)品甲鑄造外協(xié),其余自制的利潤二23-(5+2+3)=13產(chǎn)品乙全部自制的利潤二18-(5+1+2)=10產(chǎn)品乙鑄造外協(xié),其余自制的利潤二18-(6+1+2)=9產(chǎn)品丙的利潤二16-(4+3+2)=7可得至Uxi(i=l,2,3,4,5)的利潤分別為15,10,7,13,9元.161823產(chǎn)品售價(元/件)223裝配成本(元/件)312機(jī)加工成本(元/件)65外協(xié)鑄件成本(元/件)453自產(chǎn)鑄件成本(元/件)1000022裝配エ時（小時/件）12000846機(jī)加工エ時（小時7件）80007105鑄造エ時（小時/件）資源限制丙乙甲通過以上分析,可建立如下的數(shù)學(xué)模型:目標(biāo)函數(shù):Max15x1+10x2+7x3+13x4+9x5約束條件:5x1+10x2+7x3W80006x1+4x2+8x3+6x4+4x5く!20003x1+2x2+2x3+3x4+2x5W10000xl,x2,x3,x4,x520161823產(chǎn)品售價（元/件）223裝配成本（元/件）機(jī)加工成本（元/件）65外協(xié)鑄件成本（元/件）453自產(chǎn)鑄件成本（元/件）10000223裝配エ時（小時/件）12000846機(jī)加工エ時（小時7件）80007105鑄造工時（小時7件）資源限制丙甲思考題:當(dāng)產(chǎn)品的售價因市場的變化而發(fā)生變化時,應(yīng)怎樣處理?當(dāng)該公司的生產(chǎn)能力提高時,應(yīng)如何進(jìn)行分析?要求:運用計算機(jī)軟件進(jìn)行計算、分析后回答。§3套裁下料問題al32??amCllC12 ...ClnC21 C22 ...C2n??????CmlCm2...CmnAlA2??Am零件需要量BlB2...Bn各方式的零件個下料方式零件名稱 數(shù)例.設(shè)用某原材料做零件A1,A2,…,Am的毛坯,若在一件原材料上有Bl,B2，…,Bn種不同的下料方式,每種方式可得到各種毛坯個數(shù)及每種零件需要量如下表所示。問如何安排下料方式使既能滿足要求,又能使用的原材料最少。ala2??amCll C12 ... ClnC21 C22 ... C2n??????CmlCm2...CmnAlA2??Am零件需要量BlB2...Bn各方式的零件個下料方式零件名稱 數(shù)分析:零件Ai按B1方式下料按B2方式下料按Bn方式下料Cil個Ci2個Cin個ai解:設(shè)用Bj種方式下料的原材料數(shù)為xj,則這ー問題的數(shù)學(xué)模型為:目標(biāo)函數(shù)約束條件所用原材料數(shù)量最少Ai零件總數(shù)不能少于ai原材料不能是負(fù)數(shù)、分?jǐn)?shù)套裁下料問題例5.某工廠要做100套鋼架,每套用長為2.9m,2.1m,1.5m的圓鋼各ー根。已知原料每根長7.4m,問:應(yīng)如何下料,可使所用原料最省?解:共可設(shè)計下列8種下料方案,見下表設(shè)xl,-,x8分別為上面8種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù):Minxl+x2+…+x8約束條件: xl+2x2 +x4 +x621002x3+2x4+x5+x6+3x721003x1+x2+2x3 +3x5+x6 +4x82100xl,x2,…，x820運用軟件《管理運籌學(xué)2.0》求解以上模型：思考題：如果計算得到的結(jié)果不是整數(shù),即最優(yōu)方案中所需各種型號的園鋼的根數(shù)不是整數(shù)，應(yīng)怎樣處理?是否可進(jìn)行四舍五入,四舍五入后的結(jié)果是否還是最優(yōu)方案?在線性規(guī)劃中,對決策變量增加整數(shù)的要求會引出什么問題?要求：查找有關(guān)資料并閱讀整數(shù)規(guī)劃的章節(jié)進(jìn)行思考。套裁下料問題用“管理運籌學(xué)”軟件計算得出最優(yōu)下料方案:按方案1下料30根;按方案2下料:L0根;按方案4下料50根,即:xl=30;x2=10;x3=0;x4=50;x5=x6=x7=x8=0；只需90根原材料就可制造出100套鋼架。注意:在建立此類型數(shù)學(xué)模型時,約束條件用大于等于號比用等于號要好。因為有時在套用ー些下料方案時可能會多出ー根某種規(guī)格的圓鋼,但它可能是最優(yōu)方案。如果用等于號,這ー方案就不是可行解了。配料問題例6.某工廠要用三種原料1,2,3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙,數(shù)據(jù)如右表。問：該廠應(yīng)如何安排生產(chǎn),使利潤收入為最大?25不限丙35原材料1不少于25%,原材料2不超過50%乙50原材料1不少于50%,原材料2不超過25%甲單價（元/kg）規(guī)格要求產(chǎn)品名稱3560325651001單價(元ノkg)每天最多供應(yīng)量原材料名解:設(shè)xij表示第i種(甲、乙、丙)產(chǎn)品中原料j的含量。這樣我們建立數(shù)學(xué)模型時,要考慮:對甲:xll,X12,X13；xll^0.5(xll+xl2+xl3), xl2^0.25(xll+xl2+xl3)對乙:x21,x22,x23；x2120.25(x21+x22+x23),x22W0.5(x21+x22+x23)對丙:x31,x32,x33!沒限制,即無約束條件。對于原料1： xll, x21, x31； (xll+x21+x31)<100對于原料2： X12, x22, x32； (xl2+x22+x32)<100對于原料3： X13, x23, x33； (xl3+x23+x33)W60約束條件：規(guī)格要求4個;供應(yīng)量限制3個。目標(biāo)：利潤最大,利潤=收入一原料支出,故有:目標(biāo)函數(shù):Maxf=50(xll+xl2+xl3)+35(x21+x22+x23)+25(x31+x32+x33)-65(xll+x21+x31)-25(xl2+x22+x32)-35(xl3+x23+x33)=-15x11+25x12+15x13-30x21+10x22-40x31-10x33通過整理,得到以下模型：目標(biāo)函數(shù)：Maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33約束條件：s.t.0.5xll-0.5X12-0.5xl320（原材料1不少于50%）-0.25x11+0.75x12-0.25x13く〇（原材料2不超過25%）0.75x21-0.25x22-0.25x2320（原材料1不少于25%）-0.5X21+0.5x22-0.5x23W0（原材料2不超過50%）X11+x21+x31く100（供應(yīng)量限制）X12+x22+x32く100（供應(yīng)量限制）X13+x23+x33く60（供應(yīng)量限制）xij2〇,i=l,2,3;j=l,2,3思考題:如果實際問題的情況,目標(biāo)函數(shù)或約束條件不可用線性函數(shù)描述將會延拓出什么問題?進(jìn)ー步,當(dāng)實際問題的條件是不確定的或不清晰的,又將如何分析和考慮?有興趣可查閱和了解非線性規(guī)劃、模糊線性規(guī)劃等內(nèi)容。練習(xí)1學(xué)校準(zhǔn)備為學(xué)生添加營養(yǎng)餐,每個學(xué)生每月至少需要補(bǔ)充60單位的碳水化合物,40單位的蛋白質(zhì)和35單位的脂肪。已知兩種營養(yǎng)品每斤:AB含量:TOC\o"1-5"\h\z碳水化合物 5 2蛋白質(zhì) 3 2脂肪 5 1單價 1.5 0.7問題:買A和B分別多少斤既滿足學(xué)生營養(yǎng)需要又省錢?目標(biāo)函數(shù):mins=x+y約束條件: x+y260x+ y>40x+ y235變量:非負(fù)條件: x20,y20§5投資問題例8.某部門現(xiàn)有資金200萬元,今后五年內(nèi)考慮給以下的項目投資。已知:項目A：從第一年到第五年每年年初都可投資,當(dāng)年末能收回本利110%;項目B：從第一年到第四年每年年初都可投資,次年末能收回本利125%,但規(guī)定每年最大投資額不能超過30萬元;項目C:需在第三年年初投資,第五年末能收回本利140%,但規(guī)定最大投資額不能超過80萬元；項目D:需在第二年年初投資，第五年末能收回本利155%,但規(guī)定最大投資額不能超過100萬元。據(jù)測定每萬元每次投資的風(fēng)險指數(shù)如下表,問:a)應(yīng)如何確定這些項目的每年投資額,使得第五年年末擁有資金的本利金額為最大?b)應(yīng)如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利在330萬元的基礎(chǔ)上使得其投資總的風(fēng)險系數(shù)為最小?解;1)確定決策變量:連續(xù)投資問題設(shè)xij(i=1?5,j=1?4)表示第i年初投資于A(j=l)、B(j=2)、C(j=3)、D(j=4)項目的金額。這樣我們建立如下的決策變量:AX11x21x31 x41x51BX12x22x32 x42Cx33Dx242)約束條件:第?年:A當(dāng)年末可收回投資,故第一年年初應(yīng)把全部資金投出去，于是xll+X12=200；第二年:B次年末オ可收回投資,故第二年年初有資金1.1x11,于是x21+x22+x24=1.1x11；第三年：年初有資金!.1x21+1.25x12,于是x31+x32+x33=1.1x21+1.25x12第四年:年初有資金!.1x31+1.25x22,于是x41+x42=1.1x31+1.25x22第五年:年初有資金!.1x41+1.25x32?于是X51=1.1x41+1.25x32B、C、D的投資限制:xi2W30(i=l、2、3、4),x33W80,x24く1003)目標(biāo)函數(shù)及模型：a)Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.X11+X12=200x21+x22+x24=l.lxll；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；xi2く30(i=l、2、3,4),x33く80,x24W100,xij20(i=l,2,3,4,5；j=1,2,3,4,)b)所設(shè)變量與問題a相同,目標(biāo)函數(shù)為風(fēng)險最小,有:Minf=xll+x21+x31+x41+x51+3(xl2+x22+x32+x42)+4x33+5.5x24b)在問題a的約束條件中加上“第五年末擁有資金本利在330萬元”的條件,于是模型如下:Minf=xll+x21+x31+x41+x51+3(xl2+x22+x32+x42)+4x33+5.5x24s.t.xll+xl2=200x21+x22+x24=l.lxll；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；xi2く30(i=l,2,3,4),x33く80,x24く100x51+1.25x42+1.4x33+1.55x242330xijN0(i=1,2,3,4,5；j=1,2,3,4)本章結(jié)束第四章線性規(guī)劃在工商管理中的應(yīng)用廣東外語外貿(mào)大學(xué)GuangdongUniversityofForeignStudies統(tǒng)籌安排成本最低第五章運輸問題1運輸模型2運輸問題的計算機(jī)求解3運輸問題的應(yīng)用§4?運輸問題的表上作業(yè)法例1、某公司從兩個產(chǎn)地Al、A2將物品運往三個銷地Bl、B2、B3,各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示,問:應(yīng)如何調(diào)運可使總運輸費用最小?運輸模型解:產(chǎn)銷平衡問題:總產(chǎn)量=總銷量設(shè)xij為從產(chǎn)地Ai運往銷地Bj的運輸量,得到下列運輸量表:Minf=6x11+4x12+6x13+6x21+5x22+5x23產(chǎn)地Al運出的運輸量等于其產(chǎn)量:xll+xl2+xl3=200產(chǎn)地A2運出的運輸量等于其產(chǎn)量:x21+x22+x23=300運到銷地Bl的運輸量等于其需求量：xll+x21=150運到銷地B2的運輸量等于其需求量：xl2+x22=150運到銷地B3的運輸量等于其需求量：X13+X23=200運輸量非負(fù): xij20(i=l,2；j=l,2,3)§1運輸模型整理得:s.t.xll+X12+X13=200x21+x22+x23=300xll+x21=150X12+x22=150X13+x23=200xij20（i=l、2；j=l、2、3）§1運輸模型一般運輸模型:產(chǎn)銷平衡Al>A2、…、Am表示某物資的m個產(chǎn)地;Bl>B2、…、Bn表示某物質(zhì)的n個銷地;ai表示產(chǎn)地Ai的產(chǎn)量;bj表示銷地Bj的銷量;cij表示把物資從產(chǎn)地Ai運往銷地Bj的單位運價。設(shè)xij為從產(chǎn)地Ai運往銷地Bj的運輸量,得到下列一般運輸量問題的模型:運輸問題及其數(shù)學(xué)模型bnb2bl銷量BnB2Bl銷地產(chǎn)地AmA2Alama2al產(chǎn)量產(chǎn)銷平衡運價§1運輸模型bnb2bl銷量BnB2Bl銷地產(chǎn)地AmA2Alama2al產(chǎn)量cmncm2cmlc2nc22c21clncl2ell求使總的運輸費用最小的調(diào)運方案?ブン:銷平衡表運輸問題及其數(shù)學(xué)模型§1運輸模型產(chǎn)地Ai發(fā)量之和等于其產(chǎn)量銷地Bj收量之和等于其銷量運量不能為負(fù)數(shù)運輸問題線性規(guī)劃模型總費用最小§1運輸模型運輸問題網(wǎng)絡(luò)圖2321341s2=27s3=19d3=12d4=13sl=14供應(yīng)量供應(yīng)地運價需求量需求地6753842759106運輸模型運輸問題線性規(guī)劃模型供應(yīng)地約束需求地約束運輸模型§2運輸問題的計算機(jī)求解將上述問題用以下運價表:134121322銷量1910953272482145761產(chǎn)量321銷地產(chǎn)地§2 運輸問題的計算機(jī)求解運行管理運籌學(xué)計算機(jī)軟件:點擊運輸問題模塊§2 運輸問題的計算機(jī)求解點擊新建輸入3輸入4選擇Min點擊確定§2 運輸問題的計算機(jī)求解136734121322銷量191095327248214產(chǎn)量321銷地產(chǎn)地§2 運輸問題的計算機(jī)求解點擊解決§2 運輸問題的計算機(jī)求解思考題:運輸問題的特點是什么?既然運輸問題是線性規(guī)劃的ー種特殊情況,為什么不用線性規(guī)劃的方法求解?要求:對以上例子分別應(yīng)用計算機(jī)軟件的線性規(guī)劃模塊和運輸問題的模塊進(jìn)行計算、分析后回答?！? 運輸問題的計算機(jī)求解例2、某公司從兩個產(chǎn)地Al、A2將物品運往三個銷地Bl、B2、B3I各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示,問:應(yīng)如何調(diào)運可使總運輸費用最小?解:增加一個虛設(shè)的銷地運輸費用為0.§2運輸問題的計算機(jī)求解例3、某公司從兩個產(chǎn)地Al、A2將物品運往三個銷地Bl、B2、B3,各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示,問:應(yīng)如何調(diào)運可使總運輸費用最小?解:增加一個虛設(shè)的產(chǎn)地運輸費用為0思考題在例3中,即某公司從兩個產(chǎn)地Al、A2將物品運往三個銷地Bl、B2、B3,各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示,如果增加條件:B3的需求不能滿足則需以高價（每單位10元）在本地購買,問:應(yīng)如何調(diào)運可使總運輸費用最小?500650200200250銷量300556A2200646A1產(chǎn)量B3B2B1思考題在例3中,即某公司從兩個產(chǎn)地Al、A2將物品運往三個銷地Bl、B2、B3,各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示,如果增加條件:B3的需求不能滿足則需以高價（每單位10元）在本地購買,問:應(yīng)如何調(diào)運可使總運輸費用最小?650200200250銷量15010MMA3300556A2200646Al產(chǎn)量B3B2Bl§2運輸問題的計算機(jī)求解§2運輸問題的計算機(jī)求解§3 運輸問題的應(yīng)用ー、產(chǎn)銷不平衡的運輸問題例4、石家莊北方研究院有一、二、三三個區(qū)。每年分別需要用煤3000、1000、2000噸,由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng),價格、質(zhì)量相同。供應(yīng)能カ分別為1500、4000噸,運價為:由于需大于供,經(jīng)院研究決定一區(qū)供應(yīng)量可減少0-300噸,二區(qū)必須滿足需求量,三區(qū)供應(yīng)量不少于1500噸,試求總費用為最低的調(diào)運方案。解:根據(jù)題意,作出產(chǎn)銷平衡與運價表:這里M代表一個很大的正數(shù)，其作用是強(qiáng)迫相應(yīng)的x31、x33、X34取值為〇〇§3 運輸問題的應(yīng)用應(yīng)用運籌學(xué)軟件計算得：§3 運輸問題的應(yīng)用ー、產(chǎn)銷不平衡的運輸問題例5、設(shè)有A、B、C三個化肥廠供應(yīng)1、2、3、4四個地區(qū)的農(nóng)用化肥。假設(shè)效果相同,有關(guān)數(shù)據(jù)如下表：試求總費用為最低的化肥調(diào)撥方案。解:根據(jù)題意,作出產(chǎn)銷平衡與運價表:最低要求必須滿足,因此把相應(yīng)的虛設(shè)產(chǎn)地運費取為M,而最高要求與最低要求的差允許按需要安排,因此把相應(yīng)的虛設(shè)產(chǎn)地運費取為0〇對應(yīng)4"的銷量50是考慮問題本身適當(dāng)取的數(shù)據(jù),根據(jù)產(chǎn)銷平衡要求確定D的產(chǎn)量為50.210210501030702030銷量500M0M0MD5023201919C60151519131414B50171722131616A產(chǎn)量4”4'321"1'思考題考慮?運輸問題,有關(guān)產(chǎn)品的單位運價（元/千克）如下表所示,假設(shè)Al、A2處產(chǎn)品要求全部運走,A3處產(chǎn)品就地儲存的費用為每千克16元,試寫出該問題的產(chǎn)銷平衡表。55 60需求量（千克）403065TOC\o"1-5"\h\z35 2315 3428 33A1A2A3供應(yīng)量（千克）Bl B2銷地產(chǎn)地§3 運輸問題的應(yīng)用思考題該問題的產(chǎn)銷平衡表為:55 60 20需求量（千克）403065TOC\o"1-5"\h\z35 23 M15 34 M28 33 16A3供應(yīng)量（千克）Bl B2 B3銷地產(chǎn)地§3運輸問題的應(yīng)用§3運輸問題的應(yīng)用二、生產(chǎn)與儲存問題例6、某廠按合同規(guī)定須于當(dāng)年每個季度末分別提供10、15、25、20臺同ー規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如右表。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨,每臺每積壓ー個季度需儲存、維護(hù)等費用0.15萬元。試求在完成合同的情況下,使該廠全年生產(chǎn)總費用為最小的決策方案。11.310411.030311.135210.8251單位成本（萬元）生產(chǎn)能力（臺）季度解:把第i季度生產(chǎn)的柴油機(jī)數(shù)目看作第i個生產(chǎn)廠的產(chǎn)量;把第j季度交貨的柴油機(jī)數(shù)目看作第j個銷售點的銷量;成本加儲存、維護(hù)等費用看作運費?？蓸?gòu)造下列產(chǎn)銷平衡問題:1001003020251510銷量10011.30MMM430011.1511.00MM335011.4011.2511.10011.2511.1010.9510.801產(chǎn)量D4321季度季度設(shè)xij為第i季度生產(chǎn)的第j季度交貨的柴油機(jī)數(shù)目,則交貨:1001003020251510銷量10011.30430011.1511.00MM335011.4011.2511.10M225011.2511.1010.9510.801產(chǎn)量D4季度X11+X12+X13+X14く25x22+x23+x24く35X33+X34く30X44W10TOC\o"1-5"\h\zxll =10X12+X22 =15xl3+x23+x33 =25xl4+x24+x34+x44=20生產(chǎn):目標(biāo)函數(shù):Minf=10.8xll+10.95xl2+ll.lxl3+11.25xl4++11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44§3 運輸問題的應(yīng)用三、轉(zhuǎn)運問題:在原運輸問題上增加若干轉(zhuǎn)運站。運輸方式有:產(chǎn)地??轉(zhuǎn)運站、轉(zhuǎn)運站??銷地、產(chǎn)地??產(chǎn)地、產(chǎn)地??銷地、銷地??轉(zhuǎn)運站、銷地??產(chǎn)地等。例8、騰飛電子儀器公司在大連和廣州有兩個分廠生產(chǎn)同一?種儀器,大連分廠每月生產(chǎn)400臺,廣州分廠每月生產(chǎn)600臺。該公司在上海和天津有兩個銷售公司負(fù)責(zé)對南京、濟(jì)南、南昌、青島四個城市的儀器供應(yīng)。另外因為大連距離青島較近,公司同意大連分廠向青島直接供貨,運輸費用如圖,單位是百元。問應(yīng)該如何調(diào)運儀器,可使總運輸費用最低?圖中1ー廣州、2一大連、3ー上海、4ー天津、5-南京、6ー濟(jì)南、7ー南昌、8一青島。應(yīng)該如何調(diào)運儀器,可使總運輸費用最低?圖中1-廣州、2一大連、3ー上海、4-天津、5ー南京、6ー濟(jì)南、フー南昌、8一青島。大連上海天津銷量產(chǎn)量青島上海天津南京濟(jì)南南昌青島運價表260040010001000100010002001503503003MMMM31MMM2636M0廣州濟(jì)南大連上海天津南京南昌青島6004001000100023MMMM31MMM40M2636M04465廣州大連上海天津1000 1000200 1503503001000 1000200 150350300銷量產(chǎn)量上海天津南京濟(jì)南南昌青島運價表3運輸問題的應(yīng)用例9、某公司有Al、A2、A3三個分廠生產(chǎn)某種物資,分別供應(yīng)Bl、B2、B3、B4四個地區(qū)的銷售公司銷售。假設(shè)質(zhì)量相同,有關(guān)數(shù)據(jù)如下表,試求總費用為最少的調(diào)運方案。運輸問題的應(yīng)用假設(shè):.每個分廠的物資不一定直接發(fā)運到銷地,可以從其中幾個產(chǎn)地集中一起運;.運往各銷地的物資可以先運給其中幾個銷地,再轉(zhuǎn)運給其他銷地;.除產(chǎn)銷地之外,還有兒個中轉(zhuǎn)站,在產(chǎn)地之間、銷地之間或在產(chǎn)地與銷地之間轉(zhuǎn)運。運價如下表:31264765810B42241023B31218584911B2244271Bl21212323T4428121324T3725T26482231132T151047323A38231A2103113341231AlB4B3B2BlT4T3T2T1A3A2Al解:把此轉(zhuǎn)運問題轉(zhuǎn)化為?般運輸問題:.把所有產(chǎn)地、銷地、轉(zhuǎn)運站都同時看作產(chǎn)地和銷地;.運輸表中不可能方案的運費取作M,自身對自身的運費為〇;.Ai產(chǎn)量為20+原產(chǎn)量,銷量為20;Ti:產(chǎn)量、銷量均為20；Bi:產(chǎn)量為20,銷量為20+原銷量,其中20為各點可能變化的最大流量;.對于最優(yōu)方案,其中xii為自身對自身的運量,實際上不進(jìn)行運作。擴(kuò)大的運輸問題產(chǎn)銷平衡與運價表:2402625262320202020202020銷量2003126476B420302422241023B3201201M8584911B22001142713Bl2062M10212323T4204232M4T32072541101M51T2206482232T1295104732M10M3A32482912M53M01A231133412310Al產(chǎn)量B4B3B2BlT4T3T2T1A3A2Al謝謝大家返回首頁作業(yè)第一次作業(yè):P152、1第二次作業(yè):P153、3第三次作業(yè):P153、2第六章整數(shù)規(guī)劃廣東外語外貿(mào)大學(xué)GuangdongUniversityofForeignStudies運籌學(xué)第六章整數(shù)規(guī)劃§1整數(shù)規(guī)劃的圖解法§2整數(shù)規(guī)劃的計算機(jī)求解§3整數(shù)規(guī)劃的應(yīng)用*§4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃是ー類要求變量取整數(shù)值的數(shù)學(xué)規(guī)劃,可分成線性和非線性兩類。整數(shù)線性規(guī)劃（IntegerLinearProgramming,簡記為ILP）問題研究的是要求變量取整數(shù)值時,在ー組線性約束條件下ー個線性函數(shù)最優(yōu)問題,是應(yīng)用非常廣泛的運籌學(xué)的ー個重要分支。應(yīng)用實例:?項目投資問題 ?工作分配問題?選址問題 ?背包問題第六章整數(shù)規(guī)劃根據(jù)變量的取值情況,整數(shù)線性規(guī)劃又可以分為純整數(shù)規(guī)劃（所有變量取整數(shù)）,混合整數(shù)規(guī)劃（部分變量取整數(shù)），0-1整數(shù)規(guī)劃（變量只取?；?）等。求整數(shù)解的線性規(guī)劃問題,不是用四舍五入法或去尾法對線性規(guī)劃的非整數(shù)解加以處理就能解決的。整數(shù)線性規(guī)劃ー些基本算法的設(shè)計是以相應(yīng)線性規(guī)劃的最優(yōu)解為出發(fā)點而發(fā)展出來的。整數(shù)規(guī)劃是數(shù)學(xué)規(guī)劃中一個較弱的分支,目前有成熟的方法解線性整數(shù)規(guī)劃問題,而非線性整數(shù)規(guī)劃問題,還沒有好的辦法。第六章整數(shù)規(guī)劃§1整數(shù)規(guī)劃的圖解法例1. 某公司擬用集裝箱托運甲、乙兩種貨物,這兩種貨物每件的體積、

重量、可獲利潤以及托運所受限制如表所示。甲種貨物至多托運4件,問兩種貨物各托運多少件,可使獲得利潤最大貨物每件體積（立方米）每件重量（百千克）每件利潤（百元）甲乙19527344023托運限制1365140§1整數(shù)規(guī)劃的圖解法解:設(shè)xl、x2分別為甲、乙兩種貨物托運的件數(shù),建立模型。目標(biāo)函數(shù):Maxz目標(biāo)函數(shù):Maxz=2x1+3x2約束條件:s.t.195xl+273x2W13654x1+ 40x2W140xl《4xl,x220,為整數(shù)。如果去掉最后ー個約束,就是ー個線性規(guī)劃問題.貨物每件體積（立方米）每件重量（百千克）每件利潤（百元）甲乙19527344023托運限制1365140§1整數(shù)規(guī)劃的圖解法利用圖解法,得到線性規(guī)劃的最優(yōu)解為xl=2.44,x2=3.26,目標(biāo)函數(shù)值為14.66〇由圖表可看出,整數(shù)規(guī)劃的最優(yōu)解為xl=4,x2=2,目標(biāo)函數(shù)值為14。195x1+273x2=13654xl+40x2=1404231123x2xl§1整數(shù)規(guī)劃的圖解法對于整數(shù)規(guī)劃,易知有以下性質(zhì):性質(zhì)1:任何求最大目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標(biāo)函數(shù)值小于或等于相應(yīng)的線性規(guī)劃的最大目標(biāo)函數(shù)值;任何求最小目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標(biāo)函數(shù)值大于或等于相應(yīng)的線性規(guī)劃的最小目標(biāo)函數(shù)值。§2分支定界法以及計算機(jī)求解分枝定界法步驟:求解與IP相應(yīng)的LP問題,可能會出現(xiàn)下面幾種情況:若所得的最優(yōu)解的各變量恰好取整數(shù),則這個解也是原整數(shù)規(guī)劃的最優(yōu)解,計