СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ НАХОЖДЕНИЯ ОПОРНОГО ПЛАНА ТРАНСПОРТНОЙ ЗАДАЧИ НА ПРИМЕРЕ ООО «КАРИ»

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

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

Транспортная задача нацелена на получение оптимального плана перевозок грузов из пунктов отправления в пункты потребления. имея наименьшие затраты на перевозки [1].

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

В данной научной статье мы рассмотрим: что такое опорный план и основные методы его нахождения. На основе исследования конкретной задачи мы выясним, какой из методов является лучшим.

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

Рисунок 1. Методы нахождения опорного плана задачи на примере ООО "Кари"

В городе Калуга осуществляет свою деятельность компания ООО «Кари». Она специализируется на розничной торговле обувью. В городе есть три склада. Обозначим их как А1, А2, А3. У них есть запас обуви в размере 200, 180,190 пар. Так же в городе функционирует 4 магазина. Обозначим их В1, В2, В3, В4. Им требуется поставка в размере 150,130,150, 140 пар обуви.

Тарифы на перевозку заданы в виде матрицы  рублей.

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

Запишем задачу в табличном виде:

Таблица 1.

Условие транспортной задачи

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

Первый метод, который мы рассмотрим - метод северо-западного угла.

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

Чтобы заполнить клетку ( i,j), нужно сравнить текущий запас товара в рассматриваемой i-й строке с текущей потребностью в рассматриваемом j-м столбце.

Если существующий запас позволяет перевезти всю потребность, то

• в клетку (i,j) в качестве перевозки вписывается значение потребности;
• j-й столбец вычеркивается, поскольку его потребность уже исчерпана;
• от существующего запаса в i-й строке отнимается величина сделанной перевозки, прежний запас зачеркивается, а вместо него записывается остаток, т.е.

Если же существующий запас не позволяет перевезти всю потребность, то:

• в клетку (i,j) в качестве перевозки вписывается значение запаса;
• i-я строка вычеркивается, поскольку ее запас уже исчерпан;
• от существующей потребности в j-й строке отнимается величина сделанной перевозки, прежняя потребность зачеркивается, а вместо нее записывается остаток, т.е.

Производим вычисления, пока все строки и столбцы не будут вычеркнуты все строки и столбцы [7].

Вернемся к нашему примеру. При использовании метода северо-западного угла, мы получили:

Таблица 2.

Решение методом северо-западного угла

Опорный план: 150*8+50*9+80*6+100*10+50*4+140*7= 4310 рублей.

Следующий метод, который будет применяться: метод минимального элемента.

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

Таблица 3.

Решение методом минимального тарифа

Опорный план: 150*2+50*3+150*5+30*9+130*3+60*7=2280 рублей.

Последний метод, который мы рассмотрим – метод Фогеля.

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

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

Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.

Таблица 4.

Решение методом Фогеля

Опорный план: 60*2+140*3+150*5+30*6+100*3+90*4= 1920 рублей.

Сделаем вывод, что из всех вычисленных опорных планов самым оптимальным является третий, который был получен методом Фогеля. Изучив различные источники литературы, а также опираясь на мнения некоторых ученных, мы пришли к мнению, что самым лучшим методом вычисления опорного плана является метод Фогеля. [1-3] Он дает правильное решение, максимально близкое к оптимальному. Но есть и недостаток у данного метода - на его решение уходит достаточно много времени. Поэтому целесообразно добавить, что для быстроты расчётов лучше использовать метод минимального тарифа. Он дает хороший результат и достаточно прост в вычислениях.

Список литературы:

1. Гетманчук, А. В. Экономико-математические методы и модели [Электронный ресурс]: Учебное пособие для бакалавров / А. В. Гетманчук, М. М. Ермилов. - М.: Издательско-торговая корпорация «Дашков и К», 2013. - 188 с. - ISBN 978-5-394-01575-5.
2. Леонид Витальевич Канторович: математика, менеджмент, инофрматика [Электронный ресурс] / Под ред. Г.А. Леонова, В.С. Катькало, А.В. Бухвалова. СПб.: Изд-во "Высшая школа менеджмента", 2009. - 575 с. - ISBN 978-5-9924-0044-1
3. Методы принятия управленческих решений: учебное пособие/Н.В.Кузнецова - М.: НИЦ ИНФРА-М, 2015. - 222 с.: 60x90 1/16. - (Высшее образование: Бакалавриат) (Переплёт) ISBN 978-5-16-010495-9, 500 экз.
4. Пантелеев, А. В. Методы оптимизации. Практический курс: учебное пособие с мультимедиа сопровождением [Электронный ресурс] / А. В. Пантелеев, Т. А. Летова. – М.: Логос, 2011. – 424 с: ил. (Новая университетская библиотека). - ISBN 978-5-98704-540-4.
5. Разработка управленческих решений: Учебное пособие / Е.В. Строева, Е.В. Лаврова. - М.: НИЦ Инфра-М, 2013. - 128 с.: 60x88 1/16. - (Высшее образование: Бакалавриат). (обложка) ISBN 978-5-16-005222-9
6. Федосеев, В. В. Экономико-математические методы и прикладные модели [Электронный ресурс]: Учеб. пособие для вузов / В. В. Федосеев, А. Н. Гармаш, И .В. Орлова и др.; Под ред. В. В. Федосеева. - 2-е изд., перераб. и доп. - М.: ЮНИТИ-ДАНА, 2012. - 304 с. - ISBN 5-238-00819-8.
7. Экономико-математические методы в примерах и задачах: Учеб. пос. / А. Н. Гармаш, И. В. Орлова, Н. В. Концевая и др.; Под ред. А.Н. Гармаша - М.: Вуз. уч.: НИЦ ИНФРА-М, 2014 - 416с.: 60x90 1/16 + ( Доп. мат. znanium.com).(п) ISBN 978-5-9558-0322-7, 700 экз.