整数规划方法x

主要内容整数规划方法12023年2月4日整数规划的一般模型；整数规划解的求解方法；整数规划的软件求解方法；

0-1规划的模型与求解方法；整数规划的应用案例分析。

如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量.

小型中型大型现有量钢材（t）1.535600劳动时间（h）28025040060000利润（万元）234

制订月生产计划，使工厂的利润最大.引例汽车生产计划设每月生产小、中、大型汽车的数量分别为x1,x2,x3汽车厂生产计划模型建立

小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)模型求解

3）模型中增加条件：x1,x2,x3

均为整数，重新求解.

ObjectiveValue:632.2581VariableValueReducedCost

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237RowSlackorSurplusDualPrice20.0000000.73118330.0000000.003226结果为小数，怎么办？1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大.2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解.

但必须检验它们是否满足约束条件.为什么？IP可用LINGO直接求解整数规划(IntegerProgramming,简记IP)IP的最优解x1=64，x2=168，x3=0，最优值z=632

Globaloptimalsolutionfound.

Objectivevalue:632.0000Extendedsolversteps:0Totalsolveriterations:3VariableValueReducedCost

X164.00000-2.000000

X2168.0000-3.000000

X30.000000-4.000000模型求解

IP结果输出IP模型LINGO求解Model：max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;@gin(x1);@gin(x2);@gin(x3);end其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：方法1：分解为8个LP子模型汽车厂生产计划

若生产某类汽车，则至少生产80辆，求生产计划.x1,x2,,x3=0或80x1=80，x2=150，x3=0，最优值z=610LINGO中对0-1变量的限定：@bin(y1);@bin(y2);@bin(y3);方法2：引入0-1变量，化为整数规划

M为大的正数,本例可取1000ObjectiveValue:610.0000VariableValueReducedCost

X180.000000-2.000000

X2150.000000-3.000000

X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000

若生产某类汽车，则至少生产80辆，求生产计划.x1=0或

80x2=0或

80x3=0或

80最优解同前

IP模型LINGO求解Model：max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;x1<1000*y1;x1>80*y1;%取M=1000x2<1000*y2;x2>80*y2;x2<1000*y2;x2>80*y2;@gin(x1);@gin(x2);@gin(x3);%整数约束@bin(y1);@bin(y2);@bin(y3);%0-1变量end102023年2月4日2.整数规划模型的一般形式

一、整数规划的一般模型问题是如何求解整数规划问题呢？能否设想先略去决策变量整数约束，即变为线性规划问题求解，再对其最优解进行取整处理呢？实际上，可借鉴这种思想来解决整数规划问题．112023年2月4日1.整数规划求解的总基本思想

二、整数规划求解方法整数规划模型示例122023年2月4日固定资源分配问题问题分析与准备

固定资源分配问题资源B1…Bj…Bm车间A1利润：r11……………Ai……rij………An…………rnm价格a1…aj…am总量X1…Xj…Xm

目标总利润各车间、各资源利润资源分配量决策变量142023年2月4日

固定资源分配问题

3、整数规划的LINGO解法二、整数规划的求解方法152023年2月4日162023年2月4日

1、0-1整数规划的模型三、0-1整数规划172023年2月4日

2、指派（或分配）问题三、0-1整数规划

在生产管理上，总希望把人员最佳分派，以发挥其最大工作效率，创造最大的价值。例如：某部门有n项任务，正好需要n个人去完成，由于任务的性质和各人的专长不同，如果分配每个人仅能完成一项任务。如何分派使完成n项任务的总效益为最高（效益量化），这是典型的分配问题。2.指派（或分配）问题182023年2月4日

现在不妨设有4个人，各有能力去完成4项科研任务中的任一项，由于4个人的能力和经验不同，所需完成各项任务的时间如右表：问如何分配何人去完成何项目使完成4项任务所需总时间最少？192023年2月4日2.指派（或分配）问题202023年2月4日2.指派（或分配）问题212023年2月4日2.指派（或分配）问题222023年2月4日2.指派（或分配）问题指派问题的一般模型：232023年2月4日2.指派（或分配）问题指派问题的一般模型：242023年2月4日

匈牙利算法的基本思想

因为每个指派问题都有一个相应的效益矩阵，通过初等变换修改效益矩阵的行或列，使得在每一行或列中至少有一个零元素，直到在不同行不同列中都至少有一个零元素为止。从而得到与这些零元素相对应的一个完全分配方案，这个方案对原问题而言是一个最优的分配方案。3.指派问题的匈牙利算法252023年2月4日

用LINGO求解0-1规划模型4、0-1规划的LINGO解法262023年2月4日四、案例分析:兼职值班员问题

1.问题的提出272023年2月4日实验室开放时间为上午8:00至晚上10:00;开放时间内须有且仅有一名学生值班;规定大学生每周值班不少于8小时;研究生每周值班不少于7小时;每名学生每周值班不超3次;每次值班不少于2小时;每天安排值班的学生不超过3人，且其中必须有一名研究生.试为该实验室安排一张人员的值班表，使总支付的报酬这最少。四、案例分析:兼职值班员问题

1.问题的提出282023年2月4日四、案例分析:兼职值班员问题问题的分析目标总报酬每人报酬每人值班时长每人每天值班时长值班时刻表292023年2月4日四、案例分析:兼职值班员问题

2.模型的建立与求解302023年2月4日四、案例分析:兼职值班员问题目标总报酬每人报酬每人值班时长每人每天值班时长值班时刻表312023年2月4日四、案例分析:兼职值班员问题实验室开放时间为上午8:00至晚上10:00;开放时间内须有且仅有一名学生值班;322023年2月4日四、案例分析:兼职值班员问题规定大学生每周值班不少于8小时;332023年2月4日四、案例分析:兼职值班员问题研