运筹学课件-第二节-图解法.pptVIP

2021/3/17 * 基 x1 x2 x3 x4 x5 Z 是否基可行解 P3,P4,P5 0 0 5 10 4 5 P2,P3,P4 0 4 5 2 0 17 P1,P4,P5 5 0 0 5 4 10 P2,P3,P5 0 5 5 0 -1 20 P1,P3,P5 10 0 -5 0 4 15 P1,P2,P5 5 2.5 0 0 1.5 17.5 P1,P2,P4 5 4 0 -3 0 22 P1,P2,P3 2 4 3 0 0 19 2021/3/17 * 基的概念的理解 对于线性规划的约束条件 AX=b X≥0 设B是A矩阵中的一个非奇异的m×m子矩阵,则称B为线性规划的一个基。 设B是线性规划的一个基,则A可以表示为 A=[ B, N ] X也可相应地分成 2021/3/17 * 其中XB为m×1向量,称为基变量,其分量与基B的列向量对应;XN为(n-m)×1向量,称为非基变量，其分量与非基矩阵N的列对应。这时约束等式AX=b可表示为 或 BXB+NXN=b 若XN取确定的值，则XB有唯一的值与之对应 XB=B-1b-B-1NXN 2021/3/17 * 特别,取XN=0,这时有XB=B-1b。 线性规划的解称为线性规划与基B对应的基解。 若其中基变量的值XB=B-1b?0,则称以上的基解为一基可行解，相应的基B称为可行基。 2021/3/17 * 基本概念: 凸集——如果集合C中任意两个点X1,X2,其连线上的所有点也都是集合C中的点,则称C为凸集． 用数学解析式表示:若任意两点X１∈C,X2∈C的连线上的一切点: αX1+（1-α）X2∈ C （0α1），则称C为凸集。 1.3.2凸集及其顶点 × × 2021/3/17 * 顶点——设C是凸集,对任何的 X１?C,X2? C 有 X≠αX１+（1-α）X２　　（0α1） 则称X为C的一个顶点。 说明集合C中不存在任何两个不同的点X1,X2,使X成为这两个点连线上的一个点. 2021/3/17 * 1.3.3几个基本定理 定理1 线性规划问题存在可行解,则问题的可行域 是凸集。 证明思路:根据凸集定义,采用直接法证明; 具体步骤:①从C中任取两个不同的点, 应满足 可行解定义中相应的条件; ②证明X=αX(1)+(1-α)X(2)∈D (利用①,证明X满足凸集定义中相应的条件) 2021/3/17 * X1,x2 为C内任意两点,将两点代入约束条件: X1,X2连线上的任意一点X 将X代入约束条件 X为C内任意点,所以C为凸集 2021/3/17 * 引理 线性规划问题的可行解 为基可行解的 充分必要条件是X的正分量所对应的系数列向量线性独立。 2021/3/17 * 证明要点:引理: X为LP的基本可行解=X的正分量所对应的系数列向量线性无关 必要性→由基本可行解定义直接证得 充分性←正分量K个线性无关 k=m →X=(x1,x2,…,xm,0,…0)T即为 基本可行解 km →补齐得基→退化的基本可行解 2021/3/17 * 定理２ 线性规划问题的基可行解X对应线性规划问题可行域的顶点。 证明思路: 首先可行域非空有界就肯定有最优解 本定理要证明的是 X不是可行域的顶点 X不是基可行解 2021/3/17 * (1).X不是基可行解 不是可行域的顶点 不失一般性,假设X的前m个分量为正,所以有: 由引理得到P1,P2,…,Pm,线性相关,存在一组不全为0的数k1,k2,…,km,使 2021/3/17 * u可以这样选取:使所有的i=1,2,…,m X不是可行域的顶点 2021/3/17 * (2).X不是可行域的顶点 X不是基可行解 X不是基可行解 2021/3/17 * 定理３ 若线性规划问题有最优解,一定存在一个基可行解是最优解． 证明:设 是线性规划的最优解 是目标函数的最大值 如果X(0)不是基可行解,由定理2得到X(0)不是顶点,可在找到另外2点 将以上两点代入目标函数有: 2021/3/17 * 启示: 1、LP的可行域一定是凸集,但是凸集不一定成为LP的可行域,而非凸集一定不会是LP的可行域。 2、线性规划的基本可行解和