第四章 数学规划模型【教学目的】：深刻理解线性规划，非线性规划，动态规划方法建模的基本特点，并能熟练建立一些实际问题的数学规划模型；熟练掌握用数学软件（Matlab ，Lindo ，Lingo 等）求解优化问题的方法。
【教学重点难点】：教学重点：线性规划和非线性规划的基本概念和算法，解决数学规划问题的一般思路和方法，线性规划模型、整数规划模型、非线性规划模型的构建及其Matlab 与Lingo 实现。
教学难点：区分线性规划模型和非线性模型适用的实际问题，以及何时采用线性模型，何时采用非线性模型，线性模型与非线性模型的转化。
【课时安排】：10学时【教学方法】：采用多媒体教学手段，配合实例教学法，通过对典型例题的讲解启发学生思维，并给与学生适当的课后思考讨论的时间，加深知识掌握的程度。
安排一定课时的上机操作。
【教学内容】：在众多实际问题中，常常要求决策（确定）一些可控制量的值，使得相关的量（目标）达到最佳（最大或最小）。
这些问题就叫优化问题，通常需要建立规划模型进行求解。
称这些可控制量为决策变量，相关的目标量为目标函数；一般情况下，决策变量x 的取值是受限制的，不妨记为x ∈Ω，Ω称为可行域，优化问题的数学模型可表示为Max(或Min)f(x), x ∈Ω一般情况下，x 是一个多元变量，f(x)为多元函数，可行域比较复杂，一般可用一组不等式组来表示，这样规划问题的一般形式为()xMin f x .()0,1,2,,i st g x i m≤=虽然，该问题属于多元函数极值问题，但变量个数和约束条件比较多，一般不能用微分法进行解决，而通过规划方法来求解；这里讨论的不是规划问题的具体算法，主要是讨论如何将一个实际问题建立优化模型，并利用优化软件包进行求解。
根据目标函数和约束函数是否为线性，将规划模型分为线性规划和非线性规划。
4.1线性规划线性规划(LP)研究的实际问题多种多样的，它在工农业生产、经济管理、优化设计与控制等领域都有广泛应用。
如资源分配问题、生产计划问题、物资运输问题、合理下料问题、库存问题、劳动力安排问题、最优设计问题等等。
线性规划模型的求解方法目前仍以单纯形法为主要方法，该方法于1947年由美国数学家丹茨格（G .B.Dantzig ）提出，经过60多年的发展完善，已经形成比较成熟的算法，同时配合计算机技术的广泛应用使得该方法得到空前的普及应用。
目前，大多数数学软件都可以求解一般线性规划模型，这一节主要采用Matlab 和Lindo 软件。
4.1.1奶制品的生产与销售 例1 加工奶制品的生产计划【问题描述】一奶制品加工厂用牛奶生产1A ，2A 两种奶制品，1桶牛奶可以在设备甲上用12小时加工成3公斤1A ，或者在设备乙上用8小时加工成4公斤2A ．根据市场需求，生产的1A ，2A 全部能售出，且每公斤1A 获利24元，每公斤2A 获利16元．现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤1A ，设备乙的加工能力没有限制．试为该厂制订一个生产计划，使每天获利最大，并进一步讨论以下3个附加问题：1)若用35元可以买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？ 2)若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元? 3)由于市场需求变化，每公斤1A 的获利增加到30元，应否改变生产计划?【问题分析】这个优化问题的目标是使每天的获利最大，要作的决策是生产计划，即每天用多少桶牛奶生产1A ，用多少桶牛奶生产2A (也可以是每天生产多少公斤1A ，多少公斤2A )，决策受到3个条件的限制：原料(牛奶)供应、劳动时间、设备甲的加工能力。
【模型假设】1) 1A ，2A 两种奶制品每公斤的获利是与它们各自产量无关的常数，每桶牛奶加工出1A ，2A 的数量和所需的时间是与它们各自的产量无关的常数；2) 1A ，2A 每公斤的获利是与它们相互间产量无关的常数，每桶牛奶加工出1A ，2A 的数量和所需的时间是与它们相互间产量无关的常数；3)加工1A ，2A 的牛奶的桶数可以是任意实数．【模型建立】设每天用1x 桶牛奶生产1A ，用2x 桶牛奶生产2A ． 设每天获利为z 元．1x 桶牛奶可生产31x 公斤1A ，获利 24⨯31x ，2x 桶牛奶可生产42x 公斤2A ，获利16⨯42x ，故目标函数为：z=721x +642x ．由题目可以得到如下约束条件：原料供应： 生产1A ，2A 的原料(牛奶)总量不得超过每天的供应，即1x +2x ≤50桶； 劳动时间： 生产1A ，2A 的总加工时间不得超过每天正式工人总的劳动时间，即121x +82x ≤480小时；设备能力： 1A 的产量不得超过设备甲每天的加工能力，即31x ≤100； 非负约束： 1x +2x 均不能为负值，即1x ≥0，2x ≥0． 综上可得该问题的数学模型为：⎪⎪⎩⎪⎪⎨⎧≥≥≤≤+≤++0x 0,x 1003x 4808x 12x 50x x s.t.64x 72x max 211212121 由于目标函数和约束条件对于决策变量而言都是线性的，所以称为线性规划(LinearProgramming ，简记作LP)。
【模型求解】(图解法)：这个线性规划模型的决策变量为2维，用图解法既简单，又便于直观地把握线性规划的基本性质．将约束条件中的不等号改为等号，可知它们是1Ox ，2x 平面上的5条直线，依次记为1L ～5L ，如图1．其中4L ，5L 分别是工2x 轴和1x 轴，并且不难判断，(2)～(5)式界定的可行域是5条直线上的线段所围成的5边形OABCD ．容易算出，5个顶点的坐标为：O(0，0)，A(0，50)，B(20，30)，C(100/3，10)，D(100/3，0)．目标函数中的z 取不同数值时，在图1中表示一组平行直线(虚线)，称等值线族．如z=0是过O 点的直线，z=2400是过D 点的直线，z=3040是过C 点的直线，…．可以看出，当这族平行线向右上方移动到过B 点时，z=3360，达到最大值，所1,5[B 点的坐标(20，30)即为最优解：1x =20，2x =30．图1 图解法示意图我们直观地看到，由于目标函数和约束条件都是线性函数，在2维情形，可行域为直线段围成的凸多边形，目标函数的等值线为直线，于是最优解一定在凸多边形的某个顶点取得．推广到n 维情形，可以猜想，最优解会在约束条件所界定的一个凸多面体 (可行域)的某个顶点取得．(软件求解)在LINDO 软件中输入如下程序：max 72x1+64x2 st2）x1+x2<503）12x1+8x2<480 4）3x1<100 end运行后结果显示：OBJECTIVE FUNCTION V ALUE 1) 3360.000VARIABLE V ALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGESV ARIABLE CURRENT ALLOWABLE ALLOWABLECOEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGESROW CURRENT ALLOWABLE ALLOWABLERHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000 即：20桶牛奶生产1A , 30桶生产2A ，最大利润为3360元。
结果分析：从上述输出结果中可以看出：将3个约束条件有段不放看作三种“资源”：原料、劳动时间、甲类设备的加工能力。
输出低7~10行“SLACK OR SURPLUS”给吃这三种资源在最优解下是否剩余：原料无剩余，时间无剩余，加工能力剩余40；“资源”剩余为零的约束为紧约束（有效约束）。
目标函数可以看做 “效益”。
最优解下“资源”增加1单位时“效益”的增量：原料增加1单位, 利润增长48 ；时间增加1单位, 利润增长2；加工能力增长不影响利润。
效益的增量可以看作“资源”的潜在价值，经济学上称为影子价格：即1桶牛奶的影子价格为48元；1小时劳动的影子价格为2元；甲类设备的影子价格为0。
对于附加问题1）：35元可买到1桶牛奶，要买吗？ 由于35 <48, 应该买！对于附加问题2）：聘用临时工人付出的工资最多每小时几元？ 2元！从上述输出结果的第13-17行可以得出最优解不变时目标函数系数允许变化范围：1x 系数范围(64,96)，2x 系数范围(48,72)，1A 获利增加到 30元/千克，应否改变生产计划 1x 系数由24×3=72增加为30×3=90，在允许范围内不变！影子价格有意义时约束右端的允许变化范围：原料最多增加10，时间最多增加53。
对于附加问题3）：35元可买到1桶牛奶，每天最多买多少？最多买10桶!例2 奶制品的生产销售计划【问题描述】例1给出的1A ，2A 两种奶制品的生产条件、利润，及工厂的“资源”限制全都不变．为增加工厂的获利，开发了奶制品的深加工技术：用2小时和3元加工费，可将1公斤1A 加工成0．8公斤高级奶制品1B ，也可将1公斤2A 加工成0.75公斤高级奶制品2B ；每公斤1B 能获利44元，每公斤2B 能获利32元．试为该厂制订一个生产销售计划，使每天的净利润最大，并讨论以下问题：1)若投资30元可以增加供应1桶牛奶，投资3元可以增加1小时劳动时间，应否作这些投资?若每天投资150元，可赚回多少?2)每公斤高级奶制品1B ，2B 的获利经常有10％的波动，对制订的生产销售计划有无影响?若每公斤1B 的获利下降10％，计划应该变化吗?【问题分析】要求制订生产销售计划，决策变量可以像例l 那样，取作每天用多少桶牛奶生产1A ，2A ，再添上用多少公斤1A 加工1B ，用多少公斤2A 加工2B ，但是由于问题要分析1B ，2B 的获利对生产销售计划的影响，所以决策变量取作1A ，2A ，1B ，2B 每天的销售量更方便．目标函数是工厂每天的净利润——1A ，2A ，1B ，2B 的获利之和扣除深加工费用．约束条件基本不变，只是要添上1A ，2A 深加工时间的约束．在与例1类似的假定下用线性规划模型解决这个问题．【模型建立】设每天销售1x 公斤1A ，2x 公斤2A ，3x 公斤1B ，4x 公斤2B ，用5x 公斤1A 加工1B ，6x 公斤2A 加工2B (增设5x ，6x 可使下面的模型简单)． 设每天净利润为z ，容易写出目标函数为：6543213332441624x x x x x x z --+++=，由题设可以得到如下约束条件：原料供应 ：1A 每天生产1x +5x 公斤，用牛奶(1x +5x )／3桶， 2A 每天生产2x +6x 公斤，用牛奶(2x +6x )／4桶，二者之和不得超过每天的供应量50桶；劳动时间 ：每天生产1A ，2A 的时间分别为4(1x +5x )和2(2x +6x )，加工1B ，2B 的时间分别为25x 和26x ，二者之和不得超过总的劳动时间480小时； 设备能力 ：1A 的产量1x +5x 不得超过设备甲每天的加工能力100公斤；非负约束 ：1x ，2x ，…，6x 均为非负． 附加约束 ：l 公斤1A 加工成0．8公斤1B ，故3x = 0．85x ，类似地4x =0．756x ．综上可得该问题的数学模型为：⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥==≤+≤+++++≤++++++0,,,,x ,x 0.75x x 0.8x x 100x x 480x 2x 2)x 2(x )x 4(x 504x x 3x x s.t.3x -3x -32x 4416x 24x max 6543216453515262516251654321x x x x x 这仍然是一个线性规划模型．求解过程与上面软件求解部分类似。