数学规划模型2014

数学规划模型I引言

一个复杂系统往往要受诸多因素的影响，而这些因素又要受到一定的限制。最优化就是研究在一定约束下，如何选取这些因素的值，使某项（或某些）指标达到最优的一门学科。数学规划是最优化中的重要部分。它包括线性规划、整数规划、目标规划、动态规划、非线性规划等。数学规划方法在经济、军事、科技等领域内都有广泛的应用。内容提要

一、一般的数学规划模型二、数学规划常见模型：1.运输问题（例1，2）

2.网络（规划）问题（例3，4）3.分派问题

（例5）4.生产活动问题（例6，7，8，9）5.选址问题

（例10，11，12，13，14）

6.线性多目标规划问题（例15）7.线性目标规划问题（例15）一、一般的数学规划模型数学规划模型的一般形式：例如：maxs.t.若能写出描述S的数学式子，则可直接写出。这里目标函数可行域可行解决策变量描述S的数学式子约束条件S问题可行问题不可行最优解最优目标值几个概念：特别：(或max)或线性规划模型（LP）或等约束的LP模型的矩阵形式LP模型的向量形式注：M是常数与有相同的最优解1.2.与有相同的最优解另外：1.取整数，称模型为整数规划模型2.中部分取整数，称模型为混合整数规划模型3.只取0或1两个值，称为0—1规划模型目标函数或约束条件是非线性的，称为非线性规划模型若目标函数只有一个，称为单目标规划模型；若目标函数不只一个，称为多目标规划模型。产地销地运价例1求使总运费最少的调运方案。试建模。产量需求量42一、运输问题解则产销平衡注：若产大于销，则若产小于销，则线性规划模型

重要结论：当供应量与需求量均为整数时，模型的最优解是整数解。求解运输问题可采用表上作业法，或忽略掉运输问题的特殊性，直接使用求解一般线性规划的单纯形法实际问题中产销不平衡时，也可在分析问题阶段将其化为产销平衡问题，举例如下例：化肥供应问题：设由三个化肥场供应四个地区的农用化肥，假定等量的化肥在这些地区使用效果相同。已知各化肥厂年产量，各地区年需要量及从各化肥厂到各地区的单位运价表，试决定使得总运费最省的化肥调拨方案。IIIIIIIV产量A1613221750B1413191560C192023－50最低需求3070010最高需求507030不限I’I’’IIIIIIV’IV’’产量A16161322171750B14141319151560C1919202350D000销量7030解：分析实际问题，得产销平衡表例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千吨水须全部输出居民缴纳的买完160千吨的水费供给限制需求限制另：为了增加供水，公司考虑改造水库，使三个水库的供水能力提高一倍，问模型将作何改动？分析：由于总供水能力为320千吨，总需求量为300千吨，水不能全部卖出，所以不能将获利最多转化为引水管理费最少。须算出每千吨净利润。每千吨净利润＝用户交的900元－其它管理费450元－引水管理费净利润(元/千吨)模型改为：其它同前例3①②③④⑤⑥⑦图中弧上的数字表示每小时两结点沿箭头方向的最大车流量，求①到⑦每小时的最大车流量。二、网络（规划）问题之一-----最大流问题设v为从出发的车流量，

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

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

、为流入、的量，

、、为流入、、的量。例：多端网络问题设有5位待业者，5项工作，他们各自能胜任工作的情况如图所示，要求设计一个就业方案，使尽量多的人能就业。其中表示工人。表示工作。这本身是个最大匹配问题，可以转化为最大流问题求解。在二部图中增加两个新点分别作为发点，收点。并用有向边把它们与原二部图中顶点相连，令全部边上的容量均为1。当网络流达到最大时，如果上的流量为1，就让作工作，此即为最大匹配方案。例：某河流中有几个岛屿，从两岸至各岛屿及各岛屿之间的桥梁编号如图，在一次敌对的军事行动中，问至少应炸断几座桥，才能完全切断两岸的交通。二、网络（规划）问题之二-----中国邮路问题、最优Hamilton圈（TSP）问题18世纪，在德国东普鲁士哥尼斯堡有七座桥，连接这七座桥的陆地有四块，如下图，一个散步者能否从四块陆地中的任意一块开始，通过每座桥恰好一次，最后回到出发点？BCD七桥问题

定义：（Euler迹、Euler环游、Euler图）解：1。模拟图：以顶点表陆地，以边表桥，得4个顶点的模拟图。2。问题等价于：能否有一条闭迹包含模拟图的所有边，即：模拟图是Euler图吗？3。求解：假设图G是Euler图。因为闭迹是连通的，所以图G也连通。又因为每个顶点既能到达也能离开，所以图G的每个顶点度都是偶数。所以，欧拉在1736年得出结论：“七桥问题”是不可能的，同时开创了图论的研究。含图G的所有边的迹，称为Euler迹（如果此迹是闭迹，也叫Euler环游），把含有Euler闭迹（环游）的图称为Euler图。如果一个图G含有Euler闭迹，我们如何找到它呢？下面介绍一种寻找Euler图中Euler闭迹的算法－Fleury算法Fleury算法（1）任取一个顶点，置；（2）假定迹已经选出，则用下列方法从中选出：a）与关联；b）除非没有其它的边可选择，不是

c)当(2)不能执行时，停止，否则，令i+1i,转(2)的割边。割边：连通图G中不在任何圈中的边。两个定理定理：若G是Euler图，则G的任何用Fleury算法构成的迹都是Euler环游（闭迹）。定理：图G含Euler闭迹（环游）的充要条件是G连通且没有奇顶点。若一个邮递员在下图所示的街道上投递邮件，问如何投递才使得他走遍每一条街道，再返回邮局，且总路程最短？11111111中国邮路问题这是由中国数学家管梅谷教授于1960年提出并求解的。问题分析：据上面定理知，若街道图中没有奇点，则他就可以从邮局出发，走过每条街道一次，且仅一次，最后回到邮局，如此他所走的路程即是最短路程。而对于有奇点的图，必须在某些街道上重复走一次或多次。（假定N1为邮局）这样，路线可有多种，例：总权为12总权为11可见，按第一条路线，在边上各重复走了一次，而按第二条路线，在边上各重复走了一次。因此，我们想到，可在一个有奇点的图中，增加一些重复边，使得新图不含奇点，且要求重复边的总权最小。注释：增加重复边使图无奇点的过程称为可行方案。使总权最小的可行方案称为最小方案第一步（找初始可行方案）：找到图中的奇点，把奇点两两相连，（因为，在任何图中奇点个数必为偶数）。第二步（调整可行方案）：调整时遵循两个原则：（a）在最优方案中，图的每一条边上最多有一条重复边；（b）在最优方案中，图的每一个圈上重复边的总权不大于该圈总权的一半。（若把图中某个圈上的重复边去掉，而给原来没有重复边的的边上加上重复边，图中仍没有奇点）第三步（判断最优方案）：检查条件（a），（b）是否满足，若是，则为最优。得求解步骤：例：求解下面问题。255964343444解：奇点有：连接且连接得：255964343444因为圈的总权为24，但重复边的总权为14，大于该圈总权的一半，故需要调整，以上的重复边代替上的重复边，使重复边总长下降为17，255964343444同理，调整圈

后，得最优方案：255964343444注1：此法称为奇偶点图上作业法，由管梅谷给出。注2：最优方案就是一个Euler图了，再对它使用Fleury算法就能找到邮递员的满足要求的投递路线了。255964343444例：对上面的结果用Fleury算法给出一个Euler环游

Hamilton圈和旅行售货商问题

1859年，数学家Hamilton发明了一种周游世界的游戏。把一个12面体的20个顶点分别标上北京、东京、华盛顿等20个大都市的名字，要求玩的人从某城市出发，沿着12面体的棱通过每一个城市恰好一次，再回到出发的城市。这种游戏在欧洲曾经风靡一时，Hamilton以25个金币的高价把该项专利卖给了一个玩具商。用图论的语言来讲，此游戏本质就是在一个12面体上寻找经过每一个顶点一次且恰好一次的特殊的圈，即Hamilton回路。此问题后面会进一步详述。例5

设有工作件，人员个，且一人做一件工作，第人作第件工作的时间（或费用）为，问：如何分派可使总时间（或总费用）最少。解本题需确定：第人做或不做第件工作，这是定性变量，首先将其定量化。设0—1规划模型则注：若表示效益，则目标函数应极大化若人数“>”工作件数三、分派问题、指派问题对于指派问题，除了可以使用一般的整数规划的方法求解之外，还可以结合问题自身的特点，使用此问题专门的求解方法--------匈牙利法求解人数工作数不等的情况可以通过变化，变成相等的情况，即完美指派，举例如下甲乙丙丁戊仰泳37.732.933.83735.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1解：该问题可看作指派问题。添加一个虚拟项目，得到如下效率矩阵

甲乙丙丁戊仰泳37.732.933.83735.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1虚拟00000甲乙丙丁戊仰泳3.91.904.11.6蛙泳7.80.36.606.2蝶泳207.602.3自由泳000.40.21.9虚拟02.800.90最优结果如下四、生产活动问题(分段函数、矛盾约束等的处理方法)资源产品单耗资源量单位利润例6问如何安排生产使总利润最大。解设表示第种产品的产量，则资源分配问题分段函数问题（有关的收益问题）假设例中＝单位收益－单位成本（可变成本）若还要考虑固定成本（如：机器、厂房等）于是，需要引入0—1变量：设Lj

是xj的上界，则模型改写为：假设第j种产品的固定成本是，第j种产品产量的上界为，混合整数规划模型等价性：（1）由Z的极大化（2）由当然，固定成本一般都是指机器、厂房等带来的成本，在某个固定的时期内，它们往往是一个相对固定的值，所以一般可以在整个收益函数的后面减去此值即可。可不影响原模型的最优解。注：将目标函数变成则为非线性的。若不考虑固定成本，则不引入0-1变量。

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

y1=500时，才能以每吨8千元的价格购买y2(>0)非线性规划模型！注：当然，此时还得考虑B1这种资源的拥有量也要跟着调整，此时的b1应该改为：产品种类限制问题（不考虑固定成本）n种产品中只生产其中k种设则若加入要求：产量不小于80单位如果产量没有上限，此时可取Lj为较大的正数Lj是产量上限矛盾约束问题如果、是机器1、2的可用工时（资源），

且假定n种产品只能在其中一台机器上加工，则以下两个约束条件此时，若引入0—1变量：设M是充分大的常数，则两个矛盾约束可统一在一个模型中：是矛盾的，不能同时出现在一个模型中，即，要在达到最优的过程中让其中一个约束无效一般，若m种资源中只用其中k种资源，则令约束条件改为：若yi=1，则约束无效例7

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

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

为减少一个产品支付的费用。且或分别各增加一项：或不希望减少不希望增加例8

：求生产、存储、维修计划（多阶段资源分配问题）某机械厂计划在1－6月份生产7种产品。该厂有5种机床，其数量如下表。已知第j种产品在第t种机床上所需加工台时为第j种产品的单位利润为，第i月第j种产品的销售限量为。每种产品一次至多储存100件，每件月存储费a元，1月初无存储，6月底每种产品要求余50件。生产每天两班，每班8小时，一个月平均工作21天。工厂规定，在半年内每台机床在某月必须停车维修一次，维修时间为10天。为使利润最大，工厂应该如何安排生产？机床类型12345数量42311机床类型12345月台时13446721008336336解：将有关数据整理列表：机床单耗产品台数月台时单位利润月台时＝台数小时天数。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个料场地址未拟定，其余条件与例10相同。求使总费用最少的场址。解此处仅基于第二种考虑建模设料场的坐标为mins.t.

同前例

对可不作非负限制，称为自由变量非线性规划模型注：(1)若m个料场都要修建，则不设0—1变量（3）若区域小，且道路呈网状，则使用矩形距离（2）指标不一定是“费用”，可以是“客户”到“设施”的最大距离最小等。相当于将取成1。目标函数中的常数项应去掉。如下例12若希望用户到中心的最大距离越小越好，则••也可以是用户到中心的距离之和最小建模。均在第一象限内，例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)。以上费用均由公司负担。问公司该作何选择可使总费用最少。解为便于理解，先作网络图。工厂仓库客户费用来自两部分：运费+建设费用。可仿运输问题，将有关数据列表。产地销地运价总量其中产地运送到仓库的量

产量限制客户需求限制仓库数量限制仓库容量限制变量取值范围例14

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

先修课要求微积分

线性代数

最优化

微积分；线代

数据结构

计算机编程

应用统计

微积分；线代

计算机模拟

计算机编程7计算机编程

预测理论

应用统计9数学实验

微积分；线代课程情况表即：若x3=1，则必须有x1=x2=1课程总数类别（需求）限制先修要求注意表述方法！例15

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

为目标权重或偏好系数。

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

要“”成立，只需min要“＝”成立，需min目标规划模型达成函数一般方法：目标类型目标规划格式极小化注：1.对于硬约束“”,可不设正偏差变量，即直接取。对于“”，可直接取。2.关于优先级问题例如：上例中，目标的重要性依次为：1°A,B两种原料一定不能超过限量；2°原料B尽量用完；3°利润超过1000；4°产量之和尽量少。于是，达成函数可写为：Min

»»»其中为优先因子或Min

例某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：(1)不超过工资总额60000元；(2)每级的人数不超过定编规定的人数；(3)Ⅱ，Ⅲ级的升级面尽可能达到现有人数的20%，且无越级提升；(4)Ⅲ级不足编制的人数可录用新职工，又Ⅰ级的职工中有10%要退休。有关资料汇总于表1中，问该领导应如何拟订一个满意的方案。表1月解设x1、x2、x3分别表示提升到Ⅰ、Ⅱ级和录用到Ⅲ级的新职工人数。对各目标确定的优先因子为：P1——不超过工资总额60000元；P2——每级的人数不超过定编规定的人数；P3——Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%。先分别建立各目标约束。

P1:工资总额不超过60000元

2000(10-10×0.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1—-d1+

=60000minP1d1+P2：每级的人数不超过定编规定的人数：对Ⅰ级有10(1-0.1)