Modelo de Programação linear Inteira

AGRADECIMENTO

Este trabalho não teria sido possível sem a ajuda de alguns intervenientes os quais agradecemos sinceramente. Em primeiro lugar agradecemos a Deus pai todo-poderoso por nos ter dado a vida, saúde, força e vontade. Aos Professores pelos conhecimentos transmitidos.

A todos os nossos amigos e colegas por todo o apoio e incentivo que transmitem não só no decorrer deste trabalho mas também ao longo desse percurso académico. Aos nossos pais e irmãos por toda a ajuda e apoio que de uma forma ou de outra contribuíram na realização deste trabalho. A todos o nosso muito OBRIGADOǃ…

DEDICATORIA

[pic 1]

ÍNDICE

Agradecimento.................................................................................................................................1

Dedicatória.......................................................................................................................................2

Introdução........................................................................................................................................4

Modelo de programação inteira ......................................................................................................5

Passos básicos para resolução de programação linear.....................................................................6

Considerações matemáticas.............................................................................................................7

 Características dos modelos de programação linear.......................................................................8

Modelo de programação linear mista...............................................................................................9

Características da programação linear inteira mista......................................................................10

Modelo de programação inteira binário ........................................................................................12

Implicações, situações práticas .....................................................................................................12

Conclusão.......................................................................................................................................15

Referência bibliografica.................................................................................................................16

INTRODUÇÃO

Este trabalho inseri-se na disciplina de modelo de decisão. Abordaremos de um tema bastente pertinente que é “ a programação linear inteira”, A programação inteira surge devido a necessidade da modelagem dos problemas através de variáveis inteiras (discretas), não contínuas.

O problema geral de programação linear inteira é utilizado para otimizar (maximizar ou minimizar) uma função linear de variáveis, chamada de "função objetivo", sujeita a uma série de equações ou inequações lineares, chamadas restrições.

modelo de programação inteira é um  Problema de Programação  linear no qual algumas ou todas as variáveis do problema pertencem ao conjunto dos números inteiros. Quando todas as variáveis são inteira o modelo é denominado programação inteira pura; caso contrário, é denominado programação inteira mista.

Razão pela qual falaremos de modo resumido e com unanimidade em função a nossa pesquisa.

MODELO DE PROGRAMAÇÃO INTEIRA

Programação Linear (PL) consiste no problema de minimização de uma função de custos linear sujeita a restrições, também lineares, de igualdade ou desigualdade (BERTSIMAS; TSITSIKLIS, 1997).

O substantivo programação não se refere a softwares de computadores, e é usado aqui com o sentido de planejamento, ou seja, a programação linear envolve o planejamento de atividades de modo a se conseguir o melhor resultado possível da função objetivo (HILLIER; LIEBERMAN, 2013).

Um programa linear pode ser dividido em dois componentes básicos: a função objetivo e um conjunto de restrições. Na forma canônica de um programa linear todas as restrições são de desigualdade com ≤ e a função objetivo é sempre de maximização. Um exemplo de um problema de programação linear na forma canônica é mostrada nas equações em:

  onde  são vetores em   é um vetor em  e uma matriz em .[pic 2][pic 3][pic 4][pic 5][pic 6][pic 7]

(1.)

[pic 8]

[pic 9]

[pic 10]

[pic 11]

O algoritmo Simplex é amplamente utilizado para resolver programas lineares. Esse algoritmo otimiza a função objetivo melhorando o resultado ao mover a solução pelos vértices do problema (PAPADIMITRIOU; STEIGLITZ, 2013). Como a função objetivo de um PL é linear, se o conjunto de soluções ótima não é vazio, então ele contém pelo menos um vértice. Um modelo simples de programação linear pode ser resolvido por meio da avaliação da sua forma gráfica, checando-se os valores dos vértices.

Exemplo de um modelo com apenas duas variáveis.

Max          [pic 12]

Sujeito a

[pic 13]

[pic 14]

[pic 15]

[pic 16]

(1.1)

PASSOS BÁSICOS PARA RESOLUÇÃO DE PROGRAMAÇÃO LINEAR

• Deve ser definido o objetivo básico do problema, ou seja, a otimização a ser alcançada. Por exemplo, maximização de lucros, ou de desempenhos, ou de bem-estar social; minimização de custos, de perdas, de tempo. Tal objetivo será representado por uma função objetivo, a ser maximizada ou minimizada.

• Para que esta função objetivo seja matematicamente especificada, devem ser definidas as variáveis de decisão envolvidas. Normalmente, assume-se que todas estas variáveis possam assumir somente valores inteiros.

• Estas variáveis normalmente estão sujeitas a uma série de restrições, normalmente representadas por inequações.

Todas essas expressões, entre tanto, devem estar de acordo com a hipótese principal da programação linear, ou seja, todas as relações entre as variáveis devem ser lineares. Isto implica proporcionalidade das quantidades envolvidas. Esta característica de linearidade pode ser interessante no tocante à simplificação da estrutura matemática envolvida, mas prejudicial na representação de fenômenos não lineares (por exemplo, funções tipicamente quadráticas).