第13章線性規(guī)劃線性規(guī)劃問(wèn)題的數(shù)學(xué)模型13.1線性規(guī)劃問(wèn)題的圖解法13.213.1線性規(guī)劃問(wèn)題的數(shù)學(xué)模型13.1.1線性規(guī)劃問(wèn)題舉例

例1某工廠制造兩種產(chǎn)品P1、P2,需要三種原料M1,M2,M3。制造每種產(chǎn)品1公斤需要的各種原料,獲得的利潤(rùn)和該廠每天供應(yīng)原料的數(shù)量如表13-1。問(wèn)如何安排P1,P2

的產(chǎn)量,才能使該廠每天所獲利潤(rùn)最大?

解:為用數(shù)學(xué)語(yǔ)言來(lái)描述這個(gè)問(wèn)題,我們假設(shè)該廠日產(chǎn)P1為x1公斤,日產(chǎn)P2

為x2

公斤。由于制造產(chǎn)品P1、P2

時(shí),每天用的原

料M1

的量不能超過(guò)360(kg),所以上述關(guān)系

用不等式表示成:9x1+4x2≤360

對(duì)于每天用的原料M2

和M3

的量同樣可分別建立下述不等式:4x1+5x2≤2003x1+10x2≤300

而日產(chǎn)P1、P2的產(chǎn)量不能為負(fù)值,所以又有x1≥0,x2≥0

目標(biāo)是使每日所獲利潤(rùn)Z=70x1+120x2為最大。

例2某機(jī)械加工廠下屬甲乙兩個(gè)分廠都生產(chǎn)A、B、C三種規(guī)格的零件,已知如表13-2列出的生產(chǎn)速率:

試求每個(gè)分廠應(yīng)開(kāi)工生產(chǎn)幾個(gè)小時(shí),才能滿足供應(yīng)需求而又使成本最小?

這也是一個(gè)生產(chǎn)計(jì)劃問(wèn)題。

設(shè)生產(chǎn)分廠甲和乙分別開(kāi)工生產(chǎn)x1、x2

小時(shí),則x1

≥0,x2

≥0,由三種產(chǎn)品的需求量,可知5x1+3x2≥953x1+5x2≥705x1+4x2≥100

目標(biāo)是使成本Z=200x1+150x2

最小。

例3(熱狗和熱狗面包問(wèn)題)Heatdog是一家食品加工廠,制作熱狗和熱狗面包。他們每星期最多使用200磅自己的面粉制作熱狗面包。

每個(gè)熱狗面包需要0.1磅面粉。最近他們與Pigforland公司簽訂協(xié),Pigforland每星期一向公司供應(yīng)800磅肉制品。每個(gè)熱狗需要0.25磅的肉制品,其他所有的制作熱狗和熱狗面包的配料供應(yīng)充足。 Heatdog有5名全職雇員(每星期工作40小時(shí))。制作每一個(gè)熱狗需要3分鐘,一個(gè)熱狗面包需要2分鐘時(shí)間。一個(gè)熱狗產(chǎn)生0.2美元的利潤(rùn),一個(gè)面包產(chǎn)生0.1美元的利潤(rùn)。

表13-3列出了每份熱狗及熱狗面包的材料、工時(shí)及利潤(rùn)清單。 Heatdog想知道每個(gè)星期制作多少熱狗和熱狗面包才能獲得最大利潤(rùn)。

解設(shè)Heatdog每個(gè)星期所生產(chǎn)的熱狗和熱狗面包份數(shù)分別為x1

和x2,且x1

和x2均為整數(shù)。

那么利潤(rùn)就是Z=0.2×x1+0.1×x2,公司希望利潤(rùn)Z越大越好。

由于每個(gè)星期最多供肉制品800磅,這是一個(gè)限制條件,所以x1和x2

應(yīng)該滿足:0.25×x1+0×x2≤800

同樣,由于面粉用量、工時(shí)量的限制,x1和x2

還應(yīng)該滿足:0×x1+0.1×x2≤2003×x1+2×x2≤12000

又因?yàn)槊總€(gè)星期所生產(chǎn)的熱狗和熱狗面包份數(shù)x1和x2

必須為非負(fù)數(shù),且為整數(shù),即x1

≥0,x2

≥0,且均為整數(shù)。

所以,這一問(wèn)題就是求一組變量x1,x2

的值,使目標(biāo)函數(shù)Z=0.2×x1+0.1×x2

的值最大,并滿足如下約束條件:13.1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型 1.線性規(guī)劃數(shù)學(xué)模型的一般形式 2.建立線性規(guī)劃問(wèn)題的數(shù)學(xué)模型的一般步驟

例4(截料問(wèn)題)設(shè)有鋼材150根,長(zhǎng)15米,需軋成配套鋼料。每套由7根2米長(zhǎng)與2根7米長(zhǎng)的鋼梁組成,問(wèn)如何下料使鋼材廢料最少(設(shè)不計(jì)下料損耗)?

解:依題意,每根鋼材的下料有三種可能情形: (1)截7米長(zhǎng)0根,2米的7根,余1米廢料。 (1)截7米長(zhǎng)1根,2米長(zhǎng)4根,無(wú)廢料。 (2)截7米長(zhǎng)2根,2米長(zhǎng)0根,余1米廢料。

設(shè)用第j

截法,用去鋼材xj根(j=1,2,3)。

則這批鋼材截成7米長(zhǎng)的鋼梁為x2+2x3根, 2米長(zhǎng)的7x1+4x2

根,廢料總長(zhǎng)Z=x1+x3

米，

我們希望廢料Z

越小越好。13.2線性規(guī)劃問(wèn)題的圖解法13.2.1圖解法的步驟

例1求解線性規(guī)劃maxz=0.7x1+0.9x2

約束于

解:1.先在平面直角坐標(biāo)系x1Ox2

里畫(huà)出上述線性規(guī)劃的可行域R。以x1

為橫坐標(biāo),x2

為縱坐標(biāo)做出直角坐標(biāo)系x1Ox2,在該坐標(biāo)系中分別做出直線:x1=8;x2=7;x1+x2=12

事實(shí)上在約束條件中,每個(gè)線性等式代表平面上一條直線,這直線將坐標(biāo)平面分成兩部分,于是每個(gè)線性不等式代表一個(gè)半平面。

本例中五個(gè)線性不等式代表的五個(gè)半平面的交,就是可行域R,它是一個(gè)凸多邊形,這個(gè)凸邊形有五個(gè)頂點(diǎn),它們分別是O(0,0),A(0,7),B(5,7),C(8,4),D(8,0),如圖13-1所示。圖13-1例5 2.求解線性規(guī)劃,就是要在上述凸多邊形R

中找一點(diǎn)(x1,x2),使目標(biāo)函數(shù)Z=0.7x1+0.9x2

取最大值。對(duì)任意固定的常數(shù)C,直線0.7x1+0.9x2=C

上的每點(diǎn)都有相同的目標(biāo)函數(shù)值C,故該直線也稱(chēng)為“等值線”。當(dāng)C

變化時(shí),得出一族相互平行的等值線,這些等值線中有一部分與可行域相交。

我們要在凸多邊形即可行域R中找這樣的點(diǎn),使它所在的等值線具有最大值C。

例2某木器廠生產(chǎn)圓桌和衣柜兩種產(chǎn)品,現(xiàn)有兩種木料,第一種有72m3,第二種有56m3,假設(shè)生產(chǎn)每種產(chǎn)品都需要用兩種木料,生產(chǎn)一張圓桌和一個(gè)衣柜分別所需木料如表13-5所示。

每生產(chǎn)一張圓桌可獲利60元,生產(chǎn)一個(gè)衣柜可獲利100元。木器廠在現(xiàn)有木料條件下,圓桌和衣柜各生產(chǎn)多少,才使獲得利潤(rùn)最多?

解:設(shè)生產(chǎn)圓桌x

張,生產(chǎn)衣柜y

個(gè),利潤(rùn)總額為z元,則由已知條件得到的線性規(guī)劃數(shù)學(xué)模型為:

于是知M

點(diǎn)坐標(biāo)為(350,100),從而得到使利潤(rùn)總額最大的生產(chǎn)計(jì)劃,即生產(chǎn)圓桌350張,生產(chǎn)衣柜100個(gè),能使利潤(rùn)總額達(dá)到最大值31000元。13.2.2線性規(guī)劃問(wèn)題解的幾種情況1.有唯一最優(yōu)解2.有無(wú)窮多組最優(yōu)解3.有可行解無(wú)最優(yōu)解

例3求解線性規(guī)劃maxZ=x1+x2

約束于

解:繪出可行解域如圖13-3所示,從圖中可以看到,可行解域是一個(gè)無(wú)界的多邊形。等值線離開(kāi)原點(diǎn)可以無(wú)限向上平移,也就是Z的值趨向于無(wú)窮大,所以在這種情況下,目標(biāo)函數(shù)無(wú)上界,顯然也沒(méi)有最優(yōu)解。圖13-3例7

在實(shí)際問(wèn)題中,這種情況的發(fā)生可能是在建立數(shù)學(xué)模型中舍棄了必要的約束條件而造成的。

本例中若改為求目標(biāo)函數(shù)最小值,則它仍有最優(yōu)解:4.無(wú)可行解