Транспортная задача: Постановка

 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\]

А так как производится столько продукции, сколько ее потребляется (складируется), то:

 \[{a_i} = \sum\limits_{j = 1}^n {{x_{ij}}} ,\;\;\;\;i = 1,2, \ldots ,m\]

(продукт с предприятия вывозится полностью).

Далее, очевидным является то, что количество перевозимой с предприятия на склад продукции не может быть отрицательным, т.е.

x_{i,j} \ge 0 (i=1,2, ..., m; j = 1,2, ..., n)

Так как необходимо определить наилучший план перевозок по стоимости, то строим целевую функцию суммарных затрат на перевозки. Она должна быть минимизирована. Такая целевая функция имеет вид:

\[L = \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n {{c_{ij}}{x_{ij}}} } \]

Таким образом, имеем следующую математическую постановку задачи. Найти такие xij, которые доставляют минимум линейной форме L, т.е. и удовлетворяют условиям:

\[\sum\limits_{i = 1}^m {{x_{ij}} = {b_j}} ,\;\;\;\;j = 1,\;2,\; \ldots ,\;n\] (1)
\[\sum\limits_{j = 1}^n {{x_{ij}} = {a_i}} ,\;\;\;\;i = 1,\;2,\; \ldots ,\;m\] (2)
\[{x_{ij}} \ge 0,\;\;\;i = 1,\;2,\;...,\;m;\;\;\;\;j = 1,\;2,\;...,\;n\] (3)

 

Из (1) и (2) следует, что

\[\sum\limits_{i = 1}^m {{a_i} = \sum\limits_{j = 1}^n {{b_j}} } \]

закрытая транспортная задача

Именно в этом соотношении заключается основная специфика выделенного класса задач, так как это соотношение определяет дополнительное условие (как бы скрытое), которое позволяет произвольным образом распорядиться одной из переменных xij, а тем самым упростить решение задачи).

 

 

 




Наши друзья

Качественное решение задач курсовых работ, РГЗ по техническим предметам.
botaniks.ru

Околостуденческое

Рейтинг@Mail.ru

© 2009-2021, Список Литературы