13.6: Soluciones Integer de Problemas de Programación Lineal
- Page ID
- 118265
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
Un problema de programación lineal es un problema de optimización que se puede afirmar de la siguiente forma: Encontrar el valor máximo de una función lineal
\(c_1x_1+c_2x_2+c_3x_3+ \cdot \cdot \cdot +c_nx_n\)
sujeto a\(m\) restricciones\(C_1\),\(C_2\),...\(C_m\), donde cada restricción\(C_i\) es una ecuación lineal de la forma:
\(C_i\):\(a_{i1}x_1+a_{i2}x_2+a_{i3}x_3+ \cdot \cdot \cdot +a_{in}x_n=b_i\)
donde todos los coeficientes y constantes son números reales.
Si bien el tema general de la programación lineal es demasiado amplio para este curso, seríamos despreciables si no señaláramos que:
- Los problemas de programación lineal son una clase muy importante de problemas de optimización y tienen muchas aplicaciones en ingeniería, ciencia y entornos industriales.
- Existen algoritmos relativamente eficientes para encontrar soluciones a problemas de programación lineal.
- Un problema de programación lineal planteado con coeficientes racionales y constantes tiene una solución óptima con valores racionales, si tiene una solución óptima.
- Un problema de programación lineal planteado con coeficientes enteros y constantes no necesita tener una solución óptima con valores enteros, incluso cuando tiene una solución óptima con valores racionales.
- Un tema muy importante en la investigación de operaciones es determinar cuándo un problema de programación lineal planteado en enteros tiene una solución óptima con valores enteros. Este es un problema sutil y a menudo muy difícil.
- El problema de encontrar un flujo máximo en una red es un caso especial de un problema de programación lineal.
- Un problema de flujo de red en el que todas las capacidades son números enteros tiene un flujo máximo en el que el flujo en cada borde es un entero. ¡El algoritmo de etiquetado Ford-Fulkerson lo garantiza!
- En general, los algoritmos de programación lineal no se utilizan en las redes. En cambio, algoritmos de propósito especial, como Ford-Fulkerson, han demostrado ser más eficientes en la práctica.