§ 15. Транспортная задача
| Сайт: | Профильное обучение |
| Курс: | Информационные технологии. 11 класс (Базовый уровень) |
| Книга: | § 15. Транспортная задача |
| Напечатано:: | Гость |
| Дата: | Четверг, 21 Ноябрь 2024, 20:50 |
15.1. Основные понятия
|
Транспортная задача — задача поиска такого плана перевозок одного вида товара от нескольких поставщиков к нескольким потребителям, который имеет минимальную стоимость. Транспортная задача является экономической задачей. Исходными данными в транспортной задаче являются:
Очевидно, что общий объем заявок равен общему объему поставок. Затраты на перевозку единицы груза по каждому маршруту обычно представляют в виде таблицы, которая называется таблицей удельных затрат на перевозки (пример 15.1). План перевозок в транспортной задаче — это список планируемых для перевозки объемов товара от каждого поставщика каждому потребителю (пример 15.2). В условиях транспортной задачи можно составить много различных планов перевозок. Но любой транспортной компании экономически выгоднее составить такой план перевозок, который обеспечит ей минимальные затраты на перевозку. |
Пример 15.1. Три сахарных завода (поставщики) должны по договору поставить сахар в пять магазинов (потребители). Объемы поставок рассчитываются в мешках. Известны объемы заявок магазинов и объемы поставок заводами. С транспортной компанией заключен договор на перевозку сахара. Затраты на перевозку мешка сахара с любого завода в любой магазин рассчитываются и представляются в виде таблицы удельных затрат на перевозки.
Например, затраты на перевозку мешка сахара со склада 1 в магазин 4 составляют 3 денежные единицы. Пример 15.2. Для плана перевозок удобно использовать форму таблицы удельных затрат на перевозку.
|
15.2. Постановка задачи (этап 1)
|
Задача. Три склада должны обеспечить поставку компьютерных мониторов в четыре магазина. Объемы заявок магазинов и объемы поставок складами заданы (пример 15.3). Транспортная компания, которая должна перевезти мониторы (штучный товар), рассчитала затраты на перевозку одного монитора по каждому маршруту и составила таблицу удельных затрат на перевозки (пример 15.4). Найти план перевозок с минимальной стоимостью. |
Пример 15.3. Объемы заявок (в шт.):
Объемы поставок (в шт.):
Пример 15.4. Таблица удельных затрат на перевозки (в денежных единицах на единицу товара):
|
15.3. Выбор плана создания модели (этап 2)
|
Особенность транспортной задачи заключается в том, что исходные данные задачи заданы тремя таблицами (см. примеры 15.3, 15.4). И результатом решения тоже должна стать таблица (см. пример 15.2). Поэтому сразу будем строить компьютерную расчетную модель в электронных таблицах (пример 15.5) без построения документальной математической модели. План создания модели для решения транспортной задачи включает только этап 3 — создание компьютерной расчетной модели в электронных таблицах. |
Математическую модель транспортной задачи впервые построил французский математик Гаспар Монж в 1781 году. Первый метод решения транспортной задачи в 1939 году предложил советский математик и экономист Л.В. Канторович. С тех пор разработано еще несколько методов решения этой задачи. Пример 15.5. Транспортная задача является экстремальной задачей, и ее решение в электронных таблицах Excel обеспечивает надстройка Поиск решения.
|
15.4. Создание компьютерной расчетной модели (этап 3)
|
Исходные данные компьютерной модели разместим по схеме, приведенной в примере 15.6. Расчетную таблицу будем строить по аналогичной схеме (пример 15.7). После ввода заголовков в ячейки A11 и A12 можно таблицу из раздела «Исходные данные» скопировать в раздел «Расчетная таблица» (пример 15.8). В ячейку A18 вводится надпись «Сумма». В ячейку B18 вводится формула суммы значений ячеек этого столбца расчетной таблицы. Затем этой формулой надо заполнить диапазон C18:E18. В ячейку F14 вводится надпись «Сумма». В ячейку F15 вводится формула суммы значений ячеек этой строки расчетной таблицы. Затем этой формулой заполняется диапазон F16:17. В задаче необходимо найти такой план перевозок, для которого их суммарная стоимость минимальна в сравнении с другими планами. Построим функцию V, которая вычисляет суммарную стоимость перевозок по заданному в модели плану. Затраты на перевозку товара по одному маршруту «склад i — магазин j» будут равны произведению стоимости перевозки на ее объем. Стоимость перевозки задана в ячейке таблицы удельных затрат, а объем — в такой же ячейке таблицы плана перевозок. Для построения функции V нужно перемножить значения соответствующих ячеек двух таблиц (диапазонов), а затем все произведения сложить. Введем формулу для вычисления функции V в ячейку А20 (пример 15.9). Теперь следует вызвать окно Параметры поиска решения и ввести исходные данные для поиска решения. Целевая функция V размещена в ячейке A20, критерий — Минимум, изменяя ячейки переменных диапазона B15:E17 (ячейки плана перевозок), переходим к вводу ограничений (пример 15.10). Так как товар штучный, следует ячейки диапазона B15:E17 плана перевозок сделать целыми и неотрицательными (см. пример 14.11). Под полем для ограничений должна стоять галочка выбора пункта Сделать переменные без ограничений неотрицательными. После настроек в окне Параметры поиска решения щелкаем по кнопке Найти решение. |
Пример 15.6. Схема размещения исходных данных компьютерной модели. Столбец A нужно расширить.
Пример 15.7. Схема размещения расчетной таблицы компьютерной модели транспортной задачи.
План перевозок справа и снизу обрамлен ячейками для сумм. Пример 15.8. Для копирования таблицы из раздела «Исходные данные» следует выделить диапазон A4:E8 и скопировать его на диапазон A13:E17. Начальные значения ячеек плана перевозок могут быть любыми числами, поэтому скопированные значения ячеек плана перевозок можно оставить. Пример 15.9. Для ввода значения функции V используем математическую функцию СУММПРОИЗВ(), которая возвращает сумму произведений ячеек двух диапазонов (массивов). Табличный курсор устанавливаем на ячейку A20, щелчком по кнопке Вставить функцию в строке формул, открываем окно Вставка функции. Проводим поиск функции по ее имени, затем дважды щелкаем по ее имени в списке. Открывается окно для ввода аргументов. В таблице выделяем диапазон B6:E8. Он записывается в поле аргумента Массив1. Затем в окне щелкаем по полю второго аргумента Массив2 и в таблице выделяем массив B15:E17. Щелчком по кнопке OK завершаем ввод. Пример 15.10. Нетрудно увидеть, что суммы в ячейках правее плана перевозок должны давать объемы поставок, которые заданы в правом столбце начальных данных. А суммы в ячейках ниже плана перевозок — объемы заявок, которые заданы в последней строке начальных данных. Такие ограничения Excel позволяет задавать как равенства диапазонов. Щелкаем по кнопке Добавить. В новом окне для ввода ограничений в левое поле выделяем диапазон B18:E18. Во втором поле выбираем знак равенства. В третье поле вводим диапазон B9:E9. Щелкаем по кнопке OK. Аналогично вводим условие равенства диапазонов F15:F17 и F6:F8. |
15.5. Исследование модели и получение решения задачи (этапы 4 и 5)
|
Исследование модели предполагает изучение ее адекватности. Адекватность проверяется сравнением полученных результатов с подтвержденными (пример 15.11). Решение транспортной задачи получено. |
Пример 15.11. Подтвержденные результаты решения задачи.
|
Упражнения
1. Повторите на компьютере рассмотренное в параграфе построение компьютерной расчетной модели для транспортной задачи и найдите решение этой задачи.
2. Решите транспортную задачу, уменьшив вдвое объемы заявок и объемы отгрузки в условиях задачи, рассмотренной в параграфе.
3. Решите следующую транспортную задачу. Компания владеет тремя заводами, которые производят штучную продукцию одного вида и имеют производительность 600, 300, 330 единиц продукции в год. Компания обязалась за год поставить в четыре города соответственно 350, 350, 230 и 300 единиц продукции. Таблица удельных стоимостей перевозки имеет вид:
4. Решите транспортную задачу со следующими исходными данными для штучного товара.
5. Решите транспортную задачу со следующими исходными данными для штучного товара.
