Общая постановка задачи линейного программирования и ее графическое решение

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

Задачей линейного программирования (ЗЛП) называется задача вида

                                               (1.1.1)

                                                                                                                       (1.1.2)

                                                                                 (1.1.3)

где  - это управляющие переменные или решения задачи,

        - параметры.

Система неравенств (1.1.1) называется системой ограничений задачи.

Неравенства (1.1.2) – условие не отрицательности переменных.

Функция (1.1.3) – функция цели (целевая функция).

Вектор , удовлетворяющий неравенствам (1.1.1) и (1.1.2), называется планом задачи линейного программирования или допустимым вектором, или допустимым решением.

Решить задачу линейного программирования – это значит найти значения управляющих переменных , удовлетворяющих ограничениям (1.1.1) и (1.1.2), при которых це6левая функция (1.1.3) принимает минимальное или максимальное значение.

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

Вектор  называется оптимальным решением или оптимальным планом, если для всех .

Если оптимальное решение может быть найдено, то задача называется разрешимой, если же оптимального решения не существует, то задача называется неразрешимой.

Причины, по которым не может быть найдено оптимальное решение:

1. Функция на допустимом множестве неограниченна. Эта задача называется неразрешимой из-за неограниченности целевой функции.
2. Допустимое множество пусто , то есть не существует допустимых решений. Такая задача называется несовместимой.

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

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

Если задача линейного программирования имеет две переменные  и , то ее можно решить графически.

Решение задачи происходит в два этапа.

На первом этапе необходимо на плоскости изобразить допустимое множество, а на втором найти оптимальную точку, если она существует, а в противном случае убедиться в неразрешимости задачи.

Этап 1. Построение допустимого множества.

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

Если  в ограничениях присутствуют ограничения неотрицательности переменных, то рассматривается только первый координатный угол.

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

Алгоритм выполнения первого этапа.

Шаг 1. Выделение первого координатного угла, если присутствуют ограничения неотрицательности переменных.

Шаг 2. .

Шаг 3. -е неравенство записывается как уравнение.

Шаг 4. Полагаем,  находим из уравнения.

Шаг 5. Полагаем, находим из уравнения.

Шаг 6. Через точку и  проводится прямая.

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

Шаг 8. Если , то , переходим к Шагу 3, иначе Шаг 9.

Шаг 9. Допустимое множество получено. Если оно пустое, то выписывается ответ: «Задача несовместна», иначе переход к Этапу 2.

Этап 2. Поиск оптимальной точки.

Рассмотрим градиент функции . Так как функция  линейна, то ее градиент есть постоянный вектор с координатами .

Примечание:

Известно, что движение в направлении градиента увеличивает значение функции.

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

Алгоритм выполнения второго этапа.

Шаг 1. Строится вектор-градиент .

Шаг 2. Кладется линейка перпендикулярно вектору-градиенту.

Шаг 3. Линейка сдвигается параллельно самой себе по направлению вектора-градиента, пока хотя бы одна точка соответствующей прямой принадлежит допустимому множеству.

Шаг 4. Если при любом положении линейки перпендикулярно вектору-градиенту имеются точки допустимого множества, то выписывается ответ: «Задача неразрешима из-за неограниченности целевой функции» и переход к Шагу 10. Иначе Шаг 5.

Шаг 5. Находится последняя точка допустимого множества, лежащая на соответствующей линии уровня.

Шаг 6. Если эта точка не единственная, то выбирается точка, которая является пересечением двух прямых, ограничивающих допустимое множество.

Шаг 7. Выписывается система двух уравнений с двумя неизвестными.

Шаг 8. Из системы уравнений находится оптимальная точка .

Шаг 9. Находится оптимальное значение целевой функции .

Шаг 10. Конец.

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

Если область допустимых решений является незамкнутым выпуклым многоугольником в направлении оптимизации целевой функции, то целевая функция будет неограниченной и ЗЛП не будет иметь решений.

Очевидно также, что ЗЛП не будет иметь решений в случае, когда область допустимых решений есть пустое множество, то есть система ограничений ЗЛП содержит противоречивые неравенства, и на координатной плоскости нет ни одной точки, удовлетворяющей этим ограничениям.

Пример решения задачи:

Дана задача линейного программирования. Решить ее графически.

Решение:

1. Построим допустимое множество решений. Для этого определим множество, как пересечение полуплоскостей всех заданных неравенств.

     1)           Построим прямую               

	0	-3
	2	0

     2)            Построим прямую

	0	4
	-2	0

     3)           Построим прямую

	1	2
	-3	2

При поиске решения для случая оптимизации на минимум, получаем, что допустимое множество решений неограничено. Это означает, задача  не имеет решений из-за неограниченности целевой функции на допустимом множестве.

При оптимизации целевой функции на максимум крайней точкой допустимого множества является точка пересечения третей прямой с осью абсцисс. Определим эту точку:

получаем точку с координатами  - это оптимальная точка.

Рассчитаем значение целевой функции в этой точке:

рис.1  Пример решения задачи