5. Лабораторная работа оптимальное распределение технологического оборудования лесопромышленных предприятий

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

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

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

РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ ВЕНГЕРСКИМ МЕТОДОМ

5.1. Описание алгоритма венгерского метода.

Введем следующие определения:

1. Нулевые элементы Z₁, Z₂, ..., Z_k квадратной матрицы С будем называть независимыми нулями, если для любого 1 ≤ i ≤ k строка и столбец, на пересечении которых лежит элемент Z_i, не содержит элементов Z_k для всех k≠i.

2. Две прямоугольные матрицы С = (c_ij) и С"= (с"_ij) размером mxn назовем эквивалентными (С~С"), если с"_ij = с_ij + α_i +β_j; i =1, 2, ..., m; j = 1, 2, ..., n. Задачи выбора, определяемые эквивалентными матрицами, являются эквивалентными, так как можно доказать, что множества оптимальных назначений двух задач выбора с эквивалентными матрицами совпадают.

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

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

Предварительный этап. На этом этапе выполняются два после­довательных преобразования матрицы С, в результате которых получается эквивалентная ей неотрицательная матрица С˝ в каждом столбце и каждой строке которой есть хотя бы один нуль.

Первое преобразование проделывается со всеми столбцами мат­рицы С. Из максимального элемента j-го столбца (i = 1, 2, ..., n) вычитаются элементы этого столбца:

Полученная матрица С΄ является неотрицательной, и в каждом столбце этой матрицы имеется хотя бы один нуль.

Второе преобразование производится со строками матрицы С΄. Из элементов i-й строки матрицы С΄ вычитается минимальный элемент этой строки:

Если в каждой строке матрицы С' = (c΄_ij), полученной после пер­вого преобразования матрицы С, уже имеется хотя бы один нуль, то второе преобразование не производится.

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

Отмечаем произвольный нуль в первом столбце звездочкой (*). Затем просматриваем второй столбец, и если в нем есть нуль, расположенный в строке, где нет 0*, то отмечаем его звездочкой. Аналогично просматриваются один за другим все остальные стол­бцы матрицы C˝. Очевидно, что нули матрицы C˝, отмеченные звездочкой, по построению являются независимыми.

(k + 1)-я итерация

Допустим, что k-я итерация проведена и в результате получена матрица С_к. Если в матрице С_к имеется ровно n нулей со звездоч­кой, то процесс решения заканчивается. Если же число нулей со звездочкой меньше n, то переходим к (k + 1)-й итерации. Каждая итерация начинается первым и заканчивается вторым этапом. Между ними может несколько раз проводиться пара этапов: третий—первый. Перед началом итерации знаком «+» выделяют столбцы матри­цы С_k, которые содержат нули со звездочкой.

Первый этап. Просматривают невыделенные столбцы матри­цы С_k. Если среди них не окажется нулевых элементов, то перехо­дят к третьему этапу. Если же невыделенный нуль матрицы С_k об­наружен, то возможен один из двух случаев: а) строка, содержа­щая невыделенный нуль, содержит также нуль со звездочкой; б) эта строка не содержит нуля со звездочкой.

В случае (а) невыделенный нуль отмечают штрихом и выделяют строку, в которой он содержится, знаком «+» справа от нее. Затем уничтожают знак «+», обводя его рамкой, над тем столбцом, на пересечении которого с данной выделенной строкой содержится нуль со звездочкой. Далее опять просматривают невыделенные стол­бцы, отыскивая в них невыделенные нули. Этот процесс за конеч­ное число шагов заканчивается одним из следующих исходов:

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

IB — все нули матрицы С_k выделены, т. е. находятся в выделен­ных строках или столбцах. При этом переходят к третьему этапу.

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

Второй этап. Строят следующую цепочку из нулевых элементов матрицы С_k. отмеченный последним нуль со штрихом, нуль со звездочкой, расположенный в одном столбце с ним, нуль со штри­хом, расположенный в одной строке с предшествующим нулем со звездочкой, и т. д. Итак, цепочка образуется передвижением от О' к 0* по столбцу, от 0* к 0' по строке и т. д.

Можно доказать, что описанный алгоритм построения цепочки однозначен и конечен. При этом цепочка всегда начинается и закан­чивается нулем со штрихом (возможно, она будет состоять из од­ного нуля со штрихом). Далее, над элементами цепочки, стоящими на нечетных местах (0'), ставят звездочки, уничтожая их над чет­ными элементами (0*). Затем уничтожают все штрихи над элемен­тами матрицы С_k и знаки «+». При этом количество независимых нулей будет увеличено на единицу; (k+1)-я итерация закончена.

Третий этап. К этому этапу переходят после первого, если все нули матрицы С_k выделены, т. е. находятся в выделенных строках или столбцах. В таком случае среди невыделенных элементов мат­рицы С_k выбирают минимальный и обозначают его h > 0. Далее величину h вычитают из всех элементов матрицы С_k, располо­женных в невыделенных строках, и прибавляют ко всем элемен­там, расположенным в выделенных столбцах. Получают новую мат­рицу С_k⁽¹⁾, эквивалентную С_k.

Поскольку среди невыделенных элементов матрицы С_k⁽¹⁾, появятся новые нули (согласно определению), переходят к первому этапу, при этом вместо матрицы С_k рассматривают матрицу С_k⁽¹⁾. Завершив первый этап, либо переходят ко второму этапу, либо вновь возвращаются к третьему этапу, если все нули матрицы С_k⁽¹⁾ оказываются выделенными.

После конечного числа построений очередной первый этап обязательно закончится переходом на второй этап и количество независимых нулей увеличится на единицу, т. е. (k+1)-я итерация будет завершена.