Date post: | 29-Dec-2015 |
Category: |
Documents |
Upload: | brayan-esteban-ceron-pastes |
View: | 23 times |
Download: | 0 times |
.1. Introducción.
Muchas personas clasifican el desarrollo de la Programación Lineal (PL) entre los
avances científicos más importantes de mediados del siglo XX. En la actualidad es una
herramienta común que ha ahorrado miles o millones de dólares a muchas compañías y
negocios, incluyendo industrias medianas en distintos países del mundo. ¿Cuál es la
naturaleza de esta notable herramienta y qué tipo de problemas puede manejar?
Expresado brevemente, el tipo más común de aplicación abarca el problema general de
asignar recursos limitados entre actividades competitivas de la mejor manera posible (es
decir, en forma óptima). Este problema de asignación puede surgir cuando deba elegirse el
nivel de ciertas actividades que compiten por recursos escasos para realizarlas. La variedad
de situaciones a las que se puede aplicar esta descripción es sin duda muy grande, y va
desde la asignación de instalaciones productivas a los productos, hasta la asignación de los
recursos nacionales a las necesidades de un país; desde la planeación agrícola, hasta el
diseño de una terapia de radiación; etc. No obstante, el ingrediente común de todas estas
situaciones es la necesidad de asignar recursos a las actividades.
Con frecuencia, seleccionar una alternativa incluye satisfacer varios criterios al
mismo tiempo. Por ejemplo, cuando se compra una pieza de pan se tiene el criterio de
frescura, tamaño, tipo (blanco, integral u otro), costo y rebanado o sin rebanar. Se puede ir
un paso más adelante y dividir estos criterios en dos categorías: restricciones y el objetivo.
Las restricciones son las condiciones que debe satisfacer una solución que está bajo
consideración. Si más de una alternativa satisfacen todas las restricciones, el objetivo se usa
para seleccionar entre todas las alternativas factibles. Cuando se elige una pieza de pan,
pueden quererse 100 gr. de pan blanco rebanado y hecho no antes de ayer. Si varias marcas
satisfacen estas restricciones, puede aplicarse el objetivo de un costo mínimo y escoger las
más barata.
Existen muchos problemas administrativos que se ajustan a este molde de tratar de
minimizar o maximizar un objetivo que está sujeto a una lista de restricciones. un corredor
de inversiones, por ejemplo, trata de maximizar el rendimiento sobre los fondos invertidos
pero las posibles inversiones están restringidas por las leyes y las políticas bancarias. Un
hospital debe planear que las comidas para los pacientes satisfagan ciertas restricciones
sobre sabor, propiedades nutritivas, tipo y variedad, al mismo tiempo que se trata de
minimizar el costo. Un fabricante, al planear la producción futura, busca un costo mínimo
al mismo tiempo cómo cumplir restricciones sobre la demanda del producto, la capacidad
de producción, los inventarios, el nivel de empleados y la tecnología. La PL se ha aplicado
con éxito a estos y otros problemas.
La PL es una técnica determinista, no incluye probabilidades y utiliza un modelo
matemático para describir el problema. El adjetivo lineal significa que todas las funciones
matemáticas del modelo deben ser funciones lineales. En este caso, la palabra
programación no se refiere a programación en computadoras; en esencia es un sinónimo de
planeación. Así, la PL trata la planeación de las actividades para obtener un resultado
óptimo, esto es, el resultado que mejor alcance la meta especificada (según el modelo)
entre todas las opciones de solución. Aunque la asignación de recursos a las actividades es
la aplicación más frecuente, la PL tiene muchas otras posibilidades. De hecho, cualquier
problema cuyo modelo matemático se ajuste al formato general del modelo de PL es un
problema de PL.
Supuestos de la programación lineal.
Existe un número de suposiciones realizadas en cada modelo. La utilidad de un
modelo está directamente relacionada con la realidad de los supuestos.
El primer supuesto tiene que ver con la forma lineal de las funciones. Ya que el
objetivo es lineal, la contribución al objetivo de cualquier decisión es proporcional al valor
de la variable de decisión. Producir dos veces más de producto producirá dos veces más de
ganacia, contratando el doble de páginas en las revistas doblará el costo relacionado con las
revistas. Es una Suposición de Proporción.
Además, la contribución de una variable a la función objetivo es independiente de
los valores de las otras variables. La ganancia con una computadora Notebook es de
$10,750.00, independientemente de cuantas computadoras Desktop se producen. Este es un
Supuesto de Adición.
Análogamente, ya que cada restricción es lineal, la contribución de cada variable al
lado izquierdo de cada restricción es proporcional al valor de la variable e independiente de
los valores de cualquier ora variable.
Estas suposiciones son bastante restrictivas. Veremos, sin embargo, que ser claros y
precisos en la formulación del modelo puede ayudar a manejar situaciones que parecen en
un comienzo como lejanos a estos supuestos.
El siguiente supuesto es la Suposición de ser Divisible. Es posible tomar una
fracción de cualquier variable. Por ejemplo, en un problema de marketing, qué significa
comprar 2.67 avisos en la televisión?. Es posible que la suposición de ser divisible sea
insatisfecha en este ejemplo. O puede ser que tales unidades de 2.67 avisos correspondan a
2,666.7 minutos de avisos, en cuyo caso redondeando la solución serían 2,667 minutos con
una mínima duda que esté cercana a la solución óptima. Si la suposición de divisible no es
válida, entonces se usará la técnica de Programación Lineal Entera.
La última suposición es el Supuesto de Certeza. La Programación Lineal no permite
incertidumbre en los valores.
Será difícil que un problema cumpla con todas las suposiciones de manera exacta.
Pero esto no negará la factibilidad de uso del modelo. Un modelo puede ser aún útil aunque
difiera de la realidad, si se es consistente con los requerimientos más estrictos dentro del
modelo y se tiene claras sus limitaciones al interpretar los resultados.
Existen limitaciones prácticas para el uso de la PL. Una se relaciona con los
cálculos. En general se necesita una computadora. Desafortunadamente, las calculadoras,
aun las programables, son poco útiles, puesto que la PL tiene necesidad de gran cantidad de
memoria o almacenamiento. Si no se tiene acceso a una computadora, se estará limitado a
problemas muy sencillos. La otra limitación se refiere al costo de formular un problema de
PL. En teoría, podría usarse PL, por ejemplo, para hacer las compras semanales de
abarrotes. Sin embargo, sería necesario conocer todas las compras posibles que pueden
realizarse (éstas serían las variables), además de cada restricción como sabor, número de
comidas, vitaminas y proteínas. Es obvio que el costo de obtener todos estos datos excede
lo que se podría ahorrar si se hicieran las compras óptimas. Antes de emprender una
aplicación de PL, debe considerarse la disponibilidad y el costo de los datos necesarios.
2.2. Formulación de modelos de Programación Lineal.
Aunque se ponga en duda, la parte más difícil de PL es reconocer cuándo ésta puede
aplicarse y formular el problema matemáticamente. Una vez hecha esa parte, resolver el
problema casi siempre es fácil.
Para formular un problema en forma matemática, deben expresarse afirmaciones
lógicas en términos matemáticos. Esto se realiza cuando se resuelven “problemas hablados”
al estudiar un curso de álgebra. Algo muy parecido sucede aquí al formular las
restricciones. Por ejemplo, considérese la siguiente afirmación: A usa 3 horas por unidad y
B usa 2 horas por unidad. Si deben usarse todas las 100 horas disponibles, la restricción
será:
3A + 2B = 100
Sin embargo, en la mayoría de las situaciones de negocios, no es obligatorio que se
usen todos los recursos (en este caso, horas de mano de obra). Más bien la limitación es que
se use, cuando mucho, lo que se tiene disponible. Para este caso, la afirmación anterior
puede escribirse como una desigualdad:
3A + 2B ≤ 100
Para que sea aceptable para PL, cada restricción debe ser una suma de variables con
exponente 1. Los cuadrados, las raíces cuadradas, etc. no son aceptables, ni tampoco los
productos de variables. Además, la forma estándar para una restricción pone a todas las
variables del lado izquierdo y sólo una constante positiva o cero del lado derecho. Esto
puede requerir algún reacomodo de los términos. Si, por ejemplo, la restricción es que A
debe ser por los menos el doble de B, esto puede escribirse como:
A ≥ 2B ó A − 2B ≥ 0
Nótese que pueden moverse términos de un lado a otro de las desigualdades como si
fuera un signo de igualdad. Pero al multiplicar una desigualdad por −1, el sentido de esta
desigualdad se invierte. Puede ser necesario hacer esto para que los coeficientes del lado
derecho sean positivos. Por ejemplo, si se quiere que A sea por lo menos tan grande como
B − 2, entonces:
A ≥ B − 2ó A − B ≥ − 2
por último B − A ≥ 2
Una nota final sobre desigualdades: es sencillo convertir una desigualdad en una
ecuación. Todo lo que se tiene que hacer es agregar (o restar) una variable extra. Por
ejemplo:
B − A ≤ 2 es lo mismo que B − A + S = 2
en donde S representa la diferencia, o la holgura, entre B − A y 2. S se llama variable de
holgura. Por otro lado, se restaría una variable de superávit en el caso siguiente:
A − 2B ≥ 0 es lo mismo que A − 2B −S = 0
Algunos métodos de solución (como el Método Símplex) y la mayoría de los
programas de computadora (como el MathProg, que viene en el OR Courseware, que
acompaña al libro “Introducción a la Investigación de Operaciones” de los autores Hillier y
Lieberman) requieren que todas las desigualdades se conviertan en igualdades.
La metodología de PL requiere que todas las variables sean positivas o cero, es
decir, no negativas. Para la mayoría de los problemas esto es real, no se querría una
solución que diga: prodúzcanse menos dos cajas o contrátense menos cuatro personas.
Mientras que no existe un límite en el número de restricciones que puede tener un
problema de PL, sólo puede haber un objetivo. La forma matemática del objetivo se llama
función objetivo. Debe llevar consigo el maximizar o minimizar alguna medida numérica.
Podría ser maximizar el rendimiento, la ganancia, la contribución marginal o los contactos
con los clientes. Podría ser minimizar el costo, el número de empleados o el material de
desperdicio. Con frecuencia el objetivo es evidente al observar el problema.
Como el valor de la función objetivo no se conoce hasta que se resuelve el
problema, se usa la letra Z para representarlo. La función objetivo tendrá, entonces, la
forma:
Maximizar Z = 4A + 6B
ó
Minimizar Z = 2x1 + 5x2
Se analiza una aplicación para ilustrar el formato de los problemas de Programación Lineal.
Planeación de la fuerza de trabajo.
El gerente de personal de “La Tortuga Veloz, S.A. de C.V.”, está analizando la
necesidad de mano de obra semi calificada durante los próximos seis meses. Se lleva 1 mes
adiestrar a una persona nueva. Durante este período de entrenamiento un trabajador regular,
junto con uno en adiestramiento (aprendiz), producen el equivalente a lo que producen 1.2
trabajadores regulares. Se paga $500.00 mensuales a quien está en entrenamiento, mientras
que los trabajadores regulares ganan $800.00 mensuales. La rotación de personal entre los
trabajadores regulares es bastante alta, del 10% mensual.
El gerente de personal debe decidir cuántas personas necesita contratar cada mes
para adiestramiento. En seguida se da el número de meses-hombre necesarios. También se
desea tener una fuerza de trabajo regular de 110 al principio de julio. En cuanto al 1º de
enero, hay 58 empleados regulares.
Mes Meses-hombre requeridos Mes Meses-hombre requeridosEnero 60 Abril 80Febrero 50 Mayo 70Marzo 60 Junio 100
Este problema tiene un aspecto dinámico, ya que la fuerza de trabajo en cualquier
mes depende de la fuerza de trabajo regular y en adiestramiento del mes anterior. Para
cualquier mes, el número total de meses-hombre disponibles se puede expresar como sigue:
Meses-hombre disponibles: Ri + 0.2Ai
en donde: Ri = número de trabajadores regulares al principio del mes
Ai = número de aprendices contratados en el mes.
Entonces los requerimientos de cada mes pueden expresarse por las restricciones:
enero R1 + 0.2A1 ≥ 60febrero R2 + 0.2A2 ≥ 50marzo R3 + 0.2A3 ≥ 60abril R4 + 0.2A4 ≥ 80mayo R5 + 0.2A5 ≥ 70junio R6 + 0.2A6 ≥ 100julio (principio) R7 ≥ 110
Debido a la rotación, el 10% de los trabajadores regulares se van cada mes. Así, el número
de trabajadores regulares disponibles, por ejemplo, al principio de febrero sería:
R2 = 0.9R1 + A1
En la misma forma, pueden escribirse las ecuaciones para el número de trabajadores
disponibles al principio de cada mes:
enero R1 = 58 (dado)febrero R2 = 0.9R1 + A1
marzo R3 = 0.9R2 + A2
abril R4 = 0.9R3 + A3
mayo R5 = 0.9R4 + A4
junio R6 = 0.9R5 + A5
julio R7 = 0.9R6 + A6
El objetivo global del gerente de personal es minimizar el costo. La función objetivo es:
Minimizar: Z = 800(R1 + R2 + R3 + R4 + R5 + R6) + 500(A1 + A2 + A3 + A4 + A5 + A6)
Ahora se tiene el problema en el formato general de PL con 13 variables y 14 restricciones.
Los tomadores de decisiones en las empresas establecen criterios que debe cumplir
una solución y, después, buscan esa solución. En PL, los criterios se expresan como
restricciones. Se exploran las soluciones posibles y se usa la función objetivo para elegir la
mejor de entre aquellas que cumplen con los criterios. La PL se denomina técnica de
optimización, pero optimiza sólo dentro de los límites de las restricciones. En realidad es un
método de satisfacción de criterios.
Forma estándar de los modelos de Programación Lineal.
Supóngase que existe cualquier número (digamos m) de recursos limitados de
cualquier tipo, que se pueden asignar entre cualquier número (digamos n) de actividades
competitivas de cualquier clase. Etiquétense los recursos con números (1, 2, ..., m) al igual
que las actividades (1, 2, ..., n). Sea xj (una variable de decisión) el nivel de la actividad j,
para j = 1, 2, ..., n, y sea Z la medida de efectividad global seleccionada. Sea cj el
incremento que resulta en Z por cada incremento unitario en xj (para j = 1, 2, ..., n). Ahora
sea bi la cantidad disponible del recurso i (para i = 1, 2, ..., m). Por último defínase aij como
la cantidad de recurso i que consume cada unidad de la actividad j (para i = 1, 2, ..., m y j
= 1, 2, ..., n). Se puede formular el modelo matemático para el problema general de asignar
recursos a actividades. En particular, este modelo consiste en elegir valores de x1, x2, ..., xn
para:
Maximizar Z = c1x1 + c2x2 + ... + cnxn,
sujeto a las restricciones:
a11x1 + a12x2 + ... + a1nxn ≤ b1
a21x1 + a22x2 + ... + a2nxn ≤ b2
am1x1 + am2x2 + ... + amnxn ≤ bm
y
x1 ≥ 0, x2 ≥ 0, ..., xn ≥ 0
Ésta se llamará nuestra forma estándar (porque algunos libros de texto adoptan otras
formas) para el problema de PL. Cualquier situación cuya formulación matemática se ajuste
a este modelo es un problema de PL.
En este momento se puede resumir la terminología que usaremos para los modelos
de PL. La función que se desea maximizar, c1x1 + c2x2 + ... + cnxn, se llama función objetivo.
Por lo general, se hace referencia a las limitaciones como restricciones. Las primeras m
restricciones (aquellas con una función del tipo ai1x1 + ai2x2 + ... + ainxn, que representa el
consumo total del recurso i) reciben el nombre de restricciones funcionales. De manera
parecida, las restricciones xj ≥ 0 se llaman restricciones de no negatividad. Las variables xj
son las variables de decisión. Las constantes de entrada, aij, bi, cj, reciben el nombre de
parámetros del modelo.
Otras formas de modelos de Programación Lineal.
Es conveniente agregar que el modelo anterior no se ajusta a la forma natural de
algunos problemas de programación lineal. Las otras formas legítimas son las siguientes:
1. Minimizar en lugar de maximizar la función objetivo:
Minimizar Z = c1x1 + c2x2 + ... + cnxn,
2. Algunas restricciones funcionales con desigualdad en el sentido mayor o igual:
ai1x1 + ai2x2 + ... + ainxn, ≥ bi, para algunos valores de i,
3. Algunas restricciones funcionales en forma de ecuación:
ai1x1 + ai2x2 + ... + ainxn, = bi, para algunos valores de i,
4. Las variables de decisión sin la restricción de no negatividad:
xj no restringida en signo para algunos valores de j.
Cualquier problema que incluya una, varias o todas estas formas del modelo anterior
también se clasifica como un problema de PL, siempre y cuando éstas sean las únicas
formas nuevas introducidas. Puede ser que la interpretación que se ha dado de asignación
de recursos limitados entre actividades que compiten no se aplique, pero
independientemente de la interpretación o el contexto, lo único que se necesita es que la
formulación matemática del problema se ajuste a las formas permitidas. Se verá que estas
otras cuatro formas legales se pueden reescribir en una forma equivalente para que se ajuste
al modelo que se presentó. Entonces, todo problema de PL se puede poner en nuestra forma
estándar si se desea.
2.3. Solución Gráfica de Modelos Lineales con dos Variables.
Para la solución gráfica de programas lineales con dos variables, lo que se tiene que
hacer es trazar un eje de coordenadas cartesianas, para graficar las desigualdades dadas por
el problema, después encontrar el Área de Soluciones Factibles y proceder a graficar la
función objetivo para conocer el valor óptimo (maximizar o minimizar) que será la solución
del problema.
Ejemplo: Problema de mezcla de productos.
Un fabricante está tratando de decidir sobre las cantidades de producción para dos artículos:
mesas y sillas. Se cuenta con 96 unidades de material y con 72 horas de mano de obra.
Cada mesa requiere 12 unidades de material y 6 horas de mano de obra. Por otra parte, las
sillas usan 8 unidades de material cada una y requieren 12 horas de mano de obra por silla.
El margen de contribución es el mismo para las mesas que para las sillas: $5.00 por unidad.
El fabricante prometió construir por lo menos dos mesas.
Paso 1: formulación del problema.
El primer paso para resolver el problema es expresarlo en términos matemáticos en el
formato general de PL. ¿Cuál es el objetivo? Es maximizar la contribución a la ganancia.
Cada unidad de mesas o sillas producidas contribuirá con $5 en la ganancia. Así las dos
alternativas son la producción de mesas y la producción de sillas. Ahora puede escribirse la
función objetivo:
Maximizar Z = 5x1 + 5x2
en donde: x1 = número de mesas producidas
x2 = número de sillas producidas
¿Cuáles son las restricciones o limitaciones del problema? Existen tres restricciones.
Primero, el material está limitado a 96 unidades. Cada mesa se lleva 12 unidades de
material y cada silla usa 8 unidades. La primera restricción es, entonces:
12x1 + 8x2 ≤ 96
La segunda restricción es el total de horas de mano de obra. Una mesa se lleva 6 horas, una
silla 12 horas y se dispone de un total de 72 horas. Así:
6x1 + 12x2 ≤ 72
Existe una limitación más. El fabricante prometió producir por lo menos dos mesas. Esto
puede expresarse como:
x1 ≥ 2
Por último, las restricciones de no negatividad son:
x1 ≥ 0, x2 ≥ 0
Poniendo todo junto el modelo se tiene:
Maximizar Z = 5x1 + 5x2
Restricciones: 12x1 + 8x2 ≤ 96
6x1 + 12x2 ≤ 72
x1 ≥ 2
x1 ≥ 0, x2 ≥ 0
Paso 2: gráfica de las restricciones.
El siguiente paso en el método gráfico es dibujar todas las restricciones en una gráfica. Esto
puede hacerse en cualquier orden. Por conveniencia se comenzará con las restricciones de
no negatividad. Éstas se muestran en la siguiente figura:
En esta gráfica, una solución se representaría por un punto con coordenadas x1 (mesas) y x2
(sillas). Las coordenadas representarían las cantidades de cada artículo que se deben
producir. El cuadrante superior derecho se llama Región Factible puesto que es el único
cuadrante en que pueden estar las soluciones. Los otros tres cuadrantes no son factibles, ya
que requerirían la producción de cantidades negativas de mesas o de sillas o de ambas.
La siguiente restricción es x1 ≥ 2. La manera más sencilla de dibujar las restricciones de
recursos es en dos pasos: (1) convertir una desigualdad en una ecuación y graficar la
ecuación y (2) sombrear el área apropiada arriba y abajo de la línea que resulta en el paso 1.
Convertir una igualdad en una ecuación aquí significa ignorar la parte de “mayor que” o
“menor que” de la restricción.
Así, en el ejemplo, x1 ≥ 2 se convierte en x1 = 2. Esta ecuación está trazada en la siguiente
figura:
Cualquier punto en la línea x1 = 2 satisface la ecuación. Sin embargo, la restricción es más
amplia, ya que cualquier punto x1 > 2 también la cumplirá. Esto incluye todos los puntos
que están a la derecha de la línea x1 = 2. Entonces, la región factible incluye todos los
valores de x1 que están sobre o a la derecha de la línea x1 = 2.
La limitación sobre las horas de mano de obra es la siguiente restricción. Como antes,
primero se convierte en una ecuación: 6x1 + 12x2 = 72. Puede graficarse esta línea si se
encuentran dos puntos sobre ella. El par de puntos más sencillos de localizar son las
intersecciones con los ejes X1 y X2. Para encontrar la intersección con el eje X2 se hace x1 =
0. La ecuación se reduce, entonces, a:
12x2 = 72
x2 = 6
La intersección con el eje X1 se encuentra haciendo x2 = 0. Así:
6x1 = 72
x1 = 12
Estos dos puntos y la línea que los une se muestran en la siguiente figura:
Cualquier punto que está sobre o abajo de esta línea cumplirá con la restricción. Cualquier
punto arriba de esta línea requerirá más de 72 horas de mano de obra y no es aceptable. En
la siguiente figura se combina esta restricción con la anterior. En la región factible, ambas
restricciones se cumplen.
La última restricción es la de material. Siguiendo el procedimiento anterior, primero se
encuentran las intersecciones para la igualdad. Éstas son x1 = 0, x2 = 12 y x1 = 8, x2 =0. Se
localizan los dos puntos en la gráfica; se traza la línea, y como la restricción es del tipo
menor o igual que, se sombrea el área que está abajo de la línea. El resultado se muestra en
la siguiente figura:
Cualquier solución que esté en la frontera o dentro del área sombreada cumplirá con todas
las restricciones. Ahora se utilizará la función objetivo para seleccionar la solución óptima.
Paso 3: obtención de la solución óptima: líneas de indiferencia.
Para encontrar la solución óptima, se grafica la función objetivo en la misma gráfica de las
restricciones. La función objetivo en este problema es Z = 5x1 + 5x2. Como todavía no se
conoce el máximo valor factible de Z, no puede trazarse el óptimo de la función objetivo.
No obstante, es posible suponer algunos valores para Z y graficar las líneas resultantes. En
la siguiente figura se muestran las líneas para Z = 25 yZ = 50:
Las líneas de este tipo se llaman líneas de indiferencia, porque cualquier punto sobre una
línea dada da la misma ganancia total. Nótese que la distancia perpendicular del origen a la
línea aumenta al aumentar el valor de Z. También, todas las líneas de indiferencia son
paralelas entre sí. Estas propiedades gráficas pueden usarse para resolver el problema.
En la siguiente figura, se ilustran todas las restricciones y las dos líneas de indiferencia
supuestas. En la gráfica puede observarse que la línea de indiferencia para Z = 50 está
completamente fuera de la región factible. Para Z = 25, parte de la línea cae dentro de la
región factible. Por tanto, existe alguna combinación de x1 y x2 que satisface todas las
restricciones y da una ganancia total de $25. Por inspección, puede observarse que hay
ganancias más altas que son factibles.
Imaginando que la línea de indiferencia Z = 25 se mueve hacia la línea Z = 50, de las
propiedades de la gráfica que se hicieron notar antes, el punto óptimo estará sobre la línea
de indiferencia más lejana al origen pero que todavía toque la región factible. Esto se
muestra en la siguiente figura:
Con el punto óptimo localizado gráficamente, la única tarea que queda es encontrar las
coordenadas del punto. Nótese que el punto óptimo está en la intersección de las líneas de
restricción para materiales y horas de mano de obra. Las coordenadas de este punto se
pueden encontrar resolviendo el sistema de ecuaciones que forman estas dos restricciones
utilizando cualquiera de los métodos de solución (suma y resta, sustitución o igualación).
Las coordenadas de este punto resultan ser (6, 3). La sustitución de este punto en la función
objetivo da la ganancia máxima:
Z = 5(6) + 5(3) = $45
Resumen del método gráfico.
Para resolver gráficamente problemas de programación lineal:
1. Exprésense los datos del problema como una función objetivo y restricciones.
2. Grafíquese cada restricción.
3. Localícese la solución óptima.
Uso del método gráfico para minimización.
Consideremos un Problema de PL en el cual el objetivo es minimizar costos. La
solución del problema de minimización sigue el mismo procedimiento que la de problemas
de maximización. La única diferencia es que ahora se quiere el menor valor posible para la
función objetivo. Supóngase que se tiene el siguiente problema:
Ejemplo: Problema de dieta.
Un comprador está tratando de seleccionar la combinación más barata de dos
alimentos, que debe cumplir con ciertas necesidades diarias de vitaminas. Los
requerimientos vitamínicos son por lo menos 40 unidades de vitamina W, 50 unidades de
vitamina X y 49 unidades de vitamina Y. Cada onza del alimento A proporciona 4 unidades
de vitamina W, 10 unidades de vitamina X y 7 unidades de vitamina Y; cada onza del
alimento B proporciona 10 unidades de W, 5 unidades de X y 7 unidades de Y. El alimento
A cuesta 5 pesos/kilogramo y el alimento B cuesta 8 pesos/kilogramo.
Paso 1: formulación del problema.
La meta en este problema es encontrar la manera menos costosa para satisfacer las
necesidades vitamínicas. Las dos alternativas disponibles son los alimentos A y B.
Matemáticamente la función objetivo es:
Minimizar Z = 5A + 8B
Las restricciones son los requerimientos mínimos de las tres vitaminas. Éstas se muestran
enseguida:
Restricciones: 4A + 10B ≥ 40 vitamina W
10A + 5B ≥ 50 vitamina X
7A + 7B ≥ 49 vitamina Y
A ≥ 0, B ≥ 0 no negatividad
Paso 2: gráfica de las restricciones.
El procedimiento para graficar es el mismo que se usó antes: (1) graficar cada ecuación de
restricción; (2) graficar el área apropiada. Para la primera restricción la ecuación es 4A +
10B = 40. Las dos intersecciones con los ejes son (0,4) y (10,0). Esta línea se muestra en la
siguiente figura:
La restricción pide 40 unidades o más de la vitamina W. Cualquier punto que esté arriba de
la línea de restricción será factible y todos los puntos que quedan abajo de esa línea serán
aceptables. En la siguiente figura se muestra la región factible:
Después se grafica la restricción para la vitamina X. La ecuación 10A + 5B = 50 tiene
intersecciones con los ejes en (0,10) y (5,0). En la siguiente figura se ilustran las
restricciones para las vitaminas W y X. Nótese que las soluciones que quedan en las áreas a
o b no son factibles, ya que quedarían abajo de las líneas de restricción.
Al agregar la tercera restricción, este segundo paso queda terminado, como se muestra en la
siguiente figura:
Paso 3: localización de la solución óptima.
En la siguiente figura se muestra la frontera extrema más dos líneas de indiferencia, las de
Z = 40 pesos y Z = 60 pesos. La frontera extrema está formada por los puntos a, b, c y d,
puesto que éstos son los puntos de intersección factibles más cercanos al origen.
Gráficamente, el objetivo de minimizar el valor de Z significa ajustar una línea de
indiferencia tan cerca del origen como sea posible. En la figura anterior puede observarse
que existen muchas soluciones posibles para Z = 60, pero ninguna para Z = 40. Imaginando
mover la línea Z = 60 hacia el origen, el último punto de contacto con la frontera extrema
será el punto b. Entonces, el punto b es la solución óptima. En la figura anterior se observa
que el punto b es la intersección de dos líneas:
(1) 4A + 10B = 40
(2) 7A + 7B = 49
Resolviendo el sistema de ecuaciones:
Multiplíquese la ecuación (1) por 7: (3) 28A + 70B = 280
Multiplíquese la ecuación (2) por – 4: (4) –28A – 28B = –196
42B
= 84
B = 2
Sustitúyase en la ecuación (1): 4A + 10(2) = 40
A = 5
La solución menos costosa es 5 kilogramos de alimento A y 2 kilogramos de alimento B. El costo total de esta combinación es:
Z = 5A + 8B = 5(5) + 8(2) = 25 + 16 = 41 pesos
Si se usa el método de prueba y error para localizar la solución óptima, se deben encontrar
las coordenadas de los puntos a, b, c, y d. Se debe calcular después el valor de la función
objetivo para cada punto. A continuación se muestran los resultados de este procedimiento:
Resultados de prueba y error
Punto Coordenadas Z = 5A +
8Ba A = 10, B = 0 50
b A = 5, B = 2 41 menor
c A =3, B = 4 47
d A = 0, B = 10 80
CASOS ESPECIALES.
Múltiples soluciones.
Maximizar Z = 3x1 + 2x2 sujeta a x1 ≤ 4 x2 ≤ 12 3x1 + 2x2 ≤ 18 x1 ≥ 0, x2 ≥ 0
Ninguna solución factible.
Maximizar Z = 3x1 + 2x2 sujeta a 1/40x1 + 1/60x2 ≤ 1 1/50x1 + 1/50x2 ≤ 1 x1 ≥ 30 x2 ≥ 20 x1 ≥ 0, x2 ≥ 0
Área o Región de Soluciones Factibles no Acotada.
Maximizar Z = 2x1 – x2 sujeta a x1 – x2 ≤ 1 2x1 + x2 ≥ 6 x1 ≥ 0, x2 ≥ 0
Regresar a la Página Prin cipal
ASPECTOS BÁSICOS DE LA PROGRAMACIÓN LINEAL
Muchas personas clasifican el desarrollo de la programación lineal entre los avances
científicos más importantes de mediados del siglo XX, su impacto desde 1950 ha sido
extraordinario. En la actualidad es una herramienta de uso normal que ha ahorrado miles o
millones de pesos a muchas compañías o negocios, incluyendo empresas medianas en los
distintos países industrializados del mundo; su aplicación a otros sectores de la sociedad se
está ampliando con rapidez. Una proporción muy grande de los cálculos científicos en
computadoras está dedicada al uso de la programación lineal.
¿Cuál es la naturaleza de esta notable herramienta y qué tipos de problemas puede manejar.
Expresado brevemente, el tipo más común de aplicación abarca el problema general de asignar
recursos limitados entre actividades competitivas de la mejor manera posible (es decir, en
forma óptima). Con más precisión, este problema incluye elegir el nivel de ciertas actividades
que compiten por recursos escasos necesarios para realizarlas. Después, los niveles de
actividad elegidos dictan la cantidad de cada recurso que consumirá cada una de ellas. La
variedad de situaciones a las que se puede aplicar esta descripción es sin duda muy grande, y
va desde la asignación de instalaciones de producción a los productos, hasta la asignación de
los recursos nacionales a las necesidades de un país; desde la selección de una cartera de
inversiones, hasta la selección de los patrones de envío; desde la planeación agrícola, hasta el
diseño de una terapia de radiación, etc. No obstante, el ingrediente común de todas estas
situaciones es la necesidad de asignar recursos a las actividades eligiendo los niveles de las
mismas.
La programación lineal utiliza un modelo matemático para describir el problema. El adjetivo
lineal significa que todas las funciones matemáticas del modelo deber ser funciones lineales.
En este caso, las palabra programación no se refiere a programación en computadoras; en
esencia es un sinónimo de planeación. Así, la programación lineal trata la planeación de las
actividades para obtener un resultado óptimo, esto es, el resultado que mejor alcance la meta
especificada (según el modelo matemático) entre todas las alternativas de solución.
Aunque la asignación de recursos a las actividades es la aplicación más frecuente, la
programación lineal tiene muchas otras posibilidades. de hecho, cualquier problema cuyo
modelo matemático se ajuste al formato general del modelo de programación lineal es un
problema de programación lineal. Aún más, se dispone de un procedimiento de solución
extraordinariamente eficiente llamado método simplex, para resolver estos problemas, incluso
los de gran tamaño. Estas son algunas causas del tremendo auge de la programación lineal en
las últimas décadas.
MODELO DE PROGRAMACIÓN LINEAL
Los términos clave son recursos y actividades, en donde m denota el número de distintos tipos
de recursos que se pueden usar y n denota el número de actividades bajo consideración.
Algunos ejemplos de recursos son dinero y tipos especiales de maquinaria, equipo, vehículos y
personal. Los ejemplos de actividades incluyen inversión en proyectos específicos, publicidad
en un medio determinado y el envío de bienes de cierta fuente a cierto destino. En cualquier
aplicación de programación lineal, puede ser que todas las actividades sean de un tipo general
(como cualquiera de los ejemplos), y entonces cada una correspondería en forma individual a
las alternativas específicas dentro de esta categoría general.
El tipo más usual de aplicación de programación lineal involucra la asignación de recursos a
ciertas actividades. La cantidad disponible de cada recurso está limitada, de forma que deben
asignarse con todo cuidado. La determinación de esta asignación incluye elegir los niveles de
las actividades que lograrán el mejor valor posible de la medida global de efectividad.
Ciertos símbolos se usan de manera convencional para denotar las distintas componentes de
un modelo de programación lineal. Estos símbolos se enumeran a continuación, junto con su
interpretación para el problema general de asignación de recursos a actividades.
Z = valor de la medida global de efectividad
xj = nivel de la actividad j (para j = 1,2,...,n)
cj = incremento en Z que resulta al aumentar una unidad en el nivel de la actividad j
bi = cantidad de recurso i disponible para asignar a las actividades (para i = 1,2,...,m)
aij = cantidad del recurso i consumido por cada unidad de la actividad j
El modelo establece el problema en términos de tomar decisiones sobre los niveles de las
actividades, por lo que x1,x2,....,xn se llaman variables de decisión. Los valores de cj, bi y aij
(para i = 1,2,....,m y j = 1,2,....,n) son las constantes de entrada al modelo. Las cj, bi y aij
también se conocen como parámetros del modelo.
FORMA ESTÁNDAR DEL MODELO
Ahora se puede formular al modelo matemático para este problema general de asignación de
recursos a actividades. En Datos necesarios para un modelo de programación lineal que
maneja la asignación de recursos a actividades particular, este modelo consiste en elegir
valores de x1,x2,....,xn para:
optimizar (maximizar o minimizar) Z = c1x1 + c2x2 +....+ cnxn,
sujeta a las restricciones:
a11x1 + a12x2 +....+ a1nxn < b1
a21x1 + a22x2 +....+ a2nxn < b2
.
.
.
am1x1 + am2x2 +....+ amnxn < bm
X1 ³ 0, X2 ³0, ..., Xn ³0.
SUPOSICIONES DEL MODELO DE PROGRAMACIÓN LINEALSUPOSICIONES DEL MODELO DE PROGRAMACIÓN LINEAL
PROPORCIONALIDAD
La contribución de cada actividad al valor de la función objetivo Z es proporcional al nivel de
actividad xj, como lo representa el término cjxj en la función objetivo. De manera similar, la
contribución de cada actividad al lado izquierdo de cada restricción funcional es proporcional
al nivel de la actividad xj, en la forma en que lo representa el término aijxj en la restricción. En
consecuencia, esta suposición elimina cualquier exponente diferente a 1 para las variables en
cualquier término de las funciones (ya sea la función objetivo o la función en el lado izquierdo
de las restricciones funcionales) en un modelo de programación lineal.
ACTIVIDAD
Establece que la entrada y salida de un recurso en particular al conjunto de actividades, deben
ser la misma cantidad; o sea, que las actividades transforman los recursos y no los crean o
destruyen. Esta suposición garantiza que la contribución total tanto a la función objetivo
como a las restricciones, es igual a la suma de las contribuciones individuales. Cuando en un
problema dado no se tenga la aditividad puede recurrirse al empleo de otras técnicas de la
programación matemática, dependiendo de cada caso en particular.
ADITIVIDAD
Cada función en un modelo de programación lineal (ya sea la función objetivo o el lado
izquierdo de las restricciones funcionales) es la suma de las contribuciones individuales de las
actividades respectivas.
DIVISIBILIDAD
Las variables de decisión en un modelo de programación lineal pueden tomar cualquier valor,
incluyendo valores no enteros, que satisfagan las restricciones funcionales y de no
negatividad. Así, estas variables no están restringidas a sólo valores enteros. Como cada
variable de decisión representa el nivel de alguna actividad, se supondrá que las actividades se
pueden realizar a niveles fracciónales.
LIMITACIONES DEL MODELO DE PROGRAMACIÓN LINEALLIMITACIONES DEL MODELO DE PROGRAMACIÓN LINEAL
MODELO DETERMINÍSTICOMODELO DETERMINÍSTICO
El modelo de PL involucra únicamente tres tipos de parámetros: Cj, aij y bi; de ahí su sencillez
y gran aplicación. Sin embargo, el valor de dichos parámetros debe ser conocido y constante.
Cuando el valor de los parámetros tiene un cierto riesgo o incertidumbre, pude utilizarse la
programación paramédica, la programación estocástica, o realizarse un análisis de
sensibilidad.
MODELO ESTÁTICOMODELO ESTÁTICO
En algunos modelos matemáticos se han empleado con éxito las ecuaciones diferenciales,
para inducir la variable tiempo en ellos. En este sentido, puede decidirse que la PL utiliza un
modelo estático, ya que la variable tiempo no se involucra formalmente. Adquiriendo un
poco de experiencia en la formulación de modelos de PL, puede imbuirse la temporabilidad
mencionada, con el uso de subíndices en las variables.
MODELO QUE NO SUB-OPTIMIZAMODELO QUE NO SUB-OPTIMIZA
Debido a la forma que se plantea el modelo de PL, o encuentra la solución óptima o declara
que ésta no existe. Cuando no es posible obtener una solución óptima y se debe obtener
alguna, se recurre a otra técnica más avanzada que la PL, la cual se denomina programación
lineal por metas.
Regresar a la Página principal
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 0Conjunto 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:
• De número : x + y 80 • De fermentación: 0.5x + 0.2y 9000 • Las variables x e y han de ser, lógicamente, no negativas; es decir: x 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:Optimizar (maximizar o minimizar) una función objetivo, función lineal de varias variables, sujeta a:una serie de restricciones, expresadas por inecuaciones lineales.
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 4, vemos que no la satisface: 0 + 0 = 0 < 4 . Por tanto, el conjunto de soluciones de la inecuación es el semiplano situado por encima de la recta r : x + y = 4 .
Procedemos como en el paso anterior. Las coordenadas (0,0) satisfacen la inecuación y 4 ( 0 4) . Por tanto, el conjunto de soluciones de la inecuación es el semiplano que incluye al punto O.
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 x ( y = 0 < 1 = x ). Por tanto, el conjunto solución de esta inecuación es el semiplano determinado por la recta t que no incluye al punto (1,0).
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:
• La recta s : x = 4 pasa por el punto (4,0) y es paralela al eje Y. Las soluciones de 0 x 4 son los puntos entre el eje Y y la recta x = 4
• La recta r : y = 4 pasa por el punto (0,4) y es paralela al eje X. Las soluciones de 0 y 4 son los puntos entre el eje X y la recta y = 4
• La recta t : y = x/2 pasa por los puntos (0,0) y (2,1) . Las soluciones de y 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.
En un programa lineal con dos variables, si existe una solución única que optimice la función objetivo, ésta se encuentra en un punto extremo (vértice) de la región factible acotada, nunca en el interior de dicha región.
Si la función objetivo toma el mismo valor óptimo en dos vértices, también toma idéntico valor en los puntos del segmento que determinan.
En el caso de que la región factible no es acotada, la función lineal objetivo no alcanza necesariamente un valor óptimo concreto, pero, si lo hace, éste se encuentra en uno de los vértices de la región
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:
• B no cumple la segunda restricción 2x + 5y 30 , ya que 2·0 + 5·8 = 40 . Por tanto, el punto B no es un vértice de la región factible.
• E no cumple la primera restricción 4x + 5y 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.
• Un mínimo de 20 bidones de aceite de girasol: x 20 • Un mínimo de 40 bidones de aceite de oliva: y 40 • 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: y x/2 • La capacidad total del almacén es de 150 bidones: x + y 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?
• Variables: x = nº de casas tipo A ; y = nº de casas tipo B
• Función objetivo: Maximizar Z = f(x,y) = 4x + 3y• Conjunto de restricciones: El coste total 30x + 20y
1800 . El Ayuntamiento impone x + y 80 . De no negatividad: x 0 , y 0.
Tiene por región factible la región coloreada.Si hallamos los valores de la función objetivo en cada uno de los vértices :f(O) = f(0,0) = 0 ; f(C)=f(60,0) = 240 ;f(D) = f(20,60) = 260 ; f(E) = f(0,80) = 240La solución es única, y corresponde al vértice para el que la función objetivo toma el valor máximo. En este caso es el vértice D(20,60). Por tanto se deben construir 20 casas de tipo A y 60 de tipo B con un coste de 260 millones de pesetas.
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:f(O)=f(0,0) = 0 , f(A) = f(1,0) = 4 ; f(B)=f(5/3,2/3) = 8 , f(C) = f(0,4) = 8La función objetivo alcanza el valor máximo en los vértices B y C, por tanto, en todos los puntos del segmento BC.Hay infinitas soluciones, solución múltiple, que corresponden a los
puntos del segmento situado entre dos vértices de la región factible.En estos casos, como ya vimos en el capítulo anterior, la función objetivo es paralela a una de las restricciones.
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.La función crece indefinidamente para valores crecientes de x e y.En este caso no existe un valor extremo para la función
objetivo, por lo que puede decirse que el problema carece de solución.Para que suceda esta situación la región factible debe estar 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 .Por tanto, el conjunto de soluciones del sistema de desigualdades no determina ninguna región factible.
Este tipo de problemas carece de solución.
Método del SimplexEs 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:
MaximizarZ= f(x,y)= 3x +
2y
Sujeto a: 2x + y 18
2x + 3y 42
3x + y 24
x 0 , 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 = 182x + 3y + s = 423x +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
A. Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto). En nuestro caso, la variable x de coeficiente - 3.
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).
B. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. En nuestro caso: 18/2 [=9] , 42/2 [=21] y 24/3 [=8]
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.
C. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3.
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):
Vieja fila de s 2 3 0 1 0 42 - - - - - -Coeficiente 2 2 2 2 2 2 x x x x x xNueva fila pivote 1 1/3 0 0 1/3 8 = = = = = =Nueva fila de s 0 7/3 0 1 -2/3 26
Tabla II . Iteración nº 2Base 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:
A. La variable que entra en la base es y, por ser la variable que corresponde al coeficiente -1B. Para calcular la variable que sale, dividimos los términos de la última columna entre los
términos correspondientes de la nueva columna pivote:2:1/3 [=6] , 26:7/3 [=78/7] y 8:1/3 [=8] y como el menor cociente positivo es 6, tenemos que la variable de holgura que sale es h.
C. El elemento pivote, que ahora hay que hacer 1, es 1/3.
Operando de forma análoga a la anterior obtenemos la tabla:
Tabla III . Iteración nº 3Base 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:
A. La variable que entra en la base es d, por ser la variable que corresponde al coeficiente -1B. Para calcular la variable que sale, dividimos los términos de la última columna entre los
términos correspondientes de la nueva columna pivote:6/(-2) [=-3] , 12/4 [=3], y 6:1 [=6] y como el menor cociente positivo es 3, tenemos que la variable de holgura que sale es s.
C. El elemento pivote, que ahora hay que hacer 1, es 4.
Obtenemos la tabla:
Tabla IV . Final del procesoBase 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
Interpretación geométrica del método del simplex
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.
Regresar a la Página Principal
MÉTODO DE SOLUCIÓN GRÁFICO regresar
Introducción. La PL es una técnica mediante la cual se toman decisiones, reduciendo el problema bajo estudio a un modelo matemático general, el cual debe ser resuelto por métodos cuantitativos.
En desarrollo de este capítulo se aplicarán la solución de dichos modelos aplicando diversas técnicas como: el método gráfico, método simplex, método matricial, técnica de la gran M.
Además se desarrollara la aplicación de variables artificiales y obtención de soluciones para identificar a que tipo de clasificación pertenecen. Por medio de dichos modelos de solución se podrá obtener las solución adecuada para cada problema y facilitar la toma de decisiones.
Método gráfico.
El método gráfico se utiliza para la solución de problemas de PL, representando geométricamente a las restricciones, condiciones técnicas y el objetivo.
El modelo se puede resolver en forma gráfica si sólo tiene dos variables. Para modelos con tres o más variables, el método gráfico es impráctico o imposible.
Cuando los ejes son relacionados con las variables del problema, el método es llamado método gráfico en actividad. Cuando se relacionan las restricciones tecnológicas se denomina método gráfico en recursos.
Los pasos necesarios para realizar el método son nueve: 1. graficar las soluciones factibles, o el espacio de soluciones (factible), que satisfagan todas las restricciones en forma simultánea. 2. Las restricciones de no negatividad Xi>= 0 confían todos los valores posibles. 3. El espacio encerrado por las restricciones restantes se determinan sustituyendo en primer término <= por (=) para cada restricción, con lo cual se produce la ecuación de una línea recta. 4. trazar cada línea recta en el plano y la región en cual se encuentra cada restricción cuando se considera la desigualdad lo indica la dirección de la flecha situada sobre la línea recta asociada. 5. Cada punto contenido o situado en la frontera del espacio de soluciones satisfacen todas las restricciones y por consiguiente, representa un punto factible. 6. Aunque hay un número infinito de puntos factibles en el espacio de soluciones, la solución óptima puede determinarse al observar la dirección en la cual aumenta la función objetivo. 7. Las líneas paralelas que representan la función objetivo se trazan mediante la asignación de valores arbitrarios a fin de determinar la pendiente y la dirección en la cual crece o decrece el valor de la función objetivo.
Ejemplo. Maximizar Z = 3X1 + 2X2 restricciones : X1 + 2X2 <=6 (1) 2X1 + X2 <=8 (2) -X1 + X2 <=1 (3) X2 <= 2 (4) X1 >= 0 (5) X2 >= 0 (6)
Convirtiendo las restricciones a igualdad y representandolas gráficamente se tiene:
X1 + 2X2 = 6 (1) 2X1 + X2 = 8 (2) -X1 + X2 = 1 (3) X2 = 2 (4) X1 = 0 (5) X2 = 0 (6)
Figura 1 Espacio de solución presentada con WinQsb
Figura 2 Determinación de solución
Maximizar Z = 3X1 + 2X2
Punto (X1, X2) Z A (0, 0) 0 B (4, 0) 12 C (3.3, 1.3) 12.6 ( óptima ) D (2, 3) 12 E (1, 3) 9 F (0, 2) 4
Tabla 2. Solución Método Gráfico
Para obtener la solución gráfica, después de haber obtenido el espacio de solución y graficada la función objetivo el factor clave consiste en decidir la dirección de mejora de la función objetivo.
MÉTODO SIMPLEX. (Dantzig 1940) regresar
En la solución gráfica observamos que la solución óptima está asociada siempre con un punto extremo del espacio de soluciones. El método simplex está basado fundamentalmente en este concepto.
Careciendo de la ventaja visual asociada con la representación gráfica del espacio de soluciones, el método simplex emplea un proceso iterativo que principia en un punto extremo factible, normalmente el origen, y se desplaza sistemáticamente de un punto extremo factible a otro, hasta que se llega por último al punto óptimo.
Existen reglas que rigen la selección del siguiente punto extremo del método simplex: 1. El siguiente punto extremo debe ser adyacente al actual. 2. La solución no puede regresar nunca a un punto extremo considerado con la anterioridad.
El algoritmo simplex da inicio en el origen, que suele llamarse solución inicial. Después se desplaza a un punto extremo adyacente. La elección específica de uno a otro punto depende de los coeficientes de la función objetivo hasta encontrar el punto óptimo.
Al aplicar la condición de optimidad a la tabla inicial seleccionamos a Xi como la variable que entra. En este punto la variable que sale debe ser una de las variables artificiales.
Los pasos del algoritmo simplex son ( 10 ) :
1. Determinar una solución básica factible inicial. 2. Prueba de optimidad: determinar si la solución básica factible inicial es óptima y sólo si todos los coeficientes de la ecuación son no negativos ( >= 0 ). Si es así, el proceso termina; de otra manera se lleva a cabo otra interacción para obtener la nueva solución básica factible inicial. 3. Condición de factibilidad.- Para todos los problemas de maximización y minimización, variable que sale es la variable básica que tiene la razón más pequeña (positiva). Una coincidencia se anula arbitrariamente. 4. Seleccionar las variables de holgura como las variables básicas de inicio. 5. Selecciona una variable que entra de entre las variables no básicas actuales que, cuando se incrementan arriba de cero, pueden mejorar el valor de la función objetivo. Si no existe la solución básica es la óptima, si existe pasar al paso siguiente. 6. Realizar el paso iterativo. a) Se determina la variable básica entrante mediante la elección de la variable con el coeficiente negativo que tiene el valor mayor valor absoluto en la ecuación. Se enmarca la columna correspondiente a este coeficiente y se le da el nombre de columna pivote. b) Se determina la variable básica que sale; para esta, se toma cada coeficiente positivo (>0) de la columna enmarcada, se divide el lado derecho de cada renglón entre estos coeficientes, se identifica la ecuación con el menor cociente y se selecciona la variable básica para esta ecuación. c) Se determina la nueva solución básica factible construyendo una nueva tabla en la forma apropiada de eliminación de Gauss, abajo de la que se tiene. Para cambiar el coeficiente de la nueva variable básica en el renglón pivote a 1, se divide todo el renglón entre el número pivote, entonces
renglón pivote nuevo = renglón pivote antiguo número pivote
para completar la primera iteración es necesario seguir usando la eliminación de Gauss para obtener coeficientes de 0 para la nueva variable básica Xj en los otros renglones, para realizar este cambio se utiliza la siguiente fórmula:
renglón nuevo = renglón antiguo - ( coeficiente de la columna pivote X renglón pivote nuevo)
cuando el coeficiente es negativo se utiliza la fórmula:
renglón nuevo = renglón antiguo + (coeficiente de la columna pivote X renglón pivote nuevo)
TABLA SIMPLEX como se capturaría la solución básica factible inicial en el siguiente ejemplo:
sea:
Maximizar Z = 2X1+4X2 sujeto a:
2X1+ X2<= 230 X1+ 2X2<= 250 X2<= 120 todas las X1,X2>=0
BASE Z X1 X2 S1 S2 S3 SOLUCIÓN RAZÓN
Z 0 -2 -4 0 0 0 0 0
S1 0 2 1 1 0 0 230 230/1
S2 0 1 2 0 1 0 250 250/2
S3 0 0 1 0 0 1 120 120/1
Seleccione la variable que entra y la variable que sale de la base:
Entra X2 y sale S3, se desarrolla la nueva tabla solución y se continua el proceso iterativo hasta encontrar la solución optima si es que está existe.
Tabla Optima:
BASE Z X1 X2 S1 S2 S3 SOLUCIÓN RAZÓN
Z 0 0 0 0 2 0 500
S1 0 0 0 1 -2 3 90
X1 0 1 0 0 1 -2 10
X2 0 0 1 0 0 1 120
Solución: Z = $500 fabricando X1=10 X2=120 Sobrante de S1 = 90 Tipo de solución: Optima Múltiple
Solución de problemas en donde la solución continua no sea aplicable
regresar
Uso de paquetes computacionales en la solución e interpretación de los resultados
Puedes bajar el tutorial de WinQsb+
Tutorial WinQsb+
regresar
WinQsb+: Debe bajar el Software de apoyo para resolver los modelos de programación lineal.
Interpretación de los resultados: Veamos la salida de un modelo que involucra la planeación de la producción, en donde se desean construir mesas y sillas el recurso disponible es 30 m2 de madera por semana, 48 horas por semana; la demanda de las sillas es de 5 unidades y la de mesas de 10 unidades, la utilidad que se obtiene por las mesas es de $10 y por las sillas de $8, ademas para construir la mesa se ocupa lo siguiente: 4.5 m2 de madera por unidad, 6 horas por unidad. Para la silla se ocupan: 1.5 m2 de madera por unidad y 3 horas por cada unidad fabricada. Con esta información se desarrolla el modelo siguiente:
Max Z = 10X1+8X2 s.a. 4.5X1+1.5X2 <= 30 6.0X1+3.0X2 <= 48 toda X1,X2 >=0
El reporte final de este modelo es el siguiente (por WinQsb)
Decision Variable
Solution Value
Unit Cost or Profit cj
Total Contribution
Reduced
Cost
Basis Status
Allowable Min cj
Allowable Max cj
X1 0 10.0000 0 -6.0000 at bound -M 16.0000
X2 16.0000 8.0000 128.0000 0 basic 5.0000 M
Objetive Function (Max) = 128.0000
ConstraintLeft
Hand Side
DirectionRigth Hand
SideSlack or Surplas
Shadow Price
Allowable
Min. RHS
Allowable Max. RHS
C1 24.0000 <= 30.0000 6.0000 0 24.0000 M
C2 48.0000 <= 48.0000 0 2.6667 0 60.0000
INTERPRETACIÓN DE LA SALIDA:
Información de la Función Objetivo:
Decision Variable (Variable de Decisión): Son las variables que se han definido en la formulación del problema en este caso representan al producto X1 = mesas y X2= sillas.
Solution Value (Valor de la solución): Cantidad de mesas y sillas a fabricar, el problema se resuelve y nos indica que para obtener la mejor solución en términos de la utilidad, se necesitan fabricar 16 sillas y no fabricar mesas.
Unit Cost or Profit (costo por unidad, Utilidad por unidad): Cantidad de pesos que vamos a ganar por cada mesa y por cada silla ($10 y $8 respectivamente.
Total Contribution (contribución total): Es la cantidad en pesos que resulta al multiplicar la utilidad de cada producto por la cantidad que se va a fabricar, ejemplo al fabricar 16 sillas y multiplicarlo por $/silla 8, la contribución es de $128.0000, así al sumar la contribución por concepto de las mesas nos arroja una aportación de $0.0000, esto resulta de hacer la operación de ($/mesa10) (0mesas)= $0.0000, finalmente la suma de 128.0000+0.0000 = $128.0000, esto es lo que se conoce como el valor de Objetive Function Max.
Reduced Cost (Costo reducido): esto nos indica el dinero que hemos dejado de ganar por cada unidad no fabricada. en este caso debemos de aumentar a mas de $6.0000 la utilidad de la mesa para que sea atractiva la fabricación de mesas.
Basis Status (estado de la base): Indica si la variable es básica o no básica, en este ejemplo la variable X1 (mesas) resulta ser no básica, esto es que no forma parte de la solución óptima, la variable X2 (sillas) es una variable básica, ya que forma parte de la solución.
Allowed Min cj (rango mínimo del cj): esta es la mínima utilidad que puedo obtener sin que la base actual cambie. (-M)
Allowed Max cj (rango mínimo del cj): esta es la máxima utilidad que puedo obtener sin que la base actual cambie. (16.0000)
los valores que aparecen son para el producto Mesa.
Interpretación de las Restricciones:
Constraint (Restricción): Son las restricciones que forman parte del problema, se tienen dos restricciones (C1 y C2) la restricción de la madera y la de horas hombre.
Left hand side (valor al lado izquierdo): esto nos indica el consumo de recurso, de 30.000 m2 de madera se consumieron 24.000 m2.
Direction (dirección): es la dirección de la restricción (<=,>= o =)
Rigth hand side (valor lado derecho): es el recurso disponible actualmente 30 m2
Slack or Surplas (holguras): nos indican un faltante o bien un sobrante
Shadow Price (precio sombra): nos indica la solución Dual, esto es que el 2.6667 indica que cada hra-hombre se debe ofrecer como mínimo en $/hr 2.6667.
Allowed Min RHS (rango mínimo del bj): esta es la mínima cantidad de recurso que se debe de mantener sin que la base actual cambie. (0 hrs-hombre)
Allowed Max RHS (rango mínimo del bj): esta es la máxima cantidad de recurso que se debe de mantener sin que la base actual cambie (60.0000 hrs-hombre)
regresar
SOLUCIÓN GRÁFICA DE PROBLEMAS DE PROGRAMACIÓN LINEAL
Muchos problemas de administración y economía están relacionados con la optimización (maximización o minimización) de una función sujeta a un sistema de igualdades o desigualdades. La función por optimizar es la función objetivo. Las funciones de ganancia y de costo son ejemplos de funciones objetivo. El sistema de igualdades o desigualdades a las que está sujeta la función objetivo reflejan las restricciones (por ejemplo, las limitaciones sobre recursos como materiales y mano de obra) impuestas a la solución (o soluciones) del problema. Los problemas de esta naturaleza se llaman problemas de programación matemática. En particular, aquellas donde la función objetivo y las restricciones se expresan como ecuaciones o desigualdades lineales se llaman problemas de programación lineal.
Un problema de programación lineal
Un problema de programación lineal consta de una funci´n objetivo lineal por maximizar o minimizar, sujeta a ciertas restricciones en la forma de igualdades o desigualdades lineales.
Como ejemplo de un problema de programación lineal en que la función objetivo debe maximizarse, considerese el siguiente problema de producción con dos variables
El granjero Lopez tiene 480 hectáreas en la que se puede sembrar ya sea trigo o maíz. El calcula que tiene 800 horas de trabajo disponible durante la estación crucial del verano. Dados márgenes de utilidad y los requerimientos
Maiz: Utilidad: $40 por hrs.Trabajo: 2hs por hrs.
laborales mostrados a la derecha, ¿Cuántas hectáreas de cada uno debe plantar para maximizar su utilidad?¿Cuál es ésta utilidad máxima?
Trigo: Utilidad: $30 por hrs.Trabajo: 1hs por hrs.
Solución: Como primer paso para la formulación matemática de este problema, se tabula la información dada (Tabla 1). Si llamamos x a las hectáreas de maíz e y a las hectáreas de trigo. Entonces la ganancia total P, en dólares, está dada por:
P=40x+30y
Que es la función objetivo por maximizar.
Maíz TrigoElementos disponibles
Horas 2 1
Hectáreas 1 1 800
Utilidad por unidad $40 $30 480
La cantidad total de tiempo par hectáreas para sembrar maíz y trigo está dada por 2x+y horas que no debe exceder las 800 horas disponibles para el trabajo. Así se tiene la desigualdad:
2x+y<800
En forma análoga, la cantidad de hectáreas disponibles está dada por x+y, y ésta no puede exceder las hectáreas disponibles para el trabajo, lo que conduce a la desigualdad. Por último, si no queremos tener pérdidas, x y y no pueden ser negativa, de modo que
x>0 y>0
En resumen, el problema en cuestión consiste en maximizar la función objetivo P=40x+30y sujeta a las desigualdades
2x+y<800 x+y<480
x>0 y>0
Solución Gráfica
Los problemas de programación lineal en dos variables tienen interpretaciones geométricas relativamente sencillas; por ejemplo, el sistema de restricciones lineales asociado con un problema de programación lineal bidimensional- si no es inconsistente- define una región plana cuya frontera está formada por segmentos de recta o semirrectas, por lo tanto es posible analizar tales problemas en forma gráfica.
Si consideremos el problema del granjero López, es decir, de maximizar P = 40x+ 30y sujeta a
2x+y<800 x+y<480
x>0, y>0 (7) El sistema de desigualdades (7) define la región plana S que aparece en la figura 5. Cada punto de S es un candidato para resolver este problema y se conoce
como solución factible. El conjunto S se conoce como conjunto factible. El objetivo es encontrar – entre todos los puntos del conjunto S- el punto o los puntos que optimicen la función objetivo P. Tal solución factible es una solución óptima y constituyen la solución del problema de programación lineal en cuestión.
Como ya se ha observado, cada punto P(x,y) en S es un candidato para la solución óptima del problema en cuestión, por ejemplo, es fácil ver que el punto (200, 150) está en S y, por lo tanto, entra en la competencia. El valor de la función objetivo P en el punto (200,150) está dado por P=40(200)+30(150)=12.500 . Ahora si se pudiera calcular el valor de P correspondiente a cada punto de S, entonces el punto (o los puntos) en S que proporcione el valor máximo de P formará el conjunto solución buscado. Por desgracia, en la mayoría de los problemas, la cantidad de candidatos es demasiado grande o, como en este problema, es infinita. Así este método no es adecuado.
Es mejor cambiar de punto de vista: en vez de buscar el valor de la función objetivo P en un punto factible, se asignará un valor a la función P y se buscarán los puntos factibles que correspondieran a un valor dado de P. Para esto supóngase que se asigna a P el valor 6000. Entonces la función objetivo se convierte en 40x+ 30y = 6.000,una ecuación lineal en x e y; por lo tanto, tiene como gráfica una línea recta L1 en el plano.
Está claro que a cada punto del segmento de recta dado por la intersección de la línea recta L1 y el conjunto factible S corresponde el valor dado 6000 de P. Al repetir el proceso, pero ahora asignando a P el valor de 12.000, se obtiene la ecuación 40x+ 30y =12.000 y la recta L2 lo cual sugiere que existen puntos
factibles que corresponden a un valor mayor de P. Obsérvese que la recta L2 es paralela a L1, pues ambas tienen una pendiente igual a –4/3. Esto se comprueba con facilidad escribiendo las ecuaciones en explícita de la recta.
En general, al asignar diversos valores a la función objetivo, se obtiene una familia de rectas paralelas, cada una con pendiente igual a –4/3. Además, una recta correspondiente a un valor mayor de P está más alejada del origen que una recta con un valor menor de P. El significado es claro. Para obtener las soluciones óptimas de este problema, se encuentra la recta perteneciente a esta familia que se encuentra más lejos del origen y que interseque al conjunto factible S. La recta requerida es aquella que pasa por el punto P(320,160) (Fig. 6), de modo que la solución de este problema está dado por x=320, y=160 ( es decir que el granjero López deberá sembrar 320 hectáreas de maíz y 160 hectáreas de trigo), lo que produce el valor máximo P=40(320)+30(160)=17.600.
No es casualidad que la solución óptima de este problema aparezca como vértice del conjunto factible S. De hecho, el resultado es consecuencia del siguiente teorema básico de la programación lineal, que se enuncia sin demostración.
Teorema 1 Si en problema de programación lineal tiene una solución, entonces ésta debe aparecer en un vértice, o esquina, del conjunto factible S asociado con el problema. Además, si la función objetivo dos vértices adyacente de S, entonces se optimiza en todos los puntos del segmento de recta que une estos vértices, en cuyo caso existe una infinidad de soluciones al problema
En nuestro ejemplo los únicos vértice del conjunto factible S son los puntos coordenados: (0,0); (400,0); (320,160); (0,480), llamados también puntos esquinas (Fig. 6).
Un ejemplo en el que tendríamos infinitas soluciones, es:
VERTICE P=40x+40y
(0,0) 0
(0,480) 19.200
(320,160) 19.200
(400,0) 16.000
Supóngase que la utilidad por hectáreas es de $40 para ambos, maíz y trigo. La tabla para este caso muestra la misma utilidad total en los vértices(0,480) y (320,160). Esto significa que la línea de utilidad en movimiento abandona la región sombreada por el lado determinado por esos vértices (adyacentes) , así todo punto en ese lado da una utilidad máxima. Todavía es válido, sin embargo, que la utilidad máxima ocurre en un vértice.
El teorema 1 dice que la búsqueda de las soluciones a un problema de programación lineal se puede restringir al examen del conjunto de vértices del conjunto factible S relacionado con el problema. Como un conjunto factible S tiene un número finito de vértices, el teorema sugiere que las soluciones a un problema de programación lineal se puedan hallar inspeccionando los valores de la función objetivo P en los vértices.
Aunque el teorema 1 arroja un poco de luz acerca de la naturaleza de la solución de un problema de programación lineal, no indica cuándo tiene
solución. El siguiente teorema establece ciertas condiciones que garantizan la existencia de la solución de un problema de programación lineal.
Teorema 2: Existencia de una solución
Supóngase un problema de programación lineal con un conjunto factible S y una función objetivo P = ax + by. 1. Si S está acotado, entonces P tiene u valor máximo y n valor mínimo en S. 2. Si S no está acotado y tanto a como b son no negativos, entonces P tiene un valor mínimo en S, si las restricciones que definen a S incluyen las desigualdades x ³ 0 e y ³ 0. 3. Si S es el conjunto vacío, entonces el problema de programación lineal no tiene solución; es decir, P no tiene un valor máximo ni uno mínimo
El método utilizado para resolver el problema del granjero López recibe el nombre de método de las esquinas. Este método sigue un procedimiento muy sencillo para resolver los problemas de programación lineal basado en el teorema1.
Método de las esquinas
1. Se grafica el conjunto factible. 2. Se encuentran las coordenadas de todas las esquinas (vértices) del conjunto factible.3. Se evalúa la función objetivo en cada esquina. 4. Se halla el vértice que proporcione el máximo (mínimo) de la función objetivo. Si sólo existe un vértice con esta propiedad, entonces constituye una solución única del problema. Si la función objetivo se maximiza (minimiza) en dos esquinas adyacentes de S, entonces existe una infinidad de soluciones óptimas dadas por los puntos del segmento de recta determinado por estos dos vértices.
Aplicaremos los conceptos antes emitidos al siguiente problema de nutrición, basado en los requerimientos, en el cual hay que minimizar la función objetivo.
Un nutricionista asesora a un individuo que sufre una deficiencia de hierro y vitamina B, y le indica que debe ingerir al menos 2400 mg de vitamina B-1 (tiamina) y 1500 mg de vitamina B-2 (riboflavina) durante cierto período de tiempo. Existen dos píldoras de vitaminas disponibles, la marca A y la marca B. Cada píldora de la marca A contiene 40 mg de hierro, 10 mg de vitamina B-1, 5 mg de vitamina B-2 y cuesta 6 centavos. Cada píldora de la marca B contiene 10 mg de hierro, 15 mg de vitamina B-1 y de vitamina B-2, y cuesta 8 centavos (tabla 2). ¿Cuáles combinaciones de píldoras debe comprar el paciente para cubrir sus requerimientos de hierro y vitamina al menor costo?
Marca A Marca BRequerimientos
mínimos
Hierro 40 mg 10 mg 2400 mg
Vitamina B-1 10 mg 15 mg 2100 mg
Vitamina B-2 5 mg 15 mg 1500 mg
Costo por píldora (US$)
0,06 0,08
Solución: Sea x el número de píldoras de la marca A e y el número de píldoras de la marca B por comprar. El costo C, medido en centavos, está dado por
C = 6x+ 8y
que representa la función objetivo por minimizar.
La cantidad de hierro contenida en x píldoras de la marca A e y el número de píldoras de la marca B está dada por 40x+10y mg, y esto debe ser mayor o igual a 2400 mg. Esto se traduce en la desigualdad.
40x+10y>2400
Consideraciones similares con los requisitos mínimos de vitaminas B-1 y B-2 conducen a las desigualdades:
10x+15y>2100 5x+15y>1500
respectivamente. Así el problema en este caso consiste en minimizar C=6x+8y sujeta a
40x+10y>2400 10x+15y>2100 5x+15y>1500
x>0, y>0 El conjunto factible S definido por el sistema de restricciones aparece en la figura. Los vértices del conjunto factible S son A(0,240); B(30,120); C(120; 60) y D(300,0).
Los valores de la función objetivo C en estos vértices en la tabla que sigue
Vertice C=6x + 8y
A (0,240) 1920
B(30,120) 1140
C(120,60) 1200
D(300,0) 1800
La tabla muestra que el mínimo de la función objetivo C=6x+8y ocurre en el vértice B(30,120) y tiene un valor de 1140. Así el paciente debe adquirir 30 píldoras de la marca A y 120 de la marca B, con un costo mínimo de $11,40.
El método de las esquinas es de particular utilidad para resolver problemas de programación lineal en dos variables con un número pequeño de restricciones, como han demostrado los ejemplos anteriores, sin embargo su efectividad decrece con rapidez cuando el número de variables o de restricciones aumenta. Por ejemplo, se puede mostrar que un ejemplo de programación lineal en tres variables y cinco restricciones puede tener hasta diez esquinas factibles. La determinación de las esquinas factibles requiere resolver 10 sistemas 3x3 de ecuaciones lineales y luego comprobar que cada uno es un punto factible, sustituyendo cada una de estas soluciones en el sistema de restricciones. Cuando el número de variables y de restricciones aumenta a cinco y diez, respectivamente (que aún es un sistema pequeño desde el punto de vista de las aplicaciones en economía), la cantidad de vértice por hallar y comprobar como esquinas factibles aumenta hasta 252, y cada uno de estos vértices se encuentra resolviendo el sistema lineal ...¡de 5x5! Por esta razón, el método de las esquinas se utiliza con poca frecuencia para resolver problemas de programación lineal, su valor reside en que permite tener una mejor idea acerca de la naturaleza de las soluciones a los problemas de programación lineal a través de su uso en la solución de problemas de dos variables.
Regresar a la Página Principal
PROGRAMAS DE COMPUTACIÓN PARA RESOLVER
PROBLEMAS DE PROGRAMACION LINEAL
En esta pagina, se presenta la documentación relativa a los programas de computación que serán utilizados en el curso para resolver problemas de programación Lineal, adicionalmente, el alumno puede bajar los programas de computación con fines académicos, con miras a resolver los problemas propuestos del curso y no deben ser utilizados con fines comerciales ya que los mismos están protegidos por las leyes de derechos de autor.
A.-) PROGRAMAS DE COMPUTACIÓN
Adicional al programa SOLVER, incluido en EXCEL-2000 de MIcrosoft (cuya explicación didáctica del funcionamiento del programa Solver (445 kb), se incluye en este documento que puede ser bajado por Usted), se incorporan otros programas que operan bajo sistema WIndows 98/ME/2000/XP, debiendo disponer de una computadora actualizada con procesador Pentium II y superiores,
memoria mínima de 256 kb y capacidad de disco de 50 MB y los cuales pueden ser bajados a continuación:.
A.1) El programa WinQSB (3.9 Mb), cuya propiedad intelectual es del Dr. Yih-Long Chang y es aplicable a todos los problemas de Investigación de Operaciones. Para conocer sus usos y aplicaciones, se incorpora el MANUAL DE USO del WINQSB.
A.2) El programa PrgLin, cuya propiedad es de la Universidad de Lisboa (Portugal), el cual se aplica para soluciones gráficas de problemas de dos dimensiones.
A.3) El programa InvOp (361 kb), desarrollado por la Universidad del Cuyo en Argentina, se aplica para la solución de problemas relacionados con transporte y redes.
A.3) El programa Lingo , propiedad de Lindo Systems Inc (USA), que dado su gran tamaño (18.9 Mb), se recomienda que Usted lo recupere directamente de la pagina Web del propietario de dicha tecnologia http:// www.lindo.com
Posteriormente se irán incorporando otros programas de computación específicos para cada caso y cuyo uso será descrito mediante ejemplos en la Clase.
B.-) USO DEL PROGRAMA SOLVER DE EXCEL (Microsoft)
Para conocer la aplicación del método SOLVER de EXCEL (Microsoft), se utilizará un ejemplo práctico:
Max Z= 10 X1 + 8 X2Sujeto a: 30X1 +20X2 <= 120 2X1 + 2X2 <= 9 4X1 + 6X2 <= 24
X1,X2 >=0
La única dificultad que tenemos es el de modelar el programa dentro del Excel, y eso, es muy fácil. Por supuesto, hay infinidad de maneras de hacerlo, aquí propongo una.
Se activa Excel y en una hoja...
• Se ubican las celdas que se corresponderán con el valor de las variables de decisión; en éste caso, las celdas B6 y C6, se les da un formato para diferenciarlas de las demás, aquí azul oscuro (ver captura abajo). Se ubica también, las celdas que contendrán los coeficientes de las variables de decisión, B4 y C4, y se llenan con
sus respectivos valores, 10 y 8. Aunque éste último paso, se podría omitir y dejar los coeficientes definidos en la celda de la función objetivo, así es mejor para los análisis de sensibilidad y para que la hoja quede portable para otro programa.
• Se ubica la celda que se corresponderá con la función objetivo (celda objetivo), la B3. En ella se escribe la función que sea, en éste caso, será el coeficiente de X1 (en B4) por el valor actual de X1 (en B6) mas el coeficiente de X2 (en C4) por el valor actual de X2 (en C6) O sea: =$B$4*$B$6+$C$6*$C$4
• Coeficientes para la primera restricción: los podemos escribir en la misma columna de las variables de decisión; en las celdas B7 y C7, con los valores 30 y 20, seguido del sentido de la desigualdad (<=) y de su correspondiente RHS: 120. A la derecha ubicaremos el valor actual de consumo de la restricción, ella se escribirá en función de las variables de decisión y de los coeficientes de la restricción. Esta celda, la utilizará Solver como la real restricción, cuando le digamos que el valor de ésta celda no pueda sobrepasar la de su correspondiente RHS. De nuevo será el valor del coeficiente por el de la variable:=B7*$B$6+C7*$C$6. Notese que ahora B7 y C7 no tienen el signo $. Pues es que luego que se haya escrito ésta celda, se podrá arrastrar hacia abajo para que Excel escriba la fórmula por nosotros (la pereza!), pero tome los valores relativos a los coeficientes que le corresponda a los mismos valores de las variables de decisión. Se repite los pasos anteriores para las otras restricciones, pero ahora la fórmula será: =B8*$B$6+C8*$C$6 y =B9*$B$6+C9*$C$6.
El resto del formato es para darle una presentación más bonita a la hoja. Ahora a resoverlo! Al hacer click en Herramientas , Solver se tendrá una pantalla como la siguiente. Lo primero que hay que hacer es especificar la celda objetivo y el propósito: maximizar. Se escribe B3 (o $B3 ó B$3 ó $B$3 como sea, da igual), en el recuadro "cambiando las celdas", se hace un click en la flechita roja, para poder barrer las celdas B6 y C6; lo mismo da si se escriben directamente los nombres.
Y ahora para las restricciones: se hace click en agregar...
En F7 está la primera restricción, como se puede ver en la captura. Se especifica el sentido de la restricción <=, >= ó =. Aquí también se puede especificar el tipo de variable, por defecto es continua, pero se puede escoger "Int" para entera o "Bin" para binaria. En el recuadro de la derecha establecemos la cota. Aquí podemos escribir 120 pero mejor escribimos $E$7 para que quede direccionado a
la celda que contiene el 120, y después lo podríamos cambiar y volver a encontrar la respuesta a manera de análisis de sensibilidad.
Se repite éste paso para las otras dos restricciones.
La condición de no negatividad hay que incluirla manualmente, así:
El cuadro de diálogo debe lucir así:
Y listo! Se hace click en resolver y ya. Parece un poco largo en comparación con los otros paquetes de programación lineal, pero esto se hará sólo una vez, para los próximos programas se podrá utilizar la misma hoja cambiando los coeficientes. Sin embargo, como se puede notar, la flexibilidad de modelar es muy
grande, y se puede introducir directamente en una hoja donde se haga el análisis de Planeación Agregada, Transporte, Inventario, Secuencias, balanceo, etc.
Regresar Pagina Principal
EL METODO SIMPLEX PARA SOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL
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.
Con miras a conocer la metodología que se aplica en el Método SIMPLEX, vamos a resolver el siguiente problema:
MaximizarZ= f(x,y)= 3x +
2y
sujeto a: 2x + y 18
2x + 3y 42
3x + y 24
x 0 , 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 = 182x + 3y + s = 423x +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
A. Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto).En nuestro caso, la variable x de coeficiente - 3.
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 azulado).
B. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. En nuestro caso: 18/2 [=9] , 42/2 [=21] y 24/3 [=8]
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 azulado).
Si al calcular los cocientes, dos o más son iguales, indica que cualquiera de las variables correspondientes pueden salir de la base.
C. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3.
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):
Vieja fila de s 2 3 0 1 0 42 - - - - - -Coeficiente 2 2 2 2 2 2 x x x x x xNueva fila pivote 1 1/3 0 0 1/3 8 = = = = = =Nueva fila de s 0 7/3 0 1 -2/3 26
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:
A. La variable que entra en la base es y, por ser la variable que corresponde al coeficiente -1
B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:2:1/3 [=6] , 26:7/3 [=78/7] y 8:1/3 [=8] y como el menor cociente positivo es 6, tenemos que la variable de holgura que sale es h.
C. El elemento pivote, que ahora hay que hacer 1, es 1/3.
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:
A. La variable que entra en la base es d, por ser la variable que corresponde al coeficiente -1
B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:6/(-2) [=-3] , 12/4 [=3], y 6:1 [=6] y como el menor cociente positivo es 3, tenemos que la variable de holgura que sale es s.
C. El elemento pivote, que ahora hay que hacer 1, es 4.
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
Interpretación geométrica del método del simplex
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.
Método de la “M” o de Penalización.
Hasta este momento se han presentado los detalles del método símplex con la
suposición de que el problema se encuentra en nuestra forma estándar (maximizar Z
sujeta a las restricciones funcionales de la forma ≤ y restricciones de no negatividad
sobre todas las variables) con bi ≥ 0 para toda i = 1, 2, ..., m. En esta sección se
establecerá cómo hacer los ajustes requeridos a otras formas legítimas de modelos de
Programación Lineal. Se verá que todos estos ajustes se pueden hacer en el paso inicial, de
manera que el resto del método símplex se aplica justo como se aprendió.
El único problema serio que introducen las otras formas de restricciones funcionales
(= ó ≥ ) es identificar una solución inicial básica factible. Antes, esta solución inicial se
encontraba en forma muy conveniente al hacer que las variables de holgura fueran las
variables básicas iniciales, donde cada una era igual a la constante no negativa del lado
derecho de la ecuación correspondiente. Ahora debe hacerse algo más. El enfoque estándar
que se utiliza es estos casos es la técnica de variables artificiales. Ésta construye un
problema artificial más conveniente introduciendo una variable ficticia (llamada variable
artificial) en cada restricción que lo requiera. Esta nueva variable se introduce sólo con el
fin de que sea la variable básica inicial para esa ecuación. Las restricciones usuales de no
negatividad también se aplican sobre estas variables y la función objetivo se modifica para
que imponga una penalización exorbitante en el caso de que adquieran valores mayores
que cero. Las iteraciones del método símplex automáticamente fuerzan a las variables
artificiales a desaparecer (a volverse cero) una a una, hasta que todas quedan fuera de la
solución; después de esto se resuelve el problema real.
Para ilustrar la técnica de las variables artificiales, primero se considerará el caso en
que la única forma no estándar en el problema es la presencia de una o más restricciones en
forma de igualdad.
Restricciones en forma de igualdad.
En realidad, cualquier restricción en forma de igualdad:
ai1x1 +ai2x2 + . . . + ainxn = bi
es equivalente a dos restricciones de desigualdad:
ai1x1 + ai2x2 + . . . + ainxn ≤ bi,
ai1x1 + ai2x2 + . . . + ainxn ≥ bi
Sin embargo, en lugar de hacer esta sustitución e incrementar con ello el número de
restricciones, es más conveniente usar la técnica de la variable artificial. Suponga que se
modifica el problema de ejemplo presentado y resuelto en la sección anterior. El único
cambio que sufre el modelo de programación lineal es que la tercera restricción, 3x1 + 2x2
≤ 18, se convierte en una restricción de igualdad:
3x1 + 2x2 = 18
Aplicando la técnica de las variables artificiales se introduce una variable
artificial no negativa (denotada por x5) en la última ecuación, como si fuera una variable
de holgura:
3x1 + 2x2 + x5 =18
En resumen si tenemos una restricción funcional en forma de igualdad y deseamos
“pasarla a su forma de igualdad”, únicamente debemos sumar una variable artificial.
Restricciones funcionales de la forma ≥
Para ilustrar la manera en que la técnica de las variables artificiales maneja las
restricciones de la forma ≥ usaremos el siguiente ejemplo:
Minimizar Z = 0.4x1 + 0.5x2 sujeta a 0.3x1 + 0.1x2 ≤ 2.7 0.5x1 + 0.5x2 = 6 0.6x1 + 0.4x2 ≥ 6 x1 ≥ 0, x2 ≥ 0
Notemos que la tercera restricción es del tipo ≥ , por lo que para cambiarla a su
forma de igualdad tendríamos que restar una variable de superávit (o de excedente),
quedando de la siguiente manera:
0.6x1 + 0.4x2 − x5 = 6
Se ha restado la variable de excedente x5 (se utilizó x5 porque en la primera
restricción agregamos una variable de holgura que sería x3 y en la segunda restricción
agregamos también una variable artificial que sería x4; todo esto con el fin de convertir las
desigualdades a su forma de igualdades) para que consuma el exceso de 0.6x1 + 0.4x2, o
sea, lo que se pasa de 6. No obstante en este caso debe agregarse otra variable. Esta variable
extra, llamada variable artificial se aumenta como sigue:
0.6x1 + 0.4x2 − x5 + x6 = 6
La razón de esto es que, si no se agrega la variable artificial, no se estarían
cumpliendo las restricciones de no negatividad. Para comprenderlo, se dejará sin aumentar.
El método símplex comienza por hacer todas las variables reales (originales) iguales a cero.
Entonces:
0.6x1 + 0.4x2 − x5 = 6
Sea x1 = 0 y x2 = 0, entonces:
−x5 = 6
ó x5 = −6 (que no cumple la restricción de
no negatividad)
La variable artificial opera para mantener todas las variables no negativas cuando
0.6x1 + 0.4x2 es menor que 6. Si x1 = 0 y x2 = 0, entonces x5 = 0 y
0.6x1 + 0.4x2 − x5 + x6 = 6
x6 = 6
En resumen, una restricción de la forma ≥ se convierte a su forma de igualdad
restando una variable de excedente y sumando una variable artificial.
Consideremos el siguiente problema:
Maximizar Z = 3x1 + 5x2
sujeta a x1 ≤ 4 2x2 ≤ 12 3x1 + 2x2 = 18 x1 ≥ 0, x2 ≥ 0
Como explicamos anteriormente, para resolver este problema, debemos construir un problema artificial que tiene la misma solución óptima que el problema real, haciendo dos modificaciones a este problema real.
1. Se aplica la técnica de las variables artificiales introduciendo una variable artificial
no negativa (denotada por x5) en la última ecuación, como si fuera una variable de
holgura:
3x1 + 2x2 + x5 =18
2. Se asigna una penalización enorme al hecho de tener x5 > 0, cambiando la función
objetivo
Z = 3x1 + 5x2 a:
Z = 3x1 + 5x2 − Mx5,
donde M simbólicamente representa un número positivo muy grande. Este método
que fuerza a x5 hasta el nivel de x5 = 0 en la solución óptima se llama método de la M.
Nota: Para el caso de minimización, penalizamos a la variable artificial, haciéndola
aparecer en la función objetivo con un coeficiente de +M.
Ahora se encuentra la solución óptima para el problema real aplicando el método símplex al problema artificial.
Como x5 juega el papel de la variable de holgura en la tercera restricción del
problema artificial, esta restricción es equivalente a 3x1 + 2x2 ≤ 18.
En particular, el sistema de ecuaciones después de aumentar el problema artificial
(en otras palabras, pasarlo a su forma de igualdades) es:
Maximizar Z,
sujeta a
Z − 3x1 − 5x2 + Mx5 = 0 x1 + x3 = 4 2x2 + x4 = 12
3x1 + 2x2 + x5 = 18 xj≥ 0 Para j = 1, 2, …, 5
En este momento estamos preparados para pasar los coeficientes a la tabla símplex:
Variable
Básica
Z
x1
x2
x3
x4
x5
Lado
derecho
Cociente
¿Es óptima?
Z 1 –3 –5 0 0 M 0 x3 0 1 0 1 0 0 4 x4 0 0 2 0 1 0 12
x5 0 3 2 0 0 1 18
Esta tabla todavía no está en la forma apropiada porque el coeficiente de x5 es
diferente de cero en la ecuación de Z (es M). Por lo tanto, antes de que el método símplex
pueda aplicar la prueba de optimalidad y encontrar la variable básica entrante, debe pasarse
esta tabla a la forma apropiada para que cumpla la condición símplex. Esta condición que
debe cumplir toda tabla del método símplex para que pueda reportarnos la siguiente
solución básica factible dice que: “Toda variable básica debe tener un 1 en la intersección
de su renglón y columna correspondiente y cero en los demás renglones incluido el renglón
de Z”, en otras palabras, que toda variable que sea básica solamente debe aparecer en el
renglón de la restricción que representa. Para hacer cero el coeficiente M, utilizamos el
renglón de x5 como renglón pivote multiplicándolo por −M y sumando el resultado al
renglón de Z. Realizando el procedimiento anterior, la tabla símplex queda de la siguiente
manera:
Variable
Básica
Z
x1
x2
x3
x4
x5
Lado
derecho
Cociente
¿Es óptima?
Z1 -3M-3 -2M-5 0 0 0 −18M −Mx5 + Z
x3 0 1 0 1 0 0 4 (0, 0, 4, 12, 18)x4 0 0 2 0 1 0 12 Z = −18M
x5 0 3 2 0 0 1 18
Podemos observar que la tabla anterior ya se encuentra en la forma apropiada y
podemos leer la solución básica factible actual, que es (0, 0, 4, 12, 18), la cual aplicando la
prueba de optimalidad vemos que no es óptima ya que todavía tenemos coeficientes
negativos en el renglón de Z (los correspondientes a x1 y x2). Aplicando el método símplex
a la tabla anterior tenemos: el coeficiente negativo con el mayor valor absoluto corresponde
a x1 (−3M−3), recordemos que M es un número muy grande positivo, por lo tanto, x1 se
convierte en la variable básica entrante, realizando los cocientes correspondientes, vemos
que x3 se convierte en la variable básica saliente. El procedimiento completo para resolver
este ejemplo se muestra en el siguiente conjunto de tablas:
Variable
Básica
Z
x1
x2
x3
x4
x5
Lado
derecho
Z 1 -3M-3
-2M-5
0 0 0 −18M
x3 0 1 0 1 0 0
x4 0 0 2 0 1 0
x5 0 3 2 0 0 1
Z 1 0 -2M-5
3M+3 0 0 −6M+12
x1 0 1 0 1 0 0
x4 0 0 2 0 1 0
x5 0 0 2 −3 0 1
Z 1 0 0 −9/2 0 M+5/2
x1 0 1 0 1 0 0
x4 0 0 0 3 1 −1x2 0 0 1 −3/2 0 1/2
Z 1 0 0 0 3/2 M+1
x1 0 1 0 0 −1/3 1/3
x3 0 0 0 1 1/3 −1/3
x2 0 0 1 0 1/2 0
MINIMIZACIÓN con el método símplex.
Una manera directa de minimizar Z con el método símplex es cambiar los roles de
los coeficientes negativos y positivos en el renglón de la función objetivo, tanto para la
prueba de optimalidad como para la parte 1 de una iteración. Se determina la variable
básica entrante mediante la elección de la variable con el coeficiente positivo menor en la
ecuación de Z. La solución básica factible actual es óptima si y sólo si todos los
coeficientes de la ecuación de la función objetivo (renglón de Z) son no positivos ( ≤ 0 ). Si
es así, el proceso termina; de otra manera, se lleva a cabo otra iteración para obtener la
nueva solución básica factible, lo que significa el cambio de una variable no básica por una
básica (parte 1) y viceversa (parte 2), y después despejar las variables de la nueva solución
(parte 3). Notemos que no se ha dicho nada con respecto a la forma de obtener la variable
básica saliente en una iteración, ya que este paso se realiza de la misma manera que cuando
se está maximizando, es decir, se escoge aquella variable básica con el menor cociente.
Ilustremos la forma de utilizar el método símplex para el caso de minimización.
Consideremos el siguiente ejemplo:
Minimizar Z = 3x1 + 8x2 sujeta a x1 + 4x2 ≤ 4 x1 + 2x2 ≥ 2
x1 ≥ 0, x2 ≥ 0
Pasando este problema a su forma de igualdades añadiendo las variables necesarias,
obtenemos lo siguiente:
Minimizar Z,
sujeta a
Z − 3x1 − 8x2 − Mx5 = 0 x1 + 4x2 + x3 = 4
x1 + 2x2 − x4 + x5 = 2 xj≥ 0 para j = 1, 2, …, 5
Utilizando el método de la M para obtener una solución óptima por el método
símplex, obtenemos el siguiente conjunto de tablas:
Variable
Básica
Z
x1
x2
x3
x4
x5
Lado
derecho
Cociente
¿Es óptima?
Z 1 −3 −8 0 0 −M 0 x3 0 1 4 1 0 0 4 x5 0 1 2 0 −1 1 2
Z 1 M−3 2M−8 0 −M 0 2M (0, 0, 4, 0, 2)
x3 0 1 4 1 0 0 4 4/1 = 4 Z = 2Mx5 0 1 2 0 −1 1 2 2/1 = 2
Z 1 0 −2 0 −3 −M+3 6 (2, 0, 2, 0, 0)
x3 0 0 2 1 1 −1 2 Z = 6x1 0 1 2 0 −1 1 2 Óptima
Notemos que la primera tabla no se encontraba en la forma apropiada para el
método símplex, ya que el coeficiente de la variable básica x5 era de −M en el renglón de Z,
lo cual hacia que no se cumpliera la condición símplex.
Método de las dos Fases.
En el ejemplo presentado en la sección “Restricciones funcionales de la forma ≥ “,
recordemos la función objetivo real:
Problema real: Minimizar Z = 0.4x1 + 0.5x2
Sin embargo, el método de la M utiliza la siguiente función objetivo a través de todo
el procedimiento:
Método de la M: Minimizar Z = 0.4x1 + 0.5x2 + Mx4 + Mx6
Como los dos primeros coeficientes (0.4 y 0.5) son despreciables comparados con
M, el método de dos fases puede eliminar la M usando las siguientes dos funciones objetivo
que definen Z de manera completamente diferente:
Método de las dos fases:
Fase 1: Minimizar Z = x4 + x6 (hasta que x4 = 0 y x6 =
0).
Fase 2: Minimizar Z = 0.4x1 + 0.5x2 (con x4 = 0 y x6 = 0).
La función objetivo de la fase 1 se obtiene dividiendo la función objetivo del
método de la M entre M eliminando los términos despreciables, en otras palabras, la fase 1
consiste en la minimización de la suma de todas las variables artificiales que se introduzcan
en el problema. Como la fase 1 concluye al obtener una solución básica factible para el
problema real (aquella en la que x4 = 0 y x6 = 0), esta solución se usa como la solución
básica factible inicial para aplicar el método símplex al problema real (con su función
objetivo) en la fase 2. Antes de resolver el ejemplo de esta manera se hará un resumen de
las características generales.
Resumen del método de dos fases.
Paso inicial: Se revisan las restricciones del problema original introduciendo variables
artificiales según se necesite para obtener una solución básica factible inicial obvia para el
problema artificial.
Fase 1: uso del método símplex para resolver el problema de programación lineal:
Minimizar Z = Σ de todas las variables artificiales, sujeta a las restricciones
revisadas.
La solución óptima que se obtiene para este problema (con Z = 0) será una solución
básica factible para el problema real.
Fase 2: se eliminan las variables artificiales (de todas formas, ahora todas valen
cero). Comenzando con la solución básica factible que se obtuvo al final de la fase 1, se usa
el método símplex para resolver el problema real.
Enseguida se resumen los problemas que deben resolverse por el método símplex en
las fases respectivas para el ejemplo.
Problema para la fase 1:
Minimizar W = x4 + x6,
sujeta a
0.3x1 + 0.1x2 + x3 = 2.70.5x1
+ 0.5x2 + x4 = 6
0.6x1
+ 0.4x2 − x5 + x6 = 6
y
x1≥ 0 x2≥ 0 x3≥ x4≥ 0 x5≥ 0 x6≥ 0
Problema para la fase 2:
Minimizar Z = 0.4x1 + 0.5x2,
sujeta a
0.3x1 + 0.1x2 + x3 = 2.70.5x1 + 0.5x2 = 60.6x1 + 0.4x2 − x5 = 6
y
x1≥ 0 x2≥ 0 x3≥ x5≥ 0
Las únicas diferencias entre estos dos problemas se encuentran en la
función objetivo y en la inclusión (fase 1) o exclusión (fase 2) de las variables artificiales x4
y x6. Sin las variables artificiales, el problema para la fase 2 no tiene una solución básica
factible inicial obvia. El único propósito de resolver el problema para la fase 1 es obtener
una solución básica factible con x4 = 0 y x6 = 0 que se pueda usar como la solución básica
factible inicial para la fase 2.
Las siguientes tablas muestran el resultado de aplicar el método símplex a este
problema para la fase 1:
Variable
Básica
W
x1
x2
x3
x4
x5
x6
Lado
derecho
W 1 0 0 0 −1 0 −1 0
x3 0 0.3 0.1 1 0 0 0 2.7
x4 0 0.5 0.5 0 1 0 0 6
x6 0 0.6 0.4 0 0 −1 1 6
W 1 1.1 0.9 0 0 −1 0 12x3 0 0.3 0.1 1 0 0 0 2.7
x4 0 0.5 0.5 0 1 0 0 6
x6 0 0.6 0.4 0 0 −1 1 6
W 1 0 0.53 −3.66 0 −1 0 2.1x1 0 1 0.33 3.33 0 0 0 9
x4 0 0 0.33 −1.66 1 0 0 1.5
x6 0 0 0.2 −2 0 −1 1 0.6
W 1 0 0 1.64 0 1.65 −2.65 0.51x1 0 1 0 6.63 0 1.65 −1.65 8.01
x4 0 0 0 1.64 1 1.65 −1.65 0.51
x2 0 0 1 −10 0 −5 5 3
W 1 0 0 0 −1 0 −1 0x1 0 1 0 5 −1 0 0 7.5
x5 0 0 0 0.99 0.60 1 −1 0.3
x2 0 0 1 −5.05 3 0 0 4.5
Notemos que ya hemos obtenido una solución óptima para la fase 1 que
consistió en la minimización de la suma de todas las variables artificiales. Observemos
también que la función objetivo W terminó con un valor de cero en la última tabla, lo que
indica que las dos variables artificiales (x4 y x6) valen cero ó tienen valores recíprocos y se
cancelan mutuamente para dar cero. En nuestro caso, las dos variables artificiales valen
cero ya que no se encuentran en la columna de las variables básicas en la última tabla de la
primera fase. La segunda fase consiste en resolver el problema original utilizando como
tabla inicial de esta fase la última tabla de la primera fase pero sin considerar la columna de
las variables artificiales ya que éstas tomaron el valor de cero en la primera fase. El método
símplex aplicado a la segunda fase se muestra en el siguiente conjunto de tablas:
Variable
Básica
Z
x1
x2
x3
x4
x5
x6
Lado
derecho
Cociente
¿Es óptima?
Z 1 −0.4 −0.5 0 0 0 0 0 x1 0 1 0 5 −1 0 0 7.5 x5 0 0 0 0.99 0.60 1 −1 0.3 x2 0 0 1 −5.05 3 0 0 4.5
Z 1 0 −0.5 2 0 3 x1 0 1 0 5 0 7.5 x5 0 0 0 0.99 1 0.3 x2 0 0 1 −5.05 0 4.5
Z 1 0 0 −0.52 0 5.25 x1 0 1 0 5 0 7.5 (7.5,4.5,0,0,0.3,0)x5 0 0 0 0.99 1 0.3 Z = 5.25x2 0 0 1 −5.05 0 4.5 Óptima fase 2
Notemos que no fue necesario aplicar propiamente el método símplex a la primera
tabla de la segunda fase, ya que únicamente aplicando operaciones con matrices para tratar
de llevar esta tabla a la forma apropiada para el método símplex fue suficiente para resolver
el problema planteado en la segunda fase. Es necesario aclarar que no siempre ocurrirá de
esta manera, es decir, si después de dejar la tabla en la forma apropiada, es necesario
aplicar el método símplex, se debe aplicar como lo hemos estudiado.
Nota: Independientemente de que el problema original (real) sea de maximización o
minimización, la primera fase siempre consistirá en la minimización de la suma
de todas las variables artificiales.
DUALIDAD
El dual es un problema de PL que se obtiene matemáticamente de un modelo primal de PL dado. Los problemas dual y primal están relacionados a tal grado, que la solución símplex óptima de cualquiera de los dos problemas conduce en forma automática a la solución óptima del otro.
El método símplex además de resolver un problema de PL llegando a una solución óptima nos ofrece más y mejores elementos para la toma de decisiones. La dualidad y el análisis de sensibilidad son potencialidades de éste método.
En la mayoría de los procedimiento de PL, el dual se define para varias formas del primal, dependiendo de los tipos de restricciones, de los signos de las variables y del sentido de la optimización. La experiencia nos indica que en ocasiones, los principiantes se confunden con los detalles de esas definiciones. Más importante aún es que el uso de esas definiciones múltiples puede conducir a interpretaciones
inconsistentes de los datos en la tabla símplex, sobre todo en lo que respecta a los signos de las variables.
El concepto de dualidad indica que para cada problema de PL hay una asociación
y una relación muy importante con otro problema de programación lineal, llamado
precisamente dual.
La relación entre el problema dual y su asociado, es decir el problema original llamado primal, presenta varias utilidades:
Aporta elementos que aumentan sustancialmente la compresión de la PL.
El análisis de dualidad es una herramienta útil en la solución de problemas de PL, por ejemplo: más restricciones que variables.
El problema dual tiene interpretaciones e informaciones importantes que muestran que los análisis marginales están siempre involucrados implícitamente al buscar la solución óptima a un problema de PL.
La forma estándar general del primal se defina como; para maximizar o minimizar.
sujeto a;
¿Cómo convertir un problema primal a dual?
Un problema dual se formula de un problema primal de la siguiente forma:
1. Si el primal es un problema de maximización su dual será un problema de minimización y viceversa.
2. Los coeficientes de la función objetivo del problema primal se convierten en los coeficientes del vector de la disponibilidad en el problema dual.
3. Los coeficientes del vector de disponibilidad del problema original se convierten en los coeficientes de la función objetivo (vector de costo o precio) en el problema dual.
4. Los coeficientes de las restricciones en el problema primal, será la matriz de los coeficientes tecnológicos en el dual.
5. Los signos de desigualdad del problema dual son contrarios a los del primal.
6. Cada restricción en un problema corresponde a una variable en el otro problema. Si el primal tiene m restricciones y n variables, el dual tendrá n restricciones y m variables. Así, las variables Xn del primal se convierte en nuevas variables Ym en el dual.
PROBLEMA PRIMAL EN FORMA CANONICA:
MAX Z= CX
Sujeto a:
AX ≤ b
X ≥ 0
PROBLEMA DUAL EN FORMA CANONICA:
MIN Z= BY
Sujeto a:
AY ≥ C
Y ≥ 0
Ejemplo.
Si el problema primal es: MAX Z= 45X1 + 17X2 + 55X3
Sujeto a:
X1 + X2 + X3 ≤ 200
9X1 + 8X2 + 10X3 ≤ 5000
10X1+ 7X2 + 21 X3 ≤ 4000
Xj ≥ 0
El problema dual será:
MIN Z= 200Y1 + 5000Y2 + 4000Y3
Sujeto a:
Y1 + 9Y2 + 10Y3 ≥ 45
Y1 + 8Y2 + 7Y3 ≥ 17
Y1 + 10Y2 + 21Y3 ≥ 55
Yj ≥ 0
FORMA DE PRESENTAR EL PROBLEMA DUAL
MIN = 2X1 - 3X2
Sujeto a:
1X1 + 2X2 ≤ 12
4X1 - 2X2 ≥ 3
6X1 - 1X2 = 10
X1,2 ≥ 0
1. Llevar el problema a su equivalente de maximización, multiplicando la función objetivo por –1:
MAX -2X1 + 3X2
2. Convertir las restricciones ≥ en una restricción equivalente ≤ multiplicando por –1 ambos lados:
-4x1 + 2x2 ≤ -3
3. Para las restricciones de igualdad, obtener 2 restricciones de desigualdad, una de forma ≤ y la otra de forma ≥ ; después regresar al punto anterior y cambiar la restricción ≥ a la forma ≤ :
6X1 – 1X2 ≤ 10
6X1 – 1X2 ≥ 10
6X1 – 1X2 ≤ 10
-6X1 + 1X2 ≤ -10
Así el problema primal se ha replanteado en la forma equivalente:
MAX Z= -2X1 + 3X2
Sujeto a:
1X1 + 2X2 ≤ 12
-4X1 + 2X2 ≤ - 3
6X1 – 1X2 ≤ 10
-6X1 + 1X2 ≤ -10
X1,2 ≥ 0
4. Teniendo el problema primal convertido a la forma canónica de un problema de maximización, es fácil llevarlo al problema dual:
MIN 12Y1 – 3Y2 + 10Y3
Sujeto a:Y1–4Y2 + 6Y3’–6Y3’’ ≥ -2 Y’3 y Y’’3 ambas se refieren a la tercera restricción
2Y1 + 2Y2 – 1Y3’ + 1Y3’’ ≥ 3 del problema primal.
Y1, 2, 3’, 3’’ ≥ 0
EMARIO.
I. INTRODUCCION A LA INVESTIGACION DE OPERACIONES
Definición de antecedentes, ubicación en las organizaciones, metodología.
II. PROGRAMACION LINEAL.
Modelo de la Programación Lineal (P.L. General). Propiedades.
Formulación con Programación Lineal de aplicaciones típicas en: producción, selección de equipo, procesos, horarios, dieta, etc.
Solución para el problema expresado con Programación Lineal.
Método de solución gráfica con solo dos variables.
Visualización de conceptos de P.L.; solución factible y no factible, solución básica, solución única y no única, restricción redundante, solución degenerada, variable de holgura y superflua.
Método de solución analítica para el problema de P.L.
Formas equivalentes del modelo de programación lineal.
Definiciones y teoremas de P.L.
Método SIMPLEX y criterios para el cambio de base.
Variables artificiales.
Método SIMPLEX-PENAL o de la M Grande.
Método SIMPLEX-DOS FASES.
Casos especiales en la tabla SIMPLEX.
Teoría de la Dualidad en P.L.
Obtención del Problema Dual en forma canónica.
Obtención del Problema Dual en forma directa.
Equivalencia entre las dos obtenciones anteriores
Significado de las variables duales e interpretación económica.
Método DUAL-SIMPLEX y criterios para cambios de base.
Estructura matricial de la tabla SIMPLEX.
Análisis de sensibilidad de la solución óptima de un problema.
Cambios en el vector b de recursos de restricciones.
Cambios en el vector C de coeficientes de la función objetivo.
Cambios en la matriz A de coeficientes de restricciones.
Aplicaciones de la Programación Lineal a Redes de Flujo.
Definición.
Modelo de transporte simple. Definición.
Modelo matemático de P.L. y tabla usual.
Solución inicial para la optimización de un problema.
Algorítmo de transporte (SIMPLEX-SIMPLIFICADO) para la optimización.
Ejemplificación de soluciones degenerada y no degenerada.
Modelo de transbordo definición.
Modelo matemático de transbordo balanceado y sin capacidades.
Modelo matemático de transbordo con capacidades.
Problemas y modelo matemático de ruta mínima. Definición.
Algorítmo de Dijkstra para red orientada y no orientada.
Algorítmo matricial para cualquier red.
Problema de árbol mínimo y algorítmo de conjunto conectado.
Problema y modelo matemático de flujo máximo
Algorítmo de Ford-Fulkerson para red orientada
Algorítmo matricial para cualquier red.
INVESTIGACION DE OPRERACIONES.
• Es la aplicación del método científico.• Por grupos interdisciplinarios.• En el estudio de problemas de las organizaciones creads por el hombre buscando un
a solución integral.
Modelo matemático obligado.
METODO CIENTIFICO
Métodos estadísticos de muestreo.
Investigador de operaciones.
Administradores.
Informáticos.
GRUPOS Ingenieros.
INTERDISCIPLINARIOS Economistas.
Contadores.
Etc.
CREADAS POR EL HOBRE. Enfoque sistémico.
ANTECEDENTES.
AÑO. AUTOR. TECNICA DESARROLLADA.
1759 Quesnay Modelos primarios de programación matemática.
1873 G.Jordan. Modelos lineales.
1874 Warlas. Modelos primarios de programación matemática.
1891 Minkousky. Modelos lineales.
1903 Farkas. Modelos lineales.
1897 Markov. Modelos dinámicos probabilísticos.
1905 Erlang. Líneas de espera.
Konig Egervary Asignación.
1937 Morgerstern. Lógica estadística.
1937 Von Newman. Teoría de juegos.
1939 Kantorovich. Distribución.
1947 G.Dantzig. Método SIMPLEX.
1950's Bellman. Programación dinámica.
Kun-Tucker. Programación no lineal.
Gomory. Programación entera.
Ford-Fulkerson. Redes de flujo.
AÑO. AUTOR. TECNICA DESARROLLADA.
Markowitz. Simulación.
Raifa. Análisis de decisiones.
Arrow-Karli. Inventarios.
Siglo XVI.....
Newton.
Lagrange Probabilidad y.
Cálculo Diferencial Laplace. Estadística.
Leibnitz.
Stieljes.
Metodología de Investigación de Operaciones:
1
Identifica el problema
(partes y objetivos)
2
Observar el Sistema
(información)
3
Formular un Modelo
Matemático (plantear )
4
Verificar el Modelo y
usarlo en predicción
(evaluar y derivar sol. )
5
Seleccionar alternativas
de solución
6
Presentar resultados
a la organización
7
Implementar y evaluar
recomendaciones
“Programación Lineal”
A pesar de que la programación lineal se empezó a estudiar desde finales del S.XIX no fue hasta mediados del presente siglo en que tuvo auge como técnica matemática aplicable a los problemas de la empresa.
El Dr. G. Damtzing desarrolló el método simplex y con ello hizo posible la solución de grandes problemas modelados con programación lineal que solo quedaban en la situación de estudios. Paralelamente a la invención de este método a partir de mediados del siglo se desarrollo la computación digital y se pudo tener resultados óptimos a los problemas estudiados que se quedaron como modelos.
La programación lineal es actualmente la técnica matemática utilizada mas actualmente gracias a que el algoritmo simplex es muy eficiente y al desarrollo de la computación.
Lo que se busca con la aplicación de la programación lineal es resolver problemas comunes y a la vez muy variados de la empresa en donde en general se tienen necesidades por satisfacer con cierto número de recursos limitados o escasos y con el objetivo de lograrlo en forma óptima. Esto significa la búsqueda de un valor máximo cuando se trata de beneficios; o bien la búsqueda de un mínimo cuando se trata de esfuerzos a desarrollar.
Un modelo de programación lineal es un conjunto de expresiones matemáticas las cuales deben cumplir la característica de linealidad que puede cumplirse siempre y cuando las variables utilizadas sean de primer grado. Además un modelo de P.L debe tener las propiedades de:
• Proporcionalidad• Aditividad (adición)• Divisibilidad• Certidumbre(certeza)
Antes de formular un modelo general para P.L conviene ilustrar algunos ejemplos que faciliten la interpretación de la generalización
Ejemplo de producción:
Una empresa ha dejado de fabricar ciertos productos, liberando de esta forma las cargas de producción que tenían sus equipos en los departamentos de maquinado. Ahora se tienen horas máquina que se pueden utilizar en los productos denominados 1,2,3 de la siguiente manera:
Máquina Horas por pieza de producto Horas Maq. Disponibles
1 2 3 por semana
Fresadora 9 3 5 500
Torno 5 4 - 350
Rectificadora 3 - 2 150
Utilidad
$/ pieza 50 20 25
Recomendación del Mínimo Mínimo Mínimo
Depto. Vtas a Prod. 30 15 20
Formular un modelo de P.L para este problema
• Definición de variables a utilizar en el método de programación lineal
Sea: Xj = numero de piezas de producto j(j=1,2,3) a fabricar para maximizar la utilidad.
• Función económica y objetivo:
MAX Z= 50X1 + 20X2 + 25X3 [ (Dls/Unidad) (Unidad/Sem)] = [Dls/Sem.]
sujeta a restricciones de horas máquina disponibles por semana
Fresadora : 9X1 + 3X2 + 5X3 * 500 horas máquina fresadora
Torno: 5X1 + 4X2 * 350 horas máquina torno
Rectificadora: 3X1 + 2X3 * 150 horas maquina rectificadora
Condiciones de signos pare las variables:
X1 * 30 piezas
X2 * 15 piezas
X3 * 20 piezas
Ejemplo de inversión:
Se desean invertir 2 millones de dólares en 6 tipos de inversión cuyas características son las siguientes:
Tipo de Interés Factor de Plazo promedio
Inversión Anual(%) Riesgo de inversión
1 8.5 0.02 8
2 9 0.01 2
3 8.5 0.38 5
4 14.3 0.45 6
5 6.7 0.07 2
6 13 0.35 4
El factor de riesgo significa la probabilidad de que el rendimiento real sea inferior al esperado. Se considera ventajoso un período promedio ponderado de inversión de ciando menos 5 años; pero el factor promedio ponderado de riesgo no debe ser superior a 0.20. La ley prohibe que la suma de las inversiones de los tipos 4 y 6 sea mayor al 25% del total de la inversión. Con P.L formule un modelo de P.L para decidir cómo invertir para maximizar el rendimiento de los 2 millones de dólares.
(SOL. A)
• Definición de variables
Sea: Xj = cantidad de dólares a invertir en el tipo j(j=1,2,3,4,5,6) para maximizar el rendimiento.
• Función objetivo
MAX Z= 0.085X1 + 0.09X2 + 0.85X3 + 0.143X4 + 0.067X5 +0.13X6
sujeta a restricciones:
1) X1 + X2 + X3 +X4 + X5 + X6 = 2,000.000 dls.
0.02X1 + 0.01X2 + 0.38X3 + 0.45X4 + 0.07X5 + 0.35X6 * 0.2 (2,000.000) = 400,000 dls.
8X1 + 2X2 + 5X3 +6X4 + 2X5 + 4X6 * 5 (2,000.000) = 10,000.000 dls.
X4 + X6 * 0.25 (2,000.000) = 5,000.000 dls.
X1, X2, X3, X4, X5, X6 * 0
(SOL. B)
• Definición de variables
Sea: Xj = Fracción capital a invertir en el tipo j(j=1,2,3,4,5,6) para maximizar el rendimiento.
• Función económica y objetivo:
MAX Z= 8.5X1 + 9X 2 + 8.5X3 + 14.3X 4 + 6.7X5 +13X 6
sujeta a restricciones:
1) X1 + X2 + X3 +X4 + X5 + X6 = 1 (capital)
0.02X1 + 0.01X2 + 0.38X3 + 0.45X4 + 0.07X5 + 0.35X6 * 0.2 (1) = 0.2
8X1 + 2X2 + 5X3 +6X4 + 2X5 + 4X6 * 5 (1) = 5
X4 + X6 * 0.25 (1) = 0.25
X1, X2, X3, X4, X5, X6 * 0
Ejemplo:
Problemas de mezcla en la inversión.
Definición de variables:
Sea: xj = Fracción del capital a invertir en la tipo j (j = 1,2,...,6) para maximizar el rendimiento.
Función objetivo:
Max. z = 8.5 x1 + 9 x2 + 8.5x3 + 14.3x4 + 6.7x5 + 13x6
Sujeto a restricciones:
x1 + x2 + x3 + x4 + x5 + x6 = 1
(Factor de riesgo)
0.02x1 + 0.01x2 + 0.38x3 + 0.45x4 + 0.07x5 + 0.35x6 " 0.2 (1) = 0.2
8x1 + 2x2 + 5x3 + 6x4 + 2x5 + 4x6 " 5(1) = 5
x4 + x6 " 0.25 (1) = 0.25
x1,x2,...,x6 " 0
[Ésta es otra forma de plantear el problema]
Problema de establecimiento de horario.
En un sector de la ciudad se tiene el siguiente requerimiento de policías:
PERIODO DEL DIA 1 2 3 4 5 6
HORA DEL DIA. 06-10 10-14 14-18 18-22 22-02 02-06
POLICIAS REQUERIDOS (")
300 350 425 450 250 200
El periodo #1 sigue inmediatamente del 6. Cada policía debe laborar 8 hrs consecutivas. Formular un modelo de programación lineal de este problema.
PERIODO/HORA 06-10 10-14 14-18 18-22 22-02 02-06
1
2
3
4
5
6
X1
X6
X1
X2
X2
X3
X3
X4
X4
X5
X5
X6
REQUERIDOS. " 300 " 350 " 425 " 450 "250 "200
Definición de variables:
Sea xj = Número de policías que inician el periodo j (j = 1,2,3,...,6)
Función objetivo:
Min. z = x1 + x2 + x3 + x4 + x5 + x6 (policías mínimos para cubrir turnos [6])
Sujeto a restricciones:
x1 + + x6 " 300
x1 + x2 " 350
x2 + x3 " 425
x3 + x4 " 450
x4 + x5 " 250
x5 + x6 " 200
.... toda xj " 0
Ejemplo:
Problema de aprovechamiento de recursos.
Una empresa papelera recibe un pedido de rollos de papel de la misma calidad y espesor para los siguientes anchos:
500 rollos de 30 in, 450 rollos de 45 in y 150 rollos de 56 in.
En las bodegas de la empresa solo se tiene existencia en esta calidad de papel en ancho de 108 in, por lo que se piensa deben someterse a un proceso de corte longitudinal si se desea cumplir la demanda de este pedido. Formular un modelo de programación lineal correspondiente a este problema.
108 cm CORTE
Definición de variables:
Sea xj = # de cortes del tipo j (j = 1,2,....,5) necesarios para cumplir el pedido con mínimo desperdicio de papel.
Función objetivo (o económica):
Min. z = 18x1 + 3x2 + 22x3 + 18x4 + 7x5
Sujeto a restricciones:
3x1 + 2x2 + x3 " 500 rollos de 30'
x2+ x4 + x5 " 450 rollos de 45'
x3 + x5 " 150 rollos de 56' ...las unidades:
Rollos
Corte Corte = Rollos ...para restricciones.
in
corte corte = in ...para función objetivo.
Toda xj " 0
Problema de almacenamiento en el transporte.
Un barco tiene las siguientes capacidades de almacenamiento en sus bodegas de popa, centro y proa. Los dueños del barco pueden elegir una porción o toda la carga de los productos A, B y C, cuyas características se tabulan a continuación. Además, para preservar el equilibrio del barco debe cumplirse con una carga proporcional a la capacidad de las respectivas bodegas.
BODEGA CAPACIDAD CAPACIDAD
TONELADAS m3
PROA (1) 3000 130000
CENTRO (2) 2000 10000
POPA (3) 1500 30000
PRODUCTOSTNS A TRANSPORTAR
m3/TonUTILIDAD (MILES
DLS/TN)
A 3500 60 8
B 2500 50 7
C 2000 25 6
Definición de variables:
Sea: xij = toneladas del producto j (j = A,B,C) a cargar en la bodega i (i = 1,2,3) para maximizar la utilidad en el viaje.
Función objetivo:
Max z = 8(x1A + x2A + x3a) + 7(x1B + x2B + x3B) + 6(x1C + x2C + x3C) ...con unidades
Miles de dls.
Ton Ton = miles de dólares
Sujeto a restricciones:
x1A + x1B + x1C " 3000 Ton.
Capacidad en Ton x2A + x2B + x2C " 2000
x3A + x3B + x3C " 1500
60x1A + 50x1B + 25x1C " 130000 m3.
Capacidad en Ton 60x2A + 50x2B + 25x2C " 100000
60x3A + 50x3B + 25x3C " 30000
x1A + x1B + x1C " 3500 Ton.
Capacidad en Ton x2A + x2B + x2C " 2500
x3A + x3B + x3C " 2000
Proporción de carga en las bodegas:
x1A + x1B + x1C = x2A + x2B + x2C = x3A + x3B + x3C " 1
3000 2000 1500
Modelo de programación lineal general.
Definición de variables:
Sea xj = #.... ; j = 1, 2, 3....n
Función objetivo:
Términos del primer grado que se sumen.
Max. o Min. z = C1x1 + C2x2 + ... + Cjxj + ... + Cnxn
...donde n = # total de valores
j = ocurrencia.
Sujeto a restricciones: i = 1, 2, 3, ... , m
a11x1 + a12x2 + ... + a1jxj + ... + a1nxn " = " b1
a21x1 + a22x2 + ... + a2jxj + ... + a2nxn " = " b2
·
·
ai1x1 + ai2x2 + ... + aijxj + ... + ainxn " = " bi
·
·
am1x1 + am2x2 + ... + amjxj + ... + amnxn " = " bm
Condiciones de signo para variables: toda xj " 0
Modelo general de programación lineal resumido en:
Sumatorias.
Definición de variables: sea xj = # ; j = 1, 2, 3, ... , n
Función objetivo: (Max./Min.) z = " cjxj
... sujeta a:
"aijxj " = " bi i = 1, 2, 3, ... , m
... condiciones de signo: " xj " 0
Con vectores.
(Max./Min.) z = Cx
... sujeto a: Ax " = " b
x " 0
Propiedades que debe de seguir el modelo de programación lineal.
Proporcionalidad. En el modelo de programación lineal los pagos deben ser proporcionales.
El modelo de programación lineal es estático, plantea una situación del momento.
x = progreso de la actividad
Aditividad. Siempre los pagos se suman.
Requerimientos.
Costos y
Utilidades.
Divisibilidad. Las variables involucradas en el modelo de programación lineal pueden no ser un número entero...
Si los valores son muy pequeños no importa el redondeo.
Si son muy altos afecta el redondeo.
Certidumbre. Todos los parámetros que se manejan deben ser pasados con certeza.
Métodos de solución del modelo de programación lineal.
El modelo de programación lineal se puede resolver tanto gráfica como analíticamente, pero para problemas de tamaño común que se encuentran como aplicaciones, la solución gráfica no es útil. En cambio, la solución analítica utilizando el algorítmo SIMPLEX que se verá posteriormente es el procedimiento normal para la búsqueda de la solución óptima de un problema.
Método de solución gráfica.
La gran limitación que se tiene con el método de solución gráfica con programación lineal es que su aplicación sólo puede hacerse a problemas con dos y cuando mucho tres variables, en este curso se ejemplifica para problemas solo con dos variables.
A pesar de tal inconveniente, el método gráfico resulta útil para exposición e ilustración de los conceptos de la programación lineal. Ejemplo:
Max. z = 3x1 + 5x2 ... sujeto a:
x1 " 4 .......... (1)
2x2 " 12 .......... (2)
3x1 + 2x2 " 18 .......... (3) x1 ; x2 " 0
Expresar geométricamente el sistema dentro del gráfico; rango de valores.
x1 " 4 2 x2 " 12 3 x1 + 2 x2 " 18
(1) (4,0) F (2) x2 " 6 (3) x1 x2
(0.6) A
0 9
• 0
(0,9) B
(6,0) J
Las desigualdades son fronteras o división del espacio plano. Si la recta no pasa por el origen, se toman en cuenta las coordenadas de O.
Espacio solución: Satisface al sistema (factible) posible. Conjunto de soluciones factibles.
Si se satisface la restricción, el origen pertenece al semiplano que satisface la restricción.
(1) (3) 3x1 = 12
H x1= 4 x1 = 4
3x1 + 2x2 = 18 H = (4,3)
2x2 = 6 ; x2 = 3
Trazo de la función económica
VALOR RELATIVO
z (5,0)
(0,3)
Múltiplo de los coeficientes que nos dan la pendiente de la función.
z = 15 supuesto
...trasladar a z en cualquier dirección respetando la pendiente (paralela a la obtenida).
Haciendo coincidir z con todos los vértices conocidos nos damos cuenta que a medida que se aleja del origen crece. El punto máximo es C.
... donde z = 3(2) + 5(6) = 36
Max z = 36
Los vértices son capaces de generar lo OPTIMO.
CONVEXIDAD: Si dados dos puntos cualesquiera contenidos en el conjunto y se unen mediante el segmento y si se cumple para todo par de puntos, es convexo.
Para resolver mediante el algorítmo SIMPLEX, el conjunto debe ser CONVEXO.
CONJUNTO CONVEXO: un conjunto es convexo si dados dos puntos A y B cualesquiera, contenidos en el mismo, el segmento de recta que los une queda contenido en dicho conjunto totalmente.
DEFINICION MATEMATICA: Un conjunto convexo se forma por combinación convexa lineal entre dos puntos A y B como sigue:
P = A + B(1 - ) para 0 " " 1
...donde A y B son vectores y es un escalar.
Ejemplo: Obtener un punto p que sea CCL entre dos vértices A y F con = ½.
P = ((0,6) ½) + (4,0) (1 - ½)
P = (0,3) + (2,0)
P = (2,3)
OJO: NO SE PUEDEN GENERAR LOS VERTICES.
METODO GRAFICO.
Ejemplo: Max z = 3x1 + 5x2
...sujeta a:
x1 " 4 ... (1)
2x2 " 12 ... (2)
3x1 + 2x2 " 18 ... (3) x1 ; x2 " 0
CONJUNTO CONVEXO: Un conjunto es convexo si dados dos puntos A y B contenidos en el mismo, el segmento de recta que losa une queda contenido totalmente en dicho conjunto.
DEFINICION MATEMATICA: Un conjunto convexo se forma por combinación convexa lineal entre dos puntos A y B como sigue:
P = A + B(1 - ) para 0 " " 1
Ejemplo: Obtener un punto P que sea CCL entre los vértices A y F con = ½
P = (0,6) ½ + (4,0) (1 - ½9 = (0,3) + (2,0) " P = (2,3)
(pueden calcularse así todos los puntos a excepción de los vértices)
Cuando se tienen desigualdades ha y que convertir a igualdades (ec. lineales).
Tomando la restricción 3:
En este caso coincidió, pero no lo sabíamos, si no fuera así, necesitamos una nueva variable “x” llamada holgura y retomando el ejemplo anterior se tendría:
x1 + x3 = 4 ... (1)
2x2 + x4 = 12 ... (2)
3x1 + 2x2 + x5 = 18 ... (3) x3 , x4 , x5 HOLGURA.
x1 ... x5 " 0
...y se tiene un sistema ampliado a 5 dimensiones.
VERTICE X1 X2 X3 X4 X5 OBNES.
O 0 0 4 12 18 FACTIBLE
A 0 6 4 0 6 FACTIBLE
C 2 6 2 0 0 FACTIBLE
F 4 0 0 12 6 FACTIBLE
H 4 3 0 6 0 FACTIBLE
B 0 9 4 -6 0
J 6 0 -2 12 0
R 4 6 0 0 -6
... en las observaciones se señalan los puntos como factibles porque cumplen con la no negatividad, pero los puntos B, J y R no cumplen con la condición de no negatividad, lo cual nos indica que no son factibles.
Retomando el sistema anterior, solo cambiaremos el signo de desigualdad de (3) que será ".
3x1 + 2x2 " 18 ... (3)
Agregaremos al sistema ahora una 4ª restricción, siguiendo con la condición de no negatividad.
3x1 + 2x2 " 18 ... (4)
(x1 , x2 )
si .... (0 , 12 ) 4
y si ... (8 , 0 )
Ampliando el sistema inmediato anterior, podemos hacer lo mismo que antes con 1, 2 y 4, pero no con 3 porque el signo es " y nos indica que mínimo 18 y necesitaremos una VARIABLE SUPERFLUA o de HOLGURA NEGATIVA.
VERTICE X1 X2 X3 X4 X5 X6 OBSERVACIONES
O 0 0 4 12 -18 24 NO FACTIBLE
A 0 6 4 0 -6 12 NO FACTIBLE
C 2 6 2 0 0 6 FACTIBLE
F 4 0 0 12 -6 12 NO FACTIBLE
H 4 3 0 6 0 6 FACTIBLE
B 0 9 4 -6 0 6 NO FACTIBLE
J 6 0 -2 12 0 6 NO FACTIBLE
R 4 6 0 0 6 0 FACTIBLE
Ojo: en el renglón R de la tabulación anterior hay tres ceros, a diferencia del resto de la misma tabulación y de la anterior de 5 dimensiones. Esto se debe a que por ese punto pasan 3 rectas y por el resto convergen solo dos rectas.
En el punto “R” intersectan:
1 2
R 1 4
• 4
... y se dice que el punto como tal es NO UNICO.
Y tomando en consideración que para un solo punto se requiere de una intersección, el resto de los puntos es UNICO. Se dice entonces que el punto R tiene:
SOLUCION FACTIBLE
SOLUCION NO UNICA
... y solo cuando se dan las dos anteriores soluciones se llama SOLUCION DEGENERADA.
Un vértice no único se establece cuando hay redundancia.
Observaciones características.
...el vértice O es NO FACTIBLE y UNICO.
A es NO FACTIBLE y UNICO.
C es FACTIBLE y UNICO.
F es NO FACTIBLE y UNICO.
H es FACTIBLE y UNICO.
B es NO FACTIBLE y UNICO.
J es NO FACTIBLE y UNICO.
R es FACTIBLE, UNICO y DEGENERADO.
...y por lo tanto, del gráfico anterior decimos entonces que C y H son no degeneradas.
DEFINICIONES:
SOLUCION: Es un conjunto de valores para las variables o bien un vector X = (x1 , x2 , ... , xj , xj+1 , ... , xn , xn+1 , ... , xn+m ) que satisface al conjunto de restricciones
SOLUCION FACTIBLE: Es un conjunto de valores para las variables o bien un vector X = (x1 , x2 , ... , xj , xj+1 , ... , xn , xn+1 , ... , xn+m ) que satisface al conjunto de restricciones
...y además satisface a toda xj " 0 .
SOLUCION BASICA: Es una solución que se obtiene al hacer nulas, al menos, (m+n)-m variables, en donde
m = # total de restricciones,
n = # de variables de decisión (originales)
[en el ejemplo, m = 3 y n = 2 ! (3+2) - 3 = 2 ... en el ejemplo de 4 restricciones m = 4 y n = 2, resultando (4 + 2) - 4 = 2 .... y por esto, en el sistema ampliado se tiene en VERTICE : SOLUCIONES BASICAS].
...y se resuelve el sistema para las restantes.
SOLUCION BASICA FACTIBLE: Es una solución básica que cumple toda xj " 0.
SOLUCION DEGENERADA: Es una solución básica factible que tiene menos de m variables estrictamente positivas.
SOLUCION NO DEGENERADA: Es una solución básica factible con exactamente m variables estrictamente positivas.
SOLUCION OPTIMA: Es una solución básica factible que optimiza la función
La `solución' en el gráfico 1 y 2 sería solo el área sombreada.
La `solución factible' en 1 cuando cumple con " 0 y en 2 coincide con `solución' (polígono A, C, H, F, O)
`Solución básica' en 1 todos los vértices pero en 5 dimensiones y en 2 solo C, R, H pero en 6 dimensiones.
Ejemplo: Mix z = 4x1 + 3x2
...sujeta a:
x1 + x2 " 6 ... (1)
2x1 - x2 " 0 ... (2)
x1 " 2 ... (3)
x1 ; x2 " 0
x1 , x2 2x1 = x2 x1 , x2
, 6) B 1 2 2(0) = 1(0) : (0,0) O 3 (2 , 0) F
(6 , 0) A 2(1) = 1(2) : (1,2)
2(2) = 1(4) : (2,4) C
El conjunto anterior se diferencía de los anteriores porque es un CONJUNTO ABIERTO y al pedir un máximo, se tendría una solución SIN LÍMITE.
Recordar que si el origen se encuentra en el conjunto factible, al pedirse minimizar, esta se llama solución trivial.
4(2) + 3(4) = 20 ....[Min]
Considerando Min z
4(6) + 3(0) = 24
Resolviendo analíticamente:
x1 + x2 - x3 " 6
2x1 - x2 - x4 " 0
x1 - x5 " 2 x1, x2 , x3 , x4 , x5 " 0
(los vértices en 2 dimensiones pasan a ser soluciones básicas en 3 dimensiones)
VERTICES O SOLUCIONES BASICAS
X1 X2 X3 X4 X5 CARACTERISTICAS
B 0 6 0 -6 -2 N.FACTIBLES, UNICA
F 2 0 -4 4 0 N.FACTIBLES, UNICA
O 0 0 -6 0 -2N.FACTIBLES, NO UNICA
C 2 4 0 0 0N.FACTIBLES, NO UNICA, DEGE.
A 6 0 0 12 4 N.FACTIBLES, UNICA
La degeneración en C se provoca por una restricción redundante : 3 C se genera de la simultaneización de las rectas 1,2 ; 2,3 ; 1,3 y se tienen 3 soluciones básicas.
Como en el gráfico anterior el número de soluciones básicas es infinito y hacemos o tomamos solo soluciones básicas:
# máximo de m + n = m + n = m + n !
soluciones básicas m n m! n!
m = # de restricciones.
n = # de variables de decisión.
# = 3 + 2 = 3 + 2 = 5 = 5 = 5 ! = 10
3 2 3 2 3! 2!
En los ejemplos anteriores no cambia el número máximo, pero las líneas horizontal y vertical o cruzan el eje contrario.
El modelo de programación lineal se puede presentar en diferentes formas y algunas de ellas resultan importantes para el manejo de los temas siguientes del curso.
FORMA CANONICA: Esta es útil para el manejo del tema que se refiere al problema dual de cualquier problema de programación lineal. La forma canónica aceptable y reconocida en la mayoría de los textos debe cumplir con lo s siguientes requisitos:
Función objetivo maximizar.
Restricciones del tipo ".
Condiciones de negatividad para variables.
Otra forma legítima para considerar como canónica es cumpliendo con los siguientes requisitos:
Función objetivo de minimizar.
Restricciones del tipo ".
Condiciones de no negatividad para variables.
FORMAS CANONICAS.
Maximizar. Minimizar.
z = Cx z = Cx
sujeto a: sujeto a:
Ax " b Ax " b
x " 0 x " 0
Max z = 3x1 + 5x2 (-1) Min z = -3x1 - 5x2
Suj. a: Suj. a:
x1 " 4 -x1 " -4
2x2 " 12 - 2x2 " -12
3x1 + 2x2 " 18 -3x1 - 2x2 " -18
x1 ; x2 " 0
FORMA ESTANDAR: El modelo de programación lineal para resolverse, necesita arreglarse para igualdades, lo cual se consigue utilizando tanto variables de holgura como variables superfluas. Lo anterior da lugar a la presentación del modelo cumpliendo con l os siguientes requisitos:
Función objetivo para Max. o bien Min.
Restricciones del tipo =.
Lado derecho de restricciones no negativo.
Condiciones de no negativo para variables.
FORMA IRREGULAR: El modelo de programación lineal generalmente se presenta en forma irregular; es decir, no cumple con la forma canónica ni tampoco forma estándar, pero mediante el procedimiento algebraico se puede conseguir convertir a un modelo que cumpla las formas mencionadas tal como se ve en el siguiente ejemplo:
Formas equivalentes del modelo de programación lineal.
Ejemplo: Max z = 5x1 - x2 + 3x3
...sujeta a:
x1 + 2x2 + 4x3 " 12 ... (1)
x2 + x3 = 5 ... (2)
2x1 - x2 + 5 x3 " 6 ... (3) x1 ; x2 " 0 ; x3 LIBRE
Formas canónicas (en forma vectorial)
Max z = Cx Min z = Cx
sujeto a: sujeto a:
Ax " 0 Ax " 0
x " 0 x " 0
.....en el caso anterior conviene usar Max para no invertir la función objetivo.
Forma canónica.
Algo que incomoda es x1 " 0 y entonces se hace un acuerdo matemático para crear otra variable x1 como se hace a continuación:
x1 " 0 ! -x1' = x1 " 0
...la hicimos igual a x1' y luego multiplicamos todo por -1.
(-x1' = x1 " 0) (-1) =! x1' = -x1 " 0
...ahora para x3 :
x3 = (x3+ - x3-)
x3+ ; x3- " 0
si... x3+ > x3- ! x3 > 0
x3+ < x3- ! x3 < 0
x3+ = x3- ! x3 = 0
iniciando...
Max z = 5x1 - x2 + 3x3
! z = 5x1' - x2 + 3x3+ - 3x3-
...sujeta a:
x1' + 2x2 + 4x3+ - 4x3- " 12 ... (1)
Para la restricción original (2) no tengo un proceso específico, pero se ponen en sustitución de esta restricción de igualadad a 2 restricciones de desigualdad con signos opuestos (mismo términos).
x2 + x3+ - x3- " 5 ........ (2+)
x2 + x3+ - x3- " 5 ........ (2-)
...pero como no tenemos que tener aquí " , entonces multiplicamos a 2- por (-1) y queda de la siguiente forma:
-x2 - x3+ + x3- " -5 ........ (2-)
Pasando a la restricción (3), hay que multiplicarla por (-1) sin dejar de tomar el signo para x1'.
2x1' + x2 - 5x3+ + 5x3- " -6
x1' = -x1 " 0 ; x2 , x3+ ; x3- " 0
Agrupando todo lo anterior resulta la forma canónica.
Forma estándar.
Max/Min z = Cx
Sujeta a: Ax=b
x " 0
Max z = 5x1' - x2 + 3x3' - 3x3'
Sujeta a: (tomando las originales y tomando los arreglos para variables)
- x1' + 2x2 + 4x3+ - 4x3- + x4 = 12 ..... (1)
x2 + x3+ - x3- = 5 ..... (2)
- 2x1' - x2 + 5x3+ - 5x3- - x5 = 6 ..... (3)
SUPERFLUA
x1' ; x2 ; x3+ ; x3- ; x4 y x5 " 0
......quedando de esta manera la forma estándar.
Ejercicio:
Min z = 4x1 + 3x2 - x3
Sujeta a:
2x1 - x2 + 2x3 = 14 ..... (1)
x1 + x2 + 3x3 " 8 ..... (2)
3x2 + 2x3 " 4 ..... (3)
x1 LIBRE ; x2 " 0 ; x3 " 0
Forma canónica.
-x2' = x2 " 0 x1 = (x1+ - x1-) x1+ > x1- ! x1 > 0
x2' = -x2 " 0 x1+ " 0 ; x1- " 0 x1+ < x1- ! x1 < 0
x1+= x1- ! x1 = 0
Min z = 4x1+ - 4x1- - 3x2' - x3
Sujeta a:
(2x1+ - 2x1- + 2x2' + 2x3 " 14) (-1)
2x1+ - 2x1- + 2x2' + 2x3 " 14 ..... (1-)
-2x1+ + 2x1- - 2x2' - 2x3 " -14 ..... (1+)
(x1+ - x1- - 2x2' + 3x3 " 8) (-1)
-x1+ + x1- + 2x2' - 3x3 " 8 ..... (2)
- 3x2' + 2x3 " 4 .....(3)
!
-2x1+ + 2x1- - x2' - 2x3 " -14 ..... (1+)
2x1+ - 2x1- + x2' + 2x3 " 14 ..... (1-)
-x1+ + x1- + 2x2' - 3x3 " 8 ..... (2)
- 3x2' + 2x3 " 4 ..... (3)
x1+ ; x1- ; x2' ; x3 " 0
Forma estándar.
-x2' = x2 " 0 x1 = (x1+ - x1-)
x2' = -x2 " 0 x1+ " 0 ; x1- " 0
Min z = 4x1+ - 4x1- - 3x2' - x3
Sujeta a:
2x1+ - 2x1- + x2' + 2x3 " 14 ..... (1)
x1+ - x1- - 2x2' + 3x3 + x4 " 8 ..... (2)
- 3x2' + 2x3 - x5 " 4 ..... (3)
x1+ ; x1- ; x2' ; x3 ; x4 ; x5 " 0
MÉTODO SIMPLEX.
El método símplex fue desarrollado en 1947 por el Dr. George Dantzig y conjuntamente con el desarrollo de la computadora hizo posible la solución de problemas grandes planteados con la técnica matemática de programación lineal.
El algorítmo denominado símplex es la parte medular de este método; el cual se basa en la solución de un sistema de ecuaciones lineales con el conocido procedimiento de Gauss-Jordan y apoyado con criterios para el cambio de la solución básica que se resuelve en forma iterativa hasta que la solución obtenida converge a lo que se conoce como óptimo.
Las definiciones siguientes fundamentadas en 3 importantes teoremas, ayudan a entender la filosofía de este eficiente algorítmo.
Teoremas de la Programación Lineal.
El conjunto de soluciones factibles para un problema de P.L. es un conjunto convexo.
La solución óptima del problema de programación lineal , si existe, es un punto extremo (vértice) del conjunto de soluciones factibles. Si dicha solución óptima se tiene para más de un punto extremo, entonces también optimiza en cualquier punto que sea combinación convexa lineal entre los dos vértices que optimiza.
...y suponiendo que la función objetivo fuera:
Max zC = 6x1 + 4x2 ! 6(2) + (6) = 36
Max zH = 6(4) + 4(3) = 36
Max zA = 6(0) + 4(6) = 24
Calcular P como CCL entre C y H con = ¼
P = C + (1 - ) H
P = ¼ (2 , 6) + ( 1 - ¼) (4 , 3)
P = ( ½ , 3/2) + (3 , 9/4) = (7/2 , 15/4)
... y retomando el gráfico anterior:
ZP = 6 (7/2) + 4 (15/4) = 36
El número máximo de puntos extremos (vértices) por revisar en la búsqueda de la solución óptima del problema es finito y coincide con el número máximo de soluciones básicas únicas que se pueden determinar mediante el binomio...
m + n = m + n = (m+n) !
m n m! n!
DIAGRAMA FUNCIONAL DEL
METODO SIMPLEX.
NO
SI
CRITERIOS DEL ALGORITMO
SIMPLEX PARA EL CAMBIO DE BASE.
El algorítmo símplex maneja exclusivamente soluciones básicas y que cumplan con factibilidad; es decir, todas las variables deben ser no negativas. Por lo tanto, para el manejo de las soluciones básicas factibles y su valoración, requiere de la aplicación de ciertos criterios fundamentados en los teoremas ya mencionados. Por cada intento de cálculo es necesario aplicar los siguientes criterios:
• Criterio de optimalidad. Se aplica en el algorítmo símplex para determinar entre las variables no-básicas, una que entre a la base, eligiendo aquella no-básica con el coeficiente más negativo en el renglón z de la tabla símplex; si el problema tiene el objetivo de maximizar. En caso contrario, es decir, para minimizar, debe elegirse para variable entrante a la base a aquella que tenga el coeficiente más positivo en el renglón z de la tabla.
• Criterio de factibilidad. Se aplica en el algoritmo símplex para determinar entre las variables básicas a una que salga de la base, aplicando la siguiente función.
x i
Min ; solo a i k > 0
a i k
Esto es válido tanto para problemas de maximizar como de minimizar.
Elemento pivote. Se declara como elemento pivote a aquél coeficiente que se ubica en el cruce de la columna `k' y el renglón `i' elegidos en los dos criterios ya anotados.
Ejemplo: Resolver con el método símplex el siguiente modelo de programación lineal.
Max z = 3x1 + 5x2 ...sujeta a:
x1 " 4 (1)
2x2 " 12 (2)
3x1 + 2x2 " 18 (3) x1 ; x2 " 0
... conseguir la forma estándar
Max z = 3x1 + 5x2 ...sujeta a:
x1 + x3 " 4 (1)
Bloque #1 2x2 + x4 " 12 (2)
3x1 + 2x2 + x5 " 18 (3) x1 ; x2 ; x3 ; x4 , x5 " 0
holguras
FORMA MATRICIAL.