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

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

Содержание слайда: Геометрическая интерпретация Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n=2 и n=3. Наиболее наглядна эта интерпретация для случая n=2, т.е. для случая двух переменных x1 и x2. Пусть нам задана задача линейного программирования в стандартной форме c1x1+c2x2→max a11x1+a12x2≤b1, a21x1+a22x2≤b2, ………………. am1x1+am2x2≤bm, x1≥0; x2≥0.

Содержание слайда: Геометрическая интерпретация Возьмём на плоскости декартову систему координат и каждой паре чисел (x1, x2) поставим в соответствие точку на этой плоскости. Обратим прежде всего внимание на ограничения x1≥0 и x2≥0. Они из всей плоскости вырезают лишь её первую четверть (см. рис. 1).

Содержание слайда: Геометрическая интерпретация Рассмотрим теперь, какие области соответствуют неравенствам вида a1x1+a1x2≤b. Сначала рассмотрим область, соответствующую равенству a1x1+a1x2=b. Это прямая линия. Строить её проще всего по двум точкам. Пусть b≠0. Если взять x1=0, то получится x2=b/a2. Если взять x2=0, то получится x1=b/a1. Таким образом, на прямой лежат две точки (0, b/a2) и (b/a1, 0).

Содержание слайда: Геометрическая интерпретация Дальше через эти две точки можно по линейке провести прямую линию (смотри рисунок 2). Если же b=0, то на прямой лежит точка (0,0). Чтобы найти другую точку, можно взять любое отличное от нуля значение x1 и вычислить соответствующее ему значение x2.

Содержание слайда: Геометрическая интерпретация Эта построенная прямая разбивает всю плоскость на две полуплоскости. В одной её части a1x1+a1x2<b, а в другой наоборот a1x1+a1x2>b. Узнать, в какой полуплоскости какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, например, начало координат, т.е. точка (0,0). Пример Определить полуплоскость, определяемую неравенством 4x1-6x2≤3.

Содержание слайда: Геометрическая интерпретация

Содержание слайда: Геометрическая интерпретация Вернёмся теперь к задаче линейного программирования. Там имеют место m неравенств a11x1+a12x2≤b1, a21x1+a22x2≤b2, ………………. am1x1+am2x2≤bm. Каждое из них задает на плоскости некоторую полуплоскость. Нас интересуют те точки, которые удовлетворяют всем этим m неравенствам, т.е. точки, которые принадлежат всем этим полуплоскостям одновременно. Следовательно, область, определяемая неравенствами, геометрически изображается общей частью (пересечением) всех полуплоскостей, определяемых отдельными ограничениями (к ним, естественно, надо добавить ограничения x1≥0 и x2≥0). Как уже говорилось выше, эта область называется допустимой областью задачи линейного программирования.

Содержание слайда: Пример Найти допустимую область задачи линейного программирования, определяемую ограничениями -x1+x2≤1, x1-2x2≤1, x1+x2≤3, x1≥0, x2≥0.

Содержание слайда: Пример

Содержание слайда: Пример

Содержание слайда: Возможные случаи Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника (см. рис. 6). Неосновной случай - получается неограниченный выпуклый многоугольник, имеющий вид, подобный изображенному на рис. 7. Подобная ситуация, например, получится, если в рассмотренном выше примере убрать ограничение x1+x2≤3. Оставшаяся часть будет неограниченным выпуклым многоугольником. Наконец, возможен случай, когда неравенства противоречат друг другу, и допустимая область вообще пуста.

Содержание слайда:

Содержание слайда: Геометрическая интерпретация Вернёмся теперь к исходной задаче линейного программирования. В ней, кроме системы неравенств, есть еще целевая функция c1x1+c2x2→max. Рассмотрим прямую c1x1+c2x2=L. Будем увеличивать L. Легко догадаться, что прямая будет двигаться параллельно самой себе в том направлении, которое дается вектором (c1, c2), так как это - вектор нормали к нашей прямой и одновременно вектор градиента функции f(x1, x2)=c1x1+c2x2.

Содержание слайда:

Содержание слайда: Решение А теперь сведем всё вместе. Итак, надо решить задачу c1x1+c2x2→max a11x1+a12x2≤b1, a21x1+a22x2≤b2, ………………. am1x1+am2x2≤bm, x1≥0; x2≥0. Ограничения задачи вырезают на плоскости некоторый многоугольник. Пусть при некотором L прямая c1x1+c2x2=L пересекает допустимую область. Это пересечение дает какие-то значения переменных , которые являются планами. Увеличивая L мы начнем двигать нашу прямую и её пересечение с допустимой областью будет изменяться (см. рис. 9). В конце концов эта прямая выйдет на границу допустимой области - как правило, это будет одна из вершин многоугольника. Дальнейшее увеличение L приведёт к тому, что пересечение прямой c1x1+c2x2=L с допустимой областью будет пустым. Поэтому то положение прямой c1x1+c2x2=L, при котором она вышла на граничную точку допустимой области, и даст решение задачи, а соответствующее значение L и будет оптимальным значением целевой функции.

Содержание слайда: Пример Решить задачу x1+2x2→max -x1+x2≤1, x1-2x2≤1, x1+x2≤2, x1≥0; x2≥0.

Содержание слайда:

Содержание слайда: Особый случай Обратите внимание на то, что оптимальный план, как правило, соответствует какой-то вершине многоугольника, изображающего допустимую область. И лишь в том случае, когда прямая c1x1+c2x2=L совпадет с границей допустимой области, может случиться так, что решение не будет единственным. Но и в этом случае вершины, соответствующие границам этой стороны, дают оптимальные планы нашей задачи линейного программирования. Таким образом, вершины допустимой области играют в решении задач линейного программирования особую роль.

Содержание слайда:

Содержание слайда: Заключение Ну, а если допустимая область неограничена, то и значение целевой функции может быть неограниченным. Подводя итог этим примерам, можно сформулировать следующие положения: допустимая область - это выпуклый многоугольник; оптимум достигается в вершине допустимой области (если допустимая область ограничена и не пуста); ограниченность целевой функции в допустимой области является необходимым и достаточным условием разрешимости задачи.