习题答案选01_线性规划和单纯形法
运筹学教程（胡运权主编，清华版）部分习题答案（第一章）1.5
记可行集4个顶点分别为O:(0,0)，A:(1.6,0)，B:(1,1.5)，C:(0,2.25)
当c=0，d=0时，四边形OABC中的点都是最优解
当c=0，d>0时，顶点C是最优解
当c=0，d<0时，线段OA上的点都是最优解
当c>0，d/c<2/5时，顶点A是最优解
当c>0，d/c=2/5时，线段AB上的点都是最优解
当c>0，2/5 当c>0，d/c=4/3时，线段BC上的点都是最优解 当c>0，d/c>4/3时，顶点C是最优解 当c<0，d<0时，顶点O是最优解 当c<0，d=0时，线段OC上的点都是最优解 当c<0，d>0时，顶点C是最优解 1.8 a=3，b=2，c=4，d=-2，e=2，f=3，g=1，h=0，i=5，j=5，k=-3/2，l=0 1.15 设i=1,2,3分别表示前、中、后三舱，j=1,2,3分别表示A、B、C三种商品 设第i舱装载第j中商品的件数为x ij max z = 100(x11+x21+x31) + 700(x12+x22+x32) + 600(x13+x23+x33) s.t. 8x11+6x12+5x13 ≤ 2000 8x21+6x22+5x23 ≤ 3000 8x31+6x32+5x33 ≤ 1500 10x11+5x12+7x13 ≤ 4000 10x21+5x22+7x23 ≤ 5400 10x31+5x32+7x33 ≤ 1500 x11+x21+x31≤ 600 x12+x22+x32 ≤ 1000 x13+x23+x33 ≤ 800 8x11+6x12+5x13 ≤ 1.15 (8x21+6x22+5x23) 8x21+6x22+5x23 ≤ 1.15 (8x11+6x12+5x13) 8x31+6x32+5x33 ≤ 1.15 (8x21+6x22+5x23) 8x21+6x22+5x23 ≤ 1.15 (8x31+6x32+5x33) 8x11+6x12+5x13 ≤ 1.1 (8x31+6x32+5x33) 8x31+6x32+5x33 ≤ 1.1 (8x11+6x12+5x13) x ij ≥ 0, i=1,2,3, j=1,2,3 1.16 设x i和y i分别为第i周正常工作时间内用于生产食品Ⅰ和Ⅱ的工人数； 设s i和t i分别为第i周加班时间内为食品Ⅰ和Ⅱ加工的工时； 设w i为从第i周开始抽出来培训新工人的熟练工人数； 设n i为从第i周开始接受培训的新工人数； 设u i和v i分别为第i周于生产食品Ⅰ和Ⅱ的新工人数； 设f i和g i分别为第i周末未能按期交货的食品Ⅰ和Ⅱ的数量； 设k i和l i分别为第i周末剩余的食品Ⅰ和Ⅱ的数量； 设q i和r i分别为第i周内对食品Ⅰ和Ⅱ的需求量（如表，已知）。 min z = 360[(x1 + y1 + w1) + (x2 + y2 + w1 + w2) + ... + (x7 + y7 + w6 + w7) + (x8 + y8 + w7)] + 120[(n1) + (n1 + n2) + ... + (n6 + n7)] + 240[(u3 + v3) + (u4 + v4) + ... + (u8 + v8)] + 12[(s1 + t1) + (s2 + t2) + ... + (s8 + t8)] + 0.5(f1 + f2 + ... + f8) + 0.8(g1 + g2 + ... + g8) s.t. x1 + y1 + w1 = 50 x2 + y2 + w1 + w2 = 50 …… x7 + y7 + w6 + w7 = 50 x8 + y8 + w7 = 50 n i ≤ 3 w i，i=1,2,…,7 u i + v i = n3 +... +n i-2，i=3,4,…,8 n1 + n2 + ... + n7 = 50 400x i + 10s i + f i = q i + k i，i=1,2 400x i + 400u i + 10s i + f i = q i + k i，i=3,4,…,8 240y i + 6t i + g i = r i + l i，i=1,2 240y i + 240v i + 6t i + g i = r i + l i，i=3,4,…,8 x i，y i，s i，t i，f i，g i，k i，l i ≥ 0，i=1,2,…,8 w i，n i ≥ 0，i=1,2,…,7 u i，v i ≥ 0，i=3,4,…,8 1.17 设： x i ：第i 个月公司雇佣的人数 ( i =1,2,…,6)； z i ：第i 个月末的库存量 ( i =1,2,…,6)； s i ：第i 个月的短缺量 ( i =1,2,…,6)； t i ：第i 个月因新增和解雇工人所产生的费用 ( i =1,2,…,6)； q i ：第i 个月的需求量（如表，已知）； Max Z = ∑=-61i i i )s q (30–2000∑=61i i x –5∑=61i i z –∑=61i t i s.t ????????????=≥==?=≥?=≥?=+=++,6); 1,2, i ( 0,t ,s ,z ,x 0z 4x ,6)1,2, i (),x -1000(x t ,6)1,2, i (),x -1500(x t ,6)1,2, i (,q z s 100x z i i i i 0 i -1i 1-i i i i i i i 1-i i （该条件原题中没给） 1.18 假设：每月的现金流发生在月底。 x ：上一年末的借款数； y i ：第i 个月底贷款, ( i =1,2,…,11)； z i ：第i 个月底存款, ( i =1,2,…,12)； c i ：第i 个月的现金需求量（如表，已知）； max Z = z 12 s.t. z 1 – x – y 1 + 0.01x = c 1 z i – 1.004z i-1 – y i + 0.01x + 1.015y i-1 = c i , ( i =2,3,…,11) z 12 – 1.004z 11 + 0.01x + x + 1.015y i-1 = c 12 x ≥ 0 y i ≥ 0，i=1,2,…,11 z i ≥ 0，i=1,2,…,12 单纯形法演算 j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 无穷 0 4x 24 6 2 0 1 0 4 0 5x 5 1 1 0 0 1 5 j j z c -（检验数） 2 1 首先列出表格，先确定正检验数最大值所在列为主列，然后用b 除以主列上对应的同行数字。除出来所得值最小的那一行为主行，根据主行和主列可以确定主元（交点）。接着把主元化为1并把X4换成X1. ??? ??? ?≥=++=++=+++++=0,,524261550002max 5152 14213 25 4321x x x x x x x x x x x x x x x z ??????? ≥≤+≤+≤+=0 ,5 24261552max 21212122 1x x x x x x x x x z j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 2 1x 4 1 2/6 0 1/6 0 0 5x 5 1 1 0 0 1 j j z c - 2 1 这时进行初等行列变换，把主列换单位向量，主元为1。也就是X5所在行减去X1所在行。并且重新计算检验数。 j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 2 1x 4 1 2/6 0 1/6 0 0 5x 5-4 1-1=0 1-2/6 =4/6 0-1/6=-1/6 1 j j z c - 2-2*1-0*0-0*1=0 1-0*5-2*2/6-0*4/6=1/3 0-0*0-2*1/6-0*-1/6=-1/3 再次确定主元。为4/6。然后把X5换成X2。并且把主元化成1。 一、 已知线性约束条件,探求线性目标关系最值问题 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 、 无穷大 例1：生产计划问题 某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如下表。若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费O.2万元。现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低。试建立模型。 解： 法1 设每个季度分别生产x1,x2,x3,x4 则要满足每个季度的需求x4≥26 x1+ x2≥40 x1+ x2+ x3≥70 x1+ x2+ x3+ x4=80 考虑到每个季度的生产能力 0≤x1≤30 0≤x2≤40 0≤x3≤20 0≤x4≤10 每个季度的费用为：此季度生产费用+上季度储存费用 第一季度15.0x1 第二季度14 x2 0.2(x1-20) 第三季度15.3x3+0.2(x1+ x2-40) 第四季度14.8x4+0.2(x1+ x2+ x3-70) 工厂一年的费用即为这四个季度费用之和, 得目标函数；minf=15.6 x1+14.4 x2+15.5 x3+14.8 x4-26 s.t．x1+ x2≥40 x1+ x2+ x3≥70 x1+ x2+ x3+ x4=80 20≤x1≤30 0≤x2≤40 0≤x3≤20 0≤x4≤10。 法2：设第i季度生产而用于第j季度末交货的产品数量为xij吨 根据合同要求有： xll=20 x12+x22=20 x13+x23+x33=30 x14+x24+x34+x44=10 又根据每季度的生产能力有： xll+x12+x13+x14≤30 x22+x23+x24≤40 x33+x34≤20 x44≤10 第i季度生产的用于第j季度交货的每吨产品的费用cij=dj+0.2(j-i)，于是，有线性规划模型。 minf=15.Oxll+15.2x12+15.4xl3+15.6xl4+14x22+14.2x23+14.4x24+15.3 x33+15.5x34+14.8x44 s．t． xll=20， x12+x22=20， x13+x23+x13=30， x14+x24+x34+x44=10， x1l+x12+x13+x14≤30， x22+x23+x24≤40， x33+x34≤20， 线性规划题型及解法 一、已知线性约束条件，探求线性目标关系最值问题 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 线性规划常见题型及解法 求线性目标函数的取值范围 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 习题 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、若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 2017 高考全国卷及自主招生数学高考真题 线性规划专题真题整理（附答案解析） x 3y 3, 1. （ 17 全国卷 I ，文数 ）设 x ，y 满足约束条件 x y 1, 则 z=x+y 的最大值为（ ） 7 y 0, A ． 0 B ． 1 C ．2 D ．3 答案： D 解析：如图，由图易知当目标函数 z x y 经过 直线 x 3 y 3 和 y 0 （即 x 轴）的交点 A(3,0) 时， z 能取到最大值，把 A(3,0) 代入 z=x+y 可得 z max 3 0 3 ，故选 D. x 2 y 1 2.（17 全国卷 I, 理数 14 题）设 x ，y 满足约束条件 2x y 1，则 z 3x 2 y 的最小值 x y 0 为 答案： 5 x 2 y 1 解析：不等式组 2x y 1 表示的平面区域如图所示。 x y 0 由 z 3x 2 y 变形得 y 3 x z 。要求 z 的最小值， 2 2 即求直线 y 3 x z 的纵截距的最大值。由右图，易知 2 2 当直线 y 3 x z 过图中点 A 时，纵截距最大。 2 2 联立方程组 2 x y 1 ，此时 z 3(1) 2 1 5 。 x 2 y 1 ，解得 A 点坐标为 ( 1,1) 故 z 3x 2 y 的最小值是 -5. 2x+3y 30 3. （17 全国卷Ⅱ，文数 7、理数 5）设 x、y 满足约束条件2x 3 y 3 0 .则z2x y的 y 30 最小值是（） A.-15 C.1D9 答案： A 2x+3y 30 解析：不等式组2x 3y 30 表示的可行域如图所示， y30 易知当直线z 2x y 过到y 2 x 1与 y 3 交点 3 6 ，3 时，目标函数 z2x y 取到最小值，此时有 z min 26315 ，故所求z 最小值为15． ）设，满足约束条件 3x 2 y60 的取值范围是 4. （17 全国卷Ⅲ，文数 5 x0，则 z=x-y x y y0 () A.[-3,0] B.[-3,2] C.[0,2] D.[0,3] 答案： B 解析：绘制不等式组表示的可行域，结合目标函数 的几何意义可得目标函数z x y 在直线3x 2y 60 与= - 直线 x0 （即x 轴）的交点A0,3处取得最小值， 此时 z min0 3 3。在点B2,0处取得最大值，此时 z max 2 0 2 . 故本题选择 B 选项 . 5.（17 全国卷Ⅲ，理数13）若 x，y 满足约束条件x y 0 x y 2 0 则z3x 4 y 的最小值为y 0 ________． 高考线性规划归类解析 一、平面区域和约束条件对应关系。 例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.若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.某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72m3，第二种有56m3，假设生产每种产品都需要用两种木料，生产一只圆桌和一个衣柜分别所需木料如下表所示.每生产一只圆桌可获利6元,生产 科学出版社《运筹学》教材 第一章引言 第二章线性规划，姜林 第三章对偶规划，姜林 第四章运输问题，姜林 第五章整数规划，姜林 第六章非线性规划，姜林 第七章动态规划，姜林 第八章多目标规划，姜林 第九章图与网络分析，熊贵武 第十章排队论，熊贵武 第十一章库存论，王勇 第十二章完全信息博弈，王勇 第十三章不完全信息博弈，王勇 第十四章决策论与影响图 第十五章运筹学模型的计算机求解 成年人每天需要从食物中摄取的营养以及四种食品所含营养和价格见下表。问 如何选择食品才能在满足营养的前提下使购买食品的费用最小？ 食品名称热量(kcal) 蛋白质(g) 钙（mg）价格（元）猪肉1000 50 400 14 鸡蛋800 60 200 6 大米900 20 300 3 白菜200 10 500 2 营养需求量 2000 55 800 解：设需猪肉、鸡蛋、大米和白菜各需 x1,x2,x3,x4斤。则热量的需求量为： 2000 20090080010004 3 2 1 x x x x 蛋白质 某工厂要做100套钢架，每套有长 3.5米、2.8米和2根2.4米的圆钢组成（如右图）已知原 料长12.3米，问应如何下料使需用的原材料最省。 解：假设从每根 12.3米的原材料上截取 3.5米、2.8米和2根2.4 米，则每根原材料需浪费 1.2米，做100套需浪费材料 120米，现 采用套裁的方法。 方案一二三四五六3.5 2.8 2.4 0 0 5 0 4 0 1 2 1 1 3 0 2 0 2 2 1 1 合计剩余 12 0.3 11.2 1.1 11.5 0.8 11.9 0.4 11.8 0.5 12.2 0.1 现在假设每种方案各下料x i （i=1、2、3、4、5、6），则可列出方程： minZ=0.3x 1+1.1x 2+0.8x 3+0.4x 4+0.5x 5+0.1x 6 约束条件： x 3+x 4+2x 5+2x 6=100 4x 2+2x 3+3x 4+x 6=100 5x 1+x 3+2x 5+x 6=200 ,,,800 50030020040055 102060503000 2009008001000. .23614min 4 3214 3 2 1 4 32 14 32 14321x x x x x x x x x x x x x x x x t s x x x x z 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 。 无穷大 线性规划练习题含答案 一、选择题 A ．4 5 - B ．1 C ． 2 D ．无法确定【答案】B 【解析】解：如图所示 要是目标函数取得最小值的最优解有无穷多个，则令ax+y=0,并平移过点C 24 (,)33 ，（可行域最 左侧的点）的边界重合即可。注意到a>0，只能与AC 重合，所以a=18．已知点集{}2 2 (,)48160A x y x y x y =+--+≤， {} (,)4,B x y y x m m 是常数=≥-+，点集A 所表示的平面区域与点集B 所表示的平面区域的边界的交点为,M N . 若点(,4)D m 在点集A 所表示的平面区域内（不在边界上），则△DMN 的面积的最大值是 A. 1 B. 2 C. 22 D. 4【答案】B 【解析】解：因为点集A 表示的为圆心为（2,4），半径为2的圆，而点集B 表示为绝对值函数表示的区域则利用数形结合思想，我们可以求解得到。【题型】选择题 9．在平面直角坐标系中，若不等式组101010x y x ax y +-≥??-≤??-+≥? （α为常数）所表示的平面区域内的面积等于2，则a 的值为（ ）A ． -5 B ．1 C ． 2 D ． 3 【答案】D 【解析】解：当a<0时，不等式表示的平满区域如图中的M ，一个无限的角形区域，面积不可能为2，故只能a 0≥，此时不等式表示的区域为如图中的N ，区域为三 角形区域，若这个三角形的面积为2，则AB=4，即点B （1,4），代入y=ax+1，得a=310．已知方程：2 20x ax b ++= (,)a R b R ∈∈，其一根在区间(0,1)内,另一根在区间(1,2)内，则22 (3)z a b =++的取值范围为 A. B. 1(,4)2 C. (1,2) D. (1,4)【答案】B 【解析】解： 2( ,2)2222f (x)x ax 2b,f (0)0 f (1)0,f (3)0b 0,a 2b 10,2a 2b 40a b z (a 3)b -1z 2解：设由图像可知，三者同时成立，求解得到由线性规划知识画出可行域，以为横轴，为纵轴，再以为目标，几何意义为区域内的点到（3,0）的距离的平方，当a=-1，b=0时，z 最大为4，当点到直线 a+2b+1=02的距离为，最小为，由题目，不能去边界2=++><>>++<++>=++11．的取值范围是则满足约束条件变量122,012430 ,++=≤-+≥≥?????x y s y x x y x y x （ ）A ．[1,4] B ．[2,8] C ．[2,10] D ．[3,9]【答案】B 【解析】约束条件034120x y x x y ≥≥+-≤?????表示的区域如图，221112y y s x x ++=++=?，11y x ++表示点（x ，y ）与点（-1，-1）的斜率，PB 的斜率为最小值，PA 的斜率为最大值，斜率的取值范围是[1,4]，112y x ++?的取值范围是[2,8]。 12．若变量x,y 满足约束条件1 325x y x x y ≥-?? ≥??+≤? 则z=2x+y 的最大值为 （A ）1 (B)2 (C)3 (D)4【答案】C 【解析】：∵ 作出可行域，作出目标函数线，可得直线与 y x = 与325x y +=的交点为最优解点，∴即为（1，1），当1,1x y ==时max 3z =13．在集合 }4,1,1|),{(≤+≥≥=y x y x y x A 中，y x 2+的最大值是 线性规划及单纯形法 一．选择 1. 运筹学应用分析、试验、（C ）的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 A 统筹 B 量化 C 优化 D 决策 2. 运筹学研究的基本手段是（A ）。 A 建立数学模型 B 进行数学分析 C 进行决策分析 D 建立管理规范 3. 运筹学研究的基本特点是（ C ）。 A 进行系统局部独立分析 B 考虑系统局部优化 C 考虑系统的整体优化 D 进行系统的整体决策 4. 线性规划问题的数学模型包含三个组成要素：决策变量、目标函数、（B ） A 表达式 B 约束条件 C 方程变量 D 价值系数 5. 线性规划问题的基可行解X 对应线性规划问题可行域（凸集）的（ C ） A 边 B 平面 C 顶点 D 内部 6. 目标函数取极小化（Z min ）的线性规划问题可以转化为目标函数取极大化即（C ）的线性规划问题求解 A Z min B )min(Z - C )max(Z - D Z max - 7. 标准形式的线性规划问题，最优解（C ）是可行解 A 一定 B 一定不 C 不一定 D 无法确定 8. 在线性规划问题中，称满足所有约束条件方程和非负限制的解为（ C ）。 A 最优解 B 基可行解 C 可行解 D 基解 9. 生产和经营管理中经常提出任何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是所谓的（D ） A 管理问题 B 规划问题 C 决策问题 D 优化问题 10. 在线性规划问题中，图解法适合用于处理变量（ B ）个的线性规划问题 A 1 B 2 C 3 D 4 11. 求解线性规划问题时，解的情况有:唯一最优解、无穷多最优解、（ C ）、无可行解 A 无解B 无基解 C 无界解 D 无基可行解 12. 在用图解法求解的时，找不到满足约束条件的公共范围，这时问题有（D ），其原因是模型本身有错误，约束条件之间相互矛盾，应检查修正。 A 唯一最优解 B 无穷多最优解 C 无界解D 无可行解 13. 线性规划问题的基可行解()T n X X X ,,1 =为基可行解的充要条件是X 的正分量所对 应的系数列向量是（B ） A 线性相关 B 线性独立 C 非线性独立 D 无法判断 14. 线性规划问题进行最优性检验和解的判别时，如果当0≤j σ时，人工变量仍留在基本量中且不为零，（D ） A 唯一最优解 B 无穷多最优解 C 无界解 D 无可行解 15.如果集合C 中任意两个点21,X X 其连线上的所有点也都是集合C 中的点，称C 为（B ） 高考全国卷线性规划真 题含答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 2013—2017高考全国卷线性规划真题 1.【2017全国1，文7】设x ，y 满足约束条件33,1,0,x y x y y +≤?? -≥??≥? 则z =x +y 的最大值为 A ．0 B ．1 C ．2 D ．3 2.【2017全国2，文7】设,x y 满足约束条件2+330233030x y x y y -≤?? -+≥??+≥? ,则2z x y =+的最小值 是 A.15- B.9- C.1 D 9 3.【2017全国3，文5】设x ，y 满足约束条件32600 0x y x y +-≤?? ≥??≥? ，则z x y =-的取值范围是 A ．[–3,0] B ．[–3,2] C ．[0,2] D ．[0,3] 4．(2016全国1，文16)某高科技企业生产产品A 和产品B 需要甲、乙两种新型材料．生产一件产品A 需要甲材料 kg ，乙材料1 kg ，用5个工时；生产一件产品B 需要甲材料 kg ，乙材料 kg ，用3个工时．生产一件产品A 的利润为2 100元，生产一件产品B 的利润为900元．该企业现有甲材料150 kg ，乙材料90 kg ，则在不超过600个工时的条件下，生产产品A 、产品B 的利润之和的最大值为________元． 5．(2016全国2，文14)若x ，y 满足约束条件???? ?x －y ＋1≥0，x ＋y －3≥0，x －3≤0，则z ＝ x －2y 的最小值为________． 线性规划题及答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 线性规划题型及解法 一、已知线性约束条件，探求线性目标关系最值问题 例1、设变量x 、y 满足约束条件?? ???≥+-≥-≤-1122y x y x y x ，则y x z 32+=的最大值为 。 二、已知线性约束条件，探求非线性目标关系最值问题 例2、已知1,10,220x x y x y ≥??-+≤??--≤? 则22x y +的最小值是 . “()()2221++-y x ”值域？ 三、约束条件设计参数形式，考查目标函数最值范围问题。 例3、在约束条件0 024x y y x s y x ≥??≥??+≤??+≤?下，当35s ≤≤时，目标函数32z x y =+的最大值的变化范 围是（） A.[6,15] B. [7,15] C. [6,8] D. [7,8] 四、已知平面区域，逆向考查约束条件。 例4、已知双曲线224x y -=的两条渐近线与直线3x =围成一个三角形区域,表示该区域的不等式组是（） (A)0003x y x y x -≥??+≥??≤≤? (B)0003x y x y x -≥??+≤??≤≤? (C) 0003x y x y x -≤??+≤??≤≤? (D) 0003x y x y x -≤??+≥??≤≤? 五、已知最优解成立条件，探求目标函数参数范围问题。 例5已知变量x ，y 满足约束条件1422x y x y ≤+≤??-≤-≤? 若目标函数z ax y =+（其中0a >）仅在点(3,1)处取得最大值，则a 的取值范围为 。 六、设计线性规划，探求平面区域的面积问题 例６在平面直角坐标系中，不等式组20 200x y x y y +-≤??-+≥??≥? 表示的平面区域的面积是（） (A) 七、研究线性规划中的整点最优解问题 例7、某公司招收男职员x 名，女职员y 名，x 和y 须满足约束条件 ?? ???≤≥+-≥-.112, 932,22115x y x y x 则1010z x y =+的最大值是(A)80 (B) 85 (C) 90 (D)95 八、比值问题 当目标函数形如b x a y z --= 时,可把z 看作是动点()y x P ,与定点()a b Q ,连线的斜率，这样目标函数的最值就转化为PQ 连线斜率的最值。 简单的线性规划问题 [学习目标] 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)给定一项任务，问怎样统筹安排，使完成这项任务耗费的人力、物力资源量最小． 常见问题有： ①物资调动问题 例如，已知两煤矿每年的产量，煤需经两个车站运往外地，两个车站的运输能力是有限的，且已知两煤矿运往两个车站的运输价格，煤矿应怎样编制调动方案，才能使总运费最小？ 线性规划常见题型及解法 一．基础知识： (一)二元一次不等式表示的区域 二元一次不等式0>++C By Ax 表示直线0=++C By Ax 某一侧的所有点组成的区域，把直线画成虚线表示不包括边界， 0≥++C By Ax 所表示的区域应包括边界，故边界要画成实线. 由于在直线0=++C By Ax 同一侧的所有点（x,y ）,把它的坐标（x,y ）代入C By Ax ++，所得的符号相同，所以只需在此直线的某一侧取一个特殊点（0,0y x ），从C By Ax ++00的正负即可判断0≥++C By Ax 表示直线哪一侧的平面区域。通常代特殊点（0，0）。 （二）线性规划 (1)不等式组是一组对变量x 、y 的约束条件，由于这组约束条件都是关于x 、y 的一次不等式，所以又可称其为线性约束条件.z =A x +B y 是欲达到最大值或最小值所涉及的变量x 、y 的解析式，我们把它称为目标函数.由于z =A x +B y 又是关于x 、y 的一次解析式，所以又可叫做线性目标函数. 另外注意：线性约束条件除了用一次不等式表示外，也可用一次方程表示. (2)一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题. (3)那么，满足线性约束条件的解（x ,y ）叫做可行解，由所有可行解组成的集合叫做可行域.在上述问题中，可行域就是阴影部分表示的三角形区域.其中可行解（11,y x ）和（22,y x ）分别使目标函数取得最大值和最小值，它们都叫做这个问题的最优解. 线性目标函数的最值常在可行域的顶点处取得;而求最优整数解必须首先要看它们是否在可行 (4)用图解法解决简单的线性规划问题的基本步骤： 1.首先，要根据线性约束条件画出可行域（即画出不等式组所表示的公共区域）. 2.设z =0，画出直线l 0. 3.观察、分析，平移直线l 0，从而找到最优解. 4.最后求得目标函数的最大值及最小值. (5) 利用线性规划研究实际问题的解题思路： 首先，应准确建立数学模型，即根据题意找出约束条件，确定线性目标函数. 然后，用图解法求得数学模型的解，即画出可行域，在可行域内求得使目标函数取得最值的解. 最后，还要根据实际意义将数学模型的解转化为实际问题的解，即结合实际情况求得最优解. 线性规划是新教材中新增的内容之一，由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型，除此之外，还有以下常见题型。 一、求线性目标函数的取值范围 例1、 若x 、y 满足约束条件222x y x y ≤?? ≤??+≥? ，则z=x+2y 的取值范围是 （ ） A 、[2,6] B 、[2,5] C 、[3,6] D 、（3,5] 二、求可行域的面积 x y O 2 2 x=2 y =2 x + y =2 B A 线性规划简单练习题文件编码（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 =-的取值范围为 .单纯形法步骤例题详解
线性规划经典例题及详细解析
线性规划典型例题
线性规划题及答案
六种经典线性规划例题
线性规划习题附答案模板
八种 经典线性规划例题(超实用)
高考全国卷及各省数学线性规划真题附答案.docx
高中数学线性规划经典题型
简单的线性规划 习题含答案
单纯形法典型例题
线性规划经典例题及详细解析
线性规划练习题含答案
第1章线性规划及单纯形法
高考全国卷线性规划真题含答案完整版
线性规划题及答案完整版
简单的线性规划问题附答案)
线性规划常见题型及解法 均值不等式(含答案)
线性规划简单练习题