01线性规划.pptVIP

2 最优解判断定理 1.对解X，若所有非基变量的检验数?j全﹤0，则X为最优解 3.选进基变量、离基变量 ①进基变量的确定——最大法则：选正检验数最大的非基变量进基,Max { ? j∣ ? j＞0}= ? k , 则选Xk进基 Max{2，3}=3选 X2 进基 ②离基变量的确定——最小比值法则：各约束方程的右端常数和进基变量正系数的比值。 4.迭代，建新表 上例：Max z=3X1+ X2 2X1+ 3 X2 ≤4 ① 3X1 + X2 ≤5 ② X1， X2 ≧0 ③ 基本解(X1, X2 X3, X4 )T A：(11/7,2/7,0,0)T B：(5/3,0,2/3,0)T C：(2 , 0 , 0 ,-1)T D：(0 ,5 ,-11 ,0)T E：(0 ,4/3 ,0 ,11/3)T F：( 0 ,0 ,4 , 5 )T 基本可行解A、B、E、F 最优解A、B 线性规划问题解的几何意义 ⑴ 0 1 2 3 1 2 x2 x1 ⑵ A B C D F E 可行解：满足约束条件 ①②③的解为线性规划问题的可行解(可行域内各点） 基本解：图中各约束线之间的交点A,B,C,D,E,F都是基本解 基本可行解:可行域的各顶点A,B,E,F 最优解:使目标函数达到最大值的可行解A、B线段上各点 (11/7,2/7,0,0)T 一、基本概念 1.凸集：给定一个点集K（n维欧氏空间）在集合内任取两点X1∈K,X2∈K,如果X1、X2连线上的点X=αX1+(1-α)X2∈K(0≤α≤1 ),也在集合内，则K为凸集。 ﹒ ﹒ X（1） X（2） X ﹒ ﹒ ﹒ ﹒ X（1） X（2） X 2.凸组合：设X(1)、X(2) …… X(k)为n维空间中的K个点，若存在一组数?1 ?2…… ?k且0≤?i≤1，∑?i=1使得X=?1X（1）+?2X（2）+……+?k X（k）,则称X为X(1)、X(2)、……X(k)的凸组合。 3.顶点：设K为凸集,有点X∈K,若X不能用K内不同两点X(1)、X(2)线性组合表示为X= ? X（1）+（1- ? ）X（2） （0＜? ＜1），即X不在集合内任意两点 X（1） 、 X（2）连线上，则X为顶点(极点)。 ﹒ ﹒ X（1） X 凸集 二、解的性质 定理1：若线性规划问题存在可行域，则其可行域为凸集。 定理2：线性规划问题的基可行解对应于可行域顶点 定理3 ：LP 问题有最优解,一定可在顶点上得到 单纯形法引例 例：求下面LP问题的最优解 Max z=2X1+3X2+0X3+0X4+0X5 ① X1+2X2 +X3 =8 4X1 +X4 =16 ② 4X2 +X5 =12 X1, X2 ,X3 ,X4 ,X5 ≧0 ③ 解：1.确定初始基本可行解 A= 140 204 100 010 001 初始可行基B1=（P3,P4,P5）, X3 , X4 , X5—基变量 X1, X2 —非基变量 将基变量用非基变量表示由②得 X3 =8 -X1- 2X2 X4 =16 -4 X1 ④ X5 =12 -4X2 令X1,X2=0，得初始基本可行解 X（1）=(0,0,8,16,12)T ,Z=0 2.最优解判断：④代入①中得 Z=0+2 X1+3 X2 ⑤ X1↑→Z↑,X2 ↑→Z↑ 3.由一个基本可行解→另一基可行解(选进基变量和离基变量) 3＞2,选X2→进基变量, X1仍为非基变量X1=0， 检验数 选X2进基,由④要保证解的可行性,须满足: X3 =8 -X1 - 2X2 ≥0, X2≤8/2 X4 =16 -4X1 ≥0 X5 =12 -4 X2 ≥0 , X2≤12/4 X2≤Min{8/2,12/4}, X2最大可能取值为3 当X2=?= Min