Постановка задачи

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

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

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

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

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

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

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

Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения. Имеются m пунктов отправления груза и объемы отправления по каждому пункту a ₁, a ₂,..., a_m. Известна потребность в грузах b ₁, b ₂,..., b_n по каждому из n пунктов назначения. Задана матрица стоимостей доставки по каждому варианту c_ij, . Необходимо рассчитать оптимальный план перевозок, т.е. определить, сколько груза должно быть отправлено из каждого i -го пункта отправления (от поставщика) в каждый j -ый пункт назначения (до потребителя) x_ij с минимальными транспортными издержками.

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

Таблица 3.1. Исходные данные

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

(3.1)

Если такого равенства нет (потребности выше запасов или наоборот), запасу называют открытой, т.е.:

(3.2)

Для написания модели необходимо все условия (ограничения) и целевую функцию представить в виде математических уравнении.

Все грузы из i -х пунктов должны быть отправлены, т.е.:

, (3.3)

Все j -е пункты (потребители) должны быть обеспечены грузами в плановом объеме:

, (3.4)

Суммарные объемы отправления должны равняться суммарным объемам назначения (3.1). Должно выполняться условие неотрицательности переменных: , , . Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели):

(3.5)

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

- потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;

- запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.

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

Транспортным задачам присущи следующие особенности:

- распределению подлежат однородные ресурсы;

- условия задачи описываются только уравнениями;

- все переменные выражаются в одинаковых единицах измерения;

- во всех уравнениях коэффициенты при неизвестных равны единице;

- каждая неизвестная встречается только в двух уравнениях системы ограничений.

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

Опорный план является допустимым решением транспортной задачи и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. "Качество" опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее.

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

Дата добавления: 2017-02-01