整数规划 Integer Linear Programming

有一些问题是没办法用小数的，例如一个任务不能由4.7个人完成。
生产瓶子不能生产100.6个瓶子。

整数线性规划（ILP）

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

运量要小于生产能力
运量要大于销量

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

松弛变量：x1+x2<=10 变为x1+x2+x3=10,加个约束条件x3>=0,x3是松弛变量
剩余变量：x1+x2>=10 变为x1+x2-x3=10,加个约束条件x3<=0，-x3是剩余松弛变量与不等式变量将不等式约束转化等式约束
0-1整数：适用于流程性规划，只能干一件事，例如任务的安排，运动员完成跑步

在这里插入图片描述
在这里插入图片描述

ILP(整数规划 Integer Linear Programming)规划是松弛的线性规划的网格点

在这里插入图片描述

分支定界算法求解整数规划

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

整数的数量比较少

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

割平面算法求解

在这里插入图片描述

通过切割平面

在这里插入图片描述

引入了松弛变量x3 x4

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

匈牙利算法

在这里插入图片描述

M取无穷大

在这里插入图片描述
在这里插入图片描述

M取无穷大，x1是产品数，当y取0，无法生产 产品。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

可以搜索运筹学的匈牙利算法

在这里插入图片描述

# 动态规划 # 线性代数 # 算法
Logo
DAMO开发者矩阵

DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐

cover

KingbaseES数据库：医疗信创潮涌沅江，国产化信创打造医疗新质生产力

avatar DAMO开发者矩阵
cover

告别迁移焦虑：金仓KDMS V4带你轻松搞定数据库国产化替代

avatar DAMO开发者矩阵
cover

KingbaseES数据库在常德二院全栈国产化信创中产生新质生产力,医疗信创的部署如何实现，如何操作？

avatar DAMO开发者矩阵