Теория графов. Основные понятия линейного программирования

Плоскость, полуплоскость, полупространство.

Выпуклый многоугольник – множество точек плоскости, которое является результатом пересечения конечного числа полуплоскостей (рис. 4.1).

Рисунок 4.1 – Выпуклый многоугольник.

Выпуклый многогранник – множество точек пространства, которое является результатом пересечения конечного числа полупространств.

Опорная плоскость, опорная прямая.

Прямая l (рис. 4.2) является опорной прямой, если она содержит хотя бы одну конечную точку многоугольника и не содержит ни одной внутренней точки. Прямая m – также опорная прямая (см. рис. 4.2).

Опорная плоскость – аналогично опорной прямой, но для пространства.

Рисунок 4.2 – Опорные прямые (l, m).

Рисунок 4.2 –  К теореме (см. выше).

Пример 4.1. В координатной плоскости XY задан выпуклый многоугольник (рис. 4.3). Этот многоугольник является областью определения функции вида . Найти точку данного многоугольника с координатами , в которой данная функция приобретает максимальное значение.

Решение

Пусть l – прямая, которая является опорной для данного многоугольника, а вектор  – это вектор нормали (рис. 4.3).

Рисунок 4.3 – К примеру 1.

Точка пересечения прямой с многогранником –  . Строим вектор  и умножаем его на вектор :

С другой стороны, скалярное произведение векторов – это произведение координат:

где  – координаты вектора , откуда

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

В следующих статьях мы разберем 4 основных типа задач, встречающихся в линейном программировании. К ним относятся задачи производственной, технологической, складской и транспортной логистики.

 Литература:

1. Шевченко В.В. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2009 г.
2. Ткачук А.Н. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2008 г.