运筹说第62期 | 算法介绍之整数规划（二）

2022-05-24 17:15 作者:运筹说 0人读过 | 我要投稿

本期我们继续进行运筹学之整数规划算法的讲解，我们将对整数规划的基础知识进行一个简单的回顾，并介绍求解隐枚举法和指派问题的MATLAB和Python相关代码，以帮助大家利用工具快速求解整数规划问题，做到事半功倍。由于篇幅有限，小编接下来只展示部分代码，小伙伴们可以关注“运筹说”公众号→后台回复“隐枚举法之MATLAB”、“隐枚举之Python”、“指派问题之MATLAB”、“指派问题之Python”分别获取对应的完整代码。话不多说，我们一起来看看吧！

一、基础知识

1、隐枚举法

★ 0-1型整数规划

0-1型整数规划是整数规划的一种特殊形式，它的变量 $x_%7Bj%7D$ 仅取值 0 或 1。这种只能取 0 或1 的变量称为0-1变量或二进制变量。例如：

当问题含有多项限制要素 $E_%7B1%7D%2CE%7B2%7D%2C...%2CE_%7Bn%7D$ ，其中每项都有两种选择时，可令

0-1型整数规划是一种特殊的整数规划,若含有 n 个变量,则可以产生 $2%5E%7Bn%7D$ 个可能的变量组合。当 n 较大时,采用完全枚举法解题几乎是不可能的。已有的求解0-1型整数规划的方法一般都属于隐枚举法。

★ 基本思路

求解0-1规划的隐枚举法的基本思路是从所有变量等于零出发，依次指定一些变量为 1，直至得到一个可行解，并将它作为最好的可行解。此后，依次检查变量等于 0 或 1 的变量组合，每当发现比原来更好的可行解，则进行改进，最终获得最优解。

隐枚举法不同于穷举法，它不需要将所有可行的变量一一列举，它通过分析、判断排除了许多变量组合作为最优解的可能性。

★ 求解流程

2、匈牙利法

★ 指派问题的标准形式

指派问题的标准形式是：有 n 项任务，恰好n个人承担，第 i 人完成第 j 项任务的花费(时间或费用等)为 $c_%7Bij%7D$ ，要求确定人和事之间的一一对应的指派方案，使总花费最省。

指派问题的系数矩阵如下：

为建立标准指派问题的数学模型，引入n × n个0-1变量：

指派问题的数学模型可写成如下形式：

其中，约束条件（a）表示每件事必有且只有一个人做，约束条件（b）表示每个人必做且只做一件事。指派问题有 $n!$ 个可行解。求解指派问题的方法是匈牙利法。

★ 基本思路

匈牙利法的关键是利用了指派问题最优解的一个性质：若从系数矩阵的行(列)各元素中分别减去该行(列)的最小元素,得到新矩阵，那么以新矩阵为系数矩阵求得的最优解和用原矩阵求得的最优解相同。利用这个性质,可使原系数矩阵变换为含有很多0元素的新矩阵，而最优解保持不变。

★ 求解流程

二、算法实现

1、隐枚举法

（1）例题介绍

求解0-1整数规划：

（2）平台实现

我们以上述例题为例，借助MATLAB和Python介绍实现求解“0-1”规划的相关代码。

① MATLAB

★ 代码展示

★ 代码调用

代码调用及最终结果展示如下，最优解 $(x_%7B1%7D%2Cx_%7B2%7D%2Cx_%7B3%7D)%5E%7BT%7D%3D(1%2C0%2C1)%5E%7BT%7D%2Cmax%5C%3Bz%3D8$ 。

★ 注意事项

MATLAB只能求解目标函数的最小值，而例题要求目标函数最大值，所以对目标函数进行了乘以-1处理，最后的结果也要乘以-1才是目标函数所求。

② Python

★ 代码展示

★ 代码调用

代码运行及最终结果展示如下，最优解 $(x_%7B1%7D%2Cx_%7B2%7D%2Cx_%7B3%7D)%5E%7BT%7D%3D(1%2C0%2C1)%5E%7BT%7D%2Cmax%5C%3Bz%3D8$ 。

2、指派问题

（1）例题介绍

某商业公司计划开办5家新商店，决定由5家建筑公司分别承建。已知建筑公司 $A_%7Bi%7D$ （i=1,2,…,5）对新商店 $B_%7Bj%7D$ （j=1,2,…,5）的建造费用的报价（万元） $c_%7Bij%7D$ （i,j=1,2,…,5），如下表。商业公司应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少？

若设0-1变量：

则问题的数学模型为：

（2）平台实现

我们以上述例题为例，借助MATLAB和Python介绍实现求解指派问题的相关代码。

① MATLAB

★ 代码展示

★ 代码调用

代码运行及最终结果展示如下，最优指派方案是让 $A_%7B1%7D$ 承建 $B_%7B3%7D$ ， $A_%7B2%7D$ 承建 $B_%7B2%7D$ ， $A_%7B3%7D$ 承建 $B_%7B1%7D$ ， $A_%7B4%7D$ 承建 $B_%7B4%7D$ ， $A_%7B5%7D$ 承建 $B_%7B5%7D$ ，这样安排能使得总的建造费用最少，为7+9+6+6+6=34（万元）。