Baixe o app para aproveitar ainda mais
Prévia do material em texto
Tema 5: Solução de Problemas de Programação Linear – Parte I Profª Ivonete Melo de Carvalho, Me Para início de conversa Forma padrão para o método simplex • Modelos Equivalentes para o Uso do Método Simplex • Necessariamente, o problema de programação linear, deve estar na forma padrão. ⎪ ⎩ ⎪ ⎨ ⎧ ≥ ≤+ ≤+ += 0x,x 427x3x 10010x10x :aSujeito 40x60xZMax :ObjetivoFunção 21 21 21 21 Problema de Minimização Se a função objetivo for de minimizar, devemos multiplicá-la por (-1), obtendo uma função equivalente para maximização. Considere o seguinte problema de PL: Minimizar: Z = 3x1+4x2+x3 Sujeito a: x1 + x2 + x3 ≤ 10 3x1 + x2 - x3 ≤ 20 x1, x2, x3 ≥ 0 Quando a solução ótima for encontrada para o equivalente, não se esquecer de multiplicar por (-1) o “-Z” para obter “Z”. Modelo Equivalente na Forma Padrão Minimizar: Z = 3x1 - 4x2 +x3 *(-1) Maximizar: (-Z) = –3x1 + 4x2 – x3 Sujeito a: x1 + x2 + x3 ≤ 10 3x1 + x2 - x3 ≤ 20 x1, x2, x3 ≥ 0 Se uma variável do modelo não possuir a condição de não negatividade, pode-se substituí-la pela diferença de duas outras variáveis não negativas. Problema de Variável Livre Considere o seguinte problema de PL: Maximizar Z = x1 + 2x2 + x3 Sujeito a: x1 + x2 + x3 ≤ 10 2x1 + 3x2 ≤ 20 x1, x3 ≥ 0 x2 → livre Modelo Equivalente na Forma Padrão Modelo Original: Faremos : x2 = x4 - x5 Max Z = x1 + 2x2 + x3 S.a: x1 + x2 + x3 ≤ 10 2x1 + 3x2 ≤ 20 x1, x3 ≥ 0 x2 → livre Quando a solução ótima for ca lcu lada para o modelo equivalente, não se esquecer de substituir (x4 - x5) por “x2”. Modelo Equivalente na Forma Padrão Faremos : x2 = x4 - x5 Modelo Equivalente: Max Z = x1 + 2(x4-x5) + x3 S.a: x1 + (x4-x5) + x3 ≤ 10 2x1 + 3(x4-x5) ≤ 20 x1, x3 , x4, x5 ≥ 0 Continuando A segunda restrição aparece com sinal “≥” e a terceira restrição aparece com sinal “=” Problema de Solução Inicial Considere o seguinte problema de PL: Maximizar Z = x1 + x2 + x3 Sujeito a: 2x1 + x2 - x3 ≤ 10 x1 + x2 +2x3 ≥ 20 2x1 + x2 +3x3 = 60 x1, x2, x3 ≥ 0 Problema de Solução Inicial Aparece quando: • A restrição é do tipo ≥ Nesse caso, a variável de folga é subtraída e o seu valor é negativo, quando se anulam as variáveis de decisão; • A restrição é do tipo = Essas res t r i ções não recebem variáveis de folga. A função W deve ser escrita em termos das variáveis originais do problema e comporá o novo objetivo a ser minimizado. Quando as variáveis auxiliares forem todas não-básicas, então W será igual a zero . Modelo Equivalente na Forma Padrão A inserção das variáveis auxiliares no problema de programação linear nos leva a criar uma função objetivo auxiliar (W), formada pela soma das variáveis auxiliares: W = a1 + a2 + a3 + ... + an Modelo Equivalente na Forma Padrão Para estes casos, acrescentamos nas restrições do tipo “≥” as variáveis de folga e variáveis auxiliares (denominadas de “ai”) e nas restrições do tipo “=” acrescentamos apenas variáveis auxiliares com o objet ivo de formar um mode lo equ iva lente de programação linear, para então podermos utilizar o m é t o d o s i m p l e x p a r a solucioná-lo. Modelo Equivalente na Forma Padrão As variáveis auxiliares são abandonadas quando todas são, ao mesmo tempo, variáveis não-básicas no problema. Consequentemente a função objetivo auxiliar também é abandonada. Ter-se-á neste momento, o modelo original com uma solução básica inicial procurada. Vamos praticar? Programação Linear Utilizando Microsoft Excel Resolução do modelo de PL com o “Solver” Função Objetivo: Min Z = 22x1 + 26x2 + 30x3 Sujeita a: 20x1 + 20x2 + 10x3 ≥ 250 20x1 + 40x2 + 10x3 ≥ 230 30x1 + 20x2 + 40x3 ≥ 120 x1 , x2, x3 ≥ 0 Instale a ferramenta (1) Instale a ferramenta (2) Preparando a planilha Preenchendo os dados O “solver” • Na sequência serão apresentadas as telas da planilha com os comandos necessários para a utilização da ferramenta Solver da planilha Excel. • Abra sua planilha e acompanhe as orientações. Registrar a célula com a fórmula de Z (E11) Selecionar o Min para a Função Objetivo “Células” para informar os valores das variáveis de decisão. Adicionar as Restrições Célula da fórmula do 1º membro da restrição. Sinal da 1ª restrição. Célula do 2º membro da 1ª restrição Registrar a 1ª restrição. Clicar em Adicionar para inserir novas restrições. Registrar a 1ª restrição. Registrar a “três” restrições e “OK” para sair. Registrar a 3ª restrição. Clicar em “ Opções” para registros adicionais. Conferir os registros Modelo Linear Não negatividade para x1, x2, x3. Clique em “OK” para sair Clicar em “Resolver” Relatório (Resposta) Solução Ótimo x1=12,5 ; x2=0; x3=0 Mim Z =275 Finalizando Utilizando o Excel – Solver • O Solver é uma ferramenta que nos possibilita resolver problemas particulares da programação linear. • É só entrar com os pa râme t ro s e e l e ajusta o problema, resolve e informa a solução (se ela existir). • Trabalhe no Excel.
Compartilhar