ПЗ 10. Решение транспортной задачи методом линейного программирования. Определение оптимальной загрузки оборудования

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

Транспортная задача (ТЗ) является важнейшей частной задачей линейного программирования, имеющей обширные практические приложения не только к проблемам транспорта. Она выделяется в линейном программировании определённостью экономической характеристики, особенностями математической модели, наличием специфических методов решения.

На рис. 1.11 показано общее представление транспортной задачи в виде сети с m пунктами отправления и n пунктами назначения, которые показаны в виде узлов сети. Дуги, соединяющие узлы сети, соответствуют маршрутам, связывающим пункты отправления и назначения. С дугой (i,j), соединяющей пункт отправления i с пунктом назначения j, соотносятся два вида данных: стоимость c_ij перевозки единицы груза из пункта i в пункт j и количество перевозимого груза x_ij. Объем грузов в пункте отправления i равен а_i, а объем грузов в пункте назначения j - b_j. Задача состоит в определении неизвестных величин х_ij минимизирующих суммарные транспортные расходы и удовлетворяющих ограничениям, налагаемым на объемы грузов в пунктах отправления (предложения) и пунктах назначения (спрос).

Рис. 1.11. Представление транспортной задачи

Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения. Имеются m пунктов отправления груза A₁, A₂,…,A_m и объемы отправления по каждому пункту а₁, a₂,…,a_m. Известна потребность в грузах b₁,b₂,…,b_n по каждому из n пунктов назначения B₁,B₂,…,B_n. Задана матрица стоимостей доставки по каждому варианту с_ij, i=1,2,…,m; j=1,2,…,n. Необходимо рассчитать оптимальный план перевозок, т. е. определить, сколько груза должно быть отправлено из каждого A_i-го пункта отправления (от поставщика) в каждый B_j-й пункт назначения (до потребителя) х_ij с минимальными транспортными издержками [1].

Тогда математическая модель транспортной задачи формулируется следующим образом :

Первое ограничение означают, что суммарный объем перевозок от i -го поставщика не может превышать имеющегося у него запаса товара a_i. Второе ограничение означают, что суммарные перевозки товара j -му потребителю должны полностью удовлетворить его потребности в товаре b_j. Третье ограничение исключает обратные перевозки.

Из первых двух ограничений следует, что

Если имеет место равенство

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

В случае превышения запаса над спросом, т.е. если

то вводится фиктивный (n + 1) -й потребитель со спросом

а соответствующие стоимости с_i,n+1 (i = 1,2,...,m) считаются равными нулю.

Аналогично, при

вводится фиктивный (m +1) -й поставщик с запасом товара

а соответствующие стоимости с_m+1,j (j = 1,2,...,n) считаются равными нулю.

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

Отметим, несбалансированную транспортную задачу называют также открытой транспортной задачей, тогда как сбалансированную транспортную задачу - закрытой транспортной задачей. Стремление сбалансировать транспортную задачу обусловлено возможностью применить в этом случае эффективный вычислительный метод.

Наиболее распространенным методом решения транспортных задач является метод потенциалов, который был предложен в 1949 г. советскими математиками Л.В. Канторовичем и М.К. Гавуриным. Решение задачи методом потенциалов включает следующие этапы : разработку начального плана (опорного решения); расчет потенциалов; проверку плана на оптимальность; поиск максимального звена неоптимальности (если полученный план не оптимальный); составление контура перераспределения ресурсов; определение минимального элемента в контуре перераспределения и перераспределение ресурсов по контуру; получение нового плана.

Число неизвестных переменных x_ij в транспортной задаче с m поставщиками и n потребителями равно m× n , а число уравнений в системе равно m+n. Так как транспортная задача является сбалансированной,, то число линейно независимых уравнений равно m+n-1. Следовательно, опорный план транспортной задачи может иметь не более m+n-1 отличных от нуля неизвестных. Если данное условие не выполняется, то план называется вырожденным.

Для транспортной задачи существует несколько методов отыскания начального плана (опорного решения): метод северо-западного угла; метод минимальной стоимости; метод Фогеля и т. д.

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

Рассмотрим наиболее часто встречающиеся ситуации в экономике предприятия .

1. Отдельные поставки от определенных поставщиков некоторым потребителям должны быть исключены (из-за отсутствия необходимых условий хранения, чрезмерной перегрузки коммуникаций и т. д.). Это ограничение требует, чтобы в матрице перевозок, содержащей оптимальный план, определенные клетки оставались свободными. Последнее достигается искусственным завышением затрат на перевозки с_ij в клетках, перевозки через которые следует запретить. При этом производят завышение величины с_ij до таких значений, которые будут заведомо больше всех, с которыми их придется сравнивать в процессе решения задачи.

2. На предприятии необходимо определить минимальные суммарные затраты на производство и транспортировку продукции. С подобной задачей сталкиваются при решении вопросов, связанных с оптимальным размещением производственных объектов. Здесь может оказаться экономически более выгодным доставлять сырье из более отдаленных пунктов, но зато при меньшей его себестоимости. В таких задачах за критерий оптимальности принимают сумму затрат на производство и транспортировку продукции.

3. Ряд транспортных маршрутов, по которым необходимо доставить грузы, имеют ограничения по пропускной способности. Если, например, по маршруту A_i – B_j можно провести не более q единиц груза, то B_j столбец матрицы разбивается на два столбца – B'_j и B''_j. В первом столбце спрос принимается равным разности между действительным спросом b_j и ограничением q: b'_j = b_j-q, во втором – равным ограничению q, т. е. b''_j = q. Затраты с_ij в клетке второго столбца равны данным, но в клетке первого столбца вместо истинного тарифа с_ij ставится искусственно завышенный тариф М (клетка блокируется). Затем задача решается обычным способом.

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

5. Экономическая задача не является транспортной, но в математическом отношении подобна транспортной, так как описывается аналогичной моделью, например распределение производства изделий между предприятиями, оптимальное закрепление механизмов по определенным видам работы.

6. Необходимо максимизировать целевую функцию задачи транспортного типа. В этой ситуации при составлении опорного плана в первую очередь стараются заполнить клетки с наиболее высокими значениями показателей с_ij. Выбор клетки, подлежащей заполнению при переходе от одного допустимого плана к другому, должен производиться не по минимальной отрицательной разнице [с_ij-(α_i+β_j)], а по максимальной этой разнице. Оптимальным будет план, которому в последней таблице сопутствуют свободные клетки с неположительными элементами: все разности [с_ij -(α_i+β_j)] ≤ 0.

7. Необходимо в одно время распределить груз различного рода по потребителям. Задачи данного типа называются многопродуктовыми транспортными задачами. В этих задачах поставщики m родов грузов разбиваются на m условных поставщиков, а потребители n родов грузов разбиваются на n условных потребителей. С учетом этой разбивки составляют полную транспортную таблицу. При этом заметим, что некоторые маршруты A_iB_j должны быть блокированы (закрыты), поскольку в данной постановке задачи грузы разного рода не могут заменять друг друга. Этим маршрутам A_iB_j должна соответствовать очень высокая стоимость перевозки. Многопродуктовую задачу не всегда обязательно описывать одной моделью. Например, если поставки грузов различного рода независимы, то задачу можно представить в виде комплекса транспортных задач по каждому роду груза. Однако, если между грузами различного рода существует связь (например, одни из грузов можно заменить другими), то в общем случае исходную модель (задачу) не удается разбить на комплекс простых транспортных задач.

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Лесин В.В. Основы методов оптимизации : учеб. пособие [для вузов] / В. В. Лесин, Ю. П. Лисовец. - 3-е изд., испр. - СПб. : Лань, 2011 - 341 с.

2. Аттеков А.В. Методы оптимизации [Электронный ресурс] : учеб. пособие / А. В. Аттеков. - М. : ИЦ РИОР [и др.], 2013. - 270 с. - (ЭБС "znanium.com"). - Режим доступа: http://znanium.com/.- Загл. с экрана.

3. Балдин К.В. Математическое программирование [Электронный ресурс] : учебник / К. В. Балдин, Н. А. Брызгалов, А. В. Рукосуев ; под общ. ред. К.В. Балдина. - М. : Дашков и К°, 2013. - 220 с. - (ЭБС "znanium.com "). - Режим доступа: http://znanium.com/.- Загл. с экрана.

4. Юрьева А.А. Математическое программирование [Электронный ресурс] : учеб. пособие / А. А. Юрьева. - СПб. : Лань, 2014. - 432 с. - (ЭБС "Издательство Лань"). - Режим доступа: http://e.lanbook.com/.- Загл. с экрана.