《线性整数规划》由会员分享，可在线阅读，更多相关《线性整数规划（28页珍藏版）》请在金锄头文库上搜索。
1、2.5 线性整数规划一.定义：变量部分或全部取整数的规划问题，称为整 数规划。二.分类：纯整数规划全部变量为整数混合整数规划部分变量为整数0-1整数规划变量只取0和1两个值三.0-1变量及其应用1.0-1变量用于选择问题例：某集团公司拟在市内7个预选地址中选建若干门 市部，若令 Xi=1第i个预选地址被选中0第i个预选地址未被选中(i=1,2,7)（1）2，3，5号地址最多选中2个：（2）4，7号地址中只能而且必须选中1个：（3）选地址1，必选地址2：（4）选地址3或4，就不能选地址5：（5）选地址3、4，就不能选地址5：2.0-1变量用于表示约束条件 （1）m个约束条件中只有k个起作用设约束
2、条件：M为任意大的正数则表示成（2）若k个约束条件的右端项是b1,b2,br中的一个则可表示成：（3）两组条件中满足其一如：M为任意大的正数则表示成：（4）变量x只能取值0，3，5，7中的一个例1 某服务部门（每2小时为一时段，服务员连续8小 时为一班）时段12345678 服务员最少数目10891113853问：如何安排，用服务员总数最少？解：设在第j 时段开始时上班的服务员人数为xj(j=15)则数学模型为：例2 运输问题销 产B1B2B3B4产量A1400A2600A3200A4200销量3504003001501400 1200A3或A4开工后每年的生产费用估计分别为1200万元 或1
3、500万元，A3、A4必选其一建产地，问综合考虑 建哪个厂较好。解：令xij表示Ai到Bj的运量则：数学模型为：例3 固定费用问题某工厂为生产某种产品，有3种不同的生产方式可供 选择。设第j种生产方式的固定成本为k；可变成本为 Cj，若不考虑其他约束，请建立使总成本最小的规划 模型。令采用第j种生产方式时的产量为xj则使用第j种方式时的总成本为：若设则总费用初步建模为：注：为保持z为线性函数，yj加在固定成本上。在上述 模型中，xj=0,则yj=0，由极小化目标值可实现；但 xj0，则yj=1并未保证。因此上述模型应加入一个约 束：例4 指派问题：某公司在各地有4项任务，选定了4位业务员分别处
4、理 。由于业务能力、经验和其他情况的不同，4位业务 员处理这4项任务的费用（单位：百元）各不相同。 应当怎样分派任务，才能使总的业务费最少？业务费用 业务员1 2 3 4123411 8 10 76 5 3 84 8 10 911 10 5 7设（cij第i位业务员处理第j项业 务的费用）（每人只做一项工作）（每项工作只由一人去做）四.指派问题的求解方法1.指派问题的标准形式及其数学模型 问题：n个人做n项工作，每人做一项，每项由一人做 ，如何指派，总效率最高（耗时最小）？最小指派 问题。效率矩阵：其中：cij第i人做第j项工作耗时令模型：2.匈牙利解法（1）性质1）效率矩阵某行或列+同一数，
5、其最优解不变。-2-1 -12）效率矩阵中独立的0的个数=覆盖全部0的最少直 线数。用4条直线，独立0有3个用3条直线=独立0个数（2）计算步骤：1）每行减其最小元素，每列减其最小元素；2）确定独立0元素。从第一行开始，若该行只有一个0元素，就对其划 ，对划 的0元素所在列画一条直线；若该行无0元素 或有2个以上0元素（已划去的不计在内），则转下一 行，依次进行到最后一行。同理，再对列作同样的处理。3）重复步骤2），结果可能出现：1有位于不同行，不同列0元素找到最优解2独立0元素个数少于矩阵阶数。处理方法：a）从矩阵中未被直线覆盖的数字中找出一个最小的 数k；b）未被直线覆盖的行中各元素-k被直线覆盖的行中各元素+k；c）重复步骤2，即可求出最优解。（1）人事相等-2-1-1-2-1-1 -1 -1-1+1-1 -1+1X13=x24=x31=x42=1Z0*=c13+c24+c31+c42=11（2）人事不等虚拟人或事，费用系数取0，化成人事相等问题。（3）一人可做几项工作将该人化作相同的几个人，来接受指派，费用不变 ，化成人事相等问题。第二人做两项工作（4）某事一定不能由某人来做第一人不能做第三项工作第三人不能做第四项工作（M为任意大的正数）（5）最大指派问题转化为最小指派问题最优解不变。Cij=10-cij
