INVESTIGACION DE OPERACIONES.

TEMARIO.

I. INTRODUCCION A LA INVESTIGACION DE OPERACIONES

Definición de antecedentes, ubicación en las organizaciones, metodología.

II. PROGRAMACION LINEAL.

Modelo de la Programación Lineal (P.L. General). Propiedades.

Formulación con Programación Lineal de aplicaciones típicas en: producción, selección de equipo, procesos, horarios, dieta, etc.

Solución para el problema expresado con Programación Lineal.

Método de solución gráfica con solo dos variables.

Visualización de conceptos de P.L.; solución factible y no factible, solución básica, solución única y no única, restricción redundante, solución degenerada, variable de holgura y superflua.

Método de solución analítica para el problema de P.L.

Formas equivalentes del modelo de programación lineal.

Definiciones y teoremas de P.L.

Método SIMPLEX y criterios para el cambio de base.

Variables artificiales.

Método SIMPLEX-PENAL o de la M Grande.

Método SIMPLEX-DOS FASES.

Casos especiales en la tabla SIMPLEX.

Teoría de la Dualidad en P.L.

Obtención del Problema Dual en forma canónica.

Obtención del Problema Dual en forma directa.

Equivalencia entre las dos obtenciones anteriores

Significado de las variables duales e interpretación económica.

Método DUAL-SIMPLEX y criterios para cambios de base.

Estructura matricial de la tabla SIMPLEX.

Análisis de sensibilidad de la solución óptima de un problema.

Cambios en el vector b de recursos de restricciones.

Cambios en el vector C de coeficientes de la función objetivo.

Cambios en la matriz A de coeficientes de restricciones.

Aplicaciones de la Programación Lineal a Redes de Flujo.

Definición.

Modelo de transporte simple. Definición.

Modelo matemático de P.L. y tabla usual.

Solución inicial para la optimización de un problema.

Algorítmo de transporte (SIMPLEX-SIMPLIFICADO) para la optimización.

Ejemplificación de soluciones degenerada y no degenerada.

Modelo de transbordo definición.

Modelo matemático de transbordo balanceado y sin capacidades.

Modelo matemático de transbordo con capacidades.

Problemas y modelo matemático de ruta mínima. Definición.

Algorítmo de Dijkstra para red orientada y no orientada.

Algorítmo matricial para cualquier red.

Problema de árbol mínimo y algorítmo de conjunto conectado.

Problema y modelo matemático de flujo máximo

Algorítmo de Ford-Fulkerson para red orientada

Algorítmo matricial para cualquier red.

INVESTIGACION DE OPRERACIONES.

• Es la aplicación del método científico.

• Por grupos interdisciplinarios.

• En el estudio de problemas de las organizaciones creads por el hombre buscando un a solución integral.

Modelo matemático obligado.

METODO CIENTIFICO

Métodos estadísticos de muestreo.

Investigador de operaciones.

Administradores.

Informáticos.

GRUPOS Ingenieros.

INTERDISCIPLINARIOS Economistas.

Contadores.

Etc.

CREADAS POR EL HOBRE. Enfoque sistémico.

ANTECEDENTES.

AÑO. AUTOR. TECNICA DESARROLLADA.

1759 Quesnay Modelos primarios de programación matemática.

1873 G.Jordan. Modelos lineales.

1874 Warlas. Modelos primarios de programación matemática.

1891 Minkousky. Modelos lineales.

1903 Farkas. Modelos lineales.

1897 Markov. Modelos dinámicos probabilísticos.

1905 Erlang. Líneas de espera.

Konig Egervary Asignación.

1937 Morgerstern. Lógica estadística.

1937 Von Newman. Teoría de juegos.

1939 Kantorovich. Distribución.

1947 G.Dantzig. Método SIMPLEX.

1950's Bellman. Programación dinámica.

Kun-Tucker. Programación no lineal.

Gomory. Programación entera.

Ford-Fulkerson. Redes de flujo.

AÑO. AUTOR. TECNICA DESARROLLADA.

Markowitz. Simulación.

Raifa. Análisis de decisiones.

Arrow-Karli. Inventarios.

Siglo XVI.....

Newton.

Lagrange Probabilidad y.

Cálculo Diferencial Laplace. Estadística.

Leibnitz.

Stieljes.

Metodología de Investigación de Operaciones:

1

Identifica el problema

(partes y objetivos)

2

Observar el Sistema

(información)

3

Formular un Modelo

Matemático (plantear )

4

Verificar el Modelo y

usarlo en predicción

(evaluar y derivar sol. )

5

Seleccionar alternativas

de solución

6

Presentar resultados

a la organización

7

Implementar y evaluar

recomendaciones

“Programación Lineal”

A pesar de que la programación lineal se empezó a estudiar desde finales del S.XIX no fue hasta mediados del presente siglo en que tuvo auge como técnica matemática aplicable a los problemas de la empresa.

El Dr. G. Damtzing desarrolló el método simplex y con ello hizo posible la solución de grandes problemas modelados con programación lineal que solo quedaban en la situación de estudios. Paralelamente a la invención de este método a partir de mediados del siglo se desarrollo la computación digital y se pudo tener resultados óptimos a los problemas estudiados que se quedaron como modelos.

La programación lineal es actualmente la técnica matemática utilizada mas actualmente gracias a que el algoritmo simplex es muy eficiente y al desarrollo de la computación.

Lo que se busca con la aplicación de la programación lineal es resolver problemas comunes y a la vez muy variados de la empresa en donde en general se tienen necesidades por satisfacer con cierto número de recursos limitados o escasos y con el objetivo de lograrlo en forma óptima. Esto significa la búsqueda de un valor máximo cuando se trata de beneficios; o bien la búsqueda de un mínimo cuando se trata de esfuerzos a desarrollar.

Un modelo de programación lineal es un conjunto de expresiones matemáticas las cuales deben cumplir la característica de linealidad que puede cumplirse siempre y cuando las variables utilizadas sean de primer grado. Además un modelo de P.L debe tener las propiedades de:

• Proporcionalidad

• Aditividad (adición)

• Divisibilidad

• Certidumbre(certeza)

Antes de formular un modelo general para P.L conviene ilustrar algunos ejemplos que faciliten la interpretación de la generalización

Ejemplo de producción:

Una empresa ha dejado de fabricar ciertos productos, liberando de esta forma las cargas de producción que tenían sus equipos en los departamentos de maquinado. Ahora se tienen horas máquina que se pueden utilizar en los productos denominados 1,2,3 de la siguiente manera:

Máquina Horas por pieza de producto Horas Maq. Disponibles

1 2 3 por semana

Fresadora 9 3 5 500

Torno 5 4 - 350

Rectificadora 3 - 2 150

Utilidad

$/ pieza 50 20 25

Recomendación del Mínimo Mínimo Mínimo

Depto. Vtas a Prod. 30 15 20

Formular un modelo de P.L para este problema

• Definición de variables a utilizar en el método de programación lineal

Sea: Xj = numero de piezas de producto j(j=1,2,3) a fabricar para maximizar la utilidad.

• Función económica y objetivo:

MAX Z= 50X1 + 20X2 + 25X3 [ (Dls/Unidad) (Unidad/Sem)] = [Dls/Sem.]

sujeta a restricciones de horas máquina disponibles por semana

Fresadora : 9X1 + 3X2 + 5X3 * 500 horas máquina fresadora

Torno: 5X1 + 4X2 * 350 horas máquina torno

Rectificadora: 3X1 + 2X3 * 150 horas maquina rectificadora

Condiciones de signos pare las variables:

X1 * 30 piezas

X2 * 15 piezas

X3 * 20 piezas

Ejemplo de inversión:

Se desean invertir 2 millones de dólares en 6 tipos de inversión cuyas características son las siguientes:

Tipo de Interés Factor de Plazo promedio

Inversión Anual(%) Riesgo de inversión

1 8.5 0.02 8

2 9 0.01 2

3 8.5 0.38 5

4 14.3 0.45 6

5 6.7 0.07 2

6 13 0.35 4

El factor de riesgo significa la probabilidad de que el rendimiento real sea inferior al esperado. Se considera ventajoso un período promedio ponderado de inversión de ciando menos 5 años; pero el factor promedio ponderado de riesgo no debe ser superior a 0.20. La ley prohibe que la suma de las inversiones de los tipos 4 y 6 sea mayor al 25% del total de la inversión. Con P.L formule un modelo de P.L para decidir cómo invertir para maximizar el rendimiento de los 2 millones de dólares.

(SOL. A)

• Definición de variables

Sea: Xj = cantidad de dólares a invertir en el tipo j(j=1,2,3,4,5,6) para maximizar el rendimiento.

• Función objetivo

MAX Z= 0.085X1 + 0.09X2 + 0.85X3 + 0.143X4 + 0.067X5 +0.13X6

sujeta a restricciones:

1) X1 + X2 + X3 +X4 + X5 + X6 = 2,000.000 dls.

0.02X1 + 0.01X2 + 0.38X3 + 0.45X4 + 0.07X5 + 0.35X6 * 0.2 (2,000.000) = 400,000 dls.

8X1 + 2X2 + 5X3 +6X4 + 2X5 + 4X6 * 5 (2,000.000) = 10,000.000 dls.

X4 + X6 * 0.25 (2,000.000) = 5,000.000 dls.

X1, X2, X3, X4, X5, X6 * 0

(SOL. B)

• Definición de variables

Sea: Xj = Fracción capital a invertir en el tipo j(j=1,2,3,4,5,6) para maximizar el rendimiento.

• Función económica y objetivo:

MAX Z= 8.5X1 + 9X 2 + 8.5X3 + 14.3X 4 + 6.7X5 +13X 6

sujeta a restricciones:

1) X1 + X2 + X3 +X4 + X5 + X6 = 1 (capital)

0.02X1 + 0.01X2 + 0.38X3 + 0.45X4 + 0.07X5 + 0.35X6 * 0.2 (1) = 0.2

8X1 + 2X2 + 5X3 +6X4 + 2X5 + 4X6 * 5 (1) = 5

X4 + X6 * 0.25 (1) = 0.25

X1, X2, X3, X4, X5, X6 * 0

Ejemplo:

Problemas de mezcla en la inversión.

Definición de variables:

Sea: xj = Fracción del capital a invertir en la tipo j (j = 1,2,...,6) para maximizar el rendimiento.

Función objetivo:

Max. z = 8.5 x1 + 9 x2 + 8.5x3 + 14.3x4 + 6.7x5 + 13x6

Sujeto a restricciones:

x1 + x2 + x3 + x4 + x5 + x6 = 1

(Factor de riesgo)

0.02x1 + 0.01x2 + 0.38x3 + 0.45x4 + 0.07x5 + 0.35x6 " 0.2 (1) = 0.2

8x1 + 2x2 + 5x3 + 6x4 + 2x5 + 4x6 " 5(1) = 5

x4 + x6 " 0.25 (1) = 0.25

x1,x2,...,x6 " 0

[Ésta es otra forma de plantear el problema]

Problema de establecimiento de horario.

En un sector de la ciudad se tiene el siguiente requerimiento de policías:

PERIODO DEL DIA	1	2	3	4	5	6
HORA DEL DIA.	06-10	10-14	14-18	18-22	22-02	02-06
POLICIAS REQUERIDOS (")	300	350	425	450	250	200

El periodo #1 sigue inmediatamente del 6. Cada policía debe laborar 8 hrs consecutivas. Formular un modelo de programación lineal de este problema.

PERIODO/HORA	06-10	10-14	14-18	18-22	22-02	02-06
1 2 3 4 5 6	X1 X6	X1 X2	X2 X3	X3 X4	X4 X5	X5 X6
REQUERIDOS.	" 300	" 350	" 425	" 450	"250	"200

Definición de variables:

Sea xj = Número de policías que inician el periodo j (j = 1,2,3,...,6)

Función objetivo:

Min. z = x1 + x2 + x3 + x4 + x5 + x6 (policías mínimos para cubrir turnos [6])

Sujeto a restricciones:

x1 + + x6 " 300

x1 + x2 " 350

x2 + x3 " 425

x3 + x4 " 450

x4 + x5 " 250

x5 + x6 " 200

.... toda xj " 0

Ejemplo:

Problema de aprovechamiento de recursos.

Una empresa papelera recibe un pedido de rollos de papel de la misma calidad y espesor para los siguientes anchos:

500 rollos de 30 in, 450 rollos de 45 in y 150 rollos de 56 in.

En las bodegas de la empresa solo se tiene existencia en esta calidad de papel en ancho de 108 in, por lo que se piensa deben someterse a un proceso de corte longitudinal si se desea cumplir la demanda de este pedido. Formular un modelo de programación lineal correspondiente a este problema.

108 cm CORTE

Definición de variables:

Sea xj = # de cortes del tipo j (j = 1,2,....,5) necesarios para cumplir el pedido con mínimo desperdicio de papel.

Función objetivo (o económica):

Min. z = 18x1 + 3x2 + 22x3 + 18x4 + 7x5

Sujeto a restricciones:

3x1 + 2x2 + x3 " 500 rollos de 30'

x2+ x4 + x5 " 450 rollos de 45'

x3 + x5 " 150 rollos de 56' ...las unidades:

Rollos

Corte Corte = Rollos ...para restricciones.

in

corte corte = in ...para función objetivo.

Toda xj " 0

Problema de almacenamiento en el transporte.

Un barco tiene las siguientes capacidades de almacenamiento en sus bodegas de popa, centro y proa. Los dueños del barco pueden elegir una porción o toda la carga de los productos A, B y C, cuyas características se tabulan a continuación. Además, para preservar el equilibrio del barco debe cumplirse con una carga proporcional a la capacidad de las respectivas bodegas.

BODEGA	CAPACIDAD	CAPACIDAD
	TONELADAS	m3
PROA (1)	3000	130000
CENTRO (2)	2000	10000
POPA (3)	1500	30000

PRODUCTOS	TNS A TRANSPORTAR	m3/Ton	UTILIDAD (MILES DLS/TN)
A	3500	60	8
B	2500	50	7
C	2000	25	6

Definición de variables:

Sea: xij = toneladas del producto j (j = A,B,C) a cargar en la bodega i (i = 1,2,3) para maximizar la utilidad en el viaje.

Función objetivo:

Max z = 8(x1A + x2A + x3a) + 7(x1B + x2B + x3B) + 6(x1C + x2C + x3C) ...con unidades

Miles de dls.

Ton Ton = miles de dólares

Sujeto a restricciones:

x1A + x1B + x1C " 3000 Ton.

Capacidad en Ton x2A + x2B + x2C " 2000

x3A + x3B + x3C " 1500

60x1A + 50x1B + 25x1C " 130000 m3.

Capacidad en Ton 60x2A + 50x2B + 25x2C " 100000

60x3A + 50x3B + 25x3C " 30000

x1A + x1B + x1C " 3500 Ton.

Capacidad en Ton x2A + x2B + x2C " 2500

x3A + x3B + x3C " 2000

Proporción de carga en las bodegas:

x1A + x1B + x1C = x2A + x2B + x2C = x3A + x3B + x3C " 1

3000 2000 1500

Modelo de programación lineal general.

Definición de variables:

Sea xj = #.... ; j = 1, 2, 3....n

Función objetivo:

Términos del primer grado que se sumen.

Max. o Min. z = C1x1 + C2x2 + ... + Cjxj + ... + Cnxn

...donde n = # total de valores

j = ocurrencia.

Sujeto a restricciones: i = 1, 2, 3, ... , m

a11x1 + a12x2 + ... + a1jxj + ... + a1nxn " = " b1

a21x1 + a22x2 + ... + a2jxj + ... + a2nxn " = " b2

·

·

ai1x1 + ai2x2 + ... + aijxj + ... + ainxn " = " bi

·

·

am1x1 + am2x2 + ... + amjxj + ... + amnxn " = " bm

Condiciones de signo para variables: toda xj " 0

Modelo general de programación lineal resumido en:

Sumatorias.

Definición de variables: sea xj = # ; j = 1, 2, 3, ... , n

Función objetivo: (Max./Min.) z = " cjxj

... sujeta a:

"aijxj " = " bi i = 1, 2, 3, ... , m

... condiciones de signo: " xj " 0

Con vectores.

(Max./Min.) z = Cx

... sujeto a: Ax " = " b

x " 0

Propiedades que debe de seguir el modelo de programación lineal.

Proporcionalidad. En el modelo de programación lineal los pagos deben ser proporcionales.

El modelo de programación lineal es estático, plantea una situación del momento.

x = progreso de la actividad

Aditividad. Siempre los pagos se suman.

Requerimientos.

Costos y

Utilidades.

Divisibilidad. Las variables involucradas en el modelo de programación lineal pueden no ser un número entero...

Si los valores son muy pequeños no importa el redondeo.

Si son muy altos afecta el redondeo.

Certidumbre. Todos los parámetros que se manejan deben ser pasados con certeza.

Métodos de solución del modelo de programación lineal.

El modelo de programación lineal se puede resolver tanto gráfica como analíticamente, pero para problemas de tamaño común que se encuentran como aplicaciones, la solución gráfica no es útil. En cambio, la solución analítica utilizando el algorítmo SIMPLEX que se verá posteriormente es el procedimiento normal para la búsqueda de la solución óptima de un problema.

Método de solución gráfica.

La gran limitación que se tiene con el método de solución gráfica con programación lineal es que su aplicación sólo puede hacerse a problemas con dos y cuando mucho tres variables, en este curso se ejemplifica para problemas solo con dos variables.

A pesar de tal inconveniente, el método gráfico resulta útil para exposición e ilustración de los conceptos de la programación lineal. Ejemplo:

Max. z = 3x1 + 5x2 ... sujeto a:

x1 " 4 .......... (1)

2x2 " 12 .......... (2)

3x1 + 2x2 " 18 .......... (3) x1 ; x2 " 0

Expresar geométricamente el sistema dentro del gráfico; rango de valores.

x1 " 4 2 x2 " 12 3 x1 + 2 x2 " 18

(1) (4,0) F (2) x2 " 6 (3) x1 x2

(0.6) A

0 9

• 0

(0,9) B

(6,0) J

Las desigualdades son fronteras o división del espacio plano. Si la recta no pasa por el origen, se toman en cuenta las coordenadas de O.

Espacio solución: Satisface al sistema (factible) posible. Conjunto de soluciones factibles.

Si se satisface la restricción, el origen pertenece al semiplano que satisface la restricción.

(1) (3) 3x1 = 12

H x1= 4 x1 = 4

3x1 + 2x2 = 18 H = (4,3)

2x2 = 6 ; x2 = 3

Trazo de la función económica

VALOR RELATIVO

z (5,0)

(0,3)

Múltiplo de los coeficientes que nos dan la pendiente de la función.

z = 15 supuesto

...trasladar a z en cualquier dirección respetando la pendiente (paralela a la obtenida).

Haciendo coincidir z con todos los vértices conocidos nos damos cuenta que a medida que se aleja del origen crece. El punto máximo es C.

... donde z = 3(2) + 5(6) = 36

Max z = 36

Los vértices son capaces de generar lo OPTIMO.

CONVEXIDAD: Si dados dos puntos cualesquiera contenidos en el conjunto y se unen mediante el segmento y si se cumple para todo par de puntos, es convexo.

Para resolver mediante el algorítmo SIMPLEX, el conjunto debe ser CONVEXO.

CONJUNTO CONVEXO: un conjunto es convexo si dados dos puntos A y B cualesquiera, contenidos en el mismo, el segmento de recta que los une queda contenido en dicho conjunto totalmente.

DEFINICION MATEMATICA: Un conjunto convexo se forma por combinación convexa lineal entre dos puntos A y B como sigue:

P = A + B(1 - ) para 0 "  " 1

...donde A y B son vectores y  es un escalar.

Ejemplo: Obtener un punto p que sea CCL entre dos vértices A y F con  = ½.

P = ((0,6) ½) + (4,0) (1 - ½)

P = (0,3) + (2,0)

P = (2,3)

OJO: NO SE PUEDEN GENERAR LOS VERTICES.

METODO GRAFICO.

Ejemplo: Max z = 3x1 + 5x2

...sujeta a:

x1 " 4 ... (1)

2x2 " 12 ... (2)

3x1 + 2x2 " 18 ... (3) x1 ; x2 " 0

CONJUNTO CONVEXO: Un conjunto es convexo si dados dos puntos A y B contenidos en el mismo, el segmento de recta que losa une queda contenido totalmente en dicho conjunto.

DEFINICION MATEMATICA: Un conjunto convexo se forma por combinación convexa lineal entre dos puntos A y B como sigue:

P = A + B(1 - ) para 0 "  " 1

Ejemplo: Obtener un punto P que sea CCL entre los vértices A y F con  = ½

P = (0,6) ½ + (4,0) (1 - ½9 = (0,3) + (2,0) " P = (2,3)

(pueden calcularse así todos los puntos a excepción de los vértices)

Cuando se tienen desigualdades ha y que convertir a igualdades (ec. lineales).

Tomando la restricción 3:

En este caso coincidió, pero no lo sabíamos, si no fuera así, necesitamos una nueva variable “x” llamada holgura y retomando el ejemplo anterior se tendría:

x1 + x3 = 4 ... (1)

2x2 + x4 = 12 ... (2)

3x1 + 2x2 + x5 = 18 ... (3) x3 , x4 , x5 HOLGURA.

x1 ... x5 " 0

...y se tiene un sistema ampliado a 5 dimensiones.

VERTICE	X1	X2	X3	X4	X5	OBNES.
O	0	0	4	12	18	FACTIBLE
A	0	6	4	0	6	FACTIBLE
C	2	6	2	0	0	FACTIBLE
F	4	0	0	12	6	FACTIBLE
H	4	3	0	6	0	FACTIBLE
B	0	9	4	-6	0
J	6	0	-2	12	0
R	4	6	0	0	-6

... en las observaciones se señalan los puntos como factibles porque cumplen con la no negatividad, pero los puntos B, J y R no cumplen con la condición de no negatividad, lo cual nos indica que no son factibles.

Retomando el sistema anterior, solo cambiaremos el signo de desigualdad de (3) que será ".

3x1 + 2x2 " 18 ... (3)

Agregaremos al sistema ahora una 4ª restricción, siguiendo con la condición de no negatividad.

3x1 + 2x2 " 18 ... (4)

(x1 , x2 )

si .... (0 , 12 ) 4

y si ... (8 , 0 )

Ampliando el sistema inmediato anterior, podemos hacer lo mismo que antes con 1, 2 y 4, pero no con 3 porque el signo es " y nos indica que mínimo 18 y necesitaremos una VARIABLE SUPERFLUA o de HOLGURA NEGATIVA.

VERTICE	X1	X2	X3	X4	X5	X6	OBSERVACIONES
O	0	0	4	12	-18	24	NO FACTIBLE
A	0	6	4	0	-6	12	NO FACTIBLE
C	2	6	2	0	0	6	FACTIBLE
F	4	0	0	12	-6	12	NO FACTIBLE
H	4	3	0	6	0	6	FACTIBLE
B	0	9	4	-6	0	6	NO FACTIBLE
J	6	0	-2	12	0	6	NO FACTIBLE
R	4	6	0	0	6	0	FACTIBLE

Ojo: en el renglón R de la tabulación anterior hay tres ceros, a diferencia del resto de la misma tabulación y de la anterior de 5 dimensiones. Esto se debe a que por ese punto pasan 3 rectas y por el resto convergen solo dos rectas.

En el punto “R” intersectan:

1 2

R 1 4

• 4

... y se dice que el punto como tal es NO UNICO.

Y tomando en consideración que para un solo punto se requiere de una intersección, el resto de los puntos es UNICO. Se dice entonces que el punto R tiene:

SOLUCION FACTIBLE

SOLUCION NO UNICA

... y solo cuando se dan las dos anteriores soluciones se llama SOLUCION DEGENERADA.

Un vértice no único se establece cuando hay redundancia.

Observaciones características.

...el vértice O es NO FACTIBLE y UNICO.

A es NO FACTIBLE y UNICO.

C es FACTIBLE y UNICO.

F es NO FACTIBLE y UNICO.

H es FACTIBLE y UNICO.

B es NO FACTIBLE y UNICO.

J es NO FACTIBLE y UNICO.

R es FACTIBLE, UNICO y DEGENERADO.

...y por lo tanto, del gráfico anterior decimos entonces que C y H son no degeneradas.

DEFINICIONES:

SOLUCION: Es un conjunto de valores para las variables o bien un vector X = (x1 , x2 , ... , xj , xj+1 , ... , xn , xn+1 , ... , xn+m ) que satisface al conjunto de restricciones

SOLUCION FACTIBLE: Es un conjunto de valores para las variables o bien un vector X = (x1 , x2 , ... , xj , xj+1 , ... , xn , xn+1 , ... , xn+m ) que satisface al conjunto de restricciones

...y además satisface a toda xj " 0 .

SOLUCION BASICA: Es una solución que se obtiene al hacer nulas, al menos, (m+n)-m variables, en donde

m = # total de restricciones,

n = # de variables de decisión (originales)

[en el ejemplo, m = 3 y n = 2 ! (3+2) - 3 = 2 ... en el ejemplo de 4 restricciones m = 4 y n = 2, resultando (4 + 2) - 4 = 2 .... y por esto, en el sistema ampliado se tiene en VERTICE : SOLUCIONES BASICAS].

...y se resuelve el sistema para las restantes.

SOLUCION BASICA FACTIBLE: Es una solución básica que cumple toda xj " 0.

SOLUCION DEGENERADA: Es una solución básica factible que tiene menos de m variables estrictamente positivas.

SOLUCION NO DEGENERADA: Es una solución básica factible con exactamente m variables estrictamente positivas.

SOLUCION OPTIMA: Es una solución básica factible que optimiza la función

La `solución' en el gráfico 1 y 2 sería solo el área sombreada.

La `solución factible' en 1 cuando cumple con " 0 y en 2 coincide con `solución' (polígono A, C, H, F, O)

`Solución básica' en 1 todos los vértices pero en 5 dimensiones y en 2 solo C, R, H pero en 6 dimensiones.

Ejemplo: Mix z = 4x1 + 3x2

...sujeta a:

x1 + x2 " 6 ... (1)

2x1 - x2 " 0 ... (2)

x1 " 2 ... (3)

x1 ; x2 " 0

x1 , x2 2x1 = x2 x1 , x2

, 6) B 1 2 2(0) = 1(0) : (0,0) O 3 (2 , 0) F

(6 , 0) A 2(1) = 1(2) : (1,2)

2(2) = 1(4) : (2,4) C

El conjunto anterior se diferencía de los anteriores porque es un CONJUNTO ABIERTO y al pedir un máximo, se tendría una solución SIN LÍMITE.

Recordar que si el origen se encuentra en el conjunto factible, al pedirse minimizar, esta se llama solución trivial.

4(2) + 3(4) = 20 ....[Min]

Considerando Min z

4(6) + 3(0) = 24

Resolviendo analíticamente:

x1 + x2 - x3 " 6

2x1 - x2 - x4 " 0

x1 - x5 " 2 x1, x2 , x3 , x4 , x5 " 0

(los vértices en 2 dimensiones pasan a ser soluciones básicas en 3 dimensiones)

VERTICES O SOLUCIONES BASICAS	X1	X2	X3	X4	X5	CARACTERISTICAS
B	0	6	0	-6	-2	N.FACTIBLES, UNICA
F	2	0	-4	4	0	N.FACTIBLES, UNICA
O	0	0	-6	0	-2	N.FACTIBLES, NO UNICA
C	2	4	0	0	0	N.FACTIBLES, NO UNICA, DEGE.
A	6	0	0	12	4	N.FACTIBLES, UNICA

La degeneración en C se provoca por una restricción redundante : 3 C se genera de la simultaneización de las rectas 1,2 ; 2,3 ; 1,3 y se tienen 3 soluciones básicas.

Como en el gráfico anterior el número de soluciones básicas es infinito y hacemos o tomamos solo soluciones básicas:

# máximo de m + n = m + n = m + n !

soluciones básicas m n m! n!

m = # de restricciones.

n = # de variables de decisión.

# = 3 + 2 = 3 + 2 = 5 = 5 = 5 ! = 10

3 2 3 2 3! 2!

En los ejemplos anteriores no cambia el número máximo, pero las líneas horizontal y vertical o cruzan el eje contrario.

El modelo de programación lineal se puede presentar en diferentes formas y algunas de ellas resultan importantes para el manejo de los temas siguientes del curso.

FORMA CANONICA: Esta es útil para el manejo del tema que se refiere al problema dual de cualquier problema de programación lineal. La forma canónica aceptable y reconocida en la mayoría de los textos debe cumplir con lo s siguientes requisitos:

Función objetivo maximizar.

Restricciones del tipo ".

Condiciones de negatividad para variables.

Otra forma legítima para considerar como canónica es cumpliendo con los siguientes requisitos:

Función objetivo de minimizar.

Restricciones del tipo ".

Condiciones de no negatividad para variables.

FORMAS CANONICAS.

Maximizar. Minimizar.

z = Cx z = Cx

sujeto a: sujeto a:

Ax " b Ax " b

x " 0 x " 0

Max z = 3x1 + 5x2 (-1) Min z = -3x1 - 5x2

Suj. a: Suj. a:

x1 " 4 -x1 " -4

2x2 " 12 - 2x2 " -12

3x1 + 2x2 " 18 -3x1 - 2x2 " -18

x1 ; x2 " 0

FORMA ESTANDAR: El modelo de programación lineal para resolverse, necesita arreglarse para igualdades, lo cual se consigue utilizando tanto variables de holgura como variables superfluas. Lo anterior da lugar a la presentación del modelo cumpliendo con l os siguientes requisitos:

Función objetivo para Max. o bien Min.

Restricciones del tipo =.

Lado derecho de restricciones no negativo.

Condiciones de no negativo para variables.

FORMA IRREGULAR: El modelo de programación lineal generalmente se presenta en forma irregular; es decir, no cumple con la forma canónica ni tampoco forma estándar, pero mediante el procedimiento algebraico se puede conseguir convertir a un modelo que cumpla las formas mencionadas tal como se ve en el siguiente ejemplo:

Formas equivalentes del modelo de programación lineal.

Ejemplo: Max z = 5x1 - x2 + 3x3

...sujeta a:

x1 + 2x2 + 4x3 " 12 ... (1)

x2 + x3 = 5 ... (2)

2x1 - x2 + 5 x3 " 6 ... (3) x1 ; x2 " 0 ; x3 LIBRE

Formas canónicas (en forma vectorial)

Max z = Cx Min z = Cx

sujeto a: sujeto a:

Ax " 0 Ax " 0

x " 0 x " 0

.....en el caso anterior conviene usar Max para no invertir la función objetivo.

Forma canónica.

Algo que incomoda es x1 " 0 y entonces se hace un acuerdo matemático para crear otra variable x1 como se hace a continuación:

x1 " 0 ! -x1' = x1 " 0

...la hicimos igual a x1' y luego multiplicamos todo por -1.

(-x1' = x1 " 0) (-1) =! x1' = -x1 " 0

...ahora para x3 :

x3 = (x3+ - x3-)

x3+ ; x3- " 0

si... x3+ > x3- ! x3 > 0

x3+ < x3- ! x3 < 0

x3+ = x3- ! x3 = 0

iniciando...

Max z = 5x1 - x2 + 3x3

! z = 5x1' - x2 + 3x3+ - 3x3-

...sujeta a:

x1' + 2x2 + 4x3+ - 4x3- " 12 ... (1)

Para la restricción original (2) no tengo un proceso específico, pero se ponen en sustitución de esta restricción de igualadad a 2 restricciones de desigualdad con signos opuestos (mismo términos).

x2 + x3+ - x3- " 5 ........ (2+)

x2 + x3+ - x3- " 5 ........ (2-)

...pero como no tenemos que tener aquí " , entonces multiplicamos a 2- por (-1) y queda de la siguiente forma:

-x2 - x3+ + x3- " -5 ........ (2-)

Pasando a la restricción (3), hay que multiplicarla por (-1) sin dejar de tomar el signo para x1'.

2x1' + x2 - 5x3+ + 5x3- " -6

x1' = -x1 " 0 ; x2 , x3+ ; x3- " 0

Agrupando todo lo anterior resulta la forma canónica.

Forma estándar.

Max/Min z = Cx

Sujeta a: Ax=b

x " 0

Max z = 5x1' - x2 + 3x3' - 3x3'

Sujeta a: (tomando las originales y tomando los arreglos para variables)

- x1' + 2x2 + 4x3+ - 4x3- + x4 = 12 ..... (1)

x2 + x3+ - x3- = 5 ..... (2)

- 2x1' - x2 + 5x3+ - 5x3- - x5 = 6 ..... (3)

SUPERFLUA

x1' ; x2 ; x3+ ; x3- ; x4 y x5 " 0

......quedando de esta manera la forma estándar.

Ejercicio:

Min z = 4x1 + 3x2 - x3

Sujeta a:

2x1 - x2 + 2x3 = 14 ..... (1)

x1 + x2 + 3x3 " 8 ..... (2)

3x2 + 2x3 " 4 ..... (3)

x1 LIBRE ; x2 " 0 ; x3 " 0

Forma canónica.

-x2' = x2 " 0 x1 = (x1+ - x1-) x1+ > x1- ! x1 > 0

x2' = -x2 " 0 x1+ " 0 ; x1- " 0 x1+ < x1- ! x1 < 0

x1+= x1- ! x1 = 0

Min z = 4x1+ - 4x1- - 3x2' - x3

Sujeta a:

(2x1+ - 2x1- + 2x2' + 2x3 " 14) (-1)

2x1+ - 2x1- + 2x2' + 2x3 " 14 ..... (1-)

-2x1+ + 2x1- - 2x2' - 2x3 " -14 ..... (1+)

(x1+ - x1- - 2x2' + 3x3 " 8) (-1)

-x1+ + x1- + 2x2' - 3x3 " 8 ..... (2)

- 3x2' + 2x3 " 4 .....(3)

!

-2x1+ + 2x1- - x2' - 2x3 " -14 ..... (1+)

2x1+ - 2x1- + x2' + 2x3 " 14 ..... (1-)

-x1+ + x1- + 2x2' - 3x3 " 8 ..... (2)

- 3x2' + 2x3 " 4 ..... (3)

x1+ ; x1- ; x2' ; x3 " 0

Forma estándar.

-x2' = x2 " 0 x1 = (x1+ - x1-)

x2' = -x2 " 0 x1+ " 0 ; x1- " 0

Min z = 4x1+ - 4x1- - 3x2' - x3

Sujeta a:

2x1+ - 2x1- + x2' + 2x3 " 14 ..... (1)

x1+ - x1- - 2x2' + 3x3 + x4 " 8 ..... (2)

- 3x2' + 2x3 - x5 " 4 ..... (3)

x1+ ; x1- ; x2' ; x3 ; x4 ; x5 " 0

MÉTODO SIMPLEX.

El método símplex fue desarrollado en 1947 por el Dr. George Dantzig y conjuntamente con el desarrollo de la computadora hizo posible la solución de problemas grandes planteados con la técnica matemática de programación lineal.

El algorítmo denominado símplex es la parte medular de este método; el cual se basa en la solución de un sistema de ecuaciones lineales con el conocido procedimiento de Gauss-Jordan y apoyado con criterios para el cambio de la solución básica que se resuelve en forma iterativa hasta que la solución obtenida converge a lo que se conoce como óptimo.

Las definiciones siguientes fundamentadas en 3 importantes teoremas, ayudan a entender la filosofía de este eficiente algorítmo.

Teoremas de la Programación Lineal.

El conjunto de soluciones factibles para un problema de P.L. es un conjunto convexo.

La solución óptima del problema de programación lineal , si existe, es un punto extremo (vértice) del conjunto de soluciones factibles. Si dicha solución óptima se tiene para más de un punto extremo, entonces también optimiza en cualquier punto que sea combinación convexa lineal entre los dos vértices que optimiza.

...y suponiendo que la función objetivo fuera:

 Max zC = 6x1 + 4x2 ! 6(2) + (6) = 36

Max zH = 6(4) + 4(3) = 36

Max zA = 6(0) + 4(6) = 24

Calcular P como CCL entre C y H con = ¼

P =  C + (1 - ) H

P = ¼ (2 , 6) + ( 1 - ¼) (4 , 3)

P = ( ½ , 3/2) + (3 , 9/4) = (7/2 , 15/4)

... y retomando el gráfico anterior:

ZP = 6 (7/2) + 4 (15/4) = 36

El número máximo de puntos extremos (vértices) por revisar en la búsqueda de la solución óptima del problema es finito y coincide con el número máximo de soluciones básicas únicas que se pueden determinar mediante el binomio...

m + n = m + n = (m+n) !

m n m! n!

DIAGRAMA FUNCIONAL DEL

METODO SIMPLEX.

NO

SI

CRITERIOS DEL ALGORITMO

SIMPLEX PARA EL CAMBIO DE BASE.

El algorítmo símplex maneja exclusivamente soluciones básicas y que cumplan con factibilidad; es decir, todas las variables deben ser no negativas. Por lo tanto, para el manejo de las soluciones básicas factibles y su valoración, requiere de la aplicación de ciertos criterios fundamentados en los teoremas ya mencionados. Por cada intento de cálculo es necesario aplicar los siguientes criterios:

• Criterio de optimalidad. Se aplica en el algorítmo símplex para determinar entre las variables no-básicas, una que entre a la base, eligiendo aquella no-básica con el coeficiente más negativo en el renglón z de la tabla símplex; si el problema tiene el objetivo de maximizar. En caso contrario, es decir, para minimizar, debe elegirse para variable entrante a la base a aquella que tenga el coeficiente más positivo en el renglón z de la tabla.

• Criterio de factibilidad. Se aplica en el algoritmo símplex para determinar entre las variables básicas a una que salga de la base, aplicando la siguiente función.

x i

Min ; solo a i k > 0

a i k

Esto es válido tanto para problemas de maximizar como de minimizar.

Elemento pivote. Se declara como elemento pivote a aquél coeficiente que se ubica en el cruce de la columna `k' y el renglón `i' elegidos en los dos criterios ya anotados.

Ejemplo: Resolver con el método símplex el siguiente modelo de programación lineal.

Max z = 3x1 + 5x2 ...sujeta a:

x1 " 4 (1)

2x2 " 12 (2)

3x1 + 2x2 " 18 (3) x1 ; x2 " 0

... conseguir la forma estándar

Max z = 3x1 + 5x2 ...sujeta a:

x1 + x3 " 4 (1)

Bloque #1 2x2 + x4 " 12 (2)

3x1 + 2x2 + x5 " 18 (3) x1 ; x2 ; x3 ; x4 , x5 " 0

holguras

FORMA MATRICIAL.

Descargar

BASE	Z	x1	VE ! x2	x3	x4	x5	SOLUCION
z	1	-3	-5	0	0	0	0
x3	0	1	0	1	0	0

Enviado por:	Alf
Idioma:	castellano
País:	México