simplex1.sci

gistfile1.txt

function [z, x, I, it, tipo] = simplex1(A, b, c, I)
    // m - quantidade de restricoes
    // n - quantidade de variaveis de decisao
    it = 0;
    [m, n] = size(A);
    J = setdiff(1:n, I); // tudo o que não for base, é não-base
    
    continuar = 1;
    while continuar
        A_I = A(:, I);
        A_I_inv = inv(A_I);
        c_I = c(1, I);
        // Executar passo 1 - calcular X_I, Pi e Z_0
        [ x_I, pi, z_0 ] = passo_1_calcula_x_I_pi_z_0 ( A_I_inv, b, c_I )
        // Executar passo 2 - calcular c_chapeu_J
        [ c_chapeu_J ] = passo_2_calcula_c_chapeu_J ( pi, A, c, J )
        // Executar passo 3 - encontrar quem entra na base
        [ k, c_chapeu_K ] = passo_3_encontrar_variavel_que_entra_na_base ( c_chapeu_J )
        // Executar passo 4 - verificar se solucao otima foi alcançada
        [ solucao_otima, tipo ] = passo_4_verificar_solucao_otima ( c_chapeu_K )
        if solucao_otima == 1 then
            continuar = 0;
            break;
        end
        // Executar passo 5 - calcular y_k
        [ y_k ] = passo_5_calcular_y_k ( A_I_inv, A, k );
        // Executar passo 6 - verificar se a solucao é ilimitada
        [ solucao_ilimitada, tipo ] = passo_6_verificar_solucao_ilimitada ( y_k );
        if solucao_ilimitada == 1 then
            continuar = 0;
            break;
        end
        // Executar passo 7 - encontrar o indice r da variavel a sair da base
        [ r ] = passo_7_encontrar_variavel_que_sai_da_base ( x_I, y_k );
        // Executar passo 8 - atualizar I, J
        [ I, J ] = passo_8_atualizar_I_J (I, J, k, r);
        // Atualizar a contagem de iteracoes
        it = it + 1;
    end
    z = z_0;
    x = zeros(1,n);
    x(1,I) = x_I;
endfunction

function [ x_I, pi, z_0 ] = passo_1_calcula_x_I_pi_z_0 ( A_I_inv, b, c_I )
    x_I = A_I_inv * b;
    pi = c_I * A_I_inv;
    z_0 = pi * b;
endfunction

function [ c_chapeu_J ] = passo_2_calcula_c_chapeu_J ( pi, A, c, J )
    c_chapeu_J = pi * A(:, J) - c(1, J);
endfunction

function [ k_entra_na_base, c_chapeu_K ] = passo_3_encontrar_variavel_que_entra_na_base ( c_chapeu_J )
    // primeiro retorno da funcao max - o valor do elemento maximo do vetor c_chapeu_J
    // segundo retorno da funcao max - o indice do elemento maximo do vetor c_chapeu_J
    // que corresponde a variável que vai entrar na base
    [ c_chapeu_K, k_entra_na_base ] = max(c_chapeu_J)
endfunction

function [ solucao_otima, tipo_solucao_otima ] = passo_4_verificar_solucao_otima ( c_chapeu_K )
        if c_chapeu_K > 0 then
            solucao_otima = 0;
            tipo_solucao_otima = 0;
        elseif c_chapeu_K == 0 then
            solucao_otima = 1;
            tipo_solucao_otima = 2;
        else
            // nesse caso, c_chapeu_K só pode ser menor do que zero
            // assim, temos solucao otima finita e unica
            solucao_otima = 1;
            tipo_solucao_otima = 1;
        end
endfunction

function [ y_k ] = passo_5_calcular_y_k ( A_I_inv, A, k )
    y_k = A_I_inv * A(:,k);
endfunction

function [ solucao_ilimitada, tipo_solucao ] = passo_6_verificar_solucao_ilimitada ( y_k )
    if y_k <= 0 then
        solucao_ilimitada = 1;
        tipo_solucao = 3;
    else
        solucao_ilimitada = 0;
        tipo_solucao = 0;
    end
endfunction

function [ r ] = passo_7_encontrar_variavel_que_sai_da_base ( x_I, y_k )
    filtro = y_k > 0;
    [ descarte, r ] = min(x_I(filtro) ./ y_k(filtro));
endfunction

function [ I, J ] = passo_8_atualizar_I_J (I, J, k, r)
    para_sair = I(1, r);
    I(1, r) = J(1, k); // J(k) armazena o indice da variavel que tem que entrar na base
    J(1, k) = para_sair; // J(k) recebe agora o indice da variavel que saiu da base
endfunction