Содержание

Введение

 

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

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

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

    Метод потенциалов – первый точный метод решения транспортной задачи – был предложен в 1949 г. Л.В. Канторовичем и М. К. Гавуриным. По существу этот метод является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данцигом, который исходил из общих идей линейного программирования. В американской литературе метод потенциалов принято называть модифицированным распределительным методом. Метод потенциалов позволяет, отправляясь от некоторого опорного плана перевозок, построить решение транспортной задачи за конечное число итераций (шагов).

    Цель  курсовой работы:

    Освоить математическую постановку решения  транспортной задачи методом потенциалов. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

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

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

    Перед тем как начать детальное рассмотрение метода потенциалов, естественно вернуться  к понятию потенциала.

    Пусть - произвольный план задачи 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 итераций метода потенциалов и  в результате получен опорный  план . Разберем подробно очередную, - ю итерацию.

    Этап 1. На этом этапе производится исследование плана на оптимальность. Обозначим через совокупность - существующих элементов матрицы С, т.е. таких , которым соответствуют , и определим величины (предварительные потенциалы), удовлетворяющие системе уравнений

                                    для всех .                                  (1.3)

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

    Зададимся значением одной из неизвестных  систем (1.3), например положим . Допустим, что пункт снабжает в соответствии с планом пункты . Тогда из соответствующих уравнений системы (1.3) определяем

    

.

Далее аналогичным способом определяем значения для тех , которые снабжают один из пунктов . Например, если снабжает пункт , то

    

.

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

    Если  предварительные потенциалы , таковы, что для любой пары i, j имеет место неравенство

    

,

то функция  W, определяемая условиями - потенциал задачи T и, следовательно, , будучи потенциальным, является вместе с тем и оптимальным планом исследуемой задачи.

    Если  же для некоторых индексов i, j

    

,

то план не оптимален. Необходим переход к этапу 2, на котором этот план будет улучшен.

    Этап 2. Вычислим уклонения

    

( ).

По условию  среди чисел  имеются отрицательные. Определим пару индексов из условия

    

.

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

    

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

    

.

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

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

    

,

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

    

.

Вспомним, что все элементы, стоящие в  квадратной скобке, кроме  , являются - существенными. Поэтому