Контрольная работа - Транспортная задача. Метод потенциалов. Модули Matlab - файл n1.doc

Контрольная работа - Транспортная задача. Метод потенциалов. Модули Matlab
скачать (145 kb.)
Доступные файлы (3):
n1.doc120kb.21.05.2009 17:32скачать
n2.doc179kb.21.05.2009 17:33скачать
n3.doc348kb.21.05.2009 17:31скачать

n1.doc

МЕТОД ПОТЕНЦИАЛОВ РЕШЕНИЯ ТЗ.

Метод потенциалов позволяет, исходя из некоторого опорного плана, построить за конечное число итераций решение Т-задачи.

Метод потенциалов впервые предложили Л. В. Канторович и М. К. Гавурин в 1949 г. [18; 59]. Позже аналогичный метод разработал Г. Данциг, исходя из общих идей ЛП.

Общая схема метода такова. В данном начальном опорном плане перевозок каждому пункту ставят в соответствие некоторое число, называемое его предварительным потенциалом. Предварительные потенциалы выбирают так, чтобы их разность для любой пары пунктов Ai i Bj, связанных основной коммуникацией, была равна cij. Если окажется, что разность предварительных потенциалов для всех других коммуникаций не превосходит cij, то данный план перевозок - оптимальное решение задачи. В противном случае указывают способ улучшения текущего плана Т-задачи.

Метод позволяет находить оптимальный план перевозок транс­портной таблицы. В основе лежит следующая теорема.

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

,  , ,                             (1)

,  .                                         (2)
и называются потенциалами соответствующих пунктов отправления  и пунктов назначения. Условия (1)-(2) называются условиями потенциальности.

План будем называть потенциальным, если для него существует система и , удовлетворяющая (1)-(2). Тогда теорема коротко формулируется следующим образом.

Теорема. Для оптимальности плана транспортной задачи необходимо и достаточно, чтобы он был потенциален.

Доказательство:

Достаточность. Пусть план потенциален, так что существует система и , удовлетворяющая (1)–(2). Тогда для любого допустимого плана





для потенциального плана



,

т.е. стоимость перевозок по любому плану не меньше стоимости перевозок по потенциальному плану . Следовательно, план оптимален.

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



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




0=





0=





0=



0=





0=





0=





1

x11  y11 =

-1



0



0

1



0



0

c11

























x1n  y1n =

-1



0



0

0



0



1

c1n

























xi1  yi1 =

0



-1



0

1



0



0

ci1

























xij  yij =

0



-1



0

0



1



0

cij

























xin  yin =

0



-1



0

0



0



1

cin

























xm1  ym1 =

0



0



-1

1



0



0

Cm1

























xmn  ymn =

0



0



-1

0



0



1

Cmn

1   w=

a1



ai



an

b1



bj



bn

0


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

Получаем, что двойственная задача имеет вид:



при ограничениях

,   , ,

т.е. ,   , .

     Пусть – оптимальное решение транспортной задачи. Тогда на основании первой теоремы двойственности двойственная задача имеет оптимальное решение

.

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

     Если , то по второй теореме двойственности соответствующее ограничение двойственной задачи



обращается в строгое равенство

.

Теорема доказана.
Алгоритм метода потенциалов
Алгоритм метода потенциалов состоит из предварительного этапа и повторяющегося основного этапа.

Предварительный этап.

  1. Каким-либо способом ищется допустимый план (методом северо-западного угла или минимального элемента).

  2. Для полученного плана строится система m+n чисел , , таких, что ,  .

  3. Построенная система и исследуется на потенциальность, то есть, план исследуется на оптимальность. Для этого проверяется , .

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

Основной этап.

  1. Улучшаем план, то есть от плана переходим к плану такому, что .

  2. Для плана строим новую систему , , , такую, что ,  .

  3. Исследуем систему на потенциальность. Если система не потенциальна, то переходим на п.1. Иначе найден оптимальный план.


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

Определение 5. Если допустимый опорный план содержит менее элементов , то он называется вырожденным, а транспортная задача называется вырожденной транспортной задачей.

Следующая теорема позволяет определить вырожденность задачи до ее решения.

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

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

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

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

Конец формы



МЕТОД ПОТЕНЦИАЛОВ РЕШЕНИЯ ТЗ
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации