3. Геометрична інтерпретація задачі лінійного програмування (детальна).

Графическая интерпретация возможна для ЗЛП, модель которой содержит 2, максимум 3 переменные. Для задач большей размерности геом. интерп. дается обобщением полученных свойств. Рассмотрим частный случай, когда n=2. Ограничения задачи тогда в общем виде записывается такой с-мой:

Рассмотрим отдельно ограничение равенства: .

Равенство с 2 переменными представляет собой прямую, её можно построить по 2 точкам.

Ограничение-неравенство: – полуплоскость, которая отображается соотв. прямой и может быть определена, например методом контрольной точки. Если с-ма ограничений совместна, то пересечение полуплоскостей образует некоторую общую область, которая называется ОДР задачи, каждая точка этой области может быть решением задачи.

ОДР может быть многоугольником, отрезком, точкой, а так же неограниченной многоугольной областью.

Имеет место такое свойство ОДР: если любые 2 точки ОДР ЗЛП соединить отрезком, то но будет полностью лежать в данном множестве. Такие множества называются выпуклыми.

Рассмотрим частный случай ЗЛП, когда n=3. Ограничение равенства представляет собой: - плоскость, её можно построить по 3-ём точкам. Ограничение неравенства с 3-мя неизвестными:образует собой полупространство, полученное относительно ограничений плоскости. Пересечение всех плоскостей и полупространств позволяет определить выпуклый многогранник, который представляет собой ОДР задачи.

Если больше 3 переменных: Каждое ограничение равенства – гиперплоскость, а ограничение неравенства – полупространство. Если с-ма совместна, то аналогично с рассм. выше случаями пересечение всех множеств образует многогранник допустимых решений.

Геометр. интерпретация ЦФ

ЦФ ЗЛП геометрически представляют множеством линий уровня, которые задаются уравнением:

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

ЦФ при n=3 гр. представляется линиями уровня , которые задают семейство параллельных плоскостей.

При n>=4 линии уровня цф образуют семейство параллельных гиперплоскостей.

Линии уровня заполняют все пространство, чем больше значение const, тем выше (или ниже) соотв. линии уровня. И следовательно больше (меньше) значение цф.

Решение ЗЛП состоит в том, чтобы найти такую точку ОДР, в которой цф будет достигать наибольшего или наименьшего значения.

Используя графич. интерпретацию задачи, процесс поиска опт. решения может быть осуществлен такими этапами: 1) по ограничениям задачи строится ОДР; 2) строятся линии уровня цф, которые задаются так: ; 3) определяется направление возрастания (убывания) цф; 4) Передвигая линии уровня в направлении возрастания, определяют точку минимума как первую точку касания линии уровня и ОДР и точку максимума как последнюю.

Частные случаи решения:

1) альтернативное решение – такое решение, при котором цф достигает макс или мин значения не в одной точке, а на целом множестве точек. Решение получаем в виде отрезка, ограниченного двумя вершинами многогранника и ответ записываем в виде:

2) неограниченное решение – возможно при неограниченной ОДР ()

Замечание: при неограниченной ОДР цф не всегда неограниченна, может существовать конечный максимум.

Теорема: Если ЗЛП имеет опт. решение, то цф достигает своего экстремального значения в одной из вершин ОДР.