Programación Lineal

Categoria:

Matemáticas

Rama de las Matemáticas que se ocupa de la determinación del punto de un poliedro convexo donde alcanza su máximo o mínimo una función lineal. El principal interés de la p.l. es que se pueden describir convenientemente muchos problemas que surgen al intentar emplear más eficazmente un conjunto de medios tales como: capital, materias primas, recursos humanos, etc. La p.l. trata de describir las relaciones mutuas entre las diversas componentes del sistema (económico o de otra índole) a estudiar. Aunque también se puede aplicar a problemas de ciencias físicas y otras ramas de las Matemáticas. El papel clave de los equipos de investigación operativa es determinar cuándo un modelo de tal sistema es aplicable a un problema determinado (v. INVESTIGACIÓN IV).

Hasta 1947, tal actividad no atrajo el interés de los matemáticos, pues no se consideraba importante desde el punto de vista de las aplicaciones. Los antecedentes más remotos quizá sean los de Fourier y La Vallée Poussin, que propusieron métodos cuyo principio era análogo al de la programación lineal. En la URSS, Kantorovich, en 1939, se ocupó de cuestiones análogas y obtuvo resultados parciales, aunque no llegó a una solución general y definitiva. En 1928, J. von Neumann demostró el teorema del minimax (o maximin). En 1944, J. von Neumann y O. Morgenstern publicaron su importante obra sobre teoría de los juegos y comportamiento económico (Theory of Games and Economic Behavior). En 1947, Hurwick, conocido economista asociado a la Cowles Commision, trabajando con Dantzig sobre técnicas para la resolución de problemas de p.l., con su esfuerzo y con algunas sugerencias de Koopman, obtuvo el método del símplex. Su publicación se retrasó hasta 1951. La aparición de los ordenadores electrónicos fue decisiva para ampliar y extender la p. L, es decir, los cálculos numéricos exigidos por el método del símplex. Hoy día continúa siendo el método de resolución de programas lineales. Los no lineales continúan en estado de investigación y, hasta el día de hoy, no se ha encontrado un método general para resolverlos (sólo se conocen procedimientos eficientes de cálculo para casos especiales).

Teoría general. Un problema típico de p. l. consiste en maximizar

z = cixi(1)

cuando

xj (j=1, ..., n)

satisfacen las condicionesal,

a 11 x1 + ... +a1n x n <= b1

.......................................

.......................................

a m1 x1 + ... +amn x n <= bm(2)

xj => 0(3)

Las aij, cj y bi son constantes;x1, ... xn , son variables. A veces, el problema consiste en minimizar en vez de maximizar; en ocasiones, no se requiere que todas las variables sean no negativas; algunas de las inecuaciones

ai1x1 +... + ainxn<= bi

pueden presentarse en la forma

ai1x1 + ... + ainxn => bi(i= 1, ... , m)

o ser ecuaciones.

Las inecuaciones lineales, que satisfacen las variables, corresponden algebraicamente al hecho de que el punto variable

x = (x1, ... , xn)

recorre un poliedro convexo. Los fundamentos teóricos más importantes son los siguientes.

Si la funciónncixi=1no puede tomar valores arbitrariamente grandes para puntosx=(xl, ..., xn)del poliedro convexo, el máximo se alcanza en un vértice del poliedro.

Si hay un máximo en el problema enunciado, existe un mínimo en el problema dual consistente en minimizar

~ biyicuandoyi => 0

a11 y1+ ... +am1 ym => c1

...................................

...................................

a1m y1+ ... +amn ym => cn

Además, este máximo y este mínimo tienen el mismo valor numérico. Este teorema de dualidad es esencialmente equivalente al teorema de minimax. Tanto el teorema de dualidad como el de minimax son paráfrasis algebraicas del hecha de que, si un punto no pertenece a un poliedro convexo, puede encontrarse un hiperplano que deje a un lado el punto y al otro el poliedro.

Métodos de cálculo. El método más empleado para la resolución de problemas de p. l. es el símplex. Geométricamente, es un proceso que permite moverse de un vértice del poliedro convexo a otro contiguo, consiguiendo en cada movimiento un valor más alto para

c1 x1 + ... +cn xn

hasta alcanzar el vértice que da el máximo valor. Algebraicamente, los cálculos son similares a los del procedimiento de eliminación empleado en la resolución de los sistemas de ecuaciones lineales.

Formulación de un modelo de la programación lineal. 1) Se supone el sistema descomponible en un número determinado de funciones elementales, llamadas actividades. Una actividad es un sistema cualquiera de naturaleza desconocida en el que hay un flujo medible de entradas tales como hombres, materiales, etc., e, igualmente, un flujo de salidas tales como fabricados, máquinas, personas entrenadas, etc. Al programador únicamente le interesa las cantidades de flujo que entran y salen de la actividad. Las diferentes clases de los objetos que fluyen se llaman artículos. La cantidad de cada actividad se llama nivel. 2) Proporcionalidad: las cantidades de los diversos artículos que entran o salen de una actividad son proporcionales al nivel de éstas. 3) No negatividad: carecen de sentido las actividades negativas. 4) Aditividad: las actividades son completas, es decir, para todo artículo la cantidad total exigida por el sistema es igual a la suma de las cantidades que entran en las diversas actividades menos las cantidades que salen de ellas.

Función objetivo lineal (función lineal de las actividades). Cada artículo se considera como valioso, ya que la cantidad total producida mide lo que hay que pagar por él. La aportación de cada actividad al pago total es la cantidad del artículo valioso que entra o sale de ella. Si el objetivo es maximizar beneficios, las actividades que exigen dinero son negativas; y las que lo producen, positivas. Se trata, por tanto, de obtener los valores de los niveles de las actividades que son no negativas y tales que los flujos de cada artículo para estos niveles de actividad cumplan las ecuaciones de balance y hagan que el valor del pago sea máximo.

Esquema del modelo: 1) Definir el conjunto de actividades y elegir una unidad para cada actividad que permita medir su nivel. 2) Definir el conjunto de artículos, clases de objetos consumidos o producidos por las actividades y elegir una unidad de medida para cada artículo. Escoger un artículo de forma que la cantidad producida por el sistema en su totalidad mida el coste del sistema total (de forma tal que una media negativa es el beneficio). 3) Hallar la cantidad de cada artículo consumida u obtenida por la operación de cada actividad a nivel uno. 4) Obtener las entradas o salidas de todos los artículos entre el sistema y el exterior. 5) Hallar las ecuaciones de balance material que significan que la suma algebraica de las entradas o salidas de cada artículo en cada actividad es igual a la salida externa del artículo. 6) Representar los niveles no negativos de cada actividad

x1, x2, ...., xn

para todas las actividades. El modelo construido representa las relaciones matemáticas de la totalidad de los programas factibles del sistema.

El problema de la programación lineal. Consiste en hallar los niveles de todas las actividades no negativas del sistema, que cumplen las ecuaciones de balance material y que minimizan el coste total.

Esencialmente, se puede reducir a optimizar una función lineal (función objetivo) del tipo (1) donde las

cj(j = 1, 2, . ., n)

son constantes y con las condiciones del tipo (2), (3). Las m condiciones (2) se llaman restricciones. Esta es la formulación típica del método del símplex. Si en la formulación original hubiese algún

bi < 0

se multiplicaría dicha restricción por -1, con lo que se invertiría el sentido de la desigualdad, caso de ser distinta de una ecuación; así, pues, se supone que los segundos miembros de todas las restricciones (2) son no negativos. Una vez que todos los b; son no negativos, el primer paso consiste en transformar las restricciones (2) en un sistema de ecuaciones lineales. Esto se consigue introduciendo unas variables de holgura no negativas: positivas, +U;, para las restricciones del tipo < y negativas, -E;, para las del tipo >. De esta forma, las restricciones (2) se convierten en un sistema de m ecuaciones lineales con N incógnitas, siendo

n <= N <= n+m.

Así, por la adición de variables de holgura, todo problema de p. l. se transforma en el problema equivalente

z* = Nz’ c’x’ (máx. o mín.)(4)

con

j=N~a,’¡x*=b’(i=1, 2, ..., m)(5)

x*j => 0(j = 1, 2, ..., N)(6)

Esta es la forma típica del método del símplex revisado, en la que x*j son las variables reales xj de la formulación original o las variables de holgura añadidas. Las b*i son todas no negativas, en tanto que las c*j son los cj iniciales o cero, si corresponden a variables de holgura. Toda columna

a*ij(i = 1, 2, ... , m)

recibe el nombre de vector actividad asociado a la variable x*j y el valor de la variable x*j, el de nivel de dicha actividad en una solución de (5). El vector actividad asociado a una variable de holgura positiva será un vector unidad, mientras que el vector correspondiente a una variable de holgura negativa será -1 por un vector unidad.

Hay una correspondencia biunívoca entre los conjuntos de soluciones del sistema de restricciones originales (2) con

xj => 0(j=1, 2, . ., n)

y las soluciones con

x*j => 0 (j=1, 2 ... , N)

obtenido a partir de las restricciones originales con la adición de variables de holgura.

Nomenclatura empleada en el método del símplex en su forma típica. Solución factible: Cualquier solución de (5) y (6). Solución básica: una solución de (5) obtenida anulando N-m variables XI. El conjunto de las m variables restantes se llama base. Solución básica factible: una solución que es a la vez básica y factible. Solución óptima: una solución factible que satisface la condición de optimalidad (4). Solución básica óptima: una solución básica factible que satisface (4). El método alcanza una solución básica óptima en un número finito de pasos o indica que hay una solución no acotada. Se conviene en que una solución no acotada no se llama óptima. Si el problema tiene solución básica óptima, el valor óptimo de la función objetivo z deberá ser finito, y al menos una solución básica factible será óptima. Si se tiene una solución básica factible que no es óptima, es posible obtener una solución básica óptima en un número finito de pasos o bien obtener como final la conclusión de solución no acotada. El medio de lograr una solución básica factible de partida consiste en crear (si se precisa) un conjunto de variables básicas, A;, llamadas artificiales, una para cada restricción de los tipos igual, o mayor o igual. Si en la formulación original existe alguna restricción del tipo

V. t.: INVESTIGACIÓN IV.

G. GARCÍA L. DE HEREDIA.

BIBL.: R. W. LLEWELLYN, Programación lineal, Barcelona 1968; S. 1. GASS, Programación lineal, 2 ed. México 1966; G. HADLEY, Linear Programming, Reading (Mass.) 1961; G. B. DANIZIG, Linear Programming and Extensions, Princeton 1963; M. SIMONARD, Programmation Linéaire, París 1962; H. MAURIN, Programmation Linéaire Apliquée, París 1967; GRAVES WOLFE, Recent Advances in Mathematical Programming, Nueva York 1963; A. CHARNES y W. W. COOPER, Management Model and Industrial Application of Linear Programming, Nueva York; W. GARVIN, Introduction to Linear Programming, Nueva York 1960; E. O. HEADY y W. CANDLER, Linear Programming Methods, Ames (Iowa) 1958; R. DORFMAN, P. A. SAMUELSON y R. M. SOLOW, Linear Programming and Economic Analysis, Nueva York 1958.