xik(i=1,2,...,5; k =A,B,C,D)为第年初投k项目的资金数.则：maxZ= 1.15x4A +1.40 x2c+1.25x3B+1.11xsDX1A +Xip=10X2A+X2c+X2D= 1.11 X1DX2c≤ 3X3A +X3B+X3D =1.15 X1A+1.11 X2Ds.t.X3B≤4X4A +x4D =1.15 X2A+ 1.11 X3DX5D =1.15 X3A+ 1.11 X4DXik ≥ 0, i =1,2,...,5; k =A,B,C,D;
6 xik( i =1,2,.,5; k =A,B,C,D)为第i年初投k项目的 资金数.则： maxZ= 1.15x4A +1.40 x2C+1.25x3B+1.11x5D x1A+x1D=10 x2A+x2C+x2D= 1.11 x1D x2C 3 x3A +x3B+x3D =1.15 x1A+1.11 x2D x3B 4 x4A +x4D =1.15 x2A+1.11 x3D x5D =1.15 x3A+ 1.11 x4D xik 0, i =1,2,.,5; k =A,B,C,D; s.t
2、线性规划（LP）的一般形式：max(min)z= Zc,x,j=1n[2a,x, ≤(2,=)b,i=1,2,...,ms.t.j-1x,≥0j =1,2,,n用矩阵和向量形式表示为：max(min)z = c xAx ≤(,=)bs.t.x≥0
7 2、线性规划（LP）的一般形式： 1 1 max(min) ( , ) 1, 2, , s.t. 0 1, 2, , n j j j n ij j i j j z c x a x b i m x j n = = = = = = 用矩阵和向量形式表示为： max(min) ( , )b s.t. 0 T z c x Ax x = =
3、线性规划问题的解法（1）图解法当决策变量个数n=2时，LP问题可以通过在平面上作图的方法求解，称为图解法。（2）单纯形法是求解线性规划最早的方法，也是目前实际应用中最为有效的算法，有成熟的计算机软件。（3）Karmarkar算法针对大规模线性规划问题，20实际80年代提出的一种算法
8 3、线性规划问题的解法 （1）图解法 当决策变量个数n=2时，LP问题可以通过在 平面上作图的方法求解，称为图解法。 （2）单纯形法 是求解线性规划最早的方法，也是目前实际应 用中最为有效的算法，有成熟的计算机软件。 （3）Karmarkar算法 针对大规模线性规划问题，20实际80年代提 出的一种算法
X2图解法举例maxZ=40x,+ 80x303x +2x, = 60X1+2x2 ≤ 30,3xi+2x2 ≤ 60,S.t.202x2≤24,2x2 = 24BX1,X2 ≥0 ;A10最优解：BC线段X+2x = 30DB点 : x(1)=(6,12)T0福102030C点: x(2)=(15,7.5)TZ-1200maxZ-1200Z=-0xiax(1) + (1 - α)x(2)BC线段：x=(0≤ α≤1)X2
9 (0 1) maxZ=40x1+ 80x2 x1+2x2 30, 3x1+2x2 60, 2x2 24, x1 , x2 0; 图解法举例 s.t. 最优解：BC线段 B点 : x (1)=(6,12)T C点: x (2)=(15,7.5)T BC线段: ( ) ( ) 1 (2) 2 1 x 1 x x x x = + − = maxZ=1200 0 10 20 30 x2 D A B C 3x1+2x2 = 60 x1+2x2 = 30 2x2 = 24 10 20 30 x1 Z=1200 Z=0
4、线性规划解的性质（1）线性规划问题的可行解集（可行域）为凸集。（2）若可行解集有界，则线性规划问题的最优值一定可以在其顶点上达到。顶点所对应的可行解称为基本可行解因此线性规划的最优解只需从其可行解集的有限个顶点中去寻找。10
10 （1）线性规划问题的可行解集（可行域）为凸集。 4、线性规划解的性质 （2）若可行解集有界，则线性规划问题的最优值 一定可以在其顶点上达到。 因此线性规划的最优解只需从其可行解集的 有限个顶点中去寻找。 顶点所对应的可行解称为基本可行解