运筹学第1章线性规划(2015.8)详解.pptVIP

OR课件 LP 不可行解 例1.6 某LP问题的可行域如下图： 若目标为MaxZ时： 无解（无界解） MaxZ 若目标为MinZ时： 唯一最优解（0） MinS 无解（无可行解） §4 LP问题图 解 法 可能出现的情况： 可行域是空集 可行域无界无最优解 最优解存在且唯一，则一定在顶点上达到（称为唯一最优解） 最优解存在且不唯一，且在可行域的两个顶点上同时达到，则两顶点连线上的点都是该问题的最优解（多重解或多重最优解） OR课件 LP 统称为无解 §4 LP问题图 解 法 OR课件 LP 局限性：仅能求解两个变量的LP问题 重要启示： （1）LP问题的最优解一定在可行域的顶点上达到； （2）可行域中顶点的转移实现了数学迭代，顶点的转移使得目标函数值上升或下降。 －－单纯形法的基本原理和基本思想 §4 LP问题图 解 法 图解法小结 OR课件 运 筹 帷 幄 之 中 决 胜 千 里 之 外 线性规划基础 （第1章） Linear Programming-----LP 重点 掌握什么样的问题是线性规划问题，即线性规划问题的数学模型的特点、标准型的建立和图解法的基本思想。 难点 线性规划问题解的概念和标准型的转化。 OR课件 导 学-----重点与难点 § 1 LP问题及其数学模型 § 2 LP的标准型及其转化 § 3 LP解的概念 § 4 LP的图解法 OR课件 导 学-----主要内容 §1LP问题及其数学模型 线性规划实例 生产计划问题 运输问题 线性规划模型 模型特征 建模步骤 OR课件 LP 例1、某工厂生产A、B两种产品，都需使用铜和铝两种金属材料，有关资料如下表所示。问如何确定A,B产品的产量，使工厂获取的总利润最大？ 原 料 A产品单耗（吨） B产品单耗（吨） 原料可用量 （吨） 铜 2 1 40 铝 1 3 30 单位产品的利润（万元） 3 4 OR课件 LP x1 x2 利润（Z）=3x1 + 4x2 ≤ ≤ x1 x1 x1 x2 x2 x2 + + §1 LP问题及其数学模型 解：设A、B两种产品的产量分别为x1、x2，则使工厂获取的总利润最大的数学模型如下： OR课件 LP Max z=3x1 + 4x2 目标函数 2x1＋x2 ≤ 40 （铜） x1＋3x2 ≤ 30（铝） x1, x2 ≥ 0 约束条件 决策变量 非负约束 §1 LP问题及其数学模型 例、某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的生产计划。 OR课件 LP 单位产品所需原料数量（公斤） 产品Q1 产品 Q2 产品 Q3 原料可用量 （公斤/日） 原料P1 2 3 0 1500 原料P2 0 2 4 800 原料P3 3 2 5 2000 单位产品的利润（千元） 3 5 4 x1 x2 x3 §1 LP问题及其数学模型 OR课件 LP 解：设 非负约束：产量为非负数 x1,x2,x3 ≥0 §1LP问题及其数学模型 OR课件 LP §1LP问题及其数学模型 OR课件 LP 例2 运输问题：甲乙两地分别有货物80t和100t，要运送到a，b，c三个地方，数量分别是70，60和50t，它们之间的单位运价（元/T·km）如下表，现在要制订出最佳运输方案，使总的运输费用达到最小。 收点 发点 a b c 发货量（t) 甲(i=1) 乙(i=2) 5 4 8 8 6 2 80 100 收货量(t) 70 60 50 xij §1 LP问题及其数学模型 OR课件 LP 解：设由发点i到收点j的货运量为xij ，i=1,2; j=1,2,3 Min S = 5x11+ 4x12 + 8x13 + 8 x21 + 6x22 +2x23 x11+ x12 + x13 = 80 x21 + x22 +x23 = 100 x11+ x21 = 70 x12 + x22 = 60 x13 + x23 = 50 xij ≥ 0，i=1,2; j=1,2,3 §1LP问题及其数学模型 OR课件 LP （1）每一问题都可以用一组变量（x1, x2, …, xn ）表示某一方案，一般情形下，变量的取值是非负的； （2）约束条件用线性等式或线性不等式表示； （3）都有一个目标函数，且这个目标函数可表示为一组变量的线性函数； （4）每一问题要求目