第五章数学规划模型

•数学规划，是指在一定的条件下运用特定的方法（数学的方法）达到最佳的效果，即求各式各样的条件极值问题.

•数学规划是运筹学和管理科学中应用极广泛的分支，也是解决优化问题的一个非常有用的工具.第五章数学规划方法建模一、数学规划模型的数学描述下的最大值或最小值，其中决策变量目标函数将一个优化问题用数学式子来描述，即求函数在约束条件可行域5.1数学规划概述

“受约束于”之意．简单记为以上数学模型称为数学规划模型．二、数学规划模型的分类1.线性规划（LP）

目标函数和所有的约束条件都是决策变量的线性函数．2.非线性规划（NLP）目标函数和约束条件中，至少有一个非线性函数．3.整数规划（IP）决策变量有部分或全部取整数．三、建立数学规划模型的一般步骤1.确定决策变量和目标变量；2.确定目标函数的表达式；3.寻找约束条件．重点在模型的建立．通常称

为决策变量，

为价值系数，

为消耗系数,为资源限制系数。目标函数

满足约束条件min(max)5.2线性规划模型

线性规划的数学模型可以表示为下列简洁的形式：线性规划的数学模型还可以表示为下列矩阵形式：,,线性规划问题矩阵形式：

其中

建立线性规划模型的过程可以分为四个步骤：(1)设立决策变量；(2)明确约束条件并用决策变量的线性等式或不等式表示；(3)用决策变量的线性函数表示目标，并确定是求极大（Max）还是极小（Min）；(4)根据决策变量的物理性质研究变量是否有非负性.假定一个成年人每天需要从食物中获取3000卡的热量、55克蛋白质和800毫克的钙.如果市场上只有四种食品可供选择，它们每公斤所含热量和营养成分以及市场价格见下页表.问如何选择才能在满足营养的前提下使购买食品的费用最小.例1营养配餐问题序号食品名称热量(卡)蛋白质(g)钙(mg)价格(元)1猪肉100050400142鸡蛋8006020063大米10002030034白菜200105002各种食物的营养成分表

解:设xj为第j种食品每天的购入量，则配餐问题的线性规划模型如下：Min

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

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

xi0i=1,...,4

实用的配餐问题要比上例复杂的多，可包括几十甚至上百种原料，几十种营养配方.例如医院的营养配餐和养殖业中的配合饲料问题.

要从甲地调出物质2000吨,从乙地调出物质1100吨,分别供给A地1700吨,B地1100吨,C地200吨和D地100吨,已知每吨运费如表所示,试建立一个使运费达到最小的调拨计划.单位路程运费表销地15375151乙1572521甲DCBA产地例2运输问题

分析设从第个产地到第个销地的运输量为运输成本为则问题的目标函数为由于从第一个产地调出的物质的总和为第一个产地的产量,即有同理,有对称地,对销地而言,有关系由此得到该问题的数学模型注该问题又称为运输问题.运输问题的一般形式可写成其中是第个产地的产量,是第个销地的需求量.在上面的关系中,有相应的运输问题称为产销平衡的运输问题.

某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表，若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费0.2万元.现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低.试建立线性规划模型.季度

j生产能力（aj）生产成本（dj）需求量（bj）13015．02024014．02032015．33041014．810例3生产与库存问题

解设工厂第j季度生产产品xj

吨需求约束：第一季度末需交货20吨，x1≥20第二季度末需交货20吨，x1-20+x2≥20这是上季末交货后积余第三季度末需交货30吨，x1+x2-40+x3≥30第四季度末需交货10吨，x1+x2+x3-70

+x4=10生产能力约束：0≤xj≤aj

j=1,2,3,4季度

j生产能力（aj）生产成本（dj）需求量（bj）13015．02024014．02032015．33041014．810生产、存储费用：第一季度：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.某部门在今后五年内考虑下列项目投资，已知：

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

项目B第三年年初需要投资，到第五年末回收本利125％，但规定最大投资额不超过4万元；

项目C第二年年初需要投资，到第五年末回收本利140％，但规定最大投资额不超过3万元；

项目D五年内每年年初可购买公债，当年末归还，并加利息6％．

该部门现有资金10万元，问如何确定给这些项目的投资额，使到第五年末拥有资金的本利总额最大？例4连续投资问题解：（1）决策变量设分别表示第年年初给项目的投资额，根据给定的条件将变量列表如下：

12345ABCD(2)约束条件投资额应等于手中拥有的资金，由于项目D每年都可以投资，并且当年末就能回收本息，所以该部门每年应把资金全部投出去，手中不应该有滞留资金，因此：第一年：年初拥有资金10万元，所以有第二年：因为第一年给项目A的投资到第二年末才能回收，因此在第二年初拥有资金额仅为项目D在第一年回收的本息．于是第二年年初的投资分配为：第三年：第三年初的资金额是从项目A第一年投资和项目D第二年初投资中回收的本利总和，于是第三年的投资分配是：第四年：同以上分析得第五年：此外，还有对项目的规定：(3)目标函数(第五年末拥有的资金本利总额)(4)数学模型

某人有一笔50万元的资金可用于长期投资,可供选择的投资包括购买国库券

、债券、房地产、股票或银行储蓄等．他希望投资组合的平均年限不超过5年，平均的期望收益率不低于13%，风险系数不超过4，收益的增长潜力不低于10%．在满足上述要求的前提应如何选择投资组合才能使平均收益率最高．例5证券投资组合优化

投资投资期 年收益风险增长潜方式限(年)率(％)系数力(％)国库券311 1 0债券 10 15 3 15房地产 6 25 8 30股票 2 20 6 20短期存款1 10 1 5长期存款5 12 2 10现金存款0 3 0 0决策变量：各种投资方式站总投资的比例；目标函数：平均投资收益最大；约束方程：满足各种指标要求平均投资年限不超过5年平均的期望收益率不低于13%风险系数不超过4收益的增长潜力不低于15%证券组合优化模型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

问题某机器制造厂专为拖拉机厂配套生产柴油机.今年头四个月收到的订单数量分别为3000，4500，3500，5000台柴油机.该厂正常生产每月可生产柴油机3000台，利用加班还可生产1500台.正常生产成本为每台5000元，加班生产还要追加1500元成本，库存成本为每台每月200元．该厂如何组织生产才能使生产成本最低．例6多周期动态生产计划与库存问题模型参数:

ci为第i月正常生产柴油机的成本；

ki为第i月加班生产柴油机的成本;

hi为第i月柴油机的库存成本;

di为第i月柴油机的需求; Ei为第i月柴油机的正常生产能力； Fi为第i月柴油机的加班生产能力．决策变量：xi为第i月正常生产的柴油机数；yi为第i月加班生产的柴油机数；zi为第i月初柴油机的库存数．数学模型：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：企业根据预测知道上半年市场对该企业产品的需求变化较大（见下表）：月份123456

需求600025005000350055006000企业目前有100名工人，每人每月可生产40件产品，工人平均工资每月800元，企业可以通过以下方法调节生产：

利用加班：加班需付加倍工资，每人每月利用加班生产的产品不能超过10件。利用库存：每件产品库存费用为10元/月。临时增聘或解雇工人：新聘工人培训费为1000元，解雇工人的解聘费为600元。每月新聘工人数量不能超过10人。企业目前有库存500件，希望六月底的库存不低于700件，其他月份应保持不少于200件的安全库存，企业应如何组织生产。变量设置：

xi：第i月在岗的工人数；

yi

：第i月新聘的工人数；

zi

：第i月解聘的工人数；

ki

：产品在第i月期末的库存数量；

ui

：第i月正常生产的产品数量；

vi：第i月加班生产的产品数量；约束条件：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目标函数：生产和库存费用最小minz=i(800xi+1000yi+600zi+10ki+40vi)2）每月生产的平衡约束

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）正常生产限制约束： ui-40xi

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

0

u2-40x2

0 u3-40x3

0 u4-40x4

0 u5-40x5

0 u6-40x6

04）加班生产限制约束： vi-10xi

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

0

v2-10x2

0 v3-10x3

0 v4-10x4

0 v5-10x5

0 v6-10x6

05）变量的界约束和非负约束： 安全库存约束：ki

200i=2,…,5 k0

=500,k6

700 新聘人数约束：yi

10i=1,…,6 在岗初始人数：x0

=100 变量非负约束：

xi,yi,zi,ki,ui0i=1,…,6；某公司在下一年度的1～4月份的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于下表1。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表2。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租用期限不同的合同。试确定该公司签订租借合同的最优决策，目的是使所租借费用最少。例8（租借合同的最优决策）月份1234所需仓库面积15102012表1表2合同租借期限

1个月2个月3个月4个月合同期内的租费2800450060007300单位：100m2单位；元/100m2解：设表示公司在第i(i=1,2,3,4)月初签订的租期为j

(j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。ⅠⅡⅢⅣⅤ∑≥15∑≥10∑≥20∑≥12经过上面的讨论，得到下面的LP模型：例9(产品配套问题）假定一个工厂的甲、乙、丙三个车间生产同一个产品，每件产品包括4个A零件，和3个B零件。这两种零件由两种不同的原材料制成，而这两种原材料的现有数额分别为100克和200克。每个生产班的原材料需要量和零件产量如下表所示。问这三个车间各应开多少班才能使这种产品的配套数达到最大约束条件为：三个车间共生产A零件：三个车间共生产B零件非线性要求：目标函数：目标函数Z=x4线性数学模型：线性规划问题某部门现有资金200万元，今后五年内考虑给以下的项目投资.已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元.

思考题据测定每万元每次投资的风险指数如下表：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？

b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？分别建立数学模型．

线性规划问题中,对决策变量只限于不能取负值的连续型数值．而在许多实际问题中，决策变量只有非负整数才有意义．对求整数最优解的问题，称为整数规划(IntegerProgramming)(简记为IP)．又称约束条件和函数均为线性的IP为整数线性规划(IntegerLinearProgramming)(简记为ILP)．7.4整数规划模型

线性规划问题中,对决策变量只限于不能取负值的连续型数值．而在许多实际问题中，决策变量只有非负整数才有意义．对求整数最优解的问题，称为整数规划(IntegerProgramming)(简记为IP)．又称约束条件和函数均为线性的IP为整数线性规划(IntegerLinearProgramming)(简记为ILP)．5.3整数规划模型

在整数规划中，处理“可供选择条件”的问题时，常常引入0-1变量．此时的整数规划也称为0-1规划．整数线性规划模型的一般形式问题：如何下料最节省?原料钢管:每根19米4米50根6米20根8米15根客户需求节省的标准是什么？某金属加工厂有长度为19米的圆钢料多根，某客户要订购4米，6米，8米的棒料各50根，20根，15根，问工厂如何切割最省？

整数线性规划模型的建立例1下料问题按照客户需要在一根原料钢管上安排切割的一种组合。

切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料应小于客户需要钢管的最小尺寸余料3米8米1根8米1根为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？合理切割模式2.所用原料钢管总根数最少模式

4米钢管根数6米钢管根数8米钢管根数余料(米)14003231013201341203511116030170023两种标准1.原料钢管剩余总余量最小xi~按第i种模式切割的原料钢管根数(i=1,2,…7)约束满足需求决策变量

目标1（总余量）按模式2切割12根,按模式5切割15根，余料27米

模式4米根数6米根数8米根数余料14003231013201341203511116030170023需求502015最优解：x2=12,x5=15,其余为0；最优值：27。整数约束：xi为整数当余料没有用处时，通常以总根数最少为目标目标2（总根数）约束条件不变最优解：x2=15,x5=5,x7=5,其余为0；最优值：25。xi为整数按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米虽余料增加8米，但减少了2根与目标1的结果“共切割27根，余料27米”相比时间所需售货员人数星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人某中型百货商场，对售货人员的需求经分析如下所示：为保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作的需要，又使配备的售货人员的人数最少？解例2人员安排问题时间所需售货员人数星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人约束条件:星期日售货员人数要求:星期一售货员人数要求:星期二售货员人数要求:星期三售货员人数要求:星期四售货员人数要求:星期五售货员人数要求:星期六售货员人数要求:数学模型:非负约束:数学模型:解得:某单位有5个拟选择的投资项目，其所需投资额与期望收益如下表．由于各项目之间有一定联系，A、C、E之间必须选择一项且仅需选择一项；B和D之间需选择也仅需选择一项；又由于C和D两项目密切相关，C的实施必须以D的实施为前提条件，该单位共筹资金15万元，问应该选择哪些项目投资，使期望收益最大？项目所需投资额（万元）期望收益（万元）A610B48C27D46E59例3投资项目选择问题解：决策变量：设目标函数：期望收益最大约束条件：投资额限制条件6x1+4x2+2x3+4x4+5x515项目A、C、E之间必须且只需选择一项：x1+x3+x5=1项目C的实施要以项目D的实施为前提条件：x3

x4项目B、D之间必须且只需选择一项：x2+x4=1归纳起来，其数学模型为：例4

某校篮球队准备从以下队员中选拔3名为正式队员，并使平均身高尽可能高，这6名预备队员情况如下表所示。预备队员号码身高位置

大张1193中锋大李2191中锋小王3187前卫小赵4186前卫小田5180后卫小周6185后卫队员的挑选要满足下列条件：至少补充一名后卫队员；大李或小田中间只能入选一名；最多补充一名中锋；如果大李或小赵入选，小周就不能入选。试建立此问题的数学模型。解:则该问题的数学模型为:预备队员号码身高位置

大张1193中锋大李2191中锋小王3187前卫小赵