5. Обобщения и приложения

Задача раскраски в том «чистом» виде, в каком она рассматривалась выше в настоящей главе, редко встречается на практике. Однако ее обобщения и разновидности (незачительно отличающиеся от нее) находят широкое применение в большом числе различных прикладных задач. Целью данного раздела является ознакомление читателя с несколькими наиболее часто встречающимися обобщениями. Список приложений, естественно, этими примерами не ограничивается.

5.1. Простая задача размещения (загрузки) [6]

Рассмотрим задачу размещения (загрузки) каких-то предметов по ящикам. Пусть каждый предмет соответствует определенной вершине графа Всякий раз, когда два предмета не могут быть размещены в одном ящике (например, когда предмет может загрязнить предмет в граф вводится ребро Если ящики имеют неограниченную вместимость, так что в каждый из них можно поместить сколько угодно предметов, то задача нахождения наименьшего числа ящиков для размещения предметов эквивалентна задаче нахождения хроматического числа графа причем каждому ящику соответствует определенный «цвет», а предметы, окрашенные в один цвет, укладываются в один и тот же ящик.

(i) Ящики одинаковой вместимости. В действительности ящики обладают ограниченной вместимостью. Предположим, что вместимость одинакова у всех ящиков и равна Это можно интерпретировать так: в один цвет окрашиваются не более чем вершин. В терминах 0-1-программирования (см. разд. 3 настоящей главы) данная задача загрузки может быть сформулирована следующим образом:

Решением этой задачи является матрица описывающая оптимальное размещение (распределение) предметов по ящикам (иначе говоря, группировка предметов по цвету). Число есть верхняя оценка для числа ящиков.

(ii) Ящики имеют, вообще говоря, различные вместимости, и ящикам приписаны стоимости. Пусть ящик имеет вместимость и стоимость Предположим еще, что предметам

(вершинам графа) сопоставлены веса, скажем, предмету соответствует вес Требуется так разместить предметы по ящикам, чтобы

(а) выполнялись условия, «накладываемые» графом G,

(б) удовлетворялись ограничения на вместимость ящиков,

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

при ограничениях (4.11), (4.12) и

где переменная принимает значение 1, если в ящик помещен какой-либо предмет, и равна в противном случае. L - произвольное положительное целое число, большее, чем общее число имеющихся ящиков. Ограничение (4.18) означает, что ни один из ящиков не перегружается, а ограничение (4.19) гарантирует выполнимость условия: если (т. е. ящик пуст), то все также равны 0.

В этом самом общем случае необходимо было ввести дополнительные переменные поскольку ящики (цвета) нельзя штрафовать тем способом, который характеризуется выражением (4.14). Следует отметить, что чем более общей является задача, тем менее важным становится ее «раскрасочный» аспект. Так, например, в только что рассмотренной задаче можно выделить две подзадачи:

(а) о «раскраске», соответствующую ограничению (4.12), и

(б) о «ранце», определяемую ограничением (4.18). Два других ограничения, (4.11) и (4.19), являются ограничениями структурного характера.

Из-за этих двух взаимосвязанных аспектов общая задача раскраски значительно труднее для решения, чем «чистая» задача раскраски.

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