Реализация алгоритма симплекс-метода с произвольными свободными членами

}

} 

Функция 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"  

class simplex : public user_data {

public:

void init();

void gen_plane();

bool plane_is_valid();

bool function_is_undefined();

void print_result_to_file(int it_num);

private:

double func;

double **bv;

double **sv;

double *istr;

double *th;

double alm;

int i_lrow;

int i_lcol;

std::stringstream table;

};  

#endif /* _SIMPLEX_H_ */ 

Сначала рассмотрим закрытые переменная-члены данного  класса. 

double func — содержит значение целевой фукнции. При каждой итерации оно меняется.

double **bv — Содержит  значения базисных переменных  задачи. Данный член является  указателем на массив указателей, который в последующем инициализируется двумерным массивом num_v x 2, в первом стобце которого содержатся непосредственно. Сами значения базисных переменных задачи, а во втором номера этих переменных, которые изменяются при каждой последующей итерации. Номера базисных переменных необходимы для того, чтобы правильно вывести пользователю ответ и построить таблицу на выходе.

double **sv — Матрица  коэффициентов при переменных  задачи размером num_l x num_v * 2. Первые num_v столбцы данной матрицы заполняются коэффициентами исходной системы ограничений, а последующие num_v столбцы заполняются единичной матрицей, если решается задача на максимум, если же производится решение задачи на минимум, единицы меняют свой знак.  

double *istr — индексная  строка, является одномерным массивом размером num_v * 2, первая половина которого заполняется коэффициентами функции-цели с обратным знаком, а вторая нулями на первой итерации. На последующих итерациях значения индексной строки меняются. 

Int i_lcol = индекс  ведущего столбца текущего плана. 

double *th (греч. «тета») — последний столбец симплексной  таблицы, инициализируется одномерным  массивом размером num_l. 

Int i_lrow = индекс  ведущей строки текущего плана.  

double alm — разрешающий  элемент, находящийся на пересечении ведущего столбца и ведущей строки.  

std::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"  

using std::cout;

using std::endl;  

void simplex::init()

{

int i, j;

func = 0;

sv = new double *[num_l];

for (i = 0; i < num_l; i++)

sv[i] = new double [num_v * 2];

for (i = 0; i < num_l; i++) {

for (j = 0; j < num_v; j++)

sv[i][j] = system[i][j];

for (; j < num_v * 2; j++)

if (i + num_v == j)

if (way)

sv[i][j] = 1;

else

sv[i][j] = -1;

else

sv[i][j] = 0;

}

istr = new double [num_v * 2];

bv = new double *[num_l];

for (i = 0; i < num_l; i++) {

bv[i] = new double [2];

bv[i][0] = i + num_v;

bv[i][1] = fm[i];

}

for (i = 0; i < num_v * 2; i++)

if (i < num_v)

istr[i] = function[i] * -1;

else

istr[i] = 0;

i_lcol = 0;

for (i = 0; i < num_v * 2 - 1; i++) {

if (istr[i] < 0)

if (fabs(istr[i + 1]) > fabs(istr[i]))

i_lcol = i + 1;

}

th = new double [num_l];

for (i = 0; i < num_l; i++)

th[i] = bv[i][1] / sv[i][i_lcol];

i_lrow = 0;

for (i = 0; i < num_l - 1; i++)

if (th[i] > th[i + 1])

i_lrow = i + 1;

alm = sv[i_lrow][i_lcol];

print_result_to_file(0);

}

bool simplex::plane_is_valid()

{

int i;

bool result = true;

if (way)

for (i = 0; i < num_v * 2; i++)

if (istr[i] < 0) {

result = false;

break;

}

if (!way)

for (i = 0; i < num_v * 2; i++)

if (istr[i] >= 0) {

result = false;

break;

}  

return result;

}

bool simplex::function_is_undefined()

{

int i;

for (i = 0; i < num_l; i++)

if (th[i] < 0) {

return false;

}

return true;

}

void simplex::gen_plane()

{

int i, j, it_num = 0;

double A, B;

while (!plane_is_valid() && function_is_undefined()) {

A = bv[i_lrow][1];

B = istr[i_lcol];

func -= A * B / alm;

double *tmp_bv = new double [num_l];

bv [i_lrow][0] = i_lcol;

A = bv[i_lrow][1];

for (i = 0; i < num_l; i++) {

B = sv[i][i_lcol];

tmp_bv[i] = bv[i_lrow][1];

if (i != i_lrow)

tmp_bv[i] = bv[i][1] - A * B / alm;

else

tmp_bv[i] /= alm;

}

for (i = 0; i < num_l; i++)

bv[i][1] = tmp_bv[i];

double *tmp_istr = istr;

B = istr[i_lcol];

for (i = 0; i < num_v * 2; i++) {

A = sv[i_lrow][i];

tmp_istr[i] = istr[i] - A * B / alm;

}

istr = tmp_istr;

double **tmp_sv = new double *[num_l];

for (i = 0; i < num_l; i++)

tmp_sv[i] = new double [num_v * 2];

for (i = 0; i < num_l; i++)

for (j = 0; j < num_v * 2; j++) {

tmp_sv[i][j] = sv[i][j];

A = sv[i_lrow][j];

B = sv[i][i_lcol];

if (i == i_lrow)

tmp_sv[i][j] /= alm;

else

tmp_sv[i][j] = sv[i][j] - A * B / alm;

}

sv = tmp_sv;

i_lcol = 0;

for (i = 0; i < num_l; i++)

th[i] = bv[i][1] / sv[i][i_lcol];

i_lrow = 0;

for (i = 0; i < num_l -1; i++)

if (th[i] > th[i + 1])

i_lrow = i + 1;

alm = sv[i_lrow][i_lcol];

it_num++;

print_result_to_file(it_num);

}  

if (!function_is_undefined())

cout << "\nЦелевая  фукнция не ограничена, данная  задача решений не имеет\n" << endl;

else {

cout << "\nf(x) = " << func << "\n" << endl;

for (i = 0; i < num_l; i++) {

cout << "x" << bv[i][0] + 1 << " = " << bv[i][1] << endl;

}

cout << "\nВсе  вычисления были записаны в  файл table.txt\n" << endl;

}

}

void simplex::print_result_to_file(int it_num)

{

int i, j;

if (!it_num) {

table << "Задана  целевая функция:\n" << endl;

std::stringstream f_x;

f_x << "f(x) = ";

for (i = 0; i < num_v; i++) {

if (!i)

f_x << function[i] << "x" << i + 1 << " ";

else {

if (function[i] < 0)

f_x << "- " << fabs(function[i]) << "x" << i + 1 << " ";

if (function[i] > 0)

f_x << "+ " << function[i] << "x" << i + 1 << " ";

}

}

std::string minmax;

if (way)

minmax = "max";

else

minmax = "min";

f_x << "=> " << minmax << "\n" << endl;

table << f_x.str();

table << "И  система ограничений:\n" << endl;

std::stringstream math_sys;

std::string math_sign;

for (i = 0; i < num_l; i++) {

for (j = 0; j < num_v; j++) {

if (!j)

math_sys << system[i][j] << "x" << j + 1 << " ";

else

if (system[i][j] == 1)

if (!j)

math_sys << "x" << j + 1 << " ";

else

math_sys << "+ x" << j + 1 << " ";

else

if (system[i][j] == -1)