Разбор задачи
Условие и материал
Закрытая транспортная задача
Транспортная задача — одна из распространенных задач линейного программирования.
Ее цель — разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.
В общем виде задачу можно представить следующим образом: в m пунктах производства A1, A2, ..., Am имеется однородный груз в количестве соответственно a1, a2,…, am.
Этот груз необходимо доставить в n пунктов назначения B1, В2, …., Вn в количестве соответственно b1, b2,..., bn.
Стоимость перевозки единицы груза (тариф) из пункта Ai в пункт Bj равна cij.
Требуется составить план перевозок, позволяющий вывезти все грузы и имеющий минимальную стоимость.
В зависимости от соотношения между суммарными запасами груза и суммарными потребностями в нем транспортные задачи могут быть закрытыми и открытыми.
Определение 1. ЕслиЕе цель — разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.
В общем виде задачу можно представить следующим образом: в m пунктах производства A1, A2, ..., Am имеется однородный груз в количестве соответственно a1, a2,…, am.
Этот груз необходимо доставить в n пунктов назначения B1, В2, …., Вn в количестве соответственно b1, b2,..., bn.
Стоимость перевозки единицы груза (тариф) из пункта Ai в пункт Bj равна cij.
Требуется составить план перевозок, позволяющий вывезти все грузы и имеющий минимальную стоимость.
В зависимости от соотношения между суммарными запасами груза и суммарными потребностями в нем транспортные задачи могут быть закрытыми и открытыми.
Если
Обозначим через xij количество груза, перевозимого из пункта Ai в пункт Bj.
Рассмотрим закрытую транспортную задачу. Ее условия запишем в распределительную таблицу, которую будем использовать для нахождения решения (табл. 23.1).
Рассмотрим закрытую транспортную задачу. Ее условия запишем в распределительную таблицу, которую будем использовать для нахождения решения (табл. 23.1).
Математическая модель закрытой транспортной задачи имеет вид
при ограничениях:
Транспортная задача как задача линейного программирования может быть решена симплексным методом, однако наличие большого числа переменных и ограничений делает вычисления громоздкими. Поэтому для решения транспортных задач разработан специальный метод, имеющий те же этапы, что и симплексный метод, а именно:
— нахождение исходного опорного решения;
— проверка этого решения на оптимальность;
— переход от одного опорного решения к другому.