1. 标准型的构成要素 （1）目标函数：max （2）约束条件：等式 （3）变量约束：非负 xj0 （4）资源限量：非负bi 0
18
2. 标准型的表示方法
（1）解析式
max Z c1 x1 c2 x2 cn xn
a11x1 a12x2 a1n xn b1
a21 x1
a22x2
a2n xn
1.线性规划及单纯形 法1
第一章 线性规划及其单纯形法
第一第节一章 线线性性规规划划及问单题纯及形数法学模型
Linear Programming , LP
• 1939年 苏 康托洛维奇和1941年 美 Hichook
在生产组织管理和制定交通运输方案方面研究和应用线性规划，求 解方法——解乘数法
• 1947年 G. B. Dantzig 单纯形法 • 1979年 苏 哈奇安多项式算法（椭球算法） • 1984年 Karmarkar算法
图解法意义不大，但可直观揭示有关概念。
11
3.LP解的类型
有4类： （1）唯一最优解
如例1的Q2点。 （2）无穷多最优解（多重解） （3）无界解 （4）无可行解
12
多重解示例
x2 当例1 的目标函数变为 max Z =2x1+4x2
①
96 3
③
4, 6
②
可行域
0
4
此线段上的点 均为最优点
Z=36
工 1 下 : 厂 ( 2 x 游 1 ) /5 0 .2 % 0s.t .
工 2 下 厂 :游
x1 0.8xx11
x2 x2
1.0 1.6 2.0 1.4
[0 .8 (2x 1)(1 .4x 2)/]70 0 .0 2 %
x1, x2 0
7
二、总结
线性规划问题（LP问题）的共同特征：
③
①
x1
16
4. 图解法的作用
揭示了线性规划问题有关规律和结论。
（1）规律：
有可行解 LP问题
有最优解
唯一解 无穷多解
无最优解（可行域为无界）
无可行解（无解）
（2）结论：若LP问题有最优解，则要么最优解唯一（对 应其中一个顶点），要么有无穷多最优解（对 应其中两个顶点连线上的所有点）。
17
五、 线性规划问题的标准型
b2
s.t.
am1 x1
am2 x2
amn xn
bm
x j 0, j 1,2,n
n :变量个数; m :约束行数; c j : 价值系数 bi : 右端项，bi 0, i 1,2,m; aij : 技术系数
19
简写的解析式
• 每一个问题变量都用一组决策变量（x1, x2, …, xn）表
示某一方案，这组决策变量的值代表一个具体方案，这 些变量是非负的且在某范围内连续取值。
• 存在一定的约束条件，这些约束条件可以用一组
线性等式或线性不等式来表示。
• 目标函数用决策变量的线性函数来表示。按问题
的不同，要求目标函数实现最大化和最小化。
原 A 约 料4 束 x 10x ： 216
原 B 约 料0 束 x 14x ： 212
变量非负约 x1 束0， ： x2 0
5
Step 3: 给出目标函数
mZ a 2 x x 1 3 x 2
Step 4: 整理数学模型
OBJ:maxZ 2x1 3x2
x1 s.t. 4x1
2x2 8 16
4x2 12 x1,x2 0
说明：OBJ 表示Objective;
s.t. 表示Subject to
6
例2 污水处理问题 (书P9)
2万m3 ，1000元/万m3 o工厂1
500万m3
200万m3
1.4万m3，800元/万m3 o工厂2
设 x1﹑x2 为 工 厂 1﹑2
OBJ : minZ 1000x1 800x2
的日污水处理量。建 立该问题的数学模型 为：
n :变量个数；m : 约束条件个数。
bi (, )0, i 1,2,m
9
四、两变量线性规划问题的图解法
1.线性不等式的几何意义— 半平面
2.图解法步骤
例1 （典型示例）：
• 作出LP问题的可行域
• 作出目标函数的等值线
• 移动等值线到可行域边界 得到最优点
OBJ : max Z 2x1 3x2
8
三、线性规划问题的一般形式
max(min)Z c1 x1 c2 x2 cn xn
a11 x1 a12 x2 a1n xn (, )b1
a21 x1 a22 x2 a2n xn
(, )b2
s.tБайду номын сангаас.
am1 x1
am2 x2
amn xn
(, )bm
x j (, )0, j 1,2,n
4
一、实例
例1 生产计划问题 (书P8，典型示例)
产品 I 设备 1 原料A 4 原料B 0 利润 2
II 资源限量 2 8台时 0 16公斤 4 12公斤 3
Step 1:明确问题，设定决策变量
设I、II两种产品的产量分别为x1, x2 。 Step 2: 确定约束条件
工时约x束 12： x2 8
多项式时间算法每次迭代不是从一个顶点出发求改进的顶点，而是使 迭代点保持在某个单纯形的内部，因此是一种内点算法。
3
LP是数学规划的一个重要分支，数学规划着重解决资源的 优化配置，一般可以表达成以下两个问题中的一个：
（1）当资源给定时，要求完成的任务最多； （2）当任务给定时，要求为完成任务所消耗的资源最少。 若上述问题的目标﹑约束都能表达成变量的线性关系， 则这类优化问题称LP问题。 LP是一种解决在线性约束条件下追求最大或最小的线性目 标函数的方法。
8
12
8, 3
x1
13
无界解示例
x2
①
可行域不闭合 Z增大方向
②
x1
14
产生原因：缺少约束条件 注 意：可行域不闭合不一定就会出现无界
解，这要看目标函数的性质。若目 标函数是min，则有最优解。无论 有无最优解，一定有可行解。
15
无可行解示例
x2
④
②
无公共区域(可行域) 产生原因：
有相互矛盾的 约束条件。
x1 2x2 8
s.t
.
4
x1
16 4x2 12
x1, x2 0
10
x2
Q6(0,4) Q4(0,3)
4x1=16 x1+2x2=8
Q3(2,3) Q5(4,3) Q2(4,2)
4x2=12
O(0,0)
Q1(4,0) Z=2x1+3x2
x1
Q7(8,0)
做目标函数2x1+3x2的等值线，与阴影部分的 边界相交于Q(4,2)点，表明最优生产计划为：生产I 产品4件，生产II产品2件。