線性規(guī)劃數(shù)學(xué)模型省名師優(yōu)質(zhì)課賽課獲獎?wù)n件市賽課一等獎?wù)n件

第二章線性規(guī)劃（Linear

Programming）線性規(guī)劃問題是目標(biāo)函數(shù)和約束條件均為線性最優(yōu)化問題。自從1947年丹捷格(Dantzig)提出求解線性規(guī)劃單純形方法以來，線性規(guī)劃在理論上趨向成熟。尤其是在計算機能處理成千上萬個約束條件和決議變量線性規(guī)劃問題之后，線性規(guī)劃適用領(lǐng)域更為廣泛，已成為當(dāng)代管理中經(jīng)常采取基本方法之一。線性規(guī)劃是最優(yōu)化問題中主要領(lǐng)域之一，很多運籌學(xué)中實際問題都能夠用線性規(guī)劃來表述。很多其它種類最優(yōu)化問題算法也都能夠分拆成線性規(guī)劃子問題，然后求解。經(jīng)過學(xué)習(xí)本章，應(yīng)該了解線性規(guī)劃相關(guān)概念，掌握線性規(guī)劃模型建立及優(yōu)化方法，會用計算機對大型線性規(guī)劃模型問題進行求解和分析。本章難點為單純形計算方法。第1頁1第一節(jié)線性規(guī)劃問題提出線性規(guī)劃是運籌學(xué)一個主要分支，主要用于研究處理有限資源最正確分配問題，即怎樣對有限資源做出最正確方式調(diào)配和最有利使用，方便最充分地發(fā)揮資源效能，以獲取最正確經(jīng)濟效益。它適用領(lǐng)域非常廣泛，從工業(yè)、農(nóng)業(yè)、商業(yè)、交通運輸業(yè)、軍事計劃和管理及決議到整個國民經(jīng)濟計劃最優(yōu)方案提出，都有它用武之地，是當(dāng)代管理科學(xué)主要基礎(chǔ)和伎倆之一。第2頁2第一節(jié)線性規(guī)劃問題提出線性規(guī)劃研究問題主要有以下兩類。(1) 給出一定量人力、物力、財力等資源，怎樣統(tǒng)籌規(guī)劃這些有限資源完成最大任務(wù)。（如資金、設(shè)備、原標(biāo)材料、人工、時間等）(2) 給定一項任務(wù)，怎樣運籌規(guī)劃，合理安排，以最少資源來完成它。（如產(chǎn)品量最多、利潤最大.）線性規(guī)劃要研究兩類問題中都有一個限制條件：第一類問題是給出一定量人力、物力和財力等資源；第二類問題是給定一項任務(wù)。第3頁3第二節(jié)線性規(guī)劃問題數(shù)學(xué)模型當(dāng)用線性規(guī)劃方法對實際問題進行優(yōu)化時，必須把這個實際問題用恰當(dāng)數(shù)學(xué)形式表示出來，這個表示過程，就是建立數(shù)學(xué)模型過程。數(shù)學(xué)模型建立需要經(jīng)驗和技巧以及相關(guān)專業(yè)知識，只有經(jīng)過大量實踐，在建立模型時才能得心應(yīng)手。初課時可從題目中所給出限制條件和目標(biāo)入手，由限制條件建立起線性方程組，由目標(biāo)得到目標(biāo)函數(shù)。下面，結(jié)合若干個實際問題討論數(shù)學(xué)模型建立。第4頁4一、投資問題數(shù)學(xué)模型解（參見教材P15）第5頁5二、配料問題數(shù)學(xué)模型解（參見教材P16）第6頁6二、配料問題數(shù)學(xué)模型

某化工廠要用三種原料

A，B，C

混合配制三種不一樣規(guī)格產(chǎn)品

X，Y，Z。相關(guān)數(shù)據(jù)以下：產(chǎn)品規(guī)格單價(元/kg)X原料D不少于50%原料P不超出25%50Y原料D不少于25%原料P不超出50%35Z不限25原料最大供量(kg/天)單價(元/kg)A10065B10025C6035應(yīng)如合配制，才能使利潤到達(dá)最大？表2-3表2-4第7頁二、配料問題數(shù)學(xué)模型一、決議變量

設(shè)以

xij表示天天生產(chǎn)第i

種產(chǎn)品中所含第j

種原料數(shù)量(kg，右表)。ji

A

B

CXYZx11x12x13x21x22x23x31x32x33二、約束條件⑴規(guī)格約束(據(jù)表2-3)x11+

x12+

x13x11≥

0.50x11+

x12+

x13x12≤

0.25x11+

x12+

x13x21≥

0.25x11+

x12+

x13x22≤

0.50第8頁二、配料問題數(shù)學(xué)模型改寫成

-

x11+

x12

+

x13≤

0-

x11+3

x12-x13≤

0-3

x21

+x22+

x23≤

0

x21+x22-

x23≤

0⑵資源約束(據(jù)表2-4)x11+

x21

+

x31≤

100x12+

x22+

x32≤

100x13+

x23

+

x33≤

60第9頁二、配料問題數(shù)學(xué)模型三、目標(biāo)函數(shù)⑴總產(chǎn)值(據(jù)表2-3)產(chǎn)品X產(chǎn)值:50(x11+

x12+

x13)產(chǎn)品Y產(chǎn)值:35(x21+

x22+

x23)產(chǎn)品Z產(chǎn)值:25(x31+

x32+

x33)以上三項之和即總產(chǎn)值。⑵總成本(據(jù)表2-4)原料A成本:65(x11+

x21+

x31)原料B成本:25(x12+

x22+

x32)原料C成本:35(x13+

x23+

x33)以上三項之和即總成本。第10頁二、配料問題數(shù)學(xué)模型

目標(biāo)函數(shù)為：

總利潤

=總產(chǎn)值-

總成本max

z=-15x11+25x12+15x13-30x21+10x22-40x31-10x33該問題數(shù)學(xué)模型為:s.t.

-x11

+x12+

x13

≤0-x11+3x12-

x13

≤0

-3x21+x22

+x23

≤0x21+x22-

x23≤0x11+x21+x31≤100x12+x22

+x32≤100x13

+x23+x33

≤60

xij≥

0，i=1,2,3；j=1,2,3第11頁配料問題練習(xí)：某化工廠依據(jù)一項協(xié)議要為用戶生產(chǎn)一個用甲、乙兩種原料混合配制而成特殊產(chǎn)品。甲、乙兩種原料都含有A，B，C三種化學(xué)成份，其含量(%)是:甲為12，2，

3；乙為3，3，15。按協(xié)議要求，產(chǎn)品中三種化學(xué)成份含量(%)不得低于4，2，5。甲、乙原料成本為每千克3，2元。廠方希望總成本到達(dá)最小，則應(yīng)怎樣配制該產(chǎn)品？第12頁配料問題

成份含量(%)

原

料

化學(xué)成份

甲

乙

產(chǎn)品成份

最低含量(%)A

B

C

12

3

2

3

3

15

4

2

5

成本（元/千克）

3

2

x1x2min

z

=3x1+2x212x1

+3x2≥42x1

+3x2≥2s.t.

3x1+15x2≥5

x1

+x2

=

1

x1

,

x2≥0配料平衡條件z第13頁三、人力資源問題數(shù)學(xué)模型解（參見教材P17）第14頁14三、人力資源問題數(shù)學(xué)模型練習(xí)：

某晝夜服務(wù)公交線路天天各時間段內(nèi)所需司機和乘務(wù)人員人數(shù)以下表所表示：班次時間所需人員16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030設(shè)司機和乘務(wù)人員分別在各時間段開始時上班，并連續(xù)工作8小時，問該公交線路應(yīng)怎樣安排司機和乘務(wù)人員，即能滿足工作需要，又使配置司機和乘務(wù)人員人數(shù)降低?第15頁三、人力資源問題數(shù)學(xué)模型解：設(shè)xi表示第i班次時開始上班司機和乘務(wù)人員人數(shù)。此問題最優(yōu)解：x1＝50，x2＝20，x3＝50，x4＝0，x5＝20，x6＝10，一共需要司機和乘務(wù)員150人。第16頁四、合理下料問題數(shù)學(xué)模型合理下料問題是機械工業(yè)常碰到問題。毛坯車間經(jīng)常要在長度一定條形材料或面積一定板材上切割若干個含有一定形狀、尺寸毛坯。在普通情況下，材料不可能被完全利用，會有邊角余料，造成浪費。所以，怎樣最大程度地降低邊角余料，提升材料利用率，使得切割要求數(shù)量毛坯所用材料最少就是合理下料問題所要研究。例2-5某車間有一批長度為180cm鋼管(數(shù)量充分多)，為了制造零件需要，要將其截成三種不一樣長度管料：70cm、52cm、35cm。要求這三種管料需要量分別不少于100根、150根和100根。問：應(yīng)怎樣下料能使消耗鋼管數(shù)量最少？解（參見教材P18）第17頁17四、合理下料問題數(shù)學(xué)模型練習(xí)：

制造某種機床，需要

A,B,C三種軸件，其規(guī)格與數(shù)量如表所表示，各類軸件都用5.5米長同一個圓鋼下料。若計劃生產(chǎn)100臺機床，最少需要用多少根圓鋼？第18頁四、合理下料問題數(shù)學(xué)模型軸類

規(guī)格：長度（米）

每臺機床所需軸件數(shù)

A

3.1

1

B

2.1

2

C

1.2

4

余料δj<1.2找出全部省料截法一根圓鋼所截各類軸件數(shù)

截法軸類

軸

件

需要量

A(3.1)

100

B(2.1)

200

C(1.2)

400

余料(米)

234511100.310200210.1

0

0

1

0

2

4

1

0.7第19頁四、合理下料問題數(shù)學(xué)模型min

z=

x1

+

x2

+

x3

+

x4

+

x5s.t.x1

+x2

≥100x1

+2x3

+x4

≥2002x2

+x3

+2x4

+4x5

≥400x1，x2

，x3，x4，x5

≥

0則該問題數(shù)學(xué)模型為:設(shè)第j

種截法下料

xj

根。第20頁四、合理下料問題數(shù)學(xué)模型例：現(xiàn)有一批某種型號圓鋼長8米，需要截取2.5米長毛坯100根，長1.3米毛坯200根。問怎樣才能既滿足需要，又能使總用料最少？解：為了找到一個省料套裁方案，必須先設(shè)計出很好幾個下料方案。其次要求這些方案總體能裁下全部各種規(guī)格圓鋼，以滿足對各種不一樣規(guī)格圓鋼需要并到達(dá)省料目標(biāo)，為此能夠設(shè)計出4種下料方案以供套裁用。ⅠⅡⅢⅣ2.5m32101.3m0246料頭00.40.30.2第21頁四、合理下料問題數(shù)學(xué)模型設(shè)按方案Ⅰ、Ⅱ、Ⅲ、Ⅳ下料原材料根數(shù)分別為xj(j=1，2,3,4)，可列出下面數(shù)學(xué)模型：第22頁五、運輸問題數(shù)學(xué)模型問題提出：某類產(chǎn)品有若干個產(chǎn)地，已知每個生產(chǎn)地產(chǎn)量；這類產(chǎn)品有若干個消費地，已知每個消費地需要量。假設(shè)總產(chǎn)量等于總需要量。問題是怎樣編制一個最優(yōu)運輸計劃，使從產(chǎn)地到消費地運輸費用最小。解（參見教材P20）第23頁23六、產(chǎn)品配比問題數(shù)學(xué)模型例

某廠擬生產(chǎn)甲、乙兩種產(chǎn)品，每件利潤分別為3、5百元。甲、乙產(chǎn)品部件各自在A、B兩個車間分別生產(chǎn)，每件甲、乙產(chǎn)品部件分別需要A、B車間生產(chǎn)能力1、2工時。兩件產(chǎn)品部件最終都要在C車間裝配，裝配每件甲、乙產(chǎn)品分別需要3、4工時，三車間天天可用于生產(chǎn)這兩種產(chǎn)品工時分別為8、12、36，問應(yīng)怎樣安排生產(chǎn)這兩種產(chǎn)品才能贏利最多？第24頁產(chǎn)品配比問題z

x1

x2決議變量z=3x1

+5x2max0目標(biāo)函數(shù)x1

≤8①2x2

≤12

②3x1

+4x2

≤36③函數(shù)約束

x1

，x2

≥0④非負(fù)性約束s.t.甲乙103024

81236ABC車間產(chǎn)品單耗（工時/件）最大生產(chǎn)能力（工時/天）單位利潤（百元/件）

3

5第25頁線性規(guī)劃問題數(shù)學(xué)模型練習(xí)：某企業(yè)計劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在A、B、C、D、四種不一樣設(shè)備上加工。按工藝資料要求，單件產(chǎn)品在不一樣設(shè)備上加工所需要臺時以下表所表示，企業(yè)決議者應(yīng)怎樣安排生產(chǎn)計劃，使企業(yè)總利潤最大？

設(shè)備產(chǎn)品ABCD利潤（元）

甲21402

乙22043

有效臺時1281612第26頁線性規(guī)劃問題數(shù)學(xué)模型解：設(shè)x1、x2分別為甲、乙兩種產(chǎn)品產(chǎn)量，則數(shù)學(xué)模型為：maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12第27頁七、生產(chǎn)計劃問題數(shù)學(xué)模型

某企業(yè)擬用m種資源生產(chǎn)n種產(chǎn)品，已知第i種資源數(shù)量為bi,其單價為pi,每生產(chǎn)一個單位第j種產(chǎn)品所提供產(chǎn)值為vj,所消耗第i種資源數(shù)量為aij。第j種產(chǎn)品協(xié)議與指令性計劃產(chǎn)量指標(biāo)為ej,最高需求量為dj。該企業(yè)應(yīng)怎樣確定生產(chǎn)計劃？第28頁

一、決議變量

設(shè)xj為第j種產(chǎn)品計劃產(chǎn)量

二、約束條件⑴指標(biāo)約束xj≥ej

,

j=1,2,…

,n⑵需求約束xj≤dj

,

j=1,2,…

,n⑶資源約束

三、目標(biāo)函數(shù)⑴總產(chǎn)值七、生產(chǎn)計劃問題數(shù)學(xué)模型

j=1n∑aijxj≤bi,

i=1,2,…,mj=1nm

i=1z2=∑pi(∑aij

xj)

⑵總成本z1=∑vj

xj

nj=1第29頁七、生產(chǎn)計劃問題數(shù)學(xué)模型

i=1=∑vj

xj-∑pi(∑aij

xj)j=1nmj=1n=∑(vj-

∑piaij

)

xjj=1n

i=1m令

cj

=vj-

∑piaij

i=1mxj≥ej

,

j=1,2,…

,nxj≤dj∑aijxj≤bi,

i=1,2,…,mj=1nmaxz=∑cj

xjj=1n

s.t.則⑶

總利潤

z=z1-z2第30頁七、生產(chǎn)計劃問題數(shù)學(xué)模型

某廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，都分別經(jīng)A、B兩道工序加工。設(shè)A工序可分別在設(shè)備A1和A2上完成，有B1、B2、B3三種設(shè)備可用于完成B工序。已知產(chǎn)品Ⅰ可在A、B任何一個設(shè)備上加工；產(chǎn)品Ⅱ可在任何規(guī)格A設(shè)備上加工，但完成B工序時，只能在B1設(shè)備上加工；產(chǎn)品Ⅲ只能在A2與B2設(shè)備上加工。加工單位產(chǎn)品所需工序時間及其它各項數(shù)據(jù)以下表，試安排最優(yōu)生產(chǎn)計劃，使該廠贏利最大。第31頁七、生產(chǎn)計劃問題數(shù)學(xué)模型設(shè)備產(chǎn)品設(shè)備有效臺時設(shè)備加工費（單位小時）ⅠⅡⅢ27910000321B168124000250B247000783B37114000200原料費（每件）0.250.350.5售價（每件）1.252.002.8第32頁七、生產(chǎn)計劃問題數(shù)學(xué)模型解：設(shè)xijk表示產(chǎn)品i在工序j設(shè)備k上加工數(shù)量。約束條件有：第33頁七、生產(chǎn)計劃問題數(shù)學(xué)模型目標(biāo)是利潤最大化，即利潤計算公式以下：帶入數(shù)據(jù)整理得到：第34頁七、生產(chǎn)計劃問題數(shù)學(xué)模型所以該規(guī)劃問題模型為：第35頁有n種食品,每種食品中含有m種營養(yǎng)成份。食品用

j=1,2,…

,n表示，養(yǎng)分用

i=1,2,…

,m表示。已知第

j種食品單價為

cj,天天最大供量為

dj;

而每單位第

j種食品所含第

i種養(yǎng)分?jǐn)?shù)量為

aij。假定某種生物天天對第

i種養(yǎng)分需求量最少為

bi,

而天天進食數(shù)量限定在

[

h1,

h2

]

范圍內(nèi)。試求該生物食譜，使總成本為最小。八、食譜問題數(shù)學(xué)模型第36頁八、食譜問題數(shù)學(xué)模型設(shè)xj為天天提供給該生物食用第j種食品數(shù)量，則該問題數(shù)學(xué)模型為:

s.t.

0

≤

xj

≤

dj

,

j=1,2,…,nminz=∑cj

xjj=1nj=1

h1

≤

∑xj

≤h2nj=1

∑aij

xj

≥

bi,

i=1,2,…,mn第37頁八、食譜問題數(shù)學(xué)模型配料問題例：某人天天食用甲、乙兩種食物（如豬肉、雞蛋），其資料以下：問兩種食物各食用多少，才能既滿足需要、又使總費用最省？21.5原料單價1.007.5010.000.10.151.70.751.101.30A1A2A3

最低需要量

甲乙含量食物成份第38頁八、食譜問題數(shù)學(xué)模型解：設(shè)Xj表示Bj

種食物用量第39頁九、產(chǎn)品配套問題數(shù)學(xué)模型

某廠制造某種部件，由2個B1零件,3個B2零件配套組裝而成。該廠有A1,A2,A3三種機床可加工這兩種零件，每種機床臺數(shù)，以及每臺機床生產(chǎn)率以下表所表示。求產(chǎn)量最大生產(chǎn)方案。第40頁九、產(chǎn)品配套問題數(shù)學(xué)模型

一、決議變量

設(shè)以xij表示每臺Ai(i=1,2,3)機床每個工作日加工Bj(j=1,2)零件時間(單位:工作日)；

z為B1,B2零件按2:3百分比配套數(shù)量(套/日)。機床種類機床臺數(shù)每臺機床生產(chǎn)率(件/日)零件B1零件B2A132030A223545A341018x11x12x21x22x31x32第41頁九、產(chǎn)品配套問題數(shù)學(xué)模型

二、約束條件

⑴工時約束

⑵配套約束機床種類總生產(chǎn)率(件/日)零件B1零件B2A16090A27090A34072x11x12x21x22x31x32z=min{(60x11+70x21+40x31),(90x12+90x22+72x32)}1213z≤(60x11+70x21+40x31)12z≤(90x12+90x22+72x32)13非線性，等