第一章线性规划及单纯刑法2.ppt

§1.2 图解法--线性规划问题的几何意义 §1.2 图解法--线性规划问题的几何意义 §1.2 图解法--线性规划问题的几何意义 §1.2 图解法--线性规划问题的几何意义 §1.2 图解法--线性规划问题的几何意义 §1.2 图解法--线性规划问题的几何意义 §1.2 图解法--线性规划问题的几何意义 §1.2 图解法 本节习题 §1.3线性规划问题的解及定理 §1.3线性规划问题的解及定理 §1.3线性规划问题的解及定理 §1.3线性规划问题的解及定理 §1.3线性规划问题的解及定理 §1.3线性规划问题的解及定理 §1.3线性规划问题的解及定理 §1.3线性规划问题的解及定理 §1.3线性规划问题的解及定理 §1.3线性规划问题的解及定理 * 东 北 林 业 大 学 　　所谓图解法就是在平面上，用作图的方法来求解模型。　　 一、图解法的基本内容 尽管图解法仅适合求解两个变量的线性规划模型，但对于建立ｎ维空间中线性规划问题的概念和理解求解一般线性规划问题的单纯形法，有着重要的帮助。 例:用图解法求解例1.1 东 北 林 业 大 学 ...... ① ...... ② R O A B C x1 x2 （二）约束条件的图形表示 1. x1≥0, x2 ≥0 2. 2x1 + 3x2 ≤ 100 3. 4x1 + 2x2 ≤ 120 所有约束条件的交集为R。 10 20 30 40 50 60 60 50 40 30 20 10 两个概念: 1.可行解:满足约束条件的点。 2.可行域:全部可行解的集合,即区域OABCO,用R表示。 现在,问题变为在R内找一点,使目标函数值最大。如何找?… （一）建立坐标系 东 北 林 业 大 学 R O A B C x1 x2 （三）目标函数的图形表示 z= 6x1 + 4x2 10 20 30 40 50 60 60 50 40 30 20 10 将上式改写： 　　　　　 ooooox2 ＝－3x1 /2 ＋ z/4 令Z为参量，使其取不同的值，则得到以－3/2为斜率的一族平行等值线。 如令: Z=60, 则经过点(10,0)和(0,15); Z=60 Z=120,则经过点(20,0)和(0,30); Z=0, 则经过原点; 有何规律? Z=0 Z=120 Z最大 (20,20) x1 = 20 , x2 = 20, z = 200 （四）最优解为: … … 图解法的优点: 简单、直观、明了。 缺点： 仅适合求解两个变量的模型。 东 北 林 业 大 学 课堂练习:求解如下线性规划问题. maxZ = X1 + 3X2 X1 + X2 ≤ 6 --① X1 ≤ 4 --② X1≥0, X2 ≥0 Ｘ1 Ｘ2 1 2 3 4 5 6 6 5 4 3 2 1 可行域为: 目标函数变动为: 最优解为: X1 = 0，X2 = 6 ，Z = 18 Z 东 北 林 业 大 学 R O A B C x1 x2 1. maxz = 6x1 + x2 最优解在C(30,0)点,Z=180. 10 20 30 40 50 60 60 50 40 30 20 10 ㈠约束条件不变,目标函数变化时,最优解将发生怎么改变? 2. maxz = 6x1 + 3x2 线段BC上所有的点,Z=180. 3. minz = 6x1 + 4x2 最优解在O(0,0)点,Z=0. Z = 6x1 + x2 Z = 6x1 + 3x2 minZ 重要结论:最优解一定在……？ 可行域的顶点上！ 二、线性规划问题解的讨论 ...... ① ...... ② 东 北 林 业 大 学 ㈡目标函数不变,约束条件出错时,最优解将发生怎么改变? x1 x2 10 20 30 40 50 60 60 50 40 30 20 10 1.无界解(或无解) maxZ = 6X1 + 4X2 2X1 + 3X2 ≤ 100 --① 4X1 + 2X2 ≤ 120 --② X1≥0, X2 ≥0 X2的取值无限制， z 也可以增至到无穷大。原因是遗漏了必要的约束条件。 Z 东 北 林 业 大 学 x1 x2 10 20 30 40 50 60 60 50