整数规划
定义:
若线性规划最优解可取整:
线性规划在整数规划中最优解全部都是整数,那么整数规划和线性规划的结果是相互一致的。
线性规划在整数规划中没有可行解。
线性规划在整数规划中存在可行解,但是最优解值变差。
分类:
纯整数规划(完全整数) 混合整数规划(部分整数) 0-1规划(所有决策变量只取0,1)
分支定界法 (纯,混), 割平面法(纯,混) 隐枚举法(求0-1规划,分为过滤法 分枝法)
匈牙利法(指派问题 0-1规划特殊情况) 蒙塔卡罗法(各种规划问题)
应用:
电力领域的电网的布局以及分配,仓库运输供应链领域,火车课程飞机安排问题等调度问题,路径优化(GPS)
0-1规划定义:
0-1是特殊的整数规划,决策变量只有0 ,1,也叫二进制变量
约束条件 0<=x<=1 且x为整数\
可以把各种情况统一放在一个问题中讨论(多目标函数变成单目标函数,国赛立体)
例题
某连锁超市经营企业为了扩大规模,新租用五个门店经过装修后再营业。现有四家装饰公司分别对这五个门店的装修费用进行报价,具体数据如表1所示。为保证装修质量规定每个装修公司最多承担两个门店的装修任务。则为节省装修费用,该企业该如何分配装修任务?
1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|
A | 15 | 13.8 | 12.5 | 11 | 14.3 |
B | 14 | 14 | 13.2 | 10.5 | 15 |
C | 13.8 | 13 | 12.8 | 11.3 | 14.6 |
D | 14.7 | 13.6 | 13 | 11.6 | 14 |
一 模型假设
每家店的装修工作只能由一个装修公司单独完成
二 符号说明
假设i=1,2,3,4分别表示A、B、C、D四家装修公司,那么,则表示第c(ij) (i=1,2,3,4) 家装修公司对第j个门店的装修费用报价。
三 模型建立
四 Matlab代码
clc; clear;
% 从 Excel 文件中读取数据 这是我放数据的地方,自己要更换
c = xlsread('C:\Users\lenovo\Desktop\百度网盘下载\连大数学建模\线性规划的整数规划01\工作簿1.xlsx');
% 创建优化问题
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 是求解 fval 是答案最小花费 flag
% 显示解向量
disp(sol.x);
版权声明:本文为博主作者:dddffx1原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/m0_74089897/article/details/134811790