Методы решения транспортной задачи icon

Методы решения транспортной задачи



НазваниеМетоды решения транспортной задачи
Дата конвертации29.09.2012
Размер219.61 Kb.
ТипЗадача
1. /ЛЕКЦИИ_МО/Двойственность задач ЛП.doc
2. /ЛЕКЦИИ_МО/Линейное программирование.doc
3. /ЛЕКЦИИ_МО/Метод Пауэлла и сопряженные направления.doc
4. /ЛЕКЦИИ_МО/Методы второго порядка.doc
5. /ЛЕКЦИИ_МО/Методы перв_порядка.doc
6. /ЛЕКЦИИ_МО/Методы переменной метрики.doc
7. /ЛЕКЦИИ_МО/Методы штрафных функций.doc
8. /ЛЕКЦИИ_МО/Параметрическое программирование_Р1.doc
9. /ЛЕКЦИИ_МО/Прямые методы.doc
10. /ЛЕКЦИИ_МО/Статистические методы поиска.doc
11. /ЛЕКЦИИ_МО/Трансп. задача с огр..doc
12. /ЛЕКЦИИ_МО/Транспортная задача.doc
Двойственность задачи линейного программирования
Линейное программирование Основные определения и теоремы
Метод Пауэлла и сопряженные направления
Методы второго порядка
Методы первого порядка
Методы переменной метрики
Методы штрафных функций
Параметрическое линейное программирование
Прямые методы
Статистические методы поиска
Транспортная задача с ограничениями на пропускные способности
Методы решения транспортной задачи

Методы решения транспортной задачи



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



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

,

где - стоимость перевозки единицы продукции из пункта i в пункт j; – планируемая величина перевозок из пункта i в пункт j (план перевозок gif" name="object5" align=absmiddle width=22 height=18> – матрица размерности ); - потребности в продукте в пункте j; - запасы в пункте i.

Предполагается, что модель закрытого типа, то есть .

Если модель открытого типа , то ее всегда можно привести к закрытому типу введением фиктивного пункта производства или фиктивного пункта потребления:

  • Если , то , тогда , причем .

  • Если , то , и .

Транспортная задача представляет собой задачу линейного про­граммирования и, естественно, ее можно решить с использованием метода последовательного улучшения плана или метода последовательного уточ­нения оценок. В этом случае основная трудность бывает связана с числом переменных задачи (mn) и числом ограничений (m+n). Поэтому специальные алгоритмы оказываются более эффективными. К таким алгоритмам относятся метод потенциалов и венгерский метод.

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

Метод северо-западного угла



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







30

80

20

30

90






120

2

30

4

80

2

10

3


8


30

3


5


6

10

6

20

2


40

6


8


7


4

10

5

30

60

3


4


2


1


4

60

В данном случае, имеем задачу закрытого типа, т.к. .

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

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

  • Если ресурс в данной строке исчерпан, то переходим к перевозке в следующей строке текущего столбца (на одну строку вниз).

  • Если потребности для данного пункта (столбца) удовлетворены, то переходим к следующей перевозке текущей строки в следующем столбце.

Затраты на перевозку по построенному плану равны:

.

Естественно, что найденный план далек от оптимального.

Метод минимального элемента



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







30

80

20

30

90






120

2

30

4

80

2


3


8

10

30

3


5


6


6


2

30

40

6


8


7


4


5

40

60

3


4


2

20

1

30

4

10


Затраты на перевозку по построенному плану равны:

.

Этот план лучше, но утверждать, что он оптимален, нельзя.


Определение 1. Набором называется произвольная совокупность перевозок транспортной таблицы.

Определение 2. Цепью называют такие наборы, когда каждая пара соседних клеток в цепи расположены либо в одном столбце, либо в одной строке.

Определение 3. Циклом называется цепь, крайние элементы которой находятся либо в одной строке, либо в одном столбце.

Метод потенциалов



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

Теорема. Для того, чтобы некоторый план транспортной задачи был оптимальным, необходимо и достаточно, чтобы ему соответствовала такая система 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. Иначе найден оптимальный план.


Найдем методом потенциалов оптимальное решение задачи, взяв в качестве опорного план, построенный методом северо-западного угла (1-й шаг предварительного этапа).
























2

30

4

80

2

10

3


8




3


5


6

10

– 6

20

+ 2




6


8


7


+ 4

10

– 5

30



3


4


2


1


4

60


2. Строим систему потенциалов:

, , ,

, , ,

, .

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

3. Проверяем систему на потенциальность:

, , ,

, , ,

, , ,

, , ,

Система непотенциальна.

Переходим к общему этапу.

1. Выбираем клетку, для которой неравенство вида наруша­ется в наибольшей степени, то есть, находится число



среди тех клеток, для которых условие (1) не выполняется: .

Начиная с клетки в направлении против часовой стрелки строится цепь из заполненных клеток таблицы (цикл). Совершая обход по цепи, помечаем клетки, начиная с , попеременно знаками + и –. Клетки со знаками + образуют положительную полуцепь, а со знаками – отрицательную полуцепь. В клетках отрицательной полуцепи ищем минимальную перевозку

.

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



В нашем примере =20.

1. Новому плану соответствует таблица.
























2

30

4

80

2

10

3


8




3


5


– 6

10

6

0

+ 2

20



6


8


7


4

30

5

10



3


4


+ 2


1


– 4

60

Затраты на перевозку по построенному плану равны:

.

2. Строим систему потенциалов

, , ,

, , ,

, .

Полагаем и находим значения остальных потенциалов: , , , , , , , .

3. Проверяем систему на потенциальность:

, , ,

, , ,

, , ,

, , ,


Система непотенциальна.

1. Находим , строим цикл, =10. Улучшаем план. Новому плану соответствует таблица.
























2

30

4

80

2

10

3


8




3


5


6

0

6

0

2

30



6


8


7


– 4

30

+ 5

10



3


4


2

10

+ 1


– 4

50

Затраты на перевозку по построенному плану равны:

.

2. Строим систему потенциалов

, , ,

, , ,

, .

Полагаем и находим значения остальных потенциалов: , , , , , , , .

3. Проверяем систему на потенциальность:

, , ,

, , ,

, , ,

, , ,


Система непотенциальна.

1. Находим , строим цикл, =30. Улучшаем план. Новому плану соответствует таблица.
























2

30

4

80

2

10

3


8




3


5


6


6


2

30



6


8


7


4

0

5

40



3


4


2

10

1

30

4

20

Затраты на перевозку по построенному плану равны:

.

2. Строим систему потенциалов

, , ,

, , ,

, .

Полагаем и находим значения остальных потенциалов: , , , , , , , .

3. Проверяем систему на потенциальность:

, , ,

, , ,

, , ,

, , ,


Система потенциальна, следовательно, план оптимален и окончательные затраты 790.


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

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

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

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

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


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

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

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



Похожие:

Методы решения транспортной задачи iconЛинейное программирование. Методы решения одношаговых задач оптимального управления
Методы решения таких задач получили название математического программирования. Простейшим случаем математического программирования...
Методы решения транспортной задачи iconТема: «Нестандартные методы решения уравнений» Цель
Цель: рассмотреть некоторые методы решения уравнений, позволяющие учащимся подготовиться к решению задач выпускных экзаменов
Методы решения транспортной задачи iconНестандартные методы решения иррациональных уравнений и неравенств. 1-й метод решения

Методы решения транспортной задачи iconДокументы
1. /Kr_ol/Арифметические орешки/Задачи.doc
2. /Kr_ol/Арифметические...

Методы решения транспортной задачи iconТема выступления «Автоматизированная система управления городским хозяйством»
В документе изложены цели, задачи и основные направления деятельности в сфере автоматизации. Изложены методы решения и организационно...
Методы решения транспортной задачи iconС. В. Дубовский
Причем, эти термины и понятия заимствованы как у «концептуалистов», использующих преимущественно вербальные методы, так и у «формалистов»,...
Методы решения транспортной задачи iconИсследование задачи, модели
Анализ результатов решения задачи и уточнение в случае необходимости математической модели с повторным выполнением этапов 2-5
Методы решения транспортной задачи iconКонспект урока по алгебре и началам анализа в 11 классе по теме «Общие методы решения уравнений. Замена уравнения h(f(X))=h(g(X)) уравнением f(X)=g(X)» Учитель математики
Образовательная – повторение, обобщение, систематизация знаний об общем методе решения уравнений; проверка усвоения знаний на обязательном...
Методы решения транспортной задачи iconРеферат методы организации занятий
В задачи учителя на уроке входит: обеспечить максимальную занятость каждого ученика на протяжении всего времени занятий, дать всем...
Методы решения транспортной задачи iconТематический план курса
Ключевой особенностью курса является его направленность на формирование у учащихся навыков поиска собственного решения поставленной...
Методы решения транспортной задачи iconДокументы
1. /Жюри/Для старта/1 восьмерка.doc
2. /Жюри/Для...

Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов