PROGRAMACION LINEAL

Programación Lineal
La PL es un método matemático de resolución de problemas donde el objetivo es optimizar (maximizar o minimizar) un resultado a partir de seleccionar los valores de un conjunto de variables de decisión, respetando restricciones correspondientes a disponibilidad de recursos, especificaciones técnicas, u otras condicionantes que limiten la libertad de elección.
La maximización de beneficios nos llevará a problemas en los que tengamos que determinar la producción: qué se debe fabricar y en qué cantidades para que se obtenga el máximo beneficio teniendo en cuenta las limitaciones técnicas y humanas. En el campo agrícola la adecuada utilización de los terrenos, los cupos de producción, ..., etc.
En los problemas de mínimos podremos calcular los costes mínimos para alimentar a los animales de una granja condicionado a los requerimientos nutricionales. Minimización de la contaminación atmosférica, optimización de recursos humanos, ..., etc.
Un problema de programación lineal es un problema en cual debemos hallar el valor máximo o mínimo de una expresión lineal
ax + by + cz + . . .
(llamada la función ojectiva), sujeta a unas restricciones lineales de la forma
Ax + By + Cz + . . .≤ N
o
Ax + By + Cz + . . .≥ N.
El valor más grande o más pequeño de la función objetiva se llama el valor óptimo, y un conjunto de valores de x, y, z, . . . que se resultan en el valor óptimo es la solución óptima. Las variables x, y, z, . . . se llaman las variables decisión.

Método gráfico
El método gráfico para solucionar a un problema de programación lineal es el siguiente:
Dibuje la región factible de los restricciones.
Calcule las coordenadas de los puntos extremos (puntos de esquina).
Sustituya las coordenadas de los puntos de esquina en la función objetiva para ver cual da el valor óptimo. Este punto da la solución del problema de programación lineal.
Si la región factible no es acotada, este método puede ser erróneo: soluciones óptimas siempre existen cuando la región factible está acotada, pero pueden no existir en el caso no acotado. Si la región factible no es acotada, estamos minimizando una función ojectiva cuyas coeficientes son no negativos, entonces existe una solución dado por este método.

Para determinar si existe una solución en el caso general no acotado:
Acote la región por añadir una recta horizontal por encima del punto de esquina más arriba, y una recta vertical a la derecha del punto de esquina que esté mas hacia la derecha.
Calcule las coordenadas de los puntos nuevos de esquina que se obtiene.
Halle el punto de esquina donde ocurre el valor óptimo de la función ojectiva.
Si el valor óptimo se ocurre a un punto de esquina de la región original (no acotada) entonces existe la solución óptima a aquel punto. Si ocurra el valor óptimo solo a un punto nuevo de esquina, entonces el problema de programación lineal no tiene soluciones.

Problema de maximización estándar
Una problema de maximización estándar con n incógnitas es un problema de programación lineal en lo que necesitamos maximizar (no minimizar) la función ojectiva, sujeta a restricciones de la forma
x ≥ 0, y ≥ 0, z ≥ 0, . . . ,
y restricciones adicionales de la forma
Ax + By + Cz + . . . ≤ N,
donde A, B, C, . . . y N son números con N no negativa.
Observe que la desigualdad aquí debe ser una "≤," y no "=" o "≥."
Método simplex para problemas de maximización estándar
Para solucionar un problema de maximización estándar por el método simplex, seguimos los siguientes pasos:
Paso 1. Convierta las desigualdades en igualdades por introducir variables de holgura por cada una de las restricciones, para convertirlas en igualdades, y escriba las restricciones en forma estándar como muestra enfrente en el ejemplo.
Paso 2. Escriba la tabla inicial simplex.
Paso 3. Escoja la columna pivote: Encuentre el número negativo mayor (en valor absoluto) en el último renglón (excluyendo la entrada más hacia la derecha). Su columna es la columna pivote. (Si hay más que una candidata, escoja alguna.) Si no hay números negativo en último renglón son cero (excluyendo la entrada más hacia la derecha), entonces está terminado: la corriente solución básica maximiza la función ojectiva (la solución básica está descrito más abajo).
Paso 4. Escoja el pivote en la columna pivote: El pivote debe ser una entrada positiva. Para cada entrada positiva b en la columna pivote, calcule la razón a/b, donde a es la entrada de la última columna (valores solución) del renglón. Entre estas razones de prueba, escoja la más pequeña. La entrada correspondiente b es el pivote.

Paso 5. Use el pivote para despejar la columna en la manera normal descrito en el tutorial del método Gauss Jordan, y sustituya la etiqueta de la columna pivote por la etiqueta del reglón pivote. La etiqueta original es la variable saliendo y la nueva etiqueta es la variable entrando.
Solución básica
Para obtener la solución básica que corresponde a alguna tabla del método simplex, iguale a cero a todas las variables que no aparecen como etiquetas de renglones (estas son las variables inactivas).
El valor de una variable que no aparece como una etiqueta de renglón (es decir, una variable activa) es la razón a/b, en la que a es la entrada de la última columna del renglón y a es la entrada de aquel renglón cuya columna tiene la misma etiqueta.
Método Simplex para problemas de minimización
Para solucionar un problema de minimización por el método simplex, se convierte el problema en un problema de maximización por negar la función objetiva: En vez de minimizar c, se maximiza p = -c.
Ejemplo


Minimizar C = 3x + 4y sujeta a
3x - 4y ≤ 12, x + 2y ≥ 4 x ≥ 1, y ≥ 0.
La región factible para este conjunto de restricciones fue mostrada más arriba. Aquí está otra vez con los puntos de esquinas indicados.

Programación Lineal
La PL es un método matemático de resolución de problemas donde el objetivo es optimizar (maximizar o minimizar) un resultado a partir de seleccionar los valores de un conjunto de variables de decisión, respetando restricciones correspondientes a disponibilidad de recursos, especificaciones técnicas, u otras condicionantes que limiten la libertad de elección.
La maximización de beneficios nos llevará a problemas en los que tengamos que determinar la producción: qué se debe fabricar y en qué cantidades para que se obtenga el máximo beneficio teniendo en cuenta las limitaciones técnicas y humanas. En el campo agrícola la adecuada utilización de los terrenos, los cupos de producción, ..., etc.
En los problemas de mínimos podremos calcular los costes mínimos para alimentar a los animales de una granja condicionado a los requerimientos nutricionales. Minimización de la contaminación atmosférica, optimización de recursos humanos, ..., etc.
Un problema de programación lineal es un problema en cual debemos hallar el valor máximo o mínimo de una expresión lineal
ax + by + cz + . . .
(llamada la función objetiva), sujeta a unas restricciones lineales de la forma
Ax + By + Cz + . . .≤ N
o
Ax + By + Cz + . . .≥ N.





Función Objetivo
La función objetivo puede ser:
ó
Donde:
f = coeficientes conocidos.
Ejemplo: Que es la función objetivo por maximizar.

Maíz
Trigo
Elementos 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>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>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>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
Un problema de programación lineal es un problema en cual debemos hallar el valor máximo o mínimo de una expresión lineal
ax + by + cz + . . .
(llamada la función ojectiva), sujeta a unas restricciones lineales de la forma
Ax + By + Cz + . . .≤ N
o
Ax + By + Cz + . . .≥ N.
El valor más grande o más pequeño de la función objetiva se llama el valor óptimo, y un conjunto de valores de x, y, z, . . . que se resultan en el valor óptimo es la solución óptima. Las variables x, y, z, . . . se llaman las variables decisión.

Método gráfico
El método gráfico para solucionar a un problema de programación lineal es el siguiente:
Dibuje la región factible de los restricciones.
Calcule las coordenadas de los puntos extremos (puntos de esquina).
Sustituya las coordenadas de los puntos de esquina en la función objetiva para ver cual da el valor óptimo. Este punto da la solución del problema de programación lineal.
Si la región factible no es acotada, este método puede ser erróneo: soluciones óptimas siempre existen cuando la región factible está acotada, pero pueden no existir en el caso no acotado. Si la región factible no es acotada, estamos minimizando una función objetiva cuyos coeficientes son no negativos, entonces existe una solución dado por este método.




Para determinar si existe una solución en el caso general no acotado:
Acote la región por añadir una recta horizontal por encima del punto de esquina más arriba, y una recta vertical a la derecha del punto de esquina que esté mas hacia la derecha.
Calcule las coordenadas de los puntos nuevos de esquina que se obtiene.
Halle el punto de esquina donde ocurre el valor óptimo de la función ojectiva.
Si el valor óptimo se ocurre a un punto de esquina de la región original (no acotada) entonces existe la solución óptima a aquel punto. Si ocurra el valor óptimo solo a un punto nuevo de esquina, entonces el problema de programación lineal no tiene soluciones.
Problema de maximización estándar
Una problema de maximización estándar con n incógnitas es un problema de programación lineal en lo que necesitamos maximizar (no minimizar) la función ojectiva, sujeta a restricciones de la forma
x ≥ 0, y ≥ 0, z ≥ 0, . . . ,
y restricciones adicionales de la forma
Ax + By + Cz + . . . ≤ N,
donde A, B, C, . . . y N son números con N no negativa.
Observe que la desigualdad aquí debe ser una "≤," y no "=" o "≥."
Método simplex para problemas de maximización estándar
Para solucionar un problema de maximización estándar por el método simplex, seguimos los siguientes pasos:
Paso 1. Convierta las desigualdades en igualdades por introducir variables de holgura por cada una de las restricciones, para convertirlas en igualdades, y escriba las restricciones en forma estándar como muestra enfrente en el ejemplo.
Paso 2. Escriba la tabla inicial simplex.
Paso 3. Escoja la columna pivote: Encuentre el número negativo mayor (en valor absoluto) en el último renglón (excluyendo la entrada más hacia la derecha). Su columna es la columna pivote. (Si hay más que una candidata, escoja alguna.) Si no hay números negativo en último renglón son cero (excluyendo la entrada más hacia la derecha), entonces está terminado: la corriente solución básica maximiza la función ojectiva (la solución básica está descrito más abajo).
Paso 4. Escoja el pivote en la columna pivote: El pivote debe ser una entrada positiva. Para cada entrada positiva b en la columna pivote, calcule la razón a/b, donde a es la entrada de la última columna (valores solución) del renglón. Entre estas razones de prueba, escoja la más pequeña. La entrada correspondiente b es el pivote.
Paso 5. Use el pivote para despejar la columna en la manera normal descrito en el tutorial del método Gauss Jordan, y sustituya la etiqueta de la columna pivote por la etiqueta del reglón pivote. La etiqueta original es la variable saliendo y la nueva etiqueta es la variable entrando.

MINIMIZACION ( CUADRO)

CONCEPTOS GENERALES DEL METODO SIMPLEX

CONCEPTOS GENERALES DEL METODO SIMPLEX

El método gráfico presentado anteriormente demuestra que la PL óptima está siempre asociada con un punto extremo o de esquina, del espacio de soluciones. Esta idea conduce precisamente a la creación del método símplex. Básicamente, lo que hace el método símplex es trasladar la definición geométrica del punto extremo a una definición algebraica. Durante la presentación del método símplex, deberá tenerse en mente este detalle.

¿Cómo identifica el método símplex los puntos extremos en forma algebraica?
Como paso inicial, el método símplex necesita que cada una de las restricciones esté en una forma estándar especial, en la que todas las restricciones se expresan como ecuaciones, mediante la adición de variables de holgura o de exceso, según sea necesario. Este tipo de conversión conduce normalmente a un conjunto de ecuación simultáneas donde el número de variables excede al número de ecuaciones, lo que generalmente significa que las ecuaciones dan un número infinito de puntos solución (compárese con el espacio de soluciones gráficas). Los puntos extremos de este espacio pueden identificarse algebraicamente por medio de las soluciones básicas del sistema de ecuaciones simultáneas. De acuerdo con la teoría del álgebra lineal, una solución básica se obtiene igualando a cero las variables necesarias con el fin de igualar el número total de variables y el número total de ecuaciones para que la solución sea única, y luego se resuelve el sistema con las variables restantes. Fundamentalmente, la transición del procedimiento gráfico al algebraico se basa en la validez de la siguiente relación importante: puntos extremos soluciones básicas Al no tener un espacio de soluciones gráficas que nos guíe hacia el punto optimo, necesitamos un procedimiento que identifique en forma inteligente las soluciones básicas promisorias. Lo que hace el método símplex, es identificar una solución
inicial y luego moverse sistemáticamente a otras soluciones básicas que tengan el potencial de mejorar el valor de la función objetivo. Finalmente, la solución básica correspondiente a la óptima será identificada, con lo que termina el proceso de calculo. En efecto, el método símplex es un procedimiento de cálculo iterativo donde cada iteración está asociada con una solución básica. La determinación de una solución básica en el método símplex, implica detalles tediosos de cálculo. Tales detalles no deben distraernos de la idea fundamental del método: generar soluciones básicas sucesivas, de manera que nos conduzcan al punto extremo óptimo. Todos los detalles de cálculo son secundarios a esta idea básica, y así es como debemos tratarlos.

maximizacion

NATURALEZA DE LA IO. ( CUADRO)

Maximizar y minimizar

ORIGENES DE LA INVESTIGACION DE OPERACIONES (CUADRO)

NATURALEZA DE LA IO.

• Como su nombre lo dice, la investigación de operaciones significa “investigar sobre las operaciones”. Entonces, la investigación de operaciones se aplica a problemas que se refieren a la conducción y coordinación de operaciones (o actividades) dentro de una organización. La naturaleza de la organización es en esencia inmaterial y, de hecho, la LO se ha aplicado de manera extensa en áreas tan diversas como manufactura, transporte, construcción, telecomunicaciones, planeación financiera, cuidado de la salud, milicia y servicios públicos, por nombrar sólo unas cuantas. Así, la gama de aplicaciones es extraordinariamente amplia.

• 
  La parte de investigación en el nombre significa que la IO. Usa un enfoque similar a la manera en que se lleva a cabo la investigación en los campos científicos establecidos. En gran medida, se usa el método científico para investigar el problema en cuestión. (De hecho, en ocasiones se usa el término ciencias de ¡a administración como sinónimo de investigación de operaciones.) En particular, el proceso comienza por la observación cuidadosa y la formulación del problema incluyendo la recolección de los datos pertinentes.

• El siguiente paso es la construcción de un modelo científico (por lo general matemático) que intenta abstraer la esencia del problema real. En este punto se propone la hipótesis de que el modelo es una representación suficientemente precisa de las características esenciales de la situación para que las conclusiones (soluciones) obtenidas sean válidas también pata el problema real. Después, se llevan a cabo los experimentos adecuados para probar esta hipótesis, modificarla ales necesario y eventualmente verificarla. (Este paso se conoce como validación del modelo.) Entonces, en cierto modo, la IO. incluye la investigación científica creativa de las propiedades fundamentales de las operaciones. Sin embargo, es más que esto. En particular, la IO. se ocupa también de la administración práctica de la organización. Así, para tener éxito, deberá también proveer conclusiones claras que pueda usar el tomador de decisiones cuando las necesite.

• Una característica más de la investigación de operaciones es su amplio punto de vista. Como quedó implícito en la sección anterior, la IO. adopta un punto de vista organizacional. Así, intenta resolver los conflictos de intereses entre las componentes de la organización de forma que el resultado sea el mejor para la organización completa. Esto no significa que el estudio de cada problema deba consideraren forma explícita todos los aspectos de la organización, más bien los objetivos que se buscan deben ser consistentes con los objetivos globales.
  
  Una característica adicional es que la investigación de operaciones intenta encontrar una mejor solución (llamada solución óptima) para el problema bajo consideración. (Decimos una mejor solución y no la mejor solución porque pueden existir muchas soluciones que empaten como la mejor.) En lugar de contentarse con mejorar el estado de las cosas, la meta es identificar el mejor curso de acción posible. Aun cuando debe interpretarse con todo cuidado en términos de las necesidades reales de la administración, esta “búsqueda de la optimalidad” es un aspecto importante dentro de la investigación de operaciones.

ORIGENES DE LA INVESTIGACION DE OPERACIONES

Desde el advenimiento de la Revolución Industrial, el mundo ha sido testigo de un crecimiento sin precedentes en el tamaño y la complejidad de las organizaciones. Los pequeños talleres artesanales de otra época se convirtieron en las corporaciones actuales de miles de millones de dólares, Una parte integral de este cambio revolucionario fue el gran aumento en la división del trabajo yen la separación de las responsabilidades administrativas en estas organizaciones. Los resultados han sido espectaculares. Sin embargo, junto con los beneficios, el aumento en el grado de especialización creó nuevos problemas que ocurren hasta la fecha en muchas empresas. Uno de estos problemas es la tendencia de muchas de las componentes de una organización a convertirse en imperios de relativa autonomía, con sus propias metas y sistemas de valores; con esto pierden la visión de la forma en que sus actividades y objetivos encajan con los de toda la organización. Lo que es mejor para una componente, puede ir en detrimento de otra, de manera que pueden terminar trabajando con objetivos opuestos. Un problema relacionado es que conforme la complejidad y la especialización crecen, se vuelve más difícil asignar los recursos disponibles a las diferentes actividades de la manera más eficaz para la organización como un todo. Este tipo de problemas, y la necesidad de encontrar la mejor forma de resolverlos proporcionaron el ambiente adecuado para el surgimiento de la investigación de operaciones (a la que también se hará referencia como I.O).

Las raíces de la IO. Se remontan a muchas décadas, cuando se hicieron los primeros intentos para emplear el método científico en la administración de una empresa. Sin embargo, el inicio de la actividad llamada investigación de operaciones, casi siempre se atribuye a los servicios militares prestados a principios de la Segunda Guerra Mundial. Debido a los esfuerzos bélicos, existía una necesidad urgente de asignar recursos escasos a las distintas operaciones militares ya las actividades dentro de cada operación en la forma más efectiva. Por esto, las administraciones militares americana y británica hicieron un llamado a un gran número de científicos para que aplicaran el método científico a éste y a Otros problemas estratégicos y tácticos. De hecho» se les pidió que hicieran investigación sobre operaciones (militares). Estos equipos de científicos fueron los primeros equipos de I.O. Con el desarrollo de métodos efectivos para el uso del nuevo radar, estos equipos contribuyeron al triunfo del combate aéreo británico. A través de sus investigaciones para mejorar el manejo de las operaciones antisubmarinas y de protección, jugaron también un papel importante en la victoria de la batalla del Atlántico Norte. Esfuerzos similares fueron de gran ayuda en la Campaña del Pacífico.

Se pueden identificar por lo menos otros dos factores que tuvieron gran importancia en el desarrollo de la I.O. en este periodo. Uno es el gran progreso que ya se había hecho en el mejoramiento de las récnic.ss disponibles. Después de la guerra, muchos científicos que habían participado en los equipos de 100 que tenían información sobre este trabajo, se encontraban motivados a buscar resultados sustanciales; de esto resultaron avances importantes. Un ejemplo sobresaliente es el método simplex para resolver problemas de programación lineal, desarrollado en 1947 por George Dantzig. Mochas de las herramientas características de la IO. como programación lineal, programación dinámica, líneas de espera y teoría de inventarios, se habían desarrollado casi por completo antes del término de la década de 1950.
Un segundo factor que dio un gran ímpetu al desarrollo de este campo fue la revolución de las computadoras. El manejo efectivo de los complejos problemas inherentes a la IO. casi siempre requiere un gran número de cálculos. Realizarlos a mano puede resultar casi imposible. Por lo tanto, el desarrollo de la computadora electrónica digital, con su capacidad para hacer cálculos aritméticos, miles o tal vez millones de veces más rápido que los seres humanos, fue una gran ayuda para la investigación de operaciones. Un avance más tuvo lugar en la década de 1980 con el desarrollo de computadoras personales cada vez más rápidas, acompañado de buenos paquetes de software para resolver problemas de IO. Esto puso las técnicas al alcance de un gran número de personas. Hoy en día, literalmente millones de individuos tienen acceso a estos paquetes. En consecuencia, por rutina se usa toda una gama de computadoras, desde las grandes hasta las portátiles, para resolver problemas de investigación de operaciones.