1． 基阵 2． 基向量、非基向量、基变量、非基变量 3． 基解、基可行解、可行解
§2 图解法 一、图解法步骤：
以 x1 为横轴，x2 为纵轴，作出可行域
图示目标函数及 Z 增大的方向 确定最优解。
第一章 线性规划及单纯形法
可供选用，各种饲料每公斤营养成分含量及单价如表 所示：
饲料 1
蛋白质 （克）
3
矿物质 （克）
1
维生素 (毫克)
0.5
价格 （元/千克）
0.2
2
2
0.5
1.0
0.7
3
1
0.2
0.2
0.4
4
6
2
2
0.3
5
18
0.5
0.8
0.8
要求确定既满足动物生长的营养需要，又使费用最省 的选料方案。
第一章 线性规划及单纯形法
绪论
一、运筹学的简史
1、运筹学的早期发展历史
❖1914年提出兰彻斯特（Lanchester）战斗方程。 ❖1917年丹麦工程师爱尔朗（Erlang）提出排队论 的部分著名公式、 ❖20世纪20年代，提出存储论的最优批量公式。
2、二战期间的运筹学发展
❖ 20世纪30年代，运筹学（Operational research）作为科 学名字出现。
➢ 每一个问题都用一组决策变量表示某一方案， 一般这些变量的取值是非负。
➢ 存在一定的约束条件，这些约束条件可以用一 组线性等式或不等式来表示。
➢ 都有一个要求达到的目标，它可以用决策变量 的线性函数（称为目标函数）来表示。按照问 题的不同要求实现最大或者最小化。
课堂练习：
某饲养场饲养动物出售，设每头动物每天至少需700克 蛋白质、30克矿物质、100毫克维生素。现有五种饲料
第一章 线性规划及单纯形法
三.标准型： max Z=1 c1 x +c2 x2 +…+cn xn
a 11 x +a 12 x2 +…a 1n xn1 =b
s.t.
a21 1 x +a22
x2 +…a2n
xn =b2
a n1 x +an2 x2 +…nan xn =bn
1x ,x2 …xn ≥0 bi≥0,i=1,…m
s.t.
n
p j x j ≤(=,≥)b
j 1
X≥0
T
X=(x1 ,x2 ,…xn )
C1=(c ,c2 …cn )
第一章 线性规划及单纯形法
P j =(a 1 j ,a2 j ,…amj )T
b=(b1 ,b2 ,…bm )T max(min)Z=CZ
矩阵形式：s.t. AX≤(≥,=)b Z≥0
❖ 运用于雷达防空系统。 ❖ 应用于护航舰队保护商船的编队问题。 ❖ 应用于反潜深水炸弹的合理爆炸深度研究。 ❖ 应用于船只遭受敌机攻击时，转向逃避的问题研究。
该阶段运筹学研究和解决的问题，大部分都是些短期的 和战术性的问题。
3、二战之后的发展
❖ 正式的运筹研究组织成立，开始着重研究战略性的问 题。
运筹学
主讲：黄建华
everam@
主讲老师简介
黄建华，博士、副教授。东南大学管理学硕士，大连理工 大学工学博士。
研究方向：复杂网络与复杂系统、供应链管理。 主持课题：（1）国家社科基金：干扰模拟与基于二维网络 视角的农产品供应链脆弱性研究；（2）教育部人文社科基金： 农产品供应链网络的抗毁性能研究-基于复杂网络理论的研究 视角；（3）福建省社科基金：区域农产品供应链的抗毁性能 及农业产业安全策略研究。 第一作者在系统工程理论与实践、系统管理学报、系统工 程、北京理工大学学报等国内外核心期刊发表学术论文20余 篇，其中EI收录5篇。
am1 1 x +am2 x2 +…amn xn ≤（≥，=）bm
1x ，x2 ，…xn ≥0
第一章 线性规划及单纯形法
n
即： max(min)z= C j x j j 1
s.t.
n
aij x j ≤bi
j 1
i=1,…m
x j ≥0,j=1,…n
第一章 线性规划及单纯形法
向量形式：max(min)Z=CX
问题2：下料问题 问题3：配料问题 问题4：成批生企业年度生产计划的按 月分配 问题5：连续投资问题
二、
数学模型：
第一章 线性规划及单纯形法
ｍax(min)z=1C1 x +C2 x2 +…+Cn xn
a 111x +a 12 x2 +…a 1n xn ≤（≥，1 =）b
s.t.
a21 1 x +a22 x2 +…a2n xn ≤（≥，=）2b
2、图论与网络 3、排队论（随机服务系统理论） 4、存储论 5、对策论（竞赛论、博弈论） 6、决策论（多目标决策）
三、运筹学的工作步骤
1、提出和形成问题（目的、约束、可控变量）。 2、建立模型。 3、求解（利用各种数学方法或者计算机）。 4、解的检验。 5、解的控制。 6、解的实施。
第一章 线性规划及单纯形法
❖ 60年代后，除了军事方面的研究，运筹学在工业、农 业、经济和社会问题等各领域都有广泛应用。
❖ 运筹学技术自身得到飞速发展，并且形成了许多分支。
二、运筹学的主要内容
1、数学规划
❖ 线性规划（1947年由丹捷格提出） ❖ 非线性规划 ❖ 整数规划 ❖ 目标规划（1961年由查恩斯、库伯提出） ❖ 动态规划（1951年由贝尔曼提出） ❖ 随机规划
第一章 线性规划及单纯形法
线性规划数学模型的标准化
>=0
变
<=0
量
无约束
b大于等于0
约 b小于等于0
束 小于等于号 条 等于号 件 大于等于号
目 Max z
标 Min z 函 加入变量的系数 数
不处理
取相反数
两非负数之差
不处理
两边乘以-1
加松弛变量
加人工变量
减去剩余变量，加上人 工变量
不处理
取相反数
§1 线性规划问题及其数学模型
一、问题的提出：
问题1：合理利用资源问题
12
例1：
2
产品一 产品二
12
设备
1
2
8台时
原材料A 4
0
16kg
原材料B 0
4
12kg
每件产 2元
3元
品利润
max z=2x1 +3x2
1 x +2x2 ≤8
s . t.
41x
≤16
4x2 ≤12
1 x ≥0,x2 ≥0
线性规划数学模型的三个条件（特征）
松弛、剩余变量 0
人工变量
-M
第一章 线性规划及单纯形法
四、线性规划问题的解： 1． 可行解、可行域 2． 最优解
1
线性规划解的情况：R(A)=r,R(A
①r1 ≠r,无解
1)=r
②r1 =r=m=n，唯一解
③r1 =r=m<n，无穷多解
④r1 =r<m<n，有多余方程，可归为③
第一章 线性规划及单纯形法