Конечные бескоалиционные игры и равновесия. Матвеев В.А. - 82 стр.

форме задачи линейного программирования. Такая задача отличается
от (8.1) – (8.3) тем, что ограничения в форме неравенств из (8.2)
представляются в форме равенств. Задача линейного
программирования в канонической форме имеет вид
      f ( x) = c1 x1 + ... + c m+1 x m +1 + ... +c m + n x m + n → max;           (10.1)
     ai1 x1 + ... + aim +1 x m +1 + ... + a im + n x m + n = bi , i = 1,..., n,   (10.2)
     x j ≥ 0, j = 1,..., m + n.                         (10.3)
Будем считать, что числа bj, j = 1,…,n неотрицательны. Если это
не так, то умножим равенство из (10.2) на –1. Переход от
стандартной формы к канонической форме можно осуществлять
следующим образом.
    Пусть задана задача (8.1) – (8.3), значит m определено.
Перейдём к (10.1) – (10.3) по формулам
                               c m +t = 0, t = 1,..., n,
                     aim +t = 1, если i = t ,           i, t = 1,..., n
                              aim +t = 0, если i ≠ t.
     В этом случае условие (10.3) выполнено. Формально,
получили задачу (10.1) – (10.3). Область допустимых решений в
задаче (8.1) – (8.3) есть множество X ⊂ Rm , в задаче (10.1) – (10.3)
это множество Y ⊂ R m+n . Вообще говоря, X ≠ Y, но из
определения коэффициентов в (10.1) – (10.3) следует, что
проекция множества Y на пространство R m совпадает с
множеством X. В этом смысле задачи (8.1) – (8.3) и (10.1) – (10.3)
равносильны.
      Определим первоначальное допустимое решение задачи
(10.1) – (10.3). Нетрудно видеть, что таким решением будет
x(0) = (0, …, 0, b1 , …, bn) ∈ Y ⊂ Rm+n, что соответствует нулевому
решению задачи (8.1) – (8.3).
      Выполним проверку на оптимальность. Если для (10.1)
выполнены условия cj ≤ 0, j = 1,…,m+n, то x(0) = (0, …, 0, b1, …, bn)
является оптимальным решением. Если в (10.1) найдётся сj* > 0 и
все a ij* ≤ 0, i = 1,…,n, то x (0) = (0, …, 0, b 1 , …, b n ) является
                                                                                       82