系统工程---第三章 线性规划.ppt

第三章 线性规划 LP问题的数学模型 LP问题的图解法 LP问题的标准型及其解的概念 单纯形法 对偶理论 灵敏度分析 运输问题 3.1 线性规划及其数学模型 3.1.1 线性规划简介 3.1.2 线性规划的数学模型 小结 作业 3.1 线性规划及其数学模型 运筹学中应用最广泛的方法之一 运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的 解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大 简介 历史悠久 理论成熟 应用广泛 简介 历史悠久 理论成熟 应用广泛 简介 历史悠久 理论成熟 应用广泛 简介 历史悠久 理论成熟 应用广泛 研究对象 给定一定的人力、财力、资源条件下，如何合理安排使用这些资源，使完成的任务最多或效益最高？ 给定任务的前提下，如何安排人、财、物，使得既完成任务，又使资源最省？ （1）线性规划模型特点 决策变量： x1， … ， xn 决策人要考虑和控制的因素且非负 约束条件：线性等式或不等式 目标函数：?=?(x1 … xn) 线性式，求?最大或最小值。 （4）隐含的假设 比例性：决策变量变化引起目标的改变量与决策变量改变量成正比 可加性：每个决策变量对目标和约束的影响独立于其它变量 连续性：每个决策变量取连续值 确定性：线性规划中的参数aij , bi , ci为确定值 小结 线性规划模型就是求一组非负变量在满足一系列线性等式或线性不等式的条件下，使线性目标目标函数取得最大值或最小值。 线性规划模型可以表示为： 3.2 线性规划图解法 小结： §3.3 线性规划问题的标准型及解的概念 §3.3.1 线性规划问题的标准型 §3.3.1 线性规划问题的标准型 §3.3.1 线性规划问题的标准型 线性规划问题解的概念之间的关系 本节课的重点是线性规划模型的标准化 2. 单纯型表及其格式 3.单纯形法的主要步骤 设第 l 行使 ? 最小，则第 l 行对应的基变量x l称为换出变量，第 l 行称为主元行 迭代过程 主元行 l 行与主元列 k 列相交的元素alk 称为主元，迭代以主元为中心进行 迭代的实质是线性变换，即要将主元 alk变为1，主列上其它元素变为0。 例1 用单纯形法求解下列LP问题 标准化 建立初始单纯形表 第一步迭代 第二步迭代 第三步迭代 例2 用单纯形法求解下列LP问题 用单纯形法求解下列LP问题 3.6 线性规划问题的对偶理论 3.6.1 线性规划的对偶问题 3.6.2 对偶问题的基本性质 3.6.3 对偶问题的经济意义 3.6.4 对偶单纯形法 小结 作业 3.6.1 线性规划的对偶问题 一、原问题与对偶问题 例1、某厂在计划期内要安排生产A、B两种产品，这两种产品分别需要在甲、乙丙三种不同的设备上加工，有关数据如表3-14所示。问应如何安排生产计划才能使利润最大？ 该问题的数学模型 设A、B两种产品的产量分别为x1, x2 ,则这个问题可以归结为求解下列线性规划问题： 设 y1, y2, y3分别表示设备甲、乙、丙每台时的加工费（或租金）,则 对称的对偶问题 原问题 对偶问题 非对称的对偶问题 原问题 对偶问题 混合形式的对偶问题 原问题和对偶问题的关系 二、对偶问题的基本性质 6.若原问题的最优解为XB = B-1b，则对偶问题的最优解为Y=CBB-1. 例3 已知线性规划问题 三、对偶解的经济涵义——影子价格 1.影子价格的定义 2.影子价格的求法例4 3.影子价格的作用 四、对偶单纯形法 3.8 运输问题 3.8.1 运输问题的提出 3.8.2 产销平衡运输问题的数学模型 3.8.3 产销平衡运输问题的求解方法 3.8.4 产销不平衡的运输问题 3.8.5 运输问题的应用和推广 小结 作业 3.8 运输问题 例：有一家罐头厂，下设甲、乙、丙三个分厂，向A、B、C三个地区供应其产品，其数据如下表所示。问如何调运才能使总运费最少？ 3.8 运输问题 已知:有m个生产地Ai（i=1,2,…,m），可供应某种物资其供应量（产量）分别为ai（i=1,2,…,m）。 另有n个销地Bj， （j=1,2,…,n），需要该物资其需要量分别为bj （j=1,2,…,n）.从Ai到Bj运输单位物资的运价为cij， （i=1,2,…,m;j=1,2,…,n）。 问：产销平衡的条件下，如何组织调运，才能使总运费最小？ 3.8 运输问题 产销平衡表 运价表 运输问题的数据表（运输表） 设 xij表示从Ai运输到Bj的物资的数量，i=1,2,…,m；j=1,2,…,n。 运输问题数学模型的特