線(xiàn)性規(guī)劃模型

《線(xiàn)性規(guī)劃模型》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、第一章線(xiàn)性規(guī)劃模型一、線(xiàn)性規(guī)劃模型的建立例1某工廠A有生產(chǎn)卬，乙二種產(chǎn)品的能力，H.生產(chǎn)i噸甲產(chǎn)品需要3個(gè)工口和0.35噸小麥。生產(chǎn)一噸乙產(chǎn)品需要4個(gè)工日和0.25噸小麥。該廠僅有工人12人，一個(gè)月只能Hl300個(gè)工日，小麥一個(gè)月只能進(jìn)21噸，并且還知生產(chǎn)一噸甲產(chǎn)品可盈利80（白元），生產(chǎn)一噸乙產(chǎn)品可盈利90（百元）。那么，工廠A在一月中應(yīng)如何安排這兩種產(chǎn)品的生產(chǎn)，使之獲得瑕大的利潤(rùn)？由以上條件可列表如下：資源甲乙總和工日34300小麥0.350.2521盈利8090問(wèn)題一的數(shù)學(xué)模型：設(shè)旺分別表示一月中生產(chǎn)

2、甲，乙二種產(chǎn)品的數(shù)量，稱(chēng)之為決策變量。所得利潤(rùn)為Z,問(wèn)題一的bl標(biāo)是使得總利潤(rùn)函數(shù)z=80%,+90兀2有最大值。工日的約束為：3%,+4x2<300原料小麥的約束為：0.35坷+0.25兀2<21顯然1=1標(biāo)函數(shù)和約朿條件都(1.1)T是問(wèn)題_可歸結(jié)為求目標(biāo)函數(shù)在約束條件下的最大值問(wèn)題,是決策變量的線(xiàn)性函數(shù)，即可建立以下線(xiàn)性規(guī)劃模型maxz=80%!+90x2s.t.3%!+4x2<3000?35兀［+0.25*2S21x{,x2>01.1線(xiàn)性規(guī)劃模型的一般形式max^inin)z=工cixiZ=1s.t

3、.^aijxj-(-?=X-i=1,2…(m個(gè)約束)(1.2)j=iXj>0j=1,2???,”矩陣形式max^inin)z=c1Xs.t.AX<(>=)&(1.3)X>0其中X=(兀1，兀2,…XJ為決策向量，c=(c,,c2,---cn)z為目標(biāo)函數(shù)的系數(shù)向量,b=(bi，b?,???bj為常數(shù)向量,4=(勺)為系數(shù)矩陣。V丿恥“1.2線(xiàn)性規(guī)劃模型的標(biāo)準(zhǔn)形minz=cTXs.t.AX=bX>0對(duì)于例1町?。?(80,90),A=‘34、,b=#300、o,0.350.25丿,21丿(1.4)1.3如何

4、化一般形為標(biāo)準(zhǔn)形1.3.1目標(biāo)函數(shù)的轉(zhuǎn)化例2—個(gè)工廠的卬，乙，丙三個(gè)車(chē)間牛產(chǎn)同一種產(chǎn)品，每件產(chǎn)品由4個(gè)零件A和3個(gè)零件B組成。這兩種零件耗用兩種不同的原材料，而這兩種原材料的現(xiàn)有數(shù)額分別是300公斤和500公斤。每個(gè)牛產(chǎn)班的原材料的耗用量和零件產(chǎn)量如下表。問(wèn)這三個(gè)車(chē)間應(yīng)各開(kāi)多少班數(shù)，才能使這種產(chǎn)需的配套數(shù)達(dá)到最人？乍間每班用料數(shù)每班產(chǎn)量（個(gè)）原料1原料2零件A零件B叩8675乙5969丙38848%!+5兀2+3兀勺<300「(1.5)6兀1+9兀2+8x3<500甲，乙，丙生產(chǎn)A零件總數(shù)是：7兀］+6x2

5、+8x3，生產(chǎn)B零件總數(shù)是:5xj+9x2+4x3。解：設(shè)州，兀2，心是甲，乙，丙三個(gè)車(chē)間所開(kāi)的生產(chǎn)班數(shù)，由原材料的限制條件，得因?yàn)槟繕?biāo)函數(shù)是要使產(chǎn)品的配套數(shù)最大，而每個(gè)零件要4個(gè)A零件，3個(gè)B零件，所以產(chǎn)吊的最人量不超過(guò)沁嚴(yán)和5屮響4春較小的一個(gè)卡是產(chǎn)品的配套數(shù),即S=min+6x2+8x35兀］+9x2+4x34這個(gè)日標(biāo)函數(shù)不是線(xiàn)性函數(shù)，但rij以通過(guò)適當(dāng)?shù)淖儞Q把它化為線(xiàn)性的，設(shè).7兀

6、+6x9+8小5兀

7、+9x9+4x.y=min1(1.6)則上式可以等價(jià)于卜?而兩個(gè)不等式7X(+6x2+8兀3〉5兀

8、］+9兀2+4兀3>(1?7)故可得如下線(xiàn)性規(guī)劃模型:maxS=ys.t.7兀］+6x2+8兀3—4yA05x,+9兀2+4兀3-3y>0(1.8)8%!+5x2+3x3<3005%j+9x2+8x3<500xpx2,x3,y>0目標(biāo)函數(shù)為求最大值，令5=-y即可將原問(wèn)題轉(zhuǎn)化為在相同約束條件卜?求最小值。1.3.2約束條件的轉(zhuǎn)化d內(nèi)+勺兀2-baxxx+a2x2>-b若約束條件中有n和w號(hào)，則口J在w（>）號(hào)的左端加上（或減去）一個(gè)非負(fù)變量（稱(chēng)為松弛變量）使其變成二號(hào)約朿。如4X（+5x2>6變?yōu)?旺+5兀

9、2-尤3=6。若約朿條件帶有絕對(duì)值號(hào)，如⑷坷+02X25：,則可等價(jià)轉(zhuǎn)化為:若決策變量沒(méi)有非負(fù)限制，稱(chēng)為自由變量。例如x,e（-oo,+oo）為口由變量，則可引入>0,y2>0,令Xj=yt-y2代入模型即可。二、線(xiàn)性規(guī)劃的求解方法2.1線(xiàn)性規(guī)劃解的概念定義1?1滿(mǎn)足約束條件的解x=（x,,x2,---,xjr,稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題的可行解，而使目標(biāo)隊(duì)I數(shù)達(dá)到最小值的可行解叫最優(yōu)解。所有可行解構(gòu)成的集合稱(chēng)為可行域，記為/?。2.2線(xiàn)性規(guī)劃解的基本理論定理1?1如果線(xiàn)性規(guī)劃問(wèn)題存在對(duì)行域，則其對(duì)行域是凸集。定理1

10、?2如果線(xiàn)性規(guī)劃問(wèn)題的可行域有界，則問(wèn)題的最優(yōu)解一定在可行域的頂點(diǎn)上達(dá)到。2.3單純形法單純形法是求解線(xiàn)性規(guī)劃問(wèn)題的最常用、最有效的算法z—。單純形法是首先由GeorgeDantzig于1947年提出的，近60年來(lái)，雖有許多變形體已被開(kāi)發(fā)，但卻保持著同樣的基本觀念。由定理2可知，如果線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解存在，則一定可以在其可行區(qū)域的頂點(diǎn)中找到?；诖耍瑔渭冃畏ǖ幕舅悸肥牵合日页隹尚杏虻囊粋€(gè)極點(diǎn),據(jù)一定規(guī)則判斷其