基础解、基础可行解 max Z=X1+3X2 D s.t. X+ tX 68 B X1,X2X32X4>0 0 KE 0=0A O A B D 基变量 非基变量 <0 基础可行解是是是是否否
基础解、基础可行解 max z=x1+3x2 D s.t. x1+ x2+x3 =6 B -x1+2x2 +x4 =8 x4=0 C x3=0 x1 , x2 ,x3 ,x4≥0 x1=0 E O x2=0 A O A B C D E 基变量 x3 x4 x1 x4 x1 x2 x2 x3 x2 x4 x1 x3 非基变量 x1 x2 x2 x3 x3 x4 x1 x4 x1 x3 x2 x4 xj<0 -- -- -- -- x4 x1 基础可行解 是 是 是 是 否 否
几何概念 代数概念 约束直线 满足一个等式约束的解 约束半平面 满足一个不等式约束的解 约束半平面的交集:满足一组不等式约束的解 凸多边形 约束直线的交点 基础解 可行域的极点 基础可行解 目标函数等值线: 目标函数值等于一个常 组平行线 数的解
几何概念 代数概念 约束直线 满足一个等式约束的解 约束半平面 满足一个不等式约束的解 约束半平面的交集： 凸多边形 满足一组不等式约束的解 约束直线的交点 基础解 可行域的极点 基础可行解 目标函数等值线： 一组平行线 目标函数值等于一个常 数的解
单纯形表
单纯形表
求解线性规划问题 max z= 3x +4 +2x St X +X +X 25 +2x,+X3+2 36 写成标准化形式 St +X,+x =25 X1+2x2+x3+2x4 36 X4X5X6三0
max z= 3x1 +4x2 -x3 +2x4 s.t. x1 +x2 +x3 +x4 ≦25 x1 +2x2 +x3 +2x4 ≦36 x1 x2 x3 x4 ≧0 min z'= -3x1 -4x2 +x3 -2x4 s.t. x1 +x2 +x3 +x4 +x5 =25 x1 +2x2 +x3 +2x4 +x6 =36 x1 x2 x3 x4 x5 x6 ≧0 求解线性规划问题 写成标准化形式
写出单纯形表 X6 RHS 25 13636/2 x2进基,x6离基, RHS z|1‖10-3-20-2-72 x30|012011277a x20|12112101218182 x1进基,x离基
z' x1 x2 x3 x4 x5 x6 RHS z' 1 3 4 -1 2 0 0 0 0 1 1 1 1 1 0 25 0 1 2 1 2 0 1 36 写出单纯形表 25/1 36/2 0 -3 -2 0 -2 -72 0 1 1/2 0 1 -1/2 7/1/2 1 x5 1/2 1 0 1/2 18/1/2 0 7 18 1 1/2 x2 1/2 0 x2进基， x6离基， x1进基， x5离基， z' x1 x2 x3 x4 x5 x6 RHS z' 1 3 4 -1 2 0 0 0 x5 0 1 1 1 1 1 0 25 x6 0 1 2 1 2 0 1 36