第2讲数学规划模型的建立1

数学规划模型I引言

一个复杂系统往往要受诸多因素的影响，而这些因素又要受到一定的限制。最优化就是在一定约束下，如何选取这些因素的值，使某项（或某些）指标达到最优的一门学科。它包括数学规划、决策分析、最优控制等等。最优化方法在经济、军事、科技等领域内都有广泛的应用。例1把一根直径为d

的圆木锯成矩形横梁。已知横梁强度z与宽度x

成正比，与高度y

的平方成正比。求宽、高各为多少时强度最大？该问题的数学模型为：用微分法容易求出其解。数学规划模型格式：maxs.t.例2施工点j的坐标为对某材料的需求量为第i个料场的容量为求料场的位置及各料场向各施工点的供应量，使材料运输的总吨公里最小。解设各料场到各施工点的距离为直线距离，且各施工点可在不同料场取料。则总吨公里数需求限制容量限制非负限制mins.t.学习这一部分需注意的地方：对给定的实际问题，如何作合理的假设，并建立模型。如何处理分段函数、矛盾约束等问题。2.怎样将一类模型化为另一类模型，易于求解。3.同一问题可建立不同模型第二个问题不便用微分法求解，可用数学规划方法求解。II数学规划模型的建立数学规划模型的一般形式：例如：maxs.t.若能写出描述S的数学式子，则可直接写出。这里目标函数可行域可行解决策变量描述S的数学式子约束条件S问题可行问题不可行最优解最优目标值几个概念：特别：(或max)或线性规划模型或等约束注：M是常数与有相同的最优解1.2.与有相同的最优解另外：1.取整数，称模型为整数规划模型2.中部分取整数，称模型为混合整数规划模型3.只取0或1两个值，称为0—1规划模型目标函数或约束条件是非线性的，称为非线性规划模型若目标函数只有一个，称为单目标规划模型；若目标函数不只一个，称为多目标规划模型。产地销地运价例1求使总运费最少的调运方案。试建模。产量需求量42一、运输问题解则产销平衡注：若产大于销，则若产小于销，则线性规划模型

重要结论：当供应量与需求量均为整数时，模型的最优解是整数解。例2

自来水输送问题某市有甲、乙、丙、丁四个居民区，自来水由A、B、C由三个水库供应。四个区每天必须的基本生活用水分别为30、70、10、10千吨，但三个水库每天最多只能分别供应50、60、50千吨自来水。由于地理位置的差别，自来水公司从各水库向各区送水所付出的引水管理费不同（如表，其中C水库与丁区间无输水管道），其它管理费均为450元/千吨。各区用户每千吨收费900元。此外，各区用户都向公司申请了额外用水量，分别为每天50、70、20、40千吨。问公司应如何分配供水量，才能获利最多？引水管理费(元/千吨)将有关数据整理列表：水库居民区供应量生活用水额外用水成水输本问题分析：…可看成是“产小于销”的运输问题。解设xij

分别表示水库A,B,C(i=1,2,3)向居民区甲,乙,丙,丁(j=1,2,3,4)的供水量。其中X34=0.模型建立由题意目标函数为：可转化为：供给限制需求限制一般问题中：供给限制用“”需求限制用“”“”引水管理费因160千吨水须全部输出注：为了增加供水，公司考虑改造水库，使三个水库的供水能力提高一倍，问模型将作何改动？分析：由于总供水能力为320千吨，总需求量为300千吨，水不能全部卖出，所以不能将获利最多转化为引水管理费最少。须算出每千吨净利润。每千吨净利润＝用户交的900元－其它管理费450元－引水管理费净利润(元/千吨)模型改为：其它同前例3最大流问题①②③④⑤⑥⑦图中弧上的数字表示每小时两结点沿箭头方向的最大车流量，求①到⑦每小时的最大车流量。二、网络（规划）问题设v为从出发的车流量，

为到的车流量，则流量守恒条件弧容量限制去掉去掉若不设v,则模型有四处需修改如果源、汇不止一个时，建模方法类似。可增加一个虚拟源、虚拟汇化成单源单汇的问题。

图中的结点称为源（发点），结点称为汇（收点）。图是单源单汇的情形。例42求从流出，到的最大流量。解设为到的流量，

、为流入、的量，

、、为流入、、的量。例5

设有工作件，人员个，且一人做一件工作，第人作第件工作的时间（或费用）为，问：如何分派可使总时间（或总费用）最少。解本题需确定：第人做或不做第件工作，这是定性变量，首先将其定量化。设0—1规划模型则注：若表示效益，则目标函数应极大化问：各人员类不止1人，各工作类不止1件工作，决策变量为何？若人数“>”工作件数三、分派问题四、生产活动问题(分段函数、矛盾约束等的处理方法)资源产品单耗资源量单位利润例6问如何安排生产使总利润最大。解设表示第种产品的产量，则资源分配问题分段函数问题例中＝单位收益－单位成本（可变成本）若还要考虑固定成本则第j种产品的利润为：于是引入0—1变量：设Lj

是xj的上界，则模型改写为：混合整数规划模型等价性：（1）由Z的极大化（2）由注：将目标函数变成则为非线性的。若不考虑固定成本，则不引入0-1变量。

更复杂的分段函数的处理方法*设B1是某种原料（单位：吨），还可以从市场上购买到不超过1500吨的原料。若购买量不超过500吨，其价格为10千元/吨；购买量多于500吨但不超过1000吨时，超过500吨的部分8千元/吨；购买量超过1000吨时，超过1000吨的部分6千元/吨。问怎样安排生产和采购？增设x为采购量，则可得采购支出（千元）：这时，目标函数为:处理法1：设三种价格的采购量分别为：则目标函数为：约束条件增加：只有当

x1=500时，才能以每吨8千元的价格购买x2(>0)非线性规划模型！处理法1：可用端点的凸组合来表示线段上的值，如：为了统一表示，引入0－1变量则且至多两个相邻的i取非零值可得混合整数规划模型产品种类限制问题（不考虑固定成本）n种产品中只生产其中k种设则要求产量不小于80单位80矛盾约束问题设、为机器1、2的可用工时（资源），

种产品只在一台机器上加工，则以下两个约束条件是矛盾的，不能同时出现在一个模型中。若引入0—1变量：设M是充分大的常数，则两个矛盾约束可统一在一个模型中：一般，若m种资源中只用其中k种资源，则令约束条件改为：例7

生产存储问题（多阶段问题）某公司生产一种产品，最大生产能力为100单位，第月的单位存储费为元，预定的销售量和单位成本如表。求使生产成本与存储费之和最低的生产计划。解先作合理假设•1月初无库存；•4月底卖完；•当月生产的不入库；•库存量无限制。假设：月份单位成本(元)销售量(件)模型一且为整数，第j+1月初的库存量整数规划模型设为第月的产量，为单位存储费，则模型二若设为第月初的库存量，则且为整数，增加了决策变量，但模型简洁了。本问题还可建立动态规划模型几点说明：1.增加投资扩大生产能力若每投资k元可增加一个单位的生产能力。设表示第月的投资，则第月的产量限制条件变为：第月前的投资在第月仍起作用，生产投资问题。2.均衡生产问题前例中的最优月产量为：月初库存量为：为使生产尽量均衡，可增加相继两个月产量差的限制：同时希望非负变量、越小越好。则目标函数可提为：其中a

为第月比第月增加一个产品要支付的费用，b

为减少一个产品支付的费用，c

为库存费。根据要求还可提为：或不希望减少不希望增加＃例8

（P.7例1.8）求生产、存储、维修计划将有关数据整理列表(同例1.6)：机床单耗产品台数月台时单位利润月台时＝台数小时天数。1344＝41621如一台机床维修一次需160(台时)＝10(天)16(小时)19假定：•没有轮到维修的和维修后的机床在使用期间能正常工作；•维修一台机床是在某月内完成，不会跨入下一月。设

—第月初、第种产品的库存量，

—第月、第种产品的产量，

—第月、第种机床的维修量。需求限制资源限制维修限制•第月维修哪几台机床可由人安排，只安排未维修的；例9（下料问题）某厂要做100套钢架，每套由长为2.9米，2.1米和1.5米的圆钢各一根组成。已知原料长7.4米。问如何下料使原料最省。试建模。问题分析：“最节省”可以是“所用原料根数最少”，也可以是“余料最少”。基于前者建模。一根原料钢管有不同的切割组合…..。找出每一种组合用去多少根原料钢管。所以首先列出所有可能组合即“模式”。解将8种下料方案列表:方案根数长度合计6.06.67.26.37.46.57.17.3余料1.40.80.21.100.90.30.1需求量若希望余料最少，则•余料超过1.5米•约束条件取“＝100”•设需根原料，第根下第种圆钢根，n是决策变量，而线性规划模型中是定数！该模型不易计算！以下几种作法欠妥：五、选址问题客户拟定的设施地址（1）离散型选址问题（2）连续型选址问题设施的地址未拟定，可选在所论区域（很大）的任何地方。问题：第个设施是否需修建？若要修建，应为周围哪些客户服务？选址—分配问题例10（离散型）施工点j对某材料的需求量为第i个料场的容量为的单位运费

(元/吨).求使总费用最少的场址。可基于两种考虑建模：2°施工点只能在某一料场获取全部所需材料。1°施工点可在任何料场获取部分材料，以满足需求；建场费为di

元,解1°假定：•任何施工点到任何料场的道路是通的；•施工点可在任何料场获取部分材料，以满足需求；拟定m个地方建料场，为地址到施工点一个大型工程有n个施工点，则总费用需求限制容量限制非负限制mins.t.混合整数规划模型2°假定：•任何施工点到任何料场的道路是通的；•施工点只能在某一料场获取全部所需材料。设则总费用需求限制容量限制mins.t.非负限制0—1规划模型由于区域很大，所以施工点到料场间的距离视为直线距离例11（连续型）设工程所涉及的区域很大，第j个施工点的坐标为：单位运费为c(元/吨/公里),欲建的m个料场地址未拟定，其余条件与例11相同。求使总费用最少的场址。解基于第二种考虑建模设料场的坐标为mins.t.

同前例

对可不作非负限制，称为自由变量非线性规划模型注：(1)若m个料场都要修建，则不设0—1变量（3）若区域小，且道路呈网状，则使用矩形距离（2）指标不一定是“费用”，可以是“客户”到“设施”的最大距离最小等。相当于将取成1。目标函数中的常数项应去掉。若希望用户到中心的最大距离越小越好，则•••也可以是用户到中心的距离之和最小建模。均在第一象限内，例12

设某城市的街道成纵横交叉的网状，今欲建一物资供应中心，供n个用户。问该中心建在什么位置合适。试建模。),,(yx处，坐标为供应中心建在街道拐角问题！以下几种作法不妥：•用直线距离•没设“中心”建在街道拐角处•将“中心”取在坐标原点，决策变量？•设第个用户的需求量为，单位运费为，…得（总运费）例13某公司有工厂A1,A2生产某种产品，生产能力分别为Q1,Q2,有四个容量为Mk的仓库Bk(k=1,2,3,4)存放该产品，工厂和仓库均可向n个客户Cj(j=6,7,…n+5)供货，客户需求量为qj(j=6,7,…n+5).现公司打算：扩建仓库B1,其月费用为e1，库容量增加M；新建仓库B5,月费用为e5，库容量为M5;关闭仓库B2或B3,关闭后可节约费用e2或e3;并要求总的仓库数不得超过4个。已知工厂Ai向仓库或客户供货的运费每单位为cij(i=1,2;j=1,2,3,4,5为向仓库供货的运费，j=6,7,…,n+5为向客户供货的运费)。第k个仓库向第j个客户供货的单位运费dkj(k=1,2,3,4,5;j=6,7,…,n+5)。以上费用均由公司负担。问公司该作何选择可使总费用最少。解为便于理解，先作网络图。工厂仓库客户可仿运输问题，将有关数据列表。产地销地运价总量设9

产量限制客户需求限制仓库数量限制六、曲线拟合问题（去绝对值符号、化极大极小化模型为线性规划模型）已知变量y（随机变量）随x（非随机变量）变化。并已知一组样本观测值：求近似表示y与x之关系的经验方程—回归方程。^对观测值作散点图，若点子沿一直线变化，则可用直线方程^作为经验方程。（回归方程）所给的准则不同，求出的a,b也不同。常用方法—最小二乘法：^求使最小的a,b.由可解得a,b。求回归直线这一过程，称为拟合一条回归直线。于是得到回归方程^^称函数值：为回归值。所求回归方程能否用于预测和控制，还需作假设检验。类似可拟合回归曲线和回归平面。例14（1）拟合一条回归直线，使回归值与观测值的绝对偏差之和最小；（2）拟合一条回归直线，使回归值与观测值的最大偏差最小。解设回归方程为：^（1）依题意，求解这是一个无约束的非线性规划模型，不便用微分法处理。已知变量y随变量x变化，并已知一组观察值去掉绝对值符号，化为线性规划模型令则模型化为：是2n+2个决策变量，n个约束方程的线性规划模型。（2）依题意，得一极大极小化模型：mina,b令因对任何i都有：于是得非线性规划模型：又因对任何i都有：化线性规划模型则得线性规划模型：该模型中只有三个决策变量。＃七、人员时间安排问题例15某公司上午8点到21点各时段需要的服务人员数量如表1，四个班次的作息时间及月工资如表2。求既满足需求又使公司所付工资总额最少的人员安排。序号时间区间需求人数表1班次工作时间休息时间月工资表2解利用表1、表2的各时间区间端点，将营业时间区间细分，并用“1”表示工作，“0”表示休息，得一关联表（表3）。班次时段需求人数表3列给出了各班在哪几个时段工作，行给出了各时段有哪几个班在工作。设为第班安排的人数则得整数规划模型：

且为整数，建该模型的关键是：找出各班次工作的关联表，根据关联表写出约束条件。有多余的约束条件！例16

（选课策略）某校规定，运筹学专业的学生毕业时必须至少学习过两门数学课、三门运筹学课和两门计算机课。这些课程的编号、名称、学分、所属类别和先修课要求如表。问：毕业时，学生最少可以学习哪些课程？编号名称学分所属类别先修课要求微积分5数学线性代数4数学最优化4数学；运筹学微积分；线代数据结构3数学；计算机计算机编程应用统计4数学；运筹学微积分；线代计算机模拟3计算机；运筹学计算机编程7计算机编程2计算机预测理论2运筹学应用统计9数学实验3运筹学；计算机微积分；线代课程情况表建立课程与课程类别的关联表：类别数学计算机运筹学课程微积分线代优化结构统计模拟编程预测实验需求量则得0－1规划模型：是前例中需求量为2，3，2的特别情形。解编号名称

先修课要求微积分

线性代数

最优化

微积分；线代

数据结构

计算机编程

应用统计

微积分；线代

计算机模拟

计算机编程7计算机编程

预测理论

应用统计9数学实验

微积分；线代课程情况表课程总数类别（需求）限制先修要求注意表述方法！例17

一个生产问题，有关数据如表。问如何安排生产可使总利润最大，产量之和最小。要求第二种原料用完。单位利润产品原料单耗甲乙总量解设为甲，乙的产量则双目标规划模型一般形式：矛盾的八、线性多目标规划模型化成单目标规划模型化法一或化法二

为目标权重或偏好系数。

均可看成参数，对不同的参数值求出最优解，然后加以讨论，选出满意解。例17中，要求利润最大，同时产量之和最小，这种目标称为理想目标。这些目标往往是相互矛盾的，不可能同时达到最优。更现实的做法是：给出目标值，将理想目标转化为现实目标，求出尽量达到目标值的生产方案。如要求：总利润产量之和把目标函数转化成了约束条件引入正负偏差变量、，将多目标规划模型转化为目标规划模型。九、线性目标规划模型Min

要“”成立，只需min要“＝”成立，需min目标规划模型达成函数一般方法：目标类型目标规划格式极小化注：1.对于硬约束“”,可不设正偏差变量，即直接取。对于“”，可直接取。2.关于优先级问题例如：上例中，目标的重要性依次为：1°A,B