REPUBLICA BOLIVARIANA DE VENEZUELA

UNIVERSIDAD NACIONAL EXPERIMENTAL

RAFAEL MARIA BARALT
VICERRECTORADO ACADÉMICO
PROGRAMA INGENIERÍA Y TECNOLOGÍA
PROGRAMA NACIONAL DE FORMACION EN INFORMÁTICA

Unidad
2:
Progra
mación
TSU. Bozo Lauribeth

lineal
TSU. González Miguel
 Cabimas, agosto de 2016

 Esquema

 Introducción

 Modelos de Programación Lineal

 Solución gráfica de problemas de dos dimensiones

 Método simplex de Resolución y simplex dual

 Conclusión

 Bibliografías
Introducción
Iniciarse en la técnica de programación lineal con el aspecto más importante
del método científico: la representación o modelo en formulación matemática
lineal de algunos problemas elegidos, los agrupados en "clásicos"; también
debe aprender los conceptos teóricos fundamentales utilizando la metodología
gráfica en sólo dos variables.
Modelo de programación lineal general.
El modelo de PL es una representación simbólica (abstracción) de la realidad
que se estudia, se forma con expresiones lógicas matemáticas conteniendo
términos que significan contribuciones: a la utilidad (con máximo), al costo (con
mínimo), al consumo de recurso (disponible con desigualdad <=), al recurso
requerido (con desigualdad >=), recurso especificado (con igual = ). Contiene
las siguientes cuatro partes:
1a parte
Definición con el significado cuantitativo de las variables de decisión
(controlables).

2a parte
Función económica u objetivo a optimizar (máximo o bien mínimo):

3a parte
Sujeta a restricciones:

4a parte
Condición de no negativo a variables:

PROPIEDADES DEL MODELO DE PROGRAMACIÓN LINEAL

Para que un modelo de PL sea válido, debe cumplir las propiedades siguientes:
Proporcionalidad.-Significa que la contribución al valor de la función objetivo y
el consumo o requerimiento de los recursos utilizados, son proporcionales al
valor de cada variable de decisión. Así el término 4X 1 es proporcional, porque
contribuye al valor de la función Z con 4, 8, 12, etc. para los valores 1, 2, 3,
etc., respectivamente, de X1. Se puede observar el aumento constante y
proporcional de 4 conforme crece el valor de X 1. En contraste, el término no
lineal 4X12, contribuye con 4, 16, 36, etc., para los mismos valores 1, 2, 3, etc.,
respectivamente, de la variable X1; Aquí se observa que el aumento en la
contribución no es constante y por lo tanto no hay proporcionalidad.
Aditividad.- Significa que se puede valorar la función objetivo Z, así como
también los recursos utilizados, sumando las contribuciones de cada uno de los
términos que intervienen en la función Z y en las restricciones.
Divisibilidad.- Significa que las variables de decisión son continuas y por lo
tanto son aceptados valores no enteros para ellas. La hipótesis de divisibilidad
más la restricción de no negatividad, significa que las variables de decisión
pueden tener cualquier valor que sea positivo o por lo menos igual a cero.
Certidumbre.- Significa que los parámetros o constantes son estimados con
certeza, o sea, no interviene una función de probabilidad para obtenerlos
El modelo de programación lineal es un caso especial de la programación
matemática, pues debe cumplir que, tanto la función objetivo como todas las
funciones de restricción, sean lineales.
APLICACIONES TÍPICAS DE LA PROGRAMACIÓN LINEAL
Aparentemente, las estructuras de organización complejas propias de la
sociedad moderna han reconocido interesantes problemas de optimización
tales como la manera más eficiente de manejar la economía de un país o
también la mezcla de ingredientes de un fertilizante para satisfacer las
especificaciones agrícolas a costo mínimo. Ambos problemas utilizan el modelo
de programación lineal (PL), para optimizar una función lineal condicionada a
restricciones lineales, que essencillo en su estructura matemática,
pero poderoso por su gran adaptación a una amplia variedad de problemas.
La programación lineal es una técnica matemática de resolución de problemas,
su desarrollo representa una ayuda a los administradores para tomar
decisiones en la asignación de recursos. A continuación aparecen algunas
aplicaciones típicas de la PL:
Un fabricante desea desarrollar un programa de asignación en producción y
una política de inventario que satisfagan la demanda de ventas de periodos
futuros. Así se podría cumplir la demanda con mínimo costo total de producción
y de inventario.
Un analista financiero debe seleccionar una cartera de inversiones a partir de
una diversidad de alternativas en acciones y bonos. Se debe establecer la
cartera que maximice el rendimiento sobre la inversión asignada.
Un administrador de mercadotecnia desea determinar la mejor manera
de asignar un presupuesto de publicidad como radio, televisión, periódicos y
revistas. Al gerente le gustaría determinar la combinación de medios
que maximice la efectividad de la publicidad.
Una empresa tiene almacenes en varias. ubicaciones en todo el país. Para un
conjunto de demandas de sus productos por parte de sus clientes, la empresa
desearía determinar cuánto debe asignar en embarques a cada uno de los
almacenes y a cada cliente, de manera que los costos totales de transporte
resulten mínimos.
Estas aplicaciones representan unas cuantas situaciones en las que se ha
utilizado con éxito la programación lineal, pero ilustran su potencial en la
solución de problemas. Un estudio detallado revela las características comunes
de ellas. En el ejemplo 1, el fabricante desea minimizar costos; en el 2, el
analista financiero desea maximizar el rendimiento sobre la inversión; en el 3,
el gerente de mercadotecnia desea maximizar la efectividad de la publicidad, y
en el ejemplo 4, la empresa desea minimizar los costos totales de
transporte. En todos los problemas de programación lineal, el objetivo es
el máximo o bien el mínimo de alguna cantidad en la acción de asignar
recursos.
Los problemas de programación lineal se caracterizan, además, por las
condiciones impuestas o restricciones de recursos, que limitan el grado en que
se puede cumplir algún objetivo. En el ejemplo 1, el fabricante está limitado por
restricciones que requieren que la demanda de producto quede satisfecha y por
restricciones respecto a la capacidad de producción. El problema de la cartera
del analista financiero está limitado por la cantidad total de fondos de inversión
disponibles y las cantidades máximas que se pueden invertir en cada acción o
bono. La decisión en la selección de medios del gerente de mercadotecnia,
está restringida por un presupuesto de publicidad fijo y por la disponibilidad de
los varios medios. En el problema de transportación, el programa de
embarques de costo mínimo está restringido al suministro de productos
disponibles en cada almacén. La diversidad de condiciones mencionadas, es
parte de lo que puede esperar aquel que decida enfrentar un problema, pues
las restricciones son otra característica general en todo problema de
programación lineal.

Método gráfico para resolver modelos de programación lineal con solo

dos variables.

En esta sección interesa hacer análogos geométricos, esto es, gráficas de

funciones lineales que contiene el modelo matemático de programación lineal
obtenido en la formulación del problema que se analiza. Dicho modelo puede
contener expresiones tanto en forma de ecuaciones ( = ) como en
desigualdades ( <= ó >= ), cada una de ellas corresponde a un gráfico en la
analogía geométrica.
Primero considere la infinidad de puntos que constituyen en conjunto el plano y
los cuatro cuadrantes convencionalmente aceptados, para dividirlo en zonas
caracterizadas por la combinación de signo que se puede dar, a los valores
medidos con números reales. Para lograr los cuadrantes en el plano se utilizan
los ejes cartesianos con escala de medición de valores de las variables del
problema; por ejemplo, se puede asignar el eje horizontal de abscisas para la
medición de valores de la variable X1; también se puede asignar el eje vertical
de ordenadas, para la medición de valores de la variable X 2. La localización de
cualquier punto en este espacio plano requiere de una distancia horizontal (X 1)
y de una distancia vertical (X2) denotado como par ordenado o vector (X 1, X2).
Un punto sobre el eje X1 corresponde a X2=0 y un punto sobre el eje
X2 corresponde a X1=0, que son las ecuaciones respectivas de los ejes
horizontal y vertical. Dichos ejes se cruzan en el punto (X 1, X2) = (0, 0), el cual
se conoce como origen.
Si la ecuación tiene sólo dos variables, el gráfico de la misma sobre el plano es
una línea recta, es decir, se requiere un espacio de dos dimensiones, la
horizontal y la vertical, para graficar tal ecuación; pero la representación
geométrica de una ecuación en tres variables, requiere un espacio de tres
dimensiones. En tal caso, a los ejes X 1 y X2, se les agrega un tercer eje
X3 como tercera dimensión, que pasa por el origen hacia el observador.

Método simplex de Resolución y simplex dual.

El método simplex dual resulta ser una estrategia algoritmica eficiente cuando
luego de llevar un modelo de programación lineal a su forma estándar, la
aplicación del método simplex no es inmediata o más bien compleja, por
ejemplo, puede requerir la utilización del método simplex de 2 fases.
Una aplicación típica del método simplex dual es en la resolución de problemas
con una función objetivo de minimización, con restricciones del tipo mayor o
igual y donde las variables de decisión son mayores o iguales a cero.
Ejemplo Simplex Dual
Considere el siguiente modelo de Programación Lineal:
Paso 1: Se lleva el modelo a su forma estándar. En nuestro ejemplo esto se
logra agregando variables de exceso en cada una de las restricciones (3
primeras: S1, S2, S3, respectivamente). Luego, se multiplica cada fila de las
restricciones por -1 de modo de disponer una solución básica inicial (infactible)
en las variables de exceso S1, S2 y S3. De esta forma se obtiene la siguiente
tabla inicial.

A B C S1 S2 S3

-15 -2 -1 1 0 0 -200

-7,5 -3 -1 0 1 0 -150

-5 -2 -1 0 0 1 -120

315 110 50 0 0 0 0

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

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

A B C S1 S2 S3

-
1 2/15 1/15 0 0 40/3
1/15
 0 -2 -1/2 -1/2 1 0 -50

-
0 -4/3 -2/3 -1/3 0 1
160/3

-
0 68 29 21 0 0
4.200

Paso 4: Continuar las iteraciones y siguiendo el mismo procedimiento hasta

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

A B C S1 S2 S3

- 1/1
1 0 0 0 8
1/10 0

0 1 0 1/4 -1 3/4 10

0 0 1 0 2 -3 60

-
0 0 0 4 10 36
6.620

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

óptimo V(P)=6.620 (marcado en rojo - se obtiene con signo cambiado).
También es interesante notar que los costos reducidos de las variables
artificiales S1, S2 y S3 (marcado en amarillo), corresponde a la solución óptima
del modelo presentado en el tutorial de solver, esto dado que dicho modelo
resulta ser elproblema dual de nuestro ejemplo.
Conclusión
La programación lineal es una técnica poderosa para tratar problemas de asignación de
recursos escasos entre actividades que compiten, al igual que otros problemas cuya
formulación matemática es parecida. Se ha convertido en una herramienta estándar de
gran importancia para muchas organizaciones industriales y de negocios. Aún más, casi
cualquier organización social tiene el problema de asignar recursos en algún contexto y
cada vez mayor el reconocimiento de la aplicabilidad tan amplia de esta técnica.

Bibliografías
[Link]
lineal_23.html
[Link]
[Link]
industrial/investigaci%C3%B3n-de-operaciones/programaci%C3%B3n-lineal/