GENRY RICARDEZ GARCIAING. EN SISTEMAS COMPUTACIONALES

08/09/20112011

INSTITUTO TECNOLOGICO DE VILLAHERMOSATEMARIO 1° UNIDAD

INVESTIGACION DE OPERACIONES

CATEDRATICA: M.C. ZINATH JAVIER GERONIMO

INDICE1.1 DEFINICIÓN, DESARROLLO Y TIPOS DE MODELOS DE INVESTIGACIÓN DE OPERACIONES............................................................................................................2

ORÍGENES DE LA INVESTIGACIÓN DE OPERACIONES.................................2

INVESTIGACIÓN DE OPERACIONES (IO)...........................................................3

NATURALEZA DE LA INVESTIGACIÓN DE OPERACIONES............................4

¿QUÉ ES LA INVESTIGACIÓN DE OPERACIONES?.........................................5

CONCEPTO DE OPTIMIZACIÓN..........................................................................6

ENFOQUE DE LA INVESTIGACIÓN DE OPERACIONES:..................................6

MODELOS: CLASIFICACIÓN.................................................................................7

CLASIFICADOS SEGÚN SU FUNCIÓN:..............................................................8

1.2 FORMULACIÓN DE MODELOS..........................................................................10

1.3 MÉTODO GRÁFICO..............................................................................................11

1.4 FORMAS ESTÁNDAR Y CANÓNICAS...............................................................13

1.5 MÉTODO SIMPLES...............................................................................................14

3.1.1 EXPLICACION GRAFICA DEL PROCESO SIMPLEX....................................14

1.6 TÉCNICAS CON VARIABLES ARTIFICIALES...................................................15

1.6.1 Método de la M...................................................................................................15

1.6.2 MÉTODO DE LAS DOS FASES........................................................................17

BIBLIOGRAFIA:...........................................................................................................22

1.1 DEFINICIÓN, DESARROLLO Y TIPOS DE MODELOS DE INVESTIGACIÓN DE OPERACIONES.

ORÍGENES DE LA INVESTIGACIÓN DE OPERACIONES

La toma de decisiones es un proceso que se inicia cuando una persona observa

un problema y determina que es necesario resolverlo procediendo a definirlo, a

formular un objetivo, reconocer las limitaciones o restricciones, a generar alternativas

de solución y evaluarlas hasta seleccionar la que le parece mejor, este proceso puede

ser cualitativo o cuantitativo.

El enfoque cualitativo se basa en la experiencia y el juicio personal, las

habilidades necesarias en este enfoque son inherentes en la persona y aumentan con

la práctica. En muchas ocasiones este proceso basta para tomar buenas decisiones.

El enfoque cuantitativo requiere habilidades que se obtienen del estudio de

herramientas matemáticas que le permitan a la persona mejorar su efectividad en la

toma de decisiones. Este enfoque es útil cuando no se tiene experiencia con

problemas similares o cuando el problema es tan complejo o importante que requiere

de un análisis exhaustivo para tener mayor posibilidad de elegir la mejor solución.

La investigación de operaciones proporciona a los tomadores de decisiones bases

cuantitativas para seleccionar las mejores decisiones y permite elevar su habilidad

para hacer planes a futuro.

En el ambiente socioeconómico actual altamente competitivo y complejo, los

métodos tradicionales de toma de decisiones se han vuelto inoperantes e

inadmisibles ya que los responsables de dirigir las actividades de las empresas e

instituciones se enfrentan a situaciones complicadas y cambiantes con rapidez que

requieren de soluciones creativas y prácticas apoyadas en una base cuantitativa

sólida.

En organizaciones grandes se hace necesario que el tomador de decisiones tenga

un conocimiento básico de las herramientas cuantitativas que utilizan los especialistas

para poder trabajar en forma estrecha con ellos y ser receptivos a las soluciones y

recomendaciones que se le presenten.

INVESTIGACIÓN DE OPERACIONES (IO).

Las raíces de la investigación de operaciones se remontan a muchas décadas,

cuando se hicieron los primeros intentos para emplear el método científico en la

administración de una empresa. Sin embargo, el inicio de la actividad llamada

investigación de operaciones, casi siempre se atribuye a los servicios militares

prestados a principios de la segunda guerra mundial. Debido a los esfuerzos bélicos,

existía una necesidad urgente de asignar recursos escasos a las distintas

operaciones militares y a las actividades dentro de cada operación, en la forma más

efectiva. Por esto, las administraciones militares americana e inglesa hicieron un

llamado a un gran número de científicos para que aplicaran el método científico a éste

y a otros problemas estratégicos y tácticos. De hecho, se les pidió que hicieran

investigación sobre operaciones (militares). Estos equipos de científicos fueron los

primeros equipos de IO. Con el desarrollo de métodos efectivos para el uso del nuevo

radar, estos equipos contribuyeron al triunfo del combate aéreo inglés. A través de

sus investigaciones para mejorar el manejo de las operaciones antisubmarinas y de

protección, jugaron también un papel importante en la victoria de la batalla del

Atlántico Norte. Esfuerzos similares fueron de gran ayuda en la isla de campaña en el

pacífico.

Al terminar la guerra, el éxito de la investigación de operaciones en las actividades

bélicas generó un gran interés en sus aplicaciones fuera del campo militar. Como la

explosión industrial seguía su curso, los problemas causados por el aumento en la

complejidad y especialización dentro de las organizaciones pasaron de nuevo a

primer plano. Comenzó a ser evidente para un gran número de personas, incluyendo

a los consultores industriales que habían trabajado con o para los equipos de IO

durante la guerra, que estos problemas eran básicamente los mismos que los

enfrentados por la milicia, pero en un contexto diferente. Cuando comenzó la década

de 1950, estos individuos habían introducido el uso de la investigación de

operaciones en la industria, los negocios y el gobierno. Desde entonces, esta

disciplina se ha desarrollado con rapidez.

NATURALEZA DE LA INVESTIGACIÓN DE OPERACIONES

Como su nombre lo dice, la investigación de operaciones significa "hacer

investigación sobre las operaciones". Entonces, la investigación de operaciones se

aplica a problemas que se refieren a la conducción y coordinación de operaciones (o

actividades) dentro de una organización. La naturaleza de la organización es

esencialmente inmaterial y, de hecho, la investigación de operaciones se ha aplicado

de manera extensa en áreas tan diversas como la manufactura, el transporte, la

constitución, las telecomunicaciones, la planeación financiera, el cuidado de la salud,

la milicia y los servicios públicos, por nombrar sólo unas cuantas. Así, la gama de

aplicaciones es extraordinariamente amplia.

La parte de investigación en el nombre significa que la investigación de

operaciones usa un enfoque similar a la manera en que se lleva a cabo la

investigación en los campos científicos establecidos. En gran medida, se usa el

método científico para investigar el problema en cuestión. (De hecho, en ocasiones

se usa el término ciencias de la administración como sinónimo de investigación de

operaciones.) En particular, el proceso comienza por la observación cuidadosa y la

formulación del problema incluyendo la recolección de los datos pertinentes. El

siguiente paso es la construcción de un modelo científico (por lo general matemático)

que intenta abstraer la esencia del problema real. En este punto se propone la

hipótesis de que el modelo es una representación lo suficientemente precisa de las

características esenciales de la situación como para que las conclusiones

(soluciones) obtenidas sean válidas también para el problema real. Después, se

llevan a cabo los experimentos adecuados para probar esta hipótesis, modificarla si

es necesario y eventualmente verificarla. (Con frecuencia este paso se conoce como

validación del modelo.) Entonces, en cierto modo, la investigación e operaciones

incluyen la investigación científica creativa de las propiedades fundamentales de las

operaciones. Sin embargo, existe más que esto. En particular, la IO se ocupa también

de la administración práctica de la organización. Así, para tener éxito, deberá también

proporcionar conclusiones claras que pueda usar el tomador de decisiones cuando

las necesite.

¿QUÉ ES LA INVESTIGACIÓN DE OPERACIONES?

Como toda disciplina en desarrollo, la investigación de operaciones ha ido

evolucionando no sólo en sus técnicas y aplicaciones sino en la forma como la

conceptualizan los diferentes autores, en la actualidad no existe solamente una

definición sino muchas, algunas demasiado generales, otras demasiado engañosas,

aquí seleccionamos dos de las más aceptadas y representativas.

De ésta definición se pueden destacar los siguientes conceptos:

1.  Una organización es un sistema formado por componentes que se interaccionan,

unas de estas interacciones pueden ser controladas y otras no.

2.  En un sistema la información es una parte fundamental, ya que entre las

componentes fluye información que ocasiona la interacción entre ellas. También

dentro de la estructura de los sistemas se encuentran recursos que generan

interacciones. Los objetivos de la organización se refieren a la eficacia y eficiencia

con que las componentes pueden controlarse, el control es un mecanismo de

autocorrección del sistema que permite evaluar los resultados en términos de los

objetivos establecidos.

3.  La complejidad de los problemas que se presentan en las organizaciones ya no

encajan en una sola disciplina del conocimiento, se han convertido en

multidisciplinario por lo cual para su análisis y solución se requieren grupos

compuestos por especialistas de diferentes áreas del conocimiento que logran

comunicarse con un lenguaje común.

4.  La investigación de operaciones es la aplicación de la metodología científica a

través modelos matemáticos, primero para representar al problema y luego para

resolverlo. La definición de la sociedad de investigación de operaciones de la Gran

Bretaña es la siguiente:

La investigación de operaciones es el ataque de la ciencia moderna a los

complejos problemas que surgen en la dirección y en la administración de grandes

sistemas de hombres, máquinas, materiales y dinero, en la industria, en los negocios,

en el gobierno y en la defensa.

CONCEPTO DE OPTIMIZACIÓN.

            Una característica adicional, que se mencionó como de pasada, es que la

Investigación de Operaciones intenta encontrar la mejor solución, o la solución

óptima, al problema bajo consideración. En lugar de contentarse con sólo mejorar

el estado de las cosas, la meta es identificar el mejor curso de acción posible. Aun

cuando debe interpretarse con todo cuidado, esta “búsqueda de la optimalizad” es

un aspecto muy importante dentro de la Investigación de Operaciones.

ENFOQUE DE LA INVESTIGACIÓN DE OPERACIONES:

La parte innovadora de la IO es sin duda alguna su enfoque modelístico, producto de sus

creadores aunado a la presión de supervivencia de la guerra o la sinergia generada al

combinarse diferentes disciplinas, una descripción del enfoque es la siguiente.

1. Se define el sistema real en donde se presenta el problema. Dentro del

sistema interactúan normalmente un gran número de variables.

2. Se seleccionan las variables que norman la conducta o el estado actual del

sistema, llamadas variables relevantes, con las cuales se define un sistema

asumido del sistema real.

3. Se construye un modelo cuantitativo del sistema asumido, identificando y

simplificando las relaciones entre las variables relevantes mediante la

utilización de funciones matemáticas.

4. Se obtiene la solución al modelo cuantitativo mediante la aplicación de una o

más de las técnicas desarrolladas por la IO.

5. Se adapta e imprime la máxima realidad posible a la solución teórica del

problema real obtenida en el punto 4, mediante la consideración de factores

cualitativos o no cuantificables, los cuales no pudieron incluirse en el modelo.

Además se ajusta los detalles finales vía el juicio y la experiencia del tomador

de decisiones.

6. Se implanta la solución en el sistema real.

MODELOS: CLASIFICACIÓN

Como acabamos de ver con anterioridad una de las fases de la aplicación

del método científico se basa en la construcción de modelos o formulación de

hipótesis. En nuestro caso nos centraremos en la construcción de modelos.

Aunque hay numerosas acepciones y definiciones de un modelo, hemos elegido la

de Aracil (1):

“ Un modelo constituye una representación abstracta de un cierto aspecto

de la realidad, y tiene una estructura que está formada por los elementos que

caracterizan el aspecto de la realidad modelada y por las relaciones entre estos

elementos".

A partir de este concepto de modelo se pueden obtener distintas

clasificaciones (icónico, analógicos, simbólicos, etc.), sin embargo, solo estamos

interesados en los modelos matemáticos, es decir, los modelos formales basados

en la lógica matemática, y se basan en un conjunto de relaciones matemáticas

(tales como ecuaciones, inecuaciones, relaciones lógicas, etc.) que se

corresponden con las relaciones del mundo real (tales como relaciones

tecnológicas, leyes físicas, restricciones del mercado, etc.).

No vamos a entrar en esta polémica, sino que lo único que queremos es

poner de manifiesto que los modelos deben usarse como una herramienta más

para la toma de decisiones y que deben valorarse en su justa medida, ya que

difícilmente es comprensible un problema complejo sin una mínima modelización,

aunque también hay que reconocer que no es posible modelar la totalidad de las

situaciones reales.

Con anterioridad nos hemos referido a tipos de modelos basados en sus

formas de representación (icónico, analógicos, simbólicos), no obstante podemos

establecer otros tipos de clasificaciones de los modelos matemáticos:

CLASIFICADOS SEGÚN SU FUNCIÓN:

Modelos predictivos: Este tipo de modelos nos informan del

comportamiento de la  variable en un futuro, es decir, lo que debería ser. A este

tipo de modelos corresponden aquellos basados en técnicas estadísticas y/o

econométricas, es decir, modelos de previsión.

Modelos evaluativos: Una técnica evaluativa corresponde a medir las

diferentes alternativas, y así poder comparar los resultados de ellas. Este tipo de

modelos se corresponden con los denominados árboles de decisión.

Modelos de optimización: Se trata de modelos que tratan de identificar

un óptimo (por lo general, el óptimo global) del problema, es decir, buscan la mejor

de las alternativas posibles. Estos métodos son los que están basados en las

técnicas de programación matemática.

Otra clasificación de los modelos se basa en la realidad que pretender modelar, así

podemos hablar de:

Modelos deterministas versus modelos estocásticos. En los modelos

deterministas todos los datos del problema se conocen con absoluta certeza,

mientras que cuando esto no es así tenemos los modelos estocásticos. Por lo

general los modelos más realistas son los modelos estocásticos, pero tienen la

dificultad de poderlos resolver adecuadamente, y muchas de las técnicas aplicables

a los modelos estocásticos tratan de reducir el problema a su versión determinista

para poderlo resolver.

Modelos estáticos versus modelos dinámicos. En un modelo estático la

variable tiempo no desempeña un papel relevante, mientras que en los modelos

dinámicos la variable fundamental, y de la que dependen las restante variables

relevantes. Además, el variable tiempo se considera como una variable continua.

Una vez establecida una serie de clasificaciones de  los modelos, es conveniente

plantear una medida de su solución, ya que el objetivo de plantear el modelo es el

poderlo resolver y extraer de la solución los resultados necesarios para la toma de

decisiones. El nivel de re solubilidad de los problemas es función de tres

características fundamentales:

a) El tamaño del problema: El número de variables y ecuaciones que contiene.

Cuanto mayor sea este número, más difícil de resolver es.

b) La clase del problema: Lineal, Entero y No lineal, y además por ese orden,

es decir, los problemas lineales son "fácilmente" resolubles, mientras que los

no lineales son "intrínsecamente" difíciles de resolver.

c) El tipo de instancias utilizadas: Ciertas o deterministas, con riesgo

(conocemos las probabilidades de ocurrencia), con incertidumbre

(conocemos los resultamos posibles pero no las probabilidades de

ocurrencia) y turbulencia (no conocemos nada).

1.2 FORMULACIÓN DE MODELOS La forma convencional en que la investigación de operaciones realiza esto es

construyendo un modelo matemático que represente la esencia del problema.

Un modelo siempre debe ser menos complejo que el problema real, es una

aproximación abstracta de la realidad con consideraciones y simplificaciones que

hacen más manejable el problema y permiten evaluar eficientemente las

alternativas de solución.

OBTENCIÓN DE UNA SOLUCIÓN A PARTIR DEL MODELO.

Resolver un modelo consiste en encontrar los valores de las variables

dependientes, asociadas a las componentes controlables del sistema con el

propósito de optimizar, si es posible, o cuando menos mejorar la eficiencia o la

efectividad del sistema dentro del marco de referencia que fijan los objetivos y las

restricciones del problema.

La selección del método de solución depende de las características del modelo.

Los procedimientos de solución pueden ser clasificados en tres tipos: a) analíticos,

que utilizan procesos de deducción matemática; b) numéricos, que son de carácter

inductivo y funcionan en base a operaciones de prueba y error; c) simulación, que

utiliza métodos que imitan o, emulan al sistema real, en base a un modelo.

PRUEBA DEL MODELO

Antes de usar el modelo debe probarse exhaustivamente para intentar

identificar y corregir todas las fallas que se puedan presentar.

VALIDACIÓN DEL MODELO

Es importante que todas las expresiones matemáticas sean consistentes en las

dimensiones de las unidades que emplean. Además, puede obtenerse un mejor

conocimiento de la validez del modelo variando los valores de los parámetros de

entrada y/o de las variables de decisión, y comprobando que los resultados de

modelo se comporten de una manera factible.

1.3 MÉTODO GRÁFICO.El método gráfico se utiliza para la solución de problemas de PL,

representando geométricamente a las restricciones, condiciones técnicas y el

objetivo. El modelo se puede resolver en forma gráfica si sólo tiene dos variables.

Para modelos con tres o más variables, el método gráfico es impráctico o

imposible.

Cuando los ejes son relacionados con las variables del problema, el método

es llamado método gráfico en actividad. Cuando se relacionan las restricciones

tecnológicas se denomina método gráfico en recursos.

Los pasos necesarios para realizar el método son nueve:

1. Graficar las soluciones factibles, o el espacio de soluciones (factible), que

satisfagan todas las restricciones en forma simultánea.

2. Las restricciones de no negatividad Xi>= 0 confían todos los valores

posibles.

3. El espacio encerrado por las restricciones restantes se determinan

sustituyendo en primer término <= por (=) para cada restricción, con lo cual

se produce la ecuación de una línea recta.

4. Trazar cada línea recta en el plano y la región en cual se encuentra cada

restricción cuando se considera la desigualdad lo indica la dirección de la

flecha situada sobre la línea recta asociada.

5. Cada punto contenido o situado en la frontera del espacio de soluciones

satisfacen todas las restricciones y por consiguiente, representa un punto

factible.

6. Aunque hay un número infinito de puntos factibles en el espacio de

soluciones, la solución óptima puede determinarse al observar la dirección

en la cual aumenta la función objetivo.

7. 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.

Ejemplo. Maximizar    Z  =  3X1 + 2X2 Restricciones:            X1   + 2X2   <=6       (1)                                  2X1  +  X2    <=8       (2)                                   -X1  + X2    <=1       (3)                                               X2   <= 2       (4)                                     X1              >= 0       (5)                                                X2   >= 0       (6)

Convirtiendo las restricciones a igualdad y representándolas gráficamente se tiene:

  X1 + 2X2  = 6       (1) 2X1  +  X2  = 8       (2) -X1  +  X2  = 1       (3)             X2  = 2       (4)  X1             = 0       (5)             X2  = 0       (6)

1.4 FORMAS ESTÁNDAR Y CANÓNICAS.

Un problema de programación lineal puede ser establecido en diferentes formas equivalentes a través de manipulaciones apropiadas. Dos formas en particular serán de bastante utilidad. Estas son las formas Estándar y Canónica. Un problema lineal se dice que está en la forma estándar sí;

a) Todas las restricciones son igualdades b) Todas las variables son no-negativas c) Las limitaciones ( lado derecho de la restricción) son positivas

El Método Simplex, está diseñado para ser aplicado únicamente hasta que el problema se encuentre en la forma Estándar. La forma Canónica es también de bastante utilidad, especialmente en explorar la relación de Dualidad. Un problema de P.L. está en la forma canónica si para un problema de:

Maximización, las variables son no-negativas y las restricciones son del tipo ≤

Minimización, las variables son no-negativas y las restricciones son del tipo ≥

Considere el siguiente problema de P.L. en forma canónica

Dónde: A= Matriz de coeficientes de las variables en el sistema de ecuaciones de (mxn) aij= coeficiente de la variable j en la restricción i

x=Vector solución (nx1) xj= Variable j

bi= Lado derecho de la restricción i (Limitación i)

C=Vector de costos o utilidades (1xn) cj= Coeficiente de la variable j en la función objetivo

1.5 MÉTODO SIMPLES

El método Simplex es un algoritmo iterativo para resolver de una forma eficiente los problemas de P.L de gran tamaño. Fue desarrollado primeramente en 1947 por C.B. Dantizg y sus colaboradores en el Departamento de las Fuerzas Aéreas de U.S. Se han realizado posteriormente algunas, revisiones en el método para conseguir incrementar su eficiencia de cálculo pero el método es básicamente el mismo. El método Simplex y sus variantes se han programado y codificado para todos los tipos y tamaños de ordenadores

3.1.1 EXPLICACION GRAFICA DEL PROCESO SIMPLEX

Ya se ha apuntado en el proceso de solución grafica que la búsqueda de una solución óptima debe hacerse únicamente en los vértices de espacio factible de solución. Esto es fácil de comprender en un problema con solo dos variables y tres restricciones, pero en problemas mayores se necesita un procedimiento para identificar y evaluar todos los vértices.

En el método Simplex, la búsqueda comienza, normalmente, en el origen y se desplaza al vértice adyacente que incremente el valor de la función objetivo. Cuando alcanza el nuevo vértice, la búsqueda se desplaza hacia otro nuevo adyacente que sea mejor que el último. El proceso continua hasta que no se puede lograr ninguna mejora.

El proceso Simplex siempre alcanza la solución óptima (si existe tal solución). Puesto que en cada iteración mejora la función objetico y hay solo un numero finito de vértices en la zona de factibilidad. Igualmente se alcanzara el óptimo independiente de donde comience el proceso.

1.6 TÉCNICAS CON VARIABLES ARTIFICIALESExisten problemas de programación lineal que no proporcionan una solución

básica inicial. Esta situación se presenta cuando al menos una de las restricciones es del tipo (<=) o (=). Para este propósito se desarrollan 2 métodos basados en el uso de variables artificiales: El método M o de penalización y la técnica de 2 fases.

1.6.1 MÉTODO DE LA M.

Pasos:

i. Expresar el modelo original en la forma estándar e igualar a cero la función objetivo.

ii. Sumar del lado izquierdo de cada ecuación, correspondiente a las restricciones del tipo ³ y/o =, una variable no negativa. Estas variables se llaman variables artificiales y su adición causa una alteración a las restricciones correspondientes esta dificultad es superada garantizando que las variables artificiales serán igual a cero (Z=0) en la solución final. Esto es alcanzado asignando un valor de penalización muy grande, por unidad, a estas variables en la función objetivo. Tal valor de penalización será designado por +M, si es un problema de maximización y -M para un problema de minimización con M>0.

iii. El uso de variables artificiales proporcionan una solución inicial básica, sin embargo para ello los coeficientes en la función objetivo deben ser igual a cero, para lograrlo usamos el procedimiento (algoritmo) del método simplex.

Las variables artificiales solamente proporcionan un mecanismo matemático para obtener una primera solución básica, el efecto de estas variables en la solución final es cancelado por el valor de penalización muy alto en la función objetivo. Estas variables son ficticias y no tienen alguna interpretación física ni económica directa en términos del problema original.

Ejemplo: Resolver el siguiente modelo de programación lineal por el método penal Min Z = 4x1 + x2

S.A.3x1   +   x2   = 34x1   +   3 x2   ³ 6x1   +   2 x2   # 3xj³0 (j =1,2)

i. Expresar el modelo original en la forma estándar e igualar a cero la función objetivo.

Z - 4x1-3x2+0x3-0x4+ =0S.A.3x1   +   x2            = 34x1   +   3 x2      -x3      = 6x1   +   2 x2         +x4   = 3xj³0 (j =1, 2, 3, 4,)

ii. Sumar del lado izquierdo de cada ecuación una variable artificial, identificada por W a cada una de las restricciones que en el modelo original sean del tipo = y ³, así mismo penalizar la función objetivo. Para el ejemplo que nos ocupa la primera y la segunda ecuación requieres de una variable artificial por lo que se identificarán por W1 y W2 respectivamente. La penalización en la función objetivo, es realizada restando un coeficiente M a cada una de las variables artificiales que se hayan sumado a las ecuaciones de restricción, para este ejemplo se penaliza la función objetivo dos veces, asignando un coeficiente –M para W1 y otro coeficiente –M para W2.

Min Z - 4x1 - x2 - MW1-MW2+ 0x3- 0x4=0S.A.3x1   +   x2   +   w1         = 34x1   +   3 x2   -   x3   +   w2   = 6x1   +   2 x2   +      x4      = 3xj³0 (j =1,2, 3, 4)wj³0 (j =1,2)

La tabla inicial es:

iii. Generando la solución inicial básica, haciendo ceros los coeficientes –M del renglón de la función objetivo de la tabla inicial simplex.Haciendo cero coeficiente-M de la variable artificial W1; matemáticamente:

MRp+R0

M (3   1   0   0   1   0   3) +    -4       -1       0       0       -M       -M       0    3M-4   M-1   0   0   0   –M   3M

Haciendo cero coeficiente-M de la variable artificial W2, matemáticamente: MRp+R0

M (4   3   -1   0   0   1   6) +   3M-4       M-1       0       0       0       –M       3M 7M-4   4M-1   -M   0   0   0   9M

Sustituyendo valores se tiene la siguiente tabla que corresponde a la solución inicial básica no-óptima.

1.6.2 MÉTODO DE LAS DOS FASES.

Pasos:Como su nombre lo indica, consiste en resolver problemas en dos

fases:  

i. Expresar el modelo original en la forma estándar e igualar a cero la función objetivo.  

ii. Sumar del lado izquierdo de cada ecuación, correspondiente a las restricciones del tipo ³ y/o =, una variable no negativa. Estas variables se llaman variables artifíciales y su adición causa una alteración a las restricciones correspondientes esta dificultad es superada garantizando que las variables artificiales serán igual a cero (W0=0) en la solución óptima de la primera fase.  

iii. FASE I  Formular un nuevo modelo, reemplazando la función objetivo del modelo original por la sumatoria de las variables artificiales que se sumaron en el paso anterior. La nueva función objetivo será entonces de Minimizar sujeta a las restricciones del problema original (en esta fase la función objetivo siempre será de minimizar, sin importar que la función objetivo del problema original sea de maximizar o minimizar). Si el problema tiene el espacio de soluciones factibles, el valor mínimo (optimo) de la nueva función objetivo será de cero (lo cual indica que todas las variables artificiales son cero). Si

esto ocurre podremos continuar con la fase dos de lo contrario, si el valor mínimo es mayor que cero el problema es terminado ya que esto indica que no existe espacio de soluciones factibles.

iv. FASE IIConsiderar la solución básica óptima de la fase I como una solución inicial para el problema original, en esta fase, de la tabla optima de la fase I se eliminan las columnas de las variables artificiales y se sustituye la función objetivo por la del problema original, Toda vez que se comprueba que se tiene una solución inicial básica-factible no-óptima se procede con los pasos normales del algoritmo del método simplex, hasta obtener, si existe, la solución óptima.

Ejemplo Minimizar Z=4x1+x2 S.A. 3x1   +   x2   =   3 4x1   +   3x2   ³   6 x1   +   2x2   #   3 xj³0 (j =1,2)

Solución:

i. Expresar el modelo original en la forma estándar e igualar a cero la función objetivo.

Z - 4x1-3x2+0x3-0x4 =0S.A.3x1   +   x2            = 34x1   +   3 x2      -x3      = 6x1   +   2 x2         +x4   = 3xj³0 (j =1, 2, 3, 4,)

ii. Sumar del lado izquierdo de cada ecuación una variable artificial, identificada por W a cada una de las restricciones que en el modelo original sean del tipo = y ³, Para el ejemplo que nos ocupa, la primera y la segunda ecuación requieren de una variable artificial cada una, es decir, W1 y W2 respectivamente.

3x1   +   x2   +   w1         = 34x1   +   3 x2   -   x3   +   w2   = 6x1   +   2 x2   +      x4      = 3xj³0 (j =1,2, 3, 4)wj³0 (j =1,2)

iii. FASE I  Formular un nuevo modelo cuya función objetivo será de Minimizar, se identificará por W0 y será igual a la sumatoria de las variables artificiales, es decir, W0 = W1+W2.

Min W0 - W1-W2=0S.A.3x1   +   x2   +   w1         = 34x1   +   3 x2   -   x3   +   w2   = 6x1    +   2 x2   +       x4      = 3xj³0 (j =1,2, 3, 4)wj³0 (j =1,2)

La tabla inicial de la primera fase es:

i. Segunda fase  Debemos considerar la solución básica óptima de la fase I como una solución inicial para el problema original, en esta fase, de la tabla optima de la fase I se eliminan las columnas de las variables artificiales y se sustituye la función objetivo por la del problema original, Toda vez que se comprueba que se tiene una solución inicial básica-factible no-óptima se procede con los pasos normales del algoritmo del método simplex, hasta obtener, si existe, la solución óptima. Para nuestro ejemplo, la tabla inicial de la segunda fase es:

Como podemos observar, al sustituir la función objetivo de la primera fase por la función objetivo del modelo original, la solución pierde su estructura básica

porque los coeficientes de X1 y X2 en la función objetivo son diferentes de cero, en este caso son –4 y –1 respectivamente, para restaurar la estructura básica lo que procede es hacer ceros el –4 y el –1 (coeficientes de X1 y de X2 en la función objetivo).

Haciendo cero coeficiente –4 de X1 4Rp + R0

4(1    0   1/5   0   3/5) -4       -1       0       0       0 0   -1   4/5   0   12/5

Haciendo cero coeficiente –3 de X1

1Rp + R0

1(0    1   -3/5   0   6/5) -0       -1       4/5       0       12/5 0    0    1/5   0   18/5

BIBLIOGRAFIA:

http://www.investigacion-operaciones.com/SIMPLEX_analitico.htm

METODOS CUANTITATIVOS VOLUMEN Io EDUARDO VICENS SALORT o ANGEL ORTIZ BASo JUAN JOSE GUARCH BERTOLIN

http://www.investigacion-operaciones.com/Metodos_Solucion_PL.htm

http://hemaruce.angelfire.com/ FORMA_CANONICA_Y_FORMA_ESTANDAR.pdf

INSTITUTO TECNOLOGICO SUPERIOR DE CALKINI EN EL ESTADO DE CAMPECHE:

http://148.204.211.134/polilibros/portal/Polilibros/P_Terminados/InvOperac- 1-Virginia/InvOperac/UMD/Unidad%204/Contenido/metodopenal_.htm