(数学模型 第二节 线性规划模型的解
第二节 线性规划模型的解
、模型标准化 (数学模型 标准形式 mIn Z ∑ LP st ∑ b,i=1,2,…,m j=1 ≥0 n 矩阵表示:minz=CX st AX= b X20 PP P 12 n 其中,C=(c1C2…,Cn) b=( 190299 n nt 2
一、模型标准化 标准形式 LP = = n j j xj z c 1 mins t a x bi i m n j ij j . , 1,2, , 1 = = xj 0, j = 1,2, ,n 矩阵表示： min z = CX X O s t AX b . = 其中, ( , , , ), 1 2 n C = c c c ( , , , ), b = b1 b2 bm = m m mn n n a a a a a a a a a A 1 2 21 22 2 11 12 1 P1 P2 Pn
(数学模 向量表示:minz=CX st x, P+x2 P2+.+xp=b 若(1)mxx=∑cx,则令z=-xn 目标函数化为:mnz=∑(-c1)x 两个模型的最优解相同,最优目标值有关系: z (2)∑anx-n1≥b,n≥0剩余变量 ∑x,+≤,20松弛变量 (3)x1是自由变量,则令x1=l1-V,2,v1≥0
向量表示： min z = CX s.t x1P1 + x2P2 ++ xnPn = b X O 若 （1） max , 1 0 = = n j j xj x c , x0 则令 z = − = = − n j j xj z c 1 目标函数化为：min ( ) 两个模型的最优解相同，最优目标值有关系： x = −z 0 (2) , 1 i n j aij xj b = －yi yi 0 剩余变量 , 1 i n j aij xj b = +yi yi 0 松弛变量 (3) xi 是自由变量，则令 xi = ui − vi , ui ,vi 0
不便用微分 (数学模型 法求解 min Z= CX st X= b 可行域可行解 X≥0 s={XAX=b,X≥O S是一个凸集∫凸多面体有界) 极点 或为无界的凸区域 单纯形法就是从某一个极点开始,沿棱到另一极点 的迭代,经有限步求出最优解的方法。 讨论步骤:1.先将模型变形,缩小搜索范围,变为 在有限个可行解(极点)中找最优解。 2.介绍如何找出(迭代)最优解
二、单纯形法 min z = CX X O s t AX b . = S = X | AX = b, X O 可行域 可行解 讨论步骤：1. 先将模型变形，缩小搜索范围，变为 在有限个可行解（极点）中找最优解。 2. 介绍如何找出（迭代）最优解。 S是一个凸集 凸多面体(有界) 或为无界的凸区域 • 极点 单纯形法就是从某一个极点开始，沿棱到另一极点 的迭代，经有限步求出最优解的方法。 不便用微分 法求解
数学模型 1.设r(4)=m(即无多余的约束条件) 则A中有m个列向量线性无关: B=(P,B,…,Pn)LP的一个基矩阵 N=(其余向量) 非基矩阵 XB=(x1,x1,…,xn) 或XB=(x BI 基变量 n X=(其余变量) 非基变量 于是A=(B,N,X B C=(CB,CN) N 模型中约束条件:Ax=(B,NXn=Bxn+NXx=b
1. 设 r(A) = m （即无多余的约束条件） 则A 中有 m 个列向量线性无关： j j jm P ,P , ,P B = （ 1 2 ） LP 的一个基矩阵 N =（其余向量） 非基矩阵 T B j j jm X (x , x , , x ) = 1 2 T B B B Bm X (x , x , , x ) 或 = 1 2 基变量 = (其余变量) X N 非基变量 于是 A = (B, N ), , = N B X X X ( , ) C = CB CN 模型中约束条件： = N B X X AX (B, N ) = BXB + NX N = b
→XB=Bb-B1NX(:B可逆)(数学丝 X 目标函数:CX=(CB,CNM/CnXB+CXN B CB( b-B NXN)+CNXN BB6-(CBBN-CN)X 模型改写为:minx=CBb-(CBBN-CN)XN .t X=B b-B M N X≥0 或 mn 3=yoo Ok k 10 IkK xk非基变量 io ik k B 0 k x≥0,j=1,2 12
( ) XB = B −1 b − B −1NX N B可逆 目标函数： = N B B N X X CX (C ,C ) = CB XB + CN X N = CB B b − B NX N + CN X N − − ( ) 1 1 CBB b CBB N CN X N ( ) 1 1 = − − − − 模型改写为： CBB b CBB N CN X N min z ( ) 1 1 = − − − − X O s t XB B b B NX N = − −1 −1 . 或 min z = y00 −− y0k xk − s.t xB1 = y10 −− y1k xk − xBi = yi0 −− yik xk − xBm = ym0 −− ymk xk − xj 0, j = 1,2, ,n xk 非基变量 9 10 11 12
(数学模型 或 mn = yoo ∑ st x 0-∑ e∈N x;≥0,j=1,2,…,n B Bb 是AX=b的一个解,称为基本解; B b 若Xn=Bb≥O,称 基可行解 相应的B称为可行基; 若ⅹ既是基可行解,又是最优解,则称为基最优解 相应的B称为最优基,记为B。 #
或 = − j N j xj z y y min 00 0 = − j N B i ij xj s t x y y i 0 . xj 0, j = 1,2, ,n = − O B b X X N B 1 是AX=b 的一个解， 称为基本解； , 1 XB = B b O 若 − − O B b 1 称 为基可行解， 相应的 B 称为可行基； 若 X 既是基可行解，又是最优解，则称为基最优解 相应的 B 称为最优基，记为 。 B ＃
(数学模型 可行解与基可行解的联系 可以证明: (1)LP有可行解→有基可行解 (2)LP有最优解→有基最优解 (3)LP最优解唯一→基最优解唯一,且相同; LP的最优解不唯一(S有界) 设X1,…,X为全部基最优解→ X=∑1X,4120,∑4=1是LP的全部最优解 i=1 由(1)(2)知,若有最优解,必可在基可行解中找到, 基可行解的个数≤基本解个数≤Cn 可证:基 可行域S 基本解 可行解为 S的极点。 基可行解
可行解与基可行解的联系 （1）LP 有可行解 有基可行解 （2）LP 有最优解 有基最优解 （3）LP 最优解唯一 基最优解唯一，且相同； LP 的最优解不唯一（S有界） k X , ,X 设 1 为全部基最优解 , 0, 1 1 1 = = = = k i i i k i i X iX 是LP 的全部最优解。 可以证明： 由（1）（2）知，若有最优解，必可在基可行解中找到， m Cn 可行域S • • • • • • • • 基本解 基可行解 基可行解的个数 基本解个数 S • 可证：基 可行解为 S的极点
2.单纯形法判别定理 数学模型)6 设B=(B,Bb,…,P,)是可行基,即(B ≥0 (1)若检验数y≤0(i=1,2,…,n),则最优解 Bb 最优目标值z=yo (2)若彐yak>0,k∈N 1°若k≤0(i=1,2,…,m),则LP无下界; 2°若yg>0(1≤s≤m), 则可得使目标值不增的新的可行基。 按(3)(4)迭代
2. 单纯形法判别定理 ( , , , ) j1 j2 jm 设 B = P P P 是可行基， O O B b −1 即 （1）若检验数 0 ( 1,2, , ), y0 j j = n 则最优解 , 1 = − O B b X 最优目标值 00 z = y （2）若 y0k 0,k N 1° 若 y 0 (i 1,2, ,m), ik = 则 LP 无下界； 2° 若 y 0(1 s m), sk 则可得使目标值不增的新的可行基。 按（3）（4）迭代。 6
(3)1°让P(x)入基,即成为基向量(变量) 2°令0=min{0y>0=1, 0≥0 k 则P(x)出基,得新基: B=(P 991k9 oPi 最小比值法贝 (4)计算新可行解: B B12 ,k )=(y10,y20,…,ym)C≥O) X=o 新目标值:z=y0(≤yo) 新系数:J,y 返回到(1)再判别、迭代
（3） 1° 让 ( ) Pk xk 入基，即成为基向量（变量） 2° 令 = y i = m y y ik ik i min 0, 1,2, , 0 0 0 = lk l y y ( ) l l 则 Pj xj 出基， 得新基： ( , , , , ) j1 k jm B = P P P l 最小比值法则 （4） 计算新可行解： T B B k Bm X (x , , x , , x ) = 1 ( , , , )( ) ' 0 ' 20 ' = y10 y ym O X N = O 新目标值： ( ) 00 ' 00 z = y y 新系数： j ij y , y ' 0 返回到（1）再判别、迭代。 6 ＃