Системы линейных неравенст

                        х3 = 2 х1 + 4 х2.

Теперь последовательно полагаем одно из неизвестных х1 , х2 (входящих в правую часть уравнения) равным 1, а остальные нулю. Получаем такие решения:

Х1 = (1,0,2),      Х2 = (0, 1, 4).

Далее, в качестве Х3 берем точку

                              Х3 = - ( Х1+ Х2) = (-1, -1, -6)

и, наконец, за X4 принимаем одно из решений уравнения

                           - 2 х1 - 4x2 + x3= 1,

например, Х4, = (0, 0, 1).

Точки Х1, Х2 , Х3, Х4  образуют фундаментальный набор решений для неравенства (11). Общее решение имеет вид

X = k1Х1 + k2X2 +k3X3 + k4X4 = k1(1,0,2) + k2(0, 1.4) + k3(-1,-1.-6) + k4(0, 0, 1)

или

                                     х1 = k1 — k3,

                                     x2 = k2 — k3,

х3 = 2k1 + 4 k2 — 6 k3 + k4,

где k1,k2,k3,k4 — произвольные неотрицательные числа.

5. Перестройка фундаментального набора решений при добавлении к системе еще одного неравенства. Чтобы научиться строить фундаментальные наборы решений, рассмотрим вначале такую задачу.

Пусть дана однородная система

линейных неравенств. Пусть, далее, известен фундаментальный набор решений

Х1, Х2, ..., Хр

для этой системы. Требуется построить фундаментальный набор решений для системы, полученной добавлением к (12) еще одного неравенства

.

Решения системы (12)—это в точности все неотрицательные комбинации точек Х1, Х2, ..., Хр. Среди этих комбинаций нам нужно выбрать такие, которые удовлетворяли бы неравенству (13) и, более того, составили бы фундаментальный набор решений для системы (12), (13).

По отношению к функции L(X) —левой части неравенства (13)— все точки Х1, Х2, ..., Хр можно разбить на три группы: точки, для которых , точки, для которых L(X) < 0 и, наконец, точки, для которых L (X) = 0.  Точки первой группы обозначим , , ..., , точки второй группы — , , ..., ,  точки   третьей   группы — , , ..., .

Таким образом,

, ..., , , ..., ,  ..., .

— это те же самые точки Х1, Х2, ..., Хр, но только расположенные в другом порядке.

Разумеется, все точки = 1, …, k) удовлетворяют неравенству (13). То же самое относится и к ( = 1, ..., s). Что же касается точек ( = 1, ..., l), то из них ни одна не является решением неравенства (13). Однако, из каждой пары

,

(одна точка «плюсовая» и одна  «минусовая») можно образовать неотрицательную комбинацию

,

так, чтобы она удовлетворяла условию L(X) = 0. Для этого следует взять

                                 a= - L), b= L().

Действительно, числа а и b положительны и, кроме того,

L+b)=aL()+bL()= - L) L() + L)=0.

Обозначим точку (14), где а и b имеют указанные выше значения, через :

  = -L() + L.

Ответ к поставленной задаче даёт следующая

Теорема:   Точки            , ..., ,, ...,

(всего здесь записано k + s + kl точек) образуют фундаментальный набор решений для системы (12), (13).

Чтобы доказать теорему, установим сначала такую лемму.

Лемма. Любая неотрицательная комбинация точек и может быть представлена как неотрицательная комбинация точек , или же как неотрицательная комбинация точек .

Доказательство теоремы. Прежде всего заметим, что каждая из точек (17) удовлетворяет системе (12), (13). Поэтому, чтобы доказать теорему, нам остается лишь проверить следующее: если какая-то точка X является решением системы (12), (13), то она представима в виде неотрицательной комбинации точек (17).

Будучи решением системы (12), точка X представляется в виде неотрицательной комбинации ее фундаментальных точек Х1, Х2, ..., Хр:

X=+…+ + +…+ ++…+,

где все коэффициенты а1, ..., ak, b1 ,…, bl , с1, ..., сs неотрицательны.

Если все числа b1, …, bl равны нулю, то, очевидно, доказывать нечего. Предположим поэтому, что среди указанных чисел имеются строго положительные. Заметим, что тогда среди чисел a1, …, ak тоже имеются строго положительные: в противном случае получилось бы

L(X) = b1L()+ ... + blL() + clL) + ... + csL),

что невозможно, так как X удовлетворяет неравенству (13).

Допустим, для определенности, что а1 > 0 и b1 > 0. Пользуясь леммой, можно заменить сумму неотрицательной комбинацией точек или же точек . Если в выражении для точки X произвести  такую  замену, то общее число отличных от нуля  коэффициентов   при  , 

уменьшится по крайней мере на 1. Если при этом окажется, что во вновь полученном выражении для X не все коэффициенты при равны нулю, то снова заменим одну из сумм вида неотрицательной комбинацией точек или же точек в результате число отличных от нуля коэффициентов при , ..., , уменьшится еще по крайней мере на 1. Так будет продолжаться до тех пор, пока для точки X не получится выражение, в котором все коэффициенты при будут равны нулю. Мы придем тогда к равенству вида

X = +…++ + +…+,

где все коэффициенты справа больше либо равны нулю. Но это и есть требуемое представление для X. Теорема доказана.

6. Существование и способ построения фундаментального набора решений. Рассмотрим произвольную систему однородных линейных неравенств. Для первого неравенства системы можно (способом, описанным в п. 4°) построить фундаментальный набор решений. Присоединив к первому неравенству второе, можно, опираясь на теорему п. 5°, построить фундаментальный набор решений для системы, состоящей из первых двух неравенств. Далее присоединяем третье неравенство и т. д., пока не получим фундаментальный набор решений для всей исходной системы неравенств. Этим доказано существование и одновременно указан способ построения фундаментального набора решений.

Разумеется, если в данной системе неравенств имеется подсистема, для которой сразу можно указать фундаментальный набор решений, то в качестве исходного пункта следует взять эту подсистему; присоединяя к ней последовательно остальные неравенства, мы после ряда шагов построим искомый фундаментальный набор.

Пример. Для системы

требуется найти все неотрицательные решения, т. е. все решения, удовлетворяющие условиям

Иначе говоря, нужно найти общее решение системы (19), (20).

Нетрудно видеть, что для системы (20) фундаментальным набором будет являться набор из точек

, ,

,

(действительно, любое решение () системы (20) представимо в виде ). Присоединим к системе (20) первое из неравенств (19) и для полученной таким образом системы построим фундаментальный набор решений. Для удобства вычислений составим такую таблицу:

					L1(X)
X1	1	0	0	0
X2	0	1	0	0
X3	0	0	1	0
X4	0	0	0	1

В каждой строке таблицы указана одна из фундаментальных точек для системы (20), а также значение функции L1(X) для этой точки. Из таблицы видно, что единственной точкой типа является , точки типа суть ,  а точек типа в данном случае нет.

Находим точки типа . Ими будут:

=(5, 0, 3, 0),

   =(0, 5, 4, 0),

=(0, 0, 6, 5).

 

 

Чтобы не усложнять дальнейших записей, обозначим эти точки , , (соответственно), а вместо будем писать .

Точки , , , образуют фундаментальный набор решений для системы, состоящей из (20) и первого из неравенств (19).

Присоединяем к этой системе второе из неравенств (19) и составляем следующую таблицу:

					L2(Y)
	0	0	1	0
	5	0	3	0
	0	5	4	0
	0	0	6	5

 

Из таблицы видно, что роль точек теперь играют , , роль точек играют  , , а точек типа нет. Находим точки типа :

,

  ,

    ,

         

Точки , , , , , образуют фундаментальный набор решений для системы (19), (20). Общее решение имеет вид

 

где   а, b, с, d, e, f — какие   угодно   неотрицательные числа.

Если положить a = k1 , b = k2, 5c = k3, 5d = k4, 5e = k5, 5f = k6, то получим для Х представление,

X = k1 (5, 0, 3, 0) + k2 (0, 5, 4, 0) + k3 (3, 0, 2, 0) + k4 (0, 3, 3, 0) + k5 (13, 0, 9, 1) + k6 (0, 13, 14, 3),

где   k1, k2, ..., k6— произвольные   неотрицательные числа.

 

 

2.2   неоднородная система линейных неравенств. фундаментальный       набор решений

 

Зная как строить общее решение однородной системы неравенств, не составляет труда решить аналогичную задачу для произвольной, т. е. неоднородной, системы неравенств.

 

 

Пусть

— произвольная система линейных неравенств с п неизвестными х1, х2, ..., хп. Рассмотрим наряду с ней однородную систему

с n + 1 неизвестными х1, х2, ..., хп, t.

Между решениями систем (1) и (2) имеется определенного рода связь. А именно, если х1, х2, ..., хп, t — какое-либо решение системы (2), причем t > 0, то числа

1 =, 2 =, …, n =

будут составлять решение системы (1).

В самом деле, рассмотрим, например, первое из неравенств (2). Оно выполняется для чисел х1, х2, ..., хп, t, т. е.

                             a1х1 + а2х2 + ... + апхп > at.

Разделив обе части неравенства на положительное число t, будем иметь

                                              a11 + а22 + ... + апп > a,

это означает, что набор чисел 1, 2, ..., п удовлетворяет первому из неравенств (1). Аналогичное рассуждение можно провести для любого из неравенств (2), откуда и следует наше утверждение.

Нетрудно видеть, что любое решение системы (1) может быть получено указанным выше способом. Действительно, если и, 1, 2, ..., п — какое-либо решение системы (1), то числа х1 = 1, х2 = 2,…, хп =п, t = 1 удовлетворяют системе (2), и при этом справедливы равенства (3),

Итак, чтобы отыскать все решения 1, 2, ..., п системы (1), надо найти все решения системы (2), для которых t > 0, и преобразовать их по формулам (3).

Пример. Пусть требуется найти все решения системы

Поступая, как указано выше, запишем вспомогательную однородную систему

 

Добавляя к этой системе неравенство t  ≥ 0 (ибо нас интересуют только такие решения, для которые t>0), получаем систему (19), (20) из п 2.1, с той лишь разницей, что вместо х4 написано t. Множество решений этой системы, как показано в п 2.1, описывается формулами

,

,

                                 ,

,

где — любые неотрицательные числа. Так как нас интересуют лишь решения, для которых t > 0, то следует считать, что хотя бы одно из чисел отлично от нуля (строго положительно). Теперь находим общее решение системы (4) по формулам

 

Еще раз подчеркнем, что в этих формулах — любые неотрицательные числа, причем хотя бы одно из чисел отлично от нуля.

 

 

                  3. применение линейных неравенств в экономике

 

Чтобы подробнее изучить прикладные аспекты теории линейных неравенств в математической экономике рассмотрим следующие задачи.

 

Задача  №1.  Для строительства домов на 100 строительных площадках были выбраны 5 типовых проектов. По каждому из проектов известны продолжительность закладки фундаментов и строительства остальной части дома (таблица после задания). Одновременно можно вести закладку не более 10 фундаментов и строительство не более 15 домов. Записать в математической форме условия, которым должен удовлетворять годовой план (300 рабочих дней) строительства домов при дополнительном требовании, что домов II типа должно быть построено не менее 10.

 

Вид работы	Продолжительность работ (дн.) для проекта
	I	II	III	IV	VI
Закладка фундамента   Остальные работы	20             30             35             30            40     40             20             60             35            25

 

Решение. Обозначим через ,,,, соответственно количество домов каждого типа, планируемых к строительству в течение года. По условию должно быть построено 100 домов. В принятых обозначениях этот факт можно выразить следующей записью:

 

                                           ++++=100.                                       (1)

 

       Поскольку одновременно можно вести работы по закладке не более 10 фундаментов, годовой фонд времени по этому виду работ ограничен величиной 300*10 рабочих дней. Для реализации плана (,,,,) только на закладку фундаментов потребуется (20+30+35+30+40) рабочих дней. Это количество не может превышать имеющегося фонда времени, предусмотрено для данного вида работ, поэтому должно выполняться неравенство:

 

                                 20+30+35+30+40 ≤ 3000.                         (2)