第二章单纯形法 ·1、单纯形法基本思想 ·2、单纯形法原理 ·3、表格单纯形法计算
第二章 单纯形法 • 1、单纯形法基本思想 • 2、单纯形法原理 • 3、表格单纯形法计算
线性规划基木定理P16 定理1:若LP存在可行解,则可行域为凸集 ·2、LP的基可行解对应凸集的极点(顶点) ·3、若可行域非空有界,则LP在某极点必有 最优解
线性规划基本定理P16 • 定理1：若LP存在可行解，则可行域为凸集。 • 2、LP的基可行解对应凸集的极点（顶点） • 3、若可行域非空有界，则LP在某极点必有 最优解
单纯形法原理示意图 其实,不必搜索可行域的每 极点4,最优解 个极点,只要从一个极点出发, 沿着使目标函数改善的方向,到 目标函数改善 达下一个相邻的极点。如果相邻 的所有极点都不能改善目标函数, 极点3 目标函数改善 这个极点就是最优极点。用这样 的搜索策略,可以大大减少搜索 极点2 极点的个数。 按照这样的搜索策略建立的 目标函数改善 算法,叫做单纯形法 单纯形法可以有效地减少搜 初始极点1 索极点的个数
单纯形法原理示意图 极点4，最优解 初始极点1 极点2 极点3 其实，不必搜索可行域的每 一个极点，只要从一个极点出发， 沿着使目标函数改善的方向，到 达下一个相邻的极点。如果相邻 的所有极点都不能改善目标函数， 这个极点就是最优极点。用这样 的搜索策略，可以大大减少搜索 极点的个数。 按照这样的搜索策略建立的 算法，叫做单纯形法。 单纯形法可以有效地减少搜 索极点的个数。 目标函数改善 目标函数改善 目标函数改善
用消元法描述单纯形法 可行解沿可行域的边界从一个顶点移到相 邻另一个更优顶点时目标函数、基变量相 应的变化。 此时,只有一个非基变量的值从0开始增加, 其它非基变量不变
用消元法描述单纯形法 • 可行解沿可行域的边界从一个顶点移到相 邻另一个更优顶点时目标函数、基变量相 应的变化。 • 此时，只有一个非基变量的值从0开始增加， 其它非基变量不变
(x1x2X32x4)= 0,1,2,0),z=2 2,1,0,0),z=4,最优解 B 0 A (0.0,3,1)2z=0 =0
x2=0 x1=0 x3=0 x4=0 O A B C (x1,x2,x3,x4)= (0,0,3,1), z=0 (x1,x2,x3,x4)= (0,1,2,0), z=2 (x1,x2,x3,x4)= (2,1,0,0), z=4,最优解