简单的线性 (整数 )规划问题
一. 知识要点：
1.线性规划的基础概念
(1)线性约束条件
约束条件都是关于x, y 的一次整式不等式.
(2)目标函数
待求最值 (最大值或最小值 )的函数 .
(3)线性目标函数
目标函数是关于变量x, y 的一次解析式(整式).
(4)线性规划
在线性约束条件下求线性目标函数的最大值或最小值的问题, 其中在限定变量为整数的时候 , 对应的线性规划问题 , 也称为整数规划问题 .
(5)可行解
满足全部约束条件的解 (x, y).
(6)可行域
全部可行解构成的集合称为线性规划问题的可行域 .
(7)最优解
使目标函数取到最大值或最小值的可行解.
注意 :
①线性约束条件即可用二元一次不等式表示 , 也可以用二元一次方程
表示 .
②最优解如果存在 (当然 , 最优解有不存在的情况 ), 其个数并不一定是唯一的 , 可能有多个最优解 , 也可能存在无数个最优解 .
③目标函数 z ax by 取到最优解(最大或最小值)的点,往往出现在可行域的顶点或边界上 .
④对于整数规划问题 ( xゥ, y ), 最优解未必在边界或顶点处取得, 往往
要在可行域的顶点或边界附近寻找 .
⑤寻找最优解的前提是尽量准确画出可行域的草图 , 从而有助于我们发现最优解 .
二.解题思路 :
解决线性规划问题 , 先要准确作出可行域 , 且明白目标函数表示的
几何意义 , 通过数形结合找到目标函数取到最值时可行域的顶点 (或边界上的点). 而对于整数规划问题, 则应该进一步验证解决, 边界点或顶点可能不在是最优点 , 而是在它们的临近区域的整点 .
三．求解步骤
①在平面直角坐标系中画出可行域(对于应用问题 , 则要先正确写出
规划模型及满足的约束条件, 再画出可行域 ).
②结合目标函数的几何意义 , 将目标函数变形写成直线的方程形式或
写成一次函数的形式 .
③确定最优点 : 在可行域平行移动目标函数变形后的直线 , 从而找到最优点 .
④将最优点的坐标代入目标函数即可求出最大值或最小值.
四. 高考题演练
x y 10
1. (新课标全国高考 ) 设x, y满足约束条件x y 1 0,则z 2 x 3y 的
x 3
最小值是 ()提示1
A.7
B.6
C.5
D.3
x y2
2. (高考 ) 若变量x, y满足约束条件x 1,则z2x y 的最大值和
y 0
最小值分别为 ().提示 2
A. 4和3
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元
y2x
4. (高考 ) 若变量,y满足约束条件, 则x 2 y 的最大值为
x y1
y1
().提示 4
A.5
B. 0
C.5
D.
5 232
3x y 60,
5. ( 天津高考) 设变量x, y 满足约束条件x y 2 0, 则目标函数
y 30
z y 2 x的最小值为()提示 5
A. 7
B.4
C. 1
D. 2
6. (高考 ) 若点 ( ,)位于曲线y x 与y 2 所围成的封闭区域,则 2x y
x y
的最小值是 ().提示 6
A. 6
B.2
C. 0
D.2
x y8,
2y x4
7. (高考 ) 若变量x, y满足约束条件, 且目标函数z 5y x 的
x0
y0
最大值为, 最小值为
b , 则a b 的值是() 提示 7
a
A. 48
B.30
C. 24
D. 16
参考答案 :
提示 1：不等式组表示的平面区域如图 1 中阴影部分所示 , 其顶点A, B, C的面积可直接算出, 待求面积为
S ABC1AC h1(44
) 1 4 .
V2233
x y 10,
图1
提示 2：不等式组x10,所围成的平面区域如图 2 中阴影部分所
ax y10
示, 面积为 2, 则21AC 1AC a 1 4 a3or 5 其中-5舍
2
去.
图 2
提示 3: 已知可求出
图 3
uuur uuur uuur uuur uuur
OA,OB. 可设 OA(2,0), OB (1, 3), OP(x, y), 则3
1
y
2 x ( x
)
2 3
, 由
1
3x
y 2y 2 3.
3
y
y
3
可行域参考图 3, 所求面积 S 2
1 4 3 4 3.
2
可行域由如下四个子区域拼接而成 :
3x y
3x y ① y 0
y 0
3x y 2y 2 3 y
3x 2 3
3x
y
3x y ② y 0
y 0
3x y 2y 2 3
y
3 x 2 3
3 3
3x y
3x y ③
y 0
y 0
3x
y 2 y
2 3
y
3
2 3
x
3
3
3x y
3x y ④
y 0
y 0
3x y 2 y 2 3 y
3x 2 3
x 0,
提示 4：已知 a 0, b 0, 且当
y
0,
时, 恒有 ax by 1
x
y 1
当 x 0 y 1 by b 1 0 b 1. 同理 , 当 y
x
1 ax a 1
0 a 1.
不等式组
a
1
所围成的平面区域参考图4, 其面积为 1. 0b1
图 4图 5
提示 5: 由不等式组直接作出平面区域见图5,注意直线 kx y 2 0 过
定点 (0, 2). 由平面区域面积为 4, 可知1
22k 2 4 k 1 or 3. 2
其中 -3 舍去 .提示 6：换元法
平面区域 B( x y, x y) ( x, y)
m n m n
22条件 ,m n
(x, y) A0
2
m n
20
m n
A ,可令
m
x y
x
2, 再根据
n x y m n
y
2
1
m1
m n 0, 由此不等式组确定的平
m n0
面区域即为 B(x y, x y) (x, y) A 确定的平面区域,见图6,其面积1
为 1 2 1.
2
图 6图7
提示 7: 平面区域D见上图 7 阴影部分所示 , 直线y kx 1过定点(0, 1)根据平面几何知识可知 , 若直线y kx 1将区域D分成面积相等的两
部分 , 则直线y kx 1只需过 AB 的中点即可.易求中点坐标(3
,
3
) .再
1.22
代入到直线 y kx 1 ,可求 k
3。