Математика/5. Математическое моделирование

 

Чумаченко С.В.

Костанайский государственный университет имени А. Байтурсынова,

Казахстан

Чумаченко А.А.

Санкт-Петербургский государственный морской технический университет, Россия

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

 

         Транспортная задача – математическая задача линейного программирования об оптимальном распределении однородных объектов от аккумулятора к приемникам с минимизацией затрат на перемещение. В общем случае условие классической транспортной задачи представляется следующим образом: имеется m различных поставщиков некоторой продукции A1, A2,…, Am с объемами производства a1, a2,…, am соответственно и n потребителей B1, B2,…, Bn с потребностями b1, b2,…, bn соответственно, а также известны стоимости перевозок от каждого i-ого поставщика к каждому j-ому потребителю cij. Требуется найти количество груза xij, перевозимого от всех поставщиков ко всем потребителям с минимизацией общих затрат.

         Математическая модель задачи может быть построена на основании таблицы 1.

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

.

 

 

Таблица 1. Условие транспортной задачи

потребитель

поставщик

B1

B2

Bn

b1

b2

bn

A1

a1

c11

x11

c12

x12

c1n

x1n

A2

a2

c21

x21

c22

x22

c2n

x2n

Am

am

cm1

xm1

cm2

xm2

cmn

xmn

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

         Способы решения транспортной задачи обычно делятся на два этапа: нахождение начального опорного плана и нахождение оптимального плана. К методам нахождения опорного плана относятся: метод северо-западного угла, метод минимального элемента и метод аппроксимации Фогеля. Суть метода северо-западного угла состоит в том, что на каждом шаге максимально заполняется верхняя левая клетка. При таком методе заполнение таблицы всегда начинается с клетки x11 и заканчивается клеткой xmn.

         В отличие от предыдущего способа, в методе минимального элемента нет общего случая начальной и заключительной клеток. Из всей таблицы выбирается клетка с наименьшими транспортными затратами cij, в которую помещают наименьшее из чисел ai и bj, после этого строку с обнулившейся потребностью или столбец с полностью распределенным запасом вычеркивают и действия повторяются сначала.

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

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

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

Для программной же реализации достаточно привычно представление и решение задачи с помощью графов. Рассматривается двудольный граф. В нем потребители и поставщики, находясь в разных долях, соединяются ребрами с неограниченной пропускной способностью и стоимостью за единицу потока cij. К доле производителей подсоединяется исток, а к доле потребителей – сток. Пропускная способность ребер из истока в каждый пункт производства и из стока в каждый пункт потребления равна запасу продукта в этом пункте для производителей и потребности для потребителя. Цена за единицу потока у таких ребер равна нулю. Решается задача нахождения максимального потока минимальной стоимости. Данный алгоритм может выполняться как при имеющемся опорном плане, так и без него, но в этом случае процесс решения будет более долгим. Но, тем не менее, данный способ можно назвать  одноэтапным [1,2].

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

1. Задача об оптимальной обработке деталей станками. Имеется m станков, каждый из которых тратит на обработку детали на каждом из n этапов некоторое известное время. Требуется найти,  сколько времени и на каком этапе надо использовать каждый из станков, чтобы обработать максимальное количество деталей. Решение данной задачи надо начать с переписывания условия в форме транспортной задачи. Для этого в качестве «поставщиков» можно задать станки, а в качестве «потребителей» - этапы обработки детали. Тогда в данной задаче роль cij (стоимость перевозок) будет выполнять время, затрачиваемое i-ым станком на выполнение j-ого этапа обработки. Таким образом, задача сведена к решению транспортной задачи.

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

3. Задача управления запасами. Рассматривается некоторая фирма, спрос на продукцию которой отмечается в течение некоторого промежутка времени t. Известен спрос на продукцию, за каждую единицу времени и ее возможный выпуск за этот же период. Спрос и производство в каждую единицу времени не совпадают друг с другом. За непоставку продукции на фирму накладывается штраф. Также известны затраты на хранение единицы товара из перепроизводства. Требуется составить оптимальный план производства в течение времени t. Проведя аналогию с транспортной задачей заметим, что производитель будет заменен на период производства, потребитель – на период потребления. Соответственно, объемом производства заменится на объем производства за период, потребности потребителей – на объем спроса на продукцию за период. Стоимость перевозки же будет представлять собой сумму цены продукции, затраты на хранение и штраф за непоставку. Таким образом, вид задачи упрощается, и она может быть легко решена.

4. Задача о назначениях. В данной задаче требуется распределить m различных работ по n станкам, которые могут выполнять эти работы. i-ая работа на j-ом станке выполняется с затратами cij. Задача ставится как распределение работ по станкам с минимизацией затрат. Эта задача также может быть рассмотрена как частный случай транспортной задачи. В данных условиях справедливо положить предложение в каждом исходном пункте равным 1. Со спросом в каждом пункте потребления поступим аналогично. Невозможность выполнения какой-либо работы на некотором станке аналогична запрещенной перевозке в транспортной задаче, поэтому по аналогии с ней затраты cij примем равными очень большому числу.

Таблица 2. Структура задачи о назначениях

станки

виды работ

№ 1

№ 2

n

1

1

1

1

1

c11

c12

c1n

2

1

c21

c22

c2n

m

1

cm1

cm2

cmn

         Т.к. каждая работа производится только на одном станке, а каждый станок, соответственно, выделяется под определенный вид работы, ясно, что задача имеет смысл, когда m равно n. Исходя из специфики задачи о назначениях, компоненты плана и ограничения приобретают вид:

;  .

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

 

Литература

1. Павлова Т.Н, Ракова О.А. Решение задач линейного программирования. Учебное пособие. Димитровград, 2002.

2.https://ru.wikipedia.org/wiki/Транспортная_задача.

3. Апатенок Р.Ф. Математика для экономистов. М, Просвещение, 2004.