Транспортная задача: Постановка
1. Постановка транспортной задачи.
Среди задач линейного программирования выделяется класс задач, условия постановки которых в определенной степени позволяют упростить процедуру их решения и определить специфические алгоритмы нахождения этих решений. Этот класс задач получил название "Транспортные задачи".
Рассмотрим постановку таких задач.
Пусть имеем m предприятий A1, A2,..., Am, производящих один и тот же продукт в количествах соответственно a1, a2,..., am.
Пусть, далее, имеется n потребителей (складов) B1, B2,..., Bn с потребностями (вместимостями) соответственно b1, b2,..., bn.
Пусть весь произведенный продукт может быть размещен на складах B1, B2,..., Bn при полном их заполнении.
Пусть, наконец, перевозка единицы продукции из пункта Ai в пункт Bj оценивается величиной cij (cij - заданы).
Необходимо определить наилучший план перевозок по стоимости, т.е. такой план, который давал бы минимальную стоимость перевозок всей произведенной продукции на склады.
Строим математическую модель.
Пусть xij - количество продукта, перевозимого из пункта Ai в пункт Bj. Из постановки задачи очевидно, что каждый склад вмещает:
![\[{b_j} = \sum\limits_{i = 1}^m {{x_{ij}}} ,\;\;\;\;j = 1,2, \ldots ,n\]](https://spisok-literaturi.ru/cache/8c2cf3f984825bb300e87e7f3f612050.png)
А так как производится столько продукции, сколько ее потребляется (складируется), то:
![\[{a_i} = \sum\limits_{j = 1}^n {{x_{ij}}} ,\;\;\;\;i = 1,2, \ldots ,m\]](https://spisok-literaturi.ru/cache/27dc00c1f304a9a9b4c8cea2e50a6888.png)
(продукт с предприятия вывозится полностью).
Далее, очевидным является то, что количество перевозимой с предприятия на склад продукции не может быть отрицательным, т.е.
Так как необходимо определить наилучший план перевозок по стоимости, то строим целевую функцию суммарных затрат на перевозки. Она должна быть минимизирована. Такая целевая функция имеет вид:
![\[L = \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n {{c_{ij}}{x_{ij}}} } \]](https://spisok-literaturi.ru/cache/e20505bfa707c73af54427b062dcb8e9.png)
Таким образом, имеем следующую математическую постановку задачи. Найти такие xij, которые доставляют минимум линейной форме L, т.е. и удовлетворяют условиям:
Из (1) и (2) следует, что
![\[\sum\limits_{i = 1}^m {{a_i} = \sum\limits_{j = 1}^n {{b_j}} } \]](https://spisok-literaturi.ru/cache/f2b21b64c06bc8fbda9ff37e43e337d0.png)
закрытая транспортная задача
Именно в этом соотношении заключается основная специфика выделенного класса задач, так как это соотношение определяет дополнительное условие (как бы скрытое), которое позволяет произвольным образом распорядиться одной из переменных xij, а тем самым упростить решение задачи).
![\[\sum\limits_{i = 1}^m {{x_{ij}} = {b_j}} ,\;\;\;\;j = 1,\;2,\; \ldots ,\;n\]](https://spisok-literaturi.ru/cache/e3b6d3eeb00a35d830041850710621d9.png)
![\[\sum\limits_{j = 1}^n {{x_{ij}} = {a_i}} ,\;\;\;\;i = 1,\;2,\; \ldots ,\;m\]](https://spisok-literaturi.ru/cache/079a795cb810d11c07c2b5a15af778d4.png)
![\[{x_{ij}} \ge 0,\;\;\;i = 1,\;2,\;...,\;m;\;\;\;\;j = 1,\;2,\;...,\;n\]](https://spisok-literaturi.ru/cache/e8b9559a0e4f582837ac09c777ec9d8e.png)
