求max无界 但求min有唯一解 (4)无可行解 可行域与最优解间的关系: 可行域 最优解 空集 无最优解(无可行解) 有界集 唯一最优解 多重解 无界集 无有限最优解(无界解) 结论:(1)LP问题的可行域是凸集(凸多边形,凸多面体,…)
-11- 求max无界 但求min有唯一解 （4）无可行解 可行域与最优解间的关系： 可行域 最优解 空 集 无最优解（无可行解） 有界集 唯一最优解 多重解 无界集 无有限最优解（无界解） 结论：（1）LP问题的可行域是凸集（凸多边形，凸多面体，…）； 0 x2 0 x1 x1 x2
(2)LP问题最优解若存在,则必可在可行域的顶点上得到: (3)LP问题的可行域的顶点个数是有限的 (4)若LP问题有两个最优解,则其连线上的点都是最优解。因 此,求解LP问题可转化为如何在可行域的顶点上求出使目标函数值达到最 优的点的问题 2基可行解的几何意义 对例1LP问题标准化为 +2 4x.+ 16 4. ≥0 可求得所有的基本解 x(1=(00.8,16,12)(0点)x(2)=(40.4,0,12)(Q点) x(3)=(4,2,0,0,4)(Q2点)x4=(2,3,0.8,0)(Q3点) x(5=(0,3,2,16,0)(Q4点)x6(4,3,-2,0,0)(C点) x(7=(8,0,0,-16,12)(A点)x(8=(0,4,0,16,-4)(B点) 但A、B、C三点是非可行域上的点,即非可行解。因此,x),x(2),x3), x(4),x(5)才是基可行解,它们与可行域的顶点相对应。于是还有 结论:(5)对于标准型的LP问题,X是基可行解的充要条件是X为可行 域的顶点。 (6)LP问题可行域顶点的个数=基可行解的个数≤基的个数≤Cmn 3.图解法只适用于两个变量(最多含三个变量)的LP问题。 4求解LP问题方法的思考: ①完全枚举法,对m、n较大时,Cmn是一个很大的数,几乎不可能: ②从可行域的一个顶点(基可行解)迭代到另一个顶点(基可行解)
-12- （2）LP问题最优解若存在，则必可在可行域的顶点上得到； （3）LP问题的可行域的顶点个数是有限的； （4）若LP问题有两个最优解，则其连线上的点都是最优解。因 此，求解LP问题可转化为如何在可行域的顶点上求出使目标函数值达到最 优的点的问题。 2.基可行解的几何意义 对例1 LP问题标准化为 maxZ=2x1+3x2 + = + = + + = , , 0 4 12 4 16 2 8 1 5 2 5 1 4 1 2 3 x x x x x x x x x 可求得所有的基本解： x (1)=(0,0,8,16,12)T(0点),x(2)=(4,0,4,0,12)T(Q1点) x (3)=(4,2,0,0,4)T(Q2点),x(4)=(2,3,0,8,0)T(Q3点) x (5)=(0,3,2,16,0)T(Q4点),x(6)=(4,3,-2,0,0)T(C点) x (7)=(8,0,0,-16,12)T(A点),x(8)=(0,4,0,16,-4)T(B点) 但A、B、C三点是非可行域上的点，即非可行解。因此，x (1)，x (2)，x (3)， x (4)，x (5)才是基可行解，它们与可行域的顶点相对应。于是还有 结论：（5）对于标准型的LP问题，X是基可行解的充要条件是X为可行 域的顶点。 （6）LP问题可行域顶点的个数=基可行解的个数≤基的个数≤Cmn 3.图解法只适用于两个变量（最多含三个变量）的LP问题。 4.求解LP问题方法的思考： ①完全枚举法，对m、n较大时，Cmn是一个很大的数，几乎不可能； ②从可行域的一个顶点（基可行解）迭代到另一个顶点（基可行解）
§2单纯形法与计算机求解 1解LP问题单纯形法的基本思路 求出一个初始基可行解 y 判别此基可行解是否 优 停 求出使目标函数值得到 收善的基可行解 2单纯形法的计算步骤(表格形式) (1)建立初始单纯形表,假定B=,b≥0 设maxZ=cx1+c2x2+…+cnx1 x1+a1mxmn1+…anxn=b x2+a2mm+1 +.a2nx,=b2 xm+am+xm+1+…amxn=bn x≥0(=12,…,n) 将目标函数改写为:-Z+c1x1+c2x2+…+cnxn=0 把上述方程组和目标函数方程构成n+1个变量,m+1个方程的方程组 并写成增广矩阵的形式:
-13- §2 单纯形法与计算机求解 1.解LP问题单纯形法的基本思路： 求出一个初始基可行解 y 判别此基可行解是否 最 优 解 N 求出使目标函数值得到 改善的基可行解 2.单纯形法的计算步骤（表格形式） （1）建立初始单纯形表，假定B=I，b≥0 设maxZ=c1x1+c2x2+…+cnxn = + + = + + = + + = + + + + + + 0 ( 1,2, , ) 1 1 2 2 1 1 2 2 1 1 1 1 1 1 x j n x a x a x b x a x a x b x a x a x b j m mm m mn n m m m n n m m n n 将目标函数改写为：-Z+c1x1+c2x2+…+cnxn=0 把上述方程组和目标函数方程构成n+1个变量，m+1个方程的方程组， 并写成增广矩阵的形式： 停
In b b 000 1 a 以非基变量表示基变量形式x=b-∑ax代入Z中的基变量有 cX ∑c-∑∑(ca)x+∑cx ∑c-∑Cca-c)x 令=∑5,z,=∑ 于是Z=20+∑(2-c1)x 因此,上述的增广矩阵就可写成 Zx1x2……xmXm+1 0 a b 100 0∑cam+1-cm 14-
-14- -Z x1 x2 … xm xm+1… xn b 0 1 0 … 0 a 1m+1 … a 1n b 1 0 0 1 … 0 a 2m+1 … a 2n b 2 0 0 0 … 1 a mm+1 … a mn b m -1 c1 c2 … cm cm+1… cn 0 以非基变量表示基变量形式 = = − n j i i ij j x b a x 1 代入Z中的基变量,有 = = + = + = − + m i n j m n j m i i ij j j j Z c b a X c x 1 1 1 ( ) = = = + = + = − + m i m i n j m n j m i i i i j j j j c b c a x c x 1 1 1 1 ( ) = = + = = − − m i n j m j j m i i i i ij c b c a c x 1 1 1 ( ) 令 = = = = m i m i i i j i i j Z c b Z c a 1 1 0 , 于是 = + = + − n j m o j j j Z Z Z c x 1 ( ) 因此，上述的增广矩阵就可写成： Z x1 x2 … xm xm+1… xn b 0 1 0 … 0 a 1m+1 … a 1n b 1 0 0 1 … 0 a 2m+1 … a 2n b 2 0 0 0 … 1 a mm+1 … a mn b m 1 0 0 … 0 1 1 1 + = + − m m i i im c a c …= m i iain c 1 －cn = m i ibi c 1
再令 则上述增广矩阵可写成下面表格形式:即初始单纯形表T(B) Cm+ Xm+l·"Xn b a :·……: ←G检验数 上述初始单纯形表可确定初始可行基和初始基可行解: B=(P1,P2,…Pm)=,x=(b,b2,…,bhm,0……0 从初始单纯形表建立的过程可以看到以下事实 (1)凡LP模型中约束条件为“≤”型,在化为标准型后必有B=,如 果b≥0,则模型中约束方程的各数据不改变符号照抄在表中相应的位置。 目标函数非基变量的系数则以相反数填入检验数行各相应位置。 (2)在单纯形表中,凡基变量所在的列向量必是单位列向量,其相应 的检验数均为零。 (3)Z。=∑cb,1=21-c1=∑c可0-c1(=m+1…n) 更好表现一般规律的在矩阵形式的单纯形表中 设MaxX=CX MaxZ=CX+OXL r≥0其标准型为/1x=b A<6 x,x2≥0 15-
-15- 再令 = = − = − m i j j j j iaij c Z c c 1 则上述增广矩阵可写成下面表格形式：即初始单纯形表T（B） Cj C1……Cm cm+1……cn i CB xB b x1……xm xm+1……xn C1 x1 b 1 1……0 a1m+1……a1n C2 x2 b 2 0……0 a2m+1……a2n ： ： ： ： ： ：………： Cm xm b m 0……1 amm+1……amn Z Z0 0……0 m+1……n j检验数行 上述初始单纯形表可确定初始可行基和初始基可行解： B=(P1,P2,…,Pm)=I, x=(b1,b2,…,bm, 0……0)T 从初始单纯形表建立的过程可以看到以下事实： （1）凡LP模型中约束条件为“≤”型，在化为标准型后必有B=I，如 果b≥0，则模型中约束方程的各数据不改变符号照抄在表中相应的位置。 目标函数非基变量的系数则以相反数填入检验数行各相应位置。 （2）在单纯形表中，凡基变量所在的列向量必是单位列向量，其相应 的检验数均为零。 （3） = = = = − = − = + m i m i Z cibi j Z j c j ciai j c j j m n 1 1 0 , ( 1, ) 更好表现一般规律的在矩阵形式的单纯形表中 设MaxX=CX MaxZ=CX+0XL x 0 A x b 其标准型为 + = , L 0 x L x x A Ix b