线性规划问题

点的连线上。不难证明，多胞形必为凸集。同样也不难证
明，图5.1中R的顶点均为R的极点（R 也没有其他的极点）
三、基本解与基本可行解 给m 定<n一秩个r标(A准)=形m。式取的出线A性的规m个划线问性题无（关5的.3列），，这其些中列A=构(a成ij)mAx的n ，一
个m 阶非奇异子矩阵B，称B为A的一个基矩阵。 A的其余n－m列构成一个m×(n－m)矩阵N。称对应B的列的变量 为记基为x变N 量。（共有m个），记它们为xB 。其余变量称为非基变量，
线性规划问题
在人们的生产实践中，经常会遇到如何利用现有资源 来安排生产以取得最大经济效益的问题，此类问题构 成了运筹学的一个重要分支——数学规划，而线性规 划（Linear Programming, 简记LP）则是数学规划的 一个重要部分。自从1947年G·B·Dantzig提出求解线性 规划的单纯形方法以来，线性规划在理论上日趋成 熟 ，在应用上日趋广泛，已成为现代管理中经常采 用的基本方法之一。
量yi，将不等式化为ai1x1+…+ainxn+yi = bi，且yi≥0。 若第i个约束为ai1x1+…+ainxn≥bi，可引入剩余量yi，将 不等式化为ai1x1+…+ainxn－ yi = bi，且yi≥0。
（3）若xi为自变量，则可令 xi xi xi,其中 xi 、xi ≥0
例如
例5.1并非标准形式，其标准形式为
对线性规划（5.3），取定一个基矩阵B，令非基变量xN =0，
合称为问题的可行域，记为R。对于每一固定的值z，使目标 函数值等于z的点构成的直线称为目标函数等位线，当z变动
时，我们得到一族平行直线（图5.1）。
图5.1
对于例5.1，显然等位线越趋 于右上方，其上的点具有越 大的目标函数值。不难看出， 本例的最优解为x*=(2,6)T ，最 优目标值z*=26 。
min ― 4x1―3x2 s.t 2x1 + x2 + x3 = 10 x1 + x2 + x4 = 8 x2 + x5 = 7 x1 , x2 , x3 , x4, x5≥0
三、线性规划的图解法
为了了解线性规划问题的特征并导出求解它的单纯形法，我 们先应用图解法来求解例5.1。满足线性规划所有约束条件 的点称为问题的可行点（或可行解），所有可行点构成的集
记为max；反之，当希望使目标函数最小时，记为min。（5.1）
中的几个不等式是问题的约束条件，记为S.t（即Subject
to）。由于（5.1）式中的目标函数及约束条件均为
线性函数，故被称为线性规划问题。总之，线性规划
问题是在一组线性约束条件的限止下，求一线性目标
函数最大或最小的问题。
二、线性规划的标准形式
例1的数学模型：设该厂生产x1台甲机床和x2台乙机床时总
利润最大，则 x 、x 应满足
max 4x1 + 23x
s.t
2x1 + x
2
≤10
1
2
x + x ≤8
(5.1)
1
2
x 2
≤7
x 1
,
x 2
≥0
（5.1）式中4x1 + 3x2表示生产x1台甲机床和x2台乙机床的
总利润，被称为问题的目标函数，当希望使目标函数最大时，
min z = CT x
S.t Ax = b
x≥0
（5.3）
其中C 和x 为n 维列向量，b为m 维列
i=1j,1 …,m x ≥0,j=1,…,n
j
向量，b≥0，A为m×n矩阵,m<n且
rank(A)=m。
或更简洁地
如果根据实际问题建立起来的线性规划问题并非标准形
式，可以将它如下化为标准形式：
（1）若目标函数为max z =CT x，可将它化为min－z =－CT x （2）若第i个约束为ai1x1+…+ainxn≤bi，可增加一个松驰变
从上面的图解过程可以看出并不难证明以下断言：
（1）可行域R可能会出现多种情况。R可能是空集也可能是非 空集合，当R非空时，它必定是若干个半平面的交集（ 除非 遇到空间维数的退化）。R既可能是有界区域，也可能是无界 区域。（2）在R非空时，线性规划既可以存在有限最优解，
也可以不存在有限最优解（其目标函数值无界）。（3）若线 性规划存在有限最优解，则必可找到具有最优目标函数值的
一.线性规划的实例与定义
例5.1 某机床厂生产甲、乙两种机床，每台销售后的利 润分别为4000元与3000元。生产甲机床需用A、B机器加工， 加工时间分别为每台 2小时和1小时；生产乙机床需用A、 B、C三种机器加工，加工时间为每台各一小时。若每天可 用于加工的机器时数分别为A机器10小时、B机器8小时和C 机器7小时，问该厂应生产甲、乙机床各多少台，才能使 总利润最大？
为此，我Leabharlann Baidu将采
定义5.2 设R为n维空用间另中一的途一径个来凸定集，R中的点x被称为R的 一个极点，若不存在x1 、义x它2 。∈ R及λ∈(0, 1)，使得
x =λ x1 +（1－λ）x2 。
定义5.1说明凸集中任意两点的连线必在此凸集中；而定义
5.2说明，若x是凸集R的一个极点，则x不能位于R中任意两
可行域R的“顶点”。
上述论断可以推广到一般的线性规划问题，区别只在于空间
的维数。在一般的n维空间中，满足一线性等式aix=bi的点集
被称为一个超平面，而满足一线性不等式aix≤bi （或
aix≥bi ）的点集被称为一个半空间（其中ai为一n维行向量，
bi为一实数）。若干个半空间的交集被称为多胞形，有界的
多胞形又被称为多面体。易见，线性规划的可行域R必为多胞 形（为统一起见，空集Φ也被视为多胞形）。
在一般n维空间中，要直接得出多胞形“顶点”概念还有一些
困难。在图5.1中顶点可以看成为边界直线的交点，但这一
几何概念的推广在一般n维空间中的几何意义并不十分直观。
定义5.1 称n 维空间中的区域R为一凸集，若x1 , x2 ∈ R及 λ∈(0, 1)，有λ x1 +（1－λ）x2 ∈ R。
线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件 可以是不等式也可以是等式，变量可以有非负要求也可以没有非负要 求（称这样的变量为自由变量）。为了避免这种由于形式多样性而带 来的不便，规定线性规划的标准形式为
例5.2
利用矩阵与向量记为
min
S.t
n
n j 1
c
j
x
j
aij x j bi