Решение транспортных задач методом потенциалов (стр. 1 из 8)
Решение транспортных задач методом потенциалов
Содержание
1.Теоретические основы метода 4
3.Метод потенциалов и метод последовательного улучшения плана 18
4. Алгоритм метода потенциалов 22
5. Руководство пользователя. 29
Введение
Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.
Кроме того, к задачам транспортного типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.
Формальным признаком транспортной задачи является то, что каждая переменная входит лишь в два ограничения, причем с коэффициентами, равными единице. Если при этом критерий оптимальности (сумма расходов, общий пробег) прямо пропорционален значениям переменных (транспортных потоков), возникает линейная транспортная задача. В других случаях рассматривается нелинейная транспортная задача, решаемая другими методами.
Метод потенциалов – первый точный метод решения транспортной задачи – был предложен в 1949 г. Л.В. Канторовичем и М. К. Гавуриным. По существу этот метод является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данцигом, который исходил из общих идей линейного программирования. В американской литературе метод потенциалов принято называть модифицированным распределительным методом. Метод потенциалов позволяет, отправляясь от некоторого опорного плана перевозок, построить решение транспортной задачи за конечное число итераций (шагов).
Цель курсовой работы:
Освоить математическую постановку решения транспортной задачи методом потенциалов.
Теоретические основы метода
Метод потенциалов позволяет, отправляясь от некоторого опорного плана перевозок, построить решение транспортной задачи за конечное число итераций (шагов). Общая схема отдельной итерации состоит в следующем. По данному опорному плану каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Предварительные потенциалы выбираются так, чтобы их разность для любой пары пунктов
, 
, связанных основной коммуникацией, была равна 
– стоимости перевозок между этими пунктами единицы продукта.Если разность предварительных потенциалов для каждой пары пунктов
, не превосходит 
, то данный план перевозок – решение задачи, а сами предварительные потенциалы – потенциалы задачи (или оценки ее условий).В противном случае указывается способ получения нового опорного плана, связанного с меньшими транспортными издержками. Через конечное число итераций процесс решения завершается построением оптимального плана и системы потенциалов задачи.
Перед тем как начать детальное рассмотрение метода потенциалов, естественно вернуться к понятию потенциала.
Пусть
- произвольный план задачи T. Элемент матрицы транспортных издержек 
будем называть Х- существенным, если 
, т.е. если 
- основная коммуникация плана Х.Функция W, определенная на совокупности пунктов производства и потребления задачи T, была названа вектором потенциалов или просто потенциалом данной задачи, если
(1.1) 
(1.2)для всех Х-существенных элементов некоторого плана X. Будем называть план X потенциальным, если существует потенциал задачи T, связанный с этим планом условием (1.2). Между оптимальностью и потенциальностью планов задачи T существует тесная связь. Для оптимальности плана X необходима и достаточна его потенциальность.
Заметим, что потенциал вовсе не следует считать зависящим от конкретного оптимального плана задачи T. Каждый потенциал задачи T связан условием (1.2) с любым ее оптимальным планом (естественно, что это утверждение имеет нетривиальный смысл лишь для транспортных задач с неединственным решением). Поэтому функция W может быть определена еще и так: W – потенциал задачи T, если
причем для тех
, которые являются Х-существенными элементами некоторого оптимального плана X этой задачи, соответствующие неравенства переходят в равенства. Итак, функция W определяется множеством оптимальных планов данной задачи.Напомним, что значения потенциала W в пунктах задачи T были названы потенциалами этих пунктов. Выбор этого термина можно оправдать следующей аналогией.
Представим себе, что некую единичную массу необходимо перенести из точки
в точку 
. Величина работы, которую необходимо совершить при переносе массы из 
в 
, задана и равна 
(работа, совершаемая при движении от к , предполагается равной - ). Условимся, что непосредственное движение от к (или наоборот) возможно только в случае, если 
- допустимая коммуникация задачи T. Пусть движение от 
к 
запланировано следующим образом: 
.Тогда производимая при этом работа A вычисляется по формуле
.Используя теперь свойства потенциала задачи T, имеем
Итак, разность
совпадает с количеством работы, необходимым для переноса единичной массы из 
в 
. При этом выполняется основное свойство движения в потенциальном поле: величина работы, производимой при перемещении некоторой массы, не зависит от формы возможного пути, связывающего рассматриваемые точки, а определяется лишь самими точками. Заметим, что в силу (1.1) непосредственное движение от в всегда связано с неменьшей работой по сравнению с движением между этими точками по любому из допустимых маршрутов.Метод потенциалов состоит из конечного числа однотипных итераций. Каждая итерация разбивается на два этапа. На первом этапе план, полученный в результате предыдущих итераций, проверяется на оптимальность. Если план оказывается решением задачи, процесс заканчивается. Если же это не так, осуществляется переход ко второму этапу. На втором этапе строится новый план перевозок, который в невырожденном случае связан с меньшими транспортными издержками.
Опишем отдельную итерацию метода, ограничившись вначале невырожденным случаем. Итак, допустим, что уже проведено k итераций метода потенциалов и в результате получен опорный план
. Разберем подробно очередную, 
- ю итерацию.