运筹学课设-商场售货员分配问题

1、目目 录录 一、问题提出一、问题提出.- 1 - 二、问题分析二、问题分析.- 2 - 三、模型建立三、模型建立.- 2 - 3.13.1 建立目标函数建立目标函数.- - 2 2 - - 3.23.2 建立约束方程建立约束方程.- - 2 2 - - 3.33.3 建立数学模型建立数学模型.- - 3 3 - - 四、问题求解四、问题求解.- 4 - 五、结果分析五、结果分析.- 7 - 总总 结结.- 11 - 参考文献参考文献.- 12 - 一、问题提出一、问题提出 某商场对售货员的需求分析经过统计分析如下表所示，为了保证售货人员 充分休息，售货人员每周工作 5 天，休息 2 天，并且要

2、求休息的两天是连续的， 那么应该如何安排售货员的作息，就能满足工作需求，又使配备的售货人员的 数目最少呢？ 时 间所需的售货员人数 星期日 28 星期一 15 星期二 24 星期三 25 星期四 19 星期五 31 星期六 28 二、问题分析二、问题分析 如何在保证售货员充分休息，售货员每周工作五天，连续休息两天的前提 下，排售货员分配问题，既满足工作需求，又能使配备的收货人员的数目最少， 这是一个线性规划的问题，以你我们可以建立模型，然后用 lindo 软件求得最 优解。在建立模型时我们设为每天开始休息的人数，由于每个人每周都要休 1 x 息两天而且连续两天休息，所以总的售货员人数就是所有休

3、息的收获员人数即 可得到目标函数，根据表中的约束条件，我们可以得到约束方程： 三、模型建立三、模型建立 3.1 建立目标函数建立目标函数 设（i=1,2,3，7）表示星期一至星期日开始休息的人数，Z 1 x 为总共要配备的售货员数目。 则目标函数为：min 7654321 xxxxxxxz 3.2 建立约束方程建立约束方程 从约束条件可知道周日所需要的售货员数目为 28，我们可以假设周日休息 的售货员是从周六开始的，那么周一至周五休息的人数总和必须不小于周日工 作的人数，从而得到约束方程 ： ；28 54321 xxxxx 周一所需要的售货员数目为 15，我们可以假设周一休息的售货员是从周日开

4、始 的，那么周二至周六休息的人数总和必须不小于周一工作的人数，从而得到约 束方程 ：；15 65432 xxxxx 周二所需要的售货员数目为 24，我们可以假设周二休息的售货员是从一开 始的，那么周三至周日休息的人数总和必须不小于周二工作的人数，从而得到 约束方程 ：；24 76543 xxxxx 周三所需要的售货员数目为 25，我们可以假设周三休息的售货员是从周二 开始的，那么周四至周一休息的人数总和必须不小于周三工作的人数，从而得 到约束方程：；25 17654 xxxxx 周四所需要的售货员数目为 19，我们可以假设周四休息的售货员是从周三 开始的，那么周五至周二休息的人数总和必须不小于

5、周四工作的人数，从而得 到约束方程：；19 21765 xxxxx 周五所需要的售货员数目为 31，我们可以假设周五休息的售货员是从周四 开始的，那么周六至周三休息的人数总和必须不小于周五工作的人数，从而得 到约束方程：；31 32176 xxxxx 周六所需要的售货员数目为 28，我们可以假设周六休息的售货员是从周五 开始的，那么周日至周四休息的人数总和必须不小于周六工作的人数，从而得 到约束方程：；28 43217 xxxxx 3.3 建立数学模型建立数学模型 目标函数：min 7654321 xxxxxxxz 约束条件： 28 33 16 28 22 15 30 43217 32176

6、21765 17654 76543 65432 54321 xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx (i=1,2,37)0 i x 四、问题求解四、问题求解 软件 lindo 运行结果： LP OPTIMUM FOUND AT STEP 5 OBJECTIVE FUNCTION VALUE 1) 37.66667 VARIABLE VALUE REDUCED COST X1 15. 0. X2 0. 0. X3 9. 0. X4 2. 0. X5 2. 0. X6 7. 0. X7 0. 0. ROW SLACK OR SURPLUS DUAL PR

7、ICES 2) 0. -0. 3) 7. 0. 4) 0. -0. 5) 0. -0. 6) 9. 0. 7) 0. -0. 8) 0. 0. NO. ITERATIONS= 5 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 1. 0. 1. X2 1. INFINITY 0. X3 1. 0. 1. X4 1. 0. 0. X5 1. 0. 0. X6 1. 0. 1. X7 1. INF

8、INITY 0. RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 30. 4. 2. 3 15. 7. INFINITY 4 22. 23. 7. 5 28. 14. 8. 6 16. 9. INFINITY 7 33. 4. 13. 8 28. 2. 2. 由于商场售货员人数均为整数，所以求得的解 =15. ， =0，=9.， 1 x 2 x 3 x = 2.，= 2. , = 7.，=0 不符合实际要求，要使得所求解均为整 4 x 5 x 6 x 7 x 数，可使用 GIN 命令将变

9、量仅限为整数型，文件内容如下： LP OPTIMUM FOUND AT STEP 0 OBJECTIVE VALUE = 37. FIX ALL VARS.( 2) WITH RC 0.E+00 SET X4 TO 0.E+00 SET X4 TO = 2 AT 1, BND= -38.00 TWIN= -37.67 6 NEW INTEGER SOLUTION OF 38. AT BRANCH 1 PIVOT 6 BOUND ON OPTIMUM: 37.66667 DELETE X4 AT LEVEL 1 ENUMERATION COMPLETE. BRANCHES= 1 PIVOTS=

10、6 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION. OBJECTIVE FUNCTION VALUE 1) 38.00000 VARIABLE VALUE REDUCED COST X1 16. 1. X2 0. 1. X3 10. 1. X4 2. 1. X5 2. 1. X6 8. 1. X7 0. 1. ROW SLACK OR SURPLUS DUAL PRICES 2) 0. 0. 3) 7. 0. 4) 0. 0. 5) 0. 0. 6) 10. 0. 7) 1. 0. 8) 0. 0. NO

11、. ITERATIONS= 6 BRANCHES= 1 DETERM.= 1.000E 0 五、结果分析五、结果分析 “LP OPTIMUM FOUND AT STEP 5”表示 LINDO 在（用单纯形法）5 次迭代后得 到最优解; “OBJECTIVE FUNCTION VALUE OBJECTIVE FUNCTION VALUE 1) 38.00000 ” 表示最优目标值为 38.00000; “VALUE”给出最优解中各变量的值: =16 =0 =10 =2 = 2 =8 =0 1 x 2 x 3 x 4 x 5 x 6 x 7 x “REDUCED COST”表示其中的值随最优解中各

12、变量变化而增加 REDUCED COST 中 相应的变量的值 VARIABLE VALUE REDUCED COST X1 16. 1. X2 0. 1. X3 10. 1. X4 2. 1. X5 2. 1. X6 8. 1. X7 0. 1. 即随着最优解值的变化一个单位最优值 38.00000 就增加一个相应的 REDUCED COST 中的值 “SLACK OR SURPLUS”给出松弛变量的值。即将最优解中的值代入到约束方程 中与原约束值相比较 0. 7. 0. 0. 10. 1. 0. =16+0+10+2+2=30-30=0 1 b =0+10+2+2+8=22-15=7 2 b

13、 =10+2+2+8+0=22-22=0 3 b =2+2+8+0+16=28-28=0 4 b =2+8+0+16+0=26-16=0 5 b =8+0+16+0+10=34-33=1 6 b =0+16+0+10+2=28-28=0 7 b “DUAL PRICE” （对偶价格）列出最优单纯形表中判别数所在行的松弛变量 的系数，表示当对应约束有微小变动时，目标函数的变化率，输出结果中对应 每一个约束有一个对偶价格: ROW SLACK OR SURPLUS DUAL PRICES 2) 0. 0. 3) 7. 0. 4) 0. 0. 5) 0. 0. 6) 10. 0. 7) 1. 0.

14、8) 0. 0. “RANGES IN WHICH THE BASIS IS UNCHANGED”给出灵敏度分析：如果做敏感 性分析，则系统报告当目标函数的费用系数和约束右端项在什么范围变化（此 时假定其他系数保持不变）时，最优基保持不变。报告中 INFINITY 表示正无穷。 其中， “OBJ COEFFICIENT RANGES”为目标函数的系数可变范围；“RIGHTHAND SIDE RANGES”为边界约束的可变范围。 最优基保持不变 VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE(+) DECREASE(-) X1 1. 0. 1

15、. X2 1. INFINITY 0. X3 1. 0. 1. X4 1. 0. 0. X5 1. 0. 0. X6 1. 0. 1. X7 1. INFINITY 0. 即: 的系数 0 到 1.5 之间变化，的系数在 0.67 到 之间变化， 1 x 2 x 的系数在 0 到 1.5 之间变化，在 0 到 1 之间变化，在 0 到之间变化时 3 x 6 x 7 x 不影响最优解。 约束右端项保持不变 ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 30. 4. 2. 3 15. 7. INFINITY 4 22. 23. 7.

16、 5 28. 14. 8. 6 16. 9. INFINITY 7 33. 4. 13. 8 28. 2. 2. 在 28 到 34 之间变化时不影响售货员分配的最优解； 1 b 在 0 到 22 之间变化时不影响售货员分配的最优解； 2 b 在 15 到 45.5 之间变化时不影响售货员分配的最优解； 3 b 在 20 到 42.5 之间变化时不影响售货员分配的最优解； 4 b 在 0 到 25.3 之间变化时不影响售货员分配的最优解； 5 b 在 19 到 37 之间变化时不影响售货员分配的最优解； 6 b 在 25.3 到 30 之间变化时不影响售货员分配的最优解。 7 b 经以上分析可知：当=16 =0 =10 =2 = 2 =8 =0 1 x 2 x 3 x 4 x 5 x 6 x 7 x 时，也就是周一安排 16 人休息，周二不安排人休息，周三安排 10 人休息，周 四安排 2 个人休息，周五安排 2 个人休息，周六安排 8 个人休息，周日不安排 人休息时，我们在可以保证工作需求的情况下配备最少的售货员 38 名。 总总 结结 通过本次的课程设计，我了