Investigación operativa

A investigación operativa^[1] (IO) é unha rama interdisciplinar da matemática aplicada que fai uso de modelos matemáticos, estatísticos e de algoritmos na axuda á toma de decisión. Emprégase sobre todo para analizar sistemas complexos do mundo real, tipicamente co obxectivo de mellorar ou optimizar a actuación.

A IO non é unha ciencia en si, mais si a aplicación da ciencia á solución de problemas de xerencia e administrativos, e céntrase no desempeño de sistemas organizados como un todo, en vez das súas partes tomadas separadamente.^[2].

Historia

A investigación operativa naceu no teatro de operacións da segunda guerra mundial, cando os aliados se viran confrontados con problemas (de natureza loxística e de táctica e estratexia militar) de gran dimensión e complexidade. Creáronse grupos multidisciplinares de científicos nos que se incluían matemáticos, físicos e enxeñeiros, ademais doutros orixinarios das ciencias sociais para apoiar os comandos operativos na resolución deses problemas. Aplicaron o método científico aos problemas que lles foron colocados e crearon modelos matemáticos, apoiados en datos e feitos, que lles permitisen entender os problemas en estudo e ensaiar e avaliar o resultado hipotético de estratexias ou decisións alternativas.

Co fin do conflito e o éxito obtido, os grupos de científicos trasladaron a nova metodoloxía na abordaxe de problemas para as empresas, confrontadas con problemas de decisións de gran complexidade derivados do crecemento económico que se seguiu. Coa evolución observada na informática creáronse condicións de concreción algorítmica e velocidade de procesamento adaptados á imaxinación dos profesionais da investigación operativa, e a microinformática permitiu relacionar directamente os sistemas de información cos decisores.

Fases

A resolución dun problema, polo método da investigación operativa, segue as seguintes fases:^[3]

Definición do problema. Nesta fase defínense os obxectivos que se queren lograr, as variables envolvidas no problema, e as principais restricións.
Construción do modelo matemático. A escolla do modelo depende do tipo de problema que se vai resolver. Os modelos matemáticos máis utilizados, son os de programación linear.
Solución do modelo. A partir do modelo matemático adoptado encóntrase a solución do problema.
Validación do modelo. O modelo é examinado para ver se a solución obtida coincide co problema estudado.
Posta en marcha da solución. Nesta fase, a solución é convertida en regras prácticas para a solución do problema.

Principais modelos de IO

Os analistas de IO empregan varios tipos de modelos. Os principais preséntanse a seguir.

Programación linear

A programación linear consiste en métodos para resolver problemas de optimización dunha función obxectivo linear, suxeita a restricións (desigualdades) tamén lineares.

Exemplo:

maximize $S_{1}x_{1}+S_{2}x_{2}$		(maximizar o beneficio - esta é a "función obxectivo")
sujeito a	$x_{1}+x_{2}\leq A$	(límite da área total)
	$F_{1}x_{1}+F_{2}x_{2}\leq F$	(límite do fertilizante)
	$P_{1}x_{1}+P_{2}x_{2}\leq P$	(límite do insecticida)
	$x_{1}\geq 0,\,x_{2}\geq 0$	(non se pode sementar unha área negativa)

Programación enteira

A programación enteira é un modelo de programación linear no cal as variables de decisión son enteiras.

Ao contrario da PL, que pode encontrar a solución óptima nun tempo razoable, normalmente os problemas de Programación Enteira son considerados NP-difícil. Se as variables foren binarias, ou sexa, asumiren soamente os valores 0 (cero) ou 1, temos un caso especial da PE, que tamén é NP-difícil.

Modelos de optimización en redes

Empréganse representacións de redes para problemas de diversas áreas, tales como redes de trasporte, de comunicación, de enerxía, de produción, de distribución, de planificación de proxectos, de xestión de recursos, de planificación financeira etc.

Unha rede é formalmente representada por un grafo $G=(N,A)$ , onde $N$ é o conxunto de nós (vértices) e $A$ é o conxunto de arcos, tales que cada arco conecta dous nós distinguidos. Cando se fai necesario definir sentido de cada arco, a rede é representada por digrafo (grafo orientado).

Exemplos de problemas de optimización en redes:

Programación dinámica

A programación dinámica, como o método de dividir e conquistar, resolve problemas combinando as solucións para subproblemas. Os algoritmos de división e conquista parten o problema en subproblemas, resolven os subproblemas de forma recursiva, e axiña, combinan súas solucións para resolver o problema orixinal. En contrapartida, a programación dinámica aplícase cando os subproblemas se sobrepoñen, isto é, cando os subproblemas comparten subproblemas. Neste contexto, un algoritmo de división e conquista fai máis traballo do que é preciso, resolvendo repetidamente os subproblemas comúns.

Un algoritmo de programación dinámica resolve cada subproblema só unha vez e, axiña, salva a súa resposta nunha táboa, evitando así o esforzo de recalcular a resposta cada vez que resolve cada subproblema.^[4]

Programación non linear

A programación non linear aplícase cando o modelo de programación matemática ten función obxectivo e/ou restricións non lineares.

Sexan n, m, p enteiros positivos. Sexa X un subconxunto de ℝⁿ. Sexan f, g_i, e h_j funcións reais en X.

Un problema de minimización non linear é un problema de optimización na forma:

{\begin{aligned}{\text{Min ou Max }}&f(x)\\{\text{sujeito a}}&g_{i}(x)\leq 0{\text{ para cada }}i\in \{1,\dotsc ,m\}\\&h_{j}(x)=0{\text{ para cada }}j\in \{1,\dotsc ,p\}\\&x\in X.\end{aligned}}

Os métodos para resolución de problemas de programación non linear poden ser divididos en dous grupos:

Modelos sen restricións.
Modelos con restricións.

Simulación discreta

A simulación de eventos discretos^[5] (SED) modela a operación dun sistema como unha secuencia de eventos discretos no tempo. Cada evento ocorre nun determinado instante de tempo e marca unha mudanza de estado no sistema. Entre eventos consecutivos, considérase que o sistema non sofre mudanza ningunha, así, a simulación pode saltar directamente do instante de ocorrencia dun evento para o próximo.

Unha técnica coñecida para execución de simulacións de eventos discretos é o "método das tres fases". Nesta abordaxe, a primeira fase sempre avanza o reloxo para o próximo evento a ocorrer, respectando a orde cronolóxica de eventos (chamados de eventos do tipo A). A segunda fase é a execución de todos os eventos que incondicionalmente ocorren no instante actual (chamados de eventos do tipo B). A terceira fase é a execución de todos os eventos que condicionalmente ocorren no tempo actual (chamados eventos do tipo C).

Simulación de Monte Carlo

Desígnase por método de Monte Carlo (MMC) calquera método dunha clase de métodos estatísticos que se basean en mostraxes aleatorias masivas para obter resultados numéricos, isto é, repetindo sucesivas simulacións un elevado número de veces, para calcular probabilidades heuristicamente, tal como se, de feito, se rexistrasen os resultados reais en xogos de casino (de aí o nome). Este tipo de método é utilizado en simulacións estocásticas con diversas aplicacións en áreas como a física, a matemática e a bioloxía. O método de Monte Carlo ten sido utilizado como forma de obter aproximacións numéricas de funcións complexas nas que non é viable, ou mesmo é imposible, obter unha solución analítica ou, polo menos, determinística.

Teoría de xogos

Os modelos de decisión poden ser considerados como un procedemento de toma de decisión en situacións non competitivas, no sentido de non envolver directamente outras persoas ou organizacións. Os estados ou os escenarios que irán acontecer envolven riscos ou incertezas referentes á previsión do mercado, influencia do clima etc. O tomador de decisión escolle unha das alternativas de decisión existentes. O decisor ten coñecemento dos escenarios posibles e dos riscos embutidos neses escenarios. Unha situación competitiva ou de conflito acontece cando un estado ou escenario ocorre causado pola decisión tomada por outro participante.

A análise dos problemas de decisión en situacións nas cales existen conflitos pode ser efectuada con uso da teoría de xogos, formulada por Von Neumann e Morgenstern en 1935.

Notas

↑ Departamento de Estatística e Investigación Operativa (Facultade de Matemáticas da USC)
↑ Eilon, Samuel. "Operations research (industrial engineering)". History – Britannica Online Encyclopedia. Britannica.com. Consultado o 8 de setembro de 2016.
↑ Andrade, Eduardo Leopoldino de, "Introdução à pesquisa operacional: métodos e modelos para análise de decisões, 4 Ed.", Rio de Janeiro: LTC, 2009. 202p.
↑ Cormen, Thomas H. (2009). Introduction to algorithms. Massachussetts: MIT Press. pp. 359.
↑ Hillier, Frederick S.; Lieberman, Gerald J. (2013). Introdução à Pesquisa Operacional. Porto Alegre: McGraw-Hill. pp. 934–945.

Véxase tamén

Bibliografía

HILLIER, Frederick S.; LIEBERMAN, Gerald J. Introdução à Pesquisa Operacional. 9ª Edición. Porto Alegre: McGraw-Hill. 2013. ISBN 9788580551181.

Ligazóns externas

IFORS – International Federation of Operacional Research Societies
EURO – The Association of European Operational Research Societes
APDIO – Asociación Portuguesa de Investigação Operacional
SOBRAPO – Sociedade Brasileira de Pesquisa Operacional

[1] Departamento de Estatística e Investigación Operativa (Facultade de Matemáticas da USC)

[2] Eilon, Samuel. "Operations research (industrial engineering)". History – Britannica Online Encyclopedia. Britannica.com. Consultado o 8 de setembro de 2016.

[3] Andrade, Eduardo Leopoldino de, "Introdução à pesquisa operacional: métodos e modelos para análise de decisões, 4 Ed.", Rio de Janeiro: LTC, 2009. 202p.

[4] Cormen, Thomas H. (2009). Introduction to algorithms. Massachussetts: MIT Press. pp. 359.

[5] Hillier, Frederick S.; Lieberman, Gerald J. (2013). Introdução à Pesquisa Operacional. Porto Alegre: McGraw-Hill. pp. 934–945.

[1]

[2]

[3]

[4]

[5]