第七讲整数规划(一)(运筹学基础清华大学,王永县).pptVIP

sdadsd 第七讲 整数规划 （一） §1 概述 §2 割平面法 §3 分枝定界法 §1 概述（1） §1 概述（2） §1 概述（3） §1 概述（4） §1 概述（5） §1 概述（6） §1 概述（7） §2 割平面法 §3 分枝定界法 （1） §3 分枝定界法 （2） §3 分枝定界法 （3） §3 分枝定界法 （4） §3 分枝定界法 （5） §3 分枝定界法 （6） §3 分枝定界法 （7） §3 分枝定界法 （8） §3 分枝定界法 （9） §3 分枝定界法 （10） §3 分枝定界法 （11） 第七讲 整数规划（二） §1 匈牙利法 §2 蒙特卡洛法（随机取样法）（略） §1 匈牙利法 （1） §1 匈牙利法 （2） §1 匈牙利法 （3） §1 匈牙利法 （4） §1 匈牙利法 （5） §1 匈牙利法 （6） §1 匈牙利法 （7） §1 匈牙利法 （8） §5 匈牙利法 （9） §1 匈牙利法 （10） §1 匈牙利法 （11） §1 匈牙利法 （12） §1 匈牙利法 （13） §1 匈牙利法 （14） §1 匈牙利法 （15） §1 匈牙利法 （16） 现在依次检查每列中只含一个未标记的零元素，并给未标记的零元素标Δ。对同一行其它的零元素画×（如果有的话）。 如果有多行多列同时有2个或以上的未标记零元素，则可将其中的任意行或列中一个未标零元素标Δ，并将同行和同列的其他零元素画×。 因为本例此时不可能制定出只包含零元素的完全分配方案，于是画出最少数目的水平线和垂直线，使它们穿过每行每列的零元素至少一次。其画线步骤如下： ①检查所有尚未分配（即未标记Δ）的行，并记上√。 √ ②检查那些尚未检查过的，而在已检查过的行中有零元素的列，并记上√。 ③检查那些尚未检查过的，而在已检查过的列中有标记△的行，并记上√。 √ √ √ ④重复步骤②和③，直到不能进一步检查为止。本例中，第１轮检查以后即停止。 ⑤在所有未检查的行和已检查的列画直线，这些线可覆盖所有的零。 √ √ √ ⑥在上述最后的缩减矩阵中，检查那些没有线通过的元素。设k为其中最小元素。找出含有未画线元素的各行，将这些行的每个元素减去k。本例中，k=2，因而由第1行、第4行减去2，可得 ⑦第⑥步的减法使第⑤步中画垂直线的各列中某些元素变为负，因此对第⑤步画垂直线的每一列中的所有元素加k。本例第1列的每个元素加2可得 Operations Research Prof. Wang School of Economics Management page * * 第十四、十五讲 一、定义 规划中的变量（部分或全部）限制为整数时，称为整数规 划。若在线性规划模型中，变量限制为整数，则称为整数 线性规划。 二、整数规划分类 如不加特殊说明，一般指整数线性规划。对于整数线性规 划模型大致可分为两类： ??? 变量全限制为整数的，称纯（完全）整数规划。 ??? 变量部分限制为整数的，称混合整数规划。 三、整数规划特点 整数规划标准形式（实际为整数线性规划） AX=b，X≥0，CTX=min，xj为整数（j=1，…，n） (1) 1．原线性规划有最优解，当自变量限制为整数后， 其整数规划解出现下述情况； ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。 [例2-1] 原线性规划为： 2x1+4x2=5，X≥0，CTX=x1+x2=min 其最优实数解为：x1=0，x2=5/4，min CTX =5/4。 ③有可行解（当然就存在最优解），但最优解值变差。 [例2-2] 原线性规划为： 2x1+4x2=6，X≥0，CTX=x1+x2=min 其最优实数解为：x1=0，x2=3/2，min CTX =3/2。 若限制整数则得：x1=1，x2=1，min CTX =2。 2．整数规划最优解不能按照实数最优解简单取整而获得。 [例2-3] 物品装载问题：