线性规划问题的最优解

1、引言线性规划是运筹学的一个基本分支，其应用极其广泛，其作用以为越来越多的人所重视。线性规划主要就实际问题抽象成数学形式，即求一组变量的值，在满足一定的约束条件下，是某个目标达到最小或最大，而这些约束条件用可以用一组线性不等式或线性方程来表示。而求得目标函数的最优解尤为重要，本文就线性规划问题的最优解求解方法作出阐述，并举出实例加以强化，同时也指出了线性规划问题应用于生产与运作管理的重要性。1.线性规划问题的最优解探讨考虑下面的线性规划问题的标准型：目标函数： (1)约束条件： (2)其中，,阶矩阵。设B是A中m个线性无关的列向量构成的一个基， 阶矩阵，这样将矩阵A分成两个部分，即A=,X=,C

2、=,为基B对应的非基变量和系数，,为N对应的非基变量和系数，这样将线性规划问题改写为： minZ (3)约束条件： (4) 经过矩阵变换，得出关于基B的标准型如下：+(-N) (5)约束条件： (6) 将（5）（6）展开为：+() (7)约束条件： , (8) , (9)令 , , ,称为检验数。准则一：若 ，为对应于基B的基本可行解，且对于一切的 ，>0 ，则X 为线性规划问题的最优解。 证明：>0 ，由（）式可知，对任意一组可行解， ,均有 ，但 能使等式成立，即 ，故 为线性规划问题的最优解。准则二：当, ，有某一个，设 , , ，则该线性规划问题有第二个最优的基本可行解。

3、证明：构造一个行解 ，() 得： 根据 原则 , 将 带入原目标函数（4）得：+(-+）由于 - ，故： + 也是最优的基本可行解。推论：若 和 均为最优的基本可行解， , 均为最优可行解。准则三：当 0 , ，有某一个 ，对一切 ，则该线性规划有无穷多个最优解。证明：构造一个新解 ，由 () 由于 ， ,故 ,将代入原目标函数（4）得：+(-）由于：-故： +0 , 当 时，仍为可行解，得到无穷多可行解，而目标函数仍为 ，即也是最优解。以下举出一些实例，进一步说明线性规划最优解的具体求解方法：2. 线性规划最优解的问题举例例：求解下面的线性规划问题： （1）显然 是该线性规划问题（1）的一个

4、最优解。因 ，及 ， ，可考虑如下线性规划问题： （2）易解得线性规划问题（2）的最优解为 , , 于是可得 是该线性规划问题（1）的唯一最优解。例：求解下面的线性规划问题： （1）显然 是该线性规划问题（1）的一个最优解。因 ，及 ， ，可考虑如下线性规划问题： （2）易解得线性规划问题（2）有无界解，是该问题的一个可行解 , , 于是线性规划问题的最优解不唯一。只要取如下：那么 也是线性规划问题的最优解。例如，分别取s=0.5、0.25时，则和以及都是该线性规划问题（1）的最优解，其中，是一退化的基可行解，是一非退化的基可行解，而是一可行解而不是基解。例：要将两种大小不同的钢板结成A,B,

5、C 三种规格，每张钢板可同时截得三种规格的小钢板的块数乳下表所示：钢板类型规格类型 A规格 B规格 C规格 第一种钢板 2 1 1 第二种钢板 1 2 3今需 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)、

6、（12,0），若逐一讨论其是否在可行域内比较麻烦时，只需先判断点A（）附近的整数点是否满足条件，若满足条件，则再试附近的整数点；若不满足条件，则不需要再判断下去。 故此题，我们只需先判断A点附近的整数点（3,9）、（4,8），分别代入（*）式，易得它们都满足条件。故我们还需判断（2,10）、（5，7）两点，代入（*）式发现它们都不满足条件，则其余点不需要再判断。所以该题的最优解为（3,9）、（4,8）。例：，约束条件为：，利用图解法求解如下：此例中约束条件中存在和目标函数的系数成比例的约束条件，但是由于此约束条件在可行域的形成中没有发挥作用，所以此问题没有多个最优解。 图解法是求解含有两个变量

7、的线性规划问题的一种很直观和有效的方法，所以在作出问题的可行域时，则可根据这个必要条件，若可行域中没有与目标函数平行的边界线时，则可直接判断出此问题一定没有多个最优解。例：求解问题：解：这里是一个单位矩阵，且,故基B是可行基，为基变量，为非基变量，基B对应的基本可行解为：，其目标函数值.方程组已是典式，得到第一张单纯性表如下：RHS01-20001-210020-310101-1012 注意 ，第0行的元素应是将目标函数化成等价的方程后的相应元素。检验数 ，故当前解不是最优解，列中有两个元素均为正数，取 故转轴元为，为进基变量，为出基变量。进行旋转变换后得下表：RHS001-10-110-52

8、0401-310100-111它对应的基本可行解为，其目标函数值为.但，仍不是最优解，此时为转轴元，进行旋转变换后得下表：RHS000100010001它对应的基本可行解为，其目标函数值为.此时检验数向量，故为最优解。例：接下面的LP问题：解：引进非负的剩余变量，将不等式约束化为等式约束若用原始单纯形法求解，需再引进两个非负的人工变量，然后利用两阶段法求解。由本例所具有的特点，我们只要将等式两端同乘以（-1），就直接得到原问题的一个基本（不可行）解和对偶问题的一个可行解（检验数向量）其对应的单纯形表如下：RHS-1-1-1000-3-1-110-11-111-2直接利用对偶单纯形法求解。，所以

9、为离基变量，由以下比值决定进基变量。因而为进基变量，以为转轴元，进行旋转变换后得下表：RHS000110显然为离基变量，计算确定为进基变量，以为转轴元，进行旋转变换后得下表：RHS001001此时，故原问题的最优解为，其最优解为。由以上例题可见，在某些情况下使用对偶单纯形法比用原始单纯形法更具优越性。参考文献 1 胡运权等.运筹学基础及应用M.第五版 北京：高等教育出版社,2008-06.2 管梅谷,郑汉鼎.线性规划M.济南：山东科学技术出版社,1983.3 张香云.线性规划M.浙江大学出版社,2009-02.,.线性规划导论M.机械工业出版社,2005-06.5 卢开澄,卢华明.线性规划M.清华大学出版社,2009-02.6 江道琪,何建坤,陈松华.编.使用线性规划方法及其支持系统M.清华大学出版社,2006-04.7 卢向华,侯定丕,魏权龄.运筹学教程M.北京高等教育出版社,1989.致 谢经过三四个月的忙碌和学习，本次毕业设计已经接近尾声，作为一个本科生的毕业设计，由于经验的匮乏，难免有许多考虑不周全的地方，如果没有导师的督促指导，以及一起工作的同学们的支持，想要完成这个设计是难以想象的。在这里，首先要感谢我的导师马晓娜老师。马老师平日里工作繁多，但在我做毕业设计的每个阶段，从外出实习到查阅资料，设计草案的确定和修改，中期检查，后期工作