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

第四章——1第四章整数规划4.1某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A、材料B，有关数据如下，问这两种设备各生产多少使工厂利润最大？（只建模不求解）表4－1设备材料甲乙资源限量材料A（kg）2314材料B（kg）10.54.5利润（元/件）32解：设生产甲、乙这两种设备的数量分别为x1、x2，由于是设备台数，则其变量都要求为整数，建立模型如下：2123maxxxz为整数21212121,0,5.45.01432xxxxxxxx4.22197maxxxz且为整数0,35763.212121xxxxxxts割平面法求解。（下表为最优表）jc7900bCBXBx1x2x3x49x2017/221/227/27x110－1/223/229/2cj－zj00－28/11－15/11解：线性规划的最优解为：63max,0,2/7,2/94321zxxxx由最终表中得：27221227432xxx④将系数和常数项分解成整数和非负真分式之和，上式化为；213221227432xxx移项后得：①②③④①②③第四章——2即：21221227212212274343xxxx只要把增加的约束条件加到B问题的最优单纯形表中。表4－3jc79000bCBXBx1x2x3x4x59x2017/221/2207/27x110－1/223/2209/20x500－7/22*－1/221－1/2cj－zj00－28/11－15/110这时得到的为非可行解，用对偶单纯形法进行求解。进行迭代得到：表4－4jc79000bCBXBx1x2x3x4x59x20100137x11001/7－1/732/70x30011/7－22/711/7cj－zj000－1－8由计算结果知还没有得到整数解，重新再寻找割平面方程。由x1行得：7327171541xxx将系数和常数项分解成整数和非负真分数之和：74476715541xxxx得到新的约束条件：74767154xx747671654xxx在的最优单纯形表中加上此约束，用对偶单纯形法求解：jc790000bCBXBx1x2x3x4x5x69x201001037x11001/7－1/7032/70x30011/7－22/7011/70x6000－1/7*－6/71－4/7cj－zj000－1－809x201001037x11000－1140x30010－4110x400016－74cj－zj0000－2－7则最优解为3,4*2*1xx，最优目标函数值为z*=55。4.3maxz＝4x1＋3x2＋2x3第四章——310,,13344352.32132321321或xxxxxxxxxxxts隐枚举法解：（1）先用试探的方法找出一个初始可行解，如x1＝x2＝0，x3＝1。满足约束条件，选其作为初始可行解，目标函数z0＝2。（2）附加过滤条件以目标函数0zz作为过滤约束：2234321xxx原模型变为：maxz＝4x1＋3x2＋2x310,,22341334435232132132321321或xxxxxxxxxxxxxx求解过程如表所示。点过滤条件约束z值④①②③4x1＋3x2＋2x3≥2（0，0，0）T×（0，0，1）T√√√√2（0，1，0）T√√×（0，1，1）T√√√√54x1＋3x2＋2x3≥5（1，0，0）T×（1，0，1）T√×（1，1，0）T√√√√74x1＋3x2＋2x3≥7（1，1，1）T√√√√9所以该0－1规划最优解为9,1**3*2*1zxxx。4.4某公司拟在市东、西、南三区中建立门市部，有7个点Ai（i＝1，2，…，7）可供选择，要求满足以下条件：（1）在东区，在A1，A2，A3三个点中至多选两个；（2）在西区，A4，A5两个点中至少选一个；（3）在南区，A6，A7两个点为互斥点。（4）选A2点必选A5点。若Ai点投资为bi万元，每年可获利润为ci万元，投资总额为B万元，试建立利润最大化的0－1规划模型。解：设决策变量为7,,2,1,0,1iAAxiii点未被选用当点被选用当建立0－1规划模型如下：①②③④第四章——4iiixcxcxcxcz71772211max7,,2,1,100112.52765432171ixxxxxxxxxxBxbtsiiii，或4.5某城市消防队布点问题。该城市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见表4－9，请帮助该市制定一个布点最少的计划。表4－9消防车在各区间行驶时间表单位：min地区1地区2地区3地区4地区5地区6地区101016282720地区210024321710地区316240122721地区428321201525地区527172715014地区620102125140解：引入0－1变量xi作决策变量，令6,,2,1,0,1iiixi不设消防站表示在地区设消防站表示在地区目标函数为minz＝x1＋x2＋x3＋x4＋x5＋x6本问题的约束方程是要保证每个地区都有一个消防站在15分钟行程内。如地区1，由表4－9可知，在地区1及地区2内设消防站都能达到此要求，即x1＋x2≥1因此本问题的数学模型为：minz＝x1＋x2＋x3＋x4＋x5＋x6x1＋x2≥1x1＋x2＋x6≥1x3＋x4≥1x3＋x4＋x5≥1x4＋x5＋x6≥1x2＋x5＋x6≥1xi＝1或0（i＝1，…，6）4.7一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等，每种物品的重量及重要性系数见表4－10所示，能携带的最大重量为25kg，试选择该队员所应携带的物品。表4－10序号1234567物品食品氧气冰镐绳索帐篷照相器材通信设备重量kg55251023重要性系数201516148149s.t第四章——5解：引入0－1变量xiiiixxx不携带物品携带物品01（i＝1，…，7）则0－1规划模型为：maxz＝20x1＋15x2＋16x3＋14x4＋8x5＋14x6＋9x7s.t.5x1＋5x2＋2x3＋5x4＋10x5＋2x6＋3x7≤25xi＝0或1，i＝1，0，…，7