ТРАНСПОРТНАЯ ЗАДАЧА ЛЕКЦИЯ 2

1. ТРАНСПОРТНАЯ ЗАДАЧА

ЛЕКЦИЯ 2

2. план

ПЛАН
1. Условие невырожденности плана.
2. Метод потенциалов проверки решения на оптимальность.
3. Теорема оптимальности.
4. Примеры.

3. Условие невырожденности плана

УСЛОВИЕ НЕВЫРОЖДЕННОСТИ
ПЛАНА
Если число заполненных клеток равно
m + n – 1, то план является невырожденным.
Если число заполненных клеток меньше этого
значения, то план (решение) называется
вырожденным. В случае вырожденности плана
условно считают одну (или несколько) из пустых
клеток занятой, записывая в нее нулевую
перевозку так, чтобы число занятых клеток стало
равным m + n – 1.

4. Метод потенциалов проверки решения на оптимальность

МЕТОД ПОТЕНЦИАЛОВ ПРОВЕРКИ
РЕШЕНИЯ НА ОПТИМАЛЬНОСТЬ

5.

Совокупность уравнений ui v j cij ,
составленных для всех базисных переменных,
представляет совместную систему линейных
уравнений, причем одну из переменных можно
задавать произвольно и тогда остальные
переменные из системы уравнений находятся
однозначно.

6.

Обозначим через ui v j cij , где c ij назовем
псевдостоимостями, или косвенными стоимостями
(тарифами). Эти псевдостоимости находятся для
всех свободных клеток.
Платежи ui и v j не обязательно должны быть
положительны, поскольку не исключено, что
«перевозчик» сам платит тому или иному пункту
какую-то премию за перевозку.

7. Теорема «о платежах».

ТЕОРЕМА «О ПЛАТЕЖАХ».

8. Теорема оптимальности.

ТЕОРЕМА ОПТИМАЛЬНОСТИ.

9. Пример

ПРИМЕР
Найти опорное решение методом минимальной стоимости
и проверить оптимальность решения методом потенциалов.

10.

РЕШЕНИЕ

11.

Находим потенциалы базисных, заполненных,
клеток
u1 v1 c11 2,
u1 v2 c12 3,
u1 v3 c13 1,
u2 v2 c22 2.

12.

Положим u1 0 и решим систему.
Получим
v1 2, v2 3, u2 1, v3 1.
Найдем потенциалы пустых клеток
c21 u2 v1 1 2 1,
c23 u2 v3 1 1 0.
План перевозок оптимален
c21 1 c21 4, c23 0 c23 5.
X min (30,10, 20, 0,30, 0),
F min 2 30 3 10 1 20 2 30 150.

13. Пример.

ПРИМЕР.
На складах имеются запасы продукции 90, 400 и 110 тонн
соответственно. Потребители должны получить эту
продукцию в количествах 140, 300 и 160 тонн,
соответственно. Найти такой план закрепления
поставщиков к потребителям, при котором суммы затрат на
перевозки минимальны.

14.

Расходы на перевозки 1 т продукции заданы матрицей (у.е.)
2 5 2
C 4 1 5
3 6 8
Сумма потребностей и сумма запасов равны:
140+300+160=90+400+110=600. Модель закрытая.

15.

16.

План
0
90 0
X 0 300 100
50 0
60
Fmin 2 90 1 300 5 100 3 50 8 60 1610 y.e.

17.

m n 1 3 3 1 5
u1 v1 2,
u2 v2 1,
u2 v3 5,
u3 v1 3,
u3 v3 8.

18. Внесем в таблицу потенциалы занятых клеток

ВНЕСЕМ В ТАБЛИЦУ ПОТЕНЦИАЛЫ
ЗАНЯТЫХ КЛЕТОК

19.

Найдем оценки свободных клеток и разности
c12 u1 v2 3,
c13 u1 v3 7,
12 c12 c12 5 3 2 0,
13 c13 c13 2 7 5 0,
c21 u2 v1 2 2 0, 21 c21 c21 4 0 4 0,
uur
c32 u3 v2 1 3 4. 32 c32 c32 6 4 2 0.
Решение не оптимально, т.к. имеется отрицательная оценка.

20.

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

21.

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

22.

23.

24.

25.

Получили новое решение
0
60
30
X 0 300 100 .
110 0
0
Проверим его на оптимальность, вычислив потенциалы
базисных клеток.

26.

Потенциалы заполненных клеток
u1 v1 2,
u2 v2 1,
u3 v1 3,
u1 v3 2,
u2 v3 5.
u1 0.
v1 2, u3 1, v3 2, u2 3, v2 2.

27.

Вычислим оценки свободных клеток:
c12 u1 v2 0 2 2,
12 c12 c12 5 ( 2) 7 0,
c21 u2 v1 3 2 5,
21 c21 c21 4 5 1 0,
c32 u3 v2 1 2 1,
uur
c33 u3 v3 1 2 3.
32 c32 c32 6 ( 1) 7 0,
33 c33 c33 8 3 5 0.
План не оптимален, т.к. оценка клетки (21) отрицательна.

28.

29.

30.

Новый план
0 90
0
X 30 300 70
110 0
0
Снова проверяем его на оптимальность. Для занятых
клеток находим:
u1 v3 2,
u2 v1 4,
u2 v2 1,
u2 v3 5,
u3 v1 3.
u1 0.
v3 2, u2 3, v2 2, u3 2, v1 1.

31.

Для свободных клеток псевдостоимости равны
c11 u1 v1 0 1 1,
c12 u1 v2 0 2 2,
c32 u3 v2 2 2 0,
uur
c33 u3 v3 2 2 4.

32.

Ищем оценки свободных клеток
11 c11 c11 2 1 1 0,
12 c12 c12 5 ( 2) 7 0,
32 c32 c32 6 0 6 0,
33 c33 c33 8 4 4 0.

33.

Все оценки положительны, поэтому план оптимален.
Ответ:
.
0 90
0
X 30 300 70
110 0
0
При этом
Fopt 90 2 30 4 300 1 70 5 110 3 1280.
По сравнению с первоначальным планом расходы уменьшились на
величину
1610-1280=330 у.е.