PROGRAMACIÓN LINEAL

Solución Posible.- conjunto de valores de la variable que satisface las ecuaciones de restricción.

Solución Básica posible degenerada.- al menos una variable toma el valor cero.

Solución posible básica.- ninguna variable toma valores negativos.

Solución óptima.- optimiza a la función objetivo.

Est

á da

da p

or e

xpre

sion

es m

atem

átic

as d

e tip

o lin

eal

FUNCIÓN OBJETIVO

• Se maximiza

o se minimiza

VARIABLES DE DECISIÓN

• Son las incógnitas

del problema

RESTRICCIONES

• Requisitos que deben cumplirse

CONDICIÓN TÉCNICA

• Las variables deben tomar valores positivos, y en algunos casos negativos

ESTRUCTURA DE UN MODELO DE PROGRAMACIÓN LINEAL

6) Las líneas paralelas que representan la función objetivo se trazan mediante la asignación de valores arbitrarios.

7) .  La solución óptima puede determinarse al observar la dirección en la cual aumenta la función objetivo.

4) Trazar la línea recta correspondiente a cada restricción en el plano. El punto que cumpla con la inecuación indicara el área correspondiente.

5) 5. El espacio en el cual se satisfacen las tres restricciones es el área factible

2)  Las restricciones de no negatividad  Xi ≥  0 confían todos los valores posibles.3) Sustituir  ≥ y ≤  por (=) para cada restricción, con lo cual se produce la ecuación de una línea

recta.

PASOS1)  Hallar las restricciones del problema

MÉTODO GRÁFICOSe utiliza para resolver problemas de Programación Lineal, siempre y cuando el modelo conste de

dos variables.  

Ambas deben cumplir con el requisito

de no negatividad

HOLGURA.- cantidad de recurso no

usado.

VARIABLES

EXCEDENTE.- cantidad por encima

de algún nivel mínimo

requerido.

RESTRICCIÓN ACTIVA

RESTRICCIÓN INACTIVA

• Es activa si al sustituir el valor de las variables se cumple la igualdad.

• Semirrecta que forma parte de la solución

• Es inactiva si al sustituir el valor de las variables no se cumple la igualdad.

• Recta que no forma parte de la solución óptima

De acuerdo a la solución obtenida, tenemos:

Tipos de problemas por el resultado

• Factible o de solución óptima.- una única solución que satisface el problema

• Solución Múltiple.- pares de coordenadas dentro del segmento de solución.

• No factible.- conjunto de solución vacío

ACOTADOS.- están delimitadas por un contorno.

• Solución óptima.- si se trata de un problema de minimización.• Infinitas soluciones.- problema de minimización cuyas coordenadas

de solución están en un segmento de recta.• No factible.- conjunto de solución vacío.

NO ACOTADOS.- no poseen contorno y los valores de una de las rectas toma valores infinitos.

EL PROBLEMA DUAL.- es un subproblema de l

problema primal

Si una variable de primal es positiva,

entonces la correspondiente

restricción del dual es una restricción

saturada, es decir, se verifica como una

igualdad.

Si una restricción del primal es no

saturada, entonces la variable de dual

asociada debe ser nula.

PROBLEMA DUAL.- relacionesa) El problema dual tiene tantas variables como restricciones tiene el programa primal.

b) El problema dual tiene tantas restricciones como variables tiene el programa primal

c) Los coeficientes de la función objetivo del problema dual son los términos independientes de las restricciones o RHS del programa primal

d) Los términos independientes de las restricciones o RHS del dual son los coeficientes de la función objetivo del problema primal

e) La matriz de coeficientes técnicos del problema duales la traspuesta de la matriz técnica del problema primal.

f) 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 Primal y del sentido de las restricciones del mismo problema

g) Si el programa primal es un problema de maximización, el programa dual es un problema de Minimización

h) El problema dual de un problema dual es el programa primal original.