运筹学2课件.ppt

对偶单纯形法 对偶单纯形法 对偶单纯形法 对偶单纯形法 对偶单纯形法 对偶单纯形法 对偶单纯形法 对偶单纯形法 本章小结 Chapter3 运输规划( Transportation Problem ) 运输规划问题的数学模型 例3.1 某公司从两个产地A1、A2将物品运往三个销地B1, B2, B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 运输规划问题的数学模型 解：产销平衡问题：总产量 = 总销量＝500 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表： 运输规划问题的数学模型 运输问题的一般形式：产销平衡 运输规划问题的数学模型 定理: 设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。 表上作业法 表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。 表上作业法 表上作业法 解：第1步 求初始方案 表上作业法 表上作业法 表上作业法 表上作业法 表上作业法 表上作业法 表上作业法 表上作业法 表上作业法 闭回路的概念 表上作业法 例下表中闭回路的变量集合是{x11,x12,x42,x43,x23,x25,x35, x31}共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。 表上作业法 闭回路 表上作业法 表上作业法 当存在非基变量的检验数?kl 0 且?kl =min{?ij}时，令Xkl 进基。从表中知可选X24进基。 表上作业法 表上作业法 表上作业法 表上作业法的计算步骤： 表上作业法 表上作业法 表上作业法 表上作业法 运输问题的应用 求极大值问题 目标函数求利润最大或营业额最大等问题。 运输问题的应用 求解方法： 将极大化问题转化为极小化问题。设极大化问题的运价表为C ，用一个较大的数M（M≥max{cij}）去减每一个cij得到矩阵C′，其中C′=（M－cij）≥0,将C′作为极小化问题的运价表，用表上用业法求出最优解。 运输问题的应用 例3.3 下列矩阵C是Ai（I=1，2，3）到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大. 运输问题的应用 运输问题的应用 产销不平衡的运输问题 当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。 运输问题的应用 由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地Bn+1， bn+1作为一个虚设销地Bn+1的销量(即库存量)。各产地Ai到Bn+1的运价为零，即Ci,n+1=0,（i=1，…，m）。则平衡问题的数学模型为： 运输问题的应用 当销大于产时，即： 运输问题的应用 运输问题的应用 例3.4 求下列表中极小化运输问题的最优解。 运输问题的应用 所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列 ，得到新的运价表。 运输问题的应用 下表为计算结果。可看出：产地A4还有20个单位没有运出。 运输问题的应用 3. 生产与储存问题 运输问题的应用 解： 设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那么应满足： 交货： x11 = 10 生产：x11 + x12 + x13 + x14 ≤ 25 x12 + x22 = 15 x22 + x23 + x24 ≤ 35 x13 + x23 + x33 = 25 x33 + x34 ≤ 30 x14 + x24 + x34 + x44 = 20 x44 ≤ 10 运输问题的应用 运输问题的应用 运输问题的应用 Chapter4 整数规划( Integer Programming ) 整数规划的特点及应用 整数规划（简称：IP） 要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规