3.2.6. Целочисленные модели

Результаты решений многих задач, стоящих перед строителями, должна быть. выражены в целых числах (например, определение оптимального количества заводов, являющихся поставщиками строительных конструкций или числа монтажных кранов и т.д.). Но если даже в простую задачу линейного программирования внести дополнительное требование целочисленности неизвестных (х = 1,2,3 и т.д.), то решать ее обычными методами уже нельзя. На первый взгляд кажется, что можно легко выйти из положения, округлив полученное каким-либо методом решение. Но что может означать к примеру 2, 3 дома? Надо строить 3 дома? Это решение невозможно, либо возможно осуществить за счет уменьшения других показателей плана. Найти целочисленный оптимальный план - задача непростая. Для решения ее требуется применение довольно тонких специальных математических методов (например, метод "Гомори", основанный на идеях симплекс-метода)

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

Пример. Пусть имеется необходимость перебросить пять строительных бригад к месту строительства пяти различных объектов.

Под назначением понимается факт приписки бригады к одному из объектов

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

Представим время доставки i-ой бригады в j-ый пункт назначения и виде табл.3.

Таблица 3

Таблица 4

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

Алгоритм решения может быть представлен в виде этапов.

Этап 1. Образование нулей.

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

Таблица 5 Таблица 6

Этап 2. Поиск возможного оптимального решения

Оптимальное решение в данной постановке означает, что все затраты имеют нулевое значение. Если такое решение найти не удалось, то следует перейти к третьему этапу. Последовательность действий при поиске оптимального решения состоит в следующем. Анализ табл.6 начинается с выявления строк, содержащих минимальное число нулей, при этом один из нулей такой строки обводится квадратиком. Затем вычеркиваются все остальные нули, находящиеся в этой строке. Процесс продолжается до тех пор, пока в таблице все нули будут либо обведены квадратиками, либо вычеркнутыми. На данном этапе оптимального решения получить не удалось, так как во второй строке таблицы нет нулевого элемента.

Возьмем, например, элемент = 5, тогда решение будет иметь вид:

= 5 + 0+0 + 0 + 0 = 5,

а это решение не оптимально (см. табл.4).

Этап 3. Образование набора строк и столбцов, содержащих все нули, имеющиеся в таблице (см. табл.5)

Последовательность действий:

1 .Пометим крестиком (х) строки, не содержащие ни одного обведенного квадратиком нуля. В нашем случае строка 2.

2.Отметим каждый столбец, содержащий зачеркнутый нуль хотя бы одной из помеченных строк. В нашем случае 5-ый столбец.

3. Пометим каждую строку, в которой содержится обведенный квадратиком нуль хотя бы в одном из помеченных столбцов. В нашем случае строка 1

4.Далее повторяем перечисленные действия 2 и 3 пока не останется строк и столбцов, которые еще можно пометить. Переходим к этапу 4.

Этап 4. Завершение этапа 3

Прочеркнем каждую непомеченную строку и каждый помеченный столбец (см. табл.5). Прочеркнем строки 3, 4, 5 и 5-ый столбец. Переходим к этапу 5.

Этап 5. Добавление нулей

В части таблицы, состоящей из неперечеркнутых элементов, выберем наименьший элемент (см.табл.5). Это будет элемент 1-ой строки, равный 1. Вычтем этот элемент из всех элементов столбцов 1, 2, 3, 4, 5 и прибавимего ко всем элементам перечеркнутых строк, т.е. строк 3, 4, 5. В результате получаем табл.6.

Этап 6. Получение оптимального решения или переход к этапу 3

Оптимальное решение определяется в последовательности, описанной в этапе 2. Повторив этап 2, получим таблицу 6. В табл. 6 нули, обведенные квадратиками, образуют оптимальное решение:

= 3+1+1+2+1=8,