Системы линейных неравенств. Зоркальцев В.И - 76 стр.

       5.1 Двойственные задачи линейного программирования
    Задача оптимизации, у которой целевая функция и все функции в
ограничениях     линейные,      называется     задачей     линейного
программирования. Такие задачи имеют большое самостоятельное
прикладное значение. В этом виде представляются многие экономические
модели [2]. При этом теория линейного программирования служит в
качестве основы для           многих классов задач нелинейного
программирования, у которых целевая функция и ограничения могут
быть нелинейными.
    Теория двойственности линейного программирования представлена
во многих учебниках по линейному программированию (например, [7]).
Это наиболее развитая часть теории оптимизации. Одна из целей данного
раздела состоит в том, чтобы продемонстрировать возможность
компактного и более полного, чем обычно делается во многих учебниках
по линейному программированию, изложения теории двойственности в
линейной оптимизации на базе теорем об альтернативных системах
линейных неравенств.
    Будем рассматривать две задачи линейного программирования:
                        c Τ x → min, x ∈ X ,                             (1)
                        b Τu → max, u ∈U ,                               (2)
где c ∈ R n , b ∈ R m , А – матрица m × n . Эти задачи тесно взаимосвязаны и
называются взаимно-двойственными.
     Множества
                            X = {x ∈ R n : Ax = b, x ≥ 0}
                           U = {u ∈ R m : g (u ) ≡ c − AΤ u ≥ 0}
 составляют допустимые решения задач (1), (2). Множества оптимальных
решений этих задач обозначим
              X = Arg min{c Τ x : x ∈ X } , U = Arg max{bΤu : u ∈U } .   (3)
    Введем функцию от векторов x ∈ R n , u ∈ R m
                              f ( x, u ) = c Τ x − b Τ u .               (4)
    Задание 1. Доказать, что для любых ( x, u ) ∈ R n × R m при условии
Ax = b выполняется равенство
                              f ( x, u ) = ∑ x j g j (u ) .              (5)
    Введем множества рецессивных направлений задач линейного
программирования (1), (2):
                       ~
                       X = {s ∈ R n : As = 0, s ≥ 0, c Τ s < 0} ,



                                         76