Автоматизация Решения Экстремальных Задач Линейного Программирования

Методы линейного программирования оказались весьма эффективными для решения задач из различных областей человеческой деятельности. Исключительно важное значение приобретает использование таких методов и средств при решении задач оптимального проектирования, в которых необходимо учитывать огромное количество ограничивающих факторов, что связано с большим объемом вычислений. В связи с этим студентам технических вузов, обучающихся по направлению «Информатика и вычислительная техника», необходимо как знание возможностей применения математических методов и ЭВМ, так и понимание тех проблем, которые возникают при их использовании.
Разработанный программный комплекс позволяет решать следующие задачи:
• порождение начального базисного допустимого решения;
• поиск оптимального плана и экстремума нецелочисленной задачи линейного программирования;
• поиск оптимального плана и экстремума полностью целочисленной задачи линейного программирования;
• поиск оптимального плана и экстремума частично целочисленной задачи линейного программирования;

Исходные коды на Delphi, как и саму программу, вы можете бесплатно скачать на странице http://plagiata.net.ru/?p=68.

В ряде практических задач на управляемые переменные кроме ограничений накладываются дополнительные условия, такие как требования целочисленности (например, количество выпускаемой продукции при наиболее эффективном использовании ограниченных ресурсов в экономических задачах оптимизации) или задание интервала возможных значений (оптимизация распределения массивов по уровням памяти ЭВМ). Причем довольно часто это касается не всех переменных, а только некоторых из них.
Условие целочисленности решения может быть обеспечено реализацией метода Гомори. В этом случае поиск решения задачи целочисленного программирования начинается с определения симплексным методом оптимального плана без учета целочисленности переменных. После того как этот план найден, просматривают его компоненты. Если среди компонент нет дробных чисел, то найденный план является оптимальным планом решения задачи целочисленного программирования. В противном случае к системе уравнений добавляется неравенство с преобразованными переменными, взятыми из последней симплекс-таблицы. Эти действия повторяются до тех пор, пока не будет найден оптимальный план задачи, либо установлена ее неразрешимость.
Решение частично целочисленных задач линейного программирования находится последовательным решением задач, каждая из которых получается из предыдущей с помощью введения дополнительного ограничения. Дополнительные ограничения принято называть правильным отсечением, которое можно интерпретировать как гиперплоскость, которая как бы «отсекает» от области допустимых решений нецелочисленное оптимальное решение.
При проектировании был использован принцип модульного программирования, что упрощает отладку программы и позволяет расширять ее функциональные возможности. Алгоритмическая часть программы имеет модульно-иерархическую структуру, в которой каждый модуль является самостоятельной частью программы и взаимодействует с другими модулями в порядке, установленном разработчиками. Методы решения задач линейной оптимизации, реализованные в программно-алгоритмическом комплексе, основаны на построении симплекс-теблиц, поэтому в структуре программы все алгоритмические модули связаны с модулем, организующим решение задачи линейного программирования симплекс-методом. Входными данными для этого модуля является целевая функция с указанием типа экстремума (максимум или минимум) и ограничения, накладываемые на управляемые переменные. Ограничения задаются в виде уравнений или неравенств. Далее управление передается второму модулю, где формируется начальное допустимое базисное решение. Второй, третий и четвертый модули на каждой итерации реализуемого метода вызывают модуль построения симплекс-таблиц, которому они передают текущий результат. Связь между модулями организована через внешние структуры данных. Так, например, для задания линейного критерия оптимальности, вектора управляемых переменных, вектора ограничений и матрицы ограничений используются одномерные и двумерные статические массивы, а симплекс-таблица в памяти ЭВМ представлена как двумерный динамический массив, способный изменять свою размерность, удаляя или добавляя строки и столбцы к симплекс-таблице.
Рассмотрим особенность функционирования программного комплекса. Для организации диалога с пользователем применяется стандартный графический интерфейс Windows, построенный на основе библиотеки визуальных компонентов VCL (Visual Component Library), поставляемой вместе с пакетом Delphi. При разработке программы использовалась MDI-технология (Multiple Document Interface – многодокументный пользовательский интерфейс), что позволяет пользователю работать сразу с несколькими задачами линейного программирования. В программе реализована активная форма диалога, позволяющая выбирать режимы: расчет, просмотр и редактирование информации, получение справки и т.д. Главное меню содержит следующие пункты: файл, правка, вид, вычисления, окно, справка. Все пункты главного меню вызывают подменю. В начале работы программы некоторые пункты запрещены и становятся разрешенными только по мере выбора других пунктов меню (например, меню «Правка», «Вычисления» и т. д.).
В программе предусмотрена возможность настройки параметров задачи: максимизация или минимизация; выбор опции, позволяющей просматривать промежуточные результаты итераций; ограничения количества итераций; установка размерности задачи т.п.