安徽大学：《运筹学》课程理论教案（PPT讲稿）第一章 线性规划

第一章 线性规戈划及单纯形法 线性规划问题及其数学模型 线性规划的解及其性质 解线性规划的单纯形法 单纯性法的进一步讨论 线性规划应用举例 3

3 第一章 线性规划及单纯形法 线性规划问题及其数学模型 线性规划的解及其性质 解线性规划的单纯形法 单纯性法的进一步讨论 线性规划应用举例

第一节线性规划问题及其数学模型 线性规划问题及其数学模型 1)线性规划问题的提出 例1（范例：产品配比问题）某工厂计划生 产甲、乙两种适销产品，每件利润分别为3百元 和5百元。甲、乙产品的部件各自在A、B两个车 间分别生产，每件甲、乙产品的部件分别需要A、 B车间的生产能力为1个工时和2个工时；两种产 品的部件最后都要在C车间装配，装配每件甲、 乙产品分别需要3工时和4工时 4

4 第一节 线性规划问题及其数学模型 一、线性规划问题及其数学模型 1)线性规划问题的提出 例1（范例：产品配比问题）某工厂计划生 产甲、乙两种适销产品，每件利润分别为3百元 和5百元。甲、乙产品的部件各自在A、B两个车 间分别生产，每件甲、乙产品的部件分别需要A、 B车间的生产能力为1个工时和2个工时；两种产 品的部件最后都要在C车间装配，装配每件甲、 乙产品分别需要3工时和4工时

第一节线性规划问题及其数学模型 假设A、B、C三个车间每天可用于生产这两 种产品的工时数分别为8、12和36。问应如何安排 生产这两种产品才能获利最多？ 解：这是一个典型的产品配比问题。因为 甲、乙两种产品需要争用C车间的有限能力。因 此就有一个如何搭配两种产品的产量，才能充分 发挥生产能力而获利最多的问题。 5

5 第一节 线性规划问题及其数学模型 假设A、B、C三个车间每天可用于生产这两 种产品的工时数分别为8、12和36。问应如何安排 生产这两种产品才能获利最多? 解： 这是一个典型的产品配比问题。因为 甲、乙两种产品需要争用C车间的有限能力。因 此就有一个如何搭配两种产品的产量，才能充分 发挥生产能力而获利最多的问题

第一节线性规划问题及其数学模型 现在来建立这个问题的数学模型。假设x1、 x2分别为甲、乙产品的日产量，Z为这两种产品 每天的总利润。下面先列出该问题的数据表： 6

6 第一节 线性规划问题及其数学模型 现在来建立这个问题的数学模型。假设x1、 x2分别为甲、乙产品的日产量，Z为这两种产品 每天的总利润。下面先列出该问题的数据表：

第一节线性规划问题及其数学模型 产品 单耗 (工时/件) 生产能力 车间 (时/天) 甲() 乙(2) A 1 0 8 B 0 2 12 C 3 4 36 利润 3 5 (百元/件) 表1-1例1（范例）的数据表 7

7 表1-1 例1（范例）的数据表 第一节 线性规划问题及其数学模型 产品 车间 单耗 (工时／件) 生产能力 (时／天) 甲(x1 ) 乙(x2 ) A B C 1 0 3 0 2 4 8 12 36 利润 (百元/件) 3 5

第一节线性规划问题及其数学模型 根据表1-1可知，甲、乙两种产品每天的总利 润是 Z=3X1+5x2 使总利润值Z达到最大是该厂追求的目标， 因此称①式为目标函数，而变量x1,X2的值需要 该厂决策部门加以确定，故称之为决策变量。 8

8 根据表1-1可知，甲、乙两种产品每天的总利 润是 Z = 3 x1 + 5 x2 ① 使总利润值Z达到最大是该厂追求的目标， 因此称①式为目标函数，而变量x1，x2的值需要 该厂决策部门加以确定，故称之为决策变量。 第一节 线性规划问题及其数学模型

第一节线性规划问题及其数学模型 因为生产甲、乙产品要消耗三个车间的生产 能力，而三个车间每天工时均为有限，所以根据 表1-1可知，决策变量x1,x2的值还必须满足以下 三个限制条件： 2 2X2 ≤12 3 3X1 4X2 ≤36 4 9

9 因为生产甲、乙产品要消耗三个车间的生产 能力，而三个车间每天工时均为有限，所以根据 表1-1可知，决策变量x1，x2的值还必须满足以下 三个限制条件： x1 ≤8 ② 2x2 ≤12 ③ 3x1 + 4x2 ≤36 ④ 第一节 线性规划问题及其数学模型

第一节线性规划问题及其数学模型 由于这三个不等式的左端都是关于变量x、 x2的函数，因此称之为函数约束。 又因为甲、乙产品的产量不能为负值，故x1, x,的取值还必须满足以下限制条件： x1≥0，x220 ⑤称之为非负性约束。( ②⑤式统称为约束 条件。 10

10 由于这三个不等式的左端都是关于变量xl、 x2的函数，因此称之为函数约束。 又因为甲、乙产品的产量不能为负值，故x1， x2的取值还必须满足以下限制条件： x1 ≥ 0，x2 ≥ 0 ⑤ ⑤称之为非负性约束。②~⑤式统称为约束 条件。 第一节 线性规划问题及其数学模型

第一节线性规划问题及其数学模型 这样，该问题的数学模型可归结为：在② ⑤这一组约束条件下，确定变量x1,】 2的数值， 使目标函数①式的函数值Z达到最大。为描述简 便起见，可将上述数学模型简记为： max Z=3x+5x2 ≤ 8 2X2 ≤ 12 3X1+ 4X2 ≤ 36 X1?X2≥0 11

11 这样，该问题的数学模型可归结为：在②~ ⑤这一组约束条件下，确定变量xl，x2的数值， 使目标函数①式的函数值Z达到最大。为描述简 便起见，可将上述数学模型简记为：         +    = + x x 0 3 x 4 x 36 2 x 12 x 8 max 3 5 1 2 1 2 2 1 1 2 ， Z x x 第一节 线性规划问题及其数学模型

第一节线性规划问题及其数学模型 其中max是英文maximize(最大化)的缩写 我们把例1称为范例，一方面是因为产品配比问 题是人们最早研究的问题之一，是具有代表性的 线性规划问题；另一方面是因为本章和下一章的 许多基本概念与方法多以它为示范来进行说明。 2)线性规划问题的数学模型 具体分析一下范例，可将这类问题归结为以 下共同要点：

12 其中max是英文maximize(最大化)的缩写； 我们把例l称为范例，一方面是因为产品配比问 题是人们最早研究的问题之一，是具有代表性的 线性规划问题；另一方面是因为本章和下一章的 许多基本概念与方法多以它为示范来进行说明。 2)线性规划问题的数学模型 具体分析一下范例，可将这类问题归结为以 下共同要点： 第一节 线性规划问题及其数学模型