线性规划在管理中的应用

第十章线性规划在管理中的应用,主讲高拥军,线性规划是运筹学的一个重要分支，这种理论和方法在很多领域得到应用，特别是在现代化管理中应用更为广泛；线性规划主要研究的内容是在一定的技术经济条件限制下，使某项指标成为最大或成为最小，也就是使所求指标优化的问题。在管理工作中主要用来解决：生产规划、原料配比、运输调配、分配任务、合理下料、生产布局等问题。从应用范围来看，小到队组、车间，企业，大到地区部门，甚至国民经济计划的优化也都可以求助于它。,10.1线性规划的基本理论,10.1.1线性规划问题的数学模型所谓规划问题，就是指如何最合理地利用有限的资源(如资金、劳力材料、机器、时间等)，以便使产出的消耗最小，利润最大。如果利用数学方法来进行这种分析，这就是数学规划。当所建立的模型，都是线性代数方程时，这就是一个线性规划问题。,例10-1产品决策问题某汽车工厂生产大轿车和载重汽车两种型号的汽车，已知生产每辆汽车所用的钢材都是2吨辆，该工厂每年供应的钢材为1600吨，工厂的生产能力是每2.5小时可生产一辆载重汽车，每5小时可生产一辆大轿车，工厂全年的有效工时为2500小时；已知供应给该厂大轿车用的座椅每年可装配400辆。据市场调查，出售一辆大轿车可获利4千元，出售一辆载重汽车可获利3千元。问在这些条件下，工厂应如何安排生产才能使工厂获利最大?建立数学模型如下：,例10-2广告方法的选择问题某公司要求销售部经理制定一个广告计划，计划用经费10000元，要求尽量多的人能看到广告。该经理选择了三种广告方法，电视、广播电台和报纸。据调查各种广告的费用如下，在地方电视台下午播放1.5分钟要1000元，晚上要2000元。该经理决定在电视上作广告至少两次，但不多于四次，因为他还想用其它方法作广告。在地方，报纸上作半页广告费用是300元，一页要1000元，在广播电台上作广告的价格是，白天每半分钟600元，晚上每半分钟400元。公司限制用电台作广告的次数，白天最多不超过5次，晚上不超过3次。,根据该经理所获得的资料估计，在下午观看电视广告节目的大约有40000人，晚上有90000人。看日报的大约有60000人，并估计其中1/2的人看整页的广告，1/3的人看半页的广告。广播电台的听众白天有40000人，晚上30000人。现建立数学模型如下：,例10-3某构件厂生产构件问题某建筑构件厂生产甲、乙两种构件出售，生产主要用下料机械、有机玻璃、白色和黄色油漆等设备和材料。生产一件甲种构件需机械下料2分钟，有机玻璃1.5和白色油漆2公斤；生产一件乙种构件需机械下料1分钟，有机玻璃1.5和黄色油漆2公斤。每天下料机械可供使用的时间为480分钟，供应有机玻璃450，白色油漆440公斤，黄色油漆400公斤。甲、乙两种构件的售价分别为150元和120元。若销路没有问题，要获得最大的销售额，两种构件每天各应生产多少件?建立数学模型,例10-4下料问题某工厂要作100套钢架，每套由长2.9米，2.1米和1.5米的圆钢各一根组成，已知原料长7.4米，问应如何下料使需用的原材料最省。解：最简单的方法是从每根长7.4米的料上各截一根2.9米，2.1米，1.5米的圆钢，还余09米。这样共需100根原料，余料头0.9100=90(米)。现考虑合理套裁，方案见表10.1-1下料长度（米）不同方案下料根数（根）一二三四五2.91212.12211.53123合计（米）7.47.37.27.16.6料头长（米）00.10.20.30.8建立数学模型如下：,从上面几个例子，可以看出线性规划问题的数学模型有如下特点：1都有一组未知变量（x1，x2xc）代表某一方案；它们取不同的非负值，代表不向的具体方案。2都有一个目标要求，实现极大或极小。目标函数用未知变量的线性函数表示。3未知变量受到一组约束条件的限制，这些约束条件用一组线性等式或不等式表示。正是由于目标函数和约束条件都是未知变量的线性函数，所以我们把这类问题称为线性规划问题。,10.1.2线性规划问题的标准型现规定线性规划问题的标准形式为：见教材（10.1-5）建立标准型的好处在于：我们可以针对这种标准形式来研究它的求解方法。至于其它各种形式的线性规划问题，可以将其转化为标准型，然后用标准型的求解方法求解。,10.2线性规划问题的图解法学习这一节的目的是通过两个变量的线性规划问题的图解法，了解线性规划问题解的特点，从而了解求解线性规划问题的一般方法单纯形法的基本原理。,几个有关的数学概念及定理。(1)凸集，如果在形体中任意取两点连接根直线，若线段上所有的点都在这个形体中，则称该形体为凸集。实心园，实心球体，实心立方体等都是凸集。如图10.2中的(a)，(b)图形为凸集，而(c)，(d)图形则不是凸集。（2）顶角：(3)角顶可行解和角顶不可行解：角顶可行解是指一个可行解，但它不在另外两个可行解的连线上。,2目标函数的图上表示及线性规划问题的图解法由目标函数Z=4x1+3x2可知，它在x1x2平面上是一条直线。当Z取不同的数值时，在图上便得到一族以Z为参数的平行线。位于同一直线上的点，具有相同的目标函数值，因而称每条直线为“等值线”。对于Z=4x1+3x2来说，当Z值由小变大时，各直线沿其法线方向向右上方移动，即离坐标原点愈远，Z值也愈大。从图中可以看到，当等值线平移到距原点最远且仍与可行域有一交点时，那个交点便是使Z值取最大值的可行解，因而它就是最优解。在本例的慨况，图中的B点是最优解，此时x1=200，x2=600；Z=2600。,10.3线性规划问题的单纯形解法对于决策变量数大于或等于3的线性规划问题，一般用单纯形法求解。,10.3.1线性规划问题的基本概念定义1可行解：满足约束条件（10.3-2）和（10.3-3）的解，称为线性规划问题的可行解，所有可行解的集合称为可行域。定义2最优解：满足目标函数（10.3-1）式的可行解，称为线性规划问题的最优解定义3基：设A为约束方程组系数mn矩阵定义4。基本可行性：满足非负条件（10.3-3）的基本解称为基本可行解。定义5可行基：对应于基本可行解的基称为可行基。他们之间的关系可用图10.3表示,10.3.2单纯形法的计算步骤：(1)找出初始可行基(或用增加新变量的方法创造初始可行基)建立初始单纯形表。(2)检查所有的zj-cj。如果全部的zj-cj0，则该解为最优解。如果zj-cj中有小于0的，说明该解不是最优解。3选择具有最小检验数的非基变量为换入变量。它所对应的那