Геометрическая интерпретация ЗЛП в стандартной форме

Рассмотрим задачу в стандартной форме:

(4)

Каждое условие

определяет в пространстве полупространство, лежащее по одну сторону от гиперплоскости

.

ОДР представляет собой пересечение таких полупространств.

ОДР может быть:

− выпуклый многогранник (многогранник решений):

;

− выпуклая многогранная неограниченная область:

;

− пустая область;

− единственная точка.

Если ОДР – пустое множество, ЗЛП не имеет оптимального решения из-за несовместности системы ограничений.

В случае единственной точки задача имеет единственное и, следовательно, оптимальное решение.

Замечание. Многогранник называется выпуклым, если наряду с любыми двумя своими точками, он содержит соединяющий их отрезок.

На плоскости многогранник – многоугольник.

Примеры:

выпуклый многоугольник:

невыпуклый многоугольник:

В остальных случаях следует построить поверхности (линии) уровней целевой функции.

Линии уровней целевой функции представляют собой семейство параллельных плоскостей

. (5)

Линии уровня перпендикулярны вектору – градиенту целевой функции. В случае плоскостей – вектору нормали к этим плоскостям

. (6)

Вектор указывает направление наискорейшего возрастания целевой функции, а противоположный вектор – направление убывания целевой функции.

Задача определения максимума (минимума) целевой функции сводится к нахождению в ОДР точки, через которую проходит прямая из семейства (5) и которая соответствует наибольшему (наименьшему) значению .

Возможны следующие случаи для случая двух переменных:

а)

Максимум целевой функции достигается в точке A, минимум – в точке B. Координаты точки экстремума – оптимальное решение.

б)

Максимум целевой функции достигается в любой точке А отрезка , минимум – в точке B.

в)

Максимум целевой функции недостижим, минимум – в точке B.

Пример задачи об ассортименте продукции:

1. Построим прямую :

по двум точкам:

Определим полуплоскость

:

Подставим точку О(0; 0) : Так как - верно, то выбираем нижнюю полуплоскость.

Построим полуплоскость

.

Аналогично построим прямую :

по двум точкам:

Подстановка точки О(0; 0) в неравенство

определяет нижнюю полуплоскость.

2. Построим ОДР - выпуклый четырехугольником ABCO:

3. Определим вектор – градиент целевой функции

:

.

4. Построить прямую , проходящую через начало координат и перпендикулярную вектору .

5. Передвигаем данную прямую параллельно себе в направлении вектора . Наиболее удаленная вершина В ОДР соответствуют максимуму целевой функции.