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

线性规划问题最优解的确定与改进

线性规划是运筹学的一个重要分支。自1947年丹捷格（G.B.Dantzig）提出了一般线性规划问题求解的方法——单纯形法之后，线性规划在理论上趋向成熟，在实用中日益广泛与深入。线性规划最优解求解问题，在《运筹学》本科版给出了图解法和单纯形法。 一般线性规划问题的标准型为：

maxz??cjxji?1n(1?4)

??aijxj?bi,i?1,2?m?j?1?xj?0,j?1,2,?n??n(1?5)(1?6)

满足约束条件（1-5）式、（1-6）式的解X?(x1,x2,?,xn)T，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。

2009年中国科教创新导刊，第三十期李高秀写的《线性规划中最优解的准确确定》中详细介绍了图解法的过程，图解法适合于二元线性规划问题，对于多元线性规划问题图解法相对较难。

图解法过程：

1 线性目标函数最值的分析

对于线性目标函数Z=ax+by ，若b≠0时，目标函数可变为y??在y轴上的截距。

(1)b>0时，随着直线y??截距

azazx?，则是直线y??x?bbbbazx?的平移，直线在与可行域有公共点的条件下，它在y轴上的bbzz 最大时z最大；当 最小时z最小。 bbaz (2)b<0时，随着直线y??x?的平移，直线在与可行域有公共点的条件下，它在y轴上的

bbzz截距最大时z最小；当最小时z最大。

bb由以上两点可知，要求线性目标函数z=ax+by的最大最小值要注意y的系数b的正负和平移直线在y轴上的截距。

2 在图上分别作出约束函数和目标函数，平移目标函数线到可行域的交点时，要把目标函数的斜率与相交于这一点的直线的斜率进行比较

上述的最值分析是确定平移目标函数的大概方向，而这次是确定最优解的确凿位置。斜率比较大

小的目的是直观形象的比较两直线的方向和倾斜程度。 具体的做法是：

(1)若目标函数的斜率是正(或负)的，只需要与斜率为正(或负)的直线进行比较，即与斜率同号的比较。

(2)比较斜率的绝对值，绝对值越大所对应的直线的倾斜程度越大，从直观来看直线越陡。根据上述的1和2，可准确的确定最优解的位置

单纯形法：

单纯形法的一般解题步骤可归纳如下：

① 线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。 ② 若基本可行解不存在，即约束条件有矛盾，则问题无解。

③ 若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基

变量取代某一基变量，找出目标函数值更优的另一基本可行解。

④ 按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到

问题的最优解。

⑤ 若迭代过程中发现问题的目标函数值无界，则终止迭代。

2006年甘肃联合大学学报(自然科学版)第三期，在熊洪斌发表的论文《线性规划最优解的进一步研究》中研究了线性规划最优解的参数表示，通过对某一最优解引入参数向量，得到新的LPP模型．通过求解LPP模型便可得到LP最优解的参数表达式。

人们在求解LP问题时常用单纯形方法求出一组最优解便终止．这样的思想和方法有时是不可取的．因为方案的单一性不便于决策者在短期内根据条件的变化进行灵活调整，从而使原有期望不变．用参数向量表示最优解，便可实现这一目的。

LLP方法介绍如下：

1 定义与引理

定义1 区间向量：若一向量的每个分量均为一区间数，则称该向量为区间向量．普通向量也是区间向量的一种特殊形式。

tAx?b，x?0有最优解x*。则x*??为原LP问题最优解的充要条引理1 若LP问题mincx.s..??0，A?x?0，x*???0，其中c?(c1,c2,?,cn)x?(x1,x2,?,xn)T， 件是：c?x*?(x*1,x*2,?,x*n)T，

A?(aij)m?n，

b?(b1,b2,?bm)T，

，0?(0,0,?,0)Tm?1??(?1,?2,?,?n)T。

2 LPP模型的建立

tAx?b，x?0。设其某一最优解x，则有与之对应的LPP模型：考虑标准型LP问题：mincx.s..*mincx?0,A???0,??x*?0。

由引理1和LP理论有以下定理：

定理1 设?N为LP问题非基变量的判别数集．(N 为非基变量下标集)则 (1) ?j?N,?j?0??为零向量?问题有惟一最优解． (2) ?j?N,?j?0??为区间向量?LP有无穷组最优解。

含义：?为零向量，表明决策者选择方案惟一。?为区间向量，表明决策者可随时根据条件变化调整既定方案，使原有期望不变。 3 ILPP模型的建立

tAx?b，x?Z，x?0(z为整数)，则与之对应的ILPP模型为考虑ILP问题：mincx.s..minc???0，s.t.A.??0，x*???0，??Z。

对ILPP模型，有以下定理：

定理2：

(1?j?N,?j?0??为零向量?lLP问题有惟一最优解． (2) ?j?N,?j?0??为区间向量?lLP有多重最优解．

4 数值求解

问题：现有一投资商对A、B两项产品投资，其投资利润及相关条件如下表：

利润 机器 人员

A产品 1千元/件

2 4

B产品 1千元/件

1 5

数量 6 2

情况变化 （1） 2台故障 0人请假

情况变化 （2） 1台故障 1人请假

问：该投资商在正常情况下如何安排生产，利润最大?条件变化又该如何安排生产(A、B产品数量需整数)?

解 根据题意，可得下列模型：

maxz?x1?x2 (x1，x2分别是A、B的生产数量)．

?2x1?x2?6;?(ILP)s..t?4x1?5x2?20;

?x?0,i?1,2.?i本文用割平面法解上述(ILP)，则上述(ILP)问题对应的LP松驰问题为：

maxz?x1?x2.?2x1?x2?x3?6; ?(LP)s..t?4x1?5x2?x4?20;?x?0,i?1,2,3,4.?iLP单纯性表如下： 表一 0 x1 1 x2 1 x3 0 x4 0 min(?z) 基 x3 x4 表二 6 20 2 4 1 5 1 0 0 1 对表一单纯选得最优表二

x1 0 x2 0 x3 -1/6 x4 -1/6 s1 0 -13/5 min(?z) 基 5/3 8/3 -2/3 1 0 0 0 1 0 2/3 -2/3 -1/3 -1/6 1/3 -1/3 0 0 1 x3 x4 s1 由表二中的x1为源行，可得割平面方程：s1??对表二对偶单纯选代得最优表三 表三 -4 211?x3?x4，将s1置于尾行并作为基。 333x1 0 x2 0 x3 0 x4 0 s1 -1/2 min(?z) 基 2 2 2 1 0 0 0 1 0 5/6 -1 1 0 0 1 -1/2 1 -3 x3 x4 s1 于是得ILP的一组最优解x1?2，x2?2，maxz?4。

为了考察情况变化是否直接影响投资者利益，我们有必要考虑如下模型ILPP：

min(?1??2)?0.??2?1??2??3?0;??s.t.?4?1?5?2??4?0;

????2,???2,??0,??0;234?1???,i?Z,i?1,2,3,4.通过求解ILPP问题，可得ILP的最优解可表示为：(2??1,2??1,??1,?3?1),?1?[?2,0],?1?Z. 由ILP最优解的参数表达式可知：在正常状况下，投资者有三种方案可供选择，分别为： 方案一 ?1?0,x1?2,x2?2. 方案二 ?1??1,x1?1,x2?3. 方案三 ?1??2,x1?0,x2?4.

根据情况变化(1)，投资者只可选择方案三；

根据情况变化(2)，投资者只可选择方案二。

通过LP和ILP模型的转换求出其最优解集，可让决策者更好地对其可利用资源进行更合理的分配，获得最佳利润，而不像单纯性表法只有一组最优解，一次LP和ILP模型有其优越性，可以用于解决最优化问题。

【参考文献】：

[1] 薛声家，刘 惠．一般形式线性规划最优解集的确定[M]．广州：暨南大学出版社，2001.2

[2] 熊洪斌. 线性规划最优解的进一步研究[M]. 甘肃：甘肃联合大学学报编辑部，2006.6

[3] 李高秀. 线性规划中最优解的准确确定[M].北京：中国科学技术信息研究所（ISTIC） 科学技术文献出版社，2009