线性规划和整数规划

1、优化问题v优化问题的解题步骤： 1、确定最优目标函数。 2、寻找构成目标函数的各元素应该遵守的约束条件。 3、利用相应软件或算法求解。v例例1 生产计划问题生产计划问题-Product Mixv例例2（资源定价问题）（资源定价问题）例例3 人员分配问题人员分配问题例例4 （物资运输问题）（物资运输问题）1.2 图解法图解法-graphical method例例1 生产计划问题生产计划问题-Product Mix 某企业要在计划期内安排生产甲、乙两种产品，这某企业要在计划期内安排生产甲、乙两种产品，这个企业现有的生产资料是：设备个企业现有的生产资料是：设备18台时，原材料台时，原材料A 4吨，吨

2、，原材料原材料 B 12吨；已知单位产品所需消耗生产资料及利润吨；已知单位产品所需消耗生产资料及利润如下表。问应如何确定生产计划使企业获利最多。如下表。问应如何确定生产计划使企业获利最多。1 . 1 线性规划问题线性规划问题表表1 产品产品资源资源甲甲乙乙资源量资源量设备设备/台时台时3218原料原料A/吨吨104原料原料B/吨吨0212单位赢利单位赢利/万元万元350,021xx40121xx122021xx非负约束非负约束 产品产品资源资源甲甲乙乙资源量资源量设备设备/台时台时3218原料原料A/吨吨104原料原料B/吨吨0212单位赢利单位赢利/万元万元35182321xx 设备限制设备

3、限制 原料原料A的限制的限制 原料原料B的限制的限制0,012241823212121xxxxxx.ts2153maxxxz相应的数学模型相应的数学模型 产品产品资源资源甲甲乙乙资源量资源量设备设备/台时台时3218原料原料A/吨吨104原料原料B/吨吨0212单位赢利单位赢利/万元万元35资源的合理利用问题资源的合理利用问题 一般的资源利用问题可表述为：一般的资源利用问题可表述为： 设某企业利用设某企业利用 m 种资源来生产种资源来生产 n 种产品，已知种产品，已知该企业拥有的第该企业拥有的第 i 种资源的数量是种资源的数量是b i , 生产单位第生产单位第 j 种产品所消耗的第种产品所消耗

4、的第 i 种资源的数量为种资源的数量为 aij ，第，第j种产品的种产品的单位利润是单位利润是 c j。现制定一个生产计划方案，使总利润。现制定一个生产计划方案，使总利润最大。最大。nnxcxcxcz2211max0, 0, 02122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa资源利用问题的数学模型为资源利用问题的数学模型为：. .ts the objective functionfunctional constrainsnonegativeconstrains例例2（资源定价问题）（资源定价问题）假设企业决策者不考虑自己生产产品

5、甲乙，而是将假设企业决策者不考虑自己生产产品甲乙，而是将厂里的现有资源（见表厂里的现有资源（见表1）买出。试问该厂的决策者应给）买出。试问该厂的决策者应给每种资源制定一个怎样的价格，才能获得良好收益？每种资源制定一个怎样的价格，才能获得良好收益？ 产品产品资源资源甲甲乙乙资源量资源量设备设备/台时台时3218原料原料A/吨吨104原料原料B/吨吨0212单位赢利单位赢利/万元万元35问题分析问题分析解：决策者显然要考虑两个因素：解：决策者显然要考虑两个因素：第一，每种资源所收回的费用应不底于自己生产第一，每种资源所收回的费用应不底于自己生产 时所获得的利润；时所获得的利润；第二，定价又不能太高

6、，要使对方容易接受。第二，定价又不能太高，要使对方容易接受。 总之，定价要公平合理，使双方都能接受。总之，定价要公平合理，使双方都能接受。问题分析问题分析v设设y1,y2,y3分别表示这三种资源的收费单价。则分别表示这三种资源的收费单价。则由第一条原则：将用于加工产品甲或乙的所有资由第一条原则：将用于加工产品甲或乙的所有资源，如用来加工外来产品所获得的收回的费用，源，如用来加工外来产品所获得的收回的费用，应不低于可获得的利润，即应不低于可获得的利润，即522333121yyyy从工厂的决策者来看当然是越大越好。但是根据从工厂的决策者来看当然是越大越好。但是根据第二条原则，也应该使对方的支出尽可

7、能的少；第二条原则，也应该使对方的支出尽可能的少；从而这个问题就可以转化为下述数学问题：从而这个问题就可以转化为下述数学问题：0,321yyy32112418yyyW当然对价格还要有非负限制。即：当然对价格还要有非负限制。即：将该厂所有的资源都用来加工外来产品，其将该厂所有的资源都用来加工外来产品，其总收入（即对方的总支出）是总收入（即对方的总支出）是定价问题的数学模型定价问题的数学模型 0,52233. .12418min3213121321yyyyyyytsyyyW0,012241823212121xxxxxx. .t s2153maxxxz设某单位现有设某单位现有n个人员个人员A1,A2

8、,An来完成来完成n项工作项工作B1,B2,Bn。按工作要求，每。按工作要求，每个人员需干一项工作，每项工作也需一人个人员需干一项工作，每项工作也需一人去完成。已知人员去完成。已知人员A i做工作做工作B j的效率是的效率是c ij。问应如何分配，才使总效率最好。问应如何分配，才使总效率最好。 例例3 人员分配问题人员分配问题问题分析问题分析令令x ij表示分配人员表示分配人员A i完成工作完成工作 B j的决策变量。的决策变量。 x ij = 1 表示分配表示分配Ai干工作干工作Bj xij = 0 表示不分配表示不分配Ai干工作干工作Bj 按问题要求，每人要做一项工作，每项工作需一人去做。

9、按问题要求，每人要做一项工作，每项工作需一人去做。建立该问题的数学模型的过程：建立该问题的数学模型的过程：问题分析问题分析派工方案的总效益派工方案的总效益对工作对工作B j ；要求一人员去完成要求一人员去完成nixnjij, 2 , 1, 11niijnjx1, 2 , 1, 1ninjijijxcz11对人员对人员A i；要求承担一项工作：要求承担一项工作：分配问题的数学模型分配问题的数学模型 1 ,011.max1111ijmiijnjijninjijijxxxtsxcz某公司要运销一种物资。该物资有甲、乙两个产地，某公司要运销一种物资。该物资有甲、乙两个产地，产量分别是产量分别是2000

10、吨、吨、1000吨；另有吨；另有A、B、C三个销三个销地，销量分别是地，销量分别是1700吨、吨、1100吨、吨、200吨。已知该物吨。已知该物资的单位运价如表资的单位运价如表1-2。问应如何确定调运方案，才。问应如何确定调运方案，才能使在产销平衡的条件下，总运费最低？能使在产销平衡的条件下，总运费最低？v例4 （物资运输问题）（物资运输问题）销销 地地单位运价单位运价产产 地地甲甲乙乙销销 量量 A B C 21 25 7 51 51 371700 1100 200 产产 量量20001000表表3v分析分析 确定调运方案就是确定从不同产地到各个销地的确定调运方案就是确定从不同产地到各个销地

11、的运输量运输量。设设 x ij 表示这些要找的运量。表示这些要找的运量。即即x 11 、 x 12 、 x 13分别表示从甲地调往分别表示从甲地调往A、B、C三地的运量。三地的运量。x 21 、 x 22 、 x 23分别表示从已地调往分别表示从已地调往A、B、C三地的运量。三地的运量。由于要求产销平衡：由于要求产销平衡：从两产地甲、乙分别调往三销地从两产地甲、乙分别调往三销地A、B、C的物资数的物资数量应该分别等于两产地甲、乙的产量，所以量应该分别等于两产地甲、乙的产量，所以 x ij 应应满足：满足：10002000232221131211xxxxxx运到运到A、B、C三销地的物资数量应分

12、别等于三销地的物资数量应分别等于A、B、C三销地的销量，所以三销地的销量，所以x ij 还应该满足：还应该满足： 20011001700231322122111xxxxxx由于由于x ij 是运量，不能是负数：是运量，不能是负数：3 , 2 , 1; 2 , 10jixij23222113121137515172521xxxxxxz调运方案的总运费为：调运方案的总运费为：建立产销平衡下运费最省的调运问题的建立产销平衡下运费最省的调运问题的数学模型数学模型：23222113121137515172521minxxxxxxz3 , 2 , 1; 2 , 101000200020011001700.

13、 .232221131211231322122111jixxxxxxxxxxxxxt sij运输问题的数学模型运输问题的数学模型销销 地地单位运价单位运价产产 地地甲甲乙乙销销 量量 A B C 21 25 7 51 51 371700 1100 200 产产 量量20001000 某种物资有某种物资有 m 个产地，个产地，A1 ,A2, ,Am ，产量分别，产量分别a1,a2, ,am个单位，另有个单位，另有 n 个销地个销地B1,B2 , ,Bn , 销销量分别是量分别是b1,b2, ,bn个单位。假设产销是平衡的，个单位。假设产销是平衡的，即总产量等于总销量。已知由产地即总产量等于总销量

14、。已知由产地A i 向销地向销地B j 运输一运输一个单位物资的运价个单位物资的运价x ij ；问应该怎样调运物资才能使总；问应该怎样调运物资才能使总运费最省。运费最省。 令令 x ij 表示由产地表示由产地A i 向销地向销地B j 的运量的运量运输问题的一般提法运输问题的一般提法：运输问题的运输问题的数学模型数学模型为：为： minjijijxcz11min0 xn21jbxm21iaxijm1ijijn1jiij,. .ts 上述例子，虽然有不同的实际内容，上述例子，虽然有不同的实际内容， 但是它们都是要求一组变量的值，这组值满足一但是它们都是要求一组变量的值，这组值满足一定的约束条件，

15、如资源限制、供求关系等。定的约束条件，如资源限制、供求关系等。 这种约束条件都可以用一组这种约束条件都可以用一组线性不等式线性不等式或或线性方线性方程程来表示，同时使某个来表示，同时使某个线性函数指标线性函数指标达到最大或最达到最大或最小。具有这些特征的问题，称为小。具有这些特征的问题，称为线性规划问题线性规划问题。 1.2 图解法-graphical method 图解法适用于来解只有图解法适用于来解只有两个变量两个变量的线性规划问题的线性规划问题.0,0.max(min)212211222212112121112211xxbxaxabxaxabxaxatsxcxczmmm例例12153ma

16、xxxz0,12241823212121xxxxxx图解法求解线性规划问题图解法求解线性规划问题 图解法简单直观，有助于了解线性规划问题求解图解法简单直观，有助于了解线性规划问题求解的基本原理和思想。的基本原理和思想。 下面举例说明图解法求解线性规划问题的步骤。下面举例说明图解法求解线性规划问题的步骤。 2 4 6 8 x1x2 8 6 4 2 0 x1=42 x 2 = 123x1+2x2=18QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)图解法解题过程图解法解题过程图图1-12153maxxxz0,12241823212121xxxxxx可行域可行域-the fe

17、asible region 2 4 6 x1x2 8 6 4 2 0 x1=42 x 2 = 123x1+2x2=18QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)3x1+5x2=z=363x1+5x2=z=203x1+5x2=z=0图解法解题过程图解法解题过程图图1-12153maxxxz0,12241823212121xxxxxx让直线束让直线束zxx2153沿正法线沿正法线在可行域在可行域Q移动，移动，345,343n365321xx36maxz通过点通过点 (2,6) 的直线：的直线：注：本问题只有唯一最优解。注：本问题只有唯一最优解。 x1 8 6 4 2

18、0 x1=4QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)x1注：注：问题的问题的可行域可行域是是一个有界的一个有界的凸多边形凸多边形，其边界由其边界由5条直线所围成：条直线所围成：X 1 = 0,X 2 = 0X 1 = 42 x 2 = 123 x1 + 2 x2 = 18最优解最优解(2,6)在在凸多边形的顶点凸多边形的顶点Q2上。上。x2 8 6 4 2 0 x1=4QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)x1例例2213maxxxz0, 021260521212121xxxxxxxx解解 该问题的可行域该问题的可行域 Q 是一

19、个有界的凸多边形（是一个有界的凸多边形（如图如图1-2）。）。-x1+x2=0X1+x2=56x1+2x2=213x 1 + x 2 = z =03x 1 + x 2 = z =63x 1 + x 2 = z =21/2A(11/4,9/4)B(21/6,0)x1x2213maxxxz0, 021260521212121xxxxxxxx让直线束让直线束3x 1 + x 2 = z 沿正法线向移动，到沿正法线向移动，到达线段达线段AB时，使时，使 Z 达到最大。所以线段达到最大。所以线段 AB上的每一点都可上的每一点都可使使Z达到最大值，达到最大值，注：本问题有无穷多注：本问题有无穷多个最优解。

20、个最优解。 -x1+x2=0 x1+x2=56x1+2x2=213x 1 + x 2 = z =03x 1 + x 2 = z =63x 1 + x 2 = z =21/2A(11/4,9/4)B(21/6,0)x1x2213maxxxz0, 021260521212121xxxxxxxx例例3212minxxz0,0331212121xxxxxx1x2x3321 xxzxx212图图1-3解解 该问题的可行域是一个无界的凸多边形该问题的可行域是一个无界的凸多边形121 xx212minxxz0,0331212121xxxxxx1x2x3321 xxzxx212121 xx212minxxz0

21、,0331212121xxxxxx让直线束让直线束 沿其负法线方向移动，可以无限沿其负法线方向移动，可以无限制地移动下去，一直与制地移动下去，一直与 相交，所以其最小值为相交，所以其最小值为 ；即；即函数函数 在在 上无下界。上无下界。zxx212212xxz注：本问题有可行解，注：本问题有可行解，但无最优解。但无最优解。例例4213maxxxz0,11212121xxxxxx解解 该问题的可行域是空的，即无可行解该问题的可行域是空的，即无可行解1x2xX1-x2=-1x1+x2=-1注：本问题无可行解，更无最优解。注：本问题无可行解，更无最优解。 213maxxxz0,11212121xxx

22、xxx2211maxxcxcz0,021221122221211212111xxbxaxabxaxabxaxammm. .ts给定只有给定只有两个变量两个变量的线性规划问题：的线性规划问题：图解法求解线性规划问题的步骤如下：图解法求解线性规划问题的步骤如下：2R2211xcxcz2221222211ccccccn,沿正法线方向沿正法线方向 移动可得最大值，沿负移动可得最大值，沿负法线方向法线方向 移动可得最小值。移动可得最小值。2221222211ccccccn,注意注意:一定要精确一定要精确通过以上例子可以看出，两个变量的线性规划的解可通过以上例子可以看出，两个变量的线性规划的解可能有以下能

23、有以下4种情况：种情况： 有唯一的最优解。有唯一的最优解。 最优解一定是可行域的一个顶点。最优解一定是可行域的一个顶点。 有无穷多的最优解。有无穷多的最优解。 最优解是可行域的一段边界。最优解是可行域的一段边界。 有可行解，但无最优解。目标函数值无界有可行解，但无最优解。目标函数值无界. 无可行解。无可行解。 （最大值点（最小值点）一定在可行域的边界上）（最大值点（最小值点）一定在可行域的边界上） 问题是对于一般的线性规划问题有无类似结论，问题是对于一般的线性规划问题有无类似结论，结论成立的判定准则如何。结论成立的判定准则如何。1.3 整数规划整数规划例例1、集装箱运货、集装箱运货 货物货物

24、体积体积(米米3/箱箱) 重量重量(百公斤百公斤/箱箱) 利润利润(千元千元/箱箱) 甲甲 5 2 20 乙乙 4 5 10 装运限制装运限制 24 13 解：设解：设X1 , X2 为甲、乙两货物各托运箱数为甲、乙两货物各托运箱数5X1+4X2 242X1+5X2 13X1 , X2 0 0X1 , X2为整数为整数maxZmaxZ = 20 = 20 X1 + 10 X2例例2、背包问题、背包问题背包可再装入背包可再装入8单位重量，单位重量，10单位体积物品单位体积物品物品物品 名称名称 重量重量 体积体积 价值价值 1 书书 5 2 20 2 摄像机摄像机 3 1 30 3 枕头枕头 1 4 10 4 休闲食品休闲食品 2 3 18 5 衣服衣服 4 5 15 解：解：Xi为是否带第为是否带第 i 种物品种物品maxZ=20X1 + 30X2 +10X3+18X4 +15X55X1+3X2 +X3 +2X4 +4X5 82X1+X2 +4X3 +3X4 +5X5 10Xi为为0, 1一般形式：一般形式：0max11iniiiniiiXbXaXCZ,整数整数(1)、 Xi为为i 物品携带数量物品携带数量 ai为为i 物品单位重量物品单位重量 ci为为i 物品重要性估价物品重要性估价 b为最大负重为最大负重(2)、 投资决策投资决策 Xi为在为在