运筹学-第4章--整数规划习题

第四章整数规划4.1工厂生产两种设备，甲和乙。众所周知，生产这两种设备需要消耗甲和乙两种材料。相关数据如下。这两种设备生产多少才能使工厂利润最大化？(仅建模，不求解)表4-1装备材料AB资源限制材料甲(千克)2314材料B(千克)10.54.5利润(元/件)32解决方案：将生产设备A和B的数量分别设置为x1和x2。因为它是设备的数量，它的变量都要求是整数。该模型建立如下：4.2切割平面法。(下表是最佳表格)7900bCBXBx1x2x3x49x2017/221/227/27x110-1/223/229/2cj-zj00-28/11-15/11解决方案：线性规划的最优解是：从最终表格中：系数和常数项分解为整数和非负真分数之和，上述公式转换为：移动项目后：那就是：只要在B问题的最优单纯形表中加入附加约束。表4-379000bCBXBx1x2x3x4x59x2017/221/2207/27x110-1/223/2209/20x500-7/22*-1/221-1/2cj-zj00-28/11-15/110此时，得到的解是不可行的，用对偶单纯形法求解。迭代以获得：表4-479000bCBXBx1x2x3x4x59x20100137x11001/7-1/732/70x30011/7-22/711/7cj-zj000-1-8从计算结果可知，整数解尚未得到，割线平面方程再次搜索。从x1行：将系数和常数项分为整数和非负真分数之和：获得了新的约束：将此约束添加到的最优单纯形表中，并使用对偶单纯形法求解：790000bCBXBx1x2x3x4x5x69x201001037x11001/7-1/7032/70x30011/7-22/7011/70x6000-1/7*-6/71-4/7cj-zj000-1-809x201001037x11000-1140x30010-4110x400016-74cj-zj0000-2-7那么最优解是最优目标函数值是z*=55。4.3最大z=4x1+3x2+2x3隐式枚举方法解决方法：(1)首先通过启发式方法找到一个初始可行解，如X1=X2=0，X3=1。如果满足约束条件，则选择它作为初始可行解，并且目标函数Z0=2。(2)附加过滤条件以目标函数为过滤约束：原始模型变为：最大z=4x1+3x2+2x3解决方案流程如表所示。要点过滤条件限制z值4x1+3x2+2x32(0，0，0)吨(0，0，1)吨2(0，1，0)吨(0，1，1)吨54x1+3x2+2x35(1，0，0)吨(1，0，1)吨(1，1，0)吨74x1+3x2+2x37(1，1，1)吨9因此，0-1规划的最优解是。4.4一家公司计划在该市的东、西、南区设立一个销售部。有7个点AI (I=1，2，7)可供选择，并且需要下列条件：(1)在东区，三个点A1、A2和A3将有两个或两个以上；(2)西区A4和A5中至少一个；(3)在南区，A6和A7是互斥点。(4)A2需要A5。如果艾点的投资是200万元，年利润是200万元，总投资是200万元，试着建立一个利润最大化的0-1规划模型。解决方案：将决策变量设置为如下建立0-1规划模型：4.5城市消防队的分布。这个城市有六个区，每个区都可以配备消防站。市政府希望建立最少数量的消防站，但它必须满足当城市任何地区发生火灾时，消防车应在15分钟内到达现场的要求。根据现场测量，消防车在各区之间的行驶时间如表4-9所示。请帮助城市用最少的地点制定一个计划。表4-9消防车各区间运行时间表单位：分钟区域1区域2区域3区域4区域56区区域101016282720区域210024321710区域316240122721区域428321201525区域5271727150146区20102125140解决方案：引入0-1变量xi作为决策变量目标函数是最小z=x1+x2+x3+x4+x5+x6这个问题的约束方程是确保每个区域在15分钟的行程内都有一个消防站。例如，在1区，从表4-9可以看出，1区和2区的消防站能够满足这一要求，即x1+x21因此，这个问题的数学模型如下：最小z=x1+x2+x3+x4+x5+x6x1+x2 1s.tx1+x2 +x61x3+x4 1x3+x4+x5 1x4+x5+x6 1x2 +x5+x6 1Xi=1或0 (i=1，6)4.7登山运动员需要携带食物、氧气、冰镐、绳索、帐篷、摄影设备、通讯设备等。各项目的权重和重要性系数见表4-10。可以承载的最大重量是25公斤。试着选择登山运动员应该携带的物品。表4-10序列号1234567文章食物氧冰斧绳索帐篷照相器材通信设备重量公斤55251023重要性系数201516148149解决方案：引入0-1变量xi(i=1，7)那么0-1规划模型