Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

ТРАНСПОРТНАЯ ЗАДАЧА И МЕТОДЫ ЕЕ РЕШЕНИЯ

Транспортная задача в матричной постановке и ее свойства. Вернемся к транспортной задаче в матричной, постановке, о которой мы уже упоминали при рассмотрении вопросов построения математических моделей. Напомним, что данная задача сводится к определению такого плана перевозок некоторого продукта из пунктов его производства в пункты потребления (║xi,jmxn), который минимизирует целевую функцию

на множестве допустимых планов

при соблюдении условия баланса

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

Если привести условия транспортной задачи к канонической форме задачи линейного программирования, то матрица задачи будет иметь размерность (m+n) х mn. Матрицы систем уравнений в ограничениях (3.2) и (3.3) имеют ранги, равные соответственно m и n. Однако, если, с одной стороны, просуммировать уравнения (3.2) по m, а с другой — уравнения (3.3) по n, то в силу (3.5) получим одно и то же значение. Из этого следует, что одно из уравнений в системе (3.2)-(3.3) является линейной комбинацией других. Таким образом, ранг матрицы транспортной задачи равен m+n-1, и ее невырожденный базисный план должен содержать m+n-1 ненулевых компонент.

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

Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта аi), а столбцы — пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится

цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (хi,j = 0), называют свободными, а ненулевые — занятыми (xi,j >0).