线性规划是高中哪一章

第1章 线性规划

Chapter 1 Linear Programming 本章内容提要

线性规划是运筹学的重要内容。本章介绍线性规划数学模型、线性规划的基本概念以及求解线性规划数学模型的基本算法——单纯形法。

学习本章要求掌握以下内容： ? 线性规划模型的结构

? 线性规划的标准形式，非标准形式转化为标准形式

? 线性规划的图解以及相应的概念。包括：约束直线，可行半空间，可行解，

可行域，凸集，极点，目标函数等值线，最优解

? 线性规划的基本概念。包括：基，基础解，基础可行解，基变量，非基变

量，进基变量，离基变量，基变换

? 单纯形法原理。包括：基变量和目标函数用非基变量表出，检验数，选择

进基变量的原则，确定离基变量的方法，主元，旋转运算 ? 单纯形表。包括初始单纯形表的构成，单纯形表运算方法 ? 初始基础可行解，两阶段法 ? 退化的基础可行解

§1.1 运筹学和线性规划

1.1.1 运筹学

运筹学（Operations Research）是二十世纪三十年代二次大战期间由于战争的需要发展起来的一门学科。当时，英国组织了一批自然科学和工程科学的学者，和军队指挥员一起，研究大规模战争提出的一些问题。如轰炸战术的评价和改进、反潜艇作战研究

（一）线性规划

案例分析1

例1.10 飞乐公司经营一个回收中心，专门从事用三种废弃原材料C、P、H混合调出三种不同规格的产品ABD。根据混合时候各种材料的比例，可将该产品分为不同的等级（参照表1.12）。尽管在混合各种等级产品时允许一定的机动性，但每一等级产品中各种材料的最大值和最小值必须符合下面质量标准的规定（最大值和最小值是根据该材料的重量在该等级产品总重量中的比例来确定的）。在两种较高等级的产品中，有一种特定材料的比例是固定的。已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价，分别见表1.12和表1.13，问该厂应如何安排生产，使利润收入为最大？ 表1.12

产品名称 Ａ B D

规格要求 原材料C不少于５０％ 原材料Ｐ不多于２５％ 原材料C不少于２５％ 原材料P不多于５０％

不限

单价（元／kg）

50 35 25

回收中心可以从一些渠道定期收集到所需的固体废弃物，因此，可以获得维持稳定作业的处理量。表1.13给出了中心每天可以收集到每种材料的数量和原材料单价。

表1.13

原材料名称

C P H

每天最多供应量（kg）

100 100 60

单价（元／kg）

65 25 35

飞乐公司是绿地组织的全资公司，绿地组织

第一章 线性规划与单纯形法

线性规划的英文名称为“Linear Programming”，简称LP，它是运筹学中发展最早、理论与计算方法最成熟的分支，应用十分广泛。线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好（如产量最多，利润最大，成本最小）。简单地讲，也就是资源的最优利用问题。这类问题是在生产管理和经营活动中经常会遇到的。

早在1823年法国数学家傅里叶（Fourier）就提出了与线性规划有关的问题。 1939年，前苏联的经济学家康托洛维奇（Канторович）发表了重要著作《生产组织与计划中的数学方法》，书中针对生产的组织、分配、上料等一系列问题，提出了线性规划的模型，并给出了“解乘数法”的求解方法。当时这个工作未引起足够的重视。

1947年美国数学家丹捷格（Dantzig）提出了线性规划的一般数学模型和求解线性规划问题的通用方法——单纯形法（Simplex method），这标志着线性规划这一运筹学的重要分支的诞生。此后，对线性规划的研究日渐受到关注。

1960年康托洛维奇再次发表了《最佳资源利用的经济计算》一书，受到国内外的重视，为此他获得了诺贝尔经济学奖。此外，阿罗、萨缪尔逊、西蒙、多夫曼和胡尔威茨

第一章 习题

1. 思考题

（1）微分学求极值的方法为什么不适用于线性规划的求解？

（2）线性规划的标准形有哪些限制？如何把一般的线性规划化为标准形式？ （3）图解法主要步骤是什么？从中可以看出线性规划最优解有那些特点？

（4）什么是线性规划的可行解，基本解，基可行解？引入基本解和基可行解有什么作用？

（5）对于任意基可行解，为什么必须把目标函数用非基变量表示出来？什么是检验数？它有什么作用？如何计算检验数？

（6）确定换出变量的法则是什么？违背这一法则，会发生什么问题？ （7）如何进行换基迭代运算？

（8）大M法与两阶段法的要点是什么？两者有什么共同点？有什么区别？ （9）松弛变量与人工变量有什么区别？试从定义和处理方式两方面分析。 （10）如何判定线性规划有唯一最优解，无穷多最优解和无最优解？为什么？ 2. 建立下列问题的线性规划模型：

（1）某厂生产A，B，C三种产品，每件产品消耗的原料和设备台时如表1-18所示：

表1-18 产品 原料单耗 机时单耗 利润 A 2 2.5 10 B 3 3 14 C 5 6 20 资源数量 2000 2600 另外，要求三种产品总产量不低于65件，A的产量不高于B的产量。试制定使总利润最大的模型。

第一章 习题

1. 思考题

（1）微分学求极值的方法为什么不适用于线性规划的求解？

（2）线性规划的标准形有哪些限制？如何把一般的线性规划化为标准形式？ （3）图解法主要步骤是什么？从中可以看出线性规划最优解有那些特点？

（4）什么是线性规划的可行解，基本解，基可行解？引入基本解和基可行解有什么作用？

（5）对于任意基可行解，为什么必须把目标函数用非基变量表示出来？什么是检验数？它有什么作用？如何计算检验数？

（6）确定换出变量的法则是什么？违背这一法则，会发生什么问题？ （7）如何进行换基迭代运算？

（8）大M法与两阶段法的要点是什么？两者有什么共同点？有什么区别？ （9）松弛变量与人工变量有什么区别？试从定义和处理方式两方面分析。 （10）如何判定线性规划有唯一最优解，无穷多最优解和无最优解？为什么？ 2. 建立下列问题的线性规划模型：

（1）某厂生产A，B，C三种产品，每件产品消耗的原料和设备台时如表1-18所示：

表1-18 产品 原料单耗 机时单耗 利润 A 2 2.5 10 B 3 3 14 C 5 6 20 资源数量 2000 2600 另外，要求三种产品总产量不低于65件，A的产量不高于B的产量。试制定使总利润最大的模型。

第3章 线性规划

授课时间： 授课地点：

一、线性规划的数学模型 讲解P29情景案例 涉及知识点： ? 数学模型的建立 ? 模型的计算机软件求解 ? 线性规划的一般模型

二、线性规划的应用（一）

1、某公司有60万元资金，计划投资甲、乙两个项目，按要求对项目甲的投资不小于对项目乙投资的

2倍，且对每个项目的投资不能低于5万元，对项目甲每投资1万元可获得0.43万元的利润，对项目乙每投资1万元可获得0.6万元的利润，该公司正确提财投资后，在两个项目上共可获得的最大利润为 B

A.36万元 B.31.2万元 C.30.4万元 D.24万元

2、某企业生产甲、乙两种产品。已知生产每吨甲产品要用A原料3吨、B原料2吨；生产每吨乙产品要用A原料1吨、B原料3吨。销售每吨甲产品可获得利润5万元、每吨乙产品可获得利润3万元。该企业在一个生产周期内消耗A原料不超过13吨，B原料不超过18吨，那么该企业可获得最大利润是

A 12万 B 20万 C 25万 D 27万

3、某加工厂用某原料由车间加工出A产品，由乙车间

数学建模

第七章7.2

数学规划模型

7.1 奶制品的生产与销售自来水输送与货机装运

7.37.4 7.5

汽车生产与原油采购接力队选拔和选课策略 饮料厂的生产与检修

7.6 钢管和易拉罐下料y

数学建模

数学规划模型实际问题中 的优化模型 x~决策变量

Min(或Max) z f ( x), x ( x1 , x n ) s.t. g i ( x) 0, i 1,2, mf(x)~目标函数

T

gi(x) 0~约束条件 数 学 规 划 线性规划 非线性规划 整数规划

决策变量个数n和 多元函数 约束条件个数m较大 条件极值 最优解在可行域 的边界上取得

重点在模型的建立和结果的分析

数学建模

4.1 奶制品的生产与销售企业生产计划 空间层次

工厂级：根据外部需求和内部设备、人力、原料等 条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费 用参数等，以最小成本为目标制订生产批量计划。 时间层次 若短时间内外部需求和内部资源等不随时间变化，可 制订单阶段生产计划，否则应制订多阶段生产计划。 本节课题

数学建模

例1 加工奶制品的生产计划1桶 牛奶 或 12小时 8小时 3公斤A1 获利24元/公斤

4公斤A2

获利16元/公斤

每天：

管理运筹学 西北大学 经济管理学院 茹老师课件

运 筹 学西北大学经济管理学院 茹少峰 rsf00@http://www.77cn.com.cn

管理运筹学 西北大学 经济管理学院 茹老师课件

第8章整数线性规划

本章要求理解整数规划的含义；掌握两个变量的纯整数线性规划模型的图解法；掌握分枝定界 法的思想和方法；了解割平面法的原理；能够正 确引入0—1变量建立0-1线性规划模型；掌握指派 问题的求解算法；正确使用计算机软件求解整数 规划问题。

管理运筹学 西北大学 经济管理学院 茹老师课件

8.1 整数线性规划问题的提出在前面讨论的线性规划问题中，最优解可能是分数或小数，但对于某些 具体问题常要求最优解是整数。我们称这样的线性规划问题为整数线性规划 问题(Integer Linear Programming 简记为 ILP) 。 在整数规划中如果所有的变量都限制为整数，就称为纯整数规划(Pure ILP),如果仅一部分变量限制为整数，就称为混合整数规划(Mixed ILP), 整数规划的一个特例就是 0—1 规划，它的变量仅取 0 或 1。 例 8-1 投资决策问题 某部门在今后五年中可用于投资的资金总额为

数学建模

第七章7.2

数学规划模型

7.1 奶制品的生产与销售自来水输送与货机装运

7.37.4 7.5

汽车生产与原油采购接力队选拔和选课策略 饮料厂的生产与检修

7.6 钢管和易拉罐下料y

数学建模

数学规划模型实际问题中 的优化模型 x~决策变量

Min(或Max) z f ( x), x ( x1 , x n ) s.t. g i ( x) 0, i 1,2, mf(x)~目标函数

T

gi(x) 0~约束条件 数 学 规 划 线性规划 非线性规划 整数规划

决策变量个数n和 多元函数 约束条件个数m较大 条件极值 最优解在可行域 的边界上取得

重点在模型的建立和结果的分析

数学建模

4.1 奶制品的生产与销售企业生产计划 空间层次

工厂级：根据外部需求和内部设备、人力、原料等 条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费 用参数等，以最小成本为目标制订生产批量计划。 时间层次 若短时间内外部需求和内部资源等不随时间变化，可 制订单阶段生产计划，否则应制订多阶段生产计划。 本节课题

数学建模

例1 加工奶制品的生产计划1桶 牛奶 或 12小时 8小时 3公斤A1 获利24元/公斤

4公斤A2

获利16元/公斤

每天：

第一章 线性规划模型

第一章 线性规划模型

线性规划（Linear Programming）是数学规划的一个重要组成部分，是最优化与运筹学理论中的一个重要分支和常用的方法，是最优化理论的基础性内容。

第一节 线性规划问题及其数学模型

一、问题的提出

在生产管理和经营活动中经常提出一类问题，即如何利用有限的人力、物力、财力等资源，以便得到最好的经济效果。

例1 生产计划问题

某工厂在计划期内要安排生产Ⅰ、Ⅱ的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每件产品可获得的利润如下表所示。问应如何安排生产计划使该工厂获利最多？

设备 原材料A 原材料B 单位产品利润（元） Ⅰ 1 4 0 2 Ⅱ 2 0 4 3 资源限量 8(台时) 16(kg) 12(kg) 解：设x1,x2分别表示在计划期内生产产品Ⅰ、Ⅱ的产量。由于资源的限制，所以有：

机器设备的限制条件: x1?2x2?8

原材料A的限制条件： 4x1?16（称为资源约束条件） 原材料B的限制条件： 4x2?12

同时，产品Ⅰ、Ⅱ的产量不能是负数，所以有x1?0,x2?0（称为变量的非负约束）。

显然，在满足上述约束条件下的变量取值，均能构成可行方案，