RESOLUÇÃO ANALÍTICA DO MODELO DE PROGRAMAÇÃO MATEMÁTICA

Prévia do material em texto

RESOLUÇÃO ANALÍTICA DO MODELO DE PROGRAMAÇÃO MATEMÁTICA
Na formulação dos modelos pode-se perceber que a maioria deles diz respeito a sistemas de equações, ou inequações lineares, a partir dos quais deve ser obtida a solução ótima (máximo ou mínimo) para o problema. Portanto, é de fundamental importância que tais sistemas de equações, ou inequações, possam ser resolvidos pelo modelador.
Modelos Algébricos e Gráficos
Algébrico por adição: Pelo menos uma das equações deve ser multiplicada por um escalar real, de tal forma que, após a soma das duas equações, apenas uma das variáveis seja efetivamente a incógnita do problema.
Algébrico por substituição: Isola-se uma das variáveis em uma das equações, substituindo se a relação obtida na outra equação.
Gráfico: Geralmente tem-se um sistema de equações ou inequações lineares, com duas incógnitas, que podem ser representadas geometricamente por duas retas. A intersecção entre estas fornece a solução do problema.
Método de Gauss-Jordam: Consiste da derivação de um sistema específico de equações lineares que tenha a mesma solução que o sistema original. Esse ”novo” sistema deverá ter o formato de uma matriz identidade, ou seja, coeficientes unitários na diagonal principal, o que poderá ser obtido por meio de combinações lineares das equações originais.
Método Simplex: Até então, os métodos apresentados são extremamente eficientes para a resolução de sistemas de equações lineares. Entretanto, como já pôde ser observado, normalmente as restrições de um problema são representadas por inequações. Ainda há a questão da função objetivo: como ela deve ser tratada, para que se chegue à solução ótima do problema?
Para responder a esse questionamento, o algoritmo Simplex, foi desenvolvido, tendo como base as premissas de Gauss-Jordan (Andrade, 2015; LACHTERMACHER, 2016; Medeiros da Silva et. al., 1998; GOLDBARG e LUNA, 2005).
Métodos Simplex
No desenvolvimento do Método Simplex, assim como a utilização de software especializado para programação linear a resolução gráfica fornece o comportamento do sistema e da solução ótima.
Para facilitar o entendimento do procedimento do método simplex apresenta-se o algoritmo: (Andrade, 2015; LACHTERMACHER, 2016; Medeiros da Silva et. al., 1998; GOLDBARG e LUNA, 2005).
Passo1: Acrescentar variáveis de folga e verificar o sinal das variáveis.
Passo 3: Identificar a solução inicial básica.
Passo 4: Teste de otimalidade.
Passo 5: Se a solução for ótima fim.
                Caso contrário  vá para o passo 6.
Passo 6: Encontrar uma solução viável.
Passo 7: Voltar ao teste de otimalidade.
Para melhor entendimento do passo 1 do algoritmo, vamos fazer uma breve explicação.
Passo1: Acrescentar variáveis de folga e verificar o sinal das variáveis.
Variáveis de folga
Introduzir o conceito de folga de recursos pode-se escrever a relação como:
Utilização do recurso + folga = Disponibilidade de recurso
Essa relação significa que: (Andrade, 2015; LACHTERMACHER, 2016; Medeiros da Silva et. al., 1998; GOLDBARG e LUNA, 2005).
A folga para cada recurso deve ser diferente e é representada por uma variável de modo a transformar as inequações em equações de recursos. Essas variáveis devem ser diferentes as variáveis utilizadas para representar as variáveis do problema matemática, e devem ser sempre positivas. (Andrade, 2015; LACHTERMACHER, 2016; Medeiros da Silva et. al., 1998; GOLDBARG e LUNA, 2005).
Cada restrição composta por uma inequação deve ter uma variável de folga diferente.
 
Sinal das variáveis
 
Observação: Qualquer número pode ser escrito como diferença de dois valores positivos. (Andrade, 2015; LACHTERMACHER, 2016; Medeiros da Silva et. al., 1998; GOLDBARG e LUNA, 2005).
Os demais passos serão explicados na resolução do exemplo.
Para melhor entendimento do algoritmo do método simplex vamos exemplificar resolvendo um modelo simples.
Exemplo: Seja o modelo dado a encontre a solução através do método simplex. (Andrade, 2015; LACHTERMACHER, 2016; Medeiros da Silva et. al., 1998; GOLDBARG e LUNA, 2005).
Resolução
O método simplex é formado por um grupo de critérios para escolha de soluções básicas que melhorem o desempenho do modelo, e também de um teste de otimalidade. Para isso, o problema deve apresentar uma solução básica inicial. As soluções básicas subsequentes são calculadas com a troca de variáveis básicas por não básicas, gerando novas soluções.
Os critérios para escolha de vetores e consequentemente das variáveis que entram e saem para a formação da nova base constituem o centro do simplex.
Suponhamos inicialmente que o modelo apresente uma solução básica inicial. Os modelos com restrições do tipo ≤ e com termos da direita não negativos têm uma solução básica formada pelas variáveis de folga.
Acrescentando as variáveis de folga nas restrições o problema fica:
Na fase I do método simplex deve-se expressar o modelo na forma de equações e adicione as variáveis artificiais necessárias às restrições para garantir uma solução básica inicial, estas variáveis não tem significado para o problema real. (as variáveis auxiliares/artificiais deverão ser adicionadas nas variáveis onde se subtrai a folga) (TAHA, 2008).
Deve-se encontrar uma função objetivo auxiliar que é encontra somando as restrições onde se houve a necessidade de adicionar variáveis artificiais (TAHA, 2008).
Em seguida, encontre uma solução básica com as equações resultantes que, independentemente de o problema de PL ser de Maximização ou Minimização, sempre minimizará a soma das variáveis artificiais(TAHA, 2008).
Se o valor mínimo da soma for positivo, o problema de PL não tem solução viável, o que encerra o processo (OBS.: uma variável artificial positiva significa que uma restrição original não foi satisfeita) (Andrade, 2015; LACHTERMACHER, 2016; Medeiros da Silva et. al., 1998; GOLDBARG e LUNA, 2005).
Caso contrário, passe para a FASE II (TAHA, 2008).
Fase II
 Na fase II deve-se use a solução viável da Fase I como uma solução básica viável inicial para o problema original, e resolver o problema de acordo com seu objetivo (maximizar ou minimizar) até encontra a solução ótima (Andrade, 2015; LACHTERMACHER, 2016; Medeiros da Silva et. al., 1998; GOLDBARG e LUNA, 2005, TAHA, 2008)
 Exemplo:
Dado o problema de PL (TAHA, 2008).
Referências
ANDRADE, E.L. Introdução á Pesquisa Operacional. 3 ed. RJ: LTC, 2015.
CAIXETA- FILHO. Pesquisa Operacional. SP: atlas. 2004.
GOLDBARG, M.C. e LUNA, H.P. Otimização Combinatória e Programação Linear: modelos e algoritmos, 2 ed. RJ: Elsevier, 2005.
LACHTERMACHER, G. Pesquisa Operacional na Tomada de Decisões. 2ed: RJ, Elsevier, 2016.
MEDEIROS DA SILVA, E; Medeiros da Silva, E; Gonçalves V; Murolo, A. C.. Pesquisa Operacional para os cursos de: Economia, Administração, Ciências Contábeis. 3. Ed. São Paulo: Atlas, 1998.
TAHA, H. A. Pesquisa Operacional. 8. ed. São Paulo: Pearson, 2008.