线性规划中最优解的探究

【摘要】线性规划（LP）是运筹学中较早发展起来并已经广泛地应用于各个领域的一个重要数学理论和方法。在高中數学教学中，线性规划问题最优解是很重要的一部分，本文研究和讨论了线性规划最优解的几种情形及其判定，弥补和优化了教材和专著在这方面的不足，为用线性规划解决实际问题提供了理论依据。同时，对高中学生在学习数学时如何灵活的运用课本素材，以及学生创新思维的形成及培养方面起到了很好的示范作用。

【关键词】高中数学 线性规划 最优解

【中图分类号】G633.6 【文献标识码】A 【文章编号】2095-3089（2019）33-0134-02

一、可行域中最优解的确定问题

先来看一道例题：

例1 已知变量x，y满足下列条件

X≥0，Y≥0，X+3Y≤15，X+Y≤6， 3X+Y≤15

求目标函数Z=3X+2Y的最优解。

解：满足这个不等式组的（X，Y）所存在的范围即可行域如下图所示

∵目标函数为Z=3X+2Y

∴作直线L：3X+2Y=t（t∈R），则是直线在X轴上的截距。

∴L向右平移？圳则变大？圳t变大，但这里的问题是将直线3X+2Y=t向右平移时，它究竟是在经过M点，还是经过N点时，t取得最大值呢？这就需要比较目标函数所表示直线的斜率和相关直线的斜率的大小。

∵目标函数z=3x+2y的斜率是-，而相关直线3x+y=15的斜率是-3.

x+3y=15的斜率是-. x+y=6的斜率是-1.

又∵-3<-<-1<-.

最优点在斜率为-3和斜率为-1的直线的交点M处，联立对应的方程得方程组

3x+y=15x+y=6 解得M（）.

Zmax=3×+2×=16.5 ， 显然Zmax=3×0+2×0

解题反思：目标函数在可行域中最优解的位置与目标函数所表示的直线的斜率及其相关直线的斜率有关，当最优解的位置不能从图形中明显看出来时，可在局部范围比较它们斜率的大小（当斜率不存在时可比较其倾斜角的大小）。

二、初始等值线的选择问题

例2 设z=2y-2x+4 ，式中x，y满足条件 0≤x≤1，0≤y≤2，2y-x≥1， 求z的最大值和最小值。

解：作出满足不等式组0≤x≤1，0≤y≤2，2y-x≥1，的可行域如下图阴影所示。

再作出一组z=2y-2x+4的平行直线系，即等值线2y-2x=t，我们选t=2，就是说让初始等值线过M点，即x=1，y=2时得t=2，作出2y-2x=2，这就是这里所选的初始等值线，有了这条初始等值线作参照，可明显看出，平行直线过点A（0，2）时，t取得最大值，过点B（1，1）时，t有最小值，相应地Zmin=2×1-2×1+4=4，Zmax=2×2-2×0+4=8。

解题反思：按惯例，作目标函数等值线时，一般先作Ax+By=0 再作它的平行直线系找出最优解，但在实际问题中，究竟哪一点是我们所寻找的最优解的位置呢？事实上，最优解的确定与目标函数对应直线的斜率，以及相关直线的斜率有关，这在前面已经说到。这里所说的是初始等值线的选择问题，根据本例可得出结论：在作目标函数初始等值线时，可灵活选择其为Ax+By=Z′，而对Z′的选择，原则是Z′与系数A，B有关，且在数形结合时，可明显比较出相关直线斜率或倾斜角的大小，进而直观的在可行域确定最优解的位置，如上例所选Z′=2就是很好的例证。

三、 关于整数点的最优解

求目标函数整数最优解，可利用可行域中整数网格的交点，但是利用此法对作图要求较高，所以，有时也利用其它方法调整最优解，如通过限制一个变量的范围，找到横坐标（或纵坐标）中的整数，再加以比较、验证而得到。

例3 X，Y满足不等式组x+y≥122x+y≥15x+3y≥27x≥0，y≥0 （x，y∈Z）

求目标函数z=x+2y的最小值。

解：作出不等式组表示的平面区域，如右图所示。

比较目标函数与相关直线的斜率得：

∵ -2<-1<-<， ∴ 由方程组x+y=12x+3y=27得A点坐标为（），但x，y∈z，∴A点不是整数最优解，需要调整。可令x=5，此时结合图形，y的约束条件是x+3y≥27，∴y≥∵y∈z，∴y=8 得一整数点（5，8），再令y=8，此时，约束条件为2x≥15x+y≥12？圯 x≥4x≥.∴x=4.又得一整点（4，8），比较（4，8）与（5，8），显然，可行域中使目标函数取得最小值的整数解是（4，8），即Zmin=4+2×8=20.

作者简介：

牛郁宇（1971.5-），女，汉族，甘肃省兰州市人，本科，中教一级，研究方向：中学数学教育。