简单的线性(整数)规划问题
一.知识要点：
1.线性规划的基础概念
(1)线性约束条件
约束条件都是关于x, y的一次整式不等式.
(2)目标函数
待求最值(最大值或最小值)的函数.
(3)线性目标函数
目标函数是关于变量x, y的一次解析式(整式).
(4)线性规划
在线性约束条件下求线性目标函数的最大值或最小值的问题, 其中在限定变量为整数的时候, 对应的线性规划问题, 也称为整数规划问题.
(5)可行解
满足全部约束条件的解(x, y).
(6)可行域
全部可行解构成的集合称为线性规划问题的可行域.
(7)最优解
使目标函数取到最大值或最小值的可行解.
注意:
①线性约束条件即可用二元一次不等式表示, 也可以用二元一次方程表示.
②最优解如果存在(当然, 最优解有不存在的情况), 其个数并不一定是唯一的, 可能有多个最优解, 也可能存在无数个最优解.
③目标函数z ax by
=+取到最优解(最大或最小值)的点, 往往出现在可行域的顶点或边界上.
④对于整数规划问题(,
x y
ゥ), 最优解未必在边界或顶点处取
∈∈
得, 往往要在可行域的顶点或边界附近寻找.
⑤寻找最优解的前提是尽量准确画出可行域的草图, 从而有助于我们发现最优解.
二. 解题思路:
解决线性规划问题, 先要准确作出可行域, 且明白目标函数表示的几何意义, 通过数形结合找到目标函数取到最值时可行域的顶点(或边界上的点). 而对于整数规划问题, 则应该进一步验证解决, 边界点或顶点可能不在是最优点, 而是在它们的临近区域的整点.
三．求解步骤
①在平面直角坐标系中画出可行域(对于应用问题, 则要先正确写出
规划模型及满足的约束条件, 再画出可行域).
②结合目标函数的几何意义, 将目标函数变形写成直线的方程形式或写成一次函数的形式.
③确定最优点: 在可行域平行移动目标函数变形后的直线, 从而找到最优点.
④ 将最优点的坐标代入目标函数即可求出最大值或最小值.
四. 高考题演练
1. (新课标全国高考) 设x , y 满足约束条件1010,3x y x y x -+≥⎧⎪
+-≥⎨⎪≤⎩
则23z x y =-的
最小值是( ) 提示1 A. 7- B. 6- C. 5- D. 3-
2. (高考) 若变量x , y 满足约束条件210x y x y +≤⎧⎪
≥⎨⎪≥⎩
, 则2z x y =+的最大值和
最小值分别为( ). 提示2 A. 43和 B. 4和2 C. 3和2 D. 2和0 3. (高考) 某旅行社租用A 、B 两种型号的客车安排900名客人旅行, A 、
B 两种车辆的载客量分别为36人和60人, 租金分别为1600元/
辆和2400元/辆, 旅行社要求租车的总数不超过21辆, 且B 型车不多于A 型车7辆. 则租金最小为( ). 提示3 A. 31200元 B. 36000元 C. 36800元 D. 38400元 4. (高考) 若变量x , y
满足约束条件211y x
x y y ≤⎧⎪
+≤⎨⎪≥-⎩
, 则2x y +的最大值为
( ). 提示4 A. 52
- B. 0 C. 53
D.
52
5. (天津高考) 设变量,x y满足约束条件
360,
20,
30
x y
x y
y
+-≥
⎧
⎪
--≤
⎨
⎪-≤
⎩
则目标函数
2
z y x
=-的最小值为( ) 提示5
A. 7-
B. 4-
C.1
D. 2
6. (高考) 若点(x, y)位于曲线y x
=与2
y=所围成的封闭区域, 则2x y
-的最小值是( ). 提示6
A. 6-
B. 2-
C.0
D. 2
7. (高考) 若变量,x y满足约束条件
8,
24
,
x y
y x
x
y
+≤
⎧
⎪-≤
⎪
⎨
≥
⎪
⎪≥
⎩
且目标函数5
z y x
=-的
最大值为a, 最小值为b, 则a b-的值是( ) 提示7
A. 48
B. 30
C.24
D. 16
参考答案:
提示1：不等式组表示的平面区域如图1中阴 影部分所示, 其顶点A , B , C 的面积可直接算 出, 待求面积为
1144
(4)1.2233
ABC S AC h =
⋅=⨯-⨯=V 图1
提示2：不等式组10,
10,10x y x ax y +-≥⎧⎪
-≤⎨⎪-+≥⎩
所围成的平面区域如图2中阴影部分所
示, 面积为2, 则12114352
AC AC a a or =⋅⇒=+=⇒=-其中-5舍
去.
图2 图3
提示3: 已知可求出,.3
OA OB π
〈〉=u u u r u u u r 可设(2,0),(1,3),(,),OA OB OP x y ===u u u r u u u r u u u r 则
1(22x x y λλμμ⎧=⎪+=⎧⎪⎪⇒⎨=⎪=⎪⎩
,
由12y y λμ+≤⇒-+≤ 可行域参考图3,
所求面积1
242
S =⨯⨯=
可行域由如下四个子区域拼接而成:
①
002y y
y y y y y ≥≥≥⇔≥⎨⎨⎪-+≤≤+⎩②
002y
y y y y y y ≥≥≤⇔≤⎨⎨⎪--≤⎪≥-⎪⎩
③
0233y
y y y y y y x ≤≤≥⇔≥⎨⎨⎪⎪++≤⎩⎪≤+⎪⎩
④
002y y y y y y y ≤≤≤⇔≤⎨⎨⎪⎪+-≤≥-⎩⎩
提示4：已知0,0,a b ≥≥且当0,
0,1x y x y ≥⎧⎪
≥⎨⎪+≤⎩
时, 恒有1ax by +≤⇒
当0110 1.x y by b b =⇒=⇒=≤⇒≤≤同理, 当0110 1.y x ax a a =⇒=⇒=≤⇒≤≤
不等式组
01
01
a
b
≤≤
⎧
⎨
≤≤
⎩
所围成的平面区域参考图4, 其面积为1.
图4 图5
提示5: 由不等式组直接作出平面区域见图5, 注意直线20
kx y
-+=过
定点(0, 2). 由平面区域面积为4, 可知122241 3.
2
k k or
⨯⨯+=⇒=-
其中-3舍去.
提示6：换元法
平面区域{}
(,)(,)
B x y x y x y A
=+-∈, 可令2,
2
m n
x
m x y
n x y m n
y
+
⎧
=
⎪
=+
⎧⎪
⇒
⎨⎨
=--
⎩⎪=
⎪⎩
再根据条件,
1
221
(,)00,
2
2
m n m n
m
m n
x y A m n
m n
m n
+-
⎧
+≤
⎪
≤
⎧
⎪
+
⎪⎪
∈⇔≥⇔+≥
⎨⎨
⎪⎪-≥
⎩
-
⎪
≥
⎪⎩
由此不等式组确定的平面区域即为{}
(,)(,)
B x y x y x y A
=+-∈确定的平面区域, 见图6, 其面积
为112 1.
2
⨯⨯=
图6 图7
提示7: 平面区域D见上图7阴影部分所示, 直线1
y kx
=+过定点(0, 1)根据平面几何知识可知, 若直线1
y kx
=+将区域D分成面积相等的两
部分, 则直线1
y kx
=+只需过AB的中点即可. 易求中点坐标
33 (,)
22
. 再
代入到直线1
y kx
=+, 可求
1
.
3 k=。