可行域的性质 ●线性规划的可行域是凸集 ●线性规划的最优解在极点上 凸集 凸集 不是凸集 极点
可行域的性质 ●线性规划的可行域是凸集 ●线性规划的最优解在极点上 凸集 凸集 不是凸集 极点
线性规划的基本概念 ●线性规划的基矩阵、基变量、韭基变量 目标函数□□□ 束条件 ■■口■■口■■■■=口右边常数 ■■■口■口 行列式≠0 基矩阵
线性规划的基本概念 ●线性规划的基矩阵、基变量、非基变量 = = 目标函数 约 束 条 件 行列式≠0 基矩阵 右边常数
max z= 2X1 +3x2 +X3 S t +3x2+x3<15 2x1+3 3≤18 X X2+x3≤3 0 min Z'=-2X1-3X2-X 2x1+3x 18 X6=3 X2, X3, X4, X5, 6 20
max z= 2x1 +3x2 +x3 s.t. x1 +3x2 +x3 15 2x1 +3x2 -x3 18 x1 -x2 +x3 3 x1, x2, x3 0 min z’= -2x1 -3x2 -x3 st x1 +3x2 +x3 +x4 =15 2x1 +3x2 -x3 +x5 =18 x1 -x2 +x3 +x6 =3 x1, x2, x3, x4, x5, x6 0
x1+3x+x3+x4 =15 3xd-x 18 基变量x1、x2、x3,非基变量x4、x5、x 1+3x2+x3=15 2x1+3x2-X3=18 +X3=3 基础解为 X5,x6)=(5,3,1,0,0,0) 是基础可行解,表示可行域的一个极点 目标函数值为:z=20
x1 +3x2 +x3 =15 2x1 +3x2 -x3 =18 x1 -x2 +x3 =3 x1 +3x2 +x3 +x4 =15 2x1 +3x2 -x3 +x5 =18 x1 -x2 +x3 +x6 =3 基变量x1、x2、x3，非基变量x4、x5、x6 基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=20
=15 2x1+3 =18 基变量x1、x2、x4,非基变量x3、x、x X1+3x2+x4=15 2x1+3 =18 基础解为 X5,x6)=(27/5,12/5,0,2/5,0,0 是基础可行解,表示可行域的一个极点 目标函数值为:z=18
x1 +3x2 +x4 =15 2x1 +3x2 =18 x1 -x2 =3 基变量x1、x2、x4，非基变量x3、x5、x6 基础解为 （x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=18 x1 +3x2 +x3 +x4 =15 2x1 +3x2 -x3 +x5 =18 x1 -x2 +x3 +x6 =3