第二章单纯形法 ·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,最优解
单纯形法原理(1)一松弛变量的表示 D max z=XfX, st.x1+x2≤3 X12X2≥0 引进松弛变量 B max z=X1+2X2 S.t. X1+X2+X3 +xA=1 2,X3,X4≥0 A
－ ＋ ＋ － 单纯形法原理（1）—松弛变量的表示 max z=x1+2x2 s.t. x1+x23 x2 1 x1 , x20 max z=x1+2x2 s.t. x1+x2+x3 =3 x2 +x4=1 x1 , x2 , x3 , x40 x2=0 x1=0 x3=0 x4=0 O A B C D － ＋ ＋ － 引进松弛变量
单纯形法思路 1、找到一个初始基和相应基可行解,并将目标 函数和基变量分别用非基变量表示。 ·2、根据目标函数用非基变量表示的式中的系数, 选择一个非基变量,使其值从0开始增大,z随之 变大,这个变量称为进基变量(一般选系数大的) 若任何一个非基变量的值增加都不能使z增大,则 当前基可行解为最优解。 3、在基变量用非基变量表出的式中,首先减少 到0的称为离基变量 若进基变量值增加时,所有基变量值都不减少, 则无界。 ·4、确定新的基、基可行解,返回2
单纯形法思路 • 1、找到一个初始基和相应基可行解，并将目标 函数和基变量分别用非基变量表示。 • 2、根据目标函数用非基变量表示的式中的系数， 选择一个非基变量，使其值从0开始增大，z随之 变大，这个变量称为进基变量（一般选系数大的） • 若任何一个非基变量的值增加都不能使z增大，则 当前基可行解为最优解。 • 3、在基变量用非基变量表出的式中，首先减少 到0的称为离基变量 • 若进基变量值增加时，所有基变量值都不减少， 则无界。 • 4、确定新的基、基可行解，返回2
max z=x +2x max z=x+2X St.x1+x,0为基变量 当前基可行解: (x1x2x32X4)=(0,0,3,1
x2=0 x1=0 x3=0 x4=0 O A B C x1 ,x2=0为非基变量 x3 ,x4>0为基变量 当前基可行解： (x1 ,x2 ,x3 ,x4)=(0,0,3,1 ) z=0 x2进基,从0开始增加 ，x3 ,x4随之减少 第一次叠代： 目标函数和基变量分别用 非基变量表示： z=x1+2x2 选择x2进基 x3 =3-x1-x2 x4=1 -x2 x2=1成为基变量， x4=0成为非基变量 当前基可行解： (x1 ,x2 ,x3 ,x4)=(0,1,2,0) z=2 单m s 纯.t a .x x 形z=x法1+2原x2 理(2)—第一次叠代 1+x23 x2 1 x1 , x20 max z=x1+2x2 s.t. x1+x2+x3 =3 x2 +x4=1 x1 , x2 , x3 , x40
确定离基变量的进一步讨论 设非基变量为x1、x2,基变量为x3、x4、X,进基变量为x2 =5-x1-4X2 5/4=1.25 min{5/4,4/3,2/1}=5/4 4-2x1-3x2 4/3=1.33 当x2增加到1.25时 =2-3x1-x2 2/1=2 0离基 =5-x1+4x2 增加 min{4/3,2/1}=4/3 =4-2x1-3 4/3=1.33 当x2增加到13时 2-3x 41-A2 2/1=2 x4=0离基 X1+4x 增加 min{2/1}=2/1 4-2x1+3x 增加 当x2增加到2时 2-3x1 2/1=2 0离基 1+4x2 x增加 可以无限增加,可 4-2x1+3x2 x增加 行域是开放区域,目 2-3x1+ xs增加 标函数无界
确定离基变量的进一步讨论 设非基变量为x1、x2，基变量为x3、x4、x5，进基变量为x2 x3 =5- x1-4x2 x4 =4-2x1-3x2 x5 =2-3x1- x2 5/4=1.25 4/3=1.33 2/1=2 min{5/4,4/3,2/1}=5/4 当x2增加到1.25时 x3＝0离基 x3 =5- x1+4x2 x4 =4-2x1-3x2 x5 =2-3x1- x2 x3增加 4/3=1.33 2/1=2 min{4/3,2/1}=4/3 当x2增加到1.33时 x4＝0离基 x3 =5- x1+4x2 x4 =4-2x1+3x2 x5 =2-3x1- x2 x3增加 x4增加 2/1=2 min{2/1}=2/1 当x2增加到2时 x5＝0离基 x3 =5- x1+4x2 x4 =4-2x1+3x2 x5 =2-3x1+ x2 x3增加 x4增加 x5增加 x2可以无限增加，可 行域是开放区域，目 标函数无界
=3-X 单纯形法原理(3)一第二次叠代 1-X x12成为基变量, x3=0成为非基变量 第二次叠代 当前基可行解: 目标函数和基变量分别用非 (1,x2,x3,x4)=(2,1,0,0) 基变量表示: 4 z=2+x1-2x 选择X1进基 x进基,从0开始增 3 2-x1+x4 加,基变量x2保持不 变,x3从2开始减少 B 当前基可行解: A (x1x2,x32x4)=(0,1,2,0) O X2=0 2
x2=0 x1=0 x3=0 x4=0 O A B C 第二次叠代： 目标函数和基变量分别用非 基变量表示： z=2+x1-2x4 选择x1进基 x3 =2-x1+x4 x2=1 -x4 当前基可行解： (x1 ,x2 ,x3 ,x4)=(0,1,2,0) z=2 单纯形法原理（3）—第二次叠代 x1进基，从0开始增 加，基变量x2保持不 变，x3从2开始减少 x1=2成为基变量， x3=0成为非基变量 当前基可行解： (x1 ,x2 ,x3 ,x4)=(2,1,0,0) z=4 x3 =3-x1 -x2 x4=1 -x2