龙源期刊网 https://www.wendangku.net/doc/66258679.html,
线性规划中整点最优解的求解策略
作者:郭海鹰
来源:《理科爱好者(教育教学版)》2018年第02期
【摘要】随着中学数学教育的改革和发展,简单线性规划问题已经逐渐成为中学数学教
学中的一个基本内容。简单线性规划问题与我们的日常生活息息相关,它主要涉及人力、物力、资金等资源的最优配置。在中学数学教学中,整点最优解问题是简单线性规划的核心内容,但教材对于具体的验算过程并没有作过多的描述,以致中学生在解题过程中对于具体的验算过程掌握还不够清晰。在资料上也经常见到有关简单线性规划整点最优解问题的求解方法,如:网格法,穷举法,筛选法,最小距离法等。本文将介绍利用平移法求整点最优解的两种具体的操作方法—平移交轨法,平移近值法。
【关键词】线性规划;平移;整点最优解
【中图分类号】G633.6 【文献标识码】B 【文章编号】1671-8437(2018)10-0069-02
1 平移交轨法
该方法主要是在平移直线过程中,利用直线间的交点来缩小最优值的存在范围,因此其主要思想是联立方程求解交点,然后确定最优解可能的存在范围。
例1 要将两种大小不同的钢板截成A、B、C三种规格,每张钢板可同时截得三种规格的小钢板的块数如下表所示:
根据目标函数作出一组平行直线:x+y=t。这些直线中经过可行域且和原点距离最近的直线,此直线经直线x+3y=27和2x+y=15的交点A(),此直线与原点的距离最近,z取得最小值,即:
z= x+y=
显然和都不是整数,而最优解中,x和y必须为整数,故A不是最优解,故将直线x+y= 向上平移到x+y=12,最优解可能存在于此直线上。最优解必须在可行域内,故应求出直线
2x+y=15和x+3y=27与x+y=12的交点:
可得交点坐标为B(3,9),D(,),故有:3≤x≤
这样便更进一步的缩小了x的范围,即x=3或4,将其代入x+y=12,可得y=9或8。即(3,9)和(4,8)均为所求的最优解。