运筹学单纯形.docVIP

§1.4 线性规划问题的几何解释 对于只有两个变量的线性规划问题，可以在二维直角坐标平面上表示线性规划问题。 例1.8 max z= x1 +3x2 s.t. x1 +x2 ≤6 (1) -x1 +2x2 ≤8 (2) x1, x2 ≥0 其中满足约束(1)的点位于坐标平面上直线x1+x2=6靠近原点的一侧。同样，满足约束(2)的点位于坐标平面上直线 -x1+2x2=8的靠近原点的一侧。而变量x1，x2的非负约束表明满足约束条件的点同时应位于第一象限内。这样，以上几个区域的交集就是满足以上所有约束条件的点的全体。 我们称满足线性规划问题所有约束条件（包括变量非负约束）的向量 X=(x1，x2，…，xn)T 为线性规划的可行解（Feasible Solution），称可行解的集合为可行域（Feasible Region）。 例1.8的线性规划问题的可行域如图1.2中阴影部分所示。 为了在图上表示目标函数，令z=z0为某一确定的目标函数值，取一组不同的z0值，在图上得到一组相应的平行线，称为目标函数等值线。在同一条等值线上的点，相应的可行解的目标函数值相等。在图1.2中，给出了z=0，z=3，z=6，…，z=15.3等一组目标函数等值线，对于目标函数极大化问题，这一组目标函数等值线沿目标函数增大而平行移动的方向（即目标函数梯度方向）就是目标函数的系数向量C=(c1,c2,…,…,cn)T；对于极小化问题，目标函数则沿-C方向平行移动。 在以上问题中，目标函数等值线在平行移动过程中与可行域的最后一个交点是B点，这就是线性规划问题的最优解，这个最优解可以由两直线 x1+ x2=6 -x1+2x2=8 的交点求得 最优解的目标函数值为 为了将以上概念推广到一般情况，我们给出以下定义： 定义1.1 在n维空间中，满足条件 ai1x1+ai2x2+…+ainxn=bi 的点集 X=(x1，x2，…，xn)T 称为一个超平面。 定义1.2 满足条件 ai1x1+ai2x2+…+ainxn≤（或≥）bi 的点集 X=(x1，x2，…，xn)T 称为n维空间中的一个半空间。 定义1.3 有限个半空间的交集，即同时满足以下条件的非空点集 a11x1+a12x2+…+a1nxn≤（或≥）b1 a21x1+a22x2+…+a2nxn≤（或≥）b2 ……… am1x1+am2x2+…+amnxn≤（或≥）bm 称为n维空间中的一个多面体。 运用矩阵记号，n维空间中的多面体也可记为 AX≤（或≥）b 每一个变量非负约束xi≥0（i=1，2，…，n）也都是半空间，其相应的超平面就是相应的坐标平面xi=0。 在图1.2中，我们看到，线性规划问题的可行域是一个凸多边形。容易想象，在一般的n维空间中，n个变量，m个约束的线性规划问题的可行域也应具备这一性质。为此我们引进如下的定义。 定义1.4 设S是n维空间中的一个点集。若对任意n维向量X1(S，X2(S，且X1(X2，以及任意实数(（0(((1），有 X=(X1+(1-()X2(S 则称S为n维空间中的一个凸集（Convex Set）。点X称为点X1和X2的凸组合。 以上定义有明显的几何意义，它表示凸集S中的任意两个不相同的点连线上的点（包括这两个端点），都位于凸集S之中。 (a)凸集 (b)凸集 (c)凸集 (d)非凸集 (e)非凸集 (f)非凸集 从图1.2还可以看出，线性规划如果有最优解，其最优解必定位于可行域边界的某些点上。在平面多边形中，这些点就是多边形的顶点。在n维空间中，我们称这样的点为极点（Extreme Point）。 在凸集中，不能表为不同点的凸组合的点称为凸集的极点。 定义1.5 设S为一凸集，且X(S，X1(S，X2(S。对于0(((1，若 X=(X1+(1-()X2 则必定有X=X1=X2，则称X为S的一个极点。 运用以上的定义，线性规划的可行域以及最优解有以下性质： 1、若线性规划的可行域非空，则可行域必定为一凸集。 2、若线性规划有最优解，则最优解至少位于一个极点上。 这样，求线性规划最优解的问题，从在可行域内无限个可行解中有哪些信誉好的足球投注网站的问题转化为在其可行域的有限个极点上有哪些信誉好的足球投注网站的问题。 最后，来讨论线性规划的可行域和最优解的几种可能的情况。 1、可行域为封闭的有界区域 (a)有唯一的最优解； (b)有一个以上的最优解； 2、可行域为非封闭的无界区域 (a)有唯一的最优解； (b)有一个以上的最优解； (c)目标函数无界（即虽有可行解，但在可