运筹学2.2线性规划.pptVIP

线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。 求解的思路是： 先将约束条件加以图解，求得满足约束条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。 第三步：图示目标函数 注 释 可能出现的情况： 可行域是空集(例4) 可行域无界无最优解(例3) 最优解存在且唯一，则一定在顶点上达到(例1) 最优解存在且不唯一，一定存在顶点是最优解(例2) 作 业（P. 43） 1.1 用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。 第三节 单纯形法原理 可行域的几何结构 基本假设 凸集 可行域的凸性 * * 第二节 线性规划的图解法 －－－解的几何表示 几 个 概 念 什么是图解法？ 仅适用于含两个变量的LP 步骤： 建立平面直 角坐标系 图示约束条件 找出可行域 图示目标函数 寻找最优解 例1 实施图解法，以求出最优解。 第一步：建立平面直角坐标系（变量x1,x2） x1 x2 O 第二步：对约束条件加以图解 ? ? ? ? ? í ì 3 3 ￡ + ￡ - - 3 - 0 , 0 5 2 2 2 2 2 1 2 1 2 1 2 1 x x x x x x x x x2 O x1 2 4 6 2 4 阴影部分描述了满足 约束条件的区域，即 可行域 + - = max 2 1 x x z O 2 4 6 2 4 x2 x1 画出目标函数等值线 z=常数 z=0 z=1.5 最优解(1,4)T 法线方向 (-1，1)T 沿法线方向， 函数值增加 沿负法线方向， 函数值下降 例2 O 2 4 6 4 x1 x2 法线方向 (4，-2)T z=0 线段A1A2上的每一个点均为最优解。 A2 A1 若目标函数由 Max Z = 2X1 + 4X2 改为 Min Z =2X1 + 4X2 ,则 可行解所在的范围虽然无界, 但有最优解 (4,0)点. 可行域：无界 无有限最优解 例3 maxZ=2X1+ 4X2 2X1+X2 ?8 -2X1+X2 ? 2 X1 , X2 ?0 2X1+ X2=8 -2X1+ X2=2 8 2 4 6 X2 4 0 X1 Z=0 例4 maxZ=3X1+2X2 -X1 -X2 ?1 X1 , X2 ?0 无解 无可行解 -1 X2 -1 X1 0 上述理论具有普遍意义，对于两个以上变量的线性规划问题都成立。 图解法虽然直观、简便等优点，在变量多的情况下，即在多维的情况下，它就无能为力了。因此，需要介绍一种代数方法——单纯型法。 ? 对于只有两个变量的线性规划问题可以用图解法求解： 1. 变量用直角坐标系中的点表示 2. 约束条件用坐标系中的半空间或直线的交表示，可行域是一个凸多面体 3. 目标函数用一组等值线表示，沿着增加或减少的方向移动，与可行域最后的交点就是最优解。 小 结 1947年美国数学家 丹捷格（G.B.Dantzig） 提出了求解线性规划 问题的方法 ——单纯形法 线性规划之父 基 本 假 设 凸 集 图（a)、(b)、为凸集，而图（c)、(d)不是凸集。 *