Виды моделей транспортной задачи
Транспортная задача
Рассмотрим так называемую транспортную задачу по критерию стоимости. Данная задача используется для оптимизации планирования грузоперевозок.
Постановка задачи
1. В m пунктах отправления , которые будем в дальнейшем называть поставщиками, сосредоточено определенное количество единиц некоторого однородного продукта, которое обозначим
.
Однородный – одного вида (например: пищевые продукты, одежда, обувь, ткани).
2. Данный продукт потребовался в n пунктах , которые будем называть потребителями. Объем потребителя обозначим
.
3. Известны расходы на перевозку единицы продукта из пункта в пункт
, которые равны
и приведены в матрице транспортных расходов
.
4. Требуется составить такой план прикрепления потребителей к поставщикам, т.е. план перевозок, при котором
1) весь продукт вывозится из пунктов в пункты
в соответствии с потребностью
2) общая величина транспортных издержек будет минимальной.
|
![Виды моделей транспортной задачи Виды моделей транспортной задачи - student2.ru](/images/biologiya/vidy-modeley-transportnoy-zadachi-33444-12.gif)
Обозначим количество продукта, перевозимого из пункта в пункт
через
. Тогда получим матрицу перевозок
.
А также матрицу стоимости перевозок (иногда ее называют «матрицей тарифов»)
Тогда целевая функция задачи имеет вид
(1)
а ограничения выделяют следующим образом:
(2)
(Условие по потребности)
(3)
(Условие по запасам)
(4)
Необходимым и достаточным условием того чтобы задача имела решение, является условие баланса:
(5)
Транспортная задача, в которой имеет место равенство (5) называется закрытой.
Решение транспортной задачи состоит из 2-х этапов:
1) Нахождение первоначального опорного плана.
2) Нахождение оптимального плана перевозок по методу потенциалов.
Виды моделей транспортной задачи
Модель транспортной задачи включает в себя: целевую функцию (1) и систему ограничений (2), (3) и (4).
Модель транспортных задач бывает 2-х типов.
1. Закрытая модель .
Для того чтобы решать транспортную задачу ее необходимо привезти к закрытому виду.
Для закрытых моделей доказана теорема о существовании допустимого плана.
Теорема. Для того чтобы транспортная задача имела допустимые планы необходимо и достаточно, чтобы объем запасов совпадал с объемом потребностей.
2. Открытые модели:
2а) Запасы превышают потребности
В этом случае вводится фиктивный потребитель , потребности которого равны
. Стоимость перевозки единицы груза от поставщиков к
-му потребителю равна 0.
2б) Потребности превышают запасы
В этом случае вводится фиктивный поставщик . Запасы которого равны
.
Построение первоначального опорного плана
В транспортной задаче существуют понятия вырожденного и невырожденного плана.
План невырожденный, когда количество занятых клеток равно , где m – число поставщиков, n – число потребителей.
План вырожденный, когда количество занятых клеток .
Если план оказывается вырожденным, то следует часть свободных клеток условно считать занятыми. Для этого в них реально записываются нули, которые стоят там «негласно». Это делают в одной или нескольких клетках, исходя из требования, состоящего в том, что общее число занятых клеток должно быть . В дальнейшем с другими клетками обращаются как с занятыми.
Поставщики | Потребители | Запасы | ||||
![]() | ![]() | ![]() | … | ![]() | ||
![]() | ![]() ![]() | ![]() ![]() | ![]() | |||
![]() | ![]() | |||||
![]() | ![]() | |||||
… | … | |||||
![]() | ![]() ![]() | ![]() | ||||
Потребности | ![]() | ![]() | ![]() | … | ![]() |