(数学模型 第二节 线性规划模型的解
第二节 线性规划模型的解
、模型标准化 (数学模型 标准形式 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