Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

6.3. Некоторые основные понятия и факты

Рассмотрим на плоскости, где введена система декартовых координат, две точки M1, M2 и их радиус-векторы r1 = , r2 = (рис. 13). Разность векторов r2 и r1 равна r2 - r1 = . Предположим, что λ - произвольное число, удовлетворяющее неравенству 0≤λ≤1. Если вектор умножить на скаляр λ, то получится вектор λ = s, коллинеарный , направленный в ту же сторону, но имеющий длину, меньшую чем . Ясно, что если совместить начало вектора s с точкой M1, то его конец M попадет внутрь отрезка M1M2. При λ = 0 точка M совпадает с M1, при λ = 1 - с точкой M2. При любом 0≤λ≤1 радиус-вектор r точки M равен сумме: r = r1 + s1 = r1 + λ(r2 - r1). Итак, радиус-вектор r любой точки M, лежащей на отрезке между M1 и M2, находится по формуле

r = r1 + λ(r2 - r1), где 0≤λ≤1.(18)
Рис. 13
Рис. 13

Наши рассуждения, а значит и формула (18), без всяких изменений переносятся со случая плоскости (размерность n = 2) на случай трехмерного пространства (n = 3). Поэтому естественно, перейдя к рассмотрению пространства произвольного числа n измерений, считать, что радиус-вектор r произвольной точки отрезка M1M2 находится по той же формуле (18).

На плоскости каждая из точек, например M1 и M2, задается двумя координатами: M1(x1(1), x2(1)); M2(x1(2), x2(2)). Те же координаты имеют соответствующие векторы r1 = = {x1(1), x2(1)} и r2 = = {x1(2), x2(2)}. Координаты вектора r = {x1, x2} (и точки M) находятся по формуле (18), которая при переходе к координатной записи приводит к двум соотношениям:

x1 = (1 - λ)x1(1) + λx1(2), x2 = (1 - λ)x2(1) + λx2(2).

В пространственном случае (n = 3) добавляется еще одно соотношение для третьей координаты:

x3 = (1 - λ)x3(1) + λx3(2)

В n-мерном пространстве точки M1 {x1(1), ..., x1(n)), M2 (x1(2), ..., xn(2)) задаются каждая п координатами, а координаты точки M(x1, ..., xi, ..., xn) определяются из n соотношений

xi = 1 - λ)xi(1) + λxi(2) (i = 1, ..., n)

или из одного векторного соотношения

r = (1 - λ)r1 + λr2.(19)

Множество всех таких точек M назовем отрезком M1M2 в n-мерном пространстве.

Совокупность точек пространства T называют выпуклым телом (фигурой), если вместе с двумя любыми его точками M1 и M2 к этой совокупности принадлежат все точки отрезка M1M2.

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

Рис. 14
Рис. 14

Под пересечением тел (фигур) понимают множество точек, принадлежащих каждому из этих тел. Пересечение любого числа выпуклых тел вновь является выпуклым телом. Убедимся в этом (см. рис. 14, в). Выберем любые две точки M1 и M2, принадлежащие пересечению. Эти точки принадлежат каждому из пересекающихся тел. Но каждое из них по условию выпукло и, значит, каждое содержит весь отрезок M1M2. В силу этого отрезок M1M2 полностью принадлежит и их пересечению. Последнее означает, что пересечение - выпуклое тело.

Зададим в плоскости некоторую прямую уравнением: a0 + a1x1 + a2x2 = 0. Она делит всю плоскость на две части - на две полуплоскости. Отметим далее на плоскости пару точек M1 и M2 и установим признаки, по которым можно узнать, принадлежат ли отмеченные точки одной и той же или разным полуплоскостям. Бот эти очевидные необходимые и достаточные признаки:

Если точки M1 и M2 принадлежат одной полуплоскости, то отрезок M1M2, их соединяющий, не пересекает заданной прямой. Если отрезок M1'M'2 соединяющий точки M'1 и M'2, пересекает эту прямую, то точки M'1 и M'2 лежат в разных полуплоскостях (см. рис. 15).

Рис. 15
Рис. 15

Аналогичные признаки имеют место в трехмерном пространстве: они позволяют выяснить, лежат ли точки по одну или по разные стороны от заданной плоскости a0 + a1x1 + a2x2 + a3x3 = 0. Без изменения признаки переносятся далее на общий случай n-мерного пространства. Здесь рассматривается геометрическое место точек (так называемая гиперплоскость), задаваемое линейным относительно x1, ..., xn уравнением

a0 + a1x1 + a2x2 + ... + anxn = 0.(20)

Оказывается, что совокупность всех точек n-мерного пространства T, не лежащих на гиперплоскости (20), можно разбить на две части так, что окажутся выполненными следующие условия: отрезок, соединяющий любую пару точек из одной и той же части, не пересекает гиперплоскость (20); отрезок, соединяющий любую пару точек из разных частей, пересекает гиперплоскость (20).

Убедимся в этом. Для сокращения записи ограничимся плоским случаем (n = 2). Для произвольного n рассуждения остаются теми же. Зададим прямую

a0 + a1x1 + a2x2 = 0.(21)

Линейная форма, равная левой части этого уравнения, имеет вид

Ф = a0 + a1x1 + a2x2.(22)

В точках плоскости, не лежащих на прямой (21), форма Ф≠0. Разобьем всю плоскость на две части и обозначим их через Т+ и Г-. К части Т+ отнесем все точки плоскости, в которых Ф>0, а к части Г- - все точки, где Ф<0. Проверим теперь, что для каждой из частей Т+ и Г- справедливо наше утверждение.

Пусть M1(x1(1), x2(1)) и M2(x1(2), x2(2)) - две точки из одной и той же части, например Т+. Тогда

Ф(M1) = a0 + a1x1(1) + a2x2(1)>0,(23)
Ф(M2) = a0 + a1x1(2) + a2x2(2)>0.(24)

Умножим (23) и (24) соответственно на числа 1-λ>0 и λ>0. Получим:

(1-λ) [a0 + a1x1(1) + a2x2(1)] + λ[a0 + a1x1(2) + a2x2(2)] = a0 + a1[(1-λ)x1(1) + λx1(2)] + a2[(1-λ)x2(1) + λx2(2)]>0.(25)

Но x1 = (1-λ)x1(1) + λx1(2) и x2 = (1-λ)x2(1) + λx2(2) при 0≤λ≤1 суть координаты произвольной точки M отрезка M1M2. Неравенство (25) можно записать в виде Ф(M) = (1-λ)Ф(M1) + λФ(M2). При этом результат Ф(M)>0 означает, что точка M, и следовательно весь отрезок M1M2 принадлежат части Т+. Теперь предположим, например, что Ф(M1)>0, а Ф(M2)<0, т. е. что M1 и M2 принадлежат различным частям. Точка M окажется на прямой (21), если Ф(M) = 0, т. е. при (1-λ)Ф(M1) + λФ(M2) = 0. Отсюда находим

(26)

По условию выбора точек Ф(M1)>0, Ф(M2)<0, следовательно λ, найденное из (26), удовлетворяет неравенствам 0≤λ≤1 и поэтому определяет точку M отрезка M1M2, принадлежащую в то же время прямой (21). Этим доказано, что отрезок M1M2 пересекает прямую (21).

Итак, заданием прямой (21) вся плоскость Т разбивается на две части - на две полуплоскости. Каждая из них ограничена прямой (21), которую мы условимся относить к каждой из полуплоскостей.

Если теперь обратиться к гиперплоскости (20), то, перенося рассуждения на этот общий случай, можно заключить:

Гиперплоскость (20) делит пространство на две части - полупространства. В каждом из полупространств форма Ф = a0 + a1x1 + ... + anxn сохраняет свой знак. В различных полупространствах знак Ф различен. Следовательно, любая гиперплоскость a0 + a1x1 + ... + anxn = C, где C = const, целиком лежит либо в одном, либо в другом полупространстве в зависимости от знака C.

Покажем, что полуплоскость (полупространство), ограниченная любой прямой (21) (гиперплоскостью (20)), является выпуклым телом. Мы уже видели, что если точки M1 и M2 принадлежат одной и той же полуплоскости (полупространству), то Ф(M1) и Ф(M2) имеют одинаковые знаки. Тот же знак имеет Ф(M) для любой точки M отрезка M1M2. Это означает, что той же полуплоскости (полупространству) принадлежит и весь отрезок M1M2.

Рассмотрим теперь произвольное линейное неравенство относительно переменных x1 и x2. Его всегда можно записать в виде

a0 + a1x1 + a2x2≥0.(27)

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

Убедимся, что областью решений линейного неравенства является полуплоскость. Для этого перейдем от неравенства (27) к равенству a0 + a1x1 + a2x2 = 0. Это уравнение определяет прямую на плоскости. Уже известно, что прямая делит плоскость на две полуплоскости. В каждой из точек одной из полуплоскостей F = a0 + a1x1 + a2x2≥0. Эта полуплоскость и является областью решения неравенства (27).

В качестве примера рассмотрим неравенство

2 - x1 - x2 ≥ 0.

Прямая 2 - x1 - x2 = 0 разбивает всю плоскость на две части. Областью решений неравенства (1) является та из полуплоскостей, которой принадлежит начало координат. Другая полуплоскость является областью решений неравенства 2 - x1 - x2≤0.

По аналогии с изложенным областью решений линейного неравенства

a0 + a1x1 + a2x2 + ... + anxn ≥ 0

относительно n переменных x1, ..., xn является некоторое полупространство п-мерного пространства.

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

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


является пересечение m полупространств. Это пересечение оказывается пустым множеством, если система неравенств несовместна.

Пересечение (если оно непусто) любого числа полупространств называется выпуклым многогранником (или выпуклой многогранной областью, если оно не ограничено).

Итак, областью решений совместной системы линейных неравенств является выпуклый многогранник (или неограниченная выпуклая многогранная область). Многогранник ограничен гиперплоскостями, уравнения которых получаются из неравенств системы переходом к равенствам.

Теперь в качестве иллюстрации снова рассмотрим систему ограничений (I)-(VI) поставленной ранее задачи и решим ее геометрическим методом.

Эта система неравенств определяет выпуклый многоугольник P, лежащий в первой четверти и изображенный на рис. 16.

Рис. 16
Рис. 16

Среди точек многоугольника P требуется найти точки, в которых форма S(X) из (15) принимает наименьшее значение. С этой целью рассмотрим линии уровня формы S(X). Для S(X) = 33 линия уровня имеет уравнение 33 = 33 - 2x11 - x12, т. е. x12 = - 2x11.

Эта прямая проходит через начало координат с угловым коэффициентом k = - 2 и показана на рис. соответствующей линией. Всякая другая линия уровня S (X) = C параллельна изображенной прямой.

Выделим из линий уровня S(X) ту, которая отвечает наименьшему из возможных значений и в то же время пересекает многоугольник P. Этой линией (показана на рис. 16) является та, которая проходит через вершину P - точку (1, 1). Она отвечает значению S (X) = 33 - 2 - 1 = 30. Таким образом, наименьшее значение затрат формы min S(X) = 30 и определяется значениями переменных

x11 = 1, x12 = 1, x13 = 0, x22 = 2, x23 = 1, x21 = 0.

Это означает, что оптимальным является план, согласно которому из центра A1 в клубы B1 и B2 направляется по одному футболисту. Из центра A2 в клубы B2 и B3 переводятся соответственно двое и один спортсмен.

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

предыдущая главасодержаниеследующая глава



ИНТЕРЕСНО:

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru