结果: 在顶点取到唯一最优解 有最优解 有无穷多最优解 线性规划问题的解→ 无最优解→ 解无界 可行域为空集 对一般的线性规划问题是否在顶点中存在最尤解?
结果： 线性规划问题的解 无最优解 有最优解 有无穷多最优解 在顶点取到唯一最优解 可行域为空集 解无界 对一般的线性规划问题，是否在顶点中存在最优解？
四线性规划解的概念和性质 线性规划解的概念 (LP) max z=cx (1) Ax=b (2) st x≥0 (3) 可行解:满足(2)、(3)式的解x=(x1,x2,…,xn)称为 (LP)的可行解。 可行域:D={x|4=b,x≥0} 定理线性规划问题的可行域D是凸集 证明:任取x1,x2∈D,0≤≤1
四.线性规划解的概念和性质 1.线性规划解的概念 (LP) z c x T max = = 0 . . x Ax b s t (1) (2) (3) 的可行解。 可行解：满足（ ）、（ ）式的解 称为 ( ) 2 3 ( , , , ) 1 2 LP x x x x T = n 可行域：D = { x|Ax = b, x 0}。 定理 线性规划问题的可行域D是凸集。 证明： 任取 x1 , x2 D, 0 1
A(xx1+(1-)x2)=A4x1+(1-x) b+(1-1)b b 所以Ax1+(1-1)x2∈D。即D是凸集。 顶点:设S为凸集,x∈S。如果不存在x≠x2∈S,及0<几<1。 使x=x+(1-4)x2,则称x为S的一个顶点
1 2 1 2 A(x + (1 − )x ) = Ax + (1 − )Ax b b b = = + (1 − ) 所以x1 + (1− )x2 D。即D是凸集。 使 ，则称 为 的一个顶点。 顶点：设 为凸集， 。如果不存在 ，及 。 x x x x S S x S x x S 1 2 1 2 (1 ) 0 1 = + − x 1 x 2 x
基:设A为m×n的系数矩阵,秩为m若B为A4中m×m阶的非 退化子阵,则称B为4的(或(LP问题)一个基 设基B=(P1,P2;…,Pm)称P(=1,…,m)为基向量,称P 对应的变量x;(=1,…,m)为基变量,不是基变量的变量称为 非基变量。 已知r(Amxn)=m,不妨设A的前m列向量线性无关,则可取 B=(P1,P2,…,Pm)为基,则x1, "m 为基变量 因为 Ax= b 即 B1x1+…+Pmm+Pm+1xm+…+Pnxn=b 所以Bx1+…+Pnxm=b-Pn+xm nn
退化子阵，则称 为 的 或 问题 一个基。 基 设 为 的系数矩阵 秩为 。若 为 中 阶的非 ( ( ) ) : , B A LP A m n m B A m m 非基变量。 对应的变量 为基变量，不是基变量的变量称为 设基 称 为基向量，称 ( 1, , ) ( , , , ), ( 1, , ) 1 2 x j m B P P P P j m P j i i i m i j i j = = = 为基，则 为基变量。 已知 ，不妨设 的前 列向量线性无关，则可取 m m m n B P P P x x r A m A m ( , , , ) , , ( ) = 1 2 1 = 因为 Ax = b 即 P1 x1 ++ Pm xm + Pm+1 xm ++ Pn xn = b 所以 P1 x1 ++ Pm xm = b − Pm+1 xm −− Pn xn