演示文稿管理運(yùn)籌學(xué)線性規(guī)劃應(yīng)用建模

演示文稿管理運(yùn)籌學(xué)線性規(guī)劃應(yīng)用建模當(dāng)前第1頁\共有31頁\編于星期二\11點(diǎn)管理運(yùn)籌學(xué)第二章線性規(guī)劃應(yīng)用建模當(dāng)前第2頁\共有31頁\編于星期二\11點(diǎn)人力資源分配的問題1套裁下料問題2配料問題4生產(chǎn)計劃的問題3投資問題5當(dāng)前第3頁\共有31頁\編于星期二\11點(diǎn)線性規(guī)劃應(yīng)用

合理利用線材問題：如何下料使用材最少。配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤。投資問題：從投資項目中選取方案，使投資回報最大。建模線性規(guī)劃---當(dāng)前第4頁\共有31頁\編于星期二\11點(diǎn)

產(chǎn)品生產(chǎn)計劃：合理利用人力、物力、財力等，使獲利最大。勞動力安排：用最少的勞動力來滿足工作的需要。運(yùn)輸問題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小。線性規(guī)劃應(yīng)用當(dāng)前第5頁\共有31頁\編于星期二\11點(diǎn)

數(shù)學(xué)規(guī)劃的建模有許多共同點(diǎn)，要遵循下列原則：

(1)容易理解。建立的模型不但要求建模者理解，還應(yīng)當(dāng)讓有關(guān)人員理解。這樣便于考察實(shí)際問題與模型的關(guān)系，使得到的結(jié)論能夠更好地應(yīng)用于解決實(shí)際問題。

(2)容易查找模型中的錯誤。這個原則的目的顯然與(1)相關(guān)。常出現(xiàn)的錯誤有：書寫錯誤和公式錯誤。線性規(guī)劃應(yīng)用

(3)容易求解。對線性規(guī)劃來說，容易求解問題主要是控制問題的規(guī)模，包括決策變量的個數(shù)和約束條件的個數(shù)。這條原則的實(shí)現(xiàn)往往會與(1)發(fā)生矛盾，在實(shí)現(xiàn)時需要對兩條原則進(jìn)行統(tǒng)籌考慮。當(dāng)前第6頁\共有31頁\編于星期二\11點(diǎn)

建立線性規(guī)劃模型的過程可以分為四個步驟：

(1)設(shè)立決策變量；

(2)明確約束條件并用決策變量的線性等式或不等式表示；

(3)用決策變量的線性函數(shù)表示目標(biāo)，并確定是求極大（Max）還是極?。∕in）；

(4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。線性規(guī)劃應(yīng)用當(dāng)前第7頁\共有31頁\編于星期二\11點(diǎn)

[例1]某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下：

一、人力資源分配的問題設(shè)司機(jī)和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作8h，問該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員?當(dāng)前第8頁\共有31頁\編于星期二\11點(diǎn)

解：設(shè)xi

表示第i班次時開始上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Min

z=x1+x2+x3+x4+x5+x6

約束條件：s.t.

x1+x6≥60

x1+x2≥70

x2+x3≥60

x3+x4≥50

x4+x5≥20

x5+x6≥30

x1,x2,x3,x4,x5,x6≥0一、人力資源分配的問題當(dāng)前第9頁\共有31頁\編于星期二\11點(diǎn)[例2]某工廠要做100套鋼架，每套用長為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長7.4m，問：應(yīng)如何下料，可使所用原料最??？二、套裁下料問題解:考慮下列各種下料方案（按一種邏輯順序給出）把各種下料方案按剩余料頭從小到大順序列出當(dāng)前第10頁\共有31頁\編于星期二\11點(diǎn)假設(shè)x1,x2,x3,x4,x5分別為上面前5種方案下料的原材料根數(shù)。我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：

Minz=x1+x2+x3+x4+x5

約束條件：

s.t.

x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0二、套裁下料問題當(dāng)前第11頁\共有31頁\編于星期二\11點(diǎn)約束條件用大于等于號時，目標(biāo)函數(shù)本來求所用原料最少和求料頭最少是一樣的。但由于第一個下料的方案中料頭為零，無論按第一下料方案下多少根料，料頭都為零，所以目標(biāo)函數(shù)就一定要求是原料最少。當(dāng)前第12頁\共有31頁\編于星期二\11點(diǎn)

[例3]明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機(jī)加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如下表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？三、生產(chǎn)計劃的問題當(dāng)前第13頁\共有31頁\編于星期二\11點(diǎn)解：設(shè)x1,x2,x3

分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4,x5

分別為由外協(xié)鑄造再由本公司機(jī)加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。三、生產(chǎn)計劃的問題當(dāng)前第14頁\共有31頁\編于星期二\11點(diǎn)

求xi

的利潤:利潤=售價-各成本之和可得到xi（i=1,2,3,4,5）的利潤分別為15、10、7、13、9元。這樣我們建立如下數(shù)學(xué)模型：

目標(biāo)函數(shù):Max15x1+10x2+7x3+13x4+9x5

約束條件：

s.t.5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0三、生產(chǎn)計劃的問題當(dāng)前第15頁\共有31頁\編于星期二\11點(diǎn)

[例2.14]某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下表。問：該廠應(yīng)如何安排生產(chǎn)，使利潤收入為最大？四、配料問題當(dāng)前第16頁\共有31頁\編于星期二\11點(diǎn)解：設(shè)xij

表示第i

種（甲、乙、丙）產(chǎn)品中原料j的含量。這樣我們建立數(shù)學(xué)模型時，要考慮：

對于甲：x11，x12，x13；對于乙：x21，x22，x23；對于丙：x31，x32，x33；對于原料1：x11，x21，x31；對于原料2：x12，x22，x32；對于原料3：x13，x23，x33；四、配料問題當(dāng)前第17頁\共有31頁\編于星期二\11點(diǎn)目標(biāo)函數(shù)：

利潤最大，利潤=收入-原料支出

約束條件：規(guī)格要求4個；

供應(yīng)量限制3個。

Max

z=150(x11+x12+x13)+85(x21+x22+x23)+65(x31+x32+x33)-65(x11+x21+x31)-25(x12+x22+x32)-35(x13+x23+x33)=85x11+125x12+115x13+20x21+60x22+50x23

+40x32+30x33四、配料問題當(dāng)前第18頁\共有31頁\編于星期二\11點(diǎn)s.t.0.5x11-0.5x12-0.5x13≥0

（甲對原材料1的規(guī)格要求）

-0.25x11+0.75x12-0.25x13≤0

（甲對原材料2的規(guī)格要求）

0.75x21-0.25x22-0.25x23≥0

（乙對原材料1的規(guī)格要求）

-0.5x21+0.5x22-0.5x23≤0

（乙對原材料2的規(guī)格要求）

x11+x21+x31≤100(供應(yīng)量限制）

x12+x22+x32≤100(供應(yīng)量限制）

x13+x23+x33≤60(供應(yīng)量限制）

xij≥0,i=1,2,3;j=1,2,3四、配料問題當(dāng)前第19頁\共有31頁\編于星期二\11點(diǎn)

[例5]某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以下的項目投資。已知：項目A

：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利110%；項目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過30萬元；項目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過80萬元；項目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過100萬元。

五、投資問題當(dāng)前第20頁\共有31頁\編于星期二\11點(diǎn)

據(jù)測定每萬元每次投資的風(fēng)險指數(shù)如下表：

a）應(yīng)如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利金額為最大？

b）應(yīng)如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利在330萬元的基礎(chǔ)上使得其投資總的風(fēng)險系數(shù)為最小？

五、投資問題當(dāng)前第21頁\共有31頁\編于星期二\11點(diǎn)

解：1）確定決策變量：連續(xù)投資問題設(shè)xij(i=1—5，j=1、2、3、4)表示第i

年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項目的金額。這樣我們建立如下決策變量：

A

x11x21x31x41x51

B

x12x22x32x42

C

x33

D

x24五、投資問題當(dāng)前第22頁\共有31頁\編于星期二\11點(diǎn)

2）約束條件：第一年：A當(dāng)年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是：

x11+x12=200

第二年：B次年末才可收回投資故第二年年初的資金為1.1x11，于是：

x21+x22+x24=1.1x11

第三年：年初的資金為1.1x21+1.25x12，于是：

x31+x32+x33=1.1x21+1.25x12

第四年：年初的資金為1.1x31+1.25x22，于是：

x41+x42=1.1x31+1.25x22

第五年：年初的資金為1.1x41+1.25x32，于是：

x51=1.1x41+1.25x32

B、C、D的投資限制：xi2≤30(i=1，2，3，4)，x33≤80，x24≤100五、投資問題當(dāng)前第23頁\共有31頁\編于星期二\11點(diǎn)a)Max

z=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200

x21+x22+x24=1.1x11

x31+x32+x33=1.1x21+1.25x12

x41+x42=1.1x31+1.25x22

x51=1.1x41+1.25x32

xi2≤30(i=1、2、3、4)，

x33≤80，x24≤100xij≥0(i=1,2,3,4,5；j=1,2,3,4）3）目標(biāo)函數(shù)及模型：五、投資問題當(dāng)前第24頁\共有31頁\編于星期二\11點(diǎn)b)Min

f=（x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24s.t.

x11+x12=200

x21+x22+x24=1.1x11

x31+x32+x33=1.1x21+1.25x12

x41+x42=1.1