INVESTIGACION

DE OPERACIONES

PROGRAMACIÓN
LINEAL
UNIDAD 2
 CONTENIDO
2.1 CONCEPTO

2.2 MÉTODOS DE SOLUCIÓN

2.2.1 MÉTODO GRÁFICO

2.2.2 MÉTODO SIMPLE

2.3 PLANEACIÓN Y SOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL

2.4 APLICACIONES COMPUTACIONALES

PROGRAMACIÓN
MATEMATICA O
TEORIA DE LA
OPTIMIZACIÓN
La programación lineal esta relacionada con la
programación matemática que se define de la
siguiente manera:

Es una rama de la Matemática Aplicada que

trata técnicas para maximizar o minimizar una
función objetivo sujeta a condiciones lineales,
no lineales y enteras en las variables

Tiene como finalidad resolver problemas de decisión

donde se desea optimizar un determinado objetivo,
teniendo en cuenta ciertas limitaciones de los recursos
disponibles.
TEMA 2.1

PROGRAMACIÓN
LINEAL
Consiste en la maximización o minimización de
una función objetivo lineal en sus variables sujeta
a condiciones de igualdad y desigualdad.
 En términos matemáticos, un problema
de programación lineal queda definido
por:

LAS VARIABLES UNA FUNCIÓN CONJUNTO DE

DEL PROBLEMA OBJETIVO: VALORES K:

Denominadas variables
Representa Satisfacen todas las
instrumentales.
matemáticamente, el condiciones del
Comúnmente, se
objetivo final a problema que se trata
denotan por xi o el
conseguir, denotada de resolver. Éstas
vector X, y
como Z, también lineal. también son lineales
necesariamente han de
tomar valores mayores
o iguales que cero.
 2.2 MÉTODOS DE SOLUCIÓN
En los problemas de optimización se plantea la búsqueda de una solución óptima (si existe) del
conjunto de las variables.

1. Solución Factible O Vector Admisible De Un Problema De

Programación Lineal: Es cualquier valor de X que satisface las
restricciones, refiriéndonos a la forma estándar, es decir, que la
solución esté contenida dentro del conjunto convexo (intersección de
las restricciones, que al tratarse de desigualdades lineales delimitan
semi-espacios cerrados) de oportunidades.

2. Solución Factible Óptima: Es aquel o aquellos vectores

admisibles para los que la función objetivo alcanza el óptimo
(mayor o menor valor). Está solución no tiene por qué ser única,
pueden existir infinitas soluciones.
3. Solución Básica: La solución especial obtenida por asignar las
variables independientes (no básicas) el valor cero y resolver para las
variables dependientes o básicas que coinciden con m (número de
restricciones).

4. Solución Básica Factible: Es una solución básica en la cual toda x, ≥ 0

5. Solución Óptima: Es una solución básica factible que optimiza la

función objetivo del problema.

6. Forma Canónica: Sistema de ecuaciones y variables, se dice que está

en forma canónica con respecto a un conjunto de variables si y solo si x
tiene un coeficiente unitario en la ecuación y coeficientes nulos en el
resto de las ecuaciones.
2.2.1 MÉTODO
GRAFICO

Se utiliza cuando el problema de

programación lineal tiene dos
variables de decisión. Se basa en la
representación gráfica de las
restricciones y la identificación de
la mejor solución dentro de la
región factible
 PASOS DEL MÉTODO GRÁFICO:
1 Formular el problema: Definir la función objetivo y las restricciones.

2 Representar las restricciones en un plano cartesiano: Convertir las

inecuaciones en ecuaciones y graficarlas.

3 Determinar la región factible: Es el área donde se cumplen todas las

restricciones.

4 Evaluar los vértices de la región factible: La mejor solución se

encuentra en alguno de estos puntos.

5 Seleccionar la mejor solución: Evaluar la función objetivo en los

vértices y elegir el que optimiza la función.
 2.2.2 METODO SIMPLE
Se trata de un algoritmo iterativo y se utiliza cuando hay tres o más variables, lo que hace imposible
el uso del método gráfico. Su objetivo es obtener una solución posible, mínima en un número finito
de iteraciones.

En estas iteraciones, se pretende encontrar una nueva solución posible cuyo valor correspondiente
de la función objetivo sea menor que el valor de la precedente. Este proceso continúa, hasta que se
alcanza una solución mínima.
 PASOS DEL MÉTODO SIMPLE:
Está dividido en dos fases.

1 Se introduce una nueva función objetivo (w): que es la suma de las variables
artificiales, con el propósito de encontrar una solución básica factible para
el problema original. Se aplica el algoritmo Simplex para minimizar (w)
hasta que alcance cero. Si esto ocurre, se pasa a la Fase II.

2 Se sustituye (w) por la función objetivo original (z) y se continúa aplicando

Simplex hasta encontrar la solución óptima.

El proceso se organiza en tablas, que se actualizan mediante operaciones de

✔️
pivotaje para:

✔️
Obtener la matriz identidad en las variables básicas.
Lograr costes relativos nulos en las variables básicas
 2.3 PLANTEAMIENTO Y SOLUCIÓN DE
PROBLEMAS DE PROGRAMACIÓN LINEAL
Para el planteamiento de un problema de programación lineal, se deben cumplir y cinco condiciones
básicas:

1 2 3 4 5
Recursos Limitados: Objetivo Explícito: Linealidad: Proceso, Homogeneidad: Los Divisibilidad:
Se refiere a la Es la maximización actividad o relación productos Presupone que
cantidad limitada de utilidades o que se refiere con elaborados en una tanto productos
ya sea de horas de minimización de respecto a la maquinaria son como recursos se
trabajo, equipos, costos cantidad de cada idénticos o todas las pueden subdividir
Duis aute irure dolor in Duis aute irure dolor in Duis aute irure dolor in
dinero, materiales, uno de
reprehenderit in voluptate velit los y a las horas de
reprehenderit in voluptate velit trabajoreprehenderit in en
de fracciones
voluptate velit
esse cillum dolore eu fugiat nulla esse cillum dolore eu fugiat nulla esse cillum dolore eu fugiat nulla
suministros. pariatur.
cantidades de cada un
pariatur.
obrero son igual pariatur.
uno de los de productivas.
productos.
 Definir Variables Del Problema:
01 Identificar y expresar restricciones en el
planteamiento del problema.

PARA REALIZAR UNA SOLUCIÓN EN LA

PROGRAMACIÓN LINEAL, SE INICIA CON Definir La Función Objetivo:
LOS SIGUIENTES PASOS: 02 Se determinan las variables, se representa
con letras y se definen sus unidades.

Definir Restricciones:
03 Se optimizan las variables, se representan con la
letra z, mediante una ecuación matemática en
función a las variables del problema y sus
coeficientes.

Definir Restricciones No Explícitas:

04 Se establece una ecuación en relación con las
variables del problema. Se representan por
desigualdades, sean de tipo mayor que o
menor que.
2.4 APLICACIONES
COMPUTACIONALES
La programación lineal se aplica en computación mediante
software que permite resolver modelos lineales con muchas variables.
Algunos de estos software son: Lindo, Tora, Microsoft Excel Solver, WinQSB,
Matlab.
Algunas aplicaciones de la programación lineal son:
Asignación de recursos: Se usa para distribuir recursos limitados, como
presupuestos de publicidad, entre diferentes medios de comunicación.
Planificación de rutas: Se usa para planificar rutas de transporte y horarios
de salida de vuelos.
Gestión de inventarios: Se usa para controlar inventarios y asignar
recursos óptimamente.
Mezcla de recursos: Se usa para decidir cómo mezclar dos o más fuentes
para producir uno o más productos.