Download - Apuntes Programación Lineal v4.4
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 1/33
Programación Lineal
Un problema de Programación lineal en forma
estándar es un problema de la forma:
Min/Max
Sujeto a
. .
. .
. .
donde las son constantes fijas y reales y las
son valores reales a determinar. Se supondrá que
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 2/33
En notación vectorial mas compacta, este problema
puede expresarse como:
Min/Max
Sujeto a
y
aquí es un vector columna n-dimensional, es unvector fila n-dimensional, A es una matriz de mxn y b
es un vector columna m-dimensional. La desigualdad
vectorial quiere decir que las componentes son
positivas o cero.
¿ Cómo convertir a la forma estándar diferentes
formulaciones ?
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 3/33
Por ejemplo
Minimizar
Sujeto a
. .
. .
Agregando variables de holgura a las restricciones:
. .
. .
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 4/33
Variables excedentes
Si se tienen restricciones del tipo :
Se agrega una variable excedente en cada restricción:
Variables libres
Por ejemplo so se desea que sea libre.
Se omite la restricción y se hace el reemplazo
Donde se debe cumplir
y
Luego se sustituye por y y se tiene un
sistema con n+1 variables todas
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 5/33
Ejemplos de problemas de
Programación Lineal
Problema de la dieta: ¿ Como se puede determinar la
dieta más económica que satisfaga las necesidades
nutritivas mínimas básicas para una buena salud?
Se supone que en el mercado hay n alimentos
diferentes y que el i-ésimo se vende al precio por
unidad. Además hay m ingredientes nutritivos básicos
y para recibir una dieta equilibrada, cada individuo
debe recibir al menos unidades del j-ésimo
elemento nutritivo por día. Finalmente se supone
caca unidad del alimento i contiene unidades del
del j-ésimo elemento nutritivo.
Si se denomina al número de unidades del
alimento i de la dieta, el problema consistirá en
seleccionar las para minimizar el costo total
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 6/33
Min/Max
Sujeto a las restricciones nutritivas:
. .
. .
y las restricciones de no negatividad:
Este problema se puede llevar a la forma estándar
restando una variable excedente no negativa del lado
izquierdo de cada una de las m desigualdades lineales.
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 7/33
Problema de transporte:
Las cantidades de un cierto producto se
tienen que enviar desde m lugares y se recibirán en
cantidades en n destinos,
respectivamente. Se asocia con el envío de una
producto desde el origen i hacia el destino j , un costo
de envío por unidad .
Se desea determinar las cantidades a enviar entre
cada par origen destino i=1,2,…,m; j=1,2,…,n de modo
que se satisfagan las necesidades de envío y minimice
el costo total de transporte.
. .
. .
. .
. .
. .
. .
. .
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 8/33
La i -ésima fila de esta matriz define las variables
asociadas al origen i-ésimo, mientras que la j-ésima
columna determina las variables asociadas al j-ésimo
destino.
Asi, resulta el siguiente problema de programación
lineal:
para i=1,2,…,m
para j =1,2,…,n
i=1,2,…m; j=1,2,…,n
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 9/33
Para que las restricciones sean consistentes se debe
dar que:
Este es un problema clásico y que se puede resolver
de diferentes maneras.
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 10/33
Soluciones básicas
Considérese el sistema de igualdades
Donde x es un n-vector, b es un m-vector y A es una
matriz de mxn.
Supóngase que de las n columnas de A se selecciona
un conjunto de m columnas linealmente
independientes (dicho conjunto existe si el rango de A
es m).
Supóngase que se seleccionan las primeras m
columnas de A, y sea B esta matriz de mxm.
Ejemplo 1:
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 11/33
En este caso m=3 y n=3 . La matriz A es :
* + [ ]
Eligiendo una matriz de mxm con las columnas de A,
por ejemplo:
* + y
Definamos un x con los valores restantes
(
, luego:
Dado que la matriz A es de rango completo, es decir
sus columnas son l. i. se tiene:
||
Luego
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 12/33
En el ejemplo se tiene [ ]
Entonces
(
La matriz B se denomina matriz de base. Corresponde
a una base formada por las columnas 1 y 2 de la
matriz A.
Definición:
Dado el conjunto de m ecuaciones
lineales simultáneas de n incógnitas, sea B
cualquier sub-matriz de mxm no singular,
formada por las columnas de A.
Entonces, si todas las n-m componentes de x no
asociadas a columnas de B se igualan a cero, la
solución del conjunto resultante de ecuaciones se
llama solución básica de respecto a la
baseB
.
Las componentes de x asociadas a las columnas
de B se denominan variables básicas.
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 13/33
Hipótesis de rango competo: La matriz A de mxn
tiene
y las m filas de A son linealmente
independientes.
Definición: Si una, o más variables básicas de una
solución básica es igual a cero, se dice que es una
solución básica degenerada.
Definición:
Un vector x que satisfaga { , } se
dice que es factible para estas restricciones.
Una solución factible para { , } que también sea básica, se denomina
solución factible básica.
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 14/33
Teorema fundamental de la
programación lineal
Dado el problema de programación lineal en
forma estándar
Max/min
Sujeto a
Dado en problema de programación lineal de la forma
anterior, donde A es una matriz de mxn de rango m,
1) si hay una solución factible, hay una solución
factible básica;
2) si hay una solución factible optimal, hay una
solución factible básica optimal.
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 15/33
Este teorema reduce la tarea de resolver un problema
de programación lineal a la búsqueda entre
soluciones factibles básicas.
Para un problemas con n variables y m restricciones
hay a lo sumo:
)
(
soluciones básicas.
Así, el teorema fundamental produce una técnica debúsqueda finita que deriva en el procedimiento
simplex.
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 16/33
Relaciones con la convexidad
Definición: Un punto x de un conjunto convexo C se
denomina punto extremo de C si no hay dos puntos
distintos y en C, tales que
(
Para algún
Teorema: (Equivalencia de puntos extremos y
soluciones básicas)
Sea A una matriz mxn de rango m y b un m-vector.
Sea K el polítopo convexo formado por los n-vectores
x que satisfacen
Un vector x es un punto extremo de K, si y solo si, exes una solución factible básica del sistema anterior.
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 17/33
El método simplex
Pivotes
Un sistema está en forma canónica cuando:
En cada ecuación hay una sola variable
básica.
Una variable básica se encuentra en solo una
ecuación.
Ejemplo 2:
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 18/33
Supongamos que queremos poner como
variables básicas. Se construye la tabla de
coeficientes:
Tabla 1: Tabla inicial ejemplo 2
B
1 0 0 1 1 -1 5
0 1 0 2 -3 1 3
0 0 1 -1 2 -1 -1
Primero hacemos entrar a la base para sustituirla
por . Para ello pivotamos en , es decir
esta será la celda pivote. Por lo tanto debe contener
un uno en la posición (
y ceros en las otras
celdas de la columna. Está hecho.
Para poner un cero en construimos una fila
auxiliar, multiplicando la fila pivote por 2
B
2 0 0 2 2 -2 10
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 19/33
Luego restamos la fila 2 menos la fila pivote y queda
Tabla 2: Tabla intermedia como variable basica
B
1 0 0 1 1 -1 5
-2 1 0 0 -5 3 -7
0 0 1 -1 2 -1 -1
Ahora debemos poner cero en la celda . Para ello
usamos la fila pivote sumando a la fila 3 y queda así.
Tabla 3: ; ; como variables básicas
B
1 0 0 1 1 -1 5
-2 1 0 0 -5 3 -7
1 0 1 0 3 -2 4
Luego se tiene la variable en forma canónica y
ya no es variable básica.
La siguiente pivotización es permutar por . Para
ello el pivote es . Debemos poner un uno es
esa posición, lo hacemos dividiendo la fila por -5.
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 20/33
Tabla 4: Tabla intermedia
B
1 0 0 1 1 -1 5-2/-5 1/-5 0 0 -5/-5 3/-5 -7/-5
1 0 1 0 3 -2 4
Para poner un cero en restamos fila 1 con fila 2 y
para poner un cero en
multiplicamos la fila pivote
por 3 y restamos con la fila 3 y queda:
Tabla 5: ; ; como variables básicas
B
3/5 1/5 0 1 0 -2/5 18/52/5 -1/5 0 0 1 -3/5 7/5
-1/5 3/5 1 0 0 -1/5 -1/5
Finalmente permutamos con como variable
básica. Dado que
está como variable básica en la
ecuación de la fila 3 la celda pivote es . Lo
primero es poner un uno en esa celda, lo que
hacemos dividiendo toda la fila por -1/5.
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 21/33
Tabla 6: tabla intermedia
B
3/5 1/5 0 1 0 -2/5 18/5
2/5 -1/5 0 0 1 -3/5 7/5
1 -1/3 -5 0 0 1 -1
Luego ponemos un cero en las filas y , usandooperaciones fila columna como las anteriores. Se llega
a:
Tabla 7: ; como variables básicas
B
1 -1 -2 1 0 0 41 -2 -3 0 1 0 2
1 -3 -5 0 0 1 1
De esta última forma canónica resulta la nueva
solución básica:
= 4 ; ; .
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 22/33
Recordemos que las variables que no están en forma
canónica, son no básicas y por lo tanto son cero.
Luego:
; ;
Suposición de no degeneración:
Toda solución factible básica de
, es
una solución factible básica no degenerada.
Determinación del vector que deja la base:
Supóngase que se tiene la solución factible básica
(
Que cumplen
Según la suposición de no degeneración
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 23/33
El sistema corresponde a una tabla de
la siguiente forma
Tabla 8 : Una tabla en forma canónica
… … b
1 0 0 0 …
0 1 0 0 …
0 0 1 . . . . .. . . . . . . .
. . . . . . . .
. . . . . . . .
0 0 . 1 …
Esta tabla representa una solución con base
…
Se supone que , , … , son no negativos.,
de modo que la solución básica correspondiente a
; ; …;
Es factible.
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 24/33
Se quiere incorporar a la base la variable , ,
ya que no está en la base y mantener la
factibilidad.
Para determinar el elemento de la q-ésima columna
que se va a utilizar como pivote, se calculan las
razones:
Se elige el menor cuociente no negativo y se pivota
sobre .
El algoritmo simplex pude resumirse en los siguientes
pasos:
1.- Se forma una tabla como la de la figura 8,
correspondiente a una solución factible básica. Los
coeficientes de costo relativo se pueden hallar
reducción de filas.
2.- Si todos los se para; la solución factible es
optimal.
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 25/33
3.- Se selecciona un q tal que para definir que
variable no básica se convertirá en básica.
4.- Se calculan las razones
para ,
Si ningún , se para, el problema no está
acotado. De no ser así, se selecciona p como el índice i
correspondiente a la razón mínima.5.- Se pivota sobre el pq - ésimo elemento,
actualizando todas las filas, incluida la última.
Se vuelve al paso 1.
Ejemplo 3:
Maximizar
Sujeto a
,
Se convierte el problema a minimización
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 26/33
Y se agrega la función objetivo en una fila adicional
Tabla 9: Tabla simplicial inicial ejemplo 3
B
2 1 1 1 0 0 2
1 2 3 0 1 0 5
2 2 1 0 0 1 6
-3 -1 -3 0 0 0 0
Los tres pivotes posibles están circundados en la
tabla, por simplicidad de cálculos se elige
Tabla 10: 1° iteración
b
2 1 1 1 0 0 2
-3 0 1 -2 1 0 1
-2 0 -1 -2 0 1 2
-1 0 -2 1 0 0 2
Se elige para pivotar, queda
1
1
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 27/33
Tabla 11: 2° iteración
b
5 1 0 3 -1 0 1-3 0 1 -2 1 0 1
-5 0 0 -4 1 1 3
-7 0 0 -3 2 0 4
Se elige para pivotar
Tabla 12: 3° iteración
b
1 1/5 0 3/5 -1/5 0 1/5
0 3/5 1 -1/5 2/5 0 8/5
0 1 0 -1 0 1 4
0 7/5 0 6/5 3/5 0 27/5
Como la última fila tiene elementos no negativos, se
deduce que la solución es óptima. Por lo tanto
Es la solución óptima con un valor correspondiente a
la función objetivo (negativa) de
5
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 28/33
Variables artificiales
Cuando se tiene un problema de la forma
(1)
No siempre es evidente disponer de una solución
factible inicial. Un método es el siguiente
Minimizar
∑ (2)
Sujeto a
,
Donde
( es un vector de variables
artificiales.
Si el sistema (1) tiene una solución factible entonces
el sistema (2) tiene valor mínimo cero.
El sistema (2) es un sistema de programación lineal en
si mismo, en las variables x e y .Y ya está en formacanónica con la solución factible básica
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 29/33
Ejemplo 4:
Hállese una solución factible básica a
, ,
Se introducen las variables artificiales ,
Y la función objetivo
Se resuelve el problema
Min
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 30/33
La tabla inicial es
Tabla 13: Tabla inicial ejemplo 4 primera parte
b
2 1 2 1 0 4
3 3 1 0 1 3
0 0 0 1 1 0
Aquí las variables básicas no están en forma canónicaTabla 13: Tabla simplicial ejemplo 4 primera parte
b
2 1 2 1 0 4
3 3 1 0 1 3
-5 -4 -3 0 0 -7
Pivotando sobre la columna que tiene el coeficiente
más negativo de la función objetivo (
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 31/33
Tabla 14: tabla intermedia
b
0 -1 4/3 1 -2/3 21 1 1/3 0 1/3 1
0 1 -4/3 0 5/3 -2
Aquí solo hay una elección para pivotar
Tabla 15: tabla optimal primera parte b
0 -3/4 1 3/4 -1/2 3/2
1 5/4 0 -1/4 ½ 1/2
0 0 0 1 1 0
Las dos variables artificiales han salido de la base,
reduciendo el valor de la función objetivo a cero.
La solución factible básica al problema original.
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 32/33
Problema
Min
Sujeto a
Usemos como solución factible básica Parente, por
ello usemos la del problema anterior
Tabla 16: Tabla inicial segunda parte
b0 -3/4 1 3/2
1 5/4 0 1/2
4 1 1 0
Transformando de modo que las variables básicas
estén en forma canónica, se tiene
8/18/2019 Apuntes Programación Lineal v4.4
http://slidepdf.com/reader/full/apuntes-programacion-lineal-v44 33/33
Tabla 17: 1° iteración
B
0 -3/4 1 3/21 5/4 0 1/2
0 -13/4 0 -7/2
Ingresa a la base ya que tiene
Tabla 18: Tabla óptima
b
3/5 0 1 9/5
4/5 1 0 2/5
13/5 0 0 -11/5
De aquí la solución óptima es
=9/5