PROGRAMAÇÃO LINEAR

WebQuest WebQuest da disciplina Programação Linear no curso de Análise e Desenvolvimento de Sistemas do 5º semestre da FATEC de Carapicuíba, proposto pelo professor Luciano Condori como uma atividade complementar. Introdução Este WebQuest tem como principio falar sobre a Historia da Programação Linear, a Aplicação dos Problemas Lineares e os matemáticos que estão ligados a Programação Linear, abordando os assuntos da evolução do conceitos ligados a Programação Linear, a relação do conteúdo visto na criação do website com a disciplina, os principais matemáticos que contribuíram para o desenvolvimento da Programação Linear e a forma da qual os trabalhos deles contribuíram com esse desenvolvimento. Autor Nome: Artthur Maximo Dias RA: 1430481731008 Instituição: Fatec Carapicuíba Curso: Análise e Desenvolvimento de Sistemas Professor: Luciano Condori Referencias: https://matematicabasica.net/matrizes/ http://www.phpsimplex.com/pt/teoria_metodo_grafico.htm...

Vídeo Aulas Matrizes https://www.youtube.com/embed/gE_1LTPwhV0 https://www.youtube.com/embed/pNWx2LE9meQ Método Gráfico https://www.youtube.com/embed/B518pKT7xks https://www.youtube.com/embed/4hZKBvMTOLI Método Simplex https://www.youtube.com/embed/OD0BVZbDieY https://www.youtube.com/embed/uendv1Khpcw Dualidade https://www.youtube.com/embed/z6-kdJoSwpg https://www.youtube.com/embed/tgPe1XnK9aU

Uma dos conceitos mais importantes em programação linear é o de dualidade. Qualquer problema de PL tem associado um outro problema de PL, chamado o Dual. Neste contexto, o problema original denomina-se por Primal. Um dos principais papéis da teoria da dualidade é a interpretação e implementação da análise de sensibilidade, que é uma parte muito importante de um estudo de PL. Exemplo: Considere o problema clássico da dieta: (problema primal): Quer-se consumir quantidades de determinados alimentos de tal forma a satisfazer as necessidades mínimas de nutrientes exigidas a um custo mínimo dispendido, problema este ilustrado pelo quadro seguinte.                                    alimentos                                      necessidades mín. de         ...

Exemplo: método Simplex Solução através do método Simplex do Problema seguinte: Maximizar Z = f(x,y) = 3x + 2y sujeita às restrições: 2x + y ≤ 18                                   2x + 3y ≤ 42                                   3x + y ≤ 24                                   x ≥ 0 , y ≥ 0 Consideram-se as seguintes fases: Realizar uma mudança de variáveis e normalizar o sinal dos termos independentes. Realiza-se uma mudança na nomenclatura das variáveis. Estabelecendo a seguinte correspondência: x passa a ser X1 y passa a ser X2 Como os termos independentes de todas as restrições são positivos não é necessário fazer nada. Caso contrário, se deverá multiplicar por "-1" ambos os lados da inequação (considerando que est...

O método Simplex é um processo iterativo que permite melhorar a solução da função objetivo em cada etapa. O processo finaliza quando não é possível continuar melhorando este valor, ou seja, quando se obtenha a solução ótima (o maior ou menor valor possível, segundo o caso, para que todas as restrições sejam satisfeitas). Com base no valor da função objetivo, em um ponto qualquer, o procedimento consiste em procurar outro ponto que melhore o valor anterior. Como se pode ver no método Gráfico, tais pontos são os vértices do polígono (ou poliedro ou polícoro, se o número de variáveis é maior do que 2) e que faz parte da região determinada pelas restrições a que está sujeito o problema (chamada de região viável). A pesquisa é realizada por meio de deslocamentos pelas arestas do polígono, a partir do vértice atual até um adjacente que melhore o valor da função objetivo. Sempre que exista região viável, e como seu número de vértices e de arestas é finito, será possível encontrar a solução....

Solução através do método gráfico o seguinte problema: Maximizar Z = f(x,y) = 3x + 2y sujeita às restrições: 2x + y ≤ 18   2x + 3y ≤ 42   3x + y ≤ 24   x ≥ 0 , y ≥ 0 1.Inicialmente, o sistema de coordenadas da associação de um eixo com variável "X" e o outro o "Y" é desenhado (geralmente associa-se "x" em relação ao eixo horizontal e o "y" ao vertical), como pode ser visto na figura. 2.Nestes eixos, marca-se uma escala numérica apropriada aos valores que podem assumir as variáveis conforme as restrições do problema. Para isto, em cada restrição anulam-se todas as variáveis, exceto aquelas que correspondem a um eixo concreto, estabelecendo o valor adequado para este eixo. Este processo é repetido para cada um dos eixos. 3.As restrições são representadas a seguir. Primeiramente, desenha-se a reta que é obtida ao considerar a restrição como uma igualdade. Ela é representada como o segmento que une A com B e região que delimita esta ...

Teoria do método Gráfico Interpretação gráfica do Método Simplex O método Gráfico ou método Geométrico permite a resolução de problemas simples de programação linear de forma intuitiva e visual. Este método está limitado a problemas com duas ou três variáveis de decisão, tendo em vista que não é possível ilustrar graficamente más de 3 dimensões. Embora na realidade raramente surgem problemas com somente duas ou três variáveis de decisão, no entanto, é muito útil esta metodologia de resolução. Para mostrar graficamente as situações possíveis, tais como a existência de uma única solução ótima, soluções ótimas alternativas, a não existência de solução e a limitação, constitui uma ajuda visual para interpretar e entender o algoritmo do método Simplex (muito mais sofisticado e abstrato) e os conceitos que o cercam.

Matrizes são organizações de informações numéricas em uma tabela retangular formada por linhas e colunas. Essa organização em uma tabela facilita que se possa efetuar vários cálculos simultâneos com as informações contidas na matriz. Definição de matrizes Toda matriz tem o formato m x n (leia-se: m por n, com n e m ∈ N*), onde m é o número de linhas e n o número de colunas. Representação de matrizes Existem diversas maneiras de representarmos matrizes, veja quais são: Colchetes: [ ] Parênteses: ( ) Barras Simples: | | Barras Duplas: || || Essas são as representações mais comuns que encontramos na literatura. Exemplos: Elementos de uma matriz Seja a matriz genérica Amxn, isto é, m representa as linas e n o número de colunas. Então, temos: Elementos de uma matriz Seja a matriz genérica Amxn, isto é, m representa as linas e n o número de colunas. Então, temos: Dessa forma, os elementos da matriz A são indicados por aij, onde o i representa o índice da linha e j...

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 antiaéreos, escoltas navais, etc. O objetivo era sempre reduzir custos militares e buscar maximizar as baixas inimigas. Para resolver estes problemas, a Programação Linear mostrou-se extremamente útil. Os grupos acadêmicos que a utilizavam eram sempre mantidos secretos até o ano de 1947, após o término da guerra. Foi quando a Programação Linear passou a ser muito usada em empresas com o objetivo de reduzir despesas e maximizar lucros. Também no ano de ...

O algoritmo simplex resolve problemas de PL construindo uma solução admissível no vértice do poliedro, e então percorre os vértices do poliedro que sucessivamente possuem valores mais altos da função objectivo até encontrar o máximo. Embora este algoritmo seja bastante eficiente na prática, e seja garantido de encontrar um óptimo global se certas condições para se evitar ciclos forem assumidas, ele é fraco no pior-caso: é possível construir um problema de programação linear prático para o qual o método simplex realiza uma quantidade exponencial de passos em relação ao tamanho do problema. Na verdade, por algum tempo não se soube se problemas de programação linear eram NP-completos ou tinham solução em tempo polinomial. O primeiro algoritmo de programação linear em tempo polinomial no pior caso foi proposto por Leonid Khachiyan em 1979. Foi baseado no [método do elipsóide] da nonlinear optimization de Naum Shor, que é uma generalização do método da elipsóide da [optimização convexa] d...

Geometricamente, as restrições lineares definem um poliedro convexo, que é chamado de conjunto dos pontos viáveis. Uma vez que a função objectivo é também linear, todo ótimo local é automaticamente um ótimo global. A função objetivo ser linear também implica que uma solução ótima pode apenas ocorrer em um ponto da fronteira do conjunto de pontos viáveis. Existem duas situações nas quais uma solução ótima não pode ser encontrada. Primeiro, se as restrições se contradizem (por exemplo, x ≥ 2 e x ≤ 1) logo, a região factível é vazia e não pode haver solução ótima, já que não pode haver solução nenhuma. Neste caso, o PL é dito inviável. Alternativamente, o poliedro pode ser ilimitado na direção da função objetivo (por exemplo: maximizar x1 + 3 x2 sujeito a x1 ≥ 0, x2 ≥ 0, x1 + x2 ≥ 10), neste caso não existe solução ótima uma vez que soluções arbitrariamente grandes da função objetivo podem ser construídas, e o problema é dito ilimitado. Fora estas duas condições patológicas (que são...

Suponha que uma empresa produza quatro modelos diferentes de brinquedos. Cada um deles gera uma quantidade de lucro diferente ao ser vendida. O brinquedo 1 gera $10 de lucro, o 2 gera $8, o 3 gera $9 e o 4 gera $7. A função que determina o lucro da empresa é: {\displaystyle Z=10x_{1}+8x_{2}+9x_{3}+7x_{4}} Assumindo que as variáveis são a quantidade de cada brinquedo que é vendida. Esta é uma  função linear , pois cada um dos termos da equação que a forma é uma constante ou um produto entre uma constante e um valor variável. Suponha agora que nós estamos interessados em descobrir qual é o maior lucro possível para esta empresa assumindo que o número máximo de vendas do brinquedo 1 é 100, do brinquedo 2 é 60, do brinquedo 3 é 40 e do brinquedo 4 é 70. Podemos então expressar este problema da seguinte forma: Máx  {\displaystyle Z=10x_{1}+8x_{2}+9x_{3}+7x_{4}}  (Função Objetivo) {\displaystyle 1x_{1}+0x_{2}+0x_{3}+0x_{4}\leq 100}  (Restrição 1) {\displaysty...

Em matemática, problemas de Programação Linear (PL) são problemas de optimização nos quais a função objetivo e as restrições são todas lineares. Programação Linear é uma importante área da optimização por várias razões. Muitos problemas práticos em pesquisa operacional podem ser expressos como problemas de programação linear. Certos casos especiais dessa natureza, tais como problemas de network flow e problemas de multicommodity flow são considerados importantes o suficiente para que se tenha gerado muita pesquisa em algoritmos especializados para suas soluções. Vários algoritmos para outros tipos de problemas de optimização funcionam resolvendo problemas de PL como sub-problemas. Historicamente, ideias da programação linear inspiraram muitos dos conceitos centrais de teoria da optimização, tais como dualidade, decomposição, e a importância da convexidade e suas generalizações.