s.t. （约束于：）
2 x1+2 x2 12
4x1
16
5 x2 15 x10， x2 0
此为有约束极值问题
1-2 线性规划问题的数学模型
1、原型：现实世界中人们关心、研究的实际对象。 模型：将某一部分信息简缩、提炼而构造的原型替代物。 数学模型：对现实世界的一个特定对象，为达到一定目的，
根据内在规律做出必要的简化假设,并运用适当数学工具得到 的一个数学结构。
多 退
约束为≤不等式，加上松弛变量，化为等式约束条件。
少 补
注意：松弛变量在目标函数中系数全为0。
例：max z=2 x1+3 x2
2 x1+2 x2 12
s.t.
4x1
16
5 x2 15
x10， x2 0
标准化
max z 2x1 3x2 0x3 0x4 0x5
2x1 2x2 x3
例：将下列线性规划模型化为标准形式。
min z x1 2x2 3x3
2x1 x2 x3 9
s.t.
3x1 3x1 2
x2 x2
2 x3 3x3
4 6
x1 0, x2 0, x3取值无限制
解：令z z x1 x1 (x1 0) x3 x3 x3 (x3 0, x3 0)
1-3 线性规划问题的标准形式
1、标准形式
或
2、条件
目标函数求极大值 约束条件全是等式（线性方程组） 决策变量全非负 右端常数全非负
3、标准化方法
（1）若目标函数求极小值，即
则令 z z
转化为
（2）若约束条件为不等式，
则依次引入松弛变量或剩余变量（统称为松弛变量），
转化为等式约束条件。
约束为≥不等式，减去松弛变量，化为等式约束条件；
右端列向量
矩阵形式
其中 C (c1,c2,L ,cn) 称为价值行向量；
x1
X
x2
M
xn
决策列向量
b1
b
b2
M
bm
右端列向量
a11 a12 L a1n
A
a21 a22 L M
a2n
P1, P2 ,L
, Pn
am1 am2 L amn
约束矩阵或系数矩阵
第一章 线性规划及单纯形法
Linear Programming and Simplex Method
§1.1 一般线性规划问题的数学模型
1-1 问题的提出
例1 用一块边长为a的正方形铁皮做一个无盖长方体容 器，应如何裁剪可使做成的容器的容积最大？
解：如图设四个角上减去的小正方形边
x 长为x，则容器体积为：
四、运筹学研究的基本特点
• 系统的整体优化 • 多学科的配合 • 模型方法的应用
五、运筹学研究的基本步骤
• 分析与表述问题 • 建立数学模型 • 对问题求解 • 对模型和模型导出的解进行检验 • 建立对解的有效控制 • 方案的实施
六、本课程的主要学习内容
第一章 线性规划及单纯形法 第二章 线性规划的对偶理论 第三章 运输问题 第四章 整数规划与分配问题 第六章 图与网络分析
a
V a 2x 2 x (0 x a ) 2
由 dV 0 dx
有 xa 6
时，容积最大
此为无约束的极值问题
例2 常山机器厂生产 I、II 两型产品。这两型 产品都分别要在A、B、C三种不同设备上加工。按 工艺规定，生产每件产品的单位利润、消耗三种 设备的工时以及各种设备工时的限额如下表：
原型
提炼
模型
数学工具 数学模型
2、规划问题
即求目标函数在若干约束条件下的最值。
3、规划问题数学模型的三要素
（1）决策变量：决策者为实现规划目标采取的方案、措施， 是问题中要确定的未知量。用x1，x2，…，xn表示。
（2）目标函数：问题要达到的目标要求，表示为决策变量的 函数。用 z=f(x1，x2，…，xn)表示。 （3）约束条件：决策变量取值时受到的各种可用资源的限制， 表示为含决策变量的等式或不等式。
• 国内 –1956年成立第一个运筹学小组 –1957年从“夫运筹策帷幄之中，决胜于千里之外”中 摘取“运筹”二字，将O.R.正式翻译为“运筹学”
三、运筹学的定义
研究对象：复杂系统的组织和管理 研究工具：数学，计算机科学及其他相关科学 研究目的：对有限资源进行合理规划、使用，并提供
优化决策方案。
参考《大英百科全书》、《辞海》、《中国企业管理百科全书》等。
12
s.t.
4
x1
5 x2
x4 16 x5 15
x1, x2 , x3, x4 , x5 0
（3）若决策变量xj≤0，则令
x
j
xj
且
x
j
0
（4）若决策变量xj取值无限制，则令
xj
x
j
x
j
其中
x
j，x
j
0
（“一分为二”）
（5）若约束等式的右端常数bi ≤ 0，则等式两边同时乘以“-1”。
并引入松弛变量x4, x5, 则问题化为标准形式：
运筹学
( Operations Research )
绪论
一、古代朴素的运筹学思想
例如：田忌赛马
二、运筹学的起源
• 国外 –英文原名 Operations Research 简称“O.R.” –直译为：运用研究或作业研究 –正式出现于1938年7月英国一份关于防空作战系统运 行的研究报告中 –二战后运筹学的发展经历了三个阶段
4、线性规划问题（Linear Programming）的数学模型
（1）条件：决策变量为可控的连续变量，目标函数和约束条 件都是线性的。简记为“L.P.”
（2）一般形式：
max (或 min) z=c1x1+c2x2+…+cnxn
s.t. a11x1+a12x2+…+a1nxn ≤（=，≥）b1 a21x1+a22x2+…+a2nxn ≤（=，≥） b2
…
am1x1+am2x2+…+amnxn≤（=，≥） bm
x1 , x2, …, xn≥0
（3）其他形式： 连加形式
向量形式
其中 C (c1,c2,L ,cn) 称为价值行向量；
x1
X
x2
M
xn
决策列向量
a1 j
Pj
a2 j
M
amj
系数列向量
b1
b
b2Biblioteka Mbm 单位产品消耗设 I II 设备工时限量
备工时
（小时）
设备A
22
12
设备B
40
16
设备C
05
15
单位利润（元） 2 3
如何安排生产才能使总的利润最大？
解：设计划期内两种产品的数量分别为x1，x2，则总利润为：
z=2 x1+3 x2 在满足限制条件下求z的最大值。
简记为：
max z=2 x1+3 x2