高等数学第10章 线性规划

线性规划1.简介：线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.规划问题。

一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。

在优化模型中，如果目标函数f(x)和约束条件中的gi(x)都是线性函数，则该模型称为线性规划。

2.线性规划的3个基本要素（1）决策变量（2）目标函数f(x)（3）约束条件（gi(x)≤0称为约束条件）3.建立线性规划的模型（1）找出待定的未知变量（决策变量），并用袋鼠符号表示他们。

（2）找出问题中所有的限制或者约束，写出未知变量的线性方程或线性不等式。

（3）找到模型的目标或判据，写成决策变量的线性函数，以便求出其最大值或最小值。

以下题为例，来了解一下如何将线性规划用与实际的解题与生活中。

生产计划问题某工厂生产甲乙两种产品，每单位产品消耗和获得的利润如表试拟订生产计划，使该厂获得利润最大解答：根据解题的三个基本步骤（1）找出未知变量，用符号表示：设甲乙两种产品的生产量分别为x1与x2吨，利润为z万元。

（2）确定约束条件：在这道题目当中约束条件都分别为：钢材，电力，工作日以及生产量不能为负的限制钢材：9x 1+5 x 2≤360，电力：4x 1+5 x 2≤200，工作日：3x 1+10 x 2≤300，x 1 ≥0 ，x 2 ≥0，（3）确定目标函数：Z=7x 1+12 x 2所以综合上面这三步可知，这个生产组合问题的线性规划的数学模型为：max Z=7x 1+12 x 2s.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥≤+≤+≤+00300103200543605921212121x x x x x x x x4.使用MATLAB 解决线性规划问题依旧是以上题为例，将其用MATLAB 来表示出来1.将目标函数用矩阵的乘法来表示max Z=(7 12)⎪⎪⎭⎫ ⎝⎛21x x 2.将约束条件也用矩阵的乘法表示s.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧⎪⎪⎭⎫ ⎝⎛≤⎪⎪⎭⎫ ⎝⎛⎪⎪⎪⎭⎫ ⎝⎛≤⎪⎪⎭⎫ ⎝⎛⎪⎪⎪⎭⎫ ⎝⎛2121003002003601035459x x x x 编写MATLAB 的程序如下：c=[-7 -12]; (由于是max 函数，因此将目标函数的系数全部变为负数)A=[9,5;4,5;3,10];b=[360;200;300];Aeq=[];beq=[];vlb=[0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)其运行结果显示如下：x =20.000024.0000fval =-428.00005.MATLAB 求解线性规划的语句(1)c=[ ] 表示目标函数的各个决策变量的系数(2)A=[ ] 表示约束条件中≥或≤的式子中的各个决策变量的系数。

线性规划知识点归纳总结一、知识梳理1 目标函数：P=2x＋y是一个含有两个变量x和y的函数，称为目标函数。

2 可行域：约束条件表示的平面区域称为可行域。

3 整点：坐标为整数的点叫做整点。

4 线性规划问题：求线性目标函数在线性约束条件下的最大值或最小值的问题，通常称为线性规划问题。

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

5 整数线性规划：要求量整数的线性规划称为整数线性规划。

二、疑难知识导析线性规划是一门研究如何使用最少的人力、物力和财力去最优地完成科学研究、工业设计、经济管理中实际问题的专门学科，主要在以下两类问题中得到应用：一是在人力、物力、财务等资源一定和条件下，如何使用它们来完成最多的任务；二是给一项任务，如何合理安排和规划，能以最少的人力、物力、资金等资源来完成该项任务。

1 对于不含边界的区域，要将边界画成虚线。

2 确定二元一次不等式所表示的平面区域有种方法，常用的一种方法是“选点法”：任选一个不在直线上的点，检验它的坐标是否满足所给的不等式，若适合，则该点所在的一侧即为不等式所表示的平面区域；否则，直线的另一端为所求的平面区域。

若直线不过原点，通常选择原点代入检验。

3 平移直线y=-kx+P时，直线必须经过可行域。

4 对于有实际背景的线性规划问题，可行域通常是位于第一象限内的一个凸多边形区域，此时变动直线的最佳位置一般通过这个凸多边形的顶点。

5 简单线性规划问题就是求线性目标函数在线性约束条件下的最优解，无论此类题目是以什么实际问题提出，其求解的格式与步骤是不变的：（1）寻找线性约束条件，线性目标函数；（2）由二元一次不等于表示的平面区域做出可行域；（3）在可行域内求目标函数的最优解。

积储知识：一、1．占P（x0，y0）在直线Ax+By+C=0上，则点P坐标适合方程，即Ax0+ y0+C=02．点P（x0，y0）在直线Ax+By+C=0上方（左上或右下），则当B>0时，Ax0+ y0+C >0；当B<0时，Ax0+ y0+C<0 3．点P（x0+，y0）D在直线Ax0+ y0+C=0下方（左下或右下），当B>0时，Ax0+ y0+C<0；当B>0时，Ax0+ y0+C>0 注意：（1）在直线Ax+ By+C=0同一侧的所有点，把它的坐标（x，y）代入Ax+ By+C=0，所得实数的符号都相同。

3.4.2 简单线性规划1. 相关定义：(1)线性规划问题：求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。

(2)可行解：满足线性约束条件的解叫做可行解。

(3)可行域：由所有可行解组成的集合叫做可行域。

(4)最优解：分别使目标函数取得最大值和最小值的可行解叫做最优解。

2. 线性规划问题的求解步骤：(1)先设出决策变量，找出约束条件和线性目标函数；(2)作出相应的图象（注意特殊点与边界）(3)利用图象，在线性约束条件下找出决策变量，使线性目标函数达到最大（小）值；在在求线性目标函数的最大（小）值时，直线往右（左）平移则值随之增大（小），这样就可以在可行域中确定最优解。

注：①对线性目标函数中的符号一定要注意：当时，当直线过可行域且在y 轴截距最大时，值最大，在y 轴截距最小时，值最小；当时，当直线过可行域且在y 轴截距最大时，值最小，在y 轴截距最小时，值最大。

②如果可行域是一个多边形，那么一般在其顶点处使目标函数取得最大或最小值，最优解一般就是多边形的某个顶点。

例1：设满足约束条件：，分别求下列目标函数的的最大值与最小值：(1)； (2)；(3)（是整数）； （4）； （5） 示中的区域，且【解析】先作可行域，如下图所求得、、),(y x ny mx z +=0=+ny mx By Ax z +=B 0>B z z 0<B z z y x ,⎪⎩⎪⎨⎧≥≤+-≤-1255334x y x y x y x z 106+=y x z -=2y x z -=2y x ,22y x +=ω1+=x y ωABC ∆)2,5(A)1,1(B )522,1(C(1)作出直线，再将直线平移，当的平行线过点B 时，可使达到最小值；当的平行线过点A 时，可使达到最大值。

故，(2)同上，作出直线，再将直线平移，当的平行线过点C 时，可使达到最小值；当的平行线过点A 时，可使达到最大值。

线性规划知识点一、什么是线性规划线性规划是一种数学优化方法，用于解决在给定约束条件下的线性目标函数的最优化问题。

线性规划的目标函数和约束条件都是线性的，因此可以通过线性代数的方法进行求解。

线性规划在实际问题中有广泛的应用，如生产计划、资源分配、运输问题等。

二、线性规划的基本要素1. 目标函数：线性规划的目标是最大化或最小化一个线性函数，通常表示为Z = c₁x₁ + c₂x₂ + ... + cₙxₙ，其中 Z 为目标函数值，c₁, c₂, ..., cₙ 为系数，x₁,x₂, ..., xₙ 为决策变量。

2. 决策变量：决策变量是问题中需要决策的变量，通常表示为x₁, x₂, ..., xₙ。

决策变量的取值决定了目标函数的值。

3. 约束条件：约束条件限制了决策变量的取值范围。

约束条件可以是等式约束或不等式约束，通常表示为 a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁，a₂₁x₁ +a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂，...，aₙ₁x₁ + aₙ₂x₂ + ... + aₙₙxₙ ≤ bₙ，其中 a₁₁, a₁₂, ..., aₙₙ 为系数，b₁, b₂, ..., bₙ 为常数。

4. 非负约束：线性规划中通常要求决策变量的取值非负，即 x₁ ≥ 0, x₂ ≥ 0, ...,xₙ ≥ 0。

三、线性规划的解法线性规划可以通过不同的方法进行求解，常见的方法包括图形法、单纯形法和内点法。

1. 图形法：图形法适用于二维或三维的线性规划问题。

首先将目标函数和约束条件转化为几何形式，然后在坐标系中绘制约束条件的图形，最后通过图形的分析找到最优解点。

2. 单纯形法：单纯形法是一种通过迭代寻找最优解的方法。

该方法从一个可行解开始，通过不断移动到相邻的可行解来逐步接近最优解。

单纯形法的核心是单纯形表，通过表格的变换和计算来确定下一个迭代点，直到找到最优解。

3. 内点法：内点法是一种通过迭代寻找最优解的方法。

线性规划是一种优化方法，Matlab优化工具箱中有现成函数linprog对如下式描述的LP问题求解：%min f'x%s.t .(约束条件)：Ax<=b%(等式约束条件)：Aeqx=beq%lb<=x<=ublinprog函数的调用格式如下：x=linprog(f,A,b)x=linprog(f,A,b,Aeq,beq)x=linprog(f,A,b,Aeq,beq,lb,ub)x=linprog(f,A,b,Aeq,beq,lb,ub,x0)x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)[x,fval]=linprog(…)[x, fval, exitflag]=linprog(…)[x, fval, exitflag, output]=linprog(…)[x, fval, exitflag, output, lambda]=linprog(…)其中：x=linprog(f,A,b)返回值x为最优解向量。

x=linprog(f,A,b,Aeq,beq) 作有等式约束的问题。

若没有不等式约束，则令A=[ ]、b=[ ] 。

x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options) 中lb ,ub为变量x的下界和上界，x0为初值点，options为指定优化参数进行最小化。

Options的参数描述：Display显示水平。

选择’off’ 不显示输出；选择’Iter’显示每一步迭代过程的输出；选择’final’ 显示最终结果。

MaxFunEvals 函数评价的最大允许次数Maxiter 最大允许迭代次数TolXx处的终止容限[x,fval]=linprog(…) 左端fval 返回解x处的目标函数值。

[x,fval,exitflag,output,lambda]=linprog(f,A,b, Aeq,beq,lb,ub,x0) 的输出部分：exitflag描述函数计算的退出条件：若为正值，表示目标函数收敛于解x处；若为负值，表示目标函数不收敛；若为零值，表示已经达到函数评价或迭代的最大次数。

高中必修5线性规划最快的方法简单的线性规划问题 一、知识梳理1. 目标函数: Ｐ ＝２ｘ＋ｙ是一个含有两个变 量 ｘ 和ｙ 的 函数，称为目标函数．2.可行域:约束条件所表示的平面区域称为可行域.3. 整点:坐标为整数的点叫做整点．4.线性规划问题:求线性目标函数在线性约束条件下的最大值或最小值的问题，通常称为线性规划问题．只含有两个变量的简单线性规划问题可用图解法来解决．5. 整数线性规划:要求量取整数的线性规划称为整数线性规划． 二、疑难知识导析线性规划是一门研究如何使用最少的人力、物力和财力去最优地完成科学研究、工业设计、经济管理中实际问题的专门学科.主要在以下两类问题中得到应用：一是在人力、物力、财务等资源一定的条件下，如何使用它们来完成最多的任务；二是给一项任务，如何合理安排和规划，能以最少的人力、物力、资金等资源来完成该项任务. 1.对于不含边界的区域，要将边界画成虚线．2.确定二元一次不等式所表示的平面区域有多种方法，常用的一种方法是“选点法”：任选一个不在直线上的点，检验它的坐标是否满足所给的不等式，若适合，则该点所在的一侧即为不等式所表示的平面区域；否则，直线的另一侧为所求的平面区域．若 直 线 不 过 原点，通 常 选 择 原 点 代入检验．3. 平 移 直 线 ｙ＝－k ｘ ＋Ｐ时，直线必须经过可行域．4.对于有实际背景的线性规划问题，可行域通常是位于第一象限内的一个凸多边形区域，此时变动直线的最佳位置一般通过这个凸多边形的顶点．5.简单线性规划问题就是求线性目标函数在线性约束条件下的最优解，无论此类题目是以什么实际问题提出，其求解的格式与步骤是不变的：（1）寻找线性约束条件，线性目标函数；（2）由二元一次不等式表示的平面区域做出可行域；（3）在可行域内求目标函数的最优解.积储知识：一． 1.点P(x 0,y 0)在直线Ax+By+C=0上，则点P 坐标适合方程，即Ax 0+By 0+C=02. 点P(x 0,y 0)在直线Ax+By+C=0上方（左上或右上），则当B>0时，Ax 0+By 0+C>0;当B<0时，Ax 0+By 0+C<03. 点P(x 0,y 0)在直线Ax+By+C=0下方（左下或右下），当B>0时，Ax 0+By 0+C<0;当B<0时，Ax 0+By 0+C>0 注意：（1）在直线Ax+By+C=0同一侧的所有点，把它的坐标(x,y)代入Ax+By+C,所得实数的符号都相同,（2）在直线Ax+By+C=0的两侧的两点，把它的坐标代入Ax+By+C,所得到实数的符号相反, 即：1.点P(x 1,y 1)和点Q(x 2,y 2)在直线 Ax+By+C=0的同侧，则有（Ax 1+By 1+C ）( Ax 2+By 2+C)>02.点P(x 1,y 1)和点Q(x 2,y 2)在直线 Ax+By+C=0的两侧，则有（Ax 1+By 1+C ）( Ax 2+By 2+C)<0二.二元一次不等式表示平面区域:①二元一次不等式Ax+By+C>0（或<0）在平面直角坐标系中表示直线Ax+By+C=0某一侧所有点组成的平面区域. 不．包括边界; ②二元一次不等式Ax+By+C ≥0（或≤0）在平面直角坐标系中表示直线Ax+By+C=0某一侧所有点组成的平面区域且包括边界;注意：作图时,不包括边界画成虚线;包括边界画成实线. 三、判断二元一次不等式表示哪一侧平面区域的方法: 方法一:取特殊点检验; “直线定界、特殊点定域原因:由于对在直线Ax+By+C=0的同一侧的所有点(x,y),把它的坐标(x,y)代入Ax+By+C,所得到的实数的符号都相同,所以只需在此直线的某一侧取一个特殊点(x 0,y 0),从Ax 0+By 0+C 的正负即可判断Ax+By+C>0表示直线哪一侧的平面区域.特殊地,当C ≠0时，常把原点作为特殊点，当C=0时，可用（0，1）或（1，0）当特殊点，若点坐标代入适合不等式则此点所在的区域为需画的区域，否则是另一侧区域为需画区域。