简单线性规划

1、典型例题一x y 20,例1 画岀不等式组 x y 40,表示的平面区域.x 3y 30.分析：采用“图解法”确定不等式组每一不等式所表示的平面区域，然后求其公共部分.解：把x 0, y 0代入 x y 2中得 0020不等式 x y 2 0表示直线x y 2 0下方的区域（包括边界），即位于原点的一侧，同理可画岀其他两部分，不等式组所表示的区域如图所示. 说明：“图解法”是判别二元一次不等式所表示的区域行之有效的一种方法.典型例题二例2画岀2x 3 y 3表示的区域，并求所有的正整数解（x, y）.分析：原不等式等价于 y 2x 3,而求正整数解则意味着 x，y还有限制条件，即求y 3.xx

2、yy0, y乙y 2x3.0,z,3,'解：依照二元2x3y次不等式表示的平面区域，知3表示的区域如下图：x0, y0,xz, y乙对于2 x 3y 3的正整数解，先画岀不等式组.所表示的平面区域，如图所示y2x3,y3.容易求得，在其区域内的整数解为（1,1）、（1,2）、（1,3）、（2,2）、（2,3）.说明：这类题可以将平面直角坐标系用网络线画岀来，然后在不等式组所表示的平面区域内找岀符 合题设要求的整数点来.典型例题三例3求不等式组yyx 11所表示的平面区域的面积.x 1分析：本题的关键是能够将不等式组所表示的平面区域作岀来，判断其形状进而求岀其面积而要 将平面区域作岀来的

3、关键又是能够对不等式组中的两个不等式进行化简和变形，如何变形？需对绝对值 加以讨论.解：不等式y x 11可化为y x(x 1)或y x 2(x1)；不等式y x 1可化为y x 1(x0)或y x 1(x0).在平面直角坐标系内作岀四条射线AB: yx(x 1)， AC: y x 2(x1)DE: yx1(x0)， DF : yx 1(x0)则不等式组所表示的平面区域如图由于AB与AC、DE与DF互相垂直，所以平面区域是一个矩形.42z42根据两条平行线之间的距离公式可得矩形的两条边的长度分别为和匚2 23所以其面积为 .2典型例题四2x y 120,例1若x、y满足条件3x 2y 100,

4、求z x 2y的最大值和最小值.x 4y 100.分析：画岀可行域，平移直线找最优解.解：作岀约束条件所表示的平面区域，即可行域，如图所示.1作直线l : x 2y z，即y x2当它在可行域内滑动时，由图可知，直线小值.1 1z一 、z，它表示斜率为，纵截距为的平行直线系，2 22zmax2 2 8 18zminl过点时，z取得最大值，当I过点B时，z取得最说明：解决线性规划问题，首先应明确可行域，再将线性目标函数作平移取得最值.典型例题五例5用不等式表示以 A(1,4)，B( 3,0)，C( 2,2)为顶点的三角形内部的平面区域.分析：首先要将三点中的任意两点所确定的直线方程写岀来，然后结

5、合图形考虑三角形内部区域应 怎样表示。解：直线AB的斜率为：kAB4 01 ( 3)1，其方程为y x 3 .可求得直线BC的方程为y 2x 6 直线AC的方程为y 2x 2 .面区域内，同时又在不等式 2x y 20所表示的平面区域内（如图）x y 30,所以已知三角形内部的平面区域可由不等式组2x y 6 0,表示.2x y 20说明：用不等式组可以用来平面内的一定区域，注意三角形区域内部不包括边界线.典型例题六例6已知x y 50 , x y 100 求x2 y2的最大、最小值.2分析：令zx22y2，目标函数是非线性的而2 2 2 2 z x y； x y可看做区域内的点到原点距离的平

6、方.问题转化为点到直线的距离问题.卄,x解：由y5°得可行域（如图所示）为z22 2 2 2x y, x y ，而(0,0)到xy100,x y 50，xy5100的距离分别为和102所以z的最大、最小值分别是 50和 .2说明：题目中的目标函数是非线性的解决的方法类似于线性规划问题可做岀图，利用图进行直 观的分析.典型例题七4x 3y 200,例7设z 7x 5y式中的变量x、y满足下列条件 x 3y 20, 求z的最大值.x、y N *，故只是可行域内的整0，得可行域如图所示.x N*, y N * .分析：先作出不等式组所表示的可行域，需要注意的是这里的 数点，然后作岀与直线

7、7x 5y 0平等的直线再进行观察.解：作岀直线h：4x 3y 200和直线12： x 3y 2解方程组 4x 3y 200得交点A(22,-).x 3y 2 055又作直线丨:7x 5y 0,平等移动过点 A时，7x 5y取最大值，然而点 A不是整数点，故对应4 4的z值不是最优解，此时过点A的直线为7x 5y 34 ，应考虑可行域中距离直线 7x 5y 34 最5 5近的整点，即B（2,4），有z（b） 7 2 5 4 34，应注意不是找距点 A最近的整点，如点C（4,1）为可行域中距 A最近的整点，但 z（C） 7 4 5 1 33，它小于z（B），故z的最大值为34 .说明：解决这类题

8、的关键是在可行域内找准整点若将线性目标函数改为非线性目标函数呢？典型例题八x 4y 3,例8设z x2 y2，式中的变量xy满足 3x 5y 25,试求z的最大值、最小值.2 2x y应理解为可行域中的点x 1.分析：作岀不等式组所表示的平面区域，本题的关键是目标函数与坐标原点的距离的平方.解:作岀直线h： x4y 30，l2:3x 5y 250，l3：1得到如图所示的可行域.3x4y5y25得 A(5,2)03x4y130得C(1,1)5y1250得 B(1,22).5由图可知：当（x, y）为点C（1 ,1）时，z取最小值为2；当（x, y）为点A（5,2）时，z取最大值29.x说明：若将

9、该题中的目标函数改为z，如何来求z的最大值、最小值呢？请自己探求.（将目y标函数理解为点（x, y）与点（0,0）边线的斜率）典型例题九例 9 设 x 0， y 0， z 0 ； p 3x y 2z，q x 2y 4z，x y z 1，用图表示岀点（p , q）的范围.分析：题目中的p，q与x， y， z是线性关系可借助于 x， y，z的范围确定（p , q）的范围.解：由x3x y 2z p,x 2y 4z q,得 yx y z 1,z丄(827 (1427丄(527q 6p),5q 3p),由 x4p3q),6p q 8 0,3p 5q 140,做岀不等式所示平面区域如图所示3p 4q 5

10、0,说明：题目的条件隐蔽，应考虑到已有的x, y , z的取值范围借助于三元一次方程组分别求岀 x , y , z，从而求岀 p , q所满足的不等式组找岀 （p,q）的范围.典型例题十例10某糖果厂生产 A、B两种糖果，A种糖果每箱获利润 40元，B种糖果每箱获利润 50元, 其生产过程分为混合、烹调、包装三道工序，下表为每箱糖果生产过程中所需平均时间（单位：分钟）混合烹调包装153241每种糖果的生产过程中，混合的设备至多能用12机器小时，烹调的设备至多只能用机器30机器小时，包装的设备只能用机器15机器小时，试用每种糖果各生产多少箱可获得最大利润.分析：找约束条件，建立目标函数.解：设生

11、产A种糖果x箱，B种糖果y箱，可获得利润 z元，则此问题的数学模式在约束条件x 2y 7205x 4y 18003x y 900 下，求目标函数 z 40x50 y的最大值，作岀可行域，其边界x 0y 04 z4zz由z 40x 50 y得y x，它表示斜率为，截距为的平行直线系，越大，z5 5055050越大，从而可知过 C点时截距最大，z取得了最大值.x 2y 720解方程组，C 120,3005x 4y 1800 Zmax 40 120 50 300 19800即生产A种糖果120箱，生产B种糖果300箱，可得最大利润19800元.说明：由于生产 A种糖果120箱，生产B种糖果300箱，

12、就使得两种糖果共计使用的混合时间为120 + 2X 300 = 720 （分），烹调时间 5X 120 + 4X 300 = 1800 （分），包装时间 3 X 120 + 300 = 660 （分）， 这说明该计划已完全利用了混合设备与烹调设备的可用时间，但对包装设备却有240分钟的包装时间未加利用，这种“过剩”问题构成了该问题的“松驰”部分，有待于改进研究.典型例题十例11甲、乙、丙三种食物的维生素A、B含量及成本如下表:甲乙丙维生素A （单位/千克）600700400维生素B （单位/千克）800400500成本（元/千克）1194某食物营养研究所想用 x千克甲种食物， y千克乙种食物，

13、z千克丙种食物配成 100千克的混合食 物，并使混合食物至少含56000单位维生素 A和63000单位维生素 B . （ 1）用X、y表示混合物成本C .（ 2）确定x、y、z的值，使成本最低.100 x y分析：找到线性约束条件及目标函数，用平行线移动法求最优解.解：（1 ）依题意：x、y、z满足x y z 100 z成本 C 11x 9y 4z 7x 5y 400 （元）依题意 600x 700y 4°°z 56°°02x3y160z 100 x y 3xy130x0，y0作出不等式组所对应的可行域，如图所示.800x 400y 500z 63000

14、3x y 130联立、一2x 3y 160交点 A 50,20作直线7x 5y 400 C则易知该直线截距越小,轴截距最小，从而 C最小，此时7X 50+ 5 X 20+ 400 = C = 850元 x 50千克，z 30千克时成本最低.典型例题十二例12某工厂有甲、乙两种产品，按计划每天各生产不少于15t，已知生产甲产品1t需煤9t,电力4kW，劳力3个（按工作日计算）；生产乙产品 1t需煤4t，电力5kW，劳力10个；甲产品每吨 价7万元，乙产品每吨价 12万元；但每天用煤最不得超过300吨，电力不得超过 200 kW，劳力只有300个问每天各生产甲、乙两种产品多少t，才能既保定完成生产

15、任务，又能为国家创造最多的财富.分析：先设每天生产甲、乙两种产品的产量分别为xt和yt，建立约束条件和目标函数后，再利用图形直观解题.解：设每天生产甲产品 xt，乙产品yt，总产值St，依题意约束条件为:目标函数为S 7x 12y .（如图阴影部分）.约束条件表示的可行域是五条直线所围成区域的内部的点加上它的边线上的点现在就要在可行域上找岀使S 7x 12y取最大值的点(x,y) 作直线S 7x 12y，随着S取S值的变化，得到一束平行直线，其纵截距为，可以看出，当直线的纵截距越大，S值也越大.12从图中可以看岀，当直线 S 7x 12y经过点A时，直线的纵截距最大，所以S也取最大值.4x 5

16、y 200 0,解方程组3x 10y 300 0,得 A(20,24) 故当 x 20，y 24 时,S最大值7 2012 24428 (万元)答：第天生产甲产品 20 t，乙产品24 t，这样既保证完成任务，又能为国家创造最多的财富428万元.说明：解决简单线性规划应用题的关键是：(1)找岀线性约束条件和目标函数；(2)准确画岀可行域；S(3)利用S的几何意义，求岀最优解如本例中，是目标函数S 7x 12y的纵截距.12典型例题十三例13有一批钢管，长度都是4000 mm，要截成500 mm和600 mm两种毛坯，且这两种毛坯数量1 、比大于-配套，怎样截最合理？3分析：先设岀未知数，建立约

17、束条件和目标函数后，再按求最优解是整数解的方法去求.解：设截500 mm的x根，600 mm的y根，根据题意，得5x 6y 40,y 3x, 曰且 x, y z x 0,y 0.作岀可行域，如下图中阴影部分.目标函数为z x y，作一组平行直线 x y t，经过可行域内的点且和原点距离最远的直线为过B(0,8)的直线，这时x y 8 由x，y为正整数，知(0,8)不是最优解.在可行域内找整点，使 x y 7可知点(2,5)，(3,4)，(4,3)，(5,2)，(6,1)均为最优解.答：每根钢管截 500 mm的2根，600 mm的5根，或截500 mm的3根，600 mm的4根或截500 mm

18、 的4根，600 mm的3根或截 500 mm的5根，600 mm的2根或截500 mm的6根，600 mm的1根最合 理.500x 600y 4000,3,5xy其中x、y均为整数作岀可行域,0,0.如下图所示中阴影部分.直线x yt，经过可行域内的点且和原点相距最远的直线为过解5x3x6y40402312023故a40空2323，即6y 40,3x,0,0.目标函数为y 7，调整为x 2， y 5.z x y，作一组平行A点的直线先求 A点的坐标,经检验满足条件，所以每根截500 mm的2根，600 mm的5根最合理.本题解法错误主要是在作一组平行直线x y t时没能准确作岀，而得到经过可

19、行域内的点且和原点距离最远的直线为过 A点的直线.此错误可检验如下：如果直线x y t通过A点，它是经过可行域内的点且到原点距离最远的直线，那么40 1202323175由于再有其他点满足域内找满足xA点外，不可能y为整数，所以点 A(1,5)不是最优解但在可行域内除23237，只能在可行域内找满足x y 6的点如果还没有整数点，则只能在可行5的整数点但我们知道x 2，y5满足题意，这样，就岀现了矛盾，从而判断解法错误，即x y t通过A点的直线并不是通过可行域内的点且和原点距离最远的直线.典型例题十四例14某工厂生产 A、B两种产品，已知生产 A产品1 kg要用煤9t ,电力4 kW，3个工

20、作日;生产B产品1 kg要用煤4t，电力5kW，10个工作日又知生产岀 A产品1 kg可获利7万元，生产 岀B产品1 kg可获利12万元，现在工厂只有煤360 t，电力200 kW，300个工作日，在这种情况下生产A，B产品各多少千克能获得最大经济效益.分析：在题目条件比较复杂时，可将题目中的条件列表.解： 设这个工厂应分别生产 A ， B 产品 xkg ， ykg ，可获利 z 万元根据上表中的条件，列出线3x10y300,9x4y360,性约束条件为目标函数为z 7x 12y（万兀）4x5y200,x 0,y 0,画岀如图所示的可行域， 做直线i'：7x 12y 0，做一组直线7x

21、 12y t与l'平行，当I过点A时3x 10y 300,t最大.由得A点坐标为（20,24） 把A点坐标代入I的方程，得t 428（万元）.4x 5y 200,答：应生产 A产品20 t，B产品24 t，能获最大利润 428万元.说明： 把实际问题转化为线性规划问题的难点在于找岀题目中的所有线性约束条件.同时本题的可 行域形状较复杂，要注意分析目标函数的斜率和各边界斜率的关系：从而确定在何处取得最优解.解应 用题时还应注意设岀未知量和做答这两个必要步骤.典型例题十五例15某公司每天至少要运送 180t货物公司有8辆载重为6t的A型卡车和4辆载重为10t的B型 卡车，A型卡车每天可往返

22、 4次，B型卡车可往返3次，A型卡车每天花费 320元，B型卡车每天花 费 504 元，问如何调配车辆才能使公司每天花费最少.分析：设A型卡车x辆，B型卡车y辆问题转化为线性规划问题同时应注意到题中的能取整数.0 x 8,0 x 8,解：设A型卡车x辆，B型卡车y辆，则y 4,y 10,即0y 4,y 10,24x 30y 180,4x 5y 30,目标函数 z 320x 504y 做如图所示的可行域，做直线 I'：320x 504y0 在可行域中打上网格，找岀(8,0)， (8,1)， (8,2)， (7,1)， (7,2)，（7,3），等整数点做1:320x 504y t与I平行，

23、可见当I过（8,0）时t最小，即zmin 8 3202560 （元）.说明：整数解的线性规划问题如果取最小值时不是整数点，则考虑此点附近的整数点.典型例题十六例16某工厂利用两种燃料生产三种不同的产品A、B、C，每消耗一吨燃料与产品 A、B、C有下列关系：现知每吨燃料甲与燃料乙的价格之比为2:3，现需要三种产品 A、B、C各50吨、63吨、65吨问如何使用两种燃料，才能使该厂成本最低？分析：由于该厂成本与两种燃料使用量有关，而产品 A、B、C又与这两种燃料有关，且这三种 产品的产量也有限制，因此这是一道求线性目标函数在线性约束条件下的最小值问题，这类简单的线性 规划问题一般都可以利用二元一次不等式求在可行域上的最优解.解：设该厂使用燃料甲 x吨，燃料乙y吨，甲