Baixe o app para aproveitar ainda mais
Prévia do material em texto
ENP153 –Programação Linear Aula 04 – Resolução gráfica de PPL INTRODUÇÃO Um problema de programação linear consiste em determinar valores não negativos para variáveis de decisão, satisfazendo as restrições impostas de forma a otimizar (maximizar ou minimizar) uma função, que é linear INTRODUÇÃO Para problemas que apresentam duas variáveis de decisão, a solução ótima pode ser encontrada graficamente Um problema com três variáveis também pode ser resolvido graficamente, mas na maioria das vezes, torna-se uma tarefa árdua A partir de quatro variáveis a resolução somente será possível algebricamente PASSOS PARA RESOLVER UM PPL 1° passo •Definir o modelo de programação linear 2º passo 3º passo 4º passo PASSOS PARA RESOLVER UM PPL 1° passo •Definir o modelo de programação linear 2º passo •Definir as curvas de restrições 3º passo 4º passo PASSOS PARA RESOLVER UM PPL 1° passo •Definir o modelo de programação linear 2º passo •Definir as curvas de restrições 3º passo •Definir a curva de objetivo 4º passo PASSOS PARA RESOLVER UM PPL 1° passo •Definir o modelo de programação linear 2º passo •Definir as curvas de restrições 3º passo •Definir a curva de objetivo 4º passo •Resolver o PPL PASSOS PARA RESOLVER UM PPL 1° passo •Definir o modelo de programação linear 2º passo •Definir as curvas de restrições 3º passo •Definir a curva de objetivo 4º passo •Resolver o PPL PASSO 1 𝜑 = max 𝑓 𝑥1, 𝑥2 = 200𝑥1 + 300𝑥2 𝑠. 𝑡. R1: 2𝑥1 + 𝑥2 ≤ 20 R2: 4𝑥1 ≤ 32 R3: 𝑥2 ≤ 10 R4: 𝑥1, 𝑥2 ≥ 0 PASSOS PARA RESOLVER UM PPL 1° passo •Definir o modelo de programação linear 2º passo •Definir as curvas de restrições 3º passo •Definir a curva de objetivo 4º passo •Resolver o PPL PASSO 2 Inicialmente, determina-se o conjunto de pontos 𝑥1, 𝑥2 que satisfaçam as restrições Para isso, determinam-se os pontos no plano cartesiano que satisfaçam cada uma das inequações das restrições R1: 2𝑥1 + 𝑥2 ≤ 20 Ao se atribuir valores para 𝑥1 e 𝑥2, a equação 2𝑥1 + 𝑥2 não pode resultar em valor superior a 20 Deste modo, para se criar a curva de atendimento a restrição, cria-se os pontos extremos da curva: 𝑝𝑎𝑟𝑎 𝑥1 = 0, 𝑥2 = 20 𝑝𝑎𝑟𝑎 𝑥2 = 0, 𝑥1 = 10 PASSO 2 PASSO 2 R1: 2𝑥1 + 𝑥2 ≤ 20 Ao se atribuir valores para 𝑥1 e 𝑥2, a equação 2𝑥1 + 𝑥2 não pode resultar em valor superior a 20 Deste modo, para se criar a curva de atendimento a restrição, cria-se os pontos extremos da curva: 𝑝𝑎𝑟𝑎 𝑥1 = 0, 𝑥2 = 20 𝑝𝑎𝑟𝑎 𝑥2 = 0, 𝑥1 = 10 PASSO 2 O mesmo processo deve ser efetuado para R2, R3 e R4 R2: 𝑥1 = 8 R3: 𝑥2 = 10 R4: 𝑥1 = 0, 𝑥2 = 0 PASSO 2 Os pontos que satisfazem todas as restrições estão na intersecção das regiões encontradas por R1, R2, R3 e R4 O conjunto de pontos que satisfazem todas as restrições é chamado de região viável, ou zona de viabilidade PASSOS PARA RESOLVER UM PPL 1° passo •Definir o modelo de programação linear 2º passo •Definir as curvas de restrições 3º passo •Definir a curva de objetivo 4º passo •Resolver o PPL PASSO 3 Para se determinar, caso exista, um ponto 𝑥1 ∗, 𝑥2 ∗ que pertence ao conjunto de pontos viáveis, de forma que a função objetivo assuma o maior valor possível, deve-se plotar as curvas de nível para 𝑓 𝑥1, 𝑥2 Para se obter as curvas de nível, primeiro precisa-se obter o vetor gradiente PASSO 3 O vetor gradiente de 𝑓 𝑥1, 𝑥2 é dado por: 𝛻𝑓 𝑥1, 𝑥2 = 𝜕𝑓 𝜕𝑥1 , 𝜕𝑓 𝜕𝑥2 𝛻𝑓 𝑥1, 𝑥2 = 200, 300 PASSO 3 As curvas de nível são criadas a partir da multiplicação do vetor gradiente por valores escalares, de modo a criar curvas paralelas ao 𝛻𝑓 𝐶𝑁 𝑘 = 𝑘 × 𝛻𝑓, 𝑜𝑛𝑑𝑒 𝑘 ∈ 𝑅 𝐶𝑁 0.01 = 2, 3 𝐶𝑁 0.02 = 4, 6 ... PASSO 3 PASSOS PARA RESOLVER UM PPL 1° passo •Definir o modelo de programação linear 2º passo •Definir as curvas de restrições 3º passo •Definir a curva de objetivo 4º passo •Resolver o PPL PASSO 4 PASSO 4 último ponto a ser tocado pelas curvas de nível SOLUÇÃO ÓTIMA MÚLTIPLAS SOLUÇÕES ÓTIMAS INFINITAS SOLUÇÕES ÓTIMAS SOLUÇÃO ÓTIMA INFINITA NÃO EXISTE SOLUÇÃO (INVIABILIDADE) EXEMPLO 𝜑 = min𝑓 𝑥1, 𝑥2 = 30𝑥1 + 20𝑥2 𝑠. 𝑡. R1: 4𝑥1 + 𝑥2 ≥ 20 R2: 𝑥1 + 2𝑥2 ≥ 10 R3: 𝑥1 ≥ 2 R4: 𝑥1, 𝑥2 ≥ 0
Compartilhar