物流运筹学-线性规划.ppt
第二章 线性规划,线性规划问题及其数学模型线性规划模型的求解线性规划对偶问题与灵敏度分析线性规划在物流管理中的应用,学习目标,知识目标掌握线性规划的基本形式及标准形式；掌握单纯形法计算过程；理解对偶问题；掌握对偶问题的求法及性质；了解灵敏度分析。技能目标能够结合实际情况建立线性规划的模型，并可利用单纯形法求解。,第一节 线性规划问题及其数学模型,问题的提出线性规划问题的标准形式,问题的提出,【例2-1】某企业要将产品包装成、两种规格，需要A、B两种原材料的数量、获利情况及两种材料数量限制见表2-1，两种规格的产品各包装多少件可获利最多？,表2-1,上面两个例子的共同特征：（1）每一个问题都由一组决策变量来表示某一方案，一般情况下这些变量的取值是非负且连续的。（2）存在一定的约束条件，这些约束条件可以用一组线性的等式或不等式来表示。（3）都有一个要求达到的目标，它用决策变量的线性函数（称为目标函数）来表示。按照具体问题的不同，要求目标实现最小或最大。,求取一组变量，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划（LP）。决策变量、约束条件和目标函数是其三个基本要素。,线性规划定义,线性规划问题的标准形式,第二节 线性规划模型的求解,图解法 单纯形法,满足所有约束条件的向量称为线性规划问题的可行解所有可行解构成的集合称为可行域。在可行域中使得目标函数值最大（或最小）的可行解，称为线性规划问题的最优解。最优解的全体称为最优解集合。最优解对应的目标函数值称为最优值。,图解法,线性规划解的可能情况,唯一最优解 无穷多最优解无界解无可行解,单纯形法,单纯形法的基本原理：寻找一种规则，从一个基可行解转移到另一个基可行解，目标函数值是增大的，即“顶点转换，目标上升”。,对矩阵,作初等变换：,单纯形法的计算步骤,解 初始单纯形表,得到新的单纯形表,得到新的单纯形表,第三节 线性规划对偶问题与 灵敏度分析,对偶问题的提出对偶问题的基本性质 灵敏度分析,对偶问题的提出,一般称这个线性规划问题为例2-1线性规划问题的对偶问题，例2-1称为原问题。,表2-6 原问题与对偶问题的对应关系,对偶问题的基本性质,对偶问题最优解的经济解释：影子价格。线性规划问题中，当某资源增加一个单位而其他资源都不变时，所引起目标函数最优值的增量称为资源的影子价格。影子价格是对资源在生产中作出的贡献而做的估价。,灵敏度分析,目标函数的灵敏度分析约束右端向量的灵敏度分析 约束方程系数的灵敏度分析增加一个新变量的灵敏度分析增加一个约束的灵敏度分析,第四节 线性规划在物流管理中的应用,直接应用物资配送、调运，人员的分配物流中心选址问题配送系统的重新安排项目投资等,间接应用 整数规划中的割平面法和分支定界法 运输问题中的表上作业法,本章小结,本章首先结合具体示例介绍了线性规划问题及其模型结构、线性规划的标准模型、一般线性规划模型向标准型转换的方法，接着定义了线性规划可行解、最优解的概念，重点阐述了求解线性规划的一般方法单纯形方法，给出了单纯形方法的具体求解步骤。之后，介绍了线性规划的对偶问题以及与原问题关系，阐释了对偶问题的基本性质，相应地给出了求解线性规划问题的对偶单纯形方法。并简单讨论了目标函数系数向量、约束矩阵以及约束右端项的变化给线性规划最优解带来的影响。最后，介绍了线性规划在物流领域中的典型应用。本章的重点和难点是实际物流问题的线性规划建模以及求解线性规划的单纯形方法。,案例分析,A公司分拨物流网络负责把下线产品经过配送中心发送到客户手中，包括了原材料采购、生产、运输、仓储和配送，除一些偏远地区外，该公司建立了非常完善的物流配送系统，A公司的物流运输途径大部分都采用航空运输。现在，该公司接到四类货物的配送要求，信息见表2-13。,以A公司在实际工作中，优化其现有配送资源为例，给出线性规划模型，说明线性规划的实际应用情况。,表2-13 案例相关数据,问题分析,负责运输产品的飞机有前仓、中仓和后仓三个货舱。各自所能装载的货物最大重量和体积都有限制，且为了保持飞机的平衡，三个货舱中实际装载货物的重量必须与其最大允许重量成比例。该公司为了既满足货机本身的限制，又能获得最大利润，建立了下面的模型：,问题（1）航空运输规划时考虑的因素、目标和约 束条件的限制有哪些？（2）案例中建模的过程是怎样的？（3）如何对上述建模进一步改进？,实训,实训目标 掌握线性规划模型的建立和单纯形法 实训内容与要求 要求了解企业经常遇到资源、设备等的分配问题。在分配时，用数学语言描述各种限制条件并建立相应的线性规划模型，利用单纯形法求解，给出最优的分配方案。成果与检验 能够建立相应的线性问题模型，利用单纯形法求解，得出最优分配方案。,某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台数及A、B两种原材料的消耗量，见表2-11。该工厂每生产一单位产品可获利润2元，每生产一单位产品可获利润3元，问应如何安排生产使该工厂获得的利润最大？,表2-14 实训相关数据,
