*
*
运筹学
OPERATIONS RESEARCH
*
*
第一章 线性规划及单纯形法
(Linear Programming, LP)
线性规划模型
图解法
单纯形法原理
单纯形法计算步骤
单纯形法的进一步讨论
数据包络分析
应用举例
线性规划的发展
1947年，丹·捷格提出求解线性规划的单纯形法(Simple Method)
1950-1956年，主要研究线性规划的对偶理论
1958年，发表整数规划的割平面法
1960年，Dantzig和Wolfe研究成功分解算法，奠定了大规模线性规划问题理论和算法的基础。
1979年，Khachiyan，1984年，Karmarkaa研究成功线性规划的多项式算法。
理论上日益成熟、计算技术简单、应用广泛、现代管理科学的重要基础和手段之一。
§1 一般线性规划问题的数学模型
一、问题的提出
1、规划问题：在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。
【例1】用一块边长为a的正方形铁皮做一个容器，应如何裁剪，使做成的容器的容积为最大。
V=（a - 2x）2 ﹒x
用微积分中求极值的古典
方法解决，古典方法不是
规划问题。只处理简单的
表达式和简单的约束条件。
a
x
【例2】某厂生产两种产品，下表给出了单位产品所需资源及单位产品利润。
3
2
利润(元)
15
5
0
设备C(h)
16
0
4
设备B(h)
12
2
2
设备A(h)
计划期可用能力
Ⅱ
Ⅰ
Ⅰ，Ⅱ各生产多少, 可获最大利润?
解：用数学的语言进行描述:
1.决策变量：设产品I、II的产量分别为x1、x2
2.目标函数：问题要求获取利润最大，该公司获取利润为2x1 + 3 x2，令z = 2 x1 + 3 x2，则max z = 2 x1 + 3 x2，max z 是该公司获取利润的目标值，它是变量x1、 x2的函数，称为目标函数。
3.约束条件：两种产品受设备制造能力的限制，可用不等式表示为
2x1+2x2 12
4x1 16
5x2 15
x1，x2 0
综合例2的数学模型可表示为：
max z = 2 x1 + 3 x2
这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“.”是“subject to”的缩写，表示“满足于……”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1 ,x2 的取值。
2x1+2x2 12
. 4x1 16
5x2 15
x1，x2 0
2、线性规划研究的主要问题，可以归纳为两类：
一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。
另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。
—— 实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（ max 或 min ）。
【例3】 某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量
要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。
解：1.决策变量：设四种原料的使用量分别为：x1、x2 、x3 、x4
2.目标函数：设总成本为z，则有：min z = 5 x1 + 6 x2 + 7 x3 + 8 x4
3.约束条件：
x1 + 2x2 + x3 + x4 ≥160
2x1 +4 x3 +2 x4 ＝200
3x1 ＋x2 + x3 +2 x4 ≤180
x1，x2 ，x3 ，x4≥0
8
2
2
1
丁
7
1
4
1
丙
6
1
0
2
乙
5
3
2
1
甲
单位成本
（元／吨）
C
B
A
药物
原料
*
*
线性规划模型特点
决策变量：向量X=(x1… xn)T 决策人要考虑和控制的因素，非负
约束条件：关于X的线性等式或不等式
目标函数：Z=ƒ(x1 … xn) 为关于X 的线性函数，求Z极大或极小
*
*
二、线性规划问题的数学模型
（一）三个组成要素
1.决策变量:是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量，可由决策者决定和控制。
2.目标函数:指问题要达到的目的要求，表示为决策变量的函数。按照优化目标加上最大或者最小。
3.约束条件:指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。
1.数学模型由变量、目标函数和约束条件三部分组成;
2.决策变量为可控的连续变量;
3.目标函数和约束条件都是线性的。
———满足以上三个条件的数学模型称为线性规划
（二）LP的条件或LP数学模型的特点
（三）线性规划数学模型的几种形式
n个变量xj(j=1,2,3 …… n)，xj一般非负，从数
学意义上可以有xj≤0，这时xj的取值为（-∝，+
∝），称xj取值不受约束或无约束；
价值系数cj ；
资源系数bi(i=1,2,3……m) (资源拥有量，xj受
m项资源的限制)；
工艺系数（约束系数）aij表示xj 取值一个单位时
消耗的或所含有的第j种资源的数量，由技术条件
决定。
*
*
一般线性规划问题的数学模型：
目标函数：
约束条件：
*
*
简写形式：
*
*
矩阵形式表示为：
其中：
*
*
三、线性规划问题的标准形式
标准形式：
标准形式特点：
4. 决策变量取值非负。
1. 目标函数为求极大值；
2. 约束条件全为等式；
3. 约束条件右端常数项全为非负；
*
*
一般线性规划问题如何化为标准型：
1. 目标函数求极小值：
令： ，即化为：
求minZ等价于求max(－Z) ，一个变量的极小化等价于其相反数的极大化。令Z′= －Z , 则Z′=－∑cjxj于是转化为：max Z′= －∑cjxj
或者也可理解为：
*
*
2. 约束条件为不等式：
（1）当约束条件为“≤”时
如：
可令： ， 显然
（2）当约束条件为“≥”时
如：
可令： ， 显然
称为松弛变量。
称为剩余变量。
*
*
松弛变量和剩余变量统称为松弛变量
（3）目标函数中松弛变量的系数
由于松弛变量和剩余变量分别表示未被充分利用的资源以及超用的资源，都没有转化为价值和利润，因此在目标函数中系数为零。
*
*
3. 取值无约束的变量
如果变量 x 代表某产品当年计划数与上一年计划数之差，显然 x 的取值可能是正也可能是负，这时可令：
其中：
令
4. 变量 xj≤0
，显然
5. bi <0,该约束条件两边同乘以 -1。
xj =－xj ′代入即可；
*
*
例. 将下述线性规划模型化为标准型
*
*
解：令
得标准形式为：
练习题：
将下列问题化成标准型:
=x1+2x2-3x3
x1+x2+x3 ≤9
-x1-2x2+x3 ≥2
3x1+x2-3x3= - 5
x1 ≤0, x2 ≥0 , x3无约束
= -x1+2x2-3x3
x1+x2 + x3 7
x1-x2 + x3 2
-3x1+x2+2x3 = 5
x1,x2 0 ,x3 无非负限制
解：
maxZ'=x1' －2x2+3(x3'－x3")+0x4 +0x5
－x1' + x2+x3'－x3" + x4 = 9
x1'－2x2+x3' －x3" －x5 = 2
3x1 ' － x2+3(x3' － x3" ) =5
x1' ≥ 0，x2 ≥0，x3' ≥0，x3" ≥0 ，x4≥0 ， x5≥0
Max Z= x1-2x2+3x3' -3x3" + 0x4 +0x5
. x1+x2+ x3' - x3" +x4 =7
x1-x2+ x3' - x3" -x5=2
-3x1+x2+2x3' -2x3" =5
x1, x2,x3',x3", x4,x5 0
第一节小结：建立模型；三个组成要素；四种形式；化为标准形（4个条件5点）
*
*
为了便于建立 n 维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路，先介绍图解法。
图解法简单、直观，有利于理解LP求解的基本原理（基本思路）。缺点：只适合两个变量。
求解下述线性规划问题：
§2 线性规划问题的图解法
一、图解法的步骤
1、画出坐标系：以x1为横轴、x2为纵轴；
2、图示约束条件，找出可行域（所有约束条件的公共部分）；
3、图示目标函数的直线，标出目标函数值增加（或减小）的方向；
4、确定最优解。若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向平行移动，找与可行域最后相切的点，该点就是最优解；
5、将最优解代入目标函数，求出最优值。
*
*
画出线性规划问题的可行域：
目标函数等值线
*
*
（1）可行域：约束条件所围成的区域。
（2）基可行解：对应可行域的顶点。
（3）目标函数等值线：
（4）目标函数最优值: 最大截距所对应的 。
目标函数等值线有无数条，且平行。（观察规律)
注意几点：
max Z=50x1+30x2
. 4x1+3x2 120
2x1+x2 50
x1,x2 0
线性规划的图解法
【例】 LP模型
x2
50
40
30
20
10
10
20
30
40
x1
4x1+3x2 120
由 4x1+3x2 120
x1 0 x2 0
围成的区域
x2
50
40
30
10
10
20
30
40
x1
2x1+x2 50
由 2x1+x2 50
x1 0 x2 0
围成的区域
20
x2
50
40
30
20
10
10
20
30
40
x1
2x1+x2 50
4x1+3x2 120
可行域
同时满足：
2x1+x2 50
4x1+3x2 120
x1 0 x2 0
的区域——可行域
x2
50
40
30
20
10
10
20
30
40
x1
可行域
O（0，0）
Q1（25，0）
Q2（15，20）
Q3（0，40）
可行域是由约束条件围成的区域，该区域内的每一点都是可行解，它的全体组成问题的解集合。
该问题的可行域是由O，Q1，Q2，Q3作为顶点的凸多边形
x2
50
40
30
20
10
10
20
30
40
x1
可行域
目标函数是以Z作为参数的一组平行线
x2 = Z/30-（5/3）x1
x2
50
40
30
20
10
10
20
30
40
x1
可行域
当Z值不断增加时，该直线
x2 = Z/30-（5/3）x1
沿着其法线方向向右上方移动。
x2
50
40
30
20
10
10
20
30
40
x1
可行域
当该直线移到Q2点时，Z（目标函数）值达到最大：
Max Z=50*15+30*20=1350
此时最优解=（15，20）
Q2（15，20）
线性规划的图解法
Max z=x1+3x2
. x1+ x2≤6
-x1+2x2≤8
x1 ≥0, x2≥0
可行域
目标函数等值线
最优解
6
4
-8
6
0
x1
x2
【例】
maxZ=70X1+120X2
9X1+4X2≤360
4X1+5X2 ≤200
3X1+10X2 ≤300
X1≥0 ， X2≥0
线性规划的图解法
【例】
.
90 80 60 40 20
0 20 40 60 80 100
x1
x2
9x1+4x2 ≤ 360
4x1+5x2 ≤200
3x1+10x2 ≤300
A
B
C
D
E
F
G
H
I
Z=70x1+120x2
maxZ=70X1+120X2 9X1+4X2≤360 4X1+5X2 ≤200 3X1+10X2 ≤300 X1≥0 ， X2≥0
*
*
二、解的几种情况：
（2）无穷多最优解：目标函数图形与某个约束条件平行；
（1） 唯一最优解：目标函数直线与凸多边形只有一个切点；
若目标函数改为：
约束条件不变，则:
目标函数等值线
此时，线段
上所有点都是最优
值点。
*
*
（4）无界解（无最优解）：可行域无界。一般是漏了一些约束条件。
（3） 无可行解：当可行域为空集时，无可行解。
若目标函数不变，将约束条件1和3去掉，则可行域及解的情况见下图。
目标函数等值线
此时，目标函数等值线可以向上无穷远处平移，Z值无界。
解的情况一：
有最优解
⊙有唯一最优解
⊙有无穷最优解
无最优解
⊙无界解
⊙无可行解
解的情况二：
有可行解
⊙有唯一最优解
⊙有无穷最优解
⊙无界解
无可行解
三、图解法的启示 图解法只能用来求解含有两个决策变量的线性规划问题，但对求解一般线性规划问题的单纯形法有很大启示：
1、LP解有四种情况； 2、若可行域存在，则可行域是一个凸集。这一事实可以推广到更多变量的场合； 3、若最优解存在，则必在可行域（凸集）的某个顶点处取得。
4、解题思路。
课后习题
1. c=d=0时，此时点O、A、B、C都是最优解；
2.（1）c=0,d﹥0时，目标函数等值线x2=z/d,点C为最优解
（2）c=0,d﹤0时，目标函数等值线x2=z/d,点O、A为最优解 ；
3.（1）d =0, c﹥0时，目标函数等值线x1=z/c,点A为最优解
（2）d =0, c﹤0时，目标函数等值线x1=z/c,点O、C为最优解 ；
O
X1
X1
C
A
B
课后习题
4. （1）c ﹥ 0,d﹥0时，x2=-cx1/d+z/d,c/d ﹥5/2时，点A为最优解，c/d =5/2时，点A、B为最优解 ，3/4 ﹤ c/d ﹤ 5/2时，点B为最优解 ； c/d =3/4时，点B 、C为最优解, c/d ﹤3/4时，点C为最优解;
（2） c ﹥0,d﹤0时，x2=-cx1/d+z/d，点A为最优解;
（3） c ﹤0,d﹤0时，x2=-cx1/d+z/d，点O为最优解;
（4）c ﹤0,d﹥0时，x2=-cx1/d+z/d，点C为最优解。
O
X1
X1
C
A
B
*
*
求解线性规划问题：
就是从满足约束方程组和约束不等式的决策变量取值中，找出使得目标函数达到最大的值。
一、线性规划问题的解的几个概念（针对标准形）
§3．单纯形法原理
*
*
1.可行解（feasible solution）：满足约束条件的解称为可行解，可行解的集合称为可行域。
2.最优解（optimal solution）：使目标函数达到最大值的可行解。
3.基 (radix) ：约束方程组的一个满秩子矩阵（非奇异子矩阵）（|B|0），称为规划问题的一个基，基中的每一个列向量称为基向量，与基向量对应的变量称为基变量（basic variable），其他变量称为非基变量。
4.基解（basic solution）：在约束方程组中，令所有非基变量为0，可以解出基变量的唯一解，这组解与非基变量的0共同构成基解。
5.基可行解（basic feasible solution）：满足变量非负的基解称为基可行解。
6.可行基（feasible basis）：对应于基可行解的基称为可行基。
线性规划的基本概念
线性规划的基矩阵、基变量、非基变量
=
=
目标函数
约束条件
行列式≠0
基矩阵
右边常数
*
*
例：考察下述线性规划问题：
*
*
（1） 可行解，如
或
满足约束条件，所以是可行解。
（2） 基
系数矩阵A：
其中
或
都构成基。而
不构成基。
*
*
（3）基向量、基变量
是对应于基
的三个基向量，而
是对应于这三个基向量的基变量。
（4）基解、基可行解、可行基
是对应于基
的一个基解、基可行解。
是对应于基
的一个基解、基可行解。
均是可行基 。
例：基解
Maxz = 1500 x1 + 2500 x2
. 3 x1 + 2x2 + x3 = 65
2 x1 + x2 +x4 = 40
3x2 +x5 = 75
x1 ,x2 ,x3 ,x4 ,x5 ≥ 0
注意，线性规划的基本解、基本可行解（极点）和可行基只与线性规划问题标准形式的约束条件有关。
3 2 1 0 0
A = [P1 ,P2 ,P3 ,P4 ,P5] = 2 1 0 1 0
0 3 0 0 1
A矩阵包含以下10个3×3的子矩阵：
B1=[p1 ，p2 ，p3] B2=[p1 ，p2 ，p4]
B3=[p1 ，p2 ，p5] B4=[p1 ，p3 ，p4]
B5=[p1 ，p3 ，p5] B6=[p1 ，p4 ，p5]
B7=[p2 ，p3 ，p4] B8=[p2 ，p3 ，p5]
B9=[p2 ，p4 ，p5] B10=[p3 ，p4 ，p5]
其中B4= 0，因而B4不是该线性规划问题的基。其余均为非奇异方阵，因此该问题共有9个基。
对于基B3=[p1 ，p2 ，p5]，令非基变量x3 = 0，x4 = 0，在等式约束中令x3 = 0，x4 = 0，解线性方程组：
3 x1 + 2 x2 + 0 x5 = 65
2 x1 + x2 + 0 x5 = 40
0 x1 + 3 x2 + x5 = 75
得到x1 =15，x2 = 10，x5 = 45，对应的基本可行解：
x=(x1 ，x2 ，x3 ，x4 ，x5)T=(15，10，0，0，45)T。于是对应的基B3是一个可行基。
类似可得到
x(2) = (5,25,0,5,0)T （对应B2）
x(7) = (20,0,5,0,75)T （对应B5）
x(8) = (0,25,15,15,0)T （对应B7）
x(9) = (0,0,65,40,75)T （对应B10）
是基本可行解；
而x(3)= (0,,0,,)T（对应B9）
x(4)= (65/3,0,0,-10/3,75)T （对应B6）
x(5)= (,25,,0,0)T （对应B1）
x(6) = (0,40,-15,0,-45)T （对应B8）
是基本解。
例：找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解。
maxZ=2X1+3X2 +X3
X1 +X3 =5
X1+2X2 +X4 =10 X2 +X5=4 Xj ≥0 ,j= 1,2,3,4,5
解：该LP的全部基解见下表①-⑧ ，打“√” 者为基可行解，注“﹡”者为最优解
19
0
0
3
4
2
⑧
22
0
-3
0
4
5
⑦
0
0
5
⑥
15
4
0
-5
0
10
⑤
10
4
5
0
0
5
④
17
0
2
5
4
0
③
20
-1
0
5
5
0
②
5
4
10
5
0
0
①
是否基可行解
Z
X5
X4
X3
X2
X1
解的集合：
可行解
基解
基最优解
基可行解
线性规划解之间的关系
可行解与最优解：最优解一定是可行解，但可行解不一定是最优解。
2. 可行解与基解：基解不一定是可行解，可行解也不一定是基解。
3. 可行解与基可行解：基可行解一定是可行解，但可行解不一定是基解。
4. 基解与基可行解：基可行解一定是基解，但基解不一定是基可行解。
5 .最优解与基本解：最优解一定是基解，基解不一定是最优解。
例：已知线性规划问题
maxZ=X1+3X2
X1 +X3 =5 …………… ①
X1+2X2 +X4 =10 …………… ② X2 +X5 =4 …………… ③ Xj ≥0 ,j= 1,2,3,4,5 …………… ④
下表中所列的解（a）—（f）均满足约束条件① ② ③ 试指出表中哪些解是可行解，哪些是基解，哪些是基可行解。
0
2
5
4
0
(f)
2
6
5
2
0
(e)
0
4
1
(d)
4
7
2
0
3
(c)
4
0
-5
0
10
(b)
0
0
3
4
2
(a)
X5
X4
X3
X2
X1
序 号
*
*
凸集：如果集合 C 中任意两个点 ，其连线上的所有点也都是集合C 中的点。
上图中（1）（2）是凸集，（3）（4）不是凸集
二、凸集和顶点
为什么X1、X2连线可表示为：X=X1 +(1-)X2 (01)
n维欧氏空间：线性空间，令=（X-X2 ）/（X1-X2 ）
=0时，X=X2，右端点；
=1时，X=X1，左端点
0 1时，X1与X2之间任一点
X2
X
X1
因此，凸集定义用数学语言可表示为：
设C是一个集合，X1 与 X2 是C中任意两点，如果X=X1 +(1-)X2 (01)也是C中的点，称C是一个凸集。
（几何意义：任意两点连线上的点都是C中的点）。
例（凸集）
例（非凸集）
例（凸集性质）
二个凸集的交还是凸集
二个凸集的并不一定是凸集
多边形上的点是顶点
圆周上的点都是顶点
顶点：如果对于凸集 C 中的点 X ，不存在C 中的任意其它两个不同的点 ，使得 X 在它们的连线上，这时称 X 为凸集的顶点。或者设D是C中的点，但D不在C中任何两点的连线上，则称D是C的一个顶点。
可行域的性质：
线性规划的可行域是凸集
基可行解：对应可行域的顶点。
线性规划的最优解在顶点上
凸集
凸集
不是凸集
顶点
*
*
三、线性规划问题基本定理（一般形式、标准形式均适用）
定理1:若线性规划问题存在可行解，则问题的可行域是凸集。（可行域的几何特征，图解法直观印象的一个推广，理论上加以肯定。证明思路：按照凸集的定义，可行域内任意两点的连线仍在可行域内）
证明:设 是线性规划的任意两个可行解，则
于是对于任意的 ，设 ，则
所以 也是问题的可行解，即可行域是凸集。
*
*
引理: 线性规划问题的可行解 X为基可行解的充要条件是X的正分量所对应的系数列向量线性无关。
证明:设
（1）必要性显然。
（2）设 A 的秩为m。可行解 X 的前 k 个分量为正，且它们对应的系数列向量 线性无关，则 。
当 时， 恰好构成一组基，而
就是这组基对应的基可行解。
当 时，在 基础上从其余列向量中可以找出
个线性无关的向量，恰好构成一组基，而 X 就是这组基对应的基可行解。
必要性：基可行解→ 线性独立
充分性：线性独立 →基可行解
*
*
定理2: 线性规划问题的基可行解 X 对应线性规划问题可行
域（凸集）的顶点。
证明:问题即是要证明: X是基可行解 X是可行域顶点，也即要证明其逆否命题： X不是基可行解 X不是可行域顶点 。
（1）X不是基可行解 X不是可行域顶点。
假设X是可行解，但不是基可行解，X 的前 k 个分量为正,其余分量为0，
则有
又X不是基可行解，所以由引理知，正分量对应的列向量
线性相关。即存在一组不全为零的数 ，使得
*
*
用非零常数 乘以上式得：
（1）+（3）得：
（1）-（3）得：
令
选择合适的 ，使得所有的
于是 均是可行解，并且 ，所以 X 不是可行域顶点。
*
*
（2）X不是可行域顶点 X不是基可行解 。
设 不是可行域的顶点，因而可以找到可行域内
另两个不同的点 ，
使得 ， 用分量表示即为：
易知，当 时，必有
所以
所以
于是（1）-（2）得
而 不全为零，于是知 线性相关，X不是基可行解。
*
*
定理3: 若线性规划问题有最优解，一定存在一个基可行解是最优解。
引理： 有界凸集中的任何一点均可表示成顶点的凸组合。
证明:假设 是可行域顶点， 不是可行域顶点 ，且目标函数在 处达到最优，即 。
由引理知： 可表示为 的凸组合，即
因此
假设 是所有 中最大者，则
而 是目标函数的最大值，所以 也是最大值，
也即，目标函数在可行域的某个顶点达到了最优。
*
*
前三个定理的递进关系：（1）可行解；（2）基可行解；（3）最优解
意义：从上述三个定理可以看出，要求线性规划问题的最优解，只要比较可行域（凸集）各个顶点对应的目标函数值即可，最大的就是我们所要求的最优解。理论上，只要找出可行域的所有顶点，然后比较目标值，即可找到最优解。但要找顶点，则需要找到基。问题是在技术上如何去实现？
定理四：若LP在可行域的两个顶点上达到最优，则在两个顶点的连线上也达到最优。
定理五：LP问题的一般形式与标准形式等价，即二者解的情形是完全对应相同的。
学习几个定理的思考：学习关于LP的几个基本定理，目的也让我们想一下，LP问题看上去似乎简单，可是为什么一直到20世纪中期才得以解决，在解决的过程中遇到了哪些问题，他们是如何一步一步解决的。了解这一发展过程，也使我们想一下以前的人们分析问题、处理问题的方法，这种方法和思路对我们自己今后工作和学习是有帮助的。
四、单纯形法迭代原理
思路：从一个基可行解出发（如何去找一个基可行解？），判断其是否为最优解（如何判断？）， 若不是，则转换到相邻的基可行解（如何转换）并使目标函数值不断增大，一直找到最优解为止。
*
*
1.确定初始基可行解
设给定线性规划问题：
*
*
因此约束方程组的系数矩阵为：
添加松弛变量得其标准形为：
*
*
由于该矩阵含有一个单位子矩阵，因此，这个单位阵就是一组基，就可以求出一个基可行解：
说明：如果约束条件不全是 形式，如含所有 形式，则无法找到一个单位阵做为一组基，这时需要添加人工变量。后面的内容介绍。
称其为初始基可行解。
总之，确定初始基可行解：
1）当所有约束是≤时，可通过加一些松弛变量来实现；
2）当约束是≥或=时，具体方法在后面介绍。
（结论：不管在什么情况下，初始基可行解总可以找到）
*
*
2.基可行解的改进：从初始基可行解转换为另一个（相邻的）基可行解 。如何转换？
定义：两个基可行解是相邻的，如果他们之间变换且仅变换一个基变量。
思路：对初始基可行解的系数矩阵进行初等行变换，构造出一个新的单位矩阵，其各列所对应的变量即为一组新的基变量，求出其数值，就是一个新的基可行解。
设有初始基可行解 ，并可设前m 个 分量非零，即 ，于是
*
*
由构造初始可行基的方法知前m 个基向量恰好是一个单位阵，所以约束方程组的增广矩阵为
由于任意系数列向量均可由基向量组线性表示，则非基向量中的 用基向量组线性表示为：
*
*
设有 ，则
（1）+（2）得：
由此式可知，我们找到了满足约束方程组的另一个解 ，
要使其成为可行解，只要对所有i=1,2,…m ，下式成立
要使其成为基可行解，上面m个式中至少有一个取零。
（基可行解中非零分量的个数不超过m 个。）
[与 比较]
*
*
于是前m个分量中的第l个变为零，其余非负，第j个分量为正，于是非零分量的个数 ，并可证得
线性无关，所以 是新的基可行解。
从而找到另一个基可行解，且是相邻的。
此过程也即对约束方程的增广矩阵（A b） 进行初等变换，使Pj 成为单位向量。变换后第l列出基，第j列入基,然后再检验其是否最优解。
从上述过程，我们可以得到单纯形法解的转换的一般步骤。
若aij ≤0,则对应的分量≥0; 因此只需要使aij>0对应的分量≥0即可,只要取
*
*
3.最优性检验和解的判别: 已经得到一个基可行解，判断其是否最优解
设有基可行解
比较两者对应的目标函数值，哪一个更优？
*
*
2）若对所有的 ，则 ，
就是最优解。
是判断是否达到最优解的标准，称为检验数。
1）当 时， ，目标函数值得到
了改进， 不是最优解，需要继续迭代。
易知
j =cj-zj=cj-∑ciaij= cj-( c1a1j+ c2a2j+…+ cmamj)，称为最优性检验数。
*
*
当所有 时，现有顶点对应的基可行解即为最优解。
2.当所有 时，又对某个非基变量 有
则该线性规划问题有无穷多最优解。
所有非基变量j < 0，(j=m+1,m+2,…,n),X是唯一最优解。
3. 如果存在某个 ，又 向量的所有分量 ，对任意 ，恒有 ，则存在无界解。
结论（适用于无人工变量的问题）
4.若某个j>0,则不是最优解，可以改进；
5.无可行解的判别后面第5节讲。
单纯形法原理总结：
1.我们知道在标准形中，找一个单位基矩阵并求出该基对应的基可行解。
2.检验该基可行解是否最优？通过非基变量的检验数。
3.若不是最优，则旋转找另一个基可行解，直到最优。
对此原理，我们可以通过单纯形表来实现。
初始基本可行解
是否最优解或
无限最优解?
结束
沿边界找新
的基本可行解
N
Y
单纯形法的基本过程
*
*
§4 单纯形法的计算步骤
Max(min)Z=c1x1+ c2x2+…+cnxn
a11x1+ a12x2+…+ a1nxn =b1
a21x1+ a22x2+…+ a2nxn=b2
… … …
am1x1+ am2x2+…+ amnxn =bm
xj 0(j=1,…,n)
设有线性规划问题：
*
*
(1)找到初始可行基，建立初始单纯形表.
(4) 重复二、三两步，直至找到最优解。
单纯形法的计算步骤
(2)进行最优性检验。
计算检验数，若所有 ≤0 则得最优解，结束.否则转下步.
若某 ≥ 0 而 ≤0 ，则最优解无界，结束.否则转下步.
(3)从一个可行解转换到另一个目标函数值更大的基可行解。
由最大增加原则确定进基变量；由最小比值原则选择出基变量；以 为主元素进行换基迭代。
*
*
…
…
(1)找到初始可行基，建立初始单纯形表.
0
0
…
…
…
…
…
…
…
是初始基。
教材上例5 之初始单纯形表
0
0
0
3
2
σj
1
0
0
[5]
0
15
X5
0
0
1
0
0
4
16
X4
0
0
0
1
2
2
12
X3
0
X5
X4
X3
X2
X1
b
XB
CB
0
0
0
3
2
Cj
*
*
(2)进行最优性检验
计算检验数，若所有 ≤0 则得最优解，结束.否则转下步.
若某 ≥ 0 而 ≤0 ，则最优解无界，结束.否则转下步.
检验数的计算方法：
基变量的检验数一定为0。判断是否达到最优时，只要考虑非基变量检验数。
例:下表中给出一个求最大化问题的单纯形表，问表中字母取何值时有：（a)表中解为最优解；（b)表中解为唯一最优解；（c）表中解无穷多最优解之一；（d）该LP具有无界解；（e）该LP不是最优解。
0
0
0
b
a
cj-zj
1
0
0
-3
2
3
x5
0
1
0
-5
-1
2
x4
0
0
1
c
4
5
x3
x5
x4
x3
x2
x1
（a）a ≤ 0， b ≤ 0；（b）a < 0， b < 0；（c）a ≤ 0， b ≤ 0,且a、b中至少一个为0；（d）b>0,c ≤0；（e）a、b中至少一个大于0
（3）换基迭代（转换基可行解）：从一个基可行解转换到另一个目标函数值更大的基可行解，列出新的单纯形表
a.由最大增加原则确定进基变量。取σj>0最大者(k)对应的变量Xk为进基变量（换入变量）
(特殊：两个以上最大者，任意选取其中一个) ;
b.由最小比值原则选择出基变量。用Xk所在列中正系数去除相应b列中数，选取比值最小者对应的基变量（Xl ) 作为出基变量（换出变量）;
c.以 alk 为主元素进行换基迭代。以alk为主元素做初等行变换，把主元素alk化为1，所在列其他元素（包括检验数）化为0 。
得到新的基可行解和新基，并相应画出一张新的单纯形表。
具体解释如以下几页：
进基
出基
0
0
0
3
2
σj
1
0
0
[5]
0
15
X5
0
0
1
0
0
4
16
X4
0
0
0
1
2
2
12
X3
0
X5
X4
X3
X2
X1
b
XB
CB
0
0
0
3
2
Cj
教材上例5 之初始单纯形表
=
目标函数
约束条件
基矩阵
右边常数
进基变量、离基变量、基变换
=
基变量
=
进基变量
离基变量
目标函数
约束条件
右边常数
=
=
目标函数
约束条件
新的基矩阵
右边常数
=
=
进基变量
离基变量
目标函数
约束条件
基矩阵
=
=
目标函数
约束条件
新的基矩阵
右边常数
=
*
*
(3)从一个可行解转换到另一个目标函数值更大的基可行解。
由最小比值原则选择出基变量；
进基变量
由最大增加原则确定进基变量：
当某些非基变量的检验数 时，为使目标函数值增加地更快，一般选择正检验数中最大者对应的非基变量进基 ，成为新的基变量。
为确保新的基可行解的非零分量非负，按下述规则求得最小
比值 ，其所对应的原基变量中的 出基。
于是，新的一组基是：
*
*
以 为主元素进行换基迭代：
即利用初等行变换将进基变量 所在的系数列变为单位列向量，而 变为1。这样原来基矩阵中的 就不再是单位向量，取而代之的是 ，这样就找到了一组新的基。
(4) 重复二、三两步，直至找到最优解。
说明：若目标函数是求最小，可以不必将其转变为求
最大，但在使用单纯形法求解时，确定进基变
量，应找负检验数中最小者，并应以检验数
全部为正作为判别最优的条件。
例5各基可行解和图解法中可行域的顶点的一一对应关系
X1=（0,0,12,16,15)T Z1=0
X2=（0,3,6,16,0)T Z2=9
X3=（3,3, 0,4,0)T Z3=15
P17图： X1---O； X2---Q4; X3---Q3
*
*
maxZ=3x1 +5 x2 +0x3 +0x4+0x5
x1 + x3 =8
2x2 + x4 =12
3x1 +4 x2 + x5 =36
x1 ，x2 ，x3 ，x4 ，x5 0
解 将模型标准化
例 maxZ=3x1 +5x2
x1 8
2x2 12
3x1+4x2 36
x1 ，x2 0
*
*
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
3
5
0
0
0
8
1
0
1
0
0
12
0
2
0
1
0
36
3
4
0
0
1
x3
x4
x5
0
0
0
0
3
5
0
0
0
-
12/2=6
36/4=9
作出单纯形表，进行迭代
检验数最大
比值最小
*
*
检验数j
8
1
0
1
0
0
6
0
1
0
1/2
0
12
3
0
0
-2
1
x3
x2
x5
0
5
0
30
3
0
0
-5/2
0
8
-
4
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
3
5
0
0
0
8
1
0
1
0
0
12
0
2
0
1
0
36
3
4
0
0
1
x3
x4
x5
0
0
0
0
3
5
0
0
0
-
12/2=6
36/4=9
*
*
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
3
5
0
0
0
8
1
0
1
0
0
6
0
1
0
1/2
0
12
3
0
0
-2
1
x3
x2
x5
0
5
0
30
3
0
0
-5/2
0
8
-
4
检验数j
4
0
0
1
2/3
-1/3
6
0
1
0
1/2
0
4
1
0
0
-2/3
1/3
x3
x2
x1
0
5
3
42
0
0
0
-1/2
-1
最优解 :X*=(4,6,4,0,0)T，Z*=42
例：求解线性规划问题（可以参考叙述方式）
解：化为标准形式：
MAX Z=2X1+X2 MAXZ=2X1+X2+0X3+0X4 +0X5
5X2≤15 5X2 + X3 =15
st. 6X1+2X2 ≤24 st. 6X1+2X2 +X4 =24
X1+ X2≤ 5 X1+ X2 +X5 =5
X1≥0, X2≥0 Xi≥0,i=1,2,3,4,5
于是,得到一个基可行解X=（0,0,15,24,5)T
此时,基变量为(X3, X4, X5),非基变量为(X1,X2 ),
非基变量的检验数为(2,1),不是最优解
我们可以列初始单纯形表如下:
X5
X4
X3
X2
X1
b
XB
CB
X5
X4
X3
5
24
15
0
0
0
1
2
σj
1
0
0
1
1
0
0
1
0
2
[6]
0
0
0
1
5
0
0
0
0
0
1
2
Cj
进基
出基
X1=（0,0,15,24,5)T Z1=0
X4换出，X1换入，得到一组新的基变量X3、X1、X5，对此表做初等行变换,画出新的单纯形表
1
4
15
B
X5
X1
X3
XB
0
-1/3
0
1/3
0
σj
1
-1/6
0
[2/3]
0
0
0
1/6
0
1/3
1
2
0
0
1
5
0
0
X5
X4
X3
X2
X1
CB
X2=（4,0,15,0,1)T Z2=8
仍非最优解，X2换入，X5换出,画出新的单纯形表
X2
X1
X3
XB
3/2
7/2
15/2
b
-1/2
-1/4
0
0
0
σj
3/2
-1/4
0
1
0
1
-1/2
1/4
0
0
1
2
-15/2
5/4
1
0
0
0
X5
X4
X3
X2
X1
CB
此时,非基变量检验数全部<0,于是得到最优解为
X﹡=(7/2,3/2,15/2,0,0) T ,最优值为:Z﹡=17/2
maxZ=70X1+120X2 P1 P2 P3 P4 P5
9X1+4X2+X3=360 9 4 1 0 0
4X1+5X2 +x4=200 A= 4 5 0 1 0
3X1+10X2+x5 =300 3 10 0 0 1
Xj≥0 j=1,2,…,5
例 （此例可以作为练习题）
0 0 0
σj
0 0 1
1 0 0
0 1 0
84
20
24
X3
X1
X2
0
120
120
34 0 0 0 -12
σj
0 1 0
0 0 1
1 0 0
240
50
30
X3
X4
X2
0
0
120
70 120 0 0 0
σj
9 4 1 0 0
4 5 0 1 0
3 10 0 0 1
360
200
300
X3
X4
X5
0
0
0
X1 X2 X3 X4 X5
b
XB
CB
C1 C2 c3 c4 c5
Cj
注意：单纯形法中，
1、每一步运算只能用矩阵初等行变换；
2、表中第3列（b列）的数总应保持非负（≥ 0）；
3、当所有检验数均非正（≤ 0）时，得到最优单纯形表；
4、基变量下面对应单位向量；
5、基变量检验数为0；
6、检验数用定义和初等行变换两种方法求都可以；
7、基解和图解法凸集的顶点一一对应；
8、解的退化：当选择换出变量求比值时，有两个相同的最小比值，任选一个基变量作为换出变量，则下面表中另一基变量的值将等于0，这种现象成为退化。含一个或多个基变量为0的基可行解为退化的基可行解。出现退化解时，可以随意决定哪一个变量为换出变量，不必考虑理论上可能出现的循环的后果。
例：下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ＝5X1 + 3X2，约束形式都为 ，X3,X4为松弛变量，表中解代入目标函数后得Z＝l0
（a）求a一g的值；
（b）表中给出的解是否为最优解。
用到三点：1.把解代入目标函数；2.基变量下面对应单位向量，而且基变量检验数为0；3.用定义求非基变量的检验数。
g
f
-1
b
cj - zj
1
0
e
d
a
X1
1/5
1
0
c
2
X3
X4
X3
X2
X1
（a）求a一g的值；
（b）表中给出的解是否为最优解。
（a=7，b=-6，c=0，d=1，e=0，f=1/3，g=0）
例：下表中给出某线性规划问题计算过程中的一个单纯形表，目标函数为maxZ= 28X4+X5 +2X6，约束条件都为，表中X1， X2 ,X3为松弛变量，表中解的目标函值为Z=14。
g
0
0
1
X6
-1
0
5/2
1
X5
0
2
d
6
5
X2
0
0
c
b
cj - zj
1
f
e
0
0
X4
0
-14/3
0
3
a
X6
X4
X3
X2
X1
*
*
一、人工变量（大M法）
用单纯形法解题时，需要有一个单位阵作为初始基。
当约束条件都是“≤”时，加入松弛变量就形成了初始基。
但实际存在“≥”或“＝”型的约束，没有现成的单位矩阵。
采用人造基的办法：添加人工变量，构造单位矩阵
§5 单纯形法的进一步讨论
*
*
人工单位矩阵的构造方法
在“ ”的不等式约束中减去一个剩余变量后可变为等式约束，但此剩余变量的系数是（-1），所以再加入一个人工变量，其系数是（+1），因而在系数矩阵中可得到一个相应的单位向量，以便构成初始单位阵，即初始基矩阵。
在原本就是“ = ”的约束中可直接添加一个人工变量，以便得到初始基矩阵。
△人工变量是在等式中人为加进的，人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为（-M）（M为无穷大的正数）。
总之，方法两句话：约束条件引入人工变量，目标函数中人
工变量系数为-M
注意三点：
△M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。
△如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。
△M作为一个数学符号一起参加运算；
*
*
例 解线性规划
解 化为标准型
此时无单位矩阵作为初始基。
*
*
添加人工变量，构造初始基：
（求最小值问题中，人工变量系数取M）
*
*
-3
0
1
0
0
-M
-M
x1
x2
x3
x4
x5
x6
x7
1
1
1
1
0
0
0
-2
1
-1
0
-1
1
0
0
3
1
0
0
0
1
初始单纯形表：
C
CB
XB
b
0
x4
4
-M
x6
1
-M
x7
9
-3-2M
4M
1
0
-M
0
0
4
1
3
3
0
2
1
1
-1
0
-2
1
-1
0
-1
1
0
6
0
4
0
3
-3
1
1
-
1
0
x4
3
0
x2
1
-M
x7
6
σj
-3+6M
0
1+4M
0
3M
-3M
0
*
*
-3
0
1
0
0
-M
-M
x1
x2
x3
x4
x5
x6
x7
C
CB
XB
b
0
0
3
0
3/2
-M-3/2
-M+1/2
-
3
3/2
0
0
0
1
-1/2
1/2
-1/2
0
1
1/3
0
0
0
1/3
1
0
2/3
0
1/2
-1/2
1/6
0
x4
0
0
x2
3
-3
x1
1
-3/2
0
0
0
-3/4
-M+3/4
-M-1/4
0
x4
0
0
x2
5/2
1
x3
3/2
σj
0
0
0
1
-1/2
1/2
-1/2
-1/2
1
0
0
-1/4
1/4
1/4
3/2
0
1
0
3/4
-3/4
1/4
*
*
此时人工变量全部出基，并已达最优条件。
最优解为
，最优值为
例：求下列线性规划问题（参考叙述方式）
MAX Z=3X1-X2- X3
X1 -2X2 + X3 ≤11
st. -4X1 + X2 + 2X3 ≥3
-2X1 + X3 =1
X1≥0, X2≥0 , X3≥0
解：约束条件中引入松弛变量、剩余变量和人工变量，得到
MAX Z=3X1-X2- X3 – MX6 – MX7
X1 -2X2 + X3 + X4 =11
-4X1 + X2 +2X3 – X5 + X6 = 3
st. -2X1 + X3 + X7 =1
XI>=0, I=1..7
X4, X6, X7为基变量，令非基变量X1= X2= X3 =X5=0，得初始基可行解X（0）=（0,0,0,4,0,1,9)T 列出初始单纯形表，单纯形法求解过程如下
1
3
11
b
0
1
0
0
X7
0
0
1
0
X6
-m
0
(-1+3m)
-1+m
3-6m
cj - zj
0
0
[1]
0
-2
X7
-1
0
2
1
-4
X6
0
1
1
-2
1
X4
X5
X4
X3
X2
X1
XB
1
1
10
b
-3m+1
1
-2
-1
X7
0
0
1
0
X6
-m
0
0
-1+m
1
cj - zj
0
0
1
0
-2
X3
-1
0
0
[1]
0
X6
0
1
0
-2
3
X4
X5
X4
X3
X2
X1
XB
1
1
12
b
-m-1
1
-2
-5
X7
-m+1
0
1
2
X6
-1
0
0
0
(1)
cj - zj
0
0
1
0
-2
X3
-1
0
0
1
0
X2
-2
1
0
0
(3)
X4
X5
X4
X3
X2
X1
XB
9
1
4
B
-m+2/3
-7/3
-2
-5/3
X7
-m+1/3
4/3
1
2/3
X6
-1/3
-1/3
0
0
0
cj - zj
-3/4
-2/3
1
0
0
X3
-1
0
0
1
0
X2
-2/3
1/3
0
0
1
X1
X5
X4
X3
X2
X1
XB
最优解为X﹡=(4,1,9,0,0,0,0) T ,最优值为:Z﹡=2
例：大M法
Max z = 5x1+2x2+3x3-x4-Mx5-Mx6
. x1+2x2+3x3+x5 =15
2x1+x2+5x3 +x6 =20
x1+2x2+4x3 +x4=26
x1 -x6 ≥ 0
大M法 （了解一下其它形式）
得到最优解：(25/3，10/3，0，11)T
最优目标值：112/3
*
*
maxZ= 3x1 - x2 -2 x3
3x1 + 2 x2 -3 x3 =6
x1 - 2 x2 + x3 =4
x1 , x2 , x3 ≥0
.
例 解线性规划
maxZ= 3x1 - x2 -2 x3 -M x4 -M x5
3x1 + 2 x2 -3 x3 + x4 =6
x1 - 2 x2 + x3 + x5 =4
x1 , x2 , x3 , x4 , x5 ≥0
解:按大M法构造人造基，引入人工变量x4 , x5 的辅助问题如下：
*
*
作出单纯形表，进行迭代
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
3
-1
-2
-M
-M
6
3
2
-3
1
0
4
1
-2
1
0
1
3+4M
-1
-2-2M
0
0
x4
x5
-M
-M
2
4
检验数j
2
1
2/3
-1
1/3
0
2
0
-8/3
2
-1/3
1
0
-3-8M/3
1+2M
-1-4M/3
0
x1
x5
3
-M
*
*
检验数j
2
1
2/3
-1
1/3
0
2
0
-8/3
2
-1/3
1
0
-3-8M/3
1+2M
-1-4M/3
0
x1
x5
3
-M
-
1
检验数j
3
1
-2/3
0
1/6
1/2
1
0
-4/3
1
-1/6
1/2
0
-5/3
0
-M-5/6
-M-1/2
x1
x3
3
-2
最优解 :X*=(3,0,1)T，Z*=7
原因：克服计算机求解时的麻烦，引进两阶段法
方法：
第一阶段：约束条件与大M方法相同，目标函数实现最小
化，为人工变量相加。
用单纯形法求解如果W=0，这时候的最优解就是原线性规划
的一个可行解，说明原问题存在基可行解，可以进行第二阶段
的运算，否则原问题无可行解，停止计算。
二、两阶段法
计算机上使用大M法时，需要用机器最大字长的数字代替
M，但当某些系数与之较接近时，或远小于这个数字，还是可
能会出错。另外一种求解带人工变量的线性规划问题的方法不
会出现这种问题-------两阶段法。
第二阶段：将第一阶段的最终单纯形表所对应的解，去掉人工变量，目标函数按原来的。作为第二阶段的初始单纯形表的初始基可行解，进行单纯形法的迭代，直到求出最优解。
思考：为什么可以在原来的表上继续往下计算，而
不用从头算？从头算行吗？
点评：两阶段法十分巧妙，第一阶段判断LP有无可
行解，第二阶段利用第一阶段计算的单纯形表继续往
下计算。
第一阶段问题
MaxW = - x5 - x6
. x1 +2x2 + 3x3 + x5 = 15
2x1 + x2 + 5x3 + x6 = 20
x1 + 2x2+4x3 + x4 = 26 x1 ,x2 ,x3 ,x4 ,x5 ,x6 ≥0
例：两阶段法
第一阶段
得到最优解为:(0，15/7，25/7，52/7，0,0)T
最优目标值： 0
第二阶段
得到原问题的最优解:(25/3，10/3，0，11)T
最优目标值：112/3
*
*
解（1）化标准型、并添加人工变量得：
Min f = 2x1 + 3 x2 （此处未将目标变为MAX）
. x1 + x2 –x3 +x6 = 350
x1 - x4 +x7 =125
2 x1 + x2 +x5 =600
x1 , x2 , x3, x4, x5 ,,x6,x7≥ 0
例：目标函数： Min f = 2x1 + 3 x2
约束条件：
. x1 + x2 ≥ 350
x1 ≥ 125
2 x1 + x2 ≤ 600
x1 , x2 ≥ 0
*
*
（2）构造第一阶段问题：
Min z = x6 +x7 (Max z = -x6 -x7)
. x1 + x2 –x3 +x6 = 350
x1 - x4 +x7 =125
2 x1 + x2 +x5 =600
x1 , x2 , x3, x4, x5 ,,x6,x7≥ 0
说明：原问题目标函数无论是求MAX还是求MIN，构造的
第一阶段问题目标函数都是求最小MIN。
*
*
求解第一阶段问题：
*
*
此时所得可行解目标函数值为0，故原规划问题有基可行
解。转入第二步。
*
*
（3）去掉人工变量，得到第二阶段的单纯形表，在此
基础上继续求解。
最优解为：
*
*
小结：表格单纯形表的使用
（1）化线性规划模型为标准型，建立初始单纯形表。
（2）根据单纯形表按照最大增加原则选择进基变量；
（3）按照最小比值原则选择换出变量；
（4）实施矩阵的初等变换进行换基迭代；
（5）建立新的单纯形表；
（6）重复上述过程直到求得最优表格为止。
例：已知线性规划问题
minz=-5x1-6x2-7x3
-x1+5x2-3x3≥15
-5x1-6x2+10x 3≤20
x1-x2-x3 = - 5
x1≤0,x2≥0,x3无约束
要求：（1）化为标准形式；
（2）分别列出用大M法求解时的初始单纯形表和两阶段法求解时第一阶段的初始单纯形表。
解： 令x1/= - x1, x3=x3/- x3//，x3/，x3//≥0，z/=- z，则max z/= -5 x1/-6x2+7( x3/- x3//)+ 0 x4 + 0 x5 -M x6-M x7
x1/+5x2 -3x3/+3x3//- x4 + x6 =15 5x1/ -6x2+10 x3/-10 x3// +x5 =20
x1/+ x2 + x3/- x3// + x7= 5
x1/ ,x2, x3/,x3// , x4, x5, x6, x7≥0
0
0
0
-1
2
-2
6
2
cj-zj
0
0
1
1
0
0
0
1
0
-1
0
0
3
-10
-1
-3
10
1
5
-6
1
1
1
1
-1 x6 15
0 x5 20
-1 x7 5
x7
x6
x5
x4
x3//
x3/
x2
x1/
-1
-1
0
0
0
0
0
0
*
*
三、关于解的不同情况的判别
1、无穷多最优解
例：
解：将问题化为标准型：
*
*
*
*
从上表中可知，已达最优解，为 ，
而 ，若将 选为进基变量迭代后，可得另一最优
解
上述两最优解分别对应两个顶点，而两点连线上的点均是最优解，故有无穷多最优解。
判别无穷多最优解的方法：单纯形表的检验数行已达最有性条件（全部小于或等于零），且有一个非基变量的检验数为零，此时有无穷多最优解。
*
*
2、无界解
例 用单纯形表求解下面线性规划问题。
解
*
*
迭代次数
基变量
CB
x1 x2 s1 s2
b
比值
1 1 0 0
0
s1
s2
0
0
1 -1 1 0
-3 2 0 1
1
6
1
—
cj-zj
1 1 0 0
0
1
x1
s2
1
0
1 -1 1 0 0 -1 3 1
1
9
cj-zj
0 2 -1 0
1
此时 的检验数仍为正，但系数列全为负，此时可判断这个线性规划问题是无界的，即目标函数值可以取得无限大。
*
*
事实上，此从1次迭代的单纯形表中，得到约束方程：
移项可得：
由此可知，目标
函数可以任意大，
即无界。
*
*
3、无可行解
例 用单纯形表求解下列线性规划问题
解：化为标准型：
*
*
基变量
CB
20 30 0 0 0 -M
b
x1 x2 s1 s2 s3 a1
s1
s2
a1
0
0
-M
3 10 1 0 0 0
1 0 0 1 0 0
1 1 0 0 -1 1
150
30
40
15
—
40
cj-zj
20+M 30+M 0 0 -M 0
-40M
单纯形表求解线性规划问题
*
*
1
x2
s2
a1
30
0
-M
3/10 1 1/10 0 0 0
1 0 0 1 0 0
7/10 0 -1/10 0 -1 1
15
30
25
50
30
250/7
cj-zj
11+7/10M 0 -3-M/10 0 -M 0
2
x2
x1
a1
30
20
-M
0 1 1/10 -3/10 0 0
1 0 0 1 0 0
0 0 -1/10 -7/10 -1 1
6
30
4
cj-zj
0 0 -3-M/10 -11-7M/10 -M 0
迭代次数
基变量
CB
x1 x2 s1 s2 s3 a1
b
比值
20 30 0 0 0 -M
单纯形法的最终表里有人工变量大于零，则此线性规划无可行解。
*
*
练习：用大M法求解下列线性规划问题
1、
2、
*
*
解1：将模型化为标准型得：
建立单纯形表并计算如下
*
*
显然，检验数已全部非正，已达最优解，但非基变量X2的
检验数为0，故知此问题有无穷多最优解。
*
*
解2：将模型化为标准型得：
建立单纯形表并计算如下
*
*
*
*
最优解为（4，4） T
小结：关于解的判别
1、无穷多最优解：若所有j≤0，且有某个非基变量的j=0，则有无穷多个解；当所有非基变量j < 0，(j=m+1,m+2,…,n),则X是唯一最优解。
2、无界解：若某个j>0,若同时又有该正的检验数相应变量的系数Pj<=0（即没有正数）,则线性规划有无界解。
3、无可行解：当添加人工变量求解时，如果出现所有j≤0，其基变量中仍含有非零的人工变量（或两阶段法求解时候第一阶段WO），表明问题无可行解。
例:下表中给出一个求最大化LP问题的单纯形表，x5 为人工变量。问表中d、a1、a2、c1、c2分别为何值时：（a)表中解为唯一最优解；（b）表中解无穷多最优解之一；（c）表中解为退化的可行解；（d）下一步将以x1替换基变量x5 ；（e）该LP具有无界解；（f）该LP无可行解。
0
0
0
c2
c1
cj-zj
1
0
0
-3
a2
3
x5
0
1
0
-5
-1
2
x4
0
0
1
a1
4
d
x3
x5
x4
x3
x2
x1
（a)d ≥ 0, c1<0, c2< 0；（b）d ≥ 0, c1 ≤0, c2 ≤ 0 ,且c1, c2 至少一个为0；（c）d=0或d>0，c1>0,d/4=3/ a2 （d）c1>0, 3/ a2 < d/4，a2 >0, (d>=0)；（e）c2 > 0 ，a1≤0；（f）x5 为人工变量，c1 ≤0, c2 ≤ 0
（a)表中解为唯一最优解；d ≥ 0, c1<0, c2< 0
（b）表中解无穷多最优解之一； d ≥ 0, c1 ≤0, c2 ≤ 0 ,且c1, c2 至少一个为0
（c）表中解为退化的可行解；d=0或d>0，c1>0,d/4=3/ a2
（d）下一步将以x1替换基变量x5 ； c1>0, 3/ a2 < d/4，
a2 >0, (d>=0)
（e）该LP具有无界解； c2 > 0 ，a1≤0
（f）该LP无可行解；x5 为人工变量，c1 ≤0, c2 ≤ 0
四、单纯形法计算的向量矩阵描述
假定LP问题：maxZ=∑cjxj
∑aijxj≤bi i=1,2,…,m
xj ≥0 j=1,2,…,n
用矩阵形式加上松弛变量为：
maxZ=CX+0Xs
AX+IXs=b
X ≥0, Xs ≥0
其中Xs为松弛变量Xs=（xn+1,xn+2,…,xn+m）T,I为m×m单位矩阵。单纯形法计算时，总选取I为初始基，对应基变量为Xs,这样在初始单纯形表中，可以将矩阵分成作为初始基的单位矩阵I和非基变量的系数矩阵A两块。计算迭代后，新单纯形表中的基是由上述两块矩阵中的部分向量转化并组合而成。为清楚起见，把新单纯形表中的基（也即单位矩阵I）对应的初始单纯形表中的那些向量抽出来（？）单独列出一块，用B表示，A中去掉B的若干列后，剩下的列组成矩阵N，这样初始单纯形表可以如下表示。
0
基变量
非基变量
初始解
非基变量
基变量
基可行解
0
初始单纯形表
初等行变换后
0
CB CN
cj-zj
Ⅰ
B N
0 XS b
XS
XB XN
基变量
非基变量
当迭代若干步后，基变量为XB时，则该步的单纯形表中由XB系数组成的矩阵I，Xs的系数矩阵为B-1（因为单纯形法的迭代是对约束增广矩阵进行的初等行变换）故当基变量为XB 时，新的单纯形表为
CN-CBB-1N -CBB-1
0
cj-zj
B-1N B-1
Ⅰ
CB XB B-1b
XN XS
XB
非基变量
基变量
也即假设迭代若干步后，基变量为XB,XB在初始表中系数矩阵为B，将B在初始单纯形表中单独列出，这样其初始单纯形表可以表示为如下形式：
0
CB CN
cj-zj
Ⅰ
B N
0 XS b
XS
XB XN
基变量
非基变量
当迭代后基变量为XB时，其在初始单纯形表中系数矩阵为B，则有：
1、单位矩阵Ⅰ B-1 2、基变量XS=b XB=B-1b
3、约束系数矩阵[B，N，Ⅰ] [Ⅰ， B-1N ， B-1 ]
4、如果原表中变量的系数为向量Pj ，迭代后为Pj ′=B-1 Pj
5、检验数变为：CN-CBB-1N 和-CBB-1 （也可根据定义得出）
当迭代若干步后，基变量为XB时，则该步的单纯形表中由XB系数组成的矩阵I，Xs的系数矩阵为B-1（因为单纯形法的迭代是对约束增广矩阵进行的初等行变换）故当基变量为XB 时，新的单纯形表为
CN-CBB-1N -CBB-1
0
cj-zj
B-1N B-1
Ⅰ
CB XB B-1b
XN XS
XB
非基变量
基变量
0
CB CN
cj-zj
Ⅰ
B N
0 XS b
XS
XB XN
基变量
非基变量
注意：1、B在初始单纯形表（称作上表）中找，与迭代后表（称作下表）中基变量对应；B-1在下表中找，与上表中基变量对应；
2、上表和下表也可以理解为迭代计算过程中间某两步的单纯形表；
3、在实际计算题目时，重复的向量没有列出；
4、此问题是研究单纯形法计算的另一种描述形式。只要给出一个新的基，可以直接算出新的单纯形表，而不需要进行逐步迭代，这可以为第二章学习对偶问题和灵敏度分析之用。
CN-CBB-1N -CBB-1
0
cj-zj
B-1N B-1
Ⅰ
CB XB B-1b
XN XS
XB
非基变量
基变量
其中
记
则
例：书 P36 例10，验证上述公式。
上述公式对于灵敏度分析很有帮助 。
例：P48、：此题目不涉及求目标函数值，故可认为此题目目标函数中各变量的系数即是上表中的检验数行的各个数
例、已知下表是某求极大化LP的初始单纯形表和迭代计算中某一步的单纯形表，求出表中a-l的值。
0
1
0
X6
0
0
1
X5
a
-7
6
1
cj - zj
c
k
-1
i
8
X6
b
13
-4
5
20
X5
X4
X3
X2
X1
j
h
11/7
0
0
72/7
cj - zj
g
-5/7
-3/7
0
1
l
e
X2
4/7
f
-2/7
1
0
-1/7
d
X3
X6
X5
X4
X3
X2
X1
a=1,b=-2,c=-1,d=12/7,e=4/7,f=-1/7,g=13/7,h=23/7,i=-50/7,j=1,k=5,l=-12/7。
五、单纯形法小结
1、对给定的LP首先化为标准形，选取或构造一个单位矩阵作为基（找初始可行基：松弛变量法或人工变量法）
2、求初始检验数，列单纯形表。
1）确定进基变量（最大检验数对应的列）
2）确定出基变量（min(bi/aik,aik>0)
做初等行变换。
说明：
如果（有些书中）求MinW，所有j0 ，求得最优解。
§ 应用举例---线性规划数学模型的建立
建立模型是运筹学方法的核心和精髓。
一、建模条件
1 .优化条件：问题所要达到的目标能用线型函数描述，且能够用极值（max 或 min）来表示；
2 .限定条件：达到目标受到一定的限制，且这些限制能够用决策变量的线性等式或线性不等式表示；
3. 选择条件：有多种可选择的方案供决策者选择，以便找出最优方案。
二、建模步骤
1. 确定决策变量：即需要我们作出决策或选择的量。一般情况下，题目问什么就设什么为决策变量；
2 .写出目标函数：即问题所要达到的目标，并明确是max 还是 min；
3 .找出所有限定条件：即决策变量受到的所有的约束。
三、建模案例
线性规划的应用:
（一）配料问题：在原料供应量的限制下如何获取最大利润。
（二）投资问题：从投资项目中选取方案，使投资回报最大。
（三）产品生产计划：合理利用人力、物力、财力等，使获利最大。
（四）劳动力安排：用最少的劳动力来满足工作的需要。
（五）合理利用线材问题：如何下料使用材最少。
（六）运输问题：如何制定调运方案，使总运费最小。
营养配餐问题
例:假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？
解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：
min Z=14x1+6x2 +3x3+2x4
. 1000x1+800x2 +900x3+200x4 3000
50x1+ 60x2 + 20x3+ 10x4 55
400x1+200x2 +300x3+500x4 800
x1，x2 ， x3 ， x4 0
*
*
【例13】混合配料问题
某糖果厂用原料A、B、C 加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C 含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表，问该厂每月生产这三种牌号糖果各多少千克，使该厂获利最大，试建立该问题的线性规划数学模型。
*
*
解：用 i = 1 , 2 , 3 分别代表原料A、B、C，用 j = 1, 2, 3 分别代表甲、乙、丙三种糖果。设 xij 为生产第 j 种糖果使用的第 i 种原料的质量，则问题的数学模型可归结为：
目标函数 maxZ=毛收入－原料成本
X11+x21+x31----甲糖果的重量----甲糖果仅由此三种原料构成
X12+x22+x32-----乙糖果的重量
X13+x23+x33-----丙糖果的重量
X11+x12+x13-----A原料的重量
X21+x22+x23-----B原料的重量
X31+x32+x33-----C原料的重量
x11 ≥(X11+x21+x31) —— x11(糖果甲中原材料A）占整个糖果甲的比例≥60% ；
x31 ≤ (X11+x21+x31) ——x31在糖果甲中原材料 (糖果甲中原材料C）占整个糖果甲的比例C≤20%
*
*
约束条件为
例:某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？
解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑：
对于甲： x11，x12，x13；
对于乙： x21，x22，x23；
对于丙： x31，x32，x33；
对于原料1： x11，x21，x31；
对于原料2： x12，x22，x32；
对于原料3： x13，x23，x33；
目标函数：利润最大，利润 = 收入 - 原料支出 约束条件：规格要求 4 个；供应量限制 3 个。
Maxz = -15x11+25x12+15x13-30x21+10x22-40x31-10x33
x11≥（x11+x12+x13） （原材料1不少于50%）
x12 ≤ （x11+x12+x13）（原材料2不超过25%）
x21 ≥ （x21+x22+x23）≥ 0（原材料1不少于25%）
x22 ≤ （x21+x22+x23 ）≤ 0（原材料2不超过50%）
x11+x21+x31≤ 100 (供应量限制）
x12+x22+x32≤ 100 (供应量限制）
x13+x23+x33≤ 60 (供应量限制）
xij≥0 ,i = 1,2,3; j = 1,2,3
x12 x13 ≥ 0 （原材料1不少于50%）
+ ≤ 0（原材料2不超过25%）
≥ 0 （原材料1不少于25%）
x21+ x22 x23 ≤ 0 （原材料2不超过50%）
x11+x21+x31≤ 100 (供应量限制）
x12+x22+x32≤ 100 (供应量限制）
x13+x23+x33≤ 60 (供应量限制）
xij≥0 ,i = 1,2,3; j = 1,2,3
配方问题
例:养海狸鼠饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。 I、II、 III、 IV、V五种饲料用量分别不超过50、60、50、70、40 KG。现有五种饲料，搭配使用，使费用最小。饲料成分如下表：
200
30
700
营养要求
2
7
4
9
5
1
2
1
2
3
2
1
6
18
I
II
III
IV
V
价格元/KG
Vc
Vb
Va
饲料
设抓取饲料I x1kg;饲料II x2kg;饲料III x3kg……
目标函数：最省钱 minZ=2x1+7x2+4x3+9x4+5x5
约束条件：
营养要求： 3x1+ 2x2+ x3+6x4+ 18x5 ≥700
x1+++2x4+ ≥30
+ x2++2x4+ =200
用量要求： x1 ≤50,x2 ≤60,x3 ≤50,x4 ≤70,x5 ≤40
非负性要求：x1 ≥0,x2 ≥0,x3 ≥0,x4 ≥0,x5 ≥0
*
*
【例14】投资项目的组合问题
兴安公司有一笔 30 万元的资金，考虑今后三年内用于下列项目的投资：
1. 三年内的每年年初均可投入，每年获利为投资额的 20%，其本利可一起用于下一年的投资；
2. 只允许第一年初投入，于第二年年末收回，本利合计为投资额的150%，但此类投资限额15万以内；
3. 允许于第二年初投入，于第三年末收回，本利合计为投资额的160%，但限额投资20万元以内；
4. 允许于第三年初投入，年末收回，可获利40%，但限额为10万元以内；
试为该公司确定一个使第三年末本利总和为最大的投资组合方案。
解：1）确定决策变量：连续投资问题
设xij(i=1，2，3，j =1，2，3，4)表示第i年初投资于j项目（A,B,C,D）的金额。这样我们建立如下决策变量：
考虑到第三年末利润最大
2）目标函数：
由于第三年末收回的本利只包含第三年初项目一的投资、第二年初项目三的投资和第三年初项目四的投资，因此目标函数为：
3）约束条件：
第一年：第一年年初有两个投资项目，应把全部资金投出去，第一年初投资总额为30万，于是：
x11+x12=300000
第二年：第二年初的投资额与第一年末收回的本利总额相同，因此，第二年年初的资金为，可用于投资两个项目，于是：
x21+x23=
第三年：第三年初投资额与第二年末收回的本利总额相同，年初的资金为+，可用于投资两个项目，于是：
x31+x34=+
项目2、3、4的投资限制： x12 ≤150000，x23 ≤200000，x34 ≤100000
*
*
得到该问题的线性规划模型如下：
例：投资项目组合问题
例：某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A ：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。
据测定每万元每次投资的风险指数如下表：
问：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？
b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？
解：1）确定决策变量：连续投资问题
设 xij ( i = 1—5，j = 1、2、3、4)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下决策变量：
A x11 x21 x31 x41 x51
B x12 x22 x32 x42
C x33
D x24
2）约束条件：
第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是：
x11+ x12 = 200
第二年：B次年末才可收回投资故第二年年初的资金为，于是：
x21 + x22+ x24 =
第三年：年初的资金为+，于是 ：
x31 + x32+ x33 = +
第四年：年初的资金为+，于是：
x41 + x42 = +
第五年：年初的资金为+，于是：
x51 = +
B、C、D的投资限制： xi2 ≤ 30 ( i=1，2，3，4 )，x33 ≤ 80，x24 ≤ 100
a)
Max z=+++
+ x12 = 200
x21 + x22+ x24 =
x31 + x32+ x33 = +
x41 + x42 = +
x51 = +
xi2 ≤ 30 ( i =1、2、3、4 )，
x33 ≤ 80，x24 ≤ 100
xij≥0(i=1,2,3,4,5；j=1,2,3,4）
3）目标函数及模型：
b)
Min f = （x11+x21+x31+x41+x51)+
3(x12+x22+x32+x42)+4x33+
. x11+ x12 ≤ 200
x21 + x22+ x24 ≤
x31 + x32+ x33 ≤ +
x41 + x42 ≤ +
x51 ≤ +
xi2 ≤ 30 ( i =1、2、3、4 )，
x33 ≤ 80，x24 ≤ 100
+ + + ≥ 330
xij≥0(i=1,2,3,4,5；j = 1,2,3,4）
*
*
例：投资项目的组合问题。现有资金10万元，在其后3年预对四个项目进行投资。
A：从第1年到第3年每年初可投资，年末回收本利111%；
B：第2年初投资，到第3年末回收本利125%，最大投资3万元；
C：第3年初投资，到年末回收本利120%，最大投资4万元；
D：每年初投资，次年末回收本利的115%。
求：第3年末总资本最大的投资方案。
*
*
解： 假设 表示第i年初投资于第j个项目的资金，i=1,2,3; j=A,B,C,D。
则
i j
A
B
C
D
1
2
3
课后
解：设xij表示公司在i（i=1,2,3,4）个月初签订的租借期为j(j=1,2,3,4)个月的仓库合同中规定的面积，i+j≤5
课后14 :某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过 A、B 两道工序加工。假设有两种规格的设备A1、A2都能完成 A 工序；有三种规格的设备B1、B2、B3能完成 B 工序。Ⅰ可在 A、B的任何规格的设备上加工；Ⅱ 可在任意规格的A设备上加工，但对B工序,只能在B1设备上加工；Ⅲ只能在A2与B2设备上加工；数据如下表。问：为使该厂获得最大利润，应如何制定产品加工方案？
解：设 xij表示在Ai Bj两台设备上加工的产品Ⅰ的数量，i=1，2；j=1，2，3。又设y1为在A1 B1上加工的产品Ⅱ的数量，y2为在A2 B1上加工的产品Ⅱ的数量，x为产品 Ⅲ的数量，利润 = [（销售单价 - 原料单价）× 产品件数]之和 - （每台时的设备费用×设备实际使用的总台时数）之和。
这样我们建立如下的数学模型:
MaxZ= ()(x11+x12+x13+x21+x22+x23)+()(y1+ y2 )+ ()[5(x11+x12+x13)+10 y1] [7(x21+x22+x23)+9y2 +12x][4(x12+x22) +11x]- [6(x11+x21) + 8(y1 + y2 )] [7(x13 +x23)]
5 (x11+x12+x13) +10 y1≤6000 （设备 A1 ）
7(x21+x22+x23) +9y2+12x≤10000 （ 设备 A2 ）
6(x11+x21)+8(y1+ y2 ) ≤ 4000 ( 设备 B1 ）
4(x12+x22)+11x ≤7000 ( 设备 B2 ）
7(x13+x23) ≤ 4000 （ 设备 B3 ）
以上变量均非负
例:明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？
解：设 x1 ,x2 ,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4, x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。 求 xi 的利润:利润 = 售价 - 各成本之和可得到 xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。
这样我们建立如下数学模型：
目标函数: MaxZ= 15x1+10x2+7x3+13x4+9x5
约束条件：
. 5x1+10x2+7x3 ≤8000
6x1+ 4x2+8x3+6x4+4x5 ≤12000
3x1+ 2x2+2x3+3x4+2x5 ≤10000
x1,x2,x3,x4,x5 ≥ 0
课后18:某工厂要做100套钢架，每套有长为 m, , 的圆钢各一根。已知原料每根长 m，问：应如何下料，可使所用原料最省？
合理利用线材问题（套裁下料问题）
解:考虑下列各种下料方案（按一种逻辑顺序给出）
把各种下料方案按剩余料头从小到大顺序列出
假设x1,x2,x3,x4,x5 分别为上面前5种方案下料的原材料根数。我们建立如下的数学模型。
目标函数：
MinZ=0x1++++
约束条件：
. x1+2x2 + x4 = 100
2x3 + 2x4 + x5 = 100
3x1+ x2 +2x3 +3x5 = 100
x1,x2,x3,x4,x5 ≥ 0
52
B型驳船
34
A型驳船
30
拖 轮
船只数
船只种类
400
2
200
1
合同货运量
航线号
20
27
4
—
1
4
40
72
4
2
2
3
2
20
36
4
—
1
2
25
36
—
2
1
1
1
B型
驳船
A型
驳船
拖轮
货运量
（千吨）
货运成本
（千元／队）
编队形式
船队
类型
航线号
问：应如何编队，才能既完成合同任务，又使总货运成本为最小？
例：某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：
解：设：xj为第 j 号类型船队的队数（j = 1，2，3，4），z 为总货运成本
则： min z = 36x1 + 36x2 + 72x3 + 27x4
x1 + x2 + 2x3 + x4 ≤ 30
2x1 + 2x3 ≤34
4x2 + 4x3 + 4x4 ≤52
25x1 + 20x2 ＝200
40x3 + 20x4 ＝400
xj ≥ 0 j = 1,2,3,4
用单纯形法可求得：x1 = 8，x2 = 0 ，x3 = 7， x4 = 6
最优值：z = 954
即：四种船队类型的队数分别是8、0、7、6，
此时可使总货运成本为最小，为954千元。
【例】 某工厂生产A、B两种产品，有关资料如下表
解：设总利润为z，A、B产品销量为x1、x2，产品C的销售量为x3，报废量为x4，则：
max z = 4 x1+10 x2 +3 x3－2 x4
2 x1 + 3x2 ≤ 12
3x1 + 4x2 ≤ 24
－4x2 +x3 + x4 = 0
x3 ≤ 5
x1、x2 、x3 、x4≥0
【例】：某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：
人力资源分配的问题
设司机和乘务人员分别在各时间段一开始时上班，并连续工作8h，问该公交线路怎样安排机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?
解：设 xi 表示第i班次时开始上班的司机和乘务人
员数,这样我们建立如下的数学模型。
目标函数：minZ= x1 + x2 + x3 + x4 + x5 + x6
约束条件：. x1 + x6 ≥ 60
x1 + x2 ≥ 70
x2 + x3 ≥ 60
x3 + x4 ≥ 50
x4 + x5 ≥ 20
x5 + x6 ≥ 30
x1,x2,x3,x4,x5,x6 ≥ 0
第一章知识点小结
1、化为标准形；
2、理解LP的几个概念：基、基解、基可行解、可行基；
3、图解法求解；
4、单纯形法计算的步骤；
5、大M法与两阶段法的计算方法；
6、解的几种情况的判别；
7、单纯形法计算的向量矩阵描述；
8、建立模型。（掌握一般方法）
第一章作业：
P47、（a）；
P48、（a）要求：（1）化为标准形式；（2）分别列出用大M法求解时的初始单纯形表和两阶段法求解时第一阶段的初始单纯形表。
P48、 MAX Z=2X1+3X2- 5X3
X1 + X2 + X3 =7
2X1 - 5X2 + X3 10
X1 0, X2 0 , X3 0
P49、
自己练习（不上交）：、、、、、
*
*
*
*
*
*
*
*
*
*
*
*
