运筹与决策之2线性规划

1、1question线性规划的概念和建模线性规划的概念和建模线性规划的图解法线性规划的图解法单纯形法基本步骤单纯形法基本步骤计算机软件求解计算机软件求解lp问题（下料优化）问题（下料优化）case 2:灵敏度分析灵敏度分析(21绪论绪论 introduction2线性规划线性规划 linear programming3运输问题运输问题 transportation models 4整数规划整数规划 integer programming5网络模型网络模型 network models6项目计划项目计划 pert & cpm7排队论排队论 queueing models8 模拟模拟 sim

2、ulation 9决策分析决策分析 decision theory10多目标决策多目标决策 multi-objective decision3l线性规划问题的导出线性规划问题的导出lor在企业管理的具体应用在企业管理的具体应用例例1、家具厂生产计划问题、家具厂生产计划问题例例3、合理下料问题、合理下料问题l线性规划概念和模型线性规划概念和模型4 产品产品 a b可用资源可用资源 木工木工 1 2 30 油漆工油漆工 3 2 60 搬运工搬运工 0 2 24 利润利润(￥) 40 50例例1、家具厂生产计划问题、家具厂生产计划问题a, b 各生产多少各生产多少, 可获最大利润可获最大利润?如何建

3、模？如何建模？5产品消耗系数、利润、可用资源产品消耗系数、利润、可用资源a, b 各生产多少各生产多少最大利润最大利润6x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0max z= 40 x1 +50 x2解解:设产品设产品a, b产量分别为变量产量分别为变量x1 ， x27例例2 2 营养配餐营养配餐求：最低成本的原料混合方案求：最低成本的原料混合方案 原料原料i a b 每单位成本每单位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8 每单位添每单位添 加剂中维生加剂中维生 12 14 8 素最低含量素最低含量如何建模？如何

4、建模？8解：设每单位添加剂中原料解：设每单位添加剂中原料i的用量为的用量为xi(i =1,2,3,4)min z = 2x1 + 5x2 +6x3+8x4 4x1 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14 2x2 + x3+3x4 8 xi 0 (i =1,4)9定义：定义：对于求取一组变量对于求取一组变量 xj (j=1,2,.,n)，使之既，使之既满足线性约束条件，又使具有线性的目满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为标函数取得极值的一类最优化问题称为线性规划问题。线性规划问题。10l要解决的问题的目标可以用数值指标反映要解决

5、的问题的目标可以用数值指标反映l对于要实现的目标有多种方案可选择对于要实现的目标有多种方案可选择l有影响决策的若干约束条件有影响决策的若干约束条件11l线性规划很容易而有效率地被求解线性规划很容易而有效率地被求解l如果存在最优解，则必能够找到如果存在最优解，则必能够找到l功能强大的敏感性分析（功能强大的敏感性分析（sensitivity analysis）l许多实际问题本质上是线性的许多实际问题本质上是线性的12l决策变量决策变量：向量：向量(x1 xn)t 决策人要决策人要考虑和控制的因素非负考虑和控制的因素非负l约束条件约束条件：线性等式或不等式：线性等式或不等式l目标函数目标函数：z=(

6、x1 xn) 线性式，求线性式，求z极大或极小极大或极小13一般式一般式max(min)z=c1x1+ c2x2+cnxna11x1+ a12x2+ a1nxn (=, (=, )b)b1 1a21x1+ a22x2+ a2nxn (=, (=, )b)b2 2 am1x1+ am2x2+ amnxn (=, (=, )b)bm mxj j 0(0(j=1,n) )14njjjxcz1max(min),2, 1(0),2, 1(1njxmibxajinjjij15l比例性比例性：决策变量变化引起目标的改变：决策变量变化引起目标的改变量与决策变量改变量成正比量与决策变量改变量成正比l可加性可加性

7、：每个决策变量对目标和约束的：每个决策变量对目标和约束的影响独立于其它变量影响独立于其它变量l连续性连续性：每个决策变量取连续值：每个决策变量取连续值l确定性确定性：线性规划中的参数：线性规划中的参数aij , bi , ci为为确定值确定值 16某钢筋架需要某钢筋架需要 长度长度1.5m 、2.1m和和 2.9m各各100段段 ，每根标准钢筋长度为，每根标准钢筋长度为7.4m，问如何，问如何合理下料所需标准钢筋数目最少？合理下料所需标准钢筋数目最少？ 2.9m 1 2 0 1 0 2.9m 1 2 0 1 0 2.1m 0 0 2 2 1 2.1m 0 0 2 2 1 1.5m 3 1 2

8、0 3 1.5m 3 1 2 0 3 合计合计 7.4 7.3 7.2 7.1 6.67.4 7.3 7.2 7.1 6.6 料头料头 0 0.1 0.2 0.3 0.80 0.1 0.2 0.3 0.8例例3 3、合理下料问题、合理下料问题17解：设按第解：设按第i种方案下料的原材料为种方案下料的原材料为xi根根min z = 0.1x2 + 0.2x3+0.3x4+0.8x5 x1 + 2x2 + x4 = =100 2x3 +2x4+ x5= =100 3x1+ x2+2x3 +3x5= =100 xi 0 (i =1,5)如何正确建模？如何正确建模？18l决策变量缺少整数变量约束决策变

9、量缺少整数变量约束l约束条件为等式约束条件为等式l用余料作为目标函数用余料作为目标函数l下料方式不全（少下料方式不全（少3种下料方式）种下料方式）19解：设按第解：设按第i种方案下料的原材料为种方案下料的原材料为xi根根min z = x1 + x2 +x3+x4+x5+x6+x7+x8 2x1 + x2 + x3 + x4 100 2x2 + x3 +3x5+ 2x6 + x7 100 x1+ x3+3x4 + 2x6+3x7 +4x8 100 xi 0 (i =1,8)，且为整数且为整数如何建模？如何建模？20例例4 4、运输问题、运输问题某公司有三个分厂分别供应三个市场，某公司有三个分厂

10、分别供应三个市场，具体生产能力和需求量如下表：具体生产能力和需求量如下表：如何建模？如何建模？ 市场市场1 市场市场2 市场市场3 产量产量工厂工厂1 2 1 3 50工厂工厂2 2 2 4 30工厂工厂3 3 4 2 10 需求需求 40 15 3521设设xij为为i 工厂运到工厂运到 j市场的产品数量市场的产品数量(i 1，2，3， j 1，2，3)min z = 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33x11 +x12+x13 50 x21+x22+x23 30 x31+x32+x33 10 x11 +x21+x31 = 40

11、 x12 +x22+x32 = 15x13 +x23+x33 = 35 xij 022例例5 5、连续投资、连续投资1010万元万元la：从第：从第1年年 到第到第4年每年初要投资，次年末年每年初要投资，次年末回收本利回收本利1.15lb：第第3年初投资，到第年初投资，到第5年末回收年末回收1.25，最大，最大投资投资4万元万元lc：第第2年初投资，到第年初投资，到第5年末回收年末回收1.40，最大，最大投资投资3万元万元ld：每年初投资，每年末回收每年初投资，每年末回收1.11。求：求：5 5年末总资本最大年末总资本最大如何建模？如何建模？23分析分析 1 2 3 4 5a x1a x2a

12、x3a x4a b x3bc x2cd x1d x2d x3d x4d x5d xik( i =1,2,5; k =a,b,c,d)第第i年初投年初投k项目的资金数项目的资金数max z = 1.15x4a +1.40 x2c+1.25x3b+1.11x5dx1a+x1d 10 x2a+x2c+x2d= 1.11 x1dx2c 3x3a +x3b+x3d =1.15 x1a+ 1.11 x2dx3b 4x4a +x4d =1.15 x2a+ 1.11 x3dx5d =1.15 x3a+ 1.11 x4d xik 025ax=b (1)x 0 (2)max z = cx (3)定义定义1 1:满

13、足约束满足约束(1)、(2)的的x=(x1 xn)t称为称为lp问题的问题的可行解可行解，全部可行解集合称为，全部可行解集合称为可行域。可行域。定义定义2 2:满足满足(3)的可行解称为的可行解称为lp问题的问题的最优解。最优解。26 产品产品 a b 备用资源备用资源 木工木工 1 2 30 油漆工油漆工 3 2 60 搬运工搬运工 0 2 24 利润利润 40 50例例1、家具厂生产计划问题、家具厂生产计划问题a, b 各生产多少各生产多少, 可获最大利润可获最大利润?27建立模型建立模型max z = 40x1+ 50x2 x1 + 2x2 303x1 + 2x2 60 2x2 24 x

14、1 , x2 0 0建模后如何计算？建模后如何计算？28解：解：(1)、确定可行域、确定可行域 x1 0 0 x1 =0=0 ( (横轴横轴) ) x2 0 0 x2=0=0 ( (纵轴纵轴) ) x1+2x2 30x1+2x2 =30两点两点 (0,15)、 (30,0)2030100102030x2dabc3x1+2x2 =60(0,30) (20,0) 2x2 =24x129(2)、求最优解、求最优解解：解：x* = (15,7.5) zmax =975z= 40x1+50x20=40x1+50x2 (0,0)， (10,-8)0203010102030x1x2dabcdabcc点：点：

15、 x1+2x2 =30 3x1+2x2 =6030几何概念几何概念代数概念代数概念约束直线约束直线满足一个等式约束的解满足一个等式约束的解约束半平面约束半平面满足一个不等式约束的解满足一个不等式约束的解约束半平面的交集：约束半平面的交集：凸多边形凸多边形满足一组不等式约束的解满足一组不等式约束的解约束直线的交点约束直线的交点基本解基本解可行域的极点可行域的极点基本可行解基本可行解目标函数等值线：目标函数等值线：一组平行线一组平行线 目标函数值等于一个常目标函数值等于一个常数的解数的解如何对应？如何对应？31（1）用字母表示可行域；）用字母表示可行域；（2）画出目标函数的平行线；）画出目标函数的

16、平行线；（3） 注意目标函数的斜率；注意目标函数的斜率；（4）适当的说明语句（包括可行域、最优）适当的说明语句（包括可行域、最优解、目标函数值等）解、目标函数值等）32例例2、图解法、图解法 max z =40x1+ 80x2 x1+2x2 30 3x1+2x2 60 2x2 24 x1 , x2 0 0330z= 40 x1 + 80x2 =0 x1 + 2x2 =30dabcx2x1x(1)=(6,12) x(2)=(15,7.5)x= x(1)+(1- ) x(2) (0 1)求解求解最优解：最优解：bcbc线段线段b b点点c c点点无穷多解无穷多解34x1 =6 + +(1- )15

17、x2=12 + +(1- )7.5x1 =15-9 x2 =7.5+4.5 (0 1)x= = +(1- )max z =1200 x1 6 15 x2 12 7.535无界无界无有限最优解无有限最优解例例3、 max z =2x1+ 4x2 2x1+x2 8 8-2x1+x2 2x1 , x2 0 0z=0-2x1+ x2=28246x22x1+ x2=840x136例例4、 maxz=3x1+2x2 -x1 -x2 1 1x1 , x2 0 0无解无解无可行解无可行解-1x2-1x1037 唯一解唯一解 无穷多解无穷多解 无有限最优解无有限最优解 无可行解无可行解有解有解无解无解38ax=

18、b (1)x 0 (2)maxz=cx (3)概念：概念：1 1 可行解可行解?2 2 可行域可行域? 3 3 最优解最优解?3940414243vexcel规划求解规划求解solver的功能：可以解决的功能：可以解决线性规划、线性规划、01规划以及整数线性规划等规划以及整数线性规划等问题。问题。vexcel中安装好中安装好“规划求解规划求解”？v（菜单（菜单工具工具加载宏）加载宏）v线性问题、非线性问题，变量限制线性问题、非线性问题，变量限制200个，个，约束条件最多可达约束条件最多可达100个。个。 44451 在约束中使用的在约束中使用的运算符运算符有下列有下列5个：个： =大于等于大于

19、等于; int 整数整数; bin 二进制（二进制（0或或1）2 求解中用到下列概念：求解中用到下列概念： 目标单元格最大值（最小值）：指满足可变单元格约目标单元格最大值（最小值）：指满足可变单元格约束条件后，单元格可取的最大值（最小值）。束条件后，单元格可取的最大值（最小值）。3 可变单元格可变单元格（目标函数、变量和约束条件）（目标函数、变量和约束条件） 例如，问题中例如，问题中b1、d6、d7格由公式构成，分别对应格由公式构成，分别对应模型中的目标函数（如：模型中的目标函数（如：b1=b3*b5+c3*c5）和约）和约束条件；束条件；b5、c5为为“可变单元格可变单元格”，分别对应模型，

20、分别对应模型中的变量。中的变量。4 求解过程（见求解过程（见excel）4647软件求解下料优化问题软件求解下料优化问题4849llet s = fraction of the security systems project funded by hvclm = fraction of the market analysis project funded by hvc 50 51 5253l图解法灵敏度分析图解法灵敏度分析l灵敏度分析：计算机求解灵敏度分析：计算机求解l多于两个变量的情况多于两个变量的情况54l如果在计划实施前或实施中有些因素已发如果在计划实施前或实施中有些因素已发生了改变，则

21、决策者所关心的是目前所执生了改变，则决策者所关心的是目前所执行的计划还行的计划还是不是最优是不是最优？企业应当作出什？企业应当作出什么样的反应，运用灵敏度分析而么样的反应，运用灵敏度分析而不需建立不需建立新的模型。新的模型。l模型中模型中目标函数系数目标函数系数哪个更能影响最优解哪个更能影响最优解 。l约束条件的约束条件的右端值变化右端值变化对最优解的影响。对最优解的影响。55l模型参数是粗略的模型参数是粗略的估计值估计值 l获取所需数据必须付出许多的获取所需数据必须付出许多的时间与精力时间与精力l有些因素只有在研究完成后才能精确测量有些因素只有在研究完成后才能精确测量lwhat-ifwhat

22、-if分析表明改变这些决策对结果的分析表明改变这些决策对结果的影响，从而有效指导管理者作出影响，从而有效指导管理者作出最终决策最终决策56a（原材料消耗）（原材料消耗）代表企业的技术状况；代表企业的技术状况；b（资源供应量）（资源供应量）代表企业的资源状况；代表企业的资源状况；c（价值系数）（价值系数）代表企业产品的市场状况；代表企业产品的市场状况；在这些因素（原材料消耗系数、资源供应量、在这些因素（原材料消耗系数、资源供应量、价值系数）不变的情况下企业的最优生产计价值系数）不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值划和最大利润由线性规划的最优解和最优值决定。决定。在生

23、产计划问题的一般形式在生产计划问题的一般形式中，中，a，b，c各代表什么各代表什么标准型标准型 max z=cx ax = =b x 0如何回答？如何回答？57l模型参数是粗略的估计值模型参数是粗略的估计值 l获取所需数据必须付出许多的时间与精力获取所需数据必须付出许多的时间与精力l有些因素只有在研究完成后才能精确测量有些因素只有在研究完成后才能精确测量lwhat-ifwhat-if分析表明改变这些决策对结果的分析表明改变这些决策对结果的影响，从而有效指导管理者作出最终决策影响，从而有效指导管理者作出最终决策581. c(价格系数价格系数)变化的分析变化的分析: 最优条件最优条件 cbb-1a

24、 c 0.2.增加一个新变量增加一个新变量(例如新产品投产例如新产品投产)的分析的分析: 如果最优条件如果最优条件cbb-1pj - cj 0满足，不生产满足，不生产; 如果满足如果满足cbb-1pj - cj 0，新产品生产，新产品生产.3. b(资源量资源量)变化的分析变化的分析: 最优条件最优条件b-1b0.4. 增加一个新的约束条件的分析：增加一个新的约束条件的分析：最优解满足约束条件，则不变；最优解满足约束条件，则不变；最优解不满足约束条件，则用对偶单纯形法，最优解不满足约束条件，则用对偶单纯形法， 目标值变差。目标值变差。59标准型标准型 max z=cx ax = =b x 0(

25、1)、参数、参数a，b，c在什么范围内变动，对当在什么范围内变动，对当前方案无影响？前方案无影响？(2)、参数、参数a，b，c中的一个中的一个(几个几个)变动，对变动，对当前方案影响？当前方案影响？(3)、如果最优方案改变，如何用简便方法求、如果最优方案改变，如何用简便方法求新方案？新方案？60l递减成本（递减成本（cbb-1pj -cj）表示使目标函数中表示使目标函数中变量的值为正数时相应目标函数系数的改变变量的值为正数时相应目标函数系数的改变量（最大化问题是增加；最小化问题是减小）量（最大化问题是增加；最小化问题是减小）l当某个变量对应的当某个变量对应的递减成本递减成本0，表示含义？，表示

26、含义？l见见p70 例例3.4.1中图中图3-6的的d产品的递减成本为产品的递减成本为1.15003，表明，表明d的利润应增加的利润应增加1.15003元，元，d才能变为正值。才能变为正值。61经济解释：经济解释：w= yb =(y1 ym )b1bm= b1 y1 + b2 y2 + + bm ymbi ： 第第 i 种资源的数量种资源的数量yi ：对偶价格：对偶价格bi增加增加 bi , ,其它资源数量不变时其它资源数量不变时, ,目标函数目标函数的增量的增量 z=bi yiyi ：反映：反映bi 的边际效益的边际效益( (边际成本边际成本) )62l假设目标为假设目标为maxl对偶价格对

27、偶价格y （dual price）：）：b 的单位改变量的单位改变量所引起的目标函数改变量。所引起的目标函数改变量。l如果如果y的大小与系统内资源对目标的贡献有的大小与系统内资源对目标的贡献有关，是资源的一种估价，关，是资源的一种估价，又称为影子价格又称为影子价格。 63对偶价格的准确经济意义与建模有关。对偶价格的准确经济意义与建模有关。情况情况 模型中，目标函数系数模型中，目标函数系数ci 表示利润时，表示利润时， yi 不是真正的影子价格，只表示资源不是真正的影子价格，只表示资源bi 增加增加1 1单单位时，企业目标增加的净利润。位时，企业目标增加的净利润。情况情况 模型中，目标函数系数模

28、型中，目标函数系数ci 表示成本时，表示成本时， yi 是真正的影子价格。是真正的影子价格。64胜利家具厂生产桌子和椅子两种家具。桌子售价胜利家具厂生产桌子和椅子两种家具。桌子售价50元个，椅子售元个，椅子售价价30元个，生产桌子和椅子需要木工和油漆工两种工种。生产一元个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工个桌子需要木工4小时，油漆工小时，油漆工2小时。生产一个椅子需要木工小时。生产一个椅子需要木工3小小时，油漆工时，油漆工1小时。该厂每月可用木工工时为小时。该厂每月可用木工工时为120小时，油漆工工时小时，油漆工工时为为50小时。问该厂如何组织生产才能使每月的销售收

29、入最大？小时。问该厂如何组织生产才能使每月的销售收入最大？ 资源资源 单耗单耗 产品产品桌子桌子 椅子椅子资源限量资源限量 木工木工 4 3120小时小时 油漆工油漆工 2 1 50小时小时售价售价(元个元个)50 30 65l模型模型1 1：产品：产品a(a(桌子桌子) )，b(b(椅子椅子) )销售价格发生销售价格发生变化，最优解是否改变？变化，最优解是否改变？l模型模型3 3：如果家具厂木工资源可能发生变化，：如果家具厂木工资源可能发生变化，要使生产计划不变，问木工工时要使生产计划不变，问木工工时b1b1变化范围变化范围如何如何? ?l模型模型2 2：设计一种新产品柜子：设计一种新产品柜

30、子, , 售价售价100100元元, , 单耗木工单耗木工9 9工时、油漆工工时、油漆工3 3工时问是否投产工时问是否投产? ?l模型模型4 4：若增加约束：若增加约束: : 每月可用木材量是每月可用木材量是1010立立方米方米, , 桌子单耗桌子单耗0.40.4立方米立方米, ,椅子单耗椅子单耗0.30.3立方立方米。如何安排生产米。如何安排生产? ?l模型模型5 5：如果桌子价格降价：如果桌子价格降价1010，而椅子价格，而椅子价格上涨上涨1010，该问题的最优解是否发生变化？，该问题的最优解是否发生变化？66l对所有变化的目标函数系数，对所有变化的目标函数系数，允许的增允许的增量和允许的减量百分比之和未达到量和允许的减量百分比之和未达到100%100%，最优解就不会改变。最优解就不会改变。l模型模型5 5：如果桌子价格：如果桌子价格降价降价1010，而椅子而椅子价格价格上涨上涨10