Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,909

АЛГОРИТМИЧЕСКИЕ И ПРОГРАММНЫЕ СРЕДСТВА ДЛЯ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ

Приходькова И.В. 1 Тарасова И.А. 1 Авдеюк О.А. 1 Поляков В.С. 1 Наумов В.Ю. 1 Павлова Е.С. 1
1 ФГБОУ ВО «Волгоградский государственный технический университет»
В статье описана актуальность применения программных средств для решения оптимизационных задач линейного программирования на примере транспортных задач в поиске оптимального распределения однородных объектов с минимизацией затрат на перемещение в различных областях экономики и производства. Сделан вывод, что немашинный способ решения приводит к громоздким вычислениям и поэтому целесообразно использовать компьютерные расчеты. В связи с этим основное внимание в статье уделяется применению различных программных средств для решения таких задач. На конкретном примере описаны алгоритмы вычисления транспортной задачи с помощью пакета OpenOffice.org Calc , САПР MathCAD, Lingo (demo – версия). Анализ различных программных продуктов предоставляет возможность осуществить правильный выбор для решении транспортной задачи в зависимости от специфики технического задания. Выбор конкретного программного продукта зависит также от возможности пользователей и его целей.
транспортная задача
алгоритмы
оптимизация
программные средства
1. Решение транспортных задач: учеб. пособие / А.В. Семериков. – Ухта: УГТУ, 2013. – 58 с.
2. Симаков Е.Е. Решение транспортных задач с применением программирования в системе MathCAD / Е.Е. Симаков, Е. Ким // Молодой ученый. – 2014. – № 5. – С. 8–13.
3. Приходькова И.В. Информатика в транспортной отрасли: лабораторный практикум. Решение транспортных задач: учеб. пособие / И.В. Приходькова, И.Г. Лемешкина, Е.С. Павлова. – Волгоград: ВолгГТУ, 2014. – 80 с.
4. Лабораторная работа по теме «Оптимизация» [Электронный ресурс]. – URL: http://dump.vstu.ru/files/storage/Kafiedry/PM/Ochnaia_forma_obuchieniia/Dopolnitielnyie_ghlavy_matiematiki/Maghistry_6_kurs/Mietodichieskiie_ukazaniia/Lingo_Rieshieniie_niekotorykh_zadach_optimizatsii.pdf (дата обращения: 19.05.2017).
5. LINGO Demo [Электронный ресурс]. URL: http://www.hearne.software/Software/lingo/demos (дата обращения: 19.05.2017).
6. Скворцов А.В. Реализация пакета транспортных задач в геоинформационной системе ГрфИн [Электронный ресурс]. – URL: http://www.ict.edu.ru/ft/004479/25.pdf (дата обращения: 16.06.2017).
7. Фурина К.О. О Решении задач большой размерности в пакете MATHCAD на примере транспортной задачи / К.О. Фурина // Современные проблемы науки и образования. – 2015. – № 1–1. URL: https://science-education.ru/ru/article/view?id=17348 (дата обращения: 16.06.2017).
8. Бексултанов Ж.Т., Баетов А.К. Решение транспортной задачи с помощью программы «Оптимал» / Ж.Т. Бексултанов, А.К. Баетов // Известия вузов Кыргыстана. – 2016.– № 2. – С. 3–6. URL: https://elibrary.ru/item.asp?id=25829247.
9. Родина Е.В. Общая постановка и применение транспортной задачи в сфере железнодорожного обслуживания / Е.В. Родина, Р.Х. Нураева, Х.Х. Сафаралиева// Современные наукоемкие технологии. – 2013. – № 6. – С. 84–86. URL: https://top-technologies.ru/ru/article/view?id=31994 (дата обращения: 16.06.2017).
10. Цыплакова О.Н., Цысь Ю.В., Кобылина А.В. Транспортная задача и её применение в решении экономических задач / О.Н. Цыплакова, Ю.В. Цысь, А.В. Кобылина // Современные наукоемкие технологии. – 2014. – № 5–2. – С. 178–180.

Во многих областях производственно-экономической деятельности возникает необходимость в решении задач для определения максимального эффекта при заданных ограничениях на различные виды ресурсов [1]. Ввиду сложности современных объектов исследования для их модельного описания используются различные подходы, например – линейное программирование, частью которого являются транспортные задачи. В классическом варианте они ассоциируются с перемещением груза от поставщиков к потребителям. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки. Всё это уменьшает стоимость доставки товаров, связанные с осуществлением процессов снабжения материалами, сырьём, оборудованием, топливом и т.д. Тем не менее алгоритмы и методы решения транспортной задачи могут быть использованы при рассмотрении других типов задач, не относящихся к классу объектов транспортировки груза, например сетевое, календарное планирование, составление расписания, оптимальное обеспечение материальными ресурсами предприятия, распределение торговых агентов и т.д. Известно, что при использовании методов линейного программирования необходимо выполнять многочисленные последовательные арифметические операции, причем ошибка на любом этапе решения приводит к неверному конечному результату, а повторные вычисления зачастую занимают много времени. Поэтому широкое практическое использование этой теории связано с появлением ЭВМ и соответствующего программного обеспечения.

При решении транспортной задачи используют стандартные программные средства (например, OpenOffice.org Calc, MS Excel, САПР MathCAD и др.) и специализированные программы (например, Lingo (demo-версия)), в том числе написанные на определенном языке программирования высокого уровня.

Как показал анализ литературы, например [1, 2, 6–10], ранее не проводилась оценка сложности в использовании и сравнительные характеристики современных программных средств для решения транспортных задач, что предоставило бы удобный инструмент для специалиста в области автоматизации такого рода вычислений для решения задач различного масштаба производственных и торговых предприятий. Поэтому рассмотрение способов решения транспортной задачи с использованием наиболее распространенных алгоритмических и программных средств с последующим их анализом является актуальной задачей и обладает научно-практической новизной.

Для решения поставленной задачи в качестве примера решим следующую типовую транспортную задачу. В трех пунктах отправления A1, A2 и A3 находится соответственно 34, 30 и 27 т горючего. Потребителям В1, В2, В3 и В4 требуется соответственно 25, 19, 29 и 21 т горючего. Стоимость перевозки одной тонны горючего из пункта А1 в пункты В1, В2, В3 и В4 соответственно 6, 2, 5 и 5 рублей за тонну горючего, из А2 – 4, 7, 3 и 6 руб., а из В3 – 2, 4, 1 и 5. Составить оптимальный план перевозок горючего так, чтобы общая сумма транспортных расходов была наименьшей (таблица).

План перевозок горючего

 

В1

В2

В3

В4

Всего

А1

6

2

5

5

34

А2

4

7

3

6

30

А3

2

4

1

5

27

Всего

25

19

26

21

 

Для решения этой задачи воспользуемся программой OpenOffice редактором CALC. Данный программный продукт является бесплатным аналогом пакета MicrosofOffice Excel и содержит необходимый инструментарий для построения математических моделей и решения задач линейного программирования (в том числе транспортных задач). Алгоритм работы следующий [2, 3]:

1. Введем исходные данные в ячейки рабочего листа OpenOffice.ORG редактор CALC;

2. Разметим блоки ячеек на рабочем листе OpenOffice.ORG редактор CALC, необходимые для моделирования объемов перевозок, а также для формирования элементов математической модели и целевой функции;

3. Сформируем на рабочем листе OpenOffice.ORG редактор CALC элементы математической модели и целевую функцию;

4. Настроим программу «Поиск решения» или «Решатель» (в зависимости от версии программы) и выполним ее.

После выполнения пунктов 1, 2 и 3 получим рабочий лист OpenOffice.ORG CALC с размеченными блоками ячеек (рис. 1, а).

pr1a.tif

а)

pr1b.tif

б)

pr1c.tif

в)

Рис. 1. Решение транспортной задачи OpenOffice.ORG редактор CALC

5. Затем выберем из меню «Сервис» пункт «Решатель» и заполним поля в окне диалога программы (рис. 1, б).

6. После нажатия на клавишу «Решить» на рабочем листе получим решение нашей транспортной задачи (рис. 1, в).

Таким образом, можно сделать следующие выводы: решение транспортной задачи с помощью данного программного продукта имеет как ряд преимуществ, так и недостатков. К преимуществам можно отнести то, что OpenOffice.ORG CALC распространяется бесплатно и доступен любому пользователю, и за минимальное время возможно решить любую сбалансированную транспортную задачу. Недостатком является необходимость самостоятельной разработки пользователем математической модели, задание для нее ограничений и определение целевой функции, а это в свою очередь требует от пользователя математических знаний в данной области.

Теперь рассмотрим решение этой же задачи с помощью САПР MathCAD [2]. MathCAD – программное средство, среда для выполнения на компьютере разнообразных математических и технических расчетов, снабженная простым в освоении и в работе графическим интерфейсом, которая предоставляет пользователю инструменты для работы с формулами, числами, графиками и текстами.

pr2.tif

Рис. 2. Решение в MathCAD

При решении транспортной задачи в САПР MathCAD с помощью решающего блока необходимо (рис. 2):

1. Определить матрицу С и векторы a и b.

2. Сформировать функцию цели Z.

3. Задать матрицу начального приближения X.

4. В решающем блоке ввести ограничения, для этого необходимо сформировать массивы, в которых хранятся

prih01.wmf

5. Решить задачу оптимизации с помощью функции Minimize [1].

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

Также задача может быть решена с помощью пакета Lingo [4], который является традиционным пакетом для решения задач линейного, целочисленного и квадратичного программирования (рис. 3, 4).

pr3.tif

Рис. 3. Запись условия задачи в Lingo (demo-версия)

pr4.tif

Рис. 4. Окно решения задачи в Lingo (demo-версия)

pr5.tif

Рис. 5. Окно программы «Транспортная задача»

Несомненным преимуществом данного программного продукта является то, что модели в нем записываются в простой форме, соответствующей тому, как записываются уравнения на бумаге. В отличие от рассмотренных выше пакетов, Lingo позволяет решать несбалансированные (открытые) транспортные задачи. Из программных продуктов такого класса Lingo предлагает полный набор средств для изучения внутренней работы симплекс-метода, используемого для решения задач оптимизации линейных моделей. Также уникальным для Lingo является набор средств для целевого планирования, параметрического анализа, а также эффективного решения задач квадратичного программирования. Кроме того, полученные результаты позволяют проводить дальнейший анализ решаемой задачи. Несмотря на то, что доступна демо-версия пакета [5], полновесный пакет является платным.

Еще одним из вариантов является разработка программы самостоятельно. Например, написать на ЯВУ. Например, простейшая программа для решения транспортной задачи, разработанная в среде Delphi, будет выглядеть следующим образом (рис. 5). Программа реализует интуитивно понятный интерфейс и разработана для решения как транспортной задачи заданного условия варианта, так и для решения транспортных задач с другими исходными данными, удовлетворяющих условиям программы. Для ввода данных используется клавиатура. Данные, выводимые программой, соответствуют тем, что получены при расчетах вручную – методом наименьшего элемента и методом потенциалов, соответствуют решению в программах OpenOffice.org Calc, САПР MathCAD, Lingo (демо-версия).

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


Библиографическая ссылка

Приходькова И.В., Тарасова И.А., Авдеюк О.А., Поляков В.С., Наумов В.Ю., Павлова Е.С. АЛГОРИТМИЧЕСКИЕ И ПРОГРАММНЫЕ СРЕДСТВА ДЛЯ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ // Современные наукоемкие технологии. – 2017. – № 7. – С. 66-71;
URL: http://www.top-technologies.ru/ru/article/view?id=36731 (дата обращения: 21.01.2020).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074