自學(xué)考試《運(yùn)籌學(xué)基礎(chǔ)》章節(jié)習(xí)題及答案：第5章

　　第五章作業(yè) 線性規(guī)劃P92

　　1.線性規(guī)劃的定義：線性規(guī)劃是求一組變量的值，在滿足一組約束條件下，求得目標(biāo)函數(shù)的最優(yōu)解，使決策目標(biāo)達(dá)到最優(yōu)。

　　2.闡述線性規(guī)劃的模型結(jié)構(gòu)：(答案在書上68頁)

　　·(1)變量是指實(shí)際系統(tǒng)或決策問題中有待確定的未知因素，也是指系統(tǒng)中的可控因素，一般來說，這些因素對系統(tǒng)目標(biāo)的實(shí)現(xiàn)及各項(xiàng)經(jīng)濟(jì)指標(biāo)的完成起決定作用，又稱為決策變量。

　　·(2)目標(biāo)函數(shù)是決策者對決策問題目標(biāo)的數(shù)學(xué)描述是一個(gè)極值問題，即極大值或極小值。要依據(jù)經(jīng)濟(jì)規(guī)律的客觀要求，并具體結(jié)合決策問題的實(shí)際情況來確定模型的目標(biāo)函數(shù)。

　　(3)·約束條件是指實(shí)現(xiàn)目標(biāo)的限制因素，反映到模型中就是需要滿足的基本條件即約束方程，一般是一組聯(lián)立方程組或不等式方程組的數(shù)學(xué)形式。

　　約束條件具有三種基本類型 ：大于或等于;等于;小于或等于。

　　(4)·線性規(guī)劃的變量應(yīng)為正值。

　　線性規(guī)劃明確定義:線性規(guī)劃是求一組變量X1,X2,X3…的值，在滿足一組約束條件下，求得目標(biāo)函數(shù)的最優(yōu)解(最大值或最小值)問題。

　　3、解：本題是求解最大值的問題，和書上的例題5-3類似。

　　首先擬定線性規(guī)劃模型

　　1)設(shè)定變量：

　　設(shè)該電車本周生產(chǎn)甲車x輛，乙車y輛，丙車z輛。

　　2)建立目標(biāo)函數(shù)，求利潤S 的最大值：

　　maxS=270x+400y+450z

　　3) 根據(jù)約束條件建立約束方程組：

　　x+2y+3z <=100

　　2x+2y+3z <=120

　　4) 變量非負(fù)：

　　x,y,z >=0

　　建立初始單純形表：

　　1) 引入松弛變量

　　x+2y+3z +k1=100

　　2x+2y+3z +k2=120

　　2)目標(biāo)函數(shù)：maxS=270x+400y+450z+0*k1+0*k2

　　3)變量非負(fù)

　　4)建立初始單純形表

　　Cj 270 400 450 0 0 S

　　基 x y z k1 k2

　　———————————————————————————

　　0 k1 1 2 3 1 0 100

　　0 k2 2 2 3 0 1 120

　　———————————————————————————

　　Zj 0 0 0 0 0 0

　　Cj-Zj 270 400 450 0 0 S

　　分析上面的初始表，變量系數(shù)最大的是z

　　k1所在行：100/3

　　k2所在行：120/3=40

　　所以選定 k1出基

　　進(jìn)行第一次迭代，得到如下單純形表

　　Cj 270 400 450 0 0 S

　　基 x y z k1 k2

　　———————————————————————————

　　450 z 1/3 2/3 1 1/3 0 100/3

　　0 k2 1 0 0 -1 1 20

　　———————————————————————————

　　Zj 150 300 450 150 0 15000

　　Cj-Zj 80 100 0 -150 0 S-15000

　　變量系數(shù)最大的是y,所以選擇y作為基變量。

　　z所在行：450/(2/3)=675

　　k2所在行：20/1=20

　　所以選定 k2出基

　　進(jìn)行第二次迭代，得到如下單純形表

　　Cj 270 400 450 0 0 S

　　基 x y z k1 k2

　　———————————————————————————

　　450 z 0 2/3 1 2/3 -1/3 80/3

　　270 x 1 0 0 -1 1 20

　　———————————————————————————

　　Zj 270 300 450 30 120 17400

　　Cj-Zj 0 100 0 -30 -120 S-17400

　　量系數(shù)最大的是y且是正數(shù),所以選擇y作為基變量。

　　y所在行：(80/3)/(2/3)=40

　　x所在行：20/0 =+∞

　　+∞>40，所以z出基 (小于零的和除以0的應(yīng)該不算)

　　進(jìn)行第三次迭代，得到如下單純形表

　　Cj 270 400 450 0 0 S

　　基 x y z k1 k2

　　———————————————————————————

　　400 y 0 1 3/2 3/2 -1/2 40

　　270 x 1 0 0 -1 1 20

　　———————————————————————————

　　Zj 270 400 600 330 70 21400

　　Cj-Zj 0 0 -150 -330 -70 S-21400

　　因?yàn)樗�有的系�?shù)都小于0,所以得到最優(yōu)解。

　　S=21400-150z-330k1-70k2

　　當(dāng)k1=k2=0時(shí)可得x=20,y=40

　　所以該廠本周的產(chǎn)品組合應(yīng)該為生產(chǎn)甲車20輛，乙車40輛

　　4、解：MIN S=1.5X-2.5Y+18.5

　　則S’=1.5X-2.5Y

　　約束條件：X-Y-S1+A=1/4

　　x-Y+S2=1/2

　　X+Y+S3=1

　　X+S4 =1

　　Y+S5 =1

　　標(biāo)準(zhǔn)型：MIN S’=1.5X-2.5Y+0S1+MA+0S2+0S3+0S4+0S5

　　建立初始單純行表：

　　Cj 2/3 -2/5 0 M 0 0 0 0

　　基 x y S1 A S2 S3 S4 S5 S

　　------------------------------------------------------------

　　M A 1 -1 -1 1 0 0 0 0 1/4

　　0 S2 1 -1 0 0 1 0 0 0 1/2

　　0 S3 1 -1 0 0 1 1 0 0 1

　　0 S4 1 0 0 0 0 0 1 0 1

　　0 S5 0 1 0 0 0 0 0 1 1

　　--------------------------------------------------------------

　　ZJ M -M -M M 0 0 0 0 1/4M

　　cj-zj 2/3-M -2/5+M M 0 0 0 0 0 s’-1/4m

　　分析上面的初始表，變量系數(shù)最小的是x，所以選擇x作為基變量。

　　s/x 最小的是A

　　所以選定 A出基

　　進(jìn)行第一次迭代，得到如下單純形表：

　　Cj 2/3 -2/5 0 M 0 0 0 0