INTEGRANTES:

Barreto Yoryina C.I: 22.858.246

PROFESORA: Garcia Isbeth C.I: 25.893.095
Ing. Carlena Astudillo La Rosa Jorge C.I: 21.175.916
Soto Delysmar C.I: 25.934.338

El Tigre, Septiembre de 2018

PROGRAMACIÒN LINEAL
 El Modelo de Programación Lineal, es una representación simbólica de la realidad que se estudia,
o del problema que se va a solucionar. Se forma con expresiones de lógicas matemáticas,
conteniendo términos que significan contribuciones: a la utilidad (con máximo) o al costo (con
mínimo) en la Función Objetivo del modelo. Y al consumo de recursos disponibles (con
desigualdades = ó = e igualdades =) en las restricciones.

Modelos Matemáticos de Programación Lineal de:

 Maximización: cuando se desea maximizar o incrementar las utilidades, producción,
ventas,
beneficios, rentabilidad, publicidad, etc.

 Minimización: cuando se desea minimizar o disminuir los costos, perdidas,

paradas,
desperdicios, distancias, tiempos inoperativos, etc.
 Es un procedimiento de solución de problemas de programación lineal, muy
limitado en cuanto al número de variables (2 si es un gráfico 2D y 3 si es 3D)
pero muy rico en materia de interpretación de resultados e incluso análisis de
sensibilidad.

El procedimiento consiste en trazar

las ecuaciones de las restricciones en
un eje de coordenadas X1, X2 para
tratar de identificar el área de
soluciones factibles (soluciones que
cumplen con todas las restricciones).
 El Método Simplex es un método analítico de solución de problemas de
programación lineal capaz de resolver modelos más complejos que los resueltos
mediante el método gráfico sin restricción en el número de variables.

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

solución en cada paso. La razón matemática de esta mejora radica en que el
método consiste en caminar del vértice de un poliedro a un vértice vecino de
manera que aumente o disminuya (según el contexto de la función objetivo, sea
maximizar o minimizar), dado que el número de vértices que presenta un poliedro
solución es finito siempre se hallará solución.
Esta estrategia algorítmica se aplica cuando luego de llevar un modelo de
programación lineal a su forma estándar no se dispone de una solución básica
factible inicial.

Fase 1: Consideramos un problema auxiliar que resulta de agregar tantas variables

auxiliares a las restricciones del problema, de modo de obtener una solución básica
factible. Luego se debe resolver utilizando el Método Simplex un nuevo problema que
considera como función objetivo la suma de las variables auxiliares. Si el valor óptimo
alcanzado al finalizar la Fase 1 es cero ir a la Fase 2. En caso contrario, no existe
solución factible.
Fase 2: Resolver a través del Método Simplex el problema original a partir de
la
solución básica factible inicial hallada en la Fase1.
 Cada problema de programación lineal tiene un segundo problema asociado con el.
Uno se denomina primal y el otro dual. Los 2 poseen propiedades muy relacionadas,
de tal manera que la solución óptima a un problema proporciona información
completa sobre la solución óptima para el otro.

Se aplica para resolver problemas que empiezan con factibilidad dual, es decir,
óptimos pero infactibles. Es un proceso iterativo que puede generar varias
aproximaciones a la solución a través de distintas tablas de solución. Se puede
identificar cuando se ha llegado a la solución óptima.
 La dualidad en programación lineal provee de resultados
teóricos interesantes que justifican su uso como herramienta
alternativa y complementaria de resolución.

La dualidad permite realizar importantes

interpretaciones económicas de los problemas
programación lineal. de
 El análisis de sensibilidad o postoptimal para los modelos de Programación
Lineal, tiene por objetivo identificar el impacto que resulta en los resultados del
problema original luego de determinadas variaciones en los parámetros, variables o
restricciones del modelo, sin que esto pase por resolver el problema nuevamente.

Es decir, ya sea si resolvemos nuestro modelo gráficamente o utilizando el

Método Simplex, lo que se busca es que estas variaciones o sensibilidad hagan uso
de la solución y valor óptimo actual, sin tener la necesidad de resolver para cada
variación un nuevo problema.
 El complemento Solver de Excel (que también esta disponible en una versión
Premium de Prueba) es una excelente herramienta para quienes se inician en la
resolución de modelos de Investigación Operativa por tener una interfaz amigable,
permite resolver aplicaciones estudiantiles (en cuanto al tamaño del modelo) y
estar disponible como un complemento del software Excel. Ingrese a la sección
Solver de Excel para interiorizarse en cuanto a su uso.

Para hacer uso de Solver se debe activar este complemento y

este
procedimiento varía dependiendo si se esta utilizando Office 2003 o Office
2007.
 INSTALACIÓN SOLVER DE EXCEL UTILIZANDO
MICROSOFT OFFICE 2007

Paso 1: Seleccione el boton Office en la esquina superior izquierda.

Paso 2: Seleccione Opciones de Excel.

 INSTALACIÓN SOLVER DE EXCEL UTILIZANDO
MICROSOFT OFFICE 2007

Paso 3: En el menu de la izquierda debe seleccionar Complementos y luego presionar el

boton Ir
 INSTALACIÓN SOLVER DE EXCEL UTILIZANDO
MICROSOFT OFFICE 2007

Paso 4: Marque la opción Solver y luego seleccione Aceptar.

Paso 5: Probablemente se le
autorización para instalar pediría el
Seleccione Sí. complemento.

Paso 6: Si la instalación ha resultado satisfactoria el complemento Solver deberá estar

disponible en la sección Datos de Excel.
Para ejemplificar respecto al uso de Solver utilizaremos el
siguiente modelo de Programación Lineal:
Paso 1: Abrir una planilla de cálculo de Excel y definir las variables de decisión y la
función objetivo. En este ejemplo se han marcado con amarillo y verde las
variables de decisión y función objetivo respectivamente sólo para facilitar la
comprensión. Es importante notar que la función objetivo (celda F4) será siempre
una fórmula que depende de los parámetros de la función objetivo (celdas B5, C5,
D5) y las variables de decisión (B4, C4, D4)
Paso 2: Se definen las restricciones del modelo. La columna en amarillo bajo el
titulo "Lado Izq" es una fórmula de los parámetros y las variables de decisión en las
respectivas restricciones. Por ejemplo, la fórmula incorporada en E9 es simplemente:
15X + 7,5Y + 5Z. La celda F9 es el lado derecho de dicha restricción y corresponde
a una constante (315).
Paso 3: Ingresamos a la Opción Solver (Ver Instalacion Solver de Excel). Luego
definimos la celda objetivo (función objetivo), el valor que buscamos
(máximización o minimización), las celdas que deseamos cambiar (variables de
decisión) y las restricciones. Para nuestro ejemplo está será la pantalla que se
debe obtener:
Paso 4: Accedemos a "Opciones..." y seleccionamos "Adoptar modelo
lineal"y "Adoptar no negativos". Finalmente seleccionamos "Aceptar" y
luego "Resolver".
Paso 5: Si el proceso se ha desarrollado en forma correcta la planilla de
cálculo se actualizará y se obtendrán los siguientes resultados. Solución
Óptima: X=4, Y=10, Z=36. Valor Óptimo: V(P)=6.620. Se recomienda
requerir el informe de sensibilidad tal como se muestra en la imagen de
abajo.
Paso 6: La imagen a continuación ha sido levemente editada y corresponde al
informe de sensibilidad. Por ejemplo, el parámetro que actualmente acompaña a X
en la función objetivo es 200, sin embargo, si este valor varía entre [120,240] se
conservará la actual solución óptima. En cuanto a las restricciones podemos decir,
por ejemplo, que si el lado derecho de la segunda restricción (actualmente
este lado derecho es igual a 110) aumenta a 120, es nuevo valor óptimo será
V(P)=6.620 + 10*10 =6.720, es decir, el valor óptimo aumentará en forma
proporcional al precio sombra de dicha restricción. Se recomienda revisar la
sección de Análisis de Sensibilidad para reforzar estos conceptos.
PROGRAMACIÒN ENTERA
 Es aquel cuya solución óptima tiene sentido solamente si una parte o todas las
variables de decisión toman valores restringidos a números enteros, permitiendo
incorporar en el modelamiento matemático algunos aspectos que quedan fuera del
alcance de los modelos de Programación Lineal.

Los modelos de Programación Entera se pueden clasificar en 2 grandes áreas:

 Mixta (PEM): A esta categoría pertenecen aquellos problemas de optimización que
consideran variables de decisión enteras o binarias pero no de forma exclusiva.
 Pura (PEP): En esta categoría encontramos aquellos modelos de Programación Entera
que consideran exclusivamente variables de decisión que adoptan valores enteros o
binarios
 El método de Branch and Bound (en español Ramificación y Acotamiento)
aborda la resolución de modelos de programación entera a través de la resolución
de una secuencia de modelos de programación lineal que constituirán los nodos o
subproblemas del problema entero.

Si bien el procedimiento es extensible a un número

mayor de variables, para efectos prácticos ilustraremos su
aplicación para modelos de programación entera en 2
variables.
PROGRAMACIÒN
NO LINEAL
 Es el proceso de resolución de un sistema de igualdades y desigualdades
sujetas a un conjunto de restricciones sobre un conjunto de variables reales
desconocidas, con un función objetivo a maximizar (o minimizar), cuando
alguna de las restricciones o la función objetivo no son lineales.

Modelos de Programación no Lineal de:

 OPTIMIZACIÓN NO RESTRINGIDA
 OPTIMIZACIÓN RESTRINGIDA LINEALMENTE
 PROGRAMACIÓN SEPARABLE
 PROGRAMACIÓN CUADRÁTICA
 PROGRAMACIÓN CONVEXA
 PROGRAMACIÓN NO CONVEXA
 ROGRAMACIÓN GEOMÉTRICA
 PROGRAMACIÓN FRACCIONAL
 Un modelo de Programación Lineal (PNL) es aquel donde las variables de decisión
se expresan como funciones no lineales ya sea en la función objetivo y/o restricciones
de un modelo de optimización. Esta característica particular de los modelos no lineales
permite abordar problemas donde existen economías o deseconomías de escala o en
general donde los supuestos asociados a la proporcionalidad no se cumplen.

En este sentido el método del gradiente (conocido también como método de Cauchy
o del descenso más pronunciado) consiste en un algortimo específico para la resolución
de modelos de PNL sin restricciones, perteneciente a la categoría de algoritmos
generales de descenso, donde la búsqueda de un mínimo esta asociado a la resolución
secuencial de una serie de problemas unidimensionales.
 Los pasos asociados a la utilización del método del gradiente o descenso
más pronunciado consiste en:
 El método de multiplicadores de Lagrange (el cual es generalizado por las
condiciones de optimalidad de Karush-Kuhn-Tucker) permite abordar la resolución
de modelos de programación no lineal que consideran restricciones de igualdad.

En este sentido y como resulta natural, el dominio de soluciones factibles

considerará exclusivamente aquellas soluciones que permiten verificar el
cumplimiento de la igualdad de dichas restricciones.

Por el contrario, un problema de optimización que considera inecuaciones como

restricciones, sólo requiere que éstas se cumplan y no necesariamente se deberá
forzar el cumplimiento de ellas en igualdad (activas).
 No existe una única forma de abordar la resolución de un problema de programación no
lineal utilizando el teorema de KKT. Consideraremos la aplicación de este teorema en este caso
para problemas sólo con restricciones "<=" (menor o igual). Si el problema tiene restricciones
">=" éstas se pueden transformar por "<=" multiplicando por -1.

Básicamente el procedimiento consiste en resolver el problema no lineal como uno sin

restricciones, luego si la solución óptima de dicho problema no cumple la totalidad o parte de las
restricciones del problema se activan dichas restricciones (en conjunto y/o secuencialmente) y se
resuelve nuevamente. Esto se repite hasta llegar a un conjunto de restricciones activas cuya
solución también satisface las restricciones omitidas. Notar que si se han activado la totalidad de
restricciones sin encontrar una solución factible, entonces el problema es infactible.
 Hallar el Lagrangeano de la función.
 Derivar el Lagrangeano sólo respecto a variables de la función.
 Plantear las ecuaciones:
 Derivadas=0
 λj(Restricciones)=0
 Restricciones con desigualdad
 λj con desigualdad de acuerdo a la tabla
 Planteamiento de casos para λj y desarrollo para cada uno de ellos.
 Al conseguir los valores óptimos de cada variable para cada caso, se evalúan los
mismos en el conjunto de ecuaciones planteadas, las cuales deben satisfacer para
optar a solución del problema.
 En caso de tener dos o más casos cuyos valores óptimos de las variables cumplan
con las ecuaciones planteadas, se elige en caso de maximización, aquellos valores
que maximicen la función objetivo.
 El método o algoritmo de Frank Wolfe fue propuesto en 1956 por
Marguerite Frank y Philip Wolfe y se aplica a problemas de optimización
matemática con una función objetivo no lineal convexa y cuyo dominio de
soluciones factibles esta compuesto exclusivamente por restricciones
lineales, es decir, es un conjunto convexo (en consecuencia el problema es
convexo).
1.- BAZARA, M. , SHETTY, S. Foundations of Optimization.

2.- HILLIER, F.; LEBERMAN, G.J. Introducción a la Investigación de Operaciones. Mc

Graw-Hill, 1991.

3.- LUENBERGER, D. Programación Lineal y no Lineal. Addison Wesley, 1973.

4.- PARDO, L.; FELIPE, A.; PARDO,J.A. Programación Lineal Entera. Aplicaciones
prácticas en la empresa. Diaz Santos, 1990.

5.- PRAWDA, W. Métodos y Modelos de Investigación de Operaciones. Limusa, 1976.

6.- RÍOS INSÚA, S. Investigación Operativa, Optimización. Centro de estudios

Ramón
Areces, 1988.

7.- SHAPIRO, J. Mathematical Programming, Structures and Algorithms.