二、线性规划的图解法 一一一解的几何表示
二、 线性规划的图解法 －－－解的几何表示
1.什麼是图解法? 线性规划的图解法就是用几何作图的 方法分析并求出其最优解的过程。 求解的思路是:先将约束条件加以图 解,求得满足约束条件的解的集合(即可 行域),然后结合目标函数的要求从可行 域中找出最优解
1．什麽是图解法？ 线性规划的图解法就是用几何作图的 方法分析并求出其最优解的过程。 求解的思路是：先将约束条件加以图 解，求得满足约束条件的解的集合（即可 行域），然后结合目标函数的要求从可行 域中找出最优解
2图解法举例 例1-1maxZ=2x1+3x2 1/3X,+1/3X<1 st{1/3x1+4/3x2≤3 XX 2 0 实施图解法,以求出最优生产计划(最优解
2. 图解法举例 实施图解法，以求出最优生产计划（最优解）。 例1－1 maxZ=2x1+3x2 1/ 3x +1/ 3x 1 1/ 3x + 4 / 3x 3 x , x 0 1 2 1 2 1 2 s.t
由于线性规划模型中只有两个决策 变量,因此只需建立平面直角坐标系就 可以进行图解了。 第一步:建立平面直角坐标系,标出坐标 原点,坐标轴的指向和单位长度。 用x1轴表示产品A的产量,用x2轴表示 产品B的产量。 Y第二步:对约束条件加以图解 y第三步:画出目标函数等值线,结合目标 函数的要求求出最优解一最优生产方案
由于线性规划模型中只有两个决策 变量，因此只需建立平面直角坐标系就 可以进行图解了。 第一步：建立平面直角坐标系，标出坐标 原点, 坐标轴的指向和单位长度。 用x1轴表示产品A的产量，用x2轴表示 产品B的产量。 第二步：对约束条件加以图解。 第三步：画出目标函数等值线，结合目标 函数的要求求出最优解－－最优生产方案
约束条件的图解 每一个约束不等式在平面直角坐标系中都 代表一个半平面,只要先画出该半平面的边 界,然后确定是哪个半平面 怎麼画边界 怎麼确定 半平面 以第一个约束条件 1/3x1+1/3x2≤1为例 说明约束条件的图解过程
约束条件的图解: 每一个约束不等式在平面直角坐标系中都 代表一个半平面，只要先画出该半平面的边 界，然后确定是哪个半平面。 ? 以第一个约束条件 1/3 x1+1/3 x2 1 为例 说明约束条件的图解过程。 怎麽画边界 怎麽确定 半平面
如果全部的劳动工时都用来生产A产品而不生亲 B产品,那么A产品的最大可能产量为3吨,计算过 程为: 1/3x1+13×0≤1∴X1≤3 这个结果对应着右图中的点A(3,0),同样我们可 以找到B产品最大可能生产量对应的点B(0,3)。接 A、B两点得到约束 13x1+1/3x,≤1 最优点 所代表的半平面 1 3BLE 的边界: (1/3)x+(1/3)x=1 13x1+13x,=1, 即直线AB
如果全部的劳动工时都用来生产A 产品而不生产 B产品，那么A产品的最大可能产量为3吨，计算过 程为： 1/3x1+1/3×01 x13 这个结果对应着右图中的点A(3,0),同样我们可 以找到B产品最大可能生产量对应的点B(0,3)。连接 A、B两点得到约束 1/3 x1+1/3 x2 1 所代表的半平面 的边界: 1/3 x1+1/3 x2 ＝1， 即直线AB。 X2 5– 4– l1 3B E 2 D （1/3）x1+(4/3)x2=3 l2 1 C 0 1〡 2〡 3A 4〡 5〡 6〡 7〡 8〡 9〡 x1 (1/3)x1+(1/3)x2=1 最优点
第二个约束条件 的边界一一 最优点 4 直线CD: I1 3BN E 1/3x1+4/3x2=3 1/3)x1+(4/3)x2=3 两个约束条件 (1/3)x1+(1/3)x2 及非负条件x1,x2≥0所代表的公共部分 图中阴影区,就是满足所有约束条件 和非负条件的点的集合,即可行域。在这 个区域中的每一个点都对应着一个可行的 生产方案
两个约束条件 及非负条件x1 ,x2 0所代表的公共部分 －－图中阴影区，就是满足所有约束条件 和非负条件的点的集合，即可行域。在这 个区域中的每一个点都对应着一个可行的 生产方案。 第二个约束条件 的边界－－ 直线CD: 1/3x1+4/3 x2 =3 5– 4– l 1 3B E 2 D （1/3）x1+(4/3)x2=3 l 2 1– 0 1〡 2〡 3A 4〡 5〡 6〡 7〡 8〡 9〡C (1/3)x1+(1/3)x2= 1 最优点
令Z=2x+3x2=c,其中c为任选的一个常数,在图中 画出直线2x+3x2=c这条直线上的点即对应着个可 行的生产方案,即使两种产品的总利润达到c。 这样的直线有无数条,而且相互平行,称这样的直线 为目标函数等值线。只要画出两条目标函数等值线 比如令c=0和c=6,就能看出 目标函数值递增的方向, 用箭头标出这个方向。 最优点 图中两条虚线1和2就 I E l/3)x1+(4/32=3 分别代表目标函数等值线 2x1+3x2=0和2x1+3x2=6 (1/3)x1+(1/3)x=1 箭头表示使两种产品的总树润递增的方向
令 Z=2x1+3x2=c,其中c为任选的一个常数，在图中 画出直线 2x1+3x2=c,这条直线上的点即对应着一个可 行的生产方案，即使两种产品的总利润达到c。 这样的直线有无数条，而且相互平行，称这样的直线 为目标函数等值线。只要画出两条目标函数等值线， 比如令c＝0和c=6，就能看出 目标函数值递增的方向， 用箭头标出这个方向。 图中两条虚线 l 1和l 2就 分别代表 目标函数等值线 2x1+3x2 =0 和 2x1+3x2 =6, 箭头表示使两种产品的总利润递增的方向。 X2 5– 4– l1 3B E 2 D （1/3）x1+(4/3)x2=3 l2 1– x1 0 1〡 2〡 3A 4〡 5〡 6〡 7〡 8〡 9〡C (1/3)x1+(1/3)x2=1 最优点
最优点 3BNE 3)x1+(4/3)x2=3 A+50+7+8+9e 沿着箭头的方向平移目标函数等值线,使其达到 可行域中的最远点E,E点就是要求的最优点,它对应 的相应坐标x=1x2=2就是最有利的产品组合即生 产A产品1吨,B产品2吨能使两种产品的总利润达到 最大值Zmax=2×1+3×2=8(千元),x11,x2=2就是线 性规划模型的最优解,Zmax=8就是相应的目标函数 最优值
沿着箭头的方向平移目标函数等值线，使其达到 可行域中的最远点E, E点就是要求的最优点，它对应 的相应坐标 x1=1,x2=2 就是最有利的产品组合，即生 产A产品1吨，B产品2吨能使两种产品的总利润达到 最大值 Zmax=21+32=8（千元），x1=1,x2=2就是线 性规划模型的最优解，Zmax=8就是相应的目标函数 最优值。 5– 4– l1 3B E 2 D （1/3）x1+(4/3)x2=3 l 2 1– 0 1〡 2〡 3A 4〡 5〡 6〡 7〡 8〡 9〡C (1/3)x1+(1/3)x2=1 最优点
尽管最优点的对应坐标可以直接从图中 给出,但是在大多数情况下,对实际问题精 确地看出一个解答是比较困难的。所以,通 常总是用解联立方程的方法求出最优解的精 确值。 比如E点对应的坐标值我们可以通过求 解下面的联立方程,即求直线AB和CD的交 点来求得。 直线AB:1/3x1+1/3x2=1 直线CD:1/3x1+4/3x2=3
尽管最优点的对应坐标可以直接从图中 给出，但是在大多数情况下，对实际问题精 确地看出一个解答是比较困难的。所以，通 常总是用解联立方程的方法求出最优解的精 确值。 比如E点对应的坐标值我们可以通过求 解下面的联立方程，即求直线AB和CD的交 点来求得。 直线AB: 1/3x1+1/3x2 =1 直线CD: 1/3x1+4/3x2 =3