Сравнительный анализ методов решения транспортной задачи

Размещено на http://www.allbest.ru/

СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

В.В. Крейдунова, С.Н. Мунько

Омский государственный технический университет, г. Омск, Россия

Аннотация - В работе изложены основные особенности решения транспортной задачи линейного программирования, в реальных практических задачах, с привлечением статистических данных по этим задачам. Для исследования и сравнительного анализа методов решения использованы возможности программного комплекса MathCAD, табличного процессора MSExcel и системы компьютерной алгебры MAPLE. В результате сравнительного анализа полученных решений была выбрана наиболее эффективная технология решения транспортной задачи.

Ключевые слова: транспортная задача, диагональный метод, метод минимального элемента, аппроксимация Фогеля, метод двойного предпочтения, транспортная сеть, пропускная способность.

программирование задача транспортный

Введение. Ежедневно каждый человек решает проблему, как получить наилучший эффект, имея ограниченные средства. Для достижения наибольшего эффекта, с ограниченными средствами, необходимо составить план или программу действий. В середине ХХ века был создан специальный математический инструмент, который помогает решить эту проблему. Соответствующий раздел математики называют математическим моделированием [1]. Большая часть поставленных на практике задач математического программирования слишком объемные для ручного подсчета, поэтому они могут быть решены только при помощи ЭВМ. Транспортная задача является частью линейного программирования. Такие задачи играют особую роль в снижении транспортных издержек предприятия. Это актуально в условиях рыночной экономики, где любые затраты должны быть сведены к минимуму, потому что тогда расходы покрывают часть прибыли и снижаются затраты на производство.

Под названием «транспортная задача» объединяется широкий круг задач с единой областью исследования. Как правило, такие задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи имеет свою специфику, поэтому для ее решения разработаны специальные методы [2]. Эти методы позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение [3]. Целью исследования является нахождение эффективного способа реализации методов решения.

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

Сравнение эффективности полученных решений. Решение транспортной задачи в MS Excel является наиболее упрощенным, по сравнению с системами компьютерной алгебры. Математические возможности табличного процессора MS Excel значительно уступают системам Maple и MathCad. Для решения ТЗ в программе MS Excel реализованы приближенные методы их решения с достаточно высокой степенью точности, но используя такую технологию, в результате получаем лишь опорный план. Оценить точность получаемых решений можно посредством сравнения аналитических и алгоритмических решений отдельных практических задач [4].

Табличный процессор MS Excel эффективнее использовать в совокупности с другими техническими средствами, например, с MathCad. Excel не только способен дополнить эту компьютерную среду эффективными способами решения различных прикладных задач, но и расширить границы ее применимости.

Одним из преимуществ решения ТЗ в Excel является мощная надстройка <Поиск Решения>, которая существенно облегчает работу в табличном процессоре. Для получения числового значения показателя эффективности применяются различные математические методы поиска.

MS Excel имеет следующие преимущества.

1) Реализация алгоритма решения ТЗ в табличном процессоре не требует специальных знаний в области программирования. Большинство расчетов средней сложности может быть представлено в виде некоторого набора достаточно простых математических формул в ячейках, выполняемых шаг за шагом.

2) Программа в табличном процессоре создается путём задания взаимосвязи ячеек, расположенных в пространстве листа. Такой подход использует интуитивные представления человека о пространстве и связи явлений, тем самым облегчая работу заполнения листа MS Excel.

3) В отличие от обычного программирования, требующего строгой последовательности команд для работы программы, MS Excel допускает ошибки и незаконченность структуры. Какие-то части программы в электронной таблице могут работать, в то время, как другие части могут быть ещё не закончены, что значительно упрощает разработку и отладку программ, что особенно важно на стадии создания алгоритма.

4). Ячейки листа MS Excel всегда открыты и доступны для пользователя, что позволяет контролировать результаты промежуточных действий и, при необходимости, изменять содержимое ячеек, гибко меняя алгоритм.

5). Ячейки таблицы могут содержать не только формулы, но и простой текст, что позволят описывать и комментировать логику работы программы, располагая на листе текстовые комментарии.

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

Главным недостатком решения ТЗ с использованием электронных таблиц MS Excel является низкая производительность при работе с большими объемами данных, а также ограничиваются предельные показатели. Таким образом, решение ТЗ в MS Excel является эффективным для таблиц небольшой размерности.

Для ТЗ большой размерности целесообразно использовать системы компьютерной алгебры. Наиболее известными из них являются Maple и MathCad.

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

Выделим преимущества системы компьютерной алгебры Maple.

1) Работа в пакете Maple ведется интерактивно, т.е. пользователю нужно только ввести команды и тут же на экране появляется результат их выполнения или сообщение об ошибке, так как есть вероятность неправильно введенной команды, затем выдается предложение ввести команду заново.

2) В отличие от обычной среды программирования в пакете Maple не требуется жесткая формализация всех переменных и действий с ними. Выбор нужных типов переменных и проверка правильности выполнения операций ведется автоматически.

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

4) Система Maple имеет свой язык программирования, который предназначен для быстрой реализации различных подпрограмм.

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

Ещё одним мощным программным комплексом для решения ТЗ является MathCad, который, с одной стороны, позволяет с помощью программных блоков реализовывать сложные алгоритмы, а с другой благодаря простому интерфейсу и синтаксису, доступен массовому пользователю. Кроме того, MathCad предоставляет широкие возможности для эффективного взаимодействия с различными программными системами и, в частности, с Excel. При этом вычисленные в MathCad документе значения можно передавать в Excel-документ и там с помощью функций Excel производить с ними вычислительные манипуляции, возвращая затем итоговые результаты в MathCad документ для дальнейшей обработки.

Математический пакет MathCad имеет следующие достоинства.

1) Запись выражений выполняется в общеупотребительной математической форме.

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

3) Каждая страница документа может содержать текст, математические выражения, двумерные и трехмерные графики, рисунки, созданные в других Windows-приложениях.

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

5) Пакет имеет удобные возможности импорта и экспорта данных.

Ещё одним эффективным, но трудоемким способом решения ТЗ является нахождение потока минимальной стоимости. Такой метод требует знаний в области теории графов. Графы находят широкое применение при построении математических моделей для решения различных прикладных задач. Задача о потоке минимальной стоимости состоит в нахождении самого простого способа передачи определенного количества потока через транспортную сеть [5]. Её решение аналогично нахождению максимального потока в алгоритме Форда-Фалкерсона. Только вместо кратчайшего дополняющего потока ищется самый дешёвый. Соответственно, в такой задаче используется не поиск в ширину, а алгоритм Беллмана-Форда. При возврате потока стоимость считается отрицательной. Такой алгоритм можно запускать сразу, без нахождения опорного плана. Но в этом случае процесс решения будет несколько более долгим. Преимущество графов заключается в том, они однозначно описывают структуру системы, на их основе просто записываются канонические уравнения, фиксируются физические свойства и причинная зависимость между переменными. Их особенностью является геометрический подход к изучению объектов. Для решения ТЗ большой размерности использовать такой метод не оптимально, так как построение транспортной сети в графоанализаторе отнимает много времени.

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

Для решения ТЗ при помощи программных комплексов не нужно знать математический метод их решения, но нужно уметь правильно поставить задачу. Применение математических пакетов в планировании перевозок дает большой экономический эффект [7]. У каждого способа решения транспортной задачи есть свои достоинства и недостатки. Поэтому для нахождения наиболее эффективного из них, в зависимости от заданных ситуаций, были рассмотрены и проанализированы решения транспортных задач, полученные с помощью табличного процессора MSExcel, программного комплекса MathCad и системы компьютерной алгебры Maple.

На основании проведенного анализа были сделаны следующие выводы:

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

2) Среди рассмотренных математических пакетов наиболее эффективными были выбраны системы компьютерный алгебы Maple и MathCad, расширенный функционал которых позволяет быстро получить оптимальный план транспортной задачи.

Библиографический список

1. Онлайн - библиотека // Данциг Д. Линейное программирование, его применения и обобщения. - М.: Прогресс, 1966. - 600 с. [Электронный ресурс]. - Режим доcтупа: http://еdu-lib.nеt/mаtеmаtikа

2. Абрамов, Д. Ц. Математическое программирование. / Д. Ц. Абрамов, В. Ф. Капустин. - Л.: Изд. ЛГУ. 1981. - 328 с.

3. Карманов, В. Г. Математическое программирование. - М. : Наука, 1975. - 272 с.

4. Вагнер, Г. Основы исследований операций. - М.; Мир, 1972. - Т. 1. - 337 с.

5. Кузнецов, Ю. Н. Математическое программирование./ Ю.Н. Кузнецов, В. И. Кузубов, А. В. Волощенко. - М.: Высш. школа, 1980. - 302 с.

6. Лунгу, К. Н. Линейное программирование. Руководство к решению задач. - М. : ФИЗМАТЛИТ, 2005. - 128 с.

7. Онлайн - библиотека [электронный ресурс] // Костевич Л. С. Математическое программирование: Информ. технологии оптимальных решений: учеб. пособие / Л. С. Костевич. - Мн.:, 2003. - 424 с.- Режим доcтупа: http://еdu-lib.nеt/mаtеmаtikа

Размещено на Allbest.ru