运筹说第60期 | 0-1型整数规划和指派问题 _系数

通过前两期的学习，我们已经学会了整数规划问题的数学模型、割平面法和分支定界法。本期小编带大家学习0-1整数问题和指派问题。
一 0-1整数规划 01定义
0-1型整数规划是整数规划的一种特殊形式，它的变量xj仅取值0或1 。这种只能取0或1的变量称为0-1变量或二进制变量。例如
当问题含有多项限制要素E1,E2,…,En，其中每项都有两种选择时，可令
若遇到变量可以取多个整数值时，可以用一组0-1变量取代该变量。例如，变量x可取0与9之间的任意整数时，可令
其中， x0，x1，x2，x3皆为0-1变量。
02应用
案例1 含有互斥约束条件的问题
案例2 固定费用问题
案例3 工件排序问题
03解法
对于0-1型整数规划，一般采用隐枚举法，而不必采用完全枚举法：
1、只要发现某个变量组合不满足其中一个约束条件时，就不必再去检验其他约束条件是否可行。
2、若已发现一个可行解，则可根据它的目标函数值产生一个过滤条件，对于目标函数值比它差的变量组合就不必再去检验它的可行性；在以后的求解中，每当发现更好的可行解，则以此替换原来的过滤条件。
【运筹说第60期 | 0-1型整数规划和指派问题】案例4
二指派问题 01数学模型
02 匈牙利解法
1955年，库恩利用匈牙利数学家康尼格的关于矩阵中独立零元素的定理，提出了解指派问题的一种算法，称为匈牙利解法。

运筹说 第60期 | 0-1型整数规划和指派问题

运筹说第60期 | 0-1型整数规划和指派问题