Pesquisa Operacional
na Tomada de Decisões
Programação Linear
e Seus Teoremas
2ª Edição
Capítulo 2.3
© Gerson Lachtermacher,2005
Conteúdos do Capítulo
 Programação Linear e Convexidade

Teoremas Fundamentais
 Caso LCL Produtos Farmacêuticos S.A.
Capítulo 2.3
Programação Linear e Convexidade
 Conjunto Convexo em R2

Para quaisquer dois pontos do conjunto, todos os pontos que
formam o segmento de reta que os unem faz parte do
conjunto.
Conjunto
Convexo
Capítulo 2.3
Conjunto não
Convexo
Método Simplex
Teoremas Fundamentais
 Teorema I

O conjunto de todas as soluções viáveis de um modelo de
Programação Linear formam um conjunto convexo.
 Teorema II

Toda solução compatível básica, do sistema de equações
lineares de um modelo de Programação linear, é um ponto
extremo do conjunto de soluções viáveis, isto é, do conjunto
de convexo de soluções.
Capítulo 2.3
Método Simplex
Teoremas Fundamentais
 Considere a solução gráfica do problema
21=5x1+2x2
x2
E
(0,4)
D
(1,4)
21
C
(3,3)
Solução
Viável
15
13
8
A
B
(0,0)
(3,0)
Capítulo 2.3
z
pontos
extremos
x1
A B C D E
Método Simplex
Teoremas Fundamentais
 Teorema III

Se a função-objetivo possui um ótimo finito, então pelo
menos uma solução ótima é um ponto extremo do conjunto
convexo de soluções viáveis.

Se a função-objetivo assume o ótimo em mais de um ponto
extremo do conjunto de soluções viáveis, então ela toma o
mesmo valor para qualquer ponto do segmento da reta que
une esses pontos extremos.
Capítulo 2.3
Verificação Geométrica do Teorema III
1a parte
 O valor da função-objetivo varia quando esta se desloca. Logo, o
valor ótimo (mínimo ou máximo) será obtido deslocando-se o
máximo ou o mínimo a função-objetivo.
x2
E
D
(1,4)
(0,4)
(3,3)
Solução
Viável
Mínimo =A
(0,0)
Capítulo 2.3
C = máximo
B (3,0) x1
Verificação Geométrica do Teorema III
2a parte
 Entretanto, a função-objetivo pode assumir uma inclinação tal
que no ponto ótimo ela coincida com a inclinação de alguma
restrição.
Soluções
x2
Múltiplas
D
E
(1,4)
C
(0,4)
(3,3)
Em todos os pontos do
segmento de reta CD, o
Solução
valor da função-objetivo
Viável
A
B
é o mesmo
(0,0)
(3,0) x1
Capítulo 2.3
Método Simplex
Teoremas Fundamentais
 Considere a solução gráfica do problema
z
x2
E
(0,4)
D
(1,4)
C
(3,3)
Solução
Viável
A
B
(0,0)
(3,0)
Capítulo 2.3
pontos
extremos
x1
A B C D E
Caso LCL Produtos Farmacêuticos
 As indústrias LCL Produtos Farmacêuticos Ltda. desejam
produzir dois medicamentos, um analgésico e um antibiótico, que
dependem de duas matérias primas A e B, que estão disponíveis
em quantidades de 5 e 8 toneladas, respectivamente. Na
fabricação de uma tonelada de analgésico são empregadas uma
tonelada da matéria A e uma tonelada da matéria B, e na
fabricação de uma tonelada de antibiótico são empregadas uma
tonelada de A e quatro toneladas de B. Sabendo que cada
tonelada de analgésico é vendida a $8,00 e de antibiótico a $5,00,
encontre, através da determinação dos pontos extremos do
conjunto de soluções viáveis, a quantidade de toneladas de
medicamentos a serem produzidas pelas indústrias LCL de
maneira a maximizar seu lucro.
Capítulo 2.3
Caso LCL Produtos Farmacêuticos
 Hipótese Assumida

Quantidade Produzida = Quantidade Vendida
 Variáveis de Decisão

x1 – Quantidade de Toneladas de Analgésico a ser produzida.

x2 – Quantidade de Toneladas de Antibiótico a ser produzida.
Capítulo 2.3
Caso LCL Produtos Farmacêuticos
 Função-Objetiva –
Maximizar o Lucro
Max 8 x1 + 5 x2
 Restrições de Matéria
Prima
1x1 + 1x2  5
1x1 + 4 x2  8
 Restrições de não
negatividade
x1  0 ; x2  0
Capítulo 2.3
Caso LCL Produtos Farmacêuticos
Solução Gráfica
z = 8x1 + 5x2
x1 = 0 , x2 = 0  z = 0
(0;2)
(4;1)
(0;0)
Capítulo 2.3
(5;0)
x1 = 0 , x2 = 2  z =10
x1 = 5 , x2 = 0  z = 40
x1 = 4 , x2 =1 z = 37