線性规划问题的最优解.docVIP

线性规划问题的最优解 引言 线性规划是运筹学的一个基本分支，其应用极其广泛，其作用以为越来越多的人所重视。线性规划主要就实际问题抽象成数学形式，即求一组变量的值，在满足一定的约束条件下，是某个目标达到最小或最大，而这些约束条件用可以用一组线性不等式或线性方程来表示。而求得目标函数的最优解尤为重要，本文就线性规划问题的最优解求解方法作出阐述，并举出实例加以强化，同时也指出了线性规划问题应用于生产与运作管理的重要性。 1.线性规划问题的最优解探讨 1.1线性规划问题的提出 考虑下面的线性规划问题的标准型： 目标函数： (1) 约束条件： (2) 其中，,,,阶矩阵。设B是A中m个线性无关的列向量构成的一个基， 阶矩阵，这样将矩阵A分成两个部分，即A=,X=,C=,,为基B对应的非基变量和系数，,为N对应的非基变量和系数，这样将线性规划问题改写为： minZ (3) 约束条件： (4) 经过矩阵变换，得出关于基B的标准型如下： +(-N) (5) 约束条件： (6) 将（5）（6）展开为： +() (7) 约束条件： , (8) , (9) 令 , , ,称为检验数。 1.2最优解判别准则 准则一：若 ，为对应于基B的基本可行解，且对于一切的 ，0 ，则X 为线性规划问题的最优解。 证明：0 ，由（）式可知，对任意一组可行解， ,均有 ，但 能使等式成立，即 ，故 为线性规划问题的最优解。 准则二：当, ，有某一个，设 , , ，则该线性规划问题有第二个最优的基本可行解。 证明：构造一个行解 ，() 得： 根据 原则 , 将 带入原目标函数（4）得： +(-+） 由于 - ，故： + 也是最优的基本可行解。 推论：若 和 均为最优的基本可行解， , 均为最优可行解。 准则三：当 0 , ，有某一个 ，对一切 ，则该线性规划有无穷多个最优解。 证明：构造一个新解 ，由 () 由于 ， ,故 , 将代入原目标函数（4）得： +(-） 由于：- 故： +0 , 当 时，仍为可行解，得到无穷多可行解，而目标函数仍为 ，即也是最优解。 以下举出一些实例，进一步说明线性规划最优解的具体求解方法： 2. 线性规划最优解的问题举例 2.1图解法求解线性规划问题 例：求解下面的线性规划问题： （1） 显然 是该线性规划问题（1）的一个最优解。 因 ，及 ， ， 可考虑如下线性规划问题： （2） 易解得线性规划问题（2）的最优解为 , , 于是可得 是该线性规划问题（1）的唯一最优解。 例：求解下面的线性规划问题： （1） 显然 是该线性规划问题（1）的一个最优解。 因 ，及 ， ， 可考虑如下线性规划问题： （2） 易解得线性规划问题（2）有无界解，是该问题的一个可行解 , , 于是线性规划问题的最优解不唯一。只要取如下： 那么 也是线性规划问题的最优解。例如，分别取s=0.5、0.25时，则和以及都是该线性规划问题（1）的最优解，其中，是一退化的基可行解，是一非退化的基可行解，而是一可行解而不是基解。 例：要将两种大小不同的钢板结成A,B,C 三种规格，每张钢板可同时截得三种规格的小钢板的块数乳下表所示： 钢板类型 规格类型 A规格 B规格 C规格 第一种钢板 2 1 1 第二种钢板 1 2