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

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

(неравенства в системе ограничений могут содержать знаки или ).

Так как задача задана в стандартной форме (все ограничения– неравенства), то решение задачи происходит по следующим этапам:

1. Строят три прямые, уравнения которых получаются в результате

замены в ограничениях задачи знаков неравенств на знаки равенств, т. е.

2. Находят полуплоскости, определяемые каждым из ограничений

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

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

решений (ОВР).

4. Из этой области выделяем область допустимых решений (ОДР), т.е.

пересечение области допустимых решений и первой четверти, где и . Таким образом, находим ОДР. Если ОДР пуста, то задача линейного программирования решений не имеет.

5. Строим вектор-градиент целевой функции , равный

.

6. Строим линию уровня , перпендикулярно вектору

градиенту (k -константа).

7. Передвигая линию уровня в направлении вектора , находим

точку «входа» в ОДР – это точка минимума, и точку «выхода» из ОДР – это точка максимума.

8. Определяем координаты точки минимума или максимума (в

зависимости от условия задачи) аналитически и вычисляем значение целевой функции в этой точке.

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

Решение. Построим область допустимых решений. Каждое неравенство в системе ограничений заменяем на равенство. В прямоугольной декартовой системе координат строим четыре прямые

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

-2	-3
	прямая параллельна оси

Построив прямые, определяем полуплоскости, определяемые данными неравенствами.

Так как первая прямая не проходит через начало координат, то подставив координаты точки О(0;0) в первое неравенство, получим , (верно), следовательно, первое неравенство определяет полуплоскость, лежащую ниже прямой (1). Так как вторая прямая не проходит через начало координат, то подставив координаты точки О(0;0) во второе неравенство, получим , (верно), следовательно, второе неравенство определяет полуплоскость, лежащую выше прямой (2).

Рисунок 1

Поскольку третья прямая не проходит через начало координат, то подставим координаты точки О(0;0) в третье неравенство, получим , (не верно), следовательно, третье неравенство определяет полуплоскость, лежащую выше прямой (3).

Четвертое неравенство определяет полуплоскость, лежащую ниже прямой (4).

Находим общую часть полуплоскостей решений, учитывая при этом условия неотрицательности. Заштрихованный многоугольник является областью допустимых решений (ОДР) (рисунок 1).

Строим вектор градиент .

Строим линию уровня перпендикулярно вектору .

По условию задачи нужно найти максимум и минимум функции Z. Передвигая линию уровня параллельно самой себе в направлении возрастания вектора градиента, находим точку «входа» в ОДР– это точка (см. рисунок 1). Найденная точка является точкой минимума. Найдем координаты точки аналитически. Эта точка является пересечением прямых (3) и . Решим систему:

Следовательно, . Вычислим значение целевой функции в

этой точке. .

Аналогично, находим точку «выхода» из ОДР – это точка (см. рисунок 1). Найденная точка является точкой максимума. Найдем координаты точки аналитически. Эта точка является пересечением прямых (2) и (4). Решим систему:

Следовательно, . Вычислим значение целевой функции в этой точке. .

Ответ: , .

Date: 2015-10-18; view: 627; Нарушение авторских прав