Regresar a la Página Principal
|
Aspectos Generales de la Programación Lineal |
En los siglos XVII y XVIII,
grandes matemáticos como Newton, Leibnitz,
Bernouilli y, sobre todo, Lagrange,
que tanto habían contribuido al desarrollo del cálculo
infinitesimal, se ocuparon de obtener máximos y mínimos
condicionados de determinadas funciones.
Posteriormente el matemático fránces Jean Baptiste-Joseph Fourier (1768-1830) fue el primero en intuir, aunque de forma imprecisa, los métodos de lo que actualmente llamamos programación lineal y la potencialidad que de ellos se deriva.
Si exceptuamos al matemático Gaspar Monge (1746-1818), quien en 1776 se interesó por problemas de este género, debemos remontarnos al año 1939 para encontrar nuevos estudios relacionados con los métodos de la actual programación lineal. En este año, el matemático ruso Leonodas Vitalyevich Kantarovitch publica una extensa monografía titulada Métodos matemáticos de organización y planificación de la producción en la que por primera vez se hace corresponder a una extensa gama de problemas una teoría matemática precisa y bien definida llamada, hoy en día, programación lineal .
En 1941-1942 se formula por primera vez el problema de transporte, estudiado independientemente por Koopmans y Kantarovitch, razón por la cual se suele conocer con el nombre de problema de Koopmans-Kantarovitch.
Tres años más tarde, G. Stigler plantea otro problema particular conocido con el nombre de régimen alimenticio optimal.
En estos años posteriores a la Segunda Guerra Mundial, en Estados Unidos se asumió que la eficaz coordinación de todas las energías y recursos de la nación era un problema de tal complejidad, que su resolución y simplificación pasaba necesariamente por los modelos de optimización que resuelve la programación lineal.
Paralelamente a los hechos descritos se desarrollan las técnicas de computación y los ordenadores, instrumentos que harían posible la resolución y simplificación de los problemas que se estaban gestando.
En 1947, G.B. Dantzig formula, en términos matemáticos muy precisos, el enunciado estándar al que cabe reducir todo problema de programación lineal. Dantzig, junto con una serie de investigadores del United States Departament of Air Force, formarían el grupo que dio en denominarse SCOOP (Scientific Computation of Optimum Programs).
Una de las primeras aplicaciones de los estudios del grupo SCOOP fue el puente aéreo de Berlín. Se continuó con infinidad de aplicaciones de tipo preferentemente militar.
Hacia 1950
se constituyen, fundamentalmente en Estados Unidos, distintos
grupos de estudio para ir desarrollando las diferentes
ramificaciones de la programación lineal. Cabe citar, entre
otros, Rand Corporation, con Dantzig, Orchard-Hays, Ford,
Fulkerson y Gale, el departamento de Matemáticas de la
Universidad de Princenton, con Tucker y Kuhn, así como la
Escuela Graduada de Administración Industrial, dependiente del
Carnegie Institute of Technology , con Charnes y Cooper.
Respecto al método del simplex, que estudiaremos después, señalaremos que su estudio comenzó en el año 1951 y fue desarrollado por Dantzig en el United States Bureau of Standards SEAC COMPUTER, ayudándose de varios modelos de ordenador de la firma IBM.
Los fundamentos matemáticos de la programación lineal se deben al matemático norteamericano de origen húngaro Janos von Neuman (1903-1957), quie en 1928 publicó su famoso trabajo Teoría de Juegos. En 1947 conjetura la equivalencia de los problemas de programación lineal y la teoría de matrices desarrollada en sus trabajos. La influencia de este respetado matemático, discípulo de David Hilbert en Gotinga y, desde 1930, catedrático de la Universidad de Princenton de Estados Unidos, hace que otros investigadores se interesaran paulatinamente por el desarrollo riguroso de esta disciplina.
En 1858 se aplicaron los métodos de la programación lineal a un problema concreto: el cálculo del plan óptimo de transporte de arena de construcción a las obras de edificación de la ciudad de Moscú. En este problema había 10 puntos de partida y 230 de llegada. El plan óptimo de transporte, calculado con el ordenador Strena en 10 días del mes de junio, rebajó un 11% los gastos respecto a los costes previstos.
Se ha estimado, de una manera general, que si un país subdesarrollado utilizase los métodos de la programación lineal, su producto interior bruto (PIB) aumentaría entre un 10 y un 15% en tan sólo un año.
La programación lineal hace historia: El puente aéreo de Berlín
En 1946 comienza
el largo período de la guerra fría entre la antigua Unión
Soviética (URSS) y las potencias aliadas (principalmente ,
Inglaterra y Estados Unidos). Uno de los episodios
más llamativos de esa guerra fría se produjo a mediados de
1948, cuando la URSS bloqueó las comunicaciones terrestres desde
las zonas alemanas en poder de los aliados con la ciudad de
Berlín, iniciando el bloqueo de Berlín. A los aliados se les
plantearon dos posiblidades: o romper el bloqueo terrestre por la
fuerza, o llegar a Berlín por el aire. Se adoptó la decisión
de programar una demostración técnica del poder aéreo
norteamericano; a tal efecto, se organizó un gigantesco puente
aéreo para abastecer la ciudad: en diciembre de 1948 se estaban
transportando 4500 toneladas diarias; en marzo de 1949, se llegó
a las 8000 toneladas, tanto como se transportaba por carretera y
ferrocarril antes del corte de las comunicaciones. En la
planificación de los suministros se utilizó la programación
lineal. (El 12 de mayo de 1949, los soviéticos levantaron el
bloqueo)
| ¿Qué es la programación lineal ? |
En infinidad de aplicaciones de la industria, la economía, la estrategia militar, etc.. se presentan situaciones en las que se exige maximizar o minimizar algunas fucniones que se encuentran sujetas a determinadas limitaciones, que llamaremos restricciones.
Para hacernos una idea más clara de estos supuestos, veamos dos ejemplos:
Ejemplo 1:
Problema de máximos.
En una granja se preparan dos clases de fertilizantes, P y Q,
mezclando dos productos A y B. Un saco de P contiene 8 kg de A y
2 de B, y un saco de Q contiene 10 kg de A y 5 de B. Cada saco de
P se vende a 300 Bs. y cada saco de Q a 800 Bs. Si en la
granja hay almacenados 80 kg de A y 25 de B, ¿cuántos sacos de
cada tipo de pienso deben preparar para obtener los máximos
ingresos?
Ejemplo 2:
Problema de mínimos.
Una campaña para promocionar una marca de productos
lácteos se basa en el reparto gratuito de yogures con sabor a
limón o a fresa. Se decide repartir al menos 30000 yogures.
Cada yogur de limón necesita para su elaboración 0.5 gramos de
un producto de fermentación y cada yogur de fresa necesita 0.2
gramos de este mismo producto. Se dispone de 9 kilogramos de este
producto para fermentación.
El costo de producción de un yogur de limón es de 30 Bs. y
20 Bs. uno de fresa.
En los dos ejemplos descritos está claro que tanto la cantidad que deseamos maximizar como la cantidad que deseamos minimizar podemos expresarlas en forma de ecuaciones lineales. Por otra parte, las restricciones que imponen las condiciones de ambos problemas se pueden expresar en forma de inecuaciones lineales.
Tratemos de plantear en términos matemáticos los dos ejemplos anteriores:
1) Si designamos por x al número de sacos de
fertilizante de clase P y por y el número de sacos de fertilizante de clase
Q que se han de vender, la función : Z
= 300x + 800y representará la cantidad de bolívares obtenidas por la venta
de los sacos, y por tanto es la que debemos maximizar.
Podemos hacer un pequeño cuadro que nos ayude a obtener las
restricciones:
| Nº | kg de A | kg de B | |
| P | x | 8x | 2x |
| Q | y | 10y | 5y |
 80 |
25 |
Por otra parte, las
variables x e y, lógicamente, han de ser no
negativas, por tanto : x 
0, y
0
Conjunto de restricciones:
| 8x
+ 10y
80 |
| 2x
+ 5y
25 |
| x
0, y
0 |
2) Si representamos por x el número
de yogures de limón e y al número de yogures de fresa,
se tiene que la función de costos es Z
= 30x + 20y.
Por otra parte, las condiciones del problema imponen las
siguientes restricciones:
80 9000 0, y
0 Conjunto de restricciones:
| x + y
80 |
| 0.5x
+ 0.2y
9000 |
| x
0, y
0 |
En definitiva:
Se llama
programación lineal al conjunto de técnicas
matemáticas que pretenden resolver la situación
siguiente: |
Un problema de programación lineal en dos variables, tiene la siguiente formulación estándar:
puediendo cambiarse maximizar por minimizar, y el sentido de las desigualdades.
En un problema de programación lineal intervienen:
La función f(x,y) = ax + by + c llamada función objetivo y que es necesario optimizar. En esa expresión x e y son las variables de decisión, mientras que a, b y c son constantes.
Las restricciones
que deben ser inecuaciones lineales. Su número depende
del problema en cuestión. El carácter de desigualdad
viene impuesto por las limitaciones, disponibilidades o
necesidades, que son: inferiores a ... ( menores: < o
); como mínimo
de ... (mayores: > o ) . Tanto si se trata de maximizar como de
minimizar, las desigualdades pueden darse en cualquiera
de los dos sentidos.
Al conjunto de valores de x e y que verifican todas y cada una de las restricciones se lo denomina conjunto (o región ) factible. Todo punto de ese conjunto puede ser solución del problema; todo punto no perteneciente a ese conjunto no puede ser solución. En el apartado siguiente veremos como se determina la región factible.
La solución óptima del problema será un par de valores (x0, y0) del conjunto factible que haga que f(x,y) tome el valor máximo o mínimo.
En ocasiones utilizaremos las siglas PPL para indicar problema de programación lineal.
| Determinación de la región factible |
| La solución de un problema de programación lineal, en el supuesto de que exista, debe estar en la región determinada por las distintas desigualdades. Esta recibe el nombre de región factible, y puede estar o no acotada. | |
 Región factible acotada |
 Región factible no acotada |
La región factible
incluye o no los lados y los vértices, según que las
desigualdades sean en sentido amplio ( o
) o en sentido estricto (< o >).
Si la región factible está acotada, su representación gráfica es un polígono convexo con un número de lados menor o igual que el número de restricciones.
El procedimiento para determinar la región factible es el siguiente:
1) Se resuelve cada inecuación por separado, es decir, se encuentra el semiplano de soluciones de cada una de las inecuaciones.
Se dibuja la recta asociada a la inecuación. Esta recta divide al plano en dos regiones o semiplanos
Para averiguar cuál es la región válida, el procedimiento práctico consiste en elegir un punto, por ejemplo, el (0,0) si la recta no pasa por el origen, y comprobar si las coordenadas satisfacen o no la inecuación. Si lo hacen, la región en la que está ese punto es aquella cuyos puntos verifican la inecuación; en caso contrario, la región válida es la otra.
2) La región factible está formada por la intersección o región común de las soluciones de todas las inecuaciones.
Como sucede con los sistemas de ecuaciones lineales, los sistemas de inecuaciones lineales pueden presentar varias opciones respecto a sus soluciones: puede no existir solución, en el caso de que exista el conjunto solución puede ser acotado o no.
Veámoslo con un ejemplo:
Dibuja la región factible asociada a las restricciones:
| x + y
4 |
| y 4 |
| y
x |
Las rectas asociadas son : r : x + y = 4 ; s : y = 4 , t: y = x
Elegimos el punto O(0,0),
que se encuentra en el semiplano situado por debajo de la
recta. Introduciendo las coordenadas (0,0) en la
inecuación x + y |
Procedemos como en el paso
anterior. Las coordenadas (0,0) satisfacen la inecuación
y |
La recta t asociada a la
restricción pasa por el origen, lo cual significa que si
probásemos con el punto O(0,0) no llegaríamos a ninguna
conclusión. Elegimos el punto (1,0) y vemos que no
satisface la inecuación y |
La región factible está formada por los puntos que cumplen las tres restricciones, es decir, se encuentran en los tres semiplanos anteriores. |
| Método gráfico |
| o Método de las rectas de nivel |
Las rectas de nivel dan los puntos del plano en los que la función objetivo toma el mismo valor.
Si la función objetivo es f(x,y) = ax + by + c, la ecuación de las rectas de nivel es de la forma:
ax + by
+ c = 0 
ax
+ by = k
Variando k (o p) se obtienen distintos niveles para esas rectas y, en consecuencia, distintos valores para f(x,y).
En un problema todas las rectas de nivel son paralelas, pues los coeficientes a y b de la recta ax + by = k son los que determinan su pendiente. Por tanto, si k1 es distinto de k2 , las rectas ax + by = k1 y ax + by = k2 son paralelas. Luego, trazada una cualquiera de esas rectas, las demás de obtienen por desplazamientos paralelos a ella.
Si lo que se pretende es resolver un problema de programación lineal, los únicos puntos que interesan son los de la región factible, y las únicas rectas de nivel que importan son aquellas que están en contacto con dicha región. Como el nivel aumenta (o disminuye) desplazando las rectas, el máximo (o el mínimo) de f(x,y) se alcanzará en el último (o en el primer) punto de contacto de esas rectas con la región factible.
Veamos ahora como se aplica todo esto a la resolución de un problema de programación lineal :
| Maximizar | Z = f(x,y) = x + y |
| sujeto a: | 0
x 4 |
| 0
y 4 |
|
| y
x /2 |
1) Representamos la región factible:
x 4 son los puntos entre el eje Y y la recta x
= 4
y 4 son los puntos entre el eje X y la recta y
= 4
x /2 son los puntos de su
izquierda.
Resolviendo los sistemas correspondientes calculamos los vértices de la región factible:
{ y = x/2 , x
= 0 } nos da el vértice O(0,0)
{ x = 4, y = x/2 } nos da el vértice A(4,2)
{ x = 4 , y = 4} nos da el vértice B(4,4)
{ y = 4 , x = 0 } nos da el vértice C(0,4)
2) Representamos las rectas de nivel :
En nuestro caso son
rectas de la forma x + y = k . Inicialmente
representamos Z = x + y = 0 . Trasladándola hacia la
derecha, obtenemos las rectas : x + y = 2, x + y
= 4, x + y = 8 , es decir aumenta el nivel.
3) Obtenemos la solución óptima:
Se obtiene en el punto de la región factible que hace máximo k. En nuestro caso esto ocurre en el punto B; es el último punto de contacto de esas rectas con la región factible , para el que k = 8.
| Si hay dos vértices, P y Q, que se encuentran en la misma recta de nivel ,de ecuación ax + by = k .Es evidente que todos los puntos del segmento PQ son de esa recta; por tanto, en todos ellos f(x,y) vale k. Así pues, la solución óptima es cualquier punto de esa recta; en particular los vértices P y Q. |
| Método analítico |
| o Método de los vértices |
El siguiente resultado, denominado teorema fundamental de la programación lineal, nos permite conocer otro método de solucionar un programa con dos variables.
|
La evaluación de la función objetivo en los vértices de la región factible nos va a permitir encontrar el valor óptimo (máximo o mínimo) en alguno de ellos.
Veámoslo con un ejemplo:
| Maximizar | Z = f(x,y) = 3x + 8y |
| sujeto a: | 4x + 5y
40 |
| 2x + 5y
30 |
|
| x
0 , y 0 |
1) Hallar los puntos de corte de las rectas asociadas a las restricciones:
Calculamos las soluciones de cada uno de los seis sistemas de dos ecuaciones con dos incógnitas que se pueden formar con las cuatro restricciones:
| { 4x + 5y = 40 , 2x + 5y = 30}. Solución A(5,4) | { 4x + 5y = 40 , x = 0 } Solución:B (0,8) |
| { 4x + 5y = 40 , y = 0}. Solución: C(10,0) | { 2x + 5y = 30 , x = 0} Solución: D(0,6) |
| { 2x + 5y = 30 , y = 0}. Solución : E(15,0) | { x = 0, y = 0} Solución: O(0,0) |
2) Determinar los vértices de la región factible:
Los vértices de la región factible son aquellos puntos que cumplen todas las restricciones.
Si sustituimos los puntos en cada una de las desigualdades tenemos que:
30 , ya que 2·0
+ 5·8 = 40 . Por tanto, el punto B no es un vértice de
la región factible. 40 , ya que 4·15
+ 5·0 = 60 . Por tanto, el punto E no es un vértice de
la región factible.Los puntos A, C, D y O verifican todas las desigualdades, son los vértices de la región factible.
3) Calcular los valores de la función objetivo en los vértices:
| f(A) = f(5,4) = 3·5 + 8·4 = 47 | f(C) = f(10,0) = 3·10 + 8· 0 = 30 |
| f(D) = f(0,6) = 3·0 + 8·6 = 48 | f(O) = f(0,0) = 3·0 + 8·0 = 0 |
La solución óptima corresponde al vértice para el que la función objetivo toma el valor máximo. En este caso es el vértice D(0,6).
| Este método es el menos utilizado de los tres que veremos |
| Esquema práctico |
Los problemas de programación lineal pueden presentarse en la forma estándar, dando la función objetivo y las restricciones, o bien plantearlos mediante un enunciado. Si éste es el caso, puede seguirse el camino que indicamos a continuación, ejemplificado con el siguiente problema:
En un almacén se guarda aceite de girasol y de oliva. Para atender a los clientes se han de tener almacenados un mínimo de 20 bidones de aceite de girasol y 40 de aceite de oliva y, además, el número de bidones de aceite de oliva no debe ser inferior a la mitad del número de bidones de aceite de girasol. La capacidad total del almacén es de 150 bidones. Sabiendo que el gasto de almacenaje es el mismo para los dos tipos de aceite (1 unidad monetaria) . ¿Cuántos bidones de cada tipo habrá que almacenar para que el gasto sea máximo?
| Obs: Puede parecer algo absurdo maximizar los gastos , pero se ha enunciado de esta forma para que el ejemplo sea lo más completo posible |
Paso 1º: Leer detenidamente el enunciado: determinar el objetivo, definir las variables y escribir la función objetivo.
El objetivo es: halla cuántos bidones de cada tipo hay que almacenar para maximizar los gastos
Suponemos que tal objetivo se consigue almacenado x bidones de aceite de girasol e y de aceite de oliva
Cómo cada bidón de aceite de girasol cuesta almacenarlo 1 unidad monetaria y lo mismo para uno de aceite, los gastos serán x + y
Luego, la función objetivo es:
Maximizar la función Z = f(x,y) = x + y
Paso 2º: Reordenar los datos del problema y a partir de las cantidades decididas, x e y, escribir el sistema de inecuaciones que determinan las restricciones.
20
40
x/2 150 Además, los números
de bidones deben ser cantidades positivas: x
0 ; y
0
| Obs.: Como veremos en ejemplos posteriores en algunas ocasiones puede interesar utilizar una tabla para recopilar toda la información y hacer los dos primeros apartados |
Paso 3º: Expresar el problema en la forma estándar.
Siguiendo con el ejemplo, sería:
| Maximizar: | Z = f(x,y) = x + y |
| sujeto a: | x + y
150 |
| y
x/2 |
|
| x
20 ; y 40 |
Aquí termina el planteamiento del problema. Para su resolución hay que continuar con :
Paso
4º: Representar
gráficamente las restricciones y marcar claramente la región
factible.
Para las restricciones anteriores debemos representar las rectas: x + y = 150 , y = x/2 , x = 20 e y = 40, obteniéndose la región factible que en la figura se encuentra coloreada.
Paso 5º: Hallar las coordenadas de los vértices del polígono obtenido.
Resolviendo los sistemas : { x = 20, y = 40 } , { y = x/2 , y = 40 } , { y = x/2 , x + y = 150} , { x + y = 150, x = 20}; se obtienen los vértices: A(20,40) , B(80,40) , C(100, 50) , D(20,130)
Paso 6º: Sustituir las coordenadas de esos puntos en la función objetivo y hallar el valor máximo o mínimo.
Sustituyendo en f(x,y) = x + y, se tiene:
f(20,40) = 60 , f(80,40) = 120 , f(100, 50) = 150 , f(20,130) = 150
Como el valor máximo se obtiene en los puntos C y D, puede optarse por cualquiera de los dos, o por cualquier punto perteneciente al segmento que los une. Así, por ejemplo, se obtendría el mismo gasto con 40 bidones de aceite girasol y 110 bidones de aceite de oliva; o 90 y 60 respectivamente.
Paso 7º: También es conveniente representar las rectas de nivel para comprobar que la solución gráfica coincide con la encontrada. Esta conveniencia se convierte en necesidad cunado la región factible es no acotada.
En nuestro caso,
puede comprobarse que las rectas de nivel tienen la misma
pendiente que la recta límite de la restricción x + y
150 ; por tanto, hay
múltiples soluciones.
Paso 8º: Por último, como en la resolución de todo problema es necesario criticar la solución: cerciorarse de que la solución hallada es lógica y correcta.
En este ejemplo, no todos los puntos del segmento CD son soluciones válidas, ya que no podemos admitir valores de x e y no enteros , como ocurriría en el punto (90.5,59.5) .
| Obs.: Si un problema en la forma estándar no indica que se debe realizar por el método analítico o gráfico , seguiremos para su resolución los pasos del 4º al 8º |
| Tipos de soluciones |
Los programas lineales con dos variables suelen clasificarse atendiendo al tipo de solución que presentan. Éstos pueden ser:
| Factibles | Si existe el conjunto de soluciones o valores que satisfacen las restricciones. A su vez, pueden ser: | |
| Con solución única | ||
| En una
urbanización se van a construir casas de dos tipos: A y
B. La empresa constructora dispone para ello de un
máximo de 1800 millones de pesetas, siendo el coste de
cada tipo de casa de 30 y 20 millones, respectivamente.
El Ayuntamiento exige que el número total de casas no
sea superior a 80. Sabiendo que el beneficio obtenido por la venta de una casa de tipo A es 4 millones y de 3 millones por una de tipo B, ¿cuántas casas deben construirse de cada tipo para obtener el máximo beneficio?
Tiene por región factible
la región coloreada.
|
||
| Con solución múltiple | Si existe más de una solución....................................................................................... | |
 Maximizar la función Z = f(x,y) = 4x +
2y sujeta a las restricciones 2x + y
4 , x - y 1 , x 0 , y 0.Los valores de la fucnión objetivo
en cada uno de los vértices son:
|
||
| Con solución no acotada | Cuando no existe límite para la función objetivo | |
 Maximizar la función Z = f(x,y) = x + y
sujeta a las restricciones y 2x , y
x/2 . Tiene por región factible la zona coloreada
que aparece en la figura, que es una región no acotada.
|
||
| No factibles | Cuando no existe el conjunto de soluciones que cumplen las restricciones, es decir, las restricciones son inconsistentes. | |
 Maximizar la función Z = f(x,y) = 3x +
8y sujeta a las restricciones x + y 6 , x + y
2 , x 0 , y
0.No existe la región factible, ya que las
zonas coloreadas que aparecen en la figura son
únicamente soluciones de alguna de las inecuaciones . |
||
| Método del Simplex |
| Es un
procedimiento iterativo que permite ir mejorando la
solución a cada paso. El proceso concluye cuando no es
posible seguir mejorando más dicha solución. Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución. El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta. |
El método del simplex fue creado
en 1947 por el matemático George Dantzig . El método del simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables. El álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la base del método simplex. |
Vamos a resolver mediante el método del simplex el siguiente problema:
| Maximizar | Z= f(x,y)= 3x + 2y |
| sujeto a: | 2x + y 18 |
| 2x + 3y 42 |
|
| 3x + y 24 |
|
| x0 , y 0 |
Se consideran las siguientes fases:
1. Convertir las desigualdades en igualdades
Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
| 2x + y + h = 18 |
| 2x + 3y + s = 42 |
| 3x +y + d = 24 |
2. Igualar la función objetivo a cero
- 3x - 2y + Z = 0
3. Escribir la tabla inicial simplex
En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes de las igualdades obtenidas, una fila para cada restricción y la última fila con los coeficientes de la función objetivo:
| Tabla I . Iteración nº 1 | ||||||
| Base | Variable de decisión | Variable de holgura | Valores solución | |||
| x | y | h | s | d | ||
| h | 2 | 1 | 1 | 0 | 0 | 18 |
| s | 2 | 3 | 0 | 1 | 0 | 42 |
| d | 3 | 1 | 0 | 0 | 1 | 24 |
| Z | -3 | -2 | 0 | 0 | 0 | 0 |
4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base
Si existiesen dos o más coeficientes iguales que cumplan la condición anterior, entonces se elige uno cualquiera de ellos.
Si en la última fila no existiese ningún coeficiente negativo, significa que se ha alcanzado la solución óptima. Por tanto, lo que va a determinar el final del proceso de aplicación del método del simplex, es que en la última fila no haya elementos negativos.
La columna de la variable
que entra en la base se llama columna pivote (En
color verde).
Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y no se puede seguir.
El término de la columna pivote que en la división anterior dé lugar al menor cociente positivo, el 3, ya 8 es el menor, indica la fila de la variable de holgura que sale de la base, d. Esta fila se llama fila pivote (En color verde).
Si al calcular los
cocientes, dos o más son iguales, indica que cualquiera
de las variables correspondientes pueden salir de la
base.
5. Encontrar los coeficientes de la nueva tabla.
Los nuevos coeficientes de x se obtienen dividiendo todos los coeficientes de la fila d por el pivote operacional, 3, que es el que hay que convertir en 1.
A continuación mediante la reducción gaussiana hacemos ceros los restantes términos de su columna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de la función objetivo Z.
También se puede hacer utilizando el siguiente esquema:
Fila del pivote: Nueva fila del pivote= (Vieja fila del pivote) : (Pivote) Resto de las filas: Nueva fila= (Vieja fila) - (Coeficiente de la vieja fila en la columna de la variable entrante) X (Nueva fila del pivote) Veámoslo con un ejemplo una vez calculada la fila del pivote (fila de x en la Tabla II):
|
| Tabla II . Iteración nº 2 | ||||||
| Base | Variable de decisión | Variable de holgura | Valores solución | |||
| x | y | h | s | d | ||
| h | 0 | 1/3 | 1 | 0 | -2/3 | 2 |
| s | 0 | 7/3 | 0 | 1 | -2/3 | 26 |
| x | 1 | 1/3 | 0 | 0 | 1/3 | 8 |
| Z | 0 | -1 | 0 | 0 | 1 | 24 |
Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:
Operando de forma análoga a la anterior obtenemos la tabla:
| Tabla III . Iteración nº 3 | ||||||
| Base | Variable de decisión | Variable de holgura | Valores solución | |||
| x | y | h | s | d | ||
| y | 0 | 1 | 3 | 0 | -2 | 6 |
| s | 0 | 0 | -7 | 0 | 4 | 12 |
| x | 1 | 0 | -1 | 0 | 1 | 6 |
| Z | 0 | 0 | 3 | 0 | -1 | 30 |
Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:
Obtenemos la tabla:
| Tabla IV . Final del proceso | ||||||
| Base | Variable de decisión | Variable de holgura | Valores solución | |||
| x | y | h | s | d | ||
| y | 0 | 1 | -1/2 | 0 | 0 | 12 |
| d | 0 | 0 | -7/4 | 0 | 1 | 3 |
| x | 1 | 0 | -3/4 | 0 | 0 | 3 |
| Z | 0 | 0 | 5/4 | 0 | 0 | 33 |
Como todos los coeficientes de la fila de la función objetivo son positivos, hemos llegado a la solución óptima.
Los solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33. En la misma columna se puede observar el vértice donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base: D(3,12)
* Si en el problema de maximizar apareciesen
como restricciones inecuaciones de la forma: ax +
by  c; multiplicándolas por - 1 se transforman
en inecuaciones de la forma - ax - by  - c y
estamos en el caso anterior * Si en lugar de maximizar se trata de un problema de minimizar se sigue el mismo proceso, pero cambiando el sentido del criterio, es decir, para entrar en la base se elige la variable cuyo valor, en la fila de la función objetivo, sea el mayor de los positivos y se finalizan las iteraciones cuando todos los coeficientes de la fila de la función objetivo son negativos |
Las sucesivas tablas que hemos construido van proporcionando el valor de la función objetivo en los distintos vértices, ajustándose, a la vez, los coeficientes de las variables iniciales y de holgura.
En la primera iteración (Tabla I) han permanecido todos los coeficientes iguales, se ha calculado el valor de la función objetivo en el vértice A(0,0), siendo este 0.
A continuación se desplaza por la
arista AB, calculando el valor de f , hasta llegar a B.
Este paso aporta la Tabla II.
En esta segunda iteración se ha
calculado el valor que corresponde al vértice B(8,0): Z=f(8,0) =
24
Sigue por la arista BC, hasta
llegar a C, donde se para y despliega los datos de la Tabla III.
En esta tercera iteración se ha
calculado el valor que corresponde al vértice C(6,6) :
Z=f(6,6)=30.
Continua haciendo cálculos a
través de la arista CD, hasta llegar al vértice D. Los datos
que se reflejan son los de la Tabla IV.
Concluye con esta tabla, advirtiendo
que ha terminado (antes ha comprobado que la solución no mejora
al desplazarse por la arista DE)
El valor máximo de la función
objetivo es 33, y corresponde a x = 3 e y = 12 (vértice D).
Si calculas el valor de la función objetivo en el vértice E(0,14), su valor no supera el valor 33.
