REPÚBLICA BOLIVARIANA DE VENEZUELA

MINISTERIO DEL PODER POPULAR PARA LA EDUCACIÓN UNIVERSITARIA

CIENCIA Y TECNOLOGIA

UNIVERSIDAD POLITÉCNICA TERRITORIAL JOSÉ ANTONIO ANZOÁTEGUI

UNIDAD I: PROGRAMACION LINEAL

Facilitadora: Elaborado por:

Ing. Blanca Calzadilla. T.S.U. José Yaguarin C.I 19.248.992

T.S.U. Carlos Toledo C.I 17. 223.539

Barcelona, mayo de 2025

 INDICE
INTRUDUCCIÓN ......................................................................................................................................3

Programación lineal ...............................................................................................................................4

Método simplex .................................................................................................................................... 14

Variables de decisión ......................................................................................................................... 24

Restricciones ........................................................................................................................................ 25

Función objetiva .................................................................................................................................. 30

Soluciones básicas ............................................................................................................................. 32

Variables de holgura ........................................................................................................................... 35

Variable de exceso .............................................................................................................................. 36

Variables irrestrictas........................................................................................................................... 38

Variables artificiales ........................................................................................................................... 40

Método simplex primal ....................................................................................................................... 41

Método simplex dual........................................................................................................................... 45

Método gráfico ..................................................................................................................................... 49

CONCLUSIÓN ....................................................................................................................................... 51

Bibliografía ............................................................................................................................................ 53
 INTRUDUCCIÓN

La Programación Lineal es una herramienta matemática fundamental en el campo de

la Investigación de Operaciones, diseñada para optimizar la toma de decisiones en contextos donde

los recursos son limitados. Desde su formalización en la década de 1940 por George Dantzig, quien

desarrolló el algoritmo Símplex, la PL se ha consolidado como un pilar en la resolución de problemas

de asignación de recursos, planificación estratégica y gestión eficiente en sectores como la logística, la

manufactura, las finanzas y la energía. Su capacidad para modelar situaciones reales mediante

funciones lineales y restricciones la convierte en una metodología versátil y aplicable a múltiples

escenarios.

En esencia, la Programación Lineal busca maximizar o minimizar una función objetivo lineal,

sujeta a un conjunto de restricciones lineales que definen las condiciones del problema. Por ejemplo,

una empresa podría utilizarla para determinar la combinación óptima de productos que maximice sus

ganancias, considerando limitaciones en materias primas, horas laborales o capacidad de

almacenamiento. Este enfoque no solo permite identificar soluciones óptimas, sino también analizar la

sensibilidad de los resultados ante cambios en los parámetros del modelo, lo que facilita la adaptación

a entornos dinámicos.

En este trabajo, se abordarán los fundamentos teóricos de la Programación Lineal, incluyendo

la formulación de modelos, los métodos de solución (como el Símplex y el método gráfico), y su

implementación práctica mediante herramientas computacionales (ej: Python, MATLAB o software

especializado como Gurobi). Además, se presentará un caso de estudio en el que se aplicará la PL a

un problema real, demostrando su utilidad para mejorar la eficiencia operativa y reducir costos.

Finalmente, se discutirán las limitaciones de la PL y las extensiones hacia modelos más complejos,

como la Programación Entera o la Programación No Lineal.

 Programación lineal

La programación lineal es una técnica matemática utilizada para optimizar (maximizar o

minimizar) una función lineal, llamada función objetivo, sujeta a un conjunto de restricciones,

expresadas mediante un sistema de ecuaciones o inecuaciones también lineales. Es ampliamente

aplicada en áreas como economía, logística, ingeniería y gestión empresarial.

Es importante considerar que lo que es programación lineal en investigación de operaciones

está compuesta por dos elementos fundamentales: la región factible y las restricciones estructurales y

de no negatividad.

Región factible:

Al conjunto de valores que satisfacen todas las restricciones, se les denomina región factible,

que se le cataloga como un espacio de solución o de todos los puntos posibles de un problema de

optimización que satisface las restricciones del problema, incluyendo las potencialidades, las

igualdades y las restricciones enteras.

Las restricciones estructurales y de no negatividad:

A las restricciones se les llama restricciones de no negatividad y, se le conocen como

condiciones del modelo que estipulan que las variables de decisión deben tener solo valores no

negativos, es decir, positivos o nulos.

Tipos de soluciones en la programación lineal

Los programas lineales que tienen dos variables se clasifican de acuerdo al tipo de solución que

presenten y, pueden ser los siguientes:

Factibles
 Cuando existe un conjunto de soluciones o valores que satisfacen las restricciones, estas

pueden dividirse en solución única o con solución múltiple. Además, se puede encontrar una solución

no acotada.

En el área de optimización matemática, una región factible o un conjunto factible es un espacio

de búsqueda o un espacio de solución, es decir, es el conjunto de todos los puntos posibles de un

problema de optimización que satisface las restricciones del problema.

No factibles

Sucede cuando no existe un conjunto de soluciones que cumplan las restricciones, es decir,

cuando estas son inconsistentes.

Áreas de aplicación

Para comprender mejor qué es programación lineal en investigación de operaciones se deben

tomar en cuenta sus áreas de aplicación, ya que la programación lineal es una herramienta de solución

óptima que se aplica en aspectos vinculados con la administración eficiente en todos los ámbitos de la

economía, por lo que es una práctica común en:

 Área de la ingeniería, debido a que permite la utilización de software para llevar a cabo

las labores de programación informática.

 Área científica, ya que permite la resolución de problemas científicos con el análisis,

observación y estudio a través de la programación.

 Área de negocios, ya que se aplica ampliamente en el área administrativa, contable y de

economía con la finalidad de reducir costos o aumentar ganancias a través de modelos

funcionales.

Ventajas de la Programación Lineal

 Una de las principales ventajas de la programación lineal es su capacidad para encontrar la

mejor solución posible en situaciones donde los recursos son limitados. Algunas de las ventajas más

destacadas incluyen:

 Optimización de recursos: La programación lineal permite maximizar el uso de recursos

limitados, como tiempo, dinero y materiales.

 Facilidad de implementación: Con el uso de software especializado, la programación lineal se

puede implementar de manera eficiente en diversos escenarios.

 Flexibilidad: Es posible ajustar los parámetros y restricciones para adaptarse a diferentes

situaciones y necesidades.

Desventajas de la Programación Lineal

A pesar de sus numerosas ventajas, la programación lineal también presenta algunas

desventajas que vale la pena tener en cuenta:

 Complejidad computacional: En algunos casos, resolver problemas de programación lineal

puede requerir una gran cantidad de recursos computacionales.

 Limitaciones en la modelización: Algunas situaciones del mundo real pueden no ajustarse

perfectamente al modelo lineal, lo que puede llevar a soluciones subóptimas.

 Sensibilidad a los datos de entrada: Pequeños cambios en los datos de entrada pueden tener

un impacto significativo en los resultados, lo que requiere un análisis cuidadoso.

Forma estándar

La forma más usual e intuitiva de describir un problema de programación lineal es en su forma

estándar, el cual consiste de tres partes:

 Una función lineal que se desea maximizar, por ejemplo:𝑓(𝑥, 𝑦) = 𝑐1 𝑥 + 𝑐2 𝑦.

 Restricciones lineales de la forma:

 𝑎11 𝑥1 + 𝑎12 𝑥2 ≤ 𝑏1

𝑎21 𝑥1 + 𝑎22 𝑥2 ≤ 𝑏2

𝑎31 𝑥1 + 𝑎32 𝑥2 ≤ 𝑏3

 Variables no negativas, por ejemplo

𝑥1 ≥ 0

𝑥2 ≥ 0

 El problema es usualmente representado en forma matricial como: 𝑚𝑎𝑥{𝑐 𝑡 𝑥: 𝑥𝜖ℝ𝑛 ΛΑ𝑥 ≤

𝑏𝑥 ≥ 0}.

Otras formas, como problemas de minimización, problemas con restricciones de otra forma, así

como problemas que involucran variables negativas pueden se escritos mediante un problema

equivalente en su forma estándar.

Variables

El vector x ∈ Rn tiene como entradas a las variables 𝑥𝑖 (𝑖 = 1,2, … , 𝑛) y estas son llamadas

variables de decisión; para la forma estándar de un modelo de programación lineal, estas son números

reales mayores o iguales a cero, es decir,𝑥1 ≥ 0. En caso de que se requiera que el valor resultante de

las variables sea un número entero entonces se trata de un problema de Programación Entera y

cuando se requiera que el valor resultante de las variables solo tome dos valores, por ejemplo, 0 o 1,

entonces se trata de un problema de Programación Binaria.

 Forma aumentada (variables de holgura)

Los problemas de programación lineal en su forma estándar pueden ser convertidos a su forma

aumentada para aplicar el algoritmo símplex. Esta forma introduce variables no negativas llamadas

variables de holgura para así reemplazar en las restricciones las desigualdades en igualdades. Los

problemas pueden ser escritos en la siguiente forma matricial:

donde 𝑠 son las variables de holgura, 𝑥 son las variables de decisión y 𝑧 es la variable a

maximizar.

Forma no estándar

La forma estándar de un modelo de programación lineal es cuando se tiene el modelo:

como formas no estándar, se tienen los siguientes casos:

 Cuando se desee minimizar la función objetivo.

 Cuando las restricciones son de la forma:

 o

 Cuando las variables son negativas o pueden tomar cualquier valor:

Función objetiva

La programación lineal consiste en optimizar (maximizar o minimizar) una función objetivo, que

es una función lineal de varias variables:

𝑓(𝑥, 𝑦) = 𝑎𝑥 + 𝑏𝑦.

Restricciones

La función objetivo está sujeta a una serie de restricciones, expresadas por inecuaciones

lineales:

𝑎1𝑥 + 𝑏1𝑦 ≤ 𝑐1

𝑎2𝑥 + 𝑏2𝑦 ≤ 𝑐2

𝑎𝑛𝑥 + 𝑏𝑛𝑦 ≤ 𝑐𝑛

Cada desigualdad del sistema de restricciones determina un semiplano.

 Solución factible

El conjunto intersección, de todos los semiplanos formados por las restricciones, determina un

recinto, acotado o no, que recibe el nombre de región de validez o zona de soluciones factibles.

Solución óptima

El conjunto de los vértices del recinto se denomina conjunto de soluciones factibles básicas y el

vértice donde se presenta la solución óptima se llama solución máxima (o mínima según el caso).
 Valor del programa lineal

El valor que toma la función objetivo en el vértice de solución óptima se llama valor del

programa lineal.

Pasos para resolver un problema de programación lineal

1. Elegir las incógnitas.

2. Escribir la función objetivo en función de los datos del problema.

3. Escribir las restricciones en forma de sistema de inecuaciones.

4. Averiguar el conjunto de soluciones factibles representando gráficamente las

restricciones.

5. Calcular las coordenadas de los vértices del recinto de soluciones factibles (si son

pocos).

6. Calcular el valor de la función objetivo en cada uno de los vértices para ver en cuál de

ellos presenta el valor máximo o mínimo según nos pida el problema (hay que tener en

cuenta aquí la posible no existencia de solución si el recinto no está acotado).

Ejemplo de programación lineal

 Unos grandes almacenes encargan a un fabricante pantalones y chaquetas deportivas. El

fabricante dispone para la confección de 750 m de tejido de algodón y 1000 m de tejido de poliéster.

Cada pantalón precisa 1 m de algodón y 2 m de poliéster. Para cada chaqueta se necesitan 1.5 m de

algodón y 1 m de poliéster. El precio del pantalón se fija en 50 € y el de la chaqueta en 40 €.

¿Qué número de pantalones y chaquetas debe suministrar el fabricante a los almacenes para

que éstos consigan una venta máxima?

1. Elección de las incógnitas:

𝑥 = 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑝𝑎𝑛𝑡𝑎𝑙𝑜𝑛𝑒𝑠

𝑦 = 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑐ℎ𝑎𝑞𝑢𝑒𝑡𝑎𝑠

2. Función objetivo:

𝑓(𝑥, 𝑦) = 50𝑥 + 40𝑦

3. Restricciones: Para escribir las restricciones vamos a ayudarnos de una tabla:

pantalones chaquetas disponible

algodón 1 1,5 750

poliéster 2 1 1000

𝑥 + 1.5𝑦 ≤ 750 2𝑥 + 3𝑦 ≤ 1500

2𝑥 + 𝑦 ≤ 1000

Como el número de pantalones y chaquetas son números naturales, tendremos dos

restricciones más: 𝑥 ≥ 0

𝑦 ≥ 0
 4. Hallar el conjunto de soluciones factibles. Tenemos que representar

gráficamente las restricciones. Al ser 𝑥 ≥ 0 e 𝑦 ≥ 0, trabajaremos en el primer

cuadrante.

Representamos las rectas, a partir de sus puntos de corte con los ejes.

Resolvemos gráficamente la inecuación: 2𝑥 + 3𝑦 ≤ 1500, para ello tomamos un punto del

plano, por ejemplo el (0,0).

2 · 0 + 3 · 0 ≤ 1 500

Como 0 ≤ 1 500 entonces el punto (0,0) se encuentra en el semiplano donde se cumple la

desigualdad. De modo análogo resolvemos 2𝑥 + 𝑦 ≤ 1000.

2 · 0 + 0 ≤ 100

La zona de intersección de las soluciones de las inecuaciones sería la solución al sistema de

inecuaciones, que constituye el conjunto de las soluciones factibles.

 5. Calcular las coordenadas de los vértices del recinto de las soluciones factibles.

La solución óptima, si es única, se encuentra en un vértice del recinto. éstos son las soluciones

a los sistemas:

2𝑥 + 3𝑦 = 1500; 𝑥 = 0 (0, 500)

2𝑥 + 𝑦 = 1000; 𝑦 = 0 (500, 0)

2𝑥 + 3𝑦 = 1500; 2𝑥 + 𝑦 = 1000 (375, 250)

6. Calcular el valor de la función objetivo. En la función objetivo sustituimos cada

uno de los vértices.

𝑓(𝑥, 𝑦) = 50𝑥 + 40𝑦

𝑓(0, 500) = 50 · 0 + 40 · 500 = 20000 €

𝑓(500, 0) = 50 · 500 + 40 · 0 = 25000 €

𝑓(375, 250) = 50 · 375 + 40 · 250 = 28750 € 𝑀á𝑥𝑖𝑚𝑜

La solución óptima es fabricar 375 pantalones y 250 chaquetas para obtener un beneficio de

28750 €.

Método simplex

El método simplex es un algoritmo utilizado en la programación lineal para resolver problemas

de optimización. En términos simples, busca encontrar la mejor solución posible a un problema dado,

considerando ciertas restricciones y maximizando o minimizando una función objetivo.

 El método simplex trabaja en un espacio geométrico llamado espacio de soluciones factibles.

Cada punto en este espacio representa una combinación de las cantidades de productos A y B que

puedes fabricar dentro de las restricciones dadas. El algoritmo se mueve de un punto a otro, mejorando

gradualmente la solución, hasta que encuentra el punto óptimo que maximiza tus ganancias.

Su importancia reside en su capacidad para optimizar la asignación de recursos y tomar

decisiones informadas en diversos campos, como la economía, la ingeniería y la gestión empresarial.

Ventajas

 Aplicabilidad a problemas grandes: El método simplex puede manejar problemas con muchas

variables y restricciones, lo cual lo hace útil para la optimización de procesos empresariales.

 Eficiencia: Es un método eficiente para encontrar soluciones óptimas, especialmente en

problemas de programación lineal.

 Implementación en software: Existen programas que facilitan la aplicación del método simplex,

lo cual agiliza su uso en entornos empresariales.

 Análisis de sensibilidad: El método simplex permite analizar cómo la solución óptima se ve

afectada por cambios en los parámetros del problema.

 Optimalidad: Proporciona soluciones óptimas.

 Flexibilidad: El método simplex se adapta a diferentes tipos de problemas.

Desventajas

 Complejidad para problemas grandes: Para problemas con muchas variables y restricciones, el

método simplex puede volverse más complejo y difícil de interpretar.

 Menos intuitivo: La interpretación del método simplex no es tan intuitiva como, por ejemplo, el

método gráfico para problemas simples.

  Sensibilidad a errores: Errores en los datos de entrada pueden afectar significativamente la

solución obtenida.

 Dificultad para interpretar la información dual: La información dual proporcionada por el método

simplex puede ser difícil de interpretar para algunos usuarios.

 Posible estancamiento: El método simplex puede estancarse en soluciones no óptimas en

algunos casos, especialmente con problemas no lineales.

Elementos para utilizar el método simplex

Para utilizar el método simplex de manera efectiva, se deben tener en cuenta los siguientes

elementos:

 Formulación del problema: Debes formular correctamente el problema en términos de una

función objetivo a maximizar o minimizar, así como las restricciones que limitan las variables

del problema. Es esencial identificar las variables y restricciones relevantes y establecer

correctamente los coeficientes y las desigualdades en la formulación del problema.

 Restricciones lineales: El método simplex es aplicable a problemas de programación lineal, lo

que implica que todas las restricciones deben ser lineales. Si hay restricciones no lineales,

deberás transformarlas en su equivalente lineal utilizando técnicas de linealización o considerar

otros métodos de optimización más adecuados.

 Forma estándar o canónica: El método simplex funciona mejor cuando el problema se formula

en su forma estándar o canónica. Esto implica que la función objetivo debe ser de maximización,

todas las restricciones deben ser desigualdades de tipo «<=» y todas las variables deben ser

no negativas. Si el problema no está en forma estándar, deberás realizar las transformaciones

necesarias para convertirlo a esta forma.

 Matriz de coeficientes: Debes construir la matriz de coeficientes que representa las restricciones

del problema. Esta matriz se utiliza en cada iteración del método simplex para determinar las
 variables básicas y no básicas, y para calcular las mejoras en la función objetivo. Asegúrate de

organizar correctamente los coeficientes de las variables y las restricciones en la matriz.

 Método de selección de variables: El método simplex utiliza un método de selección de variables

para determinar qué variable básica debe ingresar o salir del conjunto básico en cada iteración.

Existen diferentes reglas de selección, como la regla del costo reducido o la regla de la razón

mínima, que te indicarán qué variable modificar en cada paso del algoritmo.

 Condición de parada: Debes establecer una condición de parada para finalizar el algoritmo. Por

lo general, esto implica verificar si se ha alcanzado una solución óptima o si no se pueden

realizar más mejoras en la función objetivo. Puedes establecer criterios como la optimalidad de

la solución, la estabilidad de las variables básicas o un número máximo de iteraciones.

Usos del método simplex en la investigación de mercados

El Método Simplex puede ser utilizado en la investigación de mercados como una herramienta

poderosa para optimizar decisiones relacionadas con la asignación de recursos y la maximización de

beneficios. A continuación, se presentan algunos casos en los que el Método Simplex puede ser

aplicado en la investigación de mercados:

 Planificación publicitaria: Las empresas destinan un presupuesto limitado a sus estrategias de

publicidad. Utilizando el Método Simplex, es posible maximizar el impacto de las campañas

publicitarias asignando de manera óptima los recursos disponibles a diferentes canales de

comunicación, segmentos de mercado y momentos clave. Esto ayuda a identificar la

combinación óptima de medios y mensajes para maximizar el alcance y la efectividad de la

publicidad.

 Gestión de inventario: El Método Simplex puede utilizarse para determinar los niveles óptimos

de inventario, considerando factores como la demanda esperada, los costos de almacenamiento

y los costos asociados con la falta de existencias.

  Optimización de precios: Establecer los precios adecuados es esencial para maximizar los

ingresos y la rentabilidad. El Método Simplex puede ser empleado para encontrar el precio

óptimo de un producto o servicio, considerando variables como los costos de producción, la

demanda esperada, los precios de la competencia y las preferencias del consumidor. Esto

ayuda a las empresas a encontrar el equilibrio entre la maximización de ingresos y la atracción

de clientes.

Entrada del problema

Consideremos un problema de programación lineal;

El algoritmo símplex requiere que la matriz del problema esté en su forma aumentada. El

problema puede ser descrito como sigue:

Maximizar 𝑧 en:

Donde 𝑥 son las variables desde la forma estándar, 𝑥𝑠 son las variables de holgura introducidas

en el proceso de aumentación, 𝑐 contiene los coeficientes de optimización, describe el sistema de

ecuaciones contraídas, y 𝑧 es la variable a ser maximizada.

Conceptos básicos

Forma estándar: Es la igualación de las restricciones del modelo planteado, así como el

aumento de variables de holgura, o bien la resta de variables de exceso.

 Forma canónica: En el método símplex es de bastante utilidad la forma canónica,

especialmente para explorar la relación de dualidad, donde un problema de programación lineal se

encuentra en la forma canónica si se cumplen las siguientes condiciones:

Para el caso de la forma canónica de maximización:

 La función objetivo debe ser de maximización

 Las variables de decisión no negativas.

 Las restricciones son del tipo .

Para el caso de la forma canónica de la dieta:

 La función objetivo es minimizada.

 Las restricciones son de tipo .

 Las variables de decisión son no negativas.

Ejemplo:

Forma Canónica de Maximización:

 Forma Canónica de la dieta:

Algoritmo del método símplex

Este proceso que se repite una y otra vez, siempre inicia en un punto extremo de la región

factible que normalmente es el origen, en cada repetición se mueve a otro punto extremo adyacente

hasta llegar a la solución óptima.

Los pasos del método símplex son los siguientes:

1. Utilizando la forma estándar, determinar una solución básica factible inicial igualando a

las (n-m) variables a cero (el origen).

2. Seleccionar la variable de entrada de las variables no básicas que al incrementar su

valor pueda mejorar el valor en la función objetivo. Cuando no exista esta situación, la

solución actual es la óptima; si no, ir al siguiente paso.

3. Seleccionar la variable de salida de las variables básicas actuales.

4. Determinar la nueva solución al hacer la variable de entrada básica y la variable de salida

no básica, ir al paso 2 (actualizar).

Forma Matricial

Consideremos el modelo de programación lineal:

puede ser representado mediante matrices de la siguiente forma:

 Donde;

Esto es;

Para obtener la forma aumentada del problema de programación lineal, introducimos el vector

columna de las variables de holgura, esto es:

De tal manera que las restricciones se convierten en

Donde,
 es la matriz identidad de orden 𝑚 𝑥 𝑚.

Forma estándar de un modelo de progresión lineal

La forma estándar de un modelo de progresión lineal (o programa lineal) se refiere a una forma

específica en la que se expresan las restricciones y la función objetivo para facilitar el uso de algoritmos

de optimización, como el método simplex. La forma estándar se caracteriza por:

1. Todas las restricciones como igualdades: Las restricciones originales, que pueden

ser desigualdades (≤ o ≥), se convierten a igualdades utilizando variables de holgura

(para ≤) o variables de exceso (para ≥).

2. Variables no negativas: Todas las variables del modelo deben ser no negativas (≥ 0).

3. Función objetivo de maximización o minimización: El objetivo del modelo, ya sea

maximizar o minimizar una función lineal, debe estar expresado de forma clara.

La forma estándar de un modelo de progresión lineal es importante porque simplifica la

representación y el análisis de los problemas de optimización. Permite expresar cualquier problema de

programación lineal en una forma única y consistente, facilitando la aplicación de algoritmos de

resolución como el método Simplex.

Ventajas

 Simplicidad e interpretabilidad: Los modelos de regresión lineal son fáciles de entender e

interpretar. Los coeficientes representan el cambio en la variable dependiente ante un cambio

de una unidad en la variable independiente.

  Eficiencia computacional: es computacionalmente eficiente y se puede implementar

rápidamente, incluso en grandes conjuntos de datos.

 Supuestos: los supuestos de la regresión lineal (linealidad, independencia, homocedasticidad y

normalidad de los errores) son fáciles de comprobar y pueden proporcionar información sobre

los datos.

 Rendimiento predictivo: para muchos problemas donde la relación entre las variables es

aproximadamente lineal, la regresión lineal puede proporcionar un buen rendimiento predictivo.

 Fundación para modelos más complejos: sirve como base para métodos estadísticos más

complejos y algoritmos de aprendizaje automático, lo que permite la comprensión de modelos

más complicados.

 Importancia de las características: los coeficientes pueden ayudar a identificar la importancia de

diferentes características para predecir el resultado.

Desventajas

 Supuesto de linealidad: La regresión lineal supone una relación lineal entre las variables

dependientes e independientes. Si la relación real no es lineal, el modelo podría ser inadecuado.

 Sensibilidad a valores atípicos: la presencia de valores atípicos puede afectar significativamente

los coeficientes de regresión, dando lugar a resultados engañosos.

 Multicolinealidad: cuando las variables independientes están altamente correlacionadas, puede

hacer que las estimaciones de los coeficientes sean inestables y difíciles de interpretar.

 Sobreajuste: en casos con muchos predictores en relación con el número de observaciones, la

regresión lineal puede sobre ajustar los datos de entrenamiento, lo que genera una

generalización deficiente a nuevos datos.

 Limitado a relaciones lineales: no puede capturar interacciones o relaciones complejas entre

variables a menos que se modelen explícitamente (por ejemplo, regresión polinomial).

  Violaciones de suposiciones: si se violan las suposiciones de normalidad, independencia u

homocedasticidad de los errores, los resultados pueden no ser válidos.

Variables de decisión

Las variables de decisión son magnitudes físicas representadas por símbolos matemáticos

(𝑥 , 𝑦 ) que un decisor puede controlar y que afectan el resultado de un problema. En esencia, son las

incógnitas de un modelo que se busca optimizar, y sus valores son las decisiones que se toman para

alcanzar el mejor resultado

Importancia

Permiten traducir un problema real en un modelo matemático estructurado. Su correcta

definición es crítica para garantizar que el modelo refleje la realidad y sea resoluble.

Características

 Símbolos: Se denotan generalmente con letras como 𝑥, 𝑦, 𝑧𝑥, 𝑦, 𝑧 o con subíndices

(𝑥1, 𝑥2, … , 𝑥𝑛𝑥1, 𝑥2, … , 𝑥𝑛).

 Tipo: Pueden ser:

 Continuas (valores reales, ej.: x≥0x≥0).

 Enteras (ej.: número de empleados).

 Binarias (0 o 1, para decisiones de sí/no).

 Función objetivo: Su valor determina el resultado a optimizar (maximizar ganancias,

minimizar costos, etc.).

 Restricciones: Están sujetas a límites (recursos, tiempo, capacidad, etc.).

 Ejemplos:

1. Problema de producción:

 Variables: 𝑥1 = unidades del Producto 𝐴, 𝑥2 = unidades del Producto 𝐵.

 Objetivo: Maximizar 3𝑥1 + 5𝑥2 (ganancia).

 Restricciones: 2𝑥1 + 4𝑥2 ≤ 100.(horas de trabajo).

2. Problema de transporte:

 Variables: 𝑦𝑖𝑗 = cantidad enviada desde la fábrica 𝑖 al almacén 𝑗.

 Objetivo: Minimizar costos de transporte.

3. Problema de inversión:

 Variables binarias: 𝑧𝑘 = 1 si se invierte en el proyecto 𝑘, 0 si no.

Ejemplo grafico de programación lineal

Si maximizas 𝑍 = 2𝑥 + 3𝑦 las variables 𝑥 e 𝑦 son las decisiones que ajustas dentro de las

restricciones para obtener el máximo valor de 𝑍.

Restricciones

Las restricciones son ecuaciones o desigualdades que limitan los valores que pueden tomar las

variables de decisión en un problema. Estas restricciones definen la región factible, que contiene todas

las soluciones posibles para el problema. Las restricciones pueden representar limitaciones de

recursos, capacidades, o cualquier otra condición que deba cumplirse.

Características de las restricciones en programación lineal:

 Lineales: Las restricciones deben ser lineales, lo que significa que la relación entre las

variables es de primer grado.

  Desigualdades o igualdades: Las restricciones pueden expresarse como

desigualdades (≤, ≥, <, >) o igualdades (=).

 Limitaciones: Las restricciones representan limitaciones en la toma de decisiones,

como la disponibilidad de recursos, la capacidad de producción, o los requisitos de

calidad.

 Región factible: Las restricciones definen la región factible, que es el conjunto de todas

las soluciones que cumplen con las restricciones.

 Función objetivo: Las restricciones deben ser consideradas junto con la función

objetivo, que define lo que se desea optimizar (maximizar o minimizar

Tipos de Restricciones en IO

 Restricciones Lineales: Expresadas como ecuaciones o desigualdades lineales (𝑒𝑗: 2𝑥 +

3𝑦 ≤ 100). Son fundamentales en Programación Lineal. Ejemplo: Limitación de recursos

como horas de trabajo o materiales.

 Restricciones No Lineales: Involucran términos no lineales (𝑒𝑗: 𝑥2 + 𝑦 ≤ 10 𝑜 𝑥𝑦 ≥ 5).

Requieren técnicas como Programación No Lineal. Ejemplo: Leyes de rendimientos

decrecientes en economía.

 Restricciones de Recurso: Limitan la disponibilidad de recursos (ej: presupuesto, materia

prima, tiempo). Ejemplo: No usar más de 500 kg de material en producción.

 Restricciones de Demanda: Garantizan que la producción o entrega cumpla con la

demanda mínima/máxima. Ejemplo: Producir al menos 1000 unidades para satisfacer

pedidos.

 Restricciones de Capacidad: Definen límites físicos (ej: capacidad de almacenamiento,

máquinas). Ejemplo: Un almacén no puede contener más de 2000 cajas.

  Restricciones Tecnológicas: Derivadas de procesos técnicos (ej: proporciones fijas de

insumos). Ejemplo: Mezclar 2 partes de A por 1 parte de B en una fórmula.

 Restricciones Legales o Regulatorias: Impuestas por leyes o normas (ej: emisiones

contaminantes, seguridad). Ejemplo: Cumplir con estándares de calidad ISO.

 Restricciones Enteras o Binarias: Variables discretas (ej: 𝑥 ∈ 𝑍 para número de

camiones). Binarias: 𝑥 ∈ {0,1} (ej: sí/no construir una planta). Clave en Programación

Entera.

 Restricciones Probabilísticas (Estocásticas): Incorporan incertidumbre (ej: demanda

variable, fallos en suministros). Resueltas con Programación Estocástica o Simulación.

 Restricciones Temporales: Relacionadas con plazos o secuencias (ej: tiempos de

entrega, scheduling). Ejemplo: Terminar un proyecto en 6 meses (Método CPM/PERT).

 Restricciones de Equilibrio: Aseguran balance en sistemas de flujo (ej: oferta = demanda

en redes). Usadas en modelos de transporte o logística.

 Restricciones Suaves vs Duras:

 Duras: Absolutas (ej: no exceder un presupuesto).

 Suaves: Flexibles, permiten violaciones controladas (ej: penalizar horas extras).

Herramientas para Manejar Restricciones

 Software como CPLEX, Gurobi, LINGO, o Python/Excel para modelos lineales/enteros.

 Técnicas como Ramificación y Acotamiento (programación entera) o Algoritmos

Genéticos (no lineales).

 Enfoques híbridos (PL-Simulación para restricciones estocásticas).

Aplicaciones Prácticas

 Logística: Restricciones de rutas, capacidad de vehículos y tiempos.

  Producción: Límites de máquinas, inventario y mano de obra.

 Finanzas: Riesgo máximo permitido en carteras de inversión.

 Energía: Restricciones ambientales en generación eléctrica.

Ejemplo:

Considere a un agricultor que quiere maximizar sus ingresos de la venta de cultivos cultivados

en 240 acres de tierra. El agricultor cultiva trigo y cebada, puede vender trigo a 200 dólares por tonelada

y cebada a 150 dólares por tonelada, y espera cosechar 2,5 toneladas de trigo y 2 toneladas de cebada

por acre.

Deben destinar al menos el 40% de sus tierras al trigo y al menos el 30% de sus tierras a la

cebada. Luego, pueden formular un problema de programación lineal definiendo variables de decisión:

𝑋 (Número de acres asignados al trigo)

𝑌 (Número de acres asignados a la cebada),

Expresando la función objetivo como maximizar 𝑍 = 200 ∗ 2.5 ∗ 𝑋 + 150 ∗ 2 ∗ 𝑌,.

Expresando las restricciones como 𝑋 + 𝑌 <= 240

Restricción 1: Disponibilidad de tierras, 𝑋 >= 0,4 ∗ (𝑋 + 𝑌)

Restricción 2: Requisito de trigo, 𝑌 >= 0,3 ∗ (𝑋 + 𝑌)

Restricción 3: Requisito de cebada, 𝑋 >= 0

Restricción 4: no negatividad de 𝑋 𝑦 𝑌 >= 0

 Restricción 5: no negatividad de 𝑌 y comprobar la validez y coherencia de la función objetivo y

de las restricciones.

Ventajas de las restricciones en programación lineal:

 Modelado de la realidad: Las restricciones permiten incorporar limitaciones y

condiciones que existen en el mundo real, como límites de recursos, necesidades de

producción, o requerimientos legales.

 Definición del espacio de soluciones: Las restricciones delimitan el espacio de

soluciones factibles, es decir, las combinaciones de variables que cumplen con las

condiciones del problema. Esto facilita la búsqueda de la solución óptima, ya que el

algoritmo solo necesita considerar las soluciones que están dentro de este espacio.

 Orientación hacia la solución óptima: Al imponer restricciones, se guía la búsqueda

hacia soluciones que sean más viables y útiles en la práctica. Las restricciones pueden

ayudar a evitar soluciones que, aunque técnicamente factibles, no sean prácticas o

deseen ser evadidas por el problema.

Desventajas de las restricciones en programación lineal:

 Mayor complejidad: La inclusión de restricciones aumenta la complejidad del problema

y el tiempo necesario para encontrar la solución óptima. Esto puede requerir algoritmos

más sofisticados y mayor capacidad computacional.

 Dificultad para modelar relaciones no lineales: Si el problema involucra relaciones

no lineales entre las variables, la programación lineal puede no ser adecuada o puede

requerir la aplicación de técnicas especiales para modelar dichas relaciones.

 Posible limitación de la solución óptima: Si las restricciones son demasiado

restrictivas, pueden limitar significativamente la solución óptima. En este caso, es posible

 que la solución óptima no sea la mejor solución posible para el problema real, y se pueda

perder la posibilidad de tomar decisiones más flexibles.

 Limitaciones en la solución: En algunos casos, las restricciones pueden llevar a la

imposibilidad de encontrar una solución factible. Esto puede ocurrir si las restricciones

son contradictorias o si la combinación de variables que cumplen las restricciones no

existe.

Función objetiva

La función objetivo es una expresión matemática que representa la meta o el criterio que se

busca optimizar (maximizar o minimizar) en un problema de decisión. Define la medida de desempeño

del sistema bajo estudio y está directamente relacionada con las variables de decisión y las

restricciones del modelo. Un ejemplo es la siguiente ecuación: 𝑧 = 𝑓(𝑥, 𝑦) = 15𝑥 + 20𝑦.

Características

 Dirección de optimización:

 Maximización: Aumentar un beneficio (ej: utilidades, eficiencia).

 Minimización: Reducir un costo o impacto negativo (ej: gastos, tiempo,

desperdicio).

 Linealidad:

 Lineal: Expresada como combinación lineal de variables (𝑒𝑗: 𝑍 = 3𝑥1 + 5𝑥2 ).

 No lineal: Incluye términos cuadráticos, exponenciales o multiplicativos (ej: 𝑍 =

𝑥12 + 2𝑥1 𝑥2 ).

 Variables: Depende de las variables de decisión (ej: 𝑥 , 𝑦 ) que representan acciones

controlables.
  Sensibilidad: Su análisis revela cómo cambios en coeficientes o restricciones afectan

la solución óptima.

 Diferenciabilidad: En problemas no lineales, su derivada permite usar métodos como

el gradiente.

Tipos de funciones objetivo

 Lineal: Típica en Programación Lineal. Ejemplo: 𝑀𝑎𝑥 𝑍 = 4𝑥 + 6𝑦 (maximizar ganancias).

 No Lineal: Usada en Programación No Lineal. Ejemplo: 𝑀𝑖𝑛 𝑍 = 𝑒 2𝑥 + 𝑙𝑛(𝑦) (minimizar

costos complejos).

 Multiobjetivo: Busca optimizar varias metas simultáneas (ej: maximizar calidad y minimizar

costos). Requiere técnicas como Ponderación de Objetivos o Análisis Pareto.

 Entera o Binaria: Variables discretas (ej: 𝑍 = 10𝑥1 + 20𝑥2 , donde𝑥1 , 𝑥2 ∈ { 0 , 1 }

 Estocástica: Incluye incertidumbre en parámetros (ej: demanda aleatoria). Ejemplo:

𝑀𝑎𝑥 𝐸[𝑍] = 5𝑥 + 3𝑦, donde 𝐸 es valor esperado.

 Dinámica: Optimiza secuencias de decisiones en el tiempo (ej: modelos de inventario).

Aplicaciones

 Logística: Minimizar costos de transporte en cadenas de suministro.

 Finanzas: Maximizar el rendimiento de una cartera de inversiones.

 Producción: Optimizar mezcla de productos para maximizar ganancias.

 Energía: Minimizar emisiones de CO₂ en generación eléctrica.

 Salud: Maximizar la cobertura de vacunación con recursos limitados.

Herramientas y técnicas
  Software:

 CPLEX, Gurobi, LINDO (PL/PLE).

 MATLAB, Python (SciPy, PuLP) para modelos no lineales.

 Algoritmos:

 Método Símplex (PL).

 Algoritmos genéticos (optimización heurística).

 Puntos interiores (problemas no lineales).

Relación con las restricciones

La función objetivo y las restricciones trabajan juntas:

 Las restricciones definen qué soluciones son posibles.

 La función objetivo evalúa cuál de esas soluciones es la mejor.

Ejemplo: En un problema de dieta, las restricciones garantizan nutrientes mínimos, mientras la

función objetivo minimiza el costo total.

Soluciones básicas

Una solución básica es aquella que resulta de un proceso donde algunas variables (no básicas)

se establecen en cero, y las restantes (variables básicas) se resuelven a partir de las ecuaciones del

sistema. En esencia, es una forma de encontrar una solución al problema de programación lineal fijando

algunas variables en cero y resolviendo el sistema resultante.

El número de variables básicas debe ser igual al número de restricciones linealmente

independientes (es decir, el rango de la matriz de coeficientes).

 Las variables de holgura son una herramienta fundamental para transformar problemas reales

en modelos matemáticos manejables, permitiendo optimizar recursos en áreas como producción,

logística o finanzas.

Formulación matemática

 Dado un sistema de ecuaciones 𝑨𝒙 = 𝒃, donde:

 A: Matriz de coeficientes de tamaño (𝑚 < 𝑛𝑚 < 𝑛).

 x: Vector de variables de decisión (𝑥1, 𝑥2, . . . , 𝑥𝑛).

 b: Vector de términos independientes.

 Pasos para obtener una solución básica:

1. Seleccionar mm columnas de A que formen una submatriz invertible (base).

2. Igualar a cero las variables no básicas (las no incluidas en la base).

3. Resolver el sistema para las variables básicas.

Tipos de soluciones básicas

1. Solución Básica Factible (SBF); Es una solución básica donde todas las variables

básicas son no negativas (𝑥𝑖 ≥ 0). Representa un vértice de la región factible y es

candidata a ser solución óptima en PL.

2. Solución Básica Inviable; Al menos una variable básica toma un valor negativo. No

pertenece a la región factible y se descarta en la búsqueda del óptimo.

Propiedades clave

1. Teorema Fundamental de la Programación Lineal: Si un problema de PL tiene solución

óptima, existe al menos una solución básica factible que es óptima.

2. Relación con los vértices: Cada SBF corresponde a un vértice de la región factible

(poliedro convexo).

3. Degeneración: Ocurre cuando una SBF tiene al menos una variable básica con valor

cero. Esto puede llevar a ciclos en el algoritmo Símplex.

Ejemplo práctico

Problema: Maximizar 𝑍 = 3𝑥 + 5𝑦, sujeto a:

2𝑥 + 𝑦 ≤ 10 (𝑟𝑒𝑐𝑢𝑟𝑠𝑜)
{𝑥 + 3𝑦 ≤ 15 (𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑)
𝑥, 𝑦 ≥ 0

Paso 1: Convertir a forma estándar (agregar variables de holgura 𝑠1, 𝑠2):

2𝑥 + 𝑦 𝑠1 = 10
{𝑥 + 3𝑦 + 𝑠2 = 15
𝑥, 𝑦, 𝑠1 𝑠2 ≥ 0

Paso 2: Seleccionar variables básicas.

 Caso 1: Base = {𝑥, 𝑦} (variables no básicas: 𝑠1 = 0, 𝑠2 = 0)

2𝑥 + 𝑦 = 10
{ ⇒ 𝑥 = 3, 𝑦 = 4(𝑆𝐵𝐹, 𝑡𝑜𝑑𝑜𝑠 ≥ 0
𝑥 + 3𝑦 = 15

 Caso 2: Base = {𝑥, 𝑠1} (variables no básicas: 𝑦 = 0, 𝑠1 = 0):

 2𝑥 + 𝑠1 = 10
{
𝑥 = 15 ⇒ 𝑥 = 15 ⇒ 𝑠1 = −20 (𝑖𝑛𝑣𝑖𝑎𝑏𝑙𝑒)

Importancia:

Las soluciones básicas son fundamentales en el método Simplex, un algoritmo ampliamente

utilizado para resolver problemas de programación lineal. El método Simplex se basa en moverse

entre soluciones básicas factibles hasta llegar a la solución óptima.

Variables de holgura

Es una variable artificial no negativa que se introduce en un modelo de optimización para

convertir una desigualdad (tipo "≤" o "≥") en una igualdad, facilitando así la aplicación de métodos

como el algoritmo Símplex. Estas variables representan la "holgura" o el exceso en el uso de un

recurso y son clave para identificar soluciones factibles y óptimas.

Una variable de holgura (𝑠𝑖 ≥ 0) se añade a una restricción de desigualdad para transformarla

en una ecuación.

Para restricciones "≤": 2𝑥 + 𝑦 ≤ 10 → 2𝑥 + 𝑦 + 𝑠 = 10, 𝑑𝑜𝑛𝑑𝑒 𝑠 ≥ 0𝑠.

𝑠 representa el recurso no utilizado (ej: horas laborales no empleadas).

Para restricciones "≥": Se usan variables de exceso (𝑒𝑖 ≥ 0) en lugar de holgura:

𝑥 + 3𝑦 ≥ 15 → 𝑥 + 3𝑦 − 𝑒 = 15, 𝑑𝑜𝑛𝑑𝑒 𝑒 ≥ 0.

Objetivo

Permitir la escritura del problema en forma estándar (solo igualdades y variables no negativas).

Facilitar la identificación de soluciones básicas factibles (vértices de la región factible).

Importancia en la Interpretación Económica

 Gestión de recursos:

 𝑠𝑖 > 0: Indica recursos ociosos.

 𝑠𝑖 = 0: Recurso crítico (afecta directamente al óptimo).

Análisis de sensibilidad:

El precio dual (shadow price) de una restricción se calcula cuando su variable de holgura es

cero.

Papel en el Algoritmo Símplex

Forma estándar: Las variables de holgura permiten construir una matriz identidad en el sistema

de ecuaciones, lo que proporciona una solución básica inicial factible (SBF).

Solución inicial:

Variables básicas: 𝑠1 = 10, 𝑠2 = 15.

Variables no básicas: 𝑥 = 0, 𝑦 = 0.

Iteraciones del Símplex: Las variables de holgura entran/salen de la base según se mejore el

valor de Z.

Variable de exceso

Es una variable artificial no negativa que se introduce en restricciones de desigualdad tipo "≥"

para convertirlas en igualdades, permitiendo así aplicar métodos como el algoritmo Símplex.
 Representa la cantidad en la que el lado izquierdo de la restricción excede al lado derecho, es

decir, el "exceso" o sobrecumplimiento de una condición.

Una variable de exceso (𝑒𝑖 ≥ 0) se resta en una restricción "≥" para transformarla en una

ecuación.

Ejemplo:

3𝑥 + 2𝑦 ≥ 12 → 3𝑥 + 2𝑦 − 𝑒 = 12, donde 𝑒 ≥ 0.

𝑒 = 0: Se cumple exactamente la restricción (3𝑥 + 2𝑦 = 12).

𝑒 > 0: Indica que 3𝑥 + 2𝑦 es mayor que 12 (ej: producción excedente).

Objetivo:

 Convertir el problema a forma estándar (solo igualdades y variables no negativas).

 Facilitar la identificación de soluciones básicas factibles.

Diferencias con las Variables de Holgura

Características Variable de exceso Variable de holgura

Tipo de restricción Se usa en restricciones Se usa en restricciones
≥ ≤
Operación Se resta (−𝑒) Se suma (+𝑠)
Interpretación Mide el exceso sobre el Mide el recurso no
mínimo requerido utilizado (holgura)

Ejemplo 𝑥1 + 𝑥2 ≥ 10 → 𝑥1 + 𝑥2 2𝑥 ≤ 5 → 2𝑥 + 𝑠 = 5
− 𝑒 = 10
Ejemplo Práctico

Problema Original (Minimización con restricción "≥"):

𝑀𝑖𝑛 𝑍 = 4𝑥 + 6𝑦

sujeto a:3𝑥 + 2𝑦 ≥ 12 (Requerimiento mínimo) 𝑥, 𝑦 ≥ 0

  Paso 1: Introducir variable de exceso (e):

3𝑥 + 2𝑦 − 𝑒 = 12 CON 𝑒 ≥ 0

 Paso 2: Interpretación:

o Si 𝑥 = 2𝑥, 𝑦 = 3, entonces: 3(2) + 2(3) − 𝑒 = 12 → 12 − 𝑒 = 12 → 𝑒 = 0.

Cumplimiento exacto: No hay exceso.

o Si 𝑥 = 4, 𝑦 = 2, entonces: 3(4) + 2(2) − 𝑒 = 12 → 16 − 𝑒 = 12 → 𝑒 = 4.

Exceso de 4 unidades: Se superó el requerimiento mínimo.

Variables irrestrictas

En la Investigación de Operaciones (IO) y la Programación Lineal (PL), las variables

irrestrictas (también llamadas variables libres o free variables) son variables de decisión que no tienen

restricciones de no negatividad, es decir, pueden tomar valores positivos, negativos o cero. Estas

variables contrastan con las típicas variables en PL, que suelen estar sujetas a 𝑥𝑖 ≥ 0.

Son variables que pueden tomar cualquier valor real (𝑥 ∈ 𝑅), sin límites de signo.

Métodos para manejar variables irrestrictas

Dado que algoritmos como el Símplex requieren variables no negativas, las variables
irrestrictas deben transformarse. Las estrategias más usadas son:

1. Descomposición en variables positivas y negativas

o Cualquier variable irrestricta x se expresa como:

𝑥 = 𝑥 + −, donde 𝑥 + ≥ 0, 𝑥 − ≥ 0

Ejemplo:
 Si x=5, entonces 𝑥 + = 5, 𝑥 − = 0.

Si x=−3, entonces 𝑥 + = 0, 𝑥 − = 3.

Ventaja: Permite aplicar el algoritmo Símplex estándar.

Desventaja: Aumenta el número de variables del modelo.

2. Sustitución algebraica: Si una variable irrestricta aparece en una ecuación, puede

despejarse en términos de otras variables restringidas.

Ejemplo:

En la restricción 2𝑥 + 𝑦 = 10, si 𝑥 es irrestricta:

10 − 𝑦
𝑥= .
2

Luego, 𝑥 se sustituye en la función objetivo y demás restricciones.

3. Algoritmos especializados: Métodos como el Símplex revisado o herramientas de software

(CPLEX, Gurobi) manejan variables libres directamente sin necesidad de descomposición.

Relación con otros tipos de variables

  Variables de holgura/exceso: Siempre son no negativas (𝑠𝑖, 𝑒𝑖 ≥ 0).

 Variables artificiales: Se usan para iniciar el Símplex y tienen penalizaciones.

 Variables enteras libres: Pueden ser positivas o negativas, pero discretas (ej: 𝑥 ∈ 𝑍).

Variables artificiales

Son variables que se introducen en la programación lineal para ayudar a convertir

desigualdades en ecuaciones, especialmente cuando se enfrentan restricciones de tipo ≥ (mayor o

igual) o igualdades (=), según la University Of Moratuwa. Estas variables no representan una realidad

física del problema original, sino que son una herramienta matemática para obtener una solución

factible inicial, explica Angelfire.

Uso

Se utilizan principalmente en el método Simplex para poder obtener una solución básica

factible inicial cuando el problema original no la tiene.

Métodos que utilizan variables artificiales

 Método de la Gran M

Se añade una variable artificial (𝑎𝑖) a la restricción y se penaliza su presencia en la función

objetivo con un coeficiente muy grande (𝑀).

Ejemplo:

Restricción: 𝑥 + 2𝑦 ≥ 4 → 𝑥 + 2𝑦 − 𝑒 + 𝑎 = 4.

Función objetivo: 𝑍 = 3𝑥 + 5𝑦 + 𝑀𝑎 (si es minimización) o 𝑍 = 3𝑥 + 5𝑦 − 𝑀𝑎 (si es

maximización).
 Objetivo: Forzar que 𝑎 = 0 en la solución óptima, eliminando su influencia.

 Método de las Dos Fases

 Fase 1: Minimizar la suma de variables artificiales (𝑊 = 𝑎1 + 𝑎2+. . . +𝑎𝑛) para encontrar

una SBF inicial.

 Fase 2: Usar la SBF obtenida para resolver el problema original sin variables artificiales.

Interpretación de las variables artificiales

 No tienen significado físico: Representan un "parche" matemático, no un recurso real.

 Indicador de factibilidad:

 Si en la solución óptima 𝑎 > 0, el problema es infactible.

 Si 𝑎 = 0, la solución es válida para el problema original.

Comparación con variables de holgura/exceso

Características Variables artificiales Variables de

holgura/exceso
Propósito Permitir una SBF inicial Convertir desiguales en
igualdades
Tipos de restricción "≥" o "=" "≤" 𝑜 " ≥ "
Significado físico No tiene interpretación real Miden recursos no usados
o excesos
Presencia en la solución Debe ser cero (𝑎 = 0) Pueden ser positivas o
optima cero

Método simplex primal

El método Símplex Primal es un algoritmo fundamental en Programación Lineal (PL) utilizado

para encontrar la solución óptima de un problema de maximización o minimización sujeto a

restricciones lineales. Se enfoca en explorar los vértices (soluciones básicas factibles) de la región

factible, moviéndose iterativamente hacia mejores soluciones hasta alcanzar el óptimo.

1. Pasos del Método Símplex Primal

 Convertir el problema a forma estándar: Agregar variables de

holgura, exceso o artificiales según el tipo de restricciones.

2. Encontrar una SBF inicial:

 Si hay variables artificiales, usar el método de la Gran M o Dos Fases.

 Si no, usar variables de holgura como base inicial (ej: 𝑠1 = 𝑏1, 𝑠2 = 𝑏2).

3. Construir el tableau Símplex:

 Organizar coeficientes de la función objetivo y restricciones en una tabla.

4. Prueba de optimalidad:

 Maximización: Si todos los costos reducidos (coeficientes en la fila 𝑍) son ≤ 0,

la solución es óptima.

 Minimización: Si son ≥ 0, se alcanza el óptimo.

5. Seleccionar variable entrante:

 Maximización: Elegir la columna con el costo reducido más positivo.

 Minimización: Elegir la columna con el costo reducido más negativo.

6. Seleccionar variable saliente (Regla de la razón mínima):

𝐿𝑎𝑑𝑜 𝐷𝑒𝑟𝑒𝑐ℎ𝑜
 𝐶𝑎𝑙𝑐𝑢𝑙𝑎𝑟 𝐶𝑜𝑒𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑒 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑜 𝑑𝑒 𝑙𝑎 𝑐𝑜𝑙𝑢𝑚𝑛𝑎 𝑒𝑛𝑡𝑟𝑎𝑛𝑡𝑒

 La fila con la razón mínima determina la variable que sale de la base.

7. Actualizar el tableau (Pivoteo):

 Convertir el elemento pivote en 1 y los demás elementos de la columna en 0

mediante operaciones fila.

8. Repetir pasos 4–7 hasta cumplir la prueba de optimalidad.

Ejemplo Práctico

Problema: Maximizar Z = 3 𝑥 + 5 𝑦 , sujeto a:

2𝑥 + 𝑦 ≤ 10
{𝑥 + 3𝑦 ≤ 15
𝑥 ,𝑦 ≥ 0

Paso 1: Convertir a forma estándar (agregar variables de holgura 𝑠1, 𝑠2):

2𝑥 + 𝑦 + 𝑠1 = 10

𝑥 + 3𝑦 + 𝑠2 = 15

𝑥, 𝑦, 𝑠1, 𝑠2 ≥ 0

Paso 2: Tableau inicial:

Base 𝑥 𝑦 𝑠1 𝑠2 Lado
derecho
𝑠1 2 1 1 0 10
𝑠2 1 3 0 1
𝑍 −3 −5 0 0 0

Iteración 1:

 Variable entrante: 𝑦 (costo reducido más negativo, −5).

 Variable saliente: 𝑀í𝑛 {10/1,15/3} = 5→ 𝑠2.

 Pivote: 3 (en la fila de s2).

Actualizar tableau:

 Dividir fila de 𝑠2 𝑝𝑜𝑟 3: 𝑥/3 + 𝑦 + 𝑠2/3 = 5.

 Eliminar 𝑦 de otras filas:

 Nueva fila 𝑠1: 2𝑥 + 𝑦 + 𝑠1 − (1 × 𝑛𝑢𝑒𝑣𝑎 𝑓𝑖𝑙𝑎 𝑦) = 10 − 5.

 Nueva fila 𝑍: −3𝑥 − 5𝑦 + (5 × 𝑛𝑢𝑒𝑣𝑎 𝑓𝑖𝑙𝑎 𝑦) = 25.

  Tableau actualizado:

Base 𝑥 𝑦 𝑠2 𝑠2 Lado
derecho

5/3 0 1 1/3 5
𝑠1 1 0 5
1/3 1/3
𝑦
−4/3 0 0 5/3 25
𝑍

 Iteración 2:

 Variable entrante: x (costo reducido −4/3).

 Variable saliente: Mín {5/(5/3),5/(1/3)} = 3 → 𝑠1.

 Pivote: 5/3

 Actualizar tableau:

 Dividir fila de 𝑠1 por 5/3: 𝑥 + 0𝑦 + (3/5)𝑠1 − (1/5)𝑠2 = 3.

 Eliminar 𝑥 de otras filas.

 Tableau final (óptimo):

Base 𝑥 𝑦 𝑠1 𝑠2 Lado
derecho
𝑥 1 0 3/5 −1/5 3
𝑦 0 1 −1/5 2/5 4

𝑍 0 0 4/5 7/5 37

 Solución óptima: 𝑥 = 3, 𝑦 = 4, 𝑍 = 37.

Ventajas y Limitaciones

Ventajas:

 Eficiente en problemas con hasta miles de variables.

 Encuentra soluciones exactas en PL.

Limitaciones:
  No maneja no linealidades o variables enteras directamente.

 Ineficiente en problemas degenerados o muy grandes (se usa el Símplex

Revisado).

Método simplex dual

El método Símplex Dual es un algoritmo utilizado en Programación Lineal (PL) para resolver

problemas de optimización cuando la solución inicial es óptima pero infactible (es decir, cumple las

condiciones de optimalidad pero viola algunas restricciones). A diferencia del Símplex Primal, que parte

de una solución factible y busca la optimalidad, el Símplex Dual comienza con una solución "óptima en

papel" (basada en costos reducidos) y trabaja para alcanzar la factibilidad. Es especialmente útil en

análisis de sensibilidad, problemas con restricciones añadidas o variables acotadas superiormente.

Dualidad en PL: Todo problema de PL (primal) tiene un problema dual asociado. El Símplex

Dual resuelve el primal aprovechando las propiedades del dual.

Ventaja: Maneja eficientemente cambios en las restricciones sin resolver el problema desde

cero.

Condiciones del Símplex Dual:

Optimalidad inicial: Los costos reducidos (coeficientes en la fila 𝑍) deben ser no positivos

(para maximización) o no negativos (para minimización).

Infactibilidad inicial: Al menos un término del lado derecho (𝑏𝑖) es negativo.

Pasos del Método Símplex Dual

Verificar factibilidad:

 Si todos los bi≥0, la solución es factible y óptima → PARAR.

 Si hay bi<0, continuar.

Seleccionar variable saliente (fila pivote):

 Escoger la fila con el bi más negativo (mayor violación).

 Ejemplo: Si b2=−5, se selecciona la fila 2.

Seleccionar variable entrante (columna pivote):

𝑐𝑜𝑠𝑡𝑜 𝑟𝑒𝑑𝑢𝑐𝑖𝑑𝑜
 𝐶𝑎𝑙𝑐𝑢𝑙𝑎𝑟 𝑙𝑜𝑠 𝑟𝑎𝑡𝑖𝑜𝑠 𝐸𝑙𝑒𝑚𝑒𝑛𝑡𝑜 𝑎 𝑝𝑎𝑟𝑎𝑎𝑖𝑗 < 0.
𝑖𝑗 𝑒𝑛 𝑓𝑖𝑙𝑎 𝑝𝑖𝑣𝑜𝑡𝑒

 Regla: Elegir la columna con la ratio mínimo absoluto (para maximización) o ratio máximo

negativo (para minimización).

 Si todos 𝑎𝑖𝑗≥0 en la fila pivote → Problema infactible.

Realizar pivoteo:

 Convertir el elemento pivote (𝑎𝑖𝑗) en 1 y los demás elementos de la columna en 0

mediante operaciones fila.

Repetir hasta que todos los bi≥0.

Ejemplo practico
Problema

Maximización con solución inicial infactible:

Maximizar 𝑍 = 3𝑥 + 5𝑦.

sujeto a:

2𝑥 + 𝑦 ≤ 10
𝑥 + 3𝑦 ≤ 15
{
𝑥 ≥ 4(𝑛𝑢𝑒𝑣𝑎 𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖𝑜𝑛 𝑎ñ𝑎𝑑𝑖𝑑𝑎)
𝑥, 𝑦 ≥ 0

Paso 1: Convertir a forma estándar (agregar variables de holgura 𝑠1, 𝑠2, 𝑠3):

2𝑥 + 𝑦 + 𝑠1 = 10(𝑅𝑒𝑐𝑢𝑟𝑠𝑜 1)

𝑥 + 3𝑦 + 𝑠2 = 15(𝑅𝑒𝑐𝑢𝑟𝑠𝑜 2)

𝑥 − 𝑠3 = 4 (𝑁𝑢𝑒𝑣𝑎 𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛, 𝑠3 ≥ 0)

𝑥, 𝑦, 𝑠1, 𝑠2, 𝑠3 ≥ 0

Tableau inicial (asumiendo solución previa óptima x=3, y=4, pero viola x≥4):

Iteración 1:

Paso 1: Factibilidad → s3=−1(inviable).

Paso 2: Variable saliente → Fila de s3(lado derecho más negativo).

Paso 3: Variable entrante:

 𝑐𝑜𝑠𝑡𝑜 𝑟𝑒𝑑𝑢𝑐𝑖𝑑𝑜
 𝐶𝑎𝑙𝑐𝑢𝑙𝑎𝑟 𝑟𝑎𝑡𝑖𝑜𝑠 𝑝𝑎𝑟𝑎 𝑎𝑖𝑗 < 0 𝑒𝑛 𝑙𝑎 𝑓𝑖𝑙𝑎 𝑠3
𝑎𝑖𝑗

7
7
 𝐶𝑜𝑙𝑢𝑚𝑛𝑎 𝑠2 : 5
3 = −3
−
5

 Ratio mínimo absoluto: −7/3 → Columna s2.

Paso 4: Pivote en 𝑎𝑠3𝑠2 = −3/5.

Actualizar tableau:

1. Dividir fila s3 por −3/5:

2. Eliminar 𝑠2 de las demás filas.

Tableau actualizado:

Solución óptima y factible:

𝑥 = 4, 𝑦 = 14/3 𝑍 = 100/3 ≈ 33.33

 Aplicaciones del Símplex Dual

Análisis de sensibilidad:

 Evaluar el impacto de cambios en restricciones sin resolver el problema desde cero.

Problemas con cotas superiores:

 Manejar restricciones del tipo 𝑥 ≤ 𝑈 eficientemente.

Optimización en ramas y cotas (Branch and Bound):

 Resolver subproblemas en Programación Entera Mixta.

Restricciones añadidas:

 Como en el ejemplo, cuando se agrega una nueva restricción a un modelo ya resuelto.

Método gráfico

El método gráfico es una técnica sencilla y visual utilizada en Programación Lineal (PL) para

resolver problemas de optimización con dos variables de decisión. A través de gráficos en un plano

cartesiano, permite identificar la región factible (soluciones que cumplen todas las restricciones) y

determinar la solución óptima evaluando la función objetivo en los vértices de dicha región.

Pasos del Método Gráfico

Formular el problema:

 Definir la función objetivo (maximizar o minimizar).

 Establecer las restricciones lineales y condiciones de no negatividad.

Graficar las restricciones:

 Convertir cada desigualdad en una ecuación (línea recta).

 Determinar el área que satisface cada desigualdad (sombreado).

Identificar la región factible:

 La intersección de todas las áreas factibles es la región factible, un polígono convexo

(triángulo, cuadrilátero, etc.).

Graficar la función objetivo:

 Dibujar la recta de la función objetivo (𝑍 = 𝑐1𝑥 + 𝑐2𝑦) para un valor arbitrario de 𝑍.

 Desplazar esta recta en la dirección de mejora (maximización: hacia arriba/derecha;

minimización: hacia abajo/izquierda).

Encontrar el punto óptimo:

 El último vértice de la región factible tocado por la recta de ZZ al desplazarse es

la solución óptima.

Ventajas y Limitaciones

Ventajas Limitaciones

Visual e intuitivo. Solo aplicable a 2 variables.

Útil para enseñar conceptos de PL. No escala a problemas realistas (>2 variables).

Identifica soluciones óptimas exactas. No maneja restricciones no lineales o enteras.

 CONCLUSIÓN

La Programación Lineal se erige como una piedra angular en la optimización de sistemas

complejos, permitiendo tomar decisiones eficientes en entornos con recursos limitados. A lo largo de

este trabajo, se ha explorado cómo la interacción entre la función objetivo, las restricciones y los

algoritmos de solución —como el método Símplex (Primal y Dual)— conforman un marco robusto para

abordar problemas de maximización o minimización en contextos tan diversos como la logística, la

producción industrial o la gestión financiera.

El método Símplex Primal destaca por su capacidad para navegar desde una solución factible

inicial hacia la optimalidad, recorriendo los vértices de la región factible definida por las restricciones.

Su contraparte, el método Símplex Dual, ofrece una perspectiva complementaria: parte de una solución

óptima en términos de costos reducidos y busca alcanzar la factibilidad, siendo especialmente útil en

escenarios donde se modifican restricciones o se añaden nuevas condiciones a un modelo previamente

resuelto. Ambos métodos, aunque conceptualmente distintos, subrayan la dualidad inherente en la PL

y su flexibilidad para adaptarse a cambios dinámicos.

Las restricciones, ya sean de recurso, capacidad o demanda, no solo delimitan el espacio de

soluciones posibles, sino que también revelan cuellos de botella y oportunidades de mejora. Mediante

el uso de variables de holgura, exceso o artificiales, estas restricciones se integran en un modelo

matemático coherente, donde la función objetivo actúa como brújula que guía hacia el óptimo. Su

formulación precisa es crítica, ya que determina si se maximizan beneficios, se minimizan costos o se

equilibran múltiples metas.

En la práctica, herramientas computacionales como CPLEX, Gurobi o librerías

en Python (PuLP, SciPy) automatizan estos procesos, escalando la PL a problemas con miles de

variables y restricciones. No obstante, es esencial reconocer sus limitaciones: la PL asume linealidad

y certidumbre, lo que en entornos reales puede requerir extensiones hacia modelos estocásticos,

enteros o no lineales.

En síntesis, la Programación Lineal —respaldada por el método Símplex y su dualidad— sigue

siendo un pilar en la optimización moderna. Su valor trasciende lo teórico, materializándose en

aplicaciones que impulsan la eficiencia operativa, reducen costos y mejoran la calidad de vida. Como

campo en evolución, su integración con técnicas de inteligencia artificial y análisis de big data promete

abrir nuevas fronteras, reafirmando su relevancia en un mundo cada vez más orientado a la toma de

decisiones basada en datos.

 Bibliografía

[Link]

[Link]

[Link]

problema-lineal/

[Link]

[Link]/ingenieria/2007/2/IN34A/2/material_docente/bajar%3Fid_material%3D146739

[Link]

[Link]

[Link]

[Link]

[Link]

[Link]

d3ab832afc50