Лекция: Различные формы записи ЗЛП

1.Общая

2.Каноническая

3. Стандартная

54. Приведение любой ЗЛП к стандартному виду. Переход от ЗЛП в стандартном виде к ЗЛП с ограничениями-неравенствами.

?????????????????????????????????????????????????????????????????????????????????

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

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

Наиболее наглядна эта интерпретация для случая n =2, т.е. для случая двух переменных и. Пусть нам задана задача линейного программирования в стандартной форме

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

Обратим прежде всего внимание на ограничения и. Они из всей плоскости вырезают лишь её первую четверть (см. рис. 1). Рассмотрим теперь, какие области соответствуют неравенствам вида. Сначала рассмотрим область, соответствующую равенству. Как Вы, конечно, знаете, это прямая линия. Строить её проще всего по двум точкам.

Пусть. Если взять, то получится. Если взять, то получится. Таким образом, на прямой лежат две точки и. Дальше через эти две точки можно по линейке провести прямую линию

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

Эта построенная прямая разбивает всю плоскость на две полуплоскости. В одной её части, а в другой наоборот. Узнать, в какой полуплоскости какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, например, начало координат, т.е. точка (0,0).

Пример

Определить полуплоскость, определяемую неравенством.

Решение

Сначала строим прямую. Полагая получим или. Полагая получим или. Таким образом, наша пря- мая проходит через точки (0, -1/2) и (3/4, 0).

Теперь посмотрим, в какой полуплоскости лежит точка (0,0), т.е. начало координат. Имеем, т.е. начало координат принадлежит полуплоскости, где. Тем самым определилась и нужная нам полуплоскость

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

Каждое из них задает на плоскости некоторую полуплоскость. Нас интересуют те точки, которые удовлетворяют всем этим m неравенствам, т.е. точки, которые принадлежат всем этим полуплоскостям одновременно. Следовательно, область, определяемая неравенствами вида (1.20), геометрически изображается общей частью (пересечением) всех полуплоскостей, определяемых отдельными ограничениями (к ним, естественно, надо добавить ограничения и ).