[经济学]管理运筹学-11-整数规划1.ppt

管理运筹学 整数规划 [例] 求解下列0-1 规划问题 × 6 2 (1,1,1) × 3 (1,1,0) 8 ? 1 1 2 0 (1,0,1) × 5 1 (1,0,0) 3 ? 0 1 1 1 (0,1,1) -2 ? 4 1 4 2 (0,1,0) 5 ? 1 0 1 -1 (0,0,1) 0 ? 0 0 0 0 (0,0,0) (4) (3) (2) (1) z 可行? 约束条件 6 (1,1,1) 1 (1,1,0) 8 ? 1 1 2 0 (1,0,1) 3 (1,0,0) 3 (0,1,1) -2 (0,1,0) 5 ? 1 0 1 -1 (0,0,1) 0 ? 0 0 0 0 (0,0,0) (4) (3) (2) (1) z 可行? 约束条件 为了进一步减少运算，可按目标函数中个变量系数顺序重新排列各变量，以使最优解较早出现。(一般情况) 一般地，对于Max问题，可降序排；对于Min问题，反之。 例 求解下列0-1 规划问题 × 0 0 (1,1,0,0,0) × -1 0 (1,0,1,0,0) 8 ∨ 4 -4 (0,0,0,1,0) × -2 1 (0,0,1,0,0) × -1 1 (0,1,0,0,0) × 1 -1 (1,0,0,0,0) × 0 0 (0,0,0,0,0) 是 否 (1) (2) Z 值 满足条件 约束条件 (x5,x4,x2,x3,x1) 例 求解下列0-1规划问题 由于目标函数中变量x1, x2 , x4 的系数均为负数，可作如下变换： 令 x1 ＝1-x1′ , x2 =1- x2′, x3= x3′, x4 =1- x4′带入原题中，重新调整变量编号。 2 ? 1 4 8 (1,1,1,1) 是 否 (1) (2) (3) Z 值 满足条件 约束条件 (x3,x4,x1,x2) 一般形式的0-1规划化为标准形式： 2.0-1分支定界法： 与整数规划的分支定界法类似，但要求化为标准型。 一、0-1规划的解法 其中要求cj非正！ 例 求解下列0-1规划问题 0-1 Branch 1 x2=0,other=0 Branch 2 x2=1,other=0 ? × 0-1变量作为逻辑变量(Logical Variable), 常用于表示系统是否处于某个状态，或者决策时是否取某个方案。例如： 二、0-1变量以及应用 例： 某银行用资金a对A，B，C三个行业放款，对行业A(企业Ai=1,2,3,4）至多选择2个企业；对行业B(企业Bj=1,2,3,4,5)至多选择3个企业；对行业C(企业Ck=1,2,3,4)至多选择2个企业。如企业Xi得到放款后，银行可获利bi，应如何安排放款计划？ 令： 对本讲开始第一个例子修改如下： 例 现有甲乙两种货物拟用集装箱托运，每件货物的体积、重量、获利、以及运输方式的总托运限制如下，求托运方案。 13(车运) 24(船运) 方式限制 20 10 2 5 5 4 甲 乙 利润 重量 体积 货物 指派问题 见p173，指派问题的解： 系数矩阵： 重要性质： 如从矩阵C中的任何一行/列中的各元素，加上一个实数a，从而得到一个新的矩阵B，那么以B为效益矩阵的指派问题与原问题同解。 证明： 不失一般性，假定从C中的第k行加上实数a，则： 那么，新矩阵的目标函数为： 解题步骤： 指派问题是0-1规划的特例，也是运输问题的特例，当然可用整数规划，0-1规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不经济的。 利用指派问题的特点可有更简便的解法，这就是匈牙利法，即系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。 第1步： 变换指派问题的系数矩阵(cij)为(bij)，使在(bij)的各行各列中都出现0元素，即 (1) 从(cij)的每行元素都减去该行的最小元素； (2)再从所得新系数矩阵的每列元素中减去该列的最小元素。 第2步： 进行试指派，以寻求最优解。 在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。 否则，转下一步； 第3步： 最少直线覆盖所有0元素。 第4步 变换矩阵(bij)以增