Modelos de programación lineal

Concepto

La programación lineal es una técnica matemática muy utilizada en la dirección de operaciones, siendo uno de los grandes avances científicos que se dieron en la primera mitad del siglo XX. Su campo de estudio es la asignación óptima de los recursos limitados entre diferentes actividades empresariales, tales como:

• — Selección de la mejor combinación de factores que maximicen el beneficio, con una adecuada utilización de los recursos productivos. Los factores o recursos productivos hacen referencia a la maquinaria utilizada, a la mano de obra directa, a los materiales, al dinero o capital invertido y al tiempo, ya que la información es válida para un horizonte temporal determinado.
• — Desarrollo del programa de producción para hacer frente a la demanda esperada, minimizando los costes que esta origina.
• — Determinación de la distribución de los productos desde los almacenes hasta los puntos de venta.

Algunos ejemplos concretos de la utilización de la programación lineal son los siguientes:

• — Programación de autobuses escolares para minimizar la distancia de las rutas.
• — Asignación de coches patrullas en las zonas de mayor índice de criminalidad, para que el tiempo de respuesta sea el menor posible.
• — Programación de los cajeros en las entidades bancarias, garantizando el servicio al cliente, reduciendo los costes de mano de obra.
• — Elección de las materias primas en las industrias alimenticias, de manera que se obtengan alimentos de calidad con un coste mínimo.
• — Asignación de los espacios físicos de un centro comercial entre los diferentes arrendatarios, maximizando los ingresos de la empresa de leasing.

Los requisitos de un problema de programación lineal son los siguientes:

• a) Tiene como objetivo maximizar o minimizar alguna cantidad. En la empresa, se maximizan beneficios y se minimizan costes.
• b) La existencia de restricciones que limitan el nivel de producción y venta que se pretende alcanzar. Dichas restricciones suelen estar relacionadas con la cantidad de factores disponibles, tales como las unidades de material, las horas de trabajo, etc.
• c) Tienen que existir diferentes alternativas de elección, de productos y de procesos, de manera que el empresario pueda elegir a la hora de asignar sus recursos.
• d) Tanto la función objetivo como las restricciones deben estar expresadas en ecuaciones lineales o desigualdades.

Formulación de modelos de programación lineal

Todo problema de producción representado algebraicamente mediante un modelo de programación lineal estará formado por los siguientes elementos:

• — Variables de decisión (X_j): son las incógnitas del problema. Serán los niveles de fabricación y venta, o de utilización de un proceso, en el caso de que el empresario establezca como objetivo la maximización de sus ingresos o beneficios. Por el contrario, si los que desea es la minimización de los costes de producción, las incógnitas serán las cantidades de factores necesarias para hacer frente a la demanda.
• — Función objetivo: como se ha comentado con anterioridad, puede ser formulada siguiendo un principio de óptimo, buscando la maximización de los ingresos o beneficios empresariales, que viene dado por los productos o servicios ofrecidos.

  Max = C₁x₁+C₂x₂+...............+C_nx_n

  Donde C_j son los rendimientos directos unitarios de los procesos j (1, 2,..., n).

  Por otro lado, puede basarse en un principio de ahorro, donde lo que se quiere es minimizar el coste empleado en la producción, por lo que habrá que controlar la asignación de los factores, así como las cantidades disponibles de estos.

  Min = y₁x₁+y₂x₂+...............+y_mx_m

  Donde y_i son los costes unitarios de los factores i empleados (1, 2,..., m).

• — Restricciones: constituye el denominado conjunto de soluciones factibles o región factible. Al vector formado por las variables de decisión se le denomina plan o programa de producción, y será factible si satisface todas las restricciones o condicionantes del problema. El plan o programa óptimo será aquel programa que logre el objetivo marcado por el director de operaciones, es decir, que maximice el beneficio o minimice el coste. Podemos distinguir cuatro tipos de restricciones:
  • a) Recursos limitados: en el caso de que la función objetivo sea maximizar serán:

    a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n ≤ b₁

    a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n ≤ b₂

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

    a_m1x₁ + a_m2x₂ + ... + a_mnx_n ≤ b_m

    Dónde:

    • — a_ij: son los coeficientes técnicos y representan la cantidad de factor i (1, 2,..., m) necesaria para fabricar una unidad de producto j (1, 2,.... n). Estos coeficientes técnicos forman la denominada matriz tecnológica o de coeficientes técnicos de la empresa (A_mxn). Cada columna de esta matriz representa un proceso productivo P_j.
    • — b_m: son los recursos disponibles para la empresa. Su valor absoluto dependerá de la dimensión empresarial. Forman un vector columna (b). Ejemplo: unidades de material.
  • b) Restricciones de demanda: hace referencia a la cantidad de producto o servicio que la empresa debe ofrecer como mínimo, para cubrir la demanda existente, o como máximo, en el caso de que el mercado solo puede absorber una determinada cantidad.
  • c) Restricciones de oferta: relacionada con la cantidad mínima de los bienes que tienen que comercializarse para cubrir los costes fijos o, por el contrario, la cantidad máxima que la empresa puede fabricar de un determinado producto.
  • d) Restricción de no negatividad o sentido económico: las cantidades fabricadas y vendidas de los productos, así como los consumos mínimos de los factores para garantizar la demanda, deben ser positivos o nulos.

La definición del número de variables y de ecuaciones (restricciones y limitaciones) es algo que lo determina el propio empresario, según las características de la empresa en un momento dado. A continuación planteamos un sencillo ejemplo de producción que sigue un modelo de programación lineal.

La empresa UNICOLE, S.L. es una microempresa dedicada a la fabricación y venta de uniformes escolares infantiles personalizados, especializada en dos tipos de prendas: camisas (P₁) y faldas (P₂). El precio de venta unitario, así como los costes de fabricación directos unitarios de cada prenda, aparecen en la siguiente tabla:

La dirección de operaciones de la empresa ha propiciado los siguientes datos sobre el proceso de fabricación diario de los diferentes productos:

• — Las prendas son elaboradas con un tejido, cuyos componentes orgánicos son de alta calidad, asegurando una agradable textura y alta resistencia. La empresa puede disponer de 40m de tejido al día, siendo el ritmo de fabricación el siguiente: 2 camisas/m y 2 faldas/m.
• — La plantilla de la empresa puede trabajar un total de 90 horas diarias, de manera que cada camisa precisa 2 horas y cada falda 1 hora.
• — El departamento de bordado, acabado y planchado presenta una capacidad diaria limitada del 60 %, debido a diversas averías en la maquinaria. Se conoce que cada camisa requiere un 0 4 % de capacidad y cada falda un 0 2 %.

El planteamiento del programa sería el siguiente:

Max F(x)=Z=15x₁+20x₂

Sujeto a

Resolución gráfica de los problemas de programación lineal

El método gráfico es utilizado para la resolución del programa óptimo cuando el número de variables de decisión (incógnitas del problema) es igual a dos. Para su implementación se representa la región factible, es decir, el conjunto de puntos contenidos en el área delimitada por el eje de abscisas, el eje de ordenadas y las restricciones del programa. Para ello, se convierten dichas restricciones del problema (≤, ≥) en ecuaciones (=).

En nuestro caso, como todas las restricciones son en sentido menor o igual, las rectas constituyen los límites superiores para el conjunto de soluciones factibles, cumpliéndose además que las variables de decisión deben tomar un valor mínimo nulo (condicionante de no negatividad).

Una vez determinadas las posibles soluciones, deberemos elegir la situación óptima, siendo esta la que optimice el valor de la función objetivo. Para alcanzar esta solución pueden utilizarse dos procedimientos: el método de solución a partir de las rectas isobeneficio o el método de solución a partir de los vértices.

Método de solución a partir de las rectas isobeneficio

Se siguen los siguientes pasos:

• — Se fija un nivel arbitrario para la función objetivo y se determina la recta isobeneficio que representa todas las combinaciones (X₁, X₂) que lo alcanzarían. Para su representación se buscan los puntos de corte con el eje de abscisas (valor de X₁ cuando X₂=0) y con el eje de ordenadas (valor de X₂ cuando X₁=0).
• — A continuación se desplaza la recta isobeneficio hacia el origen y hacia + ∞, para analizar en qué sentido se optimiza el valor de la función objetivo. En el caso de maximización de beneficios este hecho se producirá a medida que nos alejamos del origen o punto (0,0).
• — Por último, se desplaza la recta isobeneficio paralelamente sobre el conjunto de soluciones factibles hasta alcanzar el valor máximo, que será uno de sus vértices.

Método de solución a partir de los vértices

También llamado método de los puntos extremos. Supone buscar el beneficio en cada uno de los vértices del conjunto de soluciones posibles, respaldado por la teoría matemática que afirma que la solución óptima se encontrará en uno de los extremos. Una vez que se han determinado los vértices de la región factible, se sustituyen en la función objetivo para calcular el máximo beneficio o mínimo coste.

Si aplicamos este método a nuestro problema de producción quedaría la siguiente representación gráfica:

Los vértices obtenidos serían:

• — Vértice 1: (0,0), donde el beneficio será Z=(15×0)+(20×0)=0€
• — Vértice 2: (0,80), donde el beneficio será Z=(15×0)+(20×80)=1.600€
• — Vértice 3: (10,70), donde el beneficio será Z=(15×10)+(20×70)=1.550€
• — Vértice 4: (45,0), donde el beneficio será Z=(15×45)+(20×0)=675€

A la vista de los resultados obtenidos, la solución óptima de esta empresa sería fabricar y vender 80 faldas, obteniendo un beneficio máximo diario de 1.600€.

Algoritmo del Simplex

El Algoritmo del Simplex fue enunciado por George Dantzing en 1947, siendo un procedimiento iterativo de búsqueda de la solución óptima en problemas de programación lineal de cualquier tamaño, solventando la limitación del método gráfico, que solo nos permite trabajar con dos variables de decisión.

Los conceptos básicos utilizados en el Algoritmo del Símplex son los siguientes:

• — Factores productivos (m): utilizados en la obtención de un producto o servicio. Pueden ser limitados, expresados en restricciones, o ilimitados.
• — Vector de recursos disponibles (b_m): vector columna formado por las cantidades utilizables de los factores.
• — Tecnología: cualquier combinación de los factores productivos.
• — Proceso productivo: supone la combinación o transformación de los factores (inputs) en bienes o servicios (outputs), utilizando una tecnología.
• — Vector Proceso (P_j): vector columna formado por las cantidades necesarias de los factores para la fabricación de una unidad de producto, utilizando ese proceso.
• — Nivel de proceso (X_j): muestra la intensidad de utilización de los factores productivos en el proceso. También es conocido como el número de veces que se repite dicho proceso.
• — Rendimiento directo del proceso (C_j): se calcula como la diferencia entre los ingresos y los costes originados por dicho proceso.
• — Programa de producción: consiste en la realización de uno o varios procesos productivos a unos determinados niveles.
• — Rendimiento de un programa: suma de los rendimientos obtenidos por los P_j que lo integran. Para calcular el rendimiento de un proceso P_j, se multiplica el rendimiento directo (C_j) por el nivel de proceso (X_j).
• — Matriz tecnológica: formada por los coeficientes técnicos unitarios, que representan la cantidad de factor i (1, 2,..., m) necesaria para fabricar una unidad de producto j (1, 2,.... n). Matricialmente se representa:

• — Vector de rendimientos: fila formada por los rendimientos directos de todos los procesos P_j (j=1, 2,..., n).

El desarrollo de este algoritmo requiere de ciertas hipótesis de partida:

• a) Proporcionalidad: la contribución de cada actividad al valor de la función objetivo es proporcional, así como al valor de los términos independientes de las restricciones.
• b) Aditividad: no se permite la existencia de productos cruzados, de manera que la combinación de varios procesos se obtiene como la suma de los factores exigidos individualmente por cada uno de ellos.
• c) Divisibilidad: todas las variables del modelo pueden tomar cualquier valor no entero, siempre y cuando cumplan todas las restricciones del programa, incluyendo la de no negatividad.
• d) Certidumbre: todos los parámetros del modelo son conocidos con certeza.

Bajo esta premisa cualquier problema de producción expresado en programación lineal quedaría de la siguiente forma:

Max = C₁x₁ + C₂x₂ + ...+ C_nx_n

sujeto a:

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n ≤ b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n ≤ b₂

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

a_m1x₁ + a_m2x₂ + ... + a_mnx_n ≤ b_m

Imaginemos que la dirección de operaciones de la empresa UNICOLE, S.L., ha decidido ampliar su cartera de productos a cuatro, fabricando camisas (P₁), faldas (P₂), pantalones (P₃) y pichis (P₄). Los datos económicos serían:

La dirección de operaciones de la empresa proporciona los datos sobre el proceso de fabricación diario de los diferentes productos:

• — Las prendas son elaboradas con un tejido, cuyos componentes orgánicos son de alta calidad, asegurando una agradable textura y alta resistencia. La empresa puede disponer de 40m de tejido al día, siendo el ritmo de fabricación el siguiente: 2 camisas/m, 2 faldas/m, 1 pantalón/m y 1 pichi/m.
• — La plantilla de la empresa puede trabajar un total de 90 horas diarias, de manera que cada camisa precisa 2 horas, cada falda 1 hora, cada pantalón 2 horas y cada pichi 3 horas.
• — El departamento de bordado, acabado y planchado presenta una capacidad diaria limitada del 60 %, debido a diversas averías en la maquinaria. Se conoce que cada camisa requiere un 0,4 % de capacidad, cada falda un 0,2 %, cada pantalón un 0,4 % y cada pichi un 0,5 %.

El planteamiento sería el siguiente:

Max F(x)=Z=15x₁+20x₂+15x₃+40x₄

Sujeto a:

El desarrollo del Algoritmo del Simplex parte de un programa base sobre el que se realizan iteraciones, es decir, de una solución básica se va pasando a soluciones o puntos extremos mejores, hasta alcanzar la solución óptima. Este autor planteó que si la organización se encuentra en un punto dentro del espacio de soluciones factibles y se quiere conseguir un acercamiento a una situación mejorada, se deberán analizar los rendimientos marginales w_j (diferencia entre los rendimientos directos -C_jj- y los rendimientos indirectos- _jZj-), y su disminución hasta llegar a la solución óptima, donde todos los rendimientos marginales son menores o iguales a cero (w_j≤0), si se persigue la maximización de beneficios.

Para implementar el Algoritmo del Simplex, llevaremos a cabo las siguientes etapas.

• — Etapa 1: conversión de las restricciones del problema en igualdades. Para ello, se introducen los procesos de holgura con un coeficiente técnico unitario en el lado izquierdo, tantos como desigualdades tenga el programa productivo, sumando en el caso de que las restricciones tengan signo ≤, o restando si la inecuación es de sentido ≥.

  En nuestro ejemplo sería:

  0´5x₁+0´5x₂+x₃+x₄+h₁=40 (m de tejido)

  2x₁+x₂+2x₃+3x₄≤40+h₂=90 (horas de trabajo)

  0´4x₁+0´2x₂+0´4x₃+0´5x₄+h₃=60 (capacidad del Departamento)

  Por lo que nuestra matriz tecnológica ampliada sería:

• — Etapa 2: Obtención del programa base o solución inicial del programa de producción, procediendo del siguiente modo:
  • a) Escoger las variables de holgura con coeficiente técnico unitario, y el mismo signo que el término independiente.
  • b) Si no es posible, seleccionar una variable de decisión (X_j) que aparezca sola en alguna restricción y que tenga el mismo signo que el término independiente.
  • c) En el caso de que tampoco fuera posible la opción anterior, introducir en las restricciones en las que se haya obtenido un vector unitario una variable artificial (K_j), con un rendimiento -M, si la función objetivo es de máximos, y +M, si es de mínimos, y con un coeficiente unitario.

  En nuestro caso, el programa lo formarían los tres procesos de holgura (P₅, P₆, P₇).

• — Etapa 3: Obtención de la tabla Simplex: formada por los siguientes elementos:
  • a) Primera fila: rendimientos directos de los procesos (C_j).
  • b) Segunda fila: procesos (P_j) que forman el plan de programación lineal, tanto los reales como los auxiliares (holgura, ficticios).
  • c) Primera columna: rendimientos directos unitarios de los procesos que forman el programa base.
  • d) Última columna: niveles de utilización del programa básico. En la primera iteración será el vector recursos (b_m).
  • e) Penúltima fila: rendimientos indirectos (Z_j). Se calcula multiplicando los rendimientos directos unitarios de los procesos que forman el programa base por el correspondiente vector del proceso (P_j).
  • f) Última fila: rendimientos marginales de los procesos (w_j). Se obtienen como diferencia entre el rendimiento directo y su indirecto (w_j=C_j-Z_j).
  • g) Cuerpo central de la tabla: matriz tecnológica ampliada (A), formada por los coeficientes técnicos unitarios o la cantidad de factor para fabricar una unidad de cada proceso, incluidos los reales y los auxiliares.

Teóricamente, la tabla del Simplex quedaría de la siguiente forma:

Con los datos de nuestro ejemplo la tabla Simplex será:

El valor de la función objetivo será: Z=(15×0)+(20×0)+(15×0)+(40×0)=0€.

• — Etapa 4: Prueba de Optimalidad. Se alcanzará la solución óptima con aquel programa base en el que todos los rendimientos marginales sean negativos o nulos, si lo que se desea es la maximización del beneficio, o no negativos, si lo que se persigue es la minimización del coste.

  Si observamos los datos de la tabla anterior comprobamos que los rendimientos marginales correspondientes a los procesos reales (W₁, W₂, W₃, W₄) son positivos, por lo que el programa base de partida no es el óptimo, no alcanzándose el máximo beneficio. Por ello, será necesario sustituir alguno de los procesos que forman parte del programa base por otro que no se encuentre en él.

• — Etapa 5: Iteración del Algoritmo del Simplex. Se siguen los siguientes pasos.
  • a) Determinación del proceso entrante: será introducido en el programa base el proceso que tenga mayor rendimiento marginal positivo en el caso de maximización, o menor rendimiento marginal negativo, si buscamos la minimización de los costes. En nuestro caso, como estamos tratando un problema de máximos, seleccionaremos como proceso entrante P₄, ya que es el de mayor rendimiento marginal (W₄).
  • b) Determinación del proceso saliente: consecuencia de incluir un nuevo proceso en el programa base. Para ello, denominamos columna pivote a aquella de la matriz tecnológica correspondiente al proceso entrante. El proceso saliente será el de menor valor, entre todos los positivos, del cociente entre su nivel de utilización y su elemento correspondiente a la columna pivote. Aplicado a nuestro ejemplo:

• Siendo la columna pivote

  Seleccionaremos el proceso con menor cociente entre los positivos, es decir, P₆, correspondiente a la segunda variable de holgura, por lo que el programa base estará formado por (P₄, P₅, P₇).

  • c) Construcción de la nueva tabla del Simplex: procedemos al cálculo de los coeficientes técnicos unitarios (a_ij), los niveles de utilización (X_j), los rendimientos indirectos (Z_j) y los rendimientos marginales (W_j).

    Los elementos correspondientes al nuevo proceso se obtienen dividiendo los elementos de esa fila en la tabla anterior (segunda fila) entre el elemento pivote, que es el perteneciente a la columna pivote con la fila del proceso saliente, en nuestro caso a₂₄, que es igual a 3. A los elementos restantes de esa columna se les denomina semipivotes.

Los elementos correspondientes a los procesos que permanecen en el programa base (P5, P7), de la Tabla 4, se calculan restando al elemento original el producto del semipivote del proceso por el elemento correspondiente del proceso entrante, tal y como muestra la siguiente tabla:

A continuación se determinan los rendimientos indirectos y marginales de cada uno de los procesos, quedando configurada la nueva tabla Simplex:

El valor de la función objetivo será: Z=(15×0)+(20×0)+(15×0)+(40×30)= 1.200€, por lo que ha aumentado su valor. Sin embargo, este programa base no corresponde con la solución óptima porque hay un rendimiento marginal positivo (W₂), tal y como se muestra en la tabla anterior. Por lo tanto, repetiremos de nuevo el procedimiento, entrando en el programa base P₂ y saliendo P₅ (holgura 1), ya que es el de menor valor del cociente entre el nivel de utilización y su correspondiente elemento de la columna pivote:

Siendo la columna pivote

A continuación se obtiene la nueva tabla Simplex:

Si sustituimos los niveles de utilización en la función objetivo será: Z=(15×0)+(20×60)+(15×0)+(40×10)= 1.600€, siendo el beneficio superior que en la situación anterior. Como todos los rendimientos marginales (W_j) son negativos o nulos, al tratarse de un problema de maximización, podemos afirmar que el programa base formado por (P₂, P₄, P₇) es la solución óptima. Si la empresa quiere obtener un beneficio máximo diario de 16.000 € debe fabricar y vender 60 faldas y 10 pichis. Por otro lado, el hecho de que la variable de holgura 3 tome un valor positivo de 43 unidades, implica la existencia de un 43 % de capacidad ociosa del departamento de bordado, acabado y planchado (tercera restricción), es decir, esa capacidad está disponible y no está siendo utilizada en el proceso productivo.