Программная реализация симплекс-метода (стр. 2 из 3)
Вверху окна стандартно располагается строка меню (JMenu), содержащая подменю (JSubMenu) Файл, Режим работы, Справка. В подменю Файл доступны следующие пункты меню (JMenuItem): Открыть файл, Выход. В подменю Режим работы с помощью Группы радиокнопок (JRadioButtonGroup) осуществляется взаимоисключающий выбор одного из двух режимов работы: автоматический, режим обучения. Из подменю Справка доступен вызов окна «О программе» (SimplexAboutBox).
Под строкой меню располагается панель инструментов, дублирующая функции, доступные из строки меню, но предоставляющая более удобное использование и быстрый доступ к ним пользователю. Она содержит кнопку (JButton) «Загрузить файл», а также список (JComboBox) для выбора режима работы.
Далее располагаются панели (JPanel), предоставляющие информацию о решаемой задаче, а именно:
·Панель параметров. Отображает количество свободных и базисных переменных и количество ограничений с помощью JLabel.
·Панель «Целевая функция» отображает вид целевой функции с помощью группы надписей (JLabel) и текстовых полей (JTextField).
·Панель «Решение» отображает вектор решения на текущем шаге выполнения задачи (для автоматического режима – оптимальное решение).
В центральной части окна расположена таблица (JTable), отображающая симплекс-таблицу на текущем шаге, и набор кнопок (JButton) для работы с таблицей:
В автоматическом режиме:
·Кнопка «решить». Осуществляет решение загруженной задачи или выдает сообщение о существующей ошибке (неверный входной файл, функция не ограничена на множестве допустимых решений).
В режиме обучения:
·«выбрать ведущий столбец». Вычисляет ведущий столбец и сравнивает результат с выбором пользователя. При несовпадении результатов выдает сообщение об ошибке «Ведущий столбец выбран неверно». Также вычисляет и заполняет вспомогательный столбец «Отношение», необходимый для выбора ведущей строки.
·«выбрать ведущую строку». Находит ведущую строку и сравнивает результат с выбором пользователя. При несовпадении результатов выдает сообщение об ошибке «Ведущая строка выбрана неверно».
·«перестроить симплексную таблицу». Осуществляет один шаг метода Гаусса для замены базисной переменной.
Внизу окна расположено поле для вывода многострочного текста (JTextArea), в котором отображается вспомогательная информация о текущем состоянии выполнения программы, а также о правилах выбора ведущих столбца и строки.
Рис. 1. Главное окно разработанного приложения.
Скриншоты интерфейса разработанного приложения при разных вариантах работы программы представлены в Приложении 1.
4. Структура программного модуля
В рамках поставленной задачи был разработан программный модуль, осуществляющий решение задачи линейного программирования на основе начального допустимого базисного решения.
Входными данными является текстовый файл, содержащий начальное допустимое базисное решение (на входные данные накладываются следующие ограничения: максимальное количество свободных переменных – 5, базисных – 8).
Выходными данными является полученный вектор решения, а также сообщения о состоянии выполнения программы.
Разработанный программный модуль предоставляет пользователю возможность выбора одного из двух режимов работы:
·автоматического,
·режима обучения.
В автоматическом режиме (Приложение 1, рис.2) решение задачи осуществляется в одно действие без участия пользователя. В режиме обучения (Приложение 1, рис.3) решение выполняется пошагово с привлечением участия пользователя на каждом шаге. Пользователь осуществляет выбор ведущего столбца, затем ведущей строки, после чего симплекс таблица перестраивается и итерация повторяется. Построение симплекс таблиц ведётся до тех пор, пока решение не станет оптимальным либо пока не будет получено сообщение об ошибке.
В программе предусмотрена обработка следующих исключительных ситуаций:
·загружен некорректный входной файл (Приложение 1, рис.4);
·целевая функция не ограничена на множестве допустимых решений (Приложение 1, рис.5).
Также реализована система подсказок, предоставляющая пользователю более лёгкую работу с программным средством.
В качестве среды разработки была выбрана NetBeansIDE, являющаяся средой разработки приложений на языке Java.
Структура созданного программного модуля представляет собой совокупность следующих классов:
·SimplexApp – главный класс приложения, осуществляющий запуск приложения, создание и отображение главного окна приложения.
·SimplexView – класс главного окна приложения, инициализирует все компоненты интерфейса, осуществляет их настройку, а также обработку событий, вызванных пользователем.
·SimplexAboutBox– класс, инициализирующий окно «О программе».
·SimplexSolve – класс, реализующий выполнение симплекс-метода.
·ReadFile– класс для обработки входного файла.
·TableView – реализует вывод симплекс-таблицы.
·Help – реализует вывод подсказок о ходе выполнения решения и о работе программы.
Класс SimplexSolve содержит следующие методы:
staticvoidinitSolution(intvarCount) - создаёт вектор решения необходимой размерности.
staticfloat[][] Solve(float[][] matrix) - осуществляет решение задачи в автоматическом режиме. Получая на вход начальную симплекс-таблицу, возвращает преобразованную симплекс-таблицу с полученным решением.
staticbooleanuserChooseCol(float[][] matrix, JTabletableName)– выполняет выбор ведущего столбца и сравнивает полученный результат с выбором пользователя. Возвращает истину, если выбор был произведен верно, иначе ложь. В случае если результаты не совпали, выводит сообщение об ошибке.
staticbooleanuserChooseRow(float[][] matrix, JTabletableName) – проводит проверку ограниченности целевой функции на множестве допустимых решений, выполняет выбор ведущей строки и сравнивает полученный результат с выбором пользователя. Возвращает истину, если выбор был осуществлён верно, иначе ложь. В случае если результаты не совпали, сообщает пользователю об ошибке.
staticvoiduserBuildNewTable(float[][] matrix, JTabletableName)– перестраивает симплексную таблицу и обновляет вектор решения.
staticbooleancheckSolved(floatmatrix[][])– проверяет текущее решение на оптимальность. Возвращает истину, если решение оптимально, иначе ложь.
Класс ReadFile содержит следующие методы:
static float[][] read(String filename) throws IOException– осуществляетчтениевходногофайла. При отсутствии ошибок, возвращает начальную симплексную таблицу, иначе выдает сообщение об ошибке входных данных.
staticString[] doVarCol(), staticString[] doVarRow() – создают вспомогательные строку и столбец обозначения переменных для отображения симплекс-таблицы.
static int getVarCount() – возвращает количество свободных переменных.
static int getBvarCount() – возвращает количество базисных переменных.
static int getCondCount() – возвращает количество ограничений.
Класс TableViewсодержит следующие методы:
static void clearTable(JTable tableName) – очищаеттаблицу.
static void setNames (JTable tableName) – заполняетшапкутаблицы.
static void fillTable(JTable tableName, float[][] matrix) – заполняетсимплекстаблицу.
static void fillProportion(JTable tableName, float[] proportion, int tempCInd) – заполняетвспомогательныйстолбецотношения(вобучающемрежиме).
Класс Helpсодержит метод
staticStringshowHelp(intevent) – осуществляет вывод подсказки в зависимости от произошедшего события.
Листинг класса SimplexSolve, содержащего алгоритм симплекс-метода, приведёт в Приложении 2.
5. Тестирование
Тест № 1.
Вход: Загружаем корректный файл с начальным допустимым базисным решением data1.txt. Выбираем автоматический режим работы. Нажимаем кнопку «решить».
Выход: В панели «Решение» отображается вектор решения. В таблицу выводится симплекс-таблица на последней итерации выполнения алгоритма. В поле подсказки отображается информация о том, что задача решена и полученное решение оптимально.
(Приложение 1, рис. 2)
Тест № 2.
Вход: Загружаем некорректный файл с начальным допустимым базисным решением data2.txt.
Выход: Выводится сообщение «Ошибка входных данных». В поле подсказки отображается дополнительная информация об ограничениях на входные данные.
(Приложение 1, рис.4)
Тест № 3.
Вход1: Загружаем корректный файл с начальным допустимым базисным решениемdata5.txt, целевая функция не ограничена на множестве допустимых решений.. Выбираем режим обучения. Выделяем неверный ведущий столбец. Нажимаем кнопку «выбрать ведущий столбец».
Выход1: Выводится сообщение «ведущий столбец выбран неверно». В поле подсказки отображается подсказка с правилом выбора ведущего столбца.
Вход2: Выделяем верный ведущий столбец. Нажимаем кнопку «выбрать ведущий столбец».
Выход2: В таблице выводится дополнительный столбец отношения.
Вход3: Выделяем ведущую строку. Нажимаем кнопку «выбрать ведущую строку».
Выход3: Выводится сообщение «функция не ограничена на множестве допустимых значений». Решение задачи прекращается. В поле подсказки выводится информация о том, что дальнейшее решение задачи невозможно, для решения новой задачи необходимо загрузить файл.
(Приложение 1, рис. 5)
По итогам данной работы был разработан программный модуль, реализующий решение задач линейного программирования симплекс-методом на основе начального допустимого базисного решения.
Симплекс-метод является наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования. Алгоритм метода прост в понимании и легок в реализации, при программировании алгоритма никаких сложностей принципиального характера не возникло. Однако, несмотря на то, что симплекс-метод является достаточно эффективным алгоритмом, показавшим хорошие результаты при решении прикладных задач ЛП, он является алгоритмом с экспоненциальной сложностью. Причина этого состоит в комбинаторном характере симплекс-метода, последовательно перебирающего вершины многогранника допустимых решений при поиске оптимального решения. Таким образом, данный метод эффективен на небольшом наборе входных данных, при увеличении же их сложность алгоритма будет возрастать скачкообразно.