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

《运筹学_第4章__整数规划习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章整数规划4.1某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A、材料B，有关数据如下，问这两种设备各生产多少使工厂利润最大？（只建模不求解）表4－1设备材料甲乙资源限量材料A（kg）2314材料B（kg）10.54.5利润（元/件）32解：设生产甲、乙这两种设备的数量分别为x1、x2，由于是设备台数，则其变量都要求为整数，建立模型如下：①②③④4.2①②③割平面法求解。（下表为最优表）7900bCBXBx1x2x3x49x2017/221/227/27x110－1/223/229/2cj－zj00－28/11－15/11解：线性规划的最优解为：由最终表中得：④将

2、系数和常数项分解成整数和非负真分式之和，上式化为；移项后得：第四章——5即：只要把增加的约束条件加到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由计算结果知还没有得到整数解，重新再寻找

3、割平面方程。由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.3maxz＝4x1＋3x2＋2x3第四章——5隐枚举法解：（1）先用试探的方法找出一个初

4、始可行解，如x1＝x2＝0，x3＝1。满足约束条件，选其作为初始可行解，目标函数z0＝2。（2）附加过滤条件以目标函数作为过滤约束：原模型变为：maxz＝4x1＋3x2＋2x3①②③④求解过程如表所示。点过滤条件约束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规划最优解为。4.4某公司拟在市东、西、南三区中建立门市部，有7个点Ai（i＝1，2

5、，…，7）可供选择，要求满足以下条件：（1）在东区，在A1，A2，A3三个点中至多选两个；（2）在西区，A4，A5两个点中至少选一个；（3）在南区，A6，A7两个点为互斥点。（4）选A2点必选A5点。若Ai点投资为bi万元，每年可获利润为ci万元，投资总额为B万元，试建立利润最大化的0－1规划模型。解：设决策变量为建立0－1规划模型如下：第四章——54.5某城市消防队布点问题。该城市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见表4－9，请帮助该市制定一个布点

6、最少的计划。表4－9消防车在各区间行驶时间表单位：min地区1地区2地区3地区4地区5地区6地区101016282720地区210024321710地区316240122721地区428321201525地区527172715014地区620102125140解：引入0－1变量xi作决策变量，令目标函数为minz＝x1＋x2＋x3＋x4＋x5＋x6本问题的约束方程是要保证每个地区都有一个消防站在15分钟行程内。如地区1，由表4－9可知，在地区1及地区2内设消防站都能达到此要求，即x1＋x2≥1因此本问题的数学模型为：minz＝x1＋x2＋x3＋x4＋x5＋x6x1＋x2≥1s.

7、tx1＋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重要性系数201516148149第四章——5解：引入0－1变量xi（i＝1，…，7）