线性规划范文

导语：如何才能写好一篇线性规划，这就需要搜集整理更多的资料和文献，欢迎阅读由公务员之家整理的十篇范文，供你借鉴。

篇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、(全国卷)在坐标平面上,不等式组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的不等式(组)或方程(组)。

②其次要确定目标函数(多是二元函数)理解它的几何意义;如:截距问题,斜率 ,两点间距离,点到直线距离。

篇3

毋庸置疑，数学规划领域的重大突破总是始于线形规划。提到线性规划算法，人们最先想到的是单纯形法和内点法。单纯形法是实际应用中使用最普遍的一种线性规划算法，而研究者们已证明在最坏的情况下单纯形法的计算复杂度是指数级的，内点算法的计算复杂度是多项式时间的。把两种算法相提并论，要么是这两种算法都已经非常完备，要么都有需改进之处。显然不属于前者，即两者都有需要改进之处。几十年来，研究者通过不断努力，在两种算法的计算上都取得相当的进展。

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结束语

除了边界点算法，椭球法，内点法，线性规划还有有效集法等经典算法、杨德庄教授的新算法及遗传算法，神经网络等求解线性规划的智能计算方法，有兴趣者可参看有关文献。

篇4

2.了解线性规划问题的图象法，并能用线性规划的方法解决一些简单的实际问题。

教学重点

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

6.(06全国ⅰ14)设，式中变量和满足下列条件则的最大值为__________________;

篇5

1.常规问题

例1 （2012・山东）设变量x，y满足约束条件x+2y≥2，

2x+y≤4，

4x-y≥-1，则目标函数z=3x-y的取值范围是（ ）

A.[-32，6] B.[-32，-1]

C.[-1，6] D.[-6，32]

解析 作出不等式组表示的可行域，如图1阴影部分所示，作直线3x-y=0，并向上、下平移，由图可得，当直线过点A时，z=3x-y取最大值；当直线过点B时，z=3x-y取最小值.由x+2y=2，

2x+y=4，解得A（2，0）；由2x+y=4，

4x-y=-1，解得B（12，3）.

所以zmax=3×2-0=6，zmin=3×12-3=-32.所以z=3x-y的取值范围是[-32，6].

2.非线性目标函数问题

例2 （2011・广东）已知平面直角坐标系xOy上的区域D由不等式组0≤x≤2，

y≤2，

x≤2y给定.若M（x，y）为D上的动点，点A的坐标为（2，1）则z=OM・OA的最大值为（ ）.

A.42 B.32 C.4 D.3

解析 如图2作出区域D，目标函数z=2x+y过点B（2，2）时取最大值，故z的最大值为2×2+2=4，

故选C.

例3 （2012・北京）设不等式组0≤x≤2，

0≤y≤2表示的平面区域为D，在区域D内随机取一个点，则此点到坐标原点的距离大于2的概率是（ ）.

A.π4 B.π-22 C.π6 D. 4-π4

解析 如图3所示，正方形OABC及其内部是不等式组所表示的区域D，且区域D的面积为4，而阴影部分表示的是区域D内到坐标原点的距离大于2的区域.因此满足条件的概率是4-π4.

3.含参的线性规划问题

例4 （2011・湖南）设m>1，在约束条件y≥x，

y≤mx，

x+y≤1下，目标函数z=x+my的最大值小于2，则m的取值范围为.

解析 目标函数z=x+my可变为y=-

1mx+zm.

因为m>1，所以-1

如图4，当目标函数经过点P（1m+1，mm+1）时取最大值，

所以1m+1+mm+11，得1

4.平面区域问题

例5 （2013安徽）在平面直角坐标系中，O是坐标原点，两定点A，B满足

|OA|=|OB|=OA・OB=2，则点集{P|OP=λOA+μOB，|λ|+|μ|≤1，λ，μ∈R}所表示的区域的面积是（ ）.

A.22 B.23 C.42 D.43

解析 若A，B，C三点共线，P是线外一点，则PA=λPB+μPC，其中λ+μ=1.

在本题中，OA・OB=|OA||OB|cosθ=4cosθ=2θ=π3.

建立直角坐标系，设A（2，0），B（1，3）.则当λ≥0，μ≥0，λ+μ≤1时，P在三角形OAB内（含边界）.

根据对称性，所求区域的面积S=4×三角形OAB的面积=43.

A.2a B.12a C.4a D.4a

解析 如果用常规方法，显然比较麻烦，有点“小题大做”了.由于直线的位置没有特殊要求，因此可选取一个特殊位置，在此位置处求1p+1q的值即可.

篇6

关键词：线性规划思想；解题；应用

中图分类号：G427 文献标识码：A文章编号：1992-7711（2012）03-076-2

线性规划问题以二元一次不等式所表示的平面区域内容为基础，它将代数与几何，数学与实际巧妙地联系起来，线性规划实际上就是以数学知识为工具，来研究在一定的人、财、物、时、空等资源条件下，如何精打细算巧妙安排以最少的资源来取得最大的经济效益。然而中学所学的线性规划只是规划论中极小的一部分，但这部分内容体现了数学的工具性、应用性，同时渗透了化归、数形结合的思想，并且为学生今后解决实际问题提供了一种重要的解题方法――数学模型法，所以掌握好这部分内容非常重要。

一、线性规划的内涵

线性规划是数学规划的一部分，它研究目标函数在约束条件下的最大值和最小值问题，即要寻找既满足约束条件又使得目标函数达到最优的解，要一下子处理可能比较困难，于是提出“可行解”这一概念，将求解线性规划的问题分解为两步，第一步先求“可行解”，第二步再求“最优解”。从而分散了难点，找到了解决问题的方法。虽然中学所学的线性规划只是规划论中极小一部分，但这部分内容体现了数学的工具性、应用性，同时渗透了化归、数形结合的思想，能够将实际问题转化为数学问题，抽象解决一些简单的线性规划应用问题的基本思路和主要方法。

二、线性规划思想解题

利用线性规划的思想解题主要是依据给定的条件，把整个题目的有关约束条件和所求目标函数用数学关系和逻辑关系表示出来，运用化规，数形结合等思想，主要通过图解法的方法求解，得出最优解和最优目标函数值。下面举例说明几种用的线性规划的方法在实际解题中的应用。

(一)向量问题转化为线性规划问题

向量是平面几何的基础，线性规划作为连接点巧妙地将几何问题与代数问题联结起来。

例1 已知在平面直角坐标系中，O(0,0)，M(1,12)，N(0,1)，Q(2,3)，动点P(x,y)满足不等式0≤OP•OM≤1，0≤OP•ON≤1，则W=OP•OQ的最大值是多少？

分析 因为O(0,0)，M(1,12)，N(0,1)，Q(2,3)，所以 0≤OP•OM≤1,0≤OP•ON≤1，0≤x+12y 图1

≤1,0≤y≤1，W=OP•OQ=2x+3y。

本例转化为在线性的约束条件

x+12y≤1,0≤y≤1,x+12y≥0

下，求线性目标函数W=OP•OQ=2x+3y的最大值题。可作出如图的可行域，显然在点T的坐标是最优解。

由

x+12y=1,y=1

得

T(12,1),

所以

Wmax=2×12+3×1=4。

注 本题将平面向量与线性规划巧妙地结合起来，真正体现了在知识交汇点处命题的高考指导思想。解决这类问题的关键是将已知的不等式组准确地转化为二元一次不等式组并准确画图，然后求最值。

(二)三角问题转化为线性规划问题

求解三角形个数问题，常规解法是根据三角形三边关系，利用分类计数原理求解，而用线性规划方法求解，则别具一格［2］。

例2 三边长均为整数，且最大边长为11的三角形个数为多少？ 图2

解 设三角形另两边长分别x,y(x,y∈N*),

根据题意得

x+y>11,x≤11,y≤11,x≥y,x,y∈N*

转化为在此约束条件下求整数点的问题，

如图所示可得 1+3+5+7+9+11=36，

故三角形的个数为36个。

注 本题巧妙地将线性规划问题运用到三角形的问题中，体现了线性规划广泛运用的特点。求解这类题目关键是利用三角形两边之和大于第三边的关系，转换为标准的线性规划问题，其中，在求整数可行解时，也就是可行域中横坐标和纵坐标都是整数的点，可先画出满足线性规划约束条件的平面区域，然后再找整数点。

(三)与函数或不等式结合,求取值范围问题

函数与不等式是高中数学的基本知识点，求取值范围也是常见地类型，结合函数或不等式的性质，运用数形结合的思想把问题转化为线性规划的问题解决，即形象又直观［3］。

例3 已知f(x)=ax2+bx，且1≤f(－1)≤2，2≤f(1)≤4，求f(－2)的取值范围。

分析 对这个问题，可以用f(－1)，f(1)表示f(－2)，再由f(－1)，f(1)的范围，结合不等式的性质求出f(－2)的取值范围。我们可以转化为线性规划问题求解。 图3

解 1≤f(－1)≤2,2≤f(1)≤4,得1≤a－b≤2,2≤a+b≤4。(1)

目标是求f(-2)=4a－2b的取值范围。

作出线性约束条件（1）下的可行域四边形ABCD，

如图3A(2,0),B(3,1),C(52,32),D(32,12)不难得到，

当直线4a－2b= f(-2)经过点B和D 时，

f(－2)分别取得最大值最小值10和5。

所以 f(-2)∈［5,10］。

注 对于这个问题，很多学生常犯如下错误:由题设

1≤a－b≤2,2≤a+b≤4,

得

32≤a≤3,0≤b≤32。 (2)

又因f(-2)=4a－2b，所以3≤f(－2)≤12。

线性规划中的可行域可以直观形象地帮助我们可看到此种解法的错误之处。作出（2）式表示的可行域如图4，可清楚地看到图3中的可行域是图4的一部分，即由（1）到（2）后范围扩大了。

(四)线性规划在函数问题中的应用

对于某些与函数有关的问题，若善于利用已知条件构造线性约束条件，将问题换为线性规划问题求解，有时能起到事半功倍的效果。

例4 已知函数f(x)=x3+ax2+bx+c在区间［－1,2］上是减函数，求a+b的最大值。

分析 根据线性规划思想，可视t=a+b为目标函数，再由已知条件可知a,b的约束条件，即由f(x)=x3+ax2+bx+c在区间［－1,2］上是减函数，得出目标函数的可行域。这样，求a+b的最大值就转化为在可行域中求目标函数的最大值。

图4

解 由题意知f′(x)=3x2+2ax+b,在［－1,2］恒有f′(x)≤0，

则

f′(－1)≤0,f′(2)≤0

即

3－2a+b≤0,12+4a+b≤0。

令t=a+b，其中a,b满足上述约束条件，作出这个约束条件下的可行域,如图5所示，当直线t=a+b 过点 A(－32,－6)时，tmax=－152。

容易验证:a=－32,b=－6 时，f(x)在区间［－1,2］上是减函数，所以a+b的最大值为－152。

注 本例题由函数的单调性，运用导数列出不等式即得出目标函数的可行域，将本例转化为求解目标函数的最大值，若直接运用函数的性质求解，显得繁琐且容易将范围扩大,因此，运用线性规划思想求解此类最值问题时既简捷又方便。

(五)与解析几何结合，求参数的范围问题

线性规划体现的是数形结合的思想，理解了这一点，则赋予了线性规划知识更广泛、更深刻的意义。在线性约束条件下，凡结论具有一定的几何意义的问题均可类比解决。

例5 已知线段AB的端点为A(1,3)、B(5,2)，若动直线l:x+ty=－1t与线段AB相交，求参数t的取值范围。

图5

分析 直线l可化为x+ty+1t=0。因线段AB与直线l有公共点。

由线性规划知识得

(1+3t+1t)(5+2t+1t)≤0,

而 t2>0，所以化为

(3t2+t+1)(2t2+5t+1)≤0。

又3t2+t+1=3(t+16)2+1112>0,

所以再化为

2t2+5t+1≤0,

解得

－5－174≤t≤－5+174。

注1 直角坐标系内有两点P1(x1,y1),P2(x2,y2)直线l:Ax+By+C=0，直线l和线段P1P2有公共点的充要条件是(Ax1+By1+C)(Ax2+By2+C)≤0。

注2 按传统解法是从直线斜率出发，由动直线引出定点，通过对直线系探讨等决与线段有公共点的问题。而本题难以确定动直线所过定点，传统方法无法用上。现在利用线性规划知识构建不等式，就可以使问题得到圆满解决。

(六)概率问题转化为线性规划问题

概率是中学数学教材中新增内容，它在理论与实际生活中都有重要意义，在求解某些概率问题的过程中，若思路受阻，或很难找到突破口，可以借助坐标和一系列的等价变换，将一次试验可能结果的全体用某一图形的面积G来代替，然后将所求事件包含的结果数以线性约束条件的形式展现出来，若其相应的可行域的面积为g，则所求事件的概率为gG。

例6 两人相约9点到10点在同一地点会面，早到的人要等另一个人20分钟才能离开，试求两人会面的概率。

分析 以x,y分别代表两人到会面地点的时刻，则两人会面的充要条件为

|x－y|≤20,x,y∈［0,60］,即x－y≤20,y－x≤20,0≤x≤60,0≤y≤60

在直角坐标系中画出x,y的可行域（如图6的阴影部分）。显然两人可能到达的时间为图中正方形内（含边界）的点，阴影部分表示能会面的点，从而可利用其面积之比得概率为:P=602－12×40×40×2602=59。

注 这是一道几何概率问题，用线性规划的思想可直观简捷的求解这类问题。本例题中有明确的不等式关系，可将其概括成不等式组，画可行域，用线性规划的思想解题。

线性规划是数学规划中理论较完整，方法较成熟，应用广泛的一个分支，它能解决许多方面的实际问题。它是直线方程的一个简单应用，也是数形结合数学思想的很好体现。文章是在了解线性规划的意义，以及线性约束、线性目标函数、可行解、可行域、最优解等概念，并且熟练掌握线性规划的图解法的基础上，运用数形结合的思想解决有关向量、函数、不等式、解析几何等方面的问题，使解决这些问题变得更加简便，同时也有助于数学思维能力的提高。

［参考文献］

［1］教育部.普通高中数学课程标准(实验).人民教育出版社,2003.

［2］吴成强.线性目标函数最优解的探求.中学生理科月刊,2003（5）.

篇7

[关键词]非线性规划 惩罚函数法 磨光法

一、引言

惩罚函数法是求解约束型非线性规划的有效算法之一。但对具有不等式约束的非线性规划问题,常用的简单罚函数法存在缺陷。由于一般的简单罚函数在可行域边界点上不可微,因此给求解无约束优化问题的编程计算带来不方便。近年来,关于处理不可微优化问题的算法很多,但大多数算法是引入次梯度的迭代算法,理论推导复杂,局限性比较大,编程计算仍然不便。受文献[1-2]利用磨光参数处理不可微点技术的启发,提出求解约束型非线性规划的磨光惩罚函数法。文献[1]利用磨光参数获得了非光滑最优控制的差分解,文献求解了具有互补约束条件的优化问题,同样引进了磨光参数将不可微点近似处理为可微函数,逐步逼近真解。磨光惩罚函数法的基本思想是,在简单罚函数法的基础上利用磨光参数将非光滑罚函数近似为光滑函数,进一步采用可微函数的常规算法获得包含磨光参数的近似解,通过逐步细磨获得最优解。该方法避开了罚函数的不可微性,使编程求解更加初等化,简单化。

二、简单罚函数法和磨光参数

考虑具有不等式约束的非线性规划问题:

Min f(x) (1)

(2)

其中f(x),gi(x)是Rn上的连续的可微函数。实现这类约束问题求解的途径是由目标函数和约束函数组成辅助函数,把原来的约束问题转换成为极小化辅助函数的无约束问题。

定义辅助函数为下列形式:

是满足下列条件的连续函数

其中,的典型取法为,其中β≥1均为给定的常数,通常取为2。构造增广目标函数,得到外点罚函数算法[4-5](SUMT)。

算法1:(SUMT)

三、磨光罚函数法及其收敛性

值得说明的是,算法2:(S- SUMT)得到的解对应的目标值与算法1(SUMT)得到的解对应的目标值相同,但最优解不一定相同。然而,如果问题(1)(2)的解唯一,则两算法得到的最优解相同。

四、数值例子

考虑约束型非线性规划问题

五、结束语

由算例可以看出随着磨光参数的减小,在同样的惩罚因子下,其解逐步趋近于精确解。因此本文提出的磨光罚函数法(S- SUMT)是可执行的,有效的。更重要的是该算法避开了简单罚函数不可微的缺陷,使得原问题连续可微,有利于编程实现。

参考文献:

[1]Xiaojun Chen. Finite difference smoothing solutions of nonsmooth constrained optimal control problem[J].Numerical Functional Analysis and Optimization, 2005,26(1):49-68.

[2]Xinmin Hu, Daniel Ralph. Convergence of a penalty method for mathematical programming with complementarity constraints[J].Journal of Optimization and application,2004,123(2):365-390.

[3]Scholtes,S. Convergence Properties of a Regularization scheme for Mathematical Programs with Complementarity Constraints[J].SIAM Journal on Optimization,2001,11(4):918-936.

篇8

关键词：线性规划 ；移动Agent

中图分类号：TP18文献标识码：A文章编号：1009-3044(2011)28-6967-02

Based on Mobile Agent of Linear Programming model

HE Bin

(Computer Science Dept. of Ningxia University, Yinchuan 750021, China)

Abstract: This article discusses a mobile agent based on linear programming solving solutions to improve the calculation efficiency, has the nice practical significance.

Key words: linear programming; mobile agent

1 绪论

整数线性规划问题的求解已广泛的应用到工程实践中。传统的求解整数线性规划方法有：枚举法、割平面法以及分枝定界法。其中分枝定界法是最为常用的方法[1]。

分枝定界法是20世纪60年代初期由Land Doid 和Dakin等人提出的，是一种系统化的解法，以一般线性规划的单纯形法解得最佳解，然后将非整数值的解分割成最接近的两个整数，分列条件，加入原问题中，如此分枝成两个子问题分别求解，这样便可求得目标函数值的上界或下界，从其中寻得可行解。 可见本算法能较快的求得最佳解，且平均速度快，但要存储很多叶子结点的限界和对应的耗费矩阵，花费很多内存空间，计算效率较低。本文探讨一种基于演化agent的解决方案。

2 基于移动Agent的整数线性规划

移动agent是具有移动性的智能agent，能够自行决定在网络的各个节点之间移动，代表其他实体（人或其他agent）进行工作的一种软件实体。移动Agent技术是分布式技术与Agent技术相结合的产物，它除了具有agent最基本的特性：自主性、反应性、能动性、通信性以外，还具有移动性[2]。这些特有的属性和技术优势使其在诸多领域得到了科学的应用，特别适合于解决传统方法中代价过于昂贵，或者解决不了的问题。

2.1 agent模型

定义一个agent，它是具有目标、动作、通信等行为功能的复合体，用符合T表示。agent的行为描述如下：

1）复制

一个agent T可以复制成两个子agent T1、T2，我们称T为父agent。它的两个子agent与其具有同样的目标，但所处的问题环境有所改变。

2）动作

Agent会根据其所处的问题环境不停地计算其目标，直到成功或者到达中止条件。

3）通信

设环境E中是agent T的计算环境，那么agent T会在这个环境中进行计算，直到达到其目标，如果目标不能达到，agent T会复制成agent T1、T2来继续计算其目标，此时环境E也会被分成E1 、E2（E的两个子环境），它们就分别是T1、T2的计算环境。

T1、T2分别在E1、E2中计算其目标，如果它们的计算达到目标，则将计算结果发送给agent T，否则将会继续复制，继续计算下去。

2.2 求解算法

这个算法的基本思想是：将松弛问题Q作为agent T的目标和计算环境，T首先按单纯形法来求解，如果计算的结果有最佳整数值，则问题得到求解。否则，T将复制成两个子agent T1、T2分别对应与两个子问题B1、B2继续求解，如此下去，以获得问题的最优整数解。算法可描述如下：

1）首先把整数线性规划问题中得目标函数以及约束条件作为agent T的目标和环境赋给它，并且定义变量p（p首先不赋予值）；

2）agent T首先求解松弛问题，如果松弛问题的最优解全为整数，那么把这些最优解赋值给p，转去执行（6），如果松弛问题没有可行解，就直接转去执行6），否则将执行下一步；

3）若在求解过程中某个变量xi的解为分数值kj，那么就分别求得小于 kj下的最大整数[kj]和大于的最小整数[kj]+1，agent T 将复制成两个子agent T1、T2。这两个子agent的计算目标与agent T相同，但其环境分别为原来T的计算环境加上约束条件xi=[kj]+1。

4）agent T1、T2 分别在其所处的环境里计算它们的目标，如果最优整数解已求出，则若p没有值，那么将最优整数解赋值给p，否则，p min（p，最优值）；

5）当T1、T2 中有非整数可行解者Tj 时，如果p没有值或所得的非整数可行解小于p，那么将Tj 的解赋值给T，转到（3）继续执行；

6）如果p已有值，则输出p，否则就输出此整数线性规划问题没有可行解。

2.3 模型的实现

可选用日本IBM公司开发的Aglet平台，该平台是目前最为成功和全面的移动平台[3]。Aglet系统可以根据需要创建agent T ；复制agent T1、T2，将它们分派到各自的环境中执行；也能执行暂停、清除。

2.4 算法的时间复杂度

在微机上，采用一般的单纯形法来求解整数线性规划问题，其时间复杂度为O (n)；而用本文的模型进行求解，它的时间复杂度为O (log n)，可见实现的时间复杂度较低。

3 结束语

通过编程实现，本文探讨的模型取得了很好的效果。Agent可以同时复制，故求解过程具有并行性；并且程序实现的时间复杂度较低，求解过程基于目标驱动，提高了计算效率。

参考文献：

[1] 张干宗.线性规划[M].武汉:武汉大学出版社,2007.

篇9

关键词：非线性规划；企业营销；Lingo

中图分类号：F274 文献标志码：A 文章编号：1673-291X（2016）04-0059-02

一、非线性规划数学模型

对实际非线性规划问题做定量分析，首先要选定适当的目标变量和决策变量，并建立起目标变量与决策变量之间的函数关系，即目标函数，并建立约束条件。非线性规划问题的一般数学模型可表述为求未知量x1，x2...，xn，使满足约束条件：

gi（x1，...，xn）≥0，i=1，...，m

hj（x1，...，xn）=0，j=1，...，p

并使目标函数f（x1，...，xn）达到最小值（或最大值）。其中gi（x1，...，xn）和hj（x1，...，xn）均是定义在n维向量空间Rn上的某子集D（定义域）上的实值函数，且f（x1，...，xn）、gi（x1，...，xn）、hj（x1，...，xn）中至少有一个是非线性函数。记x=（x1，...，xn），则上述模型可以简记为：

minf（x）或maxf（x）

s.t.gi（x）≥0，i=1，...，mhj（x）=0，j=1，...，p

定义域D中满足约束条件的点称为问题的可行解，全体可行解所组成的集合称为问题的可行集。对于一个可行解x*，如果存在x*的一个领域，使目标函数在x*处的函数值f（x*）不大于（或不小于）该领域中任何其他可行解处的函数值，则称x*为问题的局部最优解，如果f（x*）不大于（或不小于）一切可行解处的目标函数值，则称x*为该模型的整体最优解。

二、应用举例

（一）案例介绍

宏宇电器公司计划生产三类10种小家电，其中包括：热水壶（1.5升、1.8升、2升）、豆浆机（0.9升、1.1升、1.3升）、电饭煲（2升、2.5升、3升、3.5升）。三类小家电的年最大生产能力分别为：热水壶5万个、豆浆机6.5万个、电饭煲6.2万个。制定使公司利润最大的的生产、销售方案（数据来源：2010年东北三省数学建模联赛A题）。

（二）案例求解

公司的收入和支出来自计划内销售和计划外销售两部分，公司所承担的计划内成本应该根据计划内的产品数量占总产品数量的比值确定，即：

公司承担的生产成本=总成本×

公司利润的表达式：

公司总利润=已签约合同的销售额+意向签约合同的销售额+计划外营销部上缴利润-计划内成本-经费

第1种小家电的销售额与订购量的函数关系为：

f1（x）=-0.26713x2+11.418x+1.3873

同理可以得到，第2至10种家电销售额与其订购量的函数关系。记fi（x）为第i种小家电的销售额，i=1，2，...，10，x代表订购量。

同理，记gi（y）为计划外销售第i种小家电营销部向企业缴纳的利润，i=1，2，...，10，y代表销售量；记mi（z）为第种小家电的经费，i=1，2，...，10，z代表产量；记ni（y）为第种小家电的经费，i=1，2，...，10，y代表销售量；记ni（y）为第i种小家电的经费，i=1，2，...，10，y代表产量。

1.每个产品的订购量不能超过客户的最大意向签约量。xij≤Mij，其中xij代表第j个顾客对第i种小家电的订购量，i=1，2，...，10，j=1，2，3，4，5，Mij代表第j个客户对第i种产品的最大签约量。

2.计划外产品的订购量不能超过其最大可能订购量。xi6≤Ni6，其中xi6代表计划外的第i种小家电的订购量，i=1，2，...，10，Ni6代表计划外第i种产品的最大可能订购量。

3.所有产品的订购量均不能为负数。xij≥0，i=1，2，...，10，j=1，2，3，4，5，6。

4.各类产品的订购量不能与超过其最大生产能力。∑3 i=1∑6 j=1xij≤12，∑6 i=4∑6 j=1xij≤20，∑3 i=7∑6 j=1xij≤19。

运用Lingo软件得到最大值t=697.33万元，目标函数取得最大值时的各变量取值。为使公司利润达到最大时的生产方案为：1至10种小家电分别对应的生产数量（千件）为：11.59、24.54、13.87、14、29、20、12、24.3、14.3、8.4。

篇10

回答 含参线性规划问题一般可分为两类，一类是约束条件含参，另一类是目标函数含参. 这两类问题的解题原理是相同的，关键是理解参数的本质，并认清参数变化对直线位置产生的影响.下面，我们就以提问中的问题为例进行分析.

我们首先想到作出直线x+3y-3=0，2x-y-3=0与x-my+1=0，确定可行域.但怎么确定含参直线x-my+1=0的具置呢？令y=0，解得x=-1，可知直线x-my+1=0必过定点（-1，0）.当m≠0时，直线x-my+1=0的斜率k=≠0；当m=0时，直线x-my+1=0的斜率不存在，故直线x-my+1=0可看作绕定点（-1，0）旋转且不与x轴重合的动直线，参数m就是控制直线x-my+1=0的位置的关键要素.当参数m变化时，不等式组x+3y-3≥0，2x-y-3≤0，x-my+1≥0表示的可行域也会随之变化.

在解题时，我们不妨以静制动，先设m为一个任意的常数，作出一个确定的可行域，然后以动驭静，让含参直线旋转起来，在旋转中寻找满足“x+y的最大值为9”的参数m.

如图1所示，在直角坐标系中作出直线l1：x+3y-3=0，l2：2x-y-3=0，l3：x-my+1=0的图象.

注意：过点（-1，0）作直线l3：x-my+1=0的图象（以虚线表示）时，可以对参数m取任一常数.

记不等式组x+3y-3≥0，2x-y-3≤0，x-my+1≥0所表示的平面区域为Ⅰ（如图1所示）. 把条件“x+y的最大值为9”等价转化为不等式x+y≤9，作直线l4：x+y=9的图象，记不等式x+y≤9所表示的平面区域为Ⅱ.判断平面区域Ⅰ与平面区域Ⅱ的位置关系.由题意可知x+y的最大值为9，所以平面区域Ⅰ应恒在平面区域Ⅱ的下方.

在图1中，平面区域Ⅰ不恒在平面区域Ⅱ的下方. 将直线l3：x-my+1=0绕定点（-1，0）沿逆时针方向旋转，平面区域Ⅰ不恒在平面区域Ⅱ的下方，不满足题意.如图2所示，将直线l3绕定点（-1，0）沿顺时针方向旋转，使平面区域Ⅰ恒在平面区域Ⅱ的下方，但此时x+y的最大值小于9，所以直线l3的位置也不满足题意.

由此可见，要使x+y=9成立，区域Ⅰ和区域Ⅱ的交点必须在直线x+y=9上.

继续旋转直线l3：x-my+1=0.如图3所示，当它经过直线l1：x+3y-3=0与l4：x+y=9的交点A（12，-3）时，平面区域Ⅰ不恒在平面区域Ⅱ的下方，所以也不符合题意.

综上所述，如图4所示，当直线l3：x-my+1=0过直线l2：2x-y-3=0与l4：x+y=9的交点B（4，5）时，平面区域Ⅰ恒在平面区域Ⅱ的下方，且x+y取到最大值9，满足题意.

由l3：x-my+1=0过点（4，5），可解得m=1.

在约束条件含参的线性规划问题中，参数的本质就是控制含参直线位置的关键要素.我们可以先给参数取任意一个常数，即先把含参问题看成一个不含参问题，这样就能大致作出约束条件所表示的平面区域.再把已知最值的线性目标函数转化为一个不等式，作出该不等式表示的平面区域.根据题意平移或旋转含参直线的位置，并判断这两个平面区域的位置关系，求出参数值.