Programação Linear e Teoria de Grafo

Prévia do material em texto

Dionísio Ernesto Tomás 
 
 
 
 
 
 
 
Método Simplex 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
NAMPULA, 2021
 
Método Simplex 
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: 
I. Todas as variáveis são não-negativas: 
II. Todos os bi’ são não-negativos; 
III. Todas as equações iniciais do sistema são do tipo “ “. Assim, na forma padrão, só 
encontra-se variáveis de folga. 
O método Simplex é um processo iterativo que permite melhorar a solução da função 
objectivo em cada etapa. O processo finaliza quando não é possível continuar melhorando 
este valor, ou seja, quando se obtenha a solução óptima (o maior ou menor valor possível, 
segundo o caso, para que todas as restrições sejam satisfeitas). 
Com base no valor da função objectivo, em um ponto qualquer, o procedimento consiste em 
procurar outro ponto que melhore o valor anterior. Como se pode ver no método Gráfico, tais 
pontos são os vértices do polígono (ou poliedro ou polícoro, se o número de variáveis é maior 
do que 2) e que faz parte da região determinada pelas restrições a que está sujeito o problema 
(chamada de região viável). A pesquisa é realizada por meio de deslocamentos pelas arestas 
do polígono, a partir do vértice actual até um adjacente que melhore o valor da função 
objectivo. Sempre que exista região viável, e como seu número de vértices e de arestas é 
finito, será possível encontrar a solução. 
O método Simplex baseia-se na seguinte propriedade: se a função objectivo Z não toma seu 
valor máximo no vértice A, quer dizer que existe uma aresta que parte de A e ao longo da 
qual o valor de Z aumenta. 
Será necessário considerar que o método Simplex trabalha apenas com restrições do problema 
cujas desigualdades sejam do tipo "≤" (menor ou igual) e seus coeficientes independentes 
sejam maiores ou iguais a 0. Portanto, é preciso padronizar as restrições para atender aos 
requisitos antes de iniciar o algoritmo Simplex. Caso apareçam, depois deste processo, 
restrições do tipo "≥" (maior ou igual) ou "=" (igualdade), ou não seja possível alterá-las, será 
http://www.phpsimplex.com/pt/teoria_metodo_grafico.htm
necessário utilizar outros métodos de resolução, sendo o mais comum, o método das Duas 
Fases. 
Preparando o modelo para adaptá-lo ao método Simplex 
A forma padrão do modelo de problema consiste em uma função objectivo, sujeita a certos 
critérios (as restrições): 
Função objectivo: 𝑐1 · 𝑥1 + 𝑐2 · 𝑥2 + . . . + 𝑐𝑛 · 𝑥𝑛 
Sujeita às restrições: 𝑎11 · 𝑥1 + 𝑎12 · 𝑥2 + . . . + 𝑎1𝑛 · 𝑥𝑛 = 𝑏1 
𝑎21 · 𝑥1 + 𝑎22 · 𝑥2 + . . . + 𝑎2𝑛 · 𝑥𝑛 = 𝑏2 
𝑎𝑚1 · 𝑥1 + 𝑎𝑚2 · 𝑥2 + . . . + 𝑎𝑚𝑛 · 𝑥𝑛 = 𝑏𝑚 
𝑥1,..., 𝑥𝑛 ≥ 0 
O modelo deve atender às seguintes condições: 
I. O objectivo é maximizar ou minimizar o valor da função objectivo (por exemplo, 
aumentar lucros ou reduzir as perdas, respectivamente). 
II. Todas as restrições devem ser equações de igualdade (identidades matemáticas). 
III. Todas as variáveis (xi) devem ser positivas ou nulas (condição de não-negatividade). 
IV. Os termos independentes (bi) de cada equação devem ser não-negativos. 
V. HÉ preciso adaptar o problema de modelagem de acordo à forma padrão para poder 
aplicar o algoritmo Simplex. 
Tipo de Optimização. 
Como mencionado, o objetivo do método é optimizar o valor da função objectivo. No entanto, 
duas opções são apresentadas: obter o maior valor óptimo (maximizar) ou obter o menor valor 
óptimo (minimizar). 
Além disto, existem diferenças no algoritmo entre o objectivo 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: 
 Objectivo de maximização 
http://www.phpsimplex.com/pt/teoria_modelagem_problemas.htm
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. 
Exemplos de problemas resolvidos envolvendo a maximização e minimização 
1.1 Certa empresa fabrica dois produtos P1 e P2. O lucro unitário do produto P1 é de 
1.000,00 e o lucro unitário de P2 é 1.800. A empresa precisa de 20 horas para fabricar uma 
unidade de P1 e de 30 horas para fabricar uma unidade de P2. O tempo anual de produção 
disponível para isso é de 1200 horas. A demanda esperada para cada produto é de 40 unidades 
para P1 e 30 unidades para P2. Construa o modelo de programação linear que objectiva 
Maximizar o lucro. 
Solução: 
𝑃1: 𝐿𝑢𝑐𝑟𝑜 – 1.000,00 
𝑇𝑒𝑚𝑝𝑜 𝑑𝑒 𝑝𝑟𝑜𝑑𝑢çã𝑜 𝑃1: 20 ℎ𝑜𝑟𝑎𝑠 
𝑃2: 𝐿𝑢𝑐𝑟𝑜 – 1.800,00 
Tempo de produção P2: 30 horas 
Tempo Disponível de Produção: 1200 horas 
Demanda Esperada P1: 40 unidades 
Demanda Esperada P2: 30 unidades 
Unidade produzida do Produto P1: x 
Unidade produzida do Produto P2: y 
 
Função Objectivo: 
Maximizar: 𝟏𝟎𝟎𝟎𝒙 + 𝟏. 𝟖𝟎𝟎𝒚 
Restrições: 
Tempo de Produção: 1.200ℎ 
20𝑥 + 30𝑦  1.200 
Demanda Esperada do Produto P1: 40 unidades 
𝑥  40 
Demanda Esperada do Produto P2: 30 unidades 
𝑦  30 
Logo: 
Maximizar Lucro: 𝑴𝒂𝒙 𝒁 = 𝟏𝟎𝟎𝟎𝒙 + 𝟏. 𝟖𝟎𝟎𝒚 
Restrições: 
20𝑥 + 30𝑦  1.200 
𝑥  40 
𝑦  30 
𝑥 , 𝑦  0 
A 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. 
1.2 A necessidade mínima de vitaminas na alimentação é de 32 unidades por dia e a de 
proteínas de 36 unidades por dia. Uma pessoa tem disponível carne e ovo para se alimentar. 
Cada unidade de carne contém 4 unidades de vitaminas e 6 unidades de proteínas. Cada 
unidade de ovo contém 8 unidades de vitaminas e 6 unidades de proteínas. Qual a quantidade 
de carne e ovo que deve ser consumida de forma a ter o Menos custo possível. Cada unidade 
de carne custa 3,00 e cada unidade de ovo custa 2,5. 
Solução: 
Necessidade mínima de Vitamina: 32 unidades / dia 
Necessidade mínima de Proteínas: 36 unidades / dia 
1 unidade de carne: 










00,3$:
6
min4
RCusto
proteínasdeunidades
asvitaunidades
 
1 unidade de ovo: 










50,2$:
6
min8
RCusto
proteínasdeunidades
asvitaunidades
 
Unidade consumida de carne: x 
Unidade consumida de carne: y 
Minimizar Custo: 𝑴𝒊𝒏 𝒁 = 𝟑𝒙 + 𝟐, 𝟓𝒚 
Restrições: 
4𝑥 + 8𝑦  32 
6𝑥 + 6𝑦  36 
𝑥, 𝑦  0 
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 objectivo 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). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Referências bibliográficas 
Mateus, P. (s/d). Manual de Programação Linear e Teoria de Grafo – 3º Ano. Ensino à 
Distância - Universidade Católica de Moçambique 
 
	Método Simplex
	Método Simplex (1)
	Preparando o modelo para adaptá-lo ao método Simplex
	Tipo de Optimização.
	Exemplos de problemas resolvidos envolvendoa maximização e minimização
	Função Objectivo:
	A minimização
	Referências bibliográficas