Semana 4 Optprocesos

Sesión 4
UNIDAD 3. PROGRAMACIÓN NO LINEAL
Docente: Vidal Armas Torres

02 de agosto de 2023
3.1. Tipos de algoritmos no
restringidos
Algoritmos no restringidos
Tipos
Los problemas de programación no lineal se presentan
de muchas formas distintas. Al contrario del método
símplex para programación lineal, no se dispone de un
algoritmo que resuelva todos estos tipos especiales de
problemas.
En su lugar, se han desarrollado algoritmos para
algunas clases (tipos especiales) de problemas de
programación no lineal.
Tipos
Sección dorada
Método de Newton
Biseccion
Búsqueda directa
Sección dorada
Se dice que una función de una sola variable es
unimodal, cuando tiene un solo punto mínimo o
máximo. Obviamente, en una función unimodal, un
punto mínimo o máximo es global o absoluto. Toda
función cóncava o convexa es unimodal, pero no toda
función unimodal es cóncava o convexa.
Sección dorada
El método de la sección dorada requiere que la función
sea de una sola variable y unimodal. La estrategia de
este método se basa en tres puntos iniciales: dos
considerados los extremos de un intervalo (y el tercero
entre los dos primeros de tal suerte que la relación
entre la distancia de este punto interno al extremo y la
distancia entre los extremos es siempre una constante.
Método de Newton
El método de Newton-Raphson es un método iterativo
con el que se pueden encontrar aproximaciones de
soluciones de ecuaciones no lineales.
El método parte de un valor inicial que se introduce en
una expresión relacionada con la ecuación, obteniendo
así un resultado.
Método de Newton
Ese resultado se introduce en la misma expresión,
obteniendo un nuevo resultado, y así sucesivamente.
Si la elección del valor inicial es buena, cada vez que
introducimos unos de los resultados obtenidos en esa
expresión (es decir, cada vez que realizamos una
iteración del método) el método nos proporciona una
aproximación a la solución real mejor que la que
tuviéramos anteriormente.
Pasos para aplicar el Método de Newton
Se expresa la ecuación como fx=0 e identificamos la
función f. ejemplo se tiene: Ln(xn-1)+Cos(xn-1) = 0
queda F(x)= Ln(xn-1)+Cos(xn-1).
Calcular la derivada. En este caso sería: 1/(Xn -1)-
sen(Xn-1).
Se construye la formula. Quedando esta: Xn+1= Xn -
(Ln(Xn-1)+Cos(Xn-1))/(1/(Xn- 1)- sen(Xn- 1)).
Pasos para aplicar el Método de Newton
Comenzar con una aproximación inicial. X0= 1,3.
Y con los pasos anteriores se halla la aproximación
mejorada de Xn+1 que es la intersección del eje x y la
recta tangente de la función f(x) en el punto [X0, f(x0)].
Biseccion
En matemáticas, el método de bisección, también
llamado dicotomía, es un algoritmo de búsqueda de
raíces que trabaja dividiendo el intervalo a la mitad y
seleccionando el subintervalo que tiene la raíz.
Búsqueda directa
Los métodos de búsqueda directa se aplican sobre
todo a funciones de una sola variable estrictamente
unimodales, en donde la optimización de funciones de
una sola variable es clave en el desarrollo del algoritmo
general de múltiples variables.
Búsqueda directa
La idea de los métodos de búsqueda directa es
identificar el intervalo de incertidumbre que se sabe
incluye el punto de solución óptima. El procedimiento
localiza el óptimo estrechando de manera interactiva el
intervalo de incertidumbre a un nivel de exactitud
deseada.
3.2. Tipos de algoritmos restringidos
Algoritmos restringidos
Tipos
Un algoritmo de restricción es un conjunto de reglas.
Existen varios tipos de algoritmos de restricción, cada
uno con enfoques y técnicas distintas para abordar
problemas específicos. A continuación, se presentan
algunos de los tipos más comunes de algoritmos de
restricción
Tipos
Backtracking (vuelta atrás): Como se expuso
anteriormente, el algoritmo de backtracking es una técnica
recursiva que busca soluciones incrementando paso a
paso el valor de las variables involucradas en el problema
hasta que se cumplan todas las restricciones. Si en algún
momento se llega a una combinación de valores que viola
alguna restricción, el algoritmo retrocede y prueba otras
combinaciones posibles. Es útil cuando el espacio de
búsqueda no es demasiado grande.
Tipos
Algoritmos de propagación de restricciones: Estos
algoritmos se basan en la idea de propagar la
información sobre las restricciones
Sesión 4
UNIDAD 4. TEORÍA DE JUEGOS
Docente: Vidal Armas Torres

02 de agosto de 2023
4.1. Aplicaciones de la teoría de
juegos
Teoría de juegos
¿Qué es?
La teoría de juegos es una rama de las matemáticas y
de la economía que estudia la elección de la conducta
óptima de un individuo cuando los costes y los
beneficios de cada opción no están fijados de
antemano, sino que dependen de las elecciones de
otros individuos.
Teoría de juegos
Aplicaciones
La teoría de juegos tiene multitud de aplicaciones en
diferentes campos, destacando la ciencia económica,
ciencias políticas, biología evolutiva o incluso filosofía.
Economía y los negocios. Si bien entendemos por
economía, la ciencia social que estudia la forma de
administrar los recursos disponibles, esto de por sí ya
proporciona todos los ingredientes para un juego. Los
investigadores de esta rama de la teoría de juegos se han
centrado en estudiar los mercados de duopolio y oligopolio.
Teoría de juegos
Aplicaciones
Ciencias políticas teoría de Juegos no ha tenido el
mismo impacto en la ciencia política que en economía.
Tal vez esto se deba a que la gente se conduce menos
racionalmente cuando lo que está en juego son ideas
que cuando lo que está en juego es su dinero. Sin
embargo, se ha convertido en un instrumento
importante para clarificar la lógica subyacente de un
cierto número de problemas más paradigmáticos.
Teoría de juegos
Aplicaciones
Biología se ha utilizado ampliamente la teoría de
juegos para comprender y predecir ciertos resultados
de la evolución, como lo es el concepto de estrategia
evolutiva estable introducido por John Maynard Smith
en su ensayo «Teoría de Juegos y la evolución de la
lucha” Evolución de la Lucha», así como en su libro
«Evolución y Teoría de Juegos».
Teoría de juegos
Aplicaciones
Filosofía, la teoría de juegos puede demostrar que
incluso los individuos más egoístas, pueden descubrir
que en ocasiones, cooperar con otros puede redundar
en sus propios intereses.
4.2. Solución óptima de juegos entre
dos personas
Solución óptima de juegos entre dos personas
Pasos
• Utilice el procedimiento maximin para el jugador A y el procedimiento minimax para el jugador B
con el fi n de determinar si existe una solución de estrategia pura. (Consulte los pasos previos para
1 identificar una estrategia pura.) Si existe una estrategia pura, es la solución óptima.
• Si no existe una estrategia pura y el juego es mayor que 2 2, identifique una estrategia dominada
para eliminar una fila o columna. Elabore la tabla de resultados reducida y continúe con la
2 dominancia para eliminar el mayor número de filas y columnas posible.
• Si el juego reducido es 2 2, calcule las probabilidades de una estrategia mixta óptima posible. Si el
juego no se puede reducir a uno de 2 2, utilice un modelo de programación lineal para calcular las
3 probabilidades de estrategia mixta óptima.
4.3. Solución de juegos con
estrategias combinadas
Solución de juegos con estrategias
combinadas
Las estrategias mixtas son analizadas en la teoría de
juegos cuando hay muchos equilibrios posibles, lo cual
es especialmente el caso en los juegos de
coordinación. La guerra de los sexos es un ejemplo
común de un juego de coordinación en el que hay dos
equilibrios de Nash (subrayados en rojo abajo), lo que
significa que ningún equilibrio real puede ser
alcanzado.
combinadas
En la guerra de los sexos, una pareja discute sobre
qué hacer el fin de semana. Ambos saben que quieren
pasar el fin de semana juntos, pero no se ponen de
acuerdo sobre qué hacer. El hombre prefiere ir a ver un
combate de boxeo, mientras que la mujer quiere ir de
compras. Por tanto, la matriz de juego es como sigue:
combinadas
Vamos a suponer que la mujer
puede que elija el boxeo con
probabilidad q, e ir de compras
con probabilidad (1-q). Del mismo
modo, el puede que elija el boxeo
con una probabilidad de r, e ir de
compras con probabilidad (1-r). En
este caso, nuestros resultados son
los siguientes:
combinadas
Las posibilidades del hombre de
ir a un combate de boxeo (su
utilidad esperada) serán 2r (pago
multiplicado por la probabilidad) y,
de ir de compras, 1-r (porque la
utilidad derivada de ir de compras
es 1), por lo tanto r = 1/3.
combinadas
Análogamente, para la mujer, q =
2/3. Ahora ella debe analizar a que
equivale q (las posibilidades de
que el hombre valore de su propia
felicidad sobre la de ella). Si r>
1/3, irán a un combate de boxeo.
Si r = 1/3, cualquiera podría
suceder, y si r <1/3, irán de
compras.
combinadas
Tanto la mujer como el hombre deben
analizar esto con cuidado ya que, si se
equivocan en la valoración de la
probabilidad, puesto que esto sigue
siendo un juego simultáneo y no hay
segundas oportunidades, podrían
terminar pasando el fin de semana en
diferentes sitios, lo que significaría
menos utilidad para ambos.
4.4. Solución de juegos por medio
de programación lineal
Solución de juegos por medio de
programación lineal
En un juego de suma cero, la programación lineal se
utiliza para encontrar las estrategias.
La teoría de juegos tiene una fuerte relación con la
programación lineal debido a que un juego de suma
cero entre dos personas se puede expresar como un
programa lineal y viceversa
Equivalencia entre la teoría de juegos y la
programación lineal: Existe una equivalencia entre la
teoría de juegos y la programación lineal. Esto significa
que un juego de suma cero entre dos jugadores se
puede expresar como un programa lineal y viceversa.
Esta equivalencia permite utilizar técnicas de
programación lineal para resolver juegos y obtener
soluciones óptimas.
Resolución de juegos de estrategias mixtas: Los
juegos de estrategias mixtas son aquellos en los que
los jugadores eligen sus estrategias de manera
probabilística. Estos juegos se pueden resolver
mediante programación lineal. Se puede formular un
modelo de programación lineal para determinar las
estrategias óptimas de los jugadores y encontrar el
valor del juego
Técnicas de programación lineal para resolver juegos:
Existen varias técnicas de programación lineal que se
pueden utilizar para resolver juegos, como el método
simplex, el método dual y la técnica M. Estas técnicas
permiten encontrar soluciones óptimas para los juegos
y determinar las estrategias óptimas de los jugadores.

Semana 4 Optprocesos

Cargado por

Copyright:

Formatos disponibles

Semana 4 Optprocesos

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Semana 4 Optprocesos

Cargado por

Copyright:

Formatos disponibles

Sesión 4

UNIDAD 3. PROGRAMACIÓN NO LINEAL

Docente: Vidal Armas Torres

UNIDAD 4. TEORÍA DE JUEGOS

Docente: Vidal Armas Torres

También podría gustarte