《运筹学》课件 第5章 整数规划

第五章整数规划线性规划的扩展整数规划IntegerProgrammingIP模糊线性规划fuzzylinearprogramming非线性规划NonlinearProgrammingNP组合优化Combinatorialoptimization图论参数规划多目标规划随机过程stochasticprogramming线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。要求全部或部分决策变量的取值为整数的线性规划问题，称为整数线性规划，简称整数规划(IntegerProgramming)。全部决策变量的取值都为整数，则称为全整数规划(AllIP)；仅要求部分决策变量的取值为整数，则称为混合整数规划(MixedIP)；要求决策变量只能取0或1值，则称为0-1规划(0-1Programming)。第5章内容提要5.1整数规划问题5.2分支定界法5.3指派问题5.40-1规划建模应用5.1整数规划问题为了满足整数要求，似乎可以把线性规划的小数最优解进行“舍入化整”以得到与最优解相近的整数解。“舍入化整”一般是不可行的：化整后的解有可能成为非可行解；虽是可行解，却不是最优解。例如一、问题的提出

产品资源甲乙现有量A219B5735单台利润65

问如何安排甲、乙两产品的产量，使利润为最大。解：设x1为甲产品的台数，x2为乙产品的台数。maxZ=

6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整数不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题。不考虑整数约束的最优解：x1*=28/9，x2*=25/9，Z*=293/9舍入化整x1=3，x2=3，Z=33，不满足约束条件5x1+7x2≤35，非可行解；x1=3，x2=2，Z=28，满足约束条件，是可行解，但不是最优解；x1=4，x2=1，Z=29，满足约束条件，才是最优解。步骤：在线性规划的可行域内列出所有决策变量可能取的整数值，求出这些变量所有可行的整数解，比较它们相应的目标函数值，最优的目标函数值所对应的解就是整数规划的最优解。实用性：只有两个决策变量，可行的整数解较少。

5x1+7x2=352x1+x2=9•(3,3)••••••••••二、整数规划的图解法

x1x21231253445.2分枝定界法分枝定界法(BranchandBoundMethod)基本思想：先求出整数规划相应的LP(即不考虑整数限制)的最优解，若求得的最优解符合整数要求，则是原LP的最优解；若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。然后，再在缩小的可行域中求解新构造的线性规划的最优解，这样通过求解一系列线性规划问题，最终得到原整数规划的最优解。定界的含义：整数规划是在相应的线性规划的基础上增加变量为整数的约束条件，整数规划的最优解不会优于相应线性规划的最优解。对极大化问题来说，相应线性规划的目标函数最优值是原整数规划函数值的上界；对极小化问题来说，相应线性规划的目标函数的最优值是原整数规划目标函数值的下界。例maxZ=

6x1+5x2

2x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整数第一步,不考虑变量的整数约束,求相应LP(问题1)的最优解：

x1=28/9，x2=25/9，Z1=293/9第二步,定界过程这个解不满足整数约束，这时目标函值Z1是整数规划的目标上界；因为x1=x2=0是整数规划问题的可行解，所以下界为0。第三步,分枝过程将不满足整数约束的变量x1进行分枝，x1称为分枝变量，构造两个新的约束条件：

x1≤[28/9]=3，x1≥[28/9]+1=4这样就把相应的线性规划的可行域分成两个部分，如图所示。••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=3x1=4问题2：maxZ=

6x1+5x2问题3：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≥4x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数求解相应的线性规划的最优解问题2相应的线性规划的最优解：x1=3，x2=20/7，Z2=226/7问题3相应的线性规划的最优解：x1=4，x2=1，Z3=29第四步，定界过程LP3的解满足整数约束，不必再分枝，它的目标函数值是29，大于原有下界0，则新的下界为29；现有上界为未分枝子问题中目标函数最大值，即为226/7。LP2的解仍不满足整数约束的要求，它的目标函数值226/7大于现有下界，则应继续分枝。第五步，分枝过程将不满足整数约束的变量x2进行分枝，构造两个新的约束条件：

x2≤[20/7]=2，x2≥[20/7]+1=3

••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3问题4：maxZ=

6x1+5x2问题5：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≤2x2≥3x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数x2=2

x2=3求解相应的线性规划的最优解问题4相应的线性规划的最优解：

x1=3，x2=2，Z4=28问题5相应的线性规划的最优解：x1=14/5，x2=3，Z5=159/5第六步，定界过程LP4的解满足整数约束，不必再分枝，它的目标函数值是28，小于原有下界29，则下界仍为29；现有上界为未分枝子问题中目标函数最大值，即为159/5。LP5的解仍不满足整数约束的要求，它的目标函数值159/5大于现有下界29，则应继续分枝。第七步，分枝过程将不满足整数约束的变量x1进行分枝，构造两个新的约束条件：

x1≤[14/5]=2，x1≥[14/5]+1=3

问题6：maxZ=

6x1+5x2问题7：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≥3x2≥3x1≤2x1≥3x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数x2=2

x2=3••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x1=2求解相应的线性规划的最优解：问题6相应的线性规划的最优解：

x1=2，x2=25/7，Z6=209/7问题7相应的线性规划的最优解：无最优解第八步，定界过程LP7的无最优解，不必再分枝，下界仍为29；现有上界为未分枝子问题中目标函数最大值，即为209/7。LP6的解仍不满足整数约束的要求，它的目标函数值209/7大于现有下界29，则应继续分枝。第九步，分枝过程将不满足整数约束的变量x2进行分枝，构造两个新的约束条件：

x2≤3，x2≥4

问题8：maxZ=

6x1+5x2问题9：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≥3x2≥3x1≤2x1≤2x2≤3x2≥4x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x2=3x1=2x2=2

x2=4求解相应的线性规划的最优解问题8相应的线性规划的最优解：

x1=2，x2=3，Z8=27问题9相应的线性规划的最优解：x1=7/5，x2=4，Z9=142/5第十步，定界过程LP8的最优解，满足整数约束，不必再分枝，下界仍为29；现有上界为未分枝子问题中目标函数最大值，即为29。虽然LP9的解仍不满足整数约束的要求，它的目标函数值142/5小于现有下界29，则不再继续分枝。上界=下界，得整数规划问题的最优解：x1=4，x2=1，Z=29分枝定界过程x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3x2≤3x2≥4割平面法（P109)..X1X2一、指派问题及其标准形式指派问题的标准形式（以人和事为例）：设有个人和件事已知第人做第事的费用为，要求一个人和事之间一一对应的指派方案，使完成这件事的总费用最少。一般称矩阵

为指派问题的系数矩阵（coefficientmatrix）。5.3指派问题为了建立标准指派问题的数学模型，引入个0-1变量

问题的数学模型可写成

二、0－1整数规划应用－－指派问题英日德俄

甲乙丙丁2151341041415914161378119注意到：1从人来看，如果乙不作日语，损失特别大62从事来看，如果英语不分配给甲，损失特别大5英日德俄

甲乙丙丁21513410414159141613781190－1整数规划应用－－指派问题原理：从人的角度思考……..考虑人最适合的工作从工作的角度思考…….考虑工作最适合的人英日德俄

甲乙丙丁

2151341041415914161378119各行都减去这一行的最小值，得到的0表示这个0所在的行对应的人最适合的工作是这个0所在的列对应的事这一列有三个0，表示这一列的事有三个人适合作行最小值英日德俄

甲乙丙丁

01311260101105740142指派问题第一步:{各行元素}—{该行行最小}{各列元素}—{该列列最小}

本题有n个独立的0元素则已得最优解

各列都减去这一列的最小值，得到的0表示这个0所在的列行对应的事最适合的人是这个0所在的行对应的人甲俄乙日丙英丁德英日德俄

甲乙丙丁

0131126010110574014

2英日德俄

甲乙丙丁

0137

060690532010

0列最小值有三个人适合英文为什么确定丙英指派问题的匈牙利法：第一步:{各行元素}—{该行行最小}，{各列元素}—{该列列最小}

若有n个独立的0元素则已得最优解，本题有n个独立的0元素减去行列最小后矩阵英日德俄甲01370第4步行仅1零乙60第2步列仅1零69丙0第1步行仅1零532丁010第3步列仅1零0列仅一个零表示这个工作只适合一个人行仅一个零表示这个人只适合一个工作甲俄乙日丙英丁德颜色表示“确定”三、指派问题的匈牙利法第一步:{各行元素}—{该行行最小}，{各列元素}—{该列列最小}

若有n个独立的0元素则已得最优解，否则转第二步第二步:1，从只有一个0元素的行（列）开始，把0元素记为

，表示“确定”，然后划去所在行（列）的其他0元素，记为0表示“不考虑”

2.划去行（列）的新矩阵再回到:1

3.若仍有没划圈的0元素，且同行（列）至少有两个0元素，则从0元素最少的行（列）开始，试探若

“确定”的数目m等于矩阵的阶n，则最优解得到第三步1对没有

的行打（对应的人没找到合适的工作）

2对已打的行中的所含0的列打（没找到工作的人最适合的工作）

3

对打的列中的所含0的行打（没有工作的人所适合的工作分给谁了），重复2

3

对没有打的行划线（所有找到合适工作的人）对打的列划线（没找到合适工作的人最适合的工）如直线数<任务数，转第四步,如直线数=任务数,

的数<任务数，回到第三步第四步:没有被直线覆盖的行找“最小元素”打的各行—{最小元素},打的列+{最小元素}得到的新矩阵有更多的0元素，若得到n个独立元素则求的最优解，否则回到第三步克尼格定理

:

如果从分配问题效率矩阵(cij)的每一行元素中分别减去(或加上)一个常数ui，从每一列中分别减去(或加上)一个常数vj，得到一个新的效率矩阵(bij)，其中bij=aij-ui-vj,则以(bij)为效率矩阵的分配问题与以(cij)为效率矩阵的分配问题具有相同的最优解。

任务人员ABCD甲67112乙4598丙31104丁5982例:华东交通大学工业工程与物流管理系

运筹学第一步，变换系数矩阵：－5第二步，试指派：◎◎◎ØØ

找到3个独立零元素但m=3<n=

4

第三步，作最少的直线覆盖所有0元素：

◎◎◎ØØ√√√独立零元素的个数m等于最少直线数l，即l＝m=3<n=4；

第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派：000000得到4个独立零元素，所以最优解矩阵为：

◎◎◎ØØ√√√◎◎◎ØØ◎◎◎ØØ◎练习：115764戊69637丁96458丙9117129乙118957甲EDCBA费工作用人员-1-2◎Ø◎◎◎ØØ◎Ø◎◎◎ØØ√√√l=m=4<n=5◎Ø◎◎◎ØØ◎Ø◎Ø◎Ø◎Ø√√√√√√√◎Ø◎Ø◎Ø◎Ø√√√√√√√l=m=4<n=5◎Ø◎Ø◎Ø◎Ø√√√√√√√◎ØØ◎ØØ◎Ø◎Ø◎此问题有多个最优解28◎ØØ◎ØØ◎Ø◎Ø◎◎ØØ◎ØØ◎Ø◎Ø◎打破僵局时选择不当的结果：结果仅出现3个标记()，但却划出4条线，说明什么？！

四、不平衡的指派问题当人数m大于工作数n时，加上m－n项工作，例如当人数m小于工作数n时，加上n－m个人，例如求最大值的指派问题匈牙利法的条件是：模型求最小值、效率cij≥0令则与的最优解相同。设C对应的模型是求最大值将其变换为求最小值。例某人事部门拟招聘4人任职4项工作，对他们综合考评的得分如下表（满分100分），如何安排工作使总分最多。解M＝95，令用匈牙利法求解：最优解：一个人可做几件事的指派问题若某人可做几件事，则将该人化作相同的几个“人”来接受指派，且费用系数取值相同。例如：丙可以同时任职A和C工作，求最优指派方案。某事一定不能由某人做的指派问题将该人做此事的效率系数取做足够大的数，可用M表示。例分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务。每个人完成各项任务的时间如表所示。由于任务数多于人数，考虑任务E必须完成，其他4项中可任选3项完成。试确定最优分配方案，使完成任务的总时间最少。

任务人员ABCDE甲2529314237乙3938262033丙3427284032丁2442362345解:1)这是不平衡的指派问题，首先转换为标准型，再用匈牙利法求解。2)由于任务数多于人数，所以假定一名虚拟人，设为戊。因为工作E必须完成，故设戊完成E的时间为M（M为非常大的数），其余效率系数为0，则标准型的效率矩阵表示为：

任务人员ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊0000M用匈牙利法求出最优指派方案为：即甲－B，乙－D，丙－E，丁－A,任务C放弃。最少时间为105。例

混合泳接力队队员的选拔问题

赵钱张王周仰泳37.732.938.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1解：这是一个最小化指派问题，人数与事数不等。每行/列减去最小数字添加虚拟事情，利用匈牙利算法求解独立零元素个数等于矩阵维数，得到最优解分配矩阵仰泳——周蛙泳——王蝶泳——钱自由泳——赵例：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司