Programacion Lineal

Vista previa del material en texto

Programación 
lineal 
 
Introducción 
a la 
Christiam Huertas Ramírez 
http://www.xhuertas.blogspot.com/
Orígenes de la PL 
En los siglos XVII y XVIII, grandes matemáticos como Newton, 
Leibnitz, Bernoulli y, sobre todo, Lagrange, se ocuparon de 
obtener máximos y mínimos condicionados de determinadas 
funciones. 
Posteriormente el matemático 
francés Fourier (1768-1830) fue 
el primero en intuir, aunque de 
forma imprecisa, los métodos de 
lo que actualmente llamamos 
programación lineal. 
Orígenes de la PL 
El matemático Gaspar Monge (1746-
1818), también se interesó por 
problemas de este género. 
En el año 1939, el matemático ruso 
Kantarovitch publica una extensa 
monografía titulada Métodos matemáticos de 
organización y planificación de la producción 
en la que por primera vez se hace 
corresponder a una extensa gama de 
problemas; una teoría matemática precisa y 
bien definida llamada, hoy en día, 
programación lineal. 
Orígenes de la PL 
En 1941-1942 se formula por primera 
vez el problema de transporte, 
estudiado independientemente por 
Koopmans y Kantarovitch, razón por 
la cual se suele conocer con el 
nombre de problema de Koopmans-
Kantarovitch. 
Tres años más tarde, G. Stigler 
plantea otro problema particular 
conocido con el nombre de régimen 
alimenticio optimal. 
Orígenes de la PL 
En 1947 Dantzig formula en 
términos matemáticos, el 
enunciado estándar al que 
cabe reducir todo problema 
de programación lineal. 
Una de las primeras 
aplicaciones de los estudios 
del grupo SCOOP fue el 
puente aéreo de Berlín. 
Dantzig, junto con una serie 
de investigadores del United 
States Departament of Air 
Force, formarían el grupo que 
dio en denominarse SCOOP 
(Scientific Computation of 
Optimum Programs). 
Puente aéreo de Berlín 
Programación lineal 
Utilidad de la PL 
1 
• Estudio de mercados. 
2 
• Planificación de la producción. 
3 
• Planificación de horarios. 
 
4 
 
• El problema de transporte. 
 
5 
 
• El problema de la dieta, etc. 
Método de la PL 
Abstracción 
R
e
a
li
d
a
d
 
M
o
d
e
lo
 m
a
te
m
á
tic
o
 
D
e
c
is
io
n
e
s 
 Re
su
lta
d
o
s 
A
n
á
lis
is
 
In
tu
ic
ió
n
 
Interpretación 
Números reales 
Números reales 
Números racionales Números irracionales 
No enteros Enteros 
Enteros negativos Cero Enteros positivos 
ℝ 
La recta numérica 
El conjunto ℝ de los números reales puede ponerse en 
correspondencia uno-a-uno con el conjunto de los puntos de una 
línea recta. 
En consecuencia, podemos imaginar o representar a los números 
reales como los puntos de una recta horizontal llamada recta 
numérica o recta de coordenadas. 
𝟎 
Números positivos Números negativos 
1 2 3 
𝜋 −𝜋 
−∞ +∞ −1 −2 −3 
−
1
2
 
2 
El cero no es positivo 
ni negativo 
Plano cartesiano 
Un sistema coordenado rectangular se forma con dos rectas 
numéricas perpendiculares que se cruzan en el punto 
correspondiente al número 0 en cada línea. 
𝑿 
𝒀 
Primer 
cuadrante 
Segundo 
cuadrante 
Cuarto 
cuadrante 
Tercer 
cuadrante 
𝑥 
𝑦 
(𝑥; 𝑦) 
𝟎 
Línea recta 
La noción de una línea recta juega un papel importante en las 
matemáticas. Hay tres tipos de rectas en el plano 𝑋𝑌: 
Rectas 
horizontales 
Rectas 
verticales 
Rectas 
oblicuas 
𝑦 = 𝑐 𝑥 = 𝑐 𝑦 = 𝑎𝑥 + 𝑏, 𝑎 ≠ 0 
𝑐 
𝑐 
𝑏 
−
𝑏
𝑎
 
Ejemplos 
Determine la gráfica de las siguientes rectas. 
𝑦 = 3, 𝑥 = −2 y 𝑦 = 𝑥 (identidad). 
Recta 
horizontal 
Recta 
vertical 
Recta 
oblicua 
𝑦 = 3 𝑥 = −2 𝑦 = 𝑥 
3 
−2 2 
2 
3 
3 
𝟒𝟓𝐨 
Aplicaciones 
Halle el área de la región encerrada por las rectas 𝑦 = 3, 𝑥 = 5 y 
los ejes coordenados. 
𝑦 = 3 
𝑥 = 5 
𝟓 𝑢 
𝟑 𝑢 𝑅 
𝐴 𝑅 = 𝑏 × 𝑕 = 5 × 3 = 15 𝑢
2 
Aplicaciones 
Determine los vértices de la región limitada por las rectas 
𝑦 = 2, 𝑦 = 4, 𝑦 = 𝑥 y 𝑥 = 5. 
𝑦 = 2 
𝑦 = 4 
𝑦 = 𝑥 𝑥 = 5 
𝐴 𝐵 
𝐶 
𝐷 
(𝟐; 𝟐) (𝟓; 𝟐) 
(𝟓; 𝟒) (𝟒; 𝟒) 
Los vértices son los puntos: 2; 2 , 5; 2 , 5; 4 , (4; 4) 
Aplicaciones 
¿Cuantos pares ordenados de componentes enteros pertenecen a 
la región encerrada por las rectas 𝑦 = 𝑥, 𝑦 = 1, 𝑦 = 4 y 𝑥 = 8? 
𝑦 = 𝑥 
𝑦 = 1 
𝑦 = 4 
𝑥 = 8 
Existen 26 pares ordenados de componentes enteros. 
Función afín lineal 
de dos variables 
Son de la forma: 𝑓 𝑥;𝑦 = 𝑎𝑥 + 𝑏𝑦 + 𝑐 
Lo podemos evaluar para cualquier par de números (𝑥; 𝑦) ∈ ℝ2 (es 
decir, para cualquier punto del plano cartesiano) 
Ejemplo 1. 
Si 𝑓 𝑥;𝑦 = 3𝑥 + 2𝑦 + 1, entonces: 
Ejemplo 2. 
Si 𝑔(𝑥;𝑦) = 5𝑥 − 4𝑦 + 10, entonces: 
𝑓 1;1 = 
𝑓 2;3 = 
𝑓 10;20 = 
𝑔 1;2 = 
𝑔 𝑔 1;3 ;𝑔 2;4 = 
3 1 + 2 1 + 1 = 6 
3 2 + 2 3 + 1 = 13 
3 10 + 2 20 + 1 = 71 
5 1 − 4 2 + 10 = 7 
𝑔 3;4 = 5 3 − 4 4 + 10 = 9 
Aplicación 
Halle el mayor valor de la expresión 𝑓 𝑥;𝑦 = 𝑥 + 𝑦 si se sabe que 
𝑥; 𝑦 tiene componentes enteras y pertenece a la región limitada por 
las rectas 𝑦 = 1, 𝑦 = 3, 𝑥 = 1 y 𝑥 = 4. 
𝑓 1;1 = 1 + 1 = 2 
(𝟏; 𝟏) 
(𝟏; 𝟐) 
(𝟏; 𝟑) 
(𝟐; 𝟏) 
(𝟐; 𝟐) 
(𝟐; 𝟑) (𝟑; 𝟑) 
(𝟑; 𝟏) 
(𝟑; 𝟐) 
(𝟒; 𝟏) 
(𝟒; 𝟐) 
(𝟒; 𝟑) 
𝑓 1;2 = 1 + 2 = 3 
𝑓 1;3 = 1 + 3 = 4 
𝑓 2,1 = 2 + 1 = 3 
𝑓 2;2 = 2 + 2 = 4 
𝑓 2;3 = 2 + 3 = 5 
𝑓 3;1 = 3 + 1 = 4 
𝑓 3;2 = 3 + 2 = 5 
𝑓 3;3 = 3 + 3 = 6 
𝑓 4;1 = 4 + 1 = 5 
𝑓 4;2 = 4 + 2 = 6 
𝑓 4;3 = 4 + 3 = 7 
Vemos que: 
Máximo 
Mínimo 
Aplicación 
Halle el mayor valor de la expresión 𝑓 𝑥;𝑦 = 3𝑥 + 2𝑦 si se sabe que 
𝑥; 𝑦 tiene componentes enteras y pertenece a la región limitada por 
las rectas 𝑦 = 1, 𝑦 = 2, 𝑦 = 𝑥 y 𝑥 = 4. 
(𝟐; 𝟐) 
(𝟏; 𝟏) (𝟐; 𝟏) (𝟑; 𝟏) 
(𝟑; 𝟐) (𝟒; 𝟐) 
(𝟒; 𝟏) 
𝑓 1;1 = 3(1) + 2(1) = 5 
Vemos que: 
𝑓 2;1 = 3(2) + 2(1) = 8 
𝑓 3;1 = 3(3) + 2(1) = 11 
𝑓 4;1 = 3(4) + 2(1) = 14 
𝑓 4;2 = 3(4) + 2(2) = 16 
𝑓 3;2 = 3(3) + 2(2) = 13 
𝑓 2;2 = 3(2) + 2(2) = 10 
∴ El mayor valor de 𝑓 es 16 y el menor valor es 5. 
Inecuaciones en el plano 
Una inecuación lineal en dos variables en el plano viene dada por 
una desigualdad de la forma: 
𝑎𝑥 + 𝑏𝑦 + 𝑐 ≤ 0 ó 𝑎𝑥 + 𝑏𝑦 + 𝑐 < 0 
y la solución corresponde a un semiplano cuya frontera es una 
línea recta. 
𝑎𝑥 + 𝑏𝑦 + 𝑐 ≥ 0 ó 𝑎𝑥 + 𝑏𝑦 + 𝑐 > 0 
Semiplano inferior 
Semiplano superior 
𝑎, 𝑏, 𝑐 ∈ ℝ 
Inecuaciones en el plano 
Para graficar una inecuación lineal de dos variables se siguen los 
siguientes pasos: 
Se grafica la frontera: 𝒂𝒙 + 𝒃𝒚 + 𝒄 = 𝟎. 
(para cualquiera de los cuatro casos) 1 
Se elige un punto de prueba. 
(Un punto cualquiera que no este sobre la recta). 2 
Se sombrea la región apropiada. 3 
Por ser una línea recta, 
bastará buscar dos puntos 
de paso. Se recomienda: 
𝑥 𝑦 Pero Ud. puede 
elegir cualquier valor 
para 𝑥 o para 𝑦. 
Se dibuja continua si la desigualdad involucra ≤ o ≥. 
Se dibuja punteada si la desigualdad involucra < o >. 
Se recomienda el punto (0;0). 
La región que incluya al punto de prueba si este la satisface. 
? 
? 
0 
0 
Inecuaciones en el plano 
Ejemplo. Represente las soluciones de la inecuación 𝑥 + 𝑦 ≥ 1. 
𝑥 + 𝑦 = 1 → 𝑦 = 1 − 𝑥 
Se traza la gráfica de la recta 
𝑥 𝑦 
Elegimos como punto de 
prueba al origen: (0;0). 
¿ 0 + 0 ≥ 1 ? 
0 ≥ 1 
Luego, el conjunto solución 
incluye todos los puntos al 
otro lado de la recta. 
0 
0 1 
1 
Falso 
Conjunto convexo 
Se dice que 𝐶 es un conjunto convexo si todo segmento rectilíneo 
que une dos puntos cualesquiera de 𝐶 está también contenido en 𝐶, 
esto es: 
∀𝑥1, 𝑥2 ∈ 𝐶; ∀𝜆 ∈ 0; 1 ∶ 𝜆𝑥1 + (1 − 𝜆)𝑥2 ∈ 𝐶 
Conjunto convexo Conjunto no convexo 
Polígono convexo. Un polígono se dice convexo si todos sus 
ángulos interiores miden menos de 180°. 
Sistemas de 
inecuaciones lineales 
Un sistema de inecuaciones lineales en el plano viene dado por 
varias desigualdades del tipo: 
 
𝑎1𝑥 + 𝑏1𝑦 ≤ 𝑐1
𝑎2𝑥 + 𝑏2𝑦 ≤ 𝑐2
 ⋮ ⋮
𝑎𝑛𝑥 + 𝑏𝑛𝑦 ≤ 𝑐𝑛
 
Y lasolución, si existe, corresponde a una región convexa (polígono 
convexo) del plano, que llamaremos región factible. 
Aplicación 
Halle la región factible generada por el siguiente sistema de 
inecuaciones. 
 
3𝑥 + 4𝑦 ≤ 12
2𝑥 + 𝑦 ≥ 2
𝑥 ≥ 0
𝑦 ≥ 0
 
Recta 𝐿1 
3𝑥 + 4𝑦 = 12 
𝑥 𝑦 
0 
0 3 
4 
Recta 𝐿2 
2𝑥 + 𝑦 = 2 
𝑥 𝑦 
0 
0 2 
1 
En un problema de programación lineal intervienen: 
Formulación general 
del problema 
1. La función 𝑧(𝑥;𝑦) = 𝑎𝑥 + 𝑏𝑦 + 𝑐, llamada función objetivo y que es 
necesario optimizar. 
En esta expresión, 𝑥 e 𝑦 son las variables de decisión, mientras que 
𝑎, 𝑏 y 𝑐 son constantes. 
𝑎1𝑥 + 𝑏1𝑦 ≤ 𝑐1
𝑎2𝑥 + 𝑏2𝑦 ≤ 𝑐2
 ⋮ ⋮
𝑎𝑛𝑥 + 𝑏𝑛𝑦 ≤ 𝑐𝑛
𝑥 ≥ 0, 𝑦 ≥ 0
 
2. Las restricciones que deben ser inecuaciones lineales. 
Al conjunto de los valores de 𝑥 e 𝑦 que verifican todas y cada una de 
las restricciones se lo denomina región factible. 
Puntos de una 
región factible 
Punto extremo 
Punto frontera 
Punto interior 
La solución óptima del problema será un par de valores 𝑥0; 𝑦0 
(punto) del conjunto factible que haga que 𝑧(𝑥;𝑦) tome el valor 
máximo o mínimo. 
Formulación general 
del problema 
http://www.xhuertas.blogspot.com/
Teorema fundamental 
Dado el problema de optimización con restricciones lineales 
𝑧 = 𝑎𝑥 + 𝑏𝑦 + 𝑐 
el máximo o mínimo de 𝑧, si existe se alcanza en un vértice de la 
región factible. 
Sujeto a: 
𝑎1𝑥 + 𝑏1𝑦 ≤ 𝑐1
𝑎2𝑥 + 𝑏2𝑦 ≤ 𝑐2
 ⋮ ⋮
𝑎𝑛𝑥 + 𝑏𝑛𝑦 ≤ 𝑐𝑛
𝑥 ≥ 0, 𝑦 ≥ 0
 
Pro. lineal tridimensional 
 
𝑎1𝑥 + 𝑏1𝑦 + 𝑐1𝑧 ≤ 𝑑1
𝑎2𝑥 + 𝑏2𝑦 + 𝑐2𝑧 ≤ 𝑑2
𝑎3𝑥 + 𝑏3𝑦 + 𝑐3𝑧 ≤ 𝑑3
 
𝒀 
𝑿 
𝒁 
 
Máx. Mín. 𝑓 𝑥,𝑦,𝑧 = 𝑎𝑥 + 𝑏𝑦 + 𝑐𝑧 + 𝑑 
Aplicación 
Ejemplo. Halle el máximo y mínimo valor de la función 
𝑓(𝑥;𝑦) = 3𝑥 + 2𝑦 − 1 con las restricciones 
3𝑥 + 4𝑦 ≤ 12
2𝑥 + 𝑦 ≥ 2
𝑥 ≥ 0, 𝑦 ≥ 0
. 
Solución. 
Graficamos las rectas y hallamos la región factible. 
 
3𝑥 + 4𝑦 = 12
2𝑥 + 𝑦 = 2
 𝑥 = 0
 𝑦 = 0
 
El proceso para encontrar la solución óptima es el siguiente: 
Se plantea el problema, se traduce a un modo algebraico, se 
analizan las restricciones y se busca el óptimo dependiendo del 
criterio que se quiera aplicar. 
Aplicación 
Recta 𝐿1 
3𝑥 + 4𝑦 = 12 
𝑥 𝑦 
0 
0 3 
4 
Recta 𝐿2 
2𝑥 + 𝑦 = 2 
𝑥 𝑦 
0 
0 2 
1 
(𝟏; 𝟎) 
(𝟎; 𝟑) 
(𝟒; 𝟎) 
(𝟎; 𝟐) 
𝑓 1;0 = 3 1 + 2 0 − 1 = 2 
𝑓 4;0 = 3 4 + 2 0 − 1 = 11 
𝑓 0;3 = 3 0 + 2 3 − 1 = 5 
𝑓 0;2 = 3 0 + 2 2 − 1 = 3 
Evaluamos en los vértices: 
𝑓(𝑥;𝑦) = 3𝑥 + 2𝑦 − 1 
⟵ (Máximo) 
⟵ (Mínimo) 
http://www.xhuertas.blogspot.com/
Modelización de un 
problema de PL 
Introduciremos las líneas generales del modelo de Programación 
Lineal (PL) ilustrándolo con el siguiente ejemplo: 
Una fábrica de muebles produce dos tipos de escritorio, Tipo I y 
Tipo II, en los talleres de corte, armado y acabado. El número de 
horas disponibles en cada taller son de 80 h, 220 h y 210 h 
respectivamente. Las horas que se requieren en la producción en 
cada taller para cada tipo de escritorio se da en la siguiente tabla. 
Si la utilidad para cada unidad de escritorios del Tipo I y del Tipo II 
son S/. 50 y S/. 60 respectivamente. ¿Cuantas unidades de cada 
tipo se deben fabricar mensualmente para maximizar la utilidad y 
cual es dicha utilidad? ¿Cuantas horas no se utilizan en los talleres? 
Corte Armado Acabado 
Tipo I 1 h 3 h 2 h 
Tipo II 1 h 2 h 3 h 
Modelización de un 
problema de PL 
Para resolver el problema construimos un modelo matemático del 
mismo. La construcción de este modelo puede hacerse siguiendo el 
proceso que se describe a continuación: 
Paso 1: Determinar las variables de decisión o de entrada y 
representarlas algebraicamente. Tomamos en este caso las 
variables: 
𝑥1 = número de escritorios del tipo I 
Paso 2: Determinar las restricciones expresándolas como 
ecuaciones o inecuaciones de las variables de decisión. 
El total de horas en el taller de corte es: 𝑥1 + 𝑥2, pero hay 
disponible 80 horas para el taller de corte, luego 
Taller de corte: 𝑥1 + 𝑥2 ≤ 80 
Taller de armado: 3𝑥1 + 2𝑥2 ≤ 220 
Taller de acabado: 2𝑥1 + 3𝑥2 ≤ 210 
𝑥2 = número de escritorios del tipo II 
Modelización de un 
problema de PL 
Paso 3: Expresar todas las condiciones implícitamente establecidas 
por la naturaleza de las variables (que no puedan ser negativas, que 
sean enteras, que sólo pueden tomar determinados valores, etc.) 
En este ejemplo los cantidades de escritorios no pueden tomar 
valores negativos, es decir; 𝑥1 ≥ 0; 𝑥2 ≥ 0. 
Paso 4: Determinar la función objetivo. 
El objetivo de este problema es: 
Maximizar utilidad = Máx. 𝑧 = 5𝑥1 + 6𝑥2 
El modelo por tanto es el siguiente: 
Mán. 𝑧 = 5𝑥1 + 6𝑥2 
sujeto a: 
 𝑥1 + 𝑥2 ≤ 80
3𝑥1 + 2𝑥2 ≤ 220
2𝑥1 + 3𝑥2 ≤ 210
𝑥1, 𝑥2≥ 0
 
Modelización de un 
problema de PL 
3𝑥1 + 2𝑥2 = 220 
𝑥1 + 𝑥2 = 80 
2𝑥1 + 3𝑥2 = 210 
𝟎; 𝟎 𝟐𝟐𝟎
𝟑
; 𝟎 
𝟔𝟎; 𝟐𝟎 
 
 𝑥1 + 𝑥2 ≤ 80
3𝑥1 + 2𝑥2 ≤ 220
2𝑥1 + 3𝑥2 ≤ 210
𝑥1, 𝑥2≥ 0
 
𝟑𝟎; 𝟓𝟎 
𝟎; 𝟕𝟎 
Modelización de un 
problema de PL 
Evaluamos la función objetivo 𝑓(𝑥;𝑦) = 5𝑥1 + 6𝑥2 en los vértices de 
la región admisible: 0; 0 , 0; 70 , 30; 50 , 60; 20 ,
220
3
; 0 . 
𝑓 0;0 = 5(0) + 6(0) = 
𝑓 0;70 = 5 0 + 6 70 = 
𝑓 30;50 = 5(30) + 6(50) = 
0 
420 
450 Máximo 
Por lo tanto, las cantidades de escritorios de Tipo I y Tipo II que 
deben fabricarse para maximizar la utilidad debe ser de 30 y 50 
respectivamente. 
𝑓 60;20 = 5(60) + 6(20) = 
𝑓 220
3 ;0
= 5
220
3
+ 6(0) = 
420 
366,6 
Método del Simplex 
Es un procedimiento iterativo que permite ir mejorando la solución a 
cada paso. El proceso concluye cuando no es posible seguir 
mejorando más dicha solución. 
Partiendo del valor de la función 
objetivo en un vértice cualquiera, el 
método consiste en buscar 
sucesivamente otro vértice que 
mejore al anterior. 
La búsqueda se hace siempre a través de los lados del polígono (o 
de las aristas del poliedro, si el número de variables es mayor). 
Cómo el número de vértices (y de aristas) es finito, siempre se 
podrá encontrar la solución. 
Punto 
óptimo 
Resuelva mediante el método del Simplex el siguiente problema. 
Máx. 𝑓(𝑥;𝑦;𝑧) = 2𝑥 + 3𝑦 + 6𝑧 
sujeto a 
2𝑥 + 3𝑦 + 𝑧 ≤ 10
𝑥 + 𝑦 + 2𝑧 ≤ 8
 2𝑦 + 3𝑧 ≤ 6
𝑥 ≥ 0, 𝑦 ≥ 0, 𝑧 ≥ 0
 
Aplicación del MS 
I) En la función objetivo, transponer los términos del segundo 
miembro al primer miembro: 
𝑓 − 2𝑥 − 3𝑦 − 6𝑧 = 0 
II) Sumar una variable de holgura a cada desigualdad: 
 
2𝑥 + 3𝑦 + 𝑧 + 𝑠1 = 10
𝑥 + 𝑦 + 2𝑧 + 𝑠2 = 8
 2𝑦 + 3𝑧 + 𝑠3 = 6
 
Aplicación del MS 
III) Así hemos obtenido un sistema de 4 ecuaciones lineales con 7 
incógnitas (𝑓, 𝑥, 𝑦, 𝑧, 𝑠1, 𝑠2, 𝑠3): 
 
𝑓 − 2𝑥 − 3𝑦 − 6𝑧 = 0
2𝑥 + 3𝑦 + 𝑧 + 𝑠1 = 10
𝑥 + 𝑦 + 2𝑧 + 𝑠2 = 8
2𝑦 + 3𝑧 + 𝑠3 = 6
 
IV) Formar la tabla del Simplex: Tabla 1 (con los coeficientes de las 
variables y los términos independientes – matriz aumentada) 
Ctes 
Fila 1 
Fila 2 
Fila 3 
Fila 4 
𝑓 𝑥 𝑦 𝑧 𝑠1 𝑠2 𝑠3 
1 −2 −3 −6 0 0 0 0 
0 2 3 1 1 0 0 10 
0 1 
0 
1 2 0 1 0 8 
0 2 3 0 0 1 6 
V) En la Tabla 1, hacer las operaciones elementales sobre las filas 
para ir mejorando la solución factible básica. 
sss 𝑓 𝑥 𝑦 𝑧 𝑠1 𝑠2 𝑠3 Ctes 
−3 
1 −2 −3 −6 0 0 0 0 
0 2 3 1 1 0 0 10 
0 1 1 2 0 1 0 8 
0 0 2 3 0 0 1 6 
1 −2 −6 0 0 0 0 
0 2 3 1 1 0 0 10 
0 1 1 2 0 1 0 8 
0 0 2/3 1 0 0 1/3 2 
1 
0 
0 
−2 1 0 0 0 2 12 
2 7/3 0 1 0 −1/3 8 
0 1 −1/3 0 0 1 −2/3 4 
0 2/3 1 0 0 1/3 2 
1 0 1/3 0 0 2 2/3 20 
0 0 3 0 1 −2 1 0 
0 1 −1/3 0 0 1 −2/3 4 
0 0 2/3 1 0 0 1/3 2 
Localizar el elemento 
PIVOT 
1. De la fila 1 elegir el 
menor negativo. 
2. Dividir las 
constantes entre los 
números positivos de 
la COLUMNA 4. 
Razón 
10/1 = 10 
 
8/2 = 4 
 
6/3 = 2 
3.En la intersección 
encontramos el 3 que 
es el PIVOT. 
Iteración I: 
Multiplicamos la fila 4 
por 1/3 para convertir 
en 1 el PIVOT. 
Iteración II: 
Convertir en ceros los 
otros elementos de la 
columna PIVOT. 
Localizar el segundo 
Elemento PIVOT 
8/2 = 4 
 
4/1 = 4 
1. De la fila 1 
elegimos el 
menor negativo. 
2. Dividir las 
constantes entre los 
números positivos de 
la COLUMNA 2. 
Iteración III: 
La fila 3 es la fila 
PIVOT. 
Convertir en ceros los 
otros elementos de la 
columna PIVOT. 
Máximo