Решение транспортной задачи методом потенциалов
1. Построить модель транспортной задачи как задачи линейного программирования в канонической форма записи, составить к ней двойственную задачу ЛП.
2. Найти начальное решение методом минимальной стоимости или Северо-западного угла. Проверить его на вырожденность.
3. Решить задачу методом потенциалов.
4. Решить задачу в среде Microsoft Exel, приложить отчет.
В каждом варианте задания приведена таблица, в клетках которой проставлены элементы матрицы стоимостей перевозок C=[cij]mxn (m=4, n=5), справа от таблицы значения запасов груза на складах a1, a2, a3, a4, внизу значения запасов b1, b2, b3, b4, b5.
Алгоритм метода потенциалов
Построить математическую модель линейного программирования для транспортной задачи и двойственную к ней.
2.Найти начальное решение Х0 методом минимальной стоимости или методом Северо-западного угла.
Проверить решение на вырожденность с помощью необходимого условия.
N=m+n-1,
где m – число поставщиков, n – число потребителей, а N – число заполненных клеток.
Если число заполненных клеток (ненулевых компонент плана Х0 системы ограничений) равно m+n-1, то в этом случае решение называется невырожденным, а если число ненулевых решений не равно m+n-1, то такое решение называется вырожденным (вводится значимый нуль 
в клетку с минимальным значением Cij из оставшихся так, чтобы можно было найти потенциалы (U,V).
4.Проверка плана на оптимальность.
4.1. Вычислить потенциалы.
Потенциалы находят из решения системы:
Cij = Ui+Vj,
U1=0,
где Ui, Vj – потенциалы, переменные двойственной задачи
Cij – стоимость перевозки единицы груза
4.2. Вычисление оценок свободных клеток: 
если все оценки 
, то это признак единственного оптимального решения;
· если среди оценок имеется оценка 
то это признак альтернативного оптимума, и выполняется еще один шаг для его нахождения: принять этот элемент за разрешающий.
· если имеются оценки 
то это признак того, что найденное решение не является оптимальным и его можно улучшить. Необходимо перейти к новому опорному решению, при этом надо перераспределить грузы, перемещая их из занятых клеток в свободные. При этом свободная клетка становится занятой, а одна из ранее занятых клеток свободной.
5. Построить новый план
5.1.Начиная с разрешающего элемента, строим замкнутый цикл, вершинами которого будут цифры плана, отличные от нуля.
Цикл может быть представлен следующими фигурами:
 | |||||||||
 |  | |  | ||||||
5.2.Помечаем вершины цикла знаками «+» и «−» поочередно, начиная с разрешающего элемента.
5.3.Находим величину сдвига по циклу - минимальный из элементов цикла, помеченных знаком «−»:
Θ= min {xij}-, xij? Z, где Z - цикл
5.4.Строим новый план х1, добавляя или вычитая, в соответствии со знаками, величину Θ к элементам цикла. И переходим на пункт 4.
6. Решить задачу в среде Microsoft Exсel, приложить отчет.
Пример решения транспортной задачи (ТЗ) методом потенциалов
Имеется 4 оптовых склада 
с запасами однородного груза 
41; 
33; 
25; 
14. Имеются 5 магазинов 
с заказами на однородный груз 
соответственно. Обозначим хij-количество груза, перевозимого со склада А1 в магазин bj. Матрица перевозок задана в следующем виде:
Таблица 2.1 – Исходные данные
| 
| 
| 
| 
| 
| |
|
|
|
|
|
| |
|
|
|
|
|
| |
|
|
|
|
|
| |
|
|
|
|
|
|
Условия разрешимости:
-задача закрытая
1. Математическая модель прямой ТЗ:
 | |||
 |
|
|
Двойственная транспортная задача составляется для следующих переменных:
U – переменные для складов или поставщиков;
V - переменные для магазинов или потребителей.
Математическая модель двойственной ТЗ:
Ограничения представлены на другой странице.
|
|
