第3章 特殊类型的线性规划22.pptxVIP

第三章 特殊类型的线性规划;一般意义的线性规划问题;第一节 运输问题;先看一个具体的例子——例3-1;先建立数学模型;该问题数学模型的特点;;本例中，工厂的产量与门市部的销量相等，称为产销平衡的运输问题。;;例3-3;求解该问题分三个步骤;确定初始方案的方法之一 西北角法;在逐步确定初始运输方案时，一般每步要经过两个过程，先是根据运输费用确定供应关系，然后根据供需要求进行运量分配。为了方便，将产销平衡与运输费用表拆成运输费用与运量分配表。 ; 交通吸引点 交通发生点; 交通吸引点 交通发生点; 交通吸引点 交通发生点; 交通吸引点 交通发生点; 交通吸引点 交通发生点; 交通吸引点 交通发生点; 交通吸引点 交通发生点;　最小元素法的基本思想是就近供应，即依据单位运价表中最小的运价来确定供需关系。 ; 交通吸引点 交通发生点;最优方案的判别; 在原方案的分配表中，从一个空格开始作一条闭回路，这个闭回路的边只能是水平或垂直的；而它的转角，除了开始这个空格之外，其余的都是填有数字的格（有交通量的格）。; 交通吸引点 交通发生点;根据闭回路求检验数; 交通吸引点 交通发生点;得到如下的检验数表：;;方案的调整;步骤三 方案的调整;步骤三 方案的调整;对新得到的分配方案，继续进行检验。;步骤三 方案的调整;对新得到的分配方案，继续进行检验。;运输问题的作业;工程中有些线性规划问题要求解为整数 如： 以人员、车辆等规划对象 原有的计算方法得到的解存在非整数的可能;求解整数规划的方法—分枝定界法;先不考虑整数约束，解相应的线性规划问题 为了讨论方便，将原线性规划问题称为L1。;L1的最优解为x1=2.25，x2=3.75不满足整数条件;L2的最优解为x1=1.8，x2=4，Z=41;L2的最优解为x1=1.8，x2=4不满足整数条件;L4的最优解为x1=1，x2=4.44，Z=40.444;L4的最优解为x1=1，x2=4.44不满足整数条件;L6的最优解为x1=1，x2=4，Z=37;;总结：;整数??划作业;0-1整数规划;例3-5;建立模型;0-1规划的一般形式;0-1规划的求解方法——穷举法;设计一种方法，只要检查变量取值的一部分就能得到原问题的最优解。 这种方法称为隐枚举法。;例3-6;;新的0-1规划问题为;全部枚举的方法，3个变量有8种组合 原先4个约束方程，需要32次计算 增加过滤条件后，可减少计算次数;0-1规划作业;第三节 资源分配问题; 目的地 车辆编号;建立数学模型;资源分配问题的一般模型;;资源分配问题的求解方法—匈牙利法;匈牙利法的指导思想;匈牙利法的解题步骤——例3-8;使费用矩阵每行中出现零元素; 1 1 0 6 2 0 3 1 2 7 0 6 0 8 3 5 3 1 2 0 5;检验是否存在位于不同行不同列的n个0元素;检验是否存在不同行列的0元素;方案的变换;方案变换;方案变换;对新的费用矩阵进行行检验与列检验;已经得到了位于不同行不同列的n个0元素（独立零元素）;效益最大化的资源分配问题;例3-9;解;将极大化的资源分配问题转化为新费用矩阵下的极小化资源分配问题;资源分配问题作业