DOC《§3》

§3.

6 典型例题分析 题型I 线性规划问题解的概念与理论 例3-1 找出如下线性规划问题的所有的基本解,指出哪些是基本可行解. 解: , 因为 , 所以,构成基.令, 得基本解:. 同理可得: 其中为基本可行解. 例3-2 线性规划问题是否可算作条件极值问题,它与微积分中讲的条件极值问题有何不同? 解: 线性规划问题也可以看成是条件极值问题,即要在满足所有约束的条件下,求目标函数的极值.它与微积分中讲到的条件极值是不同的:(I)它的约束条件中可以有不等式约束,而后者的限制条件都是等式;

(2)它的约束条件的个数一般地都多于变量的个数,而后者恰恰相反;

(3)它的目标函数与约束条件都是线性的,而后者不必如此. 例3-3 是线性规划问题 的最优解.上述问题中若目标函数中的换成后,则问题的最优解变为,求证:. 证明: 、在目标函数的系数变化之前之后都是问题的可行解,故有 , 即(1) 同理,即有 (2) (1)+(2)则有 题型II 用图解法求解线性规划问题 图解法仅适用于两个变量的线性规划问题,求解时按原来题目对目标函数的优化要求去求解即可.不必将求极小值化为求极大值. 三个变量的线性规划问题用图解法求解时,可行域是三维空间的多面体,很难用平面上的图形画得清晰准确,目标函数对应的是三维空间中的平面,难以通过平面上画出的立体图形求出最优解.所以,从理论上讲,三个变量的线性规划也有图解法,但实际上不可行.多于三个变量的线性规划涉及到在高于三维的向量空间中求解优化问题,而三维以上的空间已无直观的几何意义,故不存在相应的图解法 例3-4 设线性规划问题为 用图解法找出最优解;

若目标函数变为,最优解如何变化? 若第三个约束变为,最优解又将如何变化? 解:(1) 在第一象限内分别画出约束边界方程对应的直线,以及两条坐标轴: 上述五条直线构成该线性规划问题的可行域为:OABCD. 如图3-1所示,可行域的五个顶点对应的坐标分别为:O(0,0);

A(0,10);

B(6,6);

C(8,4);

D(10,0). 分别画出目标函数的等值线: 由图3-1可知,目标函数等值线在顶点B(6,6)处取得最大值,最大值为z=54.即当时,目标函数值的最大值为. (2)当目标函数变化为时,可行域不变,仍然是以OABCD为顶点围成的区域.由于斜率由-4/5增大为-4/7,所以,最优解所在的顶点为A(0,10),此时目标函数取得最大值.即当时,目标函数的最大值为.如图3-2所示. (3)当第三个约束条件变化为时,可行域已经改变,是以O(0,0);

A(0,10);

B(3.75,7.5);

C(7.5,0) 为顶点围成的区域.从图2-3可知,目标函数等值线在顶点B(3.75,7.5) 取得最大值,最大值为z=52.5.即当时,目标函数的最大值为. 图3-1 图3-2 图3-3 例3-5 用图解法求解下列线性规划问题 解: (1)以和为坐标轴建立平面直角坐标系.一般以为横坐标,为纵坐标. (2)确定决策变量的可行域. 约束条件中,表明所求的可行解都在第I象限内或坐标轴的正方向部分(包括原点). 确定约束所限定的区域.画出直线,容易判断,其左下方的点满足约束 (比如,取原点(0,0)代入显然不等式成立).考虑到,则区域OAB为所确定区域.如图2-4所示. 确定约束所限定的区域.先画出直线,容易判断,其右上方的点满足约束.考虑到,及,则区域ACBD为所确定区域,如图2-5所示. 确定约束所限定的区域.先画出直线,容易判断其下方的点满足约束,考虑到,及,则区域FCDBE为所确定区域.如图3-6所示. 因为区域FCDBE所包含的点满足所有的约束条件,所以它就是决策变量的可行域. 图3-4 图3-5 图3-6 (3)画出目标函数等值线,确定优化方向. 目标函数为,可改写为,其中Z是待定的值,如果把它看作是参数,则目标函数是斜率为2,在纵轴上的截距为Z的平行直线族. 若取Z为一确定的值,如令Z=6,则6=,即,就是上述平行直线族中的一条确定直线,如图3-7所示.显然,直线上的所有点都使得目标函数的值等于6,因此称=6是Z=6时的等值线. 同样可画出目标函数的另一条等值线,如令z=12,则12=,即就是上述平行直线族中的另一条等值线. 由图2-7可以看出Z值取得越大,目标函数等值线的位置越是沿着其法线方向向右上方平行移动,这就是目标函数等值线的优化方向. (4)确定最优解. 最优解首先必须是可行解,因此只能在可行域中去找,其次还要使目标函数值达到最优.因此在可行域FCDBE中寻找这样的点,使Z值达到最大.沿着目标函数等值线的优化方向尽量平移等值线,直到它与可行域还有最后的公共部分(一点或一条线段)为止,这个公共部分就是等值线的最佳位置,最佳位置上的点就是要求的最优解.如图2-7所示,当等值线平移到E点时,如果继续向上移,就离开了可行域.因为目标函数的斜率与约束方程(1)的斜率相同,因此E点以及约束方程(1)上EB段的任何一点都是使目标函数值达到最大值的点. 图3-7 E点是直线和的交点,联立这两个方程求解得E点的坐标为E(4,2),即=(4,2),最优值为max Z=24+2=10. 同理,由于B点坐标为B(5,0),即=(5,0),最优值为max Z=25+0=10. 因此,线性规划问题的最优解可表示为: 要点:这是一个有无穷最优解的线性规划问题.,用图解法求解线性规划问题的关键有三个:第一是正确地确定决策变量的可行域,第二是确定目标函数的等值线及其优化方向,第三是在可行域范围内确定最优解的值. 题型III 用单纯形法求解线性规划问题 1.用单纯形法求解线性规划问题时,先要将问题化为标准形式 其中A是行满秩的m n的矩阵,而且m