Gramática Regular

En informática una gramática regular es una gramática formal (N, Σ, P, S) que puede ser clasificada como regular izquierda o regular derecha. Las gramáticas regulares sólo pueden generar a los lenguajes regulares de manera similar a los autómatas finitos y las expresiones regulares.

Dos gramáticas regulares que generan el mismo lenguaje regular se denominan equivalentes. Toda gramática regular es una gramática libre de contexto.

Una gramática regular derecha es aquella cuyas reglas de producción P son de la siguiente forma:

1. A → a, donde A es un símbolo no-terminal en N y a uno terminal en Σ
2. A → aB, donde A y B pertenecen a N y a pertenece a Σ
3. A → ε, donde A pertenece a N.

Análogamente, en una gramática regular izquierda, las reglas son de la siguiente forma:

1. A → a, donde A es un símbolo no-terminal en N y a uno terminal en Σ
2. A → Ba, donde A y B pertenecen a N y a pertenece a Σ
3. A → ε, donde A pertenece a N.

Una definición equivalente evita la regla 1 (A → a) ya que es sustituible por:

A → aL

L → ε

en el caso de las gramáticas regulares derechas y por:

A → La

L → ε

en el caso de las izquierdas.

Algunos autores alternativamente no permiten el uso de la regla 3 suponiendo que la cadena vacía no pertenece al lenguaje.

Un ejemplo de una gramática regular G con N = {S, A}, Σ = {a, b, c}, P se define mediante las siguientes reglas:

S → aS

S → bA

A → ε

A → cA

donde S es el símbolo inicial. Esta gramática describe el mismo lenguaje expresado mediante la expresión regular a*bc*.

Dada una gramática regular izquierda es posible convertirla, mediante un algoritmo en una derecha y viceversa.

PD: Para mayor comprension pueden descargar este documento adjunto.

Gramatica Regular.pdf

Tomado de: http://es.wikipedia.org/wiki/Gram%C3%A1tica_regular

Resumen Modelos Matemáticos

Unidad: Modelamiento Matemático

Capitulo y Tema:
- Programación Lineal
- Método Grafico
- Método Simplex

Actividad: Resumen Programación Lineal, Método Grafico y Método Simplex (Recuperación Teórica).

Módulo: 9º “B”
Nombre : Pablo Aguilar

Profesor: Ing. Luis Chamba

Fecha en la cual el profesor encarga la actividad:
14 de Octubre de 2010

Fecha en la cual el profesor recibe la actividad:
20 de Octubre de 2010

Bibliografía: http://www.investigacion-operaciones.com/Solucion_Grafica.htm
http://www.programacionlineal.net/


Programación Lineal

Un modelo de Programación Lineal (PL) considera que las variables de decisión tienen un comportamiento lineal, tanto en la función objetivo como restricciones del problema.

Método Gráfico

El análisis gráfico es una alternativa eficiente para enfrentar la resolución de modelos de Programación Lineal en 2 variables, donde el dominio de puntos factibles (en caso de existir) se encontrará en el primer cuadrante, como producto de la intersección de las distintas restricciones del problema lineal.

Método Simplex
El Método Simplex publicado por George Dantzig en 1947 consiste en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación Lineal en caso de existir esta última.

RESULTADOS:

Programación Lineal
La Programación Lineal es una de las herramientas más utilizadas en la Investigación Operativa debido a que por su naturaleza se facilitan los cálculos y en general permite una buena aproximación de la realidad.
Los Modelos Matemáticos se dividen básicamente en Modelos Determistas (MD) o Modelos Estocásticos (ME). En el primer caso (MD) se considera que los parámetros asociados al modelo son conocidos con certeza absoluta, a diferencia de los Modelos Estocásticos, donde la totalidad o un subconjunto de los parámetros tienen una distribución de probabilidad asociada.
Ejemplo: Problema de la Dieta: (Stigler, 1945). Consiste en determinar una dieta de manera eficiente, a partir de un conjunto dado de alimentos, de modo de satisfacer requerimientos nutricionales. La cantidad de alimentos a considerar, sus características nutricionales y los costos de éstos, permiten obtener diferentes variantes de este tipo de modelos. Por ejemplo:

Leche
(lt) Legumbre
(1 porción) Naranjas
(unidad) Requerimientos
Nutricionales
Niacina 3,2 4,9 0,8 13
Tiamina 1,12 1,3 0,19 15
Vitamina C 32 0 93 45
Costo 2 0,2 0,25

Variables de Decisión:
• X1: Litros de Leche utilizados en la Dieta
• X2: Porciones de Legumbres utilizadas en la Dieta
• X3: Unidades de Naranjas utilizadas en la Dieta
Función Objetivo: (Minimizar los Costos de la Dieta) Min 2X1 + 0,2X2 + 0,25X3
Restricciones: Satisfacer los requerimientos nutricionales
• Niacina: 3,2X1 + 4,9X2 + 0,8X3 >= 13
• Tiamina: 1,12X1 + 1,3X2 + 0,19X3 >=15
• Vitamina C: 32X1 + 0X2 + 93X3 >= 45
• No Negatividad: X1>=0; X2>=0; X3>=0
La solución Óptima es X1=0, X2=11,4677, X3=0,483871, con Valor Óptimo V(P)=2,4145.

Método Gráfico

Una de las propiedades básicas de un modelo de Programación Lineal que admite solución, es que ésta se encontrará en el vértice o frontera (tramo) del dominio de puntos factibles. Es decir, si luego de graficar el dominio y evaluar los distintos vértices de modo de elegir "el mejor" candidato según sea nuestro caso (el valor de la función objetivo será la que nos permitirá discriminar cual es el mejor candidato dependiendo si estamos maximizando o minimizando).
Consideremos un Ejemplo en 2 variables:

MIN 8X + 6Y
• S.A. 2X + Y >= 10
• ...... .2X + 2Y >= 16
• ..... ..X>= 0, Y>= 0

Para resolver el problema graficamos el dominio de puntos factibles y las curvas de nivel asociadas a la función objetivo:

El área pintada en color verde representa el dominio de puntos factibles del problema, es decir, son las distintas combinaciones de valores que pueden adoptar las variables de decisión que satisfacen las restricciones del problema. Cabe destacar que esto corresponde a un dominio no acotado, lo que no implica que el problema no tenga solución.
Por otra parte sabemos que el óptimo de un problema lineal se encuentra en un vértice o frontera del dominio de puntos factibles. En este caso tenemos 3 vértices candidatos al óptimo los cuales se señalan con flecha blanca y azul. El vértice (X,Y)= (0,10) con V(P)=60; (X,Y)=(2,6) con V(P)=52 y (X,Y)=(8,0) con V(P)=64. El mínimo valor para la función objetivo se alcanza en (X,Y)=(2,6) con V(P)=52, el cual resulta ser la Solución Óptima. Sin embargo, una forma más eficiente para obtener el óptimo que no implique evaluar cada vértice en la función objetivo, es desplazando las curvas de nivel de la función objetivo en la dirección del máximo decrecimiento (en el caso de un problema de minimización). Para un problema de minimización, el mayor decrecimiento se alcanza en la dirección del vector " - Gradiente F(X,Y)", en nuestro caso el vector con dirección (-8,-6) (dirección representada por flecha roja). Luego, el óptimo se alcanza en el último punto donde las curvas de nivel intersectan al dominio de puntos factibles en la dirección del máximo decrecimiento, cuya solución obviamente corresponde a (X,Y)=(2,6) con V(P)=52.

Método Simplex
La primera implementación computacional del Método Simplex es el año 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.
El Método Simplex hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar.


Modelamiento Matemático by Pablo Aguilar is licensed under a Creative Commons Attribution-NonCommercial 3.0 Ecuador License.
Permissions beyond the scope of this license may be available at http://pabloaguilar3.blogspot.com/2010/10/resumen-modelos-matematicos.html.