格格党

手机浏览器扫描二维码访问

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

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

语文数学物理化学

张92688576

王82917763

李83907465

赵93618375

四位教师每人只能教一门课，每一门课只能由一个教师来教.要确定哪一位教师上哪一门课，使四门课的平均成绩之和为最高.

设xij（i=1，2，3，4；j=1，2，3，4）为第i个教师是否教第j门课，xij只能取值0或1，其意义如下：

xij=0第i个教师不教第j门课

1第i个教师教第j门课

变量xij与教师i以及课程j的关系如下：

表58

j

i语文数学物理化学

张x11x12x13x14

王x21x22x23x24