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

Сентябрь 3, 2022

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

Содержание

2. Геометрическая интерпретация Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования,
3. Геометрическая интерпретация Возьмём на плоскости декартову систему координат и каждой паре чисел (x1, x2) поставим в
4. Геометрическая интерпретация Рассмотрим теперь, какие области соответствуют неравенствам вида a1x1+a1x2≤b. Сначала рассмотрим область, соответствующую равенству a1x1+a1x2=b.
5. Геометрическая интерпретация Дальше через эти две точки можно по линейке провести прямую линию (смотри рисунок 2).
6. Геометрическая интерпретация Эта построенная прямая разбивает всю плоскость на две полуплоскости. В одной её части a1x1+a1x2
7. Геометрическая интерпретация
8. Геометрическая интерпретация Вернёмся теперь к задаче линейного программирования. Там имеют место m неравенств a11x1+a12x2≤b1, a21x1+a22x2≤b2, ……………….
9. Пример Найти допустимую область задачи линейного программирования, определяемую ограничениями -x1+x2≤1, x1-2x2≤1, x1+x2≤3, x1≥0, x2≥0.
10. Пример
11. Пример
12. Возможные случаи Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника (см. рис. 6). Неосновной
14. Геометрическая интерпретация Вернёмся теперь к исходной задаче линейного программирования. В ней, кроме системы неравенств, есть еще
16. Решение А теперь сведем всё вместе. Итак, надо решить задачу c1x1+c2x2→max a11x1+a12x2≤b1, a21x1+a22x2≤b2, ………………. am1x1+am2x2≤bm, x1≥0;
17. Пример Решить задачу x1+2x2→max -x1+x2≤1, x1-2x2≤1, x1+x2≤2, x1≥0; x2≥0.
19. Особый случай Обратите внимание на то, что оптимальный план, как правило, соответствует какой-то вершине многоугольника, изображающего
22. Скачать презентацию

Слайд 2

Геометрическая интерпретация
Для понимания всего дальнейшего полезно знать и представлять себе геометрическую

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

Слайд 3

Геометрическая интерпретация
Возьмём на плоскости декартову систему координат и каждой паре чисел

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

Слайд 4

Геометрическая интерпретация
Рассмотрим теперь, какие области соответствуют неравенствам вида a1x1+a1x2≤b. Сначала рассмотрим

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

Слайд 5

Геометрическая интерпретация
Дальше через эти две точки можно по линейке провести прямую

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

Слайд 6

Геометрическая интерпретация
Эта построенная прямая разбивает всю плоскость на две полуплоскости. В

одной её части a1x1+a1x2b. Узнать, в какой полуплоскости какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, например, начало координат, т.е. точка (0,0).
Пример
Определить полуплоскость, определяемую неравенством 4x1-6x2≤3.

Слайд 7

Геометрическая интерпретация

Слайд 8

Геометрическая интерпретация
Вернёмся теперь к задаче линейного программирования. Там имеют место m

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

Слайд 9

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

Слайд 10

Пример

Слайд 11

Пример

Слайд 12

Возможные случаи
Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника

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

Слайд 13

Слайд 14

Геометрическая интерпретация
Вернёмся теперь к исходной задаче линейного программирования. В ней, кроме

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

Слайд 15

Слайд 16

Решение
А теперь сведем всё вместе. Итак, надо решить задачу
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 и будет оптимальным значением целевой функции.

Слайд 17

Пример
Решить задачу
x1+2x2→max
-x1+x2≤1,
x1-2x2≤1,
x1+x2≤2,
x1≥0; x2≥0.

Слайд 18

Слайд 19

Особый случай
Обратите внимание на то, что оптимальный план, как правило, соответствует

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

Слайд 20

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

Содержание

Геометрическая интерпретацияДля понимания всего дальнейшего полезно знать и представлять себе геометрическую

Геометрическая интерпретацияВозьмём на плоскости декартову систему координат и каждой паре чисел

Геометрическая интерпретацияРассмотрим теперь, какие области соответствуют неравенствам вида a1x1+a1x2≤b. Сначала рассмотрим

Геометрическая интерпретацияДальше через эти две точки можно по линейке провести прямую

Геометрическая интерпретацияЭта построенная прямая разбивает всю плоскость на две полуплоскости. В

Геометрическая интерпретация

Геометрическая интерпретацияВернёмся теперь к задаче линейного программирования. Там имеют место m

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

Пример

Пример

Возможные случаиОсновной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника

Геометрическая интерпретацияВернёмся теперь к исходной задаче линейного программирования. В ней, кроме

РешениеА теперь сведем всё вместе. Итак, надо решить задачуc1x1+c2x2→maxa11x1+a12x2≤b1,a21x1+a22x2≤b2,……………….am1x1+am2x2≤bm,x1≥0; x2≥0.Ограничения задачи

ПримерРешить задачуx1+2x2→max-x1+x2≤1,x1-2x2≤1,x1+x2≤2,x1≥0; x2≥0.

Особый случайОбратите внимание на то, что оптимальный план, как правило, соответствует

Похожие презентации

Геометрическая интерпретация
Для понимания всего дальнейшего полезно знать и представлять себе геометрическую

Геометрическая интерпретация
Возьмём на плоскости декартову систему координат и каждой паре чисел

Геометрическая интерпретация
Рассмотрим теперь, какие области соответствуют неравенствам вида a1x1+a1x2≤b. Сначала рассмотрим

Геометрическая интерпретация
Дальше через эти две точки можно по линейке провести прямую

Геометрическая интерпретация
Эта построенная прямая разбивает всю плоскость на две полуплоскости. В

Геометрическая интерпретация
Вернёмся теперь к задаче линейного программирования. Там имеют место m

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

Возможные случаи
Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника

Геометрическая интерпретация
Вернёмся теперь к исходной задаче линейного программирования. В ней, кроме

Решение
А теперь сведем всё вместе. Итак, надо решить задачу
c1x1+c2x2→max
a11x1+a12x2≤b1,
a21x1+a22x2≤b2,
……………….
am1x1+am2x2≤bm,
x1≥0; x2≥0.
Ограничения задачи

Пример
Решить задачу
x1+2x2→max
-x1+x2≤1,
x1-2x2≤1,
x1+x2≤2,
x1≥0; x2≥0.

Особый случай
Обратите внимание на то, что оптимальный план, как правило, соответствует