PROBLEMAS DE OPTIMIZACIÓN LINEAL

Un Problema de optimización lineal

El taller de Joe se especializa en cambios de aceite del motor y regulación del sistema eléctrico. El beneficio por cambio del aceite es $7 y de $15 por regulación. Joe tiene un cliente fijo con cuya flota, le garantiza 30 cambios de aceite por semana. Cada cambio de aceite requiere de 20 minutos de trabajo y $8 de insumos. Una regulación toma una hora de trabajo y gasta $15 en insumos. Joe paga a los mecánicos $10 por hora de trabajo y emplea actualmente a dos de ellos, cada uno de los cuales labora 40 horas por semana. Las compras de insumos alcanzan un valor de $1.750 semanales. Joe desea maximizar el beneficio total. Formule el problema.

Esto es una pregunta de programación linear. Una porción de un cambio del aceite o del ajuste no es factible.
X1 = Cambios del aceite, ajuste
X2 = Ajuste

Maximizar 7X1 + 15X2

Sujeta a:
X1 ³ 30 Cuenta De la Flota
20X1 + 60X2 £ 4800 De trabajo tiempo
8X1 + 15X2 £ 1750 Primas Materias
X1 ³ 0, X2 ³ 0.

El coste de trabajo de $10 por hora no se requiere para formatear el problema desde el beneficio por cambio del aceite y el ajuste toma en la consideración el coste de trabajo.

Método de Solución Gráfica

Dado que somos una especie visual (especialmente la cultura estadounidense), debido a nuestro sistema educativo, muchas de las herramientas de enseñanza escolar utilizadas en la actualidad son de naturaleza gráfica. Les enseñamos a leer mostrándoles figuras de las cosas. Les enseñamos a contar mostrándoles el orden de los números. En consecuencia, nuestros receptores visuales se agudizan a expensas de otras funciones cognitivas. También he descubierto que las personas de negocios responden mejor a los gráficos y a los cuadros que a los números.

Procedimiento para el Método Gráfico de Solución de Problemas de PL:

1. ¿El problema es un problema de PL? La respuesta es afirmativa si y sólo si:Todas las variables están elevadas a la primera potencia y son sumadas o restadas (no dividas ni multiplicadas). La restricción debe adoptar alguna de las siguientes formas (£, ³, o =, es decir que las restricciones de PL siempre están cerradas), y el objetivo debe ser de maximización o minimización.
   Por ejemplo, el siguiente problema no es un problema de PL: Max X, sujeta a <. Este problema tan sencillo no tiene solución.


2. ¿Puedo utilizar el método gráfico? La respuesta es afirmativa si la cantidad de variables de decisión es 1 o 2.


3. Utilice papel milimetrado. Grafique cada restricción, una por una, como si fueran igualdades (como si todo £ y ³, es = ) y luego trace la línea.


4. A medida que se crea cada línea, divida la región en 3 partes con respecto a cada línea. Para identificar la región factible para esta restricción en particular, elija un punto en cualquier lado de la línea y coloque sus coordenadas en la restricción, si satisface la condición, este lado es factible, de lo contrario el otro lado es factible. En el caso de restricciones de igualdad, sólo los puntos sobre la línea son factibles.


5. Elimine los lados que no son factibles.Una vez graficadas todas las restricciones, debe generarse una región factible no vacía (convexa), salvo que el problema sea no factible.


6. Cree (como mínimo) dos líneas de igual valor desde la función objetivo, fijando la función objetivo en dos números distintos cualquiera. Grafique las líneas resultantes. Al mover estas líneas paralelas, encontrará el vértice óptimo (punto extremo), si es que existe.En general, si la región factible se encuentra dentro del primer cuadrante del sistema de coordenadas (es decir si X1 y X2 ³ 0), entonces, para los problemas de maximización, usted debe mover la función objetivo de igual valor (función iso) paralela a sí misma lejos del punto de origen (0, 0), como mínimo, teniendo a la vez un punto en común con la región factible. Sin embargo, para los problemas de minimización, debe realizar lo opuesto, es decir, mover la función objetivo de igual valor (función iso) paralela a sí misma acercándola al punto de origen, a su vez teniendo como mínimo un punto en común con la región factible. El punto común proporciona la solución óptima.

Recuerde que las restricciones de PL proporcionan los vértices y las esquinas. Un vértice es la intersección de 2 líneas o en general, n hiperplanos en problemas de PL con n variables de decisión. Una esquina es un vértice que además es factible.

Un Ejemplo Numérico: El Problema del Carpintero

Maximizar 5 X1 + 3 X2

Sujeta a:
2 X1 + X2 £ 40
X1 + 2 X2 £ 50
and both X1, X2 are non-negative.

Nota: Existe una alternativa del abordaje de la función objetivo de igual valor (función iso) con problemas que tienen pocas restricciones y una región factible acotada. Primero busque todas las esquinas, también llamadas puntos extremos. Luego, evalúe la función objetivo en los puntos extremos para llegar al valor óptimo y a la solución óptima.
Por ejemplo, en el problema del carpintero, la región factible convexa proporciona los puntos extremos con las coordenadas que figuran en la siguiente Tabla:

Valor de la Función Objetivo en cada Esquina o Punto Extremo

Elecciones del Decisor	Coordenadas de los Puntos Extremos	Función de los Ingresos Netos
Cantidad de Mesas o Sillas	X1, X2	5 X1 + 3 X2
No fabricar ninguna mesa ni silla	0, 0	0
Fabricar todas la mesas posibles	20, 0	100
Fabricar todas las sillas posibles	0, 25	75
Fabricar una combinación de productos	10, 20	110

Dado que el objetivo es maximizar, de la tabla anterior surge que el valor óptimo es 110, el cual se obtiene si el carpintero sigue la estrategia óptima de X1 = 10 y X2 = 20.

 Problema de Maximización

Para restricción de £ : cambio en la misma dirección. Vale decir que un aumento en el valor RHS no produce una disminución en el valor óptimo sino que éste aumenta o permanece igual según la restricción sea obligatoria o no obligatoria.
Para restricción de ³ : cambio en la dirección opuesta. Vale decir que un aumento en el valor RHS no produce un aumento en el valor óptimo sino que éste disminuye o permanece igual según la restricción sea obligatoria o no obligatoria.
Para restricción de =: el cambio puede ser en cualquier dirección (ver la sección Más por Menos en este sitio).
                                                 

Problema de Minimización

Para restricción de £ : cambio en la dirección opuesta. Vale decir que un aumento en el valor RHS no produce un aumento del valor óptimo sino que éste disminuye o permanece igual según la restricción sea obligatoria o no obligatoria).
Para restricción de ³ : cambio en la misma dirección. Vale decir que un aumento en el valor RHS no produce una disminución del valor óptimo sino que éste aumenta o permanece igual según la restricción sea obligatoria o no obligatoria.
Para restricción de =: el cambio puede ser en cualquier dirección (ver la sección Más por Menos en este sitio).
                                                         v