第五章數(shù)學(xué)規(guī)劃模型

?數(shù)學(xué)規(guī)劃，是指在一定的條件下運用特定的方法（數(shù)學(xué)的方法）達到最佳的效果，即求各式各樣的條件極值問題.

?數(shù)學(xué)規(guī)劃是運籌學(xué)和管理科學(xué)中應(yīng)用極廣泛的分支，也是解決優(yōu)化問題的一個非常有用的工具.第五章數(shù)學(xué)規(guī)劃方法建模一、數(shù)學(xué)規(guī)劃模型的數(shù)學(xué)描述下的最大值或最小值，其中決策變量目標(biāo)函數(shù)將一個優(yōu)化問題用數(shù)學(xué)式子來描述，即求函數(shù)在約束條件可行域5.1數(shù)學(xué)規(guī)劃概述

“受約束于”之意．簡單記為以上數(shù)學(xué)模型稱為數(shù)學(xué)規(guī)劃模型．二、數(shù)學(xué)規(guī)劃模型的分類1.線性規(guī)劃（LP）

目標(biāo)函數(shù)和所有的約束條件都是決策變量的線性函數(shù)．2.非線性規(guī)劃（NLP）目標(biāo)函數(shù)和約束條件中，至少有一個非線性函數(shù)．3.整數(shù)規(guī)劃（IP）決策變量有部分或全部取整數(shù)．三、建立數(shù)學(xué)規(guī)劃模型的一般步驟1.確定決策變量和目標(biāo)變量；2.確定目標(biāo)函數(shù)的表達式；3.尋找約束條件．重點在模型的建立．通常稱

為決策變量，

為價值系數(shù)，

為消耗系數(shù),為資源限制系數(shù)。目標(biāo)函數(shù)

滿足約束條件min(max)5.2線性規(guī)劃模型

線性規(guī)劃的數(shù)學(xué)模型可以表示為下列簡潔的形式：線性規(guī)劃的數(shù)學(xué)模型還可以表示為下列矩陣形式：,,線性規(guī)劃問題矩陣形式：

其中

建立線性規(guī)劃模型的過程可以分為四個步驟：(1)設(shè)立決策變量；(2)明確約束條件并用決策變量的線性等式或不等式表示；(3)用決策變量的線性函數(shù)表示目標(biāo)，并確定是求極大（Max）還是極?。∕in）；(4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性.假定一個成年人每天需要從食物中獲取3000卡的熱量、55克蛋白質(zhì)和800毫克的鈣.如果市場上只有四種食品可供選擇，它們每公斤所含熱量和營養(yǎng)成分以及市場價格見下頁表.問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費用最小.例1營養(yǎng)配餐問題序號食品名稱熱量(卡)蛋白質(zhì)(g)鈣(mg)價格(元)1豬肉100050400142雞蛋8006020063大米10002030034白菜200105002各種食物的營養(yǎng)成分表

解:設(shè)xj為第j種食品每天的購入量，則配餐問題的線性規(guī)劃模型如下：Min

z=14x1+6x2+3x3+2x4

s.t.1000x1+800x2+900x3+200x43000 50x1+60x2+20x3+10x455 400x1+200x2+300x3+500x4800

xi0i=1,...,4

實用的配餐問題要比上例復(fù)雜的多，可包括幾十甚至上百種原料，幾十種營養(yǎng)配方.例如醫(yī)院的營養(yǎng)配餐和養(yǎng)殖業(yè)中的配合飼料問題.

要從甲地調(diào)出物質(zhì)2000噸,從乙地調(diào)出物質(zhì)1100噸,分別供給A地1700噸,B地1100噸,C地200噸和D地100噸,已知每噸運費如表所示,試建立一個使運費達到最小的調(diào)撥計劃.單位路程運費表銷地15375151乙1572521甲DCBA產(chǎn)地例2運輸問題

分析設(shè)從第個產(chǎn)地到第個銷地的運輸量為運輸成本為則問題的目標(biāo)函數(shù)為由于從第一個產(chǎn)地調(diào)出的物質(zhì)的總和為第一個產(chǎn)地的產(chǎn)量,即有同理,有對稱地,對銷地而言,有關(guān)系由此得到該問題的數(shù)學(xué)模型注該問題又稱為運輸問題.運輸問題的一般形式可寫成其中是第個產(chǎn)地的產(chǎn)量,是第個銷地的需求量.在上面的關(guān)系中,有相應(yīng)的運輸問題稱為產(chǎn)銷平衡的運輸問題.

某工廠明年根據(jù)合同，每個季度末向銷售公司提供產(chǎn)品，有關(guān)信息如表，若當(dāng)季生產(chǎn)的產(chǎn)品過多，季末有積余，則一個季度每積壓一噸產(chǎn)品需支付存貯費0.2萬元.現(xiàn)該廠考慮明年的最佳生產(chǎn)方案，使該廠在完成合同的情況下，全年的生產(chǎn)費用最低.試建立線性規(guī)劃模型.季度

j生產(chǎn)能力（aj）生產(chǎn)成本（dj）需求量（bj）13015．02024014．02032015．33041014．810例3生產(chǎn)與庫存問題

解設(shè)工廠第j季度生產(chǎn)產(chǎn)品xj

噸需求約束：第一季度末需交貨20噸，x1≥20第二季度末需交貨20噸，x1-20+x2≥20這是上季末交貨后積余第三季度末需交貨30噸，x1+x2-40+x3≥30第四季度末需交貨10噸，x1+x2+x3-70

+x4=10生產(chǎn)能力約束：0≤xj≤aj

j=1,2,3,4季度

j生產(chǎn)能力（aj）生產(chǎn)成本（dj）需求量（bj）13015．02024014．02032015．33041014．810生產(chǎn)、存儲費用：第一季度：15x1第二季度:14x2+0.2(x1-20)第三季度:15.3x3+0.2(x1+x2-40)第四季度:14.8x4+0.2(x1+x2+x3-70

)min

z

=15.6x1

+14.4x2+15.5x3+

14.8x4-26s.t.x1+x2≥40,x1+x2+x3≥70

x1+x2+x3+

x4=80,20≤x1≤30,0

≤x2≤40,0

≤x3≤20,0≤

x4≤10.某部門在今后五年內(nèi)考慮下列項目投資，已知：

項目A從第一年到第四年每年年初需要投資，并于次年末回收本利115％；

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

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

項目D五年內(nèi)每年年初可購買公債，當(dāng)年末歸還，并加利息6％．

該部門現(xiàn)有資金10萬元，問如何確定給這些項目的投資額，使到第五年末擁有資金的本利總額最大？例4連續(xù)投資問題解：（1）決策變量設(shè)分別表示第年年初給項目的投資額，根據(jù)給定的條件將變量列表如下：

12345ABCD(2)約束條件投資額應(yīng)等于手中擁有的資金，由于項目D每年都可以投資，并且當(dāng)年末就能回收本息，所以該部門每年應(yīng)把資金全部投出去，手中不應(yīng)該有滯留資金，因此：第一年：年初擁有資金10萬元，所以有第二年：因為第一年給項目A的投資到第二年末才能回收，因此在第二年初擁有資金額僅為項目D在第一年回收的本息．于是第二年年初的投資分配為：第三年：第三年初的資金額是從項目A第一年投資和項目D第二年初投資中回收的本利總和，于是第三年的投資分配是：第四年：同以上分析得第五年：此外，還有對項目的規(guī)定：(3)目標(biāo)函數(shù)(第五年末擁有的資金本利總額)(4)數(shù)學(xué)模型

某人有一筆50萬元的資金可用于長期投資,可供選擇的投資包括購買國庫券

、債券、房地產(chǎn)、股票或銀行儲蓄等．他希望投資組合的平均年限不超過5年，平均的期望收益率不低于13%，風(fēng)險系數(shù)不超過4，收益的增長潛力不低于10%．在滿足上述要求的前提應(yīng)如何選擇投資組合才能使平均收益率最高．例5證券投資組合優(yōu)化

投資投資期 年收益風(fēng)險增長潛方式限(年)率(％)系數(shù)力(％)國庫券311 1 0債券 10 15 3 15房地產(chǎn) 6 25 8 30股票 2 20 6 20短期存款1 10 1 5長期存款5 12 2 10現(xiàn)金存款0 3 0 0決策變量：各種投資方式站總投資的比例；目標(biāo)函數(shù)：平均投資收益最大；約束方程：滿足各種指標(biāo)要求平均投資年限不超過5年平均的期望收益率不低于13%風(fēng)險系數(shù)不超過4收益的增長潛力不低于15%證券組合優(yōu)化模型Max

z=11x1+15x2+25x3+20x4+10x5+12x6+3x7

s.t. 3x1+10x2+6x3+2x4+x5+5x6

511x1+15x2+25x3+20x4+10x5+12x6+3x713

x1+3x2+8x3+6x4+x5+2x6

4

15x2+30x3+20x4+5x5+10x6

10

x1+x2+x3+x4+x5+x6+x7=1

x1,x2,x3,x4,x5,x6,x70

問題某機器制造廠專為拖拉機廠配套生產(chǎn)柴油機.今年頭四個月收到的訂單數(shù)量分別為3000，4500，3500，5000臺柴油機.該廠正常生產(chǎn)每月可生產(chǎn)柴油機3000臺，利用加班還可生產(chǎn)1500臺.正常生產(chǎn)成本為每臺5000元，加班生產(chǎn)還要追加1500元成本，庫存成本為每臺每月200元．該廠如何組織生產(chǎn)才能使生產(chǎn)成本最低．例6多周期動態(tài)生產(chǎn)計劃與庫存問題模型參數(shù):

ci為第i月正常生產(chǎn)柴油機的成本；

ki為第i月加班生產(chǎn)柴油機的成本;

hi為第i月柴油機的庫存成本;

di為第i月柴油機的需求; Ei為第i月柴油機的正常生產(chǎn)能力； Fi為第i月柴油機的加班生產(chǎn)能力．決策變量：xi為第i月正常生產(chǎn)的柴油機數(shù)；yi為第i月加班生產(chǎn)的柴油機數(shù)；zi為第i月初柴油機的庫存數(shù)．?dāng)?shù)學(xué)模型：Minz=

i(ci

xi

+ki

yi

+hi

zi

)

s.t.

xi

+yi

+zi

-zi+1=di

i=1,2,3,4

xi

Ei

i=1,2,3,4 yi

Fi i=1,2,3,4

xi,

yi,

zi

0

完整模型如下：Minz=5000(x1+x2+x3+x4)+6500(y1+y2+y3+y4) +200(z2+z3+z4)

s.t.x1+y1-z2=3000

x2+y2+z2-z3=4500

x3+y3+z3-z4=3500

x4+y4+z4

=5000

0

xi

3000 i=1,2,3,4 0

yi

1500 i=1,2,3,4 zi

0 i=1,2,3,4例7：企業(yè)根據(jù)預(yù)測知道上半年市場對該企業(yè)產(chǎn)品的需求變化較大（見下表）：月份123456

需求600025005000350055006000企業(yè)目前有100名工人，每人每月可生產(chǎn)40件產(chǎn)品，工人平均工資每月800元，企業(yè)可以通過以下方法調(diào)節(jié)生產(chǎn)：

利用加班：加班需付加倍工資，每人每月利用加班生產(chǎn)的產(chǎn)品不能超過10件。利用庫存：每件產(chǎn)品庫存費用為10元/月。臨時增聘或解雇工人：新聘工人培訓(xùn)費為1000元，解雇工人的解聘費為600元。每月新聘工人數(shù)量不能超過10人。企業(yè)目前有庫存500件，希望六月底的庫存不低于700件，其他月份應(yīng)保持不少于200件的安全庫存，企業(yè)應(yīng)如何組織生產(chǎn)。變量設(shè)置：

xi：第i月在崗的工人數(shù)；

yi

：第i月新聘的工人數(shù)；

zi

：第i月解聘的工人數(shù)；

ki

：產(chǎn)品在第i月期末的庫存數(shù)量；

ui

：第i月正常生產(chǎn)的產(chǎn)品數(shù)量；

vi：第i月加班生產(chǎn)的產(chǎn)品數(shù)量；約束條件：1)每月工人的平衡約束

xi+1-xi-yi+1+zi+1=0 i=0,…,5 x1-x0-y1+z1=0 x2-x1-y2+z2=0 x3-x2-y3+z3=0 x4-x3-y4+z4=0 x5-x4-y5+z5=0

x6-x5-y6+z6=0目標(biāo)函數(shù)：生產(chǎn)和庫存費用最小minz=i(800xi+1000yi+600zi+10ki+40vi)2）每月生產(chǎn)的平衡約束

ui+vi+ki-1-ki

di

i=1,…,6

u1+v1+k0-k1

5500

u2+v2+k1-k2

3200

u3+v3+k2-k3

6700

u4+v4+k3-k4

4300

u5+v5+k4-k5

6400

u6+v6+k5-k6

75003）正常生產(chǎn)限制約束： ui-40xi

0 i=1,…,6 u1-40x1

0

u2-40x2

0 u3-40x3

0 u4-40x4

0 u5-40x5

0 u6-40x6

04）加班生產(chǎn)限制約束： vi-10xi

0 i=1,…,6 v1-10x1

0

v2-10x2

0 v3-10x3

0 v4-10x4

0 v5-10x5

0 v6-10x6

05）變量的界約束和非負(fù)約束： 安全庫存約束：ki

200i=2,…,5 k0

=500,k6

700 新聘人數(shù)約束：yi

10i=1,…,6 在崗初始人數(shù)：x0

=100 變量非負(fù)約束：

xi,yi,zi,ki,ui0i=1,…,6；某公司在下一年度的1～4月份的4個月內(nèi)擬租用倉庫堆放物資。已知各月份所需倉庫面積列于下表1。倉庫租借費用隨合同期而定，期限越長，折扣越大，具體數(shù)字見表2。租借倉庫的合同每月初都可辦理，每份合同具體規(guī)定租用面積和期限。因此該廠可根據(jù)需要，在任何一個月初辦理租借合同。每次辦理時可簽一份合同，也可簽若干份租用面積和租用期限不同的合同。試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所租借費用最少。例8（租借合同的最優(yōu)決策）月份1234所需倉庫面積15102012表1表2合同租借期限

1個月2個月3個月4個月合同期內(nèi)的租費2800450060007300單位：100m2單位；元/100m2解：設(shè)表示公司在第i(i=1,2,3,4)月初簽訂的租期為j

(j=1,2,3,4)個月的倉庫面積的合同（單位為100m2)。ⅠⅡⅢⅣⅤ∑≥15∑≥10∑≥20∑≥12經(jīng)過上面的討論，得到下面的LP模型：例9(產(chǎn)品配套問題）假定一個工廠的甲、乙、丙三個車間生產(chǎn)同一個產(chǎn)品，每件產(chǎn)品包括4個A零件，和3個B零件。這兩種零件由兩種不同的原材料制成，而這兩種原材料的現(xiàn)有數(shù)額分別為100克和200克。每個生產(chǎn)班的原材料需要量和零件產(chǎn)量如下表所示。問這三個車間各應(yīng)開多少班才能使這種產(chǎn)品的配套數(shù)達到最大約束條件為：三個車間共生產(chǎn)A零件：三個車間共生產(chǎn)B零件非線性要求：目標(biāo)函數(shù)：目標(biāo)函數(shù)Z=x4線性數(shù)學(xué)模型：線性規(guī)劃問題某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以下的項目投資.已知：項目A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利110%；項目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過30萬元；項目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過80萬元；項目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過100萬元.

思考題據(jù)測定每萬元每次投資的風(fēng)險指數(shù)如下表：a）應(yīng)如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利金額為最大？

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

線性規(guī)劃問題中,對決策變量只限于不能取負(fù)值的連續(xù)型數(shù)值．而在許多實際問題中，決策變量只有非負(fù)整數(shù)才有意義．對求整數(shù)最優(yōu)解的問題，稱為整數(shù)規(guī)劃(IntegerProgramming)(簡記為IP)．又稱約束條件和函數(shù)均為線性的IP為整數(shù)線性規(guī)劃(IntegerLinearProgramming)(簡記為ILP)．7.4整數(shù)規(guī)劃模型

線性規(guī)劃問題中,對決策變量只限于不能取負(fù)值的連續(xù)型數(shù)值．而在許多實際問題中，決策變量只有非負(fù)整數(shù)才有意義．對求整數(shù)最優(yōu)解的問題，稱為整數(shù)規(guī)劃(IntegerProgramming)(簡記為IP)．又稱約束條件和函數(shù)均為線性的IP為整數(shù)線性規(guī)劃(IntegerLinearProgramming)(簡記為ILP)．5.3整數(shù)規(guī)劃模型

在整數(shù)規(guī)劃中，處理“可供選擇條件”的問題時，常常引入0-1變量．此時的整數(shù)規(guī)劃也稱為0-1規(guī)劃．整數(shù)線性規(guī)劃模型的一般形式問題：如何下料最節(jié)省?原料鋼管:每根19米4米50根6米20根8米15根客戶需求節(jié)省的標(biāo)準(zhǔn)是什么？某金屬加工廠有長度為19米的圓鋼料多根，某客戶要訂購4米，6米，8米的棒料各50根，20根，15根，問工廠如何切割最省？

整數(shù)線性規(guī)劃模型的建立例1下料問題按照客戶需要在一根原料鋼管上安排切割的一種組合。

切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸余料3米8米1根8米1根為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)省？合理切割模式2.所用原料鋼管總根數(shù)最少模式

4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米)14003231013201341203511116030170023兩種標(biāo)準(zhǔn)1.原料鋼管剩余總余量最小xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,…7)約束滿足需求決策變量

目標(biāo)1（總余量）按模式2切割12根,按模式5切割15根，余料27米

模式4米根數(shù)6米根數(shù)8米根數(shù)余料14003231013201341203511116030170023需求502015最優(yōu)解：x2=12,x5=15,其余為0；最優(yōu)值：27。整數(shù)約束：xi為整數(shù)當(dāng)余料沒有用處時，通常以總根數(shù)最少為目標(biāo)目標(biāo)2（總根數(shù)）約束條件不變最優(yōu)解：x2=15,x5=5,x7=5,其余為0；最優(yōu)值：25。xi為整數(shù)按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米雖余料增加8米，但減少了2根與目標(biāo)1的結(jié)果“共切割27根，余料27米”相比時間所需售貨員人數(shù)星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人某中型百貨商場，對售貨人員的需求經(jīng)分析如下所示：為保證售貨人員充分休息，售貨人員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的，問應(yīng)該如何安排售貨人員的作息，既滿足了工作的需要，又使配備的售貨人員的人數(shù)最少？解例2人員安排問題時間所需售貨員人數(shù)星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人約束條件:星期日售貨員人數(shù)要求:星期一售貨員人數(shù)要求:星期二售貨員人數(shù)要求:星期三售貨員人數(shù)要求:星期四售貨員人數(shù)要求:星期五售貨員人數(shù)要求:星期六售貨員人數(shù)要求:數(shù)學(xué)模型:非負(fù)約束:數(shù)學(xué)模型:解得:某單位有5個擬選擇的投資項目，其所需投資額與期望收益如下表．由于各項目之間有一定聯(lián)系，A、C、E之間必須選擇一項且僅需選擇一項；B和D之間需選擇也僅需選擇一項；又由于C和D兩項目密切相關(guān)，C的實施必須以D的實施為前提條件，該單位共籌資金15萬元，問應(yīng)該選擇哪些項目投資，使期望收益最大？項目所需投資額（萬元）期望收益（萬元）A610B48C27D46E59例3投資項目選擇問題解：決策變量：設(shè)目標(biāo)函數(shù)：期望收益最大約束條件：投資額限制條件6x1+4x2+2x3+4x4+5x515項目A、C、E之間必須且只需選擇一項：x1+x3+x5=1項目C的實施要以項目D的實施為前提條件：x3

x4項目B、D之間必須且只需選擇一項：x2+x4=1歸納起來，其數(shù)學(xué)模型為：例4

某校籃球隊準(zhǔn)備從以下隊員中選拔3名為正式隊員，并使平均身高盡可能高，這6名預(yù)備隊員情況如下表所示。預(yù)備隊員號碼身高位置

大張1193中鋒大李2191中鋒小王3187前衛(wèi)小趙4186前衛(wèi)小田5180后衛(wèi)小周6185后衛(wèi)隊員的挑選要滿足下列條件：至少補充一名后衛(wèi)隊員；大李或小田中間只能入選一名；最多補充一名中鋒；如果大李或小趙入選，小周就不能入選。試建立此問題的數(shù)學(xué)模型。解:則該問題的數(shù)學(xué)模型為:預(yù)備隊員號碼身高位置

大張1193中鋒大李2191中鋒小王3187前衛(wèi)小趙