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

“线性规划”是新教材的新增内容 .在求最优解时 ,通过平移直线的方法得出理论最优解 ,学生能理解和掌握 ;但是 ,如果要求出整数最优解 ,多数学生往往无法下手 ,屡屡出错 .针对这种情况 ,本文将就一个引例 ,介绍五种求整数最优解的方法 ,供大家参考 .为叙述方便 ,记理论最优解时目标函数对应的直线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的…     

数学问题解答

20 0 4年 1月号问题解答(解答由问题提供人给出 )1 471　求方程组 x+y =ztz+t =xy的非负整数解 .解　因为方程组中x与y ,z与t可以互换 ,所以可以先求满足 0 ≤x≤y ,0 ≤z≤t的整数解组 (x,y ,z,t) .( 1 )若x、z中有一个为零 ,不妨设x=0 ,则由原方程组消去t得 :y+z2 =0所以y =z=0 ,t= 0 .即 ( 0 ,0 ,0 ,0 )是原方程组求的一组解 .( 2 )若x ,z都不是 0 ,但是有一个为 1 ,设x=1 ,则由原方程组消去y得 :t+z=zt - 1所以 (z- 1 ) (t- 1 ) =2 ,因为z,t为正整数且z≤t,所以z - 1 =1t- 1 =2 得z=2 ,t =3,y=5即 ( 1 ,5 ,2 ,3)是原方程组的一组解 ,同…     

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

题目:若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考虑其代数的结构,若用增元代换求解,可回避作图的繁琐,一…     

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

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

用向量数量积解决线性规划应用题

<正>实际生产与生活中有许多线性规划应用问题,其一般求解步骤是:(1)根据题意,建立数学模型,作出不等式组所表示的可行域;(2)设所求目标函数f(x,y)的值为z;(3)将各顶点坐标代入目标函数,即可得到z的最大值与最小值,或求直线f(x,y)=z在y轴上截距的最大值(最小值),从而求得z的最大值与最小值;(4)检验最优解是否符合实际意义.     

一类含三角函数的初等函数取值范围问题的图象解法

一类求在给定条件下三角函数式的取值范围问题 ,已有多篇文章论及 (参见文〔1〕〔2〕〔3〕) ,但美中不足的是文中未给出如何揭示隐含条件以避免误解 .笔者发现这类问题通过构造合适的直线或圆锥曲线能充分揭示隐含条件 ,正确求解 .例 1　已知 sinα 2 cosβ=2 ,求 2 sinα cosβ的取值范围 .解　设 x=sinα,y=cosβ,t=2 sinα cosβ则有 x 2 y=2 ,2 x y=t( |x|≤ 1,|y|≤ 1) .t的取值范围即线段 x 2 y=2与平行线段 2 x y=t( 0≤ x≤ 1,12 ≤ y≤ 1)相交时 ,2 x y=t在 y轴上截距的取值范围 .由图 ( 1)易得 :当 2 x y=t通过点 B( 1,12 )时 ,t…     

线性规划中目标函数的几种类型

线性规划初步是高中教材新增内容,这类问题的典型提法是:一个目标,若干条件;典型解法是代数几何并用,确定范围,伺机求解,下面笔者将结合一些例题,谈谈目标函数的几种类型及解法.1形如z=ax by型的目标函数例1已知点P(x,y)在不等式组x-2≤0,y-1≤0,x 2y-2≥0表示的平面区域上运动,则z=x-y取值范围是()(A)[-2,-1].(B)[-2,1].(C)[-1,2].(D)[1,2].图1例1图解先画出约束条件限定的可行域(如图1阴影部分),将z=x-y化为l:y=x-z的形式,将问题化归为求直线l在y轴上截距-z的范围,由图1观察知-z的范围[-2,1],则z的范围为[-1,2],选(C).评注在线性规划中…     

例说高考线性规划最值题型的求解

线性规划是教材的新增内容,是高考命题的热点内容.对于线性规划最值题,我们应该选择怎样的方法求解呢?本文结合近几年全国各省市高考试题及模拟试题介绍三种方法,供大家参考.1.截距化归法利用化归思想,先把目标函数的代数式化成直线的截距式“y=kx b”,然后平移直线“y=kx”,在约束条件的可行区域内寻找其截距的最值:例1(2005年山东高考理科卷第15题)设x,y满足约束条件x y≤5,3x 2y≤12,0≤x≤3,0≤y≤4,则使得目标函数z=6x 5y的值最大的点(x,y)是.图1例1图解原目标函数代数式可化为y=-65x 5z,依题意,作出约束条件的可行区域,如图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 ,易知当该直线ｌ在ｙ轴…     

数学问题解答

1999年11月号数学问题解答(解答由问题提供人给出)1221.求方程组x y z=3x3 y3 z3=3的所有整数解.解　原方程组化为x y=3-z(1)x3 y3=3-z3(2)(1)3-(2),得3xy(x y)=24-27z 9z2(3)(1)代入(3),可得xy=8-9z 3z23-z(4)由(1)、(4)知x、y是以下二次方程的两个整数根:t2-(3-z)t 8-9z 3z23-z=0解得t1,2=3-z±(z-1)2·z 5z-32=3-z±(z-1)2(1 8z-3)2(5)由此知,x、y、z均为整数当且仅当z-1=0或z-3=1或z-3=-8,即z=1或z=4或z=-5.将其依次代入求根公式(5),得原方程组的所有整数解(共四组):x=1y=1z=1或x=-5y=4z=4或x=4y=-5z=4或x=4y=4z=-5注:(5)式中根号内的(z…     

极端法解一类对称不定方程问题

<正>我在做竞赛题时体会到,一些对称的不定方程可以用极端的方法解决.这种方法很有代表性,为突出方法的重要性,例题都选自自主招生的真题.例1(2012年清华保送生考试)求不定方程1/x+1/y+1/z=1的所有正整数解(x,y,z).解不妨设x≤y≤z,由对称性,先令x=y=z,则x=3,于是只有:x=2或x=3,当x=     

用点到直线距离公式解决与函数相关的问题

点P(x,y)到直线Ax By C=0距离为d=|Ax By C|/A~2 B~2,当P(x,y)在函数y=f(x)上时,该公式变为d=|Ax Bf(x) C|/A~2 B~2,本文通过引进函数y=f(x),借助该公式解决一些与函数相关的问题.1.求函数单调性例1求f(x)=|x 2-1-x2|的单调区间及单调性.分析把函数f(x)作为点线间距离,借助图象,看x变大时,该距离如何变?图1例1图解函数的定义域是-1≤x≤1,令y=1-x2,即x2 y2=1,y≥0.如图1,所以f(x)=|x 2-y|=|x 2-y|2×2,几何意义:半圆上动点M(x,y)到定直线l:x-y 2=0的距离的2倍.由图1知使OB⊥l时,B到l的距离最小,显然OB:y=-x,由x2 y2=1,(y≥0),y=-x,…     

新题征展(30)

A　题组新编1 .( 1 )对任意的 x∈ [- 1 ,1 ],函数 f( x)= x2 - ( k 1 ) x 4的值恒大于 0 ,求实数 k的取值范围 ;( 2 )对任意的 k∈ [- 1 ,1 ],函数 f ( x) =x2 - ( k 1 ) x 4的值恒大于 0 ,求实数 x的取值范围 .2 .( 1 )过点 P( 3,1 )作直线 l交 x、y轴正方向于 A、B点 ,求使△ AOB面积最小时直线l的方程 ;( 2 )过点 P( 3,1 )作直线 l交 x轴正方向于 A,交直线 y =2 x于 B,求使△ AOB面积最小时直线 l的方程 ;( 3)过点 P( 3,1 )作直线 l分别交直线 y= - x - 2与 y =2 x 1于 A、B,且 O′为这两条直线的交点 ,求使△ AO′B面…     

一个三角函数的最小上界

文[1]提出如下问题,设x,y,z∈R,m∈N,m≥3,求u=sinmxcosy sinmycosz sinmzcosx的最小上界.这里最小上界显然为函数的最大值.本文用微分法给出m=3,4时u的最大值,当m=5,6时给出一个初步结果.因sinmxcosy sinmycosz sinmzcosx≤|sinx|m|cosy| |siny|m|cosz| |sinz|m|cosx|,所以只须在0≤x,y,z≤π2上讨论(1)的最大值,这完全等同于讨论函数f(x,y,z)=(1-x2)2my (1-y2)2mz (1-z2)2mx(0≤x,y,z≤1)(1)的最大值.设(1)的最大值为Am,一元函数g(x)=f(x,1,0)=(1-x2)2m x(0≤x≤1)的最大值为Bm,显然有Am≥Bm.引理1函数f(x)=(1-x2)2m x(0≤x≤1,m≥3,m…     

错在哪里

问题　已知函数 y =ax2 6 x bx2 1 对于一切实数 x都有 {y| 1≤ y≤ 9},求实数 a、b的值 .不少学生 (还有部分老师 )是这样解的 :∵　函数 y =ax2 6 x bx2 1 的定义域为R,于是 ( y - a) x2 - 6 x y - b =0 ,当 y≠a,由Δ≥ 0 ,得 36 - 4( y - a) ( y - b)≥ 0 ,即y2 - ( a b) y ab - 9≤ 0 ( 1 )又 1≤ y≤ 9,即 y2 - 1 0 y 9≤ 0 ( 2 )而不等式 ( 1 ) ( 2 )同解 ,∴　 a b =1 0 ,　 ab - 9=9,∴　 a =5 7,b =5- 7,或　 b =5 7,a =5- 7;当 y =a时 ,结论也成立 .剖析　这道题与《中学数学》(湖北 ) 1 999年增刊 P1 …     

求最大最小值的一些方法

求最值,有一些常规方法,例如用二次函数、不等式、三角函数来解决问题.但遇上某些问题时,利用这些方法不甚方便,我们就应寻找另外一些方法了. 1.利用条件区域求最值 这种方法就是据题目中所给定的变量范围,在直角坐标系中画出条件区域,进而采用线性规划的方法求出所给表达式的最值.(含数形结合的思想) 例1 设x、y、z满足条件x y十z=1,0≤x≤1,0≤y≤2,3y z≥2,求f(x、y、z)=     

建立曲线切线方程及平面图形面积公式又一方法

<正> 通原点在第一象限取一段直线y=mx,m>0,x∈〔0,r_1〕。这函数具有特点:①它把x 轴上一段x∈〔0_1 r_1〕映满y 轴上一段y∈〔0,r_2=mr_1〕.②函数为严增:即当0≤x_10或y=ax~3,其中x∈〔0,r_1〕,则y∈〔0_1 r_2〕,都保留映满严增的     

综合题新编选登

题164下面玩掷骰子放球游戏,若掷出1点,甲盒中放一球;若掷出2点或3点,乙盒中放一球;若掷出4点、5点或6点,丙盒中放一球.设掷n次后,甲、乙、丙各盒内的球数分别为x,y,z.1)当n=3时,求x,y,z成等差数列的概率;2)当n=6时,求x,y,z成等比数列的概率:解1)∵x y z=3,2y=x z.①x=0,y=1,z=     

智慧窗

1.巧求值设x+y+x=0,xyz≠0,求的值.2.巧解方程组解关于z,y,z的方程组     

应用题新编选登

题1　某企业有一条价值a万元的生产流水线,要提高该生产流水线的生产能力,提高产品的增加值,就要对流水线进行技术改造,假设增加值y万元与技改投入x万元之间的关系满足1y与(a- x)x2 成正比例.2当x =a2 时,y=a32 .30≤x2 (a- x)≤t,其中t为常数且t∈[0 ,2 ].1)设y=f(x) ,求出f(x)的表达式,并求其定义域;2 )求出增加值y的最大值,并求出此时的技改投入x值.解　1)设y=f (x) =k(a- x ) x2 ,因当x =a2时,y=a32 .故a32 =k(a- a2 ) (a2 ) 2 ,∴k=4 ,从而有y=4 (a- x) x2 .因0≤x2 (a- x) ≤t,解得0≤x≤2 t1+ 2 ta,于是f(x) =4 (a- x) x2 (0≤x≤2 t…