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

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

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

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

6.1.1生產(chǎn)活動問題

6.1.2運輸問題

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

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

．2.假設(shè)豆腐售價無波動

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

x1kg和x2kg，可獲得R元收益

．二、模型的分析與建立

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

約束條件：

1．受一級黃豆數(shù)量的限制：2．受二級黃豆數(shù)量的限制：綜上分析，得到該問題的線性規(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ù)此建立此問題的m文件fun6_1.m

運行結(jié)果如下：

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

拓展思考

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

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

a12

a1n

b1B2a21

a22

a2n

b2

……………Bmam1

am2

amn

bm

單位利潤c1

c2cn

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

則模型為

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

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

xij，每噸蔬菜運費為cij，其中i=1,2,3表示東、南、西蔬菜基地，

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

目標(biāo)：運送蔬菜總的費用最?。渲羞\送蔬菜的總費用為

約束條件：

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

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

綜上分析，得到該問題的線性規(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ù)此建立此問題的m文件fun6_3.m

運行結(jié)果如下：

ans=204100ans=200000001100014000120018000由此可以得到蔬菜運輸費用最省的運送方案，見表6-4．

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

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

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

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

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

c12

c1n

a1A2c21

c22

c2n

a2

……………Amcm1

cm2

cmn

am

需求量b1

b2bn

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

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

1．受2010年年初貸款數(shù)額限制：2．受2011年年初貸款數(shù)額限制：3．受2012年年初貸款數(shù)額限制：4．受2013年年初貸款數(shù)額限制：綜上分析，得到該問題的線性規(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ù)此建立此問題的m文件fun6_5.m

運行結(jié)果如下：

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

6.2.1生產(chǎn)活動問題

6.2.2人力資源管理問題

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

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

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

約束條件：

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

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

綜上分析，得到該問題的整數(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ù)此建立此問題的m文件fun6_7.m

運行結(jié)果如下：

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

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

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

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

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

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

3．受司機數(shù)量限制：4．受每天運輸任務(wù)的限制：綜上分析，得到該問題的整數(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ù)此建立此問題的m文件fun6_8.m

運行結(jié)果如下：

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

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

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

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

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

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

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

第一季度末過剩車輛在第二季度的存貯費為

第二季度末過剩車輛在第三季度的存貯費為

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

約束條件：

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

4．受四個季度總需求量的限制：5．受正常工作時間內(nèi)產(chǎn)量的限制：6．受加班時間產(chǎ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ù)此建立此問題的m文件fun6_9.m

運行結(jié)果如下：

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

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

6.2.2人力資源管理問題

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

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

xi為第

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

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

約束條件：

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

綜上分析，得到該問題的整數(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ù)此建立此問題的m文件fun6_10.m

運行結(jié)果如下：

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

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

問題11【人員配置模型

】

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

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

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

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

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

綜上分析，得到該問題的整數(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ù)此建立此問題的m文件fun6_11.m

運行結(jié)果如下：

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

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

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

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

其中約束條件：

1．受第一季度交貨數(shù)量的限制：2．受第二季度交貨數(shù)量的限制：3．受第三季度交貨數(shù)量的限制：4．受每季度生產(chǎ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ù)此建立此問題的m文件fun6_13.m

運行結(jié)果如下：

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

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

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

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

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

運送總量為

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

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

1．受配送比例的限制：

2．3年實際需求量的限制：

綜上分析，得到該問題的非線性規(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ù)此建立此問題的m文件fun6_13.m

運行結(jié)果如下：

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

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

如圖6-1所示，受兩地及河流幾何關(guā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ù)此建立此問題的m文件fun6_13.m

運行結(jié)果如下：

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

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

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

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

工人加班時間為約束條件：

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

綜上分析，得到該問題的多目標(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