运筹学整数规划习题

第四章—— 1 第四章整数规划4.1某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A 、材料 B，有关数据如下，问这两种设备各生产多少使工厂利润最大？（只建模不求解）表 4－1 设备材料甲乙资源限量材料 A（ kg）2 3 14 材料 B（kg）1 0.5 4.5 利润（元 /件）3 2 解：设生产甲、乙这两种设备的数量分别为x1、 x2，由于是设备台数，则其变量都要求为整数，建立模型如下：2123maxxxz为整数21212121,0,5.45.01432xxxxxxxx4.2 2197maxxxz且为整数0,35763.212121xxxxxxts割平面法求解。 （下表为最优表）jc7 9 0 0 b CB XBx1 x2 x3x4 9 x20 1 7/22 1/22 7/2 7 x11 0 － 1/22 3/22 9/2 cj－zj 0 0 － 28/11 －15/11 解：线性规划的最优解为：63max,0,2/7,2/94321zxxxx由最终表中得：27221227432xxx④将系数和常数项分解成整数和非负真分式之和，上式化为；213221227432xxx移项后得：①②③④①②③第四章—— 2 即：21221227212212274343xxxx只要把增加的约束条件加到B 问题的最优单纯形表中。表 4－3 jc7 9 0 0 0 b CB XBx1 x2x3x4x59 x20 1 7/22 1/22 0 7/2 7 x11 0 －1/22 3/22 0 9/2 0 x50 0 －7/22* －1/22 1 －1/2 cj －zj 0 0 －28/11 －15/11 0 这时得到的为非可行解，用对偶单纯形法进行求解。进行迭代得到：表 4－ 4 jc7 9 0 0 0 b CB XBx1 x2x3x4x59 x20 1 0 0 1 3 7 x11 0 0 1/7 －1/7 32/7 0 x30 0 1 1/7 － 22/7 11/7 cj－ zj 0 0 0 － 1 －8 由计算结果知还没有得到整数解，重新再寻找割平面方程。由 x1 行得：7327171541xxx将系数和常数项分解成整数和非负真分数之和：74476715541xxxx得到新的约束条件：74767154xx747671654xxx在的最优单纯形表中加上此约束，用对偶单纯形法求解：jc7 9 0 0 0 0 b CB XBx1 x2x3x4x5 x6 9 x20 1 0 0 1 0 3 7 x11 0 0 1/7 －1/7 0 32/7 0 x30 0 1 1/7 － 22/7 0 11/7 0 x60 0 0 －1/7* －6/7 1 － 4/7 cj－ zj 0 0 0 － 1 －8 0 9 x20 1 0 0 1 0 3 7 x11 0 0 0 －1 1 4 0 x30 0 1 0 －4 1 1 0 x40 0 0 1 6 － 7 4 cj－ zj 0 0 0 0 －2 － 7 则最优解为3,4*2*1xx，最优目标函数值为z*=55。4.3 max z＝4x1＋3x2＋2x3第四章—— 3 10,,13344352.32...