《第一章线性规划与单纯形法课件》由会员分享，可在线阅读，更多相关《第一章线性规划与单纯形法课件（323页珍藏版）》请在金锄头文库上搜索。
1、第一章第一章线性规划与单纯形法线性规划与单纯形法运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外线性规划的发展法国数学家法国数学家J.-B.-J.傅里叶和傅里叶和C.瓦莱普森分别于瓦莱普森分别于1832和和1911年独立地提出年独立地提出线性规划的想法线性规划的想法。1939年苏联数学家年苏联数学家.康托罗维奇在康托罗维奇在生产组织与计生产组织与计划中的数学方法划中的数学方法中提出中提出线性规划问题线性规划问题。1947年年美国美国数学家数学家G.B.丹齐克提出线性规划的一般数丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法学模型和求解线性规划问题的通用方法单纯
2、形法单纯形法。1947年年美国美国数学家数学家J.von诺伊曼提出诺伊曼提出对偶理论对偶理论,开创了线性开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家年美国经济学家T.C.库普曼斯库普曼斯把线性规划应用到把线性规划应用到经济领域经济领域，为此与康托罗维奇一起获，为此与康托罗维奇一起获1975年诺贝尔经济学年诺贝尔经济学奖。奖。线性规划的发展50年代后对线性规划进行大量的理论研究。年代后对线性规划进行大量的理论研究。例如，例如，1954年年C.莱姆基提出莱姆基提出对偶单纯形法对偶单纯形法，1954年年S
3、.加斯和加斯和T.萨迪等人解决了线性规划的萨迪等人解决了线性规划的灵敏灵敏度分析度分析和和参数规划问题参数规划问题，1956年年A.塔克提出塔克提出互补松弛定理互补松弛定理，1960年年G.B.丹齐克和丹齐克和P.沃尔夫提出沃尔夫提出分解算法分解算法等。等。线性规划的研究成果还直接推动了其他数学规线性规划的研究成果还直接推动了其他数学规划问题包括划问题包括整数规划整数规划、随机规划随机规划和和非线性规划非线性规划的算的算法研究。法研究。线性规划的发展1979年苏联数学家年苏联数学家L.G.Khachian提出解提出解线性规划问题的线性规划问题的椭球算法椭球算法，并证明它是多项，并证明它是多项式
4、时间算法。式时间算法。1984年年N.卡马卡提出解线性规划问题的新卡马卡提出解线性规划问题的新的的多项式时间算法多项式时间算法。用这种方法求解线性规划问题在变量个数为用这种方法求解线性规划问题在变量个数为5000时时只要单纯形法所用时间的只要单纯形法所用时间的1/50。现。现已形成线性规划已形成线性规划多项式算法理论。多项式算法理论。第一节线性规划问题及其数学模型第一节线性规划问题及其数学模型1、线性规划问题的提出、线性规划问题的提出在生产管理和经营活动中经常提出一类问题，在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财力即如何合理地利用有限的人力、物力、财力等资源
5、，以便得到最好的经济效果。等资源，以便得到最好的经济效果。第一节线性规划问题及其数学模型第一节线性规划问题及其数学模型例例1：某工厂在计划期内要安排生产：某工厂在计划期内要安排生产、两两种产品，已知生产种产品，已知生产单位产品单位产品所需的所需的设备台时设备台时及及A、B两种原材料的两种原材料的消耗消耗，如表，如表1-1所示：所示：设备设备128台时台时原材料原材料A4016kg原材料原材料B0412kg利润利润2元元3元元x x1 1x x2 2第一节线性规划问题及其数学模型第一节线性规划问题及其数学模型问：如何安排计划使该工厂获利最多？问：如何安排计划使该工厂获利最多？解题思路：用以下数学
6、模型来描述，设解题思路：用以下数学模型来描述，设x x1 1、x x2 2分别表分别表示在计划期内产品示在计划期内产品、的产量。的产量。因为设备的有效台时是因为设备的有效台时是8 8，这是一个，这是一个限制产量限制产量的条件，的条件，所以在确定产品所以在确定产品、的产量时，要考虑不超过设的产量时，要考虑不超过设备的有效台时数，即可用不等式表示为：备的有效台时数，即可用不等式表示为：第一节线性规划问题及其数学模型第一节线性规划问题及其数学模型同同理理，因因原原材材料料A、B的的限限量量，可可以以得得到到以以下下不等式：不等式：该该工工厂厂的的目目标标是是在在不不超超过过所所有有资资源源限限量量的
7、的条条件件下下，如如何何确确定定产产量量x1、x2以以得得到到最最大大的的利利润。若用润。若用z表示利润，这时表示利润，这时第一节线性规划问题及其数学模型第一节线性规划问题及其数学模型综上所述，该计划问题可用数学模型表示为：综上所述，该计划问题可用数学模型表示为：第一节线性规划问题及其数学模型第一节线性规划问题及其数学模型例例2：靠近某河流有靠近某河流有两个化工厂两个化工厂，流经第一化，流经第一化工厂的河流流量为每天工厂的河流流量为每天500万立方米万立方米，在两，在两个工厂之间有一条流量为每天个工厂之间有一条流量为每天200万立方米万立方米的支流。第一化工厂每天排放含有某种有害的支流。第一化
8、工厂每天排放含有某种有害物质的工业污水物质的工业污水2万立方米万立方米，第二化工厂每，第二化工厂每天排放含有这种污水天排放含有这种污水1.4万立方米万立方米，工厂工厂1 1工厂工厂2 2500万立方米200万立方米第一节线性规划问题及其数学模型第一节线性规划问题及其数学模型从从第一化工厂排出的工业污水流到第二化工厂以前，第一化工厂排出的工业污水流到第二化工厂以前，有有20%可以自然净化。根据环保要求，河流中工可以自然净化。根据环保要求，河流中工业污水的含量应不大于业污水的含量应不大于0.2%。这两个工厂都需各。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水自处理一部分工业污水。第
9、一化工厂处理工业污水的成本是的成本是1000元元/万立方米万立方米，第二化工厂处理工业，第二化工厂处理工业污水的成本是污水的成本是800元元/万立方米万立方米。现在要问在满足。现在要问在满足环保要求的条件下，每厂各应处理多少环保要求的条件下，每厂各应处理多少工业污水工业污水，使这两个工厂总的处理工业污水使这两个工厂总的处理工业污水费用最小费用最小。第一节线性规划问题及其数学模型第一节线性规划问题及其数学模型解题思路：用数学模型来描述。解题思路：用数学模型来描述。约束条件：约束条件：设设第一化工厂每天处理工业污水量为第一化工厂每天处理工业污水量为x1万立方米万立方米，第二化工厂每天处理工业污水量
10、为第二化工厂每天处理工业污水量为x2万立方米万立方米，从第一化工，从第一化工厂到第二化工厂之间，河流中工业污水的含量要不大于厂到第二化工厂之间，河流中工业污水的含量要不大于0.2%。由此可得近似关系式由此可得近似关系式（2-x1）/5000.2%。流经第二化工厂后，河流中的工业流经第二化工厂后，河流中的工业污水仍要不大于污水仍要不大于0.2%，这时有近似关系式，这时有近似关系式0.8（2-x1）+（1.4-x2）/(500+200)0.2%第一节线性规划问题及其数学模型第一节线性规划问题及其数学模型由于每个工厂每天处理的工业污水量不会大于每天的由于每个工厂每天处理的工业污水量不会大于每天的排放
11、量，排放量，故有故有x12；x21.4目标函数：求两厂用于处理工业污水的总费用最小，目标函数：求两厂用于处理工业污水的总费用最小，即即z=1000 x1+800 x2。第一节线性规划问题及其数学模型第一节线性规划问题及其数学模型综上所述，数学模型为：综上所述，数学模型为：目标函数目标函数 minzminz= = 1000 x1000 x1 1+800 x+800 x2 2满足约束条件满足约束条件（2-x2-x1 1）/500 0.2% /500 0.2% 0.8(2-x0.8(2-x1 1)+(1.4-x)+(1.4-x2 2)/(500+200)0.2%)/(500+200)0.2%x x1
12、 12 2 x x2 21.41.4X X1 1, x, x2 200举例举例例：生产计划问题例：生产计划问题假设工厂要根据拥有的资源和设备，计划生产假设工厂要根据拥有的资源和设备，计划生产甲、乙甲、乙两种产品，其主要资源有两种产品，其主要资源有钢材钢材4吨吨、铜材铜材3吨吨。专用设备能力。专用设备能力8千台时千台时。资源与设。资源与设备能力的备能力的消耗定额消耗定额及及单位产品单位产品所获利润如表所获利润如表1-1所示：问如何安排生产，才能使该厂获所示：问如何安排生产，才能使该厂获得的得的利润最大利润最大。举例举例生产计划问题的数据表生产计划问题的数据表产品产品单位产品单位产品消耗定额消耗定
13、额甲（件）甲（件）乙（件）乙（件）现有资源的现有资源的限制限制钢材钢材104（吨）（吨）铜材铜材013（吨）（吨）设备能力设备能力128（千台时）（千台时）单位产品的利润单位产品的利润2（万元）（万元）2（万元）（万元）x1x2使总利润使总利润f=2x1+2x2最大最大解：由题意可知：在加工时间和利润与产品产量成线解：由题意可知：在加工时间和利润与产品产量成线性关系的假设下，考虑到甲、乙两种产品的性关系的假设下，考虑到甲、乙两种产品的生产量生产量不能为负数不能为负数，即，即x1,x20，于是最优方案写成线性于是最优方案写成线性规划的数学模型为：规划的数学模型为：目标函数约束条件maximize
14、Subject to上述模型的含义是：上述模型的含义是：在给定的条件限制下，求使得目标函数在给定的条件限制下，求使得目标函数达到最大时的达到最大时的决策变量（决策变量（x1,x2）的取值。的取值。练习练习生产计划问题（资源利用问题）生产计划问题（资源利用问题）生产计划问题（资源利用问题）生产计划问题（资源利用问题）胜利家具厂生产桌子和椅子两种家具。桌子售胜利家具厂生产桌子和椅子两种家具。桌子售胜利家具厂生产桌子和椅子两种家具。桌子售胜利家具厂生产桌子和椅子两种家具。桌子售价价价价5050元元元元/ /个，椅子销售价格个，椅子销售价格个，椅子销售价格个，椅子销售价格3030元元元元/ /个，生产
15、桌子和个，生产桌子和个，生产桌子和个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌椅子要求需要木工和油漆工两种工种。生产一个桌椅子要求需要木工和油漆工两种工种。生产一个桌椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工子需要木工子需要木工子需要木工4 4小时，油漆工小时，油漆工小时，油漆工小时，油漆工2 2小时。生产一个椅子需小时。生产一个椅子需小时。生产一个椅子需小时。生产一个椅子需要木工要木工要木工要木工3 3小时，油漆工小时，油漆工小时，油漆工小时，油漆工1 1小时。该厂每个月可用木工小时。该厂每个月可用木工小时。该厂每个月可用木工小时。该厂每个月可用木工工时为工时为工时
16、为工时为120120小时，油漆工工时为小时，油漆工工时为小时，油漆工工时为小时，油漆工工时为5050小时。问该厂如小时。问该厂如小时。问该厂如小时。问该厂如何组织生产才能使每月的销售收入最大？何组织生产才能使每月的销售收入最大？何组织生产才能使每月的销售收入最大？何组织生产才能使每月的销售收入最大？练习练习某工厂生产甲、乙产品。已知生产甲种产品某工厂生产甲、乙产品。已知生产甲种产品1吨需耗吨需耗A种矿石种矿石10吨，吨，B种矿石种矿石5吨，煤吨，煤4吨；生产乙种吨；生产乙种产品产品1吨需耗吨需耗A种矿石种矿石4吨，吨，B种矿石种矿石4吨，煤吨，煤9吨。吨。每每1吨甲种产品的利润是吨甲种产品的利润是600元，每元，每1吨乙种产品的吨乙种产品的利润是利润是1000元。工厂在生产这两种产品的计划中元。工厂在生产这两种产品的计划中要求消耗要求消耗A种矿石不超过种矿石不超过300吨吨,B种矿石不超过种矿石不超过200吨，煤不超过吨，煤不超过360吨。甲，乙两种产品应各生吨。甲，乙两种产品应各生产多少吨（精确到产多少吨（精确到0.1吨），能使利润总额达到最吨），能使利润总额达到最大值？大值？练习练
