UNVIVERSIDAD SAN CARLOS DE GUATEMALA

CENTRO UNIVERSITARIO DE OCCIDENTE “CUNOC”

CIENCIAS ECONOMICAS
LICENCIATURA EN ADMINISTRACION DE EMPRESAS
9NO SEMESTRE SECCION “B”
METODOS CUANTITATIVOS IV
LIC. WERNER LOPEZ.

TAREA
INFORME FINAL

JONATHAN DANIEL
NICOLAS AGUILAR
201931452
 Método Simplex

El Método Simplex es un procedimiento matemático que se utiliza para resolver

problemas de programación lineal. Su objetivo es encontrar el valor máximo o
mínimo de una función objetivo (generalmente de costos, ganancias o
utilidades), respetando un conjunto de restricciones dadas en forma de
ecuaciones o desigualdades lineales.

Fue desarrollado por George Dantzig en 1947 y es uno de los métodos más
importantes en la optimización de recursos.

¿En qué consiste el Método Simplex?

El Método Simplex trabaja dentro de un espacio de soluciones posibles

(llamado poliedro factible) y se mueve de un vértice a otro (o de una solución
básica factible a otra) buscando mejorar el valor de la función objetivo en cada
paso, hasta llegar al vértice óptimo (donde ya no se puede mejorar más).

Idea central: En un problema de programación lineal, la mejor solución siempre

se encuentra en uno de los vértices del área factible.

Elementos principales

 Función objetivo: Lo que queremos maximizar o minimizar.

 Variables de decisión: Representan las cantidades que queremos
determinar.
 Restricciones: Condiciones que deben cumplirse (limitaciones de
recursos, capacidades, etc.).
 Tabla Simplex: Una herramienta organizada que se usa para hacer los
cálculos de manera ordenada.

Pasos básicos del Método Simplex

1. Formular el problema:
Definir la función objetivo y las restricciones en forma estándar
(igualdades).
2. Agregar variables de holgura o exceso:
Para convertir desigualdades ("≤" o "≥") en igualdades.
 3. Construir la tabla inicial Simplex:
Organizar los datos en una tabla, incluyendo las variables y sus
coeficientes.
4. Identificar la variable que entra a la base:
Elegir la variable que puede mejorar más la función objetivo (generalmente
la que tiene el coeficiente más negativo en la fila de la función objetivo).
5. Identificar la variable que sale de la base:
Usar la regla del mínimo cociente para decidir qué variable debe salir.
6. Realizar el pivoteo:
Hacer operaciones en la tabla para cambiar la base, llevando la nueva
variable de entrada a 1 y las demás a 0.
7. Repetir el proceso:
Hasta que ya no haya mejoras posibles (es decir, cuando todos los
coeficientes en la fila de la función objetivo sean positivos en maximización
o negativos en minimización).
8. Interpretar la solución:
Los valores de las variables indican la solución óptima.

Aplicaciones del Método Simplex

 Optimización de costos de producción.

 Asignación de recursos en empresas.
 Maximización de utilidades en negocios.
 Minimización de tiempos en proyectos.
 Logística y transporte.

Ventajas del Método Simplex

 Es preciso y sistemático.
 Puede manejar problemas grandes y complejos.
 Garantiza encontrar la solución óptima (si existe).

Método Simplex – Maximización

¿Qué es?

El Método Simplex de Maximización se utiliza cuando queremos encontrar el

valor más grande posible de la función objetivo.
Por ejemplo: maximizar ganancias, productividad, utilidades, ventas, etc.
Forma general

 Función objetivo (lo que queremos maximizar):

Maximizar Z=c1x1+c2x2+⋯+cnxn\text{

Maximizar Z = c_1x_1 + c_2x_2 + \dots + c_nx_n

Maximizar Z=c1x1+c2x2+⋯+cnxn

 Sujeto a restricciones (normalmente en forma “≤”):

a11x1+a12x2+⋯+a1nxn≤b1a_{11}x_1 + a_ {12}x_2 + \dots + a_{1n}x_n \leq

b_1a11x1+a12x2+⋯+a1nxn≤b1

a21x1+a22x2+⋯+a2nxn≤b2a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n \leq

b_2a21x1+a22x2+⋯+a2nxn≤b2

xi≥0x_i \geq 0xi≥0

Procedimiento

1. Formular el problema en forma estándar.

2. Agregar variables de holgura para convertir “≤” en igualdades.
3. Construir la tabla Simplex inicial.
4. Seleccionar la variable de entrada (la que más puede mejorar Z, es decir,
el coeficiente más negativo en la función objetivo).
5. Seleccionar la variable de salida (usando el mínimo cociente positivo).
6. Realizar el pivoteo para actualizar la tabla.
7. Repetir el proceso hasta que no haya más valores negativos en la
función objetivo.
8. Leer la solución óptima.

Resultado final:

Se obtiene el valor máximo posible de ZZZ, respetando todas las restricciones.

Método Simplex – Minimización

¿Qué es?
El Método Simplex de Minimización se utiliza cuando queremos encontrar el
valor más pequeño posible de la función objetivo.
Por ejemplo: minimizar costos, tiempos, pérdidas, desperdicios, etc.

Forma general

 Función objetivo (lo que queremos minimizar):

Minimizar Z=c1x1+c2x2+⋯+cnxn\text{

Minimizar} Z = c_1x_1 + c_2x_2 + \dots + c_nx_n

Minimizar Z=c1x1+c2x2+⋯+cnxn.

 Sujeto a restricciones (normalmente en forma “≥”):

a11x1+a12x2+⋯+a1nxn≥b1

a_ {11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \geq b_1a11x1+a12x2+⋯+a1n

xn≥b1

a21x1+a22x2+⋯+a2nxn≥b2a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n \geq

b_2a21x1+a22x2+⋯+a2nxn≥b2

xi≥0x_i \geq 0xi≥0

Procedimiento

1. Formular el problema en forma estándar.

2. Agregar variables de exceso y variables artificiales para convertir “≥” en
igualdades.
3. Si hay variables artificiales, usar el Método de las Dos Fases:
o Fase 1: Eliminar las variables artificiales minimizando su suma.
o Fase 2: Resolver el problema original de minimización.
4. Construir la tabla Simplex.
5. Seleccionar la variable de entrada (el coeficiente más positivo en la
función objetivo, según las reglas adaptadas para minimización).
6. Seleccionar la variable de salida usando el mínimo cociente.
7. Realizar el pivoteo para actualizar la tabla.
8. Repetir hasta que no haya mejoras.
9. Leer la solución óptima.
Resultado final:

Se obtiene el valor mínimo posible de ZZZ, respetando todas las restricciones.

Diferencias clave entre Maximización y Minimización en Simplex

Característica Maximización Minimización

Objetivo Mayor valor de Z Menor valor de Z
Restricciones típicas "≤" "≥"
Variables de exceso y
Variables adicionales Variables de holgura
artificiales
Método de Dos Fases o
Método adicional Método Simplex estándar
Forma Dual
Interpretación de la Coeficientes negativos Coeficientes positivos
tabla indican mejora indican mejora

Método de Transporte

Definición

El Método de Transporte es una técnica de optimización utilizada en investigación

de operaciones para encontrar la forma más eficiente (en términos de costo
mínimo) de transportar bienes o productos desde varios puntos de suministro
(orígenes) a varios puntos de demanda (destinos). Su objetivo principal es
minimizar el costo total de transporte, respetando las restricciones de oferta en los
orígenes y de demanda en los destinos.

Este método es un caso especial de los problemas de programación lineal, debido

a su estructura particular de restricciones y su objetivo lineal.

Aplicaciones

El Método de Transporte tiene numerosas aplicaciones prácticas en áreas como:

 Distribución de productos desde fábricas a almacenes o tiendas.

 Asignación de recursos en cadenas de suministro.
 Logística de transporte de materias primas.
 Distribución de servicios de salud o educación en regiones específicas.
  Asignación de tareas en sistemas de producción.

Componentes Básicos

 Orígenes: Lugares donde se encuentran los productos o recursos (por

ejemplo, fábricas).
 Destinos: Lugares donde se requieren esos productos o recursos (por
ejemplo, tiendas).
 Oferta (Suministro): Cantidad de productos disponibles en cada origen.
 Demanda: Cantidad de productos requeridos en cada destino.
 Costo unitario de transporte: Costo de transportar una unidad de
producto de un origen a un destino.

Estructura del Problema

El problema se representa comúnmente en una tabla de transporte, donde:

 Las filas representan los orígenes.

 Las columnas representan los destinos.
 Cada celda contiene el costo unitario de transporte y la cantidad a
transportar.

Tipos de Problemas de Transporte

 Problema balanceado: Cuando la oferta total es igual a la demanda total.

 Problema no balanceado: Cuando la oferta total es diferente de la
demanda total. Se balancea agregando un "origen o destino ficticio" con
costo cero.

Métodos para Resolver el Problema de Transporte

1. Solución Inicial (Métodos de Búsqueda de Solución Básica Factible)

Antes de optimizar, se necesita una solución inicial aceptable:

 Método de la Esquina Noroeste: Se comienza en la esquina superior

izquierda de la tabla y se asignan las cantidades posibles respetando oferta
y demanda.
  Método de Costo Mínimo: Se elige el costo más bajo disponible en la tabla
y se asignan las cantidades máximas posibles.
 Método de Aproximación de Vogel: Se basa en calcular penalizaciones
(diferencias entre los dos menores costos) para determinar la mejor
asignación inicial.

2. Optimización (Métodos de Mejora de Solución)

Una vez obtenida una solución inicial, se busca mejorarla:

 Método de Distribución MODI (Modified Distribution Method): Permite

encontrar rutas alternativas y calcular mejoras en el costo total.
 Método de Celdas Cerradas (o de Ciclos Cerrados): Se utilizan ciclos de
mejora para reajustar las asignaciones y disminuir los costos.

Pasos Generales para Resolver un Problema de Transporte

1. Formular el problema: Definir claramente los orígenes, destinos, ofertas,

demandas y costos de transporte.
2. Verificar si está balanceado: Si no lo está, agregar un origen o destino
ficticio.
3. Encontrar una solución inicial factible usando uno de los métodos
mencionados.
4. Optimizar la solución utilizando el Método MODI o ciclos cerrados.
5. Interpretar los resultados y tomar decisiones en base a la solución óptima
obtenida.

Ejemplo Básico

Supongamos tres fábricas (A, B, C) y dos almacenes (X, Y), con costos de
transporte, oferta y demanda:

X ($4) Y ($6) Oferta

A 4 6 20

B 5 2 30

C 7 3 25

Demanda 35 40
Pasos:

 Balanceamos si es necesario (en este caso, oferta total 75 = demanda total

75).
 Usamos un método inicial (por ejemplo, Costo Mínimo) para asignar
cantidades.
 Aplicamos MODI para optimizar el costo total.

Ventajas del Método de Transporte

 Minimiza costos de logística de manera sistemática y objetiva.

 Permite encontrar soluciones eficientes en tiempo razonable.
 Es adaptable a cambios de oferta, demanda o costos.

Limitaciones

 Asume que los costos de transporte son proporcionales a las cantidades

enviadas.
 No considera variaciones como tiempos de entrega o restricciones de
capacidad de transporte (aunque pueden adaptarse modelos más
avanzados).
 Requiere que todos los datos sean conocidos y fijos.

Método de Transporte – Minimización

Definición

El Método de Transporte de Minimización busca determinar la forma más

económica de transportar bienes desde varios puntos de origen hacia varios
puntos de destino, minimizando el costo total de transporte, respetando las
restricciones de oferta y demanda.

En otras palabras: encontrar la asignación de envíos que cumpla con todas las
necesidades de la manera más barata posible.

Características

 Objetivo principal: Reducir el costo total de transporte.

  Costos unitarios: Se busca enviar más productos donde el costo por
unidad transportada es menor.
 Restricciones: Se deben satisfacer completamente tanto la oferta de los
orígenes como la demanda de los destinos.
 Aplicaciones típicas: Distribución de productos, logística, abastecimiento,
redes de transporte.

Formulación Matemática

Minimizar:

Z=∑i=1m∑j=1ncijxijZ = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij}Z=i=1∑mj=1∑ncij

xij

Sujeto a:

\sum_{j=1}^{n} x_{ij} = s_i \quad \text{(oferta en el origen i)} ]

\sum_{i=1}^{m} x_{ij} = d_j \quad \text{(demanda en el destino j)} ]

x_{ij} \geq 0 ]

Donde:

 cijc_{ij}cij = costo de transportar una unidad del origen iii al destino jjj
 xijx_{ij}xij = cantidad a transportar del origen iii al destino jjj
 sis_isi = oferta en el origen iii
 djd_jdj = demanda en el destino jjj

Procedimiento

1. Formular la tabla de transporte: Con ofertas, demandas y costos.

2. Equilibrar el problema si es necesario (oferta ≠ demanda).
3. Encontrar una solución inicial (Método de la esquina noroeste, costo
mínimo o aproximación de Vogel).
4. Optimizar la solución utilizando el método MODI o ciclos cerrados.
 5. Interpretar resultados y determinar el costo mínimo total.

Ejemplo Breve

Supongamos:

Destino 1 Destino 2 Oferta

Origen 1 8 6 20
Origen 2 4 9 30
Demanda 25 25

La meta sería asignar las cantidades de modo que el costo total sea el menor
posible, considerando los costos 8, 6, 4 y 9.

Método de Transporte – Maximización

Definición

El Método de Transporte de Maximización se utiliza cuando el objetivo no es

minimizar costos, sino maximizar un beneficio, utilidad o ganancia derivada de
transportar bienes entre orígenes y destinos.

En otras palabras: encontrar la forma de obtener la mayor ganancia posible al

realizar las asignaciones.

Características

 Objetivo principal: Lograr el mayor beneficio o utilidad total.

 Beneficios unitarios: Se favorecen los envíos donde la ganancia por
unidad es mayor.
 Restricciones: Igual que en minimización, se deben satisfacer ofertas y
demandas.
  Aplicaciones típicas: Distribución de productos donde se prioriza la
maximización de utilidades o eficiencia.

Formulación Matemática

Maximizar:

Z=∑i=1m∑j=1npijxijZ = \sum_{i=1}^{m} \sum_{j=1}^{n} p_{ij} x_{ij}Z=i=1∑mj=1∑npij

xij

Sujeto a:

\sum_{j=1}^{n} x_{ij} = s_i \quad \text{(oferta en el origen i)} ]

\sum_{i=1}^{m} x_{ij} = d_j \quad \text{(demanda en el destino j)} ]

x_{ij} \geq 0 ]

Donde:

 pijp_{ij}pij = utilidad (o beneficio) por transportar una unidad del origen iii al
destino jjj
 xijx_{ij}xij = cantidad transportada

Procedimiento

1. Formular la tabla de transporte: Con ofertas, demandas y utilidades.

2. Equilibrar el problema si es necesario.
3. Convertir a minimización: (opcional) restando cada utilidad de una
constante mayor o igual a la máxima utilidad para transformar el problema a
minimización, o directamente aplicar métodos de maximización.
4. Encontrar solución inicial (costo mínimo equivalente, esquina noroeste o
Vogel).
5. Optimizar utilizando MODI adaptado a maximización.
6. Interpretar resultados: Identificar la distribución que da la mayor ganancia
total.
Nota Importante

 En maximización, los métodos tradicionales (como MODI) se ajustan para

buscar mayores ganancias en lugar de menores costos.
 Si es necesario convertir a minimización:

Nuevo costo=M−pij\text{Nuevo costo} = M - p_{ij}Nuevo costo=M−pij

donde MMM es el valor más alto de todos los beneficios pijp_{ij}pij.

Ejemplo Breve

Supongamos:

Destino 1 Destino 2 Oferta

Origen 1 12 8 20
Origen 2 10 15 30
Demanda 25 25

Aquí, los números representan beneficios. La meta es asignar las cantidades de

tal forma que el beneficio total sea el mayor posible.

Método de Asignación

Definición

El Método de Asignación es una técnica de optimización utilizada para resolver

problemas donde se deben asignar recursos limitados (personas, máquinas,
trabajos, etc.) a un conjunto de tareas específicas de la manera más eficiente
posible.

El objetivo principal es minimizar el costo total o maximizar la utilidad total de

las asignaciones, asegurando que cada recurso se asigne a una sola tarea y
cada tarea reciba exactamente un recurso.

Es un caso especial de la programación lineal y se resuelve generalmente

utilizando el Método Húngaro.
Aplicaciones

El Método de Asignación se utiliza en muchos campos como:

 Asignar trabajadores a trabajos.

 Asignar vehículos a rutas.
 Asignar máquinas a tareas de producción.
 Asignar profesores a cursos.
 Asignar proyectos a equipos de trabajo.

Características

 Número igual de agentes y tareas: Normalmente se requiere que haya el

mismo número de recursos que de tareas. Si no es así, se agregan "falsos"
recursos o tareas con costo cero.
 Cada agente realiza exactamente una tarea.
 Cada tarea es realizada por exactamente un agente.
 Costos, tiempos o eficiencias son conocidos de antemano para cada
posible asignación.

Estructura del Problema

Se organiza en una matriz de costos:

 Las filas representan los agentes o recursos.

 Las columnas representan las tareas.
 Cada celda contiene el costo (o utilidad) de asignar un recurso a una tarea.

Formulación Matemática

Minimizar:

Z=∑i=1n∑j=1ncijxijZ = \sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij} x_{ij}Z=i=1∑nj=1∑ncijxij

Sujeto a:

\sum_{j=1}^{n} x_{ij} = 1 \quad \text{para todo } i \quad \text{(cada agente se

asigna a una sola tarea)} ]
 

\sum_{i=1}^{n} x_{ij} = 1 \quad \text{para todo } j \quad \text{(cada tarea es

realizada por un solo agente)} ]

x_{ij} = 0 \text{ o } 1 \quad \text{(asignado o no asignado)} ]

Donde:

 cijc_{ij}cij = costo de asignar el recurso iii a la tarea jjj,

 xijx_{ij}xij = variable binaria: 1 si el recurso iii es asignado a la tarea jjj, 0 en
caso contrario.

Método de Resolución: Método Húngaro

El Método Húngaro es el procedimiento más utilizado para resolver problemas de

asignación. Sus pasos son:

1. Restar el mínimo de cada fila de todos los elementos de la fila.

2. Restar el mínimo de cada columna de todos los elementos de la columna
resultante.
3. Cubrir todos los ceros de la matriz con el mínimo número de líneas
horizontales y verticales.
4. Si el número de líneas es igual al número de filas (o columnas), hay una
solución óptima.
5. Si no, se modifica la matriz y se repite desde el paso 3.
6. Realizar las asignaciones respetando que cada agente realice solo una
tarea y viceversa.

Tipos de Problemas de Asignación

 De minimización: Minimizar costos, tiempos, distancias, etc.

 De maximización: Maximizar ganancias, eficiencia, productividad (se
puede convertir en minimización tomando el complemento de los valores).

Ejemplo Básico
Supongamos que tenemos tres trabajadores (A, B, C) y tres trabajos (1, 2, 3), con
los siguientes costos:

Trabajo 1 Trabajo 2 Trabajo 3

A 10 5 9
B7 8 5
C8 9 6

Aplicando el Método Húngaro, se obtendría la asignación de trabajadores a

trabajos para minimizar el costo total.

Ventajas del Método de Asignación

 Resuelve problemas de asignación de manera rápida y eficiente.

 Garantiza una solución óptima.
 Permite manejar tanto problemas de minimización como de
maximización.
 Puede adaptarse fácilmente a cambios en los costos o disponibilidades.

Limitaciones

 Se requiere que el número de agentes y tareas sea igual (aunque se puede

balancear).
 No considera prioridades más complejas, como habilidades específicas o
restricciones múltiples (estos se tratan con extensiones del método básico).

Método de Asignación – Minimización

Definición

El Método de Asignación de Minimización busca asignar recursos (personas,

máquinas, vehículos, etc.) a tareas de forma que se minimice el costo total, el
tiempo de ejecución, la distancia, o cualquier otro criterio que se desee optimizar a
la baja.

En otras palabras: se asigna cada recurso a una tarea de tal manera que el costo
total sea el más bajo posible.
Características

 Objetivo principal: Minimizar costos o tiempos.

 Datos: Se requiere una matriz de costos, donde cada celda representa el
costo de asignar un recurso a una tarea.
 Condición: Cada recurso debe ser asignado exactamente a una tarea, y
cada tarea debe recibir exactamente un recurso.
 Método usual: Se resuelve utilizando el Método Húngaro.

Procedimiento (Método Húngaro para Minimización)

1. Crear la matriz de costos.

2. Restar el valor mínimo de cada fila a todos los elementos de esa fila.
3. Restar el valor mínimo de cada columna a todos los elementos de esa
columna.
4. Cubrir todos los ceros de la matriz usando el menor número de líneas
horizontales y verticales.
5. Si el número de líneas es igual al número de filas o columnas, se puede
proceder a realizar las asignaciones óptimas.
6. Si no, modificar la matriz:
o Encontrar el valor mínimo no cubierto.
o Restarlo de todos los elementos no cubiertos.
o Sumarlo a los elementos cubiertos dos veces.
7. Asignar los ceros de forma que no haya conflictos (una tarea por recurso).

Ejemplo Breve

Supongamos una matriz de costos:

Tarea 1 Tarea 2 Tarea 3

Agente A 4 2 8
Agente B 4 3 7
Agente C 3 1 6

Aplicando el Método Húngaro, podríamos encontrar la asignación que minimice el

costo total.

Método de Asignación – Maximización

Definición

El Método de Asignación de Maximización busca asignar recursos a tareas de

forma que se maximice la ganancia, productividad o utilidad total del sistema.

En otras palabras: asignar recursos a tareas de manera que el beneficio obtenido

sea el mayor posible.

Características

 Objetivo principal: Maximizar beneficios, ingresos o eficiencia.

 Datos: Se requiere una matriz de beneficios o utilidades.
 Condición: Igual que en minimización, cada recurso debe realizar una
única tarea y cada tarea debe ser realizada por un solo recurso.
 Método usual: Se adapta el Método Húngaro para maximización.

Procedimiento (Método Húngaro para Maximización)

El Método Húngaro está diseñado originalmente para minimizar, por lo que en

maximización se transforma el problema:

1. Identificar el valor máximo de la matriz de utilidades.

2. Restar cada elemento de la matriz de utilidades del valor máximo
encontrado.
o Nueva matriz = (Valor máximo) – (Valor original).
3. Resolver el problema como un problema de minimización normal.
4. Realizar las asignaciones para lograr la máxima utilidad total.

Ejemplo Breve

Supongamos una matriz de utilidades:

Tarea 1 Tarea 2 Tarea 3

Agente A 20 28 16
Agente B 26 24 20
Agente C 22 27 23

 El mayor valor es 28.

  Se resta cada valor de 28 para convertir el problema en uno de
minimización.
 Luego se aplica el Método Húngaro como en el problema de minimización.

Diferencias entre Minimización y Maximización en Asignación

Aspecto Minimización Maximización

Reducir el costo, tiempo o Aumentar la ganancia, utilidad o
Objetivo
distancia productividad
Datos en matriz Costos o tiempos Beneficios o utilidades
Método Húngaro (con
Método usado Método Húngaro
transformación)
Conversión Se convierte en un problema de
No necesita
previa minimización