Учебное_пособие_по_Excel1. В инженерных и экономических расчетах
Скачать 4.49 Mb.
|
7.3. Решение транспортной задачиВ общем виде транспортную задачу можно сформулировать следующим образом: в m пунктах отправления A1, …, Am находится однородный груз, количество которого равно соответственно a1, …, am единиц. Данный груз необходимо доставить потребителям B1, …Bn, спрос которых – b1,…bn. Стоимость перевозки единицы груза из i-го ( ) пункта отправления в j-й ( ) пункт назначения равен сij. Необходимо составить план перевозок, который полностью удовлетворяет спрос потребителей в грузе, и при этом суммарные транспортные издержки минимальны. Математически транспортную задачу можно записать так: Таким образом, даны система ограничений (2) при условии (3) и линейная функция (1). Требуется среди множества решений системы (2) найти такое неотрицательное решение, которое доставляет минимум линейной функции (1). Модель транспортной задачи называют закрытой (сбалансированной), если суммарный объем груза, имеющегося у поставщика, равен спросу потребителей, т.е. выполняется равенство: . Если для транспортной задачи выполняется одно из условий: , то модель задачи называют открытой (несбалансированной). Для разрешимости транспортную задачу с открытой моделью следует преобразовать в закрытую. Если выполняется условие , то необходимо ввести фиктивный (n+1) –й пункт назначения Bn+1, т.е. в матрицу задачи вводится дополнительный столбец. Спрос фиктивного потребителя принимается равным . Стоимость перевозок продукции полагается одинаковой, чаще всего равной нулю (если не задана стоимость складирования продукции), т.е. . Если выполняется условие , то необходимо ввести фиктивного (m+1)-го поставщика Am+1, т.е. в матрицу задачи вводится дополнительная строка. Запас груза данного поставщика принимается равным . Стоимость перевозок продукции полагается одинаковой, чаще всего равной нулю (если не задана стоимость штрафов за недопоставку продукции), т.е. . При преобразовании открытой задачи в закрытую целевая функция не меняется, так как все слагаемые, соответствующие дополнительным перевозкам, равны нулю. Пример 7.3. Транспортная задача Производство продукции осуществляется на четырех предприятиях, а затем развозится в 5 пунктов потребления. Предприятия могут выпускать в день 235, 175, 185 и 175 единиц продукции. Пункты потребления готовы принимать ежедневно 125, 160, 60, 250 и 175 единиц продукции. Хранение на предприятии единицы продукции обходится в 2 у.е. в день, штраф за недопоставленную продукцию – 3,5 у.е. в день. Стоимость перевозки единицы продукции (в у.е.) с предприятий в пункты потребления приведена в таблице 7.6. Таблица 7.6 Транспортные расходы
Решение Проверка сбалансированности модели задачи – модель является сбалансированной, так как суммарный объем производимой продукции в день равен суммарному объему потребности в ней: 235+175+185+175 = 125+160+60+250+175. Поэтому при решении этой задачи не учитываются издержки, связанные со складированием и недопоставкой продукции. Построение математической модели – неизвестными в этой задаче являются объемы перевозок. Пусть xij – объем перевозок с I-го предприятия в j-й пункт потребления. Суммарные транспортные расходы – это функционал качества (критерий цели): где cij – стоимость перевозки единицы продукции с i-го предприятия в j‑й пункт потребления. Неизвестные в этой задаче должны удовлетворять следующим ограничениям: объемы перевозок не могут быть отрицательными; поскольку модель сбалансирована, то вся продукция должна быть вывезена с предприятий, а потребности всех пунктов потребления должны быть полностью удовлетворены. Итак, имеем следующую задачу: найти минимум функционала: при ограничениях: где ai – объем производства на i–м предприятии, bj - спрос в j-м пункте потребления. Решение задачи с помощью окна Поиск решения. 3.1. Подготовку рабочего листа для задачи осуществляем в соответствии с рис. 7.11, формулы для расчета приведены в таблице 7.7. 3.2. Ввод данных в окно Поиск решения производим в соответствии с рис.7. 12. 3.3. Полученное оптимальное решение представлено на рис. 7.13. Рис. 7.11. Исходные данные для решения транспортной задачи Таблица 7.7 Формулы для расчета в транспортной задаче
Рис. 7.12. Ввод данных в окно Поиск решения для транспортной задачи Рис. 7.13. Оптимальное решение для транспортной задачи |