- •Симплексный метод
- •Двойственная задача и экономическая интерпретация переменных двойственной задачи
- •Экономическая интерпретация ограничений двойственной задачи
- •Анализ устойчивости двойственных оценок
- •Транспортной задачи
- •3). Нахождение оптимального плана транспортной задачи.
- •Пусть , тогда получим:
- •Проверяем опорный план на оптимальность по свободным клеткам, определяя, выполняется ли соотношение :
- •Полагая , находим, что . Далее, для свободных клеток проверяем, будут ли выполняться соотношение :
- •Далее, для свободных клеток проверяем, будут ли выполняться соотношение :
Полагая , находим, что . Далее, для свободных клеток проверяем, будут ли выполняться соотношение :
Таким образом, для клетки условие не выполняется, из чего мы заключаем, что базисный план не оптимален. Стоимость перевозок можно уменьшить, если перераспределить груз для потребителей так, чтобы некоторую его часть транспортировать из пункта А2 в пункт В2. Отметим клетку знаком «+» и построим цикл перераспределения (табл. 22), который начинается и заканчивается в данной клетке.
Таблица 22
-
Поставщик
Потребитель
Запасы
ai
B1
B2
B3
B4
A1
7
8
1
+
2
170
80
90
A2
4
5
9
8
150
125
25
A3
9
2
3
6
180
6 0
+ 120
Потребности bj
125
60
200
115
В разгружаемых клетках данного цикла наименьшее число находится в клетке и равно 25. Теперь к каждому значению загружаемой клетки цикла прибавим 25, а от каждого соответствующего значения разгружаемой клетки вычтем 25. В результате таких перемещений грузов получится новый базисный план транспортной задачи (табл. 23).
Таблица 23
-
Поставщик
Потребитель
Запасы
ai
B1
B2
B3
B4
A1
7
8
1
2
170
55
115
A2
4
5
9
8
150
125
25
A3
9
2
3
6
180
35
145
Потребности bj
125
60
200
115
.
Снова к данному плану применяем ту же схему. Для всех занятых клеток таблицы составляем уравнения вида :
Полагая , находим, что .