Решение классической транспортной задачи с помощью Excel

Постановка задачи. Пусть к перевозке представлен однородный груз, который необходимо доставить из пунктов отправления А в количестве 44 т, Б – 79 т, В – 70 т, Г- 30 т в пункты назначения Д в количестве 25 т, Е – 70 т, Ж – 36 т, З – 42 т, И – 20 т, К – 30 т. Известна стоимость доставки одной тонны груза на каждом направлении. Представление исходных данных в редакторе Excel изображено на рис. 9.

Необходимо составить план перевозок, при котором все запасы из пунктов отправления будут вывезены, потребности всех пунктов назначения будут удовлетворены, а общая стоимость доставки по всем направлениям будет минимальной.

Математическая модель транспортной задачи в общем виде имеет следующий вид.

Целевая функция, направленная на минимизацию суммарных транспортных расходов:

(2)

Ограничение о полном вывозе груза от отправителей:

(3)

Ограничение об удовлетворении потребности в грузе всех получателей:

(4)

Условие неотрицательности переменных:

(5)

В качестве критерия оптимальности в задаче выступает стоимость доставки одной тонны груза (c_ij), в качестве параметра управления – количество груза, перевозимое на направлении (x_ij).

Для данного примера количество возможных направлений перевозки груза составляет 24 (4 пункта отправления Х 6 пунктов назначения), то есть в задаче 24 переменные x_ij (табл. 1).

Таблица 1.

Отправители	Порты назначения
Д	Е	Ж	З	И	К
А		х11	х12	х13	х14	х15	х16
Б		х21	х22	х23	х24	х25	х26
В		х31	х32	х33	х34	х35	х36
Г		х41	х42	х43	х44	х45	х46

Для решения транспортной задачи с помощью Excel необходимо:

1. Создать новую таблицу с пустыми ячейками, под которыми понимается возможная доставка груза x_ij на определенных направлениях. В таблице будет проводиться поиск оптимального плана распределения перевозок (рис 10).

2. Создать дополнительные таблицы, в которых будут учтены ограничения по задаче. Причем, в правый столбец перенесены значения из условия задачи, а в пустые ячейки левого столбца будут внесены формулы. Также создаем ячейку для целевой функции (рис. 11).

3. В ячейку целевой функции ввести формулу (1) в числовом видедля представленных значений c_ijx_ij (при этом, каждое значение c_ij умножается на пустую на данном этапе ячейку x_ij (рис. 12).

4. В ячейки ограничений ввести формулы (2) и (3) для представленных условий (рис. 13а и 13б).

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

6. Открываем меню СЕРВИС → ПОИСК РЕШЕНИЯ.

Устанавливаем в качестве целевой ячейки ссылку на формулу целевой функции. Определяем стремление к минимальному значению.

В строке «Изменяя ячейки» выделяем пустое поле, в котором будет проводиться поиск решения (рис. 14).

7. Добавляем по очереди все ограничения (рис. 15). Для данного случая во всех ограничениях будет стоять знак равенства, так как задача сбалансированная.

8. В меню «Параметры» отмечаем позиции «Линейная модель» и «Неотрицательные значения» (рис. 16).

9. Нажимаем «Выполнить» и получаем оптимальный план распределения перевозок между отправителями и получателями при соблюдении всех выдвинутых условий (рис.17).

Как можно видеть, все ограничения выполнены, значение целевой функции найдено. При полученном плане распределения перевозок суммарные затраты составят 770 ден. единиц, что соответствует минимально возможному значению.