1.3线性规划问题的标准型式 例4将下述线性规划问题化为标准形式线性规划 min z=-x+2x-3x x1+x2+x3≤7 x1=x2+x3 3x1+x2+x2= x1,x2≥0;x3为无约束 1)用x4x替换x3其中x,x=0; (2)在第一个约束不等式左端加入松弛变量x; (3)在第二个约束不等式左端减去剩余变量x; 4)令=一,将求mnz改为求maxz 即可得到该问题的标准型
1.3 线性规划问题的标准型式 例4 将下述线性规划问题化为标准形式线性规划 − + + = − + + + = − + − 1 2 3为无约束 1 2 3 1 2 3 1 2 3 1 2 3 0 3 5 3 7 2 3 x ,x ; x x x x x x x x x x min z x x x (1) 用x4−x5替换x3，其中x4，x5≥0； (2) 在第一个约束不等式左端加入松弛变量x6； (3) 在第二个约束不等式左端减去剩余变量x7； (4) 令z′= −z，将求min z 改为求max z′ 即可得到该问题的标准型
1.3线性规划问题的标准型式 例4例4的标准型 maxz=x1-2x2+3(x4-x5)+0x6+0x7 x1+x2+(x4-x5)+x6=7 x1-x)+ 2 4-15 x7=2 3x1+x2+2(x4-x) =5 X1 x 2,425 , x62 x7≥0
1.3 线性规划问题的标准型式 例4 例4的标准型 − + + − = − + − − = + + − + = = − + − + + , , , , , 0 3 2( ) 5 ( ) 2 ( ) 7 max 2 3( ) 0 0 1 2 4 5 6 7 1 2 4 1 2 4 5 7 1 2 4 5 6 1 2 4 5 6 7 ' x x x x x x x x x x x x x x x x x x x x z x x x x x x
1.4线性规划问题的解概念 ÷1可行解 2基 今3.基可行解 4可行基
1.4 线性规划问题的解概念 ❖ 1.可行解 ❖ 2.基 ❖ 3.基可行解 ❖ 4.可行基
1.4线性规划问题的解的概念 1.可行解 定义 满足约束条件(1-5)、(1-6)式的解X=(x1x2,…,xn), 称为线性规划问题的可行解,其中使目标函数达到最 大值的可行解称为最优解。 maxz=∑cx ∑a1x1=b,1=12…m(1-5) x1≥0,j=1,2…,n(1-6)
1.4 线性规划问题的解的概念 ❖ 定义 满足约束条件(1-5)、(1-6)式的解X=(x1 ,x2，…，xn ) T ， 称为线性规划问题的可行解，其中使目标函数达到最 大值的可行解称为最优解。 = − = = − = − = = x , j , , ,n ( ) a x b ,i , , m ( ) max z c x ( ) j n j i j j i n j j j 0 1 2 1 6 1 2 1 5 1 4 1 1 1. 可行解
1.4线性规划问题的解的概念 2.基,基向量,基变量 B是系数矩阵A中的mxm阶价非奇异子矩阵(B≠0) 称B为线性规划问题的基。 12 B= |=(P,P2…Pm) amI am2 P/(=12…m)为基向量, x(=12,m为基变量
1.4 线性规划问题的解的概念 ( ) ( ) 为基变量。 为基向量， 称 为线性规划问题的基。 是系数矩阵 中的 阶非奇异子矩阵 x ( 1,2, ) P ( 1,2, ) , , B A B 0 j j 1 2 1 2 2 1 2 2 2 1 1 1 2 1 j m j m P P P a a a a a a a a a B B m m m m m m m m m = = = = 2. 基，基向量，基变量