Основы систем автоматизированного проектирования в сварке: Учеб. пособие
Внимание! эта страница распознана автоматически, поэтому мы не гарантируем, что она не содержит ошибок. Для того, чтобы увидеть оригинал, Вам необходимо
Если Вы являетесь автором данной книги и её распространение ущемляет Ваши авторские права или если Вы хотите внести изменения в данный документ или опубликовать новую книгу свяжитесь с нами по по .
Страницы: 1 2 3... 129 130 131 132 133 134 135... 264 265 266
|
|
|
|
5.4. Транспортная задача 131 5.4.2. Задача о назначениях Частным случаем транспортной задачи является задача о назначениях, в которой число пунктов производства равно числу пунктов назначения, т.е. транспортная таблица имеет форму квадрата. Кроме того, в каждом пункте назначения объем потребности равен 1, и величина предложения каждого пункта производства равна 1. Любая задача о назначениях может быть решена с использованием методов линейного программирования или алгоритма решения транспортной задачи. Однако ввиду особой структуры данной задачи был разработан специальный алгоритм, получивший название Венгерского метода. Этот алгоритм состоит из трех этапов. Этап 1: 1. формализация проблемы в виде транспортной таблицы по аналогии с решением транспортной задачи; 2. в каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки; 3. повторить ту же самую процедуру для столбцов. Теперь в каждой строке и в каждом столбце таблицы есть, по крайней мере, один нулевой элемент. Представленная в виде полученной с помощью описанного выше приема "приведенной" транспортной таблицы задача о назначениях эквивалента исходной задаче, и оптимальное решение для обеих задач будет одним и тем же. Сущность Венгерского метода заключается в продолжении процесса приведения матрицы до тех пор, пока все подлежащие распределению единицы не попадут в клетки с нулевой стоимостью. Это означает, что итоговое значение приведенной целевой функции будет равно нулю. Так как существует ограничение на неотрицательность переменных, нулевое значение целевой функции является оптимальным.
Карта
|
|
|
|
|
|
|
|
Страницы: 1 2 3... 129 130 131 132 133 134 135... 264 265 266
Внимание! эта страница распознана автоматически, поэтому мы не гарантируем, что она не содержит ошибок. Для того, чтобы увидеть оригинал, Вам необходимо скачать книгу |
