Содержание

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

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

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

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

5     Руководство пользователя. 32
Заключение. 33

Список  литературы.. 34

Введение

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

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

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

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

().

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

.

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



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

.

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

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

,

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

.

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

.

Учитывая далее отрицательность уклонения  и положительность , имеем



.

Итак, составленный новый план перевозок , соответствующий меньшему значению линейной формы транспортной задачи. Этап 2, а вместе с ним и -я итерация закончены.

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

                            ,  ,                    (1.4)

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

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

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

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

Алгоритм метода потенциалов складывается из предварительного этапа и конечного числа однотипных итераций. На предварительном этапе строится исходный опорный план  задачи T и составляется матрица

,

где  и  - предварительные потенциалы, отвечающие исходному плану .

На каждой итерации рассматриваются и преобразуются две матрицы

и .

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



где  и  - предварительные потенциалы, отвечающие плану .

Вначале будем предполагать задачу T невырожденной. Необходимые замечания относительно вырожденного случая будут сделаны ниже.

Предварительный этап. С помощью метода северо-западного угла или метода минимального элемента определяется исходный опорный план  исследуемой задачи T. Далее, согласно правилам, изложенным при описании 1-го этапа метода потенциалов, вычисляем величины , , , и составляем матрицу

.

Если все элементы  неотрицательны, то  - решение задачи T. В противном случае переходим ко второму этапу, описание которго приводится ниже. Процесс вычисления предварительных потенциалов формализуется следующим образом. Пусть  - номера тех столбцов матрицы С, которые содержат -существенные элементы в 1-й строке;  - номера строк матрицы С, которые содержат -существенные элементы в столбцах с номерами . Если множества  и  для  уже определены, то  объединяет номера тех столбцов матрицы С, не принадлежащих , которые содержат -существенные элементы в строках с номерами , а  состоит из номеров строк этой матрицы, не включенных в  и содержащих -существенные элементы в столбцах с номерами . Образование множеств  и  производится до тех пор, пока процесс не прерывается получением пустого множества. Если , то под  будем понимать такой элемент множества , что  - -существенный элемент С. Аналогично, для  определим  как элемент , при котором  является -существенным элементом С. Из опорности плана  следует, что множества , равно как и множества , не пересекаются. Невырожденность плана  приводит к тому, что объединение всех множеств  есть , а объединение всех множеств  составляет .

Полагаем  и вычисляем

 для .

Далее определяем

 для .

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

Каждая итерация алгоритмов состоит из двух этапов. Предположим, что уже приведено k итераций, в результате которых получен план  и матрица

.

Целью  - й итерации является формирование матрицы  и либо установление оптимальности плана , либо построение нового, более экономичного плана . Рассмотрим каждый из этапов  - й итерации.

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

.

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

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

Следовательно,  - предварительные потенциалы, соответствующие плану , а

.

Как нетрудно заметить, описанное правило отыскания предварительных потенциалов ,  или, что то же самое, матрицы , базируется на определении разностей

.

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

Если все элементы матрицы  неотрицательны,  - искомое решение. Если же среди величин  имеются отрицательные, необходим переход к этапу 2.

Этап 2. На этапе 2 производится улучшение плана . Основой этапа является процесс составления цепочки из положительных элементов этого плана. Выберем наименьший элемент матрицы , расположенный, скажем, на пересечении  - й строки и - го столбца, и обозначим его через . По условию . Переходим к поиску цепочки из положительных элементов матрицы , замыкающейся на элементе  (очевидно, =0). Соединим стрелками  со всеми положительными элементами его строки, совокупность которых обозначим через . Затем каждый из элементов  соединим стрелками со всеми положительными элементами, расположенными в его столбце. Совокупность всех таких элементов обозначим через . Процесс образования множеств  продолжается до тех пор, пока при некотором p (p
– нечетное число) среди столбцов, содержащих элементы , обнаружится столбец с номером . Заметим, что в силу опорности плана  множества , не пересекаются, ибо в противном случае существовала бы замкнутая цепочка из ненулевых перевозок плана . Это обстоятельство, а также то, что любые  два пункта невырожденной задачи T могут быть соединены коммуникациями с ненулевыми перевозками, служит доказательством существования введенного выше числа . Теперь уже нетрудно образовать искомую цепочку. От элемента  перейдем по столбцу к элементу . От  по строке перейдем к соединенному с ним стрелкой элементу  и т.д. Двигаясь таким образом вдоль намеченных стрелок по строкам и столбцам матрицы , получим в конце концов последовательность положительных элементов этой матрицы вида

                                   ,                           (4.1)

образующую цепочку, которая замыкается на элементе .

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

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

Элементы матрицы , оставшиеся после процесса вычеркивания, составляют искомую цепочку. Построив цепочку (4.1), легко сформировать новый план .

Обозначим совокупность пар индексов ,   через , а множество пар индексов вида ,  через . Положим

                                                  .                                        (4.2)

Новый план  определяется согласно правилу

                                                                          (4.3)

Другими словами, из нечетных элементов цепочки (4.1) вычитается , к четным элементам цепочки и к элементу  величина   прибавляется, остальные элементы плана  сохраняют свои прежние значения.

Итак, в результате  - й итерации мы перешли от плана  и матрицы оценок



к улучшенному плану  и к новой матрице

.

Из способа построения плана  следует, что среди  - существенных элементов  лишь один  не равен нулю.

Блок-схема алгоритма метода потенциалов.

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

После запуска программы на экране появляется главное окно.



Нажимаем на кнопку «Добавить». Вводим объемы производства и потребления. Нажимая на левую кнопку мыши, перетаскиваем пункты производства и потребления. Нажимая на правую кнопку мыши, устанавливаем связи между пунктами потребления и производства, устанавливаем тарифы.

Если все введено верно, то нажимаем кнопку «Рассчитать».

Заключение.

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

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

1.     Гольштейн, Е.Г. Линейное программирование./ Гольштейн, Е.Г., Юдин, Д.Б. Теория, методы и приложения. – М., Наука, 1969. – с. 424;

2.     Грешилов, А.А. Прикладные задачи математического программирования: учебное пособие для ВУЗов./ Грешилов, А.А.  – М., Логос, 2006. – с. 286;

3.     Зайченко, Ю.П. Исследование операций./ Зайченко, Ю.П. – 2-ое издание, перер. и доп. – Киев., Высшая школа, 1979. – с. 392;

4.     Таха. Введение в исследование операций./ Таха, Хэмди, А.  – 6-е изд. - М., Изд. дом «Вильямс», 2001. – с. 912.