WikiSort.ru - Программирование

Лемма Фаркаша — утверждение о свойствах линейных неравенств. Была сформулирована и доказана Дьюлой Фаркашем. Применяется в геометрическом программировании.

Формулировка

Пусть ${\displaystyle f_{1}(x),f_{2}(x),...,f_{r}(x)}$ и ${\displaystyle g(x)}$ - однородные линейные функции ${\displaystyle m}$ переменных ${\displaystyle x_{1},x_{2},...,x_{m}}$ .

Предположим, что соотношения ${\displaystyle f_{1}(x)\geqslant 0,f_{2}(x)\geqslant 0,...,f_{r}(x)\geqslant 0,}$ влекут за собой неравенство ${\displaystyle g(x)\geqslant 0}$ .

Тогда существуют неотрицательные постоянные ${\displaystyle y_{1},y_{2},...,y_{r}}$ , такие, что ${\displaystyle y_{1}f_{1}(x)+y_{2}f_{2}(x)+...+y_{r}f_{r}(x)\equiv g(x)}$ является тождеством.

Предполагается, что все постоянные и переменные вещественны.

Доказательство

Доказательство есть в книге ^[1].

Примечания

Литература

• Р. Даффин, Э. Питерсон, К. Зенер. Геометрическое программирование. — М.: Мир, 1972. — 311 с.