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


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

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

 1-osnovnye-poniatiia-lineinogo-programmirovaniia

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

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

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

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

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

2-osnovnye-poniatiia-lineinogo-programmirovaniia

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

Теорема

Пусть дан многоугольник Q (рис. 4.3) и дан ненулевой вектор 3-osnovnye-poniatiia-lineinogo-programmirovaniia, тогда существует единственная опорная прямая данного многоугольника, для которой вектор 3-osnovnye-poniatiia-lineinogo-programmirovaniia является нормалью (аналогично для многогранников).

4-osnovnye-poniatiia-lineinogo-programmirovaniia

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

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

Решение

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

5-osnovnye-poniatiia-lineinogo-programmirovaniia

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

Точка пересечения прямой с многогранником – 7-osnovnye-poniatiia-lineinogo-programmirovaniia . Строим вектор 8-osnovnye-poniatiia-lineinogo-programmirovaniia и умножаем его на вектор 3-osnovnye-poniatiia-lineinogo-programmirovaniia:

9-osnovnye-poniatiia-lineinogo-programmirovaniia

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

10-osnovnye-poniatiia-lineinogo-programmirovaniia

где 11-osnovnye-poniatiia-lineinogo-programmirovaniia – координаты вектора 8-osnovnye-poniatiia-lineinogo-programmirovaniia, откуда

12-osnovnye-poniatiia-lineinogo-programmirovaniia

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

Линейная функция, заданная на многоугольнике, достигает своих наименьших и наибольших значений на границах этого многоугольника.

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

 Литература:

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


Категории: Логистика  

Об этой статье

teoriia-grafov-osnovnye-poniatiia-lineinogo-programmirovaniia-avatar
2017-11-02 13:13:42
382
user
Логистика; Лекции; Линейное программирование;
В статье описаны основные понятия линейного программирования