第二章線性規(guī)劃模型

1、第一章 線性規(guī)劃模型 在生產(chǎn)管理和經(jīng)營(yíng)活動(dòng)中經(jīng)常需要解決：如何合理地利用有限的資源，以得到最大的效益。 例1 某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源?，F(xiàn)將有關(guān)數(shù)據(jù)列表如下： 試擬訂使總收入最大的生產(chǎn)方案。資源單耗 產(chǎn)品資源甲 乙資源限量煤電油9 44 5 3 10360200300單位產(chǎn)品價(jià)格 7 12線性規(guī)劃模型的三要素3.約束條件：為實(shí)現(xiàn)優(yōu)化目標(biāo)需受到的限制，用 決策變量的等式或不 等式表示；1.決策變量：需決策的量，即待求的未知數(shù)；2.目標(biāo)函數(shù)：需優(yōu)化的量，即欲達(dá)的目標(biāo)，用決 策變量的表達(dá)式表示；目標(biāo)函數(shù)：總收入，記為z, ,則z=7x1+12x2，為體現(xiàn)對(duì)其 追求極大化，

2、在z 的前面冠以極大號(hào)Max；決策變量：甲、乙產(chǎn)品的計(jì)劃產(chǎn)量，記為 ；在本例中約束條件：分別來(lái)自資源煤、電、油限量的約束，和產(chǎn) 量非負(fù)的約束，表示為0,3001032005436049. .21212121xxxxxxxxts,xx解：設(shè)安排甲、乙產(chǎn)量分別 為 ,總收入為 ， 則模型為：21,xxz21127maxxxz0,3001032005436049. .21212121xxxxxxxxts線性規(guī)劃模型的一個(gè)基本特點(diǎn)： 目標(biāo)和約束均為變量的線性表達(dá)式如果模型中出現(xiàn)如的非線性表達(dá)式，則屬于非線性規(guī)劃。32211ln2xxx例2 某市今年要興建大量住宅,已知有三種住宅體系可以大量興建，各體系

3、資源用量及今年供應(yīng)量見(jiàn)下表：要求在充分利用各種資源條件下使建造住宅的總面積為最大(即求安排各住宅多少m2)，求建造方案。水泥(公斤/m2)4000(千工日)147000(千塊)150000(噸)20000(噸)110000(千元)資源限量3.518025120大模住宅3.019030135壁板住宅4.521011012105磚混住宅人工(工日/m2)磚(塊/m2)鋼材(公斤/m2)造價(jià)(元/m2) 資源住宅體系 解: 設(shè)今年計(jì)劃修建磚混、壁板、大模住宅各為 x1,x2,x3 m2, z為總面積,則本問(wèn)題的數(shù)學(xué)模型為:0,40000035. 0003. 00045. 0147000210. 01

4、50000180. 0190. 0110. 020000025. 0030. 0012. 0110000120. 0135. 0105. 0.3213211321321321xxxxxxxxxxxxxxxxts321xxxMaxz 前蘇聯(lián)的尼古拉也夫斯克城住宅興建計(jì)劃采用了上述模型，共用了12個(gè)變量，10個(gè)約束條件。練習(xí)：某畜牧廠每日要為牲畜購(gòu)買(mǎi)飼料以使其獲取A、B、C、D四種養(yǎng)分。市場(chǎng)上可選擇的飼料有M、N兩種。有關(guān)數(shù)據(jù)如下：試決定買(mǎi)M與N二種飼料各多少公斤而使支出的總費(fèi)用為最少？410售價(jià) 0.4 0.6 2.0 1.7牲畜每日每頭需要量 0 0.1 0.2 0.1N 0.1 0 0.1

5、0.2 M每公斤含營(yíng)養(yǎng)成分 A B C D飼料解：設(shè)購(gòu)買(mǎi)M、N飼料各為 ，則 21410 xxMinz0,7 . 11 . 02 . 00 . 22 . 01 . 06 . 01 . 004 . 001 . 0. .2121212121xxxxxxxxxxts21,xx例例3：現(xiàn)有一批某種型號(hào)的圓鋼長(zhǎng)：現(xiàn)有一批某種型號(hào)的圓鋼長(zhǎng)8米，需要截取米，需要截取2.5米長(zhǎng)的毛坯米長(zhǎng)的毛坯100根，長(zhǎng)根，長(zhǎng)1.3米的毛坯米的毛坯200根。問(wèn)如何才根。問(wèn)如何才能既滿足需要，又能使總的用料最少？能既滿足需要，又能使總的用料最少？解：為了找到一個(gè)省料的套裁方案，必須先設(shè)計(jì)出較好的幾解：為了找到一個(gè)省料的套裁方案

6、，必須先設(shè)計(jì)出較好的幾個(gè)下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格個(gè)下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格的圓鋼，以滿足對(duì)各種不同規(guī)格圓鋼的需要并達(dá)到省料的目的圓鋼，以滿足對(duì)各種不同規(guī)格圓鋼的需要并達(dá)到省料的目的，為此可以設(shè)計(jì)出的，為此可以設(shè)計(jì)出4種下料方案以供套裁用。種下料方案以供套裁用。2.5m32101.3m0246料頭0.50.40.30.2 )4.3.2.1(020064210023min4323214321jxxxxxxxxxxxZj設(shè)按方案設(shè)按方案、下料的原材料根數(shù)分別為下料的原材料根數(shù)分別為xj (j=1，2,3,4)，可列出下面的數(shù)學(xué)模型：，可列出下面的數(shù)

7、學(xué)模型：線性規(guī)劃模型的一般形式：決策變量：目標(biāo)函數(shù)：約束條件：11 11121 1221 11( , )( , ). .( , ),0nnnnmmnnmna xa xba xa xbsta xaxbxx nxxx,.,21,nnxcxcxczor.min)max(2211則模型可表示為模型一般式的矩陣形式記TmnmijnTnbbbaAccCxxX),(,)(),(,),(111(min)( , ). .0max orzCXAXbstX 回顧例1的模型其中 表示決策變量的向量； 表示產(chǎn)品的價(jià)格向量； 表示資源限制向量； 表示產(chǎn)品對(duì)資源的單耗系數(shù)矩陣。TxxX),(21)12, 7(CTb)300,200,360(10