线性规划中最优整解的一种求解方法

正如文[1]所说,"在线性规划问题中,最令学生、教师头疼的莫过于如何寻找最优整解.通常作法是用网格法,即把可行域中的整点标出,再通过代点检验来完成最优整解寻找;不过这种方法要经过大量繁复的运算才能保证结果的正确性."     

用调整优值法求最优整数解

“线性规划问题”的最优整数解是《简单的线性规划》一节中的一个难点 .现以教科书 (试验本 )第二册 (上 )第 6 5页习题 7.4的第四题为例说明如何用调整优值法来求“线性规划问题”的最优整数解 .(题目略 )本题的线性约束条件为1 8ｘ + 1 5 ｙ≤ 1 80 ,1 0 0 0ｘ + 6 0 0 ｙ≤ 80 0 0 ,ｘ∈Ｎ ,ｙ∈Ｎ , 6ｘ + 5 ｙ≤ 6 0 ,5ｘ + 3ｙ≤ 40 ,ｘ∈Ｎ ,ｙ∈Ｎ .线性目标函数为ｚ =2 0 0ｘ + 1 5 0 ｙ ,其中ｘ、ｙ分别表示大、小房间的间数 .作出可行域如图 1 .图 1为求ｚ的最大值 ,先将目标函数化为ｙ =-43ｘ + ｚ1 5 0 ,易知当该直线ｌ在ｙ轴…     

线性规划中最优整解的一种简捷求法

寻找最优整解是线性规划中的一类常见问题,通常用网格法,即把可行域中的整点标出,再通过代点检验来寻找最优整解,但这种方法需要准确的作图和比较繁琐的检验才能保证其正确性,如果可行域中的整点找不全或找不准,就会使得最优整解不正确或最优整解个数不全．为了克服网格法的缺点,笔者常采     

线性规划中最优整解的一种寻找方法

在线性规划问题中，最令学生、教师头疼的莫过于如何寻找最优整解．通常作法是用网格法，即把可行域中的整点标出，再通过代点检验来完成最优整解寻找；不过这种方法要经过大量繁复的运算才能保证结果的正确性．在实际应用中常出现：可行域中的整点找不全找不准、最优解不正确或最优解个数不全等问题．笔者在教学中，发现用平行线分割法，虽然也有一定的运算量，但克服了网格法的大部分缺点，可以在教学中一试．     

简单线性规划问题的向量解法

在高中数学新教材中 ,增选简单线性规划为必修内容 .在用图解法求简单线性规划问题的最优解时 ,教师教学用书中 ,通过比较平行线在 x轴或 y轴上的截距大小寻求目标函数的最优解 .本文提出用目标函数法向量的方法寻求目标函数的最优解 ,供同行参考 .先看例题 .例 1　设 z =2 x y,式中变量 x,y满足下列条件x - 4y≤ - 3,3x 5y≤ 2 5,x≥ 1 .求 z的最大值和最小值 .解　画出可行域如图 1中的阴影部分 .过原点 O( 0 ,0 )作直线 l0 :2 x y =0 ,正法向量为 n =( 2 ,1 ) .当直线 2 x y =t沿着正法向量平行移动时 ,t的值就逐渐增大 ,当直线…     

谈线性规划中“整点最优解”处理方法

现行高中数学教材新增设了线性规划的内容 ,并开设了研究性课题 :线性规划的实际应用 .但教材中寻找整点最优解的方法介绍得笼统 ,不易掌握与操作 ,使寻找整点最优解成为了学习中的难点 .本人据第六十五页习题 7.4第 4题介绍两种求整点最优解的方法 ,供同学们学习中参考 :引例　某人有楼户一幢 ,室内面积共1 80ｍ2 ,拟分隔成两类房间作为旅游客房 ,大房间每间面积 1 8ｍ2 ,可住游客 5名 ,每名游客每天住宿费为 40元 ;小房间每间面积为 1 5ｍ2 ,可住游客 3名 ,每名游客每天住宿费为 50元 ;装修大房间每间需 1 0 0 0元 ,装修小房间每间需60 0…     

线性规划中求整数最优解的五种方法

“线性规划”是新教材的新增内容 .在求最优解时 ,通过平移直线的方法得出理论最优解 ,学生能理解和掌握 ;但是 ,如果要求出整数最优解 ,多数学生往往无法下手 ,屡屡出错 .针对这种情况 ,本文将就一个引例 ,介绍五种求整数最优解的方法 ,供大家参考 .为叙述方便 ,记理论最优解时目标函数对应的直线Ax +By +C =0为l0 .图 1　引例用图引例　已知x ,y满足4x +3y - 2 0≤ 0 ,x - 3y - 2≤ 0 ,x ,y∈N+ ,求s =7x +5 y的最大值 .分析 :首先我们将x ,y∈N+ 改成x ,y >0 ,画出可行域 (如图 1) ,通过画图发现直线 4x +3y - 2 0=0 ,x - 3y - 2 =0的…     

切割定界与整数分枝结合求解整数线性规划

把一种改进的割平面方法和分枝定界的思想结合起来求解整数线性规划 ( ILP)问题 .它利用目标函数等值面的移动来切去相应 ( LP)的可行域中含其非整数最优解但不含 ( ILP)可行解的“无用部分”,并将对应的目标函数值作为 ( ILP)目标最优值的一个上界 ;最后 ,通过 ( LP)最优解中非整数基变量的整数分枝来获得整数线性规划的最优解 .     

简单的线性规划

1　重难点分析本单元要求了解二元一次不等式表示的是直线一侧的平面区域 ,能够具体画出二元一次不等式(组 )所表示的平面区域 ,了解线性规划的意义及线性约束条件、线性目标函数、可行解、可行域、最优解等基本概念 ,了解线性规划问题的图解法 ,能用图解法求最优解及线性目标函数的最大值或最小值 ,能用线性规划的方法解决实际生活中简单的最优问题 ,培养提高对实际问题进行探索分析研究的能力 .本单元的重点是二元一次不等式表示的平面区域和解线性规划问题的图解法 .难点之一是确定二元一次不等式的解表示的是直线的哪一侧区域 ,解决此难…     

整数线性规划的一种新的割平面法

本文提出了一种新的求解整数线性规划的割平面思路 .它利用目标函数等值面的移动来切割与(IL P)相应的 (SL P)可行域的“无用”部分 ,再通过扩大与 (SL P)最优基相应的非基变量的取值来压缩 (SL P)的可行域 ,由此求得整数线性规划的最优解 .     

旅馆只开一天——对一道课本习题的再探讨

贵刊文 (1 )、文 (2 )及文 (3 )讨论了高中试验教材第二册 (上 )中《简单的线性规划》的一道习题的整点最优解问题 ,读后很有收获 ,但另一方面 ,这些解都只考虑了旅馆一天的收入 ,笔者以为不尽合理 ,设想一下 ,如果旅馆营业时间不止一天 ,而是足够长 ,原先的那二组最优解还是最优吗 ?这两组解之间就真的难分伯仲了吗 ?进而思之 ,难道就没有比这两组“最优解”更优的解了吗 ?以下是笔者的一点浅见 ,敬请专家、同行指教 ,先抄录一下原题和文 (3 )的解法 .题目 (教材Ｐ6 5第 4题 )某人有楼房一幢 ,室内面积共 1 80ｍ2 ,拟分隔成两类房间作为旅…     

在直线与二次曲线围成的可行域上求目标函数最值

在线性规划中,可行域都是直线围成的平面区域,我们能求出目标函数的最值,当可行域由直线与二次曲线围成时,如何求目标函数的最值呢?现在就让我们一起来学习探讨.例1已知x,y满足(x-2)2 y2-1≤0,x-3y≤0,求x y3的最大值和最小值.分析x y3可看作动点M(x,y)与定点B(-3,0)所在直线的     

线性规划应用中的优值调整

人教版高中数学试验本第二册 (上 )增加了“简单的线性规划”这部分内容 ,在线性规划的实际应用中 ,理论上得到的最优解有时可能不满足实际要求 ,这时就需要进行优值调整 .本文将归纳优值调整的几种常用方法 ,供参考 .　　一、在可行域内 ,找出可能成为最优解的所有可行解 ,逐个代入目标函数验证 ,确定出实际最优解 .这种方法适用于可行域内这种可能成为最优解的可行解不太多的问题 .例 1　某运输公司有 7辆载重量为 6ｔ的Ａ型卡车和 4辆载重量为 1 0ｔ的Ｂ型卡车 ,有9名驾驶员 .在建筑某段高速公路中 ,此公司承包了每天至少搬运 36 0ｔ沥青…     

缩小可行域求线性规划的整数最优解

新教材中添加了"简单的线性规划"一节.在求最优解的问题中,如果所求的不是整数最优解,通过平移直线的方法得出最优解,学生能够理解,也容易掌握.但如果要求整数最优解,讲解的时候利用多媒体演示学生也能理解,但在学生做作业的时候就出现了问题,学生不知从何下手.如果同样利用平移的方法,由于此时的可行域为不连续的点,很难得到最优解.这时我们可以采用缩小可行域的方法解决求整数最优解的问题.     

一类线性规划的分析解法

本文给出一类线性规划的分析解法。它同单纯形法[1]或直除法[2]相比,具有如下优点:1.不需要进行“调整”,就能直接得最优解或判定规划无解,因而计算简单。2.在得出最优解的同时就能给出全部最优解(即所有的最小值点)。     

简单线性规划两种教学法比较

为加强理论与实际的联系 ,培养学生应用数学知识解决实际问题的意识和能力 ,高中数学新教材中 ,增选简单线性规划为必修内容之一 .如何用图解法求线性规划问题的最优解 ,是本节的重点难点所在 .教师教学用书中建议通过比较平行线在ｘ轴或 ｙ轴上的截距大小求解 (本文中称之为途径 1 ) .本人在教学中则是通过比较等值线的值的大小求解 (本文中称之为途径 2 ) .寻求最优解的这两种途径 ,何者更科学、更符合学生学习心理呢 ?本文拟就此做一比较 ,与大家共商 .1　知识准备定义 :平面内 ,如果方程Ａｘ Ｂｙ Ｃ =0 (Ａ、Ｂ不同时为 0 )的直线ｌ上…     

一类线性规划问题的快速解法

研究了在组合投资和多属性决策指标权重确定中有着重要应用的一类线性规划问题,得到了该类线性规划问题有可行解的充要条件,以及在有可行解的情况下寻求最优解的快速解法.     

对一道教材例题解法的质疑

人教社高中《数学》第二册(上)P61例3是一道简单线性规划应用题.由于题目要求最优解的结果精确到0.1t,所以教材解法对可行域中点M的坐标取了近似值.笔者认为这种做法是错误的.为方便起见,将教材中的例3及其解法抄录如下.例3某工厂生产甲、乙两种产品.已知生产甲种产品1t需耗A种     

浅谈数学教学中学生思维品质优化策略

例一1、一题多解,拓宽思路,激活思维的广阔性已知M(2,-3)、N(-3,-2),直线L过点P(1,1)与线段MN相交,求直线L的斜率k的取值范围.解法一、数形结合法,如图,因kPN=43,kPM=-4,由正切函数的单调性知k≤-4或k≥43.解法二、用线性规划知识求解,设过点P的直线L:y=k(x-1) 1,即kx-y-k 1=0,因点M、N在L的两侧或L上,故(k 4)(-4k 3)≤0,∴k≤-4或k≥43.解法三、设经过点P的直线L的方程为:y=k(x-1) 1……(1),而直线MN的方程为:x 5y 13=0……(2),显然k≠-51.由(1)(2)解方程组可得交点Q的横坐标为xQ=55kk- 118,由题意知,-3≤xQ≤2即-3≤55kk- 118≤…     

一道线性规划问题求解新视角

题目:若x,y满足x≥0,y≥0,2x y≤6,x 2y≤6,,求z=2x 3y的最大值·分析1变换角度,建立zoy坐标系,通过观察可行域中的横坐标z的取值范围,从而得到z的最值·解法1由z=2x 3y得x=(z-3y)/2,则(z-3y)/2≥0,y≥0,z-3y y≤6,(z-3y)/2 2y≤6,即z-3y≥0,y≥0,z-2y≤6,z y≤12,作出可行域如图1所示,由图知zm ax=10·点评线性规划问题的一般解法都是先作可行域,再平移目标函数,最后确定最优解,而上述处理,转换了视角,一步到位地将z融入在可行域中,以横坐标的定义来诠释z,使得再求z的最大值·分析2考虑其代数的结构,若用增元代换求解,可回避作图的繁琐,一…