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

Б) Метод минимального элемента.

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

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

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

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

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

А) Метод потенциалов

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

Для определения опорного плана транспортной задачи будем пользоваться одним из методов, рассмотренных выше. Эти методы гарантируют получение занятых в исходном плане п+т-1 клеток, причем в некоторых из них могут стоять нули. Полученный план следует проверить на оптимальность.

Если для некоторого опорного плана задачи существуют такие числа что:

при (8)

при (9)

для всех и , то Х* = () - оптимальный план решаемой задачи.