第一章线性规划-模型和图解法.pptVIP

LP问题标准形式的特征是： ⑴ 求目标函数的最大值； ⑵ 约束条件为等式； ⑶ 决策变量非负。 下面分析如何将LP问题标准化： ⑴ 若目标函数为 引进新的目标函数 则 的最小值即为 的最大值，即： 从而目标函数变换为： （2）若约束条件为不等式，分为两种情况讨论： 加入松弛变量 加入剩余变量 （3）对于决策变量非负的要求，分为两种情况讨论： ①非正变量：即xk ≤0 令xkˊ= -xk即可 ②自由变量：即xk无约束 令xk = xkˊ－xk〞 例1 将LP问题 化为标准形。 解：引进新的目标函数 于是原LP问题化为标准形式： 例2 将LP问题 化为标准形。 松弛变量 例3 将LP问题 化为标准形。 剩余变量 例4 将LP问题 化为标准形。 课堂练习 例 将LP问题 课堂练习 例 将LP问题 化为标准形。 我们得到例4的标准形为： §1.2 线性规划问 题的图解法 1. 2线性规划图解法 所谓图解法，就是在平面直角坐标上画出各个约束条件所允许变化的范围，通过图上作业法求出最优解和目标函数值。 一个线性规划问题有解，是指能找出一组xj(j=1,2,…n),满足所有约束条件，称这组xj为问题的可行解。 通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域。 在用图解法求解时，可形象的看到可行域。 在可行域中使目标函数值达到最优的可行解称为最优解 对不存在可行解的线性规划问题，称该问题无解 图解法背景知识 图解法背景知识 由中学知识可知：y=ax+b是一条直线。 同理(如果Z值固定) Z=70x1+120x2 x2= -70/120x1 + Z/120也是一条直线 x2= -70/120x1 + Z/120也是一组平行的等值线 1.2.1图解法的步骤 1、建立直角坐标系； 2、根据约束条件描绘可行域； 3、作目标函数的等高线； 4、求解最优点和最优目标函数值。 例题1—生产计划问题 某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表： 产品A 产品B 资源限量 劳动力 设 备 原材料 9 4 3 4 5 10 360 200 300 利润元/kg 70 120 问题：如何安排生产计划，使得获利最多？ 例1 图解法 . 90 80 60 40 20 0 20 40 60 80 100 x1 x2 9x1+4x2 ＝ 360 4x1+5x2 ＝200 3x1+10x2 ＝300 Z=70x1+120x2 maxZ=70X1+120X2 9X1+4X2≤360 4X1+5X2 ≤200 3X1+10X2 ≤300 X1≥0 X2≥0 最优解(20,24),Z=4280 可行域 课堂练习 用图解法求解下述线性规划问题。 1） 3） 2） 1.2.2求解的几种可能结局 1、无穷多最优解。 2、唯一最优解。 2、无界解。 3、无解或无可行解。 解的可能性 多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。 唯一最优解：只有一个最优点。 x1 =8 2x2 =12 3x1 +4 x2 =36 x1 x2 4 8 12 3 6 9 0 A B C(4,6) D 例1的数学模型变为 maxZ= 3x1 +4 x2 x1 ≤8 2x2 ≤12 3x1 +4 x2 ≤36 x1 ≥0, x2 ≥0 S.t. Z=24 Z=36 Z=12 无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件） 例如 maxZ= 3x1 +2 x2 -2x1 + x2 ≤2 x1 -3 x2 ≤3 x1 ≥0, x2 ≥0 -2x1 + x2 =2 x1 -3 x2 =3 x2 1 2 3 -1 x1 1 2 3 -1 Z=6 Z=12 S.t. 解的可能性 无可行解：若约束条件相互矛盾，则可行域为空集 例如 maxZ= 3x1 +2 x2 -2x1 + x