关于线性规划问题的两种解法

石 磊

   本文通过对现行规划问题的研究，线性规划问题的两种方法：图解法、单纯形法．

在工农业生产、交通运输、经济贸易等工作中，必须提高经济效率，做到耗费较少的人力、财力、物力，创造出更多的经济效益，提高社会生产力．

线性规划的应用很广泛，如运输问题、生产的组织与计划问题、合理下料问题、配料问题、布局问题等．数学模型是描述实际问题共性的抽象数学形式．

   一、线性规划问题的几种解法

   （一）图解法(解的几何表示)

   1.图解法求解线性规划问题的步骤如下

   (1)分别取决策变量，为坐标向量建立直角坐标系；

   (2)对每个约束(包括非负约束)条件，先取其等式在坐标系中作出直线，通过判断确定不等式所决定的半平面．各约束半平面交出来的区域(存在或不存在)，若存在，其中的点表示的解称为此线性规划的可行解．这些符合约束限制的点集合，称为可行集或可行域．进行(3)；否则该线性规划问题无可行解．

   (3)任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平移后值增加的方向，平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置(有时交于无穷远处，此时称无有限最优解)．若有交点时，此目标函数等值线与可行域的交点即最优解(一个或多个)，此目标函数的值即最优值．

   2.对图解法的几点解释

   (1)有效与无效(紧与松)约束：与最优解相关的约束为有效（紧）约束．

   (2)最优解：总是在可行域的边界上，一般由可行域的顶点表示．

   (3)可行域：由约束平面围起来的凸多边形区域,可行域内的每一个点代表一个可行解．

   (4)可行域可能会出现多种情况．

    (5)在非空时，线性规划既可以存在有限最优解,也可以不存在有限最优解(其目标函数值无界)．

   (6)非空且线性规划有有限最优解时，最优解可以唯一或有无穷多个．

   (7)若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域的“顶点”．

  （二）单纯形法

单纯形法是求解线性规划问题的最有效的方法，它实际上是一种迭代算法．单纯形法的基本思想是，根据问题的标准型，首先找到一个基本可行解，检验是否为最优解；如果不是，再找一个使目标函数有改进的基本可行解，进行检验；反复迭代，直至找到最优解，或判断问题无有限最优解．

单纯形法解决线性规划问题的步骤：

   (1)把一般的线性规划问题化为标准型．

   (2)将标准型化为如下式的基本形式

，

（1．5）

并建立线性规划问题表如下：

表线性规划问题表基变量…………可行解1……………… … …… … …………………… … …… … ………………目标…………    (3)找出初始可行基，确定初始基本可行解，建立初始单纯形表．

    (4)检查对应于非基变量的检查数，如果所有的检查数，则已得到最优解，停止计算．否则，转下一步．

    (5)若存在，并非所对应的列向量，则此问题无界，停止计算．否则，转下一步．

    (6)根据，确定为进基变量，根据．确定为出基变量，并称为主元素，转下一步．

    (7)在表中以为主元素进行旋转迭代，即用高斯消元法将所对应的列变换为，由此得到新的单纯形表。

从表中可以看出，得到的新的基本可行解为

相应的目标函数值为．

即目标函数值减小了．再以新的单纯形表为起点，返回(5)．

（作者单位：西北民族大学数学与计算机科学学院）