Транспортная задача: Постановка
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)
(продукт с предприятия вывозится полностью).
Далее, очевидным является то, что количество перевозимой с предприятия на склад продукции не может быть отрицательным, т.е.
![x_{i,j} \ge 0 (i=1,2, ..., m; j = 1,2, ..., n)](https://spisok-literaturi.ru/cache/77fae92bd2a72bee91b0979304be8d83.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, а тем самым упростить решение задачи).