线性规划模板(10篇)

导言：作为写作爱好者，不可错过为您精心挑选的10篇线性规划，它们将为您的写作提供全新的视角，我们衷心期待您的阅读，并希望这些内容能为您提供灵感和参考。

篇1

线性规划的研究内容可归纳为两个方面：一是系统的任务已定，如何合理筹划，精细安排，用最少的资源（人力、物力和财力）去实现这个任务；二是资源的数量已定，如何合理利用、调配，使任务的完成数最多.

“线性规划”在知识的整合、解题思路的拓展、方法的迁移等方面都有其鲜明的特点，有着丰富的思想内涵. 挖掘题中条件，不失时机地运用“线性规划”的思想方法解题，将使我们观察思考问题的立意更高，视野更加开阔.

“线性规划”问题的教学现状

在中学教材中，称求目标函数在线性约束条件下的最大值或最小值的问题为线性规划问题. “线性规划”的教学分为三个层次：

（1）二元一次不等式表示的平面区域；

（2）二元一次不等式组表示的平面区域；

（3）线性目标函数在约束条件下的最值.

只含有两个变量的简单线性规划问题可用图解法来解决.

例如：设实数x，y满足0≤x≤1，0≤y≤2，2y-x≥1，则z=2y-x+4的最大值是__________.

上述问题可转化为一个平面区域与一条直线在有公共点的前提下，结合z的几何意义来求解.

具体教学过程中，学生感觉有困难的部分是作图环节，体现在速度慢，不够准确. 如何准确有效地作出所需图形，应给予学生充分的指导、训练和体验. 学生作图时会出现过于细致的问题，如逐步描绘坐标系刻度；又或出现过于轻率的问题，连图形的形状和基本特征都无法抓住.这两个问题都使解题的速度和准确性大打折扣.

当然，线性规划是一个比较深入的课题，教材中也介绍了更多变量的线性规划问题，可引导学生进一步学习.

线性规划问题的考查特点与趋势

1. 转化成基本线性规划问题

常规考题考查知识与技能，但还需要学生有一定的转化和化归意识，命题者会在行文叙述、符号变化、算式特征等方面设置一定障碍，需要解题者对得到的信息加工出熟悉的数学模型.

例1 （江苏2013年9题）抛物线y=x2在x=1处的切线与两坐标轴围成三角形区域为D（包含三角形内部和边界）. 若点P（x，y）是区域D内的任意一点，则x+2y的取值范围是__________.

分析：本题以抛物线的切线为背景，以文字叙述的方式提供了可行区域，题中曲线切线利用导数可得.

解决：求导得y′=2x，切线方程为y=2x-1 ，转化为等价的基本问题：约束条件为x≥0，y≤0，y≥2x-1，目标函数z=x+2y. 作出图形，易知z的取值范围为-2，.

例2 设实数x，y满足3≤xy2≤8，4≤≤9，则的最大值是__________.

分析：如何将其化归成基础问题，找到未知问题和基本题之间的桥梁是破解的关键.

解法一：整体代换，令xy2=m，=n，

那么==，转化为等价问题：约束条件为3≤m≤8，16≤N≤81.目标函数为z=，z几何意义为对应区域内动点与坐标原点连线的斜率，易得最大值为27.

解法二：将除法转变为和或差，题中代数式两边都取以2为底的对数，令log2x=A，log2B=y. 转化为等价问题：约束条件为log23≤A+2B≤3，2≤2A-B≤2log23，目标函数为z=3A-4B，可行区域如图，容易求得z的最大值为3log23，那么=2z的最大值是27.

图2

点评：解法一采用了整体换元，解法二采用了取对数化积为和、化除为差，通过转化和化归转化成已经解决过的基本问题.

2. 线性规划问题的拓展延伸

（1）线性规划问题中目标函数的拓展

熟悉线性规划基本题还远远不够，深刻把握它的数学特点和数学思想，在实际处理问题中将未知问题转化为基本题才更重要. 那么该类问题的基本特点是什么，常见问题是什么？只有清楚这些，我们才能在实际处理过程中及时、敏锐地转化问题，达到解决问题的目的.

以下提供最常见的基本类型；

约束条件：实数x，y满足y≤x，y≥0，2x-y≤2，可行区域如图3.

图3

目标函数（1）：z=3x+y的最大值是__________，z的几何意义即直线y=-3x+z的纵截距；

目标函数（2）：z=的最大值是__________，z的几何意义即可行区域内动点P（x，y）与点（-1，0）所连直线的斜率；

目标函数（3）：z=的最大值是__________，z的几何意义即可行区域内动点P（x，y）与点（0，1）之间的距离.

与线性规划相关的问题普遍具有一些基本特征，主要表现为已知条件是含“双变量”的不等关系，目标任务为代数式的最值或取值范围问题. 可解决的目标函数也不一定是线性代数式，可以为其他类型.常见的可以为乘积或比值形式、二次或根式形式，甚至可以用向量等给出的代数式. 也不一定拘泥于目标函数的最值问题，也可成为以可行区域为背景的面积、向量、概率等问题.

（2）线性规划问题中约束条件的拓展

我们可以将它的数学思想拓展得更宽. 约束条件不一定要是线性约束条件，相应的平面区域也可以为直线、圆、曲线等构成的复合形态.

例如：实数x，y满足x2+y2=1，则x+y的最大值是__________.

此题可行区域可认为是圆，可视为曲线圆与直线x+y=m有公共点. 由此看来，约束条件的给出有了更大的空间，线性规划这个知识点也更容易渗透到其他数学知识点中.

例3 若a>0，b>0且+=1，则a+2b的最小值为__________.

分析：题目涉及两个变量的等量关系，可以考虑减元处理，已由代数式整理得a=-b++1，结合基本不等式解决a+2b的最小值；也可以考虑其几何意义，视作以b为自变量的函数，那么P（b，a）为函数图象上的每一个点.

图4

解决：a=-b++1，令z=a+2b，z表示此直线的纵截距.当直线与曲线相切时z最小，此时a′=-2.求导a′=-1-，所以b=，a=-++1=+，所以a+2b=+.

例4 （江苏2012年14题）已知正数a，b，c满足：5c-3a≤b≤4c-a，clnb≥a+clnc，则的取值范围是__________.

分析：此题和基本问题的相似度极高，已知条件含有3个变量，而且目标函数为比值形式，有明确的几何意义. 由代数式clnb≥a+clnc的逻辑计算知ln≥，由此得到转化的突破口，可转化为两个变元.

图5

解决：已知两个不等式同除c得到5-3≤≤4-，ln≥.记=x，=y，

转化为等价问题：

约束条件为x，y>0，5-3x≤y≤4-x，lny≥x？圳y≥ex，目标函数k==.

作出图形，利用导数求出曲线y=ex过坐标原点的切线为y=ex，发现切点T（1，e）在可行区域内. 综上，直线y=kx过C点时k最大，与曲线y=ex相切于点T时k最小. 所求取值范围为[e，7].

图6

点评：三变量的问题转化为两变量问题，该问题的解决具有一定的代表性.由已知代数式还可以考虑同除a或b进行转化，不是每一个转化都适合，但有些转化又是相通和可行的，因此求解时需要一定的尝试和观察.

3. 线性规划问题的知识迁移

有些数学问题并无明显的线性规划痕迹，却也可以转化成线性规划的基本问题，比如解析几何、函数、数列等含有多个变量的数学问题可采用线性规划的方法来求解. 以下试题立足于课本，但高于课本，题目充分体现了命题教师的高瞻远瞩，而反过来又对高中的教学提出更高要求.

例5 （江苏2011年14题）设集合A=（x，y）≤（x-2）2+y2≤m2，x，y∈R，B={（x，y）2m≤x+y≤2m+1，x，y∈R}，若A∩B≠，则实数m的取值范围是__________.

分析：两集合为点集，交集非空.思考难度超越课本，类比线性规划，将其转化为两个平面区域有公共点，同时本题的计算量大.

解决：集合A对应区域为D1，集合B对应区域为D2，D2容易认识为两平行直线确定的带状区域. 由区域D1非空可知m2≥，求得m≤0或m≥.

（1）m=0区域D1收缩为一点，容易判断不满足要求；

（2）m≠0区域D1又分为两种情况，当m0时表示两个同心圆确定的环形区域.不论哪种情况，要满足题意，只需要保证圆（x-2）2+y2=m2和直线x+y=2m或直线x+y=2m+1其中之一有公共点. 圆心到两直线距离分别为d1和d2，且d1=，d2=. 所以d1≤r=m或d2≤r=m，容易解得m∈1-，2+，综合以上分析，实数m的取值范围是，2+.

点评：问题描述采用了几何语言，解决思路和线性规划有类似之处，同时解析几何背景很强，充分考查了直线和圆的位置关系，而且分析时利用分类讨论细化，处理时又不讨论集中解决，思维跳跃度很大.

例6 已知a，b为常数，a≠0，函数f（x）=a+ex. 若f（2）

分析：此题仅仅从表象上看到已知条件对变量a，b作了限制，与线性规划知识点的相关性相当隐蔽. 该题目变量的关系相互依赖性较强，关键从已知条件合理的抽离出最有效约束条件.

图7

解决：由f（2）

点评：g（x）=ax2+bx-b≥0恒成立分析较难，考虑不等式成立的必要条件攻克了这个难点，根据代数式的依存关系得到约束条件，画出图形，所求面积视为两个三角形面积差.

以上可以看出这些问题和教材中很多知识点综合，都需要学生具备良好的知识迁移能力. 包括高考在内的众多考题都或多或少地含有线性规划知识或思想的若干部分，这样的考题都具备一定的难度，成为命题的热点题型，在考试中层出不穷.

篇2

线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中,提高经济效果是人们不可缺少的要求,而提高经济效果一般通过两种途径:一是技术方面的改进,例如改善生产工艺,使用新设备和新型原材料.二是生产组织与计划的改进,即合理安排人力物力资源.线性规划所研究的是:在一定条件下,合理安排人力物力等资源,使经济效果达到最好.一般地,求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题.满足线性约束条件的解叫做可行解,由所有可行解组成的集合叫做可行域.决

策变量、约束条件、目标函数是线性规划的三要素.而此类问题在课本中已经有了很多体现,在此笔者不再赘述.本文中,笔者想叙述线性规划应用的一种情况,就是用线性规划的方法解决一类概率问题.此类概率问题一般是几何概率的问题.

请看下面两例:

例1.甲、乙两人约定在6时到7时之间在某处会面,并约定先到者应等候另一人一刻钟,过时即可离去.求两人能会面的概率.

稍加分析我们不难发现,本题中显然不是一个变量,而是两个变量,即甲、乙各自到达约会地点的时间,所以可以假设两个变量.那么可以在平面直角坐标系内用x轴表示甲到达约会地点的时间,y轴表示乙到达约会地点的时间,用0分到60分表示6时到7时的时间段,则横轴0到60与纵轴0到60的正方形中任一点的坐标(x,y)就表示甲、乙两人分别在6时到7时时间段内到达的时间.而能会面的时间由x-y≤15

所对应的图中阴影部分表示.

反思说明:

(1)三角形三边长度都是在0到l之间,故每一对结果对应三条边长,分别用x,y轴上的数表示,则每一个结果(x,y)就对应于图中三角形内的任一点;

(2)找出事件A发生的条件,并把它在图中的区域找出来分别计算面积即可;

(3)本题的难点是把三条边长分别用x,y两个坐标分别表示,构成平面内的点(x,y),从而把边长是一段长度问题转化为平面图形中的线性规划问题,转化成面积为测度的几何概型的问题.

但是对于类似问题我们一定要注意是否是以面积为测度的概率问题,有些仍然是古典概率,如下例:

例3.如下图,从某学校高三年级共800名男生中随机抽取50名测量身高,测量发现被测学生身高全部介于155cm和195cm之间,将测量结果按如下方式分成八组:第一组[155,160)、第二组[160,165)、……第八组[190,195),下图是按上述分组方法得到的频率分布直方图的一部分,已知第一组与第八组人数相同,第六组、第七组、第八组人数依次构成等差数列.若从身高属于第六组和第八组的所有男生中随机抽取两名男生,记他们的身高分别为x、y,求满足x-y≤5的事件概率.

篇3

常规的线性规划问题求最优解，要明确线性规划问题求解的基本步骤，即在作出可行域，理解目标函数z的意义的基础上，通过平移目标函数所在直线，最终寻求最优解.

例1 （2015年陕西）某企业生产甲、乙两种产品均需用A，B两种原料.已知生产1吨每种产品需原料及每天原料的可用限额如表所示，如果生产1吨甲、乙产品可获利润分别为3万元、4万元，则该企业每天可获得最大利润为（ ）.

A.12万元 B.16万元 C.17万元 D.18万元

甲乙原料限额A（吨）3212B（吨）128

解析 设该企业每天生产甲、乙两种产品分别为x、y吨，则利润z=3x+4y，

由题意可列3x+2y≤12，

x+2y≤8，

x≥0，

y≥0，该不等式组表示的平面区域如图1所示阴影部分：

图1

易知目标函数z=3x+4y所在直线y=-34x+z4过点A（2，3），即x=2，y=3时，z取得最大值，zmax=3×2+4×3=18，故选D.

实际问题涉及的线性规划问题求解，不同于纯数学形式的线性规划问题，尤其最优解，要遵循实际问题所在的意义.类似教材中钢板张数，人力资源分配，车辆配备等问题要寻求最优整数解等，都不同于一般的数学求实数解问题，这在求解过程中尤其注意.

练习 （2015年天津）设变量x，y满足约束条件x+2≥0，

x-y+3≥0，

2x+y-3≤0，则目标函数z=x+6y的最大值为（ ）.

A.3 B.4 C.18 D.40

（答案C.）

2 线性规划问题中的参数求解

在线性规划问题中，常常遇到借助于不等式组，或者目标函数设置一些参数，利用已知的目标函数z的最值，来求出参数值的题目.这类线性规划问题的求解，方法上仍要遵循线性规划问题的求解步骤，但在求解中涉及到分类讨论，数形结合等数学思想.

例2 （2015年山东）已知x，y满足约束条件x-y≥0，

x+y≤2，

y≥0. 若z=ax+y的最大值为4，则a=（ ）.

A.3 B.2 C.-2 D.-3

图2

解析 由z=ax+y得y=-ax+z，借助图形2可知：

当-a≥1，即a≤-1时，在x=y=0时有最大值0，不符合题意;

当0≤-a<1，即-1<a≤0时，在x=y=1时有最大值a+1=4，a=3，不满足-1<a≤0;

当-1<-a≤0，即0<a≤1时，在x=y=1时有最大值a+1=4，a=3，不满足0<a≤1;当-a<-1，即a>1时在x=2，y=0时有最大值2a=4，a=2，满足a>1;故选B.

本例中参数a在目标函数所在直线方程中的意义与斜率有关，即直线的斜率k=-a，故如何利用条件中的函数最大值4求参数a成为解题关键，或者说目标函数所在直线经过不等式组所示区域的哪一点取到最大值成为参数a分类讨论的依据.

3 非线性目标函数的最值求解

在线性规划问题中，我们常常会遇到一些非线性目标函数的求解问题.

例3 （2015年四川）设实数x，y满足

2x+y≤10，

2+2y≤14，

x+y≥6，

则xy的最大值为（ ）.

A.252 B.492

C.12 D.14 图3

解析 不等式所示平面区域如图3，

当动点（x，y）在线段AC上时，此时2x+y=10，据基本不等式知道，非线性目标函数z=xy=12（2x・y）≤12（2x+y2）2=252，当且仅当x=52，y=5时取等号，对应点落在线段AC上，故最大值为252，选A.

本例中，目标函数z=xy，借助于直线方程2x+y=10，通过变形xy=12（2x・y）联想到不等式2x・y≤（2x+y2）2，从而找到目标函数xy的最优解.类似非线性目标函数x2+y2，y-bx-a等形式都要在理解函数意义的基础上寻求最优解.

练习 （2015年新课标卷）若x，y满足约束条件x-1≥0，

x-y≤0，

x+y-4≤0， 则yx的最大值为 .

（答案3.）

4 线性规划问题的综合运用

有些数学问题如果转化为线性规划问题会得到简捷的解法，当然这要求对问题有着较深刻的理解，要善于利用转化和划归思想转化为线性规划问题.

例4 （2015年浙江理科）若实数满足x2+y2≤1，则|2x+y-2|+|6-x-3y|的最小值是 .

解析 条件x2+y2≤1表示圆x2+y2=1及其内部，易得直线6-x-3y=0与该圆相离，故|6-x-3y|=6-x-3y，设函数z=|2x+y-2|+|6-x-3y|，

当2x+y-2≥0时，则x2+y2≤1，

2x+y-2≥0，所示平面区域如图4所示，可行域为小的弓形内部，易知目标函数z=|2x+y-2|+|6-x-3y|=x-2y+4，

故目标函数z=x-2y+4所在直线y=12x-z2+2过点A（35，45）时z最小，即x=35，y=45时，zmin=4;

图4

当x-2y+4<0时，z=|2x+y-2|+|6-x-3y|=8-3x-4y，可行域为大的弓形

内部，同理可知目标函数z=8-3x-4y所在直线y=-34x-z4+2过点A（35，45）时z最小，当x=35，y=45时，zmin=4.

篇4

一、面积问题

1、(全国卷)在坐标平面上,不等式组y≥x-1y≤-3x+1所表示的平面区域的面积为_________。

解析:原不等式组去掉绝对值后转化为两个不等式组,画出平面区域,根据三角形面积公式求得答案。

二、最值问题

2、(全国卷)若x,y满足约束条件x+y≥0x-y+3≥00≤x≤3则z=2x-y的最大值为____________。

解析:z=2x-y的几何意义是斜率为2的直线的纵截距的相反数,在坐标平面上画出可行域,可得结果。

x,y满足x-y-2≤0x+2y-4>02y-3≤0则的最大值是________。

3、(江西)设实数

解析:在坐标平面上画出可行域z==的几何意义是两点O(0,0)A(x,y)连线的斜率,画图可知,在点(1, )时z最大,故所求最大值为。

4、教材第二册(上)第99页 第5题

解析:由问题的形式联想到两点间距离公式,从而利用线性规划的思想去解决。上述几题中的约束条件是以不等式的形式出现,有时以方程形式给出,如教材第二册(上)第99页 第6题

方法提炼:

①解决线性规划问题,首先找到线性约束条件,画出可行域;线性约束条件可能是关于x、y的不等式(组)或方程(组)。

篇5

这个参数往往与直线的斜率有关系，并且已知最优解，因此解题时可充分利用斜率的特征加以转化。

1.目标函数中的系数为参数

例1、(2009年陕西理11)若x，y满足约束条件x+y?叟1x-y?叟-12x-y?燮2，目标函数z=ax+2y仅在点（1，0）处取得最小值，则a的取值范围是（ ）

A. (-1,2) B. (-4,2) C. (-4,0) D.(-2,4)

分析：明确a的几何意义，与直线的斜率有关，根据图形特征确定怎样才能保证仅在点（1，0）处取得最小值。

解：作出约束条件所形成的区域图形，目标函数化成y=-■x+■，则斜率k=-■，截距为■，要使截距最小，则-1

2.目标函数中的系数为参数

例2 (2006湖北理) 已知平面区域D由以A(1，3)，B(5，2)，C(3，1)为顶点的三角形内部和边界组成，若在区域D上有无穷多个点(x，y)可使目标函数z=x+my取得最小值,则m=（ ）。

A.-2 B.-1 C.1 D.4

分析：最优解有无穷多个，往往是指目标函数与其中一条直线重合，此外要注意到参数为或的系数上的不一致。

解：要使目标函数z=x+my的最优解有无穷多个，则直线z=x+my应与直线AC或AB，BC重合，但要使目标函数Z=X+my取得最小值，必须使得函数斜率为负值，且斜率的绝对值要大，从而只能与直线AC重合，则-■=kAC=-1，所以m=1，选C。

3.目标函数中x,y的系数均为参数

例3 (2009年山东理12) 设x，y满足约束条件3x-y-6?燮0x-y+2?叟0x?叟0,y?叟0，若目标函数z=ax+by，(a>0,b>0)的值是最大值为12，则■+■的最小值为( )。

A.■ B.■ C.■ D. 4

分析：本题综合地考查了线性规划问题和由基本不等式求函数的最值问题.要求能准确地画出不等式表示的平面区域,并且能够求得目标函数的最值,对于形如已知2a+3b=6,求■+■的最小值常用乘积进而用均值不等式解答。

解：不等式表示的平面区域如图所示阴影部分,当直线z=ax+by(a>b,b>0)过直线x-y+2=0与直线3x-y-6=0的交点A(4,6)时,目标函数z=ax+by(a>0,b>0)取得最大12,4a+6b=12,即2a+3b=6,而■+■=(■+■)■=■+(■+■)?叟■+2=■,故选A。

二、约束条件中含有参数

约束条件中某一个约束条件含有参数，意味着约束条件是变动的，这种变动导致了目标函数最值的变动。

1.已知目标函数最值，求参数的值

例4 （2010年浙江理7）若实数，满足不等式组x+3y-3?叟0，2x-y-3?燮0，x-my+1?叟0，且z=x+y的最大值为9，则实数m=（ ）。

A.-2 B.-1

C.1 D.2

分析：已知目标函数的最值求参数的值，关键是找到最优解，代入到目标函数中，求出参数的值。

解：不等式组表示的平面区域如图中阴影所示，把目标函数化为y=-x+z，则当直线y=-x+z过A点时z最大，由2x-y-3=0，x-my+1=0，得到A(■，■)，代入目标函数得■+■=9，所以m=1。

2.已知目标函数最值范围，求参数的范围

例5 (2011年高考湖南卷理科7)设m>1，在约束条件y?叟xy?燮mxx+y?燮1下，目标函数Z=x+my的最大值小于2，则m的取值范围为

。

分析：本题关键是理解参数的几何意义是直线的斜率，找到关于m的一个不等式。

篇6

1． 当变量x，y满足约束条件x≥0，y≤x，2x+y+k≤0时（k为常数），能使z=x+3y的最大值为12的k为（）

3． 如果实数x，y满足条件x－y+1≥0，y+1≥0，x+y+1≤0，那么2x－y的最大值为（）

A． 2?摇?摇?摇?摇?摇?摇 B． 1 ?摇?摇 C． －2?摇 ?摇?摇?摇?摇?摇D． －3

4． 已知2x+y－2≥0，x－2y+4≥0，3x－y－3≤0，则x2+y2的最大值与最小值分别是（）

A． 13，1 B． 13，2

5. 已知三点A（x0，y0），B（1，1），C（5，2）.如果一个线性规划问题的可行域是ABC的边界及其内部，线性目标函数z=ax+by在点B处取得最小值3，在点C处取得最大值12，则下列关系成立的是（）

A. 3≤x0+2y0≤12

B． x0+2y0≤3或x0+2y0≥12

C． 3≤2x0+y0≤12

D． 2x0+y0≤3或2x0+y0≥12

7． 在约束条件x≥0，y≥0，y+x≤s，y+2x≤4下，当3≤s≤5时，目标函数z=3x+2y的最大值的变化范围是_______．

以上题目从多角度考查了线性规划的相关知识，同学们只要抓住解线性规划题的本质就不难解决．

1. 首先要能正确画出可行域（可借助特殊点法来确定二元一次不等式表示的区域）；

2. 然后利用平移法找到所要求的最值（可借助直线的斜率来帮助判断最值点），此外还要注意目标函数的几何意义（除了通常的截距外还可能转化为两点间距离，斜率等）；

3. 最后在解实际问题时一定要仔细读题，然后根据条件列出线性约束条件和目标函数，这以后的步骤就用1、2两点的方法来解决．

同学们在解此类题目时，不管题目如何变化，只要按照所讲的步骤一步步进行下去，这些问题都会迎刃而1． B

2． A

3． B

篇7

1数学模型

线性规划问题通常表示成如下两种形式:标准型、规范型。

设jj(2…，n)是待确定的非负的决策变量；认2…，n)是与决策变量相对应的价格系数；K2…mj=l2…n)是技术系数；b(i12…，m)是右端项系数；

线性规划是运筹学最基本、运用最广泛的分支，是其他运筹学问题研究的基础。在20世纪50年代

到60年代期间，运筹学领域出现许多新的分支：非线性规划（nonlinearprogranming、商业应用（crnxmereialpplieation、大尺度方法(laresealemeh-Qd)随机规划（stochasticPKgiamniig)、整数规划(ntegerprogramming)、互补转轴理论（amplmentaiyPivotheor)多项式时间算法（polynomialtjneagatm)等。20世纪70年代末，上述分支领域都得到了极大发展，但是却都不完善。而且数学规划领域中存在许多Nfkhard问题，如TP问题，整数规划问题等。这些问题的基本模型都可以写成线性规划形式，因此通过对线性规划算法的进一步研究，可以进一步启发及推动数学规划领域内其他分支的发展。

2边界点算法

由于单纯形法与基线算法都是在可行集的边界上取得最优值，故合称单纯形法与基线法为边界点算法。单纯形法是线性规划使用最早也是目前实际应用中最流行和求解新型规划问题最有效的算法之一。它实施起来相当简单特别对中小规模问题效果显著。单纯形法最早是由Damzg于1947年夏季首先提出来的。1953年Dantzig为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法12。1954年美国数学家CELmH3针对对偶问题提出一种在数学上等价于用改进单纯形法求解的对偶线形规划。1974年CuretN41提出了求解一般线性规划问题的原对偶单纯形法，该算法与对偶单纯形法类似，但是原对偶单纯形法允许我们从一个非基础对偶可行解开始算法求解。

1972年Klee等举例证明了单纯形算法的时间复杂性有可能是指数型。1973年，Jeoslowoi和Zdeh7又分别进一步指出常用的对偶单纯形法、原一对偶单纯形法等都是指数级的。

这就让人们产生两个疑问:①是否存在单纯形法的某种改型，用它求解线性规划问题是多项式时算法。

对于问题①，研究者们对单纯形法采用了一系列改进技术如数据的预处理方法、更好的退化性处理、更好的局部价格向量计算、原一对偶最速下降边算法的应用、更快和更稳定的矩阵分解、更好的Cach存贮的应用、以及阶段1和阶段2的组合算法等。但是仍未能从理论上证明线形规划算法是多项式时间的。

近年来国内也出现了一批致力于线形规划算法研究的学者，但是国内学者的研究主要集中在对单纯形法的突破研究上，如基线法|8_'最钝角原理1111等。

最钝角及投影主元标算法都是针对单纯形算法存在退化现象就如何选择最优入基、离基做出的一系列研究及改进。退化现象是单纯形法一直以来需解决的难题，为了克服退化问题许多学者提出了有限主元规则：扰动法、字典序规则、Blad规则1171等，其中Bind规则由于其简单而备受关注，但是这些有限主元规则的实际应用方面并不令人满意，甚至都不能和Dantzg规则相比。1990年，潘平奇教授在文献[11]给出了线性规划问题最优基的一个启发式刻画特征:最钝角原理。最钝角原理是引人反映目标梯度与约束梯度夹角大小的“主元标”乍为确定变量进基优先性的依据，潘教授的数值试验11819表明此规则明显优于Bland规则。然而潘的方法仅适用于只含不等式约束的线性规划问题。为便于求解标准线性规划问题，许多学者在其基础上又提出了对偶主元标法。由于对偶主元标法是利用严格互补松弛来推导过度的，针对这一问题，又有学者提出了投影主元标法。

除此之外还有一系列最钝角原理在非人工变量两阶段算法1M21及亏基情况下的应用研究。这些研究表明，最钝角原理是克服单纯形法退化的一种有效方法。

基线算法的概念是1996年阮国桢教授提出来的1891，这种算法是单纯形法的发展，名字由来一方面是相对单纯形法（基点法）提出，另一方面是使用

基线算法的主要思想是：

其中疋FTX1;eRbERm为一个m阶单位矩阵。n是问题的维数，m是约束个数。把目标函数v=ff作为一个约束，看作参数。

Stef!以任意：>0所对应的变量作为进基变量，则x所在的列与单位矩阵一起构成了一个可行基B改写八=[N马，相应地改写X为[xrxo’，x为非基变量，x为基变量。于是方程组AX=[vb’可以写成Nx+Bx^Evl]’=a0+^0VStep求B1，以B1左乘，得B^1N^N+3B=B1[v]’=矿a0+B1⑷v

(2.1)

令a=B1a。，p=B-1仏则式（21河写作

Sep对任意巨{01，…，m}，令aA^vs0

计算出当前基线表对应的可行值区间[J-”。若h

…，n-L贝IJv为最优值，或者转SteP4

Sep旋转基表，更新BaP旋转基表时通常只使用有限软上界行的负可旋主元。对于负可旋主元的选择主要实现方法有：最大负主元算法[221，行列最好主元算法[231,保硬主元算法[24251等。

基线算法操作简单迭代次数少，求解速度快。相对单纯形法来说，单纯形法最多能搜索与当前极点相邻的n个极点，而基线算法能搜索11个二维面，这是基线算法能够快速求解LP问题的关键所在。

发展至今，基线算法已有其对偶算法[271，群部分算法['目标规划[29301,锥上算法[311等一整套的理论基础和一系列具体的快速实现算法12632,围绕着是否存在着多项式的基线算法，在计算复杂度方面作深入的研究将对线性规划的发展具有十分深远的意义。

3割平面法

线性规划算法中割平面思想的应用主要是指椭球法。1979年Khanchiaii33!改进Yudin和Nan-

ovski等[34]为凸规划开发的椭球法，获得了一个求解线形规划的多项式时间算法:椭球法。对问题②做出了明确回答。不同于单纯形法从一个基础可行解开始迭代，椭球法的特点是求解过程的每一阶段都有一个以某一点为中心的椭球，迭代是从一个包含最优解的较大的椭球迭代到包含最优解的较小的椭球直至逼近最优解。

为线性规划问题式（1.2)的规模。其中，lg]是以2为底的对数，「?]表示刚刚大于括号值的整数。则椭球法的时间复杂度为OML)

Khachiar椭!球法的主要思想是：

根据线性规划的强对偶定理，线性规划问题式(1.2)可以转为下列求可行域问题：

2)从球开始，这个球大到包括式（3l1)的所有可行集X不断构造一系列椭球，第k次迭代的椭球为Ek检验椭球中心&是否满足约束条件；若满

足则停止，否则利用割平面球的半椭球$Ek=EH

{aTA构造新的椭球更新椭球Ek+1为包含半椭球的最小体积椭球。按照这种算法下去直到椭球中心位于目标集内，椭球中心即为问题式（31)的解;否则椭球体积太小以至不含问题式（31)的可行解。

由于Khachiarn椭球法从构造包含可行域的大

的椭球出发，初始椭球体积有可能是天文数字，而且KhanCir椭球法利用K-K-T条件将原规划问题转

化为可行域求解问题，扩大了求解规模的同时加入了等式约束，使得可行集体积为零。虽然求解时，对等式进行摄动，可行集体积仍然很小。初始椭球体积太大，最终椭球（包含可行集的最小椭球）体积又几乎为零，算法可能需要经过非常大的迭代步数才能收敛。而且如果对偶问题无界则原问题不可行，因此当计算结果无解时不能判断是原问题无界呢还是原问题不可行。

不少研究者从加大每次迭代后椭球缩小比出发，提出了许多KhanCirn椭球法的改进算法:深切害J(deepeus)35-37、替代切割（surrogatecuts)381、

平行切割（paUMeus)|39-411等。最新成果是杨德庄等人提出的新的椭球法142,其优点在于引入目标束不等式及目标不等式组成，与原椭球法相比一方面大大缩小了算法求解规模，另一方面扩大了可行集的体积。而且新算法中可行集切割及目标切割交替进行，加速了椭球体积的缩小。不过令人失望的是即使最好的椭球法实施在计算上都难以与已有的单纯形法相比。因此，实际中很少作为一般方法使用1431。

然而线性规划的其他解法如单纯形法、内点法都需要从一个基础解出发，然后确定迭代方向、迭代步长，因此每次迭代都需要计算目标函数和所有约束函数。而椭球法的计算则简单得多，理论上来说椭球法对于约束条件多的问题更有效。

4内点法

1984年KamarH441提出了一个比Khanchian法好的多项式时间算法的内点法，称为Kamaikar法。由于该法引用了非线性规划中的牛顿投影，因此又称K_aka牧影法。

K_aka袪的提出在线性规划领域具有极大的理论意义。与椭球法不同，这个新算法不仅在最坏情况下在时间复杂度上优于单纯形法，在大型实际问题中也有潜力与单纯形法竞争。

这一方法的提出掀起了一股内点法的研究热潮。鉴于Kamaka?法的难读性，一些研究学者?对Kamaika袪进行了适度的修改，使其简便易读。然而直接用该方法编程解题的测试表明，与目前基于单纯形法的商用软件相比，并没有明显的优势1491。因此很多研究者在Kamarka法的基础上深入研究并提出了各种修正内点法方法：仿射尺度法，对数障碍函数法，路径跟踪法算法等。

仿射比例调节法又分为原（Ptme)仿射比例调节法和对偶（Dua)方射比例调节法。原仿射比例调节法是从原问题出发，用一个仿射变换代替投影变换，把坐标系从一个非负象限不是单纯形）映射到其本身。该法1967年由前苏联学者Dkii5(0提出，但他的工作直到Bame1]等人再次研究该法后才被 法，另一方面作了完全的收敛性的证明。此外，1989年AdleP等发表了从原问题的对偶问题出发的对偶仿射比例调节法。

1986年G1531等人第一次把用于非线性规划的对数障碍函数法用于线性规划，并证明了对数障碍函数法和Kamarka投影法是等价的。以后的研究表明kamaikaf法实际上是广义对数障碍函数法的一个特殊情形。由于其计算方面的优越性，因此该法得到更多的研究和发展，该法也分为原对数障碍函数法和对偶对数障碍函数法。

原对偶（PrimaDua)各径跟踪法，实际上是原对偶障碍函数法，是MeidG19M541年提出的。他将包含对数障碍函数问题的障碍参数的唯一的最优解所构成的曲线称为一条路径或中心轨迹，当障碍参数趋近零时，中心轨迹的极限即为原问题的最优解。Kojma55'等最早（1987)提出收敛的算法，之后其他研究者对算法作了进一步的改进。为了找到起始可行解算法都要引进人工变量和附加约束条件，分别以适当的大数作系数和右端值，但算法对这些大数的选择很敏感易导致算法中数值的不稳定性。因此LustiTi等考虑使这些大数同时变为无穷大时坐标增量的“极限可行方向”该方向只改变了求最优解的方向，并不改变确定轨迹中心的方向，因而问题解法成为不可行问题原对偶牛顿法，其优点是对初始解不必引入人工变量。该法也可用类似形式应用于不可行原问题或对偶问题的方法中[57581。该法还便于处理有界变量问题。然而这个方法的计算复杂性尚未确知，没有一般收敛的算法的证明。此外，在方法的改进方面，出现了全面收敛不可行内点算法和预计改正法。

势函数下降法有基于Gezaga等人提出的原势函数下降法和Ye等人提出的原对偶势函数下降法,计算复杂性都达到较好指标。前者算法包含了两个搜索方向，且所有仿射变换方法都采用了最速下降方向。这方面的改进还有Kajmm等的原对偶势函数下降法等。由于上述势函数下降法的各种算法是基于一系列严格的可行解上，方法都要求说是难以做到的。显然直接采用不可行内点算法是最好的解决办法，因而Y，eTOdd和Misunol994年提

出了构建“齐次自对偶问题”的方法，该齐次自对偶问题的解则可以用Kajjna等的原对偶势函数下降法来解出。

在20世纪90年代内点法理论发展成一个相当成熟的原理。这一时期，对内点法理论的一个主要贡献来自YENesterov和八SNmirovski两位数学家[69。他们创建的Self-Cocrdant函数理论，使基于对数障碍函数的线性规划内点法很容易推广到更为复杂的优化问题上，如非线性凸规划、非线性互补、变分不等式、半定优化以及二阶锥优化等。目前自协调函数形式主要有：对数函数和商函数形式。

今天，内点法的研究热点主要转向于半定优化、半定互补、非凸优化及组合优化问题上。

5自协调函数理论

自协调函数可谓是线性规划算法研究的一个重大突破，也是我们后续研究的重点。自协调函数理论又名自协调障碍函数理论，为解线性和凸优化问题提供了多项式时间内点算法。根据自协调障碍函数的参数就可以分析内点算法的复杂性。

自协调函数定义：

一个凸函数fR-R对定义域内的任意x满足Lf"(x)<2f(x3/2,我们就称它为自协调函数。如果函数(Rn-R对于任意直线满足自协调条件，我们称函数§(9是自协调函数。

自协调函数理论的关键是算法的复杂性由自协调函数的两个参数决定，只要这两个参数可以推导出，则可求得算法的复杂性。

然而目前常用的自协调函数形式只有对数障碍函数形式:负对数函数：f=一Igx及负商函数加上负对数函数：f=xgx^lgP]。

最近CReas等m指出有些内核函数尽管没有全局自协调性，却能在局部自协调。而且，CR?s

部值 也可以较好的求得算法的复杂性。基于CRQ0S的思想，金正静等1711提出了一个局部自协调函数，其形式如下

自协调函数理论的提出，为我们分析算法复杂性带来了极大的便利。然而以上的自协调函数形式都要求核函数为正，这为我们的研究带来了极大的限制。那么自协调函数是否存在不要求核函数为正的形式为我们研究自协调函数提供了方向。

6结束语

篇8

A. 1 B. [32]

C. 2 D. 3

2. 若实数[x]，[y]满足不等式组[x+3y-3≥0，2x-y-3≤0，x-my+1≥0，]且[x+y]的最大值为9，则实数[m=]（ ）

A. [-2] B. [-1]

C. 1 D. 2

3. 设不等式组[x+y-11≥0，3x-y+3≥0，5x-3y+9≤0，]表示的平面区域为[D]，若指数函数[y=ax]的图象上存在区域D上的点，则[a]的取值范围是（ ）

A. [（1，3]] B. [[2，3]]

C. [（1，2]] D. [[3，+∞）]

4. 某公司生产甲、乙两种桶装产品.已知生产甲产品1桶需耗[A]原料1千克、[B]原料2千克；生产乙产品1桶需耗[A]原料2千克，[B]原料1千克.每桶甲产品的利润是300元，每桶乙产品的利润是400元.公司在生产这两种产品的计划中，要求每天消耗[A]，[B]原料都不超过12千克. 通过合理安排生产计划，从每天生产的甲、乙两种产品中，公司共可获得的最大利润是（ ）

A. 1800元 B. 2400元

C. 2800元 D. 3100元

5. 在平面直角坐标系[xOy]中，[M]为不等式组[2x-y-2≥0，x+2y-1≥0，3x+y-8≤0]所表示的平面区域上一动点，则[OM]斜率的最小值为（ ）

A. [2] B. [1]

C. [-13] D. [-12]

6. 已知[a>0]，[x，y]满足约束条件[x≥1，x+y≤3，y≥a（x-3），]若[z=2x+y]的最小值为[1]，则[a=]（ ）

A. [14] B. [12]

C. [1] D. [2]

7. 某旅行社租用[A]，[B]两种型号的客车安排900名客人旅行，[A]，[B]两种车辆的载客量分别为36人和60人，租金分别为1600元/辆和2400元/辆，旅行社要求租车总数不超过21辆，且[B]型车不多于[A]型车7辆. 则租金最少为（ ）

A. 31200元 B. 36000元

C. 36800元 D. 38400元

8. 设变量[x，y]满足[x+y≤1，]则[x+2y]的最大值和最小值分别为（ ）

A. 1，-1 B. 2，-2

C. 1，-2 D. 2，-1

9. 已知变量[x，y]满足[2x-y≤0，x-2y+3≥0，x≥0，]则[z=log12（x+y+5）]的最小值为（ ）

A. -8 B. -4

C. -3 D. -2

10. 已知实数[x，y]满足[y≥0y≤2x-1x+y≤m]，如果目标函数[z=x-y]的最小值的取值范围是[-2，-1]，则目标函数的最大值的取值范围是（ ）

A. [1，2] B. [3，6]

C. [5，8] D. [7，10]

二、填空题（每小题4分，共16分）

11. 已知[z=2x-y]，式中变量[x]，[y]满足约束条件[y≤x，x+y≥1，x≤2，]，则[z]的最大值为 .

12. 抛物线[y=x2]在[x=1]处的切线与两坐标轴围成三角形区域为[D]（包含三角形内部和边界） . 若点[P（x，y）]是区域[D]内的任意一点，则[x+2y]的取值范围是 .

13. 设[P]是不等式组[x，y≥0，x-y≥-1，x+y≤3]表示的平面区域内的任意一点，向量[m=（1，1）]，[n=（2，1）]，若[OP=λm][+μn]（[λ，μ]为实数），则[2λ+μ]的最大值为 .

14. 记不等式组[x≥0x+3y≥43x+y≤4]，所表示的平面区域为[D]，若直线[y=a（x+1）]与[D]有公共点，则[a]的取值范围是 .

三、解答题（共4小题，44分）

15. （10分）若变量[x，y]满足约束条件[3≤2x+y≤9，6≤x-y≤9，]求[z=x+2y]的最小值.

篇9

1.静态可行域下形如z=ax+by+c截距型线性目标函数的最值

例1（2015年湖南卷）若变量x，y满足约束条件则z=3x-y 的最小值为（ ）

解析：作出可行域（图略），作直线l：3x-y=0，平移直线l利用数形结合法求最值。答案：选A

命题点睛 要求考生理解目标函数的意义：把z=3x-y看作一条“动直线”l，观察其位置，从而确定目标函数取得最值时所经过的点。动中有静，动直线l牵引出最优解（定点），从而得到z的最小值。

2.动态可行域下形如z=ax+by+c 截距型线性目标函数最值的逆向问题

例2 （2015年福建卷）变量x，y满足约束条件若z=2x-y的最大值为2，则实数m 等于（ ）

A、-2 B、-1

C、1 D、2

图1

解析 将目标函数看作动直线l：2x-z=0，当z取最大值时，动直线l纵截距最小。故当m≤0时，不满足题意;当m>0时，由可行域如图1所示，其中 是最优解，代入目标函数得：，得m=1。故选C。

命题点睛 以动制静，动直线l的位置与参数m的符号相互制约，由两条动直线l：y=2x-z与l1：y=mx牵引出定点B最优解。解含参数的线性规划问题，要善于从已知的可行域（动态区域）中找出不变的（静态）区域。困难在于对参数m的符号讨论，以确定可行域，往往还要将动直线l的斜率和可行域边界的斜率比较，否则找出最优解很容易出错。思维从静态到动态模式跳跃式开放性发展，更能考查学生的创新应用能力。

二、一线牵引出非线性目标函数的最值

1.斜率型

例3 （2015年全国卷） 若x，y 满足约束条件 则的最大值为 。

解析 作出可行域（图略），由斜率的意义知是可行域内的动点P（x，y）与原点连线的斜率。答案：3

命题点睛 形如型的目标函数，其表示可行域内的动点P（x，y）与定点M（a，b）连线的斜率。将直线PM绕点M旋转，且确保动点P在可行域内，这样由动点与定点的连线牵引出斜率的取值范围。

2.距离型：点点距、点线距

例4 （2016年山东卷） 若变量x，y满足 则x2+y2的最大值是（ ）

A、4 B、9

C、10 D、12

解析x2+y2表示可行域内的动点（x，y）到原点O（0，0）距离的平方，可得x2+y2的最大值为10。故选C。

命题点睛 点点距离型实质就是动点与定点连线的长度。

变式探究1（点线距）：（2016年浙江卷文・4改编）

若平面区域

（1） 的最大值是 。

（2）的最大值是 。

答案：（1）（2）

3.向量数量积型（夹角型、投影型）

例5 （2016年浙江卷） 在平面上，过点P作直线l的垂线所得的垂足称为点P在直线l上的投影。由区域中的点在直线x+y-2=0上的投影构成的线段记为AB，则|AB|（ ）。

A、 B、4

C、 D、6

答案：C

变式拓展2：（夹角型、投影型） 已知点A（3，1），O为坐标原点，点P（x，y）满足则

（1） 的最小值是 。

（2） 的最大值是 。

（3） 的取值范围是 。

解析 如图2所示，（1）

当且仅当与 反向时，取等号;

（2）的最大值即在方向上的投影，为

（3）的最小值即在方向上的投影，为

其最大值即与共线时在方向上的投影，为，所以其取值范围是

命题点睛 （1）中抓住定向量与动向量的夹角;（2）中抓住动线段OP在一条定直线OA上的投影;（3）与（2）正好反之。

图2

4.直线与圆锥曲线相关位置型

图3

例6 （2016年山东卷文・4改编） 设x，y满足约束条件若Z=x2+4y2，则Z的取值范围是 。

解析Z=x2+4y2表示中心在坐标

原点，焦点在x 轴上的椭圆，当此椭圆与直线x+y=1相切时，Z=x2+4y2最小，

由 得5y2-2y+1=0 ，由Δ=0

得 为最小值;当此椭圆过点 时，为最大值，故所求范围是

图4

命题点睛 圆锥曲线（动曲线）与一条定直线（或定点）的位置关系牵引出z的取值范围，此题型新颖别致，赏心悦目，耐人寻味。

变式拓展3 设变量x，y满足约束条件

其中k∈R，k>0.

篇10

教学重点

1.二元一次不等式(组)表示的平面区域;

2.应用线性规划的方法解决一些简单的实际问题。

教学难点

线性规划在实际问题的应用

高考展望

1.线性规划是教材的新增内容，高考中对这方面的知识涉及的还比较少，但今后将会成为新高考的热点之一;

2.在高考中一般不会单独出现，往往都是隐含在其他数学内容的问题之中，就是说常结合其他数学内容考查，往往都是容易题

知识整合

1.二元一次不等式(组)表示平面区域：一般地，二元一次不等式在平面直角坐标系中表示直线某一侧所有点组成的__________。我们把直线画成虚线以表示区域_________边界直线。当我们在坐标系中画不等式所表示的平面区域时,此区域应___________边界直线，则把边界直线画成____________.

2.由于对在直线同一侧的所有点，把它的坐标代入，所得到实数的符号都__________，所以只需在此直线的某一侧取一个特殊点，从的_________即可判断>0表示直线哪一侧的平面区域

3.二元一次不等式组是一组对变量x,y的__________，这组约束条件都是关于x,y的一次不等式，所以又称为_____________;

4.(a,b是实常数)是欲达到最大值或_________所涉及的变量x,y的解析式，叫做______________。由于又是x,y的一次解析式，所以又叫做_________;

5.求线性目标函数在_______下的最大值或____________的问题，统称为_________问题。满足线性约束条件的解叫做_________，由所有可行解组成的集合叫做_________。分别使目标函数取得____________和最小值的可行解叫做这个问题的___________.

典型例题

例1.(课本题)画出下列不等式(组)表示的平面区域，

1)2)3)

4)5)6)

例2.

1)画出表示的区域，并求所有的正整数解

2)画出以A(3，-1)、B(-1，1)、C(1，3)为顶点的的区域(包括各边)，写出该区域所表示的二元一次不等式组，并求以该区域为可行域的目标函数的最大值和最小值。

例3.1)已知，求的取值范围

2)已知函数，满足求的取值范围

例4(04苏19)制定投资计划时，不仅要考虑可能获得的盈利，而且要考虑可能出现的亏损。某投资人打算投资甲、乙两个项目，根据预测，甲、乙项目可能的最大盈利率分别为100%和50%，可能的最大亏损率为30%和10%，投资人计划投资金额不超过10万元，要求确保可能的资金亏损不超过1.8万元，问投资人对甲、乙两个项目各投资打算多少万元，才能使可能的盈利最大?

例5.某人承揽一项业务，需做文字标牌4个，绘画标牌6个，现有两种规格原料，甲种规格每张3m，可做文字标牌1个，绘画标牌2个;乙种规格每张2m，可做文字标牌2个，绘画标牌1个,求两种规格的原料各用多少张，才能使总的用料面积最小?

例6.某人上午时乘摩托艇以匀速V海里/小时从A港出发到相距50海里的B港驶去，然后乘汽车以匀速W千米/小时自B港向相距300km的C市驶去，应该在同一天下午4点到9点到达C市。设汽车、摩托艇所需时间分别为小时，如果已知所要经费P=(元)，那么V、W分别是多少时走得最经济?此时需花费多少元?

巩固练习

1.将目标函数看作直线方程,z为参数时，z的意义是()

A.该直线的纵截距B。该直线纵截距的3倍

C.该直线的横截距的相反数D。该直线纵截距的

2。变量满足条件则使的值最小的是()

A.(B。(3，6)C。(9，2)D。(6，4)

3。设式中变量和满足条件则的最小值为()

A.1B。-1C。3D。-3

4。(05浙7)设集合A={是三角形的三边长}，则A所表示的平面区域(不含边界的阴影部分)是()

5。在坐标平面上，不等式组所表示的平面区域的面积为()

A。B。C。D。2