Cтраница 4
Основным методом нахождения оптимума экономической функции линейной программы является симплексный метод, или метод, предложенный Данцигом. Учитывая глубокую связь между теорией линейного программирования и теорией игр ( или, как ее иногда называют, теорией стратегических игр), нельзя не упомянуть также фон Неймана и его последователей. [46]
Для этих новых весов [ nt, Кг ] новый специальный остовный подграф графа G2 изображен на рис. 12.24. После введения нового ребра ( z12, zn) альтернирующее дерево на рис. 12.22 становится аугментальным, так что новое ребро входит в паросочетание. В любом случае ребро ( х9, xw) сразу же попадает в паросочетание и получается совершенное паросочетание. Так как в соответствии с теорией линейного программирования максимум величины z из (12.11) равен минимуму величины и из (12.16), то можно сделать проверку. [47]
В теории автоматического опознания образов иногда представляется целесообразным обращаться к наиболее наглядной форме - геометрической форме представления тех или иных процессов. Но обычного трехмерного пространства недостаточно для этих представлений, так как число параметров, которые должны быть отложены по осям координат, значительно более трех. В математической физике, а позднее и в теория линейного программирования, и в теории конечных автоматов стали рассматривать абстрактные пространства многих измерений. Это оказалось очень удобным, так как аналитические выражения, характеризующие те или иные построения, совпадают по форме и для двухмерного, и для трехмерного, и для четырехмерного и, вообще, для / г-мерного пространства. [48]
Вторая глава начиналась с утверждения о том, что, хотя метод исключения и дает способ для решения системы Ах Ь, возможен другой и более глубокий подход. То же самое справедливо и для линейного программирования. Механика симплекс-метода позволяет решить линейную программу, но центром теории линейного программирования является идея двойственности. Это красивая идея, и в то же время она очень важна для приложений. [49]
Приведенные достаточные признаки оптимальности в действительности являются также и необходимыми. Однако доказательство этого факта требует применения более тонких методов анализа. Соответствующий результат устанавливается ниже как одно из следствий основной теоремы теории линейного программирования. [50]