Xreferat.com » Рефераты по транспорту » Решение транспортной задачи методом потенциалов

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

построении мы совсем не учитывали стоимость перевозок Сij .

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

Пусть имеется транспортная таблица, соответствующая начальному решению, хil = для базисного решения переменных, хil = 0 для свободных переменных (ячейки, соответствующие свободным переменным, остаются пустыми). Далее, нам требуется таблица расходов с заданными pij.

Отыскание симплекс множителей. Заполним таблицу расходов, оставив ячейки, соответствующие свободным переменным, пустыми. В крайний правый столбец внесем значения неизвестных u1,…,um, в нижнюю строку – значения неизвестных v1,…,vn,. Эти m + n неизвестных для всех (i, j), соответствующих базисным переменным, должны удовлетворять линейной системе уравнений ui + vj = pij.


pll


plj


pln

ul


.

…

.


.

…

.


.

.

.

pil


pij


pin

ui


.

…

.


.

…

.


.

.

.

pml


pmj


pmn

um

vl

…

vj

…

vn



Для всех базисных решений эта система имеет треугольный вид, ранг её матрицы равен n + m – 1. Следовательно, систему всегда можно решить следующим способом.

Полагают vn = 0. Если значения k неизвестных определены, то в системе всегда имеется уравнение, одно из неизвестных в котором уже найдено, а другое ещё нет.

Переменные ui и vj симплекс - множителями. Иногда они называются также потенциалами, а этот метод решения называют методом потенциалов.

Пример 2.

5





u1

6

4

7



u2



3

1

8

u3

v1

v2

v3

v4

v5



v5 = 0 ® u3 = 8, так как u3 + u5 = p35 = 8, ® v4 = -7, так как u3 + v4 = p34 = 1, ® v3 = -5, так как u3 + v3 = 3, ® u2 = 12 ® v2 = -8, ® v1 = -6 ® u1 = 11.

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

Для определения симплекс – множителей мы вносим на свободные места в таблице значения

pўij = pij – ui – vj

(коэффициенты целевой функции, пересчитанные для свободных переменных). Если все pўij 0, то базисное решение оптимально. В противном случае мы выбираем произвольное pўab < 0, чаще всего наименьшее. Индексом ab помечено свободное переменное хab , которое должно войти в базис. Соответствующую ячейку транспортной таблицы мы отметим знаком +.

Пример 3.

5

6

3

5

9

6

4

7

3

5

2

5

3

1

8

pij:

5





11


6

4

7



12

®



3

1

8

8


-6

-8

-5

-7

0






5

3

-3

1

-2

®

6

4

7

-2

-7


0

5

3

1

8


Минимальный элемент –7 ® (a, b) = (2,5).

Кроме ячейки (a, b) транспортной таблицы, мы пометим значками – и + другие занятые числами ячейки таким образом, чтобы в каждой строке и в каждом столбце транспортной таблицы число знаков + было равно числу знаков -. Это всегда можно сделать единственным образом, причем в каждой строке и в каждом столбце будет содержаться максимум по одному знаку = и по одному знаку -.

Пример 4.


15






5

5

5


+

®



5

10

5




15





®

5

5

5-


+




5+

10

5-


Знак + поставлен в ячейке (2,5). Соответственно в последнем столбце должен быть поставлен знак -, это можно сделать только в ячейке (3,5). Следовательно, знак + должен быть поставлен в последней строке. В ячейке с числом 10 этого сделать нельзя, так как тогда в соответствующем столбце не было бы знака -, и д.т.


Затем мы определяем минимум М из всех элементов, помеченных знаком -, и выбираем ячейку (g, d), где этот минимум достигается.

В нашем примере с М = 5 можно выбрать (g, d) = (2, 3); при этом (g, d) определяет базисное переменное, которое должно стать свободным, т.е. базисное переменное, соответствующее индексу разрешающей строки симплекс – метода.



20

5

10

10

5

15

15





15

5

5

5-


+

20



5+

10

5-


Ї


15





5-

5



5+

+


10

10

0-


Ї


15-


+



5

5



5

0+


10-

10



Ї


5


10



5-

5


+

5

10+



10-



Ї

5


10




5


5

5

15



5



Копт = 150


Переход к новой транспортной таблице (замена базиса) происходит следующим образом:

а). В ячейку (a, b) новой таблицы записывается число М.

б). Ячейка (g, d) остается пустой.

в). В других ячейках помеченных знаками – или +, число М вычитается из стоящего в ячейке числа (-) или складывается с ним (+). Результат вносится в соответствующую ячейку новой таблицы.

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

Пример 5.

15






5

5

5-


+

®



5+

10

5-




15





®

5

5



5




10

10

0

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

Пример 6. Ниже воспроизведен ход решения примера 1.

5

3

-3

1

-2

11

6

4

7

-2

-7

12

0

5

3

1

8

8

-6

-8

-5

-7

0



5

3

4

8

5

4

6

4

7

5

5

5

-7

-2

3

1

8

8

-1

-1

2

0

0



5

3

-3

1

5

4

6

4

0

-2

5

5

2

5

3

1

7

1

1

-1

2

0

0



5

3

3

1

5

4

6

4

3

-2

5

5

2

5

3

1

7

1

1

-1

-1

0

0



5

1

3

1

3

6

2

4

5

3

5

5

2

3

3

1

5

3

-1

-1

-3

-2

0



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


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

Если дана вырожденная транспортная таблица (её можно узнать по имеющемуся 0, то заменив am на am + ne и все bj на bj + e , где e > 0 подразумевается очень малым, исправим значения базисных переменных так, что бы для новых ai и bj получилось базисное решение. Это всегда можно сделать единственным способом (как и при отыскании симплекс – множителей).


15





5

5



5



10

10

0



20 + e

5 + e

10 + e

10 + e

5 + e

15






15






20 + e







15 + 2e





5 - e

5 + e



5 - 2e



10 + e

10 + e

3e


Если полученный таким образом элемент окажется отрицательным, то в этой же строке должен найтись положительный (ещё до изменения) элемент и в этом же столбце – положительный элемент . Тогда ячейка (s, r) свободна, отмечаем её знаком + и проводим замену базиса. Так можно избавиться от всех отрицательных значений*1.

Затем при помощи метода потенциалов расчеты продолжают дальше (вырождение уже никогда больше не встретится). Устремляя e ® 0, приходим к оптимальному решению исходной задачи.

Список использованной литературы:


1. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования М.; Наука, 1976г.

2. Карманов В.Г. Математическое программирование. – М.; Наука, 1986г.

3. Моисеев Н.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. – М.; Наука, 1978г.

4. Иванов Ю.П., Лотов А.В. Математические модели в экономике. – М.; Наука, 1979г.

5. Бронштейн И.Н., Семендяев К.А. Справочник по математике. – М.; Наука, 1986г.

1 Часто бывает достаточно везде заменить e на -e.

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: