Метод искусственного базиса

Если ограничения ЗЛП можно преобразовать к виду AX £ A ₀ при А ₀³0, то система ограничений всегда содержит единичную матрицу. Многие ЗЛП, имеющие решения, не содержат единичной матрицы и не приводятся к указанному виду. В этом случае для решения задач применяется метод искусственного базиса. Рассмотрим общую ЗЛП.

Найти минимальное значение линейной функции Z = C ₁ x ₁ + C ₂ x ₂ +... + C_nx_n при ограничениях

где b_i ³ 0 и система ограничений не содержит единичной матрицы. Для получения единичной матрицы к каждому равенству прибавим по одной переменной х_n+i ³ 0 (i =1,2,..., m), которые назовем искусственными, и рассмотрим расширенную задачу, связанную с отысканием наименьшего значения линейной функции при ограничениях

Величина М предполагается достаточно большим положительным числом, если задача решается на отыскание минимального значения линейной функции, и достаточно малым отрицательным числом, если находится максимальное значение линейной функции. Единичные векторы A _{n +1}, A _{n +2},..., A _n+m, соответствующие искусственным переменным, образуют искусственный базис.

Основные понятия теории игр

Теория игр представляет собой математическую теорию конфликтных ситуаций. Ее цель — выработка рекомендаций по разумному поведению участников конфликта.

Конфликтными называются ситуации, в которых сталкиваются интересы двух (или более) сторон, преследующих разные (иногда противоположные) цели, причем выигрыш каждой стороны зависит от того, как себя поведут другие.

Каждая непосредственно взятая из практики конфликтная ситуация очень сложна и ее анализ затруднен наличием многих несущественных факторов. Чтобы сделать возможным математический анализ конфликта, строится его математическая модель. Такую модель называют игрой. От реального конфликта игра отличается тем, что ведется по определенным правилам.

конфликтующие стороны условно называются игроками, одно осуществление игры — партией, исход игры — выигрышем или проигрышем.

В игре могут сталкиваться интересы двух или более участников; в первом случае игра называется парной, во втором — множественной.

Ходом называется выбор игроком одного из предусмотренных правилами игры действий и его осуществление. Ходы бывают личные и случайные. При личном ходе игрок сознательно выбирает и осуществляет тот или другой вариант действий (пример — любой ход в шахматах). При случайном ходе выбор осуществляется не волей игрока, а каким-то механизмом случайного выбора

Цель — оптимизация поведения игрока в игре, где (может быть, наряду со случайными) есть личные ходы. Такие игры называются стратегическими.