物流运筹学-线性规划.ppt

《物流运筹学-线性规划.ppt》由会员分享，可在线阅读，更多相关《物流运筹学-线性规划.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章 线性规划线性规划线性规划问题及其数学模型线性规划问题及其数学模型线性规划模型的求解线性规划模型的求解线性规划对偶问题与灵敏度分析线性规划对偶问题与灵敏度分析线性规划在物流管理中的应用线性规划在物流管理中的应用学习目标知识目标知识目标l掌握线性规划的基本形式及标准形式；l掌握单纯形法计算过程；l理解对偶问题；l掌握对偶问题的求法及性质；l了解灵敏度分析。技能目标技能目标l能够结合实际情况建立线性规划的模型，并可利用单纯形法求解。第一节 线性规划问题及其数学模型l问题的提出l线性规划问题的标准形式 问题的提出【例2-1】某企业要将产品包装成、两种规格，需要A、B两种原材料的数量、获利

2、情况及两种材料数量限制见表2-1，两种规格的产品各包装多少件可获利最多？表表2-1 产品规格AB利润/（元/件）4212519材料限制208上面两个例子的共同特征：（1）每一个问题都由一组决策变量来表示某一方案，一般情况下这些变量的取值是非负且连续的。（2）存在一定的约束条件，这些约束条件可以用一组线性的等式或不等式来表示。（3）都有一个要求达到的目标，它用决策变量的线性函数（称为目标函数）来表示。按照具体问题的不同，要求目标实现最小或最大。求取一组变量，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划（LP）。决策变量、约束

3、条件和目标函数是其三个基本要素。线性规划定义线性规划问题的标准形式 第二节 线性规划模型的求解l图解法 l单纯形法 满足所有约束条件的向量称为线性规划问题的可行解所有可行解构成的集合称为可行域。在可行域中使得目标函数值最大（或最小）的可行解，称为线性规划问题的最优解。最优解的全体称为最优解集合。最优解对应的目标函数值称为最优值。图解法图解法线性规划解的可能情况l唯一最优解 l无穷多最优解l无界解l无可行解 单单纯纯形形法法单纯形法的基本原理：寻找一种规则，从一个基可行解转移到另一个基可行解，目标函数值是增大的，即“顶点转换，目标上升”。对矩阵作初等变换：单纯形法的计算步骤单纯形法的计算步骤解解

4、 初始单纯形表初始单纯形表得到新的单纯形表得到新的单纯形表得到新的单纯形表得到新的单纯形表第三节 线性规划对偶问题与 灵敏度分析l对偶问题的提出l对偶问题的基本性质 l灵敏度分析对偶问题的提出对偶问题的提出一般称这个线性规划问题为例2-1线性规划问题的对偶问题对偶问题，例2-1称为原问题原问题。表表2-6 原问题与对偶问题的对应关系原问题与对偶问题的对应关系对偶问题的基本性质对偶问题的基本性质对偶问题最优解的经济解释：影子价格。线性规划问题中，当某资源增加一个单位而其他资源都不变时，所引起目标函数最优值的增量称为资源的影子价格。影子价格是对资源在生产中作出的贡献而做的估价。灵敏度分析灵敏度分析

5、目标函数的灵敏度分析约束右端向量的灵敏度分析 约束方程系数的灵敏度分析增加一个新变量的灵敏度分析增加一个约束的灵敏度分析 第四节 线性规划在物流管理中的应用直接应用l物资配送、调运，人员的分配l物流中心选址问题l配送系统的重新安排l项目投资等间接应用l l 整数规划中的割平面法和分支定界法l l 运输问题中的表上作业法本章小结l本章首先结合具体示例介绍了线性规划问题及其模型结构、线性规划的标准模型、一般线性规划模型向标准型转换的方法，接着定义了线性规划可行解、最优解的概念，重点阐述了求解线性规划的一般方法单纯形方法，给出了单纯形方法的具体求解步骤。之后，介绍了线性规划的对偶问题以及与原问题关系

6、，阐释了对偶问题的基本性质，相应地给出了求解线性规划问题的对偶单纯形方法。并简单讨论了目标函数系数向量、约束矩阵以及约束右端项的变化给线性规划最优解带来的影响。最后，介绍了线性规划在物流领域中的典型应用。l本章的重点和难点是实际物流问题的线性规划建模以及求解线性规划的单纯形方法。案例分析A公司分拨物流网络负责把下线产品经过配送中心发送到客户手中，包括了原材料采购、生产、运输、仓储和配送，除一些偏远地区外，该公司建立了非常完善的物流配送系统，A公司的物流运输途径大部分都采用航空运输。现在，该公司接到四类货物的配送要求，信息见表2-13。以A公司在实际工作中，优化其现有配送资源为例，给出线性规划模

7、型，说明线性规划的实际应用情况。重量/吨空间/（立方米/吨）利润/（元/吨）货物1184803100货物2156503800货物3235803500货物4123902850表表2-13 案例相关数据案例相关数据问题分析 负责运输产品的飞机有前仓、中仓和后仓三个货舱。各自所能装载的货物最大重量和体积都有限制，且为了保持飞机的平衡，三个货舱中实际装载货物的重量必须与其最大允许重量成比例。该公司为了既满足货机本身的限制，又能获得最大利润，建立了下面的模型：问题问题（1）航空运输规划时考虑的因素、目标和约 束条件的限制有哪些？（2）案例中建模的过程是怎样的？（3）如何对上述建模进一步改进？实训 实训目

8、标实训目标 掌握线性规划模型的建立和单纯形法 实训内容与要求实训内容与要求 要求了解企业经常遇到资源、设备等的分配问题。在分配时，用数学语言描述各种限制条件并建立相应的线性规划模型，利用单纯形法求解，给出最优的分配方案。成果与检验成果与检验 能够建立相应的线性问题模型，利用单纯形法求解，得出最优分配方案。某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台数及A、B两种原材料的消耗量，见表2-11。该工厂每生产一单位产品可获利润2元，每生产一单位产品可获利润3元，问应如何安排生产使该工厂获得的利润最大？资源限量设备/台时)128原材料A/千克4016原材料B/千克0412表表2-14 实训相关数据实训相关数据