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

Общая задача линейного программирования.

Исследования различных процессов, в том числе и экономических, начинаются с их моделирования, т.е. отражения реального процесса через математические соотношения. При этом составляются уравнения и неравенства, которые связывают различные показатели (переменные) исследуемого процесса, образуя систему ограничений. В этих соотношениях выделяются такие переменные, меняя которые можно получить оптимальное значение основного показателя данной системы (прибыль, доход, затраты и т.п.) Соответствующие методы, позволяющие решать указанные задачи, объединяются под общим названием «математическое программирование» или «математические методы исследования операций».

Математическое программирование - это раздел высшей математики, посвященный решению задач, связанных с нахождением экстремумов функций нескольких переменных при наличии ограничений на переменные. Оно включает в себя такие разделы математики, как линейное, нелинейное и динамическое программирование. Сюда же относят и стохастическое программирование, теорию игр, теорию массового обслуживания, теорию управления запасами и некоторые другие.

Методами математического программирования решаются задачи распределения ресурсов, планирования выпуска продукции, ценообразования, транспортные задачи и т.п.

Математическое программирование возникло в 30е годы ХХ века. Венгерский математик Б.Эгервари в 1931 году решил задачу, называемую проблемой выбора. Американский ученый Г.У. Кун обобщил этот метод, после чего он стал называться «венгерским методом». В 1939 году российский ученый Л.В. Канторович разработал метод разрешающих множителей решения задач линейного программирования. Большой вклад в развитие математического программирования внесли американские ученые. В 1947 году американский ученый Дж.Данцит описал один из основных методов решения задач линейного программирования, получивший названия «симплексный».

Метод называется симплексным, так как области допустимых решений задач, которые рассматривались на начальном этапе развития метода, имели простейший (simple) вид (n =2, n =3 ).

Построение математической модели экономической задачи включает следующие этапы:

1. выбор переменных задачи;

2. составление системы ограничений;

3. выбор целевой функции.

Переменными задачи называются величины х₁, х₂,..., х_n, которые полностью характеризуют экономический процесс.

Система ограничений включает в себя систему уравнений и неравенств, которым удовлетворяют переменные задачи и которые следуют из ограниченности ресурсов или других экономических или физических условий, например, положительности переменных и т.п.

Целевой функцией называют функцию переменных задачи, которая характеризует качество выполнения задачи и экстремум которой требуется найти.

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

Z(X)=c1x1+c2x2+...+cnxn → max (min)	(1)
xj ≥0, j =1,2,..., t, t ≤ n.	(2)

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор Х =(х₁, х₂,..., х_n), удовлетворяющий системе ограничений и условиям неотрицательности.

Множество допустимых решений задачи образует область допустимых решений.

Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение задачи, при котором целевая функция достигает экстремума.

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

х1 ≥0, х2 ≥0

(3)

Задача линейного программирования в стандартной форме представляет собой следующее: требуется найти экстремум целевой функции при допустимой области, которая есть система линейных равенств и неравенств, а переменные неотрицательны.

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

Обратим прежде всего внимание на ограничения х₁ ≥0, и х₂ ≥0. Они из всей плоскости вырезают лишь её первую четверть (рис. 1). Рассмотрим теперь, какие области соответствуют неравенствам вида а₁ х₁+а₂ х₂≤b. Сначала рассмотрим область, соответствующую равенству а₁ х₁+а₂ х₂=b. Это прямая линия. Строить её проще всего по двум точкам.

Пусть b≠0. Если взять х₁=0, то получится х₂=b/а₂. Если взять х₂=0, то получится х₁=b/а₁. Таким образом, на прямой лежат две точки (0,b/а₂) и (b/а₁,0). Дальше через эти две точки можно по линейке провести прямую линию (рис. 2).

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

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

Дата добавления: 2014-01-20