第4讲 规划模型(一).ppt

1、优化问题和计划模型、优化问题(最大、最小、最大、最小等)。解决优化问题的数学方法：运营研究运营研究的主要领域：线性计划、非线性计划、动态计划、图形和网络分析、存储论、排队LUN、博弈论、决策理论。第一，1939年苏联数学家孔托洛维奇，1947年美国数学家乔治丹奇克、冯诺依曼提出了线性规划的一般模型和理论。案例一，用于家具生产的家具制造设备家具公司共使用450个工作时间，木材4立方米15个工作时间，0.2立方米木材价格80元。每把椅子10个工作时间，0.05立方木材的价格为45元。为了获得最大收益，应该如何安排生产？分析：1。你想要什么？生产多少张桌子？生产多少把椅子？2.优化什么？最高收入3。

2、约束？原料总劳动力，x1 x2max z=80 x 145 x20.2 x10.05 x24 15 x1 10 x 2450，模型I:以产值为目标实现最大收入。设定：生产表格x1，椅子x2，(决定变数)要最佳化的目标表示如下：max f=80 x145x22决策变量的约束(约束):0.2x1 0.05x24 15x110x2450，x1 0，x20，模型II。评估资源贡献，最小化“成本”投资，而不降低当前生产水平。(将在下一节中介绍)计划问题：在约束条件中查找目标函数的最佳值点。计划问题包括三个组件：“决策变量”(decision variable)“目标函数”(objective funct

3、ion)“约束条件”(constraint)。如果目标函数和约束条件都是决定变量的线性函数，则称为线性编程问题，否则称为非线性编程问题。线性程序设计问题解决方法1，图形方法： (两个变量的线性程序设计问题解决方案)在平面上绘制可行域(凸多边形)，比较每个极点(多边形顶点)上目标函数的值，然后计算出最高值点作为最佳解决方案。、凸集(Convex set)、凸集、(如果连接至集中两点的线都属于该集，则称为凸集)如果是凸集，并且只对应于随机实数和随机数字，则“极点”(Extreme point)称为凸集，如果X不能表示为k上两个不同点的凸组合，则称为凸集，X是凸集k的极值点。x不能是k的一个线段的内

4、部点，只能是k的一个线段的端点。o，命题1线性规划问题的可行解集为凸集可执行解集：线性不等式组的解(可执行域)，0.2x1 0.05x2=4，15x1 10 x2=450，可执行解：满足约束的解。绿色区域中的每个点(包括边界点)都是可行的解决方案。此区域是方案1中线性编程问题(可行的解决方案域)的解决方案集合。可行域，命题2线性规划问题的目标函数不同的目标值是描述线距原点的距离的一系列平行线，目标值的大小，案例1的目标函数Z=80 x1 45x2是此坐标平面中Z作为参数，-16/9为斜率的一系列平行线：同一直线上的点，“等值线”z值越小，直线沿法线方向向右上方移动。如果移动到c，则z值最大化到

5、可行域的边界。最佳解决方案(14，24)，Z=2200。最佳生产方案：台生产14张，椅子生产24张，最大利润2200元(最佳值)。，c，命题3线性规划问题的最优解必须在可能解集的极值点实现(在可行域的目标直线组中，离原点最远(或最近)的直线通过的凸多边形的顶点)。2，单纯形法：确定约束方程的基本解，计算相应的目标函数值，从可能解集的极点检索最优解。以统一的标准形式建模线性编程，以便用简单的方法解决线性编程问题。线性编程问题的标准型为： 1目标函数，最大(或最小)2约束为方程3变量XJ非负4常量bi非负线性编程标准(Standard form of LP)，模型的标准化决策变量： x1，x2，X

6、n。目标函数3360 Z=c1x1 c2x2 cnxn。约束： a11a1 nxnb1，am 1x1 amnxn BM，模型标准化10。引入平滑变量以将不平等约束更改为等式约束如果存在ai1x1 ainxbi，则引入xn I 0；如果存在Ai 1x1 ainxn I=bi aj1x1 ajnxnbj，则引入xn j 0以引入aj 1x1 ajpn xn-xn j=bj。和z=c 1x1 c2x2 cnxn 0 xn 1 xn m，20。用目标函数的最大化替换目标函数的优化。如果找到min Z并输入Z=Z，则问题为max Z. 30。引入了手动变量，以便所有变量都为负数。如果Xi没有非负条件，则

7、引入Xi 0和xi0，使用xi=Xi Xi可以使问题中的所有变量都变为非负。标准化模型会寻找变数x1，X2，xn，maxz=c 1x1cnxn，s.t.a11a1nxn=B1，am1x1xn=BM，X10，xn 0，是因为标准要求非负变量，所以(2)第一个约束条件是编号，在左端添加宽松变量(宽松变量)x4，x40，使其成为等式。(4)第三个约束条件为数字，常数为负数，因此在左侧添加平滑变量X6，X60，两边乘以1。(5)目标函数为最小值。要获得Z=Z的最大值，请获取max Z=Z。也就是说，当z达到最小值时，z达到最大值，反之亦然。(3)第二个约束是左端减去其馀变量x5，x50的数字。也称为松

8、弛变量，当存在xj0变量时，合并创建x/j=xj的以下标准类型：如果约束是绝对值不等式，则将绝对值不等式变为两个不等式(例如，约束、转换为两个不等式、将松弛变量添加为等式)。示例线性编程为标准形式，然后解决方案的核心是从目标函数中删除绝对值。线性规划的标准形式，标准LP问题的单纯形法的基本思想，在确定初始基本可执行解决方案是否为最优解决方案的情况下结束。否则，请寻找相邻的可改进基础解决方案。再次确定此解决方案是否最佳后，就结束了。否则，请寻找预设最佳解决方案，或寻找相邻且增强的预设可执行解决方案，直到问题无法解决。，单纯形法需要解决的三个问题：(1)如何确定初始基本可行解？(2)解的最优判别方

9、法？(3)如何找到改进的基本可行解决方案？如果将n个变量m个约束的标准LP中的n m变量指定为0，则将在约束条件中解决剩馀m个变量的非唯一非负解决方案。此时，该线性编程的可行解决方案称为该LP的基本可行解决方案。上述n-m变量称为自由变量，其馀m变量称为基本变量，基本在矩阵学习后详细介绍了使用单纯形方法解决线性编程问题的具体步骤。3、使用MATLAB软件解决线性规划问题，解决线性规划问题的方法包括图形方法、单纯形方法、矩阵方法等。但是，如果决策变量数量大，解决过程复杂，则使用MATLAB软件解决线性编程问题会更简单。用于解决线性编程问题的MATLAB命令、X=linprog(f，A，b)、LP

10、故障排除、命令格式、命令函数linprog () x，fval=linprog (f，A，)函数说明(1)、f、A、X、b、线性编程的不等式约束、aeq、Beq、线性编程的等式约束、由目标函数从中获取极值的决定变量组成的列矢量、矩阵、矢量、矢量、由目标函数的系数组成的矢量、ll 优化结束后获得的目标函数值，由目标函数的系数组成的向量，线性编程的不等式约束，矩阵，向量，控制计划过程的参数系列，变量的初始值， 在此示例中，如果存在约束LB，则后面的参数可能未给定也可能未声明，但是，即使未给出等式约束等，LB前面的参数也必须声明为null矩阵，不能省略。函数说明，(3)返回值exitflag有三个方

11、案：exitflag=1表示优化结果不收敛。Exitflag=1时，变量在优化过程中收敛到解决方案x。Exitflag=0表示优化结果超过了函数的预期值或声明的最大迭代数。(4)返回值output有三个组件，iterations表示优化过程中的迭代数，cgiterations表示PCG迭代数，algorithm表示优化采用的计算规则。函数说明，(5)返回值lambda有四个分量，行qlin是线性不等式约束，eqlin是线性等式约束，upper是变量的上限约束，lower是变量的下限约会条件。它们的返回值分别指示其约束在优化过程中是否有效，如本示例所示，在三个不等式约束中，后者是合适的。(6)如

12、果线性规划问题没有解决方法，则警告： the constraints are overly stringent；There is no feasible solution。如果优化成功，则为：optimization terminated successfully，函数说明，方案2(生产计划中的问题)如果工厂知道在计划期间生产，计划两种产品，生产单位产品所需的设备，则a，b这两种原材料的消耗以及每种产品可以获得的收益如下表所示。如何制定使工厂最有利可图的计划？返回，使用MATLAB解决案例2中生产计划的LP问题，解决原始LP问题，MATLAB命令的标准外观是查找目标函数的最小值。通常，通过将m

13、axf转换为min-f以编程方式解决。原始问题转换为并输入到MATLAB中，clear，f=-2，3；A=1，2；4，0；0，4；B=8，16，12；lb=0，0；x，fval=linprog (f，a，b，lb)，enter键，显示最佳解决方案和目标函数最佳值，优化terminated successfully，x=，4.0000，案例3(营养配餐问题)假设一个成年人每天需要从食物中摄取3000卡路里，55克蛋白质和800毫克钙。如果市场上只有4种食物，包括每公斤热量、营养成分和市场价格，如下表所示。在满足营养的前提下，试着建立最小化食品购买费用的数学模型。返回并使用MATLAB解决案例3中

14、的线性编程问题。解决方案原始LP模型，在MATLAB中输入，clear，f=10，6，3，2；A=-10，-8，-9，-2；-5，-6，-2，-1；-4，-2，-3，-5；B=-30、-5.5、-8；lb=0，0，0，0；x，fval=linprog (f，a，b，lb)，显示最佳解决方案和目标函数最佳值，优化terminated successfully，x=，0.0000，0.0000因此，为了满足营养要求，并将食品购买成本降至最低，必须购买3.3333公斤大米。案例4(投资问题)一家公司拥有四项专案投资的资金，投资于每个专案的净收益为：出于某种原因，对项目a的投资不大于其他投资的总和，对项目b和c的投资大于项目d的投资。试着建立那个公司收益最大的投资分配计划的数学模型。返回并使用MATLAB解决案例4中的投资问题。x1、x2、x3和x4分别表示项目a、b、c和d的投资百分比时，投资问题的数学模型为MAT