Usted puede probar la Birkhoff-von Neumann teorema directamente con la programación lineal. Dependiendo de su gusto, se trata de una elegante manera de probar que el resultado. Básicamente, hay dos maneras - para utilizar las condiciones para un vértice de un polytope dado por las restricciones para demostrar que una doblemente estocástica de la matriz, la cual es un vértice de la Birkhoff polytope debe tener una fila o columna con sólo uno distinto de cero de la entrada, entonces inducen. Esto no utilizan la totalidad de la "teorema fundamental de la programación lineal".
El otro enfoque es observar que en un vértice de un conjunto de dimensiones lineales objetivos para los que el vértice es la óptima, formular el programa doble y, a continuación, mostrar que el 2n sin restricciones de doble variables mentira en un espacio de dimensión n; holgura complementaria, a continuación, muestra que la principal variable tiene sólo n distinto de cero elementos, el doble de la estocasticidad garantiza debe haber uno en cada fila, en cada columna, y cada uno debe ser la unidad - por lo tanto, una matriz de permutación. Obviamente este enfoque realmente hace explotar el lineal de la estructura del programa, si es que eso es lo que quieren enseñar.
Se me ocurrió esto a mí mismo, así que no sé de una referencia real, pero no debe ser esa novela.
También puede probar Birkhoff-von Neumann son un max de flujo/min corte teorema (que es bastante conocido) pero no me parece que igual de elegante. Sin embargo, si usted está haciendo hincapié max flujo/min corte frente a la programación lineal de la estructura, entonces usted puede ser que desee hacer que uno.
