線性規(guī)劃圖解法(經(jīng)典運(yùn)籌學(xué))

上堂課主要內(nèi)容：一、線性規(guī)劃模型引例二、線性規(guī)劃模型的建立

精選課件

1、建模的一般步驟：步驟一：確定決策變量即用變量取不同的值來(lái)表示可供選擇的各種不同方案步驟二：建立目標(biāo)函數(shù)即找到目標(biāo)值與決策變量的數(shù)量關(guān)系步驟三：確定約束條件即決策變量所受到的外界條件的制約。約束條件一般為決策變量的等式或不等式要求：目標(biāo)函數(shù)與約束條件均是線性的，且目標(biāo)函數(shù)只能是一個(gè)。精選課件2、線性規(guī)劃模型的一般形式：決策變量約束方程非負(fù)約束目標(biāo)函數(shù)精選課件三、線性規(guī)劃求解：四、線性規(guī)劃應(yīng)用舉例計(jì)算機(jī)應(yīng)用軟件精選課件時(shí)間所需售貨員人數(shù)星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人例3福安商場(chǎng)是個(gè)中型的百貨商場(chǎng)，它對(duì)售貨人員的需求經(jīng)過(guò)統(tǒng)計(jì)分析如下所示：為保證售貨人員充分休息，售貨人員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的，問(wèn)應(yīng)該如何安排售貨人員的作息，既滿(mǎn)足了工作的需要，又使配備的售貨人員的人數(shù)最少？解精選課件時(shí)間所需售貨員人數(shù)星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人約束條件:星期日售貨員人數(shù)要求:星期一售貨員人數(shù)要求:星期二售貨員人數(shù)要求:星期三售貨員人數(shù)要求:星期四售貨員人數(shù)要求:星期五售貨員人數(shù)要求:星期六售貨員人數(shù)要求:數(shù)學(xué)模型:非負(fù)約束:精選課件數(shù)學(xué)模型:解得:精選課件時(shí)間所需售貨員人數(shù)星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人例3福安商場(chǎng)是個(gè)中型的百貨商場(chǎng)，它對(duì)售貨人員的需求經(jīng)過(guò)統(tǒng)計(jì)分析如下所示：為保證售貨人員充分休息，售貨人員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的，問(wèn)應(yīng)該如何安排售貨人員的作息，既滿(mǎn)足了工作的需要，又使配備的售貨人員的人數(shù)最少？解精選課件方案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合計(jì)7.4m7.3m7.2m7.1m6.6下角料0m0.1m0.2m0.3m0.8m方案下料數(shù)(根)長(zhǎng)度例4某工廠要做100套鋼架,每套用長(zhǎng)為2.9m,2.1m,和1.5m的圓鋼各一根,原料每根長(zhǎng)7.4m,問(wèn)應(yīng)如何下料,可使所用原料最省.分析:每根原料做一套鋼架,下角料：0.9m用套裁方式下料方案：精選課件方案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合計(jì)7.4m7.3m7.2m7.1m6.6下角料0m0.1m0.2m0.3m0.8m方案下料數(shù)(根)長(zhǎng)度下料方案：精選課件方案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合計(jì)7.4m7.3m7.2m7.1m6.6下角料0m0.1m0.2m0.3m0.8m方案下料數(shù)(根)長(zhǎng)度例4某工廠要做100套鋼架,每套用長(zhǎng)為2.9m,2.1m,和1.5m的圓鋼各一根,原料每根長(zhǎng)7.4m,問(wèn)應(yīng)如何下料,可使所用原料最省.下料方案：最優(yōu)下料方案：按方案1下料30根，方案2下料10根，方案4下料50根，共需原料90根。精選課件例5(產(chǎn)品配套問(wèn)題〕假定一個(gè)工廠的甲、乙、丙三個(gè)車(chē)間生產(chǎn)同一個(gè)產(chǎn)品，每件產(chǎn)品包括4個(gè)A零件，和3個(gè)B零件。這兩種零件由兩種不同的原材料制成，而這兩種原材料的現(xiàn)有數(shù)額分別為100克和200克。每個(gè)生產(chǎn)班的原材料需要量和零件產(chǎn)量如下表所示。問(wèn)這三個(gè)車(chē)間各應(yīng)開(kāi)多少班才能使這種產(chǎn)品的配套數(shù)到達(dá)最大約束條件為：精選課件三個(gè)車(chē)間共生產(chǎn)A零件：三個(gè)車(chē)間共生產(chǎn)B零件非線性要求：目標(biāo)函數(shù)：目標(biāo)函數(shù)Z=x4線性精選課件數(shù)學(xué)模型：線性規(guī)劃問(wèn)題精選課件例6〔多周期動(dòng)態(tài)生產(chǎn)方案問(wèn)題〕華津機(jī)器制造廠專(zhuān)為拖拉機(jī)廠配套生產(chǎn)柴油機(jī)，今年頭四個(gè)月收到的定單數(shù)量分別為3000臺(tái)、4500臺(tái)、3500臺(tái)、5000臺(tái)。該廠正常生產(chǎn)每月可生產(chǎn)3000臺(tái)，利用加班還可生產(chǎn)1500臺(tái)，正常生產(chǎn)本錢(qián)為每臺(tái)5000元，加工生產(chǎn)還要追加1500元，庫(kù)存本錢(qián)為每臺(tái)每月200元。問(wèn)華津廠如何組織生產(chǎn)才能使生產(chǎn)本錢(qián)最低？分析：設(shè)C=本錢(qián)=四個(gè)月正常生產(chǎn)的本錢(qián)+四個(gè)月加班生產(chǎn)的本錢(qián)+四個(gè)月庫(kù)存本錢(qián)約束條件：精選課件需求約束：第4個(gè)月第3個(gè)月第2個(gè)月第1個(gè)月生產(chǎn)能力約束：數(shù)學(xué)模型：四個(gè)月定單數(shù)量分別為3000臺(tái)、4500臺(tái)、3500臺(tái)、5000臺(tái)每月可生產(chǎn)3000臺(tái)，利用加班還可生產(chǎn)1500臺(tái)庫(kù)存約束：精選課件例7.連續(xù)投資問(wèn)題建模:某投資公司有100萬(wàn)元資金用于投資，投資的方案可以有以下六種，現(xiàn)要做一個(gè)5年期的投資方案，具體可選擇的投資方案如下：方案A：5年內(nèi)的每年年初均可投資，且金額不限，投資期限1年，年投資回報(bào)率7%。方案B：5年內(nèi)的每年年初均可投資，且金額不限，投資期限2年，年投資回報(bào)率10%〔不計(jì)復(fù)利〕。方案C：5年內(nèi)的每年年初均可投資，且金額不限，投資期限3年，年投資回報(bào)率12%〔不計(jì)復(fù)利〕方案D：只在第一年年初有一次投資時(shí)機(jī)，最大投資金額為50萬(wàn)元，投資期限4年，年投資回報(bào)率20%方案E：在第二年和第四年年初有一次投資時(shí)機(jī)，最大投資金額均為30萬(wàn)元，投資期限1年，年投資回報(bào)率30%方案F：在第四年年初有一次投資時(shí)機(jī)，金額不限，投資期限2年，年投資回報(bào)率25%假設(shè)當(dāng)年的投資金額及其收益均可用于下一年的投資，問(wèn)公司應(yīng)如何投資才能使第五年末收回的資金最多？精選課件假設(shè)當(dāng)年的投資金額及其收益均可用于下一年的投資，問(wèn)公司應(yīng)如何投資才能使第五年末收回的資金最多？精選課件連續(xù)投資問(wèn)題模型:精選課件1.1.2、線性規(guī)劃的標(biāo)準(zhǔn)形式和矩陣表達(dá)式線性規(guī)劃問(wèn)題的一般形式：精選課件1、線性規(guī)劃的標(biāo)準(zhǔn)形式精選課件標(biāo)準(zhǔn)型式的特征:1、求目標(biāo)函數(shù)的最大值2、約束方程為等式方程3、約束方程的右邊非負(fù)4、決策變量均非負(fù)非標(biāo)準(zhǔn)型式有以下幾種可能：1、求目標(biāo)函數(shù)的最小值4、決策變量<0或無(wú)限制2、約束方程為不等式方程3、約束方程的右邊精選課件2、非標(biāo)準(zhǔn)型式線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)化-max〔1〕對(duì)求目標(biāo)函數(shù)最小值:=精選課件〔2〕約束條件為“≤〞型松弛變量精選課件〔3〕約束條件為“≥〞型剩余變量精選課件(4)約束條件右邊為負(fù)〔6〕決策變量無(wú)符號(hào)限制〔5〕決策變量≤0例如帶入約束方程及目標(biāo)函數(shù)精選課件那么原線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型為:精選課件精選課件3.線性規(guī)劃問(wèn)題的矩陣表達(dá)式：精選課件§1.3線性規(guī)劃的基本理論精選課件一、線性規(guī)劃的解1、可行解：2、可行域：〔LP〕的全體可行解構(gòu)成的集合稱(chēng)為可行域3、最優(yōu)解及最優(yōu)值：設(shè)S是〔LP〕的可行域不唯一唯一4、假設(shè)對(duì)任意大的M>0,都存在可行解使得該線性規(guī)劃的目標(biāo)函數(shù)值，那么稱(chēng)該線性規(guī)劃問(wèn)題無(wú)界精選課件二、兩個(gè)變量的線性規(guī)劃的圖解法解：〔1〕在直角坐標(biāo)系上畫(huà)出可行域〔2〕做目標(biāo)函數(shù)的等值線0可行域凸多邊形頂點(diǎn).精選課件解：〔1〕在直角坐標(biāo)系上畫(huà)出可行域〔2〕做目標(biāo)函數(shù)的等值線0無(wú)窮多..精選課件解：〔1〕在直角坐標(biāo)系上畫(huà)出可行域〔2〕做目標(biāo)函數(shù)的等值線0目標(biāo)函數(shù)無(wú)上界，該問(wèn)題無(wú)界無(wú)最優(yōu)解精選課件解：〔1〕在直角坐標(biāo)系上畫(huà)出可行域0可行域?yàn)榭占療o(wú)可行解該問(wèn)題無(wú)最優(yōu)解精選課件圖解法的根本步驟：〔一般是一個(gè)凸多邊形〕注意：假設(shè)是求目標(biāo)函數(shù)的最小值，目標(biāo)函數(shù)直線向下移動(dòng)精選課件關(guān)于線性規(guī)劃解的結(jié)論：1、假設(shè)〔LP〕問(wèn)題有可行解，那么可行域是一個(gè)凸多邊形〔或凸多面體〕。它可能是有界的；也可能是無(wú)界的。2、假設(shè)〔LP〕問(wèn)題有最優(yōu)解，那么最優(yōu)解可能是唯一的；也可能是無(wú)窮多個(gè)。如果是唯一的，這個(gè)解一定在該凸多邊形的某個(gè)頂點(diǎn)上；如果是無(wú)窮多個(gè)，那么這些最優(yōu)解一定充滿(mǎn)凸多邊形的一條邊界〔包括此邊界的兩個(gè)頂點(diǎn)〕總之，假設(shè)〔LP〕問(wèn)題有最優(yōu)解，那么最優(yōu)解一定可以在凸多邊形的某個(gè)頂點(diǎn)到達(dá)3、假設(shè)〔LP〕問(wèn)題有可行解，但沒(méi)有有限最優(yōu)解，此時(shí)凸多邊形是無(wú)界的〔反之不成立〕4、假設(shè)〔LP〕問(wèn)題沒(méi)有可行解，那么該問(wèn)題沒(méi)有最優(yōu)解精選課件三、基與根本可行解不妨設(shè)AX=b有解，且m≤n利用線性代數(shù)的方法求出無(wú)窮多解？×只討論r<n,

此時(shí)精選課件且r(A)=r=m(假設(shè)r<m,必有多余方程，可去掉〕由線性代數(shù)結(jié)論知:假設(shè)r(A)=m，那么A中至少存在一個(gè)m階子式|B|≠0即A中存在滿(mǎn)秩的m階矩陣B,稱(chēng)B為〔LP〕問(wèn)題的一個(gè)基不妨設(shè)m≤n精選課件定義1.3在〔LP〕問(wèn)題中，A的任意一個(gè)m×m階的非奇異子方陣B〔即|B|≠0〕稱(chēng)為〔LP〕問(wèn)題的一個(gè)基一個(gè)線性規(guī)劃問(wèn)題最多有基設(shè)r(Amxn)=r=m精選課件基基不是基精選課件設(shè)r(A)=m<n不妨設(shè)A的前m列構(gòu)成A的一個(gè)基基變量非基變量精選課件基,基非基,精選課件由于B可逆根本解定義1.4設(shè)B是〔LP〕問(wèn)題的一個(gè)基，,A=〔B,N〕,稱(chēng)此解為對(duì)應(yīng)于基B的根本解自由未知量精選課件基,非基,精選課件定義1.5根本可行解的個(gè)數(shù)根本可行解對(duì)應(yīng)的基稱(chēng)為可行基精選課件基,非基,根本可行解可行基精選課件A的任意一個(gè)m×m階的非奇異子方陣B設(shè)r(A)=r=m基:根本解:根本可行解:精選課件可行解根本解根本可行解有限精選課件設(shè)X為根本可行解，那么X的n個(gè)分量中，最多有個(gè)分量>0根本可行解退化根本可行解：根本可行解中，存在取0值的基變量非退化根本可行解：根本可行解中，基變量的取值均>0對(duì)應(yīng)的基稱(chēng)為退化基對(duì)應(yīng)的基稱(chēng)為非退化基線性規(guī)劃問(wèn)題：存在退化基：所有基均非退化m精選課件1.運(yùn)輸問(wèn)題建模: