Simplex

#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>  //para limitar casas decimais print do float

using namespace std;



//Tipos criados
typedef vector< vector<float> > Matrix;
typedef vector<float> Row;
typedef vector<float> Values;


//Variaveis
int numeroRestricoes = 0;
bool maximizacao = false;
int escolha = 0;

int numeroVariaveis = 0;
float coefVariavel = 0;
int colunaPivo = 0;
int linhaPivo = 0;
float coefPivoDeCadaLinha = 0;
float menorElementolinhaZ = 0;
float menorElementoColunaDivisaoLD = 0;
float elementoPivo = 0;
bool continuarExecucao = true;
int numeroIteracoes = 0;
bool houveErros = false;

vector<int> colunaVariaveis(0, 0); //variaveis atualmente na tabela
vector<int> linhaVariaveis(0, 0); // todas variaveis
Matrix matrix;
Matrix tabelaSimplex;
Values colunaValores;
Values linhaZ;


//Funcoes
void menu();
void preencherMatriz();
void imprimirMatriz();
void preencherValoresRestricao();  // preencher coluna apos o "="
void aplicarSimplex();
void preencheLinhaZ();
void imprimeLinhaZ();
void imprimeLinhaZcomVariaveis();
void procuraMenorValorLinhaZ();
void posicionarVariaveisDeFolga();
void imprimeMatrizSimplex();
void procuraLinhaPivo();
void trocaLinhaPivoPorColunaPivo();
void alterarLinhas();
void imprimeResultados();
bool verificarFinal();

/// Main code
int main() {
    menu();

    system("PAUSE");
    return 0;
}



void menu() {
    cout << "Defina qual o tipo do problema:" << endl << "1 - Maximizacao" << endl << "2 - Minimizacao" << endl;
    cin >> escolha;
    if (escolha == 1) { maximizacao = true; }
    else { maximizacao = false; }
    cout << "Numero de restricoes: " << endl;
    cin >> numeroRestricoes;
    cout << "Informe o numero de variaveis: " << endl;
    cin >> numeroVariaveis;

    cout << fixed;
    cout << setprecision(3); //limita print do float para 4 casas

    preencheLinhaZ();
    preencherMatriz();
    preencherValoresRestricao();
    imprimirMatriz();
    imprimeLinhaZcomVariaveis();
    aplicarSimplex();

}

void preencheLinhaZ() {
    int aux = 0;
    cout << "Infome a equacao Z:" << endl;
    for (size_t i = 0; i < numeroVariaveis; i++) {
        cout << "Coeficiente de X" << i << ":" << endl;
        cin >> aux;
        linhaZ.push_back(aux);
    }
}

void imprimeLinhaZcomVariaveis() {
    cout << endl << "-----------------------------------------------------------------" << endl;
    cout << "Z:";
    for (size_t i = 0; i < numeroVariaveis; i++) {
        cout << linhaZ[i] << "X" << i << " ";
    }
    cout << endl;
}

void imprimeLinhaZ() {
    cout << endl << "-----------------------------------------------------------------" << endl;
    for (size_t i = 0; i < numeroVariaveis + numeroRestricoes+1; i++) {
        cout << linhaZ[i] << "\t";
    }
    cout << endl;
}


void preencherMatriz() {
    for (size_t i = 0; i < numeroRestricoes; ++i)
    {
        cout << "Restricao " << i << ":" << endl;
        Row row(numeroVariaveis);
        for (size_t j = 0; j < numeroVariaveis; ++j)
        {
            cout << "Coeficiente da variavel x" << j << ": ";
            cin >> coefVariavel;
            row[j] = coefVariavel;
        }
        matrix.push_back(row); // coloca a linha na matriz apos ser preenchida
    }
}

void preencherValoresRestricao() {
    //Values colunaValores(numeroRestricoes);
    cout << "Informe os valores apos o '>=' ou '<=' " << endl;
    int aux = 0;
    for (size_t i = 0; i < numeroRestricoes; i++) {
        //para cada restricao, adicionar um valor apos o =
        cout << "Restricao " << i << ": ";
        cin >> aux;
        colunaValores.push_back(aux);
    }
}

void imprimirMatriz() {
    cout << endl << "-----------------------------------------------------------------" << endl;
    cout << "Matriz de restricoes: " << endl;
    for (size_t i = 0; i < numeroRestricoes; ++i) {
        for (size_t j = 0; j < numeroVariaveis; ++j) {
            cout << matrix[i][j] << " ";
            if (numeroVariaveis == j+1) {
                if (maximizacao) { cout << ">= " << colunaValores[i] << endl; }
                else { cout << "<= " << colunaValores[i] << endl; }
            }
        }
    }
    cout << endl;
}

void procuraMenorValorLinhaZ() {
    for (size_t i = 0; i < numeroVariaveis + numeroRestricoes; i++) {
        if (i == 0) {
            colunaPivo = i;
            menorElementolinhaZ = linhaZ[0];
        } //sendo o primeiro a verificar, sera o menor
        else {
            if (linhaZ[i]<linhaZ[colunaPivo]) {
                colunaPivo = i;
                menorElementolinhaZ = linhaZ[colunaPivo];
            }
        }
    }
}

void posicionarVariaveisDeFolga() {
    int contadorvariaveis = numeroVariaveis;
    for (size_t i = 0; i < numeroRestricoes; i++) {
        contadorvariaveis++; //posicao onde sera colocada a variavel de folga
        for (size_t j = numeroVariaveis + 1; j <= numeroVariaveis + numeroRestricoes; j++) {
            if (j == contadorvariaveis) { tabelaSimplex[i].push_back(1); }
            else { tabelaSimplex[i].push_back(0); }
        }
        tabelaSimplex[i].push_back(colunaValores[i]);
    }
}

void imprimeMatrizSimplex() {
    cout << endl << "-----------------------------------------------------------------" << endl;
    cout << "Matriz do Simplex: " << endl;
    imprimeLinhaZ();
    for (size_t i = 0; i < numeroRestricoes; ++i) {
        for (size_t j = 0; j<(numeroVariaveis + numeroRestricoes + 1); j++) {
            cout << tabelaSimplex[i][j] << "\t";
        }
        cout << endl;
    }
}

void procuraLinhaPivo() {
    //cout << endl << "Tamaho de cada linha: " << tabelaSimplex[0].size(); //para acessar, usar tamanho-1 pois indice comeca em 0
    int indiceUltimoElemento = tabelaSimplex[0].size() - 1;
    float aux = 0;
    bool todosValoresNegativos = true;
    for (size_t i = 0; i < numeroRestricoes; i++) {
        if ((tabelaSimplex[i][colunaPivo]) > 0) {
            todosValoresNegativos = false; //entrou uma vez, ha um valor positivo na coluna pivo
            if (i == 0) {
                menorElementoColunaDivisaoLD = (tabelaSimplex[0][indiceUltimoElemento]) / (tabelaSimplex[0][colunaPivo]);
                linhaPivo = 0;
            }
            else {
                aux = (tabelaSimplex[i][indiceUltimoElemento]) / (tabelaSimplex[i][colunaPivo]);
                if (aux < menorElementoColunaDivisaoLD) {
                    menorElementoColunaDivisaoLD = aux;
                    linhaPivo = i;
                }
            }
        }
    }
    if (todosValoresNegativos) { continuarExecucao = false; }
    elementoPivo = tabelaSimplex[linhaPivo][colunaPivo];
    cout << "Elemento pivo: " << elementoPivo << endl;

    if (elementoPivo == 0) {
        cout << "Erro! Elemento Pivo é zero!";
        continuarExecucao = false;
    };
}

void trocaLinhaPivoPorColunaPivo() {
    //dividir a linhaPivo pelo elemento pivo
    int tamanhoLinha = tabelaSimplex[0].size();
    for (size_t i = 0; i < tamanhoLinha; i++) {
        if(elementoPivo != 0){ tabelaSimplex[linhaPivo][i] = (tabelaSimplex[linhaPivo][i]) / elementoPivo; }
        else { tabelaSimplex[linhaPivo][i] = 0; }
    }

    colunaVariaveis[linhaPivo] = linhaVariaveis[colunaPivo];
}

void alterarLinhas() {
    int tamanhoLinha = tabelaSimplex[0].size();
    for (size_t i = 0; i < numeroRestricoes; i++) {
        if (i != linhaPivo) {
            coefPivoDeCadaLinha = tabelaSimplex[i][colunaPivo]; //salva coef pra cada linha, para nao ser alterado durante calculos
            for (size_t j = 0; j < tamanhoLinha; j++) {
                 tabelaSimplex[i][j] = (tabelaSimplex[i][j]) - ((coefPivoDeCadaLinha) * tabelaSimplex[linhaPivo][j]);
            }
        }
    }
    coefPivoDeCadaLinha = linhaZ[colunaPivo];
    for (size_t i = 0; i < tamanhoLinha;i++) {
        linhaZ[i] = linhaZ[i] - (coefPivoDeCadaLinha * tabelaSimplex[linhaPivo][i]);
    }
}

bool verificarFinal() {
    int tamanhoLinha = linhaZ.size();
    for (size_t i = 0; i < tamanhoLinha; i++) {
        if (linhaZ[i] < 0) {
            return true;
        }
    }
    return false;
}

void imprimeResultados() {
    int indiceUltimoElemento = tabelaSimplex[0].size() - 1;
    cout << endl << "Variaveis atualmente na tabela: " << endl;
    cout << fixed;
    cout << setprecision(0); //limita print do float para 4 casas
    cout << "Z = " << linhaZ[indiceUltimoElemento] << endl;
    cout << fixed;
    cout << setprecision(3); //limita print do float para 4 casas
    for (size_t i = 0; i < numeroRestricoes; i++) {
        cout << "X" << colunaVariaveis[i] << "=" << tabelaSimplex[i][indiceUltimoElemento] << endl;
    }
}

void aplicarSimplex() {
    //posicionar os 0 da variaveis de folga em Z e do LD
    for (size_t i = 0; i < numeroRestricoes+1; i++) {
        linhaZ.push_back(0);
    }
    cout << "Aplicando variaveis de folga e movendo todos coeficientes para mesmo lado da equacao:" << endl << "Z ";
    for (size_t i = 0; i < numeroVariaveis+numeroRestricoes; i++) {
        linhaZ[i] = linhaZ[i] * (-1);
        cout << linhaZ[i] << "X" << i << " ";
    }

    //Coluna das variaveis presentes na tabela, no comeco, é somente as variaveis de folga
    for (size_t i = numeroVariaveis; i < numeroVariaveis + numeroRestricoes; i++) {
        colunaVariaveis.push_back(i); //coloca os indices de qual variavel esta na coluna. ex: 3 variaveis (0 a 2), vai adicionar as variaveis a partir da 3, qeu sao as de folga
    }
    for (size_t i = 0; i < numeroVariaveis + numeroRestricoes;i++) {
        linhaVariaveis.push_back(i); //indices de todas variaveis
    }

    //Monta tabela do simplex
    tabelaSimplex = matrix;

    //Posicionar variaveis de folga
    posicionarVariaveisDeFolga();

    //Imprimir matriz do simplex e linha Z acima
    imprimeMatrizSimplex();

    //Loop de iteracoes

    while (continuarExecucao) {
        cout << endl << "-----------------------------------------------------------------" << endl;
        cout << "Iteracao " << numeroIteracoes << ":" << endl;
        numeroIteracoes++;

        //procura menor valor de Z
        procuraMenorValorLinhaZ();
        cout << "Menor valor da linha Z: " << menorElementolinhaZ << " Com indices i: 0 e j: " << colunaPivo << endl;

        //Dividir cada valor do LD (lado direito) pelo valor da coluna pivo e achar o menor destas divisoes. Assim acha o elemento pivo
        procuraLinhaPivo();

        //Se o elemento pivo encontrado foi zero, a execucao deve parar
        if (!continuarExecucao) { break; }


        //Trocar linhaPivo por ColunaPivo
        trocaLinhaPivoPorColunaPivo();

        //Aplicar iteracao ao resto das linhas
        alterarLinhas();

        //Imprimir nova tabela
        imprimeMatrizSimplex();

        //Verifica se existe valor negativo em Z, se houver repete todos os passos, senao tem a resposta
        continuarExecucao = verificarFinal();
    }

    if (!houveErros) { imprimeResultados(); };
}