怎样求最优整数解:线性规划最优解的求法

时间：2019-03-12 03:26:43　来源：柠檬阅读网本文已影响人

　　提问：线性规划应用题中经常有要求最优整数解的题目，有没有什么通法来解决呢？　　回答：让我们先来看一道题. 　　某营养师要为某个儿童预订午餐和晚餐．已知一个单位的午餐含12个单位的碳水化合物、6个单位的蛋白质和6个单位的维生素C，一个单位的晚餐含8个单位的碳水化合物、6个单位的蛋白质和10个单位的维生素C．该儿童的午餐和晚餐至少应含有64个单位的碳水化合物、42个单位的蛋白质和54个单位的维生素C．
　　如果一个单位的午餐的费用是2.5元，一个单位的晚餐的费用是4元，那么要满足上述营养要求，并且花费最少，应当为该儿童分别预订多少个单位的午餐和晚餐？
　　设营养师为该儿童分别预订x个单位的午餐和y个单位的晚餐，共花费z元，则目标函数z=2.5x+4y，且x，y应满足不等式组12x+8y≥64，6x+6y≥42，6x+10y≥54，x∈N*，y∈N*，即3x+2y≥16，x+y≥7，3x+5y≥27，x∈N*，y∈N*.
　　不等式组表示的平面区域如图1中的阴影部分所示. 图中的直线为l1：3x+2y=16，l2：x+y=7，l3：3x+5y=27．其中，l1与y轴的交点为D（0，8），l1与l2的交点为C（2，5），l2与l3的交点为B（4，3），l3与ｘ轴的交点为A（9，0）．把目标函数化为截距式，得ｌ：ｙ＝-ｘ+，令ｚ＝0，画出基线ｌ0：ｙ＝-ｘ的图象．
　　∵ 0＞ｋｌ3＞ｋｌ0＞ｋｌ2＞ｋｌ1， ∴由图1可知，当直线l自l0处沿着y轴正方向平移至点B（4，3）时，ｚ＝2.5ｘ+4ｙ有最小值，ｚｍｉｎ＝ｚB＝2.5×4+4×3＝22（元）．
　　很明显，该题的解法与一般线性规划问题的解法相同．究其原因，是目标函数表示的直线l所经过的可行域内的最低点碰巧是整点（横坐标和纵坐标均为整数的点）B（4，3），这自然就成为问题的最优整数解了！
　　那么，如果目标函数表示的直线经过可行域的最低点或最高点不为整点，该如何处理呢？
　　让我们修改一下题目条件，将原题改为“该儿童的午餐和晚餐至少应含有64个单位的碳水化合物、42个单位的蛋白质和52个单位的维生素C”. 那么，原来的解法依旧可行吗？要求最优整数解，又有哪些规律可循呢？
　　修改后，目标函数ｚ＝2.5ｘ+4ｙ不变，x，y应满足不等式12x+8y≥64，6x+6y≥42，6x+10y≥52，x∈N*，y∈N*，即3x+2y≥16，x+y≥7，3x+5y≥26，x∈N*，y∈N*.
　　如图2所示，图中的直线为l1：3x+2y=16，l2：x+y=7，l3：3x+5y=26．其中，l1与y轴的交点为D（0，8），l1与l2的交点为C（2，5），l2与l3的交点为B（4.5，2.5），l3与ｘ轴的交点为A，0．把目标函数化为截距式，得ｌ：ｙ＝-ｘ+，令ｚ＝0，画出基线ｌ0：ｙ＝-ｘ的图象．运用原题解法，易知当l过点B时，z=2.5x+4y有最小值，ｚｍｉｎ＝ｚB＝2.5×4.5+4×2.5＝21.25．
　　∵ 非整点B是l经过的可行域内的最低点，又所求最优解必须是l经过的可行域内的最低整点， ∴最优解一定位于可行域内、点B附近．
　　如图2所示，∵ B（4.5，2.5）的横坐标ｘB∈［4，5］，∴可先求出直线ｘ＝4或ｘ＝5与可行域的交点中的最低整点．把ｘ＝4代入不等式组，解得ｙｍｉｎ＝3，得第一个较低整点E（4，3），此时ｚE＝2.5×4+4×3＝22；把ｘ＝5代入不等式组，解得ｙｍｉｎ＝3，得第二个较低整点F（5，3），此时ｚF＝2.5×5+4×3＝24.5． ∴ 午餐费和晚餐费之和的最小值是22元，ｘ＝4，y＝3是一组最优整数解．
　　反思一下此题的求解过程，我们可以发现求最优整数解有一个通法，即根据非整点时的最优解来探究最优整数解．我们可以把求线性规划问题最优整数解的解题步骤概括成两步：首先在不考虑最优解必为整数的前提下，求出最值z0=ax0+by0；然后根据点（ｘ0，y0）所在的位置，寻找可行域内距离点（ｘ0，y0）最近的整点，求出这些整点所对应的值，找出与ｚ0最接近的值ｚ1，ｚ1所对应的整点――可能是以上这些整点中的一个或数个――即为最优整数解．
　　注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文

怎样求最优整数解:线性规划最优解的求法

最新文章

热门文章