![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод потенциалов
Для определения оптимального плана транспортной задачи разработано несколько методов. Однако наиболее часто используются метод потенциалов и метод дифференциальных рент. Метод потенциалов. Общий принцип определения оптимального плана транспортной задачи методом потенциалов аналогичен принципу решения задачи линейного программирования симплексным методом, а именно: сначала находят опорный план транспортной задачи, а затем его последовательно улучшают до получения оптимального плана. Для определения опорного плана транспортной задачи будем пользоваться одним из методов, рассмотренных выше. Эти методы гарантируют получение занятых в исходном плане Теорема. Если для некоторого опорного плана
и
для всех Определение. Числа Сформулированная теорема позволяет построить алгоритм нахождения решения транспортной задачи. Он состоит в следующем. Пусть одним из рассмотренных выше методов найден опорный план транспортной задачи. Для каждого из пунктов отправления и назначения определяют потенциалы
где Так как число заполненных клеток равно
Если среди чисел Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде других занятых клеток и связанных с заполненной так называемым циклом. Определение. Циклом в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья – вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое – в столбце. Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами. Примеры некоторых циклов показаны на рис. 1. При правильном построении опорного плана для любой свободной клетки можно построить лишь один цикл. После того как для выбранной свободной клетки он построен, следует перейти к новому опорному плану. Для этого необходимо переместить грузы в пределах клеток, связанных с данной свободной клеткой. Это перемещение производят по следующим правилам: 1) каждой из клеток, связанных циклом с данной свободной клеткой, приписывают определенный знак, причем свободной клетке – знак плюс, а всем остальным клеткам – поочередно знаки минус и плюс (будем называть эти клетки минусовыми и плюсовыми); 2) в данную свободную клетку переносят меньшее из чисел В результате указанных выше перемещений грузов в пределах клеток, связанных циклом с данной свободной клеткой, определяют новый опорный план транспортной задачи. Описанный выше переход от одного опорного плана транспортной задачи к другому ее опорному плану называется сдвигом по циклу пересчета. Следует отметить, что при сдвиге по циклу пересчета число занятых клеток остается неизменным, а именно остается равным Полученный новый опорный план проверяют на оптимальность. Для этого определяют потенциалы пунктов отправления и назначения и находят числа Из изложенного выше следует, что процесс нахождения решения транспортной задачи методом потенциалов включает следующие этапы: 1. Находят опорный план. При этом число заполненных клеток должно быть равным 2. Находят потенциалы 3. Для каждой свободной клетки определяют число 4. Среди положительных чисел 5. Полученный опорный план проверяют на оптимальность, т.е. снова повторяют все действия начиная с этапа 2. В заключение отметим, что при определении опорного плана или в процессе решения задачи может быть получен вырожденный опорный план. Чтобы избежать в этом случае зацикливания, следует соответствующие нулевые элементы опорного плана заменить сколь угодно малым положительным числом Пример. Для транспортной задачи, исходные данные которой приведены в табл. 8.3, найти оптимальный план. Таблица 8.3
Решение. Сначала, используя метод северо-западного угла, находим опорный план задачи. Этот план записан в табл. 8.3. Найденный опорный план проверяем на оптимальность. В связи с этим находим потенциалы пунктов отправления и назначения. Для определения потенциалов получаем систему
содержащую шесть уравнений с семью неизвестными. Полагая Так как среди чисел
Таблица 8.4
После этих преобразований получаем новый опорный план (табл. 8.5).
Таблица 8.5
Этот план проверяем на оптимальность. Снова находим потенциалы пунктов отправления и назначения. Для этого составляем следующую систему уравнений:
Полагаем Таким образом, видим, что данный план перевозок не является оптимальным. Поэтому переходим к новому опорному плану (табл. 8.6). Таблица 8.6
Сравнивая разности является оптимальным. При данном плане стоимость перевозок
Контрольные вопросы: 1. Сформулируйте условие оптимальности. 2. Что такое контур, цена цикла? 3. Опишите метод потенциалов.
|