Лекция 3 Транспортная задача.
Вопросы:
Постановка транспортной задачи. Закрытая модель. Теорема о существовании решения.
Метод потенциалов: а) построение опорного плана; б) схема решения.
Метод дифференциальных рент.
Дополнительные ограничения транспортной задачи.
Постановка транспортной задачи. Закрытая модель. Теорема о существовании решения.
Транспортная задача является одним из наиболее важных частных случаев общей задачи линейного программирования, в силу специфики ее построения и области применения. Транспортная модель изначально предназначена для выбора наиболее экономного планирования грузопотоков и работы различных видов транспорта. Однако сфера применения транспортной модели этим не ограничивается. Примерами использования транспортной модели могут служить задачи календарного планирования производства, рационального использования природных и людских ресурсов и др.
Пусть в пунктах А1,А2,...,Аm производится некоторый продукт, причем объем производства в п. Аi составляет ai единиц, . Произведенный продукт должен быть доставлен в пункты потребления В1,В2,...,Вn, причем объем потребления в п. Вj составляет bj единиц, . Предполагается, что транспортировка готовой продукции возможна из любого пункта производства в любой пункт потребления, транспортные издержки на перевозку единицы продукции из п. Аi в п. Вj составляют Cij денежных единиц. Задача состоит в организации такого плана перевозок, при котором суммарные транспортные издержки были бы минимальными.
Математически транспортная задача может быть записана следующим образом. Пусть xij - количество продукта, перевозимого из п. Аi в п. Вj . Требуется определить совокупность (mn)величин xij , удовлетворяющих условиям:
(1)
и обращающих в минимум линейную форму
(2)
Специфическими для транспортной задачи являются следующие два обстоятельства: а) каждое из переменных xij входит в два уравнения системы (1); б) все коэффициенты при переменных xij принимают лишь два значения 0 или 1.
ОПРЕДЕЛЕНИЕ 1. Если общая потребность в продукте в пунктах потребления равна общему запасу продукта в пунктах производства, т.е.
, (3)
то модель транспортной задачи называется закрытой. Если это условие не выполняется, то модель называется открытой.
ТЕОРЕМА: Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы продукта в пунктах производства были равны потребностям в пунктах потребления, т.е. чтобы выполнялось равенство (3).
ЗАМЕЧАНИЯ:
1. Если запас превышает потребность, т.е. , вводится фиктивный (n+1)-й
пункт потребления с потребностью , а соответствующие
транспортные издержки равны нулю, Ci(n+1) = 0, i = .
2. Если потребности превышают запасы, т.е. , вводится фиктивный (m+1)-
й пункт производства с запасом , а соответствующие тарифы
равны нулю, C(m+1)j = 0, j = .
ОПРЕДЕЛЕНИЕ 2. Всякое неотрицательное решение системы линейных уравнений (1) называется планом транспортной задачи.
ОПРЕДЕЛЕНИЕ 3. План X* = ,;, при котором функция (2) принимает минимальное значение, называется оптимальным планом транспортной задачи.
Часто план транспортной задачи, с которого начинают решение, называют опорным.
Число переменных xij в транспортной задаче с m пунктами производства и n пунктами потребления равно mn, а число уравнений в системе (1) равно m+n. Т.к. предполагается, что выполняется условие (3), то число линейно независимых уравнений равно n+m-1. Следовательно, опорный план может иметь не более n+m-1 отличных от нуля неизвестных.
Если в опорном плане число отличных от нуля компонент равно в точности n+m-1 , то план является невырожденным, а если - меньше - то вырожденным.
Для определения оптимального плана транспортной задачи разработаны алгоритмы, существенно более простые, чем симплекс-метод, который является одним из основных методов решения задач линейного программирования. Наиболее известными из этих алгоритмов являются метод потенциалов и метод дифференциальных рент (или венгерский).