ФГОУ СПО Волгоградский технологический колледж
Специальность
230105 «Программное обеспечение вычислительной техники и автоматизированных
систем»
КУРСОВАЯ РАБОТА
По дисциплине «Математические методы»
Тема:
Реализация
алгоритма симплекс-метода с произвольными свободными членами
Выполнил: Левитин С.А.
Студент гр. ВТ-3-1
Проверил:
Теткин А.А.
Волгоград 2011
Содержание
Введение
1. Постановка задачи
2. Математическое обеспечение
. Разработка алгоритма программы
. Пример работы программы
Заключение
Список
используемой литературы
Введение
Основной целью данного проекта является закрепление теоретических знаний в области решения задач базовых линейного программирования симплекс - методом, получившем в литературе также название метода последовательного улучшения плана и реализация поставленной задачи на языке программирования С++.
Симплексный метод решения задач линейного программирования - вычислительная процедура, основанная на принципе последовательного улучшения решений - перехода от одной базисной точки к другой, для которой значение целевой функции больше (эти операции фиксируются в симплексной таблице). Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число шагов (за исключением так называемой «вырожденной задачи; при которой возможно явление «зацикливания», т. е. многократного возврата к одному и тому же положению).
Данный метод был разработан американским математиком Джорджем Данцигом (George Dantzig) в 1947 году.
1. Постановка задачи
Необходимо разработать программу, решающую
базовую задачу линейного программирования симплекс-методом с помощью
симплекс-таблиц. Свободные члены системы ограничений задачи могут быть
произвольными.
2. Математическое обеспечение
Примером задачи линейного программирования является целевая функция с определенным направлением экстремума и система ограничений для этой целевой функции. Например:
F(X) = 3x1 + 5x2 + 4x3 => max
,1x1 + 0,2x2 + 0,4x3 <= 1100
.05x1 + 0.02x2 - 0.02x3 <= 120
x1 + x2 + 2x3 <= 8000
Необходимо найти оптимальный план данной задачи
с помощью симплекс-метода с использованием симплекс-таблицы.
3. Разработка алгоритма программы
Перед началом работы необходимо было понять сам
алгоритм симплекс-метода. Для этого решалось несколько задач письменно. После
освоение алгоритма была продумана структора самого проекта. Первым делом был
написан класс user_data, который принимает пользовательские данные, т.е.
Саму задачу, которую необходимо решить с помощью симплекс-метода. Рассмотрим
содержимое заголовочного файла этого класса.
Листинг 1. user_data.h
#ifndef _USER_DATA_H_
#define _USER_DATA_H_
user_data {:get_data_from_user();user_data_is_valid();:*function;*fm;**system;*sign;num_v;num_l;way;
};
#endif /* _USER_DATA_H_ */
Рассмотрим все защищенные переменные-члены данного класса.
int num_v хранит в себе значение количества переменных исходной задачи.
Int num_l хранит в себе значение количества ограничений исходной задачи.
double *function хранит значения коэффициентов целевой функции задачи. Данный член является указателем типа double, для которого в последующем будет выделена память и произведется инициализация его как одномерного массива с размером num_v.
double *fm хранит в себе значения свободных членов системы ограничений. Также является указателем типа double, который будет инициализирован как одномерный массив с размером num_l.
double **system хранит в себе значения коэффициентов самой системы ограничений. Это член является указателем на массив указателей, который в последующем будет инициализирован как матрица, соответствующая по размеру системе ограничений поставленной задачи (num_l x num_v).
int *sign хранит в себе знак каждого ограничения системы. Является указателем типа int, который будет инициализирован как одномерный массив типа с размером num_l. Рационально использовать в данном случае целочисленный тип а не строковый. т.к. У нас есть три знака: <=, = и >=, которые храняться в *sign как 0, 1 и 2 соответственно.
bool way хранит в себе направление целевой функции задачи (min/max). При решении задачи на максимум эта переменная-член будет хранить в себе значение истины (true). А при решении на минимум, соответственно, ложь (false). Такой способ хранения данных очень рационален в данном случае, поскольку направлений у функции цели может быть только два. Поэтому тип bool идеально подходит для этого.
Функция void get_data_from_user(),
собственно запрашивает у пользователя данные, которые обрабатывает должным
образом и помещает в защищенные переменные-члены данного класса, приведенные
выше. В заголовочном файле хранится только прототип данной функции. Само
определение функции находится в файле user_data.cpp. Рассмотрим
содержимое этого файла.
Листинг 2. user_data.cpp
#include <iostream>
#include <string>
#include <cstdlib>
#include "user_data.h"std::cout;std::cin;std::endl;std::string;
error(int err_no)
{(err_no) {0:<< "\nВы ввели некорректное значение.\n" << endl;
break;1:<< "\nВы не можете задать менее двух ограничений.\n" << endl;;2:<< "\nВы не можете задать больше 500 ограничений.\n" << endl;;3:<< "\nВы не можете задать менее двух переменных.\n" << endl;;4:<< "\nВы не можете задать более 500 уравнений.\n" << endl;
break;
}
}
user_data::get_data_from_user()
{num_limits, num_vars, s_var, fr_m,
sn, func, w;i, j;validator = false;
do {<< "Введите количество ограничений в системе: ";
getline(cin, num_limits);(atoi(num_limits.c_str()) < 2)(1);if (atoi(num_limits.c_str()) > 500)(2);= true;
} while (!validator);
_l = atoi(num_limits.c_str());
validator = false;
{<< "Введите количество переменных в системе ограничений:";
getline(cin,
num_vars);(atoi(num_vars.c_str()) < 2)(3);if (atoi (num_vars.c_str()) >
500)(4);= true;
} while (!validator);
_v = atoi(num_vars.c_str());= false;= new double [num_v];= new double *[num_l];(i = 0; i < num_l; i++)[i] = new double [num_v];= new double [num_l];= new int [num_l];
for (i = 0; i < num_v; i++) {
do {<< "Введите коэффициент целевой фукнции при x" << i + 1 << ": ";
getline(cin, func);(atof(func.c_str()) == 0)(0);{= true;[i] = atof(func.c_str());
}
} while (!validator);= false;
}{
cout << "Введите направление целевой функции ( min, max ) : ";
getline(cin, w);(w == "max" || w == "MAX" || w == "min" || w == "MIN") {= true;(w == "max" || w == "MAX")= true;= false;
}(0);
} while (!validator);<< "\nЗаполните систему ограничений.\n" << endl;
(i = 0; i < num_l; i++) {
cout << "Заполните " << i + 1 << "-е ограничение.\n" << endl;
for (j = 0; j < num_v; j++) {
do {<< "Введите коэффициэнт при x" << j + 1 << ": ";
getline(cin, s_var);(atof(s_var.c_str()) == 0)(0);{= true;
}
} while (!validator);[i][j] = atof(s_var.c_str());
validator = false;
}
{<< "Введите знак при " << i + 1 << "-м ограничении ( <=, =, >= ) : ";
getline(cin, sn);(sn == "<=" || sn == "=" || sn == ">=") {= true;(sn == "<=")[i] = 0;(sn == "=")[i] = 1;(sn == ">=")[i] = 2;
}(0);<< sign[i] << endl;
} while (!validator);
= false;
{
cout << "Введите свободный член при " << i + 1 << "-м ограничении: ";
getline(cin, fr_m);(atof(fr_m.c_str()) == 0)(0);= true;
} while (!validator);
[i] = atof(fr_m.c_str());
validator = false;
<< endl;
}
}
Функция error(int err_no) принимает в качестве аргумента номер ошибки, которая должна вывестись пользователю в том случае, если он ввел некорректные данные. Далее номер ошибки, переданный в функцию обрабатывается оператором switch(), и в зависимости от принимаемого функцией аргумента, выводится ошибка с помощью оператора cout.]
Теперь рассмотрим функцию-член get_data_from_user() класса user_data. Все данные, который вводит пользователь, первоначально помещаются в объект типа string, а затем проверяется корректность данных, если все введено верно, то выполняется преобразование из std::string в int или double с помощью функций atoi() и atof() соответственно.
Сначала у пользователя запрашивается количество ограничений в системе. Если было введено целое число, от 2 до 500, то это значение преобразуется в int и заностится в переменную-член num_l. В противном случае вызывается функция error() с номером соответвующей ошибки и снова запрашивается ввод данных.
Далее, таким же образом пользователь вводит количество переменных задачи.
Затем выделяется память под массив function и матрицу system, а затем также идет ввод коэффициентов функции цели в цикле. После идет ввод значения направления функции. Если оно введено верно, то в переменная-член way заносится true или false, в зависимости от введенного значения. Регистр при вводе направления не учитывается при проверке. Если все верно, заполняется матрица system коэффициентами системы ограничений исходной задачи. Заполнение происходит в двух вложенных циклах, в первом из которых, также вводится знак ограничения и значение свободного члена при этом ограничении. Когда пользователь закончит ввод, все переменная-члены класса user_data будут заполнены, и тогда мы переходим к самому алгоритму, который реализован в классе simplex, являющимся прямым наследником класса user_data. Рассмотрим содержимое заголовочного файла этого класса.
Листинг 3. simplex.h
#ifndef _SIMPLEX_H_
#define _SIMPLEX_H_
#include <sstream>
#include "user_data.h"
simplex : public user_data {:init();gen_plane();plane_is_valid();function_is_undefined();print_result_to_file(int it_num);:func;**bv;**sv;*istr;*th;alm;i_lrow;i_lcol;::stringstream table;
};
#endif
/* _SIMPLEX_H_
*/
Сначала рассмотрим закрытые переменная-члены данного класса.
double func - содержит значение целевой фукнции. При каждой итерации оно меняется.**bv - Содержит значения базисных переменных задачи. Данный член является указателем на массив указателей, который в последующем инициализируется двумерным массивом num_v x 2, в первом стобце которого содержатся непосредственно. Сами значения базисных переменных задачи, а во втором номера этих переменных, которые изменяются при каждой последующей итерации. Номера базисных переменных необходимы для того, чтобы правильно вывести пользователю ответ и построить таблицу на выходе.**sv - Матрица коэффициентов при переменных задачи размером num_l x num_v * 2. Первые num_v столбцы данной матрицы заполняются коэффициентами исходной системы ограничений, а последующие num_v столбцы заполняются единичной матрицей, если решается задача на максимум, если же производится решение задачи на минимум, единицы меняют свой знак.*istr - индексная строка, является одномерным массивом размером num_v * 2, первая половина которого заполняется коэффициентами функции-цели с обратным знаком, а вторая нулями на первой итерации. На последующих итерациях значения индексной строки меняются.
линейный программирование симплекс таблица
Int i_lcol = индекс ведущего столбца текущего плана.
*th (греч. «тета») - последний столбец симплексной таблицы, инициализируется одномерным массивом размером num_l.
i_lrow = индекс ведущей строки текущего плана.
alm - разрешающий элемент, находящийся на пересечении ведущего столбца и ведущей строки.::stringstream table - объект класса std::stringstream, который содержит весь пользовательский вывод в выходной файл.
Собственно, сейчас были рассмотрены предназначения каждой переменная-члена класса simplex. Весь алгоритм вычисления вышеприведенных значений производится в файле simplex.cpp.
Листинг 4.
simplex.cpp
#include <iostream>
#include <cmath>
#include <fstream>
#include <sstream>
#include <string>
#include "user_data.h"
#include "simplex.h"
std::cout;std::endl;
simplex::init()
{i, j;= 0;= new double *[num_l];(i = 0; i < num_l; i++)[i] = new double [num_v * 2];(i = 0; i < num_l; i++) {(j = 0; j < num_v; j++)[i][j] = system[i][j];(; j < num_v * 2; j++)(i + num_v == j)(way)[i][j] = 1;[i][j] = -1;[i][j] = 0;
}= new double [num_v * 2];= new double *[num_l];(i = 0; i < num_l; i++) {[i] = new double [2];[i][0] = i + num_v;[i][1] = fm[i];
}(i = 0; i < num_v * 2; i++)(i < num_v)[i] = function[i] * -1;[i] = 0;_lcol = 0;(i = 0; i < num_v * 2 - 1; i++) {(istr[i] < 0)(fabs(istr[i + 1]) > fabs(istr[i]))_lcol = i + 1;
}= new double [num_l];(i = 0; i < num_l; i++)[i] = bv[i][1] / sv[i][i_lcol];_lrow = 0;(i = 0; i < num_l - 1; i++)(th[i] > th[i + 1])_lrow = i + 1;= sv[i_lrow][i_lcol];_result_to_file(0);
}simplex::plane_is_valid()
{i;result = true;(way)(i = 0; i < num_v * 2; i++)(istr[i] < 0) {= false;;
}
result;
}simplex::function_is_undefined()
{i;(i = 0; i < num_l; i++)(th[i] < 0) {false;
}true;
}simplex::gen_plane()
{i, j, it_num = 0;A, B;(!plane_is_valid() && function_is_undefined()) {= bv[i_lrow][1];= istr[i_lcol];-= A * B / alm;*tmp_bv = new double [num_l];[i_lrow][0] = i_lcol;= bv[i_lrow][1];(i = 0; i < num_l; i++) {= sv[i][i_lcol];_bv[i] = bv[i_lrow][1];(i != i_lrow)_bv[i] = bv[i][1] - A * B / alm;_bv[i] /= alm;
}(i = 0; i < num_l; i++)[i][1] = tmp_bv[i];*tmp_istr = istr;= istr[i_lcol];(i = 0; i < num_v * 2; i++) {= sv[i_lrow][i];_istr[i] = istr[i] - A * B / alm;
}= tmp_istr;**tmp_sv = new double *[num_l];(i = 0; i < num_l; i++)_sv[i] = new double [num_v * 2];(i = 0; i < num_l; i++)(j = 0; j < num_v * 2; j++) {_sv[i][j] = sv[i][j];= sv[i_lrow][j];= sv[i][i_lcol];(i == i_lrow)_sv[i][j] /= alm;_sv[i][j] = sv[i][j] - A * B / alm;
}= tmp_sv;_lcol = 0;(i = 0; i < num_l; i++)[i] = bv[i][1] / sv[i][i_lcol];_lrow = 0;(i = 0; i < num_l -1; i++)(th[i] > th[i + 1])_lrow = i + 1;= sv[i_lrow][i_lcol];_num++;_result_to_file(it_num);
}(!function_is_undefined())<< "\nЦелевая фукнция не ограничена, данная задача решений не
имеет\n" << endl;
else {<< "\nf(x) = " << func << "\n" << endl;(i = 0; i < num_l; i++) {<< "x" << bv[i][0] + 1 << " = " << bv[i][1] << endl;
}<< "\nВсе вычисления были записаны в файл table.txt\n" << endl;
}
}simplex::print_result_to_file(int it_num)
{i, j;(!it_num) {
table << "Задана целевая функция:\n" << endl;
std::stringstream f_x;_x << "f(x) = ";(i = 0; i < num_v; i++) {(!i)_x << function[i] << "x" << i + 1 << " ";{(function[i] < 0)_x << "- " << fabs(function[i]) << "x" << i + 1 << " ";(function[i] > 0)_x << "+ " << function[i] << "x" << i + 1 << " ";
}
}::string minmax;(way)= "max";= "min";_x << "=> " << minmax << "\n" << endl;
table << f_x.str();<< "И система ограничений:\n" << endl;
std::stringstream math_sys;::string math_sign;(i = 0; i < num_l; i++) {(j = 0; j < num_v; j++) {(!j)_sys << system[i][j] << "x" << j + 1 << " ";(system[i][j] == 1)(!j)_sys << "x" << j + 1 << " ";_sys << "+ x" << j + 1 << " ";(system[i][j] == -1)(!j)_sys << "-x" << j + 1 << " ";_sys << "- x" << j + 1 << " ";{(system[i][j] < 0)_sys << "- " << fabs(system[i][j])<< "x" << j + 1 << " ";_sys << "+ " << system[i][j] << "x" << i + 1 << " ";(!sign[i])_sign = "<=";(sign[i] == 1)_sign = "=";(sign[i] == 2)_sign = ">=";
}
}
_sys << math_sign << " " << fm[i];_sys << endl;
}::string min_or_max;(way)_or_max = "максимум";_or_max = "минимум";<< math_sys.str() << endl;
table << "Решим данную задачу на " << min_or_max << " методом
симплексных таблиц.\nПостроим первый опорный план:\n" << endl;
}(i = 0; i < num_l; i++) {
<< "x" << bv[i][0] + 1 << "\t" << bv[i][1] << "\t";(j = 0; j < num_v * 2; j++)<< sv[i][j] << "\t";(!plane_is_valid())<< th[i];<< "\n" << endl;
}<< "f(x)\t" << func << "\t";(i = 0; i < num_v * 2; i++)<< istr[i] << "\t";<< "\n";(plane_is_valid()) {(plane_is_valid() && function_is_undefined())
table << "\nДанный план является оптимальным и не требует
улучшения. Решение найдено." << endl;::ofstream outfile ("table.txt");<< table.str();
}{::string ln_or_gn;(way)_or_gn = "неположительные";_or_gn = "положительные";::stringstream num_of_plane;(!it_num)_of_plane << "Первый опорный план";_of_plane << it_num + 1 << "-й план также";
table << "\n" << num_of_plane.str() << " не является оптимальным,
поскольку\nв индексной строке присутствуют " << ln_or_gn << "
элементы.\nErо необходимо улучшить.\n" << endl;
}
}
Сначала выполняется инициализация первого опорного плана. Этим занимается функция-член init() класса simplex.
Значение функции-цели в первом опорном плане всегда равно нулю, поэтому в init() выполняется инициализация переменной-члена func класса simplex именно нулем.
Затем выделяется память под матрицу коэффициентов sv. И производится ее заполнение. Первая часть данной матрицы заполняется коэффициентами системы ограничений исходной задачи, вторая часть является единичной матрицей, в случае решения задачи на максимум, если же решается задача на минимум, единицы в данной матрице меняют свой знак.