Смысл и сущность метода потенциалов Потенциалы u и v являются переменными двойственной транспортной задачи и обозначают оплату за перевозку единицы груза в пунктах отправления (поставщиками) и назначения (потребителями) соответственно, поэтому их сумма равна транспортному тарифу cij = ui + vj
Всякое неотрицательное решение системы линейных уравнений, определяемое матрицей X = (xij) называется допустимым планом.
Допустимый план транспортной задачи, имеющий не более (m + n - 1) отличных от нуля величин xij, называется опорным.
Если в опорном плане число отличных от нуля компонент равно в точности (m + n - 1), то план является невырожденным, если меньше, то план называется вырожденным.
План X = (xij), при котором функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи.
Циклом, или прямоугольным контуром, в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, другое - в столбце. Если ломаная линия, образующая цикл, пересекается, то точки пересечения не являются вершинами. Для каждой свободной клетки таблицы можно построить единственный цикл.
Методы построения первого опорного плана
метод наименьших тарифов (стоимости). Выбирается минимальный тариф, c0 = min(cij);
метод северо-западного угла. Выбирается первый тариф начиная с первого, c0 = c11;
Алгоритм оценки оптимальности плана методом потенциалов
Построение первого опорного плана;
Проверка вырожденности плана;
Определение значения функции цели путем суммирования произведений тарифов (удельных затрат) на объем перевозимого груза по всем занятым клеткам таблицы;
Проверка условия оптимальности;
Построение нового опорного плана.
Пример решения задачи методом северо-западного угла
Стоимость доставки единицы груза из каждого пункта отправления в
соответствующие пункты назначения задана матрицей тарифов:
Для проверки полученного решения или получения автоматического решения транспортной задачи можно использовать сервис Решение транспортной задачи. Результаты оформляются в формате doc (MS Word, OpenOffice) с комментариями и ходом решения.
.
Симплексный метод бесплатно. Примеры решений.
.
Транспортная задача бесплатно. Примеры решений транспортной задачи.
.
Задача о назначениях бесплатно. Венгерский метод решения.