《《线性规划》教学课件》由会员分享，可在线阅读，更多相关《《线性规划》教学课件（25页珍藏版）》请在金锄头文库上搜索。
1、 1 线性规划1.1 线性规划问题及其数学模型 1.1.1 问题的提出 1.1.2 图解法 1.1.3 线性规划问题的标准型1.2 线性规划问题的求解单纯形法 1.2.1 基本概念 1.2.2 单纯形法 1.2.3 单纯形法计算机软件 1.3 线性规划应用举例 1.3.1 线材的合理利用问题 1.3.2 配料问题 1.3.3 连续投资问题1.1 线性规划问题及其数学模型 1.1.1 问题的提出问题的提出(一一) 例 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时和原料A、B的消耗量如下表。 该工厂每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排生产计划能使
2、该厂获利最多？ 这个问题可以用下面的数学模型来描述，设计划期内产品、的产量分别为x1，x2，可获利润用z表示，则有：Max Z=2x1+3x2x1+2x284x1 16 4x212x1, x20 1.1.1 问题的提出问题的提出(二二) 例例 靠近某河流有两个化工厂，靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天流经第一化工厂的河流流量为每天500万万m3，两工厂之间有一条流量，两工厂之间有一条流量为每天为每天200万万m3的支流（见图）。的支流（见图）。 第一化工厂每天排放污水第一化工厂每天排放污水2万万m3，第二化工厂每天排放污水，第二化工厂每天排放污水 1.4万万m3。污水从工厂
3、。污水从工厂1流到工厂流到工厂2前会前会有有20%自然净化。根据环保要求，自然净化。根据环保要求，河水中污水的含量应不大于河水中污水的含量应不大于0.2%。而工厂而工厂1和工厂和工厂2处理污水的成本分处理污水的成本分别为别为1000元元/万万m3和和800元元/万万m3。问两工厂各应处理多少污水才能使问两工厂各应处理多少污水才能使处理污水的总费用最低？处理污水的总费用最低？ 设工厂设工厂1和工厂和工厂2每天分别处理污水每天分别处理污水x1和和x2万万m3，则有，则有：Min z=1000x1+800x2 (2-x1)/500 0.0020.8(2-x1)+1.4-x2/700 0.002 x1
4、2, x21.4 x1, x20 1.1.1 问题的提出问题的提出(三三) 以上两例都有一些共同的特征：用一组变量表示某个方案，一般这些变量取值是非负的。存在一定的约束条件，可以用线性等式或线性不等式来表示。都有一个要达到的目标，可以用决策变量的线性函数来表示。 满足以上条件的数学模型称为线性规划模型。线性规划模型的一般形式如下：1.1 线性规划问题及其数学模型 1.1.2 1.1.2 图解法图解法唯一最优解无穷多最优解x1x2x1x2 解无界无可行解 线性规划问题如果有最优解,则最优解一定在可行域的边界上取得,特别地,一定可在可行域的顶点上取得.1.1 线性规划问题及其数学模型 1.1.3
5、1.1.3 线性规划问题的标准型线性规划问题的标准型线性规划问题的标准型max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1, x2, , xn0其中，bi0 (i=1,2,m)令xj= xj - xj，对模型中的进行变量代换。不符合标准型的几个方面：目标函数为 min z=c1x1+c2x2+cnxn令z=-z ,变为 max z= -c1x1- c2x2- -cnxn约束条件为 a11x1+a12x2+a1nxnb1加入非负变量xn+1，称为松弛变量，有 a11x1+a1
6、2x2+a1nxn+xn+1=b1约束条件为 a11x1+a12x2+a1nxnb1减去非负变量xn+1，称为剩余变量，有 a11x1+a12x2+a1nxn - xn+1=b1变量xj无约束。1.2 线性规划问题的求解单纯形法 1.2.1 基本概念基本概念 可行解满足约束条件（包括非负条件）的一组变量值，称可行解。 所有可行解的集合称为可行域。 最优解使目标函数达到最大的可行解称为最优解。 基本解对于有n个变量、m个约束方程的标准型线性规划问题，取其m个变量。若这些变量在约束方程中的系数列向量线性无关，则它们组成一组基变量。确定了一组基变量后，其它n-m个变量称为非基变量。 令非基变量都为0
7、 ，解约束方程，可唯一得到基变量的值，从而得到一个满足约束方程的解，称为基本解。由此可见，一个基本解的非零分量个数不超过m个。 基本可行解满足非负条件的基本解称为基本可行解。 基本可行解既是基本解、又是可行解，它对应于线性规划问题可行域的顶点。1.2 线性规划问题的求解单纯形法 1.2.2 单纯形法单纯形法(一一) 要找到线性规划问题的最优解，只要在基本可行解中寻找就可以了。虽然基本可行解的数目是有限个（不超过Cnm个），但当m,n较大时，要用“穷举法”求出所有基本可行解也是行不通的。因此，必须寻求一种更有效的方法。 单纯形法的基本思路是：从线性规划问题的一个基本可行解开始，转换到另一个使目标
8、函数值增大的基本可行解。反复迭代，直到目标函数值达到最大时，就得到了最优解。 为了便于单纯形法的实施，我们用单纯形表来描述线性规划问题的一个基本可行解的情况。不妨设x1,x2,xm组成一组基变量，且对应一个基本可行解。用高斯消去法把等式约束和目标函数变形为x1 +a1m+1xm+1+a1nxn=b1 x2 +a2m+1xm+1+a2nxn=b2 xm+amm+1xm+1+amnxn=bm -z +m+1xm+1+nxn= -z0把其系数列成数据表即单纯形表: 1.2.2 单纯形法单纯形法(二二) 按照单纯形法的思路求解线性规划问题, 要解决三个技术问题:给出第一个基本可行解; 检验一个基本可行
9、解是否是最优解; 转换到另一个基本可行解. 把线性规划问题变成标准型后, 观察是否每个约束方程中都有独有的、系数为1的变量. 如果是,则取这些变量作为基变量,变得到一个基本可行解; 否则,就给没有这种变量的约束条件添加一个人工变量,同时修改目标函数. (见例题) 如果单纯形表最后以行中的j都满足 j0, 则对应的基本可行解是最优解; 否则就不是最优解. j称为检验数. 第一,确定换入变量. 在大于0的检验数中找最大的为k, 对应变量xk为换入变量. 第二,确定换出变量. 取=minbi/aik|aik0=bl/alk, 对应的第l行的基变量为换出变量. 第三, 旋转运算. 换入变量所在的行与换
10、出变量所在的列交叉点的元素称为中心元素,用高斯削去法把中心元素化成1, 同列的其他元素化成0, 得到一个新的单纯形表,也就得到一个新的基本可行解. 1.2.2 单纯形法单纯形法(三三) 用单纯形法求解线性规划问题的具体步骤如下：找出初始可行基，确定初始基本可行解，建立初始单纯形表；转。检验对应于非基变量的检验数j。若j0（xj为非基变量）都成立，则当前单纯形表对应的基本解就是最优解，停止计算；否则转。在所有j0中，若有一个k对应的xk的系数aik0 (i=1,2,m)，则此问题为无界解（无解），停止计算；否则转。根据max（j0）=k 确定xk为换入变量；根据规则minbi/aik1im, a
11、ik0bl/alk确定相应的换出变量，并得到中心元素alk。转。以alk为枢轴元素进行转轴运算，得到新的单纯形表。转. 用单纯行法求解线性规划问题后，应回答下面几个问题：是否解无界？上面的步骤已作出回答。是否无可行解？求解后，若人工变量都已取0，则有可行解；否则，无可行解。唯一最优解还是无穷多最优解？在最后的单纯形表中，若所有非基变量的检验数都严格小于0，则为唯一最优解；若存在某个非基变量的检验数等于0，则有无穷多最优解。1.2.22 单纯形法单纯形法(四四)Max z=2x1+3x2 x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 x1, x2, x3 ,x4,x50
12、 此问题的最优解为此问题的最优解为:x1*=4, x2*=2, x5*=4, x3*= x4*= x1*=0, z*=2 4+3 2=14例Max z=2x1+3x2 x1+2x2 8 4x1 16 4x2 12 x1, x2 0 1.2.2 单纯形法单纯形法(五五)例例Min z= -3x1 +x2 +x3 x1 -2x2+x3 11 -4x1 +x2 +2x3 3 -2x2 + x3=1 x1, x2, x3 0Max z= 3x1 -x2 -x3 -M x6 -Mx7 x1 -2x2 +x3 +x4 =11 -4x1 +x2+2 x3 -x5 +x6 =3 -2x1 +x3 +x7 =1
13、 x1, x2, x3, x4, x5, x6, x70 x6, x7称为人工变量称为人工变量 此问题的最优解为此问题的最优解为: x1*=4, x2*=1, x3*= 9, x4*= x5*= x6*= x7*= 0, z*= -3 4+9+1= -2 1.2.3 用计算机软件求解线性规划问题 关于线性规划问题的求解，有许多好的专业软件和商务软件，通过计算机可十分方便地完成求解过程。最简便易行的求解软件是Excel，下面介绍其使用方法。 （1）建立Excsl工作表。用 一组单元格表示变量，作为可变单元格（空）；用几组单元格分别表示各约束条件和目标函数的系数；用一些单元格输入公式表示各组系数和
14、变量的关系。 （2）打开工具栏中的“规划求解”对话框，指定存有目标函数的单元格为目标单元格，指定表示变量的单元格为可变单元格，建立约束条件。 （3）在规划求解对话框中按下“求解”按钮，即可求出最优解和最优值。推出规划求解对话框。 1.3 应用举例应用举例(一一)解 先看有多少种裁料方案，再进行组合和选择。方案： 例 合理利用线材问题 现要做一百套钢管, 每套要长为2.9m、2.1m和1.5m的钢管各一根。已知原料长7.4m，问应如何下料，使用的原料最省。 设用方案设用方案,分别裁原料分别裁原料钢管钢管x1,x2, ,x8根根, 则：则：Min z= x1+ x2+ x3+x4+ x5+x6+x
15、7+x8 2x1+ x2+x3 + x4 100 2x2+x3+ 3x5 +2x6+ x7 100 x1+ x3 +3x4 +2x6+3x7+4x8 100 x1, x2, x3, x4, x5 ,x6, x7, x8 0 例例 某工厂要用三种原材料某工厂要用三种原材料C,P,HC,P,H混合调配出三混合调配出三种不同规格的产品种不同规格的产品A,B,DA,B,D。已知产品的规格要求、。已知产品的规格要求、单价和原料的供应量、单价如下表。该厂应如何单价和原料的供应量、单价如下表。该厂应如何安排生产，能使利润最大？安排生产，能使利润最大？ 1.3应用举例应用举例( (二）二）根据产品要求有：根据
16、产品要求有： AC0.5A, AP0.25A BC0.25B, BP0.5B AC+AP+AH=A BC+BP+BH=B根据原料供应量有：根据原料供应量有： AC+BC+DC100 AP+BP+DP100 AH+BH+DH60设设AC,AP,DH分别为分别为x1,x2,x9，有，有Max z=50(x1+x2+x3)+35(x4+x5+x6) +25(x7+x8+x9) - 65(x1+x4+x7) - 25(x2+x5+x8) - 35(x3 +x6 +x9) x10.5(x1+ x2+ x3) x2 0.25(x1+ x2+ x3) x4 0.25(x4+ x5+ x6) x5 0.5(x
17、4+ x5+ x6) x1+ x4+ x7100 x2+ x5+ x8100 x3+ x6+ x960 xj0, j=1,2,3,4,5,6,7,8,9解：记产品解：记产品A,B,DA,B,D中中C,P,HC,P,H的含量分的含量分别为别为AC,AP,AH,BC,BP,BH,DC,DP,DH。1.3 应用举例（三）例 成批生产企业年度生产计划的按月分配。 在年度计划按月分配时一般要考虑：从数量和品种上保证年度计划的完成；成批的产品尽可能集中在几个月内生产；由于技术方面的原因，某些产品在某个月后才能生产；某些产品要求年初交货；批量小的产品尽量集中在一个或几个月内生产出来，以便减少各月内的品种数量
18、。考虑以上条件，使设备负荷均衡并使利用率最大化。 假定工厂有m类设备，用i表示(i=1,2,m)；生产n种产品，用j表示(j=1,2,n)。各产品的全年计划量用dj表示。 用aij表示加工单位j种产品所需要的第i类设备的台时数，bik表示k月份第i类设备的生产能力(台时)(k=1,2,12)。 再假定第5、8两种产品下半年投产，第4号产品要求二月底前完成全年计划。 如要对全年12个月同时考虑，会使模型非常复杂，我们根据上述条件从1月到12月份，一个月一个月地分别建模计算。设k月份计划生产j种产品的数量为xjk。一月份模型为： m n mMax z=( aijxj1) (bi1) i=1 j=1
19、 i=1 n aijxj1bi1 (i=1,2,m) j=1xj1dj (j=1,2,n)x51=x81=0xj10 (j=1,2,n)二月份模型为： m n mMax z=( aijxj2) (bi2) i=1 j=1 i=1 n aijxj2bi2 (i=1,2,m) j=1xj2dj-xj1 (j=1,2,n)x52=x82=0xj20 (j=1,2,n)1.3 应用举例应用举例(四四) 例例 连续投资问题。某单位有资金连续投资问题。某单位有资金10万元，在今万元，在今后后5年内可考虑下列投资项目，已知：年内可考虑下列投资项目，已知： 项目项目A：从第：从第1到第到第4年每年初可投资，并
20、于次年每年初可投资，并于次年末回收本利年末回收本利115%； 项目项目B：第：第3年初需要投资，到第年初需要投资，到第5年末回收本年末回收本利利125%，但最大投资额不超过，但最大投资额不超过4万元；万元； 项目项目C：第：第2年初需要投资，到第年初需要投资，到第5年末能回收年末能回收本利本利140%，但最大投资额不超过，但最大投资额不超过3万元；万元； 项目项目D：5年内每年初可购买公債，当年末回年内每年初可购买公債，当年末回收本利收本利106%。 问它应该如何安排每年的投资，使到问它应该如何安排每年的投资，使到5年末拥年末拥有的资金最多？有的资金最多？ x2A+x2C+x2D=1.06x1
21、D解：每年的投资额解：每年的投资额应不超过手中的资应不超过手中的资金。由于项目金。由于项目D每每年都可投资，且当年都可投资，且当年末就可收回。所年末就可收回。所以该单位每年必然以该单位每年必然把资金全部投出去，把资金全部投出去，即投资额等于手中即投资额等于手中的资金数。的资金数。 设第设第i年投资各项目的资金年投资各项目的资金为为xiA,xib,xiC,xiD 。数学模型为：。数学模型为：Max z=1.15x4A+1.4x2C+1.25x3B+1.06x5D x1A+x1D=10x3A+x3B+x3D=1.15x1A+1.06x2Dx4A+x4D=1.15x2A+1.06x3D x5D=1.15x3A+1.06x4DxiA,xib,xiC,xiD0
