线性规划问题的几何意义

第三章线性规划的解法§3.1重点、难点提要一、线性规划问题的图解法及几何意义1．图解法。

线性规划问题采用在平面上作图的方法求解，这种方法称为图解法。

图解法具有简单、直观、容易理解的特点，而且从几何的角度说明了线性规划方法的思路，所以，图解法还有助于了解一般线性规划问题的实质和求解的原理。

（1）图解法适用于求解只有两个或三个变量的线性规划问题，求解的具体步骤为：1）在平面上建立直角坐标系；2）图示约束条件，找出可行域。

具体做法是画出所有约束方程(约束条件取等式)对应的直线，用原点判定直线的哪一边符合约束条件，从而找出所有约束条件都同时满足的公共平面区域，即得可行域。

求出约束直线之间，以及约束直线与坐标轴的所有交点，即可行域的所有顶点；3）图示目标函数直线。

给定目标函数Z一个特定的值k，画出相应的目标函数等值线；4）将目标函数直线沿其法线方向向可行域边界平移，直至与可行域边界第一次相切为止，这个切点就是最优点。

具体地，当k值发生变化时，等值线将平行移动。

对于目标函数最大化问题，找出目标函数值增加的方向(即坐标系纵轴值增大的方向)，等值线平行上移到可行域(阴影部分)的临界点，最终交点就是取得目标函数最大值的最优解；对于目标函数最小化问题，找出目标函数值减少的方向(即坐标系纵轴值减少的方向)，等值线平行下移到可行域(阴影部分)的临界点，最终交点就是取得目标函数最小值的最优解。

（2）线性规划问题的几种可能结果：1）有唯一最优解；2）有无穷多个最优解；3）无最优解(无解或只有无界解)。

2．重要结论。

（1）线性规划的可行域为一个凸集，每一个可行解对应该凸集中的一个点；（2）每一个基可行解对应可行域的一个顶点。

若可行解集非空，则必有顶点存在，从而，有可行解必有基可行解。

（3）一个基可行解对应约束方程组系数矩阵中一组线性无关的列向量，对于n 个变量m 个约束方程的线性规划问题，基可行解的个数不会超过!!()!m n n m n m C =-。

借助目标函数的几何意义解线性规划问题
线性规划问题是企业决策分析中常见的问题，它利用目标函数的几何意义来求解，目标函数的几何意义就是通过特定的函数曲线使得所求的最优解能够达到的最佳的位置及形状，以达到实现优化的最大化或者最小化的目的。

下面以做公司生产原料决策为例，讲解目标函数几何意义。

企业要求以X1和X2为两种原料采购，采购成本分别为1元和2元，通过原材料加工生产制成品，售价为3元每台。

线性规划问题就是在一定的条件下，如何选择X1和X2的采购量，用更少的采购成本来达到最高的利润。

假设有约束条件，比如最多只能采购3个X1和2个X2，那么，目标函数的几何意义表示的是把X1和X2的采购量作为变量，利润作为函数的函数曲线，在X1和X2的采购量满足约束条件的前提下，把曲线微调，把利润最大化，称为最佳曲线。

因此，结合目标函数几何意义，最终企业可以从曲线最高点处，获得最优原材料采购量，比如最高点处极大值为9，则最优解是，X1=3，X2=2，则最高利润为27元。

线性规划问题可以借助目标函数的几何意义来解决，也就是说，解决线性规划问题的问主要就是把函数曲线的极大值调整到可以实现最大化或最小化的结果位置。

从而可以有效的获得最优解。

第一节 线性规划问题及其数学模型
可加性假定：每个决策变量对目标函数和约
束方程的影响是独立于其他变量的，目标函 数值是每个决策变量对目标函数贡献的总和 连续性假定：线性规划问题中的决策变量应 取连续值。 确定性假定：线性规划问题中的所有参数都 是确定的参数。线性规划问题不包含随机因 素。
约 束 方 程
约束条件
变量约束
第一节 线性规划问题及其数学模型
线性规划问题隐含的假定： 比例性假定 可加性假定 连续性假定 确定性假定
比例性假定：决策变量变化引起的目标函数
的改变量和决策变量的改变量成比例，同样， 每个决策变量的变化引起约束方程左端值的 改变量和该变量的改变量成比例
≥0
=
≥0
第一节 线性规划问题及其数学模型
标准型的简缩形式
max Z
c x
j j 1
n
j
s .t
n aij x j bi , i 1,2 , , m j 1 x j 0 , i 1,2 , , m

第一节 线性规划问题及其数学模型
或
松弛变量
a i 1 x 1 a i 2 x 2 a in x n bi
a i 1 x1 a i 2 x 2 a in x n x p bi , x p 0
剩余变量
练习
例:将下列线性规划问题划为标准形式： min Z = x1+3x2
s.t.
6x1+7x28 -x1+3x2-6 x1-x2=3 x10
可行域无界
x1+2x2 10 x2 0 x1
可行域无界
x2
x1 0

引言
对线性规划贡献最大的是美国数学家G.B.Dantig(丹捷格)，他 在1947年提出了求解线性规划的单纯形法（Simple Method），并同时给出了许多很有价值的理论，为线性规划 奠定了理论基础。在1953年，丹捷格又提出了改进单纯形法， 1954年Lemke(兰母凯)提出了对偶单纯形法（dual simplex method）。 在1976年， R. G. Bland 提出避免出现循环的方法后，使线 性规划的理论更加完善。但在1972年，V. Klee和G .Minmty 构造了一个例子，发现单纯形法的迭代次数是指数次运算，不 是好方法——并不是多项式算法（多项式算法被认为是好算 法），这对单纯形法提出了挑战。
B2
B3
70
50 60
A2
60 110 160
[解] 设xij 表示 Ai运往Bj的运量（万块） minS=50x11+60x12+70x13+60x21+110x22+160x23 S.t. x11+x12+x13=23 x21+x22+x23=27 x11+x21=17 x12+x22=18 x13+x23=15 xij≥0, i=1,2、j=1,2,3
2.线性规划问题的几何意义
2.1基本概念 凸集：设k为n维欧氏空间的一点集，任取X,Y∈K,若 连接X,Y的线段仍属于K,则称K为凸集。即任取α ,0<α <1 α X+(1-α )Y∈K 称K为凸集。 顶点（极点）：设K是凸集，X∈K,若X不能用不同的两
点 X(1) ∈K,X2) ∈K 的线性组合表示为 X=α X(1)+(1-α )X(2) (0<α <1) 则称X为极点。