第二章线性规划的图解法分解.ppt

第二章 线性规划的图解法 一、线性规划的概念 二、线性规划问题的提出 三、线性规划的数学模型 四、线性规划的图解法 五、线性规划解的情况 六、LP图解法的灵敏度分析 一、线性规划的概念 线性规划Linear Programming 简称LP，是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。 线性规划的目标和约束条件都可以表示成线性的式子。 二、线性规划问题的提出 例1.1、胜利家具厂生产桌子和椅子两种家具，桌子售价50元/张，椅子售价30元/张。生产一张桌子需要木工4h，油漆工2h，生产一张椅子需要木工3h，油漆工1h。该厂每月可用木工工时120h，油漆工工时50h。问该厂每月生产多少张桌子和椅子才能使每月的销售收入最大？ 解： 1、确定决策变量 x1、x2——每月生产桌子、椅子的数量； 2、确定目标函数——销售收入最大 Max s =50x1+30x2 3、确定约束条件 s.t. 4x1+3x2≤ 120 2x1+x2≤ 50 4、变量非负限制 x1 ,x2 ≥0 线性规划模型： Max s =50x1+30x2 s.t. 4x1+3x2≤ 120 2x1+x2≤ 50 x1 ,x2 ≥0 例1.2 某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的生产计划 决策变量：每天生产三种产品的数量，分别设为x1，x2，x3； 目标：每天的生产利润最大 目标函数为Max s ＝3x1＋5x2＋4x3 约束条件：每天原料的需求量不超过可用量 原料P1 ： 2x1＋3x2＋0x3≤ 1500 原料P2 ： 0x1＋2x2＋4x3≤800 原料P3 ： 3x1＋2x2＋5x3≤2000 隐含约束：产量为非负数x1 ，x2 ，x3 ≥0 数学模型： Max s = 3x1＋5x2＋4x3 s.t. 2x1＋3x2＋0x3≤ 1500 0x1＋2x2＋4x3≤800 3x1＋2x2＋5x3≤2000 x1 ，x2 ，x3 ≥0 从前面两个例子中可以看出一般线性规划问题的建模过程： A、理解要解决的问题，明确在什么条件下，要追求什么目标； B、定义决策变量； C、用决策变量的线性函数形式写出所要追求的目标，即目标函数,按问题的不同，要求目标函数实现最大化和最小化； D、用一组决策变量的等式或不等式来表示在解决问题过程中所必须遵循的约束条件。 三、线性规划的数学模型 1、LP模型的一般形式 xj为待定的决策变量； cj为目标函数系数，或价值系数、费用系数； aij为技术系数； bj为资源常数，简称右端项； 其中i＝1，2，…m； j＝1，2，…n 可以看出，一般LP模型的特点： A、决策变量x1，x2，x3，……xn表示要寻求的方案，每一组值就是一个方案； B、约束条件是用等式或不等式表述的限制条件； C、一定有一个追求目标，或希望最大或希望最小； D、所有函数都是线性的。 标准形式的特点： A、目标函数为Max形式 B、约束全为＝式 C、所有决策变量xj ≥0，j＝ 1，2，3，… n D、所有bi≥0，i＝1，2，3，…… m 3、如何将一般LP问题化为标准形式 A、极小化目标函数问题转化为极大化目标函数问题： 若目标函数为： Min f = c1x1 + c2x2 + … + cnxn 则可令z ＝ -f ，原目标等同于： Max z = -c1x1 - c2x2 - … - cnxn 但须注意, f* ＝ – z* B、约束条件不是等式的问题： 若约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量si ，使它等于约束右边与左边之差 si=bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然，si 也具有非负约束，即si≥0， 这时新的约束条件成为