几种特殊规划
几种特殊规划
几种特殊规划 (1) 线性规划 (2) 整数规划 (3) 0-1规划 (4) 二次规划 (5) 多目标规划 2
2 （ 1）线性规划 （ 2）整数规划 （ 3 ） 0 - 1规划 （ 4）二次规划 （ 5）多目标规划 几种特殊规划
一、线性规划
3 一、线性规划
1、引例连续投资10万元于4个项目。各项目投资时间和本利情况如下项目A：从第1年到第4年每年初要投资，次年末回收本利1.15倍项目B：第3年初投资，到第5年末回收本利1.25倍最大投资4万元项目C：第2年初投资，到第5年末回收本利1.40倍最大投资3万元，每年初投资，每年末回收本利1.11倍。项目D：求：如何分配投资资金使得5年末总资本最大？
4 1、引例 连续投资10万元于4个项目。各项目投资时间和本 利情况如下： 项目A：从第1年 到第4年每年初要投资，次年末 回收本利1.15倍。 项目B：第3年初投资，到第5年末回收本利1.25倍， 最大投资4万元。 项目C：第2年初投资，到第5年末回收本利1.40倍， 最大投资3万元。 项目D：每年初投资，每年末回收本利1.11倍。 求：如何分配投资资金使得5年末总资本最大？
解：设xik(i=1,2,3,4,5; k=A,B,C,D)表示第年初投资第k项目的资金数。年份25134项目AX1AX3AX4AX2ABX3BCX2CDXiDX4DXsDX2DX3D
5 解： 1 2 3 4 5 A x1A x2A x3A x4A B x3B C x2C D x1D x2D x3D x4D x5D 项目 年份 设xik( i =1,2,3,4,5; k =A,B,C,D)表示第i年初投 资第k项目的资金数
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）若可行解集有界，则线性规划问题的最优值 一定可以在其顶点上达到。 因此线性规划的最优解只需从其可行解集的 有限个顶点中去寻找。 顶点所对应的可行解称为基本可行解