Контрольная работа: Программная реализация симплекс-метода
static void setNames (JTable tableName) – заполняет шапку таблицы.
static void fillTable(JTable tableName, float[][] matrix) – заполняет симплекс таблицу.
static void fillProportion(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 - http://www.mathelp.spb.ru/lp.htm
3. Электронный ресурс: Wikipedia – Линейное программирование – http://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 – Задача линейного программирования http://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
Интерфейс программы
Рис. 2. Автоматический режим работы программы
Рис. 3. Режим обучения
линейный программирование симплекс метод
Рис. 4. Обработка события «Ошибка входных данных»
Рис. 5. Обработка события «Целевая функция не ограничена на множестве допустимых решений».
Листинг класса SimplexSolve
package simplex;
import javax.swing.JOptionPane;
import javax.swing.JTable;
public class SimplexSolve {
static boolean solved = false;
static boolean lim = false;
static int tempCInd = 0;
static int minRInd = 0;
static int minCInd = 1;
static float[] solution;
//решение задачи в автоматическом режиме
static float[][] Solve(float[][] matrix){
M1: {
solved = true;
// проверяем решение на оптимальность
for (int i = 0; i <= ReadFile.colCount; i++){
if (matrix[i][0] < 0)
solved = false;
}
/ /пока решение не оптимально
while (!solved){
// находим ведущий столбец
float minR = matrix[0][0];
int minRInd = 0;
for (int i = 0; i <= ReadFile.colCount; i++){
if (matrix[i][0] < minR){
minR = matrix[i][0];
minRInd = i;
}
}
//проверяем, ограничена ли целевая функция на множестве доп. решений
lim = false;
for (int i = 0; i <= ReadFile.rowCount; 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 < tempCInd; i++){
if (matrix[ReadFile.colCount][i]/matrix[minRInd][i] < minC){
minC = matrix[ReadFile.colCount][i]/matrix[minRInd][i];
minCInd = i;
}
}
for (int i = tempCInd + 1; i <= ReadFile.rowCount; i++){
if (matrix[ReadFile.colCount][i]/matrix[minRInd][i] < minC){
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 <= ReadFile.colCount; i++){
matrix[i][minCInd] /= temp;
}
//получаем нули в ведущем столбце
for (int j = 0; j < minCInd; j++){
float minTemp = matrix[minRInd][j];
for (int i = 0; i <= ReadFile.colCount; i++){
matrix[i][j] += matrix[i][minCInd] * -minTemp;
}
}
for (int j = minCInd+1; j <=ReadFile.rowCount; j++){
float minTemp = matrix[minRInd][j];
for (int i = 0; i <= ReadFile.colCount; i++){
matrix[i][j] += matrix[i][minCInd] * -minTemp;
}
}
//обновляем вектор решения
for (int i = 0; i < ReadFile.bvarCount; i++){
for (int j = 0 ; j < ReadFile.varCount; 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 void initSolution(int varCount){
solution = new float[varCount];
for (int i = 0; i < varCount; i++){
solution[i] = 0;
}
}
//выбор ведущего столбца в режиме обучения
static boolean userChooseCol(float[][] matrix, JTable tableName){
boolean err = false;
M1: {
//находим ведущий столбец
float minR = matrix[0][0];
minRInd = 0;
for (int i = 0; i <= ReadFile.colCount; i++){
if (matrix[i][0] < minR){
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 <= ReadFile.rowCount; 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 boolean userChooseRow(float[][] matrix, JTable tableName){
lim = false;
boolean err = false;
M1:{
//проверяем, ограничена ли целевая функция на множестве доп. решений
for (int i = 0; i <= ReadFile.rowCount; 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 < tempCInd; i++){
if (matrix[ReadFile.colCount][i]/matrix[minRInd][i] < minC){
minC = matrix[ReadFile.colCount][i]/matrix[minRInd][i];
minCInd = i;
}
}
for (int i = tempCInd + 1; i <= ReadFile.rowCount; i++){
if (matrix[ReadFile.colCount][i]/matrix[minRInd][i] < minC){
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 void userBuildNewTable(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 <= ReadFile.colCount; i++){
matrix[i][minCInd] /= temp;
}
//получаем нули в ведущем столбце
for (int j = 0; j < minCInd; j++){
float minTemp = matrix[minRInd][j];
for (int i = 0; i <= ReadFile.colCount; i++){
matrix[i][j] += matrix[i][minCInd] * -minTemp;
}
}
for (int j = minCInd+1; j <=ReadFile.rowCount; j++){
float minTemp = matrix[minRInd][j];
for (int i = 0; i <= ReadFile.colCount; i++){
matrix[i][j] += matrix[i][minCInd] * -minTemp;
}
}
for (int i = 0; i < ReadFile.bvarCount; i++){
for (int j = 0 ; j < ReadFile.varCount; 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 boolean checkSolved(float matrix[][]){
solved = true;
for (int i = 0; i <= ReadFile.colCount; i++){
if (matrix[i][0] < 0)
solved = false;
}
if (solved){
JOptionPane.showMessageDialog(null, " задача решена ");
tempCInd = 0;
}
return solved;
}
}
