数学建模——整数规划

这篇具有很好参考价值的文章主要介绍了数学建模——整数规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

基本概念

整数规划模型求解

整数线性规划模型求解

蒙特卡洛求解 

遗传算法求解 

 其他


基本概念

一部分或全部决策变量必须取整数值的规划问题称为整数规划

纯整数规划:全部决策变量都为整数;混合整数规划:决策变量有一部分是整数值,另一部分不是整数;0-1整数规划:决策变量只能取0或1的整数规划。

整数线性规划模型(一个线性规划模型中的部分或全部决策变量为整数)一般形式:

整数规划模型,数学建模,算法

有时,也可以通过引入0-1变量将一些特定的非线性约束条件进行线性化。如果有m个相互排斥的约束条件,即同一时间只能有一个条件起作用,则引入m个0-1变量:

整数规划模型,数学建模,算法

和一个充分大的正常数M,则下面这一组m+1个约束条件就合于上述要求:

整数规划模型,数学建模,算法

整数规划模型求解

整数线性规划模型求解

例如求解如下整数规划:

整数规划模型,数学建模,算法

整数规划模型,数学建模,算法

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,fval

ans =

    35
     5
    45
     0
    55
     0
fval =

   140

 也能这样编:

整数规划模型,数学建模,算法

蒙特卡洛求解 

蒙特卡洛法也称为计算机模拟法,类似于在一个已知面积的正方形区域内,求其包围的不规则图形的面积,撒数目很大的豆子,根据豆子的数目比例,求得面积。

unifrnd(A,B)%生成被A和B指定上下端点[A,B]的连续均匀分布的随机数组R。

R = unifrnd(A,B,m,n,...)

R = unifrnd(A,B,[m,n,...])%返回m*n*...数组

rng(1)%1作为随机数种子,为了进行一致性的比较。

rng('shuffle')%根据当前时间为随机数生成器提供种子。

tic%计时开始

toc%计时结束

B = all(A)%如果A是二维的,列数为n,则B为一个1*n的矩阵。如果A中某一列的元素全为真,则B中对应元素为1。如果A是三维的,则B的列数、页数和A相同,B的行数为1。高于三维的情况可以以此类推。

例如求解非线性整数规划:x均为整数

整数规划模型,数学建模,算法

clc,clear
rng(0);
p0 = 0;
n = 10^6;
tic;
for i = 1:n
    x = randi([0,99],1,5);
    [f,g] = mente(x);
    if all(g <= 0)
        if p0 <f
            x0 = x;p0 = f;
        end
    end
end
x0,p0,toc

function [f,g] = mente(x)
f = x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)^2-8*x(1)-2*x(2)...
    -3*x(3)-x(4)-2*x(5);
g = [sum(x)-400
    x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800
    2*x(1)+x(2)+6*x(3)-200
    x(3)+x(4)+5*x(5)-200];
end

x0 =

    46    98     1    99     3
p0 =

       50273

历时 0.927967 秒。

遗传算法求解 

整数规划模型,数学建模,算法

 fun是目标函数(只能最小值),nvars表示变量个数,A、b线性不等号约束,Aeq、beq线性等号约束,lb、ub表示上下界,nonlcon表示非线性约束,intcon指明哪些变量是整数变量,options用来指明其他一些优化设置。

还采用上面那个例子:

clc,clear
f = @(x) x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)^2-8*x(1)-2*x(2)...
    -3*x(3)-x(4)-2*x(5);
A = [1,1,1,1,1;
    1,2,2,1,6;
    2,1,6,0,0;
    0,0,1,1,5];
b = [400;800;200;200];
[x,fvdisc] = ga(@(x)-f(x),5,A,b,[],[],zeros(1,5),99*ones(1,5),[],[1:5])

 @(x)-f(x)表示又定义一个匿名函数是-f(x)

x =

    50    99     0    99    20
fvdisc =

      -51568 

 其他

解决实际问题经过:问题分析、模型假设、符号说明、模型建立。

MATLAB中一行太长可以使用"..."来换行文章来源地址https://www.toymoban.com/news/detail-732291.html

到了这里,关于数学建模——整数规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • OLS回归模型-斯皮尔曼相关系数-数值模拟-多目标规划-养老服务床位需求预测与运营模式研究-之数学建模

    数学建模 -OLS回归模型 斯皮尔曼相关系数 数值模拟 多目标规划-养老服务床位需求预测与运营模式研究 养老服务床位需求预测与运营模式研究 摘要         随着时间的推移,我国人口老龄化逐渐增多,老龄化的社会问题越来越突出,从2009年到2018年,无论是老年人口数量

    2024年02月09日
    浏览(47)
  • 数学建模十大算法03—线性规划、整数规划、非线性规划、多目标规划

    一、线性规划(Linear Programming,LP) 1.1 引例 在人们的生产实践中,经常会遇到 如何利用现有资源来安排生产,以取得最大经济效益的问题。 此类问题构成了运筹学的一个重要分支一数学规划,而 线性规划(Linear Programming, LP) 则是数学规划的一个重要分支。 简而言之,线

    2024年02月13日
    浏览(46)
  • 数学建模笔记——整数规划类问题之我见(匈牙利算法)

    目录 浅浅叙述匈牙利算法 基本思路 计算步骤 来一道简单例题 1.1 符号规定 1.2目标函数​编辑       1.3约束条件 ​编辑 1.4代码 题目复述 基本假设 问题分析 符号说明  模型的建立与求解 模型建立思路 模型建立的过程 建立0-1整数规划模型  运用匈牙利方法: 代码实现  

    2023年04月11日
    浏览(50)
  • 数学模型之整数规划(0-1规划)

    常见的规划问题大体四类 1.线性规划 2.非线性规划 3.整数规划 (0 1规划) 4.动态规划 提示: 规划中的变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中, 变量限制为整数,则称为整数线性规划。目前所流行的求解整数规划的方法,往往只适 用于整数

    2024年01月19日
    浏览(38)
  • Matlab数学建模算法详解之混合整数线性规划 (MILP) 算法(附完整实现代码)

    🔗 运行环境:Matlab 🚩 撰写作者:左手の明天 🥇 精选专栏:《python》 🔥  推荐专栏:《算法研究》 ####  防伪水印—— 左手の明天 #### 💗 大家好🤗🤗🤗,我是 左手の明天 !好久不见💗 💗今天分享matlab数学建模算法—— 混合整数线性规划 (MILP) 算法 💗

    2024年02月04日
    浏览(52)
  • 数学建模基础算法Chapter2.1 -- 整数规划(ILP): 分支定界+割平面

    By 进栈需检票 当题目要求的最优解是整数,例如物件的数量,参与人员的数量等时,就不能继续使用之前的线性规划了(当出现小数的情况),这个时候需考虑整数规划这样的一种建模形式 但是目前所流行的求整数规划的方法,只适用于整数线性规划,不能解决一切的整数

    2024年02月12日
    浏览(54)
  • 数学建模之整数规划

    1 定义 数学规划中,变量部分或全部限制为整数,叫整数规划。 线性规划中,变量全是整数,叫整数线性规划。 2 分类 依据是否变量全为整数,分为完全整数规划和混合整数规划。 依据决策变量要求,分为纯整数,混合整数,全整数以及0-1规划。  注:1)松弛变量和剩余

    2024年02月12日
    浏览(49)
  • 数学建模(三)整数规划

    视频推荐:B站_数学建模老哥 目录 一、整数规划基本原理 1.1 整数规划的分类 1.2 整数规划的特点 1.3 案例 1.4  整数规划的数学模型一般形式 二、整数线性规划的求解方法 2.1 分枝定界法 2.1.1 分枝定界法的求解过程 2.1.2 案例 2.1.3 代码实现 2.2 割平面法 2.2.1 割平面法的基本思

    2024年02月12日
    浏览(41)
  • 数学建模——整数规划

    目录 基本概念 整数规划模型求解 整数线性规划模型求解 蒙特卡洛求解  遗传算法求解   其他 一部分或全部决策变量必须取整数值的规划问题称为 整数规划 。 纯整数规划:全部决策变量都为整数;混合整数规划:决策变量有一部分是整数值,另一部分不是整数;0-1整数规

    2024年02月07日
    浏览(51)
  • 数学建模——整数规划(0-1规划)问题

    题目:现拟将录用的8名公务员安排到所属的7个部门,并且要求每个部门至少安排一名公员。 x招聘领导小组在确定录用名单的过程中,本着公平、公开的原则,同时考虑录用人员的合理分配和使用,有利于发挥个人的特长和能力。招聘领导小组将7个用人单位的基本情况(包

    2023年04月17日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包