II. Двухиндексные задачи ЛП (транспортная задача)

Информационные системы и технологии

Практическая работа №7. Использование электронных таблиц EXCEL при решении транспортной задачи

Цель – изучить информационную технологию определения оптимального маршрута на основе применения инструмента МS Excel «Поиск решения». Теоретический раздел – лекция №7.

Задачи маршрутизации, предназначенные для определения маршрутов и составления графиков перевозок, вызывает у предприятий значительный интерес благодаря тому, что выбор оптимального маршрута позволяет сократить транспортные расходы на 10-15 и более процентов%.

Метод потенциалов и другие методы решения транспортной задачи являются довольно затратными по времени. Применение информационной технологии в виде надстройки МS Excel Поиск решения позволяет повысить производительность управленческого труда, получить экономию ресурсов.

Методические указания

II. Двухиндексные задачи ЛП (транспортная задача)

Постановка задачи. Существует запас однотипной продукции у поставщиков I3 (200 т), I4 (120 т), I5 (180 т). Существует потребность в этой продукции потребителей C8 (150 т), D8(150 т), E8(100 т), F8(100 т). Стоимость доставки 1т груза от поставщика i потребителю j в условных единицах представлена в таблице С11:F13.

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

Рассмотрим решение транспортной задачи, представленной в табл. 7.1.

Таблица 7.1

Целевая функция задачи выглядит следующим образом:

где x_ij =0, если поставка в эту клетку отсутствует, и , если поставка имеется. Из условия того, что все поставщики должны полностью реализовать свои «запасы», а потребители – полностью удовлетворить свои потребности, следует система ограничений (по строкам и столбцам) (7.1):

(7.1)

С учетом смысла задачи (например, перевозка людей) добавим условие неотрицательности и целочисленности переменных:

x_ij 0; x_ij =целое (i = 1; 2; 3; j = 1; 2; 3; 4).

Экранная форма ввода условий задачи показана на рис. 7.11.

Рис. 7.1

Формула расчета целевой функции введена в ячейку Н13. Как и в случае одноиндексных задач, она вводится с помощью функции суммпроизв содержимого всех ячеек переменных x_ij на коэффициенты ЦФ (тарифы). В ячейки диапазона (G3:G6) вводятся левые части ограничений по строкам; в ячейки диапазона (C6:E6) – левые части ограничений по столбцам с помощью функции сумм. В табл. 6.4 приведено соответствие условий математической модели их выражениям в Excel.

Таблица 7.4

Далее, как и в случае одноиндексных задач, открываем окно Поиск решения (рис. 7.2).

Рис. 7.2

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

Экранная форма решения транспортной задачи показана на рис. 6.3.

Рис. 7.3

Сравниваем решение этой задачи, полученное в разделе 4 (пример 5.4), с рис. 6.3.