凌晨: m七章整数规划(P) 虽然用途广泛,但经常地,客观上要求 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