1. Постановка задачи.
Решить транспортную задачу и усложнённую транспортную задачу методом потенциалов. В качестве опорного плана необходимо взять вектор, найденный методом северо-западного угла.
Решить задачу симплекс методом и сравнить результаты.
Условие задачи:
Столбец “Поставщики” содержит значения количества запасов. Строка “Склады” содержит значения количества потребностей. Ячейки таблицы содержат значения стоимости перевозки ресурсов.
Условие многопродуктовой задачи:
2. Исследование применимости метода.
Если сумма запасов равна сумме потребностей, то транспортная задача называется закрытой. Если равенство не соблюдается, то задача называетсяоткрытой. Для решения транспортной задачи методом потенциалов необходимо, чтобы она была приведена к закрытому виду.
Общее число запасов на складах:27; Общая потребность:27
Задача является закрытой, значит метод применим.
3. Описание алгоритма метода.
1. Поиск начального решения.
Решение транспортной задачи начинается с поиска допустимого начального решения (плана перевозок), чтобы все запасы поставщиков были распределены по потребителям. Допустимое начальное решение может быть найдено любым методом, например, северо-западного угла.
2. Метод северо-западного угла.
Допустимое начальное решение транспортной задачи можно построить, последовательно перебирая строки таблицы (то есть поставщиков) сверху вниз. В пределах каждой строки нужно перебрать слева направо не охваченных или не полностью охваченных поставками потребителей, записывая в соответствующие ячейки объем поставляемого груза от поставщика в данной строке, и так до исчерпания возможностей поставщика. Таким образом, весь груз от поставщиков будет распределен по потребителям.
3. Проверка плана на вырожденность.
Ячейки (клетки) транспортной таблицы с ненулевыми перевозками называются базисными, а клетки с нулевыми объемами перевозки — свободными.
Базисных ячеек таблицы должно быть не менее m + n - 1, где m и n, соответственно, число поставщиков и потребителей, иначе решение считается вырожденным и требует введения в базис одной из ячеек с нулевой перевозкой (чтобы алгоритм не впал в бесконечный цикл, эта ячейка должна быть случайной).
4. Вычисление потенциалов.
Каждому поставщику Ai соответствует потенциал Ui, а каждому потребителю Bj соответствует потенциал Vj. Чтобы определить эти потенциалы, полагают, что U1 =0, а остальные потенциалы вычисляют из соотношения
Ui + Vj = Cij
5. Проверка решения на оптимальность.
Для всех пустых ячеек (с нулевым объемом перевозки) вычисляют оценки клеток распределительной таблицы Δij по формуле Δij = Сij – Ui – Vj.
Для всех занятых ячеек (с ненулевыми объемами перевозки) полагают Δij=0, поскольку на следующем шаге нам потребуется значение с минимальной оценкой в незанятых ячейках.
Если в получившейся таблице нет отрицательных значений Δij, то план перевозок оптимален и задача решена.
Наличие отрицательных значений Δij означает, что решение не оптимально.
Наименьшее отрицательное значение - начальная вершина для цикла пересчёта.
6. Построение цикла пересчёта.
Цикл пересчёта поставок представляет собой замкнутую ломаную линию, которая соединяет начальную и ячейки транспортной таблицы по определенным правилам:
1. Изменение направления осуществляется только в заполненных ячейках
2. Звенья параллельны строкам или столбцам
3. Начинается в пустой клетке и заканчивается там же.
7. Перераспределение поставок по циклу.
Начальной ячейке цикла присваиваем знак (+), следующей по циклу (начать двигаться можно в любом направлении) — знак (–), следующей ячейке цикла — опять (+) и так далее. Находим минимальную поставку по отмеченным знаком (–) вершинам цикла и обозначаем ее θ. Значение θ вычитаем из вершин цикла, которые помечены знаком (–) и прибавляем его к вершинам цикла, которые помечены знаком (+).
8. Алгоритм добавления многопродуктовости
Для добавления многопродуктовости в транспортной задаче необходимо запретить поставки между пунктами хранения и значения, при которых продукты, вывозимые из пункта хранения и ожидаемые в пункте назначения, отличаются.
Для этого установим для следующей поставки тариф, который точно не может войти в оптимальное решение, например, 
4. Результаты работы методов.
Результат работы метода потенциалов:
Общие затраты: 116
Симплекс-метод.
Условия:
С = [8 2 5 3 14 10 4 5 7 15 5 1 2 1 10 6 3 2 4 15]
А =
[1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 ]
b = [ 8 3 11 5 4 5 4 9 5 ]
Последнее ограничение специально исключено из задачи, поскольку при его наличии мы имеем дело с матрицей не полного ранга и симплекс метод не применим
Результат работы симплекс метода:
Общие затраты: 116