線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型.ppt
《線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型.ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型.ppt(36頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
LinearProgramming,運(yùn)籌學(xué)課件,線性規(guī)劃,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型圖解法單純形法原理單純形法計(jì)算步驟單純形法的進(jìn)一步討論數(shù)據(jù)包絡(luò)其他應(yīng)用例子案例分析,線性規(guī)劃概述,線性規(guī)劃(LinearProgramming,簡(jiǎn)記為L(zhǎng)P)是運(yùn)籌學(xué)中的一個(gè)最重要、應(yīng)用最廣泛的分支。線性規(guī)劃及其通用解法--單純形法一般認(rèn)為是美國(guó)學(xué)者丹捷格(G.Dantzig)在1947年研究美國(guó)空軍軍事規(guī)劃時(shí)提出的。蘇聯(lián)學(xué)者康托洛維奇在1939年解決工業(yè)生產(chǎn)組織與計(jì)劃問(wèn)題時(shí)就提出類似線性規(guī)劃的模型及解法;康托洛維奇的工作當(dāng)時(shí)沒(méi)有被重視,但直到1960年康托洛維奇再次發(fā)表《最佳資源利用的經(jīng)濟(jì)計(jì)算》一書(shū)后,才受到重視。一些常見(jiàn)的帶有Spreadsheet的軟件,如:Excel、Lotus1-2-3等,均有內(nèi)置的線性規(guī)劃求解功能。最優(yōu)化問(wèn)題求解軟件,如:Lindo、Lingo、Matlab等。,線性規(guī)劃問(wèn)題提出,在生產(chǎn)管理和經(jīng)營(yíng)活動(dòng)中經(jīng)常會(huì)提出這樣一類問(wèn)題:如何利用有限的人力、物力、財(cái)力等資源,取得最好的效果。例如:配載問(wèn)題一交通工具,運(yùn)輸幾種不同體積、重量的物資,如何裝配,所運(yùn)的物資最多?下料問(wèn)題用圓鋼制造長(zhǎng)度不等的機(jī)軸,如何下料,所剩的余料最少?生產(chǎn)計(jì)劃問(wèn)題企業(yè)生產(chǎn)A、B兩種電器產(chǎn)品,兩種產(chǎn)品的市場(chǎng)需求狀況可以確定,按當(dāng)前的定價(jià)可確保所有產(chǎn)品均能銷售出去。企業(yè)可提供的兩種原材料和勞動(dòng)時(shí)間的數(shù)量是有限的。產(chǎn)品A與產(chǎn)品B各應(yīng)生產(chǎn)多少,可使企業(yè)總利潤(rùn)最大?,線性規(guī)劃問(wèn)題提出,上述這些問(wèn)題有如下共同特點(diǎn):?jiǎn)栴}解決要滿足一定條件,稱為約束條件;問(wèn)題有多個(gè)滿足條件的解決方案;問(wèn)題解決有明確的目標(biāo)要求,對(duì)應(yīng)不同方案有不同目標(biāo)值,可表示成目標(biāo)函數(shù)。,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,問(wèn)題提出與建模生產(chǎn)計(jì)劃問(wèn)題運(yùn)輸問(wèn)題線性規(guī)劃模型一般形式規(guī)范形式標(biāo)準(zhǔn)形式形式轉(zhuǎn)換,常山機(jī)械廠制造Ⅰ、Ⅱ兩種產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)備A、B、C的臺(tái)時(shí),每天可用于這兩種家電的能力、各售出一件時(shí)的獲利情況如下表所示。問(wèn)該企業(yè)應(yīng)制造兩種產(chǎn)品各多少件,可使獲取的利潤(rùn)最大。,生產(chǎn)計(jì)劃問(wèn)題,問(wèn)題分析,模型,運(yùn)輸問(wèn)題,問(wèn)題分析,模型,線性規(guī)劃問(wèn)題的三個(gè)要素,決策變量決策問(wèn)題待定的量值稱為決策變量。決策變量的取值有時(shí)要求非負(fù)。約束條件任何問(wèn)題都是限定在一定的條件下求解,把各種限制條件表示為一組等式或不等式,稱之為約束條件。約束條件是決策方案可行的保障。LP的約束條件,都是決策變量的線性函數(shù)。目標(biāo)函數(shù)衡量決策方案優(yōu)劣的準(zhǔn)則,如時(shí)間最省、利潤(rùn)最大、成本最低。目標(biāo)函數(shù)是決策變量的線性函數(shù)。有的目標(biāo)要實(shí)現(xiàn)極大,有的則要求極小。,何謂線性規(guī)劃問(wèn)題,最優(yōu)化問(wèn)題我們稱如下一般問(wèn)題:“在一定約束條件下,求目標(biāo)函數(shù)的最大或最小值”為最優(yōu)化問(wèn)題,用數(shù)學(xué)模型描述的最優(yōu)化問(wèn)題,稱為數(shù)學(xué)規(guī)劃問(wèn)題。線性規(guī)劃問(wèn)題在最優(yōu)化問(wèn)題中,如果約束條件與目標(biāo)函數(shù)均是線性的,我們就稱之為線性規(guī)劃問(wèn)題。,線性規(guī)劃的數(shù)學(xué)模型,如果規(guī)劃問(wèn)題的數(shù)學(xué)模型中,決策變量的取值是連續(xù)的,既可以為整數(shù),也可以為分?jǐn)?shù)、小數(shù)或?qū)崝?shù),目標(biāo)函數(shù)是決策變量的線性函數(shù),約束條件是含決策變量的線性等式或不等式,則該規(guī)劃問(wèn)題的數(shù)學(xué)模型為線性規(guī)劃的數(shù)學(xué)模型。,線性規(guī)劃數(shù)學(xué)模型,建立線性規(guī)劃問(wèn)題數(shù)學(xué)模型的步驟:Step1分析實(shí)際問(wèn)題;Step2確定決策變量;Step3找出約束條件;Step4確定目標(biāo)函數(shù);Step5整理、寫(xiě)出數(shù)學(xué)模型。,【例1.1】某市今年要興建大量住宅,已知有三種住宅體系可以大量興建,各體系資源用量及今年供應(yīng)量見(jiàn)下表:要求在充分利用各種資源條件下使建造住宅的總面積為最大(即求安排各住宅多少m2),求建造方案。,線性規(guī)劃問(wèn)題舉例,【例1.2】最優(yōu)生產(chǎn)計(jì)劃問(wèn)題。某企業(yè)在計(jì)劃期內(nèi)計(jì)劃生產(chǎn)甲、乙、丙三種產(chǎn)品。這些產(chǎn)品分別需要要在設(shè)備A、B上加工,需要消耗材料C、D,按工藝資料規(guī)定,單件產(chǎn)品在不同設(shè)備上加工及所需要的資源如表1.1所示。已知在計(jì)劃期內(nèi)設(shè)備的加工能力各為200臺(tái)時(shí),可供材料分別為360、300公斤;每生產(chǎn)一件甲、乙、丙三種產(chǎn)品,企業(yè)可獲得利潤(rùn)分別為40、30、50元,假定市場(chǎng)需求無(wú)限制。企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃,使企業(yè)在計(jì)劃期內(nèi)總的利潤(rùn)收入最大?,線性規(guī)劃問(wèn)題舉例,產(chǎn)品資源消耗表,【例1.3】某商場(chǎng)決定:營(yíng)業(yè)員每周連續(xù)工作5天后連續(xù)休息2天,輪流休息。根據(jù)統(tǒng)計(jì),商場(chǎng)每天需要的營(yíng)業(yè)員如表1.2所示。,表1.2營(yíng)業(yè)員需要量統(tǒng)計(jì)表,商場(chǎng)人力資源部應(yīng)如何安排每天的上班人數(shù),使商場(chǎng)總的營(yíng)業(yè)員最少。,線性規(guī)劃問(wèn)題舉例,【例1.4】合理用料問(wèn)題。某汽車需要用甲、乙、丙三種規(guī)格的軸各一根,這些軸的規(guī)格分別是1.5,1,0.7(m),這些軸需要用同一種圓鋼來(lái)做,圓鋼長(zhǎng)度為4m?,F(xiàn)在要制造1000輛汽車,最少要用多少圓鋼來(lái)生產(chǎn)這些軸?,線性規(guī)劃問(wèn)題舉例,注意:(1)求下料方案時(shí)應(yīng)注意,余料不能超過(guò)最短毛坯的長(zhǎng)度;(2)最好將毛坯長(zhǎng)度按降的次序排列,即先切割長(zhǎng)度最長(zhǎng)的毛坯,再切割次長(zhǎng)的,最后切割最短的,不能遺漏了方案。(3)如果方案較多,用計(jì)算機(jī)編程排方案,去掉余料較長(zhǎng)的方案,進(jìn)行初選。,,【例1.5】配料問(wèn)題。某鋼鐵公司生產(chǎn)一種合金,要求的成分規(guī)格是:錫不少于28%,鋅不多于15%,鉛恰好10%,鎳要界于35%~55%之間,不允許有其他成分。鋼鐵公司擬從五種不同級(jí)別的礦石中進(jìn)行冶煉,每種礦物的成分含量和價(jià)格如表1.4所示。礦石雜質(zhì)在治煉過(guò)程中廢棄,現(xiàn)要求每噸合金成本最低的礦物數(shù)量。假設(shè)礦石在冶煉過(guò)程中,合金含量沒(méi)有發(fā)生變化。,表1.4礦石的金屬含量,,線性規(guī)劃問(wèn)題舉例,解:設(shè)xj(j=1,2,…,5)是第j種礦石數(shù)量,得到下列線性規(guī)劃模型,注意:礦石在實(shí)際冶煉時(shí)金屬含量會(huì)發(fā)生變化,建模時(shí)應(yīng)將這種變化考慮進(jìn)去,有可能是非線性關(guān)系。配料問(wèn)題也稱配方問(wèn)題、營(yíng)養(yǎng)問(wèn)題或混合問(wèn)題,在許多行業(yè)生產(chǎn)中都能遇到。,【例1.6】投資問(wèn)題。某投資公司在第一年有200萬(wàn)元資金,每年都有如下的投資方案可供考慮采納:“假使第一年投入一筆資金,第二年又繼續(xù)投入此資金的50%,那么到第三年就可回收第一年投入資金的一倍金額”。投資公司決定最優(yōu)的投資策略使第六年所掌握的資金最多。,,線性規(guī)劃問(wèn)題舉例,,【例1.7】均衡配套生產(chǎn)問(wèn)題。某產(chǎn)品由2件甲、3件乙零件組裝而成。兩種零件必須經(jīng)過(guò)設(shè)備A、B上加工,每件甲零件在A、B上的加工時(shí)間分別為5分鐘和9分鐘,每件乙零件在A、B上的加工時(shí)間分別為4分鐘和10分鐘?,F(xiàn)有2臺(tái)設(shè)備A和3臺(tái)設(shè)備B,每天每臺(tái)可供加工時(shí)間為8小時(shí)。為了保持兩種設(shè)備均衡負(fù)荷生產(chǎn),要求一種設(shè)備每天的加工總時(shí)間不超過(guò)另一種設(shè)備總時(shí)間1小時(shí)。怎樣安排設(shè)備的加工時(shí)間使每天產(chǎn)品的產(chǎn)量最大。,線性規(guī)劃問(wèn)題舉例,,,線性規(guī)劃問(wèn)題的一般形式,目標(biāo)函數(shù),約束條件,,,假定線性規(guī)劃問(wèn)題有n個(gè)決策變量,m個(gè)約束條件。一般地,線性規(guī)劃問(wèn)題數(shù)學(xué)模型中可表示成如下形式:,注釋,規(guī)范形式,標(biāo)準(zhǔn)形式,模型轉(zhuǎn)換,約束轉(zhuǎn)換實(shí)例,目標(biāo)轉(zhuǎn)換,變量轉(zhuǎn)換,約束轉(zhuǎn)換,不等式變等式不等式變不等式,等式變不等式,,,不等式變等式,松弛變量,,剩余變量,,不等式變不等式,例1把問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式,例1把問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式,練習(xí)將下列問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式,- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 線性規(guī)劃 問(wèn)題 及其 數(shù)學(xué)模型
鏈接地址:http://kudomayuko.com/p-3510623.html