运筹学《第五章-整数规划》.ppt

第五章整数规划;第一节整数规划的数学模型及其解的特点;第一节整数规划的数学模型及其解的特点;第一节整数规划的数学模型及其解的特点;第一节整数规划的数学模型及其解的特点;第一节整数规划的数学模型及其解的特点;第一节整数规划的数学模型及其解的特点;第一节整数规划的数学模型及其解的特点;X1=1,x2=1

X1=0,x2=1

X1=0,x2=0;第一节整数规划的数学模型及其解的特点;X5=0,x6=1,x7=1

X5=1,x6=1,x7=0X5=1,x6=0,x7=1;第一节整数规划的数学模型及其解的特点;;;第一节整数规划的数学模型及其解的特点;第一节整数规划的数学模型及其解的特点;第一节整数规划的数学模型及其解的特点;第一节目标规划问题及其数学模型;第一节目标规划问题及其数学模型;第二节割平面法;第二节割平面法;第二节割平面法;cj;第二节割平面法;第二节割平面法;第二节割平面法;cj;cj;cj;cj;cj;cj;cj;cj;x1=1,x2=2;第三节分支定界法;第三节分支定界法;第三节分支定界法;第三节分支定界法;例7求解;第三节分支定界法;第三节分支定界法;第三节分支定界法;第三节分支定界法;第三节分支定界法;第三节分支定界法;S;S;S;S;A;A;A;A;解：首先不考虑整数约束，相应的问题称为原问题的松驰问题;问题（0）

x1=2.5，x2=2.5z=87.5;分支定界法的步骤;分支定界法的步骤;例8厂址选择问题。

在5个地点中选3处建生产同一产品的工厂，在这5个地点建厂所需投资，占用农田，建成以后的生产能力等数据如下表所示，现在有总投资800万元，占用农田指标60亩，应如何选择厂址，使建成后总生产能力最大。;第四节0-1型整数规划;例9含有相互排斥的约束条件的问题。

某厂生产A1，A2两种产品，需要经过B1，B2，B3三道工序加工。单件工时和利润以及各个工序每周工时限额见下表，问工厂应如何安排生产，才能使总利润最大？;;B31;假设y1=0;假设y1=0;假设y2=0;假设y2=0;例10固定费用问题

有三种资源被用于生产三种产品，资源量、产品单价可变费用售价、资源单耗量及组织三种产品生产的固定费用见下表,要求制定一个生产方案使总收益最大.;;;;设生产产品I,II,III分别x1,x2,x3件;例11变量之间需要满足一定的逻辑关系的问题

一个工厂用三种设备生产5种产品，三种设备的总能力〔小时〕，生产每种产品需要占用的各种设备的能力〔小时/件〕以及三种产品的利润〔元/件〕如下表所示;;;;;;练习：说明如何用0-1整数变量将以下条件表示为线性约束;练习：说明如何用0-1整数变量将以下条件表示为线性约束;例12求解0-1整数规划;(x1,x2,x3);(x1,x2,x3);例求解0-1整数规划;(x2,x1,x4,x3);(x2,x1,x3);第五节指派问题;第五节指派问题;第五节指派问题;第五节指派问题;第五节指派问题;第五节指派问题;第五节指派问题;第五节指派问题;第五节指派问题;第五节指派问题;第五节指派问题;第五节指派问题;说明:在确定独立零元素过程中，假设遇到在所有的行和列中,零元素都不止一个，可任选其中一个零元素加圈,同时划去同行和同列的其它零元素。;例：有四台机器都可作A、B、C、D四种工作，但所需费用不同，其费用系数矩阵假设下表。为使总费用最小，求最优秀分派方案？;(-1);第五节指派问题;第五节指派问题;第五节指派问题;第五节指派问题;2;练习1:分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每人完成各项任务的时间如下表。由于任务重，人数少，考虑：

a).任务E必须完成，其它4项任务可选3项完成。但甲不能做A项工作。

b)其中有一人完成两项，其他人每人完成一项。

试分别确定最优分配方案，使完成任务的总时间最少。;练习1:分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每人完成各项任务的时间如下表。由于任务重，人数少，考虑：

a).任务E必须完成，其它4项任务可选3项完成。但甲不能做A项工作。

b)其中有一人完成两项，其他人每人完成一项。

试分别确定最优分配方案，使完成任务的总时间最少。;练习2:某城市可划分为11个防火区,已设有4个消防站,如以下图,图中虚线表示该消防站可以在消防允许时间内到达该地区进行有效的消防灭火.问能否关闭假设干消防站,但仍不影响任何一个防火区的消防救灾工作.;1;用隐枚举法解得X=〔1011〕T

可以关闭消防站2