运筹学_第4章__整数规划习题.doc

第四章 整数规划4.1 某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A、材料B，有关数据如下，问这两种设备各生产多少使工厂利润最大？（只建模不求解）表41设备材 料甲乙资源限量材料A（kg）2314材料B（kg）10.54.5利润（元/件）32解：设生产甲、乙这两种设备的数量分别为x1、x2，由于是设备台数，则其变量都要求为整数，建立模型如下：4.2 割平面法求解。（下表为最优表）7900bCBXBx1x2x3x49x2017/221/227/27x1101/223/229/2cjzj0028/1115/11解： 线性规划的最优解为：由最终表中得： 将系数和常数项分解成整数和非负真分式之和，上式化为；移项后得：即： 只要把增加的约束条件加到B问题的最优单纯形表中。表4379000bCBXBx1x2x3x4x59x2017/221/2207/27x1101/223/2209/20x5007/22*1/2211/2cjzj0028/1115/110这时得到的为非可行解，用对偶单纯形法进行求解。进行迭代得到：表4479000bCBXBx1x2x3x4x59x20100137x11001/71/732/70x30011/722/711/7cjzj00018由计算结果知还没有得到整数解，重新再寻找割平面方程。由x1行得：将系数和常数项分解成整数和非负真分数之和：得到新的约束条件： 在的最优单纯形表中加上此约束，用对偶单纯形法求解：790000bCBXBx1x2x3x4x5x69x201001037x11001/71/7032/70x30011/722/7011/70x60001/7*6/714/7cjzj0001809x201001037x110001140x300104110x40001674cjzj000027则最优解为，最优目标函数值为z*=55。4.3 max z4x13x22x3隐枚举法解：（1）先用试探的方法找出一个初始可行解，如x1x20，x31。满足约束条件，选其作为初始可行解，目标函数z02。（2）附加过滤条件以目标函数作为过滤约束：原模型变为：max z4x13x22x3求解过程如表所示。点过滤条件约束z值4x13x22x32（0，0，0）T（0，0，1）T2（0，1，0）T（0，1，1）T54x13x22x35（1，0，0）T（1，0，1）T（1，1，0）T74x13x22x37（1，1，1）T9所以该01规划最优解为。4.4 某公司拟在市东、西、南三区中建立门市部，有7个点Ai（i1，2，7）可供选择，要求满足以下条件：（1）在东区，在A1，A2，A3三个点中至多选两个；（2）在西区，A4，A5两个点中至少选一个；（3）在南区，A6，A7两个点为互斥点。（4）选A2点必选A5点。若Ai点投资为bi万元，每年可获利润为ci万元，投资总额为B万元，试建立利润最大化的01规划模型。解：设决策变量为建立01规划模型如下：4.5 某城市消防队布点问题。该城市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15 分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见表49，请帮助该市制定一个布点最少的计划。表49 消防车在各区间行驶时间表 单位：min地区1地区2地区3地区4地区5地区6地区101016282720地区210024321710地区316240122721地区428321201525地区527172715014地区620102125140解：引入01变量xi作决策变量，令目标函数为min zx1x2x3x4x5x6本问题的约束方程是要保证每个地区都有一个消防站在15分钟行程内。如地区1，由表49可知，在地区1及地区2内设消防站都能达到此要求，即x1x21因此本问题的数学模型为：min zx1x2x3x4x5x6 x1x2 1s.t x1x2 x61 x3x4 1 x3x4x5 1 x4x5x6 1 x2 x5x6 1 xi1或0 （i1，6）4.7 一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等，每种物品的重量及重要性系数见表410所示，能携带的最大重量为25 kg，试选择该队员所应携带的物品。表410序号1234567物品食品氧气冰镐绳索帐篷照相器材通信设备重量kg55251023重要性系数201516148149解：引入0