《数据、模型与决策 (第二版)》第四章整数规划.ppt

《《数据、模型与决策 (第二版)》第四章整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章整数规划第四章整数规划数据、模型与决策(第二版)学习目的整数规划是最近二十年多来发展起来的规划论中的一个分支。本章的学习应着重于整数线性规划的概念、整数线性规划模型分类、如何建立整数规划模型、整数规划的求解—图解法、分枝定界法，以及0-1整数规划的求解方法。第四章整数规划数据、模型与决策(第二版)第四章整数规划4.1整数规划概述4.2整数规划的图解法4.3分枝定界法4.40-1整数规划第四章整数规划数据、模型与决策(第二版)4.1整数规划概述4.1.1整数线形规划的概念4.1.2整数线形规划模型分类4.1.3建立整数规

2、划模型第四章整数规划数据、模型与决策(第二版)4.1.1整数线形规划的概念整数规划：是一类要求设计变量取整数值的数学规划。整数线性规划的可行解集是相应的线性规划的可行解集的一个子集。第四章整数规划数据、模型与决策(第二版)实例分析：ＴＢＡ航空公司是一家地区性公司，从事小型飞机的短途运输。公司运营状况良好，目前正考虑扩展业务。公司管理层面临的主要问题是要在两种决策中作出选择：是购买小型飞机增加短途航班，在原有市场中进一步发展；还是购买一个大型机提供跨省市航班，从而将市场扩大到整个国家；或者是采取两种措施。许多因素都影响着管理层

3、的最终决策，但其中最重要的一点是其中哪种措施会带来最大的利润。表４－１的第一行表示的是各种型号飞机估计的年利润（包括资金回收成本）。第二行表示的是各种飞机的单位购买成本以及可用于购买飞机的总资金１亿美元。第三行表明管理层购买小型飞机不会多于两架，因为他们认为可获利的短途航线是有限的，不需要在短途航线上增加更多的飞机，而大型飞机的购买量还没有确定。公司要作出决策，为了获取最大的利润，公司应该购买多少架飞机？而各种型号飞机的用油该如何组合呢？第四章整数规划数据、模型与决策(第二版)项目小型飞机大型飞机可得资金总额每架飞机年利润（

4、万美元）1005001亿美元飞机的单位购价（万美元）5005000最多购买数量2----第四章整数规划数据、模型与决策(第二版)4.1.2整数线形规划模型分类纯整数线性规划所有决策变量必须取整数值的整数线性规划，也称为全整数线性规划。混合整数线性规划决策变量中的一部分必须取整数值，而其他的可以不取整数值的整数线性规划。０－１型整数线性规划决策变量只能取０或１的整数线性规划。第四章整数规划数据、模型与决策(第二版)4.1.3建立整数规划模型实例分析：一家电子厂生产两种产品Ａ１和Ａ２，需经过三道工序加工：Ｂ１，Ｂ２，Ｂ３。单件加

5、工利润以及各工时每周限额如表所示。应该如何安排生产才能取得最大利润？第四章整数规划数据、模型与决策(第二版)项目工序B1工序B2工序B3利润（元/件）产品（件）0.40.40.330产品（件）0.50.30.228工时限额（小时/周）200180120--解题过程：因为待生产的产品数量是整数，所以这是一个整数线性规划问题。设每周生产产品件，产品件。目标函数：maxz＝30ａ１＋28ａ２约束条件：0.4ａ１＋0.5ａ２≤2000.4ａ１＋0.3ａ２≤1800.3ａ１＋0.2ａ２≤200，≥０，且必须为整数第四章整数规划数据、模

6、型与决策(第二版)某宾馆服务部门各时段（每３小时为一时段）需要的服务人员人数如表所示。按照规定，服务员连续工作９个小时也就是三个时段为一班，现在要根据此表安排服务员工作时间，使该部门的服务员数量最少。时段12345678服务员最少数量（人）9810127563第四章整数规划数据、模型与决策(第二版)这是一个纯整数线性规划问题。假设在第ｊ时段上班的服务员人数为ｘｊ，由于第ｊ时段开始上班的服务员人数将在第（ｊ＋２）时段结束时下班，所以不需要设置９个决策变量将各个时段的服务员人数全部表示出来，只需要６个决策变量：ｘ１，ｘ２，ｘ３，

7、ｘ４，ｘ５和ｘ６，建立该问题的整数线性规划模型如下。目标函数：minz＝约束条件：≥９≥８≥１０≥１２≥７≥５≥６≥３非负整数约束≥０，且均为整数。第四章整数规划数据、模型与决策(第二版)某公司准备有总额为ｘ的投资资金，可供选择的投资项目有７个，项目ｊ所需投资额和预期收益分别为ａｊ和ｃｊ（ｊ＝１，２，…，ｎ），此外，由于种种原因，投资项目有三个附加条件：①若是选择项目１，就必须同时选择项目２。②项目３和项目４至少选择一个。③项目５，６，７中必须选择两个。现在应该如何选择投资项目？第四章整数规划数据、模型与决策(第二版)解题过

8、程为：由于每一个项目都有被选择和不被选择两种可能性，因此这个问题可以看成一个０－１规划问题，决策变量设为，如果对项目ｊ投资，那么＝１，否则为０。第四章整数规划数据、模型与决策(第二版)第四章整数规划4.1整数规划概述4.2整数规划的图解法4.3分枝定界法4.40-1整数规划第四章整数规划数