整数规划模型与应用

整数规划模型与应用

引用

CSDN

1.

https://blog.csdn.net/2302_76671472/article/details/136754890

本文内容整理自《数学建模算法与应用》，主要介绍了整数规划的相关概念、模型建立方法以及实际应用案例。通过具体问题的分析和求解过程，帮助读者理解整数规划的基本原理和应用技巧。

一、整数规划

从决策变量的取值范围来看，整数规划通常可以分为以下几种类型：

1. 纯整数规划：全部决策变量都必须取整数值的整数规划模型；
2. 混合整数规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数规划模型；
3. 0-1整数规划：决策变量只能取0或1的整数规划。

背包问题

一个旅行者外出旅行，携带一背包，装一些最有用的东西，共有n件物品供选择。已知每件物品的“使用价值”Cj和重量aj，要求：

（1）最多携带物品的重量为b kg；
（2）每件物品要么不带，要么只能整件携带。问携带哪些物品使总使用价值最大？

问题分析

这是决策问题中比较经典的规划问题。可选方案很多，决策方案是带什么？选择的方式是要么带，要么不带，是一个二值逻辑问题。

约束条件

（1）重量限制：最多只能携带b kg，即Xi=0或1，i=1，2...n。

二、整数规划模型求解

生产线工人配备问题

为了生产的需要，某工厂的一条生产线需要每天24小时不间断运转，但是每天不同时间段所需要的工人最低数量不同，具体数据如表2.1所示。已知每名工人的连续工作时间为8小时。则该工厂应该为该生产线配备多少名工人，才能保证生产线的正常运转？

问题分析

从降低经营成本的角度来看，为该生产线配备的工人数量越少，工厂所付出的工人薪资之和也就越低。因此，该问题需要确定在每个时间段工作的工人的数量，使其既能满足生产线的生产需求，又能使得雇佣的工人总数最低。

模型假设

（1）每名工人每24小时只能工作8小时；
（2）每名工人只能在某个班次的初始时刻报到。

符号说明

设Xi表示在第i个班次报道的工人数量，i=1，2，...，6。

模型建立

该问题的目标函数为雇佣的工人总数最小。约束条件为安排在不同班次上班的工人数量应该不低于该班次需要的人数，且Xi为非负整数。

计算的Matlab程序如下：

clc, clear, prob = optimproblem;
x = optimvar('x',6,'Type','integer','LowerBound',0);
prob.Objective = sum(x);
con = optimconstr(6);
a = [35,40,50,45,55,30];
con(1) = x(1)+x(6)>=35;
for i =1 :5
    con(i+1) = x(i)+x(i+1)>=a(i+1);
end
prob.Constraints.con = con;
[sol, fval, flag] = solve(prob), sol.x

装修任务分配问题

某连锁超市经营企业为了扩大规模，新租用五个门店，经过装修后再营业。现有四家装饰公司分别对这五个门店的装修费用进行报价，具体数据如表2.2所示。为保证装修质量，规定每个装修公司最多承担两个门店的装修任务。则为节省装修费用，该企业该如何分配装修任务？

问题分析

这是一个非标准（人数和工作不相等）的“指派问题”。解决此类问题就是在满足指派要求的条件下，确定最优的指派方案，使得按该方案实施后的“效益”最佳。可以引入0-1变量来表示某一个装修公司是否承担某一个门店的装修任务。

模型假设

每个门店的装修工作只能由一个装修公司单独完成。

符号说明

模型建立

引入0-1变量

计算的Matlab程序如下：

clc, clear, c = load('data2_6.txt');
prob = optimproblem;
x = optimvar('x',4,5,'Type','integer','LowerBound',0,'UpperBound',1);
prob.Objective = sum(sum(c.*x));
prob.Constraints.con1 = sum(x,1)==1;
prob.Constraints.con2 = sum(x,2)<=2;
[sol, fval, flag] = solve(prob), sol.x

三、比赛项目排序问题

本题选自2005年电工杯数学建模竞赛B题。

在各种运动比赛中，为了使比赛公平、公正、合理地举行，一个基本要求是：在比赛项目排序过程中，尽可能使每个运动员不连续参加两项比赛，以便运动员恢复体力，发挥正常水平。

表2.4所示是某个小型运动会的比赛报名表。有14个比赛项目，40名运动员参加比赛。表中第1行表示14个比赛项目，第1列表示40名运动员，表中“#”号位置表示运动员参加此项比赛。建立此问题的数学模型，并且合理安排比赛项目顺序，使连续参加两项比赛的运动员人次尽可能地少。

表2.4 某小型运动会的比赛报名表

则问题转化为求项目1到项目14的一个排列，使相邻顶点之间的权重之和最小。我们采用TSP（旅行商）问题求解，但由于开始项目和结束项目没有连接，可考虑引入虚拟项目15，该虚拟项目与各个项目的连接权重都为0。

clc, clear, a = importdata('data2_10.xlsx'); 
a(isnan(a))=0; %把不确定值NaN替换为0
M=10^7; w=ones(14)*M;
for i=1:14
    for j=1:14
        if i~=j, w(i,j)=sum(a(:,i).*a(:,j)); end
    end
end
n=15; w(n,n)=M; prob=optimproblem; 
x=optimvar('x',n,n,'Type','integer','LowerBound',0,'UpperBound',1);
u=optimvar('u',n,'LowerBound',0)  %序号变量
prob.Objective=sum(sum(w.*x));
prob.Constraints.con1=[sum(x,2)==1; sum(x,1)'==1; u(1)==0];
con2 = [1<=u(2:end); u(2:end)<=14];
for i=1:n
    for j=2:n
        con2 =[con2; u(i)-u(j)+n*x(i,j)<=n-1];
    end
end
prob.Constraints.con2 = con2;
[sol, fval, flag]=solve(prob)
xx=sol.x; [i,j]=find(xx); 
fprintf('xij=1对应的行列位置如下：\n')
ij=[i'; j']