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

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

Формулировка транспортной задачи представляет собой схему перевозок (рис. 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с.