整数规划 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

当 AI 面试官走进沉浸式空间：面境背后的端到端具身交互智能实战手记

avatar DAMO开发者矩阵
cover

学了十年英语还是开不了口？端到端具身交互智能口语教练让你真正开口说

avatar DAMO开发者矩阵
cover

微信API如何设计群聊冷却机制？WechatApi 防止微信群机器人频繁刷屏的工程方案

avatar DAMO开发者矩阵