x1
0 1 0 0
x2
1 0 0 0
x3
0 0 1 0
x4
3/160
x5
-1/120 1/60 1/2 -1/6
bi
3/4 7/2
i
数学既不严峻，也不遥远，她和 几乎所有的人类活动有关，还让每个 对她感兴趣的人受益。 ― R.C.Buck 数学是理解世界及其发展的一 把主要钥匙。 ― 里约热内卢宣言
数学实验
合金工厂的生产规划
上海交通大学数学科学学院
实际问题1
某合金工厂生产甲、乙两种合金，生产每吨 甲种合金需用A元素20 kg、 B元素40kg 和C元素 90 kg，而生产每吨乙种合金需用A元素100 kg、 B元素80 kg和C元素60 kg. 由于A、B、C三种元素都是原料市场上紧缺
20x1 100x2 200 40x 80x 200 1 2 90x1 60x2 360 x1 0, x2 0
线性规划 问题
求最优解
图解法（回到问题1）
二元一次方程 a1x1+a2x2 =b 代表x1 x2平面 上的一条直线, 而二元一次不等式a1x1+a2x2 b 则代表了以此直线为界的半平面 a1 x1+a2 x2 b
x2 p
Q
30x1+40x2= u
从图看出最 优解应为R点 R
O
S
x1
问题的解答
最优解在R点,由R是直线40x1+ 80x2= 200与 直线90x1+ 60x2= 360的交点,可得最优解为x1=3.5, x2=0.75,此时有最大值为u=135. 说明安排月生产 甲、乙种合金分别为3.5 t、0.75t，才能获得最大 利润135万元.
末一行
■
从末一行非基变正系数)，最小者2，该行对应的x3 成 非基，交叉位的系数100 称主元;
■
作初等变换主元变成1,这列其他系数变成0
这样得到的单纯形表(矩阵)为
x2 x4 x5 1/5 24 78 22
■
x1
x2
1 0 0 0
1/100 -4/5 -3/5 -2/3
单纯形法的步骤 1.化标准型 (1)把问题变为求在约束下的极小,(2)引进新变量, 将约束中的不等式化为等式(除了变量xi非负)
v u，增加 x3 , x4 , x5
约束条件

求 min v min (30x1 40x2 0x3 0x4 0x5 )
200 20x1 100x2 x3 40x 80x x4 200 1 2 x5 360 90x1 60x2 i 1, 2, 3, 4, 5 xi 0,
初等变换：先选末行xi系数最大的列 算θ(最小正) 定主元
20 100 1 0 0 200 40 80 0 1 0 200 90 60 0 0 1 360 30 40 0 0 0 0
1 / 5 24 78 22
1 0 0 0
x3
0 1 0 0
x4
0 0 1 0
x5
bi i 2 10 40 5/3 240 120/39 -80
现在x2, x4, x5成为基,这次末一行正系数最大者 再看i=bi/(x1的正系数）其最小者5/3，所在行
是22，x1成新基;
■
对应 x4成非基,24 成为主元
■
再做初等变换主元变成1，这列其他系数变0
货品,工厂每月所能得到的这些元素的供应量分别 为200kg、200kg和360kg. 工厂生产每吨甲种合金
利润为30万元，生产每吨乙种合金利润为40万元.
试问：应如何安排生产，才能获得最大利润？
数学模型
设每月生产甲种合金 x1t，乙种合金 x2 t , 利润为 u万元, 那么 u= 30 x1+40 x2 求何时有 max u= max (30 x1+40 x2) x1, x2 满足约束条件
a1x1+a2x2 =b
这问题中约束条件意味着五个半平面的交
集. 它是一个包含边界的凸多边形 OPQRS
x2 线性规划的 容许集
p
Q R
O
S
x1
将 u 视作参数，则30x1+40x2= u 代表一条直线，随着u 的增减，直线向右上或左下方平移. 若直线经过容许集的某 顶点时u再增将使直线离开容许集，则此临界状态直线所对应 的u就是所求的最大值，此顶点的坐标就是问题的最优解
1 / 100 4/5 3/ 5 2/5
0 1 0 0
0 2 0 40 1 240 0 80
0 1 0 0
1 1 / 60 1 / 120 0 1 / 30 1 / 24 0 2 13 / 4 0 1 / 3 11 / 12
0 5/ 3 0 5/ 3 1 110 0 350 / 3
2. 单纯形表 利用矩阵的初等变换来实现单纯形法 ■ 选系数线性无关三个变量(x3,x4,x5 )为基; 用约束条件将目标函数写成仅含非基变量，列表 x1 x2 x3 x4 x5 bi i
x3 x4 x5 20 40 90 30 100 80 60 40 1 0 0 0 0 1 0 0 0 0 1 0 200 200 360 0 2 2.5 6
0 1 0 0
1 0 0 0
0 0 1 0
3 / 160 1 / 120 3 / 40 1 / 80 1 / 60 7 / 2 13 / 8 1 / 2 55 3 / 8 1 / 6 135
直至末行非基变量系数均负，对应表为
x2 x1 x3
图解法的局限
画图并不方便，可以不画图而求出容许集所有 的顶点，再将目标函数在这些顶点上的值加以比 较来求出最优解.但在约束条件多或多变量时，也 是难以做到的
单纯形法
基本思路是：线性规划(通常是求最小值的 的形式)若有最优解，其必定在容许集(在相应的 几何空间中是一个凸多面体)的顶点达到，故 从某一个顶点出发，沿着凸多面体的棱向另一 顶点迭代，使得目标函 数的值下降,经过有限次 迭代,将达到最优解点.