Теоретические основы методов линейного программирования

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

Выпуклые множества в n-мерном пространстве

В параграфе 2.2 выпуклое множество точек определялось как множество, которое вместе с любыми своими двумя точками содержит весь отрезок, их соединяющий. Однако в случае п переменных не ясно, что следует понимать под «отрезком» в n-мерном пространстве. Очевидно, надо дать аналитическое определение этого понятия.

Начнем с п = 2 (двумерного пространства, плоскости). Пусть и | - точки плоскости , а «любая точка отрезка (рис. 3.1).

Рис. 3.1.

Очевидно, что отношение а длин отрезков ХХ2 и ХхХ2 удовлетворяет условию 0<�а<1. Запишем это отношение, а через координаты точек. Получим откуда

(3.1) где

(3.2).

Полагая оц =а и ?2=1-?, условия (3.1), (3.2) примут вид.

(3.3).

(3.4).

Равенство (3.3) можно записать в виде.

(3.5).

понимая, что в нем все операции выполняются покоординатно (т.е. отдельно по переменной дг, и отдельно по переменной х2).

Таким образом, отрезок ХхХ2 можно определить как множество точек (векторов), удовлетворяющих условиям (3.5) и (3.4).

В случае «-мерного пространства определение отрезка будет таким же — множество точек, удовлетворяющих условиям (3.5) и (3.4), если под Х{ и X., подразумевать точки (векторы) n-мерного пространства: и Обобщением понятия отрезка для нескольких точек является их выпуклая линейная комбинация.

Точка X называется выпуклой линейной комбинацией точек Хх, Х2,…, Хп, если выполняются условия

Так, например, выражение (1/6)¾ + (½)Х2 + (l/3)X:i есть выпуклая линейная комбинация точек Хх, Х2, Ху, а выражения (1/3)¾ + (½)¾ + (1/3)¾ или (1/3)¾ — (½)¾ + (7/6)¾ являются линейными, но нс выпуклыми комбинациями тех же точек (в нервом , а во втором ).

Очевидно, что в частном случае при п = 2 выпуклой линейной комбинацией двух точек является соединяющий их отрезок. Поэтому множество точек является выпуклым, если оно вместе с любыми своими двумя точками содержит их произвольную выпуклую линейную комбинацию.

Рассмотрим теорему о представлении выпуклого многогранника.

Теорема 3.1. выпуклый п-мерный многогранник является выпуклой линейной комбинацией своих угловых точек.

Возьмем для простоты п = 2, а в качестве многогранника — треугольник^, 3/43/4 (рис. 3.2). Через произвольную точку X треугольника проведем отрезок XlXi. Поскольку точка X лежит на этом отрезке, то.

где.

Точка ХЛ лежит на отрезке Х2Х3, следовательно, ХА = а2Х2 + а3Х3, где а2 > О, а3 > О, а2 + а3 = 1.

Подставив значение Х4 в выражение для X, получим

Рис. 3.2.

Обозначив , получим окончательно.

где.

Таким образом, точка X есть выпуклая линейная комбинация угловых точек (вершин) треугольника ХхХ.2Хn. ¦

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