方案
规格
12 3
y1(根)
2 21
4
56 7
8
11 000
9 10 需求量 0 0 1000
y2
1
02
10
43 2
1 0 1000
y3
0
10
23 012
4 5 1000
余料（m）
0 0.3 0.5 0.1 o.4 0 0.3 0.6 0.2 0.5
14
设xj(j=1,2…,10)为第j种下料方案所用圆钢的根数。则用料最少数学模型为:
线性规划及其通用解法--单纯形法一般认为是美国学者丹捷 格（G.Dantzig）在1947年研究美国空军军事规划时提出 的。
苏联学者康托洛维奇在1939年解决工业生产组织与计划问 题时就提出类似线性规划的模型及解法；康托洛维奇的工作 当时没有被重视，但直到1960年康托洛维奇再次发表《最 佳资源利用的经济计算》一书后，才受到重视。
一些常见的带有Spreadsheet的软件，如：Excel、 Lotus1-2-3等，均有内置的线性规划求解功能。
最优化问题求解软件，如：Lindo、Lingo、Matlab等。
3
线性规划问题提出
在生产管理和经营活动中经常会提出这样一类问题：如何利 用有限的人力、物力、财力等资源，取得最好的效果。例如： 配载问题 一交通工具，运输几种不同体积、重量的物资，如何装配， 所运的物资最多？
甲
乙
1
2
3
2
3
4
生产能力
8 12 36
单位产品获利
3
5
问如何安排甲、乙两产品的产量，使利润为最大。
8
线性规划数学模型
建立数学模型的步骤：
Step1 分析实际问题； Step2 确定决策变量； Step3 找出约束条件； Step4 确定目标函数； Step5 整理、写出数学模型。
9
线性规划问题举例
上述这些问题有如下共同特点： 问题解决要满足一定条件，称为约束条件； 问题有多个满足条件的解决方案； 问题解决有明确的目标要求，对应不同方案有
不同目标值，可表示成目标函数。
5
何谓线性规划问题
最优化问题
我们称如下一般问题：“在一定约束条件下，求目标函 数的最大或最小值”为最优化问题，用数学模型描述的 最优化问题，称为数学规划问题。
产品资源消耗表
产品
资源
甲
乙
丙
现有资源
设备A
3
1
2
200
设备B
2
2
4
200
材料C
4
5
1
360
材料D
2
3
5
300
利润（元/件）
40
30
50
11
线性规划问题举例
【例1.3】某商场决定：营业员每周连续工作5天后连续休息2天， 轮流休息。根据统计，商场每天需要的营业员如表1.2所示。
星期 一 二 三 四
表1.2 营业员需要量统计表
运筹学 Operations Research
Mob.:
1
线性规划及其基本理论
线性规划概述 线性规划问题 线性规划数学模型
一般模型 标准模型 线性规划解的概念 可行解、最优解 基阵、基解、基可行解 线性规划的基本性质
2
线性规划概述
线性规划（Linear Programming，简记为LP）是运筹 学中的一个最重要、应用最广泛的分支。
下料问题 用圆钢制造长度不等的机轴，如何下料，所剩的余料最少？
生产计划问题 企业生产A、B两种电器产品，两种产品的市场需求状况可以 确定，按当前的定价可确保所有产品均能销售出去。 企业可提供的两种原材料和劳动时间的数量是有限的。产品A 与产品B各应生产多少，可使企业总利润最大?
4
线性规划问题提出
需要人数 星期
需要人数
300
五
480
300
六
600
350
日
550
400
商场人力资源部应如何安排每天的上班人数，使商场总的营业员 最少。
12
线性规划问题举例
【例1.4】合理用料问题。某汽车需要用甲、乙、丙三种规 格的轴各一根，这些轴的规格分别是1.5，1，0.7（m）， 这些轴需要用同一种圆钢来做，圆钢长度为4 m。现在要制 造1000辆汽车，最少要用多少圆钢来生产这些轴？
120
110000 (千元)
25
20000 (吨)
180
——
150000 147000
(吨)
(千块)
3.5
4000 (千工日)
要求在充分利用各种资源条件下使建造住宅的总面积为最
大(即求安排各住宅多少m2)，求建造方案。
10
线性规划问题举例
【例1.2】最优生产计划问题。某企业在计划期内计划生产甲、乙、丙三种 产品。这些产品分别需要要在设备A、B上加工，需要消耗材料C、D，按工 艺资料规定，单件产品在不同设备上加工及所需要的资源如表1.1所示。已 知在计划期内设备的加工能力各为200台时，可供材料分别为360、300公斤； 每生产一件甲、乙、丙三种产品，企业可获得利润分别为40、30、50元，假 定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总 的利润收入最大？
13
【解】这是一个条材下料问题 ，设切口宽度为零。 设一根圆钢切割成甲、 乙、丙三种轴的根数分别为y1，y2，y3,则切割方式可用不等式 1.5y1+y2+0.7y3≤4表示，求这个不等式关于y1，y2，y3的非负整数解。象这样 的非负整数解共有10组，也就是有10种下料方式，如表1.3所示。
表1．3 下料方案
线性规划问题
在最优化问题中，如果约束条件与目标函数均是线性的， 我们就称之为线性规划问题。
6
线性规划问题的三个要素
决策变量
决策问题待定的量值称为决策变量。 决策变量的取值有时要求非负。
约束条件
任何问题都是限定在一定的条件下求解，把各种限制条件 表示为一组等式或不等式，称之为约束条件。
约束条件是决策方案可行的保障。 LP的约束条件，都是决策变量的线性函数。
【例1.1】某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各 体系资源用量及今年供应量见下表：
资源 住宅体系
砖混住宅 壁板住宅
大模住宅 资源限量造价钢材Fra bibliotek水泥砖
人工
(元/m2) (公斤/m2) (公斤/m2) (块/m2) (工日/m2)
105
12
110
210
4.5
135
30
190
——
3.0
目标函数
衡量决策方案优劣的准则，如时间最省、利润最大、成本 最低。
目标函数是决策变量的线性函数。 有的目标要实现极大，有的则要求极小。
7
线性规划数学模型
例 生产计划问题
某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车 间装配，相关数据如表所示：
车间
产品
A B C
工时单耗