凌晨: 七章整数规划(IP) 虽然用途广泛,但经常地,客观上要求 L.P.最优解中不能含有非整数值(如股票 的购买之解答),整数规划就是专门用来 求解这类问题的有效工具 重点掌握:0-1规划灵活应用、分枝定界 法
Ling Xueling 虽然用途广泛，但经常地，客观上要求 L.P.最优解中不能含有非整数值（如股票 的购买之解答），整数规划就是专门用来 求解这类问题的有效工具 重点掌握：0-1 规划灵活应用、分枝定界 法。 第七章 整数规划（I.P.） 凌晨: 凌晨:
凌晨: 第一节IP概念和应用 IP.概念 1、什么是IP 要求部分或全部决策变量是整数的LP.问题 2、IP.的用处 1)现实需要,不得已 2)使用整变量常常使得建模更灵活、应用面扩大 3、IP.的不利 求解通常不易 所谓分枝定界法是最有效的求解方法 几乎所有的计算机程序都用此法
Ling Xueling 一、I.P. 概念 1、什么是 I.P. 要求部分或全部决策变量是整数的 L.P. 问题 2、I.P. 的用处 1）现实需要，不得已 2）使用整变量常常使得建模更灵活、应用面扩大 3、I.P. 的不利 求解通常不易 所谓分枝定界法是最有效的求解方法 几乎所有的计算机程序都用此法。 第一节 I.P. 概念和应用 凌晨: 凌晨:
凌晨: 第一节IP概念和应用 IP.模型分类 1、全整数规划 LP.中若要求所有决策变量皆≥0,且为整数。如股票决策 2、混合IP 如:奖金人数及其奖金数额之决策 3、0-1规划 决策变量只取0或1 4、IP.的LP.松弛 简单放弃ⅠP.中对决策变量是整数的要求而得到的LP模型
Ling Xueling 二、I.P. 模型分类 1、全整数规划 L.P. 中若要求所有决策变量皆 0，且为整数。如股票决策 2、混合 I.P. 如：奖金人数及其奖金数额之决策 3、0－1 规划 决策变量只取 0 或 1 4、I.P. 的 L.P. 松弛 简单放弃 I.P. 中对决策变量是整数的要求而得到的 L.P.模型。 第一节 I.P. 概念和应用 凌晨: 凌晨:
凌晨: 第一节IP概念和应用 IP.模型的应用一一只介绍0-1规划 1、资金预算问题( capital budgeting) 运筹学在财务管理中的应用不少都集中在资金预算问题 假定IC.公司要对今后四年的一些投资项目进行资金管理 目标:选择能得到最大利润的项目并对资金作出预算 有关数据如下 资金需求 项目 预期收入 第一年第二年第三年第四年 1厂房扩建90,000 15,00020,00020,00015,000 x2仓库扩建40,000 10,00015,00020,0005000 x3购新机器10,000 10.000 04,000 x4新品开发37,000 15,00010,00010,00010,000 各年可用资金额 40.00050.00040.00035000
Ling Xueling 三、I.P. 模型的应用－－只介绍 0－1规划 1、资金预算问题（capital budgeting） 运筹学在财务管理中的应用不少都集中在资金预算问题 假定 I.C. 公司要对今后四年的一些投资项目进行资金管理 目标：选择能得到最大利润的项目并对资金作出预算 有关数据如下： 资金需求 项目 预期收入 第一年 第二年 第三年 第四年 x1 厂房扩建 90,000 15,000 20,000 20,000 15,000 x2 仓库扩建 40,000 10,000 15,000 20,000 5,000 x3 购新机器 10,000 10,000 0 0 4,000 x4 新品开发 37,000 15,000 10,000 10,000 10,000 各年可用资金额 40,000 50,000 40,000 35,000 第一节 I.P. 概念和应用 凌晨: 凌晨:
且t 凌晨: 第一节IP概念和应用 IP.模型的应用 1、资金预算问题( capital budgeting) 1)建模(引进0-1变量,但仍然是LP.模型) 设决策变量 1对t项目投资 (单位:1000) 0否则 max90x1+40x2+10x3+37 S t 15X1+10x2+10x3+15x4≤40 (每年可用资金限制) x1+5x2+4x3+10x4≤35 x;≥0
Ling Xueling 三、I.P. 模型的应用 1、资金预算问题（capital budgeting） 1）建模（ 引进 0－1 变量，但仍然是 L.P. 模型） 设决策变量： （单位：1000 ） max 90x1 + 40x2 + 10x3 + 37x4 s.t. 15x1 + 10x2 + 10x3 + 15x4 ≤ 40 .................................... （每年可用资金限制） 15x1 + 5x2 + 4x3 + 10x4 ≤ 35 x i ≥ 0 第一节 I.P. 概念和应用 凌晨: 凌晨: = 否则 对 项目投资 0 1 i xi
凌晨: 第一节IP概念和应用 IP.模型的应用 1、资金预算问题( capital budgeting 2)模型的解及其问题 以上模型实际上是一个LP.模型,其解为: 1=1,x2=0.5,x3=0.5,x4=1,o.f.=152,000 显然是不可行解一一第二、三项目如何只完成50%? 采用简单化整:x1=1,x2=x3=0,x4=1,of=127,000 问题:仍然是最优解吗?
Ling Xueling 三、I.P. 模型的应用 1、资金预算问题（capital budgeting） 2）模型的解及其问题 以上模型实际上是一个 L.P. 模型，其解为： x1 = 1, x2 = 0.5, x3 = 0.5, x4 = 1, o.f. = 152,000 显然是不可行解－－第二、三项目如何只完成 50％？ 采用简单化整： x1 = 1, x2 = x3 = 0, x4 = 1, o.f. = 127,000 问题：仍然是最优解吗？ 第一节 I.P. 概念和应用 凌晨: 凌晨:
凌晨: 第一节IP概念和应用 IP.模型的应用 1、资金预算问题( capital budgeting) 3)采用LP.重新建模(0-1模型) max90x1+40x2+10x3+37x4 5x1+10x2+10x3+15x4≤40 (每年可用资金限制 5x1+5X2+4x2+10x1≤35 0,1 最优解: 0,o.f.=140,000-—可行
Ling Xueling 三、I.P. 模型的应用 1、资金预算问题（capital budgeting） 3）采用 I.P. 重新建模（ 0－1 模型） max 90x1 + 40x2 + 10x3 + 37x4 s.t. 15x1 + 10x2 + 10x3 + 15x4 ≤ 40 .................................... (每年可用资金限制) 15x1 + 5x2 + 4x3 + 10x4 ≤ 35 x i ＝ 0， 1 最优解： x1 = x2 = x3 = 1, x4 = 0, o.f. = 140,000－－可行。 第一节 I.P. 概念和应用 凌晨: 凌晨:
凌晨: 第一节IP概念和应用 IP.模型的应用 1、资金预算问题( capital budgeting) 4)0-1模型用于资金预算的优势 (1)避免小数 (2)灵活性,讨论如下: (i)多重选择 假设实际上有三个仓库可以考虑扩建,要求:三个中有且 仅能有一个得到扩建,则令:x2=1--第一个考虑仓库, 第二个考虑扩建 第三个仓库考虑扩 建,则只需添加下列约束即可: X5+x6 一LP模型没有这么方便
Ling Xueling 三、I.P. 模型的应用 1、资金预算问题（capital budgeting） 4）0－1模型用于资金预算的优势 （1）避免小数 （2）灵活性，讨论如下： （i）多重选择 假设实际上有三个仓库可以考虑扩建，要求：三个中有且 仅能有一个得到扩建，则令：x2 = 1－－第一个考虑仓库， x5 = 1 －－ 第二个考虑扩建，x6 = 1 －－第三个仓库考虑扩 建，则只需添加下列约束即可： x2 + x5 + x6 = 1 －－－L.P. 模型没有这么方便。 第一节 I.P. 概念和应用 凌晨: 凌晨:
凌晨: 第一节IP概念和应用 IP.模型的应用 1、资金预算问题( capital budgeting 4)0-1模型用于资金预算的优势 (i)互斥选择 若要求:至多一个扩建,可添加x2+x5+x6≤ i1)在若干个项目中选择k个的约束 以x2,x3,x62x7,x8表示五个潜在的仓库扩建项目=1或0 a)五中选二 b)五中不超过二: x2+xs+x6+x7+x8≤2
Ling Xueling 三、I.P. 模型的应用 1、资金预算问题（capital budgeting） 4）0－1模型用于资金预算的优势 （ii）互斥选择 若要求：至多一个扩建，可添加 x2 + x5 + x6 ≤ 1 （iii）在若干个项目中选择 k 个的约束 以 x2 , x5 , x6 , x7 , x8 表示五个潜在的仓库扩建项目＝1 或 0 a) 五中选二： x2 + x5 + x6 + x7 + x8 = 2 b) 五中不超过二： x2 + x5 + x6 + x7 + x8 ≤ 2 。 第一节 I.P. 概念和应用 凌晨: 凌晨:
凌晨: 第一节IP概念和应用 IP.模型的应用 1、资金预算问题( capital budgeting iv)有条件约束一某项目的采纳有赖于另一项目的采纳 要求:除非扩建厂房,否则不考虑扩建仓库: or 0 (v)共需约束 要求:只要扩建厂房,就应扩建仓库:x2
Ling Xueling 三、I.P. 模型的应用 1、资金预算问题（capital budgeting） （iv）有条件约束－某项目的采纳有赖于另一项目的采纳 要求：除非扩建厂房，否则不考虑扩建仓库： x2 ≤ x1 or x2 － x1 ≤ 0 （v）共需约束 要求：只要扩建厂房，就应扩建仓库： x2 = x1 。 第一节 I.P. 概念和应用 凌晨: 凌晨: