运筹学-线性规划问题最优解的确定与改进

1、=J最线性规划问题最优解的确定与改进线性规划是运筹学的一个重要分支。自1947年丹捷格(G.B.Dantzig)提出了一般线性规划问题 求解的方法一一单纯形法之后，线性规划在理论上趋向成熟，在实用中日益广泛与深入。线性规划 最优解求解问题，在运筹学本科版给出了图解法和单纯形法。一般线性规划问题的标准型为：(1-4)(1-5)(1-6)max (1-4)(1-5)(1-6)i=1 J JZX =b,i=1,2.mj=x. 0,j=1,2,n满足约束条件(1-5)式、(1-6)式的解X =(气,x2,xjr，称为线性规划问题的可行解，其中 使目标函数达到最大值的可行解称为最优解。2009年中国科教

2、创新导刊，第三十期李高秀写的线性规划中最优解的准确确定中详细介绍了 图解法的过程，图解法适合于二元线性规划问题，对于多元线性规划问题图解法相对较难。图解法过程：1线性目标函数最值的分析 a z . a z对于线性目标函数Z=ax+by，右bN0时，目标函数可变为y = -丁 x + 丁，则是直线y = -丁 x + -b bb b在y轴上的截距。azb0时，随着直线y =-丁x +厂的平移，直线在与可行域有公共点的条件下，它在y轴上的bbzz截距丁 最大时z最大；当丁 最小时z最小。bbazb 0有最优解x*。则x* +为原LP问题最优解的充要条件是：c = 0，Ax = 0，x * + 0，

3、其中 c = (c , c，,c ) x = (x , x，,x )t， TOC o 1-5 h z 12n12nx* = (x* ,x* ,，x* )t ，A = (a )，b = (b ,b，b )t ，0 = (0,0, ,0)t，1 2nij mx n1 2 mmxlW = (3 ,0，,O )t。2 LPP模型的建立考虑标准型LP问题：min cx.s.t Ax = b，x 。设其某一最优解x*，则有与之对应的LPP模型：min cx = 0, AW = 0, W + x* 0。由引理1和LP理论有以下定理：定理1设&n为LP问题非基变量的判别数集(N为非基变量下标集)则W e N,

4、E 0 0W为零向量。问题有惟一最优解.3j e N,&j 0 (z为整数)，则与之对应的ILPP模型为min c = 0， s.t A.w = 0， x* + 0， e Z。对ILPP模型，有以下定理：定理2：(1 Vj e N,弓 0。3为零向量。lLP问题有惟一最优解.(2)刃e N,弓 0。3为区间向量。1LP有多重最优解.4数值求解问题：现有一投资商对A、B两项产品投资，其投资利润及相关条件如下表：A产品B产品数量情况变化情况变化(1)(2)利润1千元/件1千元/件机器216人员4522台故障1台故障0人请假1人请假问：该投资商在正常情况下如何安排生产，利润最大?条件变化又该如何安排

5、生产(A、B产品数量需 整数)？解 根据题意，可得下列模型：max z = x + x (x，x分别是A、B的生产数量).1212I% + x2 6；(ILP)s.t 4x + 5x 0, i 2= 1,2.i本文用割平面法解上述(ILP)，则上述(ILP)问题对应的LP松驰问题为：max z = x + x .2 x + x + x = 6;(LP) s.t 0, i = 1,2,3,4.I iLP单纯性表如下：表一x1x2x3x4min(-z)基01100 x62110 x204501对表一单纯选得最优表二表二xxxxsin(-z)基、-13/500-1/6-1/60 x3、5/3102/

6、3-1/60 x8/301-2/31/30s-2/300-1/3-1/31由表二中的x为源行，可得割平面方程：S =-2 +1 x +1 x，将S置于尾行并作为基。11333341对表二对偶单纯选代得最优表三表三xxxxsin(-z)基-40000-1/2x3、2105/60-1/2x201-101s20011-3于是得ILP的一组最优解气=2，x2= 2，maxz = 4。为了考察情况变化是否直接影响投资者利益，我们有必要考虑如下模型ILPP：min( 3 +3 ) = 0.2 3 i +3 2 +3 3 = 0 0；3 - 2, 3 - 2, 3 0；12343 , i G Z , i =

7、 1,2,3, 4.通过求解ILPP问题，可得ILP的最优解可表示为：(2 + 3，2-W , 3,-3w ),Q g -2,0, w g Z.111111由ILP最优解的参数表达式可知：在正常状况下，投资者有三种方案可供选择，分别为：方案一 气二0,气=2, % = 2.方案二 31 = -1,% -1,x2 = 3.方案三 31 =-2, %1 = 0, % = 4.根据情况变化(1)，投资者只可选择方案三；根据情况变化(2)，投资者只可选择方案二。通过LP和ILP模型的转换求出其最优解集，可让决策者更好地对其可利用资源进行更合理的分配， 获得最佳利润，而不像单纯性表法只有一组最优解，一次匚？和ILP模型有其优越性，可以用于解决 最优化问题。【参考文献】：薛声家，刘惠.一般形式线性规划最优解集的确定M