Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65

Статья опубликована в рамках: XLVIII Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ЭКОНОМИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 05 декабря 2016 г.)

Наука: Экономика

Секция: Менеджмент

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Кузнецова Ю.И., Гасанова М.Т. СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ НАХОЖДЕНИЯ ОПОРНОГО ПЛАНА ТРАНСПОРТНОЙ ЗАДАЧИ НА ПРИМЕРЕ ООО «КАРИ» // Научное сообщество студентов XXI столетия. ЭКОНОМИЧЕСКИЕ НАУКИ: сб. ст. по мат. XLVIII междунар. студ. науч.-практ. конф. № 11(48). URL: https://sibac.info/archive/economy/11(48).pdf (дата обращения: 22.09.2021)
Проголосовать за статью
Конференция завершена
Эта статья набрала 0 голосов
Дипломы участников
Диплом лауреата
отправлен участнику

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

Кузнецова Юлия Игоревна

студент, кафедра экономики и менеджмент, ФГБОУ ВПО «Калужский филиал Российской академии народного хозяйства и государственной службы при Президенте Российской Федерации», г. Калуга

Гасанова Мадия Токтархановна

студент, кафедра экономики и менеджмент, ФГБОУ ВПО «Калужский филиал Российской академии народного хозяйства и государственной службы при Президенте Российской Федерации», г. Калуга

Научный руководитель Мезенцева Анна Сергеевна

кандидат технических наук, доцент, кафедра естественнонаучных и математических дисциплин, ФГБОУ ВПО «Калужский филиал Российской академии народного хозяйства и государственной службы при Президенте Российской Федерации», г. Калуга

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

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

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

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

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

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

 

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

 

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

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

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

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

Таблица 1.

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1

8

9

2

3

200

A 2

5

6

10

9

180

A 3

10

3

4

7

190

Потребность

150

130

150

140

570

 

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

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

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

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

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

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

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

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

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

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

Таблица 2.

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

 

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1

150 8

50 9

2

3

200

A 2

5

80 6

100 10

9

180

A 3

10

3

50 4

140 7

190

Потребность

150

130

150

140

570

 

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

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

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

Таблица 3.

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1

8

9

150 2

50 3

200

A 2

150 5

6

10

30 9

180

A 3

10

130 3

4

60 7

190

Потребность

150

130

150

140

570

 

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

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

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

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

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

Таблица 4.

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

Поставщик

Потребитель

Запас

Штрафы

B 1

B 2

B 3

B 4

A 1

8

9

60 2

140 3

200

1

6

 

 

A 2

150 5

30 6

10

9

180

1

1

1

1

A 3

10

100 3

90 4

7

190

1

1

1

7

Потребность

150

130

150

140

570

 

Штрафы

3

3

2

4

 

3

3

2

 

5

3

6

 

5

3

 

 

 

Опорный план: 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 экз.
Проголосовать за статью
Конференция завершена
Эта статья набрала 0 голосов
Дипломы участников
Диплом лауреата
отправлен участнику

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом