线性规划的概念

3.6：线性规划

目录：

（1）线性规划的基本概念

（2）线性规划在实际问题中的应用

【知识点1：线性规划的基本概念】

(1)如果对于变量x 、y 的约束条件，都是关于x 、y 的一次不等式，则称这些约束条件为__线性约束条件__(),z f x y =是欲求函数的最大值或最小值所涉及的变量x 、y 的解析式，叫做__目标函数_，当(),f x y 是x 、y 的一次解析式时，(),z f x y =叫做_线性目标函数__. (2)求线性目标函数在线性约束条件下的最大值或最小值问题，称为__线性规划问题__ ；满足线性约束条件的解(),x y 叫做__可行解_；由所有可行解组成的集合叫做__可行域_；使目标函数取得最大值或最小值的可行解叫做_最优解__

例题：若变量x 、y 满足约束条件2

10x y x y +≤??

≥??≥?

，则z x y =+的最大值和最小值分别为

( B )

A. 4和3

B. 4和2

C. 3和2

D. 2和0

分析：本题考查了不等式组表示平面区域，目标函数最值求法.

解：画出可行域如图

作020l x y +=：

所以当直线2z x y =+过()20A ，

时z 最大，过()1,0B 时z 最小max min 4, 2.z z ==

变式1：已知2z x y =+，式子中变量x 、y 满足条件11y x

x y y ≤??

+≤??≥-?

，则z 的最大值是__3___

解：不等式组表示的平面区域如图所示.

作直线0:20l x y +=，平移直线0l ，当直线0l 经过

平面区域的点()21A -，时，z 取最大值2213?-=.

变式2：设2z x y =+，式中变量x 、y 满足条件43

35251x y x y x -≤-??

+≤??≥?

，求z 的最大值和最小值

分析：由于所给约束条件及目标函数均为关于x 、y 的一次式，所以此问题是简单线性

规划问题，使用图解法求解

解：作出不等式组表示的平面区域(即可行域)，如图所示．

把2z x y =+变形为2y x z =-+，得到斜率为-2，在y 轴上的截距为z ，随z 变化的一族平行直线．

由图可看出，当直线2z x y =+经过可行域上的点A 时，截距z 最大，经过点B 时，截距z 最小．

解方程组430

35250x y x y -+=??+-=?，得A 点坐标为()5,2，

解方程组1

430x x y =??-+=?

，得B 点坐标为()1,1

所以max min 25212,211 3.z z =?+==?+=

变式3：若变量x 、y 满足约束条件6

321x y x y x +≤??

-≤-??≥?

，则23z x y =+的最小值为( C )

A. 17

B. 14

C. 5

D. 3

解:作出可行域(如图阴影部分所示)．

作出直线:230l x y +=.

平移直线l 到l ′的位置，使直线l 通过可行域中的A 点(如图) 这时直线在y 轴上的截距最小，z 取得最小值． 解方程组132x x y =??-=-?，得最优解1

1x y =??=?，

min 21315z ∴=?+?=

【知识点2:线性规划在实际问题中的应用】

例题：某工厂生产甲、乙两种产品，其产量分别为45个与55个，所用原料为A 、B 两种规格金属板，每张面积分别为2m2与3m2.用A 种规格金属板可造甲种产品3个，乙种产品5个；用B 种规格金属板可造甲、乙两种产品各6个．问A 、B 两种规格金属板各取多少张，才能完成计划，并使总的用料面积最省？

解：设A 、B 两种金属板分别取x 张、y 张，用料面积为z ，则约束条件为 3645

565500

x y x y x y +≥??+≥?

?

≥??≥? 目标函数为23z x y =+.

作出以上不等式组所表示的平面区域(即可行域)，如图所示：

23z x y =+变为233z y x =-+，得斜率为23-，在y 轴上截距为3

z

且随z 变化的一组平行

直线．

当直线23z x y =+过可行域上点M 时，截距最小，z 最小． 解方程组 ，得M 点的坐标为(5,5)．

此时()

2min 253525z m =?+?=．

答：当两种金属板各取5张时，用料面积最省．

变式1：4个茶杯和5包茶叶的价格之和小于22元，而6个茶杯与3包茶叶的价格之和大于24元，则2个茶杯和3包茶叶的价格比较( A ) A ．2个茶杯贵 B ．3包茶叶贵 C ．相同 D ．无法确定 解：设茶杯每个x 元，茶叶每包y 元，则

45226324,x y x y x y N +

+>??∈?

2U x y =-取值的符号判断如下

由2.033U y x U =

-=当时，过点()32A ，

，往下平移．经过可行域内的点03

U

-< ∴0U >，即23x y >.往上平移不经过可行域内的点． ∴选A.

变式2 已知x 、y 满足20

40250x y x y x y -+≥??

+-≥??--≤?

，求：

(1)221025z x y y =+-+的最小值； (2)1

1

y z x +=

+的取值范围. 分析：(1)将z 化为()2

25z x y =+-，问题转化为求可行域中的点与定点的最小距离问题； (2)将式子化为(1)

(1)

y z x --=--或1(1)y z x +=+，问题转化为求可行域中的点与定点的连线的

斜率的最值问题

解：作出可行域如图

并求出点A 、B 的坐标分别为(13)(31)，，

(1)()2

25z x y =+-表示可行域内任一点(),x y 到定点()0,5M 的距离的平方，过M 作直线

AC 的垂线MN ，垂足为N ，则：2

2

min

922z MN ??=∣∣== ? ???

. (2)1(1)

1(1)

y y z x x +--=

=

+--表示可行域内任一点(),x y 与定点()1,1Q --连线的斜率，可知，kAQ 最大，kQB 最小．而31111

2,11312

QA QB k k ++=

===++. ∴z 的取值范围为1,22??

????

．

点评:求非线性目标函数的最值，要注意分析目标函数所表示的几何意义，通常与截距、斜率、距离等联系，是数列结合的体现．

变式3 在条件02

021

x y x y ≤≤??≤≤??-≥?

下，()()2211z x y =++-的取值范围是___122??

????，__.

解：由约束条件作出可行域如图

目标函数表示点(x y)，与点(11)M ，的距离的平方．由图可知，z 的最小值为点M 与直线1x y -=的距离的平方．即2

min

1

22z ??==. z 的最大值为点()11M ，与点(20)B ，的距离的平方： 即()()2

2

max 12102z =-+-=. ∴z 的取值范围为122??

????

，．

变式4 设变量x 、y 满足条件3210411,0,0

x y x y x Z y Z x y +≤??+≤?

?∈∈??>>?. 求54S x y =+的最大值.

错解：依约束条件画出可行域如图所示

如先不考虑x 、y 为整数的条件，则当直线54x y S +=过点923,510A ??

???

时，

54S x y =+max 91

5

S =

取最大值， . 因为x 、y 为整数，而离点A 最近的整点是()1,2C ，这时13S =，所要求的最大值为13. 分析：显然整点(21)B ，满足约束条件，且此时14S =，故上述解法不正确． 对于整点解问题，其最优解不一定是离边界点最近的整点． 而要先对边界点作目标函数t Ax By =+的图像， 则最优解是在可行域内离直线t Ax By =+最近的整点． 正解：依约束条件画出可行域如图示 作直线:540l x y +=

平行移动直线l 经过可行域内的整点(21)B ，时，max 14S =.

线性规划的概念

3.6：线性规划 目录： （1）线性规划的基本概念 （2）线性规划在实际问题中的应用 【知识点1：线性规划的基本概念】 (1)如果对于变量x 、y 的约束条件，都是关于x 、y 的一次不等式，则称这些约束条件为__线性约束条件__(),z f x y =是欲求函数的最大值或最小值所涉及的变量x 、y 的解析式，叫做__目标函数_，当(),f x y 是x 、y 的一次解析式时，(),z f x y =叫做_线性目标函数__. (2)求线性目标函数在线性约束条件下的最大值或最小值问题，称为__线性规划问题__ ；满足线性约束条件的解(),x y 叫做__可行解_；由所有可行解组成的集合叫做__可行域_；使目标函数取得最大值或最小值的可行解叫做_最优解__ 例题：若变量x 、y 满足约束条件2 10x y x y +≤?? ≥??≥? ，则z x y =+的最大值和最小值分别为 ( B ) A. 4和3 B. 4和2 C. 3和2 D. 2和0 分析：本题考查了不等式组表示平面区域，目标函数最值求法. 解：画出可行域如图 作020l x y +=： 所以当直线2z x y =+过()20A ， 时z 最大，过()1,0B 时z 最小max min 4, 2.z z == 变式1：已知2z x y =+，式子中变量x 、y 满足条件11y x x y y ≤?? +≤??≥-? ，则z 的最大值是__3___ 解：不等式组表示的平面区域如图所示.

作直线0:20l x y +=，平移直线0l ，当直线0l 经过 平面区域的点()21A -，时，z 取最大值2213?-=. 变式2：设2z x y =+，式中变量x 、y 满足条件43 35251x y x y x -≤-?? +≤??≥? ，求z 的最大值和最小值 分析：由于所给约束条件及目标函数均为关于x 、y 的一次式，所以此问题是简单线性 规划问题，使用图解法求解 解：作出不等式组表示的平面区域(即可行域)，如图所示． 把2z x y =+变形为2y x z =-+，得到斜率为-2，在y 轴上的截距为z ，随z 变化的一族平行直线． 由图可看出，当直线2z x y =+经过可行域上的点A 时，截距z 最大，经过点B 时，截距z 最小． 解方程组430 35250x y x y -+=??+-=?，得A 点坐标为()5,2， 解方程组1 430x x y =??-+=? ，得B 点坐标为()1,1 所以max min 25212,211 3.z z =?+==?+= 变式3：若变量x 、y 满足约束条件6 321x y x y x +≤?? -≤-??≥? ，则23z x y =+的最小值为( C ) A. 17 B. 14 C. 5 D. 3

简单的线性规划问题附答案)

简单的线性规划问题 [学习目标] 1.了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念.2.了解线性规划问题的图解法，并能应用它解决一些简单的实际问题． 知识点一 线性规划中的基本概念 知识点二 1．目标函数的最值 线性目标函数z ＝ax ＋by (b ≠0)对应的斜截式直线方程是y ＝－a b x ＋z b ，在y 轴上的截距是z b ，当z 变化时，方程表 示一组互相平行的直线． 当b >0，截距最大时，z 取得最大值，截距最小时，z 取得最小值； 当b <0，截距最大时，z 取得最小值，截距最小时，z 取得最大值． 2．解决简单线性规划问题的一般步骤 在确定线性约束条件和线性目标函数的前提下，解决简单线性规划问题的步骤可以概括为：“画、移、求、答”四步，即， (1)画：根据线性约束条件，在平面直角坐标系中，把可行域表示的平面图形准确地画出来，可行域可以是封闭的多边形，也可以是一侧开放的无限大的平面区域． (2)移：运用数形结合的思想，把目标函数表示的直线平行移动，最先通过或最后通过的顶点(或边界)便是最优解． (3)求：解方程组求最优解，进而求出目标函数的最大值或最小值． (4)答：写出答案． 知识点三 简单线性规划问题的实际应用 1．线性规划的实际问题的类型 (1)给定一定数量的人力、物力资源，问怎样运用这些资源，使完成的任务量最大，收到的效益最大； (2)给定一项任务，问怎样统筹安排，使完成这项任务耗费的人力、物力资源量最小． 常见问题有： ①物资调动问题 例如，已知两煤矿每年的产量，煤需经两个车站运往外地，两个车站的运输能力是有限的，且已知两煤矿运往两个车站的运输价格，煤矿应怎样编制调动方案，才能使总运费最小？

线性规划基本概念及模型构建

LP （Linear Programming）

Alex 有一个家庭农场。除了农场上的农作物以外，他还饲养了一些猪拿到市场上出售，猪可获得的饲料及其所含成分如下表：Alex如何喂养猪更好？ 成分/每公斤 玉米槽料苜蓿每日最小需求量碳水化合物 蛋白质 维他命 成本(美分)903010842080207240606060200180150 问题1：科学养猪线性规划建模（猪饲料的配方）饲养成本最小

--- 每天玉米、槽料、苜蓿各喂多少公斤？ --- 必须满足要求12--- 追求成本最低 Min. 84x 1+ 72x 2+ 60x 3 3x 1x 2x 3 知识点 建模三要素 决策变量约 束目标 90x 1+ 20x 2+ 40x 3 ≥ 20030x 1+ 80x 2+ 60x 3 ≥ 18010x 1+ 20x 2+ 60x 3 ≥ 150 x i ≥0 , i =1，2，3 成分/每公 斤 玉米槽料苜蓿每日最小需求量碳水化合物 蛋白质 维他命 成本(美分)903010842080207240606060200180150

s.t. 90x 1+ 20x 2+ 40x 3 ≥ 200 30x 1 + 80x 2+ 60x 3 ≥ 180 10x 1+ 20x 2+ 60x 3 ≥ 150 x i ≥0 , i =1,2,3 Min . 84x 1+ 72x 2+ 60x 3 目标函数约束函数符号中必含等号符号的右侧为常数线性--变量均为1次方 Max. 或 Min.线性--所有变量均为1次方常规约束：变量非负！知识点 模型表示

？线性规划模型能求解出来吗？ 能！--- 万能的单纯形法 结合软件 QSB应用