apuntes ing4520 2011/02 programación matemáticajuaperez/clases_def_prelim_draft.pdf ·...
TRANSCRIPT
Universidad de Los Andes
Facultad de Ingeniería y Ciencias
Ingeniería Industrial
Apuntes ING4520 – 2011/02
Programación Matemática
Definiciones Preliminares
Este documento corresponde a los apuntes de las clases de definiciones preliminares. Es un
documento que está en revisión, tiene una condición de apunte de clase, y por ende NO está libre
de errores. Se agradece que reporten ya sea al profesor o al auxiliar si encuentran errores en el
presente documento a fin de poder mejorarlo.
I
Tabla de Contenidos
1 Definiciones Preliminares ________________________________________ 2
1.1 Problema de Programación Lineal _________________________________ 6
1.2 Soluciones Básicas Factibles _____________________________________ 10
2 El Método Simplex ______________________________________________ 20
2.1 ¿Qué es Pivotear? ______________________________________________ 21
2.2 Puntos Extremos Adyacentes ____________________________________ 24
2.3 Determinando una Solución Mínima Factible ______________________ 28
2.4 Definición del Procedimiento Completo, Consideraciones Docentes y
Prácticas ___________________________________________________________ 33
2.4.1 Transformaciones previas del problema ________________________ 34
2.4.2 ¿Fase I (F1)? _______________________________________________ 36
2.4.3 Fase II ____________________________________________________ 40
2.4.4 Procedimiento Completo _____________________________________ 40
Tabla de Ilustraciones
ILUSTRACIÓN 1: CONJUNTO CONVEXO Y CONJUNTO NO CONVEXO ............................ 3
ILUSTRACIÓN 2: INTUICIÓN DETRÁS DE LA DEMOSTRACIÓN ......................................... 6
ILUSTRACIÓN 3: ALGORITMO PARA ENCONTRAR MEJOR SOLUCIÓN BÁSICA FACTIBLE
................................................................................................................................... 13
ILUSTRACIÓN 4: EJEMPLO DE LOS PUNTOS EXTREMOS DE UN POLÍGONO QUE SON SUS
VÉRTICES. .................................................................................................................. 14
ILUSTRACIÓN 5: INTRODUCIENDO LA FUNCIÓN OBJETIVO ........................................... 16
II
ING4520 1
RESUM EN
En este capítulo veremos los tópicos básicos de programación lineal, los cuales
sirven de base para el entendimiento completo del curso. Se hace una formalización
matemática de lo que un problema de programación u optimización significa, luego
se presentan las formas clásicas de representarlos, luego se hace la mención
particular a problemas de optimización lineales, para finalmente aprender el
método Simplex.
ING4520 2
1 DEFINICIONES PRELIMINARES
Definición: Problema de Optimización – Un problema de optimización consiste de
un conjunto D , el cual denominaremos dominio, y una función real :f D , que
denominaremos función objetivo. El valor f x representa el “beneficio” o
“costo” asociado con la variable de decisión x D .
Los problemas de optimización pueden ser de maximización o minimización. En un
problema de maximización, el objetivo es encontrar un valor de x D tal que
f y f x y D . En otras palabras, se busca el elemento del dominio que
permita obtener el mayor beneficio. En un problema de minimización
(maximización), el objetivo es encontrar un valor de x D tal que f x f y (
f x f y ) y D En este caso es el elemento del dominio con menor (mayor)
costo (beneficio).
Definición: Problema de Programación Matemática – Un problema de
programación matemática está compuesto por una función : nf un conjunto
de m funciones de restricciones 1
:mn
i ig y un vector de constantes
1,...,m
mb b b . El objetivo es encontrar x D que minimice (maximice) f x ,
donde nD está definido en forma implícita por restricciones de desigualdad
i ig x b , 1 i m , 1
: ,1m n
i iiD x g x b i m .
La notación habitual para representar un problema de programación matemática es
la siguiente:
min
. .
1,...,i i
f x
s a
g x b i m
Es importante mencionar que puede se mínimo o máximo, en la literatura podrán
encontrar ambas versiones. En esta sección del capítulo diremos que es
minimización, cuando llegue el momento (Simplex) se explicará donde difiere el
ING4520 3
método en el caso de mínimo o máximo, pero como se pueden imaginar son
totalmente equivalentes.
En dicha notación la abreviación s.a. significa “sujeto a”, para referirse a la
posterior definición de las restricciones.
El dominio de las variables puede tener variadas formas, en términos específicos y
para los propósitos de este capítulo, nos enfocaremos en dominios convexos. Pero
¿Qué es eso?
Definición: Conjunto Convexo – Un conjunto nS es convexo si todo segmento
de línea que une dos puntos contenidos en S está completamente contenido en
dicho conjunto. Es decir, S es convexo que si para 0,1 y ,x y S se tiene que
1x y z S .
Ilustración 1: Conjunto Convexo y Conjunto no Convexo
Definición: Función Convexa – Si nS , una función :f S es una función
convexa si dado un escalar 0,1 y ,x y S se tiene que
1 1f x y f x f y .
En otros términos, una función es convexa si su imagen sobre todas las
combinaciones de puntos de un conjunto convexo, está acotada superiormente por
la combinación convexa de sus imágenes.
ING4520 4
Ejemplo: Las normas son funciones : n que satisfacen las siguientes tres
condiciones:
i. 0 0 0 0nx x
ii. ncx c x x c
iii. , nx y x y x y
Demostración:
Sea : nf una norma, , nx y y 0,1 . Así se tiene que:
1 1x y x y por propiedad iii.
1 1x y x y por propiedad ii.
Así 1 1x y x y QED (Quod erat demonstrandum).
Definición: Problema convexo de programación matemática – Un problema de
programación matemática.
min
. .
1,...,i i
f x
s a
g x b i m
Se dice que es convexo si tanto la función objetivo : nf y las funciones de
restricciones 1
:mn
i ig son convexas.
Como se ha definido en forma implícita el conjunto de restricciones, acá se
requieren dos condiciones.
Lema: La intersección de una colección de conjuntos convexos es convexa.
Demostración:
ING4520 5
La demostración es simple, la intersección de todos los conjuntos son una serie de
de puntos que por definición está también en todos ellos, luego, debido a que cada
uno de ellos es convexo, entonces en particular, la intersección también los será.
Lema: Sea : ng una función convexa y b una constante. El conjunto
:n nS x g x b es convexo.
Demostración:
Sean ,x y S y 0,1 , entonces debido a que la función es convexa, se tiene que:
1 1g x y g x g y
Sea max ,h g x g y , entonces se tiene que 1 1g x g y h h .
1g x y h debido a que 1 1 .
1g x y b debido a que ,x y S .
Teorema: El dominio 1
mii
D D , :ni i iD x g x b de un problema de
programación convexo.
min
. .
1,...,i i
f x
s a
g x b i m
Es un conjunto convexo.
La demostración del teorema anterior, es consecuencia directa de los dos lemas
precedentes.
Definición: Mínimo (Máximo) Local y Mínimo (Máximo) Global – Sea nD y la
función : nf . Diremos que x D es un mínimo (máximo) local de la función
en el dominio, si f x es el valor más pequeño de la función en alguna esfera de
dimensión n y centrada en x . Formalmente, tal que f x f y y D (
ING4520 6
f x f y y D ), tal que 2
x y . En el caso que dicha condición se cumple
y D entonces x D en un mínimo (máximo) global.
Teorema: Sea : nf una función convexa Todo mínimo (máximo) local de
ella x D es un mínimo (máximo) global.
Demostración:
Sea z D un punto arbitrario en el dominio y x D sea un mínimo (máximo)
local. Luego, 2
,f x f y y D x y (2
,f x f y y D x y ), donde
es una constante real positiva. Consideremos una combinación convexa de
ambas 1y x z ( 0,1 ) que sea cercana, tan cercana que x y .
Dado que por convexidad y D y puesto que x es un mínimo (máximo) local,
entonces se tiene que:
1 1f x f y f x z f x f z
Entonces se tiene que 1 1f x f z f x f z .QED.
Ilustración 2: Intuición detrás de la demostración
1.1 Problema de Programación Lineal
La programación lineal es un caso particular muy importante de la programación
convexa, que ha sido estudiada en forma intensiva en las últimas décadas.
Definición: Función Lineal – Una función : nf es lineal si:
i. f x y f x f y
x
y
z
ING4520 7
ii. f x f x
Lo cual se cumple para , nx y .
Es importante que mencionemos que toda función lineal es posible de ser expresada
como una sumatoria de sus componentes por ciertos coeficientes reales. Es decir
que:
1
nii i
f x c x
¿Son convexas las funciones lineales?, veamos:
Sea : nf una función lineal, sean , nx y y 0,1
1 1f x y f x f y por la primera propiedad de linealidad.
1 1f x y f x f y por la segunda propiedad de linealidad.
1 1f x y f x f y .
Definición: Problema de Programación Lineal (PPL) Convexo – Un problema de
programación convexo.
min
. .
1,...,i i
f x
s a
g x b i m
Es lineal si su función objetivo y sus funciones de restricciones son lineales. Es
decir:
: nf puede ser expresada como 1
nii i
f x c x , y,
: , 1nig i m pueden ser expresadas como
1
ni ijj jg x a x .
Luego el problema queda de la siguiente forma:
ING4520 8
1
1
min
. .
1,...,
nj jj
nij j ij
c x
s a
a x b i m
En términos generales podemos hablar de una taxonomía que queda representada
gráficamente como sigue.
Definición: Forma Estándar de un PPL – Un PPL se dice que está en forma
estándar si está expresado de la siguiente forma:
min
. .
0
c x
s a
Ax b
x
Definición: Forma Canónica de un PPL – Un PPL se dice que está en forma
canónica si está expresado de la siguiente forma:
min
. .
0
c x
s a
Ax b
x
En general nos encontraremos con:
problemas de maximización o minimización
Problemas de Optimización
Dominio Finito Dominio Continuo
Programación Matemática
Optimización Convexa
Programación Lineal
ING4520 9
restricciones =, <=, >=.
Variables positivas, negativas e irrestrictas.
Es de utilidad saber convertir PPL’s que estén sin un formato establecido, al
formato estándar. La idea es introducir variables de holgura en las restricciones de
desigualdad, a modo de convertirlas en restricciones de igualdad. Por su parte,
cuando las variables son irrestrictas o negativas, siempre se pueden transformar a
variables positivas, mediante el uso de variables auxiliares.
Ejemplo: Convertir el siguiente problema a forma estándar.
1 2
1 2
1
2
max 3
. .
2 10
0
z x x
s a
x x
x
x
Primero se introduce una variable de holgura en la restricción, de modo que
1 22 10x x se convierta en 1 2 12 10x x y y tengamos que 1 0y .
Luego se reemplaza la variable irrestricta por dos variables auxiliares, de la
siguiente manera. 1 1 10 0x x x .
Finalmente, la función objetivo simplemente invierte su eje, y así se convierte en
minimización, es decir max minz z .
Con los pasos anteriores el problema se convierte en la forma estándar, y queda
como se muestra a continuación.
1 1 2
1 1 2 1
1 1 2 1
min 3
. .
2 2 10
, , , 0
x x x
s a
x x x y
x x x y
ING4520 10
1.2 Soluciones Básicas Factibles
Consideremos un sistema de ecuaciones lineales Ax b donde la matriz tiene m
filas y n columnas. Recordemos que el rango de una matriz es el número de filas
(columnas) que son linealmente independientes. Para efectos de los PPL que
veremos consideraremos que m n y que el rango de la matriz es m , que
formalmente designaremos como rank A m .
Ejemplo: Considerar el siguiente grupo de ecuaciones:
1 2
1 3
1 2 3
5
2 8
3 5 ...
x x
x x
x x x
El valor que falta puede ser igual o diferente de 23, en el primer caso la tercera
ecuación sería redundante, mientras que en el último caso, el sistema sería
inconsistente.
Ahora, introduzcamos una notación para denominar a las filas y a las columnas de
la matriz A . Denomínese a iA a la i-ésima fila de la matriz A , y a jA a su j-ésima
columna.
Ahora, formalmente veremos los supuestos sobre A. Bueno, supongamos que iA es
linealmente dependiente del resto de las columnas. Así i j jj iA A , entonces
para cualquier solución se tiene que:
i ib A x
i j jj ib A x
i j jb A x
i j jb b
ING4520 11
Así entonces la i-ésima ecuación sería redundante. De otro modo, no existiría
ningún punto que satisfaga el sistema. Ambos casos pueden ser detectados en forma
simple por eliminación gausiana.
En el último ejemplo, si la tercera ecuación fuese igual a 23, entonces ésta es
redundante y se elimina, mientras que en caso contrario el sistema es infactible y
hay que detener el proceso.
Con el supuesto simple anterior, introduzcamos una situación trivial, en la cual
m n . En el caso en que la matriz sea no singular, entonces el sistema tiene
solución única, y esta viene dada por 1x A b . Si 0x entonces es la única
solución del sistema, en caso contrario, el sistema es infactible.
Utilizaremos esta simple observación para caracterizar un cierto conjunto finito de
soluciones factibles, las cuales juegan un rol preponderante en lo que sigue del
curso.
Definición: Conjunto de Soluciones Factibles – Sea : 0,P x x Ax b el
conjunto de lo que denominaremos soluciones factibles.
Una solución del sistema satisface todo el conjunto de ecuaciones de restricciones
j jjx A b . Tomemos un subconjunto 1,...,I n tal que ,jA j I es un conjunto
de columnas linealmente independientes, sabemos que a lo menos hay un conjunto
tal que su rango sea m ( rank A m ). Relacionamos el conjunto 1,...,I n con un
vector x , para el cual para todo j I , 0jx . Debido a la independencia lineal, las
columnas ,jA j I , sabremos que tienen una solución única que satisface Ax b .
Formalmente, si definimos IA como la matriz que es la parte de A que sólo
contiene las columnas de I, entonces se puede definir el vector Ix que sólo toma las
componentes del aludido conjunto, y se tendrá que 1 0I I Tx A b x .
Definición: Solución Básica Factible – Un vector x definido según los lineamientos
anteriores, es una solución básica asociada con I. Si 0x , entonces x P y
entonces se le denomina solución básica factible.
ING4520 12
Ejemplo: Consideremos el siguiente PPL.
min 1,1, 0
. .
Tx
s a
Ax b
Donde:
1 2 0 4
1 2 1 7A b
Primero definamos 1 1, 3I , así:
1
1 0
1 1IA
1 1
2 2
41 0 4 4
01 1 7 7
3
x xx
x x
Siguiente paso es escoger 2 2, 3I , así:
2
2 0
2 1IA
2 2
3 3
02 0 4 2
22 1 7 3
3
x xx
x x
En el contexto anteriormente descrito entonces podemos restringir nuestro análisis
a un conjunto finito de soluciones básicas factibles de un PPL en forma estándar, y
si recorremos todas estas soluciones, entonces podremos encontrar el óptimo. El
algoritmo más trivial es evaluarlas todas, recorrerlas todas y escoger la mínima.
Al final de este algoritmo se habrá encontrado a la mejor solución básica factible.
Ahora bien, consideremos que tendremos !
! !
n nm m n m
iteraciones, lo que por
ejemplo para / 2m n se torna exponencial en n .
ING4520 13
Afirmación: Así, podemos decir que la representación de una solución básica
factible es polinomial en el tamaño de la información de entrada de un PPL.
Definición: Punto Extremo de P – Llamaremos a x P un punto extremo si no es
un punto que esté entre dos puntos , ,y z P x y x z .
Ilustración 3: Algoritmo para encontrar mejor solución básica factible
Ejemplos:
Inicio
Inicializa: z = ∞
A, b, c
¿Es AI no
singular?
¿x=AI b >= 0?
sí
sí
¿cx < z?
z = cx
x* = x
sí
I{1…n} tal que I=m
no
no no
no
ING4520 14
Los puntos extremos en el intervalo 0,1 son 0,1 .
0 es un punto extremo de 0x .
1x son los puntos extremos de 1x .
Los vértices de un polígono, son sus puntos extremos.
Ilustración 4: Ejemplo de los puntos extremos de un polígono que son sus
vértices.
Lema: x es una solución básica factible es un punto extremo.
Demostración: “Parte ”
Supongamos que x es una solución básica factible, y demostraremos que entonces es
un punto extremo.
Si x es una solución básica factible, y que es un punto entre dos puntos.
Si un punto está entre dos puntos, entonces se puede reconstruir como una
combinación convexa de los otros dos puntos.
1 0,1 , ,x y z y z P
Enfocándonos en un conjunto I, tendremos que:
1j j jx y z j I
ING4520 15
0 1j j jx y z j I
Debido a que ,y z P tenemos que , 0j jy z 0j jy z para j I , luego:
1j j iy z B b x j I x y z
Lo anterior conduce a una contradicción, y nos lleva unívocamente a concluir que
x es un punto extremo.
Demostración: “Parte ”
Suponemos que x es un punto extremo y demostraremos que eso implica es una
solución básica factible.
Entonces si x fuere una solución básica factible, esto sucede sólo si : 0jJ j x
corresponde a un conjunto de columnas linealmente independiente. Si este conjunto
no fuere independiente, es directo deducir que x no es una solución básica factible,
y si es independiente entonces por simple álgebra lineal se puede ver que existe una
forma de encontrar un conjunto de columnas I tal que ,I m J I . Así,
claramente x es una solución básica factible que corresponde a la base I.
Asumamos que x no es una solución básica factible. Definamos : 0jJ j x .
Sabemos que x P y que las columnas iA ( 0ix ) son linealmente independientes
sólo si x es una solución básica factible. Por ende las columnas en JA son
linealmente dependientes y así debiese haber un vector v distinto de cero, fuera de
J tal que 0Av . Así se tiene que:
A x v Ax Av Ax b
En otras palabras x v es una solución al sistema Ax b . Para un 0 lo
suficientemente pequeño, tanto 0x v , como 0x v . Por lo que ambas están
en P ( x v P ).
Ahora, puesto que 1 1
2 2y z
x x v x v x es un punto intermedio no es
un punto extremo. Lo que por contradicción QED.
ING4520 16
Afirmación: Si x es una solución básica factible existe un vector c tal que
,c x c y y P .
Ilustración 5: Introduciendo la función objetivo
Demostración:
Si x es solución básica factible, entonces 0,jx j I . Entonces se elige un vector c
tal que 0, 1,j jc j I c j I . Claramente se tiene que 0c x . Si x y ,
entonces 0Iy (de otra manera I Iy x y por ende y x ), además puesto que
y P , luego 0Iy y es más, 0Iy . Por lo anterior se tiene que 0c y c x .
La demostración en el otro sentido es trivial. Si se supone que x no es una solución
básica factible, entonces x será un punto intermedio de otros dos puntos, y por
ende el valor no podrá ser menor que ambos, luego se tendrá la contradicción
buscada.
Ahora recién estamos en condiciones de realizar la siguiente afirmación.
Afirmación: Si un PPL en su forma estándar tiene una solución óptima, entonces
tiene una que es una solución básica factible.
Demostración:
Asumamos que tenemos una solución óptima del problema, y llamémosla *x . Si *x
es una solución básica factible, entonces se demuestra. En otro caso, podríamos
encontrar una solución básica factible a través de un procedimiento iterativo.
*
*
*
0
0
0
0
0
0
1
1
1
x c
AI
ING4520 17
Comenzar una solución inicial 0x .
Definamos 0: 0jJ j x .
Si la columna ,jA j J es linealmente independiente, entonces detenerse:
o x es una solución básica factible.
Sino:
o Escoger un vector , 0 0jv Av v ,
o si 0jx :
Sea k un índice para el cual : 0minj
jk
j vk j
xx
v v
Definir k
k
x
v
Definir 1 0x x v . Con lo cual se puede verificar que:
1 0x x P
1 0kx
1 0jx j J
Repetir el proceso con 1x
Este proceso terminará cuando J sea un conjunto de índices de columnas
independientes de A. Notar que también se puede terminar cuando J sea vacío, en
cuyo caso x es nulo, y el cero es una solución básica factible.
Finalmente, mostramos que la solución básica factible es tan buena como la
solución óptima, y terminamos con la demostración. En efecto, en cada iteración
del procedimiento anteriormente descrito, la función objetivo cambia en v c , si
probamos la siguiente afirmación, concretamos nuestro objetivo.
ING4520 18
Afirmación: 0c v
Demostración:
Asumamos que x es una solución óptima. Luego para 0 lo suficientemente
pequeño x v P .
c x v c x c v
Puesto que 0 , entonces 0c v cambiará el valor de la solución óptima en x.
QED.
Ejemplo: Dado el sistema:
Ax b
1 0 1 2 3
1 1 2 3 5
0 1 1 1 8
A , 9
18
9
b y 0
1
3
4
2
0
x ,
Encontremos una solución básica factible.
Paso 1: 1,2, 3, 4J (sólo el último elemento de 0x es nulo). Las columnas de A
que tienen los índices en J no son linealmente independientes, luego se puede
escoger 1 1 1 0 0T
v tal que 0Av y 5 0v . Luego calculamos , lo cual se
realiza comparando las razones /j jx v para todo 0jv .
1 2 3
1 2 3
1 3 4
1 1 1
x x x
v v v
Luego el mínimo se da en 1j , luego 1 .
ING4520 19
1 0
1 1 0
3 1 2
4 1 1 5
2 0 2
0 0 0
x x v
Paso 2: 2, 3, 4J (el primer y último quedan fuera por ser nulos). Las columnas
de A que siguen los índices de J no son linealmente independientes, así podemos
escoger 0, 1,2, 1, 0T
v tal que 0Av y 1 5, 0v v . Luego se calcula el nuevo
comparando las razones /j jx v para todo 0jv
2 3 4
2 3 4
2 5 2
1 2 1
x x x
v v v
Luego el mínimo se da en 2j y en 4j , luego 2 .
2 1
0 0 0
2 1 0
5 2 2 9
2 1 0
0 0 0
x x v
Ahora tenemos sólo una columna de A, correspondientes a 0jx en 3j . Este
vector es obviamente linealmente independiente, así, la solución será
2 0 0 9 0 0x , la cual es una solución básica factible.
ING4520 20
2 EL MÉTODO SIMPLEX
Hasta el momento hemos visto las definiciones formales requeridas para poder
definir el método Simplex, en particular:
Definimos Solución Básica Factible (SBF).
Demostramos que una SBF y un punto extremo de un poliedro son
equivalentes.
Demostramos que si existe un óptimo para un PPL, entonces existe una
SBF que es un óptimo.
o Con esto se definió un algoritmo de fuerza bruta para encontrar el
óptimo de un PPL.
o Las soluciones que son candidatas a óptimo son aquellas que son
linealmente independientes y existe una combinación no negativa de
columnas que es igual a b.
Finalmente demostramos que siempre existirá un conjunto de costos que
permita que una solución básica factible sea mínima.
En adelante, con la matemática esencial vista anteriormente, definiremos el método
Simplex. Ahora bien, aprovechando que ya poseen conocimientos al respecto, y
tomando en consideración que este segundo capítulo de repaso, haremos una breve
revisión de las diferentes formas en las que se puede abordar el problema.
La idea subyacente en el método Simplex es comenzar desde una solución básica
factible (que como sabemos, es un punto extremo del poliedro de restricciones) del
conjunto de restricciones del problema en forma estándar, y moverse hasta otra
solución básica factible, de tal modo que continuamente decrezca (o crezca en
maximización) el valor de la función objetivo, hasta que se encuentre un mínimo.
Como ya sabemos, basta con enfocarse en las soluciones básicas factibles, puesto
ING4520 21
que entre ellas está el óptimo. Veremos una forma eficiente de “movernos” entre
soluciones básicas factibles para encontrar el mínimo de la función objetivo.
2.1 ¿Qué es Pivotear?
El procedimiento iterativo que esbozamos en la sección anterior para demostrar que
todo PPL tiene una solución básica factible, ya esboza las bases de la definición del
proceso básico de pivote, y consideraremos que este concepto se refiere a la forma
en la cual nos cambiaremos de base, a modo de encontrar una nueva y mejor.
Consideremos un conjunto de ecuaciones lineales.
Ax b
11 1 1 1
21 2
1
n
n
m mn n n
a a x b
a a
a a x b
11 1 12 2 1 1
21 1 22 2 2 2
1 1
n n
n n
m mn n n
a x a x a x b
a x a x a x b
a x a x b
11,...,
nij i jia x b j m
1,...,j jA x b j m
Ponemos algunas de las notaciones más comunes, por si ya se nos ha olvidado que
todas se refieren a lo mismo.
Como ya sabemos, en el espacio n-dimensional de las columnas (variables),
sabremos que este sistema de m ecuaciones debe ser satisfecho por un vector x.
En el caso en que existan menos ecuaciones que variables (m n ) y las ecuaciones
sean linealmente independientes, entonces no habrá una única solución. Sin
ING4520 22
embargo, si se agregan n-m ecuaciones linealmente independientes, entonces
existirá una única solución.
Si el sistema general de ecuaciones antes expuesto es linealmente independiente,
entonces se pueden reemplazar una determinada ecuación por algún múltiplo
distinto de cero o por ella misma, más alguna combinación lineal de las otras
ecuaciones en el sistema. Esto lleva a los bien conocidos (les pido por favor que
repasen en forma somera esta materia por si es que no la recuerdan) métodos
Gausianos de reducción de matrices, en los cuales múltiples ecuaciones son
sistemáticamente restadas de otras para llevarlas una forma triangular o bien
canónica. Así, es bien conocido, y fácil de demostrar, que si el primer conjunto de
m columnas de A es linealmente independiente, entonces el aludido sistema puede
ser convertido a una forma canónica:
1 1, 1 1 1, 2 2 1, 10
2 2, 1 1 2, 2 2 1, 20
, 1 1 , 0
m m m m n n
m m m m n n
m m m m m n n m
x y x y x y x y
x y x y x y x y
x y x y x y
Así, esta base canónica tiene en las primeras m variables a su correspondiente
solución básica (las otras variables las denominaremos no básicas), la
correspondiente solución es:
0 1,...,
0 1,...,i
i
y i mx
i m n
En forma vectorial (equivalente) 0 0x y donde 0y es un vector de dimensión m y
el 0 es un vector nulo de dimensión n-m.
Al correspondiente conjunto de valores de la matriz en forma canónica se le
denomina tableau.
1, 1 1, 2 1, 10
2, 1 2, 2 2, 20
, 1 , 2 , 0
1 0 0
0 1 0
0 0 0
0 0 1
m m n
m m n
m m m m m n m
y y y y
y y y y
y y y y
ING4520 23
La pregunta resuelta por el pivoteo es: Dado un sistema en forma canónica,
suponga que una variable básica se debe tornar no básica, y una variable no básica
se debe tornar básica; ¿Cuál es la nueva forma canónica correspondiente
al nuevo conjunto de variables básicas?
La respuesta es muy simple, supongamos que en el sistema canónico ya descrito
queremos reemplazar la variable básica , 1px p m , por la variable no básica qx .
Lo anterior sólo puede ser realizado si pqy es no nulo, y se realiza dividiendo la
columna p por pqy para extraer un coeficiente para px en la p-ésima ecuación, y
luego restando un adecuado múltiplo de la fila p desde cada una de las otras filas,
con el fin de conseguir un coeficiente nulo para qx en todas las otras ecuaciones. Lo
anterior transforma la q-ésima columna del tableau de modo que es nulo con
excepción de su posición p-ésima, y no afecta a las columnas de las otras variables
básicas. Mediante la denominación de los coeficientes del nuevo sistema en forma
canónica por 'ijy , entonces tendremos que:
'
'
pjij ij iq
pq
pjij
pq
yy y y i p
y
yy
y
El elemento pqy en el sistema original se le denomina pivote.
Ejemplo: Consideremos el siguiente sistema en forma canónica.
1 4 5 6
2 4 5 6
3 4 5 6
5
2 3 3
2 1
x x x x
x x x x
x x x x
Encontremos la solución básica para las variables 4, 5 y 6.
Primero escribamos el tabeau.
ING4520 24
1 2 3 4 5 6
1 0 0 1 1 1 5
0 1 0 2 3 1 3
0 0 1 1 2 1 1
x x x x x x
El elemento enmarcado es nuestro primer pivote, y corresponde a reemplazar en la
base a la variable 1 con la 4.
Lo anterior resulta en que:
1 2 3 4 5 6
1 0 0 0 1 1 5
2 1 0 0 5 3 7
1 0 1 1 3 2 4
x x x x x x
Luego procedemos con intercambiar la variable 2 con la 5.
1 2 3 4 5 6
3 5 1 5 0 1 0 2 5 18 5
2 5 1 5 0 0 1 3 5 7 5
1 5 3 5 1 0 0 1 5 1 5
x x x x x x
Finalmente intercambiamos 6 con 3.
1 2 3 4 5 6
1 1 2 1 0 0 4
1 2 3 0 1 0 2
1 3 5 0 0 1 1
x x x x x x
Desde la forma canónica se obtiene esta nueva solución básica.
0, 0, 0, 4,2,1T
x
2.2 Puntos Extremos Adyacentes
Como ya sabemos, sólo debemos enfocarnos en las soluciones básicas factibles (en
adelante SBF), para encontrar la solución de un sistema en forma estándar.
0
Ax b
x
ING4520 25
Cuando resolvemos un PPL, podemos hacerlo cambiando de base mediante pivoteo,
lo cual reemplaza una variable básica por una no básica. Sin embargo, a pesar de
cambiarnos de una solución a otra, las restricciones de no negatividad de la
variables no necesariamente se cumplen. En la presente sección mostraremos cómo
es posible intercambiar pivotes de modo de preservar la factibilidad.
En una etapa preliminar, y con fines explicativos, asumiremos que las soluciones
básicas factibles son no degeneradas, luego generalizaremos a una versión con
degeneración de variables básicas.
Recuerden que el que una SBF sea degenerada quiere decir que alguno (s) de sus
elementos toma (n) el valor nulo.
Con el supuesto anterior, entonces la pregunta a resolver es ¿cuál es el vector que
debe dejar la base?
Supongamos que tenemos una SBF tal que:
1 2, ,..., , 0,..., 0mx x x x
1 1 ... m mx A x A b
Bajo el supuesto de no degeneración, entonces tendremos que 0, 1,...,ix i m .
Supongamos también que hemos decidido representar explícitamente al vector qA ,
q m . Tendremos la opción de representar dicha columna con respecto a la base
actual.
1 1 ...q q mq mA y A y A
Multiplicando la expresión anterior por un valor mayor 0 y restando de la
ecuación en los términos originales, se tiene que:
1 1 1 ...q m mq m qx y A x y A A b
Luego, para algún 0 se puede construir b como una combinación lineal de a lo
más m+1 vectores. Cuando 0 se tiene la SBF original. En la medida que
ING4520 26
crece alejándose de cero, entonces el coeficiente de qA crece, y es claro que para un
lo suficientemente pequeño, la ecuación anterior da como resultado una solución
factible, pero no básica. Los coeficientes de los otros vectores (columnas de A)
pueden incrementarse o decrecer en forma lineal, en la medida que crece. Si
alguno decrece, entonces se deberá fijar igual al valor que corresponda cuando
uno o más de los coeficientes sea nulo, es decir:
min : 0iiq
iiq
xy
y
En este caso tendremos una nueva SBF, con el vector qA reemplazando al vector
pA , donde p corresponde al índice que minimiza la expresión anterior, es decir:
arg min : 0iiq
iiq
xp y
y
Si el mínimo no es único, entonces la nueva solución será degenerada.
Por otra parte, si ninguno de los coeficientes iqy es positivo, entonces todos los
coeficientes i iqx y se incrementarán o permanecerán constantes en la medida
que crece, y por ende no se podrán obtener nuevas soluciones básicas factibles.
Observemos, sin embargo, que en este caso existen soluciones factibles que tienen
coeficientes arbitrariamente grandes. Esto significa que el conjunto de soluciones
factibles es no acotado, y se constituye en un caso particular, que al igual que la
degeneración es un tema a tener presente en el método Simplex.
En resumen, se ha deducido que dada una SBF y un vector arbitrario qA , o bien
existe una nueva SBF o que tiene a dicha columna en su base, o bien el conjunto
de soluciones factibles es no acotado.
Veamos como los cálculos de esta sección se pueden ver en el tableau. Asumamos
que correspondiente al sistema:
0
Ax b
x
ING4520 27
Se tendrá el tableau:
1 2 1 1
1, 1 1, 2 1, 10
2, 1 2, 2 2, 20
, 1 , 2 , 0
1 0 0
0 1 0
0 0 0
0 0 1
m m m n
m m n
m m n
m m m m m n m
A A A A A A b
y y y y
y y y y
y y y y
Este tableau podría ser el resultado genérico de muchos procesos de pivote, pero en
cualquier evento, éste representa una solución con una base 1... mA A . Si asumimos
que los valores 10 0,..., my y son no negativos, tal que la correspondiente solución
básica 1 10 0,..., m mx y x y es factible. La idea es introducir a la base una columna
qA , q m , y mantener la factibilidad. Con el fin de determinar cual elemento en la
q-ésima columna usar como pivote (y por ende saber cual columna saldrá de la
base), utilizaremos la expresión para determinar y calcularemos las razones
0 , 1,...,i iq i iqx y y y i m y seleccionaremos la menor de entre las no negativas, y
haremos el pivote en el correspondiente iqy .
Ejemplo: Consideremos el siguiente sistema.
1 2 3 4 5 6
1 0 0 2 4 6 4
0 1 0 1 2 3 3
0 0 1 1 2 1 1
A A A A A A b
Cuya base son las columnas 1,2 y 3, y la solución básica factible es 4, 3,1, 0, 0, 0T
x .
Supongamos que seleccionamos a la columna 4 para que ingrese a la base. Así, para
determinar cual elemento en las cuatro columnas es el pivote apropiado, calculamos
las razones correspondientes:
4 3 12, 3, 1
2 1 1
Seleccionamos el menor de entre los no negativos, lo cual nos indica que la columna
2 es elemento de pivote. El nuevo tableau es:
ING4520 28
1 2 3 4 5 6
1 2 0 0 1 2 6 2
1 2 1 0 0 0 0 1
1 2 0 1 0 4 1 3
A A A A A A b
Con su correspondiente SBF 0,1, 3,2, 0, 0T
x .
La presente derivación del método para seleccionar el pivote en una determinada
columna que lleve a una nueva SBF, se basa en una interpretación vectorial de la
ecuación Ax b . Una derivación alternativa puede ser construida considerando un
enfoque con el problema dual, que se basa en las filas del tableau más que en las
columnas.
A modo resumido: Si decidimos pivotear e intercambiar las columnas p y q,
entonces primero dividimos la p-ésima fila por elemento pivote pqy para convertirlo
en 1. Con el fin que la nueva 0py siga siendo positiva, es claro que 0pqy . A
continuación, se extraen múltiplos de la fila p-ésima desde las otras fila, a fin de
obtener ceros en la columna q. En este proceso, los nuevos elementos de la última
columna deben permanecer no negativos (si el pivote fue escogido en forma
adecuada). La operación completa es restar desde la i-ésima fila iq pqy y veces la fila
p. Lo que lleva a una nueva solución que se obtiene directamente desde la última
columna:
' iqi i p
pq
yx x x
y
Para que permanezca no negativa, se debe tener que p pq i iqx y x y , y por ende
nuevamente tenemos que debemos seleccionar p desde el conjunto que hace mínima
la razón i iqx y .
2.3 Determinando una Solución Mínima Factible
En la última sección vimos como pivotear de una solución básica factible a otra (o
determinar que el conjunto de soluciones es no acotado), mediante la selección
ING4520 29
arbitraria de una columna para pivotear, y luego seleccionar apropiadamente el
pivote en dicha columna.
La idea del método simplex es seleccionar la columna tal que el resultado de una
nueva solución básica factible lleve a una mejora en la función objetivo. Mediante
un cálculo elemental, que derivamos en lo que sigue, es posible determinar cual
vector (columna) debe entrar a la base, a modo que la función objetivo sea menor
(o mayor si fuere maximización). Por otro lado, también mediante un simple
cálculo, que derivamos en la sección anterior, es posible entonces determinar cual
vector debe salir de la base, con el objetivo de mantener factibilidad.
Supongamos que tenemos una SBF.
10 0, 0 ,..., , 0,..., 0T T
B mx y y
Cuyo correspondiente tableau es.
1 2 1 1
1, 1 1, 2 1, 10
2, 1 2, 2 2, 20
, 1 , 2 , 0
1 0 0
0 1 0
0 0 0
0 0 1
m m m n
m m n
m m n
m m m m m n m
A A A A A A b
y y y y
y y y y
y y y y
El valor de la función objetivo correspondiente a una solución x cualquiera es:
z c x
En el caso de la SBF el resultado es:
0 B Bz c x
Donde 1,...,B mc c c
A pesar que es natural utilizar la solución básica , 0Bx cuando tenemos un tableau
como el que estamos viendo, cuando tenemos valores arbitrarios de 1,...,m nx x se
puede resolver fácilmente para el resto de las variables:
ING4520 30
1 10 11
0 1
...
nj jj m
nm m mj jj m
x y y x
x y y x
Usando lo anterior, podemos eliminar los elementos del 1 al m de x desde la
fórmula general z c x y se obtiene que:
0 1 1 1 2 2 2 ...m m m m m m n n nz c x z c z x c z x c z x
Donde:
1 1 2 2 ... , 1j j j mj mz y c y c y c m j n
La cual es la relación fundamental para determinar la columna pivote. Un punto
importante que esta ecuación entrega los valores de la función objetivo para todas
las soluciones del sistema, un términos de las variables no básicas. Desde lo cual
podemos determinar si existe alguna ventaja en cambiar la solución básica
mediante la introducción de alguna de las variables no básicas. Por ejemplo, si
j jc z es negativo para algún , 1j m j n , entonces incrementar jx desde cero
hasta algún valor positivo podría hacer bajar el costo total, y por ende llevar a una
mejor solución.
Ahora, derivemos esta relación desde un punto de vista distinto. Sea iy la i-ésima
columna del tableau. Entonces cualquier solución satisface que:
1 1 0 1 1 2 2... ...m m m m m m n nx e x e y x y x y x y
Si multiplicamos (producto punto) por el vector de costos:
01 1
m ni i B j ji j mc x c y z x
Donde j B jz c y . Luego, sumando 1
nj jj mc x a ambos lados:
0 1
nj j jj m
z c x z c z x
ING4520 31
Tal como ya lo habíamos hecho, hemos encontrado una relación que nos permite
mejorar en la función objetivo.
Teorema: Mejora en la SBF – Dada una SBF no degenerada con su
correspondiente valor de función objetivo 0z , suponiendo que para algunos j se
tiene que 0j jc z . Entonces existe una solución básica factible cuyo valor de
función objetivo respectivo es mejor que 0z . Si la columna jA puede ser substituida
por algún vector en la base original para llevar a una nueva SBF, esta nueva
solución tendrá un valor de su función objetivo menor que 0z . Si la columna jA no
puede ser sustituida para llevar a una solución básica factible, entonces el conjunto
de restricciones es no acotado y la función objetivo puede ser arbitrariamente
pequeña ( ).
Demostración: El resultado es una consecuencia inmediata de la discusión previa.
Sea 1,..., , 0,..., 0T
mx x la solución básica factible con función objetivo evaluada 0z y
supongamos que 1 1 0m mc z . Entonces, en cualquier caso, nuevas soluciones
factibles pueden ser construidas de la siguiente forma ' ' '1 1,..., , , 0,..., 0
T
m mx x x con el
valor m+1 mayor que cero. Lo anterior puede ser utilizado para entonces calcular
la variación en la función objetivo, y se tendrá que:
'0 1 1 1 0m m mz z c z x
Por ende 0 0z z . Así, es claro que decidiremos hacer '1mx tan grande como sea
posible. En la medida que '1mx crece, las otras componentes también lo hacen,
permanecen constantes, o decrecen. Así, '1mx puede ser incrementado hasta que
uno de los ' ,ix i m , caso en el cual obtendremos una solución básica factible, o si
ninguno de los ' ,ix i m decrece, '1mx puede ser incrementado sin límites, lo que
indica que estamos en presencia de un conjunto de soluciones factible no acotadas,
y una función objetivo sin cota inferior.
Así, se ve que en cualquier etapa 0j jc z para algún j, es posible hacer jx
positivo y hacer menor la función objetivo. Así, finalmente sólo nos queda resolver,
entre cual de todos los 0j jc z se tiene el óptimo.
ING4520 32
Teorema: Si para alguna solución básica factible 0j jc z para todo j la
solución es óptima.
Demostración: (no).
Debido a que las constantes j jc z juegan un rol central en la metodología que
estamos esbozando, entonces es habitual (y bueno para nuestros propósitos) definir
una notación abreviada para ellos, en la literatura se los llama de muchas formas,
nosotros utilizaremos dos de las más comunes, y lo llamaremos indistintamente
coeficientes de costos reducidos o relativos, o simplemente costos reducidos
(relativos).
j j jr c z
Ejemplo: En particular enfoquémonos en una zanahoria y su paralelo, la
“zanahoria sintética”.
Imaginemos el problema de la dieta que vimos en la parte introductoria, pero
que en vez de los “alimentos” que definimos, tenemos una serie de vegetales,
y variedades de platos artificiales que nos permitirían emular estos vegetales.
En términos del problema, una columna de la matriz A dará el equivalente
nutricional una unidad de un determinado alimento. Supongamos que existe
una base que consista de las primeras m columnas de A, el correspondiente
tableau mostrará como cualquier alimento (o más precisamente, el contenido
nutricional de alguna comida) podría ser construido como una combinación
de comidas en la base. Por ejemplo, si las zanahorias no estuvieren en la
base, utilizando la descripción del tableau, se puede desarrollar una
“zanahoria sintética” cuyo equivalente nutricional es el mismo que la
zanahoria, mediante una combinación apropiada de las comidas que estén en
base.
Con el objetivo de saber si la solución de la base es óptima, consideremos un
alimento que no esté en base, digamos la zanahoria, y determinamos si hacer
ING4520 33
el cambio sería desventajoso o no en términos de la función objetivo. Lo cual
se puede hacer mediante la inspección del costo de las zanahorias, con
respecto al costo de sus pares sintéticas. Específicamente si las zanahorias
son la comida j, entonces su costo será jc y el costo de las zanahorias
sintéticas será 1
mj i ijiz c y .
Si 0j j jr c z , entonces será ventajoso usar zanahorias naturales por
sobre las sintéticas, y por ende debiesen ser “compradas” a la base.
En términos generales los valores jz pueden ser pensados como el precio de una
unidad de columna jA de la correspondiente base. La diferencia entre este precio
artificial (“precio de la zanahoria sintética”) y el precio directo de la columna
determinará cuál de ellas deberá entrar a la base.
2.4 Definición del Procedimiento Completo, Consideraciones
Docentes y Prácticas
Hasta el momento hemos visto todas las definiciones y las metodologías que son
inherentes al método, pero no hemos ordenado todas estas ideas en un todo único,
que nos permita apreciarlo en su dimensión aplicada. En esta sección nos
dedicaremos a resumir todos estos aspectos en una forma didáctica, con el uso
intensivo de ejemplos.
Los estudiantes suelen preguntar por qué es importante estudiar el método Simplex
cuando existen muchos programas de fácil uso, que realizan esta labor. Sin
embargo:
Un buen conocimiento de los detalles del método Simplex y del cómo este
trabaja, hace más fácil apreciar los criterios de optimalidad de optimización
en general y en particular de LP, y de su racionalidad práctica y económica.
Los costos reducidos o relativos obtenidos del método Simplex y el cómo
estos funcionan tienen aplicaciones prácticas que son de utilidad, y que
ING4520 34
juegan roles fundamentales en problemas de operación, planificación, y
tarificación en general.
Muchas aplicaciones involucran modelos con estructuras muy particulares,
en las cuales desde el conocimiento empírico uno podría aproximar sus
soluciones, el tener un conocimiento de este método sirve para hacer el
enlace empírico teórico, validar la intuición (muchas veces sin necesidad de
solucionar el problema completo), y lo principal, logrando convencer a tus
colegas (o hacer prevalecer la posición que estés defendiendo) con
argumentos sólidos.
En muchas situaciones prácticas reales y tangibles, el modelo inicial puede
ser infactible, o pueden producir una solución impracticable. En estos casos
se hace necesario realizar cambios en el modelo; un bueno conocimiento del
método puede ser muy útil para este tipo de análisis.
El método Simplex es uno de los métodos fundamentales de la optimización.
Entenderlo y saber cómo funciona es de utilidad para el entendimiento de
otros algoritmos de optimización.
Debido a que hay muchas alternativas para usar programas computacionales
para resolver PPL, es verdad que podría ser inútil conocer el método con el
cual se solucionan. Pero necesitarán tener una idea muy clara del proceso y
del cómo el algoritmo funciona, si es que desean hacer más que una simple
contribución a la aplicación, entendimiento de los resultados, y posterior
utilización de los mismos en la práctica.
2.4.1 Transformaciones previas del problema
Ya habíamos hablado de las más típicas pero hagamos un sumario de todas las
alternativas:
Paso 1: Transformaciones de variables a modo que tengan una única cota (superior
o inferior, pero no ambas).
ING4520 35
Si hay una variable positiva, déjela sin cambios
Si una variable está acotada inferiormente, hacer un cambio coordenadas
para dicha variable tal que 1 1 1 1 1 1 1 1x l x y l x y l , y reemplace
este valor en todas las restricciones y función objetivo.
Si una variable está acotada superiormente, realizar un cambio de
coordenadas para dicha variable tal que 1 1 1 1 1 1 1 1x u x s u x u s , y
reemplace este valor en todas las restricciones y función objetivo.
Ejercicio Propuesto:
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
max 2 3 2 7
. .
2 6
3 5
2, 7, 0, 0
z x x x x
s a
x x x x
x x x x
x x x x
Paso 2: Transformaciones de variables sujetas a restricciones de cota superior e
inferior.
Supongamos que 2 2 2l x u donde 2 2u l . Primero observamos a la
restricción de cota inferior 2 2 2 2 2 2 2 2x l x y l x y l , y se cambia en
todas las restricciones y función objetivo el valor anterior, lo cual elimina a
la variable del problema. En este proceso entones la restricción de cota
superior se convierte en 2 2 2 2 2 2 2 2x u y l u y u l , entonces se le
aplica el mismo procedimiento que en el paso anterior y se tiene que
2 2 2 2y s u l . Entonces incluir esta restricción de igualdad en el modelo.
Paso 3: Transformar todas las restricciones de desigualdad restantes en igualdades.
Lo cual como ya saben se realiza poniendo variables de holgura.
Paso 4: Poner la función objetivo en forma de mínimo.
Recuerden que min maxz z .
ING4520 36
Paso 5: Eliminar o transformar las variables irrestrictas.
Como ya saben si 1 1 1 1x x x x
2.4.2 ¿Fase I (F1)?
Hasta el momento hemos dicho frases como “… dada una solución básicas factibles
inicial”, “… siempre es posible escribir el problema como columnas básicas y no
básicas”. Pero ¿Cómo llegar a la forma deseada de las columnas en base y el resto
de las columnas? Tal como ya les adelanté en la clase, la forma de transformar un
sistema de ecuaciones en la forma “base & no-base” radica en el método de Gauss-
Jordan para resolución de sistemas lineales. ¿y por qué ha de ser necesario?, la
razón es simple, los problemas pueden venir en cualquier forma, y por ende no
siempre tendrán asegurada la forma estándar para poder aplicar el procedimiento.
No sólo el tema práctico relacionado con el hecho que los problemas pueden tener
cualquier forma es problemático, sino que también el hecho que para algunos tipos
de problemas (flujo en redes por ejemplo), ya la tarea de encontrar una solución
básica factible inicial es no trivial.
Así, para abordar problemas de esta índole se ha definido una etapa adicional a los
aspectos que ya hemos visto, la cual denominaremos indistintamente Fase I o F1.
En términos simples, en esta fase se ignora la función objetivo, y se hace foco en
encontrar una SBF. Si la F1 es exitosa y logra entregar un SBF, se da entonces
comienzo con la segunda parte, o Fase II (F2) que es simplemente lo que ya hemos
visto hasta el momento (SBF + Cambios de base con mejora de objetivo +
criterios de optimo). A la F2 también se le denomina Algoritmo Simplex Primal.
Así, si una SBF puede ser definida por simple inspección, entonces el método
simplex parte en F2.
El método de Gauss – Jordan es un método que debemos recordar desde los tópicos
de álgebra lineal, y permite encontrar una solución básica para el sistema de
ecuaciones Ax b , ignorando el hecho que la variable x es no negativa, debido a
ING4520 37
que no está adecuado para lidiar con restricciones de desigualdad. En 1947 G.
Dantzig mostró que el problema de encontrar una SBF para este sistema de
ecuaciones lineales, puede ser planteado como un PPL, para el cual una SBF está
disponible, mediante la introducción variables adicionales o artificiales. Este nuevo
PPL lo denominaremos como Problema F1. La forma en la cual este problema se
resuelve es con Simplex Primal.
Dado un vector de m variables en un PPL en forma estándar, para determinar si es
o no un vector básico, se necesita determinar si las m correspondientes columnas de
A son l.i. (linealmente independientes), lo cual demorará m pasos de pivote de
Gauss-Jordan. Un conjunto de vectores columna que puede ser fácilmente
identificado para ser linealmente independiente, es el conjunto de columnas de la
matriz identidad. Esa es la razón por la cual el método Simplex es típicamente
inicializado con una SBF unitaria.
A continuación describiremos una forma simple de buscar una SBF unitaria:
En un PPL en su forma estándar, identificamos el vector del lado derecho b,
Si alguno de sus valores es negativo, entonces multiplicar ambos lados de la
correspondiente ecuación por -1 para que el lado derecho (en adelante RHS,
por sus siglas en Inglés Right Hand Side) se torne positivo.
Escriba los coeficientes en un tableau y busque si está presente la i-ésima
base canónica (o vector unitario) de A, hágalo de i=1,…,m.
o Si las encuentra todas, entonces he ahí su SBF inicial, y puede
proceder con la F2.
o Si no las encuentra todas, entonces a lo menos uno de los vectores de
la base canónica no está, entonces se debe construir y resolver el
Problema F1.
Para plantear y resolver el problema F1 asumiremos que los primeros r<m vectores
canónicos son encontrados en la matriz original de coeficientes, y estas son los
ING4520 38
vectores columnas de los elementos 1 a r de las variables. Así, el tableau original
queda así:
1 1
1, 1 1 1
, 1
, 1
1 1
1 0 0
0
0 1 0
0 0 0
1
0, , min
r r n
r n
r r rn r
m r mn m
r r n
j
x x x x z b
a a b
a a b
a a b
c c c c
x j z
Nótese que acabamos introducir el valor , que simplemente representa una
constante inicial en la función objetivo. Tal que en vez que como es habitual
tenemos z cx , ahora consideremos z cx . Los cálculos son equivalentes, pero
es mejor dejarlo por escrito para generalizar.
A fin de encontrar una solución del Problema F1, introduciremos variables
artificiales al mismo, las que llamaremos it , cada una de las cuales se asociará con
el i-ésimo vector unitario en el tableau original para cada 1,...,i r m , a fin de
completar la base unitaria que se tiene de 1,…,r. Noten que si no tienen ningún
vector de la base canónica, entonces deberán generar la matriz identidad completa.
Las variables de 1, ..., nx x les llamaremos las variables del problema original a fin de
distinguirlas de las nuevas variables artificiales. Durante la F1 la función objetivo
original, ahora denominada como función objetivo F2 es ignorada, y se introduce
una nueva fila en la función en el tableau, que estará en la (m+2)-ésima fila, y que
denominaremos fila objetivo de la F1, la cual corresponde a los costos de la función
objetivo de la F1, cuales denotaremos por w, y definiremos según:
Los costos de la F1 para toda variable del problema original será nula, y
para las variables artificiales será 1.
Los costos de la F2 de todas las variables artificiales serán nulos.
ING4520 39
Luego, la función objetivo w de la F1 será la suma de las variables artificiales t, y
puesto que todas ellas son no - negativas, entonces w siempre será positivo. Y por
ende el tableau original de la F1 será definido en la forma que se muestra a
continuación, y corresponde a la simple introducción de las variables t.
1 1 1
1, 1 1 1
, 1
1, 1 1, 1
, 1
1 1
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 1 0
0 0 1 1 0 0 0 1 0
, 0, , , min
r r m r n
r n
r r rn r
r r r n r
m r mn m
r r n
j i
x x t t x x z w
a a b
a a b
a a b
a a b
c c c c
x t i j w
Dado que los elementos de b son mayores que cero, entonces el vector unitario
básico 1 1,..., , ,...,r r mx x t t es factible para el problema de la F1, y corresponde a una
SBF.
1 1 1,..., , ,..., ,..., , 0,..., 0T T
r r m rx x t t b b
Con un valor de la función objetivo de la F1 0 1 ...r mw b b
Alguna solución a la F1 en la cual w se nula, debe tener todas las variables
artificiales nulas, y entonces la parte x debe ser factible para el problema original.
Así, para encontrar una solución del problema original, se tuvo que encontrar una
solución para el problema de la F1. Si el valor mínimo de la F1 fuere mayor que
cero, entonces es imposible encontrar una solución factible en la cual w sea nulo; lo
que implica que el problema original no tiene una solución factible. Ahora, el
problema F1 por si sólo puede ser solucionado con Simplex, puesto que está por
definición en forma estándar.
En el entendido que pasamos desde una zona de infactibilidad, a una de
factibilidad, al momento de resolver el problema de la F1, el valor objetivo de la F1
ING4520 40
w se convierte en un indicador de cuan infactible es el problema. Razón por la cual
al valor de w se le suele llamar medida de infactibilidad.
2.4.3 Fase II
Tal como ya vimos los pasos iterativos del algoritmo Simplex se conocen como
pasos de pivote, o pivoteo, etc. La razón es simple, y es porque involucran al
método Gauss – Jordan.
En un paso de pivote, se intercambia una variable básica con una no básica. La
variable no básica se denomina variable entrante, y la variable básica se denomina
variable saliente. Las cuales se definen por las reglas de entrada y salida que ya
vimos.
La regla para definir la variable entrante se asegura que la función objetivo mejore
o decrezca en valor en el paso de pivote.
La regla para definir la variable saliente se asegura que la nueva solución básica
obtenida sea factible.
Las reglas anteriores, ya las hemos visto, y para que entrenen un poco, les dejo el
siguiente ejemplo: Considere el siguiente tableau en forma canónica para un PPL,
con respecto a las variables básicas 1,…,4.
1 2 3 4 5 6 7 8
1
2
3
4
1 0 0 0 1 1 1 0 0 6
0 1 0 0 2 1 2 1 0 12
0 0 1 0 0 1 3 2 0 3
0 0 0 1 2 1 7 3 0 1
0 0 0 0 3 2 0 2 1 100
SBF x x x x x x x x z b
x
x
x
x
z
¿Qué pasa con el método en este caso?. Analice.
2.4.4 Procedimiento Completo
A continuación se escribe el procedimiento completo en forma estructurada y con
explicaciones para recordar en cada paso.
ING4520 41
Paso 1: Inicialización:
o Paso 1.1. Hacer el RHS no negativo: multiplicar por -1 las
correspondientes restricciones.
o Paso 1.2. Buscar los vectores de la base canónica en el problema: para
cada i=1,..,m, buscar la variable asociada con el i-ésimo vector
unitario en el tableau original; si las hay (si hay más de una, poner
escoger aquella que tenga el menor coeficiente de costo) detectarlas y
definirlas como base.
En este proceso, si se ha encontrado toda la base canónica, defina el
vector de variables básicas. Dado que todos los valores del RHS son
positivos (por construcción) entonces esta base es una SBF. Escriba el
tableau con respecto a las variables básicas y calcule con este vector
los valores de z. y ejecute el Paso 2, cual corresponde a la Fase II.
Si las variables básicas no han sido seleccionadas por completo,
entonces debe ir al Paso 3, cual corresponde a la Fase I antes
definida.
Paso 2… comenzando con un tableau en forma canónica:
o Paso 2.1. Tableau Canónico: En un tableau canónico las columnas
pueden aparecer en cualquier orden (desde izquierda a derecha), por
efectos docentes explicativos, se abordará el problema asumiendo que
la base está de 1 a m.
*** Dibujo en Clase ***
o Paso 2.2. Verificar Óptimo: Si todos los costos reducidos de las
variables no básicas son positivos, entonces la SBF es un óptimo, y el
valor de la solución es el actual calculado, entonces terminar.
ING4520 42
o Paso 2.3. Seleccionando la variable entrante: Si el criterio de óptimo
no se cumple, seleccione una variable no básica, con un costo reducido
negativo como la variable entrante. Llamemos a la columna
correspondiente columna pivote.
o Paso 2.4.a Verificando No Acotamiento: Si la columna pivote no tiene
todos sus valores estrictamente positivos, entonces la función objetivo
es no acotada y por ende no existe una solución finita.
o Paso 2.4.b Cálculo de razón mínima Si la columna pivote tiene al
menos un valor positivo, entonces para todos los valores que lo sean
calcular la razón i isb a e ingresar a la base el que corresponda al
mínimo. Es decir la variable que se define por el mínimo será la
variable saliente, la correspondiente fila se denomina fila pivote.
o Paso 2.5. Paso del pivote para hacer el tableau canónico: Realice el
paso de pivoteo en el tableau canónico original con las
correspondientes filas y columna pivote. En el tableau resultante
reemplace la variable entrante, que lleve al nuevo tableau canónico
con respecto a la nueva base, y comience una nueva iteración.
Paso 3: Construya el problema de Fase I. ya visto
Paso 4: Fase I.
o Paso 4.1 Si encuentra SBF en la cual no hay variables artificiales
involucradas entonces ir a Paso 2.
o Paso 4.2. Si no, entonces el problema es infactible.