線性規(guī)劃及其基本理論課件

運(yùn)籌學(xué)Operationsresearch陳志松Mob籌學(xué)1線性規(guī)劃及其基本理論口線性規(guī)劃概述口線性規(guī)劃問(wèn)題口線性規(guī)劃數(shù)學(xué)模型般模型標(biāo)準(zhǔn)模型口線性規(guī)劃解的概念可行解、最優(yōu)解基陣、基解、基可行解口線性規(guī)劃的基本性質(zhì)線性規(guī)劃及其基本理論2線性規(guī)劃概述口線性規(guī)劃(LinearProgramming,簡(jiǎn)記為L(zhǎng)P)是運(yùn)籌學(xué)中的一個(gè)最重要、應(yīng)用最廣泛的分支?？诰€性規(guī)劃及其通用解法-單純形法一般認(rèn)為是美國(guó)學(xué)者丹捷格(GDantzig)在1947年研究美國(guó)空軍軍事規(guī)劃時(shí)提出的口蘇聯(lián)學(xué)者康托洛維奇在1939年解決工業(yè)生產(chǎn)組織與計(jì)劃問(wèn)題時(shí)就提出類(lèi)似線性規(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ī)劃概述3線性規(guī)劃問(wèn)題提出在生產(chǎn)管理和經(jīng)營(yíng)活動(dòng)中經(jīng)常會(huì)提出這樣一類(lèi)問(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)品均能銷(xiāo)售出去企業(yè)可提供的兩種原材料和勞動(dòng)時(shí)間的數(shù)量是有限的。產(chǎn)品A與產(chǎn)品B各應(yīng)生產(chǎn)多少,可使企業(yè)總利潤(rùn)最大?線性規(guī)劃問(wèn)題提出4線性規(guī)劃問(wèn)題提出上述這些問(wèn)題有如下共同特點(diǎn):□問(wèn)題解決要滿足一定條件,稱(chēng)為約束條件;口問(wèn)題有多個(gè)滿足條件的解決方案;口問(wèn)題解決有明確的目標(biāo)要求,對(duì)應(yīng)不同方案有不同目標(biāo)值,可表示成目標(biāo)函數(shù)線性規(guī)劃問(wèn)題提出5何謂線性規(guī)劃問(wèn)題口最優(yōu)化問(wèn)題我們稱(chēng)如下一般問(wèn)題:“在一定約束條件下,求目標(biāo)函數(shù)的最大或最小值”為最優(yōu)化問(wèn)題,用數(shù)學(xué)模型描述的最優(yōu)化問(wèn)題,稱(chēng)為數(shù)學(xué)規(guī)劃問(wèn)題口線性規(guī)劃問(wèn)題在最優(yōu)化問(wèn)題中,如果約束條件與目標(biāo)函數(shù)均是線性的,我們就稱(chēng)之為線性規(guī)劃問(wèn)題。何謂線性規(guī)劃問(wèn)題6線性規(guī)劃問(wèn)題的三個(gè)要素口決策變量決策問(wèn)題待定的量值稱(chēng)為決策變量決策變量的取值有時(shí)要求非負(fù)。口約束條件任何問(wèn)題都是限定在一定的條件下求解,把各種限制條件表示為一組等式或不等式,稱(chēng)之為約束條件?！黾s束條件是決策方案可行的保障LP的約束條件,都是決策變量的線性函數(shù)目標(biāo)函數(shù)衡量決策方案優(yōu)劣的準(zhǔn)則,如時(shí)間最省、利潤(rùn)最大、成本最低。目標(biāo)函數(shù)是決策變量的線性函數(shù)?！鲇械哪繕?biāo)要實(shí)現(xiàn)極大,有的則要求極小線性規(guī)劃問(wèn)題的三個(gè)要素7線性規(guī)劃數(shù)學(xué)模型例生產(chǎn)計(jì)劃問(wèn)題某廠生產(chǎn)甲乙兩種產(chǎn)品,各自的零部件分別在A、B車(chē)間生產(chǎn),最后都需在c車(chē)間裝配,相關(guān)數(shù)據(jù)如表所示:產(chǎn)品工時(shí)單耗生產(chǎn)能力車(chē)間乙ABc甲1333822451236單位產(chǎn)品獲利問(wèn)如何安排甲、乙兩產(chǎn)品的產(chǎn)量,使利潤(rùn)為最大線性規(guī)劃數(shù)學(xué)模型8線性規(guī)劃數(shù)學(xué)模型口建立數(shù)學(xué)模型的步驟:Step1分析實(shí)際問(wèn)題;Step2確定決策變量;Step3找出約束條件;Step4確定目標(biāo)函數(shù);Step5整理、寫(xiě)出數(shù)學(xué)模型。線性規(guī)劃數(shù)學(xué)模型9線性規(guī)劃問(wèn)題舉例例1.1】某市今年要興建大量住宅,已知有三種住宅體系可以大量興建,各體系資源用量及今年供應(yīng)量見(jiàn)下表:資源造價(jià)鋼材水泥磚人工住宅體系〔元/m2)(公斤/m2)(公斤/m)(塊/m2)(工日/m2)磚混住宅105121102104.5壁板住宅135301903.0大模住宅120251803.5資源限量11000020000|1500001470004000(千元)(噸)(噸)(千塊)(千工日要求在充分利用各種資源條件下使建造住宅的總面積為最大(即求安排各住宅多少m2),求建造方案。線性規(guī)劃問(wèn)題舉例10線性規(guī)劃及其基本理論課件11線性規(guī)劃及其基本理論課件12線性規(guī)劃及其基本理論課件13線性規(guī)劃及其基本理論課件14線性規(guī)劃及其基本理論課件15線性規(guī)劃及其基本理論課件16線性規(guī)劃及其基本理論課件17線性規(guī)劃及其基本理論課件18線性規(guī)劃及其基本理論課件19線性規(guī)劃及其基本理論課件20線性規(guī)劃及其基本理論課件21線性規(guī)劃及其基本理論課件22線性規(guī)劃及其基本理論課件23線性規(guī)劃及其基本理論課件24線性規(guī)劃及其基本理論課件25線性規(guī)劃及其基本理論課件26線性規(guī)劃及其基本理論課件27線性規(guī)劃及其基本理論課件28線性規(guī)劃及其基本理論課件29線性規(guī)劃及其基本理論課件30線性規(guī)劃及其基本理論課件31線性規(guī)劃及其基本理論課件32線性規(guī)劃及其基本理論課件33線性規(guī)劃及其基本理論課件34線性規(guī)劃及其基本理論課件35線性規(guī)劃及其基本理論課件36線性規(guī)劃及其基本理論課件37線性規(guī)劃及其基本理論課件38線性規(guī)劃及其基本理論課件39線性規(guī)劃及其基本理論課件40線性規(guī)劃及其基本理論課件41線性規(guī)劃及其基本理論課件42線性規(guī)劃及其基本理論課件43線性規(guī)劃及其基本理論課件44運(yùn)籌學(xué)Operationsresearch陳志松Mob籌學(xué)45線性規(guī)劃及其基本理論口線性規(guī)劃概述口線性規(guī)劃問(wèn)題口線性規(guī)劃數(shù)學(xué)模型般模型標(biāo)準(zhǔn)模型口線性規(guī)劃解的概念可行解、最優(yōu)解基陣、基解、基可行解口線性規(guī)劃的基本性質(zhì)線性規(guī)劃及其基本理論46線性規(guī)劃概述口線性規(guī)劃(LinearProgramming,簡(jiǎn)記為L(zhǎng)P)是運(yùn)籌學(xué)中的一個(gè)最重要、應(yīng)用最廣泛的分支?？诰€性規(guī)劃及其通用解法-單純形法一般認(rèn)為是美國(guó)學(xué)者丹捷格(GDantzig)在1947年研究美國(guó)空軍軍事規(guī)劃時(shí)提出的口蘇聯(lián)學(xué)者康托洛維奇在1939年解決工業(yè)生產(chǎn)組織與計(jì)劃問(wèn)題時(shí)就提出類(lèi)似線性規(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ī)劃概述47線性規(guī)劃問(wèn)題提出在生產(chǎn)管理和經(jīng)營(yíng)活動(dòng)中經(jīng)常會(huì)提出這樣一類(lèi)問(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)品均能銷(xiāo)售出去企業(yè)可提供的兩種原材料和勞動(dòng)時(shí)間的數(shù)量是有限的。產(chǎn)品A與產(chǎn)品B各應(yīng)生產(chǎn)多少,可使企業(yè)總利潤(rùn)最大?線性規(guī)劃問(wèn)題提出48線性規(guī)劃問(wèn)題提出上述這些問(wèn)題有如下共同特點(diǎn):□問(wèn)題解決要滿足一定條件,稱(chēng)為約束條件;口問(wèn)題有多個(gè)滿足條件的解決方案;口問(wèn)題解決有明確的目標(biāo)要求,對(duì)應(yīng)不同方案有不同目標(biāo)值,可表示成目標(biāo)函數(shù)線性規(guī)劃問(wèn)題提出49何謂線性規(guī)劃問(wèn)題口最優(yōu)化問(wèn)題我們稱(chēng)如下一般問(wèn)題:“在一定約束條件下,求目標(biāo)函數(shù)的最大或最小值”為最優(yōu)化問(wèn)題,用數(shù)學(xué)模型描述的最優(yōu)化問(wèn)題,稱(chēng)為數(shù)學(xué)規(guī)劃問(wèn)題口線性規(guī)劃問(wèn)題在最優(yōu)化問(wèn)題中,如果約束條件與目標(biāo)函數(shù)均是線性的,我們就稱(chēng)之為線性規(guī)劃問(wèn)題。何謂線性規(guī)劃問(wèn)題50線性規(guī)劃問(wèn)題的三個(gè)要素口決策變量決策問(wèn)題待定的量值稱(chēng)為決策變量決策變量的取值有時(shí)要求非負(fù)。口約束條件任何問(wèn)題都是限定在一定的條件下求解,把各種限制條件表示為一組等式或不等式,稱(chēng)之為約束條件。■約束條件是決策方案可行的保障LP的約束條件,都是決策變量的線性函數(shù)目標(biāo)函數(shù)衡量決策方案優(yōu)劣的準(zhǔn)則,如時(shí)間最省、利潤(rùn)最大、成本最低。目標(biāo)函數(shù)是決策變量的線性函數(shù)。■有的目標(biāo)要實(shí)現(xiàn)極大,有的則要求極小線性規(guī)劃問(wèn)題的三個(gè)要素51線性規(guī)劃數(shù)學(xué)模型例生產(chǎn)計(jì)劃問(wèn)題某廠生產(chǎn)甲乙兩種產(chǎn)品,各自的零部件分別在A、B車(chē)間生產(chǎn),最后都需在c車(chē)間裝配,相關(guān)數(shù)據(jù)如表所示:產(chǎn)品工時(shí)單耗生產(chǎn)能力車(chē)間乙ABc甲1333822451236單位產(chǎn)品獲利問(wèn)如何安排甲、乙兩產(chǎn)品的產(chǎn)量,使利潤(rùn)為最大線性規(guī)劃數(shù)學(xué)模型52線性規(guī)劃數(shù)學(xué)模型口建立數(shù)學(xué)模型的步驟:Step1分析實(shí)際問(wèn)題;Step2確定決策變量;Step3找出約束條件;Step4確定目標(biāo)函數(shù);Step5整理、寫(xiě)出數(shù)學(xué)模型。線性規(guī)劃數(shù)學(xué)模型53線性規(guī)劃問(wèn)題舉例例1.1】某市今年要興建大量住宅,已知有三種住宅體系可以大量興建,各體系資源用量及今年供應(yīng)量見(jiàn)下表:資源造價(jià)鋼材水泥磚人工住宅體系〔元/m2)(公斤/m2)(公斤/m)(塊/m2)(工日/m2)磚混住宅105121102104.5壁板住宅135301903.0大模住宅120251803.5資源限量11000020000|1500001470004000(千元)(噸)(噸)(千塊)(千工日要求在充分利用各種資源條件下使建造住宅的總面積為最大(即求安排各住宅多少m2),求建造方案。線性規(guī)劃問(wèn)題舉例54線性規(guī)劃及其基本理論課件55線性規(guī)劃及其基本理論課件56線性規(guī)劃及其基本理論課件57線性規(guī)劃及其基本理論課件58線性規(guī)劃及其基本理論課件59線性規(guī)劃及其基本理論課件60線性規(guī)劃及其基本理論課件61線性規(guī)劃及其基本理論課件62線性規(guī)劃及其基本理論課件63線性規(guī)劃及其基本理論課件64線性規(guī)劃及其基本理論課件65線性規(guī)劃及其基本理論課件66線性規(guī)劃及其基本理論課件67線性規(guī)劃及其基本理論課件68線性規(guī)劃及其基本理論課件69線性規(guī)劃及其基本理論課件70線性規(guī)劃及其基本理論課件71線性規(guī)劃及其基本理論課件72線性規(guī)劃及其基本理論課件73線性規(guī)劃及其基本理論