Меню
Главная
Авторизация/Регистрация
 
Главная arrow Экономика arrow Исследование операций в экономике

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

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

Выпуклые множества в 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)¾ + (1/2)Х2 + (l/3)X:i есть выпуклая линейная комбинация точек Хх, Х2, Ху а выражения (1/3)¾ + (1/2)¾ + (1/3)¾ или (1/3)¾ – (1/2)¾ + (7/6)¾ являются линейными, но нс выпуклыми комбинациями тех же точек (в нервом , а во втором ).

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

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

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

Возьмем для простоты п = 2, а в качестве многогранника – треугольник ^,¾¾ (рис. 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 следует, что выпуклый многогранник порождается своими угловыми точками или вершинами: отрезок – двумя точками, треугольник – тремя, тетраэдр – четырьмя точками и т.д. В то же время выпуклая многогранная область, являясь неограниченным множеством, не определяется однозначно своими угловыми точками: любую ее точку нельзя представить в виде выпуклой линейной комбинации угловых точек.

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы