阁笔趣

2整数规划模型（第3页）

xi=1或0

解得：X=（x1，x2，x3，x4，x5，x6）=（0，1，0，1，0，0），Z=2

2。　厂址选择问题

在N个地点中选r个（Nr）建厂，在第i个地点建厂（i=1，2，…，N）所需投资为Ii万元，占地Li亩，建成以后的生产能力为Pi万吨。现在有总投资I万元，土地L亩，应如何选择厂址，使建成后总生产能力最大。

设xi=0表示在i地不建厂

1表示在i地建厂

整数规划模型为

maxz=∑Ni=1Pixi

s。t。∑Ni=1Iixi≤I

∑Ni=1Lixi≤L

∑Ni=1xi≤r

xi=0，1

这是一个0—1规划问题。

3。　考虑固定成本的最小生产费用问题

在最小成本问题中，设第j种设备运行的固定成本为dj，运行的变动成本为cj，则生产成本与设备运行时间的关系为

fj（xj）=0当xj=0

dj+cjxj当xj0

设第j种设备运行每小时可以生产第i种产品aij件，而第i种产品的定货为bi件。要满足定货同时使设备运行的总成本最小的问题为

minz=∑nj=1djyj+cjxj

s。t。∑nj=1aijxj≥bii=1，2，…，m

xj≤Myjj=1，2，…，n

xj≥0，yj=0，1

这里M是一个很大的正数。

当yj=0时，xj=0，即第j种设备不运行，相应的运行成本

djyj+cjxj=0

当yj0时，0≤xj≤M，实际上对xj没有限制，这时相应的运行成本为

dj+cjxj

这是一个混合0—1规划问题

4。　指派问题

例7有n项任务由n个人去完成，每项任务交给一个人，每个人都有一项任务。由第i个人去做第j项任务的成本（或效益）为cij。求使总成本最小（或效益最大）的分配方案。

设：xij=0第i个人不从事第j项任务

1第i个人被指派完成第j项任务

得到以下的线性规划模型：

min（max）z=∑ni=1∑nj=1cijxij

s。t。∑ni=1xij=1j=1，2，…，n

∑nj=1xij=1i=1，2，…，n

xij=0，1

例如，有张、王、李、赵4位教师被分配教语文、数学、物理、化学4门课程，每位教师教一门课程，每门课程由一位老师教。根据这四位教师以往教课的情况，他们分别教这四门课程的平均成绩如下表：

表57

语文数学物理化学