8.6.2. Задача из области производства бумаги

Предприятие должно выполнить заказ по производству различных сортов бумаги. Каждый из сортов может быть получен на любой одной из М бумагоделательных машин. Из-за высокой стоимости изменения состава бумажной массы каждый сорт бумаги должен быть обязательно произведен целиком на одной и той же машине. Известно количество бумаги в тоннах которое нужно произвести для каждого сорта при условии, что максимальная производительность каждой машины составляет т. И наконец, известна полная стоимость производства бумаги сорта на машине для каждой пары Требуется в указанных условиях организовать производство с наименьшими затратами.

Примем следующие числовые данные (реальный случай, предложенный Н. Sandi): сортов, машины. На входном языке ALICE задача формулируется сразу:

Формулировка задачи:

(см. скан)

Первая фаза. В самом начале первой фазы программа пытается определить, существует ли реализуемое решение, т. е. функция производства удовлетворяющая всем ограничениям, кроме оптимизации:

Ограничение, накладываемое на производительность определяет необходимое условие выполнимости задачи, которое достигается путем распространения этого ограничения на все множество машин. Из него получаем

С приведенными числовыми значениями обе эти суммы совпадают, их значения равны 42. Из этого программа делает выводы:

1) Нельзя заранее сказать о невозможности решения задачи.

2) Для всех знак должен быть заменен на строгое равенство, исключение недопустимо.

3) Тем не менее определенные назначения запрещены в тех случаях, когда значение превышает связанное с ним значение Для таких случаев имеем

Из этого следует, что Больше здесь ничего сделать нельзя, и программа должна сделать выбор. Выбор но ограничению ИЛИ не может быть выполнен, так как не имеется ни одного ограничения такого типа. Выбор по малым значениям в принципе возможен, но исключается программой, которая считает пространство поиска достаточно малым для того чтобы сделать более точный выбор типа Напомним критерии, которыми здесь располагает программа для определения выбора.

Критерии для выбора в предшествующей вершине

преемников

разъединений

число ограничений с i

трудности ограничений

коэффициентов

оценки

отрыва

значимости

При каждом выборе программа начинает определять рассматриваемый сорт бумаги в зависимости от этих критериев. Три критерия — с и — исключаются сразу как не имеющие отношения к данной задаче: связанные значения являются и останутся в дальнейшем нулевыми для всех Затем на первой фазе отвергаются критерии оптимизации

Остаются два критерия — а и е. Распределение значений для критерия является менее значимым, чем для критерия а. Действительно, только сорт 3 имеет двух преемников и распределение для этого критерия имеет вид Итак, с помощью критерия выделяется сорт бумаги 3, которому этот критерий оказывает предпочтение перед сортами 2, 7 и 9. Выбор машины происходит с помощью следующего набора критериев:

Критерии для вершины-преемника

число возможных предшественников

число действительных предшественников

численное значение, связанное с j

коэффициент для

Критерий а не совсем пригоден, так как выделяет от 10 до 6 предшественников. Критерий для первого выбора вообще не

принимается во внимание, так как дает нулевые результаты; Критерий 7 относится к оптимизации и также не пригоден для данного случая. Подходящим оказывается только критерий который относится к коэффициенту для присутствующему в данной совокупности ограничений.

Для облегчения решения задачи с учетом коэффициента который является вторым членом равенства, программа оставляет максимально возможную свободу для и сохраняет максимальное значение Таким образом, первые рассмотренные программой критерии для выбора и предусматривают следующее: разместить производство наиболее трудного сорта бумаги (критерий е) на наименее загруженной машине (критерии 6), т. е. производство бумаги сорта 3 на машине 3:

Выбор

Реальная производительность этой машины уменьшается до

10. Никаких других вариантов не просматривается. Для того чтобы сделать выбор 2, программа опять последовательно анализирует подходящие критерии и на первое место перед критерием а выходит критерий так как распределение становится следующим: Выбирается сорт бумаги 9. Критерии отдают равное предпочтение двум машинам — 2 и 3. Окончательно их выделяет критерий с точки зрения решения хорошей стратегией для учета ограничений на первой фазе является максимально возможное снятие ограничений с изображения. Машина 2 еще не загружена, поэтому делается следующий выбор:

Выбор

Таким образом, реальная производительность машины 2 становится равной 2, а программа, для того чтобы выполнить ограничение должна запретить на этой машине производство Других возможностей не имеется и третий выбор опять ставит на первое место критерий а, поскольку два сорта бумаги — 2 и 7 — снова имеют не более двух преемников. Их нельзя выделить на основе критерия с помощью которого в обоих случаях получается значение 5. В конце концов вступает в действие критерий и программа выбирает такие сорта бумаги, производство которых во всех

случаях обходится дороже. Итак, третий выбор программы:

Выбор для стоимости, равной 9.

Итак, возможность производства на машине 1 уменьшилась до 4 и программа далее выбирает , следовательно, Четвертый выбор происходит с использованием тех же самых критериев. Нужно разместить производство бумаги сорта

6, и критерий оказывает одинаковое предпочтение сразу двум машинам —1 и 4, — стоимости выполнения работ на которых равны 15. Выбирается машина 1 как менее загруженная (критерий 6)

Выбор .

Как показано выше, ограничения на производительность являются равенствами и единственный сорт бумаги обладает единичным значением которое соответствует остаточной производительности машины 1. Отсюда сразу получаем . Итак, для сорта 8 наименее дорогой машиной является машина 4:

Выбор

Использование машины 4 запрещается, поскольку обязательным условием является Для двух оставшихся сортов, задания для которых равны 2, полезным критерием является с помощью которого получаем Выбор

Отсюда окончательно находим . Таким образом, полное найденное решение

имеет полную стоимость, равную 99.

Вторая фаза. Получив подобное решение всего лишь после шести выборов и без возвращений назад, на второй фазе программа предпринимает попытку получить “хорошее” решение. Для этого она использует критерии, которые связаны со стоимостью и вначале были отвергнуты. Так, если сорт бумаги, определенный в результате первого выбора по тем же причинам, по-прежнему равен 3, то машина, на которой предполагается его выпускать, выбирается программой исходя из наименьшей стоимости производства (критерий

Выбор

Этот выбор совпадает с предыдущим, однако затем:

Выбор так как именно первая машина дает для этого сорта наименьшую стоимость производства. Далее с необходимостью следует

и применение критерия приводит к следующей последовательности выборов:

откуда следует

Новое решение, полученное с помощью критериев оптимизации, существенно лучше старого:

Полная стоимость производства равна 84.

Третья фаза. Все проделанное до сих пор не является бесполезным, но как получить действительно оптимальное решение? Проследим за дальнейшим ходом действий ALICE. Каждый сорт бумаги должен иметь изображение поэтому выражение функции стоимости

показывает, что величина во всех случаях превышает сумму минимальных значений коэффициентов для каждого сорта бумаги Обозначим эту величину через

и напомним еще раз, что Но программа, кроме того, выполняет преобразование стоимостей, вычитая из всех значений стоимость производства бумаги сорта столбец таблицы; для программы — это совокупность дуг, исходящих из — минимальную стоимость для этого сорта. Тогда новые стоимости получают следующие значения:

Сумма вычтенных величин Точное соотношение принимает вид

Лучшее известное решение , Поскольку все положительны по определению, имеем

где — искомое оптимальное значение.

ALICE исключает все значения стоимости, строго превышающие которые не могут дать такого же хорошего решения, как в фазе 2. Дуга для данного случая проходит через точки (10,4) и определяет стоимость, уменьшенную до

19. Других вариантов нет, и первый выбор ALICE делает с помощью критерия оптимизации - максимума отрыва. При этом выбирается дуга нулевой стоимости, так как в противном случае стоимость оказалась бы максимальной. Значения отрывов в данном случае равны просто следующим после минимальных значений стоимости в каждом столбце:

Таким образом, первый выбор в последней фазе:

Выбор

т. е. все три различных критерия дают один и тот же результат. Затем тот же критерий дает:

Выбор

Отсюда следует для всех остальных сортов бумаги. В частности, запрещено сведение к нулю стоимостей для сортов

4, 5 и вычитает иовые минимумы из столбцов 1, 7 и 5, что при двух сделанных предположениях (Выбор 1, Выбор 2) дает для значения нижней границы

Приведенные стоимости, строго превышающие 3, необходимо исключить, так как с их помощью нельзя получить решение, удовлетворяющее программу. Остается

Из сделанных исключений следует и таким же образом выполняется третий выбор:

Выбор

Из ограничения на объем производства следует, что Таким образом, для этого сорта бумаги требуется новое вычитание. В результате становится равным

хотя разрешены только нулевые и единичные стоимости. В частности, следовательно, Затем

Выбор

из которого следует

Отсюда

Из этого в свою очередь следует:

Отсюда

Это в конце концов дает решение стоимостью 82.

• Доказательство оптимальности

Теперь для ALICE остается только еще раз вернуться к сделанным четырем выборам для доказательства их оптимальности или найти лучшее решение.

Выбор Анализ этого выбора является тривиальным. Поскольку известно решение стоимостью 82, подходящим оказывается только нулевой отрыв, следовательно, необходимо принять так как в этом случае отрыв равен 1.

Рис. 8.11. (см. скан) Оптимальное решение стоимостью 82.

Выбор . В данном случае верхняя граница равна 80, а отрыв равен 3. Этот выбор приводит к шагу назад.

Выбор Верхняя граница равна 67, а связанный с ней отрыв равен 8. Исследуется случай При этом величина (выбор 1) принимает значение Поскольку существуют еще три другие возможности размещения производства бумаги сорта 1, то ALICE приступает к повторному изучению ситуации. Дуги (10, 1) и (10, 3) исключаются, из чего следует Также исключаются дуги что дает

Ограничение по производительности приводит к При этом четвертая машина полностью загружена, следовательно, Но так как действует ограничение по стоимости, то

Отсюда следует, что

Таким образом, завершить решение нужно только с помощью дуг стоимостью ниже 2. Но так как оставшаяся производительность первой машины является недостаточной для

этого сорта бумаги и, следовательно, таким путем завершить решение задачи нельзя. Тогда остается только первый выбор: Выбор

Остается единственная возможность сделать Запрещены все стоимости, превышающие частности, необходимо сделать одновременно Эти два условия несовместимы, так как предполагают общее производство 5 единиц на машине, которая способна не больше 3, т. е. невозможно получить решение стоимостью меньше 82. Окончательный вид дерева поиска представлен на рис. 8.11, который показывает оптимальность полученного решения.