22基本定理 ◆定理1若线性规划问题存在可行 域,则其可行域 D=x∑Px=b20 ◆是凸集
2.2 基本定理 定理1 若线性规划问题存在可行 域，则其可行域 是凸集。 = = = n j j j j D X P x b x 1 | , 0
◆引理1线性规划问题的可行解 X=(x1x2-×y)为基可行解的充分必要 条件是X的正分量是线性独立的 ◆定理2线性规划问题的基可行解X对 应于可行域的顶点 ◆引理2若K是有界凸集,则任意一点 X∈K可表示为K的顶点的凸组合。 ◆定理3若可行域有界,线性规划问 题的目标函数一定可以在其可行域的 顶点上达到最优
引 理 1 线 性 规 划 问 题 的 可 行 解 X=(x1 ,x2 ,…,xn ) T为基可行解的充分必要 条件是X的正分量是线性独立的。 定理 2 线性规划问题的基可行解X对 应于可行域的顶点。 引理 2 若K是有界凸集，则任意一点 x∈K可表示为K的顶点的凸组合。 定理3 若可行域有界，线性规划问 题的目标函数一定可以在其可行域的 顶点上达到最优
◆有时目标函数可能在多个顶 达到最大值。这时这些顶点的 凸组合上也达到最大值。称这 种线性规划问题有无限多个最 优值
有时目标函数可能在多个顶点 达到最大值。这时这些顶点的 凸组合上也达到最大值。称这 种线性规划问题有无限多个最 优值
s3单纯形法 ◆3.1单纯形法举例
§3 单纯形法 3.1 单纯形法举例
例6试以例1来讨论它的求解 ◆例1的标准型为 ◆maxz=2×1+3×2+0X3+0×4+0X5 1+2X2+X3 8 4x +XA 16 4x TX 5 12 ◆X1≥0,j
例6 试以例1来讨论它的求解。 例1的标准型为 max z=2x1+3x2+0x3+0x4+0x5 x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 xj ≥0，j=1,2,…,5