Решение транспортной задачи методом потенциалов в Excel с примером

Решим транспортную задачу методом потенциалов. Нам известны торговые запасы, потребительские запросы и стоимость доставки за единицу продукции. Сделаем три исходные таблицы.

Построим опорный план транспортной задачи с помощью инструмента «Поиск решений». Рядом составим такие же по объему таблицы с пустыми ячейками. Таблица А – аналог стоимостной, Б – «запасов», В – «спроса».

3 таблицы.

Элементы таблицы Б – сумма соответствующих строк в таблице А. Элементы таблицы В – сумма соответствующих столбцов в таблице А.

Отдельно составим результирующую таблицу Г. В ней отразятся оптимальные транспортные расходы. Каждый элемент таблицы Г – произведение элемента А и соответствующего элемента стоимостной таблицы.

Элементы таблицы.

В отдельном месте листа введем формулу функции: =СУММПРОИЗВ(A1:C3;G1:I3)

Первый массив – стоимостная таблица, второй – диапазон А.

Ставим курсор в ячейку со значением функции. Вызываем инструмент «Поиск решения». Заполняем диалоговое окно:

  1. Целевая ячейка – ссылка на ячейку со значением функции.
  2. Она должна быть равна «максимальному значению», как наиболее выгодному для перевозчика.
  3. Команда изменяет значения ячеек в таблице А. Значения – целые числа.
  4. Диапазон таблицы Б = «Запасам».
  5. Диапазон В = «Потребительскому спросу».
Поиск решения.

В открытом диалоговом окне нажимаем кнопку «Параметры» и устанавливаем следующие настройки:

Параметры поиска решения.

Жмем ОК – «Выполнить». Получаем опорный план транспортной задачи:

Опорный план.

Он залит бледно-зеленым цветом. Ячейки со значениями выше нуля называются «базисными», «занятыми». Ячейки со значением 0 – «свободными».

Далее действуем по плану:

Посчитаем число занятых клеток с помощью функции СЧЕТЕСЛИ.

СЧЕТЕСЛИ.

Так как результат равен 5, опорный план является не вырожденным. Проверим оптимальность опорного плана – найдем потенциалы по занятым клеткам.

Оптимальность.

Нужно составить систему уравнений. Предполагается, что αj = 0, а αi + βj = сij (стоимость доставки единицы груза). Вызываем команду «Поиск решения». Вносим условия системы уравнений в качестве ограничений.

Условия.

Заполненное диалоговое окно:

Ограничения.

Результат работы инструмента «Поиск решения»:

Пример.

Посчитаем оценки свободных клеток. Формула: сij – (αi + βj). Берем свободную клетку из таблицы А. Смотрим ее значение в стоимостной таблице. Это будет сij. Далее смотрим, какие потенциалы соответствуют данной клетке. Вставляем их значения в формулу.

В программе Excel найдем оценки с помощью математических операторов и ссылок на соответствующие ячейки.

Оценки.

План считается оптимальным, если оценки больше или равны 0. В нашем случае получились отрицательные значения – план не является оптимальным. Поэтому двигаемся дальше.

Находим, какой клетке в таблице А соответствует минимальная оценка. Строим для этой клетки цикл – замкнутую ломаную линию. Условия: обязательно чередование вертикального и горизонтального направления, только по базисным клеткам.

В исходной клетке (с минимальной оценкой) ставим знак «+». Далее чередуем: «-», «+» и т.д.

Плюс минус.

В таблице стоимости находим минимальное значение со знаком «-».

Минимальное значение с минусом.

В нашем примере – это «5», ячейка В1. Эту клетку нужно убрать из базиса. А ячейку с минимальной оценкой сделать базисной.

Базисная оценка.

С учетом изменившихся данных вновь строим опорный план транспортной задачи. Применяем инструмент «Поиск решения». Пересчитанный план перевозок выглядит так:

Пример1.

Обратите внимание: ячейка I1 (где была минимальная оценка) стала базисной, занятой.

Скачать пример решения транспортной задачи

Проводим те же расчеты для нового плана (с пункта №1): находим потенциалы, оценки свободных клеток для проверки оптимальности. И так до тех пор, пока оценки свободных клеток не будут больше или равны 0.