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

Исследование операций

Семинар

ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Определение выпуклой области.Пусть на плоскости xOy заданы две точки: А1 (x(1); y(1)) и А2 (x(2); y(2)), определяющие прямолинейный направленный отрезок (рис.1.2). Найдем координаты произвольной внутренней точки А (x; y) данного отрезка через координаты его начала и конца.

Векторы А1А = (x – x(1); y – y(1)) и A1A = (x(2) – x(1); y(2) – y(1)) параллельны и одинаково направлены, поэтому А1А = t(A1A2), где 0£ t £1, или x – x(1) = t(x(2) – x(1)), y – y(1) = t(y(2) – y(1)). Полагая 1 – t = l1, t = l2, получаем

(2.43)

Учитывая, что в (2.43) координаты точки А являются суммами одноименных координат точек А1 и А2, умноженными соответственно на числа l1 и l2, окончательно имеем:

А = l1А1 + l2А2, (2.44)

l1 ³ 0, l2 ³ 0, l1 + l2 = 1. (2.45)

Точка А, для которой выполняются условия (2.44) и (2.45), называется выпуклой линейной комбинацией точек А1 и А2. Множество называется выпуклым, если вместе с любыми двумя своими точками оно содержит и их произвольную выпуклую линейную комбинацию. Геометрический смысл этого определения состоит в том, что множеству вместе с его двумя произвольными точками полностью принадлежит и прямолинейный отрезок, их соединяющий. Точка множества называется граничной, если любой шар сколь угодно малого радиуса с центром в этой точке содержит как точки, принадлежащие множеству, так и точки, не принадлежащие ему. Граничные точки множества образуют его границу. Замкнутым называется множество, содержащее все свои граничные точки. Замкнутое множество называется ограниченным, если существует шар радиуса конечной длины с центром в любой точке множества, который полностью содержит в себе данное множество; в противном случае множество называется неограниченным. Пересечением двух (или нескольких) множеств называется множество, представляющее общую часть данных множеств. Точка A выпуклого множества называется угловой, если она не может быть представлена в виде выпуклой линейной комбинации каких-нибудь двух различных точек данного множества. Выпуклым многоугольником называется выпуклое замкнутое ограниченное множество на плоскости, имеющее конечное число угловых точек. Угловые точки многоугольника называются его вершинами, а отрезки, соединяющие две вершины и образующие его границу, - сторонами многоугольника.

Выпуклым многогранником называется замкнутое ограниченное выпуклое множество трехмерного пространства, имеющее конечное число угловых точек. Угловые точки многогранника называются его вершинами; многоугольники, ограничивающие многогранник, - гранями; отрезки, по которым они пересекаются, - ребрами.

Т е о р е м а 2.Замкнутый, ограниченный, выпуклый многогранник является выпуклой линейной комбинайией своих угловых точек.

Доказательство. Рассмотрим многоугольник, имеющий n вершин.

1) Докажем, что любая точка треугольника удовлетворяет теореме. В треугольнике A1А2А3 (рис.2.3) возьмем произвольную точку А4 и через нее проведем отрезок А1А4.

Так как точка А принадлежит отрезку А1А4, то она - выпуклая линейная комбинация его концов, т. е.

А = t1A1 + t4А4, t1 ³ 0, t4 ³ 0,

t1 + t4 = 1. (2.46)

Точка А4 принадлежит отрезку А2А3, следовательно, является выпуклой линейной комбинацией его концов, т. е.

А4 = t2А2 + t3А3, t2 ³ 0, t3 ³ 0, t2 + t3 = 1. (2.47)

Подставляя (2.47) в (2.46) получаем

А = t1A1 + t4(t2А2 + t3А3) = t1А1 + t2t4А2 + t3t4А3.

Полагая t1 = l1, t2t4 = l2, t3t4 = l3, окончательно имеем

А = l1А1 + l2А2 + l3А3,

l1 ³ 0, l2 ³ 0, l3 ³ 0, l1 + l2 + l3 = 1, (2.48)

т. е. точка А - выпуклая линейная комбинация вершин А1, А2, А3.

2) В выпуклом многоугольнике, имеющем n вершин (n > 3), добавляя к правой части соотношения (2.48) остальные n ‑ 3 вершины, умноженные на нуль, окончательно получим

А = l1А1 + l2А2 + l3А3 + 0×А4 + ... + 0×Аn,

lI ³ 0 (i = 1, 2, ..., n), ,

т. е. точка А - выпуклая линейная комбинация угловых точек многоугольника.

Лемма 1. Пересечение любого числа выпуклых множеств есть множество выпуклое (если оно не пусто).

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

Пусть дана задача

(min) Z = C1x1 + C2x2 (2.49)

(2.50)

х1 ³ 0, х2 ³ 0. (2.51)

Совокупность чисел х1, х2, ..., хn, удовлетворяющих ограничениям называется решением. Если система неравенств (2.50) при условии (2.51) имеет хотя бы одно решение, она называется совместной, в противном случае несовместной. Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений задает на плоскости х1Ох2 некоторую полуплоскость с граничной прямой аi1x1 + аi2x2 = bi (i = 1, 2, ..., m). Полуплоскость - выпуклое множество. Но по лемме 1 пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений задачи (2.49)-(2.51) есть выпуклое множество.



Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми х1 = 0, х2 = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы. Совокупность этих точек (решений) назовем многоугольником решений. Он может быть точкой, отрезком, лучом, многоугольником, неограниченной многоугольной областью.

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

Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП - непустое множество. Например, многоугольник А1А2А3А4А5А6 (рис. 2.4). Выберем произвольное значение целевой функции Z = Z0. Получим C1x1 + C2x2 = Z0. Это уравнение прямой линии. В точках прямой NM целевая функция сохраняет одно и то же постоянное значение Z0. Считая в равенстве (2.49) Z параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).