运筹学 线性规划习题解析.ppt

管理运筹学,第一章线性规划,第一章线性规划,1、某化工厂生产某项化学产品，每单位标准重量为1000克，由A、B、C三种化学物混合而成。产品组成成分是每单位产品中A不超过300克，B不少于150克，C不少于200克。A、B、C每克成本分别为5元、6元、7元。问如何配置此化学产品，才能使成本最低？,minS=min(5x1+6x2+7x3)x1+x2+x3=1000 x1300 x2150 x3200 x1,x2,x30,解：设配制此化学产品所需A、B、C三种化学物分别为x1，x2，x3克，成本为S元，则由题意可得本题的线性规划模型为：,第一章线性规划,2、某产品重量为150千克，用A、B两种原料制成。每单位A原料成本为2元，每单位B原料成本为8元。该产品至少需要含14单位B原料，最多含20单位A原料。每单位A、B原料分别重5千克、10千克，为使成本最小，该产品中A、B原料应各占多少？,minS=min(2x1+8x2)5x1+10 x2=150 x120 x214x1,x20,解：由题意可设该产品中A、B原料分别为x1，x2千克，总成本为S，则本题线性规划模型为：,第一章线性规划,3、设某工厂有甲、乙、丙、丁四台机床，生产A、B、C、D、E、F六种产品。加工每一件产品所需要时间和每一件产品的单价如下表所示：表中没有填数的表示这台机床不参加生产这种产品。现假设在某一时间内，甲、乙、丙、丁四台机床的最大工作能力分别为850、700、600、900工时，问这一时段内，每种产品各应生产多少，才能使该厂总收入最大？,maxS=max(40 x1+28x2+32x3+72x4+64x5+80 x6)x1+x2+x3+3x4+3x5+3x68502x1+5x47002x2+5x46003x3+8x6900 x1，x2x60,解：由题意可设产品A、B、C、D、E、F分别生产x1，x2，x3，x4，x5，x6单位，总收入为S元，则本题的线性规划模型为：,第一章线性规划,4、一家玩具公司制造三种玩具，每一种要求不同的制造技术。高级的一种需要17个小时加工装配，8小时检测，每台利润30元；中级的需2小时加工装配，半小时检测，每台利润5元；低级的需半小时加工装配，10分钟检测，每台利润1元。现公司可供利用的加工装配时间为500小时，检测时间100小时。市场预测显示，对高级、中级、低级玩具的需求量分别不超过10台、30台、100台，试制定一个能够使总利润最大的生产计划。,解：由题意设生产高级、中级、低级玩具各为x1，x2，x3台，总利润为S元，则由题意可得本题的线性规划模型为：,由题意可得下表条件约束：,maxS=max(30 x1+5x2+x3)17x1+2x2+1/2x35008x1+1/2x2+1/6x3100 x110 x230 x3100 x1,x2,x30,第一章线性规划,5、现有300cm长的钢管500根，需截成70cm长和80cm长两种规格的成套材料。每套由70cm的3根，80cm的12根组成。问如何截管，可以使余料最少，套数最多？,解：由题设条件可得到1根300cm长的钢管有以下几种分割方法：,设x1、x2、x3、x4分别代表四种方法分割300cm的钢管的根数，S表示废料的总长度,x1+x2+x3+x4=500可以截得80cm钢管（3x1+2x2+x3）根，70cm钢管（2x2+3x3+4x4）根，共有废料（60 x1+10 x3+20 x4）cm则可得：(3x1+2x2+x3):(2x2+3x3+4x4)=12:3化简的：3x1-6x2-11x3-16x4=0,minS=min(60 x1+10 x2+20 x3)x1+x2+x3+x4=5003x1-6x2-11x3-16x4=0 x1，x2，x3,x40,第一章线性规划,6、某皮革厂生产甲、乙两种皮带，生产甲、乙皮带每条可获利分别为4元、3元。但生产一条甲皮带是生产一条乙皮带所需工时的2倍，如果全部生产乙皮带，该厂每天可生产1000条，但皮革供应只够日产800条（甲、乙两种皮带合计），甲、乙皮带所用皮扣（一条一扣）每天分别只能供应400个、700个。问如何安排生产，可使该厂获利最大？,maxS=max(4x1+3x2)2x1+x21000 x1+x2800 x1400 x2700 x1、x20,解：由题设条件设生产甲、乙两种皮带分别为x1、x2根,交点：x1=200 x2=600,第一章线性规划,7、某厂用甲、乙两种原料生产A、B两种产品，制造A、B产品每吨所需要的各种原料、可得利润以及工厂现有的各种原料数如下表所示：,（1）在现有原料条件下，如何组织生产才能使利润最大maxS=max(7x1+5x2)x1+2x2284x1+x242x1，x20,解：设生产A、B两种产品分别为x1、x2单位,（1）在现有原料条件下，如何组织生产才能使利润最大,图解：,x2,x1,14,28,42,10.5,4x1+x2=42,X1+2x2=28,k=-7/5,4x1+x2=42X1+2x2=28,解得：x1=8,x2=10,K1=-4,k2=-1/2,（2）如果原料甲增加到42吨，原最优解是否改变？,图解：,x2,x1,21,42,42,10.5,4x1+x2=42,X1+2x2=42,k=-7/5,4x1+x2=42X1+2x2=42,解得：x1=6,x2=18,(3)如果每吨B产品的利润增加到15万元，原最优解是否改变？,图解：,x2,x1,14,28,42,10.5,4x1+x2=42,X1+2x2=28,k=-7/15,最优解是x1+2x2=28与x2轴的交点（0,14）,（4）每吨B产品的利润在什么范围内变化，原最优解才不会改变？,图解：,x2,x1,14,28,42,10.5,4x1+x2=42,X1+2x2=28,-4k-1/2,k1=-4,k2=-1/2,可得：-4k-1/2目标函数：7x1+bx2k=-7/b7/4b14,复习,条件：满足前约束满足后约束无非零分量，或有非零分量但其非零分量对应的A的列向量线性无关使目标函数最大,第一章线性规划,10、已知线性规划问题为：minS=min(x1+2x2-3x3+4x4)5x2+x3+3x4=5x1+4x2+x3+4x4=7xi(i=1,2,3,4)判断下述各点：X1=（8,2,7，-4）T，X2=（1，0,2,1）T，X3=（2,0,5,0）T，X4=（0,0，-1,2）T，X5=（3,1,0,0）T是不是该问题的可行解、基础解、基可行解。试从中找出最优的一个解。,第一章线性规划,X1不是基础解（满足前约束但非零分量对应的列向量线性相关），不是可行解（不满足后约束），不是基可行解。X2不是基础解（非零分量对应的列变量线性相关），是可行解（满足前后约束），不是基可行解。X3是基础解（非零分量对应的列变量线性无关）、可行解，因此也是基可行解。X4是基础解，不是可行解，因此也不是基可行解。X5是基础解、可行解，因此也是基可行解。将X3和X5带入目标函数可得：S3S5，所以X3是最优解。,第一章线性规划,11、已知X0=（2,3,0）T是某线性规划问题的最优解，能否判断：（1）X0一定是基础解；（2）X0一定是可行解；（3）X0一定是基可行解；（4）X0一定是基最优解。,错,对,错,错,第一章线性规划,12、已知X0=（2,0，-1）T是某已化成满秩标准形的，具有3个变量的线性规划问题的一组值，能否判定：（1）X0一定不是基础解；（2）X0一定不是可行解；（3）X0一定不是基可行解；（4）X0一定不是最优解；（5）X0一定不是基最优解。,错,对,对,对,对,第一章线性规划,13、已知线性规划问题maxS=max(x1+x2-x3)ax1+