第3講線性規(guī)劃

第三講線性規(guī)劃模型哈爾濱金融學(xué)院《數(shù)學(xué)建?！坊A(chǔ)教研部：夏冰數(shù)學(xué)規(guī)劃模型

x~決策變量f(x)~目標(biāo)函數(shù)gi(x)0~約束條件分類：線性規(guī)劃模型整數(shù)規(guī)劃與0－1規(guī)劃模型非線性規(guī)劃模型

重點(diǎn)：模型的建立和結(jié)果的分析哈爾濱金融學(xué)院《數(shù)學(xué)建模》某企業(yè)在計(jì)劃期內(nèi)計(jì)劃生產(chǎn)甲、乙、丙三種產(chǎn)品。這些產(chǎn)品分別需要在設(shè)備A、B上加工，需要消耗材料C、D，按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工及所需要的資源如表1所示。已知在計(jì)劃期內(nèi)設(shè)備的加工能力各為200臺時(shí)，可供材料分別為360、300公斤；每生產(chǎn)一件甲、乙、丙三種產(chǎn)品，企業(yè)可獲得利潤分別為40、30、50元，假定市場需求無限制。企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)在計(jì)劃期內(nèi)總的利潤收入最大？哈爾濱金融學(xué)院《數(shù)學(xué)建模》例1最優(yōu)生產(chǎn)計(jì)劃問題產(chǎn)品資源甲乙丙現(xiàn)有資源設(shè)備A312200設(shè)備B224200材料C451360材料D235300利潤(元/件)

403050表1產(chǎn)品資源消耗哈爾濱金融學(xué)院《數(shù)學(xué)建?！饭枮I金融學(xué)院《數(shù)學(xué)建模》限制條件：1、設(shè)備的加工能力各為200臺；2、可供材料分別為360、300公斤。問題分析：目標(biāo)：總的利潤收入最大。其中每生產(chǎn)一件甲、乙、丙三種產(chǎn)品，企業(yè)可獲得利潤分別為40、30、50元。符號說明：設(shè)x1、x2、x3

分別為甲、乙、丙三種產(chǎn)品的產(chǎn)量；Z為總的利潤收入。產(chǎn)品

資源甲

乙丙現(xiàn)有資源設(shè)備A312200設(shè)備B224200材料C451360材料D235300利潤(元/件)403050哈爾濱金融學(xué)院《數(shù)學(xué)建?！方⒛Ｐ停?、總的利潤收入2、加工能力限制為200臺3、可供材料分別為360、300公斤應(yīng)用Lingo軟件求得：X=(50,30,10)時(shí),maxZ=3400哈爾濱金融學(xué)院《數(shù)學(xué)建?！肪C上所述，建立線性規(guī)劃模型：模型求解：例2食用油加工計(jì)劃

加工一種食用油需要精煉若干種原油并把它們混合起來。原油來源有兩類共5種：植物油(VEG1，VEG2)、非植物油（OIL1，OIL2，OIL3），購買每種原油的價(jià)格（鎊/噸）見表1：

VEG1VEG2OIL1OIL2OIL3110120130110115表1：

最終產(chǎn)品以150鎊/噸價(jià)格出售。植物油和非植物油需要在不同的生產(chǎn)線上進(jìn)行精煉。每月能夠精煉的植物油不超過200噸，非植物油不超過250噸；在精煉過程中，重量沒有損失，精煉費(fèi)用可忽略不計(jì)。哈爾濱金融學(xué)院《數(shù)學(xué)建模》最終產(chǎn)品要符合硬度的技術(shù)條件。按照硬度計(jì)量單位，它必須在3—6之間。假定硬度的混合是線性的，而原油的硬度見表2：表2VEG1VEG2OIL1OIL2OIL38.86.12.04.25.0問：為使利潤最大，應(yīng)該怎樣制定它的月采購和加工計(jì)劃？哈爾濱金融學(xué)院《數(shù)學(xué)建?！?．確定決策變量設(shè)x1，…，x5分別代表需要采購的5種原油的噸數(shù)，y代表需要加工的成品油的噸數(shù)。2．確定約束條件關(guān)于植物油：x1+x2

200關(guān)于非植物油：x3+x4+x5

250硬度上限：8.8x1+6.1x2+2x3+4.2x4+5x5

6y硬度下限：8.8x1+6.1x2+2x3+4.2x4+5x5

3y連續(xù)性（均衡性）：x1+x2+x3+x4+x5=y非負(fù)性：xi

0（i=1,…,5），y03．確定目標(biāo)函數(shù)目標(biāo)是使利潤最大，即出售產(chǎn)品的收入扣除原油成本之后所得最大：150y110x1

120x2

130x3

110x4

115x5

最大。哈爾濱金融學(xué)院《數(shù)學(xué)建模》建立線性規(guī)劃模型：

哈爾濱金融學(xué)院《數(shù)學(xué)建?！酚谑窃虏少徟c生產(chǎn)計(jì)劃為：原油VEG1VEG2OIL1OIL2OIL3采購量159.259340.740702500生產(chǎn)量：450總利潤：1.7593104某商場決定：營業(yè)員每周連續(xù)工作5天后連續(xù)休息2天，輪流休息。根據(jù)統(tǒng)計(jì)，商場每天需要的營業(yè)員如下表所示。問：商場人力資源部應(yīng)如何安排每天的上班人數(shù)，使商場總的營業(yè)員最少？星期需要人數(shù)星期需要人數(shù)一300五480二300六600三350日550四400哈爾濱金融學(xué)院《數(shù)學(xué)建?！肪毩?xí)1雇用營業(yè)員解：設(shè)Xj(j=1，2，…，7)為休息2天后星期一到星期日開始上班的營業(yè)員，則這個(gè)問題的線性規(guī)劃模型為哈爾濱金融學(xué)院《數(shù)學(xué)建?！钒才派a(chǎn)計(jì)劃,滿足每周的需求,使4周總費(fèi)用最小。存貯費(fèi):每周每千箱飲料0.2千元。例3飲料廠的生產(chǎn)與檢修計(jì)劃在4周內(nèi)安排一次設(shè)備檢修，占用當(dāng)周15千箱生產(chǎn)能力，能使檢修后每周增產(chǎn)5千箱，檢修應(yīng)排在哪一周?

周次需求量(千箱)生產(chǎn)能力(千箱)成本(千元/千箱)115305.0225405.1335455.4425205.5合計(jì)100135

某種飲料4周的需求量、生產(chǎn)能力和成本哈爾濱金融學(xué)院《數(shù)學(xué)建?！穯栴}分析除第4周外每周的生產(chǎn)能力超過每周的需求；生產(chǎn)成本逐周上升；前幾周應(yīng)多生產(chǎn)一些。周次需求能力11530225403354542520合計(jì)100135成本5.05.15.45.5

哈爾濱金融學(xué)院《數(shù)學(xué)建?！凤嬃蠌S在第1周開始時(shí)沒有庫存；從費(fèi)用最小考慮,第4周末不能有庫存；周末有庫存時(shí)需支出一周的存貯費(fèi)，存貯費(fèi):0.2(千元/周?千箱)

；每周末的庫存量等于下周初的庫存量。模型假設(shè)

哈爾濱金融學(xué)院《數(shù)學(xué)建?！穢1~x4：第1~4周的生產(chǎn)量y1~y3：第1~3周末庫存量符號說明

目標(biāo)函數(shù)約束條件產(chǎn)量、庫存與需求平衡

能力限制非負(fù)限制

建立模型哈爾濱金融學(xué)院《數(shù)學(xué)建?！纺Ｐ颓蠼?/p>

4周生產(chǎn)計(jì)劃的總費(fèi)用為528(千元)最優(yōu)解：

x1~x4：15，40，25，20；

y1~y3：

0，15，5.周次需求能力11530225403354542520成本5.05.15.45.5產(chǎn)量15402520庫存01550哈爾濱金融學(xué)院《數(shù)學(xué)建?！匪伎迹涸?周內(nèi)安排一次設(shè)備檢修，占用當(dāng)周15千箱生產(chǎn)能力，能使檢修后每周增產(chǎn)5千箱，檢修應(yīng)排在哪一周?

哈爾濱金融學(xué)院《數(shù)學(xué)建?！纺称囆枰眉住⒁?、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是1.5，1，0.7(m)，這些軸需要用同一種圓鋼來做，圓鋼長度為4m?，F(xiàn)在要制造1000輛汽車，最少要用多少圓鋼來生產(chǎn)這些軸？哈爾濱金融學(xué)院《數(shù)學(xué)建?！肪毩?xí)2合理用料問題

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

01023012451000余料(m)00.30.50.10.400.30.60.20.5解：這是一個(gè)條材下料問題，設(shè)切口寬度為零。設(shè)一根圓鋼切割成甲、乙、丙三種軸的根數(shù)分別為y1，y2，y3,則切割方式可用不等式1.5y1+y2+0.7y3≤4表示，求這個(gè)不等式關(guān)于y1，y2，y3的非負(fù)整數(shù)解。象這樣的非負(fù)整數(shù)解共有10組，也就是有10種下料方式，如表所示。哈爾濱金融學(xué)院《數(shù)學(xué)建?！吩O(shè)xj(j=1,2…,10)為第j種下料方案所用圓鋼的根數(shù)，則用料最少數(shù)學(xué)模型為:哈爾濱金融學(xué)院《數(shù)學(xué)建?！啡绻a(chǎn)某一類型汽車，則至少要生產(chǎn)80輛，那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？課后練習(xí)：汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼材、勞動時(shí)間的需求，利潤及工廠每月的現(xiàn)有量。小型中型大型現(xiàn)有量鋼材（噸）1.5

3

5600勞動時(shí)間（小時(shí)）280