|
63 Заметим, что в этом решении значение оценочной функции для третьего производителя меньше, чем фактическая стоимость ^(8 )= 8 < зз(8 ) = 16. Поэтому разбиваем второе подмножество на два подмножества р 2 [ н Q2 2 . В первом из них хз < 8 , а во втором хз > 8 . Анализ подмножества Qn. Оценочная функция третьего производителя имеет вид %(хз)= 2 хз, для второго и первого оценочные функции не меняются. Одно из оптимальных решений оценочной задачи xi = О, Х2 = 8 , хз = 6 , 5 = 2 8 . Анализ подмножества Q22. Оценочная функция третьего производителя имеет вид %(xj)= Х3 9 < Х3 < 10. Оптимальное решение оценочной задачи Х] = О, Х2 = 6 , Хз = 9, 5 =2 1 и совпадает с фактической стоимостью. Заметим, что в данном случае центр закупает продукции больше, чем требуется, поскольку, закупая ровно 14 единиц, он в данном случае проигрывает. Действительно, если центр закупает у второго производителя не 6 единиц, а 5, стоимость составит 5-3 = 15 единиц вместо 12, а если он закупает у третьего производителя не 9 единиц, а 8 , то стоимость составит 8-2 = 16 единиц вместо 9. Сравнивая оценочные стоимости подмножеств Qi, Q2 1 и Q2 2 , выбираем подмножество с минимальной оценкой s(Q2 2 )=2 1 . Соответствующее решение Xi = О, хэ = 6 , Х3 = 9 является оптимальным, поскольку оценочная стоимость совпадает с фактической. На рис. 2.2.9 показано дерево ветвлений (разбиений множества всех решений на подмножества), вершины которого соответствуют подмножествам, а числа в вершинах оценочным стоимостям. |
75 чи остается прежним: х, = 0, х2= 4, х3= 10, причем оценка стоимости S = 22 совпадает с фактической стоимостью. Анализ второго подмножества. Оценочная функция для второго производителя во втором подмножестве решений выделена на рис. 2.1.9 толстой линией. Оптимальное решение оценочной задачи х, 0, х2= 6, х3= 8, оценочная стоимость s =12+8=20. Из двух решений выбираем решение с минимальной величиной оценочной функции, то есть второе подмножество Q2с решением х, = 0, х2= 6, х3= 8. Заметим, что в этом решении значение оценочной функции для третьего производителя меньше, чем фактическая стоимость 8 < s3(8) 16. Поэтому разбиваем второе подмножество на два подмножества Q2, и Q22. В первом из них х3<,8, а во втором х3г 8. Анализ подмножества Q2,. Оценочная функция третьего производителя имеет вид g^ Одно из оптимальных решений оценочной задачи х, = 0, х2= 8, х3= 6, s =28. Анализ подмножества Q22. Оценочная функция трсгьего производителя имеет вид %(х3)= х39 < х3< 10. Оптимальное решение оценочной задачи х, = 0, х2= 6, х3= 9, s =21и совпадает с фактической стоимостью. Заметим, что в данном случае центр закупает продукции больше, чем требуется, поскольку, закупая ровно 14 единиц, он в данном случае проигрывает. 75 76 Действительно, если центр закупает у второго производителя не 6 единиц, а 5, стоимость составит 5*3 = 15 единиц вместо 12, а если он закупает у третьего производителя не 9 единиц, а 8, то стоимость составит 8-2 = 16 единиц вместо 9. Сравнивая оценочные стоимости подмножеств Ql3 Q2, и Q22, выбираем подмножество с минимальной оценкой s(Q22)»2i. Соответствующее решение Xj = О, х2= 6, х39 является оптимальным, поскольку оценочная стоимость совпадает с фактической. На рис. 2.1.10 показано дерево ветвлений (разбиений множества всех решений на подмножества), вершины которого соответствуют подмножествам, а числа в вершинах оценочным стоимостям. Решая задачу при разных значениях V, мы получаем зависимость b(V). Далее задача решается также, как в случае одного производителя. Зависимость b(V) можно получить и на основе метода динамического программирования. Для применения метода динамического программирования упорядочим производителей произвольным образом, например, согласно их номерам. Пусть нам необходимо получить зависимость b(V) при 1 < V < 16. Берем первого производителя и определяем минимальные стоимости закупок у него продукции в количестве от 1 до 10 (больше у него нет). Эти данные помещены в табл. 2.1.6. Добавляем второго производителя и определяем минимальные стоимос ти закупок продукции у этих двух производителей в количестве от 1 до 16. Это делается следующим образом. Возьмем, например, заказ V-3. Его можно обеспечить четырьмя способами: все заказать у первого производителя (стоимость составит в(3) “ 18), заказать 2 единицы у первого и 1 единицу у второго (стой76 |