第六章規(guī)劃模型-顏文勇

第六章數(shù)學(xué)規(guī)劃模型學(xué)習(xí)目標(biāo)1.掌握建立線性規(guī)劃問(wèn)題、整數(shù)規(guī)劃問(wèn)題和非線性規(guī)劃問(wèn)題模型的方法；

2.掌握求解線性規(guī)劃問(wèn)題、整數(shù)規(guī)劃問(wèn)題和非線性規(guī)劃問(wèn)題的求解方法；3.了解多目標(biāo)規(guī)劃的建立及求解方法．

數(shù)學(xué)規(guī)劃是指在一項(xiàng)活動(dòng)中決策者如何采用最好的資源配置方式以獲得最大效用或達(dá)到最佳效果．如利用有限的人力、物力、資金等資源使得生產(chǎn)活動(dòng)支付的成本最小或獲得的利潤(rùn)最大．?dāng)?shù)學(xué)規(guī)劃問(wèn)題一般是求在給定條件下目標(biāo)函數(shù)的最大值（max）或最小值（min），其一般形式為前言目標(biāo)函數(shù)決策變量約束條件數(shù)學(xué)規(guī)劃模型的結(jié)構(gòu)一般包括以下三個(gè)方面：1．決策變量：該問(wèn)題的決定因素，也是通過(guò)模型建立與求解將確定的未知量．2．目標(biāo)函數(shù)：指所關(guān)心的目標(biāo)(某一變量)與相關(guān)的因素(某些變量)的函數(shù)關(guān)系．3．約束條件：實(shí)現(xiàn)目標(biāo)的制約因素．6.1線性規(guī)劃模型

6.1.1生產(chǎn)活動(dòng)問(wèn)題

6.1.2運(yùn)輸問(wèn)題

6.1.3投資問(wèn)題線性規(guī)劃模型的一般形式為：或表示為：其中，為已知常數(shù)，為決策變量，為目標(biāo)函數(shù)．問(wèn)題1【生產(chǎn)安排模型】

詠樂(lè)豆腐店用不同質(zhì)量的黃豆制作兩種不同口感的豆腐．制作口感較鮮嫩的豆腐每千克需要一級(jí)黃豆0.2kg及二級(jí)黃豆0.1kg，售價(jià)為5元/kg；制作口感較厚實(shí)的豆腐每千克需要一級(jí)黃豆0.1kg及二級(jí)黃豆0.3kg，售價(jià)3元/kg．現(xiàn)小店購(gòu)入9kg一級(jí)黃豆和8kg二級(jí)黃豆．問(wèn)豆腐店應(yīng)制作兩種豆腐各多少kg，才能獲得最大收益，最大收益是多少？6.1.1生產(chǎn)活動(dòng)問(wèn)題一、模型假設(shè)與符號(hào)說(shuō)明1.假設(shè)制作的各種豆腐均能全部售完

．2.假設(shè)豆腐售價(jià)無(wú)波動(dòng)

．3.設(shè)計(jì)劃制作口感鮮嫩和厚實(shí)的豆腐各

x1kg和x2kg，可獲得R元收益

．二、模型的分析與建立

該問(wèn)題是在原材料一定的情況下確定各種豆腐的生產(chǎn)量，以獲得最大收益.目標(biāo)：獲得的總收益最大．而總收益可表示為

約束條件：

1．受一級(jí)黃豆數(shù)量的限制：2．受二級(jí)黃豆數(shù)量的限制：綜上分析，得到該問(wèn)題的線性規(guī)劃模型

三、模型求解x=sdpvar(1,2);C=[53];a=[0.20.1;0.10.3];b=[98];f=C*x';F=set(0<=x<=inf);F=F+set(a*x'<=b');solvesdp(F,-f);double(f)double(x)

據(jù)此建立此問(wèn)題的m文件fun6_1.m

運(yùn)行結(jié)果如下：

ans=232ans=38.000014.0000由此可知，制作口感鮮嫩和口感厚實(shí)兩種豆腐分別為38kg、14kg時(shí)豆腐店可獲得最大收益,最大收益為232元．

拓展思考

若豆腐店還要用黃豆生產(chǎn)豆?jié){，而每制作1kg豆?jié){需要一級(jí)黃豆80克，又已知豆?jié){的售價(jià)為1元/kg，受銷量影響，每天最多只能生產(chǎn)200kg豆?jié){．問(wèn)豆腐店該如何安排生產(chǎn)量，才能使收益最高．

建立規(guī)劃模型的一般步驟1.形成問(wèn)題：提出最優(yōu)化問(wèn)題，包括敘述目標(biāo)是什么？約束條件是什么？求什么變量？2．建立模型：建立最優(yōu)化問(wèn)題的數(shù)學(xué)模型，確定變量，列出目標(biāo)函數(shù)及約束式（等式或不等式）．3.分析模型：選擇合適的求解方法．目前，一般利用計(jì)算機(jī)輔以計(jì)算．YALMIP規(guī)劃工具箱簡(jiǎn)介YALMIP（Matlab優(yōu)化工具箱）求解線性規(guī)劃，整數(shù)規(guī)劃，非線性規(guī)劃，混合規(guī)劃．YALMIP工具箱求解規(guī)劃問(wèn)題的方法如下：▲定義變量：sqdvar（）:實(shí)型intvar（）:整型binvar（）:0-1型▲設(shè)定目標(biāo)函數(shù):f=目標(biāo)函數(shù)▲設(shè)定限定條件：F=set（限定條件）▲多個(gè)限定條件用加號(hào)相連：F=set（限定條件）+set（限定條件1）+set（限定條件2）……▲求解：solvesdp（F,f）這里解得是F條件下目標(biāo)函數(shù)f的最小值，要求最大值f前面加個(gè)負(fù)號(hào)．求解之后查看數(shù)值:double（f）double（變量）．一般地，設(shè)某公司有m種資源B1,B2,…,Bm,生產(chǎn)n種不同的產(chǎn)品A1,A2,…,An．其單位利潤(rùn)等有關(guān)數(shù)據(jù)見(jiàn)表6-2，問(wèn)如何安排生產(chǎn)使總利潤(rùn)最大．產(chǎn)品資源A1A2…An總量B1a11

a12

a1n

b1B2a21

a22

a2n

b2

……………Bmam1

am2

amn

bm

單位利潤(rùn)c1

c2cn

設(shè)xj表示第j種產(chǎn)品的產(chǎn)量，則可得線性規(guī)劃模型如下：若還要考慮固定成本，則需要引入0-1變量．設(shè)第j種產(chǎn)品的固定成本為Mj，第j種產(chǎn)品產(chǎn)量的上界為L(zhǎng)j，引入0-1變量

則模型為

問(wèn)題3【蔬菜運(yùn)送模型】某市東、南、西三個(gè)蔬菜基地要向市內(nèi)東、南、西、北四個(gè)菜市場(chǎng)運(yùn)送蔬菜以保證該市居民每天的蔬菜需求．東南西三個(gè)蔬菜基地的蔬菜供應(yīng)量分別為2000T，2500T，3000T．東、南、西、北四個(gè)菜市場(chǎng)蔬菜需求量分別為2000T，2300T，1800T，1400T．每噸蔬菜的運(yùn)送費(fèi)用見(jiàn)表6-3．問(wèn)應(yīng)該如何制訂運(yùn)送方案才能使運(yùn)費(fèi)最省．

6.1.2運(yùn)輸問(wèn)題市場(chǎng)蔬菜基地市場(chǎng)東市場(chǎng)南市場(chǎng)西市場(chǎng)北基地東21271340基地南45513720基地西32352030表6-3一、模型假設(shè)與符號(hào)說(shuō)明1.假設(shè)運(yùn)輸費(fèi)用不受其他因素影響．2.假設(shè)只考慮各市場(chǎng)對(duì)蔬菜總量的要求，而不考慮各個(gè)市場(chǎng)對(duì)不同種類蔬菜需求量的要求．3.設(shè)東、南、西蔬菜基地分別運(yùn)往東、南、西、北市場(chǎng)的蔬菜數(shù)量為

xij，每噸蔬菜運(yùn)費(fèi)為cij，其中i=1,2,3表示東、南、西蔬菜基地，

j=1,2,3,4表示東、南、西、北市場(chǎng)．二、模型的分析與建立該問(wèn)題要求制定不同蔬菜基地向不同菜市場(chǎng)運(yùn)送蔬菜的數(shù)量，使得在滿足居民日常蔬菜需求的條件下運(yùn)送蔬菜的費(fèi)用最低．通過(guò)簡(jiǎn)單分析，發(fā)現(xiàn)3個(gè)蔬菜基地的蔬菜供應(yīng)總量恰好等于4個(gè)市場(chǎng)的需求總量．

目標(biāo)：運(yùn)送蔬菜總的費(fèi)用最省．其中運(yùn)送蔬菜的總費(fèi)用為

約束條件：

1．受蔬菜基地蔬菜產(chǎn)量的限制，運(yùn)往四個(gè)市場(chǎng)的蔬菜總量要等于該基地產(chǎn)量，如以基地東為例，有

2．受市場(chǎng)蔬菜需求量的限制，不同基地運(yùn)往同一市場(chǎng)蔬菜的總量應(yīng)等于其需求量，如以市場(chǎng)東為例，有

綜上分析，得到該問(wèn)題的線性規(guī)劃模型三、模型求解x=intvar(3,4);C=[21271340;45513720;32352030];a=[200025003000];b=[2000230018001400];f=sum(sum(C.*x));F=set(0<=x<=inf);F=F+set((sum(x'))'<=a')+set((sum(x))'==b');solvesdp(F,f)double(f)double(x)

據(jù)此建立此問(wèn)題的m文件fun6_3.m

運(yùn)行結(jié)果如下：

ans=204100ans=200000001100014000120018000由此可以得到蔬菜運(yùn)輸費(fèi)用最省的運(yùn)送方案，見(jiàn)表6-4．

表6-4市場(chǎng)蔬菜基地市場(chǎng)東市場(chǎng)南市場(chǎng)西市場(chǎng)北基地東542642475341基地南666767600467基地西792891725592拓展思考1.如果各市場(chǎng)對(duì)普通蔬菜和反季節(jié)蔬菜有不同的要求，問(wèn)又該如何建立模型．2.在考慮兩類蔬菜調(diào)配方案的基礎(chǔ)上，能否推廣至一般情形．問(wèn)題4【裝貨模型】

遠(yuǎn)洋號(hào)貨輪有前、中、后三個(gè)艙位，它們的容積與最大允許載重量見(jiàn)表6-5．現(xiàn)有三種貨物待運(yùn)，相關(guān)數(shù)據(jù)見(jiàn)表6-6．問(wèn)該貨輪應(yīng)裝載A、B、C各多少件才能使運(yùn)費(fèi)收入最大．前艙中艙后艙最大允許載重量（t）200030001500容積（m3）400054001500表6-5表6-6商品數(shù)量(件)每件體積(m3/件)每件重量(t/件)運(yùn)價(jià)(元/件)A6001081000B100056700C80075600一、模型假設(shè)與符號(hào)說(shuō)明1.假設(shè)物資裝運(yùn)時(shí)貨物之間的空隙忽略不計(jì)．2.假設(shè)每件貨物不能拆分裝載．3.假設(shè)貨物的重量無(wú)差異．4.只考慮貨物體積限制，不具體考慮貨物長(zhǎng)寬高等尺寸的限制．5.設(shè)商品A、B、C分別裝入前艙、中艙、后艙的數(shù)量為xij，i=1,2,3，j=1,2,3二、模型的分析與建立該問(wèn)題要求在滿足不同艙位對(duì)重量和體積的限制條件下合理安排各種貨物的裝載數(shù)量，以獲得最大收入．目標(biāo)：運(yùn)費(fèi)總收入最大．其中運(yùn)費(fèi)總收入函數(shù)為約束條件：

1．受船艙重量限制(以前艙為例)：2．受船艙容積限制(以前艙為例)：3．受貨物數(shù)量限制（以為例）：

綜上分析，得到該問(wèn)題的線性規(guī)劃模型三、模型求解x=intvar(1,9);C=[100010001000700700700600600600];a1=[865];a2=[1057];b1=[200030001500];b2=[400054001500];f=C*x';F=set(0<=x<=inf);據(jù)此建立此問(wèn)題的m文件fun6_4.m

F=F+set(a1*[x(1)x(4)x(7)]'<=b1(1))+set(a1*[x(2)x(5)x(8)]'<=b1(2))+set(a1*[x(3)x(6)x(9)]'<=b1(3))+set(a2*[x(1)x(4)x(7)]'<=b2(1))+set(a2*[x(2)x(5)x(8)]'<=b2(2))+set(a2*[x(3)x(6)x(9)]'<=b2(3))+set(x(1)+x(2)+x(3)<=600)+set(x(4)+x(5)+x(6)<=1000)+set(x(7)+x(8)+x(9)<=800);solvesdp(F,-f)double(f)double(x)運(yùn)行結(jié)果如下：ans=801000ans=150375750015016000表6-7由此得到各類貨物裝在不同艙位獲利最大的方案，見(jiàn)表6-7．商品前艙中艙后艙A15037575B00150C16000拓展思考1.此模型獲得的最大收益時(shí)可能導(dǎo)致前艙，中艙貨物過(guò)多，從而出現(xiàn)頭重腳輕，致使行船危險(xiǎn)性增大．請(qǐng)查閱相關(guān)資料考慮在盡量平衡的狀態(tài)下的最優(yōu)貨物裝載方式．2.該問(wèn)題與上一問(wèn)題同屬物流配送問(wèn)題．不同的是該問(wèn)題考慮的是在裝載空間有限的條件下的物資配送．在實(shí)際物流配送中，我們往往要考慮諸多因素，首先是對(duì)不同地區(qū)物資運(yùn)送量的分配（如問(wèn)題3），其次是運(yùn)往每一地區(qū)的物資運(yùn)送方案的確定（如本題）．一般地，設(shè)某產(chǎn)品有m個(gè)產(chǎn)地A1,A2,…,Am，n個(gè)銷地B1,B2,…,Bn．各產(chǎn)地的產(chǎn)量、各銷地的需求量及各產(chǎn)地運(yùn)往各銷地的單位運(yùn)價(jià)如表6-8，且設(shè)，問(wèn)在滿足各地需求以及生產(chǎn)能力允許的條件下如何調(diào)運(yùn)使總運(yùn)費(fèi)最少．

銷品產(chǎn)地B1B2…Bn總量A1c11

c12

c1n

a1A2c21

c22

c2n

a2

……………Amcm1

cm2

cmn

am

需求量b1

b2bn

設(shè)xij表示從產(chǎn)地Ai運(yùn)往銷地Bj的數(shù)量，則可得線性規(guī)劃模型如下：?jiǎn)栴}5【投資收益模型】中財(cái)證券承諾為宏遠(yuǎn)建筑公司提供以下貸款：從2010年起連續(xù)4年內(nèi)，于每年年初提供如下數(shù)額的貸款：2010年——100萬(wàn)元，2011年——150萬(wàn)元，2012年——120萬(wàn)元，2013年——110萬(wàn)元．以上貸款中財(cái)證券已于2009年年底已全部籌集到．但為了充分發(fā)揮這筆資金的作用，在滿足每年貸款額的前提下，中財(cái)證券可將多余資金分別用于下列投資項(xiàng)目：6.1.3投資問(wèn)題（1）2010年初購(gòu)買A種債券，期限3年，到期后本息合計(jì)為投資額的140％，限購(gòu)60萬(wàn)元；（2）2010年初購(gòu)買B種債券，期限2年，到期后本息合計(jì)為投資額的125％，限購(gòu)90萬(wàn)元；（3）2011年初購(gòu)買C種債券，期限2年，到期后本息合計(jì)為投資額的130％，限購(gòu)50萬(wàn)元；（4）銀行年息4％．問(wèn)中財(cái)證券應(yīng)如何安排這筆籌集到的資金，使得2009年年底需要籌集到的資金數(shù)額最少．一、模型假設(shè)與變量說(shuō)明1.假設(shè)各項(xiàng)投資收益穩(wěn)定．2.假設(shè)投資金額能及時(shí)回收用于貸款，無(wú)時(shí)間擔(dān)擱．3.假設(shè)證券公司每年年初將用于貸款和投資后多余的資金全部存入銀行，年底取出．4.設(shè)2009年年底籌集的資金為P萬(wàn)元，購(gòu)買A,B,C債券的金額分別為xA,xB,xC萬(wàn)元，每年存銀行金額為xi，i=1,2,3

二、模型的分析與建立該問(wèn)題是在滿足對(duì)建筑公司每年貸款數(shù)額要求的條件下，合理安排每年的投資計(jì)劃，使得2009年底籌集到的貸款金額最少．目標(biāo)：2009年年底籌集的貸款金額P最少．約束條件：

1．受2010年年初貸款數(shù)額限制：2．受2011年年初貸款數(shù)額限制：3．受2012年年初貸款數(shù)額限制：4．受2013年年初貸款數(shù)額限制：綜上分析，得到該問(wèn)題的線性規(guī)劃模型三、模型求解x=intvar(1,7);a1=[-100-1-101;0.04-10-1-1-11;0.040.04-1-10.25-11;0.040.040.040.40.250.31];b1=[100250370480];f=x(7);F=set(0<=x<=inf);F=F+set(a1*x'>=b1')+set(x(4)<=60)+set(x(5)<=90)+set(x(6)<=50);solvesdp(F,f)double(f)double(x)據(jù)此建立此問(wèn)題的m文件fun6_5.m

運(yùn)行結(jié)果如下：

ans=421ans=175100588822421由此可知，在10，11，12年初分別存入銀行175萬(wàn)，10萬(wàn)，0萬(wàn)，購(gòu)買A種債券58萬(wàn)，B種債券88萬(wàn)，C種債券22萬(wàn)，這樣在2009年底只需要籌集到421萬(wàn)元資金，就能滿足今后4年內(nèi)提供的貸款需求．拓展思考1.請(qǐng)調(diào)查某一保險(xiǎn)基金的投資管理情況，并對(duì)影響投資收益的相關(guān)因素作出分析，給出結(jié)論．2．請(qǐng)參考幾種實(shí)際的基金或者保險(xiǎn)業(yè)務(wù)，制定出一套投資方案．3．如果你是位投資理財(cái)師，該如何為客戶制訂較好的投資理財(cái)方案．6.2整數(shù)規(guī)劃模型

6.2.1生產(chǎn)活動(dòng)問(wèn)題

6.2.2人力資源管理問(wèn)題

數(shù)學(xué)規(guī)劃問(wèn)題中有很多決策變量都只能取整數(shù)，如人員數(shù)量、機(jī)器設(shè)備臺(tái)數(shù)、服裝件數(shù)、汽車輛數(shù)等．如果規(guī)劃問(wèn)題中的決策變量xi(i=1,2,…,n),要求取整數(shù)值，則稱這個(gè)模型為整數(shù)規(guī)劃模型．其中，為已知常數(shù)，為決策變量。問(wèn)題7【銷售安排模型】樂(lè)家百貨商場(chǎng)準(zhǔn)備派小李、小張、小王三位銷售人員去銷售庫(kù)存的120件大衣．由于他們以前的銷售業(yè)績(jī)不同，每銷售一件產(chǎn)品小李、小張、小王的報(bào)酬分別為6元、4元、3元．商場(chǎng)為保證銷售速度，規(guī)定小李至少要承擔(dān)30件銷售任務(wù)，小張至少要承擔(dān)20件銷售任務(wù)，而小王承擔(dān)的銷售任務(wù)不能超過(guò)50件．問(wèn)應(yīng)該如何安排銷售計(jì)劃使總銷售成本最低．一、模型假設(shè)與變量說(shuō)明1．假設(shè)三位銷售人員能銷售完120件大衣．2．小李、小張、小王承擔(dān)的銷售任務(wù)分別為

x1,x2,x3．二、模型的分析與建立

該問(wèn)題是在對(duì)三位銷售人員銷售數(shù)量進(jìn)行一定限制的情況下，合理安排各銷售人員的銷售數(shù)量，使得公司支付給三位銷售人員的總報(bào)酬最少．目標(biāo)：三位銷售人員的總報(bào)酬最低．而總報(bào)酬為

約束條件：

1．受總銷售數(shù)量的限制：

2．受銷售員銷售數(shù)量的限制（如小李）：

綜上分析，得到該問(wèn)題的整數(shù)規(guī)劃模型三、模型求解x=intvar(1,3);f=[643]*x';F=set(0<=x<inf);F=F+set([111]*x'==120)+set(x(1)>=30)+set(x(2)>=20)+set(0<=x(3)<=50);solvesdp(F,f)double(f)double(x)據(jù)此建立此問(wèn)題的m文件fun6_7.m

運(yùn)行結(jié)果如下：

ans=490ans=304050由此可知，小李，小張，小王分別承擔(dān)30，40，50件銷售任務(wù)時(shí)，公司支付的總報(bào)酬最少．

拓展思考1.請(qǐng)調(diào)研銷售行業(yè)營(yíng)銷人員薪酬的確定方式．2．我國(guó)營(yíng)銷人員數(shù)量眾多，一般來(lái)說(shuō)，營(yíng)銷人員的收入都與銷售額有關(guān)．而某些企業(yè)為提高產(chǎn)品銷售量，留住優(yōu)秀的營(yíng)銷人員，建立的激勵(lì)機(jī)制便是賣出的產(chǎn)品越多，提成也越高．如果本題中，營(yíng)業(yè)員銷售超過(guò)20件產(chǎn)品時(shí)，每件產(chǎn)品可多提成一元，40件多提成兩元，以此類推，最高提成不超過(guò)10元．問(wèn)在這種情況下應(yīng)如何安排銷售任務(wù)．3．如果營(yíng)業(yè)員銷售超過(guò)20件產(chǎn)品時(shí)，超出部分每件多提成一元，結(jié)果又如何？

matlab的優(yōu)化工具箱—YALMIP可以解決線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃和混合規(guī)劃．用Matlab公具箱編寫(xiě)求解此類問(wèn)題的幾個(gè)函數(shù)為：intvar（m，n）：生成整數(shù)型變量；sdpvar（m，n）：生成變量；solvesdp（F，f）：求解最優(yōu)解（最小值），其中F為約束條件（用set連接），f為目標(biāo)函數(shù)；double：顯示求解的答案注：intvar，sdpvar生成的變量可以像矩陣一樣使用．問(wèn)題8【汽車調(diào)度模型】豐順汽車運(yùn)輸隊(duì)有8輛載重量為6T的A型卡車和6輛載重量為10T的B型卡車，有10名駕駛員．此車隊(duì)承擔(dān)了每天從甲地運(yùn)送至少720T蔬菜到乙地的任務(wù)．已知每輛卡車每天往返的次數(shù)為A型卡車16次，B型卡車12次．每輛卡車每天往返的成本費(fèi)為A型車240元，B型車378元．問(wèn)每天派出A型車與B型車各多少輛可使運(yùn)輸隊(duì)花費(fèi)的成本最低．

一、模型假設(shè)與變量說(shuō)明1.假設(shè)卡車不能超載．2.假設(shè)卡車往返次數(shù)不受駕駛員駕駛速度、車況等因素影響．3.假設(shè)每種型號(hào)每輛車的運(yùn)輸成本只與車次有關(guān)，與其他因素?zé)o關(guān)．4.假設(shè)每位駕駛員都能駕駛各種類型的車輛．5.設(shè)每天派出x1輛A型車和x2輛B型車，總的運(yùn)輸成本為C元．二、模型的分析與建立

該問(wèn)題是求在滿足卡車數(shù)量、往返次數(shù)、司機(jī)數(shù)量等限制條件下完成運(yùn)輸任務(wù)所需的運(yùn)輸成本最?。繕?biāo)：求運(yùn)輸?shù)目偝杀咀钚。渲羞\(yùn)輸總成本為約束條件：

1．受A型車數(shù)量限制：2．受B型車數(shù)量限制：

3．受司機(jī)數(shù)量限制：4．受每天運(yùn)輸任務(wù)的限制：綜上分析，得到該問(wèn)題的整數(shù)規(guī)劃模型三、模型求解x=intvar(1,2);C=[240378];a=[10;01;11];b=[8610];f=C*x';F=set(0<=x<=inf);F=F+set(a*x'<=b')+set(96*x(1)+120*x(2)>=720);solvesdp(F,f)double(f)double(x)據(jù)此建立此問(wèn)題的m文件fun6_8.m

運(yùn)行結(jié)果如下：

ans=1920ans=80由此可知，運(yùn)輸隊(duì)每天只需要派出8輛型卡車就既能完成運(yùn)輸任務(wù)又能使得成本最低，最低成本為1920元．

拓展思考1.若每天的運(yùn)輸任務(wù)增至792T，結(jié)果如何？2.若每噸蔬菜的運(yùn)費(fèi)為5元，試確定運(yùn)輸隊(duì)每天的最大收益．3.目前由于許多高校多校區(qū)辦學(xué)，因此開(kāi)通了各校區(qū)之間的交通車．請(qǐng)調(diào)查校內(nèi)校車運(yùn)行成本，座位數(shù)量等數(shù)據(jù)，制定一套合理的客車調(diào)度方案．問(wèn)題9【生產(chǎn)成本控制模型】吉發(fā)汽車生產(chǎn)商正在制訂來(lái)年四個(gè)季度的汽車生產(chǎn)計(jì)劃．根據(jù)前幾年生產(chǎn)銷售經(jīng)驗(yàn)估計(jì)，明年前兩個(gè)季度汽車生產(chǎn)成本為每輛30000元，后兩個(gè)季度為35000元．每個(gè)季度汽車的需求量分別為700輛，800輛，1000輛，1200輛．工廠每個(gè)季度最多生產(chǎn)900輛汽車，為了應(yīng)對(duì)特殊情況，工廠允許第二、三兩個(gè)季度加班．每個(gè)季度加班最多可增加300輛汽車，但每輛汽車的成本將增加6000元．過(guò)剩產(chǎn)品的存貯費(fèi)用為每個(gè)季度3000元/輛．問(wèn)汽車生產(chǎn)商應(yīng)如何安排生產(chǎn)，使得總成本最低．

一、模型假設(shè)與變量說(shuō)明1.假設(shè)汽車的需求量為廠家可銷售的數(shù)量．2.假設(shè)在一個(gè)季度內(nèi)生產(chǎn)的車輛不考慮存儲(chǔ)費(fèi)．3.設(shè)四個(gè)季度正常工作時(shí)間內(nèi)生產(chǎn)的汽車分別為

x1,x2,x3,x4輛；第二、三個(gè)季度加班生產(chǎn)的汽車為

x5,x6,輛．總成本為C元．=二、模型的分析與建立該問(wèn)題是在生產(chǎn)規(guī)模受限，市場(chǎng)需求一定的情況下，制定不同季度的汽車產(chǎn)量，使汽車制造總成本最低．

目標(biāo)：汽車的總成本最低．而總成本包括正常工作時(shí)間生產(chǎn)的成本，加班時(shí)間的生產(chǎn)成本和每季度過(guò)剩車輛的存貯費(fèi)．其中正常工作時(shí)間的生產(chǎn)成本為

加班時(shí)間的生產(chǎn)成本為

第一季度末過(guò)剩車輛在第二季度的存貯費(fèi)為

第二季度末過(guò)剩車輛在第三季度的存貯費(fèi)為

第三季度末過(guò)剩車輛在第四季度的存貯費(fèi)為要使總成本最低，第四季度末應(yīng)沒(méi)有過(guò)剩車輛，因此第四季度末無(wú)存貯費(fèi)．因此總的存貯費(fèi)為

約束條件：

1．受第一季度需求量的限制：2．受前二季度需求量的限制：3．受前三季度需求量的限制：約束條件：

4．受四個(gè)季度總需求量的限制：5．受正常工作時(shí)間內(nèi)產(chǎn)量的限制：6．受加班時(shí)間產(chǎn)量的限制：綜上分析，得到該問(wèn)題的整數(shù)規(guī)劃模型三、模型求解x=intvar(1,6);C=[390003600038000350004200044000]a1=[110010;111011];b=[15002500];a2=[111111];f=C*x'-14100000;F=set(0<=x<=900)+set(a2*x'==3700);F=F+set(a1*x'>=b')+set(x(1)>=700)+set(x(5)<=300)+set(x(6)<=300);solvesdp(F,f)double(f)double(x)

據(jù)此建立此問(wèn)題的m文件fun6_9.m

運(yùn)行結(jié)果如下：

ans=123000000ans=9009009009001000由此可知，在第一、二、三、四季度分別生產(chǎn)900，900，900，900輛汽車，第二季度加班生產(chǎn)100輛汽車可使得成本最低，最低成本為123000000元，即1.23億．問(wèn)題10【超市人力資源需求模型

】開(kāi)心購(gòu)物24小時(shí)營(yíng)業(yè)超市需要招收一批服務(wù)人員，要求每人每天連續(xù)工作八小時(shí)（即兩個(gè)時(shí)段）.每日各個(gè)時(shí)段超市需要服務(wù)員的最低數(shù)量見(jiàn)表6-10．問(wèn)超市至少需要招聘多少名服務(wù)人員，才能滿足超市日常業(yè)務(wù)需求？

6.2.2人力資源管理問(wèn)題

時(shí)段時(shí)間最低人數(shù)12：00-6：001026：00-10：0020310：00-14：0040414：00-18：0050518：00-22：0080622：00-2：0020表6-10

一、模型假設(shè)與符號(hào)說(shuō)明1．假設(shè)服務(wù)員在某一時(shí)段一起開(kāi)始上班，在某一時(shí)段結(jié)束時(shí)一起下班．2．假設(shè)每個(gè)服務(wù)員必須連續(xù)工作兩個(gè)時(shí)段．3．假設(shè)不考慮上下班人員交接班、中途吃飯和休息等時(shí)間．4.設(shè)

xi為第

i時(shí)段開(kāi)始上班的人數(shù)(i=1,2,…,6)二、模型的分析與建立

該問(wèn)題是在滿足超市每天每個(gè)時(shí)段最低服務(wù)人數(shù)要求的條件下，給出總?cè)藛T最少的配置方案．由于每個(gè)時(shí)段都有可能有人剛上班也有可能有人剛下班，因此需要找出每個(gè)時(shí)段上下班人員流動(dòng)情況，再計(jì)算出總的服務(wù)人員數(shù)量．目標(biāo)：服務(wù)員人數(shù)最少．所需服務(wù)員的總數(shù)為

約束條件：

受每個(gè)時(shí)段最低人數(shù)要求的限制，如第一時(shí)段開(kāi)始上班的人與第六時(shí)段開(kāi)始上班的人均服務(wù)于第一時(shí)段．

綜上分析，得到該問(wèn)題的整數(shù)規(guī)劃模型三、模型求解x=intvar(1,6);a=[102040508020];f=sum(x);F=set(0<=x<=inf);F=F+set(x(6)+x(1)>=a(1))+set(x(2)+x(1)>=a(2))+set(x(2)+x(3)>=a(3))+set(x(3)+x(4)>=a(4))+set(x(4)+x(5)>=a(5))+set(x(6)+x(5)>=a(6));solvesdp(F,f)double(f)double(x)據(jù)此建立此問(wèn)題的m文件fun6_10.m

運(yùn)行結(jié)果如下：

ans=130ans=1040060200由此可知，超市至少需要招聘130名服務(wù)人員．

拓展思考1.請(qǐng)調(diào)研企業(yè)（如大型工廠或超市）確定招聘人員數(shù)量的方案，并思考其合理性.2.本問(wèn)中沒(méi)有考慮員工中途吃飯、休息以及不同時(shí)間段超市應(yīng)支付不同工資等因素．若員工的月基本工資為1000元，在晚上22：00-早上6：00這兩個(gè)時(shí)間段超市要多支付20（元/人、時(shí)段）的夜班費(fèi).問(wèn)應(yīng)如何招聘服務(wù)人員既能滿足日常業(yè)務(wù)需求又能使公司所支付的工資總數(shù)最少．

問(wèn)題11【人員配置模型

】

平安自行車零部件廠生產(chǎn)組裝自行車所需的座墊、腳踏、車軸和車筐四種零部件，一車間有4個(gè)技術(shù)工人，每個(gè)工人加工各個(gè)部件所用時(shí)間見(jiàn)表6-11．問(wèn)應(yīng)如何安排加工任務(wù)使加工總時(shí)間最少．表6-11部件1（座墊）部件2（腳踏）部件3（車軸）部件4（車筐）A10978B5877C5465D2345一、模型假設(shè)與符號(hào)說(shuō)明1．假設(shè)部件加工過(guò)程中每位工人的加工時(shí)間不受其它因素影響．2．假設(shè)加工過(guò)程中，每個(gè)工人只能加工一種部件．3.設(shè)hij表示第

i加工部件j所用的時(shí)間．設(shè)0-1變量二、模型的分析與建立該問(wèn)題要求合理安排四人的加工任務(wù)，使得加工總時(shí)間最少．

目標(biāo)：加工零件所花費(fèi)的總時(shí)間最少．加工零件所花費(fèi)的總時(shí)間為約束條件：

1．受每個(gè)人只能加工一種零件的限制：

2．受一個(gè)零件只能由一人完成的限制：

綜上分析，得到該問(wèn)題的整數(shù)規(guī)劃模型三、模型求解x=binvar(4,4);h=[10978587754652345];a=ones(4,1);f=sum(sum(h.*x));F=set((sum(x))'==a)+set((sum(x'))'==a);solvesdp(F,f)double(f)double(x)據(jù)此建立此問(wèn)題的m文件fun6_11.m

運(yùn)行結(jié)果如下：

ans=21ans=0001001001001000由此可知，第一人生產(chǎn)車筐，第二人生產(chǎn)車軸，第三人生產(chǎn)腳踏，第四人生產(chǎn)座墊所用總工時(shí)最少，最少時(shí)間為21小時(shí)．

一般地，設(shè)有工作m件，人員n個(gè)，且一人只能做一件工作，第i人做第j件工作的時(shí)間（或費(fèi)用）為cij,問(wèn)如何分派這些人員使總時(shí)間（或總費(fèi)用）最少．這里，可設(shè)則建立0-1規(guī)劃模型如下：6.3非線性規(guī)劃模型問(wèn)題13【季度交貨模型】

彩虹電視機(jī)廠每季度向陽(yáng)光電器商行提供彩電.按合同約定，其交貨數(shù)量和日期分別為：第一季度末交40臺(tái)，第二季末交60臺(tái)，第三季末交80臺(tái)．工廠每季度的最大生產(chǎn)能力為100臺(tái)，每季度的生產(chǎn)費(fèi)用為f(x)=50x+0.2x2（元），其中x（臺(tái)）為該季度生產(chǎn)彩電的數(shù)量．若工廠生產(chǎn)太多彩電，則多余的彩電可轉(zhuǎn)到下季度向用戶交貨，但工廠需要支付存貯費(fèi)，每臺(tái)彩電每季度的存貯費(fèi)為4元．問(wèn)該廠每季度生產(chǎn)多少臺(tái)彩電，才能既滿足交貨合同，又使工廠所花費(fèi)的費(fèi)用最少．一、模型假設(shè)與變量說(shuō)明1．假設(shè)第一季度開(kāi)始時(shí)無(wú)彩電庫(kù)存．2．假設(shè)不考慮彩電運(yùn)送費(fèi)等其他費(fèi)用．3.假設(shè)工廠只考慮前三季度的生產(chǎn).4.設(shè)xi（臺(tái)）為工廠第i季度生產(chǎn)彩電的數(shù)量，生產(chǎn)費(fèi)用為C1（元），存貯費(fèi)用為C2（元），總費(fèi)用為C（元）．二、模型的分析與建立

該問(wèn)題是要確定工廠每季度彩電的生產(chǎn)數(shù)量，在滿足商場(chǎng)每季度對(duì)產(chǎn)品需求量的前提下，使得生產(chǎn)的總成本（包括存貯費(fèi)）最低．目標(biāo)：總費(fèi)用最少．總費(fèi)用為

其中約束條件：

1．受第一季度交貨數(shù)量的限制：2．受第二季度交貨數(shù)量的限制：3．受第三季度交貨數(shù)量的限制：4．受每季度生產(chǎn)能力限制：綜上分析，得到該問(wèn)題的非線性規(guī)劃模型三、模型求解x=intvar(1,3);f=sum(0.2*(x.^2)')+sum(50*x)+[1284]*x'-1280;A=[100;110;111];b=[40100180];F=set(0<=x<=100);F=F+(A*x'>=b');solvesdp(F,f);double(f)double(x)據(jù)此建立此問(wèn)題的m文件fun6_13.m

運(yùn)行結(jié)果如下：

ans=11280ans=506070由此可知，工廠第一、二、三季度分別生產(chǎn)50，60，70臺(tái)彩電就既滿足市場(chǎng)需求，又使得總費(fèi)用最低，最低費(fèi)用為11280元．拓展思考

請(qǐng)調(diào)研企業(yè)的生產(chǎn)計(jì)劃的制訂，他們考慮了哪些因素，如果把這些因素并入到模型中，應(yīng)對(duì)模型進(jìn)行怎樣的改進(jìn)．問(wèn)題14【資源配置模型】

冬季臨近，為保證全國(guó)居民用電需求，某煤礦計(jì)劃向華中、華東、華北地區(qū)配送電煤1000萬(wàn)噸．近三年來(lái)各地冬季電煤實(shí)際需求量見(jiàn)表6-12．請(qǐng)據(jù)此制定合理的電煤運(yùn)送方案，最大限度地滿足各地居民生活用電的需求．

各地需求量（萬(wàn)噸）年份華中地區(qū)華東地區(qū)華北地區(qū)總需求量2007200250350800200825030035090020092503504001000表6-12一、模型假設(shè)與變量說(shuō)明1．假設(shè)華中、華東、華北三地2010年的用電量與往幾年基本持平，沒(méi)有明顯的增長(zhǎng)或減少．2．假設(shè)近幾年煤礦向華中、華東、華北三地配送電煤的比例不變．3.假設(shè)前三年煤礦向華中、華東、華北三地配送電煤的量能滿足當(dāng)?shù)鼐用裆钣秒姷男枰?.設(shè)向華中、華東、華北各地配送電煤比例分別為

，近三年華中、華東、華北三個(gè)地區(qū)電煤實(shí)際需求量分別為mi萬(wàn)噸，ei萬(wàn)噸，ni萬(wàn)噸，

運(yùn)送總量為

Ti萬(wàn)噸，i=1,2,3二、模型的分析與建立該問(wèn)題是已知前三年電煤配送的情況下，以前3年三地實(shí)際需求量為依據(jù)，確定2010年的運(yùn)送方案．

目標(biāo)：使配送比例與近三年各地實(shí)際需求量相差的平方和最?。繕?biāo)函數(shù)：配送比例與近三年與各地實(shí)際需求量之差為約束條件：

1．受配送比例的限制：

2．3年實(shí)際需求量的限制：

綜上分析，得到該問(wèn)題的非線性規(guī)劃模型三、模型求解x=sdpvar(1,3);C1=[200250350];C2=[250300350];C3=[250350400];T=[8009001000];f=sum((C1-T.*x).^2)+sum((C2-T.*x).^2)+sum((C3-T.*x).^2);F=0<=x<=1;F=F+set(sum(x)==1);solvesdp(F,f);double(f)double(x)

據(jù)此建立此問(wèn)題的m文件fun6_13.m

運(yùn)行結(jié)果如下：

ans=8.3882e+003ans=0.29510.33600.3689由此可知，根據(jù)以往的經(jīng)驗(yàn)，為了盡可能地避免意外發(fā)生，向華中、華東、華北運(yùn)送的電煤量分別占總量的29.51%、33.60%、36.86%．問(wèn)題15【公路設(shè)計(jì)模型】

長(zhǎng)壽鄉(xiāng)盛產(chǎn)柑橘，但由于道路交通不便，致使每年大量柑橘無(wú)法銷往外地而腐爛．于是長(zhǎng)壽市政府決定修建一條通往長(zhǎng)壽鄉(xiāng)的公路．長(zhǎng)壽市與長(zhǎng)壽鄉(xiāng)兩地水平距離為80km，與長(zhǎng)壽鄉(xiāng)垂直距離30km處有一條河流流經(jīng)長(zhǎng)壽市，如圖6-1所示．單位貨物公路運(yùn)輸費(fèi)用與水路運(yùn)輸費(fèi)用之比為5：2．問(wèn)應(yīng)如何設(shè)計(jì)該公路使運(yùn)輸費(fèi)用最低．圖6-1一、模型假設(shè)與變量說(shuō)明1.不考慮地形因素對(duì)路線的影響，也就是可以修建直線型公路．2.假設(shè)河流流動(dòng)路線筆直．3.假設(shè)在河流流經(jīng)之處均可修建裝運(yùn)碼頭．4.不考慮貨物裝卸、搬運(yùn)等費(fèi)用．5.設(shè)修建公路的長(zhǎng)度為x1km，可利用水路運(yùn)輸?shù)拈L(zhǎng)度為x2km，單位貨物水路運(yùn)輸費(fèi)用為2k（k為常數(shù)）．二、模型的分析與建立該問(wèn)題是要求設(shè)計(jì)交通路線，使總運(yùn)費(fèi)（公路運(yùn)費(fèi)和水路運(yùn)費(fèi)之和）最低．由問(wèn)題可知，單位貨物公路運(yùn)輸費(fèi)用為5k.目標(biāo)：使配送比例與近三年各地實(shí)際需求量相差的平方和最?。繕?biāo)函數(shù)：配送比例與近三年與各地實(shí)際需求量之差為約束條件：

如圖6-1所示，受兩地及河流幾何關(guān)系的限制，有綜上分析，得到該問(wèn)題的非線性規(guī)劃模型三、模型求解x=sdpvar(1,2);C=[5-2];f=C*x'+160;*令x’(2)=80-x(2)F=set(1<=x<=inf);F=F+set((x(1))^2-(x(2))^2==900)+set(0<=x(2)<=80);solvesdp(F,f);double(f)double(x)據(jù)此建立此問(wèn)題的m文件fun6_13.m

運(yùn)行結(jié)果如下：

ans=297.4773ans=32.732713.0931由此可知，修建公路32.73km，利用水路80-13.09=66.91km使得將來(lái)運(yùn)輸成本最低，為297.48k元．6.4多目標(biāo)規(guī)劃模型問(wèn)題16【玩具生產(chǎn)安排模型】樂(lè)樂(lè)玩具廠生產(chǎn)兩種玩具，玩具車的利潤(rùn)為10元/個(gè)，洋娃娃的利潤(rùn)為8元/個(gè).玩具車每個(gè)需要3h裝配時(shí)間，而洋娃娃需要2h．每周有效總裝配時(shí)間為120h．工廠允許加班，但加班生產(chǎn)出來(lái)的每個(gè)玩具利潤(rùn)要減少1元．兩種玩具每周的需求量均為30個(gè)．問(wèn)應(yīng)如何安排生產(chǎn)才能使工廠的總利潤(rùn)最大并且使得工人盡可能少加班．6.3.1生產(chǎn)經(jīng)營(yíng)與消費(fèi)中的問(wèn)題一、模型假設(shè)與變量說(shuō)明1．假設(shè)每周生產(chǎn)需求量?jī)?nèi)的產(chǎn)品能全部售完．2．不考慮生產(chǎn)過(guò)程中其他各種因素對(duì)加工時(shí)間的影響．3.設(shè)

x1，x2分別為每周正常時(shí)間內(nèi)生產(chǎn)的玩具車和洋娃娃的數(shù)量，

x3，x4分別為每周加班時(shí)間生產(chǎn)的玩具車和洋娃娃的數(shù)量．二、模型的分析與建立該問(wèn)題要求在完成每周兩種玩具生產(chǎn)任務(wù)的前提下，對(duì)兩種玩具的生產(chǎn)數(shù)量作統(tǒng)籌安排，使得滿足以下兩個(gè)條件：獲得的利潤(rùn)最大且加班時(shí)間盡量少．

目標(biāo)：總利潤(rùn)最大且加班時(shí)間盡量少．其中總利潤(rùn)為

工人加班時(shí)間為約束條件：

1．滿足每周各種產(chǎn)品需求量的要求：2．受每周有效總工時(shí)的限制：

綜上分析，得到該問(wèn)題的多目標(biāo)規(guī)劃模型三、模型求解x=intvar(1,4);a=[10897];f=a*x';F=set(0<=x<=inf);F=F+set(x(1)+x(3)==30)+set(x(2)+x(4)==30)+set(3*x(1)+2*x(2)<=120);solvesdp(F