Plano de Aula PO1 Capitulo 6 - Programação Linear Forma Padrão

Prévia do material em texto

Apostila de Exercícios da 
Disciplina de Pesquisa 
Operacional I 
Capítulo 6 – PL e Forma Padrão 
Luís Alberto Duncan Rangel 
Depto. de Engenharia de Produção da EEIMVR 
Universidade Federal Fluminense 
luisduncan@id.uff.br 
Volta Redonda, RJ 
SUMÁRIO 
6. Programação Linear: 
6.1 Definição de um PPL 
6.2 Forma Padrão de um PPL 
6.3 Forma Canônica de um PPL 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.1 Algoritmo Simplex através dos quadros 
6.4.2 Tipos de soluções de um PPL 
6.4.3 Uma única solução ótima 
6.4.4 Múltiplas ou infinitas soluções ótimas 
6.4.5 Método das Duas Fases 
6.4.6 Uma única solução ótima 
6.4.7 Múltiplas ou infinitas soluções ótimas 
6.5 Exercícios para colocar o PPL na Forma Padrão 
6.1 Definição de um Problema de Programação Linear 
O algoritmo Simplex foi desenvolvido por Dantzig em 1947, para 
resolver Problema de Programação Linear (PPL) . O objetivo do 
algoritmo é otimizar a função objetivo. Para fazer isto é necessário 
colocar o PPL esteja em uma forma adequada para implementar o 
algoritmo. 
Na Forma Padrão as inequações são transformadas em equações. 
Na Forma Canônica, além das restrições estarem escritas através 
de equações, há uma solução básica inicial que Método SIMPLEX 
busca melhorar a cada interação. 
Em muitas publicações e trabalhos o PPL na Forma Canônica é 
chamado de PPL na Forma Padrão, como será utilizado aqui. 
6. Programação Linear 
6.1 Definição de um PPL 
Max (ou Min) Z = c1x1 + c2x2 + c3x3 + . . . + cnxn 
Sujeito a: a11x1 + a12x2 + a13x3 + . . . + a1nxn <= b1 
 a21x1 + a22x2 + a23x3 + . . . + a2nxn <= b2 
 . . . 
 ak1x1 + ak2x2 + ak3x3 + . . . + aknxn >= bk 
 . . . 
 am1x1 + am2x2 + am3x3 + . . . + amnxn = bm 
 x1>=0; x2>=0; x3>=0; . . . ; xn>=0 
 
 
6. Programação Linear 
6.1 Definição de um PPL 
Nesta forma, pode-se associar o seguinte significado a cada 
elemento do modelo do PPL: 
x (n.x.1) é o vetor coluna das variáveis de decisão do PPL 
c (1.x.n) é o vetor linha dos coeficientes da função objetivo do PPL 
A (m.x.n) é a matriz dos coeficientes tecnológicos do PPL 
B (m.x.1) é o vetor coluna dos coeficientes dos recursos 
disponíveis ou necessários do PPL. 
6. Programação Linear 
6.2 Transformação de um PPL para a Forma Padrão 
Nesta forma do modelo matemático as restrições do modelo são 
descritas através de equações lineares. Não existem inequações 
nesta forma de representação do modelo matemático. 
Max (ou Min) Z = c1x1 + c2x2 + c3x3 + . . . + cnxn 
Sujeito a: a11x1 + a12x2 + a13x3 + . . . + a1nxn = b1 
 a21x1 + a22x2 + a23x3 + . . . + a2nxn = b2 
 . . . 
 ak1x1 + ak2x2 + ak3x3 + . . . + aknxn = bk 
 . . . 
 amx1 + am2x2 + am3x3 + . . . + anxn = bm 
 x1>=0; x2>=0; x3>=0; . . . ; xn>=0 
 
6. Programação Linear 
6.2 Transformação de um PPL para a Forma Padrão 
 
Em notação matricial tem-se: 
 
Max (ou Min) Z = C.X 
Sujeito a: A.X = B 
 X>=0 
6. Programação Linear 
6.3 Forma Canônica de um PPL 
 
O PPL na Forma Canônica, além de estar representado somente 
por equações lineares, o PPL apresenta uma solução básica inicial 
para que o algoritmo SIMPLEX inicie a busca pela solução ótima. 
 
O PPL na Forma Canônica apresenta uma matriz identidade, que é 
a solução do PPL. 
 
Em muitas publicações e trabalhos o PPL na Forma Canônica é 
chamado também de PPL na Forma Padrão. 
 
6. Programação Linear 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.1 Desigualdade do tipo menor ou igual: 
 
Se uma restrição for representada da seguinte forma: 
 X1 + 3X2 + 5X3 <= 9 
 
Para transforma esta restrição, faz-se necessário a inserção de 
uma variável de folga. Desta forma, tem-se: 
 
 X1 + 3X2 + 5X3 + XF4 = 9 
 
6. Programação Linear 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.1 Desigualdade do tipo menor ou igual: 
 
Se uma restrição for representada da seguinte forma: 
 X1 + 3X2 + 5X3 <= 9 
 
Para transforma esta restrição, faz-se necessário a inserção de 
uma variável de folga. Desta forma, tem-se: 
 
 X1 + 3X2 + 5X3 + XF4 = 9 
 
6. Programação Linear 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.1 Desigualdade do tipo menor ou igual: 
 
Exemplo. Coloque o PPL abaixo na forma padrão: 
 
MAX Z = 6X1 + 2X2 + 4X3 
S.A. 
 3X1 - 5X2 <= 31 
 8X1 + 9X3 <= 29 
 X1>=0; X2>=0; X3>=0 
 
6. Programação Linear 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.1 Desigualdade do tipo menor ou igual: 
 
 
Na Forma Padrão 
 
MAX Z = 6X1 + 2X2 + 4X3 
S.A 
 3X1 - 5X2 + XF4 = 31 
 8X1 + 9X3 + XF5 = 29 
 X1>=0; X2>=0; X3>=0, XF4>=0, XF5>=0 
 
6. Programação Linear 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.2 Desigualdade do tipo maior ou igual: 
 
Se uma restrição for representada da seguinte forma: 
 4X3 + 7X5 >= 13 
 
Para transforma esta restrição, faz-se necessário a inserção de 
uma variável de folga com sinal negativo. Desta forma, tem-se: 
 
 4X3 + 7X5 – XF6 = 13 
 
6. Programação Linear 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.2 Desigualdade do tipo maior ou igual: 
 
Exemplo. Coloque o PPL abaixo na forma padrão: 
 
MAX Z = X1 + 2X4 – 5X5 
SUJEITO A 
 X1 - 3X3 >= 27 
 2X2 + 9X4 >= 16 
 X1>=0; X2>=0; X3>=0; X4>=0; X5>=0 
 
6. Programação Linear 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.2 Desigualdade do tipo maior ou igual: 
 
Na Forma Padrão: 
 
MAX Z = X1 + 2X4 – 5X5 
SUJEITO A 
 X1 - 3X3 – XF6 = 27 
 2X2 + 9X4 – XF7 = 16 
 X1>=0; X2>=0; X3>=0; X4>=0; X5>=0 
 XF6>=0; XF7>=0 
 
6. Programação Linear 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.3 Variável sem restrição de sinal: 
Se uma variável do modelo matemático puder assumir qualquer 
valor, isto é, valores positivos, negativos ou nulos, é necessário a 
sua substituição por duas outras variáveis que só possam assumir 
valores positivos. 
 
 X4 – pode assumir qualquer valor (X4 – qq). 
 
6. Programação Linear 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.3 Variável sem restrição de sinal: 
 
Desta forma, esta variável será substituída pela expressão: 
 
 X4 = X41 – X42 
 
sendo que X41 >=0; e X42 >= 0. 
Assim: 
Se X41 > X42 o valor a ser assumido por X4 é positivo. 
Se X41 < X42 o valor a ser assumido por X4 é negativo. 
Se X41 = X42 o valor a ser assumido por X4 é nulo. 
6. Programação Linear 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.4 Lado direito negativo: 
 
Se uma restrição apresenta um valor negativo no lado direito, para 
colocar esta restrição na forma padrão, tem-se que multiplicar toda 
a restrição por (-1), alterando os sinais das constantes, invertendo 
o sinal da inequação e alterando o valor do lado direito da 
restrição por um valor positivo. 
 
Por exemplo: 2x1 – 7x2 >= - 9 
 
Multiplicando a restrição por (-1) tem-se: 
 
 - 2x1 + 7x2 <= 9 
6. Programação Linear 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.5 Variáveis que só podem assumir valores negativos: 
 
Se uma variável quando for definida em um PPL só puder assumir 
valores negativos ou nulo, esta variável tem que ser substituída 
por uma outra variável com sinal trocado. 
 
Por exemplo: X8 <= 0 
 
Esta variável é substituída por uma outra variável com sinal 
trocado: 
 X81 = - X8 
 
Em que: X81 >= 0 
6. Programação Linear 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.6 Equivalência entre Min e Max: 
 
Se um PPL tiver por objetivo a minimização da FO, pode-se fazer a 
transformação deste PPL de minimização em maximização, através 
da multiplicação da FO do PPL de minimização por (-1). Desta 
forma, estar-se-á trabalhando com o simétrico da FO, e nada será 
alterado em relação à otimização da FO. 
 
Por exemplo: (FO) MIN Z = 3X1 – 2X2 
 
Multiplicando a FO por (-1) ter-se-á: (FO) MAX - Z = - 3X1 + 2X2 
6. Programação Linear 
6.4 Transformaçãode um PPL para a Forma Padrão 
6.4.6 Exercício – Coloque o PPL na Forma Padrão: 
 
 MAX Z = 4X1 + 3X2 + 5X4 
 S.A. 
 2X2 + 4X3 + 3X4 <= 24 
 3X1 + 2X2 + 4X3 <= 48 
 4X1 - 4X2 + 5X4 <= 80 
 X1>=0; X2>=0; X3>=0; X4>=0 
6. Programação Linear 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.6 Exercício – Coloque o PPL na Forma Padrão: 
 
Na Forma Padrão: 
 
 MAX Z = 4X1 + 3X2 + 5X4 
 S.A. 
 2X2 + 4X3 + 3X4 + XF5 = 24 
 3X1 + 2X2 + 4X3 + XF6 = 48 
 4X1 - 4X2 + 5X4 + XF7 = 80 
 X1>=0; X2>=0; X3>=0; X4>=0 
 XF5>=0; XF6=0; XF7>=0 
6. Programação Linear 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.6 Exercício – Coloque o PPL na Forma Padrão: 
 
 MIN Z = 2X1 - X2 + 3X3 
 S.A. 
X2 + 3X3 >= 12 
2X1 - X2 >= 14 
 3X1 + 2X2 + X3 <= 80 
 X1>=0; X2>=0; X3>=0 
6. Programação Linear 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.6 Exercício – Coloque o PPL na Forma Padrão: 
 
Na Forma Padrão: 
 
 MAX - Z = - 2X1 + X2 - 3X3 
 S.A. 
X2 + 3X3 – XF4 = 12 
2X1 - X2 – XF5 = 14 
 3X1 + 2X2 + X3 + XF6 = 80 
 X1>=0; X2>=0; X3>=0 
 XF4>=0; XF5=0; XF6>=0 
6. Programação Linear 
6.4 Transformação de um PPL para a Forma Padrão 
6.4.7 Quando uma restrição for descrita por uma equação, 
 esta equação deve ser substituída por duas 
 inequações. 
 
Por exemplo: 4X1 + 7X2 =9 
 
Substituir por: 4X1 + 7X2 >= 9 e 4X1 + 7X2 <=9 
 
Observação: uma outra maneira de tratar esta restrição é inserir 
uma variável artificial e criar uma FO artificial. Este exemplo será 
visto no Método SIMLEX das Duas Fases. 
6. Programação Linear 
6.5 Exercícios: Colocar o PLL na Forma Padrão 
 
Ex1: MAX Z = 5X1 + 2X2 
 S.A. 
 X1 <= 3 
 X2 <= 4 
 X1 + 2X2 <=9 
 X1>=0; X2>=0; 
 
6. Programação Linear 
6.5 Exercícios: Colocar o PLL na Forma Padrão 
 
Ex1: MAX Z = 5X1 + 2X2 
 S.A. 
 X1 + XF3 = 3 
 X2 + XF4 = 4 
 X1 + 2X2 + XF5 =9 
 X1>=0; X2>=0; 
 XF3>=0; XF4>=0; XF5>=0 
 
6. Programação Linear 
6.5 Exercícios: Colocar o PLL na Forma Padrão 
 
Ex2: MIN Z = 3X1 + 8X2 
 S.A. 
 2X1 + X4 <= 3 
 9X2 + X3 >= 4 
 3X1 + 2X2 >=9 
 X1>=0; X2>=0; X3>=0; X4>=0 
 
6. Programação Linear 
6.5 Exercícios: Colocar o PLL na Forma Padrão 
 
Ex2: MAX - Z = - 3X1 - 8X2 
 S.A. 
 2X1 + X4 + XF5 = 3 
 9X2 + X3 – XF6 = 4 
 3X1 + 2X2 – XF7 =9 
 X1>=0; X2>=0; X3>=0; X4>=0 
 XF5>=0; XF6>=0; XF73>=0 
 
 
6. Programação Linear 
6.5 Exercícios: Colocar o PLL na Forma Padrão 
 
Ex3: MAX Z = 6X1 + 7X3 
 S.A. 
 X2 + X3 <= 3 
 X3 + X4 >= 4 
 X1>=0; X2>=0; X3=qualquer; XF4>=0 
 
6. Programação Linear 
6.5 Exercícios: Colocar o PLL na Forma Padrão 
 
Ex3: MAX Z = 6X1 + 7X31 – 7X32 
 S.A. 
 X2 + X31 – X32 + XF5 = 3 
 X31 – X32 + X4 – XF6 = 4 
 X1>=0; X2>=0; X4>=0 
 X3 = X31-X32; X31>=0; X32>=0 
 XF5>=0; XF6>=0 
 
6. Programação Linear 
6.6 Exercícios – Modelos de PLL 
Uma indústria fabrica dois tipos de tintas, uma para interiores 
(TI) e outra para exteriores (TE). Sabe-se que para produzir um 
litro de TI são necessários 0,4 litros unidades do produto P1, 0,3 
litros de P2 e 0,3 litros de P3; já para produzir um litro de TE, 
são necessários 0,1 litros de P1, 0,5 litros de P2 e 0,4 litros de 
P3. Sabe-se também que o lucro com as vendas das tintas são 
R$ 23 e R$ 26 respectivamente para TI e TE. Escreva o modelo 
matemático de tal forma a obter o maior lucro possível, 
sabendo-se que a indústria tem disponível, 2000 litros de P1, 
3000 litros de P2 e 4000 litros de P3, e suponha que a indústria 
consiga vender toda a sua produção das duas tintas TI e TE. 
6. Programação Linear 
- Variáveis de Decisão: 
X1 – quantidade em litros a ser produzido da tinta para interior TI; 
X2 – quantidade em litros a ser produzido da tinta para exterior TE; 
As variáveis X1 e X2 são variáveis reais. 
 
- Restrições Tecnológicas: 
Restrições devido aos Produtos: 
Quantidade de P1, P2 e P3 que entra na composição de TI e TE: 
 0,4X1 + 0,1X2 <= 2000 (litros disponíveis de P1) 
 0,3X1 + 0,5X2 <= 3000 (litros disponíveis de P2) 
 0,3X1 + 0,4X2 <= 4000 (litros disponíveis de P3) 
 
6. Programação Linear 
- Restrições de não-negatividade: 
Como a produção de TI e TE não podem ser negativas, temos: 
X1 > 0 
X2 > 0 
 
- Função Objetiva: 
O lucro com as vendas dos conservantes: 
FO Max: Z = 23 X1 + 26 X2 
6. Programação Linear 
- Modelo Matemático do PPL Tintas: 
 
FO MAX: Z = 23 X1 + 26 X2 
Sujeito à: 
 0,4X1 + 0,1X2 <= 2000 
 0,3X1 + 0,5X2 <= 3000 
 0,3X1 + 0,4X2 <= 4000 
 X1 > 0 
 X2 > 0 
 X1 e X2 – Reais 
6. Programação Linear 
- Solução pelo Software LINDO SYSTEM: 
 
Forma do PPL para implementar no software LINDO: 
 
FO MAX 23 X1 + 26 X2 
ST 
 0.4X1 + 0.1X2 <= 2000 
 0.3X1 + 0.5X2 <= 3000 
 0.3X1 + 0.4X2 <= 4000 
 END 
6. Programação Linear 
- Solução do PPL - Tintas: 
 
Portanto, a indústria de tintas tem que produzir: 
4117,643 litros da tinta para interiores (TI), 
3529,411 litros da tinta para exteriores (TE), 
 
Com esta produção o lucro com a venda das duas tintas será 
de R$ 186.470,60 
6. Programação Linear