線性規(guī)劃與單純形法第6節(jié)

第6節(jié)

應(yīng)用舉例

一般講，一個(gè)經(jīng)濟(jì)、管理問(wèn)題凡滿足以下條件時(shí)，才能建立線性規(guī)劃的模型。(1)要求解問(wèn)題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)表示，且Z=f(x)為線性函數(shù)；(2)存在著多種方案；(3)要求達(dá)到的目標(biāo)是在一定約束條件下實(shí)現(xiàn)的；這些約束條件可用線性等式或不等式來(lái)描述。

合理利用線材問(wèn)題

現(xiàn)要做100套鋼架，每套需用長(zhǎng)為2.9m，2.1m和1.5m的元鋼各一根。已知原料長(zhǎng)7.4m，問(wèn)應(yīng)如何下料，使用的原材料最省。

解：所有合理的下料方式列舉如下8種方式使用的原料根數(shù)即為決策變量，按余料從小到大給各變量編號(hào)，問(wèn)題歸結(jié)為如下線性規(guī)劃若僅選取余料長(zhǎng)小于0.9m的套裁方案設(shè)按Ⅰ方案下料的原材料根數(shù)為x1,Ⅱ方案為x2，Ⅲ方案為x3，Ⅳ方案為x4,Ⅴ方案為x5。可列出以下數(shù)學(xué)模型：

最優(yōu)下料方案：按Ⅰ方案下料30根，Ⅱ方案下料10根，Ⅳ方案下料50根，需90根原材料可以制造100套鋼架。

其他最優(yōu)方案：Ⅱ方案下料40根，III方案下料30根，按IV方案下料20根，需90根原材料可以制造100套鋼架。

配料問(wèn)題

某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、D。已知產(chǎn)品的規(guī)格要求，產(chǎn)品單價(jià)，每天能供應(yīng)的原材料數(shù)量及原材料單價(jià)，分別見(jiàn)表格。該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大?解以AC表示產(chǎn)品A中C的成分，AP表示產(chǎn)品A中P的成分，依次類推，根據(jù)原材料比例限制將(1-40)逐個(gè)代入(1-39)并整理得到根據(jù)原材料供應(yīng)數(shù)量的限額9個(gè)變量分別用x1,…,x9表示，則約束條件可表示為：目標(biāo)函數(shù)為產(chǎn)品收入減去原材料成本

產(chǎn)品收入為：50A+35B+25D，即50(x1+x2+x3)——產(chǎn)品A35(x4+x5+x6)——產(chǎn)品B25(x7+x8+x9)——產(chǎn)品D

原材料成本為：65C+25P+35H，即65(x1+x4+x7)——原材料C25(x2+x5+x8)——原材料P35(x3+x6+x9)——原材料H

所以，目標(biāo)函數(shù)為

產(chǎn)品計(jì)劃問(wèn)題

某廠生產(chǎn)I，II，III三種產(chǎn)品，都分別經(jīng)A，B兩道工序加工。設(shè)A工序可分別在設(shè)備A1或A2上完成，B工序可在B1，B2，B3三種設(shè)備上完成。已知產(chǎn)品I可在A，B任何一種設(shè)備上加工；產(chǎn)品II可在任何規(guī)格的A設(shè)備上加工，但完成B工序時(shí)，只能在B1設(shè)備上加工，產(chǎn)品III只能在A2與B2設(shè)備上加工。加工單位產(chǎn)品所需工序時(shí)間及其他各項(xiàng)數(shù)據(jù)如表格所示，試安排最優(yōu)生產(chǎn)計(jì)劃，使該廠獲利最大。解設(shè)產(chǎn)品I，II，III的產(chǎn)量分別為x1，x2，x3件。

產(chǎn)品I六種加工方案(A1,B1),(A1,B2),(A1,B3),(A2,B1),(A2,B2),(A2,B3)加工的產(chǎn)品I的數(shù)量分別用x11,x12,x13,x14,x15,x16表示；

產(chǎn)品II兩種加工方案(A1,B1),(A2,B1)加工的產(chǎn)品II的數(shù)量分別用x21,x22表示；

產(chǎn)品III只有1種加工方案(A2,B2)加工產(chǎn)品III的數(shù)量等于x3。

x1=x11+x12+x13+x14+x15+x16

x2=x21+x22工廠的盈利為產(chǎn)品售價(jià)減去相應(yīng)的原料費(fèi)和設(shè)備加工費(fèi)，產(chǎn)品加工量只受設(shè)備有效臺(tái)時(shí)的限制。

LP模型為

生產(chǎn)與庫(kù)存的優(yōu)化安排

某工廠生產(chǎn)五種產(chǎn)品(i=1,…,5)，上半年各月對(duì)每種產(chǎn)品的最大市場(chǎng)需求量為dij(i

=1,…,5;j=1,…,6)。已知每件產(chǎn)品的單件售價(jià)為Si元，生產(chǎn)每件產(chǎn)品所需要工時(shí)為ai，單件成本為Ci元；該工廠上半年各月正常生產(chǎn)工時(shí)為rj(j=1,…,6)，各月內(nèi)允許的最大加班工時(shí)為rj

′;Ci′為加班單件成本。又每月生產(chǎn)的各種產(chǎn)品如當(dāng)月銷售不完，可以庫(kù)存。庫(kù)存費(fèi)用為Hi(元/件·月)。假設(shè)1月初所有產(chǎn)品的庫(kù)存為零，要求6月底各產(chǎn)品庫(kù)存量分別為ki件?，F(xiàn)要求為該工廠制定一個(gè)生產(chǎn)計(jì)劃，在盡可能利用生產(chǎn)能力的條件下，獲取最大利潤(rùn)。

解設(shè)xij,

xij/分別為該工廠第i種產(chǎn)品在第j個(gè)月在正常時(shí)間和加班時(shí)間內(nèi)的生產(chǎn)量；

yij為i種產(chǎn)品在第j月的銷售量，

ωij為第i種產(chǎn)品第j月末的庫(kù)存量。(1)各種產(chǎn)品每月的生產(chǎn)量不能超過(guò)允許的生產(chǎn)能力，表示為：(2)各種產(chǎn)品每月銷售量不超過(guò)市場(chǎng)最大需求量(3)每月末庫(kù)存量等于上月末庫(kù)存量加上該月產(chǎn)量減掉當(dāng)月的銷售量(4)滿足各變量的非負(fù)約束(5)該工廠上半年總盈利最大可表示為：

連續(xù)投資問(wèn)題

某部門在今后五年內(nèi)考慮給下列項(xiàng)目投資，已知：

項(xiàng)目A，從第一年到第四年每年年初需要投資，并于次年末回收本利115%；

項(xiàng)目B，第三年初需要投資，到第五年末能回收本利125%，但規(guī)定最大投資額不超過(guò)4萬(wàn)元；

項(xiàng)目C，第二年初需要投資，到第五年末能回收本利140%，但規(guī)定最大投資額不超過(guò)3萬(wàn)元；

項(xiàng)目D，五年內(nèi)每年初可購(gòu)買公債，于當(dāng)年末歸還，并加利息6%。該部門現(xiàn)有資金10萬(wàn)元，問(wèn)它應(yīng)如何確定給這些項(xiàng)目每年的投資額，使到第五年末擁有的資金的本利總額為最大?解：(1)確定決策變量,以xiA,xiB,xiC,xiD(i=1,2,…，5)分別表示第i年年初給項(xiàng)目A，B，C，D的投資額(2)投資額應(yīng)等于手中擁有的資金額

由于項(xiàng)目D每年都可以投資，并且當(dāng)年末即能回收本息。所以該部門每年應(yīng)把資金全部投出去，手中不應(yīng)當(dāng)有剩余的呆滯資金。因此第一年：該部門年初擁有100000元，所以有x1A+x1D=100000第二年：因第一年給項(xiàng)目A的投資要到第二年末才能回收。所以該部門在第二年初擁有資金額僅為項(xiàng)目D在第一年回收的本息x1D(1+6%)。于是第二年的投資分配是x2A+x2C+x2D=1.06x1D

第三年：

第三年初的資金額是從項(xiàng)目A第一年投資及項(xiàng)目D第二年投資中回收的本利總和：x1A(1+15%)及x2D(1+6%)。

于是第三年的資金分配為

x3A+x3B+x3D=1.15x1A+1.06x2D

第四年：與以上分析相同，可得x4A+x4D=1.15x2A+1.06x3D第五年：x5D=1.15x3A+1.06x4D此外，由于對(duì)項(xiàng)目B、C的投資有限額的規(guī)定，即：x3B≤40000x2C≤30000

(3)目標(biāo)函數(shù)

問(wèn)題是要求在第