ÍNDICE

RESUMEN
RESUMEN ..................................................................................................................... 3
INTRODUCCIÓN................................................................................................................ 4
Objetivo General................................................................................................................. 5
Objetivo Específico
TEORÍA DE PROGRAMACIÓN LINEAL ..................................................................... 6
Conceptos básicos ............................................................................................................. 6
Solución gráfica
Forma padrãoo.................................................................................................................... 9
Forma canónica............................................................................................................... 10
MÉTODO SIMPLEX ..................................................................................................... 11
Algoritmo Simplex Tabular............................................................................................ 11
Múltiples Soluciones Óptimas............................................................................................. 12
Adaptaciones de Casos Específicos................................................................................... 12
Método Big-M ................................................................................................................ 12
DUALIDAD EN LA PROGRAMACIÓN LINEAL
CONCLUSIÓN
REFERENCIAS BIBLIOGRÁFICAS ........................................................................... 15
 RESUMEN

En este trabajo se llevó a cabo el estudio de los principales conceptos de la Programación

Lineal, con el fin de proporcionar la comprensión de sus métodos de construcción y resolución de

problemas. Para tal, foram estudados e são aqui apresentados os conceitos essenciais
para la formulación de los problemas en su forma estándar a través de una fundamentación
teórica y resolución de ejemplos, permitiendo así una comprensión de la Programación
Lineal. Para la solución de los problemas, se estudiaron los métodos Simplex, Simplex
Revisado e Dual Simplex bem como a Dualidade na programação linear e suas formas
de resolución.

Palabras Clave: Programación Lineal. Simplex. Duales. Revisado

2
 RESUMEN

Este trabajo se llevó a cabo para estudiar los conceptos principales de la Programación Lineal en

orden para proporcionar una comprensión de sus métodos de construcción y resolución de problemas.

Para tales, se estudiaron y se presentan aquí, los conceptos esenciales para la formulación
de problemas en su forma estándar a través de una base teórica y resolución de
ejemplos, lo que permite una comprensión de la Programación Lineal. Para resolver el
problemas, los métodos Simplex, Simplex Revisado y Simplex Dual así como el
Se ha utilizado la dualidad en la programación lineal y sus formas de resolución.

Programación Lineal. Simplex. Dualidad. Revisado.

3
 INTRODUCCIÓN

El tema elegido para objeto de esta disertación 'Programación Lineal'

La Programación Lineal fue creada por Dantzig (1948) como una forma de planificación
automatizado para la distribución de recursos, logística y asignación de tiempo para el
Ejército de los Estados Unidos. En esencia, la Programación Lineal se centra en la
optimización de sistemas, a través de la maximización o minimización de determinados
problemas matemáticamente formulados (Hillier; Leiberman, 2006).

En 1949, Dantzig publicó un estudio que describía el Método Simplex para

resolución de problemas de Programación Lineal. Este método es ampliamente utilizado
debido a su capacidad para gestionar problemas complejos de toma de decisiones, bien
como la habilidad de producir decisiones aceptables en un corto período de tiempo
(Hillier; Leiberman, 2006). Este estudio tiene como objetivo proporcionar el conocimiento
necesario sobre los principales conceptos y formas de resolución de problemas de
Programación Lineal, actuando como forma de aprendizaje en la resolución y construcción de
problemas a través de los algoritmos disponibles actualmente.

4
Objetivo General

Se utiliza para optimizar (maximizar o minimizar) una función lineal de

variables, llamada de función objetivo, sujeta a una serie de ecuaciones (o
inequaciones) lineales, llamadas restricciones.

Objetivo Específico

Reconocer los problemas que son susceptibles de análisis por el modelo;

Auxiliar al analista en la etapa inicial de la investigación;
Evaluar e interpretar inteligentemente los resultados;

5
 TEORÍA DE PROGRAMACIÓN LINEAL

Conceptos básicos
La Programación Lineal tiene como objetivo la realización de operaciones con
finalidad de encontrar la mejor solución y ayudar en la toma de decisiones de problemas
que sean representados por modelos con expresiones lineales. Este enfoque tiene
cómo escopo la maximización o minimización de una función lineal, llamada Función
Objetivo, que comúnmente es dado por:

= 1+ 1 +⋯
2 2+ no cual las variables se llaman variables de
decisión.

Para determinar cuáles son los valores adecuados que las variables de decisión deben tener

asumir, es necesario seguir un conjunto de ecuaciones o desigualdades también lineales,

que determinan reglas que el modelo debe adoptar. Este conjunto de expresiones son
conocidos por Restricciones del Modelo y siguen la siguiente estructura:

11+ 11+ ⋯12+ 12 ≤ 1 1 1

+ 21 + ⋯22+ 22 ≤
21 2 2 2
⋮ ⋮ ⋮ ⋮ ⋮
+1 1 ⋯ +2 ≤2
+ m

,1 , …
2 , ≥ 0.

Las Restricciones del Modelo son responsables de la delimitación de un área de

solución conocida como área factible o área viable. La mejor solución, conocida como
solución óptima se encuentra dentro de esta región pudiendo maximizar o minimizar la
función objetivo. Bazaraa, Jarvis y Sherali (2010) definen que un problema de
La Programación Lineal debe ser creada a partir de un análisis que requiere una serie de
pasos, son ellos:

Formulación del problema: Consiste en una evaluación del problema real, en

cuales se deben considerar factores limitantes, posibles variaciones, constantes y
restricciones. Es en esta etapa que ocurre la recolección de datos y se identifica el

problema a ser estudiado;

Construcción del modelo matemático: Representa la fase en la cual el problema
matemático es idealizado a través del análisis realizado durante el paso anterior. A

6
 la formulación debe ser minuciosamente construida para que esta genere un
modelo matemático que representa el problema;
Obtención de una solución: Debe elegirse cuál es el enfoque de
resolución dar al modelo. Es posible que se busquen múltiples soluciones óptimas
o solamente una, y para ambos los casos, se deben elegir heurísticas o
técnicas que mejor se adapten de forma a obtener el mínimo decrecimiento de
calidad
Teste del modelo: En este paso se realizan análisis de confiabilidad y si
necesario, reestructuraciones a través de la adición o simplificación de expresiones,
para que el modelo en cuestión se vuelva confiable en diferentes situaciones.
Para una mayor credibilidad de los resultados, también es imprescindible la
análisis de resultados esperados con resultados ya previstos;
Implementación: Es necesario que el modelo sea constantemente actualizado
con posibles nuevos parámetros o restricciones si es necesario, así como el
mismo sea reevaluado constantemente para que no se vuelva obsoleto.

Solución gráfica
Entre los métodos de solución existentes para problemas de Programación Lineal, es
extensamente abordado por autores como Bazaraa, Jarvis y Sherali (2010) y Kolman y
Beck (1995) la posibilidad de resolver gráficamente problemas con un pequeño
número de variables de decisión. Como ejemplo, considere el problema (I).

La existencia de dos variables de decisión posibilita la representación gráfica en

un espacio de dos dimensiones, en el cual puede
1 asumir el eje de las abcisas y como 2
ordenadas. Esta categoría de solución de problemas puede alcanzar la solución óptima,
siguiendo los siguientes pasos:
1. Encontrar la región factible de solución a través de la representación de las respectivas
retas de las restricciones, obedeciendo los puntos que satisfacen la restricción.

7
 2. A través de la verificación del punto (0,0), para cada restricción, es posible analizar
visualmente en qué lado de la recta estará la solución, permitiendo así una
delimitación global utilizando todas las restricciones, dejando visible la región
factible.
a) Es posible que existan problemas en los que el área factible no exista, siendo

entonces considerado un problema imposible, o inviable.

3. Una serie de rectas paralelas se pueden generar a través de la representación de la

función objetivo. La solución óptima se encuentra en el punto que está asociado a
valor que mejor optimiza el problema y toca la región factible.

La Figura 1 muestra la representación gráfica de todas las restricciones relacionadas con el modelo.

Considerando las restricciones para la percepción de la región factible del problema,

conforme indicado en el paso 2, se crea entonces el gráfico presentado en la Figura 2.

Figura 2–Región factible del problema (I) en destaque

8
 La Figura 3 presenta las rectas referentes a la función objetivo, generando un gradiente
que permite que se visualicen posibles soluciones al problema.

Figura 3–Rectas con la función objetivo destacadas en el gráfico.

Es presumible a través del análisis de la tendencia de las rectas que el punto que lleva a
la mejor solución del problema se encuentra en la intersección entre las rectas de las ecuaciones (1) y

(2), generando el respectivo sistema:

La resolución del sistema generado por estas dos ecuaciones lleva al punto (200,
600). Sustituyendo dichos valores en la función objetivo, se obtiene = 2600. ¿Qué es la solución?

óptima.

Forma estándar

Para que se utilice un algoritmo de solución como el Simplex o Simplex

revisado, comúnmente utilizado en problemas prácticos, se recomienda que el problema
tratado sea transformado en una forma estándar. El modelo de minimización se encuentra
en la forma estándar en la siguiente formulación, de acuerdo con Marins (2011):

9
 Forma canónica
Considere el siguiente sistema de ecuaciones:

El conjunto solución del sistema son los valores de 1, 2, 3, y que 4 5

satisfacen ambas las ecuaciones del sistema simultáneamente. Siendo considerado un

Sistema Equivalente. Sistemas equivalentes pueden obtenerse a través de un proceso
matemático llamado Método de Eliminación de Gauss Jordan. Este proceso se basa en
en la multiplicación y división de una de las ecuaciones de un sistema por un determinado
número que al sumarse a la combinación lineal en otra ecuación, resulta en términos
eliminados.

El Método de Eliminación de Gauss Jordan en el sistema que contiene las ecuaciones (11)

e (12) se inicia con la multiplicación de (11) por -1 seguida de la adición a (12), obteniendo
así, el siguiente sistema equivalente:

Todavía es posible eliminar 2de (13) Multiplicando (14) por 2 y sumándolo en la ecuación
en cuestión, lo que resulta en:

Como ya no es posible reducir la cantidad de variables, se dice que

esa es la Forma Canónica del sistema original. Considerando el sistema en su forma
canónica, es posible entonces realizar las siguientes definiciones:

Se considera una variable básica aquella que tiene el coeficiente 1 en una de

ecuaciones, y asume un valor nulo en las demás. Si esta condición es falsa, esta
entonces se considera una variable no básica. El sistema canónico (II)
discutido, contiene 1y 2como variables básicas y 3, 4e cincocomo no básicas.

10
 La solución básica de un sistema en su forma canónica se da haciendo que
todas las variables no básicas asuman un valor nulo. Para el sistema (II) 3=
4= 5= 0, 1= 6 e 2= 2 vuelve a la solución básica.
Cuando todas las variables asumen valores positivos, se dice que esta solución es
una solución básica viable. Para el sistema (II) dado, la solución básica es una
solución básica viable.

MÉTODO SIMPLEX
Es un procedimiento iterativo algebraico desarrollado por George B. Dantzig en
1947. Tiene como objetivo continuar a partir de una solución básica viable dada, presente
en un punto extremo, hacia otro punto adyacente que busca aumentar la función
objetivo, o en el peor de los casos mantenerla con el mismo valor.

El algoritmo se ejecuta hasta que se encuentra una solución óptima o se concluye

que el problema no tiene una solución óptima finita (Kolman; Beck, 1995). El
el algoritmo se basa en dos pasos principales según Kolman y Beck (1995):

1) Verificar si una determinada solución básica viable es una solución óptima;

2) Encontrar una solución básica factible con el mismo valor o un valor mayor
para la función objetivo.

Algoritmo Simplex Tabular

El método Simplex se utiliza en formato de tabla, que representa una forma

sucinta y organizada para la resolución de problemas. Para la creación de la tabla, es
necesario la identificación de los coeficientes de las variables y las constantes del lado derecho
da equação. La tabla llamada Tabla Simplex tiene el objetivo de simplificar de manera
exhibir de manera compacta el sistema de ecuaciones que conduce a una solución básica viable.

Diversos autores como Kolman y Beck (1995), Bazaraa, Jarvis y Sherali (2010)
Hillier y Leiberman (2006) presentan ligeras variaciones en la construcción de la Tabla
Sin embargo, no presentan cambios en la realización del algoritmo para la solución
de problemas. Para este estudio, se adoptó el modelo de Bazaraa, Jarvis y Sherali (2010),
que está presentada en la Tabla 1.

11
 Tabla 1 - Formato de la tabla en el método Simplex tabul

Soluciones Óptimas Múltiples

El hecho de que un problema de Programación Lineal pueda tener más de una solución,
puede llevar a casos donde se puede encontrar más de un resultado óptimo. El método
Simplex, al ser finalizado, puede indicar si se aplican otras soluciones óptimas. Si
¿existe algún? = 0 asociado a alguna variable no básica , entonces el modelo en
la cuestión tiene otra solución óptima viable donde es una variable básica.

Adaptaciones de Casos Específicos

En casos en que el modelo no sigue la forma estándar de la resuelta por el método

Es posible utilizar procesos para que se adapte y pueda ser

resuelto normalmente. Estas adaptaciones normalmente requieren que la tabla Simplex
pase por un proceso de solución en dos fases, que se pueden realizar a través del
Método Big-M.

Método Big-M
Este método se aplica a restrições que não respetan el modelo estándar a través de
de la utilización de restricciones funcionales, teniendo por lo tanto la siguiente forma:

12
 Ométodo Big-M se basa en una manipulación en el formato del modelo, creando
un problema artificial cuya solución óptima es la misma que la del problema original. Son

introducidas variables artificiales no negativas en las respectivas restricciones como si

fossem variables de folga. As variables criadas necessitam de um custo extremamente
alto, representado por el coeficiente en la función objetivo. El método Simplex para el
el problema artificial se ejecuta normalmente, sin embargo, se debe tener en cuenta la
necesidad de todos los se tornarán variables no básicas, por lo tanto, asumiendo
valores nulos. Em seguida, as colunas que representam os valores de deben ser
eliminadas de la tabla Simplex y el proceso continuado hasta que se encuentre una solución
óptima. Caso a solução óptima encontrada contenha uma variável artificial com valor
diferente de 0, o problema original é infactível.

DUALIDAD EN LA PROGRAMACIÓN LINEAL

Para cada problema de programação linear, esse considerado Primal, existe outro
problema llamado Dual. Este problema se genera directamente por los valores contenidos
no problema Primal original (BAZARAA; JARVIS; SHERALI, 2010). Asumiendo el
siguiente formato:

Los coeficientes de la función objetivo en el Primal asumen los valores del lado
derecho de las restricciones del problema dual;

Los valores del lado derecho del problema Primal se convierten en los coeficientes
de costo de la función objetivo en el problema Dual, es decir, generando una

variable por restricción;

Cada conjunto de coeficientes pertenecientes a la misma variable presente
en las restricciones del Primal, se convierte en una variable en el problema Dual;

Los signos de desigualdad están invertidos.

Figura 4–Paralelo entre los problemas Primal y Dual

13
 CONCLUSIÓN

Este trabajo tuvo la finalidad de actuar como una práctica de aprendizaje para los
principales conceptos y resoluciones de problemas de programación lineal. Este objetivo fue
concluido a través de la exposición de los conceptos referentes a los métodos Simplex,
Simplex Revisado y Dual Simplex para la resolución de problemas de programación lineal.
A través de esta conceptualización basada en una fundamentación teórica de sus
algoritmos, técnicas de resolución y adaptación de casos fue posible realizar resolución de
problemas que llevaron a la comprensión de los conceptos expuestos.

14
 REFERENCIAS BIBLIOGRÁFICAS

BAZARAA M. S.; JARVIS J. J; SHERALI H. D. Programación Lineal y

Flujos de Red. Virginia: Wiley, 2010. 4ª ed. 748 p. DANTZIG G. B. Programación en un
Estructura Lineal, Contralor, Fuerza Aérea de los Estados Unidos, Washington, 1948. HILLIER F.
S.; LIEBERMAN G. J,. Introducción a la investigación operativa. São Paulo: McGraw Hill,
2006. 8 ed. 829 p. KOLMAN B.; BECK R. E. Programación Lineal Elemental con
Aplicaciones, Estados Unidos: Elsevier, 1995, 449 p. MARINS F. A. S. Introducción a
investigación operacional. São Paulo: Cultura Académica, 2011. 176 p.

15