Estudo1 - Simplex Padrão - JhonathandeAngelo

Prévia do material em texto

Universidade Federal de Santa Catarina Campus Araranguá 
 Disciplina: Pesquisa Operacional – DEC7542 
 
Professor: Vitor Antunes 
Aluno: Jhonathan F. Mataruco de Angelo - 13103225 
 
 
Estudo 1 – Simplex Padrão 
 
1.Introdução 
 
O Método Simplex é uma técnica utilizada para se determinar, numericamente, 
a solução ótima de um modelo de Programação Linear. Será desenvolvido 
inicialmente para Problemas de Programação Linear, na forma padrão, mas com 
as seguintes características para o sistema linear de equações: 
Todas as variáveis são não-negativas; Todos os bⅈ são não-negativos; Todas as 
equações iniciais do sistema são do tipo “≤ “. Assim, na forma padrão, só se 
encontra variáveis de folga. 
2.Descrição teórica e matemática do método 
Para ser iniciado, o método simplex necessita conhecer uma solução básica 
viável (solução inicial). Se a solução atual não é ótima, então o simplex muda do 
ponto extremo atual ao ponto extremo adjacente. Este processo continua até que 
a solução seja ótima. 
-Achar uma solução viável básica inicial. 
-Verificar se a solução atual é ótima. Se for, pare. 
-Determinar a variável não-básica que deve entrar na base. 
-Determinar a variável básica que deve sair da base. 
-Achar a nova solução viável básica, e voltar ao Passo 1 
Teorema: Se a função objetivo possui um máximo (mínimo) finito, então pelo 
menos uma solução ótima é um ponto extremo do conjunto das soluções 
(viáveis). 
 
Variáveis básicas e não básicas: Considerando-se o sistema Ax=b, definido 
em (introdução) e B ∈ ℜ mxm uma submatriz base de A, então, as variáveis 
associadas à submatriz B ∈ ℜ mxm são denominadas variáveis básicas. 
Notação: variáveis básicas: xB. Definida a submatriz base B restam em A (n - m) 
colunas que se chamara de submatriz não base N. As variáveis associadas a 
esta submatriz N são denominadas variáveis não básicas. Notação: variáveis 
não básicas: xN. 
Variáveis de folga: Nos problemas onde as restrições são do tipo “≤” (menor ou 
igual) é sempre possível obtermos uma submatriz (identidade) com o auxílio das 
variáveis de folga, e assim a solução inicial é óbvia. Porém, quando não temos 
uma solução inicial óbvia, ou seja, não conseguimos uma submatriz base 
(identidade) necessitamos de um procedimento para desenvolvê-la. Isto ocorre 
quando o problema de Programação Linear tiver restrições de “= “(igualdade) e 
ou restrições do tipo “≥” (maior ou igual). 
Tipo de Otimização. 
Como mencionado, o objetivo do método é otimizar o valor da função objetivo. 
No entanto, duas opções são apresentadas: obter o maior valor ótimo 
(maximizar) ou obter o menor valor ótimo (minimizar). 
Além disto, existem diferenças no algoritmo entre o objetivo de maximização e 
de minimização quanto ao critério de parada para finalizar as iterações e as 
condições de entrada e saída da base. Assim: 
• Objetivo de maximização 
Critério de parada: quando na linha Z não aparece nenhum valor negativo. 
Condição de entrada na base: o menor valor negativo na linha Z (ou o de maior 
valor absoluto entre os negativos) indica a variável Pj que entra na base. 
Condição de saída da base: depois de obter a variável de entrada, determina-se 
a variável de saída por meio do menor quociente P0/Pj dos valores estritamente 
positivos. 
• Objetivo de minimização 
Critério de parada: quando na linha Z não aparece nenhum valor positivo. 
Condição de entrada na base: o maior valor positivo na linha Z indica a variável 
Pj que entra na base. 
Condição de saída da base: depois de obter a variável de entrada, determina-se 
a variável de saída por meio do menor quociente P0/Pj dos valores estritamente 
negativos. 
No entanto, é possível normalizar o objetivo do problema, a fim de aplicar sempre 
os mesmos critérios sobre o critério de parada do algoritmo e as condições de 
entrada e saída nas variáveis da base. Assim, se o objetivo é minimizar a solução 
pode-se mudar o problema para outro equivalente de maximização, apenas 
multiplicando a função objetivo por "-1". Ou seja, o problema de minimizar Z é 
equivalente ao problema de maximizar (-1) ·Z. Uma vez obtida a solução, será 
preciso multiplicar por (-1). 
3.Vantagens e desvantagens do método 
Vantagens: Não será preciso se preocupar com novos critérios de parada, 
condição de entrada e de saída da base, já que são mantidos. 
Desvantagens: No caso em que a função tenha todos os coeficientes de suas 
variáveis básicas positivas e, adicionalmente, as restrições sejam do tipo de 
desigualdade "≤", ao fazer a mudança, tais coeficientes ficam negativos 
cumprindo assim a condição de parada na primeira iteração (na linha de valor da 
função objetivo todos os valores são positivos ou zero). Neste caso, obtém-se 
por padrão um valor ótimo para a função igual a 0. 
Solução: Não existe este problema, dado que para que a solução seja superior 
a 0 é necessário que alguma restrição tenha imposto a condição "≥" (que seria 
um modelo para o método das Duas Fases). No caso mencionado, a solução 
real deve ser zero. 
4.Formato padrão de PLs 
Outra condição do modelo padrão do problema é que todas as restrições sejam 
equações de igualdade (também chamada de restrições de igualdade), por isso 
é necessário converter as restrições de desigualdade ou inequações em tais 
identidades matemáticas. 
A condição de não negatividade das variáveis (x1,..., xn ≥ 0) é a única exceção 
e se mantém inalterada. 
• Restrição do tipo "≤" 
Para normalizar uma restrição com uma desigualdade do tipo "≤", adiciona-se 
uma nova variável, chamada variável de folga xs (com condição de não 
negatividade: xs ≥ 0). Esta nova variável aparece com coeficiente zero na função 
objetivo e, somando na equação correspondente (que agora é uma identidade 
matemática ou equação de igualdade). 
a11·x1 + a12·x2 ≤ b1 a11·x1 + a12·x2 + 1·xs = b1 
• Restrição do tipo "≥" 
No caso de uma desigualdade do tipo "≥", deve-se acrescentar também uma 
nova variável chamada de variável de excesso xs (com condição de não 
negatividade: xs ≥ 0). Esta nova variável aparece com coeficiente zero na função 
objetivo e, subtraindo na equação correspondente. 
Surge agora um problema com a condição de não negatividade com esta nova 
variável do problema. As inequações contendo uma desigualdade do tipo "≥" 
ficariam: 
a11·x1 + a12·x2 ≥ b1 a11·x1 + a12·x2 - 1·xs = b1 
Ao realizar a primeira iteração do método Simplex, as variáveis básicas não 
estarão na base e assumirão o valor zero. Neste caso, a nova variável xs, depois 
de zerar x1 e x2, assumirá o valor -b1 além de não cumprir a condição de não 
negatividade. É necessário adicionar outra variável xr, chamada de variável 
artificial, que também aparecerá com coeficiente zero na função objetivo e 
somando na restrição correspondente. Ficando da seguinte maneira: 
a11·x1 + a12·x2 ≥ b1 a11·x1 + a12·x2 - 1·xs + 1·xr = b1 
• Restrição do tipo "=" 
Ao contrário do que se poderia pensar, para restrições do tipo "=" (embora já 
sejam identidades) também é necessário adicionar variáveis artificiais xr. Como 
no caso anterior, seu coeficiente será zero na função objetivo e aparecerá 
somando na restrição correspondente. 
a11·x1 + a12·x2 = b1 a11·x1 + a12·x2 + 1·xr = b1 
No último caso, é evidente que as variáveis artificiais representam uma violação 
das leis da álgebra, de modo que será necessário garantir que as variáveis 
artificiais tenham um valor 0 na solução final. Esta é a responsabilidade 
do método das Duas Fases e por isso, sempre que apareça este tipo de variável, 
se deverá realizar este procedimento. 
A tabela a seguir resume a desigualdade, o tipo de variável que aparece na 
equação padrão, assim como seu sinal: 
 
5.Existencia de variações de métodos e soluções 
Solução ótima: quando o critério de parada é satisfeito e não existam variáveis 
artificiais na base com valor positivo (os valores são indicados na coluna P0), a 
otimização foi alcançada.O valor Z0 atual é a solução ótima do problema, 
cumprindo para as variáveis que estão na base. Caso trate-se de um problema 
de minimização, o valor ótimo obtido deverá ser multiplicado por "-1". 
Soluções infinitas: satisfeito o critério de parada, se alguma variável de decisão 
não-básica tem um valor 0 na fila Z, significa que existe outra solução que 
fornece o mesmo valor ótimo para a função objetivo. Neste caso, o problema 
admite infinitas soluções, todas as quais abrangidas dentro do segmento (ou 
parte do plano, região de espaço, etc., conforme o número de variáveis do 
problema) definido por A·X1 + B·X2 = Z0. Através de uma nova iteração e 
fazendo com que a variável de decisão que tenha 0 na linha Z entre na base, é 
obtida uma solução diferente para o mesmo valor ótimo. 
Solução ilimitada (unbounded): se toda coluna da variável que entra na base 
tem todos os seus elementos negativos ou nulos, trata-se de um problema não-
limitado, ou seja, que tem solução ilimitada. Não há valor ótimo concreto para a 
função objetivo, mas à medida que os valores das variáveis são aumentados, o 
valor Z também aumenta sem violar qualquer restrição. 
Não existe solução: quando nenhum ponto satisfaz às restrições do problema, 
ocorre a inviabilidade, não existindo nenhuma solução possível para ele. Neste 
caso, uma vez terminadas todas as iterações do algoritmo, existem na base 
variáveis artificiais em que o valor é superior a zero. 
Empate de variável de entrada: quando ocorre um empate na escolha da 
variável entrante, pode-se optar por qualquer uma delas sem que isto afete a 
solução final. Por outro lado, se ela influencia o número de iterações necessárias 
para obter a solução. É aconselhável optar pelas variáveis básicas, já que elas 
são as que farão parte da solução ótima. 
Empate de variável de saída: novamente é possível optar por qualquer uma 
delas. No entanto, a fim de não ampliar o problema e evitar que a entrada fique 
em um ciclo infinito (caso degenerado), discrimina-se a favor das variáveis de 
decisão fazendo que permaneçam na base. No caso de ser a primeira fase do 
método das Duas Fases, se optará por retirar da base as variáveis artificiais. 
Curiosidade na fase 1: ao finalizar a fase 1, caso o problema original tenha 
solução, todas as variáveis artificiais na linha indicadora devem ter o valor "1". 
O elemento pivô pode ser nulo?: Não, o elemento pivô sempre será 
estritamente positivo já que apenas realizam-se os quocientes entre os valores 
não-negativos e maiores que zero (em um problema de maximização). 
6.Exemplo de resolução 
Empresa que fabrica apenas dois Produtos: 
Ao modelar um problema de otimização, deve-se ficar atento as seguintes 
questões de extrema importância nesse processo: Quais as variáveis de 
decisão, qual o objetivo e quais são as restrições. Sendo assim, devem-se: 
• Explicitar as decisões a serem tomadas e representá-las através de variáveis 
de decisão 
(x1, x2...), o qual, se o problema é de programação de produção as variáveis de 
decisão são as quantidades a produzir no período. 
• Identificar o objetivo da tomada de decisão, que geralmente será a 
maximização de lucro ou receita, minimização de custos, perda, etc. A função 
objetivo calculará o valor do objetivo (lucros, receita, perda, etc), em função das 
variáveis. 
• Restringir as variáveis através de equações ou inequações matemáticas 
lineares. 
 
Descrição do Problema (Quando as Restrições são todas ≤): 
Uma empresa pode-se fabricar dois produtos 1 e produto 2. Na fabricação do 
produto 1 a empresa gasta nove horas-homem e três horas-máquina, onde a 
tecnologia utilizada é intensiva em mão-de-obra. Na fabricação do produto 2 a 
empresa gasta uma hora-homem e uma hora-máquina, onde a tecnologia é 
intensiva em capital. Sendo x1 e x2 as quantidades fabricadas dos produtos 1 e 
2 e sabendo-se que a empresa dispõe de 18 horas-homem e 12 horas-máquina 
e ainda que os lucros dos produtos são $4 e $1 respectivamente, quanto deve 
fabricar cada produto para obter o maior lucro possível? 
 
Modelagem do Problema 
 Admitindo que não há economia de escala, mas quantidades fabricadas quanto 
ao lucro, a função lucro a ser maximizada é: 
L = 4 x1 + x2 
por uma escolha de x1 e x2. 
Se o problema parasse aqui o lucro seria ilimitado. Porém, existem recursos 
limitados. 
O que limita as quantidades fabricadas aqui são as horas-homem e horas-
máquina disponíveis. Assim, as quantidades fabricadas e as horas utilizadas de 
cada recursos não podem ultrapassar as quantidades de recursos disponíveis, 
ou seja: 
 H-H 9x1 + x2 ≤ 18 e 
 H-M 3x1 + x2 ≤ 12 
 Assim, o lucro só poderá crescer até esses limites. 
 Temos então o seguinte modelo matemático: 
 Max L = 4 x1 + x2 
 sujeito a: 
 horas-homem 9x1 + x2 ≤ 18 
 horas-máquina 3 x1 + x2 ≤ 12 
 x1 ≥ 0 e x2 ≥ 0 
 
Consideremos então o modelo: 
Max. L = 4x1 + x2 
 
 9x1 + x2 + xf1 =18 
Sujeito a: 3x1 + x2 + xf2 =12 
 x1 ≥ 0, x2 ≥ 0, xf1 ≥ 0, xf2 ≥ 0 
 
Cálculo da Nova Solução Básica: 
Variável que entra na base: entra na base a variável com coeficiente negativo de 
maior valor absoluto. A ideia é melhorar rapidamente o valor de L. Examinando 
a função objetivo do exemplo: 
 
L - 4x1 - x2 = 0 ou L = 4x1 + x2 
Entra a variável x1, pois cada unidade a mais em x1, aumenta L em 4 unidades. 
 
Variável que sai: sai a variável que primeiro se anula com a entrada da variável 
escolhida no item anterior, no caso x1, que entra com maior valor possível. Ela 
pode ser descoberta dividindo-se os termos da direta das restrições pelos 
coeficientes positivos da variável que entra. O menor valor indica que a variável 
básica dessa linha é a que primeiro se anula e sairá da base. 
9x1 + x2 + xf1 = 18 18 ÷9 = 2 → sai 
3x1 + x2 + xf2 = 12 12 ÷3 = 4 
 ↑ 
Entra 
 
Elemento pivô 
A coluna da variável que entra e a linha da variável que sai identificam um 
elemento chamado pivô. A linha da variável que sai é também linha pivô. No 
caso, a primeira linha é a pivô e o coeficiente 4 de x2 é o elemento pivô. 
 
Calculando a nova solução 
 D1. Vamos organizar a função objetivo e restrições numa tabela com colunas 
formadas pelos coeficientes de cada variável e outra dos termos independentes. 
L X1 X2 Xf1 Xf2 b 
1 -4 -1 0 0 0 
0 9 1 1 0 18 
0 3 1 0 1 12 
 ↑ 
 Entra 
 
D2. Dividimos a linha pivô pelo valor do elemento pivô, obtendo uma nova linha 
com pivô unitário. 
 
Linha pivô: 0 9 1 1 0 18 
Dividindo por 4: 0 1 0,111 0,111 0 2 →nova linha pivô. 
 
D3. Vamos reescrever cada uma das outras linhas da seguinte maneira: 1º 
Multiplicar os elementos da nova linha pivô pelo coeficiente da variável que entra 
da outra linha, com sinal trocado. 2º Somar termo a termo com os elementos da 
outra linha. Sendo assim, o coeficiente da variável que entra (x1) na primeira 
linha é -4. Então: 
 
nova linha pivô: 0 1 0.111 0.111 0 2 
x4: 0 4 0.444 0.444 0 8 
+ primeira linha: 0 -4 -1 0 0 0 
 
Soma = nova primeira linha: 1 0 -0.555 0.444 0 8 
 
O coeficiente da variável que entra (x1) na terceira linha é 3. Então: 
 
nova linha pivô: 0 1 0.111 0.111 0 2 
x (-3): 0 -3 -0.333 -0.333 0 6 
+ terceira linha: 0 3 1 0 1 12 
 
Soma = nova terceira linha: 0 0 0.666 -0.333 1 6 
Reescrevemosa tabela com os resultados obtidos teremos: 
 
L X1 X2 Xf1 Xf2 b 
1 0 -0.555 0.444 0 8 
0 1 0.111 0.111 0 2 
0 0 0.666 -0.333 1 6 
 
De onde concluímos a nova solução: 
Variáveis não básicas: Variáveis básicas Valor de L: 
 x2 = 0 X1 = 2 L = 8 
xf1 = 0 xf2 = 6 
A função objetivo na nova solução está escrita em termos das variáveis 
não básicas x2 e xf1.as variáveis básicas tem coeficientes nulos. 
A solução obtida tem L = 8, contra L = 0 da solução inicial. É melhor, mas 
ainda não é ótima, pois o coeficiente de x2 na função objetivo é negativo. 
Variável que entra: x2 (coeficiente negativo de maior valor absoluto na função 
objetivo). 
Variável que sai: 
Vamos dividir os termos independentes pelos coeficientes positivos de x2: 
2 ÷0.111 = 18 
6 ÷0.666 = 9 → menor valor: sai a variável dessa linha no caso xf2. 
 
Reescrevendo a nova linha tabela como os resultados obtidos teremos: 
L X1 X2 Xf1 Xf2 b 
1 0 0 0.1666 0.8333 13 
0 1 0 0.1666 -0.1666 1 
0 0 1 -0.5 1.5 9 
 
A nova solução será, portanto: 
Variáveis não básicas: Variáveis básicas Valor de L: 
xf1 = 0 x1 = 1 L = 13 
Xf2 = 0 x2 = 9 
A função objetivo está escrita em termos das variáveis não básicas xf1 e 
xf2, pois os coeficientes das variáveis são nulos. O valor de L passou de L = 8 
para L = 13. Essa solução é ótima, pois os coeficientes das variáveis não básicas 
na função objetivo são positivos. Se xf1 ou xf2 entrar na base, o valor de L 
diminui, contrariando o objetivo. 
 
7.Ferramentas computacionais para resolução de 
problemas lineares 
Resolução utilizando o R: Para a resolução do exercício no R podem ser 
utilizados entre outros, os pacotes ‘boot’ (CANTY; RIPLEY, 2012) e ‘Rglpk’ 
(HORNIK; THEUSSL, 2012) que possuem funções para resolver problemas de 
programação linear. 
Resolução utilizando o LINDO: Para proceder a resolução por meio do LINDO é 
necessário que após abrir o programa se escreva max ou min antes da função 
objetivo e após a mesma introduza a expressão subject to. Então, entre com as 
restrições, finalizando com a expressão end. 
Resolução utilizando o EXCEL: Inicialmente deve-se transferir os dados do 
problema para a planilha do excel utilizando qualquer uma das células. Como o 
problema apresenta apenas duas variáveis escolha duas células e introduza os 
coeficientes da função objetivo Z. Em seguida, para as variáveis de decisão 
deixe duas células em branco abaixo das mesmas. Escolha outra célula e 
formule a função objetivo conforme foi dada no exercício, multiplicando-se o 
coeficiente 4 pela célula em branco abaixo de x1, que representa x1, após 
multiplique 1 pela célula em branco abaixo de x2, que representa x2. Feito isso, 
deve-se inserir as restrições do modelo. Os valores abaixo de x1 e x2 
representam os coeficientes de restrição do modelo, as equações de restrição 
são dadas pela soma das multiplicações dos coeficientes de restrição pelas 
variáveis de decisão (células em branco abaixo de x1 e x2). Feito isso, deve-se 
inserir as constantes que representam os recursos disponíveis, dados no 
exercício. 
Para livre acesso encontrei a ferramenta LibreOffice que tem a maioria das 
funções do Excel, sendo um bom substituto para o mesmo.