Методы решения задачи оптимального закрепления операций за станками

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

А) Метод северо-западного угла

Б) Метод наименьших затрат

В) Метод аппроксимации Фогеля

Как нам известно, число переменных Хij в задаче с т количеством станков и п количеством операций равно пт, а число уравнений в системах равно п + т. Так как мы предполагаем, что выполняется условие равности потребности в операциях количеству станков, то число линейно независимых уравнений равно п + т - 1. Следовательно, опорный план задачи может иметь не более п + т - 1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности п + т - 1, то план является невырожденным, а если меньше - то вырожденным. транспортный задача оптимальный закрепление

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

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

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

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

Перейдем к характеристике каждого из методов нахождения оптимального плана закрепления операций за станками:

А) Метод северо - западного угла.

При нахождении опорного плана задачи методом северо-западного угла на каждом шаге рассматривают первую из оставшихся операций и первый из оставшихся станков. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного Х11 («северо-западный угол») и заканчивается клеткой для неизвестного хтп, т. е. идет как бы по диагонали таблицы.