Системы линейных неравенств
3.2 Существование и способ построения фундаментального набора решений
Рассмотрим произвольную систему однородных линейных неравенств. Для первого неравенства можно построить фундаментальный набор решений. Присоединив к первому неравенству второе можно построить фундаментальный набор решений для системы, состоящей из двух первых неравенств. Далее присоединяем третье неравенство и т.д., пока не получим фундаментальный набор решений для всей исходной системы неравенств. Этим доказано существование и одновременно показан способ построения фундаментального набора решений.
Разумеется, если в данной системе неравенств имеется подсистема, для которой сразу можно найти фундаментальный набор решений, то в качестве исходного пункта следует взять эту подсистему; присоединяя к ней последовательно остальные неравенства, после ряда шагов можно построить искомый фундаментальный набор решений.
Рассмотрим пример. Для системы:
(16)
Требуется найти все неотрицательные решения, т.е. все решения, удовлетворяющие условиям:
(17)
Нетрудно видеть, что для системы (17) фундаментальным набором решений будет являться набор из точек:
Присоединим к системе(17) первое неравенство (16) и для полученной таким образом системы получим фундаментальный набор решений. Для удобства вычислений составим таблицу:
L1(X) |
||||||
X1 |
1 |
0 |
0 |
0 |
-3 |
|
X2 |
0 |
1 |
0 |
0 |
-4 |
|
X3 |
0 |
0 |
1 |
0 |
5 |
|
X4 |
0 |
0 |
0 |
1 |
-6 |
В каждой строке таблицы указана одна из фундаментальных точек системы (17), а также значение точки L1(X) для этой точки. Находим точки типа
.
Точку X3 обозначим Y3. Точки Y3, Y1, Y2, Y4 образуют фундаментальный набор решений для системы, состоящей из (17) и первого неравенства (16).
Присоединяем к этой системе второе неравенство из (16) и получаем:
L2(Y) |
||||||
Y1 |
0 |
0 |
1 |
0 |
-3 |
|
Y2 |
5 |
0 |
3 |
0 |
1 |
|
Y3 |
0 |
5 |
4 |
0 |
3 |
|
Y4 |
0 |
0 |
6 |
5 |
-13 |
Находим точки типа :
Все эти точки образуют фундаментальный набор решений систем (16), (17).
Общее решение имеет вид: