segunda unidad
TRANSCRIPT
Unidad 2 MARLON VILLA VILLA
1
UNIRESIDAD NACIONAL DE CHIMBORAZO
FACULTAD DE CIENCIAS POLITICAS Y ADMINSITRATIVAS
CARRERA DE CONTABILIDAD Y AUDITORÌA
UNIDAD 2
PROGRAMACIÓN LINEAL
QUINTO SEMESTRE “A”
NOMBRE: JESSICA PÈREZ
DOCENTE: MARLON VILLA VILLA
2014- 2015
Unidad 2 MARLON VILLA VILLA
2
PROGRAMACIÒN LINEAL
CONCEPTOS PROPIOS DE LA PROGRAMACIÓN LINEAL:
PROGRAMACION LINEAL
Es una parte de la investigación operativa que la podremos aplicar cuando el problema que tratamos se puede traducir a expresiones matemáticas de tipo lineal y que las l imitaciones o restricciones que tenga el sistema productivo se pueda también traducir en expresiones matemáticas de tipo lineal.
FUNCION OBJETIVO
Es una expresión matemática lineal que representa el objetivo del problema. Es la expresión que tendremos que maximizar o minimizar.
ECUACIONES O INECUACIONES DE RESTRICCION
Expresiones matemáticas, ecuaciones o inecuaciones de tipo lineal que representan las limitaciones del problema.
Solución Posible: Es cualquier conjunto de valores de la variable que satisface el s istema de ecuaciones de la restricción.
Solución Posible Básica: Es aquella solución posible en la que ninguna variable toma va lores negativos.
Solución Básica Posible Degenerada: Solución básica pos ible en la que al menos una variable toma el va lor cero
Solución Óptima: Es aquella solución básica posible que optimiza a la función objetivo.
Unidad 2 MARLON VILLA VILLA
3
ESTRUCTURA DE UN MODELO DE PL
MODELO GENERAL DE PL
OPTIMIZAR Z =
SUJETO A:
GRÁFICA DE DESIGUALDADES Y CONTORNOS
FUNCIÓN OBJETIVO Consiste en optimizar el objetivo que persigue una situación la cual es una función lineal de las diferentes actividades
del problema, la función objetivo se maximiza o se minimiza
VARIABLES DE DECISIÓN. Son las incógnitas del problema, La
definición de las variables es el punto clave y básicamente consiste en l0s niveles de todas las actividades que
pueden llevarse a cabo en el problema a formular.
RESTRICCIONES ESTRUCUTURALES. Diferentes requisitos que deben
cumplir cualquier solución para que pueda llevarse a cabo, dichas restricciones pueden ser de
capacidad, mercado, materia prima, calidad, balance de materiales, etc.
CONDICIÓN TÉCNICA. Todas las variables deben tomar valores
positivos, o en algunos casos puede ser que algunas variables tomen
valores negativos
n
j
jj xc1
n
j
ijij mibxa1
,......,2,1
njx j ,.......,2,10
Unidad 2 MARLON VILLA VILLA
4
EL MÉTODO GRÁFICO
Gráfica de la igualdad. Convierta la desigualdad en igualdad y grafique la
recta
Escoja un punto de ensayo
Evalúe el primer miembro de la expresión
Determine si el punto de ensayo satisface la
desigualdad.
Unidad 2 MARLON VILLA VILLA
5
CONJUNTO CONVEXO
El método gráfico es una forma fácil para resolver problemas de
Programación Lineal, siempre y cuando el modelo conste de dos
variables
Los pasos necesarios para realizar el método son:
Hallar las restricciones del problema
Las restricciones de no negatividad Xi ≥ 0 confían todos los
valores posibles.
Sustituir ≥ y ≤ por (=) para cada restricción, con lo cual se produce la
ecuación de una línea recta.
Trazar la línea recta correspondiente a cada restricción en el plano
El espacio en el cual se satisfacen las tres restricciones es el área factible
Las líneas paralelas que representan la función objetivo se trazan
mediante la asignación de valores arbitrarios a fin de determinar la
pendiente y la dirección en la cual crece o decrece el valor de la función
objetivo.
La solución óptima puede determinarse al observar la dirección
en la cual aumenta la función objetivo,
par de puntos de C se encuentra
totalmente en C
Un conjunto C es convexo si el
segmento rectilíneo que une cualquieR
CONJUNTO CONVEXO
Unidad 2 MARLON VILLA VILLA
6
VARIABLES DE HOLGURA Y VARIABLES DE EXCEDENTE
RESTRICCIONES
Variable agregada al lado izquierdo de una restricción de "menor o igual que" para convertir la restricción en una igualdad
• Variable de holgura
Variable restada del lado izquierdo de una restricción de "mayor o igual que" para convertir dicha restricción en una igualdad.
• Variable de Excedente
RESTRICCIÓN ACTIVA.
Dada una solución factible, una restricción es activa si a l sustituir el va lor de las
variables se cumple la igualdad. Es decir, para esa solución el valor de la holgura o
excedente, según sea el caso es CERO
RESTRICCIÓN INACTIVA.
Dada una solución factible, una restricción es inactiva si a l sustituir el va lor de las variables no se cumple la igualdad. Es deci r, para esa solución el valor de la
holgura o excedente, según sea el caso es DIFERENTE A CERO
Unidad 2 MARLON VILLA VILLA
7
PROBLEMAS NO ACOTADOS
PROBLEMAS NO FACTIBLES
Hay que distinguir el término “problema no acotado” con el término “conjunto factible no
acotado”, éste último se refiere a una región factible en la que al menos una
de las variables de decisión puede asumir valores indefinidamente
grandes
Si un programa lineal es no acotado, el conjunto factible también debe ser no acotado. Sin embargo, es posible
tener un conjunto factible no acotado sin que el problema sea no acotado
Son problemas que tiene un conjunto factible vacío:
es decir no existe combinación de valores para las variables de
decisión que satisfaga simultáneamente todas las
restricciones
Unidad 2 MARLON VILLA VILLA
8
EL PROBLEMA DUAL
En un modelo de programación lineal cada problema lineal tiene otro
problema denominado problema dual (PD),
que posee importantes propiedades y relaciones notables con respecto al
Problema lineal original, llamado problema primal
(PP)
Las relaciones las podemos enumerar como
siguen:
El problema dual tiene tantas variables como restricciones tiene
el programa primal.
El problema dual tiene tantas restricciones como variables tiene
el programa primal
Los coeficientes de la función objetivo del problema dual son los
términos independientes de las restricciones o RHS del programa
primal
Los términos independientes de las restricciones o RHS del dual son los coeficientes de la función objetivo
del problema primal.
La matriz de coeficientes técnicos del problema duales la traspuesta de la matriz técnica del problema
primal.
El sentido de las desigualdades de las restricciones del problema dual y el signo de las variables del mismo
problema, dependen de la forma de que tenga el signo de las variables
del problema
Si el programa primal es un problema de maximización, el
programa dual es un problema de
Minimización
El problema dual de un problema dual es el programa primal original.
Tabla de TUCKER
Unidad 2 MARLON VILLA VILLA
9
MAXIMIZACION
RESTRICCIONES
≤ ≥ =
VARIABLES ≥
≤ > < MINIMIZACIÓN
VARIABLES ≥
≥ > < RESTRICCIONES
≥
≤ =