Наглядная программная реализация для решения транспортных задач методом потенциалов | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 14 марта, печатный экземпляр отправим 18 марта.

Опубликовать статью в журнале

Автор:

Рубрика: Информационные технологии

Опубликовано в Молодой учёный №5 (243) февраль 2019 г.

Дата публикации: 03.02.2019

Статья просмотрена: 713 раз

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

Бевз Р. Ю. Наглядная программная реализация для решения транспортных задач методом потенциалов // Молодой ученый. — 2019. — №5. — С. 10-14. — URL https://moluch.ru/archive/243/56191/ (дата обращения: 29.02.2020).



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

Главное назначение Т-задачи — определить объем перевозок из пунктов отправления в пункты назначения с минимальной суммарной стоимостью перевозок.

Формулировка транспортной задачи представляет собой схему перевозок (рис. 1) и несколько условий, необходимые и достаточные, чтобы найти оптимальное решение. В общем виде она представляет собой следующую схему:

Рис. 1. Графическое представление транспортной задачи

Каждому пункту отправления соответствует количество поставляемого этим пунктом товара — , аналогично с пунктами назначения — . Формулами (1) и (2) обозначены основные условия для разрешимости Т-задачи.

(1)

(2)

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

Постановка Т-задачи, применяемая в обозреваемой программе имеет следующий вид: имеется множество пунктов отправления (3)

(3)

Множество пунктов назначения (4)

(4)

И матрица тарифов на перевозки между поставщиками и потребителями , зависящая от предыдущих двух множеств, и содержащая затраты на перевозку :

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

Разработка программы проводилась в среде Microsoft Visual Studio 2017 на языке программирования C#. Программа является полностью автономной (состоит из одного файла расширения.exe) и предоставляет пользователю классический, интуитивно понятный оконный интерфейс. Самой значимой частью программы, несомненно, является решение транспортных задач различных размерностей, включающее в себя два основных блока. Первый — это нахождения начального опорного плана методом северо-западного угла или минимального элемента, где пользователь может наглядно увидеть первичную матрицу перевозок. И второй — последующая оптимизация опорного плана методом потенциалов и вывод значения целевой функции.

Давайте найдем оптимальный опорный план для заданной Т-задачи. Предполагается, что пользователь ознакомлен с необходимой теорией. Заполнение полей производится в соответствии с заданными выше условиями.

Рис. 2. Заполнение полей условия Т-задачи

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

Рис. 4. Решение методом минимального элемента

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

Рис. 5. Один из вопросов теста

Рис. 6. Условие задачи, которая представлена в тесте

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

Литература:

  1. Таха Х. А. Введение в исследование операций — 7-е издание.: Пер. с англ. — Москва: Издательский дом «Вильяме», 2005. — 912 с.
  2. Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа — М.: Наука, ФИЗМАТЛИТ, 1969. — 384 с.
  3. Зайченко Ю. П. Исследование операций — Киев: Вища школа. Головное изд-во, 1979 г.
  4. Кнут Д., Искусство программирования на ЭВМ. 1-й том Основные алгоритмы. Учебное пособие. 3-е изд. — М.: Издательский дом “Вильямс”. — 2000. — 712с.
Основные термины (генерируются автоматически): целевая функция, метод потенциалов, минимальный элемент, транспортная задача, северо-западный угол, пользователь, оптимальное решение, опорный план, начальный опорный план, линейное программирование.


Похожие статьи

Решение транспортных задач с применением... | Молодой ученый

Одной из задач линейного программирования является транспортная задачазадача о наиболее

2. Составить алгоритм для реализации методов решения транспортных задач в MathCAD.

Транспортная задача — математическая задача линейного программирования...

Методы оптимального планирования в системах военного...

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

2. Определим начальный опорный план , назначая перевозки способом «северо-западного угла» в

Транспортная задача — математическая задача линейного программирования об.

Интерактивный подход к решению транспортной задачи...

Транспортные задачи составляют класс задач линейного программирования

Решение задачи методом многих масштабов. Решение транспортных задач с помощью линейного

Транспортная задачазадача об оптимальном плане перевозок продукта из пункта...

Решение транспортных задач с использованием свойств...

Транспортная задача — математическая задача линейного программирования об оптимальном

Целевая функция L= в рассматриваемой задаче стремится к минимуму.

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

Разрешимость транспортной задачи по критерию времени

Составим начальное опорное решение Х1 методом северо-западного угла Максимум целевой функции

Транспортная задача — математическая задача линейного программирования об оптимальном плане перевозок грузов из пунктов отправления в...

Определение рациональных маршрутов доставки транспортных...

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

Декомпозиционный метод решения транспортной задачи...

целевая функция, оптимальное решение задачи, ограничение, задача, сумма значений, значение переменных, оптимальное решение задач, транспортная

Транспортная задачазадача об оптимальном плане перевозок продукта из пункта наличия в пункт потребления.

Формирование оптимальной производственной программы на...

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

Построение математических моделей в прикладных задачах

Транспортная задача — математическая задача линейного программирования об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления с минимальными затратами. Условие этой задачи таково. Решение транспортной задачи с...

Похожие статьи

Решение транспортных задач с применением... | Молодой ученый

Одной из задач линейного программирования является транспортная задачазадача о наиболее

2. Составить алгоритм для реализации методов решения транспортных задач в MathCAD.

Транспортная задача — математическая задача линейного программирования...

Методы оптимального планирования в системах военного...

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

2. Определим начальный опорный план , назначая перевозки способом «северо-западного угла» в

Транспортная задача — математическая задача линейного программирования об.

Интерактивный подход к решению транспортной задачи...

Транспортные задачи составляют класс задач линейного программирования

Решение задачи методом многих масштабов. Решение транспортных задач с помощью линейного

Транспортная задачазадача об оптимальном плане перевозок продукта из пункта...

Решение транспортных задач с использованием свойств...

Транспортная задача — математическая задача линейного программирования об оптимальном

Целевая функция L= в рассматриваемой задаче стремится к минимуму.

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

Разрешимость транспортной задачи по критерию времени

Составим начальное опорное решение Х1 методом северо-западного угла Максимум целевой функции

Транспортная задача — математическая задача линейного программирования об оптимальном плане перевозок грузов из пунктов отправления в...

Определение рациональных маршрутов доставки транспортных...

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

Декомпозиционный метод решения транспортной задачи...

целевая функция, оптимальное решение задачи, ограничение, задача, сумма значений, значение переменных, оптимальное решение задач, транспортная

Транспортная задачазадача об оптимальном плане перевозок продукта из пункта наличия в пункт потребления.

Формирование оптимальной производственной программы на...

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

Построение математических моделей в прикладных задачах

Транспортная задача — математическая задача линейного программирования об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления с минимальными затратами. Условие этой задачи таково. Решение транспортной задачи с...

Задать вопрос