#include "Simplex.h"
Simplex::Simplex(double *c, double **Matr, double *b, int row, int column)
:row(row), column(column),input_matrix_coef_X(Matr),target_function(c), free_variables(b)
{
upstring = new string[column];
leftstring = new string[row];
// выделение памяти под главную таблицу со всеми данными
memory_alloc_for_matrix(row, column);
upstring[0] = "S_i0";
for (int j = 1; j < column; j++)
{
upstring[j] = "x_" + to_string(j);
}
for (int i = 0; i < row - 1; i++)
{
leftstring[i] = "x_" + to_string(i + column);
}
leftstring[row - 1] = "F";
}
void Simplex::memory_alloc_for_matrix( int row, int column){
Table = new double*[row];
for(int i = 0; i < column;++i)
Table[i] = new double[column];
}
void Simplex::start_normal_simlex(){
int i = 0, j = 0;
for (i = 0; i < row - 1; i++)
{
Table[i][0] = free_variables[i];//свободные члены(самый левый столбец)
}
for (i = 0; i < row - 1; i++)//коэффц иксов
{
for (j = 1; j < column; j++)
{
Table[i][j] = input_matrix_coef_X[i][j - 1];
}
}
for (j = 1; j < column; j++)//заполнили строку ЦФ
{
Table[row - 1][j] = target_function[j - 1];
}
Table[row - 1][0] = 0;
this->start();
}
void Simplex::start_revert_simlex(){
int i = 0, j = 0;
for (i = 0; i < row - 1; i++)
{
Table[i][0] = (-target_function[i]);//свободные члены(самый левый столбец)
}
//приводим матрицу из первой лабы к критериям второй
transp_input_matr_A();
for (i = 0; i < row - 1; i++)//коэффц иксов
{
for (j = 1; j < column; j++)
{
Table[i][j] = -input_matrix_coef_X[i][j - 1];
}
}
for (j = 1; j < column; j++)//заполнили строку ЦФ//сделать жи = 0
{
Table[row - 1][j] = (-free_variables[j - 1]);
}
Table[row - 1][0] = 0;
this->start();
}
Simplex::~Simplex()
{
delete [] upstring;
delete [] leftstring;
for(int i = 0; i < column;++i){
delete [] Table[i] ;
}
delete [] Table ;
}
int Simplex::print()
{
int i = 0, j = 0;
cout << endl << '\t' << " ";
for (j = 0; j < column; j++)//печатаем название столбоцов
{
std::cout.setf(std::ios::right);
if(j == 1){
std::cout.width(7);
std::cout << upstring[j];
}
else{
std::cout.width(8);
std::cout << upstring[j];
}
}
cout.setf(ios::fixed);// fixed -- обыкновенная нотация(не научная, выводится без exp в степени)
cout.precision(3); // - число символов после точки
cout << endl;
for (i = 0; i < row; i++)
{
std::cout.width(6);
cout << leftstring[i] << ' ';
for (j = 0; j < column; j++)
{
std::cout.width(7);
cout << Table[i][j] << ' ';
}
cout << endl;
}
cout << endl;
return 0;
}
int Simplex::start()
{
cout << "На основе первоначальных данных составленная симплекс-таблица равна:" << endl;
print();
cout << "Ищем опорное решение:" << endl;
if (find_main_solution()<0)
cout << "Ничего не вышло \nв следующий раз обязательно получится, \nдо свидания";
cout << "Так как все элементы столбца S_i0 неотрицательны, имеем опорное решение. \nАнализируем строку F:" << endl;
if (find_optimal_solution() < 0)
cout << "Нет ничего, до свидания";
else
{
cout << "Оптимальное решение: ";
for (int j = 1; j < column; j++)
{
cout << upstring[j] << " = ";
}
cout << "0, ";
for (int i = 0; i < row - 1; i++)
{
cout << leftstring[i] << " = " << Table[i][0] << ", ";
}
cout << "\nЦелевая функция F = " << Table[row - 1][0] << endl;
}
return 0;
}
int Simplex::find_main_solution()
{
int i = 0, j = 0;
int r = 0, k = 0;
int count_for_while = 1;
while (count_for_while) {
for (i = 0; i < row - 1; i++) {
if (Table[i][j] < 0) {
r = i;
k = search_good_column_to_swap(r);
if (k < 0) {
cout << "Нет возможных решений :(" << endl;
return -1;
}
r = search_good_row_to_swap(k);
if (r < 0) {
cout << "Нет возможных решений :(" << endl;
return -1;
}
my_swap(r, k);
count_for_while = 2;
i = row;
}
}
if (count_for_while != 1) count_for_while = 1;
else count_for_while = 0;
}
return 0;
}
int Simplex::search_good_column_to_swap(int r)
{
int j = 0;
for (j = 1; j < column; j++)
{
if (Table[r][j] < 0)
{
std::cout << upstring[j] << " - разрешающий столбец" << std::endl;
return j;
}
}
return -1;
}
int Simplex::find_optimal_solution()
{
int i = row - 1, j = 0;
int r = 0, k = 0;
int count_for_while = 1;
while (count_for_while)
{
for (j = 1; j < column; j++)
{
if (Table[i][j] >= 0)
{
cout << upstring[j] << " - разрешающий столбец. Ищем разрешающую строку." << endl;
k = j;
r = search_good_row_to_swap(k);
if (r < 0)
{
cout << "Нет возможных решений :(" << endl;
return -1;
}
my_swap(r, k);
count_for_while = 2;
j = column;
}
}
if (count_for_while != 1) count_for_while = 1;
else count_for_while = 0;
}
return 0;
}
int Simplex::search_good_row_to_swap(int k)
{
int i = 0, j = 0;
int imin = 0;
int count_of_good_rows = 0;
for (i = 0; i < row - 1; i++)
{
if (Table[i][k] != 0 && Table[i][j] / Table[i][k] > 0)
{
if (count_of_good_rows == 0) imin = i;
count_of_good_rows++;
if (Table[i][j] / Table[i][k] < Table[imin][j] / Table[imin][k]) imin = i;
}
}
if (count_of_good_rows == 0) return -1;
std::cout << leftstring[imin] << " - разрешающая строка." << std::endl;
return imin;
}
int Simplex::my_swap(int r, int k)
{
cout << "Заменим базисы " << leftstring[r] << "<->" << upstring[k] << endl;
string temp;
temp = leftstring[r];
leftstring[r] = upstring[k];
upstring[k] = temp;
int i = 0, j = 0;
Table[r][k] = 1 / Table[r][k];
for (j = 0; j < column; j++)
{
if (j != k)
{
Table[r][j] = Table[r][j] * Table[r][k];
}
}
for (i = 0; i < row; i++)
{
if (i != r)
{
Table[i][k] = -1 * Table[i][k] * Table[r][k];
}
}
for (i = 0; i < row; i++)
{
for (j = 0; j < column; j++)
{
if (i != r && j != k)
{
Table[i][j] = Table[i][j] + Table[r][j] * Table[i][k] / Table[r][k];
}
}
}
cout << "Получаем симплекс-таблицу" << endl;
print();
return 0;
}
void Simplex::transp_input_matr_A()//коэффециенты при иксах
{
int new_row = row-1;
int new_column = column-1;
double temp[new_row][new_column];
for(int i=0;i<new_column;i++)
{
for(int j=0;j<new_row;j++)
{
temp[i][j]=input_matrix_coef_X[i][j];
}
}
for(int i=0;i<new_column;i++)
{
for(int j=0;j<new_row;j++)
{
input_matrix_coef_X[j][i]=temp[i][j];
}
}
}