Objetivo Do Desafio

O que é programação linear?

A programação linear, no campo da programação matemática, é uma área da pesquisa operacional com vasta aplicação em apoio à decisão. O termo “programação”, tanto linear quanto matemática, não tem a ver diretamente com programação de computadores, ou linguagem de programação. Este termo tem origem em suas aplicações, originalmente desenvolvido para resolver problemas industriais. Assim, o termo “programação” da programação linear está relacionado ao planejamento de recursos escassos visando atender as condições operacionais. Estas, por sua vez, são representadas por equações e funções lineares.

A aplicação da programação linear em apoio à decisão ocorre na condição que se decide para atingir um objetivo. Este, por sua vez, é resultante da alocação ótima dos recursos. Por isso caracterizamos a programação linear como uma técnica de otimização. No problema de otimização em siderurgia, por exemplo, buscamos determinar a alocação ótima dos recursos de produção de forma a atender as limitações de capacidades de cada usina e maximizar o lucro resultante. Tanto a função de maximizar o lucro quanto as restrições de capacidade de cada planta são representados por funções lineares. Neste exemplo, o tomador de decisão pode escolher diversas combinações de alocação de seus produtos, no entanto apenas uma combinação é a mais lucrativa. Esta e a combinação ótima que maximiza o lucro, uma função linear, do problema de programação linear.

Programação linear: equações e funções são lineares

Embora originalmente o tempo “programação” de programação linear não tem a ver diretamente com programação de computadores, os problemas reais não podem ser resolvidos manualmente, dada a dimensão de problemas reais. Com a evolução da tecnologia de hardware e software, os algoritmos de programação linear são implementados em uma linguagem computacional para viabilizar a resolução de problemas reais em menor tempo. A programação linear, dessa forma, teve seu desenvolvimento junto com o desenvolvimento dos computadores, a partir da década de quarenta.

A programação linear é uma das técnicas mais usadas dentre outras grandes áreas da pesquisa operacional, como simulação, teoria de filas, programação dinâmica, teoria dos jogos. O problema de programação linear foi inventado pelo matemático Russo L. Kantorovich em 1939. L. Kantorovich e T. Koopmans ganharam o prêmio Nobel por suas contribuições à teoria de alocação ótima de recursos. No entanto, o algoritmo mais utilizado para resolver problemas de programação linear é o simplex e suas variações (primal simplex, dual simplex, simplex revisado) formalizado por George Dantzig em 1947 enquanto trabalhava no projeto de computação científica de otimização SCOOP (Scientific Computation of Optimal Programs) na RAND (Research and Development) Corporation para a Força Aérea Americana.

Diversas áreas utilizam a programação linear para apoio a decisão. Dentre as áreas de aplicação estão: (i) planejamento logístico de frotas e rotas, (ii) planejamento da produção de longo, médio e curto prazo, (iii) decisão em escolha de mix de produtos em manufatura, (iv) estratégias operacionais em mineração, siderurgia, petroquímicas, agricultura, (v) decisão de localização de facilidade ou instalação de fábricas ou centros de distribuição, (vi) decisão em finanças na escolha da melhor carteira de investimentos, entre outros.

MODELAGEM EM PROGRAMAÇÃO LINEAR

PASSOS BÁSICOS NA OBTENÇÃO DE MODELOS DE P. L.:

1. IDENTIFICAR AS VARIÁVEIS DE DECISÃO, REPRESENTÁ-LAS EM

SIMBOLOGIA ALGÉBRICA.

2. IDENTIFICAR AS RESTRIÇÕES DO PROBLEMA, EXPRESSÁ-LAS COMO

EQUAÇÕES OU INEQUAÇÕES LINEARES EM TERMOS DAS VARIÁVEIS

DE DECISÃO.

3. IDENTIFICAR O OBJETIVO DE INTERESSE NO PROBLEMA,

REPRESENTÁ-LO COMO FUNÇÃO LINEAR EM TERMOS DAS VARIÁVEIS

DE DECISÃO, QUE DEVERÁ SER MAXIMIZADA OU MINIMIZADA.

CONSTRUÇÃO DE MODELOS NÃO É UMA CIÊNCIA, MAS UMA ARTE, PODENDO SER MELHORADA COM A PRÁTICA.

EXEMPLOS A SEREM TRABALHADOS:

• DETERMINAÇÃO DO MIX DE PRODUÇÃO.

• SELEÇÃO DE MÍDIA PARA PROPAGANDA.

• UM PROBLEMA DE TREINAMENTO.

• UMA INDÚSTRIA QUÍMICA.

• UMA OFICINA MECÂNICA.

• DIMENSIONAMENTO DE EQUIPES DE INSPEÇÃO.

MODELAGEM EM PROGRAMAÇÃO LINEAR

DETERMINAÇÃO DO MIX DE PRODUÇÃO

UMA COMPANHIA DESEJA PROGRAMAR A PRODUÇÃO DE UM UTENSÍLIO DE COZINHA QUE REQUER O USO DE DOIS TIPOS DE RECURSOS – MÃO-DE-OBRA E MATERIAL. A COMPANHIA ESTÁ CONSIDERANDO A FABRICAÇÃO DE TRÊS MODELOS E O SEU DEPARTAMENTO DE ENGENHARIA FORNECEU OS DADOS A SEGUIR:

MODELO

A B C

MÃO-DE-OBRA

(HORAS POR UNIDADE)

7

3

6

MATERIAL

(KILOS POR UNIDADE)

4

4

5

LUCRO

($ POR UNIDADE)

4

2

3

O SUPRIMENTO DE MATERIAL É DE 200 KILOS POR DIA. A DISPONIBILIDADE DIÁRIA DE MÃO-DE –OBRA É