第4章 数学规划模型
4.1 某饲养场用n种原料配合成饲料喂鸡,为了让鸡生长得快,对m种营养成分有一个最低标准。即对i?1,?,m,要求第种i营养成分在饲料中的含量不少于bi,若每单位第j种原料
中含第i种营养成分的量为aij,第j种原料的单价为cj,问应如何配制饲料才能使成本最低? 解:
模型假设:假设bi为每单位饲料中营养成分的最少含量
假设aij每单位第j种原料中第i种营养成分的百分比 模型的建立:
设xj为每单位饲料中第j种原料的含量,其中j?1,?,n 由已知,目标函数为minz?n?cxjj?1nj
约束条件为:
?axijj?1j?bi i?1,?,m
甲、 干 且 各 右 才 少。
4.2拟分配
工作 乙、丙、丁四人去1 2 3 4 工人 四项工作,每人干
甲 10 9 7 8 仅干一项。他们干
乙 5 8 7 7 项工作需用天数见
丙 5 4 6 5 表,问应如何分配
丁 2 3 4 5 能使总用工天数最
解:
模型的建立与求解:
记i=1,2,3,4分别表示甲乙丙丁四人,j=1,2,3,4分别表示工作1 2 3 4, 用aij表示i人干工作j。
aij 1 2 3 4
1 10 5 5 2 2 9 8 4 3 3 7 7 6 4 4 8 7 5 5 引入0-1变量xij,若i人干j工作,则xij=1,否则xij=0。
根据题目要求,四人干四项工作,每人干且仅干一项,可得以下约束条件: (1)
? xi?14ij=1 (2)
?xj?14ij=1
当第i人干第j项工作时,aijxij表示所用天数,否则aijxij=0,所以甲乙丙丁分工干各项工作的总用工天数为
??axi?1j?144ijij,也即该问题的目标函数。
综上,这个问题的0-1规划模型可写作: min z=
??axi?1j?1ij44ijij
s.t.
? xi?14=1 j=1,2,3,4
?xj?14ij=1 i=1,2,3,4
xij={0,1}
程序:
将题目所给数据带入上述模型,并输入lindo: min 10x11+9x12+7x13+8x14 +5x21+8x22+7x23+7x24 +5x31+4x32+6x33+5x34 +2x41+3x42+4x43+5x44 s.t.
x11+x12+x13+x14=1 x21+x22+x23+x24=1 x31+x32+x33+x34=1 x41+x42+x43+x44=1 x11+x21+x31+x41=1 x12+x22+x32+x42=1 x13+x23+x33+x43=1 x14+x24+x34+x44=1 end int16
计算结果为:x13=x21=x34=x42=1,其余全为0,即甲做第三项工作,乙做第一项工作,丙做第四项工作,丁做第二项工作,最少用工天数为20天。
4.3 某校经预赛选出A,B,C,D四名学生,将派他们去参加该地区各学校之间的竞赛。此次竞赛的四门功课考试在同一时间进行,因而每人只能参加一门,比赛结果将以团体总分计名次(不计个人名次)。设下表是四名学生选拔时的成绩,问应如何组队较好?
课程 数学 物理 化学 外语
学生
90 95 78 83 A
85 89 73 80 B
93 91 88 79 C
79 85 84 87 D 解:
模型的建立与求解:
记i=1,2,3,4分别表示A、B、C、D四名学生,j=1,2,3,4分别表示数学、物理、化学、外语, 用aij表示i同学参加j功课考试。
aij 1 2 3 4
1 90 85 93 79 2 95 89 91 85 3 78 73 88 84 4 83 80 79 87 引入0-1变量xij,若i同学参加 j功课考试,则xij=1,否则xij=0。
根据题目要求,每人只能参加一门考试,且以团体总分计名次,不计个人名次,可得以下约束条件:
(1)
? xi?14ij=1 (2)
?xj?14ij=1
当第i同学参加第j功课考试时,aijxij表示所得成绩,否则aijxij=0,所以A B C D分别参加各门功课考试的总成绩为
??axi?1j?144ijij,也即该问题的目标函数。
综上,这个问题的0-1规划模型可写作: max z=
??axi?1j?1ij44ijij
s.t.
? xi?14=1 j=1,2,3,4
?xj?14ij=1 i=1,2,3,4
xij={0,1}
程序:
将题目所给数据带入上述模型,并输入lindo: max 90x11+95x12+78x13+83x14 +85x21+89x22+73x23+80x24 +93x31+91x32+88x33+79x34 +79x41+85x42+84x43+87x44 s.t.
x11+x12+x13+x14=1 x21+x22+x23+x24=1 x31+x32+x33+x34=1 x41+x42+x43+x44=1 x11+x21+x31+x41=1 x12+x22+x32+x42=1 x13+x23+x33+x43=1 x14+x24+x34+x44=1 end int16
计算结果为:x12=x21=x33=x44=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根,若原料充分多,在完成任务的前提下,应如何截切,使得留下的余料最少? 解:
模型的建立与求解:
材料的切割模式有如下: 模式 1 2 3 4 5 6 78cm 6 5 3 2 1 0 98cm 0 1 2 3 4 5 余料 32 12 70 50 30 10 设按第i种模式切割的线材个数为xi,i=1,2,3,4,5,6
相关推荐: