運(yùn)籌學(xué)線性規(guī)劃完整版

運(yùn)籌學(xué)OperationsResearch

線性規(guī)劃LinearProgramming1.1LP的數(shù)學(xué)模型

MathematicalModelofLP1.2圖解法

GraphicalMethod1.3標(biāo)準(zhǔn)型

StandardformofLP1.4基本概念

BasicConcepts1.5單純形法

SimplexMethod1.1數(shù)學(xué)模型

MathematicalModel14十月20231.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP線性規(guī)劃（LinearProgramming,縮寫(xiě)為L(zhǎng)P）通常研究資源的最優(yōu)利用、設(shè)備最佳運(yùn)行等問(wèn)題。例如，當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)；企業(yè)在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多、利潤(rùn)最大）。14十月2023【例1-1】生產(chǎn)計(jì)劃問(wèn)題。某企業(yè)在計(jì)劃期內(nèi)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。按工藝資料規(guī)定，每件產(chǎn)品甲需要消耗材料A2公斤，消耗材料B1公斤，每件產(chǎn)品乙需要消耗材料A1公斤，消耗材料B1.5公斤。已知在計(jì)劃期內(nèi)可供材料分別為40、30公斤；每生產(chǎn)一件甲、乙兩產(chǎn)品，企業(yè)可獲得利潤(rùn)分別為40、30元，如表1－1所示。假定市場(chǎng)需求無(wú)限制。企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)在計(jì)劃期內(nèi)總的利潤(rùn)收入最大。1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP1.1.1應(yīng)用模型舉例14十月2023【解】設(shè)x1、x2分別為甲、乙產(chǎn)品的產(chǎn)量，數(shù)學(xué)模型為：1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP

產(chǎn)品

資源

甲

乙現(xiàn)有資源材料C2140材料D11.530利潤(rùn)（元/件）300400表1-114十月2023線性規(guī)劃的數(shù)學(xué)模型由決策變量

Decisionvariables

目標(biāo)函數(shù)Objectivefunction及約束條件Constraints構(gòu)成。稱為三個(gè)要素。其特征是：1．解決問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是求最大值或最小值；2．解決問(wèn)題的約束條件是一組多個(gè)決策變量的線性不等式或等式。怎樣辨別一個(gè)模型是線性規(guī)劃模型？1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP14十月2023【例1-2】某商場(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è)員最少。星期需要人數(shù)星期需要人數(shù)一300五480二300六600三350日550四4001.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP14十月2023【解】設(shè)xj(j=1，2，…，7)為休息2天后星期一到星期日開(kāi)始上班的營(yíng)業(yè)員，則這個(gè)問(wèn)題的線性規(guī)劃模型為1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP星期需要人數(shù)星期需要人數(shù)一300五480二300六600三350日550四40014十月20231X10C1404>=3001042X267C2301>=30013X3146C3350>=35004X4170C4400>=40005X597C5480>=48006X6120C6600>=60007X717C7550>=5500最優(yōu)解：Z＝617（人）1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP14十月2023【例1-3】合理用料問(wèn)題。某汽車需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是1.5，1，0.7（m），這些軸需要用同一種圓鋼來(lái)做，圓鋼長(zhǎng)度為4m?，F(xiàn)在要制造1000輛汽車，最少要用多少圓鋼來(lái)生產(chǎn)這些軸？【解】這是一個(gè)條材下料問(wèn)題，設(shè)切口寬度為零。設(shè)一根圓鋼切割成甲、乙、丙三種軸的根數(shù)分別為y1，y2，y3,則切割方式可用不等式1.5y1+y2+0.7y3≤4表示，求這個(gè)不等式關(guān)于y1，y2，y3的非負(fù)整數(shù)解。象這樣的非負(fù)整數(shù)解共有10組，也就是有10種下料方式，如表1-3所示。表1-3下料方案

方案規(guī)格12345678910需求量y1(根)

22111000001000y210210432101000y3

01023012451000余料（m）00.30.50.1o.400.30.60.20.51.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP14十月2023設(shè)xj(j=1,2…,10)為第j種下料方案所用圓鋼的根數(shù)。則用料最少數(shù)學(xué)模型為:求下料方案時(shí)應(yīng)注意，余料不能超過(guò)最短毛坯的長(zhǎng)度；最好將毛坯長(zhǎng)度按降的次序排列，即先切割長(zhǎng)度最長(zhǎng)的毛坯，再切割次長(zhǎng)的，最后切割最短的，不能遺漏了方案。如果方案較多，用計(jì)算機(jī)編程排方案，去掉余料較長(zhǎng)的方案，進(jìn)行初選。1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP

方案規(guī)格12345678910需求量y1(根)22111000001000y210210432101000y3

01023012451000余料（m）00.30.50.1o.400.30.60.20.514十月20231X15002X203X304X405X506X662.57X708X809X925010X100Z＝812.51.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP14十月2023【例1-4】配料問(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礦石的金屬含量

合金礦石錫%鋅%鉛%鎳%雜質(zhì)費(fèi)用（元/t）1251010253034024000303026030155206018042020040202305851517551901.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP14十月2023解:設(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.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP礦石錫%鋅%鉛%鎳%雜質(zhì)費(fèi)用（元/t）12510102530340240003030260301552060180420200402023058515175519014十月20231X102X20.33333X304X40.58335X50.6667最優(yōu)解：Z=347.51.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP14十月20231.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP【例1-5】投資問(wèn)題。某投資公司擬將5000萬(wàn)元的資金用于國(guó)債、地方國(guó)債及基金三種類型證券投資，每類各有兩種。每種證券的評(píng)級(jí)、到期年限及每年稅后收益率見(jiàn)表1-5所示。表1－5證券投資方案序號(hào)證券類型評(píng)級(jí)到期年限每年稅后收益率(%)1國(guó)債1183.22國(guó)債21103.83地方債券1244.34地方債券2364.75基金1434.26基金2544.6

決策者希望：國(guó)債投資額不少于1000萬(wàn)，平均到期年限不超過(guò)5年，平均評(píng)級(jí)不超過(guò)2。問(wèn)每種證券各投資多少使總收益最大。14十月20231.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP解設(shè)xj(j=1,2,…，6)為第j種證券的投資額，目標(biāo)函數(shù)是稅后總收益為資金約束：國(guó)債投資額約束：平均評(píng)級(jí)約束：平均到期年限約束：14十月2023整理后得到線性規(guī)劃模型1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP14十月2023【例1-6】均衡配套生產(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，每天可供加工時(shí)間為8小時(shí)。為了保持兩種設(shè)備均衡負(fù)荷生產(chǎn)，要求一種設(shè)備每天的加工總時(shí)間不超過(guò)另一種設(shè)備總時(shí)間1小時(shí)。怎樣安排設(shè)備的加工時(shí)間使每天產(chǎn)品的產(chǎn)量最大?！窘狻吭O(shè)x1、x2為每天加工甲、乙兩種零件的件數(shù)，則產(chǎn)品的產(chǎn)量是設(shè)備A、B每天加工工時(shí)的約束為要求一種設(shè)備每臺(tái)每天的加工時(shí)間不超過(guò)另一種設(shè)備1小時(shí)的約束為1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP14十月2023目標(biāo)函數(shù)線性化。產(chǎn)品的產(chǎn)量y等價(jià)于整理得到線性規(guī)劃模型約束線性化。將絕對(duì)值約束寫(xiě)成兩個(gè)不等式1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP14十月20231.1.2線性規(guī)劃的一般模型一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型中，有m個(gè)約束，有n個(gè)決策變量xj,j=1,2…,n，目標(biāo)函數(shù)的變量系數(shù)用cj表示,cj稱為價(jià)值系數(shù)。約束條件的變量系數(shù)用aij表示，aij稱為工藝系數(shù)。約束條件右端的常數(shù)用bi表示，bi稱為資源限量。則線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式可寫(xiě)成為了書(shū)寫(xiě)方便，上式也可寫(xiě)成：1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP14十月2023在實(shí)際中一般xj≥0,但有時(shí)xj≤0或xj無(wú)符號(hào)限制。1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP14十月20231.什么是線性規(guī)劃，掌握線性規(guī)劃在管理中的幾個(gè)應(yīng)用例子2.線性規(guī)劃數(shù)學(xué)模型的組成及其特征3.線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式。1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP1.2圖解法

GraphicalMethod14十月2023圖解法的步驟：1.求可行解集合。分別求出滿足每個(gè)約束包括變量非負(fù)要求的區(qū)域，其交集就是可行解集合，或稱為可行域；2.繪制目標(biāo)函數(shù)圖形。先過(guò)原點(diǎn)作一條矢量指向點(diǎn)（c1,c2)，矢量的方向就是目標(biāo)函數(shù)增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標(biāo)函數(shù)圖形；3.求最優(yōu)解。依據(jù)目標(biāo)函數(shù)求最大或最小移動(dòng)目標(biāo)函數(shù)直線，直線與可行域相交的點(diǎn)對(duì)應(yīng)的坐標(biāo)就是最優(yōu)解。一般地，將目標(biāo)函數(shù)直線放在可行域中求最大值時(shí)直線沿著矢量方向移動(dòng)求最小值時(shí)沿著矢量的反方向移動(dòng)1.2圖解法TheGraphicalMethod14十月2023x1x2O1020304010203040(300,400)(15,10)最優(yōu)解X=(15,10)最優(yōu)值Z=8500例1-71.2圖解法TheGraphicalMethod14十月2023246x1x2246最優(yōu)解X=(3,1)最優(yōu)值Z=5(3,1)minZ=x1+2x2例1-8(1,2)1.2圖解法TheGraphicalMethod14十月2023246x1x2246X（2）＝（3,1）X（1）＝（1,3）(