Определение оптимального плана транспортных задач, имеющих некоторые усложнения в их постановке

Введение

 

Транспортная задача (ТЗ) является представителем класса задач линейного программирования и поэтому обладает всеми качествами линейных оптимизационных задач, но одновременно она имеет и ряд дополнительных полезных свойств, которые позволили разработать специальные методы ее решения. ТЗ является одной из наиболее распространенных специальных задач линейного программирования. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О. Н. Толстым. Первая строгая постановка транспортной задачи принадлежит Ф. Хичкоку, поэтому в зарубежной литературе ее называют проблемой Хичкока.

Первый точный метод решения ТЗ разработан Л. В. Канторовичем и М. К. Гавуриным. Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. [1] Однако ее специфическая структура позволяет так модифицировать симплекс-метод, что вычислительные процедуры становятся более эффективными. При разработке метода решения транспортной задачи существенную роль играет теория двойственности.

В классической транспортной задаче рассматриваются перевозки (прямые или с промежуточными пунктами) одного или нескольких видов продукции  из исходных пунктов в пункты назначения. Эту задачу можно видоизменить, включив  в нее ограничения сверху на пропускные способности транспортных коммуникаций. Задачу о назначениях и задачу управления запасами можно рассматривать как задачи транспортного типа.  [2, с.58]

 

 

1 Определение оптимального  плана транспортных задач, имеющих  некоторые усложнения в их  постановке

1.1 Транспортная задача

 

Транспортная задача (ТЗ) – это математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.

Под термином "транспортные задачи" понимается широкий круг задач не только транспортного характера. Общим для них является, как  правило, распределение ресурсов, находящихся  у m производителей (поставщиков), по n потребителям этих ресурсов. В качестве критериев в транспортных задачах используют: критерий стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию), критерий времени (план оптимален, если на его реализацию затрачивается минимум времени) и другие.

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

•        прикрепление потребителей ресурса к производителям;

•        привязка пунктов отправления к пунктам  назначения;

•        взаимная привязка грузопотоков прямого и  обратного направлений;

•        отдельные  задачи оптимальной загрузки промышленного  оборудования;

•        оптимальное  распределение объемов выпуска  промышленной продукции между заводами-изготовителями и др.

Пусть имеется m поставщиков А₁, А₂, ...,А_m однородного груза в количествах соответственно а_1, а₂,...,а_m единиц и n потребителей В_1, В₂,...,В_n этого груза, потребность которых составляет соответственно b₁, b_2,...,b_n единиц. Известна стоимость (тариф) c_ij перевозки единицы груза от  i-го (i= поставщика к j-му ( потребителю. Требуется составить такой план прикрепления потребителей к поставщикам, т.е. план перевозок, при котором весь продукт вывозится из пунктов A_i в пункты B_j в соответствии с потребностью и общая величина транспортных издержек будет минимальной.

 

Таблица 1 – Исходные данные транспортной задачи

Bj Ai	b1	b2	...	bn
a1	c11	c12	...	c1n
a2	c21	c22	...	c2n
...	...	...	...	...
am	cm1	cm2	...	cmn

 

При постановке конкретных задач перевозки грузов может  возникнуть одна из трех ситуаций:

                                                                            

                                                                                          (1)

                          

                       (2)

                                             (3)

Каждой ситуации соответствует  определенная модель ТЗ: ситуации (1) (суммарный  объем груза, имеющегося у поставщиков, равен суммарному  спросу потребителей) отвечает закрытая модель ТЗ (сбалансированная транспортная модель), а ситуациям (2) и (3) - отвечает открытая модель ТЗ (несбалансированная транспортная модель).

Рассмотрим ситуацию (1). Обозначим  через  количество единиц груза, которое необходимо доставить от i-го поставщика к j-му потребителю.

Экономико-математическая модель ТЗ должна отражать все условия и  цель задачи в математической форме. Переменные должны удовлетворять ограничениям по запасам, потребностям и условиям неотрицательности. В математической форме эти условия можно записать так:

                                                                                                            (4)

                   

                                            (5)                 

                                                                   (6)

 

Цель ТЗ - минимизировать общие затраты на реализацию плана  перевозок, которые можно представить  функцией:

  (7)

Итак, математически ТЗ ставится так.

Даны система ограничений (4) и (5) (ограничения (5) отражают тот факт, что весь груз от всех поставщиков должен быть вывезен, а ограничения (4) отражают тот факт, что каждый потребитель должен получить ровно столько груза, сколько ему необходимо) при условии (6) и линейная функция (7). Найти такое неотрицательное решение, при котором линейная функция (7) принимает минимальное значение.

Для того, чтобы ТЗ (4)-(7) имела допустимые планы, необходимо и достаточно выполнение равенства (1)

Решение транспортной задачи состоит из двух этапов:

   1 этап. Нахождение начального плана перевозок (x_ij), удовлетворяющего ограничениям (4)-(6);

   2 этап. Улучшение  начального плана перевозок и  получение оптимального плана  перевозок (x_ij), доставляющего минимум функции (7).

 

 

 

1.2 Методы отыскания оптимального решения транспортной задачи

 

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

Отсюда вытекает способ отыскания  оптимального решения транспортной задачи, состоящий в том, что, имея некоторое базисное решение, вычисляют алгебраические суммы тарифов для всех свободных клеток. Если критерий оптимальности выполнен, то данное решение является оптимальным; если же имеются клетки с отрицательными алгебраическими суммами тарифов, то переходят к новому базису, производя пересчет по циклу, соответствующему одной из таких клеток. Полученное таким образом новое базисное решение будет лучше исходного – затраты на его реализацию будут меньшими. Для нового решения также проверяют выполнимость критерия оптимальности и в случае необходимости снова совершают пересчет по циклу для одной из клеток с отрицательной алгебраической суммой тарифов и т. д.

Через конечное число шагов  приходят к искомому оптимальному базисному  решению.

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

В зависимости от методов  подсчета алгебраических сумм тарифов для свободных клеток различают два метода отыскания оптимального решения транспортной задачи:

1. Распределительный метод. 

При этом методе для каждой пустой клетки строят цикл и для каждого цикла непосредственно вычисляют алгебраическую сумму тарифов.

2. Метод потенциалов. 

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

Преимущества метода потенциалов  по сравнению с распределительным методом состоят в том, что отпадает необходимость построения циклов для каждой из пустых клеток и упрощается вычисление алгебраических сумм тарифов. Цикл строится только один – тот, по которому производится пересчет.

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

Следует иметь в виду, что потенциалы (так же как и  циклы) для каждого нового базисного  плана определяются заново.

 

1.3 Усложнённые задачи  транспортного вида

 

1. Транспортная задача с избытком запасов:

Для отыскания оптимального плана вводят фиктивный (n+1)-й пункт назначения B_n+1 с потребностью b_n+1 и полагают стоимости перевозок грузов в B_n+1 равными нулю. Полученная новая транспортная задача является закрытой. Найдя оптимальный план x_ij этой транспортной задачи и отбрасывая в полученной таблице последний столбец, получим оптимальный план исходной транспортной задачи.

2. Транспортная задача с избытком заявок:

Эта задача несколько сложнее  предыдущей: дело в том, что как  ни развози грузы, все потребности  удовлетворить все равно не удается. Поэтому постановка задачи нуждается  в уточнении.

1. Все пункты назначения требуется удовлетворить пропорционально поданным заявкам. В этом случае, подсчитав коэффициент пропорциональности

и «подправив» заявки: получим закрытую модель транспортной задачи.

2. Если не заботиться о «справедливости» удовлетворения заявок, а по-прежнему интересоваться лишь минимизацией транспортных расходов, то для отыскания оптимального плана вводят фиктивный пункт (m+1)-й отправления A_m+1 с запасом груза a_m+1 и полагают стоимости перевозок грузов из A_m+1 равными нулю. Полученная транспортная задача является закрытой. Найдя оптимальный план x_ij этой транспортной задачи и отбрасывая в полученной таблице последнюю строку, получим оптимальный план исходной транспортной задачи.

И в случае 1 и в случае 2.2 при преобразовании открытой задачи в закрытую, целевая функция не меняется, так как все слагаемые, соответствующие дополнительным перевозкам, равны нулю.

3. Транспортная задача с поиском максимума целевой функции.

Перейдем к целевой  функции Z=-F и найдем план ( , доставляющий ей минимум. Тогда ( будет оптимальным и для исходной задачи, причем ( .

4. Транспортная задача с запретными маршрутами.