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

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