第2章线性规划导.ppt

《第2章线性规划导.ppt》由会员分享，可在线阅读，更多相关《第2章线性规划导.ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2章章 线性规划导论线性规划导论 线性规划是一种帮助线性规划是一种帮助管理者制定决策和解决问管理者制定决策和解决问题的方法。在今天激烈的题的方法。在今天激烈的商业竞争中，有很多应用商业竞争中，有很多应用线性规划的例子。为了说线性规划的例子。为了说明线性规划问题所共有的明线性规划问题所共有的特性，我们考虑以下几个特性，我们考虑以下几个典型的例子。典型的例子。例例1 Par公司是一个生产高尔夫器材的小公司是一个生产高尔夫器材的小型公司，它决定进入中等和高等价位的高尔夫型公司，它决定进入中等和高等价位的高尔夫袋市场。分销商对新产品十分感兴趣，且同意袋市场。分销商对新产品十分感兴趣，且同意买进买进

2、Par公司未来公司未来3个月内的全部产品。个月内的全部产品。在对整个高尔夫袋生产步骤进行了详细调在对整个高尔夫袋生产步骤进行了详细调查以后，管理层明确了高尔夫袋的生产过程：查以后，管理层明确了高尔夫袋的生产过程：(1)切割并印染原材料；切割并印染原材料；(2)缝合；缝合；(3)成型（插入支撑架、球棒分离装置等）；成型（插入支撑架、球棒分离装置等）；(4)检查与包装。检查与包装。2.1线性规划模型 生产主管详细分析了生产过程的每一步，生产主管详细分析了生产过程的每一步，得出以下结论：生产一个中价位标准高尔夫得出以下结论：生产一个中价位标准高尔夫袋需要用袋需要用7/10小时切割与印染，小时切割与印

3、染，1/2小时缝小时缝合，合，1小时成型，小时成型，1/10小时检查与包装。生小时检查与包装。生产一个高级袋则需要产一个高级袋则需要1小时切割与印染，小时切割与印染，5/6小时缝合，小时缝合，2/3小时成型，小时成型，1/4小时检查与小时检查与包装。生产主管估计未来包装。生产主管估计未来3个月内每个部门个月内每个部门可用的最大生产时间分别是：切割与印染可用的最大生产时间分别是：切割与印染630小时，缝合小时，缝合600小时，成型小时，成型708小时，检小时，检查与包装查与包装135小时。生产信息列于表小时。生产信息列于表2-1中。中。表表2-1 生生产产每个高每个高尔尔夫袋所需的夫袋所需的时间

4、时间部部门门生生产时间产时间（小（小时时）各部各部门门可用可用时间时间标标准袋准袋 高高级级袋袋切割与印染切割与印染缝缝合合成型成型检查检查与包装与包装7/10 1 1/2 5/6 1 2/3 1/10 1/4630600708135 已知生产一个标准袋的利润是已知生产一个标准袋的利润是10美元，生产美元，生产一个高级袋的利润是一个高级袋的利润是9美元。现在需要确定美元。现在需要确定标准袋和高级袋各生产多少，以最大化公司标准袋和高级袋各生产多少，以最大化公司的利润贡献。的利润贡献。解解：将将一一个个实实际际问问题题转转化化为为线线性性规规划划模模型型有有以下几个步骤：以下几个步骤：1确定决策变

5、量：确定决策变量：S=标准袋产量标准袋产量，D=高级袋产量高级袋产量。2确定目标函数：确定目标函数：目标就是使产品的利润目标就是使产品的利润贡献最大。更具体一点，是使两种产品单贡献最大。更具体一点，是使两种产品单位利润与产量的乘积的总和最大，因此目位利润与产量的乘积的总和最大，因此目标函数可写为：标函数可写为：max 10S+9D 3确定约束条件：确定约束条件：描述约束条件描述约束条件 对于生产时间来说，一共有对于生产时间来说，一共有4个个约束条件，他们制约着两种高尔夫袋的生产。约束条件，他们制约着两种高尔夫袋的生产。约束条件约束条件1 1：用于切割与印染的总时间必须小用于切割与印染的总时间必

6、须小于等于切割与印染部所能承受的最大工作时间。于等于切割与印染部所能承受的最大工作时间。约束条件约束条件2 2：用于缝合的总时间必须小于等于用于缝合的总时间必须小于等于缝合部所能承受的最大工作时间。缝合部所能承受的最大工作时间。约束条件约束条件3 3：用于成型的总时间必须小于等于用于成型的总时间必须小于等于成型部所能承受的最大工作时间。成型部所能承受的最大工作时间。约束条件约束条件4 4：用于检查与包装的总时间必须小用于检查与包装的总时间必须小于等于检查与包装部所能承受的最大工作时间。于等于检查与包装部所能承受的最大工作时间。用决策变量表示约束条件如下：用决策变量表示约束条件如下：4变量取值限

7、制：变量取值限制：一般情况，决策变量只取正值（非负值）一般情况，决策变量只取正值（非负值）S 0,D 0 Par问题完整的数学模型如下：问题完整的数学模型如下：max 10S+9D 例例2 某厂生产甲、乙、丙三种产品，主要消某厂生产甲、乙、丙三种产品，主要消耗耗A、B、C三种原料，已知每单位产品消三种原料，已知每单位产品消耗原料的数量等数据如表耗原料的数量等数据如表1.1所示。所示。甲甲乙乙丙丙原料原料总总量量（kg）ABC1504222354500 63003800产产品品单单价价（百元）（百元）2 45 产产品品单单位位消消耗耗原原料料要求确定甲、乙、丙的产量，使总产值最大。要求确定甲、乙

8、、丙的产量，使总产值最大。解：解：1确定决策变量：确定决策变量：x1=生产产品甲的数量，生产产品甲的数量，x2=生产产品乙的数量，生产产品乙的数量，x3=生产产品丙的数量。生产产品丙的数量。2确定目标函数：确定目标函数：工厂的目标是使总产值工厂的目标是使总产值最大，更具体一点，是使三种产品单价与最大，更具体一点，是使三种产品单价与产量的乘积的总和最大，因此目标函数可产量的乘积的总和最大，因此目标函数可写为：写为：如果工厂可以随意选择生产产品甲、乙、如果工厂可以随意选择生产产品甲、乙、丙的数量，他们的总产值可以随意大。而丙的数量，他们的总产值可以随意大。而这实际上是不可能的，因为任何生产都会这实

9、际上是不可能的，因为任何生产都会受到种种客观条件的限制。一个正确的模受到种种客观条件的限制。一个正确的模型应通过约束方程来反映这些客观条件。型应通过约束方程来反映这些客观条件。本例中的限制条件是对原料本例中的限制条件是对原料A、B、C的使的使用数量不能超过其拥有量。这三个条件可用数量不能超过其拥有量。这三个条件可由以下方程表示：由以下方程表示：3确定约束条件：确定约束条件：4变量取值限制：变量取值限制：一般情况，决策变量只取正值（非负值）一般情况，决策变量只取正值（非负值）x1 0,x2 0,x3 0 例例3 某工厂熔炼一种新型不锈钢，需要用四某工厂熔炼一种新型不锈钢，需要用四种合金种合金A、

10、B、C、D为原料，经测这四种原为原料，经测这四种原料关于元素铬（料关于元素铬（Cr），锰（），锰（Mn）和镍）和镍（Ni）的含量（）的含量（%）、单价，以及这种不锈）、单价，以及这种不锈钢所需铬（钢所需铬（Cr），锰（），锰（Mn）和镍（）和镍（Ni）的）的最低含量（最低含量（%）如表）如表1.2所示：所示：假设熔炼时重量没有损耗。假设熔炼时重量没有损耗。问题：要熔炼成问题：要熔炼成100吨这样的不锈钢，应选吨这样的不锈钢，应选用原料用原料A、B、C、D各多少吨，能够使成本各多少吨，能够使成本最小？最小？原原料料含含量量成成分分ABCD不不锈钢锈钢所所需各元需各元 素的最素的最低含量低含量 铬

11、铬（Cr）1.893.464.262.673.25锰锰（Mn）3.572.111.454.662.15镍镍（Ni）5.324.252.721.374.55单单价（万元价（万元/吨）吨）13.615.8 10.02 9.91解解 设选设选用原料用原料A、B、C、D分分别为别为x1，x2，x3，x4吨。根据吨。根据题题目，目目，目标标函数函数为为：（铬铬的含量）的含量）（镍的含量）（镍的含量）另外，各种合金原料的选用不能为负值。另外，各种合金原料的选用不能为负值。约束条件为：约束条件为：（熔炼成（熔炼成100吨不锈钢）吨不锈钢）（锰的含量）（锰的含量）问题归结为下列模型：问题归结为下列模型：例例4

12、 某厂生产某厂生产A、B、C三种产品，可供三种产品，可供选择的原料有甲、乙、丙、丁。四种原选择的原料有甲、乙、丙、丁。四种原料的成本分别是料的成本分别是15元，元，23元，元，21元，元，28元。每公斤不同原料所能提取的各种产元。每公斤不同原料所能提取的各种产品的数量（单位：克品的数量（单位：克/公斤）见表公斤）见表1.3。工厂要求每天生产工厂要求每天生产A产品不超过产品不超过120克，克，B产品恰好产品恰好550克，克，C产品至少产品至少310克，克，要求选配各种原料的数量既满足生产需要求选配各种原料的数量既满足生产需要，又使总成本最小，试建立此问题的要，又使总成本最小，试建立此问题的数学模

13、型。数学模型。产产品品原料原料ABC价价 格格(元元/kg)甲甲31515乙乙25723丙丙14321丁丁68628生生产产量量(克克)不超不超过过120 恰好恰好550 至少至少310解解 设设x1，x2，x3，x4 分分别为别为原料甲、乙、原料甲、乙、丙、丁的丙、丁的选选配数量（配数量（单单位：位：kg），），则则有目有目标标函数函数为总为总成本最少，即：成本最少，即：对产对产品品A的的产产量是每天不超量是每天不超过过120克，所以有：克，所以有：对产对产品品B的的产产量是每天恰好量是每天恰好为为550克，所以有：克，所以有：对产对产品品C的的产产量是每天至少量是每天至少为为310克，所以

14、有：克，所以有：另外，另外，产产品的品的产产量量为为非非负负的。的。综综合起来，合起来，得到本得到本问题问题的数学模型的数学模型为为：线性规划问题数学模型的一般形式线性规划问题数学模型的一般形式上述几个问题属于同一类型的决策优化问题，上述几个问题属于同一类型的决策优化问题，它们具有下列共同特点：它们具有下列共同特点：（1）每个行动方案可用一组变量）每个行动方案可用一组变量(x1，xn)的值表示，这些变量一般取非负值；的值表示，这些变量一般取非负值；（2）变量的变化要受某些条件限制，这些）变量的变化要受某些条件限制，这些限制条件可用一些线性等式或不等式表示；限制条件可用一些线性等式或不等式表示；

15、（3）有一个需要优化的目标，它也是变量）有一个需要优化的目标，它也是变量的线性函数。的线性函数。具具备备以上三个特点的数学模型称以上三个特点的数学模型称为线为线性性规规划，它的一般形式划，它的一般形式为为：线性规划模型的三要素线性规划模型的三要素3.3.约束条件：约束条件：为实现优化目标需受到的限制，为实现优化目标需受到的限制，用决策变量的等式或不用决策变量的等式或不 等式表示；等式表示；1.1.决策变量：决策变量：需决策的量，即待求的未知数；需决策的量，即待求的未知数；2.2.目标函数：目标函数：需优化的量，即欲达的目标，用决需优化的量，即欲达的目标，用决 策变量的表达式表示；策变量的表达式

16、表示；2.2 线性规划的图解法 图解法是用画图的方式求解线性规划图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些而是在于能够直观地说明线性规划解的一些重要性质。重要性质。我们称能够满足所有约束条件的解为我们称能够满足所有约束条件的解为可行可行解解，可行解所在的阴影区域称为，可行解所在的阴影区域称为可行域可行域。任何。任何在可行域边界上或在可行域内的解点都是可行在可行域边界上或在可行域内的解点都是可行解点。解点。图解法求

17、解线性规划问题的步骤如下：图解法求解线性规划问题的步骤如下：（1）分别取决策变量）分别取决策变量x1，x2 为坐标向量，为坐标向量，建立直角坐标系；建立直角坐标系；（2）对每个约束（包括非负约束）条件，）对每个约束（包括非负约束）条件，先取其等式在坐标系中作出直线，通过判断先取其等式在坐标系中作出直线，通过判断确定不等式所决定的半平面。各约束半平面确定不等式所决定的半平面。各约束半平面交出来的区域（存在或不存在），若存在，交出来的区域（存在或不存在），若存在，其中的点表示的解就是此线性规划的可行解。其中的点表示的解就是此线性规划的可行解。这些符合约束限制的点集合，就是线性规划这些符合约束限制的

18、点集合，就是线性规划的可行集或可行域。当可行域存在时，进行的可行集或可行域。当可行域存在时，进行（3）；否则该线性规划问题无可行解。）；否则该线性规划问题无可行解。（3）任意给定目标函数一个值作一条目标）任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平移后值函数的等值线，并确定该等值线平移后值增加的方向，平移此目标函数的等值线，增加的方向，平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值使其达到既与可行域有交点又不可能使值再增加的位置（有时交于无穷远处，此时再增加的位置（有时交于无穷远处，此时称无有限最优解）。若有交点时，此目标称无有限最优解）。若有交点时，此目标函数

19、等值线与可行域的交点即最优解（一函数等值线与可行域的交点即最优解（一个或多个），此目标函数的值即最优值。个或多个），此目标函数的值即最优值。图解法简单、直观，便于初学者了解图解法简单、直观，便于初学者了解线性规划基本原理和几何意义。线性规划基本原理和几何意义。我们以我们以Par公司问题为例，说明图解法。公司问题为例，说明图解法。解解（1）建立直角坐）建立直角坐标标系。由于系。由于S0，D0，因此只需要在第一象限作，因此只需要在第一象限作图讨论图讨论。（2）确定）确定问题问题的可行域。的可行域。（3）做目标函数）做目标函数z的等值线，平行移动的等值线，平行移动找出找出z值增大的方向，确定最优解的

20、位置。值增大的方向，确定最优解的位置。例例1 用图解法求解用图解法求解Par公司问题公司问题2004006008002004006001000800oSD1200100012001400(7/10)S+D 6302004006008002004006001000800oSD1200100012001400(1/2)S+(5/6)D 1352004006008002004006001000800oSD1200100012001400S+(2/3)D 7082004006008002004006001000800oSD1200100012001400(1/10)S+(1/4)D 135200400

21、6008002004006001000800oSD1200100012001400(7/10)S+D 630S+(2/3)D 708(1/10)S+(1/4)D 135(1/2)S+(5/6)D 135图2-5200400600800200400600oSD可行域可行域10S+9D=1800200400600800200400600oSD可行域可行域10S+9D=3600200400600800200400600oSD可行域可行域10S+9D=5400200400600800200400600oSD可行域可行域10S+9D=7668图2-9 最优解处最优解处S和和D的值即决策变量的最优解。的值

22、即决策变量的最优解。能否准确的确定能否准确的确定S和和D的值取决于图是否画得的值取决于图是否画得准确。从图准确。从图2-9可以看出，最优的生产组合是可以看出，最优的生产组合是大约生产标准袋大约生产标准袋550个（个（S），高级袋），高级袋250个个（D）。）。仔细观察图仔细观察图2-5和图和图2-9，发现最优解在切，发现最优解在切割与印染约束线和成型约束线的交点处。即最割与印染约束线和成型约束线的交点处。即最优解点既在切割于印染约束线上优解点既在切割于印染约束线上 又在成型约束线上又在成型约束线上 （2-8）（2-9）将式（将式（2-10）代入（）代入（2-9），得），得 D=252将将D=2

23、52代入（代入（2-10），得），得S=540最优解的精确位置是最优解的精确位置是S=540，D=252。所以。所以Par公司最优的生产量为公司最优的生产量为540个标准袋和个标准袋和252个高级个高级袋，利润贡献为袋，利润贡献为10540+9252=7668美元。美元。所以，决策变量所以，决策变量S和和D的最优解值必须的最优解值必须同时满足式（同时满足式（2-8）和（）和（2-9）。由式（）。由式（2-8）解出）解出S得得 即 （2-10）对只有两个决策变量的线性规划问题，决对只有两个决策变量的线性规划问题，决策变量的精确解可以先由图解法确定最优策变量的精确解可以先由图解法确定最优解点，然后

24、解相应的两个方程得到。解点，然后解相应的两个方程得到。松弛变量松弛变量 除了最优解和与之相关的利润贡献，除了最优解和与之相关的利润贡献，Par公司管理层很有可能希望知道关系每公司管理层很有可能希望知道关系每个生产运作所需要的生产时间的信息。我个生产运作所需要的生产时间的信息。我们可以通过将最优值（们可以通过将最优值（S=540，D=252）代入线性规划的约束条件里来获得该信息。代入线性规划的约束条件里来获得该信息。约束条件当S=540及D=252时所需的小时数可用小时数未用小时数切割与印切割与印染染(7/10)540+1 252=6306300缝缝合合(1/2)540+(5/6)252=482

25、600120成型成型1 540+(2/3)252=7087080检查检查与包与包装装(1/10)540+(1/4)252=11713518 因此，这个完全方案告诉管理层生产因此，这个完全方案告诉管理层生产540个标准袋和个标准袋和252个高级袋将需要耗用所有个高级袋将需要耗用所有可用的切割与印染时间（可用的切割与印染时间（630小时）以及所小时）以及所有可用的成型时间（有可用的成型时间（780小时），但还有小时），但还有600480=120个缝合小时、个缝合小时、135117=18个检查个检查与包装小时剩余。与包装小时剩余。120个缝合小时和个缝合小时和18个检个检查与包装小时对于这两个部门来

26、说就是松弛查与包装小时对于这两个部门来说就是松弛的。在线性规划术语里，对的。在线性规划术语里，对a约束条件的任约束条件的任何未用产能，都称为与约束条件对应是松弛何未用产能，都称为与约束条件对应是松弛的。的。作为对图解法的最后说明，我们提醒作为对图解法的最后说明，我们提醒大家注意一下图大家注意一下图2-5里显示的缝合约束线。里显示的缝合约束线。注意，这项约束并不影响可行政区域的大注意，这项约束并不影响可行政区域的大小。也就是说，不管有没有缝合约束，可小。也就是说，不管有没有缝合约束，可行域的大小都是一样的。这也告诉我们，行域的大小都是一样的。这也告诉我们，只要其他只要其他3个部门能完成工作量，缝

27、合部门个部门能完成工作量，缝合部门也能完成。这是因为缝合工序并不影响最也能完成。这是因为缝合工序并不影响最优解，它被称为优解，它被称为冗余约束冗余约束。例例2 M&D化学公司生产两种产品，它们是化学公司生产两种产品，它们是生产肥皂和清洗剂的原材料。基于对当前存生产肥皂和清洗剂的原材料。基于对当前存货水平和下月的市场需求的分析，货水平和下月的市场需求的分析，M&D管管理层确定理层确定A和和B的总产量至少要达到的总产量至少要达到350加仑。加仑。特别地，公司的一个主要客户订购的特别地，公司的一个主要客户订购的125加加仑必须首先得到满足。仑必须首先得到满足。A产品的制造时间是产品的制造时间是每加仑

28、每加仑2小时，而小时，而B产品则是每加仑产品则是每加仑1小时。小时。下个月总加工时间是下个月总加工时间是600小时。小时。M&D的目标的目标是在满足客户需求的前提之下尽可能降低成是在满足客户需求的前提之下尽可能降低成本。每加仑本。每加仑A产品的制造成本是产品的制造成本是2美元，而每美元，而每加仑加仑B产品的制造成本是产品的制造成本是3美元。美元。解：为了制定出使得成本达到最小的生产计解：为了制定出使得成本达到最小的生产计划，我们列出划，我们列出M&D公司的线性规划方程。设：公司的线性规划方程。设：AA产品产量；产品产量；BB产品产量。产品产量。min 2A+3B s.t.1A 125 A 产品

29、的需求量产品的需求量 1A+1B350 总产量总产量 2A+1B600 生产时间生产时间 A,B0100200300400100200300 500400oAB 600 500 600 700A=1252A+1B=6001A+1B=350100200300400100200300oAB2A+3B=800400500600可行域可行域2A+3B=1200图2-16 由图由图2-16可知最优解为可知最优解为1A+1B=350和和2A+1B=600的交点，即的交点，即A=250；B=100.剩余变量剩余变量 对于一个对于一个a约束条件的问题，我们可约束条件的问题，我们可以将松弛变量加到不等式的左边，

30、使其变以将松弛变量加到不等式的左边，使其变成一个等式。同样，对于一个成一个等式。同样，对于一个a约束条件约束条件的问题，我们可以在不等式的左边减去一的问题，我们可以在不等式的左边减去一个剩余变量而使不等式变成等式。个剩余变量而使不等式变成等式。2.3 极点与最优解 我们注意到所有最优解的点都在可行我们注意到所有最优解的点都在可行域的顶点上。在线性规划术语中，这样的域的顶点上。在线性规划术语中，这样的顶点称为可行域的极点。顶点称为可行域的极点。Par公司问题的可公司问题的可行域一共有行域一共有5个顶点，或者说个顶点，或者说5个极点。个极点。二个重要结论：二个重要结论：满足约束条件的可行域一般都构

31、成凸多满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。边形。这一事实可以推广到更多变量的场合。最优解必定能在凸多边形的某一个顶点最优解必定能在凸多边形的某一个顶点上取得，这一事实也可以推广到更多变量的上取得，这一事实也可以推广到更多变量的场合。场合。2.4线性规划问题的计算机求解线性规划问题的计算机求解 设计计算机程序来求解线性规划问题设计计算机程序来求解线性规划问题已经得到广泛的应用。已经得到广泛的应用。管理科学家是本书作者开发的软件包，管理科学家是本书作者开发的软件包，它也有线性规划模块。我们以它也有线性规划模块。我们以Par公司问题公司问题为例说明怎么使用这套软

32、件。因为计算机要为例说明怎么使用这套软件。因为计算机要求输入的数据必须为小数而不是分数，所以求输入的数据必须为小数而不是分数，所以我们将模型中的公式改写为：我们将模型中的公式改写为：max 10S+9D s.t.0.7S+1D630 切割与印染切割与印染 0.5S+0.83333D600 缝合缝合 1.0S+0.66667D708 成型成型 0.1S+0.25D135 检查与包装检查与包装 S,D0 图图2-14为计算机输出结果。首先，注意目标函为计算机输出结果。首先，注意目标函数值右边的值数值右边的值7667.99417。将它四舍五入求近似值。将它四舍五入求近似值7668美元。在目标函数值的

33、下面是最优解所对应的美元。在目标函数值的下面是最优解所对应的决策变量的值。进行同样的近似变换后，我们就得决策变量的值。进行同样的近似变换后，我们就得到：标准袋产量到：标准袋产量S=540，高级袋产量为，高级袋产量为D=252。Objective Function Value=7667.99463 Varible Value Reduced Costs-S 539.99841 0.00000 D 252.00113 0.00000Constraint Slack/Surplus Dual Prices-1 0.00000 4.37496 2 120.00000 0.00000 3 0.00000

34、 6.93753 4 17.00000 0.00000图图2-14 递减成本（递减成本（Reduced Costs）下的信息表示下的信息表示在目标函数中，决策变量的系数需改进多少才能在目标函数中，决策变量的系数需改进多少才能使最优解对应的决策变量的值是正值。如果决策使最优解对应的决策变量的值是正值。如果决策变量在最优解的条件下已经是正值了，递减成本变量在最优解的条件下已经是正值了，递减成本就应该是零。如在就应该是零。如在Par公司问题中，最优解是公司问题中，最优解是S=540和和D=252。两个变量已经是正值了，所以它。两个变量已经是正值了，所以它们相对应的递减成本是零。在第们相对应的递减成本

35、是零。在第3章我们还会介绍章我们还会介绍最优解的变量不是正值的情况。最优解的变量不是正值的情况。紧接着紧接着S、D值以及递减成本信息之后，计算值以及递减成本信息之后，计算机还给出了一些约束条件的信息。回想一下机还给出了一些约束条件的信息。回想一下Par公司问题，它有公司问题，它有4个关于时间的小于等于的约束条个关于时间的小于等于的约束条件，每个条件对应一个部门。这些信息表示在松件，每个条件对应一个部门。这些信息表示在松弛弛/剩余下面。剩余下面。2.5 线性规划解的特殊情况线性规划解的特殊情况 从对图解法的讨论，我们知道最优解可以从对图解法的讨论，我们知道最优解可以从可行域的极点中找到。现在考虑

36、一下特殊的情从可行域的极点中找到。现在考虑一下特殊的情况，目标函数线与可行域边界所在的约束线重合。况，目标函数线与可行域边界所在的约束线重合。我们会看到这会导致有多重最优解。在此情况下，我们会看到这会导致有多重最优解。在此情况下，函数的最优解将多于一个。函数的最优解将多于一个。为了解释多重最优解，我们再回到为了解释多重最优解，我们再回到Par公司公司的例子上去。假设生产每个标准袋的利润减为的例子上去。假设生产每个标准袋的利润减为6.30美元，因而目标函数的值就变成了美元，因而目标函数的值就变成了6.3S+9D。这时再用图解法求解该问题，如图这时再用图解法求解该问题，如图2-18所示。注所示。注

37、意，最优解虽然还在极点上，但实际上，两个极意，最优解虽然还在极点上，但实际上，两个极点都是最优点：极点点都是最优点：极点（S=300，D=420）和极点）和极点（S=540,D=252）。）。200400600800200400600oSD可行域可行域6.3S+9D=5670图图2-18 无可行解无可行解是指线性规划问题不存在满足全部是指线性规划问题不存在满足全部约束条件（包括非负约束）的解。在图形中，无可约束条件（包括非负约束）的解。在图形中，无可行解是指可行域并不存在。也就是说，没有任何一行解是指可行域并不存在。也就是说，没有任何一个点可以同时满足所有的约束条件以及非负约束。个点可以同时满

38、足所有的约束条件以及非负约束。为了进一步解释，我们再回到为了进一步解释，我们再回到Par公司的例子上来。公司的例子上来。假设管理层确定公司必须至少生产假设管理层确定公司必须至少生产500个标准袋和个标准袋和360个高级袋。在图形中就必须重新画出问题的解个高级袋。在图形中就必须重新画出问题的解的区域以及反映两个新增的要求（见图的区域以及反映两个新增的要求（见图2-19），左），左下方的阴影区域表示满足生产能力的解，右上方的下方的阴影区域表示满足生产能力的解，右上方的阴影区域表示的是标准袋的最低生产量是阴影区域表示的是标准袋的最低生产量是500个，个，高级袋的最低生产量是高级袋的最低生产量是360

39、个。但是没有任何一个个。但是没有任何一个点能够满足着两个约束条件。因此，如果管理层增点能够满足着两个约束条件。因此，如果管理层增加这两个最小产量约束条件，该问题就没有可行域加这两个最小产量约束条件，该问题就没有可行域了。了。200400600800200400600oSD满足部门约束满足部门约束条件的点条件的点图图2-19满足最低生产满足最低生产要求的点要求的点 如果一个最大化线性规划问题的解可以无限地如果一个最大化线性规划问题的解可以无限地变大，却不违反任何约束条件，我们就称这个解变大，却不违反任何约束条件，我们就称这个解是无界解。对于一个最小化问题，如果它的解可是无界解。对于一个最小化问题

40、，如果它的解可以无限的变小，那么它的解也是无界的。以无限的变小，那么它的解也是无界的。但是，如果一个实际的线性规划模型中出现但是，如果一个实际的线性规划模型中出现了无界解的情况，那就说明问题所对应的方程出了无界解的情况，那就说明问题所对应的方程出现了问题。我们知道对于一个现实问题来说，不现了问题。我们知道对于一个现实问题来说，不可能会出现利润无限大的情况。所以我们得出以可能会出现利润无限大的情况。所以我们得出以下结论：如果对于一个求利润最大的问题的方程下结论：如果对于一个求利润最大的问题的方程具有无界解，那么这个数学模型就一定没有真实具有无界解，那么这个数学模型就一定没有真实反映实际问题。产生

41、这种情况的原因常常是在对反映实际问题。产生这种情况的原因常常是在对模型列表达式时，遗漏了一些约束条件。模型列表达式时，遗漏了一些约束条件。我们通过下面这个例子来说明这种情况。假我们通过下面这个例子来说明这种情况。假设下面的线性规划问题只有两个变量设下面的线性规划问题只有两个变量X和和Y。Max 20X+10Y s.t.1X 2 1Y5 X,Y0在图在图2-20中我们画出了这个问题的可行域。中我们画出了这个问题的可行域。看一下看一下2-20中的目标函数线，我们发现这个中的目标函数线，我们发现这个问题的解可以使无限大的。因而我们说，该问题的解可以使无限大的。因而我们说，该线性规划的解事无界的。线性

42、规划的解事无界的。510152051015oXY20可行域可行域20X+10Y=80图2-20 20X+10Y=16020X+10Y=2402.6用用Excel求解求解LP(线性规划线性规划)问题问题 首先检查是否加载了宏首先检查是否加载了宏“规划求解规划求解”？即查看即查看Excel窗口的窗口的“工具工具”菜单下是否有菜单下是否有“规划求解规划求解”菜单条？如尚未加载，可单菜单条？如尚未加载，可单击击Excel窗口的窗口的“工具工具”“加载宏加载宏”，在，在所弹出的所弹出的“加载宏加载宏”对话框中选对话框中选“规划求规划求解解”，单击，单击“确定确定”(如下图如下图1)。一、建立线性规划问题

43、的电子表格模型一、建立线性规划问题的电子表格模型 使用使用Excel求解线性规划问题时，电子表格是求解线性规划问题时，电子表格是输入和输出的载体，因此设计良好的电子表格，更输入和输出的载体，因此设计良好的电子表格，更加易于阅读。下面以生产计划为例说明建立线性规加易于阅读。下面以生产计划为例说明建立线性规划问题的电子表格模型。其数据如下表：划问题的电子表格模型。其数据如下表：工厂工厂单单位位产产品的生品的生产时间产时间每周可用工每周可用工时时门门窗窗1231小小时时03小小时时02小小时时2小小时时4小小时时12小小时时18小小时时单单位利位利润润（元）（元）300500本例的电子表格设计如下图

44、所示：（见例本例的电子表格设计如下图所示：（见例1.1 xls）建立线性规划问题的电子表格模型需要完成建立线性规划问题的电子表格模型需要完成以下工作以下工作1在工作表中输入数据。显示数据的在工作表中输入数据。显示数据的单元格称为数据单元格。为单元格命名可以单元格称为数据单元格。为单元格命名可以使表格更容易理解和使用。在例使表格更容易理解和使用。在例1.1 xls电子电子表格中，对数据单元格做了如下命名：单位表格中，对数据单元格做了如下命名：单位利润（利润（C4:D4），可用工时（），可用工时（G7:G9）。为）。为单元格命名，首先选中单元格，然后从单元格命名，首先选中单元格，然后从“插插入入”

45、菜单中选择菜单中选择“命名命名”选项，再输入名字选项，再输入名字（或者单击数据表上公式栏左侧的名称框，（或者单击数据表上公式栏左侧的名称框，输入名字）。输入名字）。2在工作表中输入模型部分（包括决策变在工作表中输入模型部分（包括决策变量、约束条件、目标函数）。量、约束条件、目标函数）。（1）确定每个决策变量所对应的单元格，称）确定每个决策变量所对应的单元格，称为可变单元格。在例为可变单元格。在例1.1 xls电子表格中，决策电子表格中，决策变量所对应的单元格为（变量所对应的单元格为（C12:D12），并命名），并命名为每周产量。为每周产量。（2）选择单元格输入公式）选择单元格输入公式,计算每个

46、约束条计算每个约束条件左边的值。在例件左边的值。在例1.1 xls电子表格中，三个约电子表格中，三个约束的左边的值所对应的单元格为（束的左边的值所对应的单元格为（E7:E9），），并命名为实际使用。分别输入公式为：并命名为实际使用。分别输入公式为：单元格单元格E7：=C7*C12+D7*D12单元格单元格E8：=C8*C12+D8*D12单元格单元格E9：=C9*C12+D9*D12 单元格（单元格（E7:E9）中的每一个都给出了）中的每一个都给出了依赖于可变单元格（依赖于可变单元格（C12:D12）的输出结果，）的输出结果，他们称为输出单元格。他们称为输出单元格。注意输出单元格（注意输出单元

47、格（E7:E9）中输入的公）中输入的公式都是两组数相乘后相加，式都是两组数相乘后相加，Excel中的函数中的函数SUMPRODUCT可以实现这一功能，它能将可以实现这一功能，它能将2至至30个大小相同的单元格区域（每个单元格个大小相同的单元格区域（每个单元格区域用逗号隔开）中的对应数值型元素相乘区域用逗号隔开）中的对应数值型元素相乘后再相加。例如单元格后再相加。例如单元格E7中的公式用这个函中的公式用这个函数表达为：数表达为：单元格单元格E7：=SUMPRODUCT(C7:D7,C12:D12)利用利用Excel函数的复制功能，这个公式函数的复制功能，这个公式可以通过引用方法复制到可以通过引用

48、方法复制到E8、E9单元格中，单元格中，避免了重复输入公式的烦恼。因为是纵向复避免了重复输入公式的烦恼。因为是纵向复制，可以把放有资源系数的单元格区域做相制，可以把放有资源系数的单元格区域做相对引用，把放有决策变量的单元格区域做绝对引用，把放有决策变量的单元格区域做绝对引用或混合引用，即将公式变为：对引用或混合引用，即将公式变为：单元格单元格E7：=SUMPRODUCT(C7:D7,C$12:D$12)其中符号其中符号“$”表示绝对引用，表示绝对引用，“$”后面的数字或符号在拖动复制过程中不变。后面的数字或符号在拖动复制过程中不变。这样，单元格这样，单元格E7中的公式就可以通过拖动复中的公式就

49、可以通过拖动复制到制到E8、E9单元格中。单元格中。因为单元格（因为单元格（C12:D12）命名为每周）命名为每周产量，所以单元格产量，所以单元格E7中的公式也可以写为：中的公式也可以写为：单元格单元格E7：=SUMPRODUCT(C7:D7,每周产量每周产量)在单元格（在单元格（F7:F9）中，输入）中，输入“=”，它只起提示作用，并不参与运算。，它只起提示作用，并不参与运算。（3）选择某一单元格，输入目标函数的）选择某一单元格，输入目标函数的公式，称为目标单元格。在例公式，称为目标单元格。在例1.1 xls电子表电子表格中，目标函数所对应的单元格为（格中，目标函数所对应的单元格为（G12）

50、，），并命名为总利润，输入目标函数的公式为并命名为总利润，输入目标函数的公式为=C4*C12+D4*D12，或，或=SUMPRODUCT(单位利润单位利润,每周产量每周产量)。二、用二、用Excel规划求解工具求解线性规划问规划求解工具求解线性规划问题题 下面以例下面以例1.1 xls为例，说明用为例，说明用Excel规规划求解工具求解线性规划问题的步骤。划求解工具求解线性规划问题的步骤。1选择选择“工具工具”菜单，在其弹出的子菜单，在其弹出的子菜单中选择菜单中选择“规划求解规划求解”选项，打开选项，打开“规划规划求解参数求解参数”对话框，如图对话框，如图3所示。所示。图图3“规划求解参数规划