Решение транспортных задач методом потенциалов

Решение транспортных задач методом потенциалов

Содержание

Содержание 1

Введение 1

1.Теоретические основы метода 4

2.Вырожденность. 12

3.Метод потенциалов и метод последовательного улучшения плана 18

4. Алгоритм метода потенциалов 22

5. Руководство пользователя. 29

Заключение. 30

Введение

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

Кроме того, к задачам транспортного типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.

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

Метод потенциалов – первый точный метод решения транспортной задачи – был предложен в 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 были названы потенциалами этих пунктов. Выбор этого термина можно оправдать следующей аналогией.

Представим себе, что некую единичную массу необходимо перенести из точки в точку . Величина работы, которую необходимо совершить при переносе мас

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать