3.3. Требования совместности условий

В общую постановку задачи оптимизации входят неравенства вида:

где п - число неизвестных; т - число неравенств. Если в каждое неравенство добавить переменную , то от системы неравенств можно перейти к системе урав­нений

.

В этой системе общее число неизвестных N = п + m, где п - число основных неизвестных , т - число дополни­тельных неизвестных y_i, которое равно числу уравнений.

Возможны три варианта соотношения величин N и т: N < т, N = m, N > т.

Пусть число неизвестных меньше, чем число уравне­ний. Например,

,

т.е. N = 1, т = 2. Очевидно, что эта система решения не имеет, т.е. нет таких значений х₁, которые бы удовлетво­ряли обоим уравнениям. В этом случае говорят, что систе­ма условий несовместна.

Если число неизвестных N меньше числа уравнений т, то система решения не имеет и является несовместной.

Пусть число неизвестных равно числу уравнений. Например,

Решением этой системы будут значения x = у = 1.

Линейная система, в которой число неизвестных N разно числу уравнений т, имеет одно решение.

Наличие или отсутствие решений при различных соот­ношениях числа переменных и числа уравнений справедли­во только для линейно независимых уравнений, которые не могут быть получены умножением, делением, сложением, вычитанием исходных уравнений. Например, пусть есть урав­нение Зх = 6, из которого можно получить несколько: х = 2; 9х = 18; 6x = 12 и т. д. Все эти уравнения линейно зависи­мы и новых сведений о зависимостях для переменной не содержат. Поэтому в этом примере т = 1 (а не 4).

Аналогично в следующей системе есть только два ли­нейно независимых уравнения: так, уравнение (в) есть ре­зультат суммирования (а) и (б), а уравнение (г) есть резуль­тат деления (в) на 5:

Пусть число неизвестных больше числа уравнений. Напри­мер, . Очевидно, что все значения х₁ и х₂, лежа­щие на прямой этого уравнения, являются его решением. Зна­чит, это уравнение имеет бесчисленное множество решений.

Если в системе число неизвестных N больше числа уравнений т, то такая система имеет бесчисленное мно­жество решений.

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

Если все ограничения и целевая функция линейны, задача оптимизации, как нам известно, является задачей линейного программирования.

3.4. Графический метод решения задач линейного программирования

Вспомним построение линейных зависимостей. Начнем с уравнений. Линейное уравнение с двумя переменными может быть записано . Чтобы построить это уравнение, найдем точки пересечения с осями координат.

При x₁=0 получим , откуда . При х₂=0 будем иметь и (рис. 2).

Разделим теперь левую и правую части уравнения на b и перепишем уравнение, которое называют уравнением пря­мой в отрезках:

Рис. 2

Такое представление уравнения удобно для построения прямой, так как величины α₁ и α₂ - это отрезки, отсекаемые прямой на тех осях, которые указаны в числи­теле. Например, или в форме уравнения в от­резках:

т.е. α₁ = 1, α₂ = 2.

Теперь о неравенствах. Если линейное уравнение с дву­мя переменными может быть представлено прямой на плоскости, то неравенство изоб­ражается как полуплоскость.

Так, неравенство представляет собой за­штрихованную полуплоскость, координаты всех точек кото­рой, т. е. х₁ и х₂, удовлетворяют заданному равенству. Зна­чит, эти значения составляют область допустимых реше­ний (рис. 3).

Рис. 3

Рассмотрим построение системы линейных неравенств:

или в форме, аналогичной уравнениям в отрезках:

Построим каждое неравенство в системе координат х₁, х₂ в виде соответствующих полуплоскостей. Решение этой системы неравенств - координаты всех то­чек, принадлежащих области допустимых решений, т.е. АВСDО.

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

Рис. 4 Рис. 5

Не любая система линейных неравенств имеет об­ласть допустимых решений, т.е. допустимые решения.

Например, построим систему:

Из рис. 5 видно, что нет таких точек, которые бы удовлетворяли всем неравенствам системы.

Итак, мы рассмотрели линейные уравнения и неравен­ства с двумя переменными. Если перейти к линейным за­висимостям с тремя переменными, то тогда они будут опи­сывать плоскость в трехмерном пространстве; линейное неравенство характеризует полупространство, а система линейных неравенств - многогранник как область допу­стимых решений в трехмерном пространстве.

С увеличением числа переменных выше трех геометри­ческая интерпретация невозможна, так как система нера­венств - область допустимых решений в k-мерном про­странстве.

При этом мерность пространства определяют так: если ограничения заданы неравенствами, то k = n и, где п - чис­ло переменных; если ограничения в виде уравнений, то k = n - т, где т - число уравнений.

Если необходимо найти оптимальное решение, то сле­дует принять целевую функцию. Допустим, мы хотим, что­бы решение было оптимальным в смысле максимизации выпуска в целом. Тогда целевая функция:

Положим L, равной какому-либо числу (любому), на­пример 2, и построим уравнение целевой функции:

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

Отсюда можно сделать исключительно важный вы­вод: оптимальное решение - координаты вершины облас­ти допустимых решений.

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

Вершина, в которой целевая функция приобретает оп­тимальное (максимальное или минимальное) значение, яв­ляется оптимальной вершиной.

Координаты оптимальной вершины есть оптимальные значения искомых переменных.