第四章运筹与优化模型

《第四章运筹与优化模型》由会员分享，可在线阅读，更多相关《第四章运筹与优化模型（38页珍藏版）》请在装配图网上搜索。

1、第四章第四章 运筹与优化模型运筹与优化模型 运筹与优化模型是在实际问题的建运筹与优化模型是在实际问题的建模中应用十分广泛的模型，其作用是为模中应用十分广泛的模型，其作用是为决策者在作决策时提供科学依据。本章决策者在作决策时提供科学依据。本章主要介绍线性规划、非线性规划、动态主要介绍线性规划、非线性规划、动态规划和层次分析法模型规划和层次分析法模型.他们的求解都他们的求解都可在可在MATLABMATLAB软件上实施，但我们主要讲软件上实施，但我们主要讲解建模原理及怎样利用手工进行计算，解建模原理及怎样利用手工进行计算，以备中学应用。以备中学应用。4.14.1线性规划模型线性规划模型一、从工厂的生

2、产安排谈起一、从工厂的生产安排谈起设某企业现有设某企业现有m m种资源种资源Ai (i=1,2,Ai (i=1,2,m),m)用于生产用于生产n n种产品种产品Bj(jBj(j=1,2.=1,2.,n),n)，每种资源的拥有量和每种，每种资源的拥有量和每种产品所消耗的资源量及单位产品的利润如下表，试产品所消耗的资源量及单位产品的利润如下表，试问如何安排生产计划可使得该企业的利润最大：问如何安排生产计划可使得该企业的利润最大：产产品品资资源源B1B2Bn总总量量A1a11a12a1nb1A2a21a22a2nb2Amam1am2amnbm利利润润c1c2cn （一）建立数学模型（一）建立数学模型

3、设产品设产品B Bj j的产量为的产量为x xj j(j(j=1,2,=1,2,n),n)，称之为决策，称之为决策变量，所得总利润为变量，所得总利润为Z Z，则要解决的问题的目标是，则要解决的问题的目标是使（总利润）函数使（总利润）函数Z=Z=c cj jx xj j有最大值，而决策变有最大值，而决策变量所受的约束条件为：量所受的约束条件为：由于目标函数和约束条件均为决策变量的线性函由于目标函数和约束条件均为决策变量的线性函数，所以该模型称为线性规划模型。数，所以该模型称为线性规划模型。即线性规划模型即线性规划模型为：（二）线性规划模型的一般形式（二）线性规划模型的一般形式矩阵形式：矩阵形式：

4、二、二元线性规划问题的图解法二、二元线性规划问题的图解法例例1 1、某工厂要安排甲、乙两种产品的生产，、某工厂要安排甲、乙两种产品的生产，已知生产甲、乙两种产品每吨所需的原材料已知生产甲、乙两种产品每吨所需的原材料A A、B B、C C数量数量如下表所示：如下表所示：甲、乙两种产品每吨利润分别为甲、乙两种产品每吨利润分别为3 3百元和百元和2 2百元。百元。试问如何安排生产可获得最大利润？试问如何安排生产可获得最大利润？甲甲乙乙 资源数量（吨）资源数量（吨）A A1 11 15050B B4 40 0160160C C2 25 5200200 解：（一）建立模型解：（一）建立模型（1 1）设决

5、策变量）设决策变量:设生产甲、乙两种产品分别为设生产甲、乙两种产品分别为x,yx,y吨；吨；（2 2）明确目标函数）明确目标函数:令令Z Z 表示所获利润表示所获利润,则则Z=3x+2yZ=3x+2y；（二）求解（二）求解（1 1）作出可行解区域作出可行解区域，并求出顶点。，并求出顶点。顶点为顶点为O(0,0),A(40,0),B(40,10),C(50/3,100/3)O(0,0),A(40,0),B(40,10),C(50/3,100/3)D(0,40)D(0,40)(2)(2)作出目标函数作出目标函数Z=3x+2yZ=3x+2y的等值线的等值线:(3)(3)求出临界等值线，得最优解。最右

6、上角的等值线求出临界等值线，得最优解。最右上角的等值线称为临界等值线。等值线称为临界等值线。等值线l l3 3为临界等值线，临界等为临界等值线，临界等值线与可行解区域的交点值线与可行解区域的交点B B（4040，1010）对应最优解：）对应最优解：x=40,y=10,x=40,y=10,最大利润为：最大利润为：140140（百元）。（百元）。c=-3-2;c=-3-2;A=1 1;4 0;2 5;b=50;160;200;A=1 1;4 0;2 5;b=50;160;200;x,fvalx,fval=linprog(c,A,blinprog(c,A,b)Optimization termina

7、ted.Optimization terminated.x=x=40.0000 40.0000 10.0000 10.0000fvalfval=-140.0000-140.0000 利用利用LINGOLINGO软件求解软件求解max=3*x1+2*x2;max=3*x1+2*x2;x1+x2=50;x1+x2=50;4*x1=160;4*x1=160;2*x1+5*x2=200;2*x1+5*x2 c=-3-2;A=2 3;2 1;b=14;9;c=-3-2;A=2 3;2 1;b=14;9;x,fvalx,fval=linprog(c,A,blinprog(c,A,b)Optimizatio

8、n terminated.Optimization terminated.x=x=3.2500 3.2500 2.5000 2.5000fvalfval=-14.7500 -14.7500 max=3*x1+2*x2;max=3*x1+2*x2;2*x1+3*x2=14;2*x1+3*x2=14;2*x1+x2=9;2*x1+x2 c=-300,-500;c=-300,-500;A=20,40;50,20;b=3000;2400;A=20,40;50,20;b=3000;2400;x,fvalx,fval=linprog(c,A,blinprog(c,A,b)Optimization term

9、inated.Optimization terminated.x=x=22.5000 22.5000 63.7500 63.7500fvalfval=-3.8625e+004-3.8625e+004 min=300*x1+500*x2;min=300*x1+500*x2;20*x1+40*x2=3000;20*x1+40*x2=3000;50*x1+20*x2=2400;50*x1+20*x2=2400;endendGlobal optimal solution found.Objective value:38625.00 Infeasibilities:0.000000 Total solv

10、er iterations:2 Variable Value Reduced Cost X1 22.50000 0.000000 X2 63.75000 0.000000 Row Slack or Surplus Dual Price 1 38625.00 -1.000000 2 0.000000 -11.87500 3 0.000000 -1.250000 三、线性规划问题的单纯形解法三、线性规划问题的单纯形解法前面我们讨论了二元线性规划问题的图形前面我们讨论了二元线性规划问题的图形解法，其关键是画出满足约束条件的可行解法，其关键是画出满足约束条件的可行解区域：解区域：“凸集凸集”。只要存在

11、最优解，则。只要存在最优解，则一定在这个凸集的某个一定在这个凸集的某个“顶点顶点”处取得最处取得最优解。这种方法清楚、直观，容易操作。优解。这种方法清楚、直观，容易操作。但对于三个或三个以上变量的线性规划问但对于三个或三个以上变量的线性规划问题，它的可行解区域就不那么好画了。那题，它的可行解区域就不那么好画了。那么这类线性规划问题，有没有一般的解法么这类线性规划问题，有没有一般的解法呢？有，就是下面我们将介绍的呢？有，就是下面我们将介绍的单纯单纯形解法。形解法。线性规划模型的标准形式：线性规划模型的标准形式：如果所给模型不是标准形式，则可用适当的方式划归如果所给模型不是标准形式，则可用适当的方

12、式划归为标准形式：为标准形式：（1 1）如果目标函数为最大，则可利用负变化化为最）如果目标函数为最大，则可利用负变化化为最小；小；（2 2）如果约束条件为）如果约束条件为“，”，则可引入松弛变，则可引入松弛变量化为等式量化为等式.例：将例：将下列线性规划（下列线性规划（LPLP）模型化）模型化为标准形式：为标准形式：单纯形解法的一般步骤：单纯形解法的一般步骤：设约束矩阵设约束矩阵A A的秩为的秩为m m，我们把矩阵，我们把矩阵A A中任意中任意m m个线性无个线性无关的列向量组成的矩阵关的列向量组成的矩阵B B为线性规划问题的基矩阵，为线性规划问题的基矩阵，对应的变量称为基变量，其它的变量称为

13、非基变量。对应的变量称为基变量，其它的变量称为非基变量。如：如：1 1、选取基变量和非基变量、选取基变量和非基变量 C C1 C C2 2 C Cn-mn-m C Cn-m+1n-m+1 C Cn n 常常 数数x x1 1 x x2 2 x xn-mn-m x xn-m+1n-m+1 x xn n检验数检验数 djd d1 1 d d2 2 d dn-mn-m d dn-m+1n-m+1 d dn nd d0 0 2 2、选主元、选主元确定把那一个非基变量调入基变确定把那一个非基变量调入基变量，并把那一个基变量调出。在检验数量，并把那一个基变量调出。在检验数d dj j中取最中取最大者所在的

14、列确定为列向量，再用常数列中的数大者所在的列确定为列向量，再用常数列中的数b bi i除以该列中的对应数除以该列中的对应数a aijij（必须为正数），商最（必须为正数），商最小者对应的元确定为主元。小者对应的元确定为主元。3 3、进行初等行变换、进行初等行变换把主元把主元a aijij化为化为1 1，所在的，所在的行每个元均除以主元行每个元均除以主元a aijij，并把主元所在的列的其，并把主元所在的列的其它元利用行变换均化为它元利用行变换均化为0 0。若检验数若检验数d dj j行中仍有正数，重复上述行中仍有正数，重复上述2 2、3 3步，直步，直至检验数全为负数或零，则常数列对应的数（基

15、至检验数全为负数或零，则常数列对应的数（基可行解）即为最优解，检验数可行解）即为最优解，检验数d d0 0即为最优值。如即为最优值。如果在单纯形表中，某一检验数大于果在单纯形表中，某一检验数大于0 0，所对应的，所对应的列没有正数，则线性规划问题没有最优解。列没有正数，则线性规划问题没有最优解。-8 -12 0 0 0bix1 x2 x3 x4 x5000 x3x4x52 4 1 0 01/2 1/4 0 1 02 5/2 0 0 144065320检验检验数数dj8 12 0 0 00 (2)2)选主元选主元（3 3）进行初等行）进行初等行变换变换 从而得单纯性表：从而得单纯性表：（4 4）

16、再选主元）再选主元-8-12 0 0 0-8-12 0 0 0b bi ix x1 1 x x2 2 x x3 3 x x4 4 x x5 5-12-12 0 0 0 0 x x2 2x x4 4x x5 51/2 1 1/4 0 01/2 1 1/4 0 03/8 0-1/16 1 03/8 0-1/16 1 03/4 0-5/8 0 13/4 0-5/8 0 111011075/275/24545检验数检验数d dj j 2 0 -3 0 02 0 -3 0 0-1320-1320 （5 5）进行初等行变换）进行初等行变换 -8 -12 0 0 0bix1 x2 x3 x4 x5-12 0

17、-8x2x4x x1 10 1 2/3 0 -2/30 0 1/4 1 -1/21 0 -5/6 0 4/3801560检验检验数数dj0 0 -4/3 0 -8/3-1440 c=-8-12;A=2 4;0.5 0.25;2 c=-8-12;A=2 4;0.5 0.25;2 2.5;b=440;65;320;2.5;b=440;65;320;x,fvalx,fval=linprog(c,A,blinprog(c,A,b)Optimization terminated.Optimization terminated.x=x=60.0000 60.0000 80.0000 80.0000fval

18、fval=-1.4400e+003-1.4400e+003 例例4 4、一农民有田、一农民有田2 2亩，根据他的经验，若种水稻，则亩，根据他的经验，若种水稻，则每亩每期产量为每亩每期产量为400kg400kg；若种花生，每亩每期产量为；若种花生，每亩每期产量为100kg100kg。水稻亩需。水稻亩需240240元，花生只需元，花生只需8080元，且花生每公元，且花生每公斤可卖斤可卖5 5元，水稻每公斤可卖元，水稻每公斤可卖3 3元。现在该农民只能凑元。现在该农民只能凑足足400400元。问这位农民如何安排种植，才能获得最大元。问这位农民如何安排种植，才能获得最大的利润？的利润？解解：（一）建立

19、模型：（一）建立模型设种水稻设种水稻x x1 1亩，种花生亩，种花生x x2 2亩，总利润为亩，总利润为Z Z，则依题设，则依题设得模型为：得模型为：该模型为非标准模型，为此引入松弛变量该模型为非标准模型，为此引入松弛变量x x3 3,x,x4 4,化化原模型为标准模型：原模型为标准模型：-960-420 0 0-960-420 0 0b bi i x x1 1 x x2 2 x x3 3 x x4 40 00 0 x x3 3x x4 4 1 1 1 0 1 1 1 0 24 8 0 1 24 8 0 12 24040 d dj j960 420 0 0960 420 0 00 0 取取a a2121=24=24为主元，为主元，x x1 1与与x x4 4调换。调换。（3 3）进行初等行变换）进行初等行变换-960-420 0 0 bi x1 x2 x3 x40-960 x3x1 0 2/3 1-1/24 1 1/3 0 1/24 1/3 5/3 dj 0 100 0 -40-1600 从而得单纯形表从而得单纯形表 -960-420 0 0 bi x1 x2 x3 x4-420-960 x2x1 0 1 3/2-1/16 1 0 -1/2 1/16 1/2 3/2 dj 0 0-150-33.75-1680