1.4 线性规划的应用

《1.4 线性规划的应用》由会员分享，可在线阅读，更多相关《1.4 线性规划的应用（44页珍藏版）》请在金锄头文库上搜索。

1、1.4 线性规划的应 用 1.4 线性规划的应 用 一、使用线性规划方法处理实际问题一、使用线性规划方法处理实际问题一、使用线性规划方法处理实际问题一、使用线性规划方法处理实际问题 必须具备的条件必须具备的条件必须具备的条件必须具备的条件( ( ( (建模条件建模条件建模条件建模条件) ) ) )： 1)优化条件优化条件-问题的目标有极大化或极问题的目标有极大化或极问题的目标有极大化或极问题的目标有极大化或极 小化的要求小化的要求小化的要求小化的要求, ,而且能用决策变量的线性而且能用决策变量的线性而且能用决策变量的线性而且能用决策变量的线性 函数来表示。函数来表示。函数来表示。函数来表示。

2、2)选择条件选择条件-有多种可供选择的可行方有多种可供选择的可行方有多种可供选择的可行方有多种可供选择的可行方 案，以便从中选取最优方案。案，以便从中选取最优方案。案，以便从中选取最优方案。案，以便从中选取最优方案。 3）限制条件限制条件-达到目标的条件是有一定限 制的（比如，资源的供应量有限度 等），而且这些限制可以用决策变量的 线性等式或线性不等式表示出来。 达到目标的条件是有一定限 制的（比如，资源的供应量有限度 等），而且这些限制可以用决策变量的 线性等式或线性不等式表示出来。 此外，此外，描述问题的决策变量相互之描述问题的决策变量相互之描述问题的决策变量相互之描述问题的决策变量相互之

3、 间应有一定的联系，有可能建立数学关间应有一定的联系，有可能建立数学关间应有一定的联系，有可能建立数学关间应有一定的联系，有可能建立数学关 系，即这些系，即这些系，即这些系，即这些变量之间是内部相关变量之间是内部相关变量之间是内部相关变量之间是内部相关的。的。的。的。 二、建模步骤二、建模步骤二、建模步骤二、建模步骤： 第一步：设置要求解的决策变量第一步：设置要求解的决策变量第一步：设置要求解的决策变量第一步：设置要求解的决策变量。决策变量决策变量决策变量决策变量 选取得当，不仅能顺利地建立模型而且能方便选取得当，不仅能顺利地建立模型而且能方便选取得当，不仅能顺利地建立模型而且能方便选取得当，

4、不仅能顺利地建立模型而且能方便 地求解地求解地求解地求解，否则很可能事倍功半。，否则很可能事倍功半。，否则很可能事倍功半。，否则很可能事倍功半。 第二步：找出所有的限制第二步：找出所有的限制第二步：找出所有的限制第二步：找出所有的限制，即约束条件，即约束条件，即约束条件，即约束条件，并并并并 用决策变量的线性方程或线性不等式来表示用决策变量的线性方程或线性不等式来表示用决策变量的线性方程或线性不等式来表示用决策变量的线性方程或线性不等式来表示。 当限制条件多，背景比较复杂时，可以当限制条件多，背景比较复杂时，可以当限制条件多，背景比较复杂时，可以当限制条件多，背景比较复杂时，可以采用图采用图采

5、用图采用图 示或表格形式列出所有的已知数据和信息，以示或表格形式列出所有的已知数据和信息，以示或表格形式列出所有的已知数据和信息，以示或表格形式列出所有的已知数据和信息，以 避免避免避免避免“ “遗漏遗漏遗漏遗漏” ”或或或或“ “重复重复重复重复” ”所造成的错误。所造成的错误。所造成的错误。所造成的错误。 第三步：明确目标要求，并用决策变量第三步：明确目标要求，并用决策变量第三步：明确目标要求，并用决策变量第三步：明确目标要求，并用决策变量 的线性函数来表示，确定对函数是取极大的线性函数来表示，确定对函数是取极大的线性函数来表示，确定对函数是取极大的线性函数来表示，确定对函数是取极大 还是

6、取极小的要求。还是取极小的要求。还是取极小的要求。还是取极小的要求。 决策变量的非负要求可以根据问题的决策变量的非负要求可以根据问题的决策变量的非负要求可以根据问题的决策变量的非负要求可以根据问题的 实际意义加以确定。实际意义加以确定。实际意义加以确定。实际意义加以确定。 讨论：这三步的顺序可以颠倒吗？讨论：这三步的顺序可以颠倒吗？讨论：这三步的顺序可以颠倒吗？讨论：这三步的顺序可以颠倒吗？ 为什麽？为什麽？为什麽？为什麽？ 三、 经济管理领域中 几类 三、 经济管理领域中 几类典型的LP问题典型的LP问题 经济管理领域中有大量的实际问题可以归结经济管理领域中有大量的实际问题可以归结经济管理领

7、域中有大量的实际问题可以归结经济管理领域中有大量的实际问题可以归结 为线性规划问题来研究，这些问题背景不同，为线性规划问题来研究，这些问题背景不同，为线性规划问题来研究，这些问题背景不同，为线性规划问题来研究，这些问题背景不同， 表现各异，但数学模型却有着完全相同的形表现各异，但数学模型却有着完全相同的形表现各异，但数学模型却有着完全相同的形表现各异，但数学模型却有着完全相同的形 式。式。式。式。 尽可能多地掌握一些典型的模型不仅有助尽可能多地掌握一些典型的模型不仅有助尽可能多地掌握一些典型的模型不仅有助尽可能多地掌握一些典型的模型不仅有助 于深刻理解线性规划本身的理论和方法，而且于深刻理解线

8、性规划本身的理论和方法，而且于深刻理解线性规划本身的理论和方法，而且于深刻理解线性规划本身的理论和方法，而且 有利于灵活地处理千差万别的实际问题，提高有利于灵活地处理千差万别的实际问题，提高有利于灵活地处理千差万别的实际问题，提高有利于灵活地处理千差万别的实际问题，提高 解决实际问题的能力。解决实际问题的能力。解决实际问题的能力。解决实际问题的能力。 （一） 生产组织与计划问题（一） 生产组织与计划问题 1. 1. 产品计划问题产品计划问题产品计划问题产品计划问题 2. 2. 产品配套问题产品配套问题产品配套问题产品配套问题 1、产品计划问题、产品计划问题 问题的一般提法：问题的一般提法：问题

9、的一般提法：问题的一般提法：用若干种原材用若干种原材用若干种原材用若干种原材 料（资源）生产某几种产品，原材料（资源）生产某几种产品，原材料（资源）生产某几种产品，原材料（资源）生产某几种产品，原材 料（或资源）供应有一定限制，要料（或资源）供应有一定限制，要料（或资源）供应有一定限制，要料（或资源）供应有一定限制，要 求制定一个产品生产计划，使其在求制定一个产品生产计划，使其在求制定一个产品生产计划，使其在求制定一个产品生产计划，使其在 一定数量的资源限制条件下能得到一定数量的资源限制条件下能得到一定数量的资源限制条件下能得到一定数量的资源限制条件下能得到 最大的收益。最大的收益。最大的收益

10、。最大的收益。 如果如果用用用用 ， 单位产品所需资源数（如原材料、人单位产品所需资源数（如原材料、人单位产品所需资源数（如原材料、人单位产品所需资源数（如原材料、人 力、时间等）、所得利润及可供应的资源力、时间等）、所得利润及可供应的资源力、时间等）、所得利润及可供应的资源力、时间等）、所得利润及可供应的资源 总量已知，如表所示，问应如何组织生产总量已知，如表所示，问应如何组织生产总量已知，如表所示，问应如何组织生产总量已知，如表所示，问应如何组织生产 才能使利润最大？才能使利润最大？才能使利润最大？才能使利润最大？ 种产品，生产 n AAA 21 种资源 m BBB, 21 产品计划问题有

11、关信息表产品计划问题有关信息表 单位单位 产产 产品产品 品品 所需所需 资源资源 资源资源 n AAA 21 可可 供供 应应 资资 源源 m B B B 2 1 mnmm n n aaa aaa aaa 21 22121 11211 m b b b 2 1 单位产品所得利润单位产品所得利润 n ccc 21 设出产品的计划数，可列出这类问 题的数学模型如下 设出产品的计划数，可列出这类问 题的数学模型如下： 是负数）（产品计划生产数不能 ），（ 总量）的总数不能超过可供应源（生产各种产品所需资 njx B ts xcMaxZ j j n j jj 210 . . 1 m)1,2,(i i

12、b n 1j j x ij a 一般的产品计划问题举例 例一般的产品计划问题举例 例1-7： 某工厂生产某工厂生产A、B两种产品，均需经过两道工序， 每生产一吨产品 两种产品，均需经过两道工序， 每生产一吨产品A需要经第一道工序加工需要经第一道工序加工2小时，第 二道工序加工 小时，第 二道工序加工3小时；每生产一吨产品小时；每生产一吨产品B需要经第一 道工序加工 需要经第一 道工序加工3小时，第二道工序加工小时，第二道工序加工4小时。可供利用 的第一道工序为 小时。可供利用 的第一道工序为12小时，第二道工序为小时，第二道工序为24小时。小时。 生产产品生产产品生产产品生产产品B B的同时产

13、出副产品的同时产出副产品的同时产出副产品的同时产出副产品C C，每生产一吨产品每生产一吨产品每生产一吨产品每生产一吨产品 B B，可同时得到可同时得到可同时得到可同时得到2 2吨产品吨产品吨产品吨产品C C而毋需外加任何费用；副产而毋需外加任何费用；副产而毋需外加任何费用；副产而毋需外加任何费用；副产 品品品品C C一部分可以盈利，剩下的只能报废。一部分可以盈利，剩下的只能报废。一部分可以盈利，剩下的只能报废。一部分可以盈利，剩下的只能报废。 出售产品出售产品出售产品出售产品A A每吨能盈利每吨能盈利每吨能盈利每吨能盈利400400元、产品元、产品元、产品元、产品B B每吨能盈利每吨能盈利每吨

14、能盈利每吨能盈利 10001000元，每销售一吨副产品元，每销售一吨副产品元，每销售一吨副产品元，每销售一吨副产品C C能盈利能盈利能盈利能盈利300300元，而剩余元，而剩余元，而剩余元，而剩余 要报废的则每吨损失要报废的则每吨损失要报废的则每吨损失要报废的则每吨损失200200元。经市场预测，在计划期元。经市场预测，在计划期元。经市场预测，在计划期元。经市场预测，在计划期 内产品内产品内产品内产品C C最大销量为最大销量为最大销量为最大销量为5 5吨。试列出线性规划模型，决吨。试列出线性规划模型，决吨。试列出线性规划模型，决吨。试列出线性规划模型，决 定定定定A A、B B两种产品的产量，

15、使工厂总的利润最大。两种产品的产量，使工厂总的利润最大。两种产品的产量，使工厂总的利润最大。两种产品的产量，使工厂总的利润最大。 信息整理：信息整理： 产产 品品 加加 工工 工工 时（小时）时（小时） 盈盈 利（百元）利（百元） 工序工序1 工序工序2 A 2 3 4 B 3 4 10 1：2 盈利（最大销量为盈利（最大销量为5） 3 C 报废报废 -2 可供利用工时可供利用工时 12 24 利润与产量的关系图：利润与产量的关系图： 利润与产量的关系图： 利润 利润 20 20- - - - - 5 - 5 5 10 5 10 产品A的产量 产品C的产量 数学模 型： 数学模 型： 设：设：x1产品产品A的产量，的产量，x2产品产品B的 产量， 的 产量，