Геометрическая интерпретация задач линейного программирования
Задачи
А. Привести к канонической форме следующие задачи линейного программирования.
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
Б. Напишите задачи 1,2,5,6,7,8,9 в стандартных формах.
1.3. Геометрическая интерпретация задач линейного программирования
Геометрическая интерпретация задач линейного программирования
Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n =2 и n =3.
Наиболее наглядна эта интерпретация для случая n =2, т.е. для случая двух переменных 
и 
. Пусть нам задана задача линейного программирования в стандартной форме
| (1.19) |
Возьмём на плоскости декартову систему координат и каждой паре чисел 
поставим в соответствие точку на этой плоскости.
Обратим прежде всего внимание на ограничения 
и 
. Они из всей плоскости вырезают лишь её первую четверть (см. рис. 1). Рассмотрим теперь, какие области соответствуют неравенствам вида 
. Сначала рассмотрим область, соответствующую равенству 
. Как Вы, конечно, знаете, это прямая линия. Строить её проще всего по двум точкам.
Пусть 
. Если взять 
, то получится 
. Если взять 
, то получится 
. Таким образом, на прямой лежат две точки 
и 
. Дальше через эти две точки можно по линейке провести прямую линию (смотри рисунок 2).
Если же b=0, то на прямой лежит точка (0,0). Чтобы найти другую точку, можно взять любое отличное от нуля значение и вычислить
| соответствующее ему значение .
|
Эта построенная прямая разбивает всю плоскость на две полуплоскости. В одной её части 
, а в другой наоборот 
. Узнать, в какой полуплоскости какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, например, начало координат, т.е. точка (0,0).
Пример
Определить полуплоскость, определяемую неравенством 
.
Решение
Сначала строим прямую 
. Полагая получим 
или 
. Полагая получим 
или 
. Таким образом, наша пря- мая проходит через точки (0, -1/2) и (3/4, 0) (см. рис. 3)
Теперь посмотрим, в какой полуплоскости лежит точка (0,0), т.е. начало координат. Имеем 
, т.е. начало координат принадлежит полуплоскости, где . Тем самым определилась и нужная нам полуплоскость (см. рис. 3).
Вернёмся теперь к задаче линейного программирования. Там имеют место m неравенств
| (1.20) |
Каждое из них задает на плоскости некоторую полуплоскость. Нас интересуют те точки, которые удовлетворяют всем этим m неравенствам , т.е. точки, которые принадлежат всем этим полуплоскостям одновременно. Следовательно, область, определяемая неравенствами вида (1.20), геометрически изображается общей частью (пересечением) всех полуплоскостей, определяемых отдельными ограничениями (к ним,
| естественно, надо добавить ограничения и ).
|
Как уже говорилось выше, эта область называется допустимой областью задачи линейного программирования.
Пример
Найти допустимую область задачи линейного программирования, определяемую ограничениями
| (1.21) |
Решение
- Рассмотрим прямую
. При 
, а при 
. Таким образом, эта прямая проходит через точки (0,1) и (-1,0). Беря 
получим, что -0+0<1 и поэтому интересующая нас полуплоскость лежит ниже прямой, изображенной на рис. 4а. - Рассмотрим прямую
. При 
, а при . Таким образом, эта прямая проходит через точки (0, -1/2) и (1,0). так как 
4.б). - Наконец, рассмотри
м прямую 
. Она проходит через точки (0,3) и (3,0) и так как 0+0<3, то интересующая нас полуплоскость лежит ниже прямой, изображенной на рис. 4.в).
Сводя все вместе и добавляя условия 
получим рисунок 5, где выделена область, в которой выполняются одновременно все ограничения (1.21). Обратите внимание на то, что получившаяся область имеет вид выпуклого многоугольника.
Вернемся теперь к общему случаю, когда одновременно выполняются неравенства
| (1.22) |
Не приводя строгих доказательств, укажем те случаи, которые тут могут получится.
- Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника ( см. рис. 6).
- Неосновной случай получается неограниченный выпуклый многоугольник, имеющий вид, подобный изображенному на рис. 7. Подобная ситуация, например, получится, если в рассмотренном выше примере убрать ограничение
. Оставшаяся часть будет неограниченным выпуклым многоугольником.
- Наконец, возможен случай, когда неравенства (1.22) противоречат друг другу, и допустимая область вообще пуста.
Вернёмся теперь к исходной задаче линейного программирования. В ней, кроме системы неравенств, есть еще целевая функция 
.
Рассмотрим прямую 
. Будем увеличивать L. Что будет происходить с нашей прямой?
Легко догадаться, что прямая будет двигаться параллельно самой себе в том направлении, которое дается вектором 
, так как это вектор нормали к нашей прямой и одновременно вектор градиента функции 
.
А теперь сведем всё вместе. Итак, надо решить задачу
Oграничения задачи вырезают на плоскости некоторый многоугольник. Пусть при некотором L прямая пересекает допустимую область. Это пересечение дает какие-то значения переменных , которые являются планами.
Увеличивая L мы начнем двигать нашу прямую и её пересечение с допустимой областью будет изменяться (см. рис. 9). В конце концов эта прямая выйдет награницу допустимой области как правило, это будет одна из вершин многоугольника. Дальнейшее увеличение L приведёт к тому, что пересечение
прямой с допустимой областью будет пустым. Поэтому то положение прямой , при котором она вышла на граничную точку допустимой области, и даст решение задачи, а соответствующее значение L и будет оптимальным значением целевой функции.
Пример
Решить задачу
| (1.23) |