OSYHY-1-2线性规划解的概念及性质

1-2线性规划问题

解的概念和性质

LP的标准型目标函数约定是极大化Max;

约束条件均用等式表示;

决策变量限于取非负值;

右端常数均为非负值;LP问题的标准形其中:一、LP问题的各种解

可行解：满足约束条件和非负条件的决策变量的一组取值。最优解：使目标函数达到最优值的可行解。基本解：设AX=b是含n个决策变量、

m个约束条件的LP的约束方程组，B是LP问题的一个基，若令不与B的列相应的n-m个分量（非基变量）都等于零，所得的方程组的解称为方程组AX=b关于基B的基本解，简称为LP的基本解。

4.基本可行解（对应的基为可行基）：满足非负条件的基本解。

5.基本最优解（对应的基为最优基）：使目标函数达到最优值的基本可行解。最优解基本最优解用画图、模型制作、三维动画等方法清楚地显示其可行解、基本解、基本可行解。进一步具体计算出这些解来，说明它们之间的关系。课后讨论1：研究约束集合二、线性规划的图解法

－－－解的几何表示

1．什麽是图解法？线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。求解的思路是：先将约束条件加以图解，求得满足约束条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。2.图解法举例

实施图解法，以求出最优生产计划（最优解）。

例1－1maxZ=2x1+3x2s.t.

由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可以进行图解了。

第一步：建立平面直角坐标系。用x1轴表示产品A的产量，用x2轴表示产品B的产量。

第二步：对约束条件加以图解。第三步：画出目标函数等值线，结合目标函数的要求求出最优解－－最优生产方案。

0123456789x1

54321x2（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）将例1-1稍作改动形成案例1，仍使用图解法来求解。

（案例1）某工厂生产A、B、C三种产品，每吨的利润分别为2000元、3000元、1000元，生产单位产品所需的工时及原材料如表1－2所示。若供应的原材料每天不超过3吨，所能利用的劳动力总工时是固定的，应如何制定日生产计划，使三种产品的总利润最大？

设三种产品的产量分别是x1、x2、x3吨，由于有三个决策变量，用图解法求解下面的线性规划时，必须首先建立空间直角坐标系。

B点对应着该线性规划的最优解：

X*=(1,2,0)T

即x1=1（产品A的产量）

x2=2（产品B的产量）

x3=0（产品C的产量）此时可得产品最大总利润为：

Zmax=8

由右图可知，可行域为凸五面体OABCDE,粗虚线所围平面为目标函数等值面，平移目标函数等值面得最优点为B点。

例1-1和案例1所描述的都是有唯一最优解且可行域是一个非空有界区域的情况。实际上，可行域不仅仅只有这一种可能，解的情况也是各种各样的。

讨论用图解法求解线性规划的各种可能的结果

无穷多个最优解

该线性规划的可行域为上图中四边形OAED（即阴影区），虚线为目标函数等值线，箭头为目标函数值递增的方向。沿着箭头的方向平移目标函数等值线，发现平移的最终结果是目标函数等值线将与可行域的一条边界－－线段AE重合，这个结果表明，该线性规划有无穷多个最优解－－线段AE上的所有点都是最优点，它们都使目标函数取得相同的最大值Zmax=3。唯一最优解

例1-3将例1-1中目标要求改为极小化，目标函数和约束条件均不变，则可行域与例1-1相同，目标函数等值线也完全相同，只是在求最优解时，应沿着与箭头相反的方向平移目标函数等值线，求得的结果是有唯一最优解x1=0,x2=0,对应着图1-6中的坐标原点。无界解

本例中的可行域是一个无界区域，如图中阴影区所示。虚线为目函数等值线，沿着箭头所指的方向平移可以使目标函数值无限制地增大，因此找不到最优解。这种情况通常称为无“有限最优解”或“最优解无界”。如果一个实际问题抽象成像例1－4这样的线性规划模型，比如是一个生产计划问题，其经济含义就是某些资源是无限的，产品的产量可以无限大，解释不合理。此时应重新检查和修改模型，否则就没有实际意义。注意，对于无界可行域的情况，也可能有唯一最优解或无穷多个最优解。比如目标要求为minZ=x1+2x2或maxZ=－2x1+x2，而约束条件不变的例子。x1x2

综上，用图解法求解线性规划时，各种求解结果与各种类型的可行域之间的对应关系可以用下图加以描述：

课堂练习1-2：用图解法求解下面的线性规划依次完成：画约束条件1；画约束条件2；画约束条件3；标明可行域；目标函数等值线；说明如何得到最优解，算出相应的目标函数最优值。

4、用图解法求解线性规划时需特别注意：

第一、线性规划的可行域一定是凸多边形或凸多面体，所以下图中

所示阴影区不可能是某个线性规划的可行域，而

所示阴影区则有可能。第二、目标函数

Z=ax1+bx2的值递增的方向与系数a、b有关

下图表示目标函数值递增方向与其系数a、b的关系，其中箭头所指为目标函数值递增的方向。图解法小结

使用条件：仅有两个至多不超过三个决策变量的线性规划。基本步骤：第一步－－建立平面直角坐标系；第二步－－根据约束条件和非负条件画出可行域。第三步－－作出目标函数等值线（至少两条），结合目标函数优化要求，平移目标函数等值线求出最优解。图解法的优缺点：简单、直观但有局限性。

第一次作业——P69习题1：1-2；P701-3

三、基本可行解的几何意义1、

讨论课堂练习1-2（1）观察图解法求解图，其中点I、H、G均在第一象限，它们是基本解，但不是基本可行解，这与基本可行解非负性有无矛盾？（2）如何求得基本解？第一步

模型标准化；第二步

按照基本解的定义①

找基（非退化3阶方阵）——

多少个？不超过，为什麽？怎麽找？②

确定基变量和非基变量；③

令非基变量为0，解出基变量；④基变量和相应非基变量搭配构成基本解；求解结果：

H(6,4,-6,0,0)T,C(3,1,0,3,0)T,B(2,2,0,0,2)T,D(2,0,2,4,0)T,F(-2,0,6,0,4)T,I(4,0,0,6,-2)T,E(0,-2,6,6,0)T,A(0,1,3,0,3)T,G(0,4,0,-8,6)T,O(0,0,4,2,2)T2、结论：

(1)基本解对应所有可行域边界延长线、坐标轴之间的交点；

(2)基本可行解对应可行域的顶点。

1、基本概念：

凸集——设K是n维欧氏空间的一个点集，若任意两点X（1）∈K，X（2）∈K的连线上的一切点：

αX（1）+（1-α）X（2）∈

K

（0<α<1），则称K为凸集。

四、线性规划解的性质

凸组合——设X（1），X（2），…，X（k）是n维欧氏空间中的K个点，若存在k个数μ1，μ2，…，μk,满足

0≤μi≤1,i=1,2,…,k；，则称X=μ1X（1）+μ2X（2）+…+μkX(k)为X（1）,

，X（2），…，X（k）的凸组合。

顶点——设K是凸集，XK；若X不能用

X（1）

K，X（2）

K的线性组合表示，即

X≠αX（1）+（1-α）X（2）（0<α<1）则称X为K的一个顶点（也称为极点或角点）。

从直观上讲，凸集没有凹入部分，其内部没有空洞。上图中的(a)(d)(e)是凸集，(b)(c)不是凸集。下图中的(a)(b)是凸集，(c)不是凸集。2、线性规划问题解的性质定理：

定理1-1

线性规划问题的可行解集（即可行域）是凸集。

证明思路：根据凸集定义，采用直接法证明；具体步骤：①从D中任取两个不同的点，应满足可行解定义中相应的条件；②证明X=αX(1)+(1-α)X(2)∈D(利用①，证明X满足凸集定义中相应的条件)

定理1-2

线性规划几何理论基本定理若，则X是D的一个顶点的充分必要条件是X为线性规划的基本可行解。证明思路：定理1-2是X是D的一个顶点<=>X为LP的基本可行解;

引理是X为LP的基本可行解<=>X的正分量所对应的系数列向量线性无关;从而将问题转化为X是D的一个顶点<=>

X的正分量所对应的系数列向量线性无关定理1-3

若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值。证明思路：首先可行域非空有界就肯定有最优解本定理要证明的是设在非顶点X处取得最优值，则存在顶点X（1）和X（2）也取得相同的最优值。定理1-4

若目标函数在k个点处达到最优值（k≥2）,则