《线性规划》试题
一．单项选择题（每小题2分，共20分）
1．在有两个变量的线性规划问题中，若问题有唯一最优解，则（ ）
A.此最优解一定在可行域的一个顶点上达到。
B.此最优解一定在可行域的内部达到。
C.此最优解一定在可行域的一条直线段边界上达到。
D.此时可行域只有一个点。
2．设有两个变量的线性规划模型的可行域的图如下，若目标函数只在点处达到最优值，则此目标函数可能是（ ）
A.212x x z +=
B.2x z =
C.215x x z +=
D.218x x z +=
3.若线性规划模型有可行解，则此线性规划（ ）
基可行解必唯一。基可行解有无穷多个。基可行解个数必有限。基可行解都是最优解。 4．任何一个线性规划模型的可行解是（ ）
A. 一个无界集合。
B.是一个闭多面凸集。
C.是一个空集。
D.是一个无边界的集合 5．设有下面线性规划问题有最优解，则（ ）
..min ≥==X b AX t s CX f A. 此目标函数在可行域上必有下界 B.此目标函数在可行域上必有上界 C. 此目标函数在可行域上必有上界和下界 D.此目标函数在可行域上必无下界 6．设有线性规划模型
3213min x x x f ++=
s.t.
4
,3,2,1,07436326
213214321=≥=+=++=+++i x x x x x x x x x x i
则（ ）是一组对应于基的基变量
A.21,x x
B.321,,x x x
C.31,x x
D.432,,x x x 7．设有线性规划模型
..m a x ≥==X b
AX t s CX
f
则它的对偶线性规划的目标函数是（ ）
A.CX g =max
B. Cb g =min
C.Ub g =min
D.CX g =max 8．设有两个对偶的线性规划问题的模型，下面说法正确的是（ ） A.一个模型有可行解且目标函数在可行集上无界，另一个模型有可行解。 B.一个问题有可行解且目标函数在可行集上有界，但另一个问题无可行解。 C.一个问题有可行解且目标函数在可行集上无界，另一个模型无可行解。
D.两个问题都有可行集，但目标函数在可行集上都无界。 9．下列有关运输问题的陈述不正确的有（ ） A.对平衡的运输问题来说，一定存在可行解。 B.对不平衡的运输问题来说，可能不存在最优解
C.若对一外运输问题来说存在最优解，则可断定此运输问题一定是平衡运输问题
D.若地一个运输问题来说存在可行解，则可断定此运输问题一定是平衡运输问题 10．下列图形不存在闭回路的有（ ）
二．填空题（每小题2分，共20分） 11．对于线性规划模型， 的可行解称为问题的最优解。
12．下列线性规划模型
21min x x f +-=
s.t. 0
,00
2
2212121≤≥≤+≤+-x x x x x x
的标准型是
。 13．设有线性规划模型 CX f =min s.t. j n
j j
p x
AX ∑==
1
（其中j p 为矩阵A 的第j 列）
0≥X (秩（A ）=m=A 的行数)
则 称为基（阵）。
14．设有线性规划模型 CX f =min
),,,(,..211
m j n
j j p p p b p x AX t s ???==∑=为矩阵A 的基阵。
0≥X
称为基可行解。
15．设标准线性规划模型非基变量的下标集是R ，典式中的目标函数为
j R
j j x f f ∑∈-=λ0min ，则当所有检验数 时，对应的基可行解0X 为
最优解。
16．0
X 是线性规划模型
..min ≥==X b AX t s CX f 的最优基可行解，对应的基阵为B ，则=0
U 是其对偶线性规划模型
的最优解。
17．设0
X 是线性规划模型
..min ≥==X b AX t s CX f 的最优基可行解，0
U 是其对偶线性规划模型的最优解，则0
X 与0
U 的关系是 。
18．对于运输问题的一个基可行解，设kl x 为一非基变量，并设从kl x 出发基变量为其余顶点的闭回路为：
l p q p q p q p kq kl l l l x x x x x x ,,,,,,21111???
还知，该闭回路上偶序顶点对应运价及奇序顶点对应的运价，则kl x 的对应的检验数为
。 19．设运输问题的数据如下表：
用左上角法求得初始方案为 。
20．已知：),,(0
010n x x x ???=是d x b Ax ≤≤=0,的基可行解，若 ，
则称j x 为相应的第一类非基变量，若 ，则称j x 为相应的第二类非基变量。
三．计算题（一）（每小题10分，共20分） 21．设有两个变量的线性规划模型
s.t.
,021272172max 2121212
1≥≥≤+≤++=x x x x x x x x f
用图解法求其最优解。
22．用单纯形方法求解下列线性规划问题。 2143m i n x x f +-=
1x 3x + =5
2x 4x + =2
2143x x + 5x +=12
)5,4,3,2,1(,0=≥i x i
其中可选543,,x x x 为一组初始基变量。 四．计算题（二）（15分）
24．建立下面问题的线性规划模型（不要求求解）
有两个水果生产基地A,B,往三个城市X,Y ,Z 调运水果，设A 基地需要调运的水
果有20吨，B 基地需要调运的水果有11吨，设X,Y,Z 三城需要水果的数量分别是17吨，11吨，3吨，已知每吨运费如下表：
问如何安排调运，使得运费最少？
六．证明题（10分）
25．应用对偶理论证明下面线性规划问题有最优解。 2195m a x x x Z +=
s.t. 0
,0253516
2212121≥≥≤+≤+x x x x x x
参考答案 一．单项选择题。
1．A 2．C 3．C 4．B 5．A 6．B,D 7．C 8．C 9．B 10。 注：6。有两个答案， 7。题中min 应改为max 10题有误，没有正确答案 二．填空题：
11．在可行域上使目标函数达到最优值（最大值或最小值）
12． S.t.
0,0,0,0022m i n 4322
142
132
12
1≥≥≥-='≥=+'-=+'--'--=x x x x x x x x x x x x x f
13．矩阵A 的任意一个m 阶非奇异子方阵
14．因),,,(21m p p p ???为A 的一个基阵，则方程
b p x
m
j j j
=∑=1
有唯一解
0201,,m x x x ???，故0,,0,,002010??????=m x x x X 为原(LP)的一个解，称之为基解，
若进一步还有00≥X ，则称0
X 为(LP)的基可行解 15．或非正0≤ 16．1
-B C B 17．b U CX
00
=
18．kl l k kl c v u -+=λ
其中ij c 为顶点ij x 处对应的运价，且有
l
p l p q p ql pl q p q p q p q p kq q k l l l l c v u c v u c v u c v u c v u =+=+???=+=+=+,,,,,2121111111
注：可令k u =0解之 19．
20．)(),(,020
10R j d x R j x j j j ∈=∈=
21．
一、 已知线性约束条件,探求线性目标关系最值问题 1. 设变量x 、y 满足约束条件?? ???≥+-≥-≤-1122y x y x y x ,则y x z 32+=的最大值为 。 二、 已知线性约束条件,探求非线性目标关系最值问题 2. 已知1,10,220x x y x y ≥??-+≤??--≤? 则22x y +的最小值就是 。 3. 已知变量x,y 满足约束条件+201-70x y x x y -≤??≥??+≤? ,则 y x 的取值范围就是( )、 A 、 [95,6] B 、(－∞,95 ]∪[6,＋∞) C 、(－∞,3]∪[6,＋∞) D 、 [3,6] 三、 研究线性规划中的整点最优解问题 4. 某公司招收男职员x 名,女职员y 名,x 与y 须满足约束条件?? ???≤≥+-≥-.112,932,22115x y x y x 则1010z x y =+的最大值 就是 。 四、 已知最优解成立条件,探求目标函数参数范围问题 5. 已知变量x ,y 满足约束条件1422x y x y ≤+≤??-≤-≤? 。若目标函数z ax y =+(其中0a >)仅在点(3,1)处取得最大值,则a 的取值范围为 。 6. 已知x 、y 满足以下约束条件5503x y x y x +≥??-+≤??≤? ,使z=x+a y (a >0) 取得最小值的最优解有无数个,则a 的值为( ) A. －3 B 、 3 C 、 －1 D 、 1 五、 求可行域的面积 7. 不等式组260302x y x y y +-≥??+-≤??≤? 表示的平面区域的面积为 ( ) A. 4 B 、 1 C 、 5 D 、 无穷大
11（2），12,14,18 习题 2-1 判断下列说法是否正确： （1） 任何线性规划问题存在并具有惟一的对偶问题； T （2） 对偶问题的对偶问题一定是原问题；T （3） 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之， 当对偶问题无可行解时，其原问题具有无界解；F （4） 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优 解； （5） 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出 现原问题与对偶问题均为非可行解的情况； （6） 应用对偶单纯形法计算时，若单纯形表中某一基变量x i <0，又x i 所在行的元素全 部大于或等于零，则可以判断其对偶问题具有无界解。 （7） 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加 5个单位时，相应的目标函数值将增大5k ； （8） 已知y i 为线性规划的对偶问题的最优解，若y i >0，说明在最优生产计划中第 i 种资源已经完全耗尽；若y i =0，说明在最优生产计划中的第i 种资源一定有剩余。 2-2将下述线性规划问题化成标准形式。 ????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43 214321432143214321,0,,232142224.5243max )1(x x x x x x x x x x x x x x x x st x x x x z 2-3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基 可行解对应图解法中可行()?????≥≤≤-+-=++-+-=无约束 321 3213213 21,0,06 24 .322min 2x x x x x x x x x st x x x z 域的哪一顶点。 ()??? ??≥≤+≤++=0,8259 43.510max 12 1212121x x x x x x st x x z ()??? ??≥≤+≤++=0,242615 53.2max 22 121212 1x x x x x x st x x z 2-4已知线性规划问题，写出其对偶问题： 5 43212520202410max x x x x x z ++++=
线性规划常见题型及解法 求线性目标函数的取值范围 2 2 2 x y A D y 2 O x x=2 求可行域的面积 y y M 5 2 x y 2 y x y 2 x y 2 x y x (3,5] y =2 ( 13 例1 x+2y 时 6 的点 C 、 x ， 个 y 6 y 3 2 x + y —3 = 0 C 、 5 A 、 4 B 、 1 D 、无穷大 () 0,将 有 最小值 故选A .B A --- 作出可行域如右图 点个数为13个，选D x + y =2 则z=x+2y 的取值范围是 () 旦y =2 0 0表示的平面区域的面积为 三、求可行域中整点个数 解：|x| + |y| <2等价于 解：如图，作出可行域，作直线I : I 向右上方平移，过点A ( 2,0 ) 2,过点B ( 2,2 )时，有最大值 [2,6] B 、[2 ,5] C 、[3,6] 解：如图，作出可行域，△ ABC 的面积即为所求，由梯形OMBC 的面积减去梯形OMAC 的 面积即可，选B 例 3、满足 |x| + |y| <2 A 、9 个 B 、10 个 由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性 目标函数的最优解是最常见的题型，除此之外，还有以下六类常见题型。 (x 0,y 0) (x 0,y p 0) (xp 0,y 0) (xp 0,y p 0) 是正方形内部(包括边界)，容易得到整 y)中整点(横纵坐标都是整数)有() D 、 14 个 2x 例2、不等式组x x 若x 、y 满足约束条件 y O C V —? x 2x + y —6= 0
线性规划题型及解法 一、已知线性约束条件，探求线性目标关系最值问题 2x -y _2 例1、设变量x、y满足约束条件x 一y _ _1，则z =2x ? 3y的最大值为__________ 。 x y _1 二、已知线性约束条件，探求非线性目标关系最值问题 \ >1, 例2、已知」x-y+1兰0,则x2+y2的最小值是_」“(x-1)2+(y+2『”值域？ 2x - y - 2 <0 三、约束条件设计参数形式，考查目标函数最值范围问题。 Zf x _0 例3、在约束条件y_0 下，当3乞s乞5时，目标函数Z=3x?2y的最大值的变化范围是() |y x _s y 2x^4 A. [6,15] B. [7,15] C. [6,8] D. [7,8] 四、已知平面区域，逆向考查约束条件。 例4、已知双曲线x2-y2 =4的两条渐近线与直线x=3围成一个三角形区域，表示该区域的不等式组是() fx-yZ0 「x-yX0 『x-y^0 "x-y 兰0 (A) x y _ 0 (B) x y 乞0 (C) x y 乞0 (D) x y _ 0 0 _x _3 0 _x _3 0 _x _3 0 _x _3 五、已知最优解成立条件，探求目标函数参数范围问题。 (1 ：：: x ：「v ‘：：4 例5已知变量x，y满足约束条件若目标函数ax y (其中a 0)仅在 [―2 兰x—y 兰2 点(3,1)处取得最大值，则a的取值范围为 __________ 。 六、设计线性规划，探求平面区域的面积问题 丄x y _ 2 _ 0 _ 例6在平面直角坐标系中，不等式组x_y，2_0表示的平面区域的面积是()(A)4、、2 (B)4 [八0 (C) 2.2 (D)2 七、研究线性规划中的整点最优解问题 ”5x-11y —22, 例7、某公司招收男职员x名，女职员y名，x和y须满足约束条件<2x+3yX9, 则 、2x 兰11. z =10x 10y 的最大值是(A)80 (B) 85 (C) 90 (D)95 八、比值问题 当目标函数形如z =-—a时，可把z看作是动点P x, y与定点Q b, a连线的斜率，这样目 x —b 标函数的最值就转化为PQ连线斜率的最值。 x—y+ 2W 0，V
线性规划常见题型及解法 由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型，除此之外，还有以下六类常见题型。 一、求线性目标函数的取值范围 例1、若x、y满足约束条件 2 2 2 x y x y ≤ ? ? ≤ ? ?+≥ ? ，则z=x+2y的取值范围是（） A、[2,6] B、[2,5] C、[3,6] D、（3,5] 解：如图，作出可行域，作直线l：x+2y＝0，将l向右上方平移，过点A（2,0）时，有最小值2，过点B（2,2）时，有最大值6，故选 A 二、求可行域的面积 例2、不等式组 260 30 2 x y x y y +-≥ ? ? +-≤ ? ?≤ ? 表示的平面区域的面积为（） A、4 B、1 C、5 D、无穷大 解：如图，作出可行域，△ABC的面积即为所求，由梯形OMBC 的面积减去梯形OMAC的面积即可，选 B 三、求可行域中整点个数 例3、满足|x|＋|y|≤2的点（x，y）中整点（横纵坐标都是整数）有（） A、9个 B、10个 C、13个 D、14个 解：|x|＋|y|≤2等价于 2(0,0) 2(0,0) 2(0,0) 2(0,0) x y x y x y x y x y x y x y x y +≤≥≥ ? ?-≤≥ ? ? -+≤≥? ?--≤ ? 作出可行域如右图，是正方形内部（包括边界），容易得到整点个数为13个，选 D
四、求线性目标函数中参数的取值范围 例4、已知x、y满足以下约束条件 5 50 3 x y x y x +≥ ? ? -+≤ ? ?≤ ? ，使z=x+ay(a>0) 取得最小值的最优解有无数个，则a的值为（） A、－3 B、3 C、－1 D、1 解：如图，作出可行域，作直线l：x+ay＝0，要使目标函数z=x+ay(a>0)取得最小值的最优解有无数个，则将l向右上方平移后与直线x+y＝5重合，故a=1，选 D 五、求非线性目标函数的最值 例5、已知x、y满足以下约束条件 220 240 330 x y x y x y +-≥ ? ? -+≥ ? ?--≤ ? ，则z=x2+y2的最大值和最小值分别是（） A、13，1 B、13，2 C、13，4 5 D 、 解：如图，作出可行域,x2+y2是点（x，y）到原点的距离的平方，故最大值为点A（2,3）到原点的距离的平方，即|AO|2=13，最小值为原点到直线2x＋y－2=0的距离的平方， 即为4 5 ，选 C 六、求约束条件中参数的取值范围 例6、已知|2x－y＋m|＜3表示的平面区域包含点（0,0）和（－1,1），则m的取值范围是（） A、（-3,6） B、（0,6） C、（0,3） D、（-3,3） 解：|2x－y＋m|＜3等价于 230 230 x y m x y m -++>? ? -+- ? ? -< ? ,故0＜m＜3，选 C
习题 2-1 判断下列说法是否正确: （1）任何线性规划问题存在并具有惟一的对偶问题; （2）对偶问题的对偶问题一定是原问题; （3）根据对偶问题的性质, 当原问题为无界解时, 其对偶问题无可行解, 反之, 当对偶问题无可行解时, 其原问题具有无界解; （4）若线性规划的原问题有无穷多最优解, 则其对偶问题也一定具有无穷多最优解; （5）若线性规划问题中的b i, c j值同时发生变化, 反映到最终单纯形表中, 不会出现原问题与对偶问题均为非可行解的情况; （6）应用对偶单纯形法计算时, 若单纯形表中某一基变量x i<0, 又x i所在行的元素全部大于或等于零, 则能够判断其对偶问题具有无界解。 （7）若某种资源的影子价格等于k, 在其它条件不变的情况下, 当该种资源增加5个单位时, 相应的目标函数值将增大5k;
（8） 已知y i 为线性规划的对偶问题的最优解, 若y i >0, 说明在最优生产计划中第i 种资源已经完全耗尽; 若y i =0, 说明在最优生产计划中的第i 种资源一定有剩余。 2-2将下述线性规划问题化成标准形式。 ????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43 214321432143214321,0,,232142224.5243max )1(x x x x x x x x x x x x x x x x st x x x x z ()??? ??≥≤≤-+-=++-+-=无约束 321 3213213 21,0,06 24 .322min 2x x x x x x x x x st x x x z 解: (1)令'''444x x x =-, 增加松弛变量5x , 剩余变量6x , 则该问题的标准形式如下所示: ''' 12344''' 12344''' 123445''' 123446'''1234456max 342554222214..232 ,,,,,,0 z x x x x x x x x x x x x x x x x s t x x x x x x x x x x x x x =-+-+-?-+-+-=?+-+-+=??-++-+-=??≥? (2)令'z z =-, '11x x =-, '''333x x x =-, 增加松弛变量4x , 则该问题的标准形式如下所示: ''''' 1233'''' 1233'''' 12334''''12334 max 22334 ..26,,,,0z x x x x x x x x s t x x x x x x x x x x =+-+?++-=?+-++=??≥? 2-3分别用图解法和单纯形法求解下述线性规划问题, 并对照
高考线性规划归类解析 一、平面区域和约束条件对应关系。 例1、已知双曲线224x y -=的两条渐近线与直线3x =围成一个三角形区域,表示该区域的不等式组是（） (A)0003x y x y x -≥??+≥??≤≤? (B)0003x y x y x -≥?? +≤??≤≤? (C) 003x y x y x -≤?? +≤??≤≤? (D) 0003x y x y x -≤?? +≥??≤≤? 解析：双曲线224x y -=的两条渐近线方程为y x =±，与直线3x =围 成一个三角形区域（如图4所示）时有0 003x y x y x -≥?? +≥??≤≤? 。 点评：本题考查双曲线的渐近线方程以及线性规划问题。验证法或排除法是最效的方法。 例2：在平面直角坐标系中，不等式组20 200x y x y y +-≤??-+≥??≥? 表示的平面区域的面积是（） (A)42 (B)4 (C) 22 (D)2 解析：如图６，作出可行域，易知不等式组20 200x y x y y +-≤??-+≥??≥? 表示的平面区域是一个三角形。容 易求三角形的三个顶点坐标为Ａ（０，２），B(2,0),C(-2,0).于是三角形的面积为： 11 ||||42 4.22 S BC AO =?=??=从而选Ｂ。 点评：有关平面区域的面积问题，首先作出可行域，探求平面区域图形的性质；其次利用面积公式整体或部分求解是关键。 二、已知线性约束条件，探求线性截距——加减的形式(非线性距离——平方的形式，斜率——商的形式)目标关系最值问题（重点） 例3、设变量x 、y 满足约束条件?? ? ??≥+-≥-≤-1122y x y x y x ，则 ①y x 32+的最大值为 。（截距） 解析：如图1，画出可行域，得在直线 2x-y=2与直线x-y=-1 的交点A(3,4)处，目标函数z 最大值为18 点评：本题主要考查线性规划问题,由线性约束条件画出可行域,然后求出目标函数的最大值.，是一道较为简单的送分题。数形结合是数学思想的重要手段之一。 ②则2 2 x y +的最小值是 . ③1y x =+的取值范围是 . 图1
1 / 6 一、 已知线性约束条件，探求线性目标关系最值问题 1. 设变量x 、y 满足约束条件?? ? ??≥+-≥-≤-1122y x y x y x ,则y x z 32+=的最大值为 。 二、 已知线性约束条件,探求非线性目标关系最值问题 2. 已知1,10,220x x y x y ≥??-+≤??--≤? 则22 x y +的最小值是 。 3. 已知变量x ，y 满足约束条件+201-70x y x x y -≤?? ≥??+≤? ,则 错误! 的取值范围是（ )。 A 。 ［错误!，6] B.（－∞，错误!］∪［6，＋∞） C.（－∞，3］∪［6，＋∞） D 。 ［3，6］ 三、 研究线性规划中的整点最优解问题 4. 某公司招收男职员x 名，女职员y 名，x 和y 须满足约束条件?? ? ??≤≥+-≥-.112,932,22115x y x y x 则1010z x y =+的最大 值是 。 四、 已知最优解成立条件，探求目标函数参数范围问题 5. 已知变量x ，y 满足约束条件14 22x y x y ≤+≤?? -≤-≤? 。若目标函数z ax y =+(其中0a >）仅在点(3,1)处 取得最大值，则a 的取值范围为 。 6. 已知x 、y 满足以下约束条件5503x y x y x +≥?? -+≤??≤? ,使z=x+a y (a >0) 取得最小值的最优解有无数个，则a 的 值为（ ） A. －3 B. 3 C 。 －1 D. 1 五、 求可行域的面积 7. 不等式组260302x y x y y +-≥?? +-≤??≤? 表示的平面区域的面积为 （ ） A. 4 B. 1 C. 5 D 。 无穷大
《运筹学》线性规划部分练习题 一、思考题 1.什么是线性规划模型，在模型中各系数的经济意义是什么？ 2 .线性规划问题的一般形式有何特征？ 3. 建立一个实际问题的数学模型一般要几步？ 4. 两个变量的线性规划问题的图解法的一般步骤是什么？ 5. 求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6. 什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 7?试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8?试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9. 在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 10. 大M法中，M的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问 题呢？ 11 ?什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续 第二阶段？ 二、判断下列说法是否正确。 1 .线性规划问题的最优解一定在可行域的顶点达到。 2 .线性规划的可行解集是凸集。 3. 如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 4. 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的 范围一般将扩大。 5 .线性规划问题的每一个基本解对应可行域的一个顶点。 6. 如果一个线性规划问题有可行解，那么它必有最优解。 7. 用单纯形法求解标准形式（求最小值）的线性规划问题时，与j 0对应的变量都可以被 选作换入变量。 8 .单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一 个基变量的值是负的。 9. 单纯形法计算中，选取最大正检验数k对应的变量x k作为换入变量，可使目 标函数值得到最快的减少。 10 . 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形 表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1 .某公司计划在三年的计划期内，有四个建设项目可以投资：项目I从第一年到 第三年年初都可以投资。预计每年年初投资，年末可收回本利120%，每年又可以重新将所获本利纳入投资计划；项目n需要在第一年初投资，经过两年可收回本利150% , 又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目川需要在第二年年初投资，经过两年可收回本利160%，但用于该项目的最大投资额 不得超过15万元；项目"需要在第三年年初投资，年末可收回本利140%，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有 30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 2 .某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示：
《运筹学》线性规划部分练习题 一、思考题 1． 什么是线性规划模型，在模型中各系数的经济意义是什么？ 2． 线性规划问题的一般形式有何特征？ 3． 建立一个实际问题的数学模型一般要几步？ 4． 两个变量的线性规划问题的图解法的一般步骤是什么？ 5． 求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6． 什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 7． 试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8． 试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9． 在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 10．大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？ 11．什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 二、判断下列说法是否正确。 1． 线性规划问题的最优解一定在可行域的顶点达到。 2． 线性规划的可行解集是凸集。 3． 如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 4． 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 5． 线性规划问题的每一个基本解对应可行域的一个顶点。 6． 如果一个线性规划问题有可行解，那么它必有最优解。 7． 用单纯形法求解标准形式（求最小值）的线性规划问题时，与0 >j σ对应的变量都可以被选作换入变量。 8． 单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。 9． 单纯形法计算中，选取最大正检验数k σ对应的变量k x 作为换入变量，可使目 标函数值得到最快的减少。 10． 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1． 某公司计划在三年的计划期内，有四个建设项目可以投资：项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资，年末可收回本利120% ，每年又可以重新将所获本利纳入投资计划；项目Ⅱ需要在第一年初投资，经过两年可收回本利150% ，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目Ⅲ需要在第二年年初投资，经过两年可收回本利160% ，但用于该项目的最大投资额不得超过15万元；项目Ⅳ需要在第三年年初投资，年末可收回本利140% ，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 2．某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示：
线性规划 基础知识： 一、知识梳理 1. 目标函数: Ｐ ＝２ｘ＋ｙ是一个含有两个变 量 ｘ 和ｙ 的 函数，称为目标函数． 2.可行域:约束条件所表示的平面区域称为可行域. 3. 整点:坐标为整数的点叫做整点． 4.线性规划问题:求线性目标函数在线性约束条件下的最大值或最小值的问题，通常称为线性规划问题．只含有两个变量的简单线性规划问题可用图解法来解决． 5. 整数线性规划:要求量取整数的线性规划称为整数线性规划． 二：积储知识： 一． 1.点P(x 0,y 0)在直线Ax+By+C=0上，则点P 坐标适合方程，即Ax 0+By 0+C=0 2. 点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 3. 点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)>0 2.点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）当特殊点，若点坐标代入适合不等式则此点所在的区域为需画的区域，否则是另一侧区域为需画区域。 例题： 1. 如图1所示，已知ABC ?中的三顶点(2,4),(1,2),(1,0)A B C -，点(,)P x y 在ABC ?内部及边界运动，请你探究并讨论以下问题：若目标函数是1y z x -=或z =你知道其几何意义吗？你能否借助其几何意义求得min z 和max z ？
1. 一水源地的年供水能力为6000万m 3，供水范围包括工业、农业、生活三个部分，各部门的需水量、水价、供水要求见表1，如何在满足供水要求的情况下分配水量，使得供水收入达到最大？列出该问题的数学模型。 表1 各用户需水量、水价及供水要求 2. 用图解法求解以下线性规划问题，并指出问题具有唯一最优解、无穷多最优解、无界解，还是无可行解？ (1) (2) ≥,4≤1≥+10 ≤2+..3+=max 212212121x x x x x x x t s x x Z ,2+3 3+..5.1+=min 2121212 1≥≥≥x x x x x x t s x x Z 3. 将以下线性规划问题转化为标准型，找出所有基解，确定其中的 基可行解并计算其目标函数值，找出最优解及最优目标函数值。 ,12≤+315 5+3..+2=max 21212121≥≤x x x x x x t s x x Z 4. 用对偶单纯形法解下题。
≥,3≤2+x 63+4x 3≥+3x +2=max 212121212 1x x x x x x x Z ≥约束条件： 5.某企业计划生产A,B 两种产品。生产1kg 产品A 需经甲设备加工1小时，乙设备加工5小时，获利5元；生产1kg 产品B 需经甲设备加工2小时，乙设备加工2小时，获利6元。现该企业甲设备加工能力不超过12小时，乙设备加工能力不超过30小时。试问如何安排生产计划，使企业获利最大，并计算两种设备的影子价格。 6. 某地区在今后三年内有四种投资机会。第一种是在三年内每年年初投资，每年年底可将该年投资收回，并获利20%；第二种是在第一年年初投资，第二年年底可获利50%，并将本金收回，但是该项投资最多不得超过2万元；第三种投资是在第二年年初投资，第三年年底收回本金，并获利60%，该项投资不得超过1.5万元；第四种是在第三年年初投资，于该年年底收回本金，且获利40%，该项投资不得超过1万元。现在该地区准备拿出三万元资金，问如何制定投资计划，使到第三年年末本利和最大。
线性规划简单练习题文件编码（008-TTIG-UTITD-GKBTT-PUUTI-WYTUI-8256）
线性规划练习 1. 已知变量,x y满足约束条件 2 4 1 y x y x y ≤ ? ? +≥ ? ?-≤ ? ，则3 z x y =+的最大值为。 2. 设变量,x y满足 -10 0+20 015 x y x y y ≤ ? ? ≤≤ ? ?≤≤ ? ，则2+3 x y的最大值为。 3. 若,x y满足约束条件 10 30 330 x y x y x y -+≥ ? ?? +-≤ ? ? +-≥ ?? ，则3 z x y =-的最小值 为。 4. 设函数 ln,0 () 21,0 x x f x x x > ? =? --≤ ? ，D是由x轴和曲线() y f x =及该曲线在点(1,0)处的 切线所围成的封闭区域，则2 z x y =-在D上的最大值为． 5. 某农户计划种植黄瓜和韭菜，种植面积不超过50计，投入资金不超过54万 元，假设种植黄瓜和韭菜的产量、成本和售价如下表 为使一年的种植总利润（总利润=总销售收入总种植成本）最大，那么黄瓜和韭菜的种植面积（单位：亩）分别为。 6. 某公司生产甲、乙两种桶装产品. 已知生产甲产品1桶需耗A原料1千克、B 原料2千克；生产乙产品1桶需耗A原料2千克，B原料1千克. 每桶甲产品的利润是300元，每桶乙产品的利润是400元. 公司在生产这两种产品的计划中，要求每天消耗A、B原料都不超过12千克. 通过合理安排生产计划，从每
天生产的甲、乙两种产品中，公司共可获得的最大利润是。 7. 若,x y满足约束条件： 23 23 x x y x y ≥ ? ? +≥ ? ?+≤ ? ；则x y -的取值范围为_____. 8．若,x y满足约束条件 24 41 x y x y +≤ ? ? -≥- ? ，则目标函数z=3x－y的取值范围 是。 9．设,x y满足约束条件： ,0 1 3 x y x y x y ≥ ? ? -≥- ? ?+≤ ? ；则2 z x y =-的取值范围为 .
1 线性规划常见题型及解法 由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型，除此之外，还有以下六类常见题型。 一、求线性目标函数的取值范围 例1、 若x 、y 满足约束条件222x y x y ≤?? ≤??+≥? ，则z=x+2y 的取值范围是 （ ） A 、[2,6] B 、[2,5] C 、[3,6] D 、（3,5] 解：如图，作出可行域，作直线l ：x+2y ＝0，将 l 向右上方平移，过点A （2,0）时，有最小值 2，过点B （2,2）时，有最大值6，故选 A 二、求可行域的面积 例2、不等式组260302x y x y y +-≥?? +-≤??≤? 表示的平面区域的面积为 （ ） A 、4 B 、1 C 、5 D 、无穷大 解：如图，作出可行域，△ABC 的面积即为所求，由梯形OMBC 的面积减去梯形OMAC 的面积即可，选 B 三、求可行域中整点个数 例3、满足|x|＋|y|≤2的点（x ，y ）中整点（横纵坐标都是整数）有（ ） A 、9个 B 、10个 C 、13个 D 、14个 解：|x|＋|y|≤2等价于2(0,0)2(0,0)2(0,0) 2 (0,0)x y x y x y x y x y x y x y x y +≤≥≥??-≤≥? ? -+≤≥??--≤? 作出可行域如右图，是正方形内部（包括边界），容易得到整 点个数为13个，选 D
2 四、求线性目标函数中参数的取值范围 例4、已知x 、y 满足以下约束条件5503x y x y x +≥?? -+≤??≤? ，使z=x+ay(a>0) 取得最小值的最优解有无数个，则a 的值为 （ ） A 、－3 B 、3 C 、－1 D 、1 解：如图，作出可行域，作直线l ：x+ay ＝0，要使目标函数z=x+ay (a>0)取得最小值的最优解 有无数个，则将l 向右上方平移后与直线x+y ＝5重合，故a=1，选 D 五、求非线性目标函数的最值 例5、已知x 、y 满足以下约束条件220240330x y x y x y +-≥??-+≥??--≤? ，则z=x 2+y 2 的最大值和最小值分别是（ ） A 、13，1 B 、13，2 C 、13，4 5 D 、 解：如图，作出可行域,x 2 +y 2 是点（x ，y ）到原点的距离的平方，故最大值为点A （2,3）到原点的距离的平方， 即|AO|2 =13，最小值为原点到直线2x ＋y －2=0的距离的平方，即为 4 5 ，选 C 六·比值问题 当目标函数形如y a z x b -= -时,可把z 看作是动点(,)P x y 与定点(,)Q b a 连线的斜率，这样目标函数的最值就转化为PQ 连线斜率的最值。 例 已知变量x ，y 满足约束条件?????x －y ＋2≤0，x ≥1，x ＋y －7≤0， 则 y x 的取值范围是（ ）. （A ）[95，6] （B ）（－∞，9 5]∪[6，＋∞） （C ）（－∞，3]∪[6，＋∞） （D ）[3，6] 解析 y x 是可行域内的点M （x ，y ）与原点O
简单的线性规划典型例题 例1画出不等式组 ? ? ? ? ? ≤ + - ≤ - + ≤ - + - .0 3 3 4 2 y x y x y x ， ， 表示的平面区域．分析：采用“图解法”确定不等式组每一不等式所表示的平面区域，然后求其公共部分． 解：把0 = x，0 = y代入2 - + -y x中得0 2 0< - + - ∴不等式0 2≤ - + -y x表示直线0 2= - + -y x下方的区域（包括边界）， 即位于原点的一侧，同理可画出其他两部分，不等式组所表示的区域如图所示． 说明：“图解法”是判别二元一次不等式所表示的区域行之有效的一种方法． 例2 画出3 3 2≤ < -y x表示的区域，并求所有的正整数解),(y x． 分析：原不等式等价于 ? ? ? ≤ - > .3 ,3 2 y x y 而求正整数解则意味着x，y
有限制条件，即求 ? ? ? ? ? ? ? ≤ - > ∈ ∈ > > .3 ,3 2 , , ,0 ,0 y x y z y z x y x ． 解：依照二元一次不等式表示的平面区域，知3 3 2≤ < -y x表示的 区域如下图： 对于3 3 2≤ < -y x的正整数解，先画出不等式组． ? ? ? ? ? ? ? ≤ - > ∈ ∈ > > .3 ,3 2 , , ,0 ,0 y x y z y z x y x 所表示的平面区域，如图所示． 容易求得，在其区域内的整数解为)1,1(、)2,1(、)3,1(、)2,2(、)3,2(．说明：这类题可以将平面直角坐标系用网络线画出来，然后在不等式组所表示的平面区域内找出符合题设要求的整数点来． 例3求不等式组 ?? ? ? ? + - ≤ - + ≥ 1 1 1 x y x y 所表示的平面区域的面积．分析：本题的关键是能够将不等式组所表示的平面区域作出来，判断其形状进而求出其面积．而要将平面区域作出来的关键又是能够
第一章线性规划 13.对（LP ）min f = -2x 1 - 3x 2 s.t. x 1 + x 2 + x 3 = 2， 4x 1 + 6x 2 + x 4 = 9， x j ≥0, j=1,2，3，4。 已经得到最优表如下： 判断它是否有多个基本最优解。若有，试求出。 解：现在r 1=0，最小比值有效。进行转基： 得到两个基本最优解：
X1=（0，3/2，1/2，0）T，X2=（0，3/2，1/2，0）T
15、应用单纯形法证明下列问题无最优解 12max 2Z x x =+ s.t. 12322x x x -++≤ 1231x x x -+-≤ 0,1,2,3j x j ≥= 试找出一个可行解，它的目标函数值大于2000 解： 令f Z =- 12min 2f x x =-- st. 123422x x x x -+++= 12351x x x x -+-+= 0,1,2,3,4,5j x j ≥= B x 1x 2x 3x 4 x b r -2-1-1 11-2 -10 100 20 114x 5 x 5 x 0 01 在表中，110r =-<，又 1120y =-<，2110y =-<
最小比值准则失效，（LP ）的目标函数值在可行域内无下界 f →-∞ ，无最优解。 取1 0x ε'=> 230,0x x ''== 则 4 522,1x x εε''=+=+ ()f x ε'=- 为使()2000f x '<- 取2001ε= 得(2001,0,0,4004,2002)T x '= 则 ()2001f x '=- 即 ()20012000 Z x =>
线性规划专题 一、命题规律讲解 1、 求线性（非线性）目标函数最值题 2、 求可行域的面积题 3、 求目标函数中参数取值范围题 4、 求约束条件中参数取值范围题 5、 利用线性规划解答应用题 一、线性约束条件下线性函数的最值问题 线性约束条件下线性函数的最值问题即简单线性规划问题，它的线性约束条件是一个二元一次不等式组，目标函数是一个二元一次函数，可行域就是线性约束条件中不等式所对应的方程所表示的直线所围成的区域，区域内的各点的点坐标(),x y 即简单线性规划的可行解，在可行解中的使得目标函数取得最大值和最小值的点的坐标(),x y 即简单线性规划的最优解。 例1 已知43 35251x y x y x -≤-?? +≤??≥? ，2z x y =+，求z 的最大值和最小值 例2已知,x y 满足124126x y x y x y +=?? +≥??-≥-? ，求z=5x y -的最大值和最小值 二、非线性约束条件下线性函数的最值问题 高中数学中的最值问题很多可以转化为非线性约束条件下线性函数的最值问题。它们的约束条件是一个二元不等式组，目标函数是一个二元一次函数，可行域是直线或曲线所围成的图形（或一条曲线段），区域内的各点的点坐标(),x y 即可行解，在可行解中的使得目标函数取得最大值和最小值的点的坐标 (),x y 即最优解。 例3 已知,x y 满足，2 2 4x y +=，求32x y +的最大值和最小值 例4 求函数4 y x x =+[]()1,5x ∈的最大值和最小值。
三、线性约束条件下非线性函数的最值问题 这类问题也是高中数学中常见的问题，它也可以用线性规划的思想来进行解决。它的约束条件是一个二元一次不等式组，目标函数是一个二元函数，可行域是直线所围成的图形（或一条线段），区域内的各点的点坐标(),x y 即可行解，在可行解中的使得目标函数取得最大值和最小值的点的坐标(),x y 即最优解。 例5 已知实数,x y 满足不等式组10101x y x y y +-≤??-+≥??≥-? ，求22 448x y x y +--+的最小值。 例6 实数,x y 满足不等式组0 0220 y x y x y ≥?? -≥??--≥? ，求11y x -+的最小值 四、非线性约束条件下非线性函数的最值问题 在高中数学中还有一些常见的问题也可以用线性规划的思想来解决，它的约束条件是一个二元不等式组，目标函数也是一个二元函数，可行域是由曲线或直线所围成的图形（或一条曲线段），区域内的各点的点坐标(),x y 即可行解，在可行解中的使得目标函数取得最大值和最小值的点的坐标(),x y 即最优解。 例7 已知,x y 满足y 2 y x +的最大值和最小值
线性规划问题 1线性规划下的非线性问题 1.1线性规划下的距离问题 已知220 240330x y x y x y +-≥?? -+≥??--≤? ，当x ，y 取何值时（1 取得最大值？（2）()222x y ++取 得最小值？ 1.2线性规划下的斜率问题 已知220 240330 x y x y x y +-≥??-+≥??--≤? ，（1）当x ，y 取何值时，11y x ++取得最大值？（2）求3 22x y --取值范围。 1.3线性规划下的向量问题 （1）点P （x ，y ）满足不等式组10 5702x y x y y -+≥?? --≤??≥-? ，i 为x 轴正方向上的单位向量，则向量OP 在向量i 方向上的投影的最大值是____________ （2） 已知(A ，O 是原点，点P （x ，y ） 的坐标满足0200 y x y -
2.非线性规划下的线性问题 （1）实数x ，y 满足2222101212x y x y x y ?+--+≥? ≤≤??≤≤? ，则x+y 取得最小值时，点（x ，y ）的个数 是 ． （2）定义[]x 表示不超过x 的最大整数，又设x ，y 满足方程[][]313 435y x y x ?=+??=-+?? ，如果x 不 是整数，则x+y 的取值范围是 ． 3.非线性规划下的非线性问题 (1)已知钝角三角形ABC 的最大边长为2，其余两边长为x ，y ，则以（x ，y ）为坐标的点表示平面区域的面积是 ． (2)已知实数x ，y 满足不等式组226290 2312x y x y x y ?+--+≤? ≤≤??≤≤? ， 则 x 取值范围 是 ． 4线性规划的逆问题 4.1线性约束条件中的参数问题 （1）已知x ，y 满足140x x y ax by c ≥?? +≤??++≤? ，且目标函数2z x y =+的最大值是7，最小值是1， 则 _______ a b c a ++= (2)设m 为实数，若{}22 250(,)30(,)250x y x y x x y x y m x y ??-+≥????-≥?+≤?????? +≥??? ，则m 的取值范围 是 ． 4.2目标函数中的参数问题 （1）已知变量x ，y 满足的约束条件为23033010x y x y y +-≤?? +-≥??-≤? ，若目标函数z=ax+y （其中a>0） 仅在点（3，0）处取得最大值，则a 的取值范围是 ． （2）已知x ，y 满足4335251x y x y x -≤-?? +≤??≥? ，设z=ax+y （其中a>0），若当z 取得最大值时对应的 点有无数多个，求a 的值。 （3）在平面直角坐标系xOy ，已知平面区域{(,)|1,A x y x y =+≤且0,0}x y ≥≥，则平