Метод потенциалов.

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 единиц груза. Найдем значение функционала :

.

Ответ: . ●