Статья: Метод сравнения альтернатив для поиска первоначального решения транспортной задачи

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

Т.Н. Зюзько

Государственный университет "Дубна", филиал "Протвино"

А.С. Курко

Московский технологический университет

Аннотация

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

Ключевые слова: логистика, транспортная задача, оптимизация перевозок, поиск первоначального решения, метод сравнения альтернатив.

Abstract

This article analyzes and solves linear programming formulation of transportation problem. The aim ofthis work is to create and describe new method ofchoosingfirst plan, which is directed to find effective solution of transportation problem, which is optimal in most of cases.

Key words: logistics, transportation problem, optimization of transportations, choosingfirst plan, method of comparing alternatives.

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

Рассмотрим закрытую транспортную задачу. Как известно, поиск оптимального решения в данном типе начинается с выбора первоначального распределения поставок. На каждом следующем шаге решение оптимизируется [1; 2]. При случайном выборе первоначального решения процесс поиска оптимума может состоять из большого числа шагов. Для поиска первого опорного плана используются специальные методы. Такими методами являются метод северо-западного угла, правило минимального элемента, метод аппроксимации Фогеля, метод двойного предпочтения и другие [3]. Первоначальное решение, найденное по любому из перечисленных методов, может быть изначально оптимальным или далеким от оптимума в зависимости от условий задачи и специфики выбранного пути решения [4]. Опишем возможный вариант поиска первоначального распределения поставок. Назовем его методом сравнения альтернатив.

Для описания алгоритма поиска введем следующие определения. Назовем издержкой ячейки затраты на перевозку единицы груза от /-го поставщика к j-му потребителю. Альтернативная издержка для данной ячейки - коэффициент затрат для ячейки, находящейся в одной и той же строке или одном и том же столбце с рассматриваемой ячейкой. Минимальная альтернативная издержка по столбцу для данной ячейки - минимально возможный коэффициент затрат для ячейки, находящейся в одном и том же столбце с рассматриваемой ячейкой. Минимальная альтернативная издержка по строке для данной ячейки - минимально возможный коэффициент затрат для ячейки, находящейся в одной и той же строке относительно рассматриваемой ячейки. Если минимальные альтернативные издержки по строке и столбцу - одно и то же число, то минимальная альтернативная издержка равна этому числу. Если минимальные альтернативные издержки по строке и столбцу - разные числа, то минимальная альтернативная издержка для данной ячейки - наибольшее число из этих двух вариантов. Экономический смысл минимальной альтернативной издержки - количество условных единиц, которое необходимо потратить на поставку одной единицы товара в другую ячейку в случае отказа от поставки в рассматриваемую ячейку (от данного поставщика данному потребителю). Минимальная альтернативная сумма издержек для рассматриваемой ячейки - сумма минимальных альтернативных издержек по строке и столбцу для рассматриваемой ячейки. Полная альтернативная сумма для рассматриваемой ячейки - общие затраты на поставки необходимого по условиям количества товара (по соответствующей строке и столбцу) при условии, что в данную ячейку поставок не было. Минимальная полная альтернативная сумма для рассматриваемой ячейки - минимально возможные общие затраты на поставки необходимого по условиям количества товара (по соответствующей строке и столбцу) при условии, что в данную ячейку поставки не было. Полные затраты для ячейки - произведение цены поставки для данной ячейки и максимального количества товара, которое возможно поставить в эту ячейку по условиям.

Метод сравнения альтернатив состоит из трех этапов проверки, каждый из которых определяет, в какие ячейки возможно отправить максимальную поставку для получения оптимального или близкого к оптимальному первоначального решения. Чтобы определить, в какую ячейку нужно отправить поставку, нет необходимости проходить все три этапа. Часто происходит так, что ячейка для заполнения определяется на первом или втором этапах. Если же на первом этапе получено несколько возможных для поставки ячеек, то производится второй этап. Аналогично и для второго этапа. Опишем каждый этап.

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

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

Пример 1 транспортной задачи

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

Приведем описание алгоритма поиска первоначального распределения поставок предложенным методом сравнения альтернатив.

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

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

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

Рассмотрим примеры решения задач данным методом

Пример 1 (табл. 1).

Т а б л и ц а 1 Матрица оценок свободных клеток для решения примера 2 методом аппроксимации Фогеля

1. Поиск первой ячейки.

1.1. Первый этап. Выбор ячеек (2,1), (2,5), (3,2), (3,3). Для них минимальные альтернативные издержки - 6, 15, 8, 8 соответственно, поэтому выбираем (2,5) для поставки (150 единиц товара). Закрывается вторая строка.

2. Поиск второй ячейки.

2.1. Первый этап. Выбор (3,2), (3,3). Для них минимальные альтернативные издержки - 8 и 9 соответственно. Выбор (3,3) для поставки (140 ед.). Закрывается третий столбец.

3. Поиск третьей ячейки.

3.1. Первый этап. Выбор (3,1) и (3,2). Для них минимальные альтернативные издержки - 15 и 8 соответственно, поэтому выбираем (3,1) для поставки (100 ед.). Закрывается первый столбец и третья строка.

4. Поиск четвертой ячейки.

4.1. Первый этап. Выбор (1,2) и (3,2). Для них минимальные альтернативные издержки - 11 и 15 соответственно, поэтому выбираем (3,2) для поставки (10 ед.).

Далее поставки однозначно определены условиями. Получим первоначальное решение (табл. 2), где в скобках указаны поставки.

При этом матрица оценок свободных клеток в результате будет следующей (табл. 3).

Это означает, что полученное решение является оптимальным распределением поставок. Решение данной задачи, найденное методами северо-западного угла, двойного предпочтения или минимального элемента будет неоптимальным. Заметим, что метод сравнения альтернатив не приводит к неоднозначности в отличие от метода минимального элемента, где возникает необходимость случайного выбора между ячейками с одинаковыми ценовыми коэффициентами (например, между (2,1), (2,5) и (3,3)).

Пример 2 (табл. 4).

Решим задачу методом аппроксимации Фогеля и рассмотрим полученное решение (табл. 5).

Т а б л и ц а 2 Первоначальное решение для примера 1