metodo de la gran "M"

Para el caso de minimizar Z=Cx+11W sujeta a las restricciones y penalizando a Zw1-Cw.

*Condicion de introducción de las variables
Restricción > resta
Restricción < suma

Ejemplo:
3x1+5x2>25 -Mw
2x1-4x2<28 +Mw
4x1-3x2=15

EJERCICIO:
U SANDO EL METODO DE LA GRAN M, TABULAR EL SIGUIENTE SISTEMA DE INECUACIONES.
min z = 3x1+5x2
Sujeta a: X1< 4
X2< 6
3x1+2x2> 18

*X1, X2 > 0
* Z= 3x1-5x2

X1 +X3
X2 +X4 =6
3X1+2X2 -X5 = 18

X1 , X2 , X3 , X4 , X5 , > 0


H X1 X2 X3 X4 X5 W1
VECTORES 1 -3 5 0 0 0 M 0 *funcion objetivo
a 0 1 0 1 0 0 0 4
a 0 0 1 0 1 0 0 6
a 0 3 2 0 0 -1 1 18



W= 0
W> 0
Debido a que M es un valor positivo suficientemente grande, la variable A1 se penaliza en la funcios objetivo utilizando – Ma para maximización y +Ma en el caso de minimización.
Solo las restricciones que tengan “<” (lados derechos no negativos) se consideran con solucion basica factible, con posibilidad de iniciar un procedimiento simplex; las restricciones restantes “=” y “>” se debe considerar una variable de holgura, por no tener solucion basica factible.
Pasar a la forma estandar el modelo matematico.
Agregar variable artificial donde no hay variable ni holgura.
Penalizar las variables artificiales en la funcion objetivo asignando coeficiente positivo muy grande “M” Minimizar y Maximizar –“M”.Quitar las “M” de la columna artificial ya teniendo solucion inicial.

1. Se aplica el metodo simples usando el metodo de la gran “M” maximizar Z= 3x1+5x2

X1 < 4
2x2 < 8
3x1+2x2 <> 0

La funcion objetivo se debe penalizar con –Ma1 por ser maximización y para hacer a Z= 0; Z-3X1-5X2+Ma1=0 las restricciones quedaran
X1+M1=4
2x2+M2=12
3x1+2x2+A1=18

BASE Z X1 X2 M1 M2 A1 SOLUCION

Z 1 -3 -5 0 0 11 0
M1 0 1 0 1 0 0 4
M2 0 0 2 0 1 0 12
A1 0 0 2 0 0 1 0


BASE Z X1 X2 M1 M2 A1 SOLUCION


Z 1 0 -2m5 3y3 0 0 -6
X1 0 1 0 1 0 0 4
M2 0 0 2 0 1 0 12
A1 0 0 2 -3 0 1 6


BASE Z X1 X2 M1 M2 A1 SOLUCION


Z 1 0 0 -9/12 0 -3/2 27
X1 0 1 0 1 0 0 4
M2 0 0 0 3 1 1 6
X2 0 0 1 -3/2 0 1/2 3

BASE Z X1 X2 M1 M2 A1 SOLUCION


Z 1 0 0 0 3/2 M+1 36
X1 0 1 0 0 1/3 1/3 2
M1 0 0 0 1 1/3 -1/3 2
X2 0 0 0 0 1/2 1 6


X1 = 2 Z= 3x1+5x2
X2 = 6 Z= 3(2)+5(6)
M1 = 2 Z= 6+30
Z= 36


X1+M1=4 2+2=4
2X2+M2=12 2(6)+0=12
3X1+2X2+A1=18 3(2)+2(6)+0=18

MÉTODO DE LAS DOS FASES

CONSIDERAR:
A) Minimización, se resuelve como se indicador el metodo simples.
B) Maximización, se resuelve como minimización para la primera fase; la segunda fase ya es maximización.


VARIABLE ARTIFICIAL

Donde existe una fase cuyo objetivo es encontrar una solución o verificar un sistema.

Z= CX+MW
Agregar variables artificiales que no tuenen variables de holgura.
Penalizar variables artificiales en la F.O. asignándoles coeficientes grandes:
En minimizar se suma
En maximización se resta -> la penalización
4 .En la F.O. no deben aparecer variables básicas eliminar v. artificiales.
5. Aplicar método simplex.
Nota: Cuando las variables artificiales básicas tienen “igual a cero”, la solución si es factible.


TEORIA DE LA GRAN “M”

Existen problemas de programación lineal, donde el método simples ya conocido es funcional, debido a que los valores de una o mas variables básicas son negativas, y eso que significa que esta violando el principio de no negatividad en las restricciones, para ello, el problema se podrá resolver por otros métodos que son:
A) El método de la gran “M” (PENALIZACION).
B) El método de las dos fases.


EL METODO DE LA GRAN “M”
PENALIZACION

Consiste en modificar el problema original para dar lugar a un nuevo problema agregando una W llamada artificial y se penalizara mediante un costo “M”, de valores grandes y positivos en forma arbitraria , y eso permite que la función objetivo tome valores muy grandes también cuando sea minimización.

Llegara el momento en que W salga de la base en ese momento W=0 y esto indica a ver regresado al problema original, pero si se llega A W>0, entonces el problema no tiene solución.

metodo de transporte

METODO DE TRANSPORTE.
Es una forma del metodo simple y de P.L. para resolver situaciones de ORIGEN DESTINO basandose en el metodo de la esquina noroeste.
EMPRESA $ 1 PROV 1 CLIENTE1 CAP PRODUCC
2 PROV 2 10 K 5K 8K 10 <
3 PROV 3 15 K 13K 14K 15<
4 PROV 4 8 K 7K 10K 13<
Nos da la oferta y la demanda.

EJERCICIO:Supongamos que una empresa transnacional que tiene tres plantas x,w,y,,y,estas surgen de un producto a 7 almacenes Abcdefg que forma parte del grupo empresarial debemos considerar lo relacionado al costo del transporte desde la planta a cada almacen


ORIGEN PLANTA OFERTA ALMACEN DESTINO DEMAN
CAP DE PRODUCCION REQ.V
W 7,000 A 1,000
X 4,000 B 2,000
Y 10,000 C 4,500
D 4,000
E 2,000
F 3,500
G 3,000

A B C D E F G OFERTA

1,000 2,000 4,000
W 6 7 5 4 3 6 5 7000
X 10 5 4 5 4 3 2 4000
Y 4 5 3 6 5 9 4 10,000 1,000
DEMANDA 1,000 2,000 4,500 4,000 2,000 3,500 5,000 21,000 21,500
2,000
0 0 500 500 0 0 0


RUTA DE UNIDADES COSTO X COSTO TOTAL
DISTRIBUCION ENVIADAS UNIDAD MINIMO
W-A 1000 6,7 6,000
W-B 2,000 5 14,000
W-C 4,000 4 20,000
X-C 500 5 2,000
X-D 3,500 6 17,500
Y-D 500 5 3,000
Y-E 2,000 9 10,000
Y-F 3,500 4 31,500
Y-G 3,000 12,000
COSTO TOTAL MINIMO $ 116,000

metodo de transportacion

METODO DE TRANSPORTACION.
EJEMPLO: La compañía azul celeste aplica y vende fertilizante de aplicación general, la compañía aplica fertilizante entre tres plantas distintas y envia el producto final 24 almacenes diferentes ubicados en diversos puntos del pais.
Puesto que en algunas operaciones productivas han existido durante mas tiempo que otras, hay diferentes costos de producción en las distintas plantas.
En la tabla siguiente se representan los costos de producción en $ por tonelada, capacidad para la planta y requerimientos de los cuatro almcenes.

Asi mismo los precios de venta de los productos los cuales debido a que cada almacen opera en forma directa, los precios por tonelada en los respectivos almacenes difieren un poco. El objetivo de los administradores de la compañía es maximizar las utilidades totales para ella deben de considerar ademas los costos de transporte asociados con el envio del producto de una planta determinada a un almacen en especifico.

PLANTA COST .PROD COSTO DE TRANSPORTE CAP. TOTAL
1 $38 23 18 21 25 650
2 $35 21 24 23 18 600
3 $30 28 21 27 23 600
PRECIO 0 62 63 64 64
VIA
DEMANDA 0 300 450 500 500 1850/1850


TONELADA

CT= 23 (300)+18 (350)+24 (100)+23(500)+27(100)+23(500)=
CT= 41.300
CP= 38(300)+38(350)+35(100)+25(500)+30(100)+30(500)=
CP= 63,700
CV= 62(300)+63(350)+63(100)+64(500)+64(100)+64(500)
CV= 117.350
U= CV-CP-CT
U=117,350-63,700-41,300
U= 12,250

METODO DUAL (PRIMAL)
Para cualquier problema de programación lineal (primal), debe tener su metodología (dual); el problema primal puede tener mas restricciones que variables, esto significa la solucion dual, y debe resolverse con nuevas restricciones.

Si el primal se refiere a Maximizar el problema dual sera Minimizar.
Los coeficientes de la funcion objetivo del primal seran los coeficientes del vector de disponibilidad de recursos en el Dual.
Asi, los coeficientes del vector disponibilidad de recursos del problema primal seran los coeficientes de la funcion objetivo (vector, costos de precios, o utilidad) en el problema dual.
Los coeficientes de las restricciones en el primal (transpuesta de la matriz, sera la matriz de los coeficientes en el dual).
Los signos de desigualdad del problema Dualson contrarios a los del problema primal.
Las variables “X” del primal se convierten en nuevas variables “Y” en el Dual.

Considerando el siguiente problema, calcular su modelo PRIMARIO, DUAL.

Sea Max Z= 3x+5y Dual
Minimizar
Restricciones X< 4 P= 4z1+6z2+18z3+10z4
Y<> 3
3x +2y<>5
X+4y<> 0



Donde: x, y > 0

Ponemos los coeficientes disponibilidad en forma de vector columna (matriz), primal.

b= 4 estos se conviertenen vector horizontal o vertical (matriz fila) traspuesta;
6 esto es:
18 b= (4,6,18,10)
10

Hacemos las restricciones del primal en forma de matriz


1 0 1 0
A 0 1 por lo tanto su traspuesta (Dual), sera: A= 0 1
3 2 3 2
1 4 1 4

Al maximizar:
C= (3,5) su matriz traspuesta (Dual) sera: C= 3
5

2.Dado el siguiente modelo Primal,expresra su modelo dual correspondiente.

Max: Z= 3x1+8x2+2x3+4x4
Restricciones:
X1+X2+2x3+3x4 < 5
X1-X2 =-1
X3+X4 > 46
Donde: X1,X2,X3,X4 > 0

Por lo tanto (Dual), Min: G= 5y1-y2 +46y3
Las restricciones quedan:


y1+y2+ > 3
y1-y2 > 8
2 y1 + y3 > 2
3y1 -y3 > -4


Donde: y1, y2, y3 > 0
B= 5
-1 b= (5 -1 46)
46

Entonces el primal sera: y el dual sera:

1 1 2 3 1 1 0
A= 1 -1 0 0 A= 1 -1 0
0 0 1 -1 2 0 1
3 0 -1



Asi el primal queda como: y el dual quedara como:

C= 3 8 2 -4 C= 3
8
2
-4

Ejemplo II MODELO deTRANSPORTE

Un método mas resumido para representar el modelo de transporte consiste en utilizar lo que se llama tabla de transporte. Esta es una forma de matriz donde sus renglones representan las fuentes y sus columnas los destinos. Los elementos de costo C i j se resumen en la esquina noroeste de la celda de la matriz (i, j). Por lo tanto, el modelo de MG se puede resumir en la tabla siguiente.

Ejemplo de MODELO de TRANSPORTE

El esquema siguiente representa el modelo de transporte como una red con m fuentes y n destinos. Una fuente o un destino esta representado por un nodo, el arco que une fuente y un destino representa la ruta por la cual se transporta la mercancía. La cantidad de la oferta en la fuente i es ai, y la demanda en el destino j es bj. El costo de transporte unitario entre la fuente i y el destino j es Cij.

UNIDAD II

Programación Lineal
Un problema de Programación Lineal consiste en encontrar el máximo o el mínimo de una función, como, por ejemplo, los beneficios de una empresa o el coste de una dieta, teniendo en cuenta una serie de limitaciones (restricciones) impuestas por las condiciones materiales en las que se desarrolla nuestro problema (número de trabajadores, cantidad mínima diaria de calorías, etc.)
Más en concreto, un problema de Programación Lineal presenta siempre los siguientes elementos:
· Un sistema de inecuaciones, llamadas restricciones, impuestas por la naturaleza del problema. El polígono convexo formado por las soluciones del sistema recibe el nombre de región factible.
· Una función lineal de dos variables, de la forma f(x,y)=ax+by+c, que recibe el nombre de función objetivo. Resolver el problema consiste en encontrar el punto, o los puntos, de la región factible en los que f alcanza su máximo o su mínimo.
Por ejemplo, vamos a buscar el máximo de la función
f(x,y)=-x+y+2,
sujeta a las restricciones:
x>=0, y>=0, 2x-3y<=0, 2x-9y<=-18.
Si observas la animación verás que una forma de resolverlo consiste en representar en el espacio la región factible (en el plano XY) y la función objetivo en la forma
z=f(x,y),
y encontrar el punto de la región factible en el que f(x,y) es más grande (aquél en el que z alcanza su mayor altura)
El inconveniente que presenta el método anterior es que nos obliga a utilizar una representación en el espacio.
Por eso, en la práctica resulta más conveniente representar en el plano la región factible y trazar las llamadas curvas de nivel, que, como en un mapa, representan los puntos en los que la función objetivo alcanza la misma altura.
Como la función objetivo es un plano, las curvas de nivel que obtenemos son rectas, todas ellas paralelas.
Según se va cambiando de una recta paralela a otra el valor de f va aumentando o disminuyendo.
Para terminar de resolver el problema, obtener el máximo o el mínimo que estás buscando, debes observar cómo varía la función objetivo (en algunas ocasiones el valor de la función objetivo aumenta cuando aumentas la ordenada en el origen de las rectas paralelas y en otras ocurre lo contrario) y en qué puntos las paralelas a ella "abandonan" la región factible.
Si la región no está acotada los extremos a veces no existen y si existen se alcanzan en un vértice, un segmento o una semirecta (¿por qué?). Si la región está acotada siempre existen los extremos y pueden alcanzarse en un vértice o en un segmento (¿por qué?).
Método gráfico de resolución de sistemas
Cada una de las ecuaciones que forman un sistema lineal de dos ecuaciones con dos incógnitas es la de una función de primer grado, es decir, una recta. El método gráfico para resolver este tipo de sistemas consiste, por tanto, en representar en unos ejes cartesianos, o sistema de coordenadas, ambas rectas y comprobar si se cortan y, si es así, dónde. Esta última afirmación contiene la filosofía del proceso de discusión de un sistema por el método gráfico. Hay que tener en cuenta, que, en el plano, dos rectas sólo pueden tener tres posiciones relativas (entre sí): se cortan en un punto, son paralelas o son coincidentes (la misma recta). Si las dos rectas se cortan en un punto, las coordenadas de éste son el par (x, y) que conforman la única solución del sistema, ya que son los únicos valores de ambas incógnitas que satisfacen las dos ecuaciones del sistema, por lo tanto, el mismo es compatible determinado. Si las dos rectas son paralelas, no tienen ningún punto en común, por lo que no hay ningún par de números que representen a un punto que esté en ambas rectas, es decir, que satisfaga las dos ecuaciones del sistema a la vez, por lo que éste será incompatible, o sea sin solución. Por último, si ambas rectas son coincidentes, hay infinitos puntos que pertenecen a ambas, lo cual nos indica que hay infinitas soluciones del sistema (todos los puntos de las rectas), luego éste será compatible indeterminado.
El proceso de resolución de un sistema de ecuaciones mediante el método gráfico se resume en las siguientes fases:
· Se despeja la incógnita y en ambas ecuaciones.
· Se construye, para cada una de las dos funciones de primer grado obtenidas, la tabla de valores correspondientes.
· Se representan gráficamente ambas rectas en los ejes coordenados.
· En este último paso hay tres posibilidades:
· Si ambas rectas se cortan, las coordenadas del punto de corte son los únicos valores de las incógnitas x e y. Sistema compatible determinado.
· Si ambas rectas son coincidentes, el sistema tiene infinitas soluciones que son las respectivas coordenadas de todos los puntos de esa recta en la que coinciden ambas. Sistema compatible indeterminado.
· Si ambas rectas son paralelas, el sistema no tiene solución. Sistema incompatible.

EL METODO SIMPLEX PARA SOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL

Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.
Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.

MODELO DE TRANSPORTE

DEFINICIÓN Y APLICACIÓN DEL MODELO DE TRANSPORTE

El modelo de transporte busca determinar un plan de transporte de una mercancía de varias fuentes a varios destinos. Los datos del modelo son:

1. Nivel de oferta en cada fuente y la cantidad de demanda en cada destino.
2. El costo de transporte unitario de la mercancía a cada destino.

Como solo hay una mercancía un destino puede recibir su demanda de una o más fuentes. El objetivo del modelo es el de determinar la cantidad que se enviará de cada fuente a cada destino, tal que se minimice el costo del transporte total.

La suposición básica del modelo es que el costo del transporte en una ruta es directamente proporcional al numero de unidades transportadas. La definición de “unidad de transporte” variará dependiendo de la “mercancía” que se transporte.

MÉTODO de ASIGNACIÓN

El problema de asignación tiene que ver con la asignación de tareas a empleados, de territorios a vendedores, de contratos a postores o de trabajos a plantas. Al aplicar el método de transporte y el método de asignación la gerencia está buscando una ruta de distribución o una asignación que optimizará algún objetivo; éste puede se la minimización del costo total, la maximización de las utilidades o la minimización del tiempo total involucrado.
Al igual que el método de transporte el método de asignación es computacionalmente más eficiente que el método simplex para una clase especial de problemas.