第4章 数学规划模型

第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