Programación lineal

PROGRAMACION LINEAL

Nombre Alumno (s):

Loreto Vergara F.

Tamara Arévalo

Carolina Oyarce

Pía Gutiérrez

Nombre Jonathan Sánchez

Fecha: 26 de Junio de 2013

INDICE

PROGRAMACION LINEAL 1

INTRODUCCION A LA PLANEACIÓN LINEAL 3

1.- CONCEPTO: 4

2.- PLANTEAMIENTO 4

3.- FORMULACION DEL PROBLEMA DE PROGRAMACION LINEAL 5

ESTRUCTURA DE UN MODELO DE PROGRAMACION LINEAL 5

MODELO GENERAL DE PROGRAMACION LINEAL 6

Formulación de modelos de Programación Lineal. 6

FORMA ESTÁNDAR DE LOS MODELOS DE PROGRAMACIÓN LINEAL. 9

OTRAS FORMAS DE MODELOS DE PROGRAMACIÓN LINEAL. 10

FORMULACION ALGEBRAICA: 11

FORMA CANONICA 11

IMPORTANCIA DE LA FORMA CANONICA 12

TERMINOLOGIA Y CONCEPTOS BASICOS: 12

4.-METODO GRAFICO 13

INTRODUCCIÓN 13

DEFINICION 14

CONCEPTO GENERAL DEL METODO GRAFICO 16

PASOS PARA LA SOLUCION MEDIANTE EL METODO GRAFICO 17

5.-METODO SIMPLEX 20

INTRODUCION 20

CONCEPTO 20

PASOS PARA EL DESARROLLO DEL METODO SIMPLEX 20

7.- Programación entera 37

Aplicaciones 37

Ejemplo 38

8.-Cambio al vector de costo o precio. 40

INTRODUCCION A LA PLANEACIÓN LINEAL

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.

1.- CONCEPTO:

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.

La programación lineal es una técnica de investigación de operaciones para la determinación de la asignación óptima de recursos escasos cuando la función objetivo y las restricciones son lineales. Es una manera eficiente de resolver estos problemas cuando se debe hacer una elección de alternativas muy numerosas que no pueden evaluarse intuitivamente por los métodos convencionales.

2.- PLANTEAMIENTO

Resolver un problema de programación lineal consiste en optimizar una función lineal sujeta a unas restricciones, entendiendo por optimizar encontrar un valor máximo o mínimo según los casos (Maximizar o Minimizar la función).

La función lineal respecto a las variables x e y se llama función objetivo. F(x,y) = mx+ny, siendo m , n, dos números reales.

o Las ecuaciones o inecuaciones condicionantes se llaman restricciones.

o Las soluciones del sistema (el conjunto de los puntos del recinto plano que delimitan las rectas representativas del sistema) constituyen la región factible, que es la región donde debemos buscar la solución.

Optimizar condicionada a las restricciones:

a1x + b1y  c1

a2x + b2y  c2

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

anx + bny  cn

(el símbolo , según el problema planteado, corresponderá a uno de los cuatro siguientes  , , , ). La región factible es un polígono. El hecho fundamental - cuya demostración excede de estas páginas- es que si existe solución óptima se encuentra en un vértice del polígono que constituye la región factible.

3.- FORMULACION DEL PROBLEMA DE PROGRAMACION LINEAL

INTRODUCCION

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.

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.

ESTRUCTURA DE UN MODELO DE PROGRAMACION LINEAL

1. Función objetivo: Consiste en optimizar el objetivo que persigue una situación la cual es una función lineal de las diferentes actividades del problema, la función objetivo se maximizar o minimiza.

2. Variables de decisión. Son las incógnitas del problema. La definición de las variables es el punto clave y básicamente consiste en los niveles de todas las actividades que pueden llevarse a cabo en el problema a formular.

3. Restricciones Estructurales. Diferentes requisitos que debe cumplir cualquier solución para que pueda llevarse a cabo, dichas restricciones pueden ser de capacidad, mercado, materia prima, calidad, balance de materiales, etc.

4. Condición técnica. Todas las variables deben tomar valores positivos, o en algunos casos puede ser que algunas variables tomen valores negativos.

MODELO GENERAL DE PROGRAMACION LINEAL

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 -

...