Теорема Минковского.

В теории линейных неравенств одной из основных является следующая теорема.

ТЕОРЕМА 1.7. Пусть неравенство

есть следствие системы

Тогда

Доказательство (проводится индукцией по . Теорема верна при . Действительно, пусть По условию, неравенство есть следствие неравенства 0. По следствию где . Так как то Поэтому вектор есть решение неравенства и, по условию, решение неравенства (2), т. е. Следовательно, Теорема, очевидно, верна также при

Предположим, что теорема верна, когда система содержит неравенств. Так как то, последствию Среди представлений вектора b существует представление с наибольшим числом неотрицательных коэффициентов. Пусть

— одно из таких представлений.

Пусть s есть число неотрицательных коэффициентов в (3), . Надо доказать, что . Допустим, что

Мы будем считать, что коэффициенты неотрицательны. Рассмотрим вектор

тогда

Пусть М — множество всех решений системы — любой вектор из М, тогда и если ; следовательно,

Кроме того, по условию, поэтому

На основании (6) и (7) заключаем, что для любого из М, т. е. неравенство есть следствие системы (1).

По лемме 1.6, отсюда вытекает, что неравенство есть следствие системы

состоящей из неравенств. По индуктивному предположению, , т. e. с можно представить в виде

Ввиду (5) и (8)

В этом представлении вектора b число неотрицательных коэффициентов больше, чем s. Это противоречит предположению, что представление (3) вектора b содержит наибольшее число неотрицательных коэффициентов. Мы пришли к противоречию, допустив, что . Таким образом, этот случай невозможен. Следовательно, , т. е. (3) есть искомое представление вектора b в виде неотрицательной комбинации векторов