线性规划问题的最优解.doc

宿州学院2011届本科生毕业论文线性规划问题的最优解

宿州学院2010届本科生毕业论文线性规划问题的最优解

线性规划问题的最优解
引言
线性规划是运筹学的一个基本分支，其应用极其广泛，其作用以为越来越多的人所重视。线性规划主要就实际问题抽象成数学形式，即求一组变量的值，在满足一定的约束条件下，是某个目标达到最小或最大，而这些约束条件用可以用一组线性不等式或线性方程来表示。而求得目标函数的最优解尤为重要，本文就线性规划问题的最优解求解方法作出阐述，并举出实例加以强化，同时也指出了线性规划问题应用于生产与运作管理的重要性。

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规格第一种钢板211第二种钢板123
今需A,B,C三种规格的成品分别为15，18，27块，问：各截取这两种钢板多少张可得所需三种规格成品，且使得所用钢板张数最少？

解：需要截得第一种钢板X张，第二种钢板Y张，则（*）
作出可行区域图如下：
目标函数为，经过可行区域内的整点且与原点最近的直线是。它上面的整点有（0，12）、（1,11）、（2,10）、(3,9)、（4，8）、（5，7）、（6,6）、（7,5）、（8,4）、（9,3）、（10,2）、(11,1)、（12,0），若逐一讨论其是否在可行域内比较麻烦时，只需先判断点A（）附近的整数点是否满足条件，若满足条件，则再试附近的整数点；若不满足条件，则不需要再判断下去。
故此题，我们只需先判断A点附近的整数点（3,9）、（4,8），分别代入（*）式，易得它们都满足条件。故我们还需判断（2,10）、（5，7）两点，代入（*）式发现它们都不满足条件，则其余点不需要再判断。所以该题的最优解为（3,9）、（4,8）。

例：，约束条件为：

，

利用图解法求解如下：

此例中约束条件中存在和目标函数的系数成比例的约束条件，但是由于此约束条件在可行域的形成中没有发挥作用，所以此问题没有多个最优解。
图解法是求解含有两个变量的线性规划问题的一种很直观和有效的方法，所以在作出问题的可行域时，则可根据这个必要条件，若可行域中没有与目标函数平行的边界线时，则可直接判断出此问题一定没有多个最优解。

2