|
61 Рассмотрим второе подмножество. Так как заказ у второго производителя в этом подмножестве решений не менее трех единиц, то оценочная функция при Х2 ^ 3 будет иметь вид, показанный на рис. 2.2.7. Опишем более подробно алгоритм решения оценочной задачи. Начинаем с минимальных заказов у каждого производителя, то есть Xi = О, Х2 = 4 (поскольку оценочная стоимость заказа Х2 = 4 меньше, чем у заказа Х2 = 3). Сравнивая цены при небольшом увеличении заказов видим, что дополнительный заказ выгоднее делать у первого производителя (ь, =i ), а не у второго (Ьг=2 ). Поэтому оптимальное решение оценочной задачи xi = И , Х2 = 4, а минимальная оценочная стоимость составляет 19 единиц. Х 2 Сравнивая оценочные стоимости двух рассмотренных вариантов, мы видим, что во втором варианте она меньше. Поэтому выбираем вариант с меньшей оценочной стоимостью. Заметим теперь, что фактическая стоимость в решении Х) = 11, хг = 4 совпадает с оценочной. Поэтому полученное решение является оптимальным решением всей задачи. Рассмотрим более сложный пример для иллюстрации эффективности метода ветвей и границ. Пример 2.2.2. Имеются три производителя, данные о которых приведены в табл. 2.2.5. Пусть V = 14, а каждый производитель имеет не более 10 единиц продукции. Для оценочной задачи на первом шаге имеем: si(xi) = 3xi, |
73 ЛИНИЯМИ. Решим задачу минимизации суммы оценочных функций. Это задача линейного (в общем случае выпуклого) программирования, для которой существуют эффективные методы решения. В нашем случае решение очевидно. Нужно заказать все имеющееся количество продукции Xj = 12 у первого производителя по цене b, = 1, а остальные х2= Зединицы у второго, по цене Ь2= 2. Стоимость заказа составит 18 единиц. Заметим, что фактическая стоимость такого заказа составляет 12 + 3-5 = 27 единиц, поскольку при заказе у второго производителя трех единиц продукции цена составит 3 единицы. Рассмотрим теперь два варианта. В первом варианте заказ у второго производителя не превышает трех единиц, а во втором не меньше трех единиц, то есть разобьем множество всех решений на два подмножества. Рассмотрим первое подмножество. Поскольку заказ у второго производителя не превышает трех единиц, то его оценочная функция будет уже другой, а именно, ^(х2)= 5х2. Оптимальное решение оценочной задачи остается прежним: Xj 12, х2в 3. Однако, оценка стоимости заказа будет равна уже не 18, а 27, что совпадает с фактической стоимостью. Рассмотрим второе подмножество. Так как заказ у второго производителя в этом подмножестве решений не менее трех единиц, то оценочная функция при х2£ 3 будет иметь вид, показанный на рис. 2.1.8. Опишем более подробно алгоритм решения оценочной задачи. Начинаем с минимальных заказов у каждого производителя, то есть х* = 0, х2 = 4 (поскольку оценочная стоимость заказа х2= 4 меньше, чем у заказа х2 = 3). Сравнивая цены при небольшом увеличении заказов видим, что дополнительный заказ выгоднее делать у первого производителя (ь, =1), а не у второго (ь2^2). Поэтому оптимальное решение оценочной задачи х, = 11, х2= 4, а минимальная оценочная стоимость составляет 19 единиц. 73 74 Сравнивая оценочные стоимости двух рассмотренных вариантов, мы видим, что во втором варианте она меньше. Поэтому выбираем вариант с меньшей оценочной стоимостью. Заметим теперь, что фактическая стоимость в решении х, = И, х2= 4 совпадает с оценочной. Поэтому полученное решение является оптимальным решением всей задачи. Рассмотрим более сложный пример для иллюстрации эффективности метода ветвей и границ. Имеются три производителя, данные о которых приведены в таблице 2.1.5. Пусть V = 14, а каждый производитель имеет не более 10 единиц продукции. Для оценочной задачи на первом шаге имеем: s,(x,) = Зх,, s2(x2) = 2хг, s3(x3) = х3. Решение оценочной задачи, очевидно, х, = 0, х2= 4, х3= 10, I— 18. Поскольку %(4)= 8 < s2(4) = 12, то рассматриваем два подмножества решений Qrи Q2. В первом подмножестве х, < 4, а во втором х2> 4. Таблица 2.1.5 1 производитель V, 5 8 10 ь, 6 5 3 2 производитель V2 3 6 10 Ъ2 5 3 2 3 производитель V3 4 . 9 10 Ьз 4 2 1 Анализ первого подмножества. Оценочная функция для первого производителя будет уже другой %(х2>= Зх2, Оптимальное,решение оценочной зада74 |