Introducción a la programación lineal y las etapas del

      
modelamiento

Antes de iniciar con la introducción a la Programación Lineal PL) y el estudio

de las etapas del moldeamiento es importante tener un conocimiento previo
sobre los orígenes de la programación lineal. Hiller y Liberman (Hiller y
Liberman 2001), explican los orígenes de la investigación de operaciones de
la siguiente manera:

     
La programación lineal proviene de la investigación de operaciones la
cual tuvo su origen a partir de actividades bélicas y guerras. Durante
la segunda guerra mundial se hicieron investigaciones sobre
operaciones militares que mejorarían la asignación de recursos y la
precisión en las operaciones, esto implicaba una adecuada
planificación de bombardeos y ataques militares.

Para este entonces científicos de todo el mundo investigaban la

manera de que estas operaciones fueran óptimas con el fin de
derribar al enemigo e incurrir en mínimas perdidas y mínimos costos
de operación.

Fue entonces cuando el matemático Francés George Dantzig en 1947

   
desarrolló el Método Símplex para la solución de problemas de
Programación lineal y esto condujo al tratamiento de problemas no
solo militares sino de toda extensión y diversas áreas del
conocimiento.

A partir de este momento, y con el proveniente avance de los

sistemas computarizados las organizaciones usaron estos métodos
matemáticos desarrollados para la asignación óptima de recursos, y
luego los entes de planificación y desarrollo los usaron para la toma
de decisiones. De esta manera se fue expandiendo las metodologías
de programación lineal en diversas áreas y ahora es una de las áreas
de mayor aplicabilidad en todos los medios. (Hiller y Liberman, 2001,
p.13-62).
     

     
  Fuentes de estudio
  Para una mayor profundidad en la historia y aplicabilidad de  
la técnica de programación lineal ir a Introducción a la PL
(descargar)
     

Modelamiento matemático

La técnica de programación lineal parte del concepto de modelamiento

matemático el cual consiste en representar el sistema o el fenómeno del
mundo real o el problema a resolver por medio de un lenguaje matemático.
Existen 6 etapas fundamentales en el modelamiento las cuales se definen
como:

1. Definición del problema y recolección de la información.

2. Formulación de un modelo matemático.
3. Obtención de la solución a partir de un modelo.
4. Prueba del modelo.
5. Preparación para la aplicación del modelo.
6. Implantación.

     
  Fuentes de estudio
La explicación de cada una de las 6 etapas se define en:
  Introducción a la PL (descargar)

Ver ejemplo 1 (abrir documento)

El problema de la asignación de recursos      

Uno de los problemas clásicos de la programación lineal y que sirve como

ejemplo para identificar muchas de las estructuras que se modelan con esta
técnica es el  “El problema de la asignación de recursos”. El objetivo de esa
formulación es asignar recursos (limitados) entre actividades competitivas
de la mejor manera posible (óptima).       

Para ver un ejemplo del Problema de la asignación de recursos (abrir

documento) allí mismo se encontrara la manera de definir los modelos de
programación lineal de forma estándar, canónica y matricial.

Suposiciones de los modelos de PL

      

Los modelos de programación lineal poseen ciertos supuestos que deben de

respetarse para que cumplan con las condiciones algebraicas, matemáticas 
y de modelamiento, estos son:

1. El supuesto de proporcionalidad
2. El supuesto de aditividad
3. El supuesto de divisibilidad
4. El supuesto de Certidumbre

Cada uno de estos supuestos son explicados e ilustrados en Supuestos y

Modelos (abrir documento).

Modelos de Pl para problemas varios      

A continuación se recomienda al estudiante estudiar varios de los modelos
conocidos de programación lineal, entre ellos están:
Modelos de transporte de carga
Modelos de Dieta
Modelos de Inventarios
Modelos Financieros
Ir a Supuestos y Modelos para estudiar estos modelos (abrir documento).

    
  Fuentes de estudio
Otros enlaces de interés. En los siguientes enlaces encuentras material
textual y audiovisual con el cual debes profundizar sobre los temas
expuestos arriba. Se sugiere tomar nota o desarrollar fichas de lectura
de los temas y aprendizajes adquiridos con la utilización de dichos
insumos:

Base de Datos Elibro.

Guerrero, S. H. (2009). Programación lineal aplicada.Bogotá, CO: Ecoe

Ediciones.Retrieved from http://www.ebrary.com
http://site.ebrary.com/lib/univucnsp/reader.action?
ppg=33&docID=10758304&tm=1502933406419

Guerrero, S. H. (2009). Programación lineal aplicada.Bogotá, CO: Ecoe

Ediciones.Retrieved from http://www.ebrary.com
http://site.ebrary.com/lib/univucnsp/reader.action?
  ppg=291&docID=10758304&tm=1502933485868

Asignación:
https://youtu.be/1i3grIq-U3c

Transporte:
https://youtu.be/JoZXbo1cx0c

Modelo Concesionario Renault:

https://youtu.be/xhIMjKt0ZHU

Producción:
https://youtu.be/aTzkURKZvVc

Otros enlaces
http://www.purplemath.com/modules/linprog.htm
http://mathworld.wolfram.com/LinearProgramming.html
http://www.sce.carleton.ca/faculty/chinneck/po/Chapter2.pdf

Una vez finalizada la exploración y el estudio de los insumos propuestos, la

invitación es a desarrollar la siguiente actividad con la cual podrá afianzar
las competencias adquiridas a lo largo de esta unidad

Solución Grafica de un modelo de PL      

Debido a que es posible acceder a otro método de resolución el cual es
llamado comúnmente “Solución Gráfica”, comenzaremos esta unidad con su
estudio. Este es aplicado solo y únicamente cuando el problema tiene 2
variables de decisión y por lo tanto está en 2 dimensiones y puede dibujarse
en el plano. El método de solución gráfica puede desarrollarse en dos
pasos:

Paso 1
En primer lugar, se debe obtener la región de puntos factibles en el plano,
obtenida por medio de la intersección de todos los semi-espacios que
determinan cada una de las inecuaciones presentes en las restricciones del
problema.

Paso 2:
Enseguida, con el desplazamiento de las curvas de nivel de la función
objetivo (rectas de isoutilidad o contornos objetivos) en la dirección de
crecimiento de la función se obtiene la solución óptima del problema en la
intersección con la ultima zona de la región factible.

La dirección de crecimiento  corresponde a la dirección del vector gradiente

de la función. (∇z(1,x2) = (C1,C2)T) )
en la búsqueda de una solución óptima por medio de los pasos anteriores
también pueden ocurrir otras situaciones :

1) Que la solución óptima exista pero que haya más de una. Es decir que
las rectas de isoutilidad corten a una de las restricciones de la región
factible.

2) Que el problema no tenga solución, dada una región de puntos factibles

no - acotada.

3) Que  el problema no tenga solución, porque no existen puntos factibles.

Para ver un ejemplo de cada uno de los pasos citados anteriormente se
recomienda seguir la presentación Solución Gráfica de un PL (abrir
documento)

ntroducción al método Simplex      

El algoritmo SIMPLEX es un método iterativo que sigue los siguientes pasos:

1. Halla una solución inicial o una solución factible en un vértice (FEV)

2. Realiza una prueba de optimalidad: es decir, chequea las soluciones FEV

adyacentes a la solución actual.

3. Desarrolla Iteraciones: Se mueve hacia otras soluciones FEV

El método iterativo busca la solución óptima de un problema de
programación lineal y la  encuentra cuando ninguna de las soluciones FEV
adyacentes a la solución evaluada produce un mejor valor de la función
objetivo.

EL método simplex debe cumplir con cuatro teoremas fundamentales:

1. La solución óptima (si existe) se encuentra en un vértice de la Región

Factible.

2. Si una solución en un vértice, no tiene soluciones adyacentes mejores,

esa es la solución óptima (óptimo local es global).

3. Una solución básica (en un vértice aumentada) es la resultante de hacer

(n-m) variables iguales a cero y resolver el sistema de ecuaciones para las
m variables restantes.

4. Soluciones adyacentes tienen iguales todas las variables básicas menos

una (y por supuesto las no básicas).

Para ver un ejemplo inicial que ilustra la lógica del procedimiento simplex
por favor ir a: (Introducción al método Simplex)

El método simplex, procedimiento algebraico      

Definiciones claves para el procedimiento algebraico

Forma aumentada de un PL

El método simplex es un procedimiento algebraico donde las soluciones se

obtienen al resolver un sistema de ecuaciones lineales conformado a partir
de las restricciones funcionales. El sistema de ecuaciones lineales se obtiene
al convertir cada desigualdad (si el problema ha sido estructurado de esta
manera) de la forma original, en una igualdad equivalente.

Para esto es necesario usar variables de holgura, las cuales son variables,
no negativas, que se adicionan al lado izquierdo de una restricción funcional
de desigualdad del tipo ≤, para convertirla en una igualdad equivalente.

De esta manera los problemas de programación lineal pueden ser llevados

de su forma original a su forma aumentada, o en equivalencia de la forma
canónica  a la forma estándar. Para ver un ejemplo de transformación
algebraica por favor ir a (Introducción al método Simplex  -Procedimiento
algebraico del Simplex).

Variables Básicas y no Básicas

Ahora es necesario hacer una definición, o una clasificación importante de

las variables que se tienen en un problema de PL.
Para empezar es necesario aclarar que cada variable (de decisión o de
holgura) puede clasificarse en básica o no básica.

En un sistema con n variables y m restricciones, donde n > m, habrá: m:

variables básicas n - m: variables no básicas que son aquellas que se
igualan a cero por definición.

Las variables básicas obtienen su valor al solucionar el sistema de m

ecuaciones y si los valores de las variables básicas satisfacen la condición
de no negatividad se les denomina soluciones básicas factibles. Un ejemplo
de variables básicas y no básicas se ilustra en el siguiente link (Introducción
al método Simplex  -Procedimiento algebraico del Simplex).

El procedimiento algebraico del método simplex

El procedimiento algebraico del simplex consiste en desarrollar los

siguientes aspectos:

o Hallar una solución inicial.

o Hacer una Prueba de optimalidad.
o Realizar nueva iteración
o Determinación de la dirección de movimiento: Variable que
entra a la base: columna pivote
o Determinación de donde detenerse: Variable que sale de la
base: fila pivote

o Calcular una nueva solución básica factible

o Obtener 1 en la fila pivote
o Obtener 0 en el resto de la columna pivote

Para observar varios ejemplos del procedimiento algebraico por favor ir a

(Introducción al método Simplex  -Procedimiento algebraico del Simplex).

Teniendo claro como es la resolución de problemas de maximización por

medio del algoritmo simplex, la pregunta que surge es como resolver
problemas de minimización:
Se tienen dos métodos:

1.       Multiplicar la F.O del problema de minimización por -1 y resuelva el

problema como si fuera un problema de maximización. (-Z) = -
(CX1+CX2…)
2.       Seleccionar la variable con el coeficiente más positivo en el renglón 0
para que entre a la base.
Ver ejemplo en (Introducción al método Simplex  -Procedimiento algebraico
del Simplex).

Casos especiales del Simplex

Similarmente que con el método de solución gráfica el procedimiento

algebraico del simplex puede identificar cuando se tienen condiciones
especiales en los problemas de programación lineal. Estos son:
 o Empate de la variable que entra
o Empate de la variable que sale
o Cuando no hay variable básica que sale
o Soluciones óptimas alterna

Los ejemplos ilustrados de cada uno se encuentran en (Introducción al

método Simplex  -Procedimiento algebraico del Simplex).

El método simplex de las dos fases      

El simplex de dos fases se usa cuando una solución básica no está
fácilmente disponible. En pocas palabras cuando todas las restricciones no
son de tipo <= y no puede establecerse una base a partir de las variables
de holgura, es decir cuando se tienen al menos una restricción de tipo = ó
>=.

Para resolver esta situación se deben seguir los siguientes pasos:

1. Modifique las restricciones de tal manera que el segundo miembro o lado

derecho de cada una sea no negativo. (-1) (recordar que cambia la
desigualdad).

2. Identifique cada restricción que ahora es una restricción = ó >=.

3. Convierta las restricciones de desigualdad a forma estándar agregando

variables de holgura (Si) o una variable excedente (ei).

4. Sume variables artificiales ai a las restricciones >= ó =.  También

adicione la restricción de signo ai >=0.

5. Resuelva un PL cuya función objetivo es min W´ = suma de todas las

variables artificiales (PL de la fase 1). Este Pl forzara a las variables
artificiales a ser cero.

Siguiendo los pasos anteriores pueden tenerse dos casos:

 Caso 1. No hay solución:

El valor óptimo de W´ es mayor que cero en este caso el PL original

no tiene solución factible.

 Caso 2. Solución Óptima del Pl Original

El valor óptimo de w´ es igual a cero y ninguna variable artificial está

en la base optima dela fase I. Se suprimen las columnas del arreglo
óptimo de la Fase I que corresponden a las variables artificiales. Se
combina la función objetivo original  y las restricciones que quedaron
de la fase I. La solución óptima para el PL de la fase II es la solución
óptima del PL Original.
Para ver un ejemplo del método simplex de las dos fases por favor ir
 a (Introducción al método Simplex  -Procedimiento algebraico del
Simplex – Simplex de dos fases).

    
  Fuentes de estudio
Base de Datos Elibro.
Guerrero, S. H. (2009). Programación lineal aplicada.Bogotá, CO: Ecoe
Ediciones.Retrieved from http://www.ebrary.com
http://site.ebrary.com/lib/univucnsp/reader.action?
ppg=139&docID=10758304&tm=1502933605202

Métodos especiales:
http://site.ebrary.com/lib/univucnsp/reader.action?
ppg=183&docID=10758304&tm=1502933688653

Maximización:
https://youtu.be/__oYwGhVkS8
   
Minimización:
https://youtu.be/qwbJTUjxN34

Otros enlaces de interés. En los siguientes enlaces encuentra material

textual y audiovisual con el cual debe profundizar sobre los temas
expuestos arriba. Se sugiere tomar nota o desarrollar fichas de lectura
de los temas y aprendizajes adquiridos con la utilización de dichos
insumos:

http://www.zweigmedia.com/RealWorld/tutorialsf4/framesSimplex.ht
ml
http://www.phpsimplex.com/teoria_metodo_simplex.htm
http://www.ganimides.ucm.cl/haraya/doc/m_simplex.pdf
    
 

    
   Videos  

Tomado de: https://www.youtube.com/watch?v=VMKfptt43QU

Tomado de: https://www.youtube.com/watch?v=M4K6HYLHREQ

Tomado de: https://www.youtube.com/watch?v=qxls3cYg8to

 Tomado de: https://www.youtube.com/watch?v=jcdiroeksHE

Tomado de: https://www.youtube.com/watch?v=I7brzjFhYEU

    
Una vez finalizada la exploración y el estudio de los insumos propuestos, la
invitación es a desarrollar la siguiente actividad con la cual podrá afianzar
las competencias adquiridas a lo largo de esta unidad.

     

 
   Fuentes de estudio
Base de Datos Elibro.
Guerrero, S. H. (2009). Programación lineal aplicada.Bogotá, CO: Ecoe
Ediciones.Retrieved from http://www.ebrary.com
http://site.ebrary.com/lib/univucnsp/reader.action?
ppg=139&docID=10758304&tm=1502933605202
 Métodos especiales:
http://site.ebrary.com/lib/univucnsp/reader.action?
ppg=183&docID=10758304&tm=1502933688653

Maximización:
https://youtu.be/__oYwGhVkS8

Minimización:
https://youtu.be/qwbJTUjxN34

Otros enlaces de interés. En los siguientes enlaces encuentra material

textual y audiovisual con el cual debe profundizar sobre los temas
expuestos arriba. Se sugiere tomar nota o desarrollar fichas de lectura
de los temas y aprendizajes adquiridos con la utilización de dichos
insumos:

http://www.zweigmedia.com/RealWorld/tutorialsf4/framesSimplex.ht
ml
http://www.phpsimplex.com/teoria_metodo_simplex.htm
http://www.ganimides.ucm.cl/haraya/doc/m_simplex.pdf

Análisis de sensibilidad      

El análisis de sensibilidad consiste en Investigar el efecto que tendría sobre

la solución óptima y sobre la función objetivo un cambio marginal en uno de
los parámetros. Es decir que ocurre con el planteamiento y la solución
obtenida para un problema determinado si se modifica uno a la vez algunos
de los parámetros del modelo.

Para hacerlo sería necesario resolver de nuevo el problema  con los cambios
implementados, y comparar con la antigua formulación esperando a que
ocurra algún cambio, pero esta situación evidentemente seria tediosa y muy
larga. Por tal motivo existen técnicas de análisis de sensibilidad que ayudan
a diseñar un plan previo rango en que pueden variar los parámetros).

La técnica de sensibilidad que se estudiara en esta unidad corresponde al

uso del tablero simplex revisado, este tablero otorga la posibilidad de
identificar nuevas soluciones a partir de las condiciones iniciales del
problema y el tablero simplex.

El tablero simplex revisado

     
   

     

Este tablero permite hallar el tablero simplex final de un problema de

programación lineal formulado, y de esta manera poder hacer análisis de
sensibilidad cambiando los parámetros teniendo:

Cb = coeficiente de las variables básicas

B = Matriz base, conformada por las columnas  originales (del
planteamiento original) de las variables básicas actuales.
B-1 = Inversa de B
A = Matriz de coeficientes tecnológicos originales. (matriz de coeficientes de
las restricciones originales)
C = Coeficientes de costo (coeficientes de la función objetivo)
b = Coeficientes del lado derecho de las restricciones.

Para más información sobre el tablero simplex revisado ver análisis de

Sensibilidad 1 (abrir documento).

Casos del análisis de sensibilidad

El análisis de sensibilidad puede efectuarse a partir de Cambios marginales

en cada uno de los parámetros:

1.  bi : recursos o requerimientos

2.  cj : coeficientes de costos de una variable no básica.
3.  cj : coeficientes de costos de una variable básica.

Cambios en los coeficientes del lado derecho (bi) (recursos o

requerimientos)

En esta ocasión se Investiga el efecto que tendría sobre la solución óptima y

sobre la Función Objetivo un cambio marginal (aumento o disminución) en
la disponibilidad de recursos  en cada una de las restricciones, es decir en el
parámetro del lado derecho de la restricciones.

En el tablero simplex revisado se observa que los únicos argumentos que

son afectados son los que corresponden a la función objetivo y al valor de
las variables básicas, estos se ilustran a continuación,:

     
   

     

Para hacer el análisis de sensibilidad es necesario recordar que el problema

es factible si Xi ≥ 0, si esta condición se incumple se está poniendo en
riesgo la factibilidad de la solución, por lo tanto.

B-1b >= 0
Remplazando los valores respectivos de las letras puede hallarse el intervalo
de variación permitido para b para que la solución permanezca factible.
Asimismo y remplazando en CB*B-1*b puede hallarse el precio sombra el
cual Mide la contribución económica de una unidad adicional del  recurso, a
la medida del desempeño Z.

Para ver tres ejemplos de análisis de sensibilidad cambiando los bi por favor
ver análisis de Sensibilidad 1 (abrir documento).

Precio Sombra

El coeficiente de la variable de holgura en la solución óptima (renglón 0) es

el Precio Sombra, Precio Dual o Valor Marginal del recurso i Este Mide la
contribución económica de una unidad adicional del  recurso, a la medida
del desempeño Z. Es la tasa en la que varía Z, al variar (una unidad) la
cantidad que se proporciona del recurso bi.

Cambios en los coeficientes de costos      

Básicamente para este análisis de sensibilidad lo que se busca es identificar

cómo se afectan la función objetivo y la solución óptima, cuando cambia
uno de los coeficientes de costos en la función objetivo.
Los cambios en los coeficientes de costos cj requieren un análisis según
sean:

o Variables básicas: incluidas en la solución óptima.

o Variables no básicas: excluidas de la solución óptima.

Cambios en los coeficientes de costos (ci) de una variable no básica

(NVB)
 Si se observa, En la tabla óptima del Simplex Revisado el único elemento
que cambia, dado un cambio en un coeficiente de costos de una V.N.B es el
c como se ilustra abajo:

     

   

     

Cuando se varía sólo un parámetro cj al tiempo, es posible encontrar un

intervalo de valores permitidos para que la solución permanezca óptima.
(abrir documento).

Para ver un ejemplo de un análisis de sensibilidad de cambios en un

coeficiente de costos de una  variable no básica  ver análisis de Sensibilidad
2 (abrir documento).

El Costo Reducido
El costo reducido denotado como zj – cj,  es el valor máximo en el cual
debe aumentarse la utilidad de la actividad j para que se vuelva atractiva, o
lo que es lo mismo, el valor mínimo en el que debe reducirse su costo para
ser atractiva.

Cambios en los coeficientes de costos (ci) de una variable básica

(VB)
En la tabla óptima del Simplex Revisado se observa que CAMBIAN LOS
ELEMENTOS que tienen a cB:

     

   

     

Por lo tanto cambia todo el renglón (0): Evaluadores y F.O. Por tal motivo
se requiere que:

o Los evaluadores sean mayores que 0.

o Garantizar que los evaluadores sean iguales a cero, para las variables
básicas.
 o La Función Objetivo (cBB-1b)  cambia pero puede tomar puede tomar
cualquier valor.

Se debe entonces sacar el intervalo que permite que la solución siga siendo
factible y optima y ver también el cambio en la función objetivo.
Para ver un ejemplo de este tratamiento ir a ( análisis de Sensibilidad
1 – análisis de sensibilidad 2).

El problema Dual
Asociado a todo problema de P.L, existe otro problema de P.L llamado el
Problema Dual. Por lo tanto, al problema original se le llama Primal o
Primario. La solución del dual corresponde a los precios sombra de las
restricciones (recursos o requerimientos) del primal.
La formulación del problema dual a partir del primal es como sigue:

     

   

     

La relación entre el problema primal y dual se define de la siguiente

manera: La restricción de uno de los problemas está asociada a la variable
del otro.  Y los coeficientes de un problema están asociados a los a los lados
derechos del otro.

Para ver un ejemplo concreto de problema dual ir a:

Base de Datos Elibro.

Guerrero, S. H. (2009). Programación lineal aplicada.Bogotá, CO: Ecoe
Ediciones.Retrieved from http://www.ebrary.com
http://site.ebrary.com/lib/univucnsp/reader.action?
ppg=217&docID=10758304&tm=1502933204481

Modelo Dual:
https://youtu.be/alP6E6xeENY

Algunas de las propiedades del problema dual son:

o Propiedad de dualidad débil

o Propiedad de dualidad fuerte
o Propiedad de soluciones complementarias
 o Propiedad de simetría

Para ver al definición de las propiedades ir a:

Modelo Dual:
https://youtu.be/uDdCimQSUTw

Relaciones entre los problemas primal y dual

Las relaciones entre los problemas primal y dual pueden definirse como:
1. Si un problema tiene soluciones factibles y función objetivo acotada,
entonces el otro también y los valores de la función objetivo en el Óptimo
son iguales.
2. Si uno de los problemas tiene soluciones factibles y función objetivo no
acotada, entonces el otro no tiene solución factible.
3. Si un problema no tiene soluciones factibles, entonces el otro no tiene
soluciones factibles o su función objetivo es no acotada.

Adaptación a otras formas del primal

Para adaptar a otras formas del primal se usa la tabla siguiente, ella
permite cambiar las condiciones del problema primal al dual y viceversa.
     

   

     

Para ver ejemplos del uso de la tabla por favor ir a:

Base de Datos Elibro.

Guerrero, S. H. (2009). Programación lineal aplicada.Bogotá, CO: Ecoe
Ediciones. Retrieved from http://www.ebrary.com
http://site.ebrary.com/lib/univucnsp/reader.action?
ppg=267&docID=10758304&tm=1502933108374"
Análisis de Sensibilidad:
https://youtu.be/BbUyRoYDk34

    
  Fuentes de estudio
Análisis de Sensibilidad:
https://youtu.be/qwbJTUjxN34

Otros enlaces de interés. En los siguientes enlaces encuentras

material textual y audiovisual con el cual debes profundizar sobre
  los temas expuestos arriba. Se sugiere tomar nota o desarrollar  
fichas de lectura de los temas y aprendizajes adquiridos con la
utilización de dichos insumos:

http://www.programacionlineal.net/sensibilidad.html
http://www.investigaciondeoperaciones.net/analisis_de_sensibilid
ad.html
http://www.angelfire.com/ak6/invo_escom2/clase3.pdf
    

    
  Fuentes de estudio

Tomado de: https://www.youtube.com/watch?v=v68wFcVl4Cs

Tomado de: https://www.youtube.com/watch?v=y_j1Mdv-XYw

Tomado de: https://www.youtube.com/watch?v=WiEGu06qtiw

   
Tomado de: http://youtu.be/DNq_RvQZQuc

Tomado de: http://youtu.be/E4QAk49aTAQ

Tomado de: http://youtu.be/jSAc4-H80NY

    

Una vez finalizada la exploración y el estudio de los insumos propuestos, la

invitación es a desarrollar la siguiente actividad con la cual podrá afianzar
las competencias adquiridas a lo largo de esta unidad y, en general, del
módulo Programación Lineal.

Solución Grafica de un modelo de PL      

Debido a que es posible acceder a otro método de resolución el cual es

llamado comúnmente “Solución Gráfica”, comenzaremos esta unidad con su
estudio. Este es aplicado solo y únicamente cuando el problema tiene 2
variables de decisión y por lo tanto está en 2 dimensiones y puede dibujarse
en el plano. El método de solución gráfica puede desarrollarse en dos
pasos:

Paso 1
En primer lugar, se debe obtener la región de puntos factibles en el plano,
obtenida por medio de la intersección de todos los semi-espacios que
determinan cada una de las inecuaciones presentes en las restricciones del
problema.

Paso 2:
Enseguida, con el desplazamiento de las curvas de nivel de la función
objetivo (rectas de isoutilidad o contornos objetivos) en la dirección de
crecimiento de la función se obtiene la solución óptima del problema en la
intersección con la ultima zona de la región factible.

La dirección de crecimiento  corresponde a la dirección del vector gradiente

de la función. (∇z(1,x2) = (C1,C2)T) )
en la búsqueda de una solución óptima por medio de los pasos anteriores
también pueden ocurrir otras situaciones :

1) Que la solución óptima exista pero que haya más de una. Es decir que
las rectas de isoutilidad corten a una de las restricciones de la región
factible.

2) Que el problema no tenga solución, dada una región de puntos factibles

no - acotada.

3) Que  el problema no tenga solución, porque no existen puntos factibles.

Para ver un ejemplo de cada uno de los pasos citados anteriormente se
recomienda seguir la presentación Solución Gráfica de un PL (abrir
documento)

Introducción al método Simplex      

El algoritmo SIMPLEX es un método iterativo que sigue los siguientes pasos:

1. Halla una solución inicial o una solución factible en un vértice (FEV)

2. Realiza una prueba de optimalidad: es decir, chequea las soluciones FEV

adyacentes a la solución actual.

3. Desarrolla Iteraciones: Se mueve hacia otras soluciones FEV

El método iterativo busca la solución óptima de un problema de

programación lineal y la  encuentra cuando ninguna de las soluciones FEV
adyacentes a la solución evaluada produce un mejor valor de la función
objetivo.

EL método simplex debe cumplir con cuatro teoremas fundamentales:

1. La solución óptima (si existe) se encuentra en un vértice de la Región

Factible.

2. Si una solución en un vértice, no tiene soluciones adyacentes mejores,

esa es la solución óptima (óptimo local es global).

3. Una solución básica (en un vértice aumentada) es la resultante de hacer

(n-m) variables iguales a cero y resolver el sistema de ecuaciones para las
m variables restantes.

4. Soluciones adyacentes tienen iguales todas las variables básicas menos

una (y por supuesto las no básicas).

Para ver un ejemplo inicial que ilustra la lógica del procedimiento simplex
por favor ir a: (Introducción al método Simplex)

l método simplex, procedimiento algebraico      

Definiciones claves para el procedimiento algebraico

Forma aumentada de un PL

El método simplex es un procedimiento algebraico donde las soluciones se

obtienen al resolver un sistema de ecuaciones lineales conformado a partir
de las restricciones funcionales. El sistema de ecuaciones lineales se obtiene
al convertir cada desigualdad (si el problema ha sido estructurado de esta
manera) de la forma original, en una igualdad equivalente.

Para esto es necesario usar variables de holgura, las cuales son variables,
no negativas, que se adicionan al lado izquierdo de una restricción funcional
de desigualdad del tipo ≤, para convertirla en una igualdad equivalente.

De esta manera los problemas de programación lineal pueden ser llevados

de su forma original a su forma aumentada, o en equivalencia de la forma
canónica  a la forma estándar. Para ver un ejemplo de transformación
algebraica por favor ir a (Introducción al método Simplex  -Procedimiento
algebraico del Simplex).

Variables Básicas y no Básicas

Ahora es necesario hacer una definición, o una clasificación importante de

las variables que se tienen en un problema de PL.
Para empezar es necesario aclarar que cada variable (de decisión o de
holgura) puede clasificarse en básica o no básica.

En un sistema con n variables y m restricciones, donde n > m, habrá: m:

variables básicas n - m: variables no básicas que son aquellas que se
igualan a cero por definición.

Las variables básicas obtienen su valor al solucionar el sistema de m

ecuaciones y si los valores de las variables básicas satisfacen la condición
de no negatividad se les denomina soluciones básicas factibles. Un ejemplo
de variables básicas y no básicas se ilustra en el siguiente link (Introducción
al método Simplex  -Procedimiento algebraico del Simplex).

El procedimiento algebraico del método simplex

El procedimiento algebraico del simplex consiste en desarrollar los

siguientes aspectos:

o Hallar una solución inicial.

o Hacer una Prueba de optimalidad.
o Realizar nueva iteración
o Determinación de la dirección de movimiento: Variable que
entra a la base: columna pivote
o Determinación de donde detenerse: Variable que sale de la
base: fila pivote

o Calcular una nueva solución básica factible

o Obtener 1 en la fila pivote
o Obtener 0 en el resto de la columna pivote

Para observar varios ejemplos del procedimiento algebraico por favor ir a

(Introducción al método Simplex  -Procedimiento algebraico del Simplex).

Teniendo claro como es la resolución de problemas de maximización por

medio del algoritmo simplex, la pregunta que surge es como resolver
problemas de minimización:
Se tienen dos métodos:

1.       Multiplicar la F.O del problema de minimización por -1 y resuelva el

problema como si fuera un problema de maximización. (-Z) = -
(CX1+CX2…)
2.       Seleccionar la variable con el coeficiente más positivo en el renglón 0
para que entre a la base.
Ver ejemplo en (Introducción al método Simplex  -Procedimiento algebraico
del Simplex).

Casos especiales del Simplex

Similarmente que con el método de solución gráfica el procedimiento

algebraico del simplex puede identificar cuando se tienen condiciones
especiales en los problemas de programación lineal. Estos son:

o Empate de la variable que entra

o Empate de la variable que sale
o Cuando no hay variable básica que sale
o Soluciones óptimas alterna

Los ejemplos ilustrados de cada uno se encuentran en (Introducción al

método Simplex  -Procedimiento algebraico del Simplex).

El método simplex de las dos fases      

El simplex de dos fases se usa cuando una solución básica no está

fácilmente disponible. En pocas palabras cuando todas las restricciones no
son de tipo <= y no puede establecerse una base a partir de las variables
de holgura, es decir cuando se tienen al menos una restricción de tipo = ó
>=.

Para resolver esta situación se deben seguir los siguientes pasos:

1. Modifique las restricciones de tal manera que el segundo miembro o lado

derecho de cada una sea no negativo. (-1) (recordar que cambia la
desigualdad).

2. Identifique cada restricción que ahora es una restricción = ó >=.

3. Convierta las restricciones de desigualdad a forma estándar agregando

variables de holgura (Si) o una variable excedente (ei).

4. Sume variables artificiales ai a las restricciones >= ó =.  También

adicione la restricción de signo ai >=0.

5. Resuelva un PL cuya función objetivo es min W´ = suma de todas las

variables artificiales (PL de la fase 1). Este Pl forzara a las variables
artificiales a ser cero.

Siguiendo los pasos anteriores pueden tenerse dos casos:

 Caso 1. No hay solución:

El valor óptimo de W´ es mayor que cero en este caso el PL original

no tiene solución factible.
  Caso 2. Solución Óptima del Pl Original

El valor óptimo de w´ es igual a cero y ninguna variable artificial está

en la base optima dela fase I. Se suprimen las columnas del arreglo
óptimo de la Fase I que corresponden a las variables artificiales. Se
combina la función objetivo original  y las restricciones que quedaron
de la fase I. La solución óptima para el PL de la fase II es la solución
óptima del PL Original.
Para ver un ejemplo del método simplex de las dos fases por favor ir
a (Introducción al método Simplex  -Procedimiento algebraico del
Simplex – Simplex de dos fases).

    
  Fuentes de estudio
Base de Datos Elibro.
Guerrero, S. H. (2009). Programación lineal aplicada.Bogotá, CO: Ecoe
Ediciones.Retrieved from http://www.ebrary.com
http://site.ebrary.com/lib/univucnsp/reader.action?
ppg=139&docID=10758304&tm=1502933605202

Métodos especiales:
http://site.ebrary.com/lib/univucnsp/reader.action?
ppg=183&docID=10758304&tm=1502933688653

Maximización:
  https://youtu.be/__oYwGhVkS8  

Minimización:
https://youtu.be/qwbJTUjxN34

Otros enlaces de interés. En los siguientes enlaces encuentra material

textual y audiovisual con el cual debe profundizar sobre los temas
expuestos arriba. Se sugiere tomar nota o desarrollar fichas de lectura de
los temas y aprendizajes adquiridos con la utilización de dichos insumos:

http://www.zweigmedia.com/RealWorld/tutorialsf4/framesSimplex.html
http://www.phpsimplex.com/teoria_metodo_simplex.htm
http://www.ganimides.ucm.cl/haraya/doc/m_simplex.pdf
  

    
   Videos  

Tomado de: https://www.youtube.com/watch?v=VMKfptt43QU

Tomado de: https://www.youtube.com/watch?v=M4K6HYLHREQ

 Tomado de: https://www.youtube.com/watch?v=qxls3cYg8to

Tomado de: https://www.youtube.com/watch?v=jcdiroeksHE

Tomado de: https://www.youtube.com/watch?v=I7brzjFhYEU

    

Una vez finalizada la exploración y el estudio de los insumos propuestos, la

invitación es a desarrollar la siguiente actividad con la cual podrá afianzar
las competencias adquiridas a lo largo de esta unidad.