安徽大学：《运筹学》课程实验教案（PPT讲稿）第一讲 什么是数学规划

第一讲 什么是数学规划？ 引言 灵敏度分析 产品组合问题 无界模型 线性概念 无包行解模型 分析LP解答 多重最优解与退 化 3

3 第一讲 什么是数学规划？ 引言 产品组合问题 线性概念 分析LP解答 灵敏度分析 无界模型 无可行解模型 多重最优解与退 化

1.1引言 1.1引言 数学规划是一种数学程序，是用来确定在有 限资源条件下的最优配置问题。有时，数学规划 也被称为在一定约束条件下的最优化。数学规划 中最为常见的一种类型是线性规划(Linear Programming),简记为LP。在社会经济的各个 领域中线性规划都有着广泛的应用。LP最常用的 应用领域是制定运输计划和生产计划。石油工业 很早就利用L解决了燃料的调和问题。 4

4 1.1 引言 1.1 引言 数学规划是一种数学程序，是用来确定在有 限资源条件下的最优配置问题。有时，数学规划 也被称为在一定约束条件下的最优化。数学规划 中最为常见的一种类型是线性规划 （Linear Programming），简记为LP。在社会经济的各个 领域中线性规划都有着广泛的应用。LP最常用的 应用领域是制定运输计划和生产计划。石油工业 很早就利用LP解决了燃料的调和问题

1.1引言 我们首先要搞清楚数学规划英文单词“Mathe matical Programming”中“programming”的确切 含义。数学规划中的programming的含义与计算 机程序设计英文单词“Computer Programming” 中的“programming”的含义完全不同。前者是指 计划和组织，后者是指写出执行计算的指令。 我们可以将一个最优化问题所涉及的对象分 为两大类。第一类是有限的资源，例如，土地、 工厂的生产能力和商店的销售能力 5

5 1.1 引言 我们首先要搞清楚数学规划英文单词“Mathe matical Programming”中“programming”的确切 含义。数学规划中的programming的含义与计算 机程序设计英文单词“Computer Programming” 中的“programming” 的含义完全不同。前者是指 计划和组织，后者是指写出执行计算的指令。 我们可以将一个最优化问题所涉及的对象分 为两大类。第一类是有限的资源，例如，土地、 工厂的生产能力和商店的销售能力

1.1引言 第二类是活动，例如，“生产低碳钢” “生产不锈钢”和“生产高碳钢”。每一个活动 将消耗（或者可能提供）一定数量的资源。我们 的问题是如何在有限的资源范围内，最合理地确 定活动的水平。下面我们通过一个简单的实例来 体会一下LP。 6

6 1.1 引言 第二类是活动，例如， “生产低碳钢” ， “生产不锈钢”和“生产高碳钢” 。每一个活动 将消耗（或者可能提供）一定数量的资源。我们 的问题是如何在有限的资源范围内，最合理地确 定活动的水平。下面我们通过一个简单的实例来 体会一下LP

1.2一个简单的产品组合问题 1.2一个简单的产品组合问题 Endianola?公司分别用两个产品专用生产线生 产Astro和Cosmo两种品牌的电视机。Astro生产线 每天可生产60台；而Cos0生产线每天可生产50 台。生产1台Ast0需要1个小时的劳动力，而生产 1台Coso需要2个小时的劳动力。目前，公司每 天最多可以提供120个劳动力用于生产这两种产品 的生产

7 1.2 一个简单的产品组合问题 1.2 一个简单的产品组合问题 Endianola公司分别用两个产品专用生产线生 产Astro和Cosmo两种品牌的电视机。Astro生产线 每天可生产60台；而Cosmo生产线每天可生产50 台。生产1台Astro需要1个小时的劳动力，而生产 1台Cosmo需要2个小时的劳动力。目前，公司每 天最多可以提供120个劳动力用于生产这两种产品 的生产

1.2一个简单的产品组合问题 如果每台Astro和Cosmo可分别获利S20和S30, 那么，两种产品每天应该生产多少，才能使得总 利润达到最大？ 我们首先用语言来描述我们要做的事情： Maximize(最大化产生的利润 subject to(满足 Astro产品数量小于等于Astro生产线生产能力， Cosmo产品数量小于等于Cosm0生产线生产能力， 使用劳动力要小于等于每天劳动力的最大供应量

8 1.2 一个简单的产品组合问题 如果每台Astro和Cosmo可分别获利$20和$30， 那么，两种产品每天应该生产多少，才能使得总 利润达到最大？ 我们首先用语言来描述我们要做的事情: Maximize(最大化) 产生的利润 subject to(满足) Astro产品数量小于等于Astro生产线生产能力, Cosmo产品数量小于等于Cosmo生产线生产能力, 使用劳动力要小于等于每天劳动力的最大供应量

1.2一个简单的产品组合问题 如果我们要求解这个问题，我们还要对这个 问题进行更加精确的描述。我们定义： A=每天生产的Astro)产品的数量 C=每天生产的CoSm0产品的数量 此外，我们给出计量单位：利润是美元，As o和Cosmoz是台，劳动力是小时/人 这样，我们就得到了这个问题更加精确的描 述： 9

9 1.2 一个简单的产品组合问题 如果我们要求解这个问题，我们还要对这个 问题进行更加精确的描述。我们定义： A = 每天生产的Astro产品的数量 C = 每天生产的Cosmo产品的数量 此外，我们给出计量单位：利润是美元，Astr o和Cosmo是台，劳动力是小时/人。 这样，我们就得到了这个问题更加精确的描 述：

1.2一个简单的产品组合问题 Model Maximize 20A+30C (美元) subject to <= :60 (台) <=50 (台) A+2C <=120 (小时/人) End 第1行，“Maximize20A+30C是目标函数； 而其它3行是约束。 10

10 1.2 一个简单的产品组合问题 Model Maximize 20A+30C (美元) subject to A <= 60 (台) C <= 50 (台) A+ 2C <= 120 (小时/人) End 第1行， “Maximize 20A+30C”是目标函数； 而其它3行是约束

1.2一个简单的产品组合问题 大多数最优化程序（也称为“求解程序” 都假设所有的变量只取非负值。所以，A≥0，C ≥0可以忽略 这个问题有3种资源：Astro的生产能力，Cos o的生产能力和劳动力的数量；有两个活动：生 产Astro产品和生产Coso产品。一般来说，在 个最优化模型中，每一个约束都与一些资源有关； 每一个决策变量，常常都与相应的具体活动有关 11

11 1.2 一个简单的产品组合问题 大多数最优化程序（也称为“求解程序”） 都假设所有的变量只取非负值。所以，A≥0，C ≥0可以忽略。 这个问题有3种资源：Astro的生产能力，Cos mo的生产能力和劳动力的数量；有两个活动：生 产Astro产品和生产Cosmo产品。一般来说，在一 个最优化模型中，每一个约束都与一些资源有关； 每一个决策变量，常常都与相应的具体活动有关

1.2一个简单的产品组合问题 Enginola问题可以用图1-1描述。可行的生产 组合范围是左下方的5个固定直线所谓的区域。在 这个范围内，我们要找出利润最大点的位置。 图1-1 Enginola问题的可行域 C 生产能力 C03m0 生产能力 C=50 60 C 50 40 30 可行的生产组合区城 劳动能力 盘+2C=120 20 10 0 10 20 30 40 50 6070 80 90 100110120 A Ast工Os 12

12 1.2 一个简单的产品组合问题 Enginola问题可以用图1-1描述。可行的生产 组合范围是左下方的5个固定直线所谓的区域。在 这个范围内，我们要找出利润最大点的位置。 图1-1 Enginola问题的可行域