运筹学运输问题PPT课件

.第五章运输和分配问题、运输问题的表达运输问题模型、运单运输问题的解决表操作法分配问题、运输、分配和运输问题实际上可以用l.p .模型来说明，因此可以认为是l.p .的特殊单列，原因是应用面很广，实用性很强，正在开发解决这种模型的特殊有效方法。了解运输的风格化方法，简要说明，问题，A1、A2、A3三座砖厂月产量14，27，19万件，供应B1、B2、B3、B4个站点，月需求量22，13，13万韩元，一万件运费最低要求的方案。运输问题、运输问题的线性编程模型、供给地点约束、需求和约束、3.1运输问题模型和性质1、运输问题的数学模型1、运输问题的一般提到：某种物资有多个产地和销售地点，目前需要从各个产地将此物资运输到各个销售地点，总产量等于总销售量。询问如何组织各产地的产量和各销售地的销售量，以及各生产地到各生产地的单位运费(或运输距离)，以便最大限度地减少总运费(或总运输)。运输问题的一般数学模型，特定料号的m个产地国生产，该料号的n个区域需求a1，a2，am表示每个原产地生产，B1，B2，bn表示每个销售地区的销售，bj表示生产和市场平衡集xij表示原产地I运输到销售地区j的物资数量，cij表示相应的单位运费。运输问题的数学模型如下：运输问题，第二，运输问题的特点和特点1。约束方程的系数矩阵具有特殊结构写(3-1)的系数矩阵a，其中矩阵的元素为1或0。每列只有1的两个元素，其馀元素为0。热向量pij=(0，0，1，0，0，1，0，0) T .其中两个元素1分别位于I行和m j行中。第三，运输问题解决方法，1，单纯形法(为什么？2、由于表格工作方法问题的特殊形式，表格工作方法更简洁方便，3.2运输问题的表格工作方法1、表格工作方法的基本思路是：先提供初始计划，然后根据决定标准检查、调整、改进初始计划，如图3-1所示。表控制法和单纯形法的解法一致，但具体方法更加简单。图3-1运输问题解决思路图，第二，初始方案决策1，操作表(生产和营销资产负债表)初始方案是初始基本可执行解决方案。将有关运输问题的信息表和决策变量运输量结合起来构成“工作表”(生产和营销资产负债表)。表3-3是两个产地，三个销售地的运输问题操作表。表3-3运输问题操作表，3，实例3-2 a，b参考两个煤矿供应a、b、c三个城市煤炭，每个煤矿产量和每个城市的煤炭需求，每个煤矿到城市的运输距离表3-4，以最小化总运输量的运输计划。表3-4示例3-2信息表，示例3-2的数学模型，初始解决方案的确定，1，最小系数方法j=1，2，3，4，minz=aijxij (AIJ -效率)，i=1j=1，44，I作业与j个人合作完成后，I项目与j个人合作完成.nxij=1，i=1，2，nxij=1或0，58，匈牙利解决方案，标准分配问题是一种特殊的0-1整数规划问题类型，可以通过多种适当的解决方案解决。但是，这些方法都没有充分利用分配问题的特殊特性，从而有效地减少计算量。1955年，库恩(W.W.Kuhn)利用匈牙利数学家康尼格(D.Knig)矩阵内独立零元素的定理，提出了分配问题的解法，习惯上称之为匈牙利的解法。，59，匈牙利解决方案的核心是利用分配问题最优解决方案的特性。通过从分配问题的系数矩阵C=(cij)nn的行(或行)中分别减去常数k得出新的系数矩阵C=(cij)，具有系数矩阵C和C 的两个分配问题存在相同的最优解。匈牙利解决方案，60，步骤1:转换系数矩阵。允许每行和列至少包含一个没有负元素的零元素。第2步：确定试点分配，即独立的零因素。步骤3:继续转换系数矩阵并返回步骤2。匈牙利解决方案的一般阶段，61，以上示例说明阶段，215134041415914161378119，01311201011057402497，2497，min，(cij)=，匈牙利分配问题，64，匈牙利解决方案一般步骤上方的示例说明步骤，0001001000010，(xij)=，分配问题如果独立零元素(包括圆零元素)小于n，则意味着还不能确定最佳分配方案。需要一组直线来确定可以复盖所有零元素的最小直线数。分配问题(assignmentproblem)，68，匈牙利解决方案的一般步骤是对不包含零元素的行重复：所有播放，对编号行中包含零元素的所有列重复。然后，数字对指定列中有零元素的行重复。重复2)和3)，直到再也找不到弧或列为止；要创建能复盖所有零元素的最少的直线，请为没有的行绘制水平线，并在有的列上绘制垂直线。指定问题，69，匈牙利解决方案的一般步骤，500223000105298004006365，7300此方法是寻找未被线复盖的元素中最小的元素。然后从播放编号行的每个元素中减去此最小元素，以确保原始零元素没有更改。这会产生新的系数矩阵(最佳解决方案与原始问题相同)。得到n个单独的零元素是最佳解决方案。否则，重复此步骤以继续转换系数矩阵。分配问题，71，匈牙利解决方案的一般阶段，500223000105298004006365，一般的处理方法是先转换为标准形式，然后用匈牙利法求解。设置最大分配问题最大分配问题系数矩阵C=(cij)。其中最大元素是m。使用矩阵B=(bij)=(m-cij)，系数矩阵B的最小化分配问题和系数矩阵c的最大化分配问题的最佳解决方案相同。人数和天数分配问题如果人数少，则添加成本系数为零的虚拟“人”；如果人数少，则添加成本系数为零的虚拟“天”。非标准格式设置问题，75，非标准格式设置问题，一个人可以做一些工作的分配问题，如果个人可以做一些工作，则将该人改为多个“人”以接受分配。这些“人”做同样的事情的成本系数当然也是一样的。某个人不能做的指定问题如果某件事一定不能由其他人做，那么可以将相应的成本系数充分导入m。非标准形式的分配问题，非标准分配问题；例如，分配4个a、b、c和d以完成5个任务，每个任务完成时间如下表所示。针对以下要求单独解决分配：1)每个人1个2个，其他1个3) d由于某种原因1个1个，其他1个，e 1个，1个1个，2) 1个1个，2个1个，其他1个，3) d是什么样的Operational/Op