上海交大運(yùn)籌學(xué)課件(第一講).ppt

1、運(yùn)籌學(xué)課程,上海交通大學(xué)管理學(xué)院 于長(zhǎng)銳,電話(huà)：28516057 E-mail：,成績(jī)考核方法,上課考勤：10% 作業(yè)成績(jī)：20% 期末考試：70%,第一章 緒論,運(yùn)籌學(xué)的由來(lái)與發(fā)展,名稱(chēng) 運(yùn)籌學(xué)一詞的英文原名為Operations Research（縮寫(xiě)為O.R） 中文以前譯成“運(yùn)作研究”或“作業(yè)研究”或“管理數(shù)學(xué)”或“運(yùn)用學(xué)” 1957年我國(guó)從“運(yùn)籌帷幄之中，決勝千里之外”這句古語(yǔ)中摘取“運(yùn)籌”二字，將O.R正是譯為“運(yùn)籌學(xué)”。 運(yùn)籌學(xué)的產(chǎn)生與發(fā)展,樸素的運(yùn)籌學(xué)思想 田忌賽馬（對(duì)策論） 丁渭修宮（網(wǎng)絡(luò)規(guī)劃） 產(chǎn)生于第二次世界大戰(zhàn)時(shí)期 羅伊（A.P.Rowe）的雷達(dá)防空作戰(zhàn)系統(tǒng) 陸、海、空軍

2、的作戰(zhàn)策略 軍需物資的運(yùn)輸 發(fā)展于五、六十年代 電子計(jì)算機(jī)技術(shù)的迅速發(fā)展，解決線(xiàn)形規(guī)劃問(wèn)題的單純型法產(chǎn)生； 1957年在英國(guó)牛津大學(xué)召開(kāi)了第一次國(guó)際運(yùn)籌學(xué)會(huì)議。 1959年 成立國(guó)際運(yùn)籌學(xué)會(huì) (International Federation of Operations Research Societies, IFORS) 成熟于七、八十年代 運(yùn)籌學(xué)用來(lái)研究一些大的復(fù)雜的系統(tǒng)，如城市交通、環(huán)境污染、國(guó)民經(jīng)濟(jì)計(jì)劃等實(shí)際社會(huì)問(wèn)題 運(yùn)籌學(xué)進(jìn)一步細(xì)分為各個(gè)分支，專(zhuān)業(yè)學(xué)術(shù)團(tuán)體的迅速增多，更多期刊的創(chuàng)辦，運(yùn)籌學(xué)書(shū)籍 的大量出版以及更多學(xué)校將運(yùn)籌學(xué)課程納入教學(xué)計(jì)劃之中。,運(yùn)籌學(xué)定義,各種定義 據(jù)大英百科全書(shū)

3、釋義，“運(yùn)籌學(xué)是一門(mén)應(yīng)用于管理有組織系統(tǒng)的科學(xué)”，“運(yùn)籌學(xué)為掌管這類(lèi)系統(tǒng)的人提供決策目標(biāo)和數(shù)量分析的工具”。 我國(guó)辭海(1979年版)中有關(guān)運(yùn)籌學(xué)條目的釋義為，運(yùn)籌學(xué)“主要研究經(jīng)濟(jì)活動(dòng)與 軍事活動(dòng)中能用數(shù)量來(lái)表達(dá)有關(guān)運(yùn)用、籌劃與管理方面的問(wèn)題，它根據(jù)問(wèn)題的要求，通過(guò)數(shù)學(xué)的分析與運(yùn)算，作出綜合性的合理安排，以達(dá)到較經(jīng)濟(jì)較有效地使用人力物力。” 中國(guó)企業(yè)管理百科全書(shū)(1984年版)中的釋義為，運(yùn)籌學(xué)“應(yīng)用分析、試驗(yàn)、量化的方法，對(duì) 經(jīng)濟(jì)管理系統(tǒng)中人、財(cái)、物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以 實(shí)現(xiàn)最有效的管理?！?歸納 學(xué)科范圍：系統(tǒng)科學(xué) 研究方法：定量分析、數(shù)學(xué)運(yùn)算 研究目標(biāo)

4、：對(duì)系統(tǒng)中人、財(cái)、物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理決策,運(yùn)籌學(xué)的特點(diǎn)（1）,1運(yùn)籌學(xué)研究和解決問(wèn)題的基礎(chǔ)是最優(yōu)化技術(shù)，并強(qiáng)調(diào)系統(tǒng)整體最優(yōu)運(yùn)籌學(xué)針對(duì)研究的 實(shí)際問(wèn)題，從系統(tǒng)的觀(guān)點(diǎn)出發(fā)，以整體最優(yōu)為目標(biāo)，研究各組成部分的功能及其相互問(wèn)的影響 關(guān)系，解決各組成部門(mén)之間的利害沖突，求出使所研究問(wèn)題達(dá)到最佳效果的解，并尋找一個(gè)最 好的行動(dòng)方案付諸實(shí)施 2運(yùn)籌學(xué)研究和解決問(wèn)題的優(yōu)勢(shì)是應(yīng)用各學(xué)科交叉的方法，具有綜合性運(yùn)籌學(xué)從一開(kāi)始 就是由不同學(xué)科專(zhuān)長(zhǎng)、多方面專(zhuān)家經(jīng)過(guò)共同協(xié)作集體努力而獲得成果的現(xiàn)在，由于研究對(duì)象 的復(fù)雜性和多因索性，決定了運(yùn)籌學(xué)內(nèi)容的跨學(xué)科性、交叉滲

5、透性和綜合性,運(yùn)籌學(xué)的特點(diǎn)（2）,3運(yùn)籌學(xué)研究和解決問(wèn)題的方法具有顯著的系統(tǒng)分析特征，其各種方法的運(yùn)用，幾乎都需要建立數(shù)學(xué)模型和利用計(jì)算機(jī)進(jìn)行求解可以說(shuō)現(xiàn)在及今后，沒(méi)有計(jì)算機(jī)的發(fā)展就沒(méi)有運(yùn)籌學(xué)的發(fā)展 4運(yùn)籌學(xué)具有強(qiáng)烈的實(shí)踐性和應(yīng)用的廣泛性運(yùn)籌學(xué)的目的在于解決實(shí)際問(wèn)題，它所使用的全部假設(shè)和數(shù)學(xué)模型無(wú)非都是解決實(shí)際問(wèn)題的工具，有助于各種經(jīng)濟(jì)活動(dòng)和管理問(wèn)題的解決，最終能向決策者提供建設(shè)性方案并能收到實(shí)效，因此，它的應(yīng)用并不受行業(yè)和部門(mén)的限制，已被廣泛應(yīng)用于工商企業(yè)、軍事部門(mén)、服務(wù)行業(yè)和經(jīng)濟(jì)管理部門(mén)中,模型（1）,模型定義 模型是客觀(guān)世界或 現(xiàn)實(shí)系統(tǒng)的代表或抽象的描述，用以描述客觀(guān)事物的某些特征和內(nèi)在

6、聯(lián)系，從而表示或解釋某 一系統(tǒng)的過(guò)程，是幫助人們認(rèn)識(shí)、分析和解決實(shí)際問(wèn)題的有力工具 模型的功能 1模型是現(xiàn)實(shí)問(wèn)題某一主要方面的描述或抽象，比現(xiàn)實(shí)本身簡(jiǎn)單和概括使入易于認(rèn)識(shí)、 理解和操作； 2模型是由與研究實(shí)際問(wèn)題有關(guān)的主要因素所構(gòu)成，并表明這些因素的相互關(guān)系，從而能夠更簡(jiǎn)明地揭示出問(wèn)題的本質(zhì)； 3通過(guò)模型可以進(jìn)行試驗(yàn)，用以分析和預(yù)測(cè)所研究事物或系統(tǒng)的特征及性質(zhì)尤其在研究 工業(yè)系統(tǒng)、軍事系統(tǒng)、政府或社會(huì)系統(tǒng)的最優(yōu)管理或遠(yuǎn)行的問(wèn)題時(shí)十分必要因?yàn)檫@樣可以避 免由于真實(shí)對(duì)象的干擾而導(dǎo)致不測(cè)的風(fēng)險(xiǎn) 4利用模型可以在相對(duì)短的時(shí)間內(nèi)獲得所研究問(wèn)題的結(jié)果特別對(duì)一個(gè)復(fù)雜問(wèn)題的研究， 利用模型，使研究者不必真的實(shí)

7、現(xiàn)計(jì)劃即可改變其參數(shù)，從而不必等待一段較長(zhǎng)的時(shí)間就可以得到問(wèn)題的答案,模型的基本形式 形象模型、模擬模型及符號(hào)或數(shù)學(xué)模型 數(shù)學(xué)模型,數(shù)學(xué)模型是將現(xiàn)實(shí)系統(tǒng)或問(wèn)題中有關(guān)參數(shù)和因素及其相互關(guān)系歸納成一個(gè)或一組 數(shù)學(xué)表達(dá)式，并可以用一定的分析和計(jì)算方法進(jìn)行求解，以實(shí)現(xiàn)反映現(xiàn)實(shí)系統(tǒng)變化規(guī)律的主要目標(biāo),數(shù)學(xué)模型的一般形式,模型（2）,運(yùn)籌學(xué)模型（1）,建立運(yùn)籌學(xué)模型的基本要求 能完整地描述所研究的系統(tǒng)，以便能代替現(xiàn)實(shí)供我們分析研究； 模型盡量簡(jiǎn)單。 運(yùn)籌學(xué)方法分析解決問(wèn)題的步驟 1提出并形成問(wèn)題要解問(wèn)題，首先需要提出問(wèn)題，明確問(wèn)題的實(shí)質(zhì)及關(guān)鍵所在，這就要求 對(duì)系統(tǒng)進(jìn)行深入的調(diào)查和分析，確定問(wèn)題的界限，選準(zhǔn)

8、問(wèn)題的目標(biāo) 2建立模型運(yùn)籌學(xué)模型是一個(gè)能有效地達(dá)到一定目標(biāo)(或多個(gè)目標(biāo))行動(dòng)的系統(tǒng)，因此， 目標(biāo)一經(jīng)認(rèn)定，就要用數(shù)學(xué)語(yǔ)言描述問(wèn)題，建立目標(biāo)函數(shù)，分析問(wèn)題所處的環(huán)境確定約束條 件，探求與問(wèn)題有關(guān)的決策變量等，并選用合適的方法，建立運(yùn)籌學(xué)模型 3分析并求解模型根據(jù)所建模型的性質(zhì)及其數(shù)學(xué)待征，選擇適當(dāng)?shù)那蠼夥椒?，并求出模型的最?yōu)解或滿(mǎn)意解,4檢驗(yàn)并評(píng)價(jià)模型模型分析和計(jì)算得到結(jié)果以后，尚需按照它能否解決實(shí)際問(wèn)題，主要 考慮達(dá)成目標(biāo)的情況，選擇合適的標(biāo)準(zhǔn)，并通過(guò)一定的方法，例如靈敏度分析法、參數(shù)規(guī)劃法、 相關(guān)分析法等對(duì)模型結(jié)構(gòu)和一些基本參數(shù)進(jìn)行評(píng)價(jià)，以檢驗(yàn)它們是否準(zhǔn)確無(wú)誤，否則就要考 慮改換或修正模型，

9、增減計(jì)算過(guò)程中所用到的資料或數(shù)據(jù) 5應(yīng)用或?qū)嵤┠Ｐ偷慕饨?jīng)過(guò)反復(fù)檢查以后，最終應(yīng)用或?qū)嵤┠Ｐ偷慕?，就是供給決策者一套有科學(xué)依據(jù)的并為解決問(wèn)題所需要的數(shù)據(jù)、信息或方案以輔助決策者在處理問(wèn)題時(shí)作出正確的決策和行動(dòng)方案 從運(yùn)籌學(xué)模型中求出來(lái)的解不是問(wèn)題的最終答案，而僅僅是為實(shí)際問(wèn)題的科學(xué)處理提供了有用的、可以做為決策基礎(chǔ)的信息！,運(yùn)籌學(xué)模型（2）,運(yùn)籌學(xué)研究的主要內(nèi)容（1）,規(guī)劃理論（Programming Theory） 它主要研究如何有效利用有限資源，合理分配生產(chǎn)任務(wù)，選擇最佳生產(chǎn)布置以及合理安排物資調(diào)運(yùn)方案，以求取得最好的經(jīng)濟(jì)效果等問(wèn)題。 主要方法：線(xiàn)性規(guī)劃、非線(xiàn)性規(guī)劃和動(dòng)態(tài)規(guī)劃等 網(wǎng)絡(luò)分析理論

10、（Net-work Analysis Theory) 通過(guò)把研究的問(wèn)題構(gòu)造成網(wǎng)絡(luò)模型， 然后再加以數(shù)學(xué)或數(shù)量的分 析，以獲得最優(yōu)的決策效果。它已經(jīng)成功地解決了工程項(xiàng)目的計(jì) 劃安排問(wèn)題和物資運(yùn)輸中的最短路程問(wèn)題和最大流量問(wèn)題。 主要方法：關(guān)鍵路線(xiàn)法、計(jì)劃評(píng)審技術(shù)（統(tǒng)籌方法） 庫(kù)存理論（Inventory Theory） 研究在一定的采購(gòu)、運(yùn)輸條件下，使材料、物資保持合適的庫(kù)存水平，在保證生產(chǎn)或經(jīng)銷(xiāo)活動(dòng)能連續(xù)進(jìn)行的前提下，使材料、物資的庫(kù)存總費(fèi)用達(dá)到最小。 主要方法：存儲(chǔ)數(shù)學(xué)模型,運(yùn)籌學(xué)研究的主要內(nèi)容（2）,排隊(duì)理論（Queuing Theory） 用數(shù)學(xué)方法研究如何確定最適當(dāng)?shù)姆?wù)人員和服務(wù)設(shè)施

11、數(shù)目，達(dá)到服務(wù)質(zhì)量最好，服務(wù)費(fèi)用最低的目的。 主要方法：確定服務(wù)模型、隨機(jī)服務(wù)模型 決策理論（Decision-making Theory） 通過(guò)對(duì)各種客觀(guān)條件可能出現(xiàn)的概率進(jìn)行調(diào)安分析和對(duì)各種方案的經(jīng)濟(jì)效益進(jìn)行計(jì)算，研究方案的合理選擇問(wèn)題，使企業(yè)能因此而獲得最優(yōu)的經(jīng)濟(jì)效果。 主要方法：風(fēng)險(xiǎn)分析、效用分析、靈敏度分析等 對(duì)策理論（Game Theory） 研究處于競(jìng)爭(zhēng)狀態(tài)下， 企業(yè)雙方(或多方)可能采取的策略行動(dòng)，每一策略行動(dòng)給各方可能帶來(lái)的經(jīng)濟(jì)損益等問(wèn)題，通過(guò)數(shù)學(xué)分析，確定應(yīng)取哪一對(duì)策，才能使企業(yè)獲益最大(或損失最小)。 主要方法：矩陣對(duì)策模型、博弈論模型,第二章 線(xiàn)性規(guī)劃及單純形法,線(xiàn)性規(guī)

12、劃的發(fā)展,提出階段 前蘇聯(lián)數(shù)學(xué)家康托洛維奇在1939年著的生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法一 書(shū)中，首次提出了線(xiàn)性規(guī)劃問(wèn)題 美國(guó)學(xué)者希奇柯克(F.L Hitchock,1941)和柯普曼 (T. C Koopman，1947) 獨(dú)立提出了運(yùn)輸問(wèn)題這類(lèi)特殊的線(xiàn)性規(guī)劃問(wèn)題 發(fā)展階段 在1947 年，美國(guó)學(xué)者丹捷倍(G.B Dantzig)提出了線(xiàn)性規(guī)劃問(wèn)題的一般解法單純形法，為線(xiàn)性規(guī) 劃的發(fā)展奠定了基礎(chǔ)。 成熟應(yīng)用階段 40多年來(lái)，隨著電子計(jì)算機(jī)的發(fā)展，線(xiàn)性規(guī)劃已廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、 商業(yè)、交通運(yùn)輸、經(jīng)濟(jì)管理和國(guó)防等各個(gè)領(lǐng)域成為現(xiàn)代化管理的有力工具之一。,線(xiàn)性規(guī)劃研究的幾類(lèi)問(wèn)題,兩類(lèi)問(wèn)題 已有一定數(shù)量

13、的人力、物質(zhì)資源，研究怎樣充分和合理地使用這些資源，才能使完 成酌任務(wù)量最大； (max Z) 已確定了一項(xiàng)任務(wù)，研究怎樣合理安 排，才能使完成任務(wù)所耗費(fèi)的資源量最小。(min Z) 這兩類(lèi)問(wèn)題 是相互聯(lián)系的，或者說(shuō)是一個(gè)問(wèn)題的兩種不同提法，總的是要求 耗費(fèi)最小量的資源， 完成盡可能多的任務(wù)， 獲得最好的經(jīng)濟(jì)效 果。 實(shí)際應(yīng)用中的分類(lèi) 生產(chǎn)組織與計(jì)劃問(wèn)題、資源合理利用問(wèn)題、運(yùn)輸問(wèn)題、合理下料問(wèn)題、配料問(wèn)題、布局問(wèn)題,生產(chǎn)組織與計(jì)劃問(wèn)題（1）,問(wèn)題描述 一個(gè)工廠(chǎng)或車(chē)間有各種不同類(lèi) 型的設(shè)備各若干臺(tái)，各種不同設(shè)備生產(chǎn)各種零件的效率不同，在 一個(gè)生產(chǎn)周期，應(yīng)如何安排各設(shè)備的生產(chǎn)使得成全的產(chǎn)品總量最大

14、。 實(shí)例,某車(chē)間用三種不同型號(hào)的機(jī)床A1，A 2，A3加工B1，B2兩種零件。機(jī)床臺(tái)數(shù)、生產(chǎn)效率(每臺(tái)機(jī)床每個(gè)工作日完成零件的個(gè)數(shù))如表所示問(wèn)如何合理安排機(jī)床的加工任務(wù)，才能使生產(chǎn)的零件總數(shù)最多?,建立模型,生產(chǎn)組織與計(jì)劃問(wèn)題（2）,生產(chǎn)組織與規(guī)劃問(wèn)題的一般形式 某工廠(chǎng)用機(jī)床A1,A2,Am加工B1,B2,Bn種零件，在一個(gè)生產(chǎn)周期內(nèi)各機(jī)床可能的加工機(jī)時(shí)、工程必須完成各種零件的最小數(shù)量、各機(jī)床加工每個(gè)零件的時(shí)間（機(jī)時(shí)/個(gè)）和加工每個(gè)零件的成本（元/個(gè)）見(jiàn)下表。問(wèn)如何安排各機(jī)床的生產(chǎn)任務(wù)，才能完成加工任務(wù)，又使成本最低？,生產(chǎn)組織與計(jì)劃問(wèn)題（3）,表1,表2,建立模型,生產(chǎn)組織與計(jì)劃問(wèn)題（4）,

15、資源的合理利用問(wèn)題（1）,資源合理利用的一般形式 某廠(chǎng)計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)B1,B2,Bn。種產(chǎn)品，要消耗Al,A2,Am種資源。已知每件產(chǎn)品所消耗的資源數(shù)、每種資源的數(shù)量限制以及每 件產(chǎn)品可獲得的利潤(rùn)如下表所示。問(wèn)如何安排生 產(chǎn)計(jì)劃，才能充分利用現(xiàn)有資源，使獲得的總利潤(rùn)最 大？,建立模型,資源的合理利用問(wèn)題（2）,合理下料問(wèn)題（1）,問(wèn)題描述 在生產(chǎn)中經(jīng)常會(huì)遇到這樣的問(wèn)題，把長(zhǎng)度一定 的線(xiàn)材或板材截成尺寸不同曲零件毛坯，或在面積一定的 板材上切割形狀、尺寸不同的零件毛坯在一般情況 下很難使材料完全利用，總會(huì)多出一些料頭，如果恰當(dāng)?shù)拇钆湎铝?，則可以減少料頭、使原材料得到充 分利用，這就是

16、合理下料問(wèn)題問(wèn)題所要 解決的就是怎樣組成和選擇下料方案，在滿(mǎn)足各種零件毛坯數(shù)量要求的前提下使總的原材料消耗最少 實(shí)例 現(xiàn)有一批某種型號(hào)的圓鋼長(zhǎng)8m。需要裁取長(zhǎng)2.5m的毛坯100根、長(zhǎng)1.3m的毛坯 200根，問(wèn)應(yīng)該怎樣選擇下料方式，才能既滿(mǎn)足需要，又使總的用料最少?,建立模型 下料方案分析 數(shù)學(xué)模型,合理下料問(wèn)題（2）,合理下料問(wèn)題的一般形式 設(shè)用某種原材料截取零件A1,A2,Am的毛 坯，根據(jù)以往的經(jīng)驗(yàn)，在一件原材料上可以有B1,B2,Bn種不同的下料方式，每種下料方式可截得各種毛坯的個(gè)數(shù)以及每種毛坯的需要量如下表所示問(wèn)應(yīng)如何下料，才能既滿(mǎn)足需要又使原 材料消耗最少?,合理下料問(wèn)題（3）,

17、建立模型,合理下料問(wèn)題（4）,合理配料問(wèn)題（1）,合理配料問(wèn)題的一般形式 某飼養(yǎng)場(chǎng)用n種飼料B1,B2,Bn，配制成含有m種營(yíng)養(yǎng)成分A1,A2,Am的混合飼料，各種飼料所合營(yíng)養(yǎng)成分的數(shù)量、混合飼料對(duì)各種成 分的最低需要量以及各種飼料的單價(jià)如下表所 示。問(wèn)應(yīng)如何配料，才能既滿(mǎn)足需求，又使混合飼料總成本最低?,建立模型,合理配料問(wèn)題（2）,運(yùn)輸問(wèn)題（1）,問(wèn)題描述 在某一地區(qū)內(nèi)，有某種產(chǎn)品的產(chǎn)地與銷(xiāo)地各若干，把這種產(chǎn)品從各產(chǎn)地調(diào)運(yùn)到各銷(xiāo)地，調(diào)運(yùn)方案可以很多， 應(yīng)如何組織調(diào)運(yùn)，才能使總的運(yùn)費(fèi)或運(yùn)力(即總的運(yùn)輸噸公里 數(shù))最少。 實(shí)例 某公司下屬兩個(gè)工廠(chǎng)，生產(chǎn)同一種產(chǎn)品。產(chǎn)品均可運(yùn)往三個(gè)中心倉(cāng)庫(kù)去銷(xiāo)售

18、。已知每個(gè)工廠(chǎng)的產(chǎn)量，各倉(cāng)庫(kù)的銷(xiāo)量及各工廠(chǎng)到每個(gè)倉(cāng)庫(kù)的運(yùn)輸單價(jià)如下表所示。問(wèn)如何組織調(diào)運(yùn)可使生產(chǎn)與運(yùn)輸?shù)目傎M(fèi)用最少?,建立模型,運(yùn)輸問(wèn)題（2）,運(yùn)輸問(wèn)題的一般形式 設(shè)某種物資共有m個(gè)產(chǎn)地A1,A2,Am，其產(chǎn)量分別為a1,a2,am，另有n個(gè)銷(xiāo)地B1,B2,Bn，其銷(xiāo)量分別為b1,b2,bn，已知由產(chǎn) 地Ai (i=1,2,m)運(yùn)往銷(xiāo)地Bj的(j=1,2,n)的單位運(yùn)價(jià)為cij，其數(shù)據(jù)如下表所示，問(wèn)應(yīng)如何調(diào)運(yùn)，才能使總運(yùn)費(fèi)最省?,運(yùn)輸問(wèn)題（3）,建立模型,運(yùn)輸問(wèn)題（4）,運(yùn)輸問(wèn)題（5）,布局問(wèn)題（1）,布局問(wèn)題的一般形式 某農(nóng)場(chǎng)要在n塊土地B1,B2,Bn上種植m種作物A1,A2,Am ，各塊

19、土地的面積、各種作物計(jì)劃播種的面積以及各種作物在各塊土地上的單產(chǎn)如下表所示。問(wèn)應(yīng)如何合理安排種植計(jì)劃，才能使總產(chǎn)量最大？(假設(shè)計(jì)劃播種總面積等于土地總面積，即 ),建立模型,布局問(wèn)題（2）,線(xiàn)性規(guī)劃模型的建立（1）,線(xiàn)性規(guī)劃模型的特點(diǎn) 都有一組決策變量(x1,x2,xn)，決策變量的一組取值表示一個(gè)決策方案，且決策變量的取值一般都是非負(fù)的。 都有一組約束條件，約束決策變量的取值。 都有一個(gè)要達(dá)到的目標(biāo)，用目標(biāo)函數(shù)來(lái)表示。 目標(biāo)函數(shù)和約束條件都是線(xiàn)性等式或線(xiàn)性不等式。 線(xiàn)性規(guī)劃問(wèn)題求解的一般步驟 研究和明確問(wèn)題的要求和條件； 設(shè)定決策變量； 選定衡量目標(biāo)函數(shù)的數(shù)量指標(biāo)(利潤(rùn)、費(fèi)用、成本、產(chǎn)量等）

20、 收集和確定數(shù)學(xué)模型的所有參數(shù)數(shù)據(jù) 列出目標(biāo)函數(shù)的數(shù)學(xué)表達(dá)式 列出所有約束條件的線(xiàn)性數(shù)學(xué)表達(dá)式。,實(shí)例 有一艘貨輪，分前、中、后三個(gè)艙位，它們的容積與最大允許載重量如表1所示?，F(xiàn)有三種貨物待運(yùn)，已知有關(guān)數(shù)據(jù)列于表2。又為了航運(yùn)安全要求前、中、后艙在實(shí)際載重量上大體保持各艙最大允許載重量的比例關(guān)系。具體要求前、后艙分別與中艙之間載重量比例上偏差不超過(guò)15，前、后艙之間不超過(guò)10問(wèn)該貨輪應(yīng)裝載A、B、C各多少件，運(yùn)費(fèi)收入為最大?,線(xiàn)性規(guī)劃模型的建立（2）,表1,表2,問(wèn)題分析 （1）確定決策變量。 因?yàn)锳、B、C三種商品在貨輪的前、中、后艙均可裝載，令i=1,2,3分別代表商品A、B、C，用j1,

21、2,3分別代表前、中、后艙，設(shè)決策變量xij為裝于j艙位的第i種商品的數(shù)量(件). (2)確定目標(biāo)函數(shù) 商品A的件數(shù)為x11+x12+x13，即裝于貨輪前、中、后艙商品A的件數(shù)之和，類(lèi)似可得： 商品B的件數(shù)為x21+x22+x23 商品C的件數(shù)為x31+x32+x33 為使運(yùn)費(fèi)總收人最大，目標(biāo)函數(shù)為： maxZ=1000(x11+x12+x13)+700(x21+x22+x23)+600(x31+x32+x33),線(xiàn)性規(guī)劃模型的建立（3）,(3)確定約束條件 前、中、后艙位載重限制為,線(xiàn)性規(guī)劃模型的建立（4）,前、中、后艙位體積限制為,A、B、C三種商品的數(shù)量限制為,根據(jù)各艙實(shí)際載重大體應(yīng)保持

22、各艙最大允許載重量的比例關(guān)系，且前、后艙分別與中艙 之間載重量比例上偏差不超過(guò)15，前、后艙之間不超過(guò)10可得艙體平衡條件為：,線(xiàn)性規(guī)劃模型的建立（5）,各決策變量要求非負(fù)，即,建立模型,線(xiàn)性規(guī)劃模型的建立（5）,相關(guān)概念 可行解 滿(mǎn)足線(xiàn)性規(guī)劃問(wèn)題約束條件的解，都稱(chēng)為該線(xiàn)性規(guī)劃問(wèn)題的可行解，所有可行解集合稱(chēng)為可行解集（或可行域）。 最優(yōu)解 是目標(biāo)函數(shù)達(dá)到最優(yōu)值（最大值或最小值）的可行解，稱(chēng)為最優(yōu)解。 凸多邊形區(qū)域 設(shè)x1,x2為多邊形區(qū)域中的兩點(diǎn)，若兩點(diǎn)連線(xiàn)上的任意一點(diǎn)，即 ax1+（1-a)x2,(0a1)仍屬于該多邊形區(qū)域，則該多邊形區(qū)域?yàn)橥苟噙呅螀^(qū)域。 任何兩個(gè)凸多邊形區(qū)域的集合仍為凸多