Teoria gran m

INVESTIGACIÓN DE OPERACIONES
Programación Lineal

MODELAMIENTO MATEMÁTICO
COMPONENTES BÁSICOS

• Las Variables de decisión que se trata de determinar • El Objetivo (la meta) que se trata de optimizar • Las Restricciones que se deben satisfacer

PROGRAMACIÓN LINEAL

La programación lineal (PL), trata exclusivamente con funciones objetivos y restricciones lineales, es una parte de laprogramación matemática, y una de las áreas más importantes de la matemática aplicada.

Formulación del modelo
Reddy Mikks produce pinturas para interiores y exteriores, M1 y M2. La siguiente tabla proporciona los datos básicos del problema.

Ton de materia prima de

Pintura para exteriores
M1 2

Pintura para interiores
1

Disponibilidad diaria máxima (ton)
18

M2
Utilidad por Ton(miles de $)

2
3

3
2

42

También, que la demanda máxima diaria de pintura para exteriores e interiores es de 24 toneladas. Se desea determinar la mezcla optima de productos para exteriores e interiores que maximice la utilidad diaria total.

Variables
• Variables de decisión, cantidad a producir de pintura para exteriores e interiores (se determinan por los datos que se deseanhallar). • X1, Toneladas producidas diariamente, de pintura para exteriores • X2, Toneladas producidas diariamente, de pintura para interiores

Función Objetivo
• Lo que se desea alcanzar como meta es aumentar las utilidades de la empresa lo mas posible.

Si z representa la utilidad diaria el objetivo sería: Maximizar z = 3 X1 + 2 X2

Restricciones
El uso de Materia Prima, se restringe porsu disponibilidad

Uso de la materia prima M1, por día en toneladas 2 X1 + 1 X2 Uso de la materia prima M2, por día en toneladas 2X1 + 3X2 Teniendo en cuenta la disponibilidad 2X1 + 1X2 ≤ 18 2X1 + 3X2 ≤ 42

Restricciones
• De igual forma se estipulo que la demanda máxima diaria de pintura para exteriores e interiores se limita a 24 toneladas 3X1 + X2 ≤ 24

Restricción de no negatividadLos variables de decisión no pueden dar como resultado un valor negativo

X1 ≥ 0
X2 ≥ 0

Modelo Reddy Mikks
Maximizar z = 3 X1 + 2 X2 Sujeta a 2X1 + 1X2 ≤ 18 2X1 + 3X2 ≤ 42 3X1+ 1X2 ≤ 24 X1, X2 ≥ 0

La solución debe satisfacer todas las restricciones del modelo, para que la solución sea factible.

MÉTODOS DE SOLUCIÓN
MÉTODO SIMPLEX Es un procedimiento algebraico, genérico de soluciónde problemas lineales, desarrollado por George Dantzig en 1947.

Como tal, el método simplex es un procedimiento algebraico, pero puede entenderse más fácilmente como un método geométrico.

MÉTODO SIMPLEX
• El procedimiento algebraico se basa en la solución de ecuaciones. Así el primer paso del método es convertir las restricciones funcionales de desigualdad en restricción de igualdadequivalentes. (Las restricciones de no negatividad se dejan como desigualdades por que se manejan por separado). Esta conversión se logra con la introducción de variables de holguras.

• Ejemplo de modelo anterior 3X2+ 1X1 ≤ 24 La variable de holgura para esta restricción se define como X3= 24 - 3X2- 1X1 Ordenando 3X2+ 1X1 + X3 =24 Dada esta ecuación 3X2+ 1X1 ≤ 24 se cumple si y solo si 24 - 3X2- 1X1=X3 ≥ 0. entonces, la restricción original 3X2+ 1X1 ≤ 24 es totalmente equivalente al par de restricciones 3X2+ 1X1 + X3 = 2 y X3 ≥ 0

Una solución aumentada es una solución para las variables originales (las variables de decisión), que se aumento con los valores correspondientes de las variables de holgura. “Las variables de holgura no se muestran en la función objetivo por que suscoeficientes son cero”.

En cualquier problema de PL en la forma estándar la aparición de las restricciones funcionales después de introducir variables de holgura es la siguiente:

VARIABLES INDICATIVAS
• Donde,
– Xn+1 son variables de holgura – n+1 son variables artificiales – Xsi son variables de superavit

Modelo Ampliado
Modelo inicial Modelo ampliado

Maximizar z = 3 X1 + 2 X2
2X1 + 1X2...