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

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), геометрически изображается общей частью (пересечением) всех полуплоскостей, определяемых отдельными ограничениями (к ним,естественно, надо добавить ограничения и ).