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

Транспортная задача является классической задачей исследования операций. Множество задач распределения ресурсов сводится именно к этой задаче.

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

Исходные данные:

Склады	Наличие продукции, т.
Склад №1
Склад №2
Склад №3
Склад №4
Склад №5

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

 

Пункты	Потребность в продукции, т.
1 пункт
2 пункт
3 пункт
4 пункт

Расстояния между складами и пунктами доставки.

	Пункт 1	Пункт 2	Пункт 3	Пункт 4
Склад №1
Склад №2
Склад №3
Склад №4
Склад №5

На пересечении столбца конкретного пункта доставки со строкой склада находится информация о расстояниях между этими пунктом доставки и складом. Например, расстояние между 3 пунктом и складом №3 равно 10 километрам.

Для решения задачи подготовим необходимые таблицы (рис. 2.14).

Рисунок 2.14 – Изменяемые ячейки

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

Например, значение ячейки B4=СУММ(C4:F4)

Значения ячеек по 9 строке по столбцам от С до F определяются суммированием данных ячеек соответствующих столбцов с 4 по 8 строки.

Например, значение ячейки С9=СУММ(C4:C8)

Каждое значение в ячейках на пересечении столбца конкретного пункта доставки и строки склада означает количество тонн, поставляемых с этого склада в данный пункт потребления. В нижней строке (строка 9) суммируется общее количество минеральных удобрений, поставляемых в определенный пункт доставки, а во втором столбце (столбец В) суммируется количество доставленного с конкретного склада минеральных удобрений.

Теперь, используя исходные данные, введем на этом же листе требуемые объемы поставок и расстояния между складами и пунктами доставки (рис.2.15).

Рисунок 2.15 – Исходная информация

В строке 16 по столбцам C-F определим грузооборот по каждому пункту доставки. К примеру для 1 пункта (ячейка С16) это рассчитывается с помощью формулы

С16=С4*С11+С5*С12+С6*С13+С7*С14+С8*С15

либо можно использовать функцию СУММПРОИЗВ

С16=СУММПРОИЗВ(C4:C8;C11:C15)

В ячейке С4 находится количество минеральных удобрений, перевозимых со склада №1 в 1 пункт доставки, а в ячейке С11 – расстояние от склада №1 до 1 пункта доставки. Соответственно первое слагаемое в формуле означает полный грузооборот по данному маршруту. Вся же формула вычисляет полный грузооборот перевозок минеральных удобрений в 1 пункт доставки.

В ячейке В16 по формуле =СУММ(С16:F16) будет вычисляться общий объем грузооборота минеральных удобрений.

Таким образом, информация на рабочем листе примет следующий вид (рис. 2.16)

Рисунок 2.16 – Рабочий лист, подготовленный для решения
транспортной задачи

Для решения транспортной задачи воспользуемся процедурой Поиск решения, которая находится в меню Сервис.

После выбора данной команды появится диалоговое окно (рис. 2.17).

Рисунок 2.17 – Диалоговое окно Поиск решения

Поскольку в качестве критерия оптимизации нами выбрана минимизация грузооборота, в поле Установить целевую ячейку введите ссылку на ячейку, содержащую формулу расчета общего объема грузооборота минеральных удобрений. В нашем случае это ячейка $B$16. Чтобы минимизировать значение конечной ячейки путем изменения значений влияющих ячеек (влияющими, в данном случае это и изменяемые ячейки, являются ячейки, которые предназначены для хранения значений искомых неизвестных), переключатель установите в положение минимальному значению;

В поле Изменяя ячейки введите ссылки на изменяемые ячейки, разделяя их запятыми; либо, если ячейки находятся рядом, указывая первую и последнюю ячейку, разделяя их двоеточием ($С$4:$F$8). Это означает, что для достижения минимального грузооборота перевозок будут меняться значения в ячейках с С4 по F8, то есть будут изменяться количество груза, перевезенного по конкретному маршруту.

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

В группе полей Ограничения нажмите кнопку Добавить. Появится диалог Добавление ограничения (рис. 2.18)

Рисунок 2.18 – Диалоговое окно Добавление ограничения

Следует ввести левую часть ограничения в левое поле, выбрать знак условия, накладываемого на значение и ввести правую часть ограничения. Как и в других случаях, можно не вводить ссылки на ячейки, а выделить мышью эти ячейки. После ввода одного ограничения следует нажать кнопку Добавить и ввести следующее. По окончании ввода всех ограничений нажмите на кнопку ОК. В диалоге появятся строки введенных ограничений (рис. 2.19)

Рисунок 2.19 – Диалоговое окно Поиск решения
с заполненными полями

Для изменения и удаления ограничений в списке Ограничения диалогового окна Поиск решения укажите ограничение, которое требуется изменить или удалить. Выберите команду Изменить и внесите изменения либо нажмите кнопку Удалить.

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

Первое условие $B$4:$B$8 <=$B$11:$B$12. Оно означает, что значение в ячейке В4 должно быть меньше или равно значению в В11, в В5 меньше или равно, чем в В12, и так далее до В8 и В15.

В ячейках с В4 по В8 на листе находятся объемы поставок с конкретных складов. В ячейках с В11 по В15 – запасы на этих же складах. Так как невозможно вывести со склада больше, чем на нем есть, первое значение должно быть не больше второго.

Второе условие $С$4:$F$8>=0. Оно означает, что объем перевозок не может быть отрицательным, то есть, если на складе не хватает минеральных удобрений, их не везут с пункта доставки, на который эти минеральные удобрения были завезены ранее. Грузопоток имеет только одно направление – от складов к пунктам доставки удобрений.

И. наконец, третье, и последнее условие $С$9:$F$9>=$C$10:$F$10. Оно означает, что значения в ячейках девятой строки должны быть больше или равны значениям в ячейках десятой строки, то есть запросы пунктов доставки минеральных удобрений должны быть выполнены полностью. Перевыполнение объема поставок допустимо, а недовыполнение – нет.

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

После нахождения решения появляется диалог Результаты поиска решения (рис. 2.20)

Рисунок 2.20 – Диалоговое окно Результаты поиска решения

Нажав кнопку ОК, вы занесете вариант решения на рабочий лист (рис. 2.21).

Минимальный грузооборот перевозок при соблюдении всех условий равен 3540 т/км.

Дата добавления: 2014-10-22