CAPÍTULO II

PROGRAMACIÓN LINEAL

2.1. INTRODUCCIÓN

Jean-Baptiste-Joseph Fourier, matemático y físico francés (1768-1830), co-

nocido por su trabajo para determinar la conducción del calor a través de la des-
composición de funciones periódicas en series trigonométricas convergentes,
denominado “Series de Fourier”, fue el primero en intuir la metodología de eli-
minación para dar solución a un sistema de desigualdades, conocido actualmente
como programación lineal.

El desarrollo que ha tenido la programación lineal desde 1950 ha sido uno de

los avances científicos más significativos en lo que respecta a la toma de decisio-
nes. Actualmente, la programación lineal se ha convertido en una herramienta de
uso habitual que permite a las empresas de distintos países industrializados del
mundo, el ahorro de cantidades significativas de dinero, debido a la versatilidad
de los programas diseñados para computadoras.

La aplicación de la programación lineal es muy variada, ya que puede ser

utilizada en la asignación de instalaciones de producción a los productos hasta
la asignación de los recursos nacionales a las necesidades de un país; desde la se-
lección de una cartera de inversiones hasta la selección de los patrones de envío;
desde la planeación agrícola hasta el diseño de una terapia de radiación (Hillier
& Lieberman, 2010).

La programación lineal es una parte de la programación matemática, la cual

hace uso de ecuaciones lineales para representar o expresar problemas identifi-
cados en la vida real, ecuaciones donde todas las variables que forman parte del
sistema son de grado 1, es decir, su exponente es la unidad. En este capítulo se
muestra el procedimiento para expresar el problema existente, en una ecuación

28
 Ximena Granizo Espinoza

matemática y cómo dar solución al mismo, para lo cual es necesario dar a conocer
algunas definiciones.

2.2. DEFINICIONES.

A continuación, se presentan varias definiciones utilizadas en la metodología,

con la finalidad de comprender la terminología usada:

Programación Lineal: La programación lineal proporciona un ejemplo de

lo que se conoce de manera más general como modelo de toma de decisiones
con restricciones, también llamado modelo de optimización con restricciones
(Eppen, Gould, Schmidt, Moore, & Weatherford, 2000).

Función Objetivo: La función objetivo está representada por una variable,

generalmente la letra Z, y simboliza aquello que se pretende optimizar, es decir,
que el resultado logrado sea el mejor posible; por ejemplo, maximizar la utilidad
o los ingresos percibidos o a su vez, minimizar los costos existentes.

Variables del problema: Son variables que se desconocen y que al momento

de proceder con la resolución del problema, deben estar definidas en función del
objetivo principal: la optimización de la función objetivo. Las variables del pro-
blema son también denominadas variables de decisión.

Coeficientes de la función objetivo: los coeficientes, son cantidades cons-

tantes que forman parte de la ecuación que representa a la función objetivo y se
encuentran multiplicando a las variables del problema.
Restricciones: las restricciones representan aquellas condiciones que se de-
ben cumplir o las limitaciones existentes en cuanto a disponibilidad de recursos,
ya sean materiales, humanos (mano de obra), económicos, tiempo, etc. Son tam-
bién conocidas como restricciones funcionales.

Restricciones no explícitas: son aquellas restricciones que no se evidencian

en el problema, pero deben ser consideradas en el planeamiento y en la solución
del mismo. Son condiciones o limitaciones que se encuentran de cierta manera
ocultas, siendo las restricciones no explícitas más frecuentes, las siguientes:

29
 Investigación operativa. Programación lineal en las Ciencias Administrativas

- Que las variables sean no negativas

- Que las variables sean números enteros.

2.3. METODOLOGÍA PARA EL PLANTEAMIENTO DE PROBLEMAS

Para el planteamiento de problemas de programación lineal es necesario apli-

car los siguientes pasos (Bronson, 1992):

1. Definir las variables del problema: Este paso consiste en identificar las
variables que están inmersas en el planteamiento del problema y represen-
tarlas con letras, definiendo además sus unidades.

2. Definir la función objetivo: Consiste en identificar aquella variable que

se va a optimizar, la cual estará representada con la letra Z y construir la
ecuación matemática en función de las variables del problema y sus coefi-
cientes. En este paso es importante definir si la optimización persigue una
maximización o una minimización.

Un problema de maximización busca determinar la combinación de ac-

tividades que permitan obtener el mayor rendimiento de los recursos ba-
sado en el criterio de máxima utilidad, en cambio el problema de mini-
mización pretende determinar las cantidades necesarias de los recursos
basándose en el criterio del costo mínimo total (González & García, 2015).

3. Definir las restricciones: En función de las variables del problema se

procede a establecer ecuaciones para las restricciones identificadas, (una
ecuación para cada restricción), por lo general, las restricciones son des-
igualdades del tipo mayor o igual que (≥) y/o del tipo menor o igual que
(≤), existiendo en ocasiones también el uso de restricciones con signo de
igualdad (=), especialmente en el caso en que se necesite producir una
cantidad exacta equivalente a un número dado, por ejemplo, se desea pro-
ducir un kilo de algodón, preparar dos kilos de alimento, etc.

4. Definir las restricciones no explicitas: Este paso consiste en identificar

si las variables del problema son números enteros o no, si se trata de varia-

30
 Ximena Granizo Espinoza

bles no negativas y expresar aquellas restricciones en el planteamiento del

problema.

Durante el planteamiento de problemas de programación lineal se debe

prestar especial atención al planteamiento de las restricciones, ya que es
necesario verificar que tanto en el lado derecho como izquierdo de la res-
tricción consten las mismas unidades de medida, por ejemplo, si el lado
derecho está expresado en kilos, el lado izquierdo de la restricción deberá
estar expresado también en kilos.

2.4. PROBLEMAS RESUELTOS

Un centro cosmético prepara una crema hidratante, cuyos componentes, pre-

cio y características se encuentran descritos en la siguiente tabla:

ACEITES
COSTO ANTOIXODANTES AGUA
COMPONENTES VEGETALES
($/litro) % %
%
A 10 25 50 25
B 12 62 23 15
C 7 45 20 35

¿Qué cantidad de cada uno de los componentes se deberían utilizar si se de-

sea minimizar el costo al preparar 1 litro de crema hidratante, cuyo contenido de
antioxidantes no sea menor al 25%, el contenido de agua no mayor al 35% y el
contenido de aceites vegetales no sea menor al 40%?
Planteamiento:

Para proceder con el planteamiento del problema, es necesario seguir los pa-
sos descritos anteriormente.

31
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Identificamos cuántas variables intervienen en el planteamiento del proble-

ma (aquello que se desea conocer), en este caso son tres: la fracción del litro del
compuesto A, la fracción del litro del compuesto B y la fracción del litro del com-
puesto C, a mezclar para preparar un litro de crema hidratante, a continuación,
las representamos las variables con una letra, en este caso la letra X y el subíndice
que corresponde a dicha variable, así:

Variables del X1= Fracción del litro del compuesto A

problema
X2= Fracción del litro del compuesto B

X3= Fracción del litro del compuesto C

Este paso consiste en identificar aquello que se desea optimizar, en este caso,
se desea minimizar el costo al preparar 1 litro de crema hidratante y luego plan-
tear la función objetivo, expresando la ecuación matemática en función de las
variables del problema y sus coeficientes, de la siguiente manera:

función objetivo.

Min Z = 10X1 +12X2 +7X3

Variables del
problema

32
 Ximena Granizo Espinoza

Los coeficientes de la función objetivo serán los costos de los componentes

A, B y C, ya que se desea minimizar el costo total al preparar un litro de crema
hidratante.

Se debe analizar cuáles son las limitaciones o condiciones a cumplir en el

planteamiento del problema, en este caso existen cuatro:

1. Preparar un litro de crema hidratante.

2. El contenido de antioxidantes no debe ser menor al 25%.

3. El contenido de agua no debe ser mayor al 35%.

4. El contenido de aceites vegetales no debe ser menor al 40%.

Tal como menciona la metodología, se plantea una ecuación para cada res-
tricción, así:

Restricciones:

1. Se debe preparar un litro de crema hidratante:

X1 + X2 + X3 = 1

La suma de las fracciones de litro de los compuestos A, B y C, debe ser un

litro.

2. El contenido de antioxidantes no debe ser menor al 25%:

25X1 + 62X2 + 45X3 ≥ 25

En este caso, el litro de crema hidratante debe tener un contenido de antioxi-

dantes no menor al 25%, por lo tanto, la suma de los porcentajes de antioxidantes
de los componentes A, B y C, debe ser mínimo el 25%, por lo que se utiliza el
signo mayor o igual que (≥) para expresar dicha condición. De igual manera se
plantean las demás restricciones analizando el uso de los signos.

33
 Investigación operativa. Programación lineal en las Ciencias Administrativas

3. El contenido de agua no debe ser mayor al 35%:

50X1 + 23X2 + 20X3 ≤ 35

La suma de los porcentajes de agua que contienen los componentes A, B y C,

no debe superar el 35%, por lo que se utiliza el signo menor o igual que (≤) para
expresar dicho límite.

4. El contenido de aceites vegetales no debe ser menor al 40%:

25X1 + 15X2 + 35X3 ≥ 40

Al establecer como condición que la suma del contenido de aceites vegetales

de los compuestos A, B y C no debe ser menor al 40%, se utiliza el signo mayor o
igual que (≥), ya que dicho signo indica que la suma de los porcentajes debe ser
efectivamente mayor al porcentaje establecido.

En este último paso se debe identificar si son variables enteras y no negativas o

a su vez, si se cumple una sola condición. En el ejercicio propuesto las variables X1,
X2, X3, representan la fracción de litro de los compuestos A, B y C, para preparar un
litro de crema hidratante, por lo tanto, no se trata de cantidades enteras, ya que la
suma de las cantidades de los compuestos utilizadas en la preparación deberá sumar
1 (litro). Por lo tanto, se cumple únicamente con la restricción de no negatividad.
X1, X2, X3, son no negativas
Finalmente, el planteamiento del problema quedaría expresado de la siguien-
te manera:

Min Z = 10X1 + 12X2 + 7X3

Sujeto a:

X1 + X2 + X3 = 1

25X1 + 62X2 + 45X3 ≥ 25

50X1 + 23X2 + 20X3 ≤ 35

34
 Ximena Granizo Espinoza

25X1 + 15X2 + 35X3 ≥ 40

Con X1, X2, X3, no negativas

En el caso de presentarse un ejercicio cuyo objetivo sea la maximización de

ingresos o utilidades, la única diferencia será la utilización de la expresión Max Z,
en la función objetivo.

Una fábrica de alimentos cuenta con dos tipos de materias primas A y B, para
preparar un kilo de un suplemento alimenticio para diabéticos, el cual no debe
contener más del 25% de azúcares. La empresa desea conocer qué cantidad de
cada materia se debe utilizar para cumplir dicho requerimiento y a la vez maxi-
mizar sus ingresos. A continuación, se presentan las características de las materias
primas en la siguiente tabla:
Planteamiento:

MATERIA PRIMA AZÚCARES (%) UTILIDAD QUE GENERA ($)

A 20 3,25
B 35 2,50

Identificamos las variables intervienen en el planteamiento del problema, en

este caso son dos: las cantidades de materia prima A y B, para preparar un kilo de
suplemento alimenticio para diabéticos. Representamos las variables con la letra
X y el subíndice que corresponde a dicha variable, así:

X1 = cantidad de materia prima A para preparar un kilo de suplemento.

X2 = cantidad de materia prima B para preparar un kilo de suplemento.

35
 Investigación operativa. Programación lineal en las Ciencias Administrativas

En el ejercicio propuesto, se desea optimizar los ingresos, buscando una

maximización de estos, a continuación, se plantea la función objetivo, en función
de las variables del problema y sus coeficientes, de la siguiente manera:

Max Z = 3,25X1 + 2,50X2

Los coeficientes de la función objetivo son los ingresos que genera cada tipo
de materia prima.

Analizando los datos propuestos, existen dos condiciones a cumplir:

1. Preparar un kilo de suplemento alimenticio para diabéticos.

2. El contenido de azúcares del suplemento no debe exceder del 25%.

Se plantea una ecuación para cada restricción:

Restricciones:

1. Preparar un kilo de suplemento alimenticio para diabéticos.

X1 + X2 =1

La suma de las cantidades de materia prima A y B deben dar como resultado

un kilo de suplemento alimenticio.

2. El contenido de azúcares del suplemento no debe exceder del 25%.

20X1 + 35X2 ≤ 25

Tratándose de porcentajes, la restricción también podría ser planteada de la

siguiente manera:

0,20X1 + 0,35X2 ≤ 0,25

36
 Ximena Granizo Espinoza

En el ejercicio propuesto las variables X1, X2, representan las cantidades de

materia prima A y B que serán utilizadas para preparar un kilo de suplemento ali-
menticio, por lo que no se trata de cantidades enteras, cumpliéndose únicamente
la restricción de no negatividad de las variables.

X1, X2, son no negativas

El planteamiento del problema quedaría expresado de la siguiente manera:

Max Z = 3,25X1 + 2,50X2

Sujeto a:

X1 + X2 = 1

0,20X1 + 0,35X2 ≤ 0,25

Con X1, X2, no negativas.

Una panadería prepara habitualmente 3 tipos de postres: pastel, tres leches y

mousse de limón, los cuales requieren principalmente, los siguientes ingredientes
en las cantidades detalladas a continuación:

POSTRE HARINA MANTEQUILLA PRECIO DE

(g.) (g.) VENTA
Pastel 200 100 $8,00
Tres leches 150 50 $10,00
Mousse de limón 100 65 $12,00

37
 Investigación operativa. Programación lineal en las Ciencias Administrativas

La panadería dispone de 40 kg. de harina y 52 kg. de mantequilla y desea co-

nocer cuál es la cantidad de cada tipo de postre que debe preparar para maximizar
sus ingresos.

Planteamiento:

X1 = cantidad de postre tipo 1 a para preparar (pastel).

X2 = cantidad de postre tipo 2 a para preparar (tres leches).

X3 = cantidad de postre tipo 3 a para preparar (mousse de limón).

El objetivo que persigue el negocio es la maximización de las utilidades pro-

venientes de la venta de cada uno de los postres:

Max Z = 8X1 + 10X2 + 12 X3

1. Cantidad de harina disponible 40 kg = 40000 g.

200X1 + 150X2 + 100 X3 ≤ 40000

2. Cantidad de mantequilla disponible 52 kg = 52000 g.

100X1 + 50X2 + 65 X3 ≤ 52000

Los dos lados de la restricción deben estar expresados en la misma unidad de

medida, en este caso gramos.

38
 Ximena Granizo Espinoza

X1, X2, X3 son enteras y no negativas

El planteamiento del problema quedaría expresado de la siguiente manera:

Max Z = 8X1 + 10X2 + 12 X3

Sujeto a:

200X1 + 150X2 + 100 X3 ≤ 40000

100X1 + 50X2 + 65 X3 ≤ 52000

Con X1, X2, X3 enteras y no negativas.

Una fábrica de ropa dispone de 60 metros de tela impermeable y de 40 horas

de tiempo para confeccionar chompas de hombre y de mujer. Para confeccionar
el modelo de chompa para hombre, se necesitan 2 metros de tela y 3 horas de
tiempo; para confeccionar el modelo de chompa para mujer, se necesitan 1,5 me-
tros de tela y 2,5 horas. El modelo de chompa para hombre se vende en $55,00
y el modelo para mujer en $45,00. ¿Cuántas chompas para hombre y para mujer
se deberán confeccionar con la finalidad de maximizar los ingresos de la fábrica?

Planteamiento:

X1 = unidades de chompas para hombre a confeccionar.

X2 = unidades de chompas para mujer a confeccionar.

39
 Investigación operativa. Programación lineal en las Ciencias Administrativas

El objetivo es conocer cuántas chompas de hombre y mujer se deberían con-

feccionar con la finalidad de obtener la mayor cantidad de ingresos.

Max Z = 55X1 + 45X2

Con la finalidad de simplificar el planteamiento del problema e identificar los

coeficientes de las ecuaciones, es recomendable trasladar los datos del problema a
una tabla, tal como se muestra a continuación:

VARIABLES DEL TELA PARA LA TIEMPO PARA PRECIO DE

PROBLEMA CONFECCIÓN LA CONFECCIÓN VENTA
(metros) (horas) ($)
X1 2 3 55,00
X2 1,5 2,5 45,00

Disponibilidad 60 40

De esta manera se identifican fácilmente los coeficientes de las restricciones:

1. Metros de tela impermeable disponible = 60

2X1 + 1,5X2 ≤ 60

2. Horas de tiempo disponible para la confección = 40

3X1 + 2,5X2 ≤ 40

Paso 4. Definir las restricciones no explicitas:

X1, X2, son enteras y no negativas

El planteamiento del problema sería:

40
 Ximena Granizo Espinoza

Max Z = 55X1 + 45X2

Sujeto a:

2X1 + 1,5X2 ≤ 60

3X1 + 2,5X2 ≤ 40

Con X1, X2, enteras y no negativas.

La empresa My Pet desea producir un balanceado para perros a un mínimo

costo, utilizando tres materias primas para su producción, las cuales cuentan con
las siguientes características:

MATERIA CEREALES VITAMINAS PROTEÍNAS COSTO/kg

PRIMA (%) (%) (%) ($)
A 40 9 20 20,00
B 36 10 25 18,00
C 34 7 28 16,00

¿Cómo deberían mezclarse las materias primas para preparar un kilo del alimento
que contenga mínimo el 35% de cereales, un 8 % de vitaminas y un 22 % de proteínas?

Planteamiento:

X1 = cantidad de materia prima A a mezclar.

X2 = cantidad de materia prima B a mezclar.

41
 Investigación operativa. Programación lineal en las Ciencias Administrativas

X3 = cantidad de materia prima C a mezclar.

En este caso las variables son las cantidades de las materias primas A, B, C a
mezclar para la preparación de 1 kg. de balanceado.

El objetivo es producir un balanceado para perros a un mínimo costo, enton-

ces:

Min Z = 20X1 + 18X2 + 16X3

1. Preparar un kilo de alimento.

X1 + X2 + X3 = 1

La suma de las cantidades de las materias primas utilizadas en la preparación

debe ser igual a 1 kilo.

2. Contenido mínimo del 35% de cereales.

40X1 + 36X2 + 34X3 ≥ 35

3. Contenido mínimo del 8% de vitaminas.

9X1 + 10X2 + 7X3 ≥ 8

4. Contenido mínimo del 22 % de proteínas.

20X1 + 25X2 + 28X3 ≥ 22

42
 Ximena Granizo Espinoza

X1, X2, X3 son no negativas

En este caso las restricciones no explicitas son únicamente la no negatividad
de las variables.

El problema quedaría planteado de la siguiente manera:

Min Z = 20X1 + 18X2 + 16X3

Sujeto a:

X1 + X2 + X3 = 1

40X1 + 36X2 + 34X3 ≥ 35

9X1 + 10X2 + 7X3 ≥ 8

20X1 + 25X2 + 28X3 ≥ 22

Con X1, X2, X3 no negativas.

Una empresa que presta servicios de distribución posee un container de 29 tone-

ladas de capacidad, desea saber cuál es la forma más rentable de cargar el mismo, si
tiene la opción de transportar 5 tipos de productos. En la siguiente tabla se presentan
las diferentes cargas con los pesos e ingresos que generarían por su transportación:

PRODUCTOS PESO (kg.) INGRESO ($)

P1 8500 1900,00
P2 5600 1650,00
P3 4500 1480,00
P4 7000 1830,00
P5 9000 2250,00

43
 Investigación operativa. Programación lineal en las Ciencias Administrativas

¿Cómo debería cargarse el container para generar un máximo ingreso? Es

importante mencionar que no se puede fraccionar ninguna de las cargas de los
productos, es decir se deben transportar los productos seleccionados en su tota-
lidad.

Planteamiento:

Las variables en este problema representarán la probabilidad de transportar

cada producto, considerando la oportunidad de maximizar los ingresos por este
concepto.

X1 = variable de probabilidad de transportar el producto 1.

X2 = variable de probabilidad de transportar el producto 2.

X3 = variable de probabilidad de transportar el producto 3.

X4 = variable de probabilidad de transportar el producto 4.

X5 = variable de probabilidad de transportar el producto 5.

El objetivo es generar un máximo ingreso por el transporte de los productos.

Max Z = 1900X1 + 1650X2 + 1480X3 + 1830X4 + 2250X5

1. Capacidad del container 29 toneladas = 29000 kg.

8500X1 + 5600X2 + 4500X3 + 7000X4 + 9000X5 ≤ 29000

44
 Ximena Granizo Espinoza

Se realiza la conversión de toneladas a kilos, para utilizar la misma unidad de

medida en los dos lados de la ecuación. Se usa el signo menor o igual que debido
a que el container no puede transportar más peso que el de su capacidad.

2. No se puede fraccionar ninguna de las cargas de los productos.

X1 ≤ 1
X2 ≤ 1

X3 ≤ 1

X4 ≤ 1

X5 ≤ 1

Con esta restricción se establece que no se pueden fraccionar o llevar parte de

cada una de las cargas de producto, dicho de otro modo, se lleva cero o la unidad,
siendo las variables enteras y no negativas, se usa el signo menor o igual para ex-
presar dicha condición.

Paso 4. Definir las restricciones no explicitas:

X1, X2, X3, X4, X5 enteras y no negativas

El planteamiento del problema quedaría de la siguiente sería:

Max Z = 1900X1 + 1650X2 + 1480X3 + 1830X4 + 2250X5

Sujeto a:

8500X1 + 5600X2 + 4500X3 + 7000X4 + 9000X5 ≤ 29000

X1 ≤ 1

X2 ≤ 1

X3 ≤ 1

X4 ≤ 1

X5 ≤ 1

Con X1, X2, X3, X4, X5 enteras y no negativas.

45
 CAPÍTULO III
MÉTODO SIMPLEX

3.1. INTRODUCCIÓN

El método simplex fue desarrollado por George Dantzig, conocido como el

padre de la investigación operativa, en 1947. Es considerado un procedimiento
algebraico utilizado para resolver problemas de programación lineal.

El método consiste en una serie de iteraciones que pretenden encontrar la

mejor solución factible, denominada también solución óptima.

La idea general del método simplex consiste en partir de una solución básica
factible ir a una solución básica factible adyacente con mejor valor de la función
objetivo. El proceso continúa hasta que se haya encontrado una solución óptima.
Por lo que el algoritmo simplex debe (Maroto, Alcaraz, Ginestar, & Segura , 2012):

1. Encontrar una solución básica factible inicial.

2. Encontrar una solución básica adyacente a la anterior.

3. Asegurar que la nueva solución es factible.

4. Asegurar que la nueva solución es mejor que la anterior.

Si bien el método simplex consiste en un método algebraico, en el presente

capitulo se muestra cómo la interpretación de los resultados obtenidos pueden
contribuir de manera significativa en el proceso de toma de decisiones empresa-
riales.

46
 Ximena Granizo Espinoza

3.2. PROCEDIMIENTO PARA EL MÉTODO SIMPLEX

El procedimiento para el método simplex, basado en la eliminación de

Gauss-Jordan se aplica generalmente en problemas de maximización, pudiendo
también aplicarse a problemas de minimización, ya que todo problema de mini-
mización puede ser convertido en uno de maximización invirtiendo los signos de
los coeficientes, de la siguiente manera:

Min Z = 2X1 + 7X2

Max (-Z) = - 2X1 - 7X2

El método de eliminación de Gauss comienza con el sistema de ecuaciones

original y lo transforma, usando operaciones de fila, en un sistema equivalente en
el cual se puede leer la solución directamente (Budnick, 2007).

Para el desarrollo del método simplex se propone el siguiente problema de

maximización con una serie de restricciones o limitaciones a cumplir, recordando
que el uso de programación lineal enfocado a la administración está principal-
mente orientado a la maximización de utilidades o minimización de recursos,
considerando las limitaciones del sistema, entre las cuales se encuentran la dis-
ponibilidad de recursos humanos y materiales, representadas por las variables del
problema.

Max Z = 30 X1 + 50 X2
Sujeto a:

X1 ≤ 4

X2 ≤ 7

2 X1 + X2 ≤ 12

Con X1, X2 no negativas

47
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Procedimiento:

Paso 1: Igualar la función objetivo a cero trasladando los términos del lado
derecho de la ecuación al lado izquierdo, cambiando de signo los coeficientes.

Función Objetivo: Max Z = 30 X1 + 50 X2

Z - 30 X1 - 50 X2 = 0

Paso 2: Convertir las restricciones en igualdades, mediante el uso de variables

de holgura y artificiales, tal como se muestra en la siguiente tabla:

Tabla 3.1. Coeficientes de variables de holgura y artificiales

según el tipo de restricción.
TIPO DE RESTRICCIÓN COEFICIENTE COEFICIENTE
VARIABLE DE VARIABLE
HOLGURA ARTIFICIAL
+1 0
-1 +1
Igual (=) 0 +1
Aproximadamente igual +1 y -1 0
Fuente: Izar, 2012.

Cuando se tiene las restricciones de tipo menor o igual que, se añade una
variable de holgura, aduciendo a dicha variable el valor que le faltaría al lado iz-
quierdo de la ecuación para lograr la igualdad, en cada ecuación se debe añadir
una variable de holgura diferente, considerando que el problema planteado tiene
tres restricciones del tipo menor o igual que (≤), las ecuaciones quedarían plan-
teadas de la siguiente manera:

X1 ≤ 4
X1 + S1 = 4

48
 Ximena Granizo Espinoza

X2 ≤ 7

X2 + S2 = 7

2 X1 + X2 ≤ 12
2 X1 + X2 + S3 = 12

Paso 3: Conformar la tabla simplex con los coeficientes y variables del proble-
ma, colocando en las columnas las variables y en cada fila los coeficientes que co-
rresponden a la función objetivo y a las restricciones, se debe añadir una columna
para el resultado de las ecuaciones (en este caso representada con la letra R), tal
como se muestra a continuación:

Z X1 X2 S1 S2 S3 R
F1 1 -30 -50 0 0 0 0
F2 0 1 0 1 0 0 4
F3 0 0 1 0 1 0 7
F4 0 2 1 0 0 1 12

Variables de decisión Variables de holgura

Donde:

F1: Coeficientes de la función objetivo. Z - 30X1 - 50X2 = 0

F2: Coeficientes ecuación 1 X1 + S1 = 4
F3: Coeficientes ecuación 2 X2 + S2 = 7
F4: Coeficientes ecuación 3 2 X1 + X2 + S3 = 12

Paso 4: Encontrar el elemento pivote, para lo cual se debe identificar la co-

lumna pivote seleccionando el valor más negativo entre los coeficientes de la fun-
ción objetivo (en este caso se encuentra en X2), luego se procede a dividir el resul-
tado entre cada uno de los coeficientes de la columna (no se divide entre cero ni

49
 Investigación operativa. Programación lineal en las Ciencias Administrativas

entre valores negativos) a continuación, se selecciona la fila pivote y será aquella

que contenga el cociente menor de la división. El elemento pivote es aquel que se
encuentra en la intersección entre de la fila y columna, así:

Z X1 X2 S1 S2 S3 R
F1 1 -30 -50 0 0 0 0
F2 0 1 0 1 0 0 4
F3 0 0 1 0 1 0 7 7÷1=7
F4 0 2 1 0 0 1 12 12÷1=12

Paso 5: Transformar el elemento pivote en uno, esto se logra dividiendo todos

los elementos de la fila para el elemento pivote, en este caso el elemento pivote ya
es uno, por lo que no es necesario realizar este paso.

A manera demostrativa, se presenta el siguiente ejemplo con un elemento

pivote igual a 3, para una mejor comprensión:

Z X1 X2 S1 S2 S3 R
F1 1 -30 -50 0 0 0 0
F2 0 1 0 1 0 0 4
F3 0 0 3 0 1 0 7 F3 ÷3
F4 0 2 1 0 0 1 12

Al dividir la fila 3 para el elemento pivote, el elemento pivote se ha vuelto uno:

Z X1 X2 S1 S2 S3 R
F1 1 -30 -50 0 0 0 0
F2 0 1 0 1 0 0 4
F3 0 0 1 0 0,33 0 2,33
F4 0 2 1 0 0 1 12

50
 Ximena Granizo Espinoza

Paso 6: El siguiente paso es volver cero todos los elementos de la columna

pivote, esto se logra mediante eliminación gaussiana y una serie de iteraciones
entre la fila pivote y las demás filas donde se encuentran los elementos que desean
volverse cero, tal como se muestra a continuación:

Z X1 X2 S1 S2 S3 R
F1 1 -30 -50 0 0 0 0 50F3 + F1
F2 0 1 0 1 0 0 4
F3 0 0 1 0 1 0 7
F4 0 2 1 0 0 1 12 (-1F3 + F4)

En este caso se desea volver cero el elemento -50 de la fila 1 y el elemento 1 de

la fila 4, por lo que se multiplica el mismo elemento con signo invertido, por la fila
del elemento pivote y se suma la fila donde se encuentra el elemento a volver cero.

De esta manera se obtiene la siguiente tabla:

Z X1 X2 S1 S2 S3 R
F1 1 -30 0 0 50 0 350
F2 0 1 0 1 0 0 4
F3 0 0 1 0 1 0 7
F4 0 2 1 0 -1 1 5

Paso 7: A partir de este último paso se repite el procedimiento desde el paso

4, hasta encontrar la solución óptima factible para el problema, de la siguiente
manera:

Selección del elemento pivote (paso 4):

Z X1 X2 S1 S2 S3 R
F1 1 -30 0 0 50 0 350
F2 0 1 0 1 0 0 4 4÷1=4
F3 0 0 1 0 1 0 7
F4 0 2 0 0 -1 1 5 5÷2= 2,5

51
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Volver uno el elemento pivote (paso 5):

Z X1 X2 S1 S2 S3 R
F1 1 -30 0 0 50 0 350
F2 0 1 0 1 0 0 4
F3 0 0 1 0 1 0 7
F4 0 2 0 0 -1 1 5 F4 ÷ 2

Z X1 X2 S1 S2 S3 R
F1 1 -30 0 0 50 0 350
F2 0 1 0 1 0 0 4
F3 0 0 1 0 1 0 7
F4 0 1 0 0 -0,5 0,5 2,5

Volver cero todos los elementos de la columna pivote (paso 6):

Z X1 X2 S1 S2 S3 R
F1 1 -30 0 0 50 0 350
F2 0 1 0 1 0 0 4 30F4 + F1
F3 0 0 1 0 1 0 7 (-1F4 + F2)
F4 0 1 0 0 -0,5 0,5 2,5

Con esta última iteración, ya no existen elementos negativos en las variables

de decisión y se han vuelto ceros y unos todos sus elementos, entonces podría
decirse que se ha encontrado una solución factible la cual debe ser comprobada.
Para encontrar la solución en la tabla simplex, en cada columna se desciende ha-
cia el elemento uno y se dirige hacia el resultado, de la siguiente manera:

Z X1 X2 S1 S2 S3 R
F1 1 0 0 0 35 15 425
F2 0 0 0 1 0,5 -0,5 1,5
F3 0 0 1 0 1 0 7
F4 0 1 0 0 0,5 -0,5 2,5

52
 Ximena Granizo Espinoza

Solución:

Z = 425

X1 = 2,5

X2 = 7

Para comprobar si la solución factible es óptima, se reemplazan los valores de

las variables en cada una de las restricciones del problema verificando si éstas se
cumplen y se calcula Z, así:

Max Z = 30 X1 + 50 X2
Sujeto a:

X1 ≤ 4

X2 ≤ 7

2 X1 + X2 ≤ 12

Con X1, X2 no negativas

La primera restricción del problema es X1 ≤ 4, se reemplaza el valor solución

de X1 en la restricción y se comprueba si se cumple con la misma, en este caso X1
es 2,5 y siendo menor o igual a 4, se cumple con la primera restricción:

√ X1 ≤ 4
X1 = 2,5

Verificando el cumplimiento de la segunda y tercera restricción se tiene:

√ X2 ≤ 7

X2 = 7

√ 2 X1 + X2 ≤ 12

53
 Investigación operativa. Programación lineal en las Ciencias Administrativas

2(2,5) + 7 ≤ 12

12 ≤ 12

En cuanto a la restricción no explícita, se verifica también el cumplimiento,

ya que expresa únicamente la no negatividad de las variables, sin considerar en
este caso que sean enteras:

√ Con X1, X2 no negativas

X1 = 2,5; X2 = 7

Como los valores encontrados para X1 y X2, cumplen con las restricciones
establecidas, se procede a realizar la comprobación de la solución Z = 425, en la
función objetivo:

Max Z = 30 X1 + 50 X2
Max Z = 30(2,5) + 50(7)

Max Z = 75 + 350

√ Max Z = 425

Por lo tanto, se puede decir que la solución encontrada es óptima, interpre-

tándola de la siguiente manera:

Se obtiene un beneficio máximo de Z = 425, con X1 = 2,5 y X2 = 7, es decir, la

empresa obtendría una utilidad máxima de $ 425,00, utilizando una cantidad de
2,5 (unidades, litros, metros, kilos, etc) del recurso X1 y una cantidad de 7 (unida-
des, litros, metros, kilos, etc) del recurso X2.
Con la finalidad de proponer un ejemplo sobre cuál es la utilidad del método
simplex en las ciencias administrativas y la interpretación de la solución obtenida,
a continuación, se presenta el siguiente ejercicio resuelto.

54
 Ximena Granizo Espinoza

Una empresa dedicada a la producción de bienes de consumo tiene a consi-

deración producir dos tipos de productos, basándose en la siguiente información:

DETALLE PRODUCTO A PRODUCTO B

Costo de producción unitario 300 250
Precio de venta $ 465 375
Utilidad por unidad 165 125
Unidades demandadas 200 150
Materia prima requerida kg/u. 2 3
Mano de obra requerida horas/unidad. 4 2
Horas máquina h/unidad. 1 5

Si la empresa cuenta con 2000 kg de materia prima, 1000 horas de mano de

obra y 800 horas máquina. ¿Cuántos productos de cada tipo deberán producirse
con la finalidad de incrementar la utilidad?

La definición de las variables del problema sería la siguiente:

X1 = Cantidad de productos A a producir.

X2 = Cantidad de productos B a producir.

En el problema propuesto se pretende conocer cuántos tipos de cada produc-

to deberán producirse con la finalidad de incrementar la utilidad, por lo tanto, los
coeficientes de la función objetivo serán las utilidades por unidad que genera cada
producto, como se muestra a continuación:

Max Z = 165 X1 + 125 X2

En cuanto a la definición de restricciones, se debe considerar que las canti-
dades de recursos utilizados en la fabricación de los dos tipos de productos no

55
 Investigación operativa. Programación lineal en las Ciencias Administrativas

pueden superar las cantidades de recursos disponibles y tampoco se deberá pro-

ducir un número mayor a las cantidades demandadas de cada producto, como se
detalla a continuación:

S.a.

2X1 + 3X2 ≤ 2000 materia prima disponible

4X1 + 2X2 ≤ 1000 mano de obra disponible (horas)

X1 + 5X2 ≤ 800 horas máquina disponibles

X1 ≤ 200 demanda producto A

X2 ≤ 150 demanda producto B

X1, X2, enteras y no negativas

Z X1 X2 S1 S2 S3 R
F1 1 -165 -125 0 0 0 0
F2 0 2 3 1 0 0 2000 2000÷2=1000
F3 0 4 2 0 1 0 1000 1000÷4=250
F4 0 1 5 0 0 1 800 800÷1=800

Z X1 X2 S1 S2 S3 R
F1 1 -165 -125 0 0 0 0 (165F3+F1)
F2 0 2 3 1 0 0 2000 (-2F3+F2)
F3 0 1 0,5 0 0,25 0 250
F4 0 1 5 0 0 1 800 (-1F3+F4)

Z X1 X2 S1 S2 S3 R
F1 1 0 -42,5 0 41,25 0 41250
F2 0 0 2 1 -0,5 0 1500
F3 0 1 0,5 0 0,25 0 250
F4 0 0 4,5 0 -0,25 1 550

56
 Ximena Granizo Espinoza

Z X1 X2 S1 S2 S3 R
F1 1 0 -42,5 0 41,25 0 41250
F2 0 0 2 1 -0,5 0 1500 1500÷2=750
F3 0 1 0,5 0 0,25 0 250 250÷0,5=500
F4 0 0 4,5 0 -0,25 1 550 550÷4,5=122,22

Z X1 X2 S1 S2 S3 R
F1 1 0 -42,5 0 41,25 0 41250 (42,5F4+F1)
F2 0 0 2 1 -0,5 0 1500 (-2F4+F2)
F3 0 1 0,5 0 0,25 0 250 (-0,5F4+F3)
F4 0 0 1 0 -0,06 0,22 122,22 F4÷4,5

Z X1 X2 S1 S2 S3 R
F1 1 0 0 0 38,89 9,44 46444
F2 0 0 0 1 -0,39 -0,44 1256
F3 0 1 0 0 0,28 -0,11 188,89
F4 0 0 1 0 -0,06 0,22 122,22

Solución:

Z = 46444
X1 = 188,89

X2 = 122,22

57
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Max Z = 165 X1 + 125 X2 Z = 165 (188,89) + 125 (122,22)

S.a. √ Z= 46444, 35

2X1 + 3 X2 ≤ 2000 2(188,89) + 3(122,22) ≤ 2000

4 X1 + 2 X2 ≤ 1000 √ 744,44 ≤ 2000

X1 + 5X2 ≤ 800 4(188,89) + 2(122,22) ≤ 1000

X1 ≤ 200 √ 1000 ≤ 1000

X2 ≤ 150 188,89 + 5(122,22) ≤ 800

X1, X2, enteras y no negativas √ 799,99 ≤ 800

Considerando que el método simplex proporciona una solución matemática

que debe ser interpretada o adaptada a los problemas que se presentan en la vida
real, y que la restricción no explícita menciona que las variables X1 y X2 deben ser
enteras y no negativas, a la empresa corresponde la decisión de aproximar o no el
valor de X1, y producir a su vez 188 o 189 unidades de producto A, y 122 unidades
de producto B, considerando aquella opción que le brinde mayores ingresos, de
esta manera:

t
$PO
91 = 188 y X2 = 122, se obtendría Z = 46270

Z = 165 (188) + 125 (122)

Z = 46270

t
$PO
91 = 189 y X2 = 122, se obtendría Z = 46435

Z = 165 (189) + 125 (122)

Z = 46435

Analizando los valores de Z, a la empresa le convendría producir 189 unida-

des de producto A y 122 unidades de producto B, para obtener un ingreso máxi-
mo de $46435 (dólares), considerando que los valores asignados a las variables
X1 = 189 y X2 = 122, cumplen con todas las restricciones al realizar la comproba-
ción de las mismas:

58
 Ximena Granizo Espinoza

2(189) + 3(122) ≤ 2000

√ 744 ≤ 2000

4(189) + 2(122) ≤ 1000

√ 1000 ≤ 1000

189 + 5(122) ≤ 800

√ 799 ≤ 800

Como se puede evidenciar, mediante dicha comprobación, al producir 189 uni-

dades de producto A y 122 unidades de producto B, la empresa no está excediendo
su disponibilidad de recursos: 2000 kg de materia prima, 1000 horas de mano de
obra y 800 horas máquina, sin exceder además la demanda existente en el mercado
de cada producto (200 unidades de producto A, 150 unidades de producto B).

3.3. MÉTODO BIG M

El método de la Big M también conocido como método de penalización, con-

siste en una derivación del método simplex generalmente utilizado para resolver
problemas de programación lineal con restricciones de tipo mayor o igual que
(≥) o de igualdad (=), pudiendo ser utilizado tanto en problemas de minimiza-
ción como de maximización. Sin embargo, cabe mencionar que su uso se precisa
cuando intervienen variables artificiales en la solución del problema planteado,
siendo M una constante positiva suficientemente grande para representar una
penalización adecuada en la función objetivo.

Regla de penalización para variables artificiales:

Dado M, un valor positivo suficientemente grande (matemáticamente

.

ȷ
FM
DPFĕDJFOUF
PCKFUJWP
EF
VOB
WBSJBCMF
BSUJĕDJBM
SFQSFTFOUB
VOB
QFOBMJ-
zación apropiada si (Taha, 2012):

59
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Coeficiente Objetivo de la - M, en problemas de maximización

variable artificial = + M, en problemas de minimización

Para desarrollar el procedimiento del método Big M, se propone el siguiente

ejercicio planteado de maximización:

Max Z = 9X1 + 11X2

Sujeto a:

3X1 + 2X2 ≤ 19

X1 + X2 = 8

X1 + 3X2 ≥ 18

Con X1, X2 enteras y no negativas

Paso 1: Convertir las restricciones en igualdades, mediante el uso de variables

de holgura y artificiales (Véase Tabla 3.1). Coeficientes de variables de holgura y
artificiales según el tipo de restricción.

La primera restricción es de tipo menor o igual que (≤), por lo que de acuerdo
con la tabla coeficientes de variables de holgura y artificiales, se debe añadir una
variable de holgura, la cual se representará con la letra H, entonces la igualdad
quedaría de la siguiente manera:

3X1 + 2X2 + H1 = 19
Realizando el mismo proceso con la segunda restricción de igualdad, según
la tabla de coeficientes se debe añadir una variable artificial, representada con la
letra F, entonces tenemos:

60
 Ximena Granizo Espinoza

X1 + X2 + F1 = 8

En la tercera restricción, de tipo mayor o igual que (≥), se debe restar una
variable de holgura y añadir una variable artificial, según lo que indica la tabla
de coeficientes de variables de holgura y artificiales según el tipo de restricción,
entonces la restricción quedaría expresada así:

X1 + 3X2 - H2 + F2 = 18
Paso 2: Incluir en la función objetivo todas las variables de holgura y arti-
ficiales añadidas previamente en las restricciones. Las variables de holgura irán
acompañadas del coeficiente cero (0) y las variables artificiales del coeficiente M,
el cual, a su vez irá acompañado del signo + o -, según menciona la regla de pe-
nalización para variables artificiales, al tratarse de un caso de maximización o de
minimización.

En este caso, el objetivo es una maximización, por lo que la variable artificial

F tendrá el coeficiente -M, como se detalla a continuación:

Max Z = 9X1 + 11X2 + 0H1 + 0H2 - MF1 - MF2

Paso 3: Formar la primera tabla considerando todas las variables y expre-
sando las ecuaciones en función de los coeficientes. Los coeficientes del renglón
objetivo se colocan sobre el renglón de variables, de la siguiente manera:

Renglón
objetivo
9 11 0 0 -M -M
Constantes R X1 X2 H1 H2 F1 F2
19 3 2 1 0 0 0
8 1 1 0 0 1 0
18 1 3 0 -1 0 1

Cuerpo Parte identidad

Para buscar la primera solución dentro de la tabla, también llamada solución
básica, dentro de la parte identidad se deben identificar las variables cuyos coefi-
cientes sean +1, para luego agregar a la zona de solución la variable identificada
en la parte identidad junto con el coeficiente del renglón objetivo. Los coeficientes
del renglón objetivo conformarán a su vez la columna objetivo, así:
61
 Investigación operativa. Programación lineal en las Ciencias Administrativas

9 11 0 0 -M -M
R X1 X2 H1 H2 F1 F2
0 H1 19 3 2 1 0 0 0
-M F1 8 1 1 0 0 1 0
-M F2 18 1 3 0 -1 0 1
Columna Zona de
objetivo solución

Las variables que se encuentran en la zona de solución son denominadas va-

riables básicas. De esta manera la primera solución es la siguiente:

H1 = 19

F1 = 8

F2 = 18

Z=0

Siendo Z igual a cero porque no interviene en la zona de solución, al igual que

las variables X1, X2, H2, denominadas no básicas.

Variables no básicas
Variables básicas
X1 = 0
H1 =19
X2 = 0
F1 =8
H2 = 0
F2 =18
Z=0

62
 Ximena Granizo Espinoza

Paso 4: el siguiente paso será conformar el reglón de utilidad o renglón índice

a través de la fórmula siguiente:

Fig. 3.1. Fórmula para generar el renglón índice para maximización.

Sumatoria de los
productos de los
Elemento
elementos de la
correspondiente
columna por el -
a la columna en el
respectivo elemento
renglón objetivo
de la columna
objetivo
Fuente: Izar, 2012.

Es importante mencionar que la fórmula expuesta se usa en problemas de

maximización, en casos de minimización los signos de la fórmula deberán ser
invertidos, más adelante se desarrollará un ejercicio para su demostración.

Renglón Índice:

Al aplicar la fórmula para generar el renglón índice se tiene:

Renglón
objetivo
9 11 0 0 -M -M
R X1 X2 H1 H2 F1 F2
0 H1 19 3 2 1 0 0 0
-M F1 8 1 1 0 0 1 0
-M F2 18 1 3 0 -1 0 1

Columna objetivo

63
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Para X1:

Sumatoria de los productos de los elementos de la columna por el respectivo

elemento de la columna objetivo:

3(0) + 1(-M) + 1(-M) = 0 - 2M

Menos el elemento correspondiente a la columna en el renglón objetivo:

= 0 - 2M - 9

= - 9 - 2M

Para X2:

Sumatoria de los productos de los elementos de la columna por el respectivo

elemento de la columna objetivo:

2(0) + 1(-M) + 3(-M) = 0 - 4M

Menos el elemento correspondiente a la columna en el renglón objetivo:

=0 - 4M - 11

= - 11 - 4M

Para H1:

Sumatoria de los productos:

1(0) + 0(-M) + 0(-M) = 0 + 0 + 0

=0
Elemento correspondiente en el renglón objetivo:

=0-0

64
 Ximena Granizo Espinoza

Para H2:

Sumatoria de los productos:

0(0) + 0(-M) + (-1)(-M) = M

Elemento correspondiente en el renglón objetivo:

=0+M

Para F1:

Sumatoria de los productos:

0(0) + 1(-M) + 0(-M) = 0 - M + 0 = 0 - M

Elemento correspondiente en el renglón objetivo:

= 0 - M - (-M)

=-M+M

=0

Para F2:

Sumatoria de los productos:

0(0) + 0(-M) + 1(-M) = -M

Elemento correspondiente en el renglón objetivo:

= -M - (-M)
=0

65
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Para R:

Sumatoria de los productos:

19(0) + 8(-M) + 18(-M) = -26M

Elemento correspondiente en el renglón objetivo:

= -26M - 0

= 0 - 26M

Cómo puede observarse, cada número índice generado contiene una parte
numérica y una parte M, a continuación, se coloca bajo la tabla simplex en una
fila la parte numérica y en otra fila la parte M, del modo siguiente:

9 11 0 0 -M -M
R X1 X2 H1 H2 F1 F2
0 H1 19 3 2 1 0 0 0
-M F1 8 1 1 0 0 1 0
-M F2 18 1 3 0 -1 0 1
0 -9 -11 0 0 0 0 Parte numérica
-26 -2 -4 0 1 0 0 Parte M

Cuerpo

Paso 5: Este paso consiste en ubicar la columna de trabajo o columna clave,

debiendo observar en la parte M el número índice más negativo que forme parte
del cuerpo de la tabla. En el caso de presentarse un empate, se selecciona al azar.

Siempre que la tabla simplex esté compuesta por las dos partes (parte numé-
rica y parte M), se dará prioridad a la parte con términos en M y luego a la parte
numérica.

En este caso el elemento más negativo es -4, localizado en la columna que

pertenece a X2, por lo que la columna que se encuentra encabezando esa variable
será la columna clave.

66
 Ximena Granizo Espinoza

Columna
clave

9 11 0 0 -M -M
R X1 X2 H1 H2 F1 F2
0 H1 19 3 2 1 0 0 0
-M F1 8 1 1 0 0 1 0
-M F2 18 1 3 0 -1 0 1
0 -9 -11 0 0 0 0
-26 -2 -4 0 1 0 0

A continuación, se debe hallar el renglón de trabajo o renglón clave dividien-

do la columna de constantes entre el elemento que corresponde a la columna
clave, se recuerda que no se debe dividir para números negativos o para cero.
Entonces se tiene:

En la primera fila:

19 ÷ 2 = 9,5

En la segunda fila:

8÷1=8

En la tercera fila:

18 ÷ 3 = 6
El renglón clave será aquel que contenga el menor cociente de las divisiones
realizadas, en este caso se encuentra en la tercera fila, por lo que se procede a se-
ñalar dicho renglón.

9 11 0 0 -M -M
R X1 X2 H1 H2 F1 F2
0 H1 19 3 2 1 0 0 0
-M F1 8 1 1 0 0 1 0
Renglón
-M F2 18 1 3 0 -1 0 1 ÷3
clave
0 -9 -11 0 0 0 0
-26 -2 -4 0 1 0 0

67
 Investigación operativa. Programación lineal en las Ciencias Administrativas

El elemento que se encuentra en la intersección entre la columna y el renglón

clave es el denominado número clave o elemento pivote, en este ejercicio es el nú-
mero 3 y el paso siguiente consiste en volver uno el elemento pivote dividiendo
todo el renglón para dicho elemento. Una vez vuelto uno el elemento pivote se
sustituye la variable y contribución que encabeza el renglón clave por la variable y
contribución que encabeza la columna clave, de la siguiente manera:

9 11 0 0 -M -M
R X1 X2 H1 H2 F1 F2
0 H1 19 3 2 1 0 0 0
-M F1 8 1 1 0 0 1 0
11 F2 6 0,333 1 0 -0,333 0 0,333
0 -9 -11 0 0 0 0
-26 -2 -4 0 1 0 0

La variable X2 al ingresar a la zona de solución, es considerada una variable

básica, en cuanto a la variable artificial F2 al salir de la zona de solución deja de ser
básica. La metodología simplex indica que es posible eliminar de la tabla simplex
las columnas encabezadas por las variables artificiales una vez que dejan de ser
básicas.

El siguiente procedimiento será volver cero todos los elementos que se en-
cuentran arriba y abajo del elemento pivote mediante eliminación gaussiana, tal
como se explicó en la metodología simplex, tal como se indica a continuación:

9 11 0 0 -M -M
R X1 X2 H1 H2 F1 F2
f1 0 H1 19 3 2 1 0 0 0 (-2f3 + f1)
f2 -M F1 8 1 1 0 0 1 0 (-1f3 + f2)
f3 11 X2 6 0,333 1 0 -0,333 0 0,333
f4 0 -9 -11 0 0 0 0 (11f3 + f4)
f5 -26 -2 -4 0 1 0 0 (4f3 + f5)

68
 Ximena Granizo Espinoza

Para la primera fila se tiene:

f1 19 3 2 1 0 0 0 (-2f3 + f1)
6 0,333 1 0 -0,333 0 0,333
7 2,333 0 1 0,667 0,000 -0,667

Para la segunda fila se tiene:

f2 8 1 1 0 0 1 0 (-1f3 + f2)
6 0,333 1 0 -0,333 0 0,333
2 0,667 0 0 0,333 1 -0,333

Para la cuarta fila se tiene:

f4 0 -9 -11 0 0 0 0 (11f3 + f4)

6 0,333 1 0 -0,333 0 0,333
66 -5,333 0 0 -3,667 0 3,667

Para la quinta fila se tiene:

f5 -26 -2 -4 0 1 0 0 (4f3 + f5)

6 0,333 1 0 -0,333 0 0,333
-2 -0,667 0 0 -0,333 0 1,333

Al realizar estas iteraciones se genera la nueva tabla simplex en donde según

lo antes mencionado, se ha omitido la columna correspondiente a la variable F2.

69
 Investigación operativa. Programación lineal en las Ciencias Administrativas

9 11 0 0 -M
R X1 X2 H1 H2 F1
0 H1 7 2,333 0 1 -0,667 0
-M F1 2 0,667 0 0 0,333 1
11 X2 6 0,333 1 0 -0,333 0
66 -5,333 0 0 -3,663 0
-2 -0,667 0 0 -0,333 0

La tabla simplex presenta una nueva solución, la cual no puede ser conside-
rada óptima debido a que todavía existen números negativos en el renglón índice.

Nueva solución:

Variables básicas
Variables no básicas
H1 = 7
X1 = 0
F1 = 2
X2 = 0
X2 = 6
F2 = 0
Z = 66

Paso 6: Este último paso consiste en repetir el paso 5 hasta encontrar la so-
lución óptima al problema planteado, es decir hasta cuando no existan números
negativos en el renglón índice. En el caso de que el procedimiento se vuelva
cíclico (se vuelvan nuevamente negativos los números índice) se detiene el proce-
dimiento ya que no existe solución.

70
 Ximena Granizo Espinoza

Selección de la columna clave:

9 11 0 0 -M
R X1 X2 H1 H2 F1
0 H1 7 2,333 0 1 -0,667 0
-M F1 2 0,667 0 0 0,333 1
11 X2 6 0,333 1 0 -0,333 0
66 -5,333 0 0 -3,663 0
-2 -0,667 0 0 -0,333 0

Selección del renglón clave:

En la primera fila:

7 ÷ 2,333 = 3

En la segunda fila:

2 ÷ 0,667 = 3

En la tercera fila:

6 ÷ 0,333 = 18

Existe un empate entre los cocientes de las divisiones realizadas, por lo que
se procede a seleccionar al azar, en este caso se selecciona la fila 2. Selecionado
el renglón clave, se vuelve uno el elemento pivote diviendo todo el renglón para
dicho elemento.

9 11 0 0 -M
R X1 X2 H1 H2 F1
0 H1 7 2,333 0 1 -0,667 0
-M F1 2 0,667 0 0 0,333 1 ÷ 0,667
11 X2 6 0,333 1 0 -0,333 0
66 -5,333 0 0 -3,663 0
-2 -0,667 0 0 -0,333 0

71
 Investigación operativa. Programación lineal en las Ciencias Administrativas

La variable de la columna clave y su contribución pasan a encabezar el ren-

glón clave, con este procedimiento, la variable artificial F1, sale de la tabla simplex.
El siguiente paso será volver cero los elementos que se encuentran dentro de la
columna clave mediante las operaciones especificadas en cada renglón:

9 11 0 0
R X1 X2 H1 H2
0 H1 7 2,333 0 1 0,667 (-2,333f2 + f1)
9 X1 3 1 0 0 0,5
11 X2 6 0,333 1 0 -0,333 (-0,333f2 + f3)
66 -5,333 0 0 -3,667 (5,333f2 + f4)
-2 -0,667 0 0 -0,333 (0,667f2 + f5)

Con esto la tabla simplex quedaría de la siguiente manera:

9 11 0 0
R X1 X2 H1 H2
0 H1 0 0 0 1 -0,5
9 X1 3 1 0 0 0,5
11 X2 5 0 1 0 -0,5
82 0 0 0 -1
0 0 0 0 0

Al no existir más elementos negativos en el renglón índice, se ha llegado a la

solución del problema planteado, siendo esta la siguiente:
X1 = 3
X2 = 5

Z = 82

72
 Ximena Granizo Espinoza

Obtenida la solución, se procede con la comprobación con la finalidad de

verificar el cumplimiento de las restricciones:

Max Z = 9X1 + 11X2 Comprobación:

Z = 9(3) + 11(5)
Sujeto a:
√ Z = 82
3X1 + 2X2 ≤ 19
3(3) + 2(5) ≤ 19
X1 + X2 = 8 √ 19 ≤ 19
X1 + 3X2 ≥ 18 √3+5=8

X1, X2 enteras y no negativas 3 + 3(5) ≥ 18

√ 18 ≥ 18

En cuanto a la interpretación de la solución obtenida mediante el método Big

M, la empresa deberá asignar un valor de 3 al recurso que representa la variable
X1, un valor de 2 al recurso que representa la variable X2, para obtener una ganan-
cia máxima de Z = 82.

A continuación, se presenta la resolución de un problema de minimización,

el cual generalmente es utilizado por las empresas para resolver problemas de
producción a un costo mínimo:

Min Z = 6X1 + 5X2

Sujeto a:

3X1 + 2X2 ≥ 28

X1 + X2 = 10

X1, X2 enteras y no negativas

Paso 1: Convertir las restricciones en igualdades, mediante el uso de variables

de holgura y artificiales (Véase Tabla 3.1). Coeficientes de variables de holgura y
artificiales según el tipo de restricción.

73
 Investigación operativa. Programación lineal en las Ciencias Administrativas

En este problema de minimización, la primera restricción es de tipo mayor

o igual que (≥), de acuerdo con la tabla coeficientes de variables de holgura y
artificiales, se debe restar una variable de holgura y sumar una variable artificial,
las cuales se representarán con las letras H y F respectivamente, de la siguiente
manera:

3X1 + 2X2 - H1 + F1 = 28
En la segunda restricción de igualdad, según la tabla de coeficientes se debe
añadir una variable artificial, entonces tenemos:

X1 + X2 + F2 = 10

Para nuestra Función objetiva, como es Minimizar tenemos que sumar +MF
de las variables artificiales y las holguras sumarian con +0H.

Paso 2: Incluir en la función objetivo todas las variables de holgura y artificia-

les añadidas previamente en las restricciones. Las variables de holgura se acom-
pañan del coeficiente cero (0) y las variables artificiales del coeficiente M, el cual,
a su vez irá acompañado del sino + o -, según menciona la regla de penalización
para variables artificiales.

El problema propuesto trata de una minimización por lo que la variable arti-

ficial F tendrá el coeficiente +M, como se detalla a continuación:

Min Z = 6X1 + 5X2 - 0H1 + MF1 + MF2

Paso 3: Formar la primera tabla simplex incluyendo todas las variables y ex-
presando las ecuaciones en función de los coeficientes. Cabe recordar que los
coeficientes del renglón objetivo se colocan sobre el renglón de variables, de la
siguiente manera:

Renglón
objetivo
Constantes 6 5 0 M M
R X1 X2 H1 F1 F2
28 3 2 -1 1 0
10 1 1 0 0 1

Cuerpo Parte identidad

74
 Ximena Granizo Espinoza

Parar hallar la primera solución dentro de la tabla se identifican las variables

cuyos coeficientes sean +1 en la parte identidad y se agregan a la zona de solución,
la variable junto con el coeficiente del renglón objetivo. Los coeficientes del ren-
glón objetivo conforman la columna objetivo:

6 5 0 M M
R X1 X2 H1 F1 F2
M F1 28 3 2 -1 1 0
M F2 10 1 1 0 0 1
Columna Zona de
objetivo solución

De esta manera la primera solución es:

F1 = 28

F2 = 10

Z=0

Z es cero debido a que no interviene en la zona de solución, al igual que las

variables X1, X2, H1, denominadas no básicas.

Variables no básicas

Variables básicas X1 = 0

F1 = 28 X2 = 0

F2 = 10 H1 = 0

Z=0

75
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Paso 4: Conformar el reglón de utilidad o renglón índice. En caso de minimi-

zación la formula presenta la siguiente variación:

Fig. 3.2. Fórmula para generar el renglón índice para minimización.

Sumatoria de los
productos de los
Elemento
elementos de la
correspondiente
- columna por el
a la columna en el
respectivo elemento
renglón objetivo
de la columna
objetivo

Fuente: Izar, 2012.

Renglón Índice:

Para X1: 6 - (3(M) + 1(M)) = 6 - 4M

Para X2: 5 - (2(M) + 1(M)) = 5 - 3M

Para H1: 0 - (-1(M) + 0(M)) = 0 + M

Para F1: M - (1(M) + 0(M)) = 0

Para F2: M - (0(M) + 1(M)) = 0

Para R: 0 - (28(M) + 10(M)) = 0 - 38M

Una vez conformado el renglón índice, se integra a la tabla simplex, separan-

do en dos filas la parte numérica y la parte M, tal como se muestra a continuación:

76
 Ximena Granizo Espinoza

6 5 0 M M
R X1 X2 H1 F1 F2
M F1 28 3 2 -1 1 0
M F2 10 1 1 0 0 1
0 6 5 0 0 0 Parte numérica
-38 -4 -3 1 0 0 Parte M

Paso 5: Selección de la columna clave identificando el número índice más

negativo dentro del cuerpo de la tabla en la parte M. En este caso es -4, siendo X1
la variable que encabeza la columna clave:

6 5 0 M M
R X1 X2 H1 F1 F2
M F1 28 3 2 -1 1 0
M F2 10 1 1 0 0 1
0 6 5 0 0 0
-38 -4 -3 1 0 0

Selección del renglón clave: será aquel que contenga el menor cociente como
resultado de dividir las constantes para los elementos de la columna clave:

Para la fila 1: 28 ÷ 3 = 9,33

Para la fila 2: 10 ÷ 1 = 10

El menor cociente es 9,33 por lo que la fila uno será el renglón clave:

6 5 0 M M
R X1 X2 H1 F1 F2
M F1 28 3 2 -1 1 0 ÷3
M F2 10 1 1 0 0 1
0 6 5 0 0 0
-38 -4 -3 1 0 0

77
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Identificado el renglón clave, volver uno el elemento pivote dividiendo todo

el renglón para dicho elemento, realizada la operación, se sustituye la variable y
la contribución que encabeza el renglón clave por la variable y contribución que
encabeza la columna clave. Al realizar esta sustitución, la variable X1 ingresa a la
zona de solución, su contribución 6 pasa a formar parte de la columna objetivo y
se elimina la variable artificial F1 de la tabla simplex:

6 5 0 M
R X1 X2 H1 F2
f1 6 X1 9,333 1 0,667 -0,333 0
f2 M F2 10 1 1 0 1 (-1f1 + f2)
f3 0 6 5 0 0 (-6f1 + f3)
f4 -38 -4 -3 1 0 (4f1 + f4)

A continuación, se vuelven cero todos los elementos que se encuentran den-

tro de la columna clave, de esta manera:

Para la fila dos:

f2 10 1 1 0 1 (-1f1 + f2)
9,333 1 0,667 -0,333 0
0,667 0 0,333 0,333 1

Para la fila tres:

f3 0 6 5 0 0 (-6f1 + f3)
9,333 1 0,667 -0,333 0
-56 0 1 2 0

78
 Ximena Granizo Espinoza

Para la fila cuatro:

f4 -38 -4 -3 1 0 (4f1 + f4)

9,333 1 0,667 -0,333 0
-0,667 0 -0,333 -0,333 0

Paso 6: Repetir desde el paso 5 hasta encontrar la solución óptima:

Selección de la Columna Clave:

6 5 0 M
R X1 X2 H1 F2
6 X1 9,333 1 0,667 -0,333 0
M F2 0,667 0 0,333 0,333 1
-56 0 1 2 0
-0,667 0 -0,333 -0,333 0

Selección del renglón o fila clave:

9,33 ÷ 0,667 = 13,99

0,667÷ 0,333 = 2

La variable X2 y su contribución 5, pasan a la zona de solución y a la colum-

na objetivo respectivamente, la variable F2 y su contribución M, salen de la tabla
simplex:

6 5 0
R X1 X2 H1
6 X1 9,333 1 0,667 -0,333
5 X2 0,667 0 0,333 0,333 ÷ 0,333
-56 0 1 2
-0,667 0 -0,333 -0,333

79
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Volver uno el elemento pivote:

6 5 0
R X1 X2 H1
f1 6 X1 9,333 1 0,667 -0,333
f2 5 X2 2 0 1 1
f3 -56 0 1 2
f4 -0,667 0 -0,333 -0,333

Volver cero todos los elementos dentro de la columna clave:

6 5 0
R X1 X2 H1
f1 6 X1 9,333 1 0,667 -0,333 (-0,667f2 + f1)
f2 5 X2 2 0 1 1
f3 -56 0 1 2 (-1f2 + f3)
f4 -0,667 0 -0,333 -0,333 (0,333f2 + f4)

Para la fila 1:

f1 9,333 1,000 0,667 -0,333 (-0,667f2 + f1)

2 0 1 1
8 1 0 -1

Para la fila 3:

f3 -56 0 1 2 (-1f2 + f3)

2 0 1 1
-58,00 0 0 1

80
 Ximena Granizo Espinoza

Para la fila 4

f4 -0,667 0 -0,333 -0,333 (0,333f2 + f4)

2 0 1 1
0 0 0 0,000

Solución del problema: X1 = 8, X2 = 2, Z = 58

6 5 0 M
R X1 X2 H1 F2
6 X1 8 1 0 -1 0
5 X2 2 0 1 1 1
-58 0 0 1 0
0 0 0 0 0

Comprobación:
Comprobación:
Min Z = 6X1 + 5X2 Z = 6(8) + 5(2)
Sujeto a: √ Z = 58
3(8) + 2(2) ≥ 28
3X1 + 2X2 ≥ 28
√ 28 ≥ 28
X1 + X2 = 10
8 + 2 = 10
X1, X2 enteras y no negativas √ 10 = 10

En cuanto a la interpretación de la solución obtenida mediante el método Big

M, en caso de minimización, la empresa deberá asignar un valor de 8 al recurso
que representa la variable X1, un valor de 2 al recurso que representa la variable
X2, para lograr un costo mínimo en la producción equivalente a Z = 58.

81
 Investigación operativa. Programación lineal en las Ciencias Administrativas

La metodología simplex puede presentar algunos casos especiales al momen-

to de resolver problemas de programación lineal, siendo los más frecuentes los
descritos a continuación:

Desempates en la columna o renglón clave:

Cuando se genera un empate al momento de seleccionar la columna clave, se

puede seleccionar al azar cualquiera de las columnas, únicamente se verá afectado
el desarrollo de la metodología en el número de iteraciones a realizarse.

En caso de que el empate se genere al momento de seleccionar el renglón cla-

ve, también es recomendable seleccionar al azar, sin embargo, si se escoge el ren-
glón equivocado podría darse que el método vaya del primer vértice al segundo
sin producirse cambios en la función objetivo y luego regresar del segundo vértice
al primero, transformándose en un ciclo indefinido sin llegar a la solución final.
Este proceso es conocido como degeneración del simplex y en caso de presentar-
se, se soluciona simplemente cambiando el renglón seleccionado.

No existe variable básica de salida:

Cuando en el desarrollo de la metodología simplex, los elementos de la co-

lumna clave son menores o iguales a cero no es posible seleccionar el renglón
clave, en este caso se denominan problemas de Z no acotada, pudiendo Z ser
infinita o negativa. Este tipo de inconvenientes se presentan al existir errores en
el planteamiento del problema o al haber cometido errores durante la resolución,
para solucionarlo es necesario volver a revisar el planteamiento y los cálculos rea-
lizados para lograr identificar dónde reside el error y corregirlo.

Términos negativos en el segundo miembro de las restricciones:

En caso de presentarse valores negativos en el segundo miembro de las res-

tricciones, se debe multiplicar toda la restricción por (-1) y continuar con la re-

82
 Ximena Granizo Espinoza

solución del problema de manera habitual, como ejemplo se tiene la siguiente

restricción:

2X1 + 3X2 ≥ -4

(-1) 2X1 + 3X2 ≥ -4

-2X1 - 3X2 ≥ 4

Precios Sombra:

Un precio sombra es la cantidad que el valor óptimo de la función objetivo

cambiaría si el lado derecho de una restricción aumentara en una unidad (Bud-
nick, 2007).

Los precios sombra representan la relación existente entre el aumento que

se genera en la función objetivo al aumentar una unidad la constante de una res-
tricción. Los precios sombra se encuentran en los coeficientes de las variables de
holgura en el renglón índice, para una mejor comprensión se presenta el siguiente
ejemplo tomado de Izar (2012):

Max Z = 6X1 + 4X2

Sujeto a:

X1 + 2X2 ≤ 4

3X1 + 2X2 ≤ 8

Con X1, X2 no negativas

La tabla final del problema resuelto por el método Big M es la siguiente:

6 4 0 0
R X1 X2 H1 H2
0 H1 1,333 0 1,333 1 -0,333
6 X1 2,667 1 0,667 0 0,333
16 0 0 0 2
0 0 0 0 0

83
 Investigación operativa. Programación lineal en las Ciencias Administrativas

De esta manera los coeficientes de las variables de holgura en el renglón índi-

ce son los siguientes:

H1 = 0; H2 = 2
Lo cual indica que el precio sombra para la primera restricción es cero y para
la segunda restricción es dos. Al realizar la interpretación se tiene:

Siendo H1 = 0, la función objetivo no aumentará al aumentar una unidad la

constante de la primera restricción (X1 + 2X2 ≤ 4), por ejemplo, si la constante de
la restricción en lugar de 4 fuera 5, no existiría ningún cambio en Z = 16.

Al ser H2 = 2, se tiene que la función objetivo aumentará en dos unidades por

cada unidad que se aumente en la constante de la segunda restricción (3X1 + 2X2
≤ 8), por ejemplo, si en lugar de 8 la constante fuera 9, Z sería igual a 18.

3.4. DUALIDAD

Asociado a cualquier problema lineal también denominado problema prin-

cipal o primal existe un problema que se encuentra estrechamente relacionado
llamado problema dual (Valencia, 2018).

Por lo tanto, la dualidad puede ser interpretada de la siguiente manera: para

cada problema programación lineal de maximización existirá un problema aso-
ciado de minimización y viceversa.

La importancia de la dualidad radica en las siguientes razones (Hillier & Lie-

berman, 2010):

- El problema dual permite ahorrar un gran número de cálculos, sobre todo

cuando el problema primal tiene un número considerable de restricciones
y pocas variables.

- Se relaciona de manera importante con el análisis de sensibilidad, útil para

analizar cómo cambia la función objetivo ante variaciones de las condicio-
nes del problema de programación lineal.

84
 Ximena Granizo Espinoza

- Proporciona información importante sobre la manera óptima de aplicar re-

cursos escasos con el fin de obtener beneficios económicos.

Según Davis & McKeown (1986) el planteamiento del problema dual puede
realizarse a través de los siguientes pasos:

1. Invertir el sentido de la función objetivo. Si el problema primal es de

maximización, el dual será de minimización y viceversa.

2. Invertir el sentido de las desigualdades de las restricciones. Si el signo en

el problema primal es del tipo menor o igual que (≤), en el problema
dual será mayor o igual que (≥) y viceversa.

3. Los coeficientes de la función objetivo en el problema primal pasan a ser

las constantes de las restricciones del problema dual. El problema
dual tendrá entonces tantas restricciones como variables tenga el pri-
mal.

4. Las constantes de las restricciones del problema primal pasan a ser los
coeficientes de la función objetivo del problema dual, por lo tanto, el
problema dual tendrá tantas variables como restricciones tenga el primal.

5. Los coeficientes de las restricciones del problema primal se colocan

de manera que las filas del primal serán las columnas del problema
dual, a su vez las columnas del primal pasan a ser las filas del dual.

6. Las variables del problema primal son denominadas X, en tanto que las
variables del dual son denominadas Y, debiendo ser no negativas.

Para ilustrar los pasos para el planteamiento del problema dual, se presenta el
ejercicio de maximización resuelto por el método Big M:

85
 Investigación operativa. Programación lineal en las Ciencias Administrativas

función objetivo.

Max Z = 9X1 + 11X2

Sujeto a:
Constantes de las
3X1 + 2X2 ≤ 19 restricciones

X1 + X2 = 8

X1 + 3X2 ≥ 18

Con X1, X2 enteras y no negativas

Paso 1. Invertir el sentido de la función objetivo: siendo el problema primal

de maximización, el problema dual será de minimización. Para identificar el pro-
blema dual se puede agregar como subíndice la letra D, así:

Min ZD =
Paso 2. Invertir el sentido de las desigualdades de las restricciones, las restric-
ciones de igualdad mantienen el signo.

Paso 3. Los coeficientes de la función objetivo 9 y 11 del problema primal

pasan a ser las constantes de las restricciones del problema dual. Entonces el pro-
blema dual tendrá en este caso únicamente dos restricciones.

Paso 4. Las constantes de las restricciones del problema primal 19, 8 y 18 pa-
san a ser los coeficientes de la función objetivo del problema dual, el cual tendrá
a su vez tres variables: Y1, Y2, Y3:
Min ZD = 19Y1 + 8Y2 + 18Y3

Paso 5. Los coeficientes de las restricciones de las filas del primal serán las
columnas del problema dual o a su vez las columnas del primal pasan a ser las
filas del dual

86
 Ximena Granizo Espinoza

Coeficientes del primal

3 2

1 1

1 3

Paso 6. Las variables del problema primal son denominadas X, en tanto que
las variables del dual son denominadas Y.

Finalmente, el problema dual será:

Min ZD = 19Y1 + 8Y2 + 18Y3

Sujeto a:

3Y1 + Y2 + Y3 ≥ 9

2Y1 + Y2 + 3Y3 = 11

Con Y1, Y2, Y3 no negativas

La resolución del problema dual puede hacerse mediante el método simplex

tradicional o mediante el método Big M, en este caso al ser un problema de mini-
mización se utilizará el método Big M:

Paso 1: Convertir las restricciones en igualdades, considerando el uso de va-

riables de holgura y artificiales de la Tabla 3.1. Coeficientes de variables de holgu-
ra y artificiales según el tipo de restricción.

Para la primera restricción:

3Y1 + Y2 + Y3 - H1 + F1 = 9

87
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Para la segunda restricción:

2Y1 + Y2 + 3Y3 + F2 = 11

Paso 2: Incluir en la función objetivo todas las variables de holgura y artificia-

les añadidas previamente en las restricciones:

Min ZD = 19Y1 + 8Y2 + 18Y3 - 0H1 + MF1 + MF2

Paso 3: Formar la primera tabla simplex:

19 8 18 0 M M
R Y1 Y2 Y3 H1 F1 F2
M F1 9 3 1 1 -1 1 0
M F2 11 2 1 3 0 0 1
Columna Zona de
objetivo solución

Paso 4: Conformar el reglón de utilidad o renglón índice:

Para Y1: 19 - (3(M) + 2(M)) = 19 - 5M

Para Y2: 8 - (1(M) + 1 (M)) = 8 - 2M

Para Y3: 18 - (1(M) + 3(M)) = 18 - 4M

Para H1: 0 - (-1(M) + 0(M)) = 0 + M

Para F1: M - (1(M) + 0(M)) = 0

Para F2: M - (0(M) + 1(M)) = 0

Para R: 0 - (9(M) + 11(M)) = 0 - 20M

Con esto la tabla simplex sería:

88
 Ximena Granizo Espinoza

19 8 18 0 M M
R Y1 Y2 Y3 H1 F1 F2
M F1 9 3 1 1 -1 1 0
M F2 11 2 1 3 0 0 1
0 19 8 18 0 0 0 Parte numérica
-20 -5 -2 -4 1 0 0 Parte M
Columna
clave

Selección del renglón clave:

19 8 18 0 M M
R Y1 Y2 Y3 H1 F1 F2
19 Y1 9 3 1 1 -1 1 0 9÷3=3
M F2 11 2 1 3 0 0 1 11 ÷ 2 = 5,5
0 19 8 18 0 0 0
-20 -5 -2 -4 1 0 0

Volver uno el elemento pivote y cero todos los elementos dentro de la colum-
na clave:

19 8 18 0 M M
R Y1 Y2 Y3 H1 F1 F2
f1 19 Y1 3 1 0,333 0,3333 -0,333 0,333 0
f2 M F2 11 2 1 3 0 0 1 (-2f1 + f2)
f3 0 19 8 18 0 0 0 (-19f1 + f3)
f4 -20 -5 -2 -4 1 0 0 (5f1 + f4)

89
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Fila dos:

f2 11 2 1 3 0 0 1 (-2f1 + f2)
3 1 0,333 0,333 -0,333 0,333 0
5 0 0,333 2,333 0,667 -0,667 1

Fila tres:

f3 0 19 8 18 0 0 0 (-19f1 + f3)
3 1 0,333 0,333 -0,333 0,333 0
-57 0 1,667 11,667 6,333 -6,333 0

Fila cuatro:

f4 -20 -5 -2 -4 1 0 0 (5f1 + f4)

3 1 0,333 0,333 -0,333 0,333 0
-5 0 -0,333 -2,333 -0,667 1,667 0

Con esto la nueva tabla simplex sería la siguiente, y la columna clave aquella
encabezada por la variable Y3:

19 8 18 0 M M
R Y1 Y2 Y3 H1 F1 F2
19 Y1 3 1 0,333 0,333 -0,333 0,333 0 3 ÷ 0,333 = 9
M F2 5 0 0,333 2,333 0,667 -0,667 1 5 ÷ 2,333 = 2,14
-57 0 1,667 11,667 6,333 -6,333 0
-5 0 -0,333 -2,333 -0,667 1,667 0

90
 Ximena Granizo Espinoza

Volver uno el elemento pivote y cero todos los elementos dentro de la colum-
na clave:

19 8 18 0 M M
R Y1 Y2 Y3 H1 F1 F2
f1 19 Y1 3 1 0,333 0,333 -0,333 0,333 0 (-0,333f2 + f1)
f2 18 Y3 2,142 0 0,143 1 0,286 -0,286 0,428
f3 -57 0 1,667 11,667 6,333 -6,333 0 (-11,667f2 + f3)
f4 -5 0 -0,333 -2,333 -0,667 1,667 0 (2,333f2 + f4)

Fila uno:

f1 3 1 0,333 0,333 -0,333 0,333 0 (-0,333f2 + f1)

2,142 0 0,143 1 0,286 -0,286 0,428
2,286 1 0,286 0,0004 -0,428 0,428 -0,14

Fila tres:

f3 -57 0 1,667 11,667 6,333 -6,333 0 (-11,667f2 + f3)

2,142 0 0,143 1 0,286 -0,286 0,428
-82 0 0 0 3 -3 -5

Fila cuatro:

f4 -5,000 0 -0,333 -2,333 -0,667 1,667 0 (2,333f2 + f4)

2,142 0 0,143 1 0,286 -0,286 0,428
0 0 0 0 0 1 1

91
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Con estas iteraciones, al no existir más elementos negativos en el renglón

índice, la tabla simplex final sería la siguiente:

19 8 18 0 M M
R Y1 Y2 Y3 H1 F1 F2
19 Y1 2,286 1 0,286 0 -0,428 0,428 -0,143
18 Y3 2,142 0 0,143 1 0,286 -0,286 0,428
-82 0 0 0 3 -3 -5 Solución del
primal
0 0 0 0 0 1 1

Solución del problema dual:

Y1 = 2,29

Y2 = 0

Y3 = 2,14

Z = 82

Comprobación: Z = 19(2,29) + 8(0) + 18(2,14)

√ Z = 82
Min ZD = 19Y1 + 8Y2 + 18Y3

Sujeto a:
3(2,29) + 0 + 2,14 ≥ 9
3Y1 + Y2 + Y3 ≥ 9 √9≥9
2Y1 + Y2 + 3Y3 = 11 2(2,29) + 0 + 3(2,14) = 11

Con Y1, Y2, Y3 no negativas √ 11 = 11

√ X1, X2 no negativas

92
 Ximena Granizo Espinoza

La importancia del problema dual radica en que, al resolverse, proporciona

la solución del primal y el mismo valor de Z, como se puede verificar en la reso-
lución del problema primal, cuyo resultado por el método Big M fue el siguiente:

9 11 0 0
R X1 X2 H1 H2
0 H1 0 0 0 1 -1,831
9 X1 3 1 0 0 0,499
11 X2 5 0 1 0 -0,499
82 0 0 0 -1
0 0 0 0 0

La interpretación de la solución del problema dual proporcionada una visión

sobre la manera óptima de utilizar los recursos que se dispone (Hillier & Lieber-
man, 2010).

Por lo tanto, se debe estar dispuesto a pagar un costo mayor por un recurso
hasta por el valor de su variable dual correspondiente a la solución (Izar, 2012).

Por ejemplo, en la resolución del dual Y1 = 2,29, lo cual quiere decir que se
podría pagar como máximo $ 2, 29 por cada unidad extra utilizada de dicho re-
curso.

3.5. RESOLUCIÓN DE PROBLEMAS DE

PROGRAMACIÓNLINEAL MEDIANTE SOLVER

Solver es una herramienta de complemento de Microsoft Office Excel que

permite llevar a cabo análisis matemáticos orientados a la logística o a la pro-
ducción, determinando el valor máximo o mínimo de la celda objetivo, la cual se
encuentra sujeta a las restricciones establecidas en los valores de otras celdas de
la hoja de cálculo.

93
 CAPÍTULO IV
MÉTODO GRÁFICO

3.1. INTRODUCCIÓN

El método de resolución gráfica es una forma sencilla de resolver modelos de

programación lineal con dos variables de decisión (Eppen, Gould, Schmidt, Moore,
& Weatherford, 2000). Es un procedimiento simple de resolución, mediante la grá-
fica de las ecuaciones de las restricciones en el plano cartesiano, representado cada
variable en cada uno de los ejes para luego encontrar el punto factible de solución.

En este libro se presentan casos de resolución con dos variables, siendo los
problemas que con más frecuencia se resuelven con el método gráfico, al ser más
sencillos y representar de forma más didáctica el procedimiento de solución (Da-
vis & McKeown, 1986).

4.2. PROCEDIMIENTO PARA EL MÉTODO GRÁFICO

Para resolver problemas de programación lineal mediante el método gráfico,

se pueden seguir lo siguientes pasos (Thierauf & Grosse, 1990):

Paso 1: Plantear el problema: Convertir los datos del problema en un sistema

de ecuaciones.

Paso 2: Representar cada variable del problema en cada uno de los ejes del
plano cartesiano, para luego proceder a graficar las ecuaciones de las restriccio-
nes. Delimitar la zona de solución factible, de acuerdo con el tipo de restricción
planteada (mayor o igual que, menor o igual que, igualdad) en el problema.
112
 Paso 3: Graficar la ecuación de la función objetivo dando diferentes valores
a Z, para encontrar aquel punto que toca la zona factible de solución. Este paso
puede ser omitido, al desarrollar directamente el paso 4.

Paso 4: Hallar la solución del problema, aquella que permita optimizar la fun-
ción objetivo. En el caso de que una recta sea paralela a la función objetivo, pue-
den existir varias soluciones óptimas, caso contrario existirá una sola solución.

Este último paso puede también desarrollarse encontrando el valor de Z en

cada uno de los vértices que forman la zona factible de solución, considerando
que la solución se encontrará siempre en uno de los vértices de la zona factible,
dependiendo si se trata de un caso de maximización o de minimización.

En la actualidad existen varios softwares que facilitan la resolución de pro-

blemas de programación lineal como TORA y GeoGebra y varias herramientas
en línea como PHPSimplex, Atozmath, Simplex Method Calculator, entre otras.

A continuación, se presentan ejercicios resueltos para ilustrar el procedimiento.

4.3. MÉTODO GRÁFICO CASO DE MAXIMIZACIÓN

Resolver mediante el método gráfico el siguiente problema de maximización:

Max Z = 0,5X1 + 0,4X2

Sujeto a:

2X1 + X2 ≤ 20

X1 + X2 ≤ 16

Con X1, X2 no negativas

113
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Solución:

El primer paso será convertir las restricciones del problema en un sistema de

ecuaciones. Llámase ecuación lineal de n incógnitas (o variables), la ecuación de
la forma (Skorniakov, 1998):

a1x1 + a2x2 +…. anxn = b

Donde a1, a2, … an, b son los números reales dados. Los números a1, a2, …
an, son los coeficientes de la ecuación, mientras que el número b su término in-
dependiente.

En el problema dado se tiene un sistema de ecuaciones conformado por las

dos restricciones existentes, tal como se muestra a continuación:

1 2X1 + X2 = 20
2 X1 + X2 = 16

El paso siguiente será representar cada variable del problema en cada uno
de los ejes del plano cartesiano y graficar las ecuaciones de las restricciones, con
la finalidad de encontrar o delimitar la zona factible de solución. En este caso, se
representará a la variable X1 en el eje de las abscisas x y la variable X2 en el eje de
las ordenadas y.

Para graficar la recta de la ecuación, la manera más sencilla es asignar el valor

de cero a cada variable con la finalidad de encontrar los puntos a señalar en el
plano cartesiano, tal como se ilustra a continuación:

Cuando X1 toma el valor de cero, X2 = 20, obteniendo el primer punto de la

recta.

2X1 + X2 = 20

0 + X2 = 20 (0; 20)

Cuando X2 toma el valor de cero, X1 = 20, obteniendo el segundo punto para

la recta.

2X1 + X2 = 20
2X1 + 0 = 20

114
 Ximena Granizo Espinoza

X1 = 20/2

X1 = 10 (10; 0)

Al unir los puntos (0; 20) y (10; 0), se obtiene la recta de la primera ecuación,
como muestra la Fig. 4.1.

Fig. 4.1. Recta de la ecuación 2X1 + X2 = 20.

Al tratarse de una restricción de tipo menor o igual que (≤), la zona que se
encuentra bajo la recta es aquella que cumple la restricción.

Para graficar la recta de la segunda ecuación se realiza el mismo procedi-

miento:

Cuando X1 toma el valor de cero, X2 = 16, obteniendo el primer punto de la recta.

X1 + X2 = 16

0 + X2 = 16 (0; 16)

Cuando X2 toma el valor de cero, X1 = 16, obteniendo así, el segundo punto

para la recta.

115
 Investigación operativa. Programación lineal en las Ciencias Administrativas

X1 + X2 = 16

X1 + 0 = 16

X1 = 16 (16; 0)

La segunda recta se obtiene al unir los puntos (0; 16) y (16; 0), como muestra
la Fig. 4.2.

Fig. 4.2. Recta de la ecuación X1 + X2 = 16.

De igual manera, la zona que se encuentra bajo la recta de la ecuación 2, es

aquella que cumple con la segunda restricción, siendo esta de tipo menor o igual
que (≤).

Como se puede visualizar en la Fig.4.3., la intersección de las dos rectas forma

un polígono cuyos vértices A, B, C y D, delimitan la zona factible de solución que
cumple con las dos restricciones. El paso siguiente será encontrar en cuál de los
vértices de la zona factible se obtiene la solución óptima para el problema.

116
 Ximena Granizo Espinoza

Fig. 4.3. Zona factible de solución.

Para determinar los valores de X1, X2 en el vértice B se aplica uno de los mé-
todos para resolver un sistema de ecuaciones lineales, en este caso se utilizará el
método de sustitución.

El método de sustitución consiste en despejar una de las incógnitas en una

ecuación y sustituir la expresión obtenida en la otra ecuación, resultando una
ecuación de una incógnita que se resuelve por el método de solución de ecuacio-
nes lineales. Una vez encontrado el valor de una de las incógnitas por sustitución
se encuentra el valor de la otra (Riquenes, 2012).

En el sistema de ecuaciones dado tenemos dos incógnitas (las variables X1 y

X2), para despejar una de las incógnitas de la ecuación, se escogerá aquella ecua-
ción menos compleja o más fácil de despejar, en este caso se procederá a despejar
la variable X1 en la segunda ecuación:
2 X1 + X2 = 16

X1 = 16 - X2

117
 Investigación operativa. Programación lineal en las Ciencias Administrativas

A continuación, se sustituye el valor de X1 en la primera ecuación para obte-

ner el valor de X2:
1 2X1 + X2 = 20

2(16 - X2) + X2 = 20

32 - 2X2 + X2 = 20

32 - X2 = 20

- X2 = 20 - 32

- X2 = -12

X2 = 12

Finalmente, para conocer el valor de X1 se sustituye el valor de X2 en cual-

quiera de las ecuaciones del sistema, en este caso se reemplazará en la segunda
ecuación:

2 X1 + X2 = 16
X1 + 12 = 16

X1 = 16 – 12

X1 = 4

De esta manera se obtiene los valores del vértice B= (4, 12).

El tercer paso consiste en graficar la recta de la función objetivo asignando dife-

rentes valores a Z, encontrando el vértice que proporcione una mejor solución. Tal
como indica el procedimiento para el método gráfico, el paso 3 puede ser omitido
y pasar directamente al paso 4 que consiste en encontrar el valor de Z en cada uno
de los vértices que forman la zona factible de solución (Thierauf & Grosse, 1990).

La zona factible de solución en este problema de maximización se encuentra

delimitada por los vértices A, B, C, D, (Fig. 4.3.), a continuación, se procederá a
desarrollar directamente el paso 4, determinando el valor de Z en cada uno de los
vértices.

Para determinar el valor de Z en el vértice A= (0,16), se reemplazan los valo-

res de X1 y X2 en la función objetivo, de la siguiente manera:

118
 Ximena Granizo Espinoza

Z = 0,5X1 + 0,4X2

Z = 0,5(0) + 0,4(16)

Z = 6,4

Obteniendo como resultado Z= 6,4 en el vértice A, donde X1 = 0 y X2 = 16,

siendo este el primer punto para la gráfica de la función objetivo. El otro punto
para graficar la recta será X2 = 0, tal como se muestra a continuación:
Z = 6,4 = 0,5X1 + 0,4X2

6,4 = 0,5X1 + 0,4(0)

6,4 = 0,5X1

X1 = 6,4 ÷ 0,5

X1 = 12,8

Entonces se obtiene el segundo punto para la gráfica de la recta de la función

objetivo (X1= 12,8 y X2 = 0). Fig.4.4.

Fig. 4.4. Gráfica de la función objetivo en el vértice A.

119
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Para obtener el valor de Z en el punto B, se desplaza la recta de la función obje-

tivo hacia el vértice y se reemplazan los valores de X1 y X2 en la función objetivo, así:
Z = 0,5X1 + 0,4X2

Z = 0,5(4) + 0,4(12)

Z = 6,8

Obteniendo como resultado Z = 6,8 en el vértice B = (4,12) (Fig.4.5).

Fig. 4.5. Gráfica de la función objetivo en el vértice B.

Finalmente se desea conocer el valor de Z en el vértice C= (10,0), en donde

al reemplazar los valores del vértice en la función objetivo se obtiene lo siguiente:

Z = 0,5X1 + 0,4X2

Z = 0,5(10) + 0,4(0)

Z=5

120
 Ximena Granizo Espinoza

Siendo el primer punto para la gráfica de la función objetivo X1=10, X2=0,

es necesario determinar un segundo punto, el cual será cuando X1=0, entonces:

Z = 5 = 0,5(0) + 0,4X2

5 = 0 + 0,4X2

X2 = 5 ÷ 0,4

X2 = 12,5

Obteniendo de esta manera el segundo punto para la gráfica de la función

objetivo X1 = 0, X2 = 12,5 tal como se ilustra en la Fig. 4.6.

Fig. 4.6. Gráfica de la función objetivo en el vértice C.

121
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Luego de calcular los valores de Z en los vértices de la zona factible de solu-

ción: A, B y C, se determinó que:

En el vértice A= (0,16), Z= 6,4

En el vértice B= (4,12), Z= 6,8

En el vértice C= (10, 0), Z= 5

Cabe señalar que no es pertinente calcular el valor de Z en el vértice D= (0,0),

ya que, en este punto Z= 0.

En este caso particular la solución óptima para el problema es el vértice B, en

donde X1 = 4 y X2 = 12, ya que se trata de un problema de maximización, entonces:

Solución:

Z = 6,8

X1 = 4

X2 = 12

Comprobación: Z = 0,5(4) + 0,4(12)

Max Z = 0,5X1 + 0,4X2 √ Z = 6,8

Sujeto a: 2(4) + 12 ≤ 20
√ 20 ≤ 20
2X1 + X2 ≤ 20
4 + 12 ≤ 16
X1 + X2 ≤ 16 √ 16 ≤ 16
Con X1, X2 no negativas √ X1, X2 no negativas

Realizada la comprobación, el paso siguiente es interpretar la solución obte-

nida mediante el método gráfico y adaptarla al problema presentado en la vida
real.

122
 Ximena Granizo Espinoza

4.4. MÉTODO GRÁFICO CASO DE MINIMIZACIÓN

Resolver mediante el método gráfico el siguiente problema de minimización:

Min Z = 6X1 + 8X2

Sujeto a:

2X1 + X2 ≥ 18

X1 ≥ 6

X2 ≥ 5

Con X1, X2 no negativas

Solución:

El primer paso es convertir las restricciones del problema en un sistema de

ecuaciones, entonces:

1 2X1 + X2 = 18
2 X1 = 16

3 X2 = 5

El siguiente paso es representar las variables del problema en cada uno de los
ejes del plano cartesiano, graficar las ecuaciones de las restricciones y encontrar la
zona factible de solución, X1 se ubicará en el eje x y la variable X2 en el eje y.
La manera más sencilla de graficar la recta de una ecuación es asignar el valor
de 0 a cada variable con la finalidad de determinar los dos puntos a señalar en el
plano cartesiano, de la siguiente manera:

Cuando X1 toma el valor de cero, X2 = 18, obteniendo el primer punto para la

recta de la primera ecuación:

123
 Investigación operativa. Programación lineal en las Ciencias Administrativas

2X1 + X2 = 18

0 + X2 = 18 (0; 18)

Cuando X2 toma el valor de cero, X1 = 9, obteniendo el segundo punto para

la recta.

2X1 + X2 = 18

2X1 + 0 = 18

X1 = 18/2

X1 = 9 (9; 0)

Al unir los puntos (0; 18) y (9; 0), se obtiene la recta de la primera ecuación.
Fig. 4.7.

Fig. 4.7. Recta de la ecuación 2X1 + X2 = 18.

Siendo una restricción de tipo mayor o igual que (≥), la zona que cumple con
la condición es aquella que se encuentra sobre la recta.

124
 Ximena Granizo Espinoza

Graficar las rectas de la segunda ecuación (X1 = 16) y de la tercera ecuación (X2
= 5), es un procedimiento muy sencillo ya que al ser ecuaciones con una sola in-
cógnita (variable), las rectas serán paralelas a cada uno de los ejes. Fig.4.8 y Fig. 4.9.

Fig. 4.8. Recta de la ecuación X1 = 16.

Fig. 4.9. Recta de la ecuación X2 = 5.

125
 Investigación operativa. Programación lineal en las Ciencias Administrativas

En las restricciones de igualdad, la solución puede localizarse en cualquier

punto de la recta. En el ejercicio propuesto existe una restricción de tipo menor o
igual que (≤) y dos restricciones de igualdad (=), por lo que se debe ubicar aquel
punto dentro de la zona factible que cumpla con las tres restricciones y con el ob-
jetivo de minimización, considerando en este caso, que la zona factible es aquella
que se encuentra sobre la recta y que no existe ningún polígono que la delimite.

La Fig. 4.10., muestra la zona factible de solución del problema, identificando

los vértices A, B, C y D con la finalidad de analizar en cuál de éstos se encuentra
la solución óptima del problema.

Fig. 4.10. Zona factible de solución.

Para determinar los valores de los vértices que se encuentran dentro de la

zona factible de solución, se resuelve mediante sistema de ecuaciones, en este caso
particular, se tiene los vértices A, B= (16, 5), C= (9, 0),) y D= (16, 0). Los vértices
C y D quedarían excluidos de la solución al no cumplir con la restricción X2 ≥ 5.
A continuación, se aplica el método de sustitución entre las ecuaciones 1 y 3
para conocer los valores del vértice A. La ecuación 3, al ser de una sola incógnita

126
 Ximena Granizo Espinoza

(variable), proporciona directamente el valor de la variable X2= 5, por lo que se

sustituye el valor de X2 en la primera ecuación, así:
1 2X1 + X2 = 18 2X1 + X2 = 18

2 X2 = 5 2X1 + 5 = 18

2X1 = 18 – 5

X1 = 6,5

Como solución se tiene A = (6,5; 5).

El vértice B= (16, 5), al ser la intersección de las rectas de las ecuaciones 2 y 3,

se conocen los valores para X1 y X2, por lo que no es necesario resolver mediante
sistema de ecuaciones.

Tal como indica el procedimiento para la resolución del método gráfico, en

este caso se omitirá el tercer paso (gráfica de la función objetivo) y se procederá
con el cuarto paso, encontrando el valor de Z los vértices A y B que se encuentran
dentro de la zona factible de solución, como se muestra a continuación:

En el vértice A= (6,5; 5):

Min Z = 6X1 + 8X2

Min Z = 6(6,5) + 8(5)

Min Z = 79

Obteniendo como resultado en este punto Z = 79, con X1 = 6,5 y X2 = 5.

En el vértice B= (16, 5):

Min Z = 6X1 + 8X2

Min Z = 6(16) + 8(5)

Min Z = 136

Obteniendo como resultado en este punto Z = 136, con X1 = 16 y X2 = 5.

Según los valores de Z obtenidos en los vértices A y B, se determina que la solución

óptima para el problema de minimización la proporciona el vértice A= (6,5; 5), ya arroja
como resultado un valor de Z menor que aquel que proporcional el vértice B, entonces:

127
 Investigación operativa. Programación lineal en las Ciencias Administrativas

Solución:

Z = 79, con X1 = 6,5 y X2 = 5.

Como último paso, se realiza la comprobación de la solución:

Comprobación:
Z = 6(6,5) + 8(5)
Min Z = 6X1 + 8X2 √ Z = 79
Sujeto a: 2(6,5) + 5 ≥ 18

2X1 + X2 ≥ 18 √ 18 ≥ 18
X1 ≥ 6
X1 ≥ 6
√ 6,5 ≥ 6
X2 ≥ 5 X2 ≥ 5
Con X1, X2 no negativas √5≥5

√ X1, X2 no negativas

128