Содержание
Введение
1. Описание задачи
2. Описание метода решения
3. Проектирование интерфейса
4. Структура программного модуля
5. Тестирование
Заключение
Список использованной литературы и программных средств
Приложение 1. Интерфейс приложения
Приложение 2. Листинг класса SimplexSolve
Введение
Линейное программирование– математическая дисциплина, посвященная теории и методам решения экстремальныхзадач на множествах n-мерного векторного пространства, задаваемыхсистемами линейных уравнений и неравенств.
Линейноепрограммирование является частным случаем выпуклого программирования, которое всвою очередь является частным случаем математического программирования. Термин«программирование» нужно понимать в смысле «планирования». Он был предложен всередине 1940-х годов Джорджем Данцигом, одним из основателейлинейного программирования, ещё до того, как компьютеры были использованы длярешения линейных задач оптимизации.
Работапосвящена наиболее распространенному методу решения задачи линейногопрограммирования – симплекс-методу. Симплекс-метод является классическим инаиболее проработанным методом в линейном программировании.
1.Описание задачи
Задачалинейного программирования (ЛП) возникает из необходимости оптимальноиспользовать имеющиеся ресурсы. Это задачи, связанные с целеобразованием ианализом целей и функций; задачи разработки или совершенствования структур (производственныхструктур предприятий, организованных структур объединений); задачипроектирования (проектирование сложных робототехнических комплексов, гибкихпроизводственных систем).
Вкачестве конкретных примеров задач, которые относятся к области линейногопрограммирования, можно назвать задачу об использовании сырья, задачу обиспользовании мощностей, задачу на составление оптимальной производственнойпрограммы.
ЗадачаЛП заключается в отыскании вектора />, максимизирующего/минимизирующеголинейную целевую функцию
/>(1)
приследующих линейных ограничениях
/>(2)
/>(3)
Записьзадачи ЛП в виде (1)-(3) называется нормальной формой задачи.
Этуже задачу ЛП можно представить в векторно-матричной записи:
/>(4)
где /> -вектор коэффициентов целевой функции,
/> -вектор решения,
/> -вектор свободных членов,
/> -матрица коэффициентов.
Область/> называетсяобластью допустимых значений (ОДЗ) задач линейного программирования. Соотношения(2), (3) называются системами ограничений задачи ЛП. Так как />, то можноограничиться изучением задачи одного типа.
Решениемзадачи ЛП, или оптимальным планом, называется вектор, удовлетворяющий системеограничений задачи и оптимизирующий целевую функцию.
Другаяформа представления задачи ЛП – каноническая. Она имеет вид:
/>
Вканонической форме записи задач линейного программирования все переменные,входящие в систему ограничений, должны быть неотрицательными, а все ограничениядолжны быть представлены равенствами. Любую задачу линейного программированияможно свести к задаче линейного программирования в канонической форме. Дляэтого в общем случае нужно уметь сводить задачу максимизации к задачеминимизации; переходить от ограничений неравенств к ограничениям равенств изаменять переменные, которые не подчиняются условию неотрицательности.
2.Описание метода решения
Симплекс-методявляется наиболее распространенным вычислительным методом, который может бытьприменен для решения любых задач ЛП как вручную, так и с помощью ЭВМ.
Этотметод позволяет переходить от одного допустимого решения к другому, причем так,что значения целевой функции непрерывно возрастают. В результате оптимальноерешение находят за конечное число шагов. Алгоритм симплекс-метода позволяеттакже установить является ли задача ЛП разрешимой.
Рассмотримзадачу ЛП в канонической форме. Будем искать решение задачи (6), (7), (8).
/>(6)
/>(7)
/>(8)
0. Положим k = 1. Взяв переменные /> за свободные и положив их равныминулю, а />, переобозначив в /> , — забазисные, находим первую крайнюю точку:
/>.
1. Заполним начальную допустимую симплекс-таблицу
/> …
/>
/> …
/>
/>
/>
/> …
/> …
/>
/> …
/> 1 …
/> … … … … … … … …
/>
/> …
/> … 1
/>
где /> -вектор коэффициентов целевой функции,
/> -вектор свободных членов,
/> -матрица коэффициентов.
2. Если для k-той крайней точки все />, то эта точка оптимальная, переходна пункт 7.
Востальных случаях переход к пункту 3.
3. Находим ведущий столбец />. Правило выбора: выбираем столбец, в котором самыйминимальный коэффициент /> среди отрицательных:
/>
4. Находим ведущую строку /> по правилу:
/>
Если все элементы ведущего столбца />, то задача ЛП не является разрешимой, т.к. целеваяфункция не ограничена на множестве допустимых значений, переход на пункт 7.
Такимобразом, ведущий элемент />.
5. Выполняем один шаг метода Гаусса: выводимпеременную с индексом /> изчисла базисных, а переменную с индексом /> вводим в базис. Новые элементы ведущей строкинаходятся по формуле:
/>
Новыезначения элементов остальных строк матрицы:
/>,
Все элементыв ведущем столбце равны 0, тогда как сам ведущий элемент равен 1.
6. Получаем (k + 1) крайнюю точку />. Полагая k = k + 1, перестраиваем симплекс-таблицуи переходим к пункту 2.
7. Конец решения.
3. Проектированиеинтерфейса
Разработанное приложениеимеет простой однооконный интерфейс с набором всех необходимых инструментов дляработы с программой.
Вверху окна стандартнорасполагается строка меню (JMenu),содержащая подменю (JSubMenu) Файл,Режим работы, Справка. В подменю Файл доступны следующие пункты меню (JMenuItem): Открыть файл, Выход. В подменюРежим работы с помощью Группы радиокнопок (JRadioButton Group) осуществляется взаимоисключающий выбор одного издвух режимов работы: автоматический, режим обучения. Из подменю Справкадоступен вызов окна «О программе» (SimplexAboutBox).
Под строкой менюрасполагается панель инструментов, дублирующая функции, доступные из строкименю, но предоставляющая более удобное использование и быстрый доступ к нимпользователю. Она содержит кнопку (JButton) «Загрузить файл», а также список (JComboBox) для выбора режима работы.
Далее располагаютсяпанели (JPanel), предоставляющие информацию орешаемой задаче, а именно:
· Панель параметров. Отображает количество свободных ибазисных переменных и количество ограничений с помощью JLabel.
· Панель «Целевая функция» отображает вид целевойфункции с помощью группы надписей (JLabel) и текстовых полей (JTextField).
· Панель «Решение» отображает вектор решения на текущемшаге выполнения задачи (для автоматического режима – оптимальное решение).
В центральной части окнарасположена таблица (JTable),отображающая симплекс-таблицу на текущем шаге, и набор кнопок (JButton) для работы с таблицей:
В автоматическом режиме:
· Кнопка «решить». Осуществляет решение загруженной задачиили выдает сообщение о существующей ошибке (неверный входной файл, функция неограничена на множестве допустимых решений).
В режиме обучения:
· «выбрать ведущий столбец». Вычисляет ведущий столбец исравнивает результат с выбором пользователя. При несовпадении результатов выдаетсообщение об ошибке «Ведущий столбец выбран неверно». Также вычисляет изаполняет вспомогательный столбец «Отношение», необходимый для выбора ведущейстроки.
· «выбрать ведущую строку». Находит ведущую строку исравнивает результат с выбором пользователя. При несовпадении результатоввыдает сообщение об ошибке «Ведущая строка выбрана неверно».
· «перестроить симплексную таблицу». Осуществляет одиншаг метода Гаусса для замены базисной переменной.
Внизу окна расположенополе для вывода многострочного текста (JTextArea), в котором отображаетсявспомогательная информация о текущем состоянии выполнения программы, а также оправилах выбора ведущих столбца и строки.
/>
Рис. 1. Главное окноразработанного приложения.
Скриншоты интерфейса разработанногоприложения при разных вариантах работы программы представлены в Приложении 1.
4. Структура программногомодуля
В рамках поставленнойзадачи был разработан программный модуль, осуществляющий решение задачилинейного программирования на основе начального допустимого базисного решения.
Входными данными являетсятекстовый файл, содержащий начальное допустимое базисное решение (на входныеданные накладываются следующие ограничения: максимальное количество свободныхпеременных – 5, базисных – 8).
Выходными даннымиявляется полученный вектор решения, а также сообщения о состоянии выполненияпрограммы.
Разработанный программныймодуль предоставляет пользователю возможность выбора одного из двух режимовработы:
· автоматического,
· режима обучения.
В автоматическом режиме(Приложение 1, рис.2) решение задачи осуществляется в одно действие без участияпользователя. В режиме обучения (Приложение 1, рис.3) решение выполняетсяпошагово с привлечением участия пользователя на каждом шаге. Пользовательосуществляет выбор ведущего столбца, затем ведущей строки, после чего симплекстаблица перестраивается и итерация повторяется. Построение симплекс таблицведётся до тех пор, пока решение не станет оптимальным либо пока не будетполучено сообщение об ошибке.
В программе предусмотренаобработка следующих исключительных ситуаций:
· загружен некорректный входной файл (Приложение 1,рис.4);
· целевая функция не ограничена на множестве допустимыхрешений (Приложение 1, рис.5).
Также реализована системаподсказок, предоставляющая пользователю более лёгкую работу с программнымсредством.
В качестве средыразработки была выбрана NetBeans IDE, являющаяся средойразработки приложений на языке Java.
Структура созданногопрограммного модуля представляет собой совокупность следующих классов:
· SimplexApp – главный класс приложения, осуществляющий запуск приложения, создание иотображение главного окна приложения.
· SimplexView – класс главного окна приложения, инициализирует все компонентыинтерфейса, осуществляет их настройку, а также обработку событий, вызванныхпользователем.
· SimplexAboutBox – класс, инициализирующий окно «Опрограмме».
· SimplexSolve – класс, реализующий выполнениесимплекс-метода.
· ReadFile – класс для обработки входного файла.
· TableView – реализует вывод симплекс-таблицы.
· Help – реализует вывод подсказок о ходевыполнения решения и о работе программы.
Класс SimplexSolve содержит следующие методы:
static void initSolution(int varCount) — создаёт вектор решения необходимой размерности.
static float[][] Solve(float[][] matrix) — осуществляет решение задачи в автоматическом режиме. Получая на входначальную симплекс-таблицу, возвращает преобразованную симплекс-таблицу сполученным решением.
static boolean userChooseCol(float[][] matrix,JTable tableName) –выполняет выбор ведущего столбца и сравнивает полученный результат с выборомпользователя. Возвращает истину, если выбор был произведен верно, иначе ложь. Вслучае если результаты не совпали, выводит сообщение об ошибке.
static boolean userChooseRow(float[][] matrix,JTable tableName) – проводит проверку ограниченности целевой функции намножестве допустимых решений, выполняет выбор ведущей строки и сравниваетполученный результат с выбором пользователя. Возвращает истину, если выбор былосуществлён верно, иначе ложь. В случае если результаты не совпали, сообщаетпользователю об ошибке.
static void userBuildNewTable(float[][] matrix,JTable tableName) – перестраиваетсимплексную таблицу и обновляет вектор решения.
static boolean checkSolved(float matrix[][]) – проверяеттекущее решение на оптимальность. Возвращает истину, если решение оптимально,иначе ложь.
Класс ReadFile содержит следующие методы:
staticfloat[][] read(String filename) throws IOException – осуществляет чтение входного файла. При отсутствии ошибок, возвращаетначальную симплексную таблицу, иначе выдает сообщение об ошибке входных данных.
static String[] doVarCol(), static String[] doVarRow() – создаютвспомогательные строку и столбец обозначения переменных для отображения симплекс-таблицы.
static int getVarCount() – возвращает количество свободныхпеременных.
static int getBvarCount() – возвращает количество базисныхпеременных.
static int getCondCount() – возвращает количество ограничений.
Класс TableView содержит следующие методы:
static voidclearTable(JTable tableName) – очищает таблицу.
static voidsetNames (JTable tableName) – заполняет шапку таблицы.
static voidfillTable(JTable tableName, float[][] matrix) – заполняет симплекс таблицу.
static voidfillProportion(JTable tableName, float[] proportion, int tempCInd) – заполняет вспомогательный столбец отношения (в обучающем режиме).
Класс Help содержит метод
static String showHelp(int event) – осуществляет вывод подсказки в зависимости от произошедшего события.
Листинг класса SimplexSolve, содержащего алгоритмсимплекс-метода, приведёт в Приложении 2.
5. Тестирование
Тест № 1.
Вход: Загружаем корректныйфайл с начальным допустимым базисным решением data1.txt.Выбираем автоматический режим работы. Нажимаем кнопку «решить».
Выход: В панели «Решение»отображается вектор решения. В таблицу выводится симплекс-таблица на последнейитерации выполнения алгоритма. В поле подсказки отображается информация о том,что задача решена и полученное решение оптимально.
(Приложение 1, рис. 2)
Тест № 2.
Вход: Загружаемнекорректный файл с начальным допустимым базисным решением data2.txt.
Выход: Выводитсясообщение «Ошибка входных данных». В поле подсказки отображается дополнительнаяинформация об ограничениях на входные данные.
(Приложение 1, рис.4)
Тест № 3.
Вход1: Загружаемкорректный файл с начальным допустимым базисным решением data5.txt,целевая функция не ограничена на множестве допустимых решений… Выбираем режимобучения. Выделяем неверный ведущий столбец. Нажимаем кнопку «выбрать ведущийстолбец».
Выход1: Выводитсясообщение «ведущий столбец выбран неверно». В поле подсказки отображаетсяподсказка с правилом выбора ведущего столбца.
Вход2: Выделяем верныйведущий столбец. Нажимаем кнопку «выбрать ведущий столбец».
Выход2: В таблицевыводится дополнительный столбец отношения.
Вход3: Выделяем ведущуюстроку. Нажимаем кнопку «выбрать ведущую строку».
Выход3: Выводитсясообщение «функция не ограничена на множестве допустимых значений». Решениезадачи прекращается. В поле подсказки выводится информация о том, чтодальнейшее решение задачи невозможно, для решения новой задачи необходимозагрузить файл.
(Приложение 1, рис. 5)
Заключение
Поитогам данной работы был разработан программный модуль, реализующий решениезадач линейного программирования симплекс-методом на основе начальногодопустимого базисного решения.
Симплекс-методявляется наиболее известным и широко применяемым на практике для решения общейзадачи линейного программирования. Алгоритм метода прост в понимании и легок вреализации, при программировании алгоритма никаких сложностей принципиальногохарактера не возникло. Однако, несмотря на то, что симплекс-метод являетсядостаточно эффективным алгоритмом, показавшим хорошие результаты при решенииприкладных задач ЛП, он является алгоритмом с экспоненциальной сложностью. Причинаэтого состоит в комбинаторном характере симплекс-метода, последовательно перебирающеговершины многогранника допустимых решений при поиске оптимального решения. Такимобразом, данный метод эффективен на небольшом наборе входных данных, приувеличении же их сложность алгоритма будет возрастать скачкообразно.
Врамках поставленной задачи были выполнены все требования, реализованы всефункциональные составляющие. Интерфейс разработанного программного продуктаинтуитивно понятен и легок в использовании. Модульность приложенияпредоставляет возможности для его дальнейшей доработки расширения и встраиванияв вычислительные комплексы.
Списокиспользованной литературы и программных средств
1. Исенбаева Е.Н.МЕТОДИЧЕСКИЕ УКАЗАНИЯ к проведению практических занятий по курсу«Системный анализ» на тему «Симплекс-метод решения задачилинейного программирования»/ Е.Н. Исенбаева. – Ижевск: ИжГТУ, 1999. – 14с.
2. Электронныйресурс: Симплекс метод: программная реализация симплекс-метода на языке Java — www.mathelp.spb.ru/lp.htm
3. Электронныйресурс: Wikipedia – Линейное программирование – ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5
4. Электронныйресурс: Wikipedia – Задача линейного программирования ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5
5. Среда разработки NetBeans IDE 6.9.1
Приложение 1
Интерфейспрограммы
/>
Рис.2. Автоматический режимработы программы
/>
Рис. 3. Режим обучения
линейныйпрограммирование симплекс метод
/>
Рис. 4. Обработка события«Ошибка входных данных»
/>
Рис. 5. Обработка события«Целевая функция не ограничена на множестве допустимых решений».
Приложение 2
Листинг классаSimplexSolve
packagesimplex;
importjavax.swing.JOptionPane;
importjavax.swing.JTable;
public classSimplexSolve {
static booleansolved = false;
static booleanlim = false;
static inttempCInd = 0;
static intminRInd = 0;
static intminCInd = 1;
static float[] solution;
//решение задачи вавтоматическом режиме
static float[][] Solve(float[][]matrix){
M1: {
solved = true;
// проверяем решение наоптимальность
for (int i = 0; i
if(matrix[i][0]
solved =false;
}
/ /пока решение неоптимально
while (!solved){
// находим ведущийстолбец
float minR = matrix[0][0];
int minRInd = 0;
for (int i =0; i
if(matrix[i][0]
minR =matrix[i][0];
minRInd = i;
}
}
//проверяем, ограниченали целевая функция на множестве доп. решений
lim = false;
for (int i =0; i
if(matrix[minRInd][i] > 0)
lim = true;
}
//если функция неограничена, выводим сообщение об ошибке, прерываем
//решение
if (!lim){
solved =true;
JOptionPane.showMessageDialog(null, «функция не ограничена на множестве допустимыхрешений»);
break M1;
}
//находим ведущую строку
float minC = matrix[ReadFile.colCount][1]/matrix[minRInd][1];
int minCInd = 1;
for (int i =1; i
if(matrix[ReadFile.colCount][i]/matrix[minRInd][i]
minC =matrix[ReadFile.colCount][i]/matrix[minRInd][i];
minCInd = i;
}
}
for (int i =tempCInd + 1; i
if(matrix[ReadFile.colCount][i]/matrix[minRInd][i]
minC =matrix[ReadFile.colCount][i]/matrix[minRInd][i];
minCInd = i;
}
}
//выводим из базисабазисную переменную [0][minCInd],вводим в базис
//переменную [minRInd][0]
ReadFile.varCol[minCInd-1] =ReadFile.varRow[minRInd] ;
//строим новую симплексную таблицу
//делим ведущую строкуна ведущий элемент [minRInd][minCInd]
float temp =matrix[minRInd][minCInd];
System.out.print(">>" + temp + "\n");
System.out.print("\nведущаястрока: ");
for (int i =0; i
matrix[i][minCInd] /= temp;
}
//получаем нули введущем столбце
for (int j = 0; j
float minTemp= matrix[minRInd][j];
for (int i =0; i
matrix[i][j]+= matrix[i][minCInd] * -minTemp;
}
}
for (int j =minCInd+1; j
float minTemp= matrix[minRInd][j];
for (int i =0; i
matrix[i][j]+= matrix[i][minCInd] * -minTemp;
}
}
//обновляем векторрешения
for (int i =0; i
for (int j =0; j
int k = j +1;
String tempS= «x» + k;
if(tempS.equals(ReadFile.varCol[i]))
solution[j] =matrix[ReadFile.colCount][i+1];
}
}
tempCInd = minCInd;
//рекурсивно вызываемпроцедуру, пока решение не будет оптимальным
Solve(matrix);
}
}
return matrix;
}
//создаем вектор решения
static voidinitSolution(int varCount){
solution =new float[varCount];
for (int i =0; i
solution[i] = 0;
}
}
//выбор ведущего столбцав режиме обучения
static booleanuserChooseCol(float[][] matrix, JTable tableName){
boolean err = false;
M1: {
//находим ведущийстолбец
float minR = matrix[0][0];
minRInd = 0;
for (int i =0; i
if(matrix[i][0]
minR =matrix[i][0];
minRInd = i;
}
}
//проверяем выборпользователя
while (minRInd!= SimplexView.getSelectedCol() — 1){
JOptionPane.showMessageDialog(null, «ведущий столбец выбран
неверно»);
err = true;
break M1;
}
int temp =minRInd;
float[]proportion = new float[ReadFile.rowCount];
//вычисляем вспомогательный столбец отношения
for (int i =1; i
if ( i ==tempCInd ){
proportion[i-1]= java.lang.Float.NaN;
}
else{
proportion[i-1]= matrix[ReadFile.colCount][i] /
matrix[temp][i];
}
}
TableView.fillProportion(tableName,proportion, tempCInd);
}
return err;
}
//выбор ведущей строки врежиме обучения
static booleanuserChooseRow(float[][] matrix, JTable tableName){
lim = false;
boolean err =false;
M1:{
//проверяем, ограниченали целевая функция на множестве доп. решений
for (int i = 0; i
if(matrix[minRInd][i] > 0)
lim = true;
}
if (!lim){
JOptionPane.showMessageDialog(null,«функция не ограничена на
множестве допустимых решений»);
break M1;
}
//находим ведущую строку
float minC = matrix[ReadFile.colCount][1]/matrix[minRInd][1];
minCInd = 1;
for (int i =1; i
if(matrix[ReadFile.colCount][i]/matrix[minRInd][i]
minC =matrix[ReadFile.colCount][i]/matrix[minRInd][i];
minCInd = i;
}
}
for (int i =tempCInd + 1; i
if(matrix[ReadFile.colCount][i]/matrix[minRInd][i]
minC =matrix[ReadFile.colCount][i]/matrix[minRInd][i];
minCInd = i;
}
}
//проверяемвыбор пользователя
System.out.print(«user:» + SimplexView.getSelectedRow() + "; min: "
+minCInd);
while(minCInd != SimplexView.getSelectedRow()){
err = true;
JOptionPane.showMessageDialog(null,«ведущая строка выбрана
неверно»);
break M1;
}
}
return err;
}
//перестраивает симплексную таблицу
static voiduserBuildNewTable(float[][] matrix, JTable tableName){
//выводим из базиса базисную переменную[0][minCInd], вводим в базис
//переменную [minRInd][0]
ReadFile.varCol[minCInd-1]= ReadFile.varRow[minRInd] ;
//строим новую симплексную таблицу
//делим ведущую строкуна ведущий элемент [minRInd][minCInd]
float temp = matrix[minRInd][minCInd];
for (int i =0; i
matrix[i][minCInd] /= temp;
}
//получаем нули введущем столбце
for (int j = 0; j
float minTemp= matrix[minRInd][j];
for (int i =0; i
matrix[i][j]+= matrix[i][minCInd] * -minTemp;
}
}
for (int j =minCInd+1; j
float minTemp= matrix[minRInd][j];
for (int i =0; i
matrix[i][j]+= matrix[i][minCInd] * -minTemp;
}
}
for (int i =0; i
for (int j =0; j
int k = j +1;
String tempS= «x» + k;
if(tempS.equals(ReadFile.varCol[i]))
solution[j] =matrix[ReadFile.colCount][i+1];
}
}
tempCInd = minCInd;
}
//проверяет, оптимальноли текущее решение
static booleancheckSolved(float matrix[][]){
solved =true;
for (int i =0; i
if(matrix[i][0]
solved =false;
}
if (solved){
JOptionPane.showMessageDialog(null," задача решена ");
tempCInd = 0;
}
returnsolved;
}
}