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

В агрохолдинге имеется четыре склада, на которых хранится 1 350 т дизельного топлива, которое необходимо доставить в пять механизированных отрядов. Общая потребность механизированных отрядов в дизельном топливе составляет 1 300 т.

Информация о наличии дизельного топлива в разрезе складов и потребность в дизельном топливе в разрезе механизированных отрядов приведены в таблице 2.

Таблица 2. Информация о наличии и потребности в дизельном топливе, т

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

Информация о расстояниях между складами и механизированными отрядами приведена в таблице 3.

Таблица 3. Информация о расстояниях между складами и

механизированными отрядами, км

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

Исходные данные для решения транспортной задачи представлены на листе «Транспортная задача» файла MS Excel (рисунок 21).

После формирования таблицы с исходными данными необходимо сформировать в матричной форме экономико-математическую модель транспортной задачи, которая представлена на рисунке 16.

Каждое значение в ячейках (диапазон ячеек C12:G15) на пересечении столбца конкретного пункта потребления и строки склада означает количество тонн, поставляемых с этого склада в данный пункт потребления. Поэтому в первом опорном плане эти ячейки заполняются нулями.

Рисунок 21. Исходные данные для решения транспортной задачи

Рисунок 22. Исходные данные для решения транспортной задачи

Ячейки B12:B15 (Вывезено со склада) определяются суммированием элементов соответствующих строк. Например, ячейка B12=СУММ(C12:G12).

Ячейки C16:G16 (Доставлено потребителю) определяются суммированием элементов соответствующих столбцов. Например, ячейка C16СУММ(C12:C15).

В 18-ой строке в ячейках C18:G18 определим грузооборот по каждому пункту потребления. Грузооборот определяется как сумма произведений расстояний от конкретного пункта потребления до каждого из складов и объемов перевозок груза в этот пункт потребления с каждого склада. Пример формулы расчета ячейки С18 приведен в строке fx на рисунке 22.

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

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

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

Рисунок 23. Диалоговое окно команды Поиск решения

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

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

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

Рисунок 24. Диалоговое окно команды Поиск решения

В поле Ограничения: необходимо ввести все ограничения, накладываемые на поиск решения.

В разделе Ограничения: диалогового окна команды Поиск решения необходимо выбрать функцию Добавить. Появится следующее диалоговое окно (рис.25).

Рисунок 25. Диалоговое окно команды Добавление ограничения

Экономический смысл ограничений в данной задаче состоит в следующем:

· с каждого склада должно быть вывезено дизельного топлива не больше, чем на нем есть;

· потребности каждого потребителя должны быть удовлетворены полностью;

· объем грузоперевозок не может быть отрицательным.

То есть:

B12≤B5, B13≤B6, B14≤B7, B15≤B8 или $B$12:$B$15<=$B$5:$B$8;

C16=C4, D16=D4, E16=E4, F16=F4, G16=G4 или $C$16:$G$16=$C$4:$G$4

После ввода первого ограничения следует нажать кнопку Добавить и ввести второе ограничение. По окончании его ввода необходимо нажать на виртуальную кнопку ОК.

После выполнения вышеперечисленных инструкций диалоговое окно команды Поиск решения будет иметь следующий вид (рис. 26).

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

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

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

Опция Линейная модель в диалоговом окне команды Параметры поиска решения служит для ускорения поиска решения линейной задачи оптимизации.

Рисунок 27. Диалоговое окно команды Параметры поиска решения с заполненными полями

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

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

Рисунок 28. Диалоговое окно команды Результаты поиска решения

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

Прерывание поиска решения осуществляется нажатием клавиши ESC.

В результате решения и сохранения результатов поиска решения модель примет вид, представленный на рисунке 29.

Рисунок 29. Результаты поиска решения

В результате решения потребность всех механизированных отрядов удовлетворена полностью. Потребность в дизельном топливе механизированного отряда №1 (150 т) удовлетворяется полностью за счет запасов, имеющихся на складе №4. С этого же склада 170 т дизельного топлива доставляется в мехотряд №5. Еще 80 т, необходимые данному мехотряду, будут доставлены со склада №3.

Со склада №3 15 т дизельного топлива будут доставлены в мехотряд №2. Остальная потребность этого мехотряда (235 т) будет покрыта за счет дизельного топлива, хранящегося на складе №1. Потребность в дизельном топливе мехотряда №3 будет покрыта со склада №1 (13 т) и склада №2 (170 т). Вся потребность мехотряда №3 будет покрыта за счет доставки дизельного топлива со склада №2.

Со склада №3 остались невывезенными 50 т дизельного топлива.

Суммарный объем грузоперевозок составил 9 500 тонно-километров.

Задание для самостоятельной работы

Вопросы для самоконтроля

3.2. Решение задач оптимального выбора методами линейного
программирования