MATERIA
PROGRAMACIÓN
LINEAL.
Es una parte de la investigación
operativa que la podremos aplicar cuando el problema que tratamos se puede
traducir a expresiones
PROGRAMACIÓN
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
limitaciones o restricciones que tenga el sistema productivo se pueda también traducir en expresiones matemáticas de
tipo lineal.
Función 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
Restricción: Expresiones matemáticas, ecuaciones o inecuaciones de tipo lineal que representan
las limitaciones del problema.
a11x1 + a12x2 + … + a1nxn ≤ b1
a21x1 + a22x2 + … + a2nxn >= b2
a31x1 + a32x2 + … + a3nxn ≤ b3
………………………………
am1x1 + am2x2 + … + amnxn =
bm
Solución Posible: Es cualquier
conjunto de valores de la variable que satisface el sistema de ecuaciones de la restricción.
Solución Posible Básica: Es aquella
solución posible en la que ninguna variable toma valores negativos.
Solución Básica Posible Degenerada: Solución
básica posible en la que al menos una variable toma el valor cero.
Solución
Óptima: Es aquella solución básica posible
que optimiza a la función objetivo.
ESTRUCTURA DE UN MODELO DE PL
1. FUNCION 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
2. VARIABLES DE
DECISION. 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.
3. 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, ect.
4. CONDICION TECNICA. Todas las variables deben tomar
valores positivos, o en algunos casos puede ser que algunas variables tomen
valores negativos
MODELO GENERAL
OPTIMIZAR Z = 
SUJETO
A: 
GRÁFICA DE DESIGUALDADES Y CONTORNOS
Para
graficar desigualdades realice los siguientes pasos
1.
Gráfica de
la igualdad. Convierta la desigualdad en igualdad y grafique l recta
2.
Escoja un
punto de ensayo
3.
Evalúe el
primer miembro de la expresión
4.
Determine
si el punto de ensayo satisface la desigualdad.
5.
Existen
varios métodos de solución entre los cuales tenemos el gráfico, el simplex, el
algebraico, el dual, etc.
EJEMPLO POR EL MÉTODO
GRÁFICO:
Una
compañía de auditores se especializa en preparar liquidaciones y auditorías de
empresas pequeñas. Tienen interés en saber cuantas auditorías y liquidaciones
pueden realizar mensualmente para maximizar sus ingresos. Se dispone de 800
horas de trabajo directo y 320 horas para revisión. Una auditoría en promedio
requiere de 40 horas de trabajo directo y 10 horas de revisión, además aporta
un ingreso de 300 dls. Una liquidación de impuesto requiere de 8 horas de
trabajo directo y de 5 horas de revisión, produce un ingreso de 100 dls. El
máximo de liquidaciones mensuales disponibles es de 60.
OBJETIVO
: Maximizar el ingreso total.
VARIABLE
DE DECISION: Cantidad de auditorías (X1).
Cantidad
de liquidaciones (X2).
RESTRICCIONES
: Tiempo disponible de trabajo directo
Tiempo
disponible de revisión
Número
máximo de liquidaciones.
Maximizar
Sujeto
a:
La
solución óptima siempre se encuentra en uno de los vértices del conjunto de
soluciones factibles. Se analizan estos valores en la función objetivo. El
vértice que representa el mejor valor de la función objetivo será la solución
óptima.
CONTADOR DE
COSTOS
Las funciones del contador de costos
siempre estarán dadas de acuerdo a las operaciones de la empresa y
las necesidades que tenga la administración de la misma con relación
al control de sus operaciones.
Primer plano
1. Diseñar
sistemas de control de costo
2. Planificar
la organización de las estructuras para implementación de costo
3. Mantener
actualizado el registro de los bienes de uso.
4. Controlar
y contabilizar los movimientos de los almacenes.
5. Dirigir la
toma de inventarios.
6. Proceder a
la liquidación de los jornales.
7. Registrar
la Producción.
8. Determinar
los costos de producción.
9. Orientar
la política de precios.
10. Controlar los resultados de la actividad fabril y
comercial.
11. Confeccionar estadísticas.
12. Preparar presupuestos.
Segundo plano (una vez organizada la empresa con nueva
estructura de costos)
1. Estructurar y mantener actualizado el plan de cuentas
de la contabilidad de costos.
2. Orientar los movimientos de ingresos y egresos de las
fichas de existencias de materia prima, artículos generales y productos
terminados.
3. Controlar mensualmente el relevamiento del inventario
de las existencias en proceso de fabricación.
4. Establecer las variaciones entre los costos reales y
los costos standard de las secciones fabriles e investigarlas, cooperando con
la supervisión para subsanar las anormalidades causantes de las respectivas
diferencias.
5. Efectuar reuniones con los jefes de fábrica para
analizar y discutir resultados.
6. Promover trabajos generales de organización y estudio
de sistemas que afecten a las áreas fabril, de servicio y comercial, hacerlos
publicar y vigilar su aplicación.
7. Asesorar a la dirección, gerencias, y jefes de planta
en cuestiones de costos relacionadas con ampliación o cierre de sectores de
fábrica, artículos nuevos, modificación de horarios de trabajo, instalación de
nueva maquinaria, cambios de métodos o especificaciones, niveles óptimos de
producción, etc.
8. Coordinar mensualmente el programa de las fechas de
entregas de todos los trabajos administrativos que afecten a su departamento,
para que el resultado de la operación se conozca antes del sexto día hábil del
mes siguiente al que se registra.
9. Determinar
precios orientativos de venta de los artículos producidos y mantener informada
a la gerencia comercial sobre cualquier variación actual o futura de costos,
que pueda repercutir en sus planes.
10. Asesorar a la misma gerencia en materia de política de
precios; alternativas de mezcla, volumen y condiciones de venta, etc.
11. Calcular el monto invertido en cada línea de producto
para poder relacionar las ganancias con el capital que las produce.
12. Vigilar la continua rotación de las existencias
ejerciendo controles sobre los artículos sin movimiento y exigiendo a los
responsables definición sobre su futuro destino.
13. Controlar y administrar el sistema de control
presupuestario.
14. Fomentar, dentro y fuera del sector a su cargo, un
espíritu afín con la atmósfera de costos, sea promoviendo reuniones con los
jefes de fábrica, inspirando entre el personal una capacitación más eficiente
y, en general, tratando de aprovechar todos los contactos con la supervisión
para inculcarles ideas de beneficio común.
15. Lograr su vinculación a asociaciones que profundicen
el estudio de las técnicas del costo de producción, analizar libros y
publicaciones, asistir a conferencias y ponerse al corriente de las mejores
prácticas modernas con miras a su posible aplicación en la empresa.
PROBLEMAS
DE PROGRAMACIÓN LINEAL METODO GRAFICO
Disponemos de 210.000 euros para invertir en bolsa.
Nos recomiendan dos tipos de acciones. Las del tipo A, que rinden el 10% y las
del tipo B, que rinden el 8%. Decidimos invertir un máximo de 130.000 euros en
las del tipo A y como mínimo 60.000 en las del
tipo B. Además queremos que la inversión en las del tipo A sea menor que el
doble de la inversión en B. ¿Cuál tiene que ser la distribución de la inversión
para obtener el máximo interés anual?
Solución
Es un problema de programación lineal.
Llamamos x a la cantidad que invertimos en
acciones de tipo A
Llamamos y a la cantidad que invertimos en
acciones de tipo B
|
inversión
|
rendimiento
|
Tipo A
|
x
|
0,1x
|
Tipo B
|
y
|
0,08y
|
210000
0,1x+0,08y
Condiciones que deben cumplirse (restricciones):
R1 
R2 
R3 
R4
Dibujamos las rectas auxiliares asociadas a las
restricciones para conseguir la región factible (conjunto de puntos que cumplen
esas condiciones)
r1
r2 (paralela a OY)
r3(paralela
a OX)
r4
x
|
y
|
|
x
|
y
|
|
x
|
y
|
|
x
|
y
|
0
|
210000
|
|
130000
|
0
|
|
0
|
60000
|
|
0
|
0
|
210000
|
0
|
|
|
|
|
|
|
|
130000
|
65000
|
La región factible es la pintada de amarillo, de
vértices A, B, C, D y E
A(0, 60000), B(120000, 60000), C(130000, 65000),
D(130000, 80000) y E(0, 210000)
La función objetivo es;
F(x, y)= 0,1x+0,08y
Si dibujamos la curva F(x, y) =0 (en rojo) y la
desplazamos se puede comprobar gráficamente que el vértice mas alejado es
el D, y por tanto es la solución óptima.
Comprobarlo analíticamente (es decir comprobar que el valor
máximo de la función objetivo, F, se alcanza en el vértice D)
2. En una pastelería se
hacen dos tipos de tartas: Vienesa y Real. Cada tarta Vienesa necesita un
cuarto de relleno por cada Kg. de bizcocho y produce un beneficio de 250 Pts,
mientras que una tarta Real necesita medio Kg. de relleno por cada Kg. de
bizcocho y produce 400 Ptas. de beneficio. En la pastelería se pueden hacer
diariamente hasta 150 Kg. de bizcocho y 50 Kg. de relleno, aunque por problemas
de maquinaria no pueden hacer mas de 125 tartas de cada tipo. ¿Cuántas tartas
Vienesas y cuantas Reales deben vender al día para que sea máximo el beneficio?
Solución
En primer
lugar hacemos una tabla para organizar los datos:
Tipo
|
Nº
|
Bizcocho
|
Relleno
|
Beneficio
|
T.
Vienesa
|
x
|
1.x
|
0,250x
|
250x
|
T. Real
|
y
|
1.y
|
0,500y
|
400y
|
|
|
150
|
50
|
|
Función objetivo (hay que obtener su máximo): f(x, y)=250x+ 400y
Sujeta a las siguientes condiciones (restricciones del problema):
Consideramos
las rectas auxiliares a las restricciones y dibujamos la región factible:
Para 0.25x+0.50y=50, ó x + 2y=200
Para x + y =150
La otras dos son paralelas a los ejes
Al eje OY x=125
Al eje Ox y =125
Y las otras restricciones (x e y mayor o igual a cero)
nos indican que las soluciones deben estar en el primer cuadrante
La región factible la hemos coloreado de amarillo:
Encontremos los vértices:
El O(0,0), el A(125, 0) y
el D(0, 100) se encuentran directamente (son las intersecciones
con los ejes coordenados)
Se observa que la restricción y
es redundante (es decir “sobra”)
Resolviendo el sistema:
, por reducción obtenemos y=50, x=100
Otro vértice es el punto C(100, 50)
Y el último vértice que nos falta se obtiene
resolviendo el sistema:
X+y=150
X=125
Cuya solución es: X=125, Y=25 B(125, 25)
Los vértices de la región son O(0,0), A(125,0),
B(125,25) y C(100,50) y D(0,100),
Si dibujamos el vector de dirección de la
función objetivo f(x, y)=250x+ 400y
Haciendo 250x+ 400y =0, y=-(250/400)x=-125x/200
Se ve gráficamente que la solución es el punto (100,
50), ya que es el vértice mas alejado (el último que nos encontramos al
desplazar la rectas 250x+400y=0 )
Lo comprobamos con el método analítico, es decir
usando el teorema que dice que si existe solución única debe hallarse en uno de
los vértices
La unción objetivo era: f(x, y)=250x+400y,
sustituyendo en los vértices obtenemos
f(125,0)=31.250
f(125,25)=31.250+10.000=41.250
f(100,50)=25.000+20.000=45.000
f(0,100)=40.000
El máximo beneficio es 45.000 y se obtiene en el punto
(100, 50)
Conclusión: se tienen que vender 100 tartas
vienesas y 50 tartas reales.
3. Una escuela prepara una excursión para 400 alumnos.
La empresa de transporte tiene 8 autocares de 40 plazas y 10 autocares de 50
plazas, pero solo dispone de 9 conductores. El alquiler de un autocar grande
cuesta 80 euros y el de uno pequeño, 60 euros. Calcular cuantos de cada tipo
hay que utilizar para que la excursión resulte lo mas económica posible para la
escuela.
Solución
Es un problema de programación lineal, en este caso lo
que queremos es hacer mínima la función objetivo.
Llamamos x al nº de autocares de 40 plazas e y
al nº de autocares de 50 plazas que alquila la escuela.
Entonces se tiene x 
, y
Como sólo hay 9 conductores se verifica que: x +y
Como tienen que caber 400 alumnos se debe de
verificar:
40x +50y 
, que simplificada quedaría 4 x +5y 
Por lo tanto las restricciones que nos van a
permitir calcular la región factible (conjunto de puntos solución donde
se cumplen todas las condiciones) son
La función objetivo es F(x, y)= 60x+ 80y
Dibujamos las rectas auxiliares,
r1
r2
r3
r4
x
|
y
|
|
x
|
y
|
x
|
y
|
x
|
y
|
8
|
0
|
0
|
10
|
0
|
9
|
0
|
8
|
|
|
|
|
0
|
9
|
10
|
0
|
Así como la de que corresponde a F(x, y)=0 que se
dibuja en rojo.
Teniendo en cuenta las restricciones ( la de R4
es la parte de arriba y que la R3 es la parte de abajo),
se encuentra la región factible. En el dibujo es la parte amarilla.
Los vértices son (0, 8), (0, 9) y el (5, 4),
este último es el punto de intersección de las rectas r3 y r4
restando ambas ecuaciones se tiene x =5 y
sustituyendo en la 1ª ecuación, y =4
Resolviendo gráficamente se llega a que el punto (5,
4) es la solución del problema. La solución óptima .
Comprobarlo sustituyendo en F(x, y) todos los vértices
y que este es el que da menor valor (método analítico).
4. Una compañía posee dos minas: la mina A produce
cada día 1 tonelada de hierro de alta calidad, 3 toneladas de calidad media y 5
de baja calidad. La mina B produce cada día 2 toneladas de cada una de las tres
calidades. La compañía necesita al menos 80 toneladas de mineral de alta
calidad, 160 toneladas de calidad media y 200 de baja calidad. Sabiendo que el
coste diario de la operación es de 2000 euros en cada mina ¿cuántos días debe
trabajar cada mina para que el coste sea mínimo?.
Solución
Organizamos los datos en una tabla:
|
días
|
Alta calidad
|
Calidad media
|
Baja calidad
|
Coste diario
|
Mina A
|
x
|
1x
|
3x
|
5x
|
2000x
|
Mina B
|
y
|
2y
|
2y
|
2y
|
2000y
|
|
|
80
|
160
|
200
|
|
La función objetivo C(x, y)=2000x + 2000y
Las restricciones
son:
La región factible la obtenemos dibujando las rectas
auxiliares: r1 
x + 2y=80, r2 3x + 2y= 160 y r35x + 2y=200 en el primer cuadrante y
considerando la región no acotada que determina el sistema de restricciones:
Los vértices son los puntos A(0, 100), B(20, 50),
C(40, 20), D(80, 0), que se encuentran al resolver el sistema que determinan
dos a dos las rectas auxiliares y (y que estén dentro de la región factible).
r1 
r2 
que nos da el punto (40, 20)
(comprobarlo)
r2 r3 
que nos da el punto (20, 50)
r1 r3 no hace falta calcularlo
pues queda fuera de la región factible.
En la gráfica se aprecia que el primer punto que se
alcanza al desplazar la recta C(x, y)=0 es el (40, 20). Luego la solución es
trabajar 40 días en la mina A y 20 en la B. (método gráfico)
Lo comprobamos aplicando el método analítico:
C(0, 100)=2000.100=200000
C(20, 50)=2000.20+2000.50=40000 + 100000= 140000
C(40, 20)= 2000. 40+2000.20=80000 + 40000=
120000 coste mínimo
C(80, 0)= 2000.80 =160000
5. Se va a organizar una planta de un taller de
automóviles donde van a trabajar electricistas y mecánicos. Por necesidades de
mercado, es necesario que haya mayor o igual número de mecánicos que de
electricistas y que el número de mecánicos no supere al doble que el de
electricistas. En total hay disponibles 30 electricistas y 20 mecánicos. El
beneficio de la empresa por jornada es de 250 euros por electricista y 200
euros por mecánico. ¿Cuántos trabajadores de cada clase deben elegirse para
obtener el máximo beneficio y cual es este?
Sea x = nº electricistas
y = nº mecánicos
La función objetivo
f (x, y)=250x+ 200y , las restricciones 
La región factible sería para estas restricciones:
Se aprecia gráficamente (línea en rojo) que la
solución óptima está en el punto (20, 20).
Por tanto:
20 electricistas y 20 mecánicos dan el máximo
beneficio, y este es 9000 euros, ya que f(x, y) =250.20+200.20=9000
6. Para recorrer un determinado trayecto, una compañía aérea desea ofertar,
a lo sumo, 5000 plazas de dos tipos: T(turista) y P(primera). La ganancia
correspondiente a cada plaza de tipo T es de 30 euros, mientras que la ganancia
del tipo P es de 40 euros.
El número de plazas tipo T no puede exceder de 4500 y
el del tipo P, debe ser, como máximo, la tercera parte de las del tipo T que se
oferten.
Calcular cuántas tienen que ofertarse de cada
clase para que las ganancias sean máximas.
Solución
Sea x el nº que se ofertan de tipo T, y el nº que se
ofertan de tipo P.
|
nº
|
Ganancia
|
Turista
|
x
|
30x
|
Primera
|
y
|
40y
|
Total
|
5000
|
30x +40y
|
La función objetivo es:
f(x, y)=30x +40y
Las restricciones:
La región factible:
Los vértices, A(0, 5000), B(3750, 1250), C(4500, 500)
y D(4500, 0) (comprueba el punto B resolviendo el sistema correspondiente)
El método gráfico nos da que el punto solución es el B
(3750, 1250)
Comprueba los resultados usando el método analítico
(sustituyendo los puntos vértices en f y viendo q el máximo valor se obtiene en
B)
EJEMPLO
1:
Una
compañía de auditores se especializa en preparar liquidaciones y auditorías de
empresas pequeñas. Tienen interés en saber cuantas auditorías y liquidaciones
pueden realizar mensualmente para maximizar sus ingresos. Se dispone de 800
horas de trabajo directo y 320 horas para revisión. Una auditoría en promedio
requiere de 40 horas de trabajo directo y 10 horas de revisión, además aporta
un ingreso de 300 dls. Una liquidación de impuesto requiere de 8 horas de
trabajo directo y de 5 horas de revisión, produce un ingreso de 100 dls. El
máximo de liquidaciones mensuales disponibles es de 60.
OBJETIVO
: Maximizar el ingreso total.
VARIABLE
DE DECISION: Cantidad de auditorías (X1).
Cantidad
de liquidaciones (X2).
RESTRICCIONES
: Tiempo disponible de trabajo directo
Tiempo
disponible de revisión
Número
máximo de liquidaciones.
Maximizar
Sujeto
a:
La
solución óptima siempre se encuentra en uno de los vértices del conjunto de
soluciones factibles. Se analizan estos valores en la función objetivo. El
vértice que representa el mejor valor de la función objetivo será la solución
óptima.
EJEMPLO
2.
Un
departamento de publicidad tiene que planear para el próximo mes una estrategia
de publicidad para el lanzamiento de una línea de T.V. a color tiene a
consideración 2 medios de difusión: La televisión y el periódico.
Los
estudios de mercado han mostrado que:
1.
La publicidad por T.V. Llega al 2 % de las familias de ingresos altos y al 3 %
de las familias de ingresos medios por comercial.
2.
La publicidad en el periódico llega al 3 % de las familias de ingresos altos y
al 6 % de las familias de ingresos medios por anuncio.
La
publicidad en periódico tiene un costo de 500 dls. por anuncio y la publicidad
por T.V. tiene un costo de 2000 dls. por comercial. La meta es obtener al menos
una presentación como mínimo al 36 % de las familias de ingresos altos y al 60
% de las familias de ingresos medios minimizando los costos de publicidad.
OBJETIVO
: Minimizar los costos de publicidad.
VARIABLE
DE DECISION: Anuncios para las familias de ingreso alto (X1).
Anuncios
para las familias de ingreso medio (X2).
RESTRICCIONES
: Porcentaje de presentación.
Minimizar
Sujeto
a:
SOLUCION
OPTIMA:
EJEMPLO
3.
Un
expendio de carnes acostumbra preparar carne para hamburguesa con una
combinación de carne molida de res y carne molida de cerdo. La carne de res
contiene 80 % de carne y 20 % de grasa y le cuesta a la tienda 80 centavos por
libra. La carne de cerdo contiene 68 % de carne y 32 % de grasa y cuesta 60
centavos por libra. ¿Qué cantidad de cada tipo de carne debe emplear la tienda
por cada libra de carne para hamburguesa si desea minimizar el costo y mantener
el contenido de grasa no mayor de 25 %?
Minimizar
Sujeto
a:
SOLUCION
OPTIMA:
NOTA: Una desigualdad define un medio plano y una igualdad
define una línea.
Holgura Es todo recurso no utilizado, o capacidad no utilizada producto de
una restricción de tipo ≤
Excedente Es todo exceso o supera a un producto de una
restricción de tipo ≥
Cuando una de las variables de holgura o excedente
tiene un valor mayor a cero (0.0) indica que la restricción a la cual está
asociada es una restricción inactiva. Y cuando ese valor de la variable de
holgura o excedente es cero (0.0), es porque la restricción a la cual están
asociadas es una restricción activa. Dicho en otra forma, Una restricción será
Activa, si al sustituir los valores de las variables
de la solución óptima en dicha restricción, el valor resultante en su miembro
izquierdo es igual al valor del miembro
derecho (RHS). Un caso especial es el de la restricción de igualdad, donde este
tipo de
restricción siempre es activa. Si una restricción no
es activa, se dice que es inactiva. Esto es cuando al sustituir los valores de
las variables de la solución óptima en la restricción en cuestión, el valor
resultante del lado izquierdo (de la restricción) no coincide con el valor del
lado derecho de la restricción.
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:
a) 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. ( Ver tabla de TUCKER)
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.
Tabla de TUCKER
MAXIMIZACION
RESTRICCIONES
≤
≥
=
VARIABLES
≥
≤
> <
MINIMIZACIÓN
VARIABLES
≥
≥
> <
RESTRICCIONES
≥
≤
=
Los problemas duales
simétricos son los que se obtienen de un problema primal en forma canónica y
‘normalizada’, es decir, cuando llevan asociadas desigualdades de la forma
mayor o igual en los problemas de minimización, y desigualdades menores o igual
para los problemas de maximización.
CONCLUSIÓN
1.- Si una restricción del primal es no saturada,
entonces la variable de dual asociada debe ser nula.
2.- 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.
EL
MÉTODO SIMPLEX
El Método
Simplex es un procedimiento de cálculo algebráico, iterativo, para resolver
Modelos Lineales de cualquier tamaño. El
algoritmo Simplex requiere que el Modelo Lineal, para ser solucionado, cumpla
las condiciones de Forma Estándar y Sistema Canónico.
La Forma Estándar incluye:
a) una Función Objetivo a optimizar
b) lado derecho de las restricciones con valor
positivo
c) variables de decisión no negativas
d) las restricciones deben ser expresadas como
igualdades.
Para transformar las restricciones en igualdades se
deben incorporar las llamadas variables de holgura. Una variable de holgura tiene coeficiente
cero en la Función Objetivo. Se suman en restricciones del Tipo ≤ y se restan
en restricciones del Tipo ≥
En términos matemáticos, expresan la diferencia entre
el lado izquierdo y el lado derecho de las restricciones. Al igual que las
variables de decisión deben ser mayores o iguales a cero.
En términos del modelo representan la cantidad de
recurso no utilizado con relación a un máximo disponible (Parte ociosa de los
recursos). Cuando la restricción es de
una condición o requerimiento, representan la cantidad de esa condición o requerimiento
que se obtiene por encima de un mínimo o que se deja de tener con relación a un
máximo.
El
Sistema Canónico en un Modelo Lineal significa que debe existir una
variable básica en cada restricción. Esto permite obtener una primera solución
posible que satisface todas las restricciones.
Una variable básica tiene coeficiente 1 positivo en
una restricción y no existe en las demás.
Las variables de decisión (estructurales) del modelo y
las variables de holgura pueden ser
variables básicas. Cuando ninguna de ellas cumple con
la condición de ser básica, se incorpora una variable como artificio
matemático, para cumplir con el sistema canónico y a esa variable se le llama
variable artificial. Una variable artificial debe tener incorporado un
coeficiente muy alto en la Función Objetivo, con signo negativo en maximización
y con signo positivo en minimización. Con esto se logra que el procedimiento
Simplex las elimine de la solución en las primeras iteraciones. Estas variables
deben valer cero en la solución óptima del modelo.
Una Tabla
Simplex es un resumen detallado de toda la información del modelo para trabajar
más fácilmente con él. La siguiente tabla expresa cómo deben ser recogidos los
datos para resolver el problema de programación líneal por el Método Simplex.
