Apuntes



ESCOMESCOMESCOMESCOM
Cisneros Cortes David


Márquez Arregui Guillermo

Métodos Cuantitativos para la Toma de Decisiones

Grupo: 3CM7





13.Julio.2015
Apuntes


Unidad II - Programación Lineal
2.1 Programación Lineal: Conceptos Básicos
1. Definición.
Técnica de programación matemática para resolver problemas de optimización de recursos (maximización, minimización) cuando existemás de unarestricción lineal.

2. Características.
a. Se busca una combinación de recursos.
b. Se deben satisfacer varios criterios.
c. Se identifica un criterio como el objetivo.

3. Ubicación.

4. Métodos Generales.
(a) Métodos Generales
(1) Método Grafico.
(2) Método Simplex.
(b) Métodos especiales
(1) Método de Transporte.
(2) Método de Asignación.
(3) Método de Kalmarkar.
5. Supuestos.
(a) Linealidad:(1) Todas las variables deben ser lineales (exponente = 1).
(2) Todos los coeficientes deben ser constantes.
(3) Todas las operaciones son sumas o restas.
(b) Determinismo:
Debe conocerse con certeza el comportamiento de todas las
variables y de todos los coeficientes.
(c) Objetivo único:
Debe haber un solo objetivo.
6. Inconvenientes.
(a) Necesidad de computador electrónico.
(b) Costos deformulación del problema.

2.1.1 Función lineal, desigualdad lineal y región factible.
Una función lineal es una función polinómica de primer grado; es decir, una función cuya representación en el plano cartesiano es una línea recta. Esta función se puede escribir como:
f(x) = mx + b
donde m y b son constantes reales y x es una variable real. La constante m es la pendiente de la recta, y b es el punto decorte de la recta con el eje y. Si se modifica m entonces se modifica la inclinación de la recta, y si se modifica b, entonces la línea se desplazará hacia arriba o hacia abajo.

Una desigualdad lineal en la variable x es una proposición que puede ser escrita de la forma cx + b > 0 , (o bien ≥ ) donde c y b son constantes con c ≠ 0 . Resolver una desigualdad es
conseguir todos los valores x quesatisfacen esta relación.
La manera para resolver desigualdades lineales es llevarla a otra equivalente de la forma x > a o cualquiera de las otras tres formas cuya solución es evidente: x < a, x ≥ a ó x ≤ a .
Cuando un número real c se suma o se resta a ambos lados de una desigualdad, el sentido de la desigualdad no se altera:
Si a < b entonces a + c < b + c y a − c < b − c
Región Factible
Laregión factible para un problema de programación lineal es el conjunto de todos los puntos que satisfacen todas las restricciones incluidas las de no negatividad. Dicha región es un conjunto convexo, porque cualquier segmento rectilíneo que una a un par de puntos, por ejemplo a y b se encuentran completamente en dicho conjunto.


2.1.2 El problema de programación lineal como un problema deoptimización y sus características.

Un problema de programación lineal es un problema de optimización para el cual:
1. Tratamos de maximizar o minimizar una función lineal (Z) de variables de decisión, a la cual llamamos función objetivo.
2. Los valores de las variables de decisión, tienen que satisfacer un conjunto de restricciones, (ecuaciones o inecuaciones lineales) y cada restricción tiene que serlineal.
3. Existe una restricción de signo para cada variable. Para cualquier variable Xi la restricción especifica es que Xi tiene que ser no negativa.









2.2 Forma general del problema de programación lineal

En el tema 1 vimos que la forma general general de un problema problema de programación programación lineal continuo continuo era la siguiente siguiente:










Vamos analizar unaserie de transformaciones que convierten el problema en otro equivalente, entendiendo como equivalente otro problema que tiene las mismas valores para las variables de decisión y función objetivo.

Maximización y minimización
Es evidente que siempre se cumple la siguiente relación:


Luego un problema de maximización siempre podemos convertirlo en uno de minimización equivalente y viceversa....