第4章--数学规划模型

第4章数学规划模型4.1某饲养场用n种原料配合成饲料喂鸡，为了让鸡生长得快，对m种营养成分有一个最低标准。即对mi,,1，要求第种i营养成分在饲料中的含量不少于ib，若每单位第j种原料中含第i种营养成分的量为ija，第j种原料的单价为jc，问应如何配制饲料才能使成本最低？解：模型假设：假设ib为每单位饲料中营养成分的最少含量假设ija每单位第j种原料中第i种营养成分的百分比模型的建立：设jx为每单位饲料中第j种原料的含量，其中1,,jn由已知,目标函数为min1njjjzcx约束条件为:1nijjijaxb1,,im4.2拟分配甲、乙、丙、丁四人去干四项工作，每人干且仅干一项。他们干各项工作需用天数见右表，问应如何分配才能使总用工天数最少。解：模型的建立与求解:记i=1,2,3,4分别表示甲乙丙丁四人,j=1,2,3,4分别表示工作1234,用ija表示i人干工作j。ija1234110978258773546542345工作工人1234甲乙丙丁10978587754652345引入0-1变量xij，若i人干j工作，则xij=1，否则xij=0。根据题目要求，四人干四项工作，每人干且仅干一项，可得以下约束条件：（1）41ijix=1（2）41ijjx=1当第i人干第j项工作时，ijijax表示所用天数，否则ijijax=0，所以甲乙丙丁分工干各项工作的总用工天数为4411ijijijax，也即该问题的目标函数。综上，这个问题的0-1规划模型可写作：minz=4411ijijijaxs．t．41ijix=1j=1,2,3,441ijjx=1i=1,2,3,4ijx={0,1}程序：将题目所给数据带入上述模型，并输入lindo：min10x11+9x12+7x13+8x14+5x21+8x22+7x23+7x24+5x31+4x32+6x33+5x34+2x41+3x42+4x43+5x44s.t.x11+x12+x13+x14=1x21+x22+x23+x24=1x31+x32+x33+x34=1x41+x42+x43+x44=1x11+x21+x31+x41=1x12+x22+x32+x42=1x13+x23+x33+x43=1x14+x24+x34+x44=1endint16计算结果为：13x=21x=34x=42x=1，其余全为0，即甲做第三项工作，乙做第一项工作，丙做第四项工作，丁做第二项工作，最少用工天数为20天。4.3某校经预赛选出A，B，C，D四名学生，将派他们去参加该地区各学校之间的竞赛。此次竞赛的四门功课考试在同一时间进行，因而每人只能参加一门，比赛结果将以团体总分计名次（不计个人名次）。设下表是四名学生选拔时的成绩，问应如何组队较好？解：模型的建立与求解:记i=1,2,3,4分别表示A、B、C、D四名学生,j=1,2,3,4分别表示数学、物理、化学、外语,用ija表示i同学参加j功课考试。ija1234190957883285897380393918879479858487引入0-1变量xij，若i同学参加j功课考试，则xij=1，否则xij=0。根据题目要求，每人只能参加一门考试，且以团体总分计名次，不计个人名次，可得以下约束条件：（1）41ijix=1（2）41ijjx=1当第i同学参加第j功课考试时，ijijax表示所得成绩，否则ijijax=0，所以ABCD分别参加各门功课考试的总成绩为4411ijijijax，也即该问题的目标函数。综上，这个问题的0-1规划模型可写作：maxz=4411ijijijaxs．t．41ijix=1j=1,2,3,441ijjx=1i=1,2,3,4课程学生数学物理化学外语ABCD90859379958991857873888483807987ijx={0,1}程序：将题目所给数据带入上述模型，并输入lindo：max90x11+95x12+78x13+83x14+85x21+89x22+73x23+80x24+93x31+91x32+88x33+79x34+79x41+85x42+84x43+87x44s.t.x11+x12+x13+x14=1x21+x22+x23+x24=1x31+x32+x33+x34=1x41+x42+x43+x44=1x11+x21+x31+x41=1x12+x22+x32+x42=1x13+x23+x33+x43=1x14+x24+x34+x44=1endint16计算结果为：12x=21x=33x=44x=1，其余全为0，即A参加物理考试，B参加数学考试，C参加化学考试，D参加外语考试，按选拔时的成绩总分最大值为355。4.4某工厂生产两种标准件，A种每个可获利0.3元，B种每个可获利0.15元。若该厂仅生产一种标准件，每天可A种标准件800个或B种标准件1200个，但A种标准件还需某种特殊处理，每天最多处理600个，A，B标准件最多每天包装1000个。问该厂应该如何安排生产计划，才能使每天获利最大。4.5将长度为500cm的线材截成长度为78cm的坯料至少1000根，98cm的坯料至少2000根，若原料充分多，在完成任务的前提下，应如何截切，使得留下的余料最少？解：模型的建立与求解:材料的切割模式有如下:模式78cm98cm余料160322511233270423505143060510设按第i种模式切割的线材个数为ix,i=1,2,3,4,5,6由已知,目标函数为minz=321x+122x+703x+504x+305x+106x约束条件为:61x+52x+33x+24x+5x+06x100001x+2x+23x+34x+45x+56x2000运用lindo软件求解得:2x=200,6x=360,1x=3x=4x=5x=0即按第二种模式切200根,按第六种模式切360根，最少余料为6000cm。4.6某厂有原料甲、乙，生产四种产品A，B，C，D，各参数如下表：（1）求总收入最大的生产方案；（2）当最优生产方案不变时，分别求出A，B，C，D的单价的变化范围；（3）当最优基不变时，分别求出原料甲、乙的变化范围。解：模型的建立与求解:(1)设A,B,C,D四种产品的生产量分别是1x,2x,3x,4x(单位:件)该问题的目标是使总收入最大,目标函数可简记为maxz=91x+82x+503x+194x约束条件为甲乙原料的限额,即:31x+22x+103x+44x1823x+0.54x3运用lindo软件求解得:1x=2x=0,3x=1,4x=2,此时目标函数最大值为88,即可获88元收入。（2）运用lindo软件有如下运算结果：VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX19.0000004.000000INFINITYX28.0000000.666667INFINITYX350.0000002.0000012.500000X419.0000001.0000000.500000即在最优生产方案不变时，A产品单价变化范围为（0，13），B产品单价变化范围为（0，8.7），C产品单价变化范围为（47.5，52），D产品单价变化范围为（18.5，20）（3）运用lindo软件有如下运算结果：单位消耗产品原料ABCD限额（公斤）甲乙321040020.5183单价（万元/万件）985019ROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE218.0000006.0000003.00000033.0000000.6000000.750000即在最优基不变时，甲材料的变化范围是（15，24），乙材料的变化范围是（2.25，3.6）4.7某厂生产A，B两种产品，分别由四台机床加工，加工顺序任意，在一个生产期内，各机床的有效工作时数，各产品在各机床的加工时数等参数如下表：加工时数机床产品甲乙丙丁单价（百元/件）AB2140220123有效时数240200180140（1）求收入最大的生产方案；（2）若引进新产品C，每件在机床甲，乙，丙，丁的加工时间分别是3，2，4，3小时，问C的单价多少时才宜投产？当C的单价为4百元时，求C投产后的生产方案。（3）为提高产品质量，增加机床戊的精加工工序，其参数如下。问应如何安排生产。解：模型的建立与求解:(1)设A,B两种产品的生产量分别是1x,2x(单位:件)该问题的目标是使总收入最大,目标函数可简记为maxz=21x+32x由已知约束条件为各机床的有效时数,即:21x+22x2401x+22x20041x1802x140运用lindo软件求解得:1x=40,2x=80,此时目标函数最大值为320,即可获32000元收入。即当生产40件A产品,80件B产品时,可以获得最大收入。(2)设C产品的生产量为3x产品AB有效时数精加工时间22.4248目标函数改变为maxz=21x+32x+03x约束条件改变为:21x+22x+33x2401x+22x+23x20041x+43x1802x+33x140VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX12.0000001.500000INFINITYX23.000000INFINITY3.000000X30.0000003.000000INFINITY可知,C产品的价格变化在(0,3)之间时,生产方案不变,所以,当C产品的价格大于300元时,方可投入生产。当C产品的价格是400元时，目标函数变为maxz=21x+32x+43x，约束条件不变运用lindo软件求解得:1x=16,2x=68,3x=24，此时目标函数最大值为332,即可获33200元收入。即当生产16件A产品,68件B产品，24件C产品时,可以获得最大收入。（3）增加机床戊后，目标函数不变，约束条件增加一个，即21x+2.42x248运用lindo软件求解得:1x=10,2x=95,此时目标函数最大值为305,即可获30500元收入。即当生产10件A产品,95件B产品时,可以获得最大收入。4.8已知某厂生产有关参数：单位消耗产品原料ABCDE限额（公斤）甲乙丙0.100.20.30.10.20.20.100.300.300.20.1600500300单价（元）43658（1）求最优生产方案；（2）根据市场情况，计划A至少生产500件，求相应生产方案；（3）因E滞销，计划停产，求相应生产方案；（4）根据市场情况，限定C不超过1640件，求相应生产方案；（5）若限定原料甲需剩余至少50公斤，求相应生产方案；（6）若限定生产A至少1000件，生产B至少200件，求相应生产方案。解：模型的建立与求解：(1)设A,B,C,D，E四种产品的生产量分别是1x，2x，3x，4x，5x(单位:件)该问题的目标是使总收入最大,目标函数可简记为maxz=41x+32x+63x+54x+58x约束条件为甲乙丙原料的限额,即:0.11x+0.23x+0.34x+0.15x6000.21x+0.22x+0.13x+0.35x5000.32x+0.24x+0.15x300运用lindo软件求解得:1x=2x=4x=0,3x=2600,5x=800,此时目标函数最大值为22000。即最优生产方案为生产C产品2600件，生产E产品800件，其余产品不生产。（2）目标函数不变，约束条件增加一个，即：1x500运用lindo软件求解得:1x=500，2x=4x=0,3x=2500,5x=500,此时目标函数最大值为21000。即相应生产方案为生产C产品2500件，生产A产品、E产品500件，其余产品不生产。（3）目标函数变为：maxz=41x+32x+63x+54x约束条件为：0.11x+0.23x+0.34x6000.21x+0.22x+0.13x5000