1) Привести задачу к замкнутой модели.
2) Найти первоначальный план перевозок (начальную крайнюю точку множества допустимых элементов).
3) Провести исследование плана перевозок . Для найденного плана перевозок построить матрицу . Переменные называются потенциалами. Они определяются из системы уравнений для базисных индексов . Для однозначного определения потенциалов положим один из потенциалов равным заданной величине, например, .
4) Провести исследование матрицы
.
Если , то исследуемый план перевозок является решением задачи. Если среди элементов матрицы есть отрицательные, то выберем наименьший элемент. Пусть, например, .
5) Построить новый план перевозок, являющийся крайней точкой множества допустимых элементов: , где
Здесь выбирается так, чтобы одна из базисных компонент обратилась в ноль, а остальные были по-прежнему неотрицательны. Тогда вектор матрицы , соответствующий этой компоненте, выводим из числа базисных, а вектор матрицы , соответствующий переменной , вводим в число базисных векторов. Здесь под матрицей понимается матрица ограничений задачи, задаваемых уравнениями (1), (2).
Далее вновь начинаем исследование полученной крайней точки , т.е. возвращаемся к пункту 3).
В невырожденной задаче в ноль может обратиться только одна из компонент вектора . В вырожденной задаче в ноль может обратиться несколько компонент. В этом случае из числа базисных векторов исключается любой вектор с нулевым значением, как правило, исключается вектор с наибольшей стоимостью перевозок.
Пример 2. Решить транспортную задачу, заданную платежной матрицей (табл. 7.1).
Решение:
1) В примере 1 задача была приведена к замкнутой модели. Соответствующая платежная матрица представлена таблицей 7.2.
2) в качестве первоначального плана перевозок возьмем план, полученный методом «минимум по матрице» и представленный таблицей 7.4.
3) Построим матрицу :
4) Найдем матрицу :
.
В качестве наименьшего отрицательного элемента матрицы возьмем .
5) Построим новый план перевозок, добавляя в предыдущий план перевозок на место нулевого небазисного элемента величину :
Перейдем к пункту ).
) Построим матрицу :
) Найдем матрицу :
.
Наименьший отрицательный элемент полученной матрицы : . Добавляя в предыдущий план перевозок на место нулевого небазисного элемента величину , получим третий план перевозок. Вычислим значение функционала для второго плана перевозок:
.
) Построим новый план перевозок:
) Построим матрицу :
-2 |
) Найдем матрицу :
.
Так как , то третий план перевозок, полученный в пункте ), является оптимальным. Найдем значение функционала :
.
Заметим, что в исходной задаче, задаваемой платежной матрицей в виде таблицы 7.1, пункт отправления отсутствовал, он был искусственно введен для сведения задачи к замкнутой модели. Тот факт, что в полученном плане перевозок , , означает, что пункты назначения не будут полностью обслужены. Выпишем ответ для поставленной задачи.
Ответ: . ●
Пример 3. Решить транспортную задачу, заданную платежной матрицей (табл. 7.5).
Таблица 7.5
Решение:
1) В данной задаче , т.е. имеем замкнутую модель транспортной задачи.
2) Методом северно-западного угла найдем начальный план перевозок:
3) Построим матрицу :
4) Найдем матрицу :
.
Наименьший отрицательный элемент матрицы равен .
5) Построим новый план перевозок, добавляя в предыдущий план перевозок на место нулевого небазисного элемента величину :
Заметим, что здесь обратились в ноль два элемента и . Исключим из числа базисных компонент элемент с большей стоимостью перевозки.
Перейдем к пункту ).
) Построим матрицу :
-4 | -3 | -5 |
) Найдем матрицу :
Наименьший отрицательный элемент матрицы равен .
) Построим новый план перевозок, добавляя в предыдущий план перевозок на место нулевого небазисного элемента величину :
) Построим матрицу :
) Найдем матрицу :
Наименьший отрицательный элемент матрицы равен .
) Построим новый план перевозок, добавляя в предыдущий план перевозок на место нулевого небазисного элемента величину :
) Построим матрицу :
) Найдем матрицу :
.
Так как , то четвертый план перевозок, полученный в пункте ), является оптимальным. Найдем значение функционала :
.
Ответ: . ●
Пример 4. Решить транспортную задачу, заданную платежной матрицей (табл. 7.6), при дополнительном требовании полного вывоза груза из пункта .
Таблица 7.6
Решение:
1) Так как , то . Для приведения к замкнутой модели введем фиктивный пункт назначения с требуемой величиной ввоза . Так как в задаче имеется дополнительное требование полного удовлетворения вывоза груза из пункта , то положим , где - достаточно большое положительное число. Получим замкнутую модель транспортной задачи со следующей платежной матрицей:
2) Найдем начальный план перевозок методом «северо-западного угла».
Первоначальный план перевозок:
3) Построим матрицу :
4) Найдем матрицу :
.
Так как - достаточно большое число, то .
5) Построим новый план перевозок, добавляя в предыдущий план перевозок на место нулевого небазисного элемента величину :
|
t | ||
) Построим матрицу :
) Найдем матрицу :
.
Так как , то полученный в пункте 5) план перевозок является оптимальным. При этом из пункта весь груз будет вывезен, а в пункте останется 10 единиц груза. Найдем значение функционала :
.
Ответ: . ●