UNIVERSIDAD NACIONAL ABIERTA

VICERRECTORADO ACDÉMICO
COORDINACIÓN DE EVALUACIÓN ACADÉMICA

TAREA: METODO SIMPLEX

TRABAJO PRÁCTICO: X

CÓDIGO: 760

FECHA DE ENTREGA AL ESTUDIANTE: 15/12/2011

FECHA DE DEVOLUCIÓN:

NOMBRE DEL ESTUDIANTE: LUIS RAFAEL BRAVO MARCANO

CÉDULA DE IDENTIDAD: 5.397.344

CENTRO LOCAL: MONAGAS

CARRERA: MATEMÁTICA

NÚMERO DE ORIGINALES:

FIRMA DEL ESTUDIANTE:

DIRECCIÓN DE CORREO ELECTRONICO: lbravo0404@[Link]

 INDICE

Pag.
1. INTODUCCION……………………………………………………. 3
2. PROGRAMACION LINEAL………………………………………. 5

3. LINEA DEL TIEMPO SOBRE LA EVOLUCION DE LA

OPTIMIZACION…………………………………………………… 5
4. METODO SIMPLEX………………………………………………. 7
5. INTERPRETACION DEL METODO SIMPLEX…………………. 12
6. SIMPLEX REVISADO…………………………………………….. 13
7. DUAL SIMETRICO Y ASIMETRICO……………………………. 17
8. VENTAJAS DE LA PROGRAMACION DUAL………………….. 19
9. ANALISIS POST OPTIMIZACION………………………………. 21
9.1 Cambio o variación en los coeficientes de la función objetivo. 21
9.2 Modificación en los términos independientes de las restricciones 22
9.3 Variación en los coeficientes técnicos de las restricciones…….. 22
9.4 Adición de nuevas variables……………………………………. 23
9.5 Reducción de nuevas restricciones……………………………… 24
10. PROGRAMACIÓN ENTERA…………………………………….. 24
11. PROBLEMA DE TRANSPORTE…………………………………. 29
12. CONCLUSIONES………………………………………………….. 34
13. REFERENCIAS BIBLIOGRAFICAS……………………………… 36

2
 Introducción.

Un modelo de programación lineal, considera que las variables de decisión tienen un

comportamiento lineal, tanto en la función objetivo, como restricciones del problema.
Consiste en optimizar (minimizar o maximizar) una función lineal, denominada
función objetivo, de tal forma que las variables de dicha función estén sujetas a una
serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.

En este sentido, la programación lineal es una de las herramientas más utilizadas en

la investigación operativa, debido a que en su naturaleza se facilitan los cálculos y en
general permite una buena aproximación de la realidad.

Los modelos matemáticos son, los modelos Deterministas y los modelos Estocásticos.
En los modelos Deterministas se considera que los parámetros asociados al modelo
son conocidos con certeza absoluta, a diferencia de los modelos estocásticos, donde la
totalidad o un subconjunto de los parámetros tienen la distribución de probabilidades.

En la programación lineal existe un procedimiento iterativo que permite ir mejorando

la solución en cada paso, denominado Método Simplex. Donde el proceso concluye
cuando no es posible seguir mejorando dicha solución, asociado a este método, existe
el procedimiento simplex revisado, que requiere una menor cantidad de cálculos, ya
que se realizan cálculos únicamente en los vectores de aquellas variables no-básicas y
registra en memoria lo relativo a las variables básicas.

Todo problema de programación lineal tiene asociado un segundo problema,

conocido como su problema Dual. Ambos están relacionados estrechamente, hasta el
punto de que el modelo de uno puede obtenerse a partir del modelo del otro y la
solución que se obtiene del modelo del primero, proporciona información completa
acerca de la solución óptima del segundo.

3
Programación entera es un término general para los modelos de programación
matemática que presentan condiciones de integridad, condiciones que estipulan que
alguna o todas las variables de decisión deben tener valores enteros. Los modelos de
programación lineal entera, son modelos de programación lineal que tienen las
características adicionales de que algunas de las variables de decisión deben tener
valores enteros.

Para la programación lineal, cuando hay distribución de bienes o servicios, se

plantean problemas de transporte. Con el objeto de minimizar los gastos que se
producen al transportar los artículos desde los orígenes hasta los destinos.

La programación lineal constituye un importante campo de la optimización por varias

razones, muchos problemas prácticos de la investigación de operaciones pueden
plantearse como problemas de programación lineal. Algunos casos especiales de
programación lineal, tales como los problemas de flujo de redes y problemas de flujo
de mercancías se consideraron en el desarrollo de las matemáticas lo suficientemente
importantes como para generar por si mismos mucha investigación sobre algoritmos
especializados en su solución.

4
 Programación lineal.

La programación lineal, es el conjunto de técnicas analíticas para la resolución

de problemas, que tienen por objeto optimizar funciones en las que intervienen un
gran número de variables.

Línea del tiempo sobre la evolución de la optimización.

El Ábaco; El origen remoto de las maquinas de calcular se encuentra en el Ábaco

chino. Artilugio que, aún a pesar de su antigüedad se sigue utilizando en algunos
países asiáticos. De allí se desprende el origen de la informática.

Año 1642. Blaise Pascal. Diseño la primera maquina de calcular, basada en ruedas
dentadas que solo podían sumar y restar.
Año 1694. Leibniz. Matemático. Diseño una maquina ampliando los estudios de
Pascal. Esta calculadora, además de sumar y restar, también
multiplicaba, dividía e incluso extraía raíces cuadradas. Debido a
la falta de tecnología en esa época, la difusión de esta maquina
fue escasa.
Año 1822. Babbage. Estableció los principios de funcionamiento de los ordenadores
electrónicos en un proyecto de maquina denominada “maquina
diferencial” que podía resolver polinomios de hasta 8 términos y
en el año 1833 puso en practica un nuevo trabajo, “la maquina
analítica”, se le puede considerar como un prototipo de los actuales
ordenadores electrónicos.
Año 1768 – 1830. Jean Batiste, Joseph Fourier. Fue el primero en intuir, en una
forma imprecisa, los métodos llamados programación lineal.
Año 1939. Leonid Vitalevich K. Matemático ruso. Publico una extensa monografía
que tituló “Métodos matemáticos de organización y planificación”
en la que por primera vez se hace corresponder a una extensa gama

5
 de problemas, una teoría matemática precisa y bien definida,
llamada hoy en día programación lineal.
Año 1944. John Van Neuman. Propone la idea de “programa interno”, desarrolla un
fundamento teórico para la construcción de un ordenador
electrónico
Año 1945. Entra en funcionamiento el Electronic Numerical Integrator and
Calculator (E.N.I.A.C). Su primera utilización fue para la
construcción de tablas para el cálculo de trayectorias de
proyectiles.
Año 1947. George Dantzing. Desarrollo el método Simples. Procedimiento general
para resolver problemas de programación lineal
Año 1954. G. B. Dantzing y W. Hirs. Realizaron sus trabajos sobre los problemas
de costo fijos.
Año 1956. Noam Chomsky. Inicio el estudio de los lenguajes formales, al crear un
modelo matemático de una gramática. El estudio de las gramáticas
formales es uno de los campos más importantes de la informática
teórica.
Año 1959. Bowman, Wagner. Y 1960. Manne. Los primeros en formular los
modelos de problemas de secuencia.
Año 1940 – 1960. Ralfh Gomory. Surge la programación lineal, siendo el pionero en
investigaciones de la programación entera.
Año 1960. Land And Doig. Desarrollo el primer algoritmo de ramificación y
acotamiento, algoritmo que lleva su nombre y sirve para resolver
problemas enteros, puros y mixtos.
Año 1965. R. D. Young. Se le debe el primer algoritmo de corte, utilizando métodos
primales.
Año 1965. P. Porlier y B. Roy. Realizan la primera formulación de la teoría del
método de ramificación y acotamiento. La cual fue simplificada
por E. Balas en el año 1968, que a la vez más tarde fue ampliada
por L. G. Mitten en el año 1970.
Año 1968. F. Glover. Fundo sus trabajos sobre el algoritmo de métodos primales.

6
Año 1969. Prisker, Walers y Wolf. Plantearon de forma más general los modelos de
problemas de secuencia.
Año 1973. Handy A. Taha. Fundo su trabajo en el algoritmo para el problema de
costo fijo, que originalmente fue presentado por Katla Murty en el
año 1967.

Método Simplex.

Es un procedimiento iterativo que permite ir mejorando la solución a cada

paso, se concluye el proceso cuando no es posible mejorar más dicha solución.
El método algebraico, origina un gran derroche, en razón a que trabaja con
todos los datos de las ecuaciones, para mejorar este aspecto se creo el Método
Simplex, cuya gran virtud es la sencillez, método muy práctico, ya que trabaja con los
coeficientes de la función objetivo y de las restricciones.
El método Simplex se basa en la siguiente propiedad.
Si la función objetivo, no toma su valor máximo en un vértice, entonces existe
una arista que parte desde dicho vértice, a lo largo de la cual la función aumenta.
Para conocer la metodología que se aplica en el Método Simplex se presenta el
siguiente problema:

Ejemplo:

Dos haciendas productoras de café: La hacienda A produce diariamente 2

toneladas de café de alta calidad, 2 toneladas de café de calidad media y 3 toneladas
de café de calidad baja y la hacienda B produce diariamente 1 tonelada de café de
calidad alta, 3 toneladas de café de calidad media y 1 tonelada de café de baja
calidad. Siendo necesario una producción de 18 toneladas de café de alta calidad, 42
toneladas de café de calidad media y 24 toneladas de café de baja calidad. El costo
operacional es de bolívares 3 en la hacienda A y de bolívares 2 en la hacienda B.
¿Cuántos días se deberán trabajar para que el costo sea máximo?.

7
 (Max) Z = 3X + 2Y
Sujeto a: 2X + Y ≤ 18
2X + 3Y ≤ 42
3X + Y ≤ 24
X ≥ 0, Y ≥ 0

Todo problema de programación lineal que se formule de la forma Maximice, con

todas sus restricciones menor o igual que (≤) y con la condición de No negatividad, se
le llama forma estándar ó forma normal.
Aquí se debe conseguir una solución básica factible, empleando las variables de
holgura o artificiales, considerando las siguientes fases:
a) convertir las desigualdades en igualdades.
Se introduce una variable de holgura por cada restricción, para convertirlas en
igualdades, quedando como resultado un sistema de ecuaciones lineales.

2X + Y + h1 = 18
2X + 3Y + h2 = 42
3X + Y + h3 = 24

Siendo las variables de holgura h1, h2 y h3.

b) Se iguala la función objetivo a cero.

Z = 3X + 2Y
Z -3X – 2Y = 0

c) A continuación se escribe la tabla Simplex.

En las columnas se colocan todas las variables del problema y, en las filas, los
coeficientes de las igualdades obtenidas, una fila para cada restricción y la primera
fila con los coeficientes de la función objetivo.

8
 Tabla Simplex inicial
Base Variable de decisión Variable de holgura Valores de solución

X Y h1 h2 h3
Z -3 -2 0 0 0
h1 2 1 1 0 0 18
h2 2 3 0 1 0 42
h3 3 1 0 0 1 24

c) Encontrar la variable de decisión que entre en la base y la variable de holgura

que sale de la base.
. Para escoger la variable de decisión que entra en la base, se toma en cuenta la
primera fila, donde se encuentran los coeficientes de la función objetivo y se escoge
la variable con el coeficiente con signo negativo con mayor valor absoluto, en este
caso, es la variable X de coeficiente igual a -3.
. Si existieran dos o más coeficientes iguales que cumplan con la condición antes
expuesta, se elige uno cualquiera de ellos.
. Si en la primera fila no existiera ningún coeficiente negativo, significa que se ha
alcanzado la solución óptima, lo que va a determinar el final del proceso de
aplicación del Método Simplex, es que en la primera fila no haya elementos
negativos.
. La columna de la variable que entra en la base se llama columna Pivote.
. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada
término de la última columna por el término correspondiente de la columna pivote,
siempre que estos últimos sean mayores que cero. Según el ejemplo: 18/2 = (9), 42/2
= (21) y 24/3 = (8).
. Si existiese algún elemento meno o igual que cero no se realiza dicho cociente. En el
caso de que todos los elementos fuesen menores o iguales a cero, entonces se tendría
una solución no acotada y no se puede continuar.
. El término de la columna pivote que en la división anterior da lugar al menor
cociente positivo, el 3, así 24/3 = (8) es el menor, el cual indica la fila de la variable
de holgura que sale de la base, h3, esta fila se llama fila pivote.

9
. Si al calcular los cocientes, dos o más son iguales, indica que cualquiera de las
variables correspondientes puede salir de la base.
. En la intersección de la fila pivote y la columna pivote se tiene el elemento pivote
operacional.

Iteración 1

Variables de Variables de Valores

Base decisión holgura de solución

X Y h1 h2 h3
Z -3 -2 0 0 0
h1 2 1 1 0 0 18
h2 2 3 0 1 0 42
h3 3 1 0 0 1 24

El nuevos coeficientes de la variable que entra, se obtienen dividiendo todos

los coeficientes de la fila pivote, por el pivote operacional, a el cual hay que
convertirlo en uno.

Variables de Variables de Valores

Base decisión holgura de solución
X Y h1 h2 h3
Z -3 -2 0 0 0
h1 2 1 1 0 0 18
h2 2 3 0 1 0 42
X 1 1/3 0 0 1/3 8
Mediante la reducción gaussiana se hacen cero los restantes términos de la
columna, con lo que se obtienen los nuevos coeficientes de las otras filas incluyendo
los de la función objetivo (z)

Iteración 2
Variables de Variables de Valores

10
 Base decisión holgura de solución
X Y h1 h2 h3
Z 0 -1 0 0 1 24
h1 0 1/3 1 0 -2/3 2
h2 0 7/3 0 1 -2/3 26
h3 1 1/3 0 0 1/3 8

Como en los coeficientes de la primera fila existe uno negativo, (-1), significa que
no hemos llegado a la solución óptima. Se repite el proceso.
 La variable que entra en la base es Y, por ser la variable que tiene como
coeficiente a (-1).
 Para calcular la variable que sale, se dividen los términos de la ultima
columna entre los términos correspondiente de la nueva columna pivote.
Como el menor cociente es 6, se tiene que la variable de holgura que sale es
(h1).
 El elemento que hay que hacer 1, en la intersección de la columna pivote y la
fila pivote es 1/3.

Variables de Variables de Valores

Base decisión holgura de solución
X Y h1 h2 h3
Z 0 -1 0 0 1 24
Y 0 1/3 1 0 -2/3 2
h2 0 7/3 0 1 -2/3 26
X 1 1/3 0 0 1/3 8
Los nuevos coeficientes de Y se obtienen dividiendo todos los coeficientes de
la fila h1 por el pivote operacional, 1/3, el cual hay que convertirlo en 1.

Iteración 3
Variables de Variables de Valores
Base decisión holgura de solución
X Y h1 h2 h3
Z 0 0 3 0 -1 30
Y 0 1 3 0 -2 6
h2 0 0 -7 1 4 12

11
 X 1 0 -1 0 1 6

Como en los elementos de la primera fila hay coeficiente negativo, (-1) significa
que no se tiene la solución óptima, se debe repetir el proceso.
 La variable que entra en la base es h 3, por ser la variable a la cual le
corresponde el coeficiente (-1).
 Para calcular la variable que sale, se dividen los términos de la ultima
columna entre los términos que corresponden a la nueva columna pivote,
como el menor cociente positivo es 3, se tiene que la variable de holgura que
sale es h2.
 El elemento pivote que se debe hacer igual a 1, es el 4 que esta en la
intersección de la columna pivote y la fila pivote.

Iteración 4
Variables de Variables de Valores
Base decisión holgura de solución
X Y h1 h2 h3
Z 0 0 5/4 1/4 0 33
Y 0 1 -1/2 1/2 0 12
H3 0 0 -7/4 1/4 1 3
X 1 0 3/4 -1/4 0 3
Todos los coeficientes de la fila de la función objetivo son positivos, lo que
indica que se ha llegado a la solución óptima donde:
Z = 33 para X = 3 y Y = 12.
La solución óptima, viene dada por el valor de la función Z en la columna de
los valores de solución (33). En la misma columna se puede observa el punto donde
se alcanza, que corresponde a las variables de decisión que entraron en la base, (X,
Y).
Si en el problema de maximización aparecieran como restricciones
inecuaciones de la forma aX + bY ≥ c; se multiplica por (-1) para transformarlas en
inecuaciones de la forma -aX – bY ≤ -c.
Si en lugar de maximizar se tratara de problemas de minimizar se sigue el
mismo proceso, pero cambiando el sentido del criterio, es decir para entrar en la base

12
se elige la variable cuyo valor, en la fila de la función objetivo, sea el mayor de los
positivos y se finalizan las iteraciones cuando todos los coeficientes de la fila de la
función objetivo sean negativo.

Interpretación del método Simplex.

Las sucesivas tablas que se construyen van proporcionando el valor de la
función objetivo en los distintos puntos, ajustándose a la vez, los coeficientes de las
variables iniciales y de holgura.
En la primera iteración permanecen todos los coeficientes iguales, se ha
calculado el valor de la función objetivo en el punto A(0,0) siendo este igual a 0.
Z = 3X + 2Y 3(0) + 2(0) = 0
En la segunda iteración se calcula el valor que corresponde al punto B(8,0).
Z = 3X + 2Y 3(8) + 2(0) = 24
En la tercera iteración se calcula el valor que corresponde al punto C(6,6)
Z = 3X + 2Y 3(6) + 2(6) = 30
Se continua haciendo cálculos hasta llegar al punto D(3,12), donde se halla el
valor máximo de la función objetivo.
Z = 3X + 2Y 3(3) + 3(12) = 33.

Simplex Revisado.

Este método requiere una menor cantidad de cálculos, ya que realiza cálculos
únicamente en los vectores de aquellas variables no básicas y registra en memoria lo
relativo a las variables básicas.
Pasos a seguir.
 Determinar las variables básicas y formar B.
 Obtener B-1.
 Obtener Z – C = Waj – C donde W = CbB-1.
Si Zj – Cj ≥ 0 para un problema de maximización o Z j – Cj ≤ 0 para un
problema de minimización la solución es óptima y es el fin del proceso. Si
esto no se cumple continua el proceso.

13
  Determinar la variable que entra en solución, usando WA – C para toda
variable no básica.
 Se utiliza XBi/YKj para determinar que variable sale de solución. Se actualiza
la columna ak para que esta aporte la columna de la matriz identidad que
aporta la variable saliente.
 Se regresa al principio del proceso.

Base de la solución Lado derecho

W CBXB
B-1 XB

Tabla en el proceso Xk
W CBXB Zk - Ck
B-1 XB1 Y1k
XB2 Y2k
. .
. .
. .
XBm Ymk
Ejemplo:

(Max) Z = 3X + 2Y
Sujeto a: 2X + Y ≤ 18
2X + 3Y ≤ 42
3X + Y ≤ 24
Así:
X Y h1 h2 h3
2 1 1 0 0 18
A= 2 3 0 1 0 C = (3 2 0 0 0) b = 42
3 1 0 0 1 24

Se analiza para todas las variables no básicas.

14
 X Y h1
2 1 1
Zj – Cj = WA – C = (0 0 0) 2 3 0 - (3 2 0) = (-3 -2 0)
3 1 0

Por lo que entra en solución X.

Tabla 1
0 0 0 0 -3
1 0 0 18 h1 2
0 1 0 42 h2 2
0 0 1 24 h3 sale h3 3

Generando en la columna de la variable entrante, la columna necesaria para

formar la matriz identidad, se tiene.

0 0 1 24
1 0 -2/3 2 h1
0 1 -2/3 26 h2
0 0 1/3 8 X

Se analiza para todas las variables no básicas.

Y h1 h2
1 1 0
Zj – Cj = WA – C = (0 0 1) 3 0 1 - (2 0 0) = (-1 0 0)
1 0 0
Por lo que entra en solución la variable Y.

Tabla II
0 0 1 24 -1

15
 1 0 -2/3 2 h1 sale h1 1/3
0 1 -2/3 26 h2 7/3
0 0 1/3 8 X 1/3

Se genera en la columna de la variable entrante la columna necesaria para

formar la matriz identidad, se tiene:

3 0 -1 30
3 0 -2 6 Y
-7 1 4 12 h2
-1 0 1 6 X

Se analiza para todas las variables no básicas.

h1 h2 h3
1 0 0
Zj – Cj = WA – C = (3 0 -1) 0 1 0 - (0 0 0) = (3 0 -1)
0 0 1

Como existe un valor menor que cero se realiza el proceso.

Tabla III
3 0 -1 30 -1
3 0 -2 6 Y -2
-7 1 4 12 h2 sale h2 4
-1 0 1 6 X 1

Así se genera en la columna de la variable entrante la columna necesaria para

formar la matriz identidad, se tiene:

5/4 1/4 0 33

16
 -1/2 1/2 0 12 Y
7/4 1/4 1 3 h2
3/4 -1/4 0 3 X

Analizando para todas las variables no básicas se tiene:

h1 h2 h3
1 0 0
Zj – Cj = WA – C = (5/4 1/4 0) 0 1 0 - (0 0 0) = (5/4 1/4 0)
0 0 1

Como todas las variables son mayores que cero, la solución óptima se ha
alcanzado, entonces la solución óptima es:
Z = 33, para X = 3 y Y = 12.

Dual Simétrico y Asimétrico.

Asociado a cada problema lineal existe otro problema de programación lineal

que se denomina problema dual, que posee propiedades y relaciones notables con
respecto al problema lineal original, problema que para diferenciarse del problema
dual se denomina como problema primal.

Se considera el problema de programación lineal dado por:

Maximizar Z(x) = Cx
Sujeto a: Ax ≤ b
X≥ 0

Que se conoce como el problema primal. Asociado a este se tiene:

Minimizar Zdual = Yb

17
 Sujeto a: YA ≥ C
Y ≥0

A este problema se le denomina problema dual (dual simétrico) y se deriva del

problema primal de acuerdo a las siguientes condiciones:
1.- El problema dual tiene tantas variables como restricciones tiene el problema
primal.
2.- El problema dual tiene tantas restricciones como variables tiene el problema
primal.
3.- Los coeficientes de la función objetivo del problema dual son los términos
independientes de las restricciones del problema primal.
4.- Los términos independientes de las restricciones del problema dual son los
coeficientes de la función objetivo del problema primal.
5.- La matriz de coeficientes técnicos del problema dual es la traspuesta de la matriz
técnica del problema primal.
6.- El sentido de las desigualdades de las restricciones del problema dual y el signo de
las variables del mismo problema, depende de la forma de que tenga el signo de las
variables del problema primal y el sentido de las restricciones del mismo problema.
7.- Si el problema primal es un problema de maximización, el problema dual es un
problema de minimización.
8.- El problema dual de un problema dual es el problema primal original.

Los problemas duales Simétricos son los que se obtienen de un problema

primal en forma canónica y normalizada, es cuando llevan asociadas desigualdades
de la forma menor o igual que (≤) en los problemas de maximización y,
desigualdades mayor o igual que (≥) para los problemas de minimización.
Los restantes tipos de combinaciones del problema, se conocen con el nombre
de duales asimétricos. Por ejemplo:

Maximizar Z(x) = Cx
Sujeto a: Ax = b

18
 X≥0

El problema dual asimétrico es:

Minimizar Zdual = Yb
Sujeto a: YA ≥ C
Y >< 0, es decir, variables libres.

Ventajas de la programación lineal dual.

1) Permite resolver problemas lineales donde el número de restricciones es

mayor que el número de variables. La solución de uno de los problemas
(primal ó dual) nos proporciona de forma automática la solución del otro
problema.
2) La dualidad permite realizar importantes interpretaciones económicas de los
problemas de programación lineal.
3) La dualidad permite generar métodos como el método dual del Simplex, de
gran importancia en el análisis de post optimización y en la programación
lineal paramétrica.
4) Otra ventaja de la dualidad, es la posibilidad de resolver gráficamente
algunos problemas.

Ejemplo:

Maximizar Z = 3X + 2Y
Sujeto a: 2X + Y ≤ 18
2X + 3Y ≤ 42
3X + Y ≤ 24

19
 X≥0 y Y ≥0

Problema dual.
Minimizar Zdual = 18X1 + 42X2 + 24X3
Sujeto a: 2X1 + 2X2 + 3X3 ≥ 3
X1 + 3X2 + X3 ≥ 2
X1 ≥ 0, X2 ≥ 0 y X3 ≥0

Zdual - 18X1 - 42X2 - 24X3

2X1 + 2X2 + 3X3 – h1 = 3
X1 + 3X2 + X3 – h2 = 2

Tabla Simplex inicial.

X1 X2 X3 h1 h2 M M Zdual
Zdual 18 42 24 0 0 0 0 1
h1 2 2 3 -1 0 1 0 0 3
h2 1 3 1 0 -1 0 1 0 2

Primera Iteración
X1 X2 X3 h1 h2 M M Zdual
Zdual 4 0 10 0 14 0 -14 1 28
h1 4/3 0 7/3 -1 2/3 1 -2/3 0 5/3
X2 1/3 1 1/3 0 -1/3 0 1/3 0 2/3

Segunda Iteración
X1 X2 X3 h1 h2 M M Zdual
Zdual -12/7 0 0 30/7 78/7 -30/7 -78/7 1 246/7
X3 4/7 0 1 -3/7 2/7 3/7 -2/7 0 5/7

20
 X2 1/7 1 0 1/7 -3/7 -1/7 3/7 0 3/7

Tercera Iteración
X1 X2 X3 h1 h2 M M Zdual
Zdual 0 0 3 3 12 -3 -12 1 33
X1 1 0 7/4 -3/4 1/2 3/4 -1/2 0 5/4
X2 0 1 -1/4 1/4 -1/2 -1/4 1/2 0 ¼

Por lo tanto, asociado a todo problema de programación lineal existe otro

problema de programación lineal denominado programa dual que tiene importantes
relaciones con el problema original denominado programa primal.
Así los valores del programa son:
X1 = 3
X2 = 12
Z = 33

Análisis de post-optimización.

El análisis de post-optimización consiste en obtener la nueva solución óptima

de un problema lineal, cuando se produce una modificación en alguno de los
parámetros del problema, quedan afectadas las condiciones de optimalidad y de
factibilidad de la solución actual, cuando reproduce una modificación o un cambio
en alguno de los coeficientes del problema, se introduce una nueva variable de
decisión o nuevas restricciones intentando aprovechar la solución óptima del
problema previo

Dentro del análisis de post-optimización se pueden plantear los siguientes

casos que estudiaremos a continuación:
1.- Cambio o variación en los coeficientes de la función objetivo, cj.
2.- Modificación en los términos independientes de las restricciones, bi.
3.- Variación en los coeficientes técnicos de las restricciones, aij.

21
4.- Introducción de nuevas variables.
5.- Adición de nuevas restricciones.

1) CAMBIO O VARIACIÓN EN LOS COEFICIENTES DE LA FUNCIÓN

OBJETIVO, cj

Cambio en un cj de una variable no básica.

Sólo al wj de la variable cj
Así si ck pasa al valor ck’.
Wk = ck - [cb B-1 Pk]
Wk’ = ck’ - [cb B-1 Pk]
2) MODIFICACIÓN EN LOS TÉRMINOS INDEPENDIENTES DE LAS
RESTRICCIONES, bi

Afecta a la condición de factibilidad, es decir, a Xb = B-1·b si se mantiene la

condición de no negatividad de las variables (mayor o igual que cero) la solución
actual (entendida como que las variables básicas son las mismas, y no como valor de
estas variables) sigue siendo óptima.
Los cambios pueden violar esta condición de factibilidad, es decir, que xb
tenga alguna o algunas componentes menores que cero. En este caso, cuando se
rompe la factibilidad del problema, ya no es posible seguir iterando dado que se
mantiene la condición de optimalidad (wi ≤ 0 ∀i) y por tanto no hay criterio de
entrada. La forma de restablecer la factibilidad es por la vial del dual, ya que a una
solución factible primal le corresponde una solución optima dual, por tanto, si la
solución es in factible, la solución del dual deja de ser óptima, y es posible seguir
iterando por la vía del dual hasta encontrar una solución óptima y factible, momento
en el cual es posible establecer la solución correspondiente de primal.

3) VARIACIÓN EN LOS COEFICIENTES TÉCNICOS DE LAS

RESTRICCIONES, aij

22
 Los cambios o modificaciones en los coeficientes técnicos de las restricciones
pueden afectar tanto a la condición de factibilidad como a la de optimalidad, según se
trate de un coeficiente asociado a una variable no básica o a una variable básica.

Los coeficientes técnicos forman parte de los vectores asociados a las

diferentes variables, vectores Pi .Como la repercusión según se trate de una variable
básica o no básica, puede ser muy distinta, estudiaremos los dos casos por separado.

Variación en un coeficiente técnico de una variable no básica.

El cambio en un coeficiente aij afecta al vector Pj, y por tanto al

correspondiente vector transformado en la tabla óptima, dado que P j’ = B-1· Pj. Estos
cambios afectan a los rendimientos indirectos de esta variable y por consiguiente a los
rendimientos marginales, es decir, a la condición de optimalidad: wj = cj - [cb B-1 Pj]
Si wj es menor que cero, la solución actual seguirá siendo optima, y además de
vértice, si la original era así.
Si wj es cero, quiere decir que la solución actual es óptima, pero ya no es
única, sino que existe una solución alternativa a esta.
En el caso de que wj sea positivo la solución actual deja de ser óptima, y deberemos
seguir iterando hasta encontrar una nueva solución óptima.

Variación en un coeficiente técnico de una variable básica.

Los cambios en un vector básico afectan tanto a las condiciones de

optimalidad como a las de factibilidad, dado que el vector Pj pertenece a la matriz B,
y por tanto sus modificaciones pueden afectar sustancialmente al problema actual.
Los cambios pueden ser múltiples, desde hacer que B sea una matriz singular, y por
tanto sin inversa, hasta que las modificaciones de B mantengan la factibilidad y la
optimalidad de la solución actual.
En el caso que B devenga una matriz singular, ya no tenemos procedimiento para
poder continuar, y la alternativa en este caso es reiniciar el problema desde su origen.

23
4) ADICIÓN DE NUEVAS VARIABLES.

La incorporación de una nueva variable al problema original produce un

aumento de la dimensionalidad de la tabla por la vía de las columnas.
Para ver si esa adición altera la solución actualmente óptima, hay que comprobar la
condición de optimalidad de esa variable, ya que el aumento de las columnas no
afecta a la condición de factibilidad de la tabla. La nueva variable añadida xk, llevará
asociado su coeficiente en la función objetivo (ck) y su vector de coeficientes técnicos
( Pk ), y habremos de calcular su rendimiento marginal.
Wk = ck - [cb B-1 Pk ]

Si este rendimiento marginal es menor que cero, la solución actual se

mantiene como óptima. Si se anula el rendimiento marginal significa que hay
soluciones alternativas a la actual pero con el mismo valor de la función objetivo. En
el supuesto que dicho rendimiento marginal sea positivo hemos de introducir la nueva
variable en la tabla como variable básica y seguir iterando hasta encontrar la nueva
solución óptima.

5) REDUCCIÓN DE NUEVAS RESTRICCIONES.

La introducción de una nueva restricción al problema original, conlleva un

aumento de la dimensionalidad de la tabla por la vía de las filas, así como un aumento
del número de variables básicas. Por tanto, el aumento del número de filas no afecta a
la condición de optimalidad pero si a la de factibilidad.
En términos de representación gráfica las nuevas restricciones afectan al
poliedro que forman las restricciones, de manera que éste se puede ver reducido o no
y en consecuencia la actual solución puede dejar de pertenecer al nuevo conjunto
convexo.

24
 Programación Entera.

La programación entera es un término general para los modelos de programación

lineal que presentan condiciones de integridad. Los modelos de programación lineal
entera son modelos de programación lineal que tienen la característica adicional de
que algunas de las variables de decisión deben tener valores enteros. Existen diversas
clasificaciones de esta categoría de modelos.
1) Programas Enteros Puros.
Un modelo entero puro es, como su nombre lo indica, un problema en el que se
exige que todas las variables de decisión tengan valores enteros. En un modelo entero
puro. Sin que las restricciones adicionales sean enteros, seria un problema de
programación lineal.
2) Programas Enteros Mixtos.
Un problema en el que solo se requiere que algunas variables tengan valores
enteros mientras que otras pueden asumir cualquier número no negativo, se llama
programación lineal entera mixta.
3) Programas enteros 0-1
En algunos problemas se restringe el valor de las variables a 0 ó 1. Dichos
problemas se llaman binarios o programas lineales enteros 0-1. Son de particular
interés debido a que se pueden usar las variables 0-1 para representar decisiones
dicotómicas (si ó no). Diversos problemas de asignación, ubicación de plantas, planes
de producción y elaboración de cartera, son de programación lineal entera 0-1.

Existen dos métodos para generar las restricciones especiales que fuercen la solución
óptima del problema, hacia la solución óptima entera deseada.

- Método de ramificación y acotar.

- Método de planos de corte.
En ambos métodos las restricciones agregadas eliminan partes del espacio de
soluciones, pero nunca alguno de los puntos enteros factibles. Desafortunadamente,
ninguno de los dos métodos es efectivo en la solución de problemas de programación

25
lineal entera. No obstante los métodos de ramificar y acotar son mucho mejores en
cuanto al cálculo se refiere, que los métodos de plano de corte. Por esta razón, la
mayoría de los códigos comerciales se basan en el procedimiento de ramificar y
acotar.

Ejemplo.

Un agricultor tiene una parcela de 640 m2 para dedicarla al cultivo de árboles

frutales: naranjo, limonero, manzano y peral. Se pregunta de que forma deberá
repartir la superficie de la parcela entre los tipos de plantas para conseguir el máximo
beneficio sabiendo que:
Cada planta necesita un mínimo de; 16 m 2 para el naranjo, 12m2 para el limonero, 8
m2 para el manzano y 4 m2 para el peral.
Para atender la plantación dispone de 900 horas de trabajo al año; el naranjo necesita
30 horas al año, el limonero 20 horas, el manzano 10 horas y el peral 15 horas.
El agricultor tiene restricciones para el riego a causa de la sequía y le han
asignado 200 m3 de agua anual y tiene la siguiente necesidad de agua al año; 2 m 3 por
cada naranjo, 2 m3 por cada limonero, 1 m3 por cada manzano y 1 m3 por cada peral.
Obtiene beneficios unitarios de 50 Bs. 30 Bs. 25 Bs. Y 20 Bs. Por cada naranjo,
limonero, manzano y peral respectivamente.

Tabla de valores
X1 X2 X3 X4
naranjo limonero manzano peral
2
m 16 12 8 4 640
Días al año 30 20 10 15 900
m3 de agua 2 2 1 1 200
Beneficio 50 30 25 20

Las variables de decisión: X1, X2, X3 y X4.

26
 Las restricciones se expresan como ecuaciones ó inecuaciones de las variables
de decisión, que se deducen de las necesidades de cada árbol, horas de trabajos
anuales y necesidad de riego.

Estándar:

(Max) Z = 50X1 + 30X2 + 25X3 + 20X4

Sujeto a: 16X1 + 12X2 + 8X3 + 4X4 ≤ 640

30X1 + 20X2 + 10X3 + 15X4 ≤ 900
2X1 + 2X2 + X3 + X4 ≤ 200
X1 ≥ 0, X2 ≥ 0, X3 ≥ 0, X4 ≥ 0 para Xi entero.

Tabla simplex inicial.

X1 X2 X3 X4 h1 h2 h3 Z
Z -50 -30 -25 -20 0 0 0 1
h1 16 12 8 4 1 0 0 0 640
h2 30 20 10 15 0 1 0 0 900
h3 2 2 1 1 0 0 1 0 200

La solución básica no es óptima.

Nueva tabla simplex

X1 X2 X3 X4 h1 h2 h3 Z
Z -50 -30 -25 -20 0 0 0 1
h1 16 12 8 4 1 0 0 0 640
h2 30 20 10 15 0 1 0 0 900
h3 2 2 1 1 0 0 1 0 200

27
 Entra a la base la variable X 1 y sale de la base la variable de holgura h 2, se
hace 30, la intersección de la columna pivote y la fila pivote igual a 1.

Primera Iteración
X1 X2 X3 X4 h1 h2 h3 Z
Z 0 10/3 -25/3 5 0 0 0 1 1500
h1 0 4/3 8/3 -4 1 -8/15 0 0 160
X1 1 2/3 1/3 1/2 0 1/30 0 0 30
h3 0 2/3 1/3 0 0 -1/15 1 0 140
Entra a la base la variable X 3 y sale de la base la variable de holgura h 1, se
hace igual a uno 8/3 que es la intersección de la columna pivote y la fila pivote.

Segunda Iteración
X1 X2 X3 X4 h1 h2 h3 Z
Z 0 45/6 0 -45/8 25/8 0 0 1 2000
X3 0 1/2 1 -3/2 3/8 -1/5 0 0 60
X1 1 1/3 0 1 -1/8 1/10 0 0 10
h3 0 1/3 0 1/2 -1/8 0 1 0 120

Entra a la base la variable X 4 y sale de la base la variable X 1, la intersección

entre la columna pivote y la fila pivote es el uno.

Tercera Iteración
X1 X2 X3 X4 h1 h2 h3 Z
Z 0 10 0 0 35/6 3/4 0 1 2075
X3 3/2 1 1 0 -3/16 -1/20 0 0 75
X1 1 1/3 0 1 -1/8 1/10 0 0 10
h3 -1/2 1/3 0 0 -1/6 3/20 1 0 115

Z = 50X1 + 30X2 + 25X3 + 20 X4

28
 Z = 50(0) + 30(0) + 25(75) + 20(10)
Z = 0 + 0 + 1875 + 200
Z = 2075
Z = 2075
X3 = 75
X4 = 10

Para obtener el máximo beneficio debe cultivar 75 plantas de manzano y 10

plantas de peral.
Problema de Transporte.

Este tipo de problema se plantea cuando han de distribuirse bienes o servicios

que se producen en diferentes lugares y que son demandados en diferentes
ubicaciones. El propósito del problema de transporte es minimizar los gastos que se
producen al trasportar los artículos desde los orígenes a los destinos.

Propiedades del problema de transporte.

1. El problema de transporte tiene al menos una solución factible.
2. Si las demandas y disponibilidades son enteras se llaman solución básica
factible de un problema de transporte a una solución entera que verifica las
restricciones de disponibilidad y demanda con a lo sumo m + n -1 variables
distintas de cero (m = nº de orígenes, n = nº de destinos). Este problema de
transporte tiene siempre solución básica factible.
3. Si para un problema de transporte se determina una solución básica factible
inicial, entonces todas las que se obtengan de ella por el método de simplex
son básicas factibles.
4. El problema de transporte es acotado.

Ejemplo:

29
 Una agropecuaria dispone de tres almacenes que deben servir sacos de maíz a
cuatro clientes. La demanda de cada cliente, la capacidad de cada almacén y el costo
de enviar un saco desde cada almacén a cada uno de los clientes se expresa en la
siguiente tabla.

Cliente A Cliente B Cliente C Cliente D Capacidad

Almacén 1 8 6 10 9 35
Almacén 2 9 12 13 7 50
Almacén 3 14 9 16 5 40
Demanda 45 20 30 30
Para la resolución de este problema, se utiliza el método de la Esquina
Noroeste.
Este método nos conduce a una solución factible con, a lo sumo, m + n – 1
variables no negativas.
Hay que aplicar el siguiente algoritmo.
1) Partiendo de la esquina Noroeste de la tabla (esquina superior izquierda) con i
= j = 1 hacer Xij = min(ai,bj) y restar esta cantidad a ai, bj de modo que bien
una fila o una columna de la tabla quede satisfecha. Se elimina esta fila o
columna de la tabla.
2) Si no queda fila o columna parar. En caso contrario aplicar de nuevo el paso
anterior a la tabla resultante.
3) Igualar a cero las Xij que no tengan valor asignado.

Solución del problema:

El problema esta balanceado o equilibrado. Esto significa que la suma de las unidades
producidas es igual a la suma de las unidades demandadas. En este caso la producción
total es 35 + 50 + 40 = 125 sacos y la demanda total es de 45 + 20 + 30 + 30 = 125
sacos. El problema tiene 4 + 3 = 7 restricciones y 12 variables. Llamando X ij la
cantidad enviada desde el almacén i a la ciudad j, el problema consiste en minimizar
los costos de transporte.

(Mimi) Z = 8X11 + 6X12 + 10X13 + 9X14 + 9X21 + 12X22 + 13X23 + 7X24 + 14X31 + 9X32 + 16X33 + 5X34
Sujeto a;

30
 X11 + X12 + X13 + X14 = 35
X21 + X22 + X23 + X24 = 50
X31 + X32 + X33 + X34 = 40
X11 + X21 + X31 = 45
X12 + X22 + X32 = 20
X13 + X23 + X33 = 30
X14 + X24 + X34 =30

Con Xij ≥ 0
Por la forma del sistema el problema dual solo tiene dos incógnitas en cada ecuación.
Este hecho es el que se utiliza para simplificar el método de simplex dando lugar al
algoritmo de transporte.

Tabla inicial ai
Cliente A Cliente B Cliente C Cliente D Capacidad
Almacén 1 8 6 10 9 35
Almacén 2 9 12 13 7 50
Almacén 3 14 9 16 5 40
bj Demanda 45 20 30 30 125

Se comienza el algoritmo seleccionando la celda (1,1) (la esquina noroeste). Se

asigna a X11 el valor 35 = 35,45 . Se resta el valor a a 1 = 35 y a bj = 45, con lo que la
disponibilidad del primer almacén se agota. Los elementos dentro del paréntesis son
los que se van eliminando.
ai
Cliente A Cliente B Cliente C Cliente D Capacidad
Almacén 1 35 - - - (35) 0
Almacén 2 50
Almacén 3 40
bj Demanda (45) 10 20 30 30

Los valores de la solución inicial para las variables de la primera fila quedan ya
decididos y se deja de considerar esta fila en los siguientes pasos del algoritmo.

31
Se asigna a X21 el valor de 10 = 50,10 se resta este valor a a 2 = 50 y a b1 = 10 con lo
que la disponibilidad del segundo almacén se reduce a 40.

ai
Cliente A Cliente B Cliente C Cliente D Capacidad
Almacén 1 35 - - - (35) 0
Almacén 2 10 (50) 40
Almacén 3 40
bj Demanda (45) (10) 20 30 30
0

Se asigna a X22 el valor de 20 = 40,20 se resta este valor a a 2 = 40 y a b2 = 20 con lo

que la disponibilidad del segundo almacén se reduce a 20.
ai
Cliente A Cliente B Cliente C Cliente D Capacidad
Almacén 1 35 - - - (35) 0
Almacén 2 10 20 (50) (40) 20
Almacén 3 40
bj Demanda (45) (10) (20) 0 30 30
0

Se asigna a X23 el valor de 20 = 20,30 se resta este valor a a 2 = 20 y a b3 = 30 con lo

que la disponibilidad de segundo almacén se agota.
ai
Cliente A Cliente B Cliente C Cliente D Capacidad
Almacén 1 35 - - - (35) 0
Almacén 2 10 20 20 (50) (40) (20) 0
Almacén 3 40
bj Demanda (45) (10) (20) 0 (30) 10 30
0

Se asigna a X33 el valor de 10 = 40,10 se resta este valor a a 3 = 40 y a b3 = 10 con lo

que la disponibilidad del tercer almacén se reduce a 30.

32
 ai
Cliente A Cliente B Cliente C Cliente D Capacidad
Almacén 1 35 - - - (35) 0
Almacén 2 10 20 20 - (50) (40) (20) 0
Almacén 3 - - 10 (40) 30
bj Demanda (45) (10) 0 (20) 0 (30) (10) 0 30

Se asigna a X34 el valor de 30 = 30,30 se resta este valor a a 3 = 30 y a b4 = 30 con lo

que la disponibilidad del tercer almacén se agota
ai
Cliente A Cliente B Cliente C Cliente D Capacidad
Almacén 1 35 - - - (35) 0
Almacén 2 10 20 20 - (50) (40) (20) 0
Almacén 3 - - 10 30 (40) (30) 0
bj Demanda (45) (10) 0 (20) 0 (30) (10) 0 (30) 0

Se tiene que X11 = 35, X12 = 0, X13 = 0, X14 = 0, X21 = 10, X22 = 20, X23 = 20, X24 = 0,
X31 = 0, X32 = 0, X33 = 10 y X34 = 30, por lo que para minimizar la función se efectúa
la siguiente operación.
(Mimi) Z = 8X11 + 6X12 + 10X13 + 9X14 + 9X21 + 12X22 + 13X23 + 7X24 + 14X31 + 9X32 + 16X33 + 5X34
Z = 8(35) + 6(0) + 10(0) + 9(0) + 9(10) + 12(20) + 13(20) + 7(0) + 14(0) +
9(0) + 16(10) + 5(30)
Z = 280 + 0 + 0 + 0 + 90 + 240 + 260 + 0 + 0 + 0 + 160 + 150 = 1180
Z = 1180

Conclusiones.

El método simplex es más práctico que el método algebraico, pero para

problemas de unos grandes números de variables y restricciones, fácilmente se vuelve

33
dispendioso por el número de iteraciones y por supuesto demorado para obtener la
solución óptima.

Si se observa que alguna variable que no está en la base, tiene un 0 en la fila Z,

quiere decir que existe otra solución que da el mismo valor óptimo para la función
objetivo. Si estamos ante este caso, estamos ante un problema que admite infinitas
soluciones, todas ellas comprendidas dentro del segmento. Si se desea se puede hacer
otra iteración haciendo entrar en la base a la variable que tiene el 0 en la fila Z, y se
obtendrá otra solución.

Si se intenta buscar la variable que debe abandonar la base, nos encontramos

que toda la columna de la variable entrante tiene todos sus elementos negativos o
nulos, estamos ante un problema que tiene solución ilimitada. No hay valor óptimo
concreto, ya que al aumentar el valor de las variables se aumenta el valor de la
función objetivo, y no viola ninguna restricción.

Cuando existen variables entrantes iguales, se puede optar por cualquiera de

ellas, sin que afecte a la solución final, el inconveniente que presenta es que según
por cual se opte se harán más o menos iteraciones. Se aconseja que se opte a favor de
las variables básicas, ya que son aquellas las que quedarán en la base cuando se
alcance la solución con estos métodos.

Se puede dar el caso degenerado y entrar en ciclos perpetuos. Para evitarlos en

la medida de lo posible, discriminar a favor de las variables básicas haciendo que se
queden en la base. Ante el caso de estar en la primera fase, se optará por sacar en caso
de empate las variables artificiales.

Si el problema original tiene solución, todas las variables artificiales, en la fila

Z deben tener el valor "1". Ya que siempre se realizan los cocientes entre valores no
negativos y mayores que cero.

Conviene no perder de vista la relación entre las variables básica de un

problema primal con las no básicas de su dual. Es decir si una variable de primal es

34
básica, la variable de dual asociada a ella será una variable no básica, y por la misma
razón si una variable de primal es no básica, la correspondiente variable de dual será
una variable básica.

El valor de la función objetivo del problema primal y del problema dual es el

mismo. Conviene notar que si se establecen las relaciones entre las tablas óptimas de
los problemas, se ve que el valor que aparece en las respectivas tablas óptimas es el
mismo pero cambiando de signo, se debe en que en un problema se esta maximizando
y en el otro se esta minimizando, y para este problema de minimización se realiza la
transformación de mínimo a máximo, cambiando el signo de la función, para
comparar los valores no se pueden hacer desde una tabla a otra directamente.

REFERENCIAS BIBLIOGRAFICAS.

35
ORELLANA, Mauricio y TORRES, Ennodio. (1981). Geometría. Universidad
Nacional Abierta. Caracas. UNA, 1997,5.

ABREU, John y otros (1996). Introducción a la teoría de la optimización.

Universidad Nacional Abierta. Caracas. UNA.

Programación lineal. Wikipedia, la enciclopedia libre. Extraído el 12 de enero del

2012. «[Link]
%C3%B3n_lineal&oldid=50719298

Modelado de problemas, método Simplex. Extraído el 15 de enero del 2012.

[Link]

Matemáticas para todos, extraído el 16 de enero del 2012.

[Link]

Programación Lineal en [Link]. Extraído el 16 de enero del 2012.

[Link]

36