Programación

Lineal
Profesor: Integrantes:

Ing. Andrés Jiménez T.S.U. Estanga Jessuany C.I.:

18.454.181

T.S.U. Marcano Eduardo C.I.: 17.870.305

T.S.U. Marchese Giuseppe C.I.: 14.409.296

T.S.U. Molina Eva C.I.: 14.029.046

T.S.U. Sotillo Daniel C.I.: 19.940.623

Trayecto IV – Fase I

Sección: MM-01

El Tigre, Noviembre de 2023

 Introducción

La programación lineal es un campo de la programación matemática que se

dedica a maximizar o minimizar una función lineal, sujeta a restricciones
expresadas mediante un sistema de ecuaciones o inecuaciones lineales. La
función objetivo y las restricciones deben ser linealmente dependientes de las
variables. Este método se utiliza para optimizar situaciones prácticas, como la
ganancia de un fabricante con recursos limitados. La programación lineal es una
base cuantitativa para la toma de decisiones.

Los elementos que componen la programación lineal son los siguientes:

 Variables de decisión: Son las cantidades que se pueden controlar o elegir

para resolver el problema.

 Parámetros: Son los valores numéricos que se conocen y que no dependen

de las variables de decisión.

 Función objetivo: Es la expresión que se quiere optimizar, en función de las

variables de decisión y los parámetros.

 Restricciones: Son las condiciones que limitan las posibles soluciones del
problema, expresadas como ecuaciones o inecuaciones lineales.

 La programación lineal es una herramienta muy útil para optimizar

situaciones prácticas, como la ganancia de un fabricante con recursos
limitados.

La programación lineal permite hacer un uso más eficiente de los recursos, ya

que permite planificar y asignar los recursos de manera óptima. Esto permite
reducir los costos y aumentar la eficiencia de los procesos. Además, la
programación lineal permite resolver problemas complejos y encontrar soluciones
innovadoras. La programación lineal es una base cuantitativa para la toma de
decisiones y es una técnica esencial en la gestión organizacional.
Programación Lineal: Conceptos Básicos y Aplicaciones

Desde la optimización de recursos hasta la toma de decisiones

estratégicas, desempeña un papel crucial en numerosos campos. Haciendo un
ligero esbozo histórico, diré que la programación lineal, es una técnica que surgió
en el primer tercio del siglo XX, y fue desarrollada, aplicándola a situaciones
reales para resolver problemas relacionados, con la programación, el transporte y
logística en los años, de la segunda guerra mundial.

Su creador fue el matemático ruso L. Kantorovich, y su aplicación inicial

tuvo que ver con una optimización de los programas de fabricación. Sin embargo,
su aceptación, se extendió rápidamente a la economía y para 1950 el matemático
estadounidense George Dantzig creó el primer algoritmo. La programación lineal
en esencia, es una función compleja que intenta determinar a partir de un conjunto
de variables conocida, su influencia optima en determinados resultados.

Programación Lineal:

La programación lineal es una poderosa técnica matemática utilizada para

resolver problemas de optimización. Se basa en la idea de maximizar o minimizar
una función lineal sujeta a un conjunto de restricciones lineales. En otras palabras,
se trata de encontrar la mejor manera de asignar recursos limitados para lograr un
objetivo específico.

¿Cómo funciona?

Se basa en dos elementos clave: la función objetivo y las restricciones. La

función objetivo es una ecuación lineal que se busca maximizar o minimizar. Las
restricciones son desigualdades que limitan las variables de decisión. El objetivo
es encontrar los valores de las variables de decisión que optimizan la función
objetivo sin violar las restricciones.
Componentes de la Programación Lineal

Para comprenderla completamente, es importante conocer sus componentes

principales:

1. Función Objetivo

La función objetivo es el corazón de la Programación Lineal. Esta ecuación

lineal define lo que se busca maximizar o minimizar. Por ejemplo, en una empresa,
la función objetivo podría representar las ganancias que se desean maximizar o
los costos que se desean minimizar.

Coeficiente de la función:

Expresa la cantidad en la que el valor de la función objetivo cambiaría cuando

se modifica una unidad de una variable de decisión, viene dada por el coeficiente
de función objetivo correspondiente.

2. Variables de Decisión

Las variables de decisión son las incógnitas que queremos resolver en el

problema. Representan las cantidades que debemos determinar para alcanzar el
objetivo deseado. Estas variables pueden ser números de productos a producir,
horas de trabajo asignadas, entre otros.

3. Restricciones

Las restricciones son las limitaciones bajo las cuales operamos. Estas
limitaciones son representadas por ecuaciones lineales y definen las condiciones
que deben cumplirse. Por ejemplo, limitaciones de recursos, restricciones de
tiempo o restricciones de capacidad.
Restricciones no negativas.

Una condición obligatoria de este tipo de restricciones, es que tienen que

ser positivas con independencia, de que el objetivo de la función sea maximizar o
minimizar el valor. La solución óptima de un problema de programación lineal, es
aquella que satisfaga mejor las restricciones.

Esto quiere decir que, de todas las soluciones factibles, será óptima aquella
que, en el caso de una necesidad de maximización, el valor de la función objetivo
sea el mayor posible, o sea el máximo. Por el contrario, si nos encontramos ante
un problema de minimización, la solución más adecuada será aquella donde la
función objetivo ofrezca el mínimo.

Recursos disponibles

Constituyen los materiales, recursos, o elementos que participan en la

ecuación y sobre los que se aplica la misma.

Coeficientes tecnológicos

Cuando intentamos prever el futuro a través de la programación lineal, es

importante considerar las limitaciones técnicas que nos impone la realidad objetiva
y el entorno. Los coeficientes tecnológicos, son elementos de referencia que
conocemos y sobre los que se mueve el fenómeno que necesitamos estimar.

La estructura de un problema de programación lineal debería ser algo como esto:

Maximize 20* vd1 + 18*vd2; subject to

0.25*vd1 + 1*vd2 ≤60

1.40*vd1 + 0.5*vd2 ≤ 90 where vd1 & vd2 ≥ 0

Aquí podemos identificar los diferentes componentes:

 vd1 y vd2 son las variables de decisión

 Maximize 20* vd1 + 18*vd2 es la función objetivo
 20* vd1 y 18*vd2 son los coeficientes de la función
 0.25*vd1 + 1*vd2 ≤ 60 la primera restricción
 1.40*vd1 + 0.5*vd2 ≤ 90 segunda restricción
 vd1 & vd2 ≥ 0 restricción negativa
 0.25, 1, 1.40, 0.5 son los coeficientes tecnológicos
 65, 90 es la disponibilidad de recursos

Elementos importantes de la Programación lineal

Potenciación

Partimos de considerar que las variables de decisión, siempre tienen una

potencia de uno.

La condición critica

Para poder aplicar un problema de programación lineal, es necesario tener

definidas: la función objetivo, la disponibilidad de recursos y las variables de
decisión positivas relacionadas entre sí.

Dualidad

Todo problema de programación lineal, puede convertirse a su par

correspondiente, capaz de dar la misma solución factible de la función objetivo.
Esto lo puede hacer de modo automático el programa con el que trabajemos, pero
conocer su esencia es importante.
 Cuando se trata, por ejemplo, de un problema de maximización, por lógica
todas las restricciones asociadas con su función objetivo serán del tipo «menor
que igual a» la disponibilidad de recursos dada, (podría ser solo «igual a», en el
caso de una restricción en particular restringida)

Si eso no sucediese y alguna restricción fuera del tipo “mayor que igual a” lo
recomendable es convertir la solución a una forma canónica (multiplicar por un
“menos”) para que la restricción del problema de maximización se transforme en
“menor que igual a”.

Por oposición si fuera un problema de minimización, entonces todas las

restricciones asociadas con la función objetivo deben tener restricciones «mayor
que igual a» a la disponibilidad de recursos considerada, a menos que exista
alguna restricción que particularmente no esté restringida (tipo “igual a”), lo
adecuado es multiplicar por -1, para convertirlas.

Antes de la dualidad

Antes de proceder con un ejercicio de dualidad es necesario que las

variables de decisión sean igual o mayor que cero, de no ser así necesitan ser
transformadas de forma canonical. En Python, podemos trabajar los problemas de
programación lineal con Ipsolve.

Por último, decir que la programación lineal, se basa en la creación de

modelos cuando el problema que necesitamos resolver tiene solo funciones
lineales, esto es:

Tenemos variables de decisión conocidas y queremos saber que influyen

en un problema dado.

Dicho de otro modo: el concepto programación lineal no se enmarca dentro

de la programación de computadoras, sino que se refiere a escoger una vía de
solución cuando el modelo matemático del problema contiene solo funciones
lineales

4. Solución Óptima

La solución óptima es el conjunto de valores de las variables de decisión que

maximizan o minimizan la función objetivo sin infringir ninguna restricción. En
esencia, es la respuesta al problema de Programación Lineal.

¿Por Qué Programación Lineal?

Ahora que comprendemos los componentes básicos, surge la pregunta:

¿Por qué utilizar Programación Lineal?

I. Optimización de Recursos

La Programación Lineal es esencial para la optimización de recursos. En la

gestión empresarial, ayuda a asignar eficientemente recursos como mano de obra,
tiempo y capital para maximizar los beneficios o minimizar los costos.

II. Toma de Decisiones Estratégicas

En situaciones complejas, la Programación Lineal puede ayudar en la toma de

decisiones estratégicas. Por ejemplo, en la cadena de suministro, puede
determinar la mejor forma de distribuir productos para reducir costos de transporte.

III. Planificación de Producción

En la industria manufacturera, la Programación Lineal es fundamental para la

planificación de la producción. Permite determinar la cantidad óptima de productos
a fabricar para satisfacer la demanda y minimizar los costos.
IV. Diseño de Redes de Transporte

En logística y transporte, la Programación Lineal se utiliza para diseñar redes

de transporte eficientes. Esto puede tener un impacto significativo en la reducción
de costos de envío y tiempos de entrega.

V. Aplicaciones en Economía

También se aplica en economía para analizar la asignación de recursos

escasos en la sociedad y en la toma de decisiones gubernamentales.

Ejemplos de Programación Lineal

 Problema de Mezcla

Un ejemplo clásico es el problema de mezcla en la industria química. Una

empresa debe decidir la cantidad de ingredientes a utilizar en la fabricación de un
producto para maximizar las ganancias, cumpliendo con las restricciones de
disponibilidad de ingredientes y calidad del producto.

 Problema de Transporte

En el sector logístico, se utiliza para resolver el problema de transporte. Consiste

en determinar la cantidad de productos que deben enviarse desde múltiples
fuentes a múltiples destinos, minimizando los costos de transporte total.

 Planificación de la Producción

En una fábrica, la Programación Lineal puede utilizarse para planificar la

producción de diferentes productos, teniendo en cuenta la capacidad de
producción, la demanda del mercado y los recursos disponibles.
  Cartera de Inversiones

En finanzas, la Programación Lineal puede aplicarse en la construcción de una

cartera de inversiones. El objetivo es maximizar el rendimiento esperado mientras
se gestionan los riesgos.

Herramientas de Software

La Programación Lineal se ha vuelto más accesible gracias a las herramientas

de software. Algunos programas populares incluyen:

 Solver: Una extensión de Microsoft Excel que permite resolver problemas

de Programación Lineal.
 IBM CPLEX: Una herramienta de optimización que se utiliza en una
variedad de industrias.
 Lindo: Un software especializado en optimización lineal y no lineal.

Limitaciones de la Programación Lineal

Si bien es una herramienta poderosa, tiene sus limitaciones. No es adecuada para

resolver todos los tipos de problemas. Algunas de las limitaciones incluyen:

 Suposición de linealidad: La Programación Lineal asume que todas las

relaciones son lineales, lo que puede no ser cierto en todos los casos.
 Soluciones discretas: No puede manejar soluciones que requieran valores
discretos, como la producción de unidades completas de productos.
 No considera riesgos: No tiene en cuenta la incertidumbre o los riesgos
asociados a las decisiones.
Programación Lineal en la Vida Cotidiana

También tiene aplicaciones en la vida cotidiana que quizás no te hayas dado

cuenta:

1. Planificación de Dietas

Cuando planificas una dieta para cumplir con ciertas restricciones calóricas y
nutricionales mientras maximizas la satisfacción del paladar, estás resolviendo un
problema de Programación Lineal.

2. Presupuesto Personal

La Programación Lineal se utiliza de manera implícita cuando gestionas tu

presupuesto personal. Debes asignar tu dinero limitado a diferentes categorías de
gastos de manera óptima para satisfacer tus necesidades y deseos.

3. Viajes y Rutas

Al planificar un viaje o una ruta de conducción, buscas la manera más eficiente de

llegar a tu destino minimizando tiempo y gastos de transporte.

Método Simplex

El Método Simplex es un método analítico de solución de problemas

de programación lineal, capaz de resolver modelos más complejos que los
resueltos mediante el método gráfico, sin restricción en el número de variables y
con una mayor capacidad de análisis de sensibilidad.

El Método Simplex es un método iterativo que permite ir mejorando la

solución en cada paso. La razón matemática de esta mejora radica en que el
método consiste en caminar del vértice de un poliedro a un vértice vecino de
manera que aumente o disminuya (según el contexto de la función objetivo, sea
maximizar o minimizar). Dado que el número de vértices que presenta un poliedro
solución es finito, en la medida en que se pueda satisfacer el conjunto de
restricciones, siempre se hallará como mínimo una solución óptima.

Este popular método fue creado en el año de 1947 por el estadounidense

George Bernard Dantzig y el ruso Leonid Vitalievich Kantorovich, con el ánimo de
crear un algoritmo capaz de solucionar problemas de m restricciones y n variables.
Simplex es considerado como uno de los algoritmos más importantes de la
historia, y hoy por hoy sigue siendo la base en la que se fundamentan la mayor
parte de solucionadores de modelos de programación lineal.

La importancia de la teoría de matrices en el Método Simplex es

fundamental, dado que el algoritmo se basa en dicha teoría para la resolución de
sus problemas. De tal manera que veremos previamente, en qué consiste una
matriz identidad.

¿Qué es una matriz identidad?

Una matriz puede definirse como una ordenación rectangular de elementos, (o

listado finito de elementos), los cuales pueden ser números reales o complejos,
dispuestos en forma de filas y de columnas.
La matriz idéntica o identidad es una matriz cuadrada (que posee el mismo
número tanto de columnas como de filas) de orden n que tiene todos los
elementos diagonales iguales a uno (1) y todos los demás componentes iguales a
cero (0), se denomina matriz idéntica o identidad de orden n, y se denota por:

Consideraciones importantes al utilizar el Método Simplex

 Variables de holgura y exceso

El Método Simplex trabaja basándose en ecuaciones y las restricciones

iniciales que se modelan mediante programación lineal no lo son, para ello hay
que convertir estas inecuaciones en ecuaciones utilizando unas variables
denominadas de holgura y exceso relacionadas con el recurso al cual hace
referencia la restricción y que en el tabulado final representa el “Slack or
surplus” al que hacen referencia los famosos programas de resolución de
investigación de operaciones, estas variables adquieren un gran valor en el
análisis de sensibilidad y juegan un rol fundamental en la creación de la matriz
identidad, base del Simplex.

Estas variables suelen estar representadas por la letra “S”, se suman (del
lado izquierdo de la restricción) si la restricción es de signo “ <= “ y se restan (del
lado izquierdo de la restricción) si la restricción es de signo “>=”.
Por ejemplo:
 Una consideración importante consiste en que el sistema de restricciones
debe ser restrictivo, y esto significa solo una cosa: El lado derecho de las
restricciones no puede contener variables, solo un número mayor o igual a 0.
En el caso en que, por ejemplo, tengamos la siguiente restricción:
 2X1 + 1X2 + 1X3 + 2X4 <= -24
Procederemos, primero a convertir la desigualdad en igualdad añadiendo
una variable de holgura:

2X1 + 1X2 + 1X3 + 2X4 + 1S1 = -24

Segundo, a multiplicar ambos lados de la igualdad por (-1), de tal manera

que el lado derecho cumpla con la condición: positivos mayores o iguales a 0.

-2X1 – 1X2 – 1X3 – 2X4 – 1S1 = 24

De esta manera lograríamos estandarizar esta restricción para nuestro

algoritmo Simplex.

Variable artificial / Método de la “M”

Una variable artificial es un truco matemático para convertir inecuaciones

“>=” en ecuaciones, o cuando aparecen igualdades en el problema original, la
característica principal de estas variables es que no deben formar parte de la
solución, dado que no representan recursos. El objetivo fundamental de estas
variables es la formación de la matriz identidad.

Estas variables se representan por la letra “A”, siempre se suman a las

restricciones, su coeficiente es M (por esto se le denomina Método de la M
grande, donde M significa un número demasiado grande muy poco atractivo para
la función objetivo), y el signo en la función objetivo va en contra del sentido de la
misma, es decir, en problemas de Maximización su signo es menos (-) y en
problemas de Minimización su signo es (+), repetimos con el objetivo de que su
valor en la solución sea cero (0).
Variables no negativas

Todas las variables del método Simplex deben cumplir con la condición de
no negatividad. Cuando existe alguna variable del modelo que no tiene restricción
de no-negatividad, se debe reemplazar por la diferencia de dos variables positivas.
Por lo tanto, en el modelo donde aparezca esta variable, se debe cambiar por:

Sea Xi una variable sin restricción de no-negatividad (puede ser mayor, igual
o menor que cero), se debe cambiar por:

(Xi(+) – Xi(-)) donde Xi(+) >= 0 y Xi(-) >= 0

Este tipo de variables son poco comunes, y se utilizan mucho en la

programación por metas.

Método Simplex paso a paso

Lo primero que diremos es que la resolución de un problema mediante

Método Simplex manual carece de sentido práctico, y solo se utiliza hoy por hoy
con fines académicos. Dicho de otro modo, para que el estudiante reconozca el
funcionamiento del algoritmo.

Dicho esto, veamos el problema objeto de estudio.

El problema

La empresa el SAMÁN Ltda. Dedicada a la fabricación de muebles, ha

ampliado su producción en dos líneas más. Por lo tanto actualmente fabrica
mesas, sillas, camas y bibliotecas. Cada mesa requiere de 2 piezas rectangulares
de 8 pines, y 2 piezas cuadradas de 4 pines. Cada silla requiere de 1 pieza
rectangular de 8 pines y 2 piezas cuadradas de 4 pines, cada cama requiere de 1
pieza rectangular de 8 pines, 1 cuadrada de 4 pines y 2 bases trapezoidales de 2
pines y finalmente cada biblioteca requiere de 2 piezas rectangulares de 8 pines, 2
bases trapezoidales de 2 pines y 4 piezas rectangulares de 2 pines. Cada mesa
cuesta producirla $10000 y se vende en $ 30000, cada silla cuesta producirla $
8000 y se vende en $ 28000, cada cama cuesta producirla $ 20000 y se vende en
$ 40000, cada biblioteca cuesta producirla $ 40000 y se vende en $ 60000. El
objetivo de la fábrica es maximizar las utilidades.

Paso 1: Modelación mediante programación lineal

Variables:
X1 = Cantidad de mesas a producir (unidades)
X2 = Cantidad de sillas a producir (unidades)
X3 = Cantidad de camas a producir (unidades)
X4 = Cantidad de bibliotecas a producir (unidades)
Restricciones:
2X1 + 1X2 + 1X3 + 2X4 <= 24
2X1 + 2X2 + 1X3 <= 20
2X3 + 2X4 <= 20
4X4 <= 16
Función Objetivo:
ZMAX = 20000X1 + 20000X2 + 20000X3 + 20000X4

Paso 2: Estandarizar el modelo

Este paso consiste en cumplir las consideraciones del modelo para que se
ajuste al método Simplex:

 Convertir inecuaciones en ecuaciones

 Pasar, de ser necesario, el lado derecho de las restricciones a números

positivos.

 Verificar que todas nuestras variables sean de naturaleza no-negativa.

Convertir las inecuaciones en igualdades (Variables de Holgura y Exceso)

En este paso el objetivo es asignar a cada recurso una variable de Holgura, dado
que todas las restricciones son «<=».

2X1 + 1X2 + 1X3 + 2X4 + 1S1 + 0S2 + 0S3 + 0S4 = 24

2X1 + 2X2 + 1X3 + 0X4 + 0S1 + 1S2 + 0S3 + 0S4 = 20
0X1 + 0X2 + 2X3 + 2X4 + 0S1 + 0S2 + 1S3 + 0S4 = 20
0X1 + 0X2 + 0X3 + 4X4 + 0S1 + 0S2 + 0S3 + 1S4 = 16
En cuyo caso:

S1 = Cantidad de piezas rectangulares de 8 pines que no se utilizarán (holgura)

S2 = Cantidad de piezas cuadradas de 4 pines que no se utilizarán (holgura)
S3 = Cantidad de bases trapezoidales que no se utilizarán (holgura)
S4 = Cantidad de piezas rectangulares de 2 pines que no se utilizarán (holgura)
De esta manera podemos apreciar una matriz identidad (n = 4), formado por las
variables de holgura las cuales solo tienen coeficiente 1 en su respectivo recurso,
por ejemplo, la variable de holgura «S1» solo tiene coeficiente 1 en la restricción
correspondiente al recurso 1.
 La función objetivo no sufre variaciones, dado que es un problema de
maximización (más adelante veremos qué pasaría si se tratara de un problema de
minimización).

ZMAX = 20000X1 + 20000X2 + 20000X3 + 20000X4

Paso 3: Definir la solución básica inicial

El Método Simplex parte de una solución básica inicial para realizar todas
sus iteraciones, esta solución básica inicial se forma con las variables cuyo
coeficiente es 1 en la matriz identidad.

1S1 = 24
1S2 = 20
1S3 = 20
1S4 = 16

Esto en términos de solución significaría que todos los recursos

permanecerían ociosos, y suena lógico, por lo menos suena como un buen punto
de partida: inicialmente no se usa ningún recurso.

La tabla simplex

El Método Simplex se hace un poco más sencillo (y esto es mucho decir si

estamos abordando una resolución manual), mediante el uso de tabulados
simplex.
Cada quien puede agregar o retirar elementos del tabulado, de acuerdo a su
utilidad, yo particularmente recomiendo este tabulado base, y luego iré
incorporando elementos con un fin pedagógico:
 Variable Solución = Todo parte de definir las variables que harán parte de la
solución. En esta columna se consigna la solución básica inicial, y a partir
de esta en cada iteración se van incluyendo las variables que formarán
parte de la solución final.
 Solución: (segundo término) = En esta fila se consigna el segundo término
de la solución, es decir, el coeficiente de las variables de la
columna variable solución, lo más adecuado es que estas se consignen de
manera ordenada, tal cual como se escribieron en la definición de
restricciones.
 Cb = En esta columna se consigna el valor que tiene la variable que se
encuentra a su derecha «Variable solución» en la función objetivo.
 Cj = Dado que en cada columna se registra una variable (título de la
columna), la fila «Cj» hace referencia al coeficiente que tiene cada una de
ellas en la función objetivo en la función objetivo.
 Zj = En esta fila se consigna la contribución total, es decir la suma de los
productos entre el término de cada columna y Cb.
 Cj – Zj = En esta fila se realiza la diferencia entre la fila Cj y la fila Zj, su
significado es un «Shadow price», es decir, la utilidad que se deja de recibir
por cada unidad de la variable correspondiente que no forme parte de la
solución. Y representa también el precio dual de las restricciones
representadas por las variables de holgura y exceso.
Tabulado con la solución inicial:

Nota: La base del Simplex es el orden y la organización de la información.

 Paso 4: Realizar las iteraciones necesarias

Ya lo dijimos, el Método Simplex es un algoritmo iterativo, y por ende, los

criterios para pasar de una iteración a otra son definitivos.

Recordemos algo: El Método Simplex consiste en realizar intentos o

recorridos mientras el modelo va de un vértice del poliedro objetivo a otro. Cada
recorrido de un vértice a otro estará representado por un tabulado de Simplex o
iteración.

¿Qué es lo que pasa en cada iteración? Básicamente una variable entra a

la solución inicial, por ende, una variable sale de la solución inicial, y al final de la
iteración nos preguntamos si hemos hallado o no la solución óptima.

El procedimiento a seguir es el siguiente:

1. Evaluar que variable entrará y cual saldrá de la solución óptima:

En nuestro caso de ejemplo, todos los Cj – Zj son iguales a 20000, por lo

tanto, la decisión debe tomarse de forma arbitraria, es decir, puede elegirse
cualquiera como variable de entrada. Elegiremos la variable X4 ¿Por qué? Porque
sí, lo estamos haciendo de forma arbitraria para romper el empate.
 Dado que X4 es la variable de entrada, los valores que se encuentran en su
columna pasarán a ser A. Y B siempre será la columna solución. Veamos:

En el caso de la columna temporal A cuando el valor es igual o menor

que 0 no se considera para el cálculo de B/A. Por ejemplo, en la fila #2 el valor
de A era igual a 0, por lo tanto, no se considera para el cálculo de B/A.

Dado lo anterior, la elección de la fila saliente se da de acuerdo al menor valor de

la columna temporal B/A, es decir, entre los valores 20 – 10 – 4. (Tal como
observamos en la imagen anterior). Así entonces, la variable que sale será S4.
2. El hecho de que una variable distinta forme parte de las variables solución
implica una serie de cambios en el tabulado Simplex, cambios que se explicarán a
continuación.

El valor de la intersección entre la columna de la variable que entra y la fila

de la variable que sale, se denomina a (minúscula). Veamos en este caso cuál es
el a.

A continuación, todos los valores de la fila de salida se dividen por a.

Como resultado tendremos los valores correspondientes a la nueva fila, en

este caso la fila X4.
  Lo siguiente corresponde a registrar los nuevos valores de cada fila.

Recordemos que el valor de a depende de la intersección de la columna entrante y

cada fila. En este caso vamos a registrar los nuevos valores de la fila # 1,
correspondiente a la variable S1. Por lo tanto, a será equivalente a 2. Veamos:

Uno de los pasos más confusos en Simplex es el que se detallará a

continuación, sin embargo, es cuestión de prestar suma atención al procedimiento.
La fila de la nueva variable entrante:

Deberá multiplicarse por el valor de -a (Recordemos que el valor de a para

la fila #1 es 2). Es decir, -a es igual a -2. Como resultado tendremos una fila
temporal, podemos denominarla – si así lo queremos – por la iteración y la fila, es
decir, estamos en la primera iteración, y abordando la fila #1. Su nombre será fila
temporal I1-f1 (Esto es algo que me he inventado, espero no complicarlo).
 Estos valores, deben sumarse con los valores de la fila 1 que se encontraba
en la tabla anterior (S1). Veamos:

Como resultado tendremos los valores correspondientes a la fila1 de la

primera iteración, en este caso la fila S1.

En el caso de la fila 2, recordemos que el valor de a corresponde a 0. Así

que los valores pasan tal cual como se encontraban en la tabla anterior.
Veamos qué pasa con la tercera fila:

Veamos cómo queda la tabla:

Una vez registrados los valores de toda la tabla, podemos calcular el valor
de Zj y Cj – Zj.
 Esta misma operación se efectúa para toda la tabla; es decir, cada columna
deberá multiplicarse por Cb. Es recomendable utilizar otra tabla para registrar
dichos valores. Al final, deberá sumar los sumar los valores de cada columna y
totalizarlos en Zj. A esa tabla le llamaremos: Tabla de productos de Cb:

El objetivo de esta tabla anterior es determinar los valores de Zj (Sumatoria

de columnas) y Cj-Zj (Diferencia entre la fila Cj y la fila Zj), si ya los tenemos,
podemos regresar a nuestra tabla de variables:
 De esta manera se culmina la primera iteración, este paso se repetirá
cuantas veces sea necesario y solo se dará por terminado el método según los
siguientes criterios.

Maximizar Minimizar

Cuando todos los Cj – Zj sean <= 0 Cuando todos los Cj – Zj sean >= 0

 Continuamos con las iteraciones para lo cual tenemos que repetir los
pasos anteriores.

En esta última iteración podemos observar que se cumple con la

consigna Cj – Zj <= 0, para ejercicios cuya función objetivo sea «Maximizar», por
ende, hemos llegado a la respuesta óptima.

X2 = 7
X3 = 6
X4 = 4
S1 = 3 (Cantidad de piezas rectangulares de 8 pines sin utilizar =3)
Función Objetivo: $ 340000

Sin embargo, una vez finalizado el Método Simplex se debe observar una
matriz identidad en el rectángulo determinado por las variables de decisión (líneas
punteadas), el hecho de que en este caso no se muestre la matriz identidad
significa que existe una solución óptima alterna.
 La manera de llegar a la otra solución consiste en alterar el orden en que
cada una de las variables entró a la solución básica, recordemos que el proceso
fue decidido al azar debido a la igualdad en el Cj – Zj del tabulado inicial. Aquí les
presentamos una de las maneras de llegar a la otra solución.

Podemos observar cómo existe una solución óptima alternativa en la cual la

combinación de variables es distinta y existe un menor consumo de recursos,
dado que el hecho de que se encuentre la variable «S1» en la solución óptima con
un coeficiente de «3» significa que se presenta una holgura de 3 unidades del
recurso (pieza rectangular de 8 pines).
X1 = 3 (Cantidad de mesas a producir = 3)
X2 = 4 (Cantidad de sillas a producir = 4)
X3 = 6 (Cantidad de camas a producir = 6)
X4 = 4 (Cantidad de bibliotecas a producir = 4)
Con una utilidad de: $ 340000

Problemas de minimización con el Método Simplex

Para resolver problemas de minimización mediante el algoritmo simplex

existen dos procedimientos que se emplean con regularidad.

 El primero, que a mi juicio es el más recomendable se basa en un

artificio aplicable al algoritmo fundamentado en la lógica matemática que
dicta que «para cualquier función f(x), todo punto que minimice a f(x)
maximizará también a – f(x)». Por lo tanto, el procedimiento a aplicar es
multiplicar por el factor negativo (-1) a toda la función objetivo.

A continuación, se resuelve el algoritmo como un problema de

maximización.

 El segundo procedimiento, el cual pretende conservar la minimización

consiste en aplicar los criterios de decisión que hemos esbozado con
anterioridad, en los casos de la variable que entra, que sale y el caso en
el que la solución óptima es encontrada. Aquí recordamos los
procedimientos según el criterio dado el caso «minimizar».
 Forma estándar del modelo de progresión lineal.

Definición: Se dice que un problema de programación lineal está en forma

estándar si

1. Todas las restricciones son ecuaciones.

2. Todas las variables son no negativas.
3. La función objetivo puede pedirse que se optimice maximizándola, o
minimizándola.

De esta manera, un problema en forma estándar se ve como sigue:

En notación matricial, el problema en forma canónica queda expresado de

la siguiente manera:
en donde c, x, A y b≥0 son como se mencionó antes.

Así como cualquier problema de programación lineal puede ser expresado

en forma canónica, también cualquier problema de programación lineal puede
expresarse en forma estándar. Una restricción del tipo ≤ (≥) puede ser
transformada en una ecuación sumando (o restando) una variable no negativa que
recibe el nombre de variable de holgura.

Ejemplo de pasar un problema a forma estándar

Retomemos el problema ejemplo anterior, antes de expresarlo en forma

canónica.
Definición de variables de Decisión.

 Las variables de decisión

 Similar a la relación que existe entre objetivos específicos y
objetivo general, se comportan las variables de decisión respecto a la función
objetivo, puesto que estas se identifican partiendo de una serie de preguntas
derivadas de la pregunta fundamental. Las variables de decisión, son en teoría,
factores controlables del sistema que se está modelando, y como tal, estas
pueden tomar diversos valores posibles, de los cuales se precisa conocer su valor
óptimo, que contribuya con la consecución del objetivo de la función general del
problema.

 Las restricciones

Cuando hablamos de las restricciones en un problema de programación lineal,

nos referimos a todo aquello que limita la libertad de los valores que pueden tomar
las variables de decisión.

La mejor manera de hallarlas consiste en pensar en un caso hipotético en el

que decidiéramos darles un valor infinito a nuestras variables de decisión, por
ejemplo, ¿qué pasaría si en un problema que precisa maximizar sus utilidades en
un sistema de producción de calzado decidiéramos producir una cantidad infinita
de zapatos? Seguramente ahora nos surgirían múltiples interrogantes, como, por
ejemplo:

 ¿Con cuánta materia prima cuento para producirlos?

 ¿Con cuánta mano de obra cuento para fabricarlos?

 ¿Pueden las instalaciones de mi empresa albergar tal cantidad de

producto?

 ¿Podría mi fuerza de mercadeo vender todos los zapatos?

 ¿Puedo financiar tal empresa?

Pues bueno, entonces habríamos descubierto que nuestro sistema presenta

una serie de limitantes, tanto físicas, como de contexto, de tal manera que los
valores que en un momento dado podrían tomar nuestras variables de decisión se
encuentran condicionados por una serie de restricciones.

 La función objetivo

La función objetivo tiene una estrecha relación con la pregunta general que se
desea responder. Si en un modelo resultasen distintas preguntas, la función
objetivo se relacionaría con la pregunta del nivel superior, es decir, la pregunta
fundamental. Así por ejemplo, si en una situación se desean minimizar los costos,
es muy probable que la pregunta de mayor nivel sea la que se relacione con
aumentar la utilidad en lugar de un interrogante que busque hallar la manera de
disminuir los costos.

¿Qué es una Solución Básica Factible en Programación Lineal?

 En Programación Lineal una Solución Básica Factible (SBF) es aquella que
además de pertenecer a la región o área factible del problema se puede
representar a través de una solución factible en la aplicación del Método
Simplex satisfaciendo las condiciones de no negatividad.

En este contexto una solución básica factible corresponderá a uno de los

vértices del dominio de factibilidad cuya coordenada o solución se puede
representar a través de un conjunto de restricciones activas para el modelo.

Para desarrollar el concepto anterior consideremos el siguiente problema de

optimización matemática (lineal):
 La resolución gráfica del problema anterior haciendo uso de GeoGebra se
presenta en el siguiente gráfico:

El área achurada corresponde al dominio de factibilidad del problema,

identificándose en particular 5 vértices que hemos llamado
arbitrariamente A, B, C, D y E.

La solución óptima del modelo lineal se alcanza en el vértice

C donde X=100 e Y=350 con valor óptimo V(P) = 3.100. Notar que dicha solución
se puede obtener a través de la resolución de un sistema de ecuaciones con las
restricciones 1 y 3 (R1 y R3) en igualdad.

En consecuencia, el vértice C además de ser una solución básica factible es

una solución básica factible óptima.

En cuanto a los vértices A, B, D y E son soluciones básicas factibles (no

óptimas) debido a que en la aplicación del Método Simplex al menos una variable
no básica tendrá costo reducido negativo (lo que permitirá mejorar el actual valor
de la función objetivo).

La tabla a continuación es la que se obtiene al llevar al problema a su forma

estándar, agregando S1, S2 y S3 como variables de holgura de las restricciones 1,
2 y 3, respectivamente (R1, R2 y R3).

Ambas variables no básicas (iniciales) X e Y tienen costo reducido negativo (-3 y -

8) por tanto X=0 e Y=0 que si bien es una solución básica factible (vértice A) no es
solución óptima.

Para continuar la demostración realizaremos una iteración del Método

Simplex incorporando la variable Y a la base (criterio costo reducido “más
negativo”) y donde el mínimo cociente Min {1.600/4; 1.700/2; 350/1}=350 ==>
S3 deja la base:
 La solución básica factible ahora es X=0 e Y=350 (vértice B), sin embargo,
el costo reducido de la variable X sigue siendo negativo y por tanto aún no nos
encontramos en el óptimo. En consecuencia, X entra a la base y obtenemos el
mínimo cociente: Min {200/2; 1.000/6} =100 ==> S1 deja la base:

Finalmente se alcanza la solución óptima (solución básica factible óptima)

con X=100 e Y=350 (vértice C) donde todas las variables no básicas (S1 y S3)
tienen costos reducido mayor o igual a cero, cumpliendo con el criterio de
optimalidad.

¿Qué sucede con los vértices D y E? También son soluciones básicas

factibles (no óptimas) que se podrían encontrar por ejemplo incorporando en
primera instancia (tabla inicial) a la variable X a la base. De esta forma se debería
alcanzar el vértice E luego de una iteración y el vértice D en una segunda
iteración.
 Notar que también existen otras soluciones factibles (no básicas) como, por
ejemplo, X=100 e Y=100 que pertenecen al dominio de soluciones factibles, pero
no se puede representar a través de la resolución de un sistema de ecuaciones.

Variables de holgura

Las variables de holgura permiten determinar los excedentes de las

restricciones que podrían ser empleados en otros fines sin que la solución óptima
se altere. Las variables de holgura permiten convertir las desigualdades de las
restricciones en igualdades, lo cual llega a representar el sobrante de las
disponibilidades de cada recurso; en el caso que se desarrolla como ejemplo es la
capacidad de horas máquina en cada proceso o departamento.

En el ejemplo que se desarrolla.

Las restricciones lineales de forma:

Agregando una nueva variable no negativa al lado izquierdo de la

desigualdad se pueden convertir en ecuaciones, esta variable es numéricamente
igual a la diferencia entre el lado izquierdo y derecho de la desigualdad. Por lo cual
las desigualdades quedan con vértices en las siguientes ecuaciones:

Las variables de holgura S1 y S2 muestran los excedentes de tiempo en la

capacidad no utilizada en los procesos I y II respectivamente.

En la solución óptima determinada por método gráfico y algebraico, cuando:

 Las variables de holgura son:

Por tanto, las variables de holgura:

 S1 = 0
 S2 = 0

Significa que no se tienen tiempo ocioso en los procesos I ni II.

Variables Excedentarias

Las variables excedentarias permiten determinar los excedentes de las

restricciones que podrían ser empleados en otros fines sin que la solución óptima
se altere.
 Las variables excedentarias permiten convertir las desigualdades de las
restricciones en igualdades, lo cual llega a representar el sobrante de las
disponibilidades de cada recurso.

En el caso que se desarrolla, cada 100 metros de paño deben tener un

contenido de por lo menos 45 kilogramos de lana y 30 kilogramos de poliéster, por
tanto, las restricciones lineales de forma:

(0,60) (x1) + (0,30) (x2) >= 45

(0,10) (x1) + (0,50) (x2) >= 30

Agregando una nueva variable negativa al lado izquierdo de la desigualdad,

se pueden convertir en ecuaciones. Numéricamente esta variable es igual a la
diferencia entre el lado izquierdo y derecho de la desigualdad. Por lo cual, las
desigualdades quedan convertidas en las siguientes ecuaciones o igualdades:

Las variables excedentarias –t1 y –t2 muestran el exceso en el uso de

materiales fibra L y fibra M.

En la solución óptima, determinada por el método gráfico y algebraico

cuando:

 x1 = 50
 x2 = 50

Las variables excedentarias son:

 Por tanto, las variables excedentarias:

 t1 = 0
 t2 = 0

Significa que no se tienen exceso de uso de materiales fibra L y fibra M.

Variables Irrestrictas.

Son las limitantes en los valores de los niveles de las diferentes actividades
(variables). Las restricciones mas comunes son de 6 tipos, las cuales se listan a
continuación:

1. Restricción de capacidad: limitan el valor de las variables debido a la

disponibilidad de horas – hombre, horas – maquinas, espacio, etc.
2. Restricción de mercado: Surge de los valores máximos y mínimos en las
ventas o el uso del producto o actividad a realizar
3. Restricción de entradas: Son limitantes debido a la escasez de materias
primas, mano de obra, dinero, etc.
 4. Restricción de calidad: Son las restricciones que limitan las mezclas de
ingredientes, definiendo usualmente la calidad de los artículos a
manufacturar.
5. Restricciones de balance de material: estas son las restricciones que
definen las salidas de un proceso en función de las entradas, tomando en
cuenta generalmente cierto porcentaje de merma o desperdicio.
6. Restricciones internas: Son las que definen a una variable dada, en la
formulación interna del problema, un ejemplo tipo, es el de inventario.

Casos especiales de Programación lineal.

 Problemas De Minimización
 Recursos Negativos
 Variables No Positivas
 Restricciones en forma de Igualdad
 Restricciones de la forma ≥

CASO: Minimizar. Si un problema es de la forma MIN Z =…….Este caso se

puede resolver de dos maneras:

1. Se puede resolver directamente, solo que para detenerlo (Optimo) se hace

cuando todos los Cj – Zj ≥ 0.
2. Se puede convertir en un problema de maximización, multiplicando la
función objetivo por -1. La solución final se reconvierte a su situación
original.
 CASO: Recursos Negativos Si alguna restricción es de la forma: x + y =-b, se
procede así: Se multiplica la restricción por -1. Se agregan las variables de holgura
necesarias y se resuelve normalmente.

CASO: Variables no Positivas pueden darse dos posibilidades:

- Variable Negativa. En este caso primero se cambia por una Positiva

equivalente a la anterior multiplicada por -1. Se resuelve el problema con la
nueva variable. Al finalizar se hace el cambio correspondiente.

- Variable Irrestricta en Signo Ocurre cuando la variable pude tomar cualquier

valor real. En este caso se cambia la variable por la diferencia entre dos
variables positivas las que se introducen en el modelo y se resuelve
normalmente, al finalizar se reconvierte.

CASO: Restricciones con igualdad (=). Se agrega una variable Artificial.

CASO: Restricciones de la forma (≥). Se resta una Superflua (S) y se suma

una Artificial (A).

Cuando se agrega una variable artificial el problema se puede resolver de dos

maneras:

 Método de la Gran M
 Método de las dos Fases

El método de la gran M

Problemas de Maximización: Se coloca en la Función Objetivo el termino –

MA, donde M en un número lo suficientemente grande para garantizar que A debe
ser cero en la Solución final, de lo contrario se hace Minino.
 Problemas de Minimización: se coloca el termino +MA, para garantizar que
sea mínimo.

El método de 2 fases

Cuando aparecen variables artificiales, para no usar la gran M, se emplean

dos Fases así:

o FASE 1: Minimizar Z = ∑ Ai , hasta que Z=0. O sea, se eliminan la variables

artificiales.
o FASE 2: Se encuentra la solución Optima para el problema Real ( Z= ∑ai
Xi), partiendo del tablero final de la fase 1, eliminando de éste las Variables
Artificiales.

Ejercicios de aplicación

Resolver el Siguiente Caso:

Min Z = 50 X1 +40X2 + 65X3

S.A. 3X1 -5X2 - 6X3 ≥ -2000

8X1 +3X2 + 2X3 ≥500

3X1 +9X2 + 16X3 = 1000

X1 , X2 ≥0 ; X3 Irrestricta.

El procedimiento de solución es:

1. Convertir en un problema de Maximización.

2. Eliminar los recursos negativos

3. Agregar las variables de holgura

4. Cambiar las variables no Positivas, en este caso la irrestricta.

5. Aplicar el método Simplex.

6. Reconversión al problema Original.

El modelo estándar queda: Sin cambiar las variables

Max -Z = -50 X1 -40X2 - 65X3

Sa -3X1 +5X2 + 6X3 +H1 = 2000

8X1 +3X2 + 2X3 +S1 +A1 = 500

3X1 +9X2 + 16X3 +A2 =1000

X1 , X2 ≥0 ; X3 Irrestricta

Hacemos X3= X4 – X5

Donde: X4 , X5 > 0

el Modelo queda:

Max -Z = -50 X1 -40X2 - 65X4 +65X5

-3X1+5X2+ 6X4 - 6X5+H1 = 2000

8X1+3X2+ 2X4 - 2X5 +S1 +A1 = 500

3X1+9X2+ 16X4 - 16X5 +A2 =1000

X1, X2, X4, X5 ≥0

Donde: X3 = X4 - X5 y X4, X5 ≥0
Variables Artificiales

- Variable artificial / Método de la “M”

Una variable artificial es un truco matemático para convertir inecuaciones «>=»

en ecuaciones, o cuando aparecen igualdades en el problema original, la
característica principal de estas variables es que no deben formar parte de la
solución, dado que no representan recursos. El objetivo fundamental de estas
variables es la formación de la matriz identidad.

Estas variables se representan por la letra «A», siempre se suman a las

restricciones, su coeficiente es M (por esto se le denomina Método de la M
grande, donde M significa un número demasiado grande muy poco atractivo para
la función objetivo), y el signo en la función objetivo va en contra del sentido de la
misma, es decir, en problemas de Maximización su signo es menos (-) y en
problemas de Minimización su signo es (+), repetimos con el objetivo de que su
valor en la solución sea cero (0).

Técnicas de las variables artificiales

 Existen problemas de programación lineal que no proporcionan una
solución básica inicial. Esta situación se presenta cuando al menos una de las
restricciones es del tipo (<=) o (=). Para este propósito se desarrollan 2 métodos
basados en el uso de variables artificiales: El método M o de penalización y la
técnica de 2 fases.

METODO M O DE PENALIZACIÓN.

Los pasos básicos del método M son los siguientes:

1. Exprese el problema en forma estándar transformando las inecuaciones en

ecuaciones introduciendo variables de holgura.

2. Agregue variables no negativas al lado izquierdo de cada una de las

ecuaciones correspondientes a las restricciones de tipo (>=) o (=). Estas
variables se denominan variables artificiales y su adición hace que las
restricciones correspondientes.

Esta dificultad se elimina asegurando que las variables sean 0 en la

solución final. Esto se logra asignando una penalización muy grande por unidad a
estas variables en la función objetivo. Tal penalización se designará como –M para
problemas de maximización y +M para problemas de minimización.

3. Utiliza las variables artificiales en la solución básica inicial; sin embargo la

función objetivo de la tabla inicial se prepara adecuadamente para
expresarse en términos de las variables no básicas únicamente. Esto
significa que los coeficientes de las variables artificiales en la función
objetivo deben ser 0 un resultado que puede lograrse sumando múltiplos
adecuados de las ecuaciones de restricción al renglón objetivo.

4. Proceda con los pasos regulares del método simplex.

Ejemplo:

Minimizar

Sujeto a:

Minimizar

Sujeto a:

Minimizar

Sujeto a:

Minimizar
 Sujeto a:

V.B. Z X1 X2 X3 S1 S2 R1 Solución

Z 1 -3 -2 -4 0 0 -M 0

R1 0 2 2 3 -1 0 1 15

S2 0 2 3 1 0 1 0 12

V.B. Z X1 X2 X3 S1 S2 R1 Solución

Z 1 -3+2M -2+2M -4+3M -M 0 0 15M

R1 0 2 2 3 -1 0 1 15

S2 0 2 3 1 0 1 0 12

Criterio para seleccionar la variable entrante:

- Maximización: El valor mayor negativo del renglón Z.

 - Minimización: El valor mayor positivo del renglón Z.

V.B. Z X1 X2 X3 S1 S2 R1 Solución

Z 1 -1/3 2/3 0 -4/3 0 4/3-M 20

X3 0 2/3 2/3 1 -1/3 0 1/3 5

S2 0 4/3 7/3 0 1/3 1 -1/3 7

V.B. Z X1 X2 X3 S1 S2 R1 Solución

Z 1 -5/7 0 0 -10/7 -2/7 10/7-M 18

X3 0 2/7 0 1 -3/7 -2/7 3/7 3

X2 0 4/7 1 0 1/7 3/7 -1/7 3

Ejemplo:

Maximizar
Sujeto a:

Maximizar

Sujeto a:

Maximizar

Sujeto a:

Maximizar

Sujeto a:
V.B. Z X1 X2 S1 S2 R1 R2 Solución

Z 1 -4 -1 0 0 M M 0

R1 0 3 1 0 0 0 0 3

R2 0 4 3 -1 0 1 1 6

S2 0 1 2 0 1 0 0 3

V.B. Z X1 X2 S1 S2 R1 R2 Solución

Z 1 -4-7M -1-4M M 0 0 0 -9M

R1 0 3 1 0 0 0 0 3

R2 0 4 3 -1 0 1 1 6

S2 0 1 2 0 1 0 0 3

V.B. Z X1 X2 S1 S2 R1 R2 Solución

Z 1 0 1/3- M 0 4/3+7/3M 0 4-2M

5/3M
X1 0 1 1/3 0 0 1/3 0 1

R2 0 0 5/3 -1 0 -4/3 0 2

S2 0 0 5/3 0 1 -1/3 1 2

V.B. Z X1 X2 S1 S2 R1 R2 Solución

Z 1 0 0 1/5 0 8/5+M -1/5+M 18/5

X1 0 1 0 1/5 0 3/5 3/5

R2 0 0 1 -3/5 0 -4/5 3/5 6/5

S2 0 0 0 1 1 1 -1 1

Método simplex Primal

El algoritmo simplex primal es un procedimiento matemático iterativo que se

utiliza para determinar la solución óptima desde el conjunto de soluciones
factibles. Fue desarrollado por el matemático estadounidense George Dantzig en
1947. El algoritmo comienza examinando vértices adyacentes del poliedro de
soluciones y se mueve a lo largo de las aristas del poliedro hasta que alcanza el
vértice de la solución óptima.

El algoritmo simplex primal es una técnica de optimización lineal que se

utiliza para resolver problemas de programación lineal. El objetivo es maximizar o
minimizar una función lineal sujeta a restricciones lineales. El algoritmo simplex
primal es una técnica de optimización muy utilizada en la industria y en la
investigación.

Es importante tener en cuenta que, si el problema primal es demasiado

difícil de resolver, es probable que sea más fácil resolver el problema dual. Si tiene
que agregar muchas variables artificiales para resolver el primal, probablemente
sea mejor escribir el dual del LP y resolverlo usando el método Dual Simplex.

1. Una empresa produce dos productos, A y B. Cada unidad del producto A

requiere 2 horas de trabajo y 1 hora de máquina. Cada unidad del producto B
requiere 1 hora de trabajo y 3 horas de máquina. La empresa dispone de 40 horas
de trabajo y 30 horas de máquina por día. Si el beneficio por unidad del producto A
es de 50 euros y el del producto B es de 60 euros, ¿cuántas unidades de cada
producto deberá producir para maximizar el beneficio?
Respuesta:
 Paso 1: Escribir el problema en forma de ecuaciones:
2A + B <= 40

A + 3B <= 30

 Paso 2: Escribir la función objetivo:

Maximizar Z = 50A + 60B

 Paso 3: Crear la tabla Simplex:

Z A B Hol 2A + B A +3B
1 -50 -60 0 2 1
0 1 1 1 0 0

 Paso 4: Encontrar la solución óptima:

La solución óptima es producir 10 unidades del producto A y 10 unidades del
producto B, con un beneficio total de 1100 euros.
Método Simplex Dual

Cada problema de programación lineal está estrechamente relacionado con

otro problema simétrico a él, denominado problema dual. El dualismo es una
teoría que surge como consecuencia de una profundización en el estudio de la
programación lineal porque la distribución de los recursos y la formación de los
precios son dos aspectos del mismo problema. Entonces la doble formulación de
la programación lineal no se debe considerar como un simple ejercicio
matemático, sino que una y otra versión del problema vienen a explicarlos
aspectos económicos distintos para una misma situación problemática. Una
propiedad fundamental de la relación entre el primal y el dual es que la solución
óptima de cualquiera de estos problemas proporciona la solución óptima para el
otro. La resolución de los problemas duales respecto a los primales se justifica
dada la facilidad que se presenta dados problemas donde el número de
restricciones supere al número de variables. Además de tener gran aplicación en
el análisis económico del problema. Otra de las ventajas que presenta es que
dado a que el número de restricciones y variables entre problema dual y
primal es inverso, se pueden resolver gráficamente problemas que presenten
dos restricciones sin importar el número de variables.

Planteamiento de dualidad

Todo problema de programación lineal tiene asociado con él otro problema

de programación lineal llamado DUAL. El problema inicial es llamado PRIMAL y el
problema asociado (sombra) es llamado el problema PRIMAL. Los dos juntos son
llamados problemas duales ya que ambos están formados por el mismo conjunto
de datos. La solución básica factible óptima de estos problemas es tal que una
puede fácilmente ser usada para la solución de la otra. En consecuencia, es
suficiente con resolver uno de ellos (primal o dual) para poder obtener la solución
óptima y valor óptimo del problema equivalente (primal o dual según sea el caso).
Para ello se puede utilizar, por ejemplo, las condiciones establecidas en el
Teorema de Holguras Complementarias.
 Concepto del método dual sumplex

El método simplex es un algoritmo iterativo que iniciando en una solución

básica factible pero no óptima, genera soluciones básicas factibles cada vez
mejores hasta encontrar la solución óptima (sí esta existe). Nótese que la base de
su lógica es mantener la factibilidad, mientras busca la optimalidad. Pero
surge la posibilidad de usar otro esquema igualmente iterativo, que, como
contraparte del simplex, comienza en una solución básica óptima, pero no factible
y mantiene la inmejorabilidad mientras busca la factibilidad. Con este
procedimiento se llega igualmente a la solución óptima.

Un comparativo entre el método simplex y el método dual-simplex:

El método dual-simplex requiere de la aplicación de dos criterios para su solución:

El criterio de optimalidad que asegura que la solución permanecerá óptima

todo el tiempo y el criterio de factibilidad que forza las soluciones básicas hacia el
espacio factible.

Criterio de factibilidad.
 La variable saliente será aquella variable básica que tenga el valor más
negativo en el vector bi. Si todas las variables básicas son positivas o sea
≥0 se tiene la solución final, óptima y factible. Criterio de optimalidad. La
variable entrante se selecciona de entre las variables no-básicas como sigue:
Dividir los coeficientes de la ecuación cero entre los coeficientes de
la ecuación asociada con la variable saliente, ignorando denominadores
positivos y/o ceros. La variable entrante será aquella cuyo cociente sea el menor,
si el problema es de minimizar, o el de menor valor absoluto si es de
maximizar. Si todos los denominadores son ≥0, el problema no tendrá
solución factible.

Aplicaciones

Una aplicación típica del método simplex dual es en la resolución de

problemas con una función objetivo de minimización, con restricciones del tipo
mayor o igual y donde las variables de decisión son mayores o iguales a cero. Con
el método dual simplex podemos resolver problemas que se presentan deforma
cotidiano en la vida laboral como los relacionados con el control de las
organizaciones o sistemas (hombre – máquina). A fin de que se
produzcan soluciones que mejor sirvan a los objetivos de la organización.

Ejemplo:

Considere el siguiente modelo de Programación Lineal:

 Paso 1: Se lleva el modelo a su forma estándar. En nuestro ejemplo esto se
logra agregando variables de exceso en cada una de las restricciones (3 primeras:
S1, S2, S3, respectivamente). Luego, se multiplica cada fila de las restricciones
por -1 de modo de disponer una solución básica inicial (infactible) en las variables
de exceso S1, S2 y S3. De esta forma se obtiene la siguiente tabla inicial.

Paso 2: Se selecciona el lado derecho "más negativo" lo cual indicará cuál

de las actuales variables básicas deberá abandonar la base. En el
ejemplo el lado derecho más negativo se encuentra en la primera fila, por tanto,
S1 deja la base. Para determinar cuál de las actuales variables no básicas (A, B,
C) entrará a la base se busca el mínimo de {-Yj/aij} donde aij es el coeficiente de la
respectiva variable no básica en la fija i (del lado derecho más negativo, marcado
en verde) y donde Yj es el costo reducido de la respectiva variable no básica. De
esta formase obtiene: Min {-315/-15, -110/-2, -50/-1} = 21, donde el pivote
(marcado en rojo) se encuentra al hacer el primer cociente, por tanto, A entra a la
base.
 Paso 3: Se actualiza la tabla anterior siguiendo un procedimiento
similar al utilizado en el Método Simplex. En el ejemplo se debe dejar a la
variable A como básica y S1 como no básica. La tabla que resulta es la siguiente

Paso 4: Continuar las iteraciones y siguiendo el mismo

procedimiento hasta disponer de una solución básica factible. Luego de unas
iteraciones se obtiene la siguiente tabla final.

La solución óptima es A=8, B=10, C=60 (marcado en verde) con valor

óptimo V(P)=6.620 (marcado en rojo - se obtiene con signo cambiado).

Método Grafico.

Solución gráfica de programación lineal.

El método gráfico es una técnica de solución de problemas de

programación lineal que se utiliza principalmente para casos con dos variables.
Aunque no es muy práctico para una gran cantidad de variables, es muy útil para
interpretar y analizar los resultados y la sensibilidad del problema. Sin embargo,
en casos donde se requiera un mayor número de variables, es posible emplear
otras técnicas como la proyección en un plano.
 El método gráfico se basa en la representación gráfica de las restricciones
del modelo de programación lineal, lo que permite determinar el polígono solución
o región factible. Según el teorema fundamental de la programación lineal, si
existe una solución que cumple con las restricciones del modelo, se encontrará en
uno de los vértices de la región factible.

El método gráfico es una técnica que ha sido objeto de debate entre

distintos autores a lo largo de la historia. Algunos de ellos han señalado que esta
metodología presenta ciertos supuestos o limitaciones.

Uno de los supuestos más conocidos es que no permite realizar un análisis

de sensibilidad en el caso de cambios simultáneos en el lado derecho de las
restricciones o en los coeficientes de la función objetivo. Otro supuesto es que no
se pueden considerar variables binarias en el modelo.

Sin embargo, con el avance de la tecnología, es posible utilizar

herramientas como GeoGebra para superar estas limitaciones y realizar análisis
de sensibilidad con cambios simultáneos y considerar variables binarias en el
modelo. Por lo tanto, estos supuestos ya no son válidos en la actualidad.

Consideraciones previas

Es necesario recordar que el método gráfico es un método de solución, por

tanto, una etapa previa corresponde al modelamiento matemático.

El problema

Vamos a utilizar un problema técnicamente formulado con el objetivo de

abordar cada una de las fases del método gráfico.
 La fábrica de Hilados y Tejidos «Salazar» requiere fabricar dos tejidos de
calidad diferente Estándar y Premium; se dispone de 500 Kg de hilo a, 300 Kg de
hilo b y 108 Kg de hilo c. Para obtener un metro de Estándar diariamente se
necesitan 125 gr de a, 150 gr de b y 72 gr de c; para producir un metro
de Premium por día se necesitan 200 gr de a, 100 gr de b y 27 gr de c. El
Estándar se vende a $4000 el metro y el Premium se vende a $5000 el metro. Si
se debe obtener el máximo beneficio, ¿Cuántos metros de Estándar y Premium se
deben fabricar?

Modelamiento mediante programación lineal

Como lo se ha mencionado anteriormente, la base para utilizar el método

gráfico corresponde al modelo matemático de programación lineal:

Variables

 x: Cantidad de metros diarios de tejido tipo Estándar a fabricar

 y: Cantidad de metros diarios de tejido tipo Premium a fabricar

Restricciones

 0,12x + 0,2y <= 500 Kg de hilo “a”

 0,15x + 0,1y <= 300 Kg de hilo “b”
 0,072x + 0,027y <= 108 Kg de hilo “c”
 x >= 0 Restricción de no negatividad
 y >= 0 Restricción de no negatividad

Función objetivo

 Zmax = 4000x + 5000y (Maximizar los ingresos totales dados en $).

 Solución mediante método gráfico

Paso 1: Graficar las restricciones

El proceso para encontrar la solución factible comienza con la

representación gráfica de las restricciones; cada una de ellas debe representarse
de tal manera que se vayan limitando las posibles soluciones del modelo.

En este punto, debemos considerar dos posibilidades:

1. Que realicemos todo el procedimiento de forma manual

2. Que utilicemos un software gráfico que simplifique las operaciones

matemáticas

En este caso, mostraremos toda la metodología para realizar el procedimiento

manual, al mismo tiempo que utilizaremos un software gráfico para representar
cada fase del método.

Cada restricción corresponde a una función lineal, lo que significa que

gráficamente se representa mediante una línea en el plano cartesiano. Para trazar
una línea en el plano cartesiano es necesario conocer al menos dos puntos de la
función.

Para comenzar a trazar las restricciones es esencial igualar las restricciones a

cero, de esta manera podremos usar el despeje de las ecuaciones para iniciar la
tabulación que nos dará las coordenadas para dibujar cada una de las gráficas.

Igualamos las restricciones a cero:

 0.12x + 0.2y = 500 (Restricción 1)

 0.15x + 0.1y = 300 (Restricción 2)
 0.072x + 0.027y = 108 (Restricción 3)
 x=0 (Restricción 4)
 y=0 (Restricción 5)
 Iniciamos con la Restricción 1: Hallamos las primeras dos coordenadas. Para
hallar las coordenadas, regularmente llevamos una de las variables a cero, para
de esta manera despejar más fácilmente la segunda.

Cuando x = 0

 0,12(0) + 0,2y = 500

 0,2y = 500
 500/0,2 = y
 2500 = y

y cuando y = 0

 0,12x + 0,2(0) = 500

 0,12x = 500
 x = 500/0,12
 x = 4167

Restricción 1 x y

Primera coordenada 0 2500

Segunda coordenada 4167 0

 Seguimos con la Restricción 2:

Por ejemplo, cuando x = 0

 0.15(0) + 0.1y = 300

 0.1y = 300
 y = 300/0.1
 y = 3000

Cuando y = 0

 0.15x + 0.1(0) = 300

 0.15x = 300
 x = 300/0.15
 x = 2000
 Restricción 2 x y

Primera coordenada 0 3000

Segunda coordenada 2000 0

Seguimos con la Restricción 3:

Por ejemplo, cuando x = 0

 0.072x + 0.027y = 108

 0.072(0) + 0.027y = 108
 0.027y = 108
 y = 108/0.027
 y = 4000
Cuando y = 0

 0.072x + 0.027(0) = 108

 0.072x = 108
 x = 108/0.072
 x = 1500

Restricción 3 x y

Primera coordenada 0 4000

Segunda coordenada 1500 0

 Restricciones de no negatividad:

Paso 2: Encontrar el área solución (Polígono solución)

Después de que todas las restricciones sean representadas gráficamente,

el siguiente paso consiste en encontrar el área factible o polígono solución; que no
es otra cosa más que la región en la que todos los puntos satisfacen la totalidad
de las restricciones, es decir, son factibles.

Para delimitar el área factible, es necesario determinar el sentido de las

restricciones. Aquí me detengo un poco; ya que prefiero explicarlo en detalle.
Cada línea que representa una restricción divide el plano cartesiano en dos
semiplanos: En un lado y en el otro lado de la restricción. Bien, solo los puntos del
uno de los lados pueden considerarse como factibles.
 Si queremos encontrar el área factible, debemos empezar por encontrar el
lado factible de cada una de las restricciones; esto es lo que yo llamo: evaluar el
sentido de las restricciones.

Veamos un ejemplo para la primera restricción.

Evaluar el sentido de la Restricción 1

Esto es muy sencillo, solo debemos evaluar un punto cualquiera del plano
cartesiano, debe corresponder a uno de los lados de la restricción. Si se satisface
o no la restricción, sabremos el sentido de la misma.

0,12x + 0,2y <= 500

Es normal que queramos simplificar el proceso aritmético, y es común

utilizar el punto de coordenadas (0, 0):

 0,12(0) + 0,2(0) <= 500

 0 <= 500
 Dado que 0 es menor o igual a 500, podemos afirmar que de ese lado de la
restricción se encuentran los valores que la satisfacen.

La región en verde representa el área en la que se encuentran todos los

puntos que satisfacen la restricción 1.

Cuando la función de la restricción (línea en el plano) pase por el punto (0,

0) este no servirá para evaluar la restricción. Recuerde que debe elegirse un punto
que se encuentre en uno de los lados de la restricción.

Para encontrar la región factible, el procedimiento debe repetirse para cada

una de las restricciones del problema. Dado que todas las restricciones deben
cumplirse, la región factible será el resultado de la intersección de todas las
regiones factibles de cada una de las restricciones del modelo.
 El área sombreada de la gráfica anterior corresponde a la región factible.

Paso 3: La búsqueda de la solución óptima

Una vez que se ha encontrado la región factible que cumple con todas las
restricciones del modelo, el siguiente paso es encontrar la solución óptima. Es
importante diferenciar entre factibilidad y optimalidad.

La solución óptima dependerá del criterio de optimización de la función

objetivo y, de acuerdo al teorema fundamental de la programación lineal, se
encuentra en uno de los vértices del área factible. Técnicamente, en los vértices
se encuentra la solución óptima para cualquier criterio de optimización: El valor
mínimo (minimización) y el valor máximo (maximización).
 Hay principalmente dos procedimientos para encontrar la solución óptima:

1. Gráficamente

2. Evaluando todos los vértices (Fuerza bruta)

Gráficamente

Este método requiere de la representación gráfica de la función objetivo.

Por lo menos dos veces.

Es necesario graficar la función objetivo y encontrar el sentido en el cual se

acerca al criterio de optimización. ¿Cómo lo hacemos? En cada caso,
necesitamos dos puntos para graficar la primera línea que representa a la función
objetivo; estos dos puntos deben dar como resultado el mismo Z. Veamos:

Zmax = 4000x + 5000y

Función objetivo (Z1) 4000(x) 5000(y) z

Primera coordenada 4000(500) 5000(0) 2000000

Segunda coordenada 4000(0) 5000(400) 2000000

Ahora, podemos intentar con otra representación de la función objetivo que

se acerque aún más al criterio de optimización: Maximizar; es decir, un Z2 mayor a
Z1. Veamos:

Función objetivo (Z2) 4000(x) 5000(y) z

Primera coordenada 4000(1000) 5000(0) 4000000

Segunda coordenada 4000(0) 5000(800) 4000000

 Ahora podemos intentar con otra representación de la función objetivo que
nos da incluso mucho mas cerca del criterio de optimización:

Maximize: que es un Z2 mejor que Z1, veamos:

Se puede ver cómo la función objetivo se aproxima al criterio de

optimización (aumenta) mientras se desplaza hacia arriba. El siguiente paso es
encontrar el último vértice del área factible (en dirección ascendente en este caso),
donde una línea paralela a la función objetivo no corta el polígono factible. En este
punto se encontrará la solución óptima.
 Utilice la barra de desplazamiento de GeoGebra para desplazar la función
objetivo. Verá que el último vértice en el que la función objetivo no corta el área
factible es el que se da por la intersección de la Restricción 2 y la Restricción 3
(Vértice C). Este punto corresponde a la solución óptima.

Para encontrar el valor de esta coordenada es necesario resolver una ecuación

lineal 2×2, y se pueden considerar varios métodos de solución, como:

 Método de sustitución

 Método de igualación

 Método de reducción o Eliminación

 Método de eliminación Gauss

 Método de eliminación Gauss-Jordán

 Método de determinantes
 Hay muchos métodos disponibles, pero uno de los más utilizados es el método
de reducción o eliminación, que es muy fácil de aplicar.

El método de reducción o eliminación consiste en igualar los coeficientes de

una de las variables multiplicando una o ambas ecuaciones, teniendo en cuenta
que estos coeficientes queden iguales, pero con signos contrarios.

Ecuación 1 0,12x + 0,2y = 500

Ecuación 2 0,15x + 0,1y = 300 multiplicamos por (-2)

Ecuación 3 (2*(-2)) -0,30x – 0,2y = -600

Sumamos 1 y 3 -0,18x = -100

Despejamos «x» x = -100 / (-0,18)

x = 555,55

Luego reemplazamos x = 555,55 en cualquiera de las dos ecuaciones

originales con el objetivo de despejar “y”.

Ecuación 1 0,12x + 0,2y = 500

Reemplazamos «x» 0,12(555,55) + 0,2y = 500

Despejamos «y» 66,666 + 0,2y = 500

0,2y = 500 – 66,666

0,2y = 433,334

y = 433,334 / 0,2

y = 2166,67
 De esta forma hemos obtenido los valores para “x” y “y”.

 x: Cantidad de metros diarios de tejido tipo Estándar a fabricar

 y: Cantidad de metros diarios de tejido tipo Premium a fabricar

- Cantidad de metros diarios de tejido tipo Estándar a fabricar = 555,55

- Cantidad de metros diarios de tejido tipo Premium a fabricar = 2166,67

La contribución obtenida (reemplazando las variables en la función objetivo)

es de:

Zmax = 4000x + 5000y

Zmax = 4000(555,55) + 5000(2166,67)

Zmax = $13.055.550

Ahora podemos comparar los resultados con los obtenidos mediante

resolución en Excel, pero recuerden que el método de búsqueda de la solución
óptima en el método gráfico que utilizamos es geométrico y que existe una forma
mucho más compleja pero igualmente efectiva, que es el método de iteración por
vértice. Este consiste en hallar todas las coordenadas de los vértices y luego
evaluar la función objetivo en cada coordenada. Cada coordenada nos
proporciona un valor en “x” y otro en “y”, luego reemplazamos estos valores en la
función objetivo “4000x + 5000y =?” y evaluamos los resultados seleccionando el
mayor valor.
 Conclusión

La Programación Lineal es una herramienta esencial en la toma de

decisiones y la optimización de recursos en una amplia variedad de campos.
Desde la gestión empresarial hasta la planificación de rutas de viaje, su
aplicabilidad es sorprendente. No obstante, la programación lineal logra brindar a
cualquier tipo de organización ciertas características, entre las más destacables
tenemos:

La programación lineal permite hacer un uso más eficiente de los recursos,

ya que permite planificar y asignar los recursos de manera óptima. Esto permite
reducir los costos y aumentar la eficiencia de los procesos.

La programación lineal permite resolver problemas complejos y encontrar

soluciones innovadoras. Además, permite explorar diferentes escenarios y evaluar
sus consecuencias.

La programación lineal tiene algunas limitaciones, como la necesidad de

cumplir con ciertas suposiciones, como la linealidad de la función objetivo y las
restricciones, la divisibilidad de las variables y la independencia de las actividades.
Cuando no se cumplen estas suposiciones, se pueden aplicar otros modelos
matemáticos, como la programación entera o la programación no lineal.

La programación lineal se puede resolver mediante diferentes métodos,

como el método gráfico, el método simplex, el método de los multiplicadores de
Lagrange o el método de las regiones factibles. Estos métodos permiten encontrar
la solución óptima del problema de forma eficiente
 Bibliografía

- [Link]
paso-a-paso
- [Link]
durango/fundamentos-de-investigacion/metodo-dual-simplex/6489847
- [Link]
irrestricta-en-docplex-python
- [Link]
- [Link]
- [Link]
%20se%20midan%2C%20las,Ordinales%20o%20cuasicuantitativas.
- [Link]
- [Link]
- [Link]
- [Link]
- Hamdy A. TAHA (2012). Investigación de operaciones, Pearson Education,
México.