“Bicentenário da Independência: 200 anos de ciência, tecnologia e inovação no Brasil e 96 anos de contribuição da UFV”.
8 a 10 de novembro de 2022
Trabalho 16705
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Álgebra |
| Setor | Instituto de Ciências Exatas e Tecnológicas - Campus Rio Paranaíba |
| Bolsa | PIBIC/CNPq |
| Conclusão de bolsa | Sim |
| Apoio financeiro | CNPq |
| Primeiro autor | Lídio Antônio de Oliveira Junior |
| Orientador | VAGNER RODRIGUES DE BESSA |
| Título | A Álgebra Linear como ferramenta para Programação Linear e o Método Simplex |
| Resumo | Os fundamentos teóricos deste trabalho foram construídos a partir de uma revisão bibliográfica das ferramentas teóricas da Álgebra Linear e da Topologia dos Espaços Métricos, a destacar: o conceito de métrica de um espaço; ponto de aderência; espaços métricos fechados e abertos; o conceito conjunto compacto; dentre outros. Diante disso foi possível compreender a demonstração de alguns teoremas relacionados a área da Programação Linear e resolver problemas de otimização (maximização e minimização) por intermédio do Método Simplex. Um problema de programação linear (PPL) consiste em minimizar uma função (função objetiva) Q(x) = \sum_{j=1}^{n}c_jx_j onde os coeficientes c_j são constantes pertencentes ao conjunto dos números reais e x (x_1,x_2,...,x_n) são as variáveis da função Q, com n>=1. Essa função está sujeita a um conjunto de m restrições da forma a_{i1}x_1+a_{i2}x_2+...a_{in}x_n<=b_i (i = 1, 2, ..., m) , onde cada a_{ij} representa uma constante pertencente ao conjunto dos números reais (modelo com m restrições). As restrições determinam um conjunto de soluções viáveis que é um conjunto limitado e convexo e as soluções estão no(s) vértice(s) desse conjunto. A solução viável que otimiza (maximiza ou minimiza) a função objetiva é a chamada solução ótima. O método que usamos, em nosso trabalho, para encontrar uma solução ótima de um PPL foi o método simplex, que consiste na determinação de soluções viáveis básicas. O algoritmo do método simplex consiste basicamente de 5 etapas: 1. Construção do quadro inicial onde as variáveis são escritas como o título das colunas e as restrições do modelo são inseridas nas primeiras linhas seguidas pela linha objetiva; 2. Se a linha objetiva não tem elementos negativos nas colunas correspondentes às variáveis, então a solução indicada é ótima, podendo encerrar os cálculos, caso contrário seguimos para próximo passo; 3. Escolha de uma coluna do pivô; 4. Escolha de uma linha do pivô. Se nenhum dos elementos na coluna do pivô acima da linha objetiva for positivo, o problema não tem solução ótima finita encerrando-se os cálculos, caso contrário seguimos para o próximo passo; 5. Realização de operações de pivoteamento para construir um novo quadro e retoma-se à etapa 2. Geometricamente, o método Simplex nos permite ir de um vértice até um outro adjacente, de tal maneira que o valor da função objetivo aumente (max.) ou diminua (min.) à medida que nos movemos de um vértice a outro até que se obtenha uma solução ótima ou que se descubra que o problema não possui tal solução ótima. Em suma, a programação linear tem aplicabilidade em diversas áreas visto que, em quase todas estamos interessados em tomar decisões que maximizem ou minimizem alguma função linear. Desta forma a compreensão do método pode nos auxiliar na tomada de decisões que resultam principalmente em uma grande economia de dinheiro e/ou recursos. |
| Palavras-chave | Programação Linear, Simplex, Otimização |
| Forma de apresentação..... | Painel |
| Link para apresentação | Painel |
|---|