[管理学]管理运筹学 第一章_线性规划.ppt

二、 0-1整数规划 投资场所的选址问题 指派问题 背包问题 消防队问题 1. 投资场所的选址问题 某城市拟在东、西、南三区设立商业网点，备选位置有A1~A7共7个，如果选Ai，估计投资为bi元，利润为ci元，要求总投资不超过B元，规定 东区：A1、A2、A3中至多选2个 西区：A4、A5中至少选一个 南区：A6、A7中至少选一个 问如何设点使总利润最大？ 1， Ai被选中 0， Ai没被选中 解：令 xi= max z= xi=0或 1，i=1, … ,7 ∑ bixi≤B i=1 7 x1+x2+x3≤2 x4+x5≥1 x6+x7≥1 s.t. 课堂练习1: 某钻井队要从S1~S10共10个井位中确定五个钻井探油，如果选Si，估计钻探费用为ci元，并且井位选择上要满足下列条件： （1）或选择S1和S7，或选择S8 ; （2）选择了S3或S4就不能选择S5，反 过来也一样; （3）在S5，S6 ，S7，S8中最多只能选两个。 问如何选择井位使总费用最小？ 课堂练习1: 某钻井队要从S1~S10共10个井位中确定五个钻井探油，如果选Si，估计钻探费用为ci元，并且井位选择上要满足下列条件： （1）或选择S1和S7，或选择S8 （2）选择了S3或S4就不能选择S5，反过来也一样 （3）在S5，S6 ，S7，S8中最多只能选两个 问如何选择井位使总费用最小？ 1， Si被选中 0， Si没被选中 解：令 xi= min z= s.t. 或 1，i=1, … ,10 某篮球队有8名队员，其身高和专长如下表，现要选拔5名球员上场参赛，要求： （1）中锋只有1人上场 （2）后卫至少有一人上场 （3）只有2号上场，6号才上场 要求平均身高最高，应如何选拔队员？ 课堂练习2: 1， 队员i被选中 0，队员i没被选中 解：令 xi= max z= 或 1，i=1, … ,8 s.t. 某篮球队有8名队员，其身高和专长如下表，现要选拔5名球员上场参赛，要求： （1）中锋只有1人上场 （2）后卫至少有一人上场 （3）只有2号上场，6号才上场 要求平均身高最高，应如何选拔队员？ 2. 指派问题 例： 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作任务E、J、G、R，现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种说明书所需的时间如下表所示，问应指派何人去完成何项任务，使所需总时间最少？ 问题描述：n项任务可由n个人完成，由于专长不同，各人完成各任务的时间也不同，求最优安排。 要求：每人只能完成一项任务，每项任务只能由一人完成。 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 ( E任务只能一人干) x12+ x22+ x32+ x42= 1 ( J任务只能一人干) x13+ x23+ x33+ x43= 1 ( G任务只能一人干) x14+ x24+ x34+ x44= 1 ( R任务只能一人干) xij = 0 或 1，i,j = 1,2,3,4 min z=2x11+15x12+13x13+4x14+10x21+4x22+14x23+15x24 +9x31+14x32+16x33+13x34+7x41 +8x42+11x43+9x44 1， 指派第i人去完成第j项任务