Информационные технологии в управлении и экономике
Скачать 0.8 Mb.
|
Семериков А. В. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Имитационный метод решения транспортной задачи | Simulation method for solving transport tasks |
| А. В. Семериков | А. V. Semerikov |
| Ухтинский государственный технический университет, г. Ухта, Россия | Ukhta state technical University, Ukhta, Russia |
| В статье рассматривается решение транспортной задачи методом имитационного моделирования. При реализации этого метода было установлено полное совпадение результатов расчёта с результатами расчёта на основе симплекс-метода. К достоинствам рассмотренного метода расчёта следует отнести возможность определения альтернативных маршрутов перемещения товара при одинаковой минимальной стоимости затрат на перемещение. Экспериментальными исследованиями была установлено, что при увеличении числа потребителей и поставщиков затраты машинного времени существенно превышают затраты машинного времени при реализации симплекс-метода. | The article discusses the solution of the transport problem by means of simulation. When implementing this method, it was established a complete coincidence of calculated results and calculation results based on the simplex method. The advantages of the considered method of calculation should include the possibility of identifying alternative routes for the movement of goods with the same minimum value of the cost of moving. Experimental research was found that increasing the number of consumers and suppliers of machine time costs significantly exceed the costs of machine time during the implementation of the simplex method. |
| Ключевые слова: линейное программирование, имитационное моделирование, транспортная задача, эксперимент. | Keywords: linear programming, simulation, transportation problem, experiment. |
Введение
Транспортные задачи – специальный класс задач линейного программирования. На основе решения этих задач определяется оптимальный объем перемещения какого-либо товара из исходного пункта, например место производства, в пункт потребления, например магазин. В качестве критерия оптимальности принимается минимум суммарной стоимости перевозок. При этом учитываются ограничения, налагаемые на объёмы товаров, имеющихся в пунктах производства, и ограничения на потребность в товарах в пунктах назначения. В транспортной модели предполагается, что стоимость перемещения товара по любому маршруту прямо пропорциональна объему товара.
В общем случае транспортная модель используется для описания и решения многих практических задач хозяйственной деятельности.
Транспортная задача может быть решена как обычная задача линейного программирования [1, 2]. Вместе с тем ее специальная структура позволила разработать алгоритм с упрощенными вычислениями, которые по форме отличаются от симплекс-метода, а по сути, повторяют его. Решение транспортной задачи осуществляется с помощью так называемой транспортной таблицы (табл. 1).
Таблица 1
| | D | F | производство | ||
| A | x1,1 | C1,1 | x1,2 | C1,2 | a1 |
| | | | | ||
| B | x2,1 | C2,1 | x2,2 | C2,1 | a2 |
| | | | | ||
| C | x3,1 | C3,1 | x3,2 | C3,3 | a3 |
| | | | | ||
| спрос | b1 | b2 | | ||
В этой таблице A, B, C – пункты производства, D, F – пункты потребления, x1,1.. x3,2 – количество товара, перемещённого товара из пунктов производства в пункты назначения, c1,1 … c3,2 – цена перемещения товара.
Метод решения транспортной задачи заключается в следующем:
1. Определяется начальное допустимое решение.
2. Выделяется из числа небазисных переменных переменная, вводимая в базис.
3. Выбирается выводимая из базиса переменная и определяется новое базисное решение.
Процесс расчета заканчивается, когда оценки у всех небазисных переменных становятся неположительные.
Экспериментальная часть
В настоящей статье предлагается следующий метод расчета.
1. Пункты производства A, B, C и пункты спроса идентифицируются соответственно 1, 2, 3 и 1, 2.
2. Определяются все перестановки чисел 1, 2, 3 и 1, 2. Каждый отдельный вид перестановки ассоциируется с порядком расположения пунктов производства и пунктов спроса. Например 1, 2, 3 означает, что первый в строке производителей находится A, второй B и третьим будет пункт C. В колонке потребителей первым стоит пункт D, а вторым пункт F.
3. Для каждого отдельного вида перестановки методом северо-западного угла определяются количество перемещенного товара из пунктов производства в пункты назначения.
4. Определяется общая стоимость перемещения товара для каждого вида перестановок.
5. Из полученного массива стоимости перемещения товаров выбирается наименьшая стоимость. Минимальной стоимости будут соответствовать оптимальные объемы перемещения товаров.
Для оценки адекватности рассмотренного метода было выполнено сравнение результатов решения с результатами решения транспортной задачи известным методом (табл. 2).
Таблица 2
| | D | F | производство | ||
| A | 0 | 5 | 100 | 3 | 100 |
| | | | | ||
| B | 200 | 7 | | 8 | 200 |
| | | | | ||
| C | | 11 | 300 | 4 | 300 |
| | | | | ||
| спрос | 200 | 400 | | ||
Оптимальное решение формулируется следующим образом. Перевести 100 единиц товара из пункта A в пункт F, перевести 200 единиц товара из пункта B в пункт D, перевести 300 единиц товара из пункта C в пункт D в пункт F. Суммарные транспортные затраты составят:
05 + 1003 + 2007 + 3004 = 2900 рублей.
Проиллюстрируем решение этой же задачи рассматриваемым методом.
1. Присвоим А = 1, B = 2, С = 3 и D = 1, F = 2.
2. Определим все перестановки чисел 123, 12, используя лексикографический метод [3].
Алгоритм перестановки состоит из четырех шагов.
а) найти справа налево число ai < ai+1. В данном случае это будет число am = 2.
б) выбрать слева направо наименьшее число больше числа am = 2. В данном случае это будет число ai = 3.
в) поменять местами числа am и ai.
г) переупорядочить все числа после числа ai.
В результате выполнения перечисленных вычислений получается набор чисел 1, 3, 2. Проводя подобным образом перестановки, получается следующий набор перестановок в количестве шести комбинаций 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 1, 2; 3, 2, 1. Из представленного примера перестановок видно, что алгоритм перебора заканчивает работу в момент времени при смене упорядоченности первоначальных чисел на противоположную (123 на 321).
Перестановку второго набора чисел 1, 2 можно провести только один раз. Весь набор перестановок состоит из двух комбинаций 1, 2; 2, 1.
Таким образом, используя полученные комбинации перестановок, представляется возможным в транспортной таблице шесть раз поменять местами строки таблицы и два раза ее столбцы. Общее число различных таблиц можно получить в количестве 62 = 12.
Для каждой полученной транспортной таблицы методом северно-западного угла определяем начальное решение. Например, для первой комбинации 1, 2, 3 и 1, 2 оно имеет решение (табл. 3).
Таблица 3
| | | vi | | | ||
| | | D | F | производство | ||
| u1 | A | 100 | 5 | | 3 | 100 |
| | | | | |||
| | B | 100 | 7 | 100 | 8 | 200 |
| | | | | | ||
| | C | | 11 | 300 | 4 | 300 |
| | | | | | ||
| | спрос | 200 | 400 | | ||
Суммарные транспортные затраты составят:
1005 + 1007 + 1008 + 3004 = 3200 рублей.
Для второй комбинации 1, 3, 2 и 1, 2 начальное решение имеет вид (табл. 4).
Таблица 4
| | D | F | производство | ||
| A | 100 | 5 | | 3 | 100 |
| | | | | ||
| С | 100 | 11 | 200 | 4 | 300 |
| | | | | ||
| В | | 7 | 200 | 8 | 200 |
| | | | | ||
| спрос | 200 | 400 | | ||
Суммарные транспортные затраты составят:
1005 + 10011 + 2004 + 2008 = 4000 рублей.
Для третьей комбинации 2, 1, 3 и 1, 2 начальное решение имеет вид (табл. 5).
Таблица 5
| | | vi | | | ||
| | | D | F | производство | ||
| u1 | В | 200 | 7 | | 8 | 200 |
| | | | | |||
| | А | 0 | 5 | 100 | 3 | 100 |
| | | | | | ||
| | С | | 11 | 300 | 4 | 200 |
| | | | | | ||
| | спрос | 200 | 400 | | ||
Суммарные транспортные затраты составят:
2007 + 1003 + 3004 = 2900 рублей.
4. Проводятся вычисления для всего набора комбинаций. Для комбинаций (1,2,3 и 1,2), (1,3,2 и 1,2), (2,1,3 и 1,2), (2,3,1 и 1,2), (3,1,2 и 1,2), (3,2,1 и 1,2), (1,2,3 и 2,1), (1,3,2 и 2,1), (2,1,3 и 2,1), (2,3,1 и 2,1), (3,1,2 и 2,1), (3,2,1 и 2,1) суммарные транспортные расходы соответственно составляют: 3100, 4000, 2900, 2900, 4500, 4500, 4500, 3300, 4000, 4000, 2900, 3200.
5. Из полученного массива стоимости выбирается наименьшая стоимость. В данном примере наименьшая стоимость перемещения товара равняется 2900, которая имеет быть место у трех схем перемещения. Для третьей комбинации схема перемещения товара может быть представлена в следующем виде (рис. 1).
Рисунок 1. Схема оптимального перемещения товара
Для проверки наличия оптимальности используется метод потенциалов. Для третьей комбинации схемы перемещения (табл. 5) потенциалы имеют следующие значения:
u1 + v1 = 5; u2 + v1 = 5; u2 + v2 = 3; u3 + v2 = 4;
u1 = 0; v1 = 7; v2 = 5; u2 = –2; u3 = –1.
Согласно полученных потенциалов оценки небазисных переменных принимают следующие значения: c1,2 = u1 + v2—8 = –10; c3,1 = u3 + v1- – 11 = –5.
Таким образом, коэффициенты у небазисных переменных имеют отрицательные значения. Это означает, что получены оптимальные значения. Оценки небазисных переменных для четвертой и одиннадцатой комбинаций так же имеют отрицательные значения.
Результаты
На основе рассмотренного метода разработано программное средство для автоматизации расчетов.
Сопоставление экспериментальных результатов расчета с результатами решения на основе симплекс-метода позволяет утверждать об адекватности рассматриваемого метода решения.
В процессе проведения экспериментов было установлено, что перемещение товаров может осуществляться по альтернативным маршрутам при одинаковой наименьшей стоимости затрат на перемещение. Получение этой информации при использование известных методов расчета не представляется возможным.
Затраты машинного времени при реализации рассмотренного метода расчета превышают затраты машинного времени при решении симплекс-методом. По этой причине использование его при большом количестве поставщиков и потребителей может быть оправдано для поиска альтернативных маршрутов.
Список литературы
1. Таха Х. А. Введение в исследование операций / Х. А Таха. 7-е изд.; пер. с англ. М. : Издательский дом «Вильямс», 2005. 912 с.: ил.
2. Решение задач ЛП онлайн симплекс методом. [Электронный ресурс] : Режим доступа http://www.uchimatchast.ru/.
3. Джеймс Андерсон. Дискретная математика и комбинаторика / Джеймс Андерсон; пер. с англ. М.: Издательский дом «Вильямс», 2004. 959 с.: ил.
List of references
1. Taha H. A. Introduction to operations research. 7th ed.; translation from English. Moscow, Publishing house Williams, 2005, 912 p., il.
2. The solution of problems LP online simplex method, Mode of access http://www.uchimatchast.ru/.
3. James Anderson, Discrete mathematics and combinatorics, translation from English. Moscow, Publishing house Williams, 2004, 959 p., il.
Рецензия
на статью « Семерикова А. В. Имитационный метод решения транспортной задачи // Информационные технологии в управлении и экономике. 2016. № 2»
Статья А. В. Семерикова посвящена решение транспортной задачи методом имитационного моделирования.
Актуальность данной статьи не вызывает сомнения, поскольку составление оптимального плана перевозок продукта из пункта наличия в пункт потребления является очень важной и необходимой составной частью задачи уменьшение транспортных издержек предприятия. Это является актуальным вопросом в условиях рыночной экономики, когда любые затраты должны быть минимизированы.
Новизна и оригинальность идеи, положенных в основу работы заключается в применении специальной структуры транспортной задачи, которая позволяет разработать алгоритм с упрощенными вычислениями, которые по форме отличаются от симплекс-метода, а по сути, повторяют его.
К достоинствам рассмотренного метода расчёта следует отнести возможность определения альтернативных маршрутов перемещения товара при одинаковой минимальной стоимости затрат на перемещение.
Автором проведена серьезная работа по проведению экспериментальных исследований, в ходе которых было установлено, что при увеличении числа потребителей и поставщиков затраты машинного времени существенно превышают затраты машинного времени при реализации симплекс-метода.
Следует отметить, что статья написана ясным языком, не перегружена излишней узкоспециальной терминологией. Выводы автора являются весьма обоснованными. Статья А. В. Семерикова «Имитационный метод решения транспортной задачи» представляет научный интерес и соответствует всем требованиям, предъявляемым к работам такого рода.
Данная статья может быть рекомендована к публикации.
08.11.2016
Дорогобед А. Н.
кандидат технических наук
Заместитель директора центра творческого развития студентов,
доцент кафедры вычислительной техники,
информационных систем и технологий
Ухтинского государственного
технического университета
УДК 005.934:332, ВАК 08.00.05, ГРНТИ 06.00.00
Похожие:
 | Методические указания предназначены для студентов экономических и других специальностей, изучающих дисциплины «Информационные системы»,... | | Цель. Научиться создавать презентации, редактировать их, проводить презентации в сети |
| Основные задачи манипулирования данными в ходе управленческой деятельности иллюстрируются на рисунке |  | Григорьев М. В. Информационные системы в экономике. Учебно-методический комплекс. Рабочая программа для студентов направления 02.... |
| Фгбоу впо «Российская академия народного хозяйства и государственной службы при Президенте Российской Федерации» | | Современная экономика характеризуется все ускоряющимися темпами научно-технического прогресса. Стремительно развиваются информационные,... |
| Арм, классификация и принципы построения; арм кадровой службы; вычислительные сети, нейросетевые технологии и средства мультимедиа;... | | Российская академия народного хозяйства и государственной службы при Президенте Российской Федерации |
| Дисциплина «Информационные системы в управлении международными проектами» является обязательной дисциплиной вариативной части дисциплин... | | Настоящее пособие предназначено для студентов Государственного института управления и социальных технологий бгу и ориентировано на... |