Restricciones de una u otra (I)

Considérese el importante caso en el que se debe elegir entre dos restricciones, de manera que sólo una se tiene que cumplir. Por ejemplo, puede existir la opción de usar uno de dos tipos de recursos para un cierto propósito, de manera que nada más una de las restricciones  de disponibilidad de estos recursos se cumpla matemáticamente. Para ilustrar este tipo de situaciones, supóngase que uno de los requerimientos en el problema completo es que

puesto que al agregar M al lado derecho de una restricción se obtiene el efecto de eliminarla, ya que cualquier solución que satisfaga las otras restricciones del problema automáticamente cumplirá está. (Dicha formulación supone que el conjunto de soluciones factibles del problema completo es un conjunto acotado y que M es lo suficientemente grande para que no elimine ninguna de esas soluciones factibles.) Esta formulación es equivalente al conjunto de restricciones

Otras posibilidades de formulación con variables binarias

Se acaba de presentar un ejemplo prototipo en el que las decisiones básicas del problema son del tipo sí o no, por lo que se introdujeron variables binarias para representarlas. Las variables binarias pueden también ser muy útiles en el caso de la formulación de problemas difíciles, de modo que se puedan manejar con facilidad. En particular, estas variables a veces permiten tomar un problema cuya formulación no se puede manejar y reformularlo como un problema de programación entera pura o mixta.

Este tipo de situación surge cuando la formulación original del problema se ajusta a un problema de programación entera o a uno de programación lineal, excepto por cierta diferencias menores que incluyen relaciones combinatorias en el modelo. Al expresar estas relaciones en términos de preguntas cuya respuesta debe ser sí o no, se pueden introducir variables binarias auxiliares en el modelo que representan  estas decisiones de sí o no. Al introducir estas variables el problema de reducir a uno de programación entera mixta (o pura si toda las variables originales también estan restringidas a valores enteros).

En seguida se presentan algunos casos que se pueden formular con este enfoque, en donde las xj denotan las variables originales del problema (pueden ser variables continuas o enteras), y las yi denotan las variables auxiliares introducidas para la reformulación.

Programación Entera: Ejemplo Prototipo (III)

Excepto por su tamaño pequeño, este ejemplo representa muchas aplicaciones reales de programación entera en las que las decisiones básicas que se toman son del tipo sí o no. Al igual que los dos pares de decisiones de este ejemplo, muchos grupos de decisiones sí o no constituyen grupos de alternativas mutuamente excluyentes tales que sólo una decisión de ese grupo  puede ser sí. Cada grupo requiere una restricción que obligue a la suma de las variables binarias correspondientes a ser = 1 (si exactamente una decisión de ese grupo de ser si) o   ≤ 1 (si cuando mucho una decisión en ese grupo puede ser sí). En ocasiones , las decisiones del tipo si o no son decisiones contingentes, es decir, que dependen de decisiones previas. En particular se dice que una decisión es contingente sobre otra si se permite que sea sí sólo si la otra es sí. Esta situación ocurre cuando una decisión contingente implica una acción que sigue a otra y que se vuelve irrelevante, y a veces imposible, si la otra decisión es no. La forma que toma siempre la restricción que resulta es la que se ilustra en la cuarta y quinta restricciones del ejemplo.

Programación Entera: Ejemplo Prototipo (II)

Como las últimas dos decisiones representan alternativas mutuamente excluyentes (la compañia quiere construir sólo un almacén nuevo), se necesita la restricción

x3 + x4 ≤ 1

Lo que es más, las decisiones 3 y 4 son decisiones contingentes porque se toman como resultado de las decisiones 1 y 2, respectivamente (la compañia consideraría la construcción de un almacén en una ciudad sólo si la nueva fábrica va a estar ahí). Esta contingencia se toma en cuenta mediante las restricciones:

Programación Entera: Ejemplo Prototipo (I)

La CALIFORNIA MANUFACTURING COMPANY ha decidido ampliarse mediante la construcción de una nueva fábrica ya sea en Los Angeles o en San Francisco. También está pensando en construir un nuevo almacén en aquella ciudad que se elija para la nueva fábrica. En la cuarta columna de la tabla 13.1 se muestra el valor presente neto (beneficio total que toma en cuenta el valor del dinero en el tiempo) de cada alternativa. La última columna da el capital requerido para las respectivas inversiones, en donde el capital total disponible es de $10 000 000. El objetivo es encontrar la combinación factible de alternativas que maximice el valor presente neto total.

Aun cuando este problema es tan pequeño que se puede resolver rápido por simple inspección (construir fábricas en ambas ciudades pero ningún almacén), se formulará el modelo de programación entera con propósitos ilustrativos. Todas las variables de decisión tienen forma binaria.

Programación Entera (III)

Con sólo dos posibilidades, este tipo de decisiones se puede representar mediante variables de decisión restringidas a sólo dos valores, por ejemplo cero y uno. Así, la j-ésima decisión sí o no se puede representar por xj, tal que

LAs variables de este tipo se llaman variables binarias (o variables 0-1). En consecuencia, algunas veces se hace referencia a los problemas de programación entera que contienen sólo variables binarias como problemas de programación entera binaria (PEB) (o problemas 0-1 de programación entera).

La sección 13.1 presenta una versión miniatura de un problema representativo de PEB. En la sección 13.2 se estudian otras posibilidades de formulación. El resto de las secciones se dedican a analizar las maneras de resolver los problemas de PE, incluyendo los de PEB y los de PEM.

Programación Entera (II)

Por ejemplo, el problema de la Wyndor Glass Co. que se presentó en la sección 3.1 habría sido en realidad un problema de programación entera, si las dos variables de decisión x1 y x2 hubieran representado el número total de unidades que se debían producir de los respectivos artículos 1 y 2, en lugar de las tasas de producción. Como ambos productos (puertas de vidrio y ventas con marco de madera) tienen que ser unidades completas, x1 y x2 tendrían que estar restringidas a valores enteros.

Se han desarrollado numerosas aplicaciones de programación entera en las cuales existe una extensión directa de programación lineal en la que debe eliminarse la suposición de divisibilidad. Sin embargo, existe otra área de aplicación que puede ser de mayor importancia e incluye un cierto número de "decisiones sí o no" interrelacionadas. En las decisiones de este tipo, las únicas dos elecciones posibles son sí o no. Por ejemplo, debe emprenderse un proyecto fijo específico? Debe hacerse una inversión fija específica? Se debe localizar una instalación en un sitio en particular?

Programación Entera (I)

En la parte dos se estudiaron muchos ejemplos de aplicaciones distintas de programación lineal. Como se pudo ver, una limitación importante que impide muchas otras aplicaciones es la suposición de divisibilidad, que dice que las variables de decisión pueden tomar valores no enteros. En muchos problemas prácticos, las variables de decisión sólo tienen un sentido real si su valor es entero. Por ejemplo, con frecuencia es necesario asignar personas, máquinas o vehículos a las actividades, en cantidades enteras. Si el hecho de exigir valores enteros es la única diferencia que tiene un problema con al formulación de programación líneal, entonces se trata de un problema de programación entera (PE). (El nombre completo es programación lineal entera, pero por lo general el adjetivo lineal se deja fuera, excepto cuando se hace una comparación con el problema más esotérico de programación no lineal entera que está más allá del alance de este blog.)

El modelo matemático para programación entera es sencillamente el modelo de programación líneal con la restricción adicional de que las variables deben tener valores enteros. Si sólo es necesario que algunas de las variables tengan valores enteros ( y la suposición de divisbilidad se cumple para el resto), el modelo, es de programación entera mixta (PEM). Cuando se hace la distinción entre un problema con todas las variables enteras y este caso mixto, el primero se llama de programación entera pura.

Conclusiones de Teoría de Juegos

El problema general de cómo tomar una decisión en un medio competitivo es bastante común e importante. La contribución fundamental de la teoría de juegos es que propociona un maro conceptual básico para formular y analizar tales problemas en situaciones simples. Sin embargo, existe un gran abismo entre lo que la teoría puede manejar y la complejidad de la mayor parte de las situaciones de competencia que surgen en la práctica. Así, las herramientas conceptuales de la teoría de juegos por lo general desempeñan un papel suplementario cuando se aplican a estas situaciones.

Dada la importancia general del problema, la investigación sobre este tema pretende extender la teoría a casos más complejos, y continúa con algunos éxitos.

Extensiones (III)

Otra extensión más es la que se llama de juegos infinitos, en donde los jugadores cuentan con un número finito de estrategias puras. Estos juegos están diseñados para aquellas situaciones en las que la estrategia seleccionada se puede representar por una variable continua. Por ejemplo, la variable de decisión puede ser el tiempo en el que se lleva a cabo cierta acción, o la proporción de recursos propios que se asignan a cierta actividad, en una situación de competencia. En los últimos años una gran parte de la investigación se ha concentrado en este tipo de juegos.

El análisis que se requiere en estas extensiones del juego finito de dos personas y suma cero, es relativamente complejo y no se profundizará en él.

Extensiones (II)

Otra generalización es el juego de suma no cero, en el que la suma de los pagos a los jugadores no tiene que sumar cero (o ninguna otra constante fija). Este caso refleja el hecho de que muchas situaciones de competencia incluyen aspectos no competitivos que contribuyen a la ventaja o desventaja mutua de los jugadores. Por ejemplo, las estrategias de publicidad para compañias que compiten por un mismo mercado pueden afectar no sólo la división de ese mercado sino también el tamaño total del mercado que comparte sus productos. Como es posible la ganancia mutua, los juegos de suma no cero se subdividen en términos del grado en que se permite que los jugadores cooperen. En un extremo se encuentran el juego no cooperativo, en donde no hay comunicación anterior al juego entre los jugadores. En el otro ejemplo está el juego cooperativo en el que se permiten discusiones y acuerdos antes del juego. Ejemplos que se podrían formular como juegos cooperativos son las situaciones competitivas que engloban leyes de comercio exterior entre países o los acuerdos que se toman entre patrones y obreros. Cuando existen más de dos jugadores, los juegos competitivos permiten también que se formen coaliciones entre algunos o todos los jugadores. 

Extensiones (I)

Aunque en este capítulo se han considerado sólo los juegos de dos personas con suma cero con un número finito de estrategias puras, sería incorrecto concluir que la teoría de juegos se limita a este tipo de juegos. De hecho, se han llevado a cabo investigaciones extensas sobre varios tipos de juegos más complicados, que incluyen los que se resumen en esta sección.

Uno de estos tipos es el juego de n personas, en el que pueden participar más de dos jugadores. Esta generalización es de particular importancia porque en muchos casos de situaciones competitivas, suelen existir más de dos competidores, como en la competencia entre las empresas de negocios, en la diplomacia internacional, etc. Desafortunadamente, la teoría existente para tales juegos es menos satisfactoria que la disponible para juegos de dos personas.

Solución mediante programación lineal (IX)

Como ya se había encontrado la estrategia mixta óptima para el jugador II cuando se resolvió el primer modelo, no era necesario resolver el segundo; en general, siempre se pueden encontrar las estrategias mixtas óptimas para ambos jugadores con sólo elegir uno de los modelos (cualesquiera) y usar el método símplex para obtener tanto la solución óptima como la solución óptima dual.

Los dos modelos suponen que v ≥ 0. Si esta suposición se violara ninguno de los dos modelos tendría soluciones factibles, y el método símplex se detendría rápidamente con el mensaje. Para evitar este riesgo, se pudo haber agregado una constante positiva, como 3 (el valor absoluto del elemento más negativo), a todos los elementos de la tabla 12.6. ESto habría aumentado en 3 todos los coeficientes de x1, x2, y1, y2 y y3 en las restricciones de los dos modelos.

Solución mediante programación lineal (VIII)

A manera de ilustración, considérese de nuevo la variación 3 del problema de la campaña política después de eliminar la estrategia denominada 3 para el jugador I. Como existen algunos elementos negativos en la matriz de pagos reducida, no es evidente si el valor del v es no negativo (ocurre que sí lo es). Por el momento, supóngase que v ≥ 0 y procádase sin hacer ninguno de los ajustes mencionados. Para escribir el modelo de programacion lineal que se mostró antes para el jugador I, obsérvese que pij es el elemento del renglón i y la columna j de la tabla 12.16, para i = 1,2 y j = 1,2,3. Empleando maximizar x(m+1) en lugar de la forma equivalente de minimizar (-xm+1) con m=2 y n =3,el modelo que se obtiene es

Solución mediante programación lineal (VII)

Queda un cabo suelto por atar, a saber, cómo proceder si x(m+1) y (yn+1) no están restringidas en signo en sus formulaciones de programación lineal. Si es evidente que v ≥ 0 para que los valores óptimos de x(m+1) y y(n+1) sean no negativos, entonces no hay peligro si se introducen las restricciones de no negatividad sonbre estas variables con el propósito de aplicar el método símplex. No obstante, si v < 0, entonces debe hacerse un ajuste. Una posibilidad es emplear el enfoque descrito en la sección 4.6 en el que se sustituye una variabe no restringida por la diferencia de dos variables no negativas. Otra posibilidad es invertir a los jugadores I y II para que la matriz de pagos se reescriba como el pago al jugador II original, lo que haría que el valor correspondiente de v fuera positivo. Un tercer procedimiento, y el más usado, es agregar una constante fija grande a todos los elementos de la matriz de pagos para que el nuevo valor de juego sea positivo. (Por ejemplo, bastaría con igualar esta constante al valor absoluto del elemento más negativo) Como la misma constante se agrega a todos los elementos, este ajuste no puede alterar de ninguna manera las estrategias mixtas óptimas, y por lo tanto ahora éstas se pueden obtener en forma normal. El valor incluido del juego se aumentará en la cantidad constante, pero se puede reajustar después de obtener la solución.

Solución mediante programación lineal (VI)

Una consecuencia de esto es que proporciona una prueba muy sencilla del teorema minimax.

Solución mediante programación lineal (V)

Obsérvese el importante hecho de que este problema de programación lineal y el obtenido para el jugador I son duales uno del otro en el sentido descrito en las secciones 6.1 y 6.4 (En particular, este problema está en la forma dada para el problema primal y del jugador I es el correspondiente al problema dual). Este hecho tiene varias implicaciones importantes. Una es que se pueden encontrar las estrategias mixtas óptimas para los dos jugadores al resolver sólo uno de los problemas de programación lineal puesto que la solución óptima dual es un producto complementario automático de los cálculos del método símplex para encontrar la solución óptima primal. Una segunda implicación es que esto trae consigo toda la teoría de dualidad (descrita en el capítulo 6) para fundamentar en ella la interpretación y el análisis de los juegos.

Solución mediante programación lineal (IV)

(La función objetivo y la restricción de igualdad se rescribieron en una forma equivalente porque más tarde se aplicarán así.) Nótese que x(m+1) no está restringida a ser no negativa, mientras que el método símplex sólo se puede aplicar una vez que todas las variables tengan la restricción de no negatividad. Este asunto se puede resolver con facilidad como se verá en seguida.

Ahora considérese  al jugador II. Él puede encontrar su estrategia óptima mixta si se reescribe la matriz de pagos como los pagos a sí mismo en lugar de al jugador I y si después se procede justo como se acaba de describir. Sin embargo, resulta ilustrativo resumir su formulación en términos de la matriz de pagos original. Si se sigue un procedimiento análogo al descrito, el jugador II concluiría que su estrategia mixta óptima está dada por la solución óptima del problema de programación lineal:

Solución mediante programación lineal (III)

En consecuencia, el problema de encontrar una estrategia mixta óptima se ha reducido a encontrar una solución factible para un problema de programación líneal, lo que se puede hacer según lo descrito en el capitulo 4. Las dos dificultades que quedan por resolver son: 1) se desconoce v, y 2) el problema de programación lineal no tiene función objetivo. Por fortuna, ambos obstáculos se pueden salvar al mismo tiempo sustituyendo la constante desconocida v por la variable x(m+1) y después maximizando x(m+1), de manera que automáticamente x(m+1) será igual a v (por definición) en la solución óptima del problema de programación lineal.

Para resumir, el jugador 1 encontrará su estrategia mixta óptima empleando el método simplex para resolver el problema de programación lineal.

y xi ≥ 0 para i = 1,2......,m

Solución mediante programación lineal (II)

Ya que la implicación va en ambas direcciones, se concluye que imponer este conjunto de n desigualdades lineales es equivalente a requerir que la desigualdad original se cumpla para todas las estrategias (y1,y2,.......yn). Pero estas n desigualdades son restricciones válidas en programación lineal, como lo son las restricciones adicionales.

x1 + x2 + ...........+ xm  =1
                              xi    ≥ 0, para i =1,2,......,m


que se necesitan para asegurar que las x1 sean probabilidades. Por esta razón, cualquier solución (x1,x2,........xm) que satisfaga este conjunto completo de restricciones de programación lineal es la estrategia mixta óptima deseada.

Solución mediante programación lineal (I)

Cualquier juego de estrategias mixtas se puede resolver en forma muy sencilla transformándolo en un problema de programación lineal. Como se verá, esta transformación requiere apenas un poco más que la aplicación del teorema minimax y el uso de la definición de valor maximin v y valor minimax v.

Primero, considérese cómo se encuentra la estrategia mixta del jugador 1. Comos e indicó en la sección 12.3

Procedimiento de solución gráfica (VII)

Si en algún otro problema, ocurre que más de dos líneas pasan por el punto maximin, de manera que más de dos líneas y*j pueden ser mayores que cero, habría muchos empates para la estrategia mixta óptima del jugador II. Una de estas estrategias se puede identificar al igualar arbitrariamente todas menos dos de estas yj* a cero y resolver las dos restantes como se acaba de describir.

Si bien este procedimiento gráfico se ejemplificó para un problema en particular, se puede usar esencialmente el mismo razonamiento para resolver cualquier juego con estrategias mixtas que tenga sólo dos estrategias puras no dominadas para uno de los jugadores.

Procedimiento de solución gráfica (VI)

Pero y*2 y y*3 son números y entonces el lado derecho es la ecuación de una línea recta lo cual es un peso ponderado fijo de las dos líneas "de abajo" de la gráfica. Como la ordenada de esta línea debe ser igual a 2/11 en el punto x1 = 7/11 y como nunca debe exceder 2/11, la línea necesariamente es horizontal. (esta conclusión siempre es valida a menos que el valor óptimo de x1 sea cero o 1, en cuyo caso el jugador II también debe usar una sola estrategia pura.) como resultado.

Procedimiento de solución gráfica (V)

En consecuencia, y1* = 0, ya que y1* > 0 violaría la penúltima ecuación; es decir, en la gráfica, el pago esperado en el punto x1= 7/11 estaría por encima del punto maximin.(en general, a cualquier línea que no pasa por el punto maximin se le debe asignar un peso de cero para evitar un aumento en el pago esperado más allá de este punto.)

Entonces,

Procedimiento de solución gráfica (IV)

Para encontrar la estrategia mixta óptima correspondiente para el jugador II, el razonamiento es el siguiente. De acuerdo con la definición de valor minimax v y el teorema minimax, el pago esperado que resulta de esta estrategia (y1, y2, y3) =(y1*, y2*, y3*) tendrá que satisfacer la condición.

Procedimiento de solución gráfica (III)

Así, dado x1, el pago esperado mínimo está dado por el punto correspondiente en la "parte anterior" de la recta. De acuerdo al criterio minimax (o maximin), el jugador I debe elegir el valor de x1 que da el mayor pago esperado mínimo, de modo que

Procedimiento de solución gráfica (II)

Ahora se grafican estas rectas del pago esperado, como se muestra en la figura 12.1. Para cualquier valor dado de x1 y de (y1, y2, y3), el pago esperado será el promedio ponderado apropiado de los puntos correspondientes a estas tres rectas. En particular.

Procedimiento de solución gráfica (I)

Considérese cualquier juego con estrategias mixtas tal que después de eliminar las estrategias dominadas, uno de los jugadores tiene sólo dos estrategias puras. Para ser específico, sea éste el jugador I. Como sus estrategias mixtas son (x1, x2) y x2 = 1-x1, nada más debe obtener el valor óptimo de x1. Es directo y sencillo hacer la gráfica del pago esperado como una función de x1, para ada una de las estrategias de su oponente. ESta gráfica se puede usar para identificar el punto que maximiza el mínimo pago esperado. También es posible identificar en ella la estrategia mixta minimax del oponente.

Para ilustrar este procedimiento, considérese la variación 3 del problema de la campaña política. Nótese que la tercera estrategia pura del jugador I está dominada por la segunda, por lo que la matriz de pagos se puede reducir a la forma dada en la tabla 12.6. Entonces, para cada estrategia pura de que dispone el jugador II, el pago esperado para el jugador I será:

Juegos con estrategias mixtas (V)

Aunque el concepto de estrategias mixtas se vuelve bastante intuitivo si se juega repetidas veces, si requiere una interpretación cuando sólo se va a jugar una vez. En este caso, el uso de una estrategia mixta todavía implica elegir y usar una estrategia pura (elegida aleatoriamente a partir de una distribución de probabilidad específica), y podría parecer más sensato ignorar este proceso de aleatorización y sólo escoger la "mejor" estrategia pura. Sin embargo, ya se ilustró en la variación 3 de la sección anterior que un jugador no puede permitir que su oponente deduzca cuál será su estrategia (es decir, el procedimiento de solución bajo las reglas de teoría de juegos no debe identificar de manera definitiva la estrategia pura que se usará , cuando el juego es inestable.) Lo que es más, aun cuando el oponente pueda usar sólo su conocimiento de las tendencias del primer jugador para deducir probabilidades (para la estrategia pura elegida) que sean distintas a las de estrategia mixta óptima, todavía puede aprovechar este conocimiento para reducir el pago esperado para el primer jugador. Lo que es más, aun cuando el oponente pueda usar sólo su conocimiento de las tendencias del primer jugador para deducir las probabilidades (para la estrategia pura elegida) que son diferentes de aquellas para la estrategia mixta óptima, de todas las formas podría tomar ventaja de este conocimiento para reducir el pago esperado del primer jugador. Así pues, la única manera de garantizar que se logre el pago esperado óptimo v, es elegir aleatoriamente la estrategia para que debe usarse, a partir de la distribución de probabilida para la estrategia óptima.

Ahora se mostrará cómo se encuentra la estrategia mixta óptima para cada jugador. Se dispone de varios métodos. Uno es un procedimiento  gráfico que se puede usar siempre que uno de los jugadores tenga sólo dos estrategias puras (no dominadas); este enfoque se describe en la siguiente sección. cuando se trata de juegos más grande, el método más empleado consiste en transformar el problema en uno de programación lineal que se puede resolver por el método símplex en una computadora; la sección 12.5 analiza este enfoque.

Teorema minimax

Si se permiten estrategias mixtas, el par de estrategias que es óptimo de acuerdo con el criterio minimax proporciona una solución estable con v = V = v (el valor del juego), de manera que ninguno de los dos jugadores puede mejorar cambiando unilateralmente su estrategia.

Juegos con estrategias mixtas (IV)

Al usar esta medida, la teoría de juegos puede extender el concepto del criterio minimax a juegos que no tienen punto silla y que, por tanto, necesitan estrategias mixtas. En este contexto, el criterio minimax dice que un jugador debe elegir la estrategia mixta que minimice la máxima perdida esperada para sí mismo. De manera equivalente, si se analizan los pagos (jugador I) en lugar de las pérdidas (jugador II), este criterio es maximin, es decir, maximizar el pago esperado mínimo para el jugador. Por pago esperado mínimo se entiende el pago esperado mas pequeño posible que puede resultar de cualquier estrategia mixta con la que el oponente puede contar. ASí, la estrategia mixta para el jugador I que, de acuerdo con este criterio, es óptima y es la que proporciona la garantía (el mínimo pago esperado) de que es la mejor (máxima). (El valor de esta mejor garantía es el valor maximin y se denota por v.) De manera análoga, la estrategia óptima para el jugador II es la que proporciona la mejor garantia, en donde mejor significa mínima y garantía se refiere a la máxima perdida esperada que puede lograrse con cualquiera de las estrategias mixtas del oponente. (La mejor garantia es el valor minimax que se denota por V.)

Recuérdese que cuando sólo se usan estrategias puras, resulta que los juegos que no tienen punto silla son inestables (sin soluciones estables). La razón esencial es que v <V, por lo que los jugadores quieren cambiar sus estrategias para mejorar su posición. De manera parecida, en los juegos con estrategias mixtas es necesario que v = V  par que la solución óptima sea estable. Por fortuna, según el teorema minimax de la teoría de  juegos, esta condición siempre se cumple para estos juegos.