Pesquisa operacional/Introdução à Programação Linear: diferenças entre revisões
[edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
Trocando categorização manual por AutoCat (o indexador da categoria estava incorreto) [ usando AWB ] |
Correção de typos e formatação geral, typos fixed: analizar → analisar (2), anti-a → antia utilizando AWB |
||
Linha 27:
O desenvolvimento de técnicas algébricas para se lidar com inequações lineares é algo bastante antigo. Durante o século XVIII, o matemático e físico Jean-Baptiste Joseph Fourier desenvolveu vários métodos inovadores para se resolver sistemas de ineqüações. Um dos principais algoritmos desenvolvido por Fourier foi o Método de Eliminação de Fourier–Motzkin.
Durante a Segunda Guerra Mundial, novas tecnologias bélicas levaram à criação de grupos acadêmicos com o objetivo de resolver problemas como o uso eficiente de radares, canhões
Também no ano de 1947, o matemático George Dantzig desenvolveu o '''Algoritmo Simplex''', a maneira mais eficiente conhecida de se resolver modelos de Programação Linear. No mesmo ano, John von Neumann desenvolveu a teoria da dualidade e Leonid Kantorovich foi a primeira pessoa a aplicar a Programação Linear à Economia.
Linha 34:
Em 1984, surge mais um método de se resolver problemas de pesquisa operacional: o Algoritmo do Ponto Interior, criado por Narendra Karmarkar. Assim como o Algoritmo Elipsóide, ele era polinomial. A diferença é que ele era bem mais rápido e conseguia competir com o Algoritmo Simplex.
==A Criação de Modelos==
Linha 70 ⟶ 69:
Máx <math>Z = 6M + 8C</math> (Função-Objetivo)
Agora precisamos
<math>30M + 20C \leq 310</math> (Restrição 1)
Linha 86 ⟶ 85:
==Solução Gráfica==
Muito bem! Já sabemos como criar os modelos de Programação Linear. Mas... Como podemos resolvê-los? Como usar todos aqueles algoritmos comentados na seção sobre a história da Programação Linear? Bem, vamos com calma. Vamos ver primeiro uma das formas mais simples de se resolver este problema (embora não seja computacionalmente eficiente). Vamos fazer um gráfico
[[Imagem:
As linhas mais finas representam o eixo X e Y, os quais representam respectivamente o número de mesas (M) e cadeiras (C). Todos os pontos dentro ou abaixo àquela reta grossa mais inclinada verticalmente representam pontos que satisfazem a Restrição 2. Todos os pontos deitro ou abaixo àquela reta grossa inclinada mais horizontalmente satisfazem a Restrição 1. Pontos à direita da reta Y e àcima do eixo X satisfazem a exigência de que não podemos fabricar um número negativo de objetos. Quanto mais restrições um ponto no gráfico acima satisfaz, mais escuro ele aparece. A única região onde todas as restrições são satisfeitas é aquele triângulo escuro localizado próximo ao centro do gráfico. Os vértices do triângulo são os pontos (0,0), (0,10) e (5,0).
Linha 130 ⟶ 129:
O gráfico do Domínio é:
[[Imagem:
O polígono mais escuro que representa os pontos que atendem à todas as restrições possui como vértices os pontos (0,0), (3,0), (3,3) e (1,4). O lucro em (0,0) é 0$. Em (3,0) é 3$. Em (3,3) é 9$. Em (1,4) é 9$. Neste exemplo, não existe apenas um único ponto que representa o máximo da função - existem infinitos pontos. Todos aqueles que pertencem ao Domínio e estão na reta que liga (3,3) e (1,4) são o máximo da função e representam a quantidade ideal de produção de pastéis e cachorros-quentes para o vendedor ambulante. Como o vendedor ambulante não pode fazer um número fracionário de pastéis e cachorros, quentes, a resposta é: 3 pastéis e 3 cachorros-quentes ou então 1 pastel e 4 cachorros-quente.
----
'''2.''' Temos que resolver o modelo:
Linha 149 ⟶ 146:
Perceba que não é possível resolver este modelo. Não existe nenhuma informação que limite superiormente o número de bombardeiros que temos disponíveis. Logo, podemos simplesmente dizer que o melhor é atacar com infinitos bombardeiros. Isso é um absurdo. É uma solução inconcebível. Modelos com solução infinita costumam ocorrer quando algum tipo de restrição é omitida do modelo.
----
'''3.''' Isso acrescenta uma nova restrição ao modelo:
Linha 159 ⟶ 154:
Agora sim podemos resolver o modelo. Tente desenhar o gráfico do Domínio desta função-objetivo. Ele gera um triângulo com três vértices. A resposta é que devemos enviar 4 tanques e 5 bombardeiros para que causemos em média 330 baixas no inimigo.
<!-- CATGORIAS -->
|