RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA...
Transcript of RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA...
![Page 1: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/1.jpg)
(2.c) RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX
• FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de las v. básicas en función de las no básicas. Forma tabular.• CAMBIO DE BASE CON CONSERVACIÓN DE LA FACTIBILIDAD. Casos singulares. Región no acotada. Cambio degenerado de base.• CONCEPTO DE COSTE REDUCIDO. Cambio de base con disminución de la f.obj. Cálculo de los costes reducidos.• ALGORITMO DEL SÍMPLEX Forma tabular. Fórmulas matriciales. Ejemplos• INICIALIZACIÓN DEL ALGORITMO. (fase 0) Método de las variables artificiales.
![Page 2: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/2.jpg)
U P C Investigación Operativa U P C
FORMA STANDARD DE UN P. P.L.
Tras transformaciones, todo P.P.L. puede expresarse de la forma:
• Todas las variables xi están sujetas a xi ≥ 0, i = 1, 2, … n• Todos los términos de la derecha bi son no negativos: bi ≥ 0, i = 1, 2, … m• La matriz de coeficientes A es de pleno rango:
Hay m columnas de A tales que al formar una matriz B con ellas,ésta es inversible.
( m ≤ n )
Todos los paquetes para P.L. convierten automáticamente a la forma Standard
![Page 3: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/3.jpg)
U P C I. U P C Investigación Operativa
DEFINICIÓN DE BASE FACTIBLE .
Sistema Ax = b, x ≥ 0
B=
DEFINICIÓN: B es base factible si:
≥0
B es una base asociada al conjunto de índices {1, 4, 5}
![Page 4: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/4.jpg)
U P C U P C Investigación Operativa
Sistema Ax = b, x ≥ 0
B base asociada a IB = {1, 4, 5}
≥0
![Page 5: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/5.jpg)
Una estrategia para resolver el P.P.L. consiste en:
1. Determinar si F=∅ .
2. En caso contrario, determinar una s.b.f. (vértice) de F inicial
3. Visitar s.b.f's hasta encontrar una que sea solución de (P)
4. Determinar si la s.b.f. solución es única o existen otrassoluciones.
![Page 6: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/6.jpg)
En este tema:• Se desarrolla un método para saltar de una s.b.f. a otra vecina. (CONSERVACIÓN DE LA FACTIBILIDAD).
• En cada salto se mejora la función objetivo.
• Se detecta si se alcanza una solución de (P) o bien si elproblema es no acotado.
• Finalmente, se desarrolla un método para encontrar una s.b.f.inicial o bien detectar que F=∅ .
ALGORITMO DEL SÍMPLEX
![Page 7: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/7.jpg)
B xB + N xN = b
B-1 ( B xB + N xN ) = B-1 b
xB + B-1N xN = B-1 b
xB + Y xN = y0
FORMA CANÓNICA DE UN SISTEMA LINEAL Ax=bRespecto del conjunto de índices IB = {1, 4, 5}
![Page 8: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/8.jpg)
U P C U P C Investigación Operativa
FORMA CANÓNICA DE UN SISTEMA LINEAL Ax=b
Para el conjunto de índices asociados a una base B, IB={i1, i2 ,… , im}
xB + Y xN = y0
Columnas básicas Columnas no básicas
≥ 0 si B es base factible
![Page 9: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/9.jpg)
U P C I.O.E. Diploística U P CInvestigación Operativa
xB (xN) = y0 - Y xNLa forma canónica expresa la dependencia de lasvariables xB respecto de las xN
Para xN = 0, xB(0) = y0; el punto xR = (y0 , 0 ) es un vértice del Poliedro.
Si B es una base factible: xB(0) ≥0;Incrementando xN desde 0 encontraremos otros puntos xB (xN) ≥0.Se incrementa una sola v. No básica. El resto se mantienen a cero
CAMBIO DE BASE CON CONSERVACION DE LA FACTIBLIDAD
x2
x1
IB = {1, 4, 5}
![Page 10: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/10.jpg)
U P C I.O.E. U P CInvestigación Operativa
x21 2
CAMBIO DE BASE CON CONSERVACION DE LA FACTIBLIDAD
![Page 11: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/11.jpg)
U P C I.O.E. Diplomatur U P CInvestigación Operativa
PIVOTACIÓN
![Page 12: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/12.jpg)
U P C I.O.E. Diplomatura de Estadística U P C Investigación Operativa
CAMBIO DE BASE CON CONSERVACION DE LA FACTIBLIDADENTRA VARIABLE NO BÁSICA -> SALE VARIABLE BÁSICA
![Page 13: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/13.jpg)
U P C I.O.E. Diplomatura de Estadística U P CInvestigación Operativa
CAMBIO DE BASE CON CONSERVACION DE LA FACTIBLIDADCASOS SINGULARES:
x2
x1
IB = {1, 4, 5}
Incrementando x2 al menos unav. básica crece indef.
Se detecta dirección de crecimiento ilimitado de la regiónfactible
![Page 14: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/14.jpg)
U P C I.O.E. Diplomatura de Estadística U P C Investigación Operativa
CAMBIO DE BASE CON CONSERVACION DE LA FACTIBLIDADCASOS SINGULARES:
Se obtiene elmismo punto
![Page 15: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/15.jpg)
U P C I.O.E. Diplomatura de Estadística U P CInvestigación Operativa
![Page 16: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/16.jpg)
U P C I.O.E. Diplomatura de Estadística U P C Investigación Operativa
![Page 17: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/17.jpg)
U P C I.O.E. Diplo U P C Investigación Operativa
x2
x1
![Page 18: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/18.jpg)
U P C I.O.E. Diplomatura de Estadística U P C Investigación Operativa
x2
x1
![Page 19: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/19.jpg)
U P C I.O.E. Diplomatura de Estadística
U P CInvestigación Operativ
TEMA 2.c
RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX
Semana 2. Sesión 2
• Concepto de coste reducido. Expresión de las v. básicas en función de las no básicas. Cambio de base con disminución de la f.obj. Cálculo de los costes reducidos.
• ALGORITMO DEL SÍMPLEX Forma tabular. Fórmulas matriciales. Ejemplos
![Page 20: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/20.jpg)
U P C I.O.E. Diplomaturaa U P C Investigación Operativ
B xB + N xN = b
B-1 ( B xB + N xN ) = B-1 b
xB + B-1N xN = B-1 b
xB + Y xN = y0
xB (xN) = y0 - Y xN
![Page 21: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/21.jpg)
U P C I.O.E. Diplomatura U P CInvestigación Operativa
CAMBIOS DE BASE DIMINUYENDO EL VALOR DE LA F.OBJETIVO
Se quieren encontrar las solucionesdel problema de P.L.
![Page 22: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/22.jpg)
![Page 23: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/23.jpg)
U P C I.O.E. Diplomatura de Estadística U P C Investigación Operativa
![Page 24: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/24.jpg)
U P C I.O.E. Diplomatura de Estadística U P C Investigación Operativa
CÁLCULO DE LOS COSTES REDUCIDOS
![Page 25: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/25.jpg)
U P C I.O.E. Diplomatura de U P C Investigación Operativa
DISPOSICIÓN EN FORMA TABULAR Y FÓRMULAS MATRICIALES.
![Page 26: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/26.jpg)
U P C I.O.E. Diplomatura de Estadística U P C I.O.D. Diplomatura de Estadística
![Page 27: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/27.jpg)
U P C I.O.E. Diplomatura de Estadística U P C Investigación Operativa
A
B
x1
x2
x3
VÉRTICE A
![Page 28: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/28.jpg)
U P C I.O.E. Diplomatura de Estadística U P C Investigación Operativa
x1
x2
x3
VÉRTICE B
VÉRTICE C
BC
ÓPTIMOS ALTERNATIVOS
![Page 29: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/29.jpg)
U P C I.O.E. Diplomatura de Estadístic U P C Investigación Operativa
x1
x2
x3Recorriendo las diferentes basesencontraríamos los puntos C, D, E, F.En todos ellos la f.obj. tiene igualvalor: z* = 220/15.
C
D
E
F
G
Cualquier punto G sobre lacara tendrá igual valor para laf.obj.
( COMPROBADLO)
![Page 30: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/30.jpg)
U P C I.O.E. Diplomatura de Estadística U P C Investigación Operativa
EFICACIA DEL ALGORITMO SÍMPLEX
• En el ejemplo anterior se examinan sólo 3 de los 9 vértices delpoliedro.
• Hay ejemplos en los que el algoritmo debe examinarlos TODOS(Klee-Minty, 1972). ⇒ PEOR CASO POSIBLE.
x1
x2
x3
![Page 31: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/31.jpg)
En los problemas reales con n=nºvar. >> m=nº restr. :
( A = ………….….. )
Nº medio de iteraciones ≈ k m, k entre 1 y 3 !!!!
En la actualidad el SÍMPLEX continúa siendo un algoritmopresente en casi todos los paquetes de soft. para P.L.
EFICACIA DEL ALGORITMO SÍMPLEX
![Page 32: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/32.jpg)
![Page 33: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/33.jpg)
U P C I.O.E. Diplomatura de Estadística U P C I.O.D. Diplomatura de Estadística
![Page 34: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/34.jpg)
![Page 35: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/35.jpg)
![Page 36: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/36.jpg)
U P C I.O.E. Diplomatura de Estadística
U P C Investigación Operativa
Sesión 2.c
RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX
Semana 3.
• ALGORITMO DEL SÍMPLEX (Repaso) Forma tabular. Fórmulas matriciales.
• Inicialización del algoritmo. (fase 0) Objetivos. Detección de problemas infactibles. Método de las variables artificiales. Problema auxiliar. Casos. Ejemplos
![Page 37: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/37.jpg)
U P C I.O.E. Diplomatura de Estadística U P C I.O.D. Diplomatura de Estadística
![Page 38: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/38.jpg)
U P C U P C Investigación Operativaí
IDENTIFICACIÓN DE BASES INICIALES FACTIBLES.
No es posible identificar unabase inicial factible
![Page 39: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/39.jpg)
U P C I.O.E. Dtica U P C Investigación Operativaí i
IDENTIFICACIÓN DE BASES INICIALES FACTIBLES.
VARIABLES ARTIFICIALES Y PROBLEMA AUXILIAR:
Se construye un "problema auxiliar" con las mismas variablesy coeficientes en las restricciones que en el problema original.
Se añaden las variables artificiales (≥ 0):
• Una por cada fila con una variable de exceso.
• Una por cada fila sin variable de exceso ni de holgura.
La función objetivo del problema auxiliar es la suma de lasVariables artificiales.
![Page 40: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/40.jpg)
I.O.E. Dica Investigación Operativaí i
![Page 41: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/41.jpg)
U P CU P C Investigación Operativaí i
Para el problemaauxiliar se obtiene
una base inicialfactible de forma
inmediata
![Page 42: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/42.jpg)
U P CU P C
í i
SOLUCIÓN del PROBLEMA AUXILIAR
Casos:
a) El problema auxiliar presenta una solución óptima con lasvariables auxiliares ai = 0
• Se obtiene una base inicial factible para el problema original. ⇒ El problema original tiene REGIÓN FACTIBLE no vacía.
b) El problema auxiliar presenta una solución óptima con algunavariable auxiliar ai > 0
• No se puede hallar base inicial factible para el problema
original. ⇒ El problema original tiene REGIÓN FACTIBLE vacía.
![Page 43: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/43.jpg)
U P CU P C
í
RESOLVER
![Page 44: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/44.jpg)
U P CU P C
í
![Page 45: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/45.jpg)
U P CU P C
í
![Page 46: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/46.jpg)
U P C I.O.E. Diplomatura de Estadística U P C I.O.D. Diplomatura de Estadística
![Page 47: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/47.jpg)
U P CU P C
í
RESOLVER
![Page 48: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/48.jpg)
U P CU P C
í i
![Page 49: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/49.jpg)
U P CU P C
í i
1/112
![Page 50: RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX ... · ALGORITMO DEL SIMPLEX • FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de](https://reader030.fdocumento.com/reader030/viewer/2022013006/5ba3813109d3f21e368b8b80/html5/thumbnails/50.jpg)
PRÁCTICA 1Seguimiento de las iteraciones del SÍMPLEX mediante LINDO
MAX 3 X1 + 2 X2 SUBJECT TO 2) 2 X1 + X2 <= 100 3) X1 + X2 <= 80 4) X1 <= 40 END