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.

...