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

↑

▷ Содержание

⇐ ПредыдущаяСтр 4 из 9Следующая ⇒

Общей задачей линейного программирования называется задача нахожде­ния минимума (максимума) линейной функции

Z = c₁ x₁ + c₂ x₂ +...+ c_n x_n ® min (max) (1)

при ограничениях:

a₁₁ x₁ + a₁₂ x₂ +...+ a_1n x_n £ (=, ³) b₁

a₂₁ x₁ + a₂₂ x₂ +...+ a_2n x_n £ (=, ³) b₂ (2)

..................................

a_m1 x₁ + a_m2 x₂ +...+ a_mn x_n £ (=, ³) b_m,

x_j ³ 0, j = 1,..., n (3)

где c_j, a_ij, b_i - заданные числа, x_j - неизвестные, i = 1,…,m, j = 1,…,n и в лю­бом из ограничений вида (2) может встречаться любой из знаков £, = или ³.

Если число неизвестных n = 2, то задача (1) – (3) примет вид

Z = c₁ x + c₂ y ® min (max) (4)

a₁₁ x + a₁₂ y £ (=, ³) b₁

a₂₁ x + a₂₂ y £ (=, ³) b₂ (5)

......................

a_m1 x + a_m2 y £ (=, ³) b_m,

x ³ 0, y ³ 0. (6)

и ее можно решить геометрическим методом, так как каждая пара неизвестных (х, y) может быть представлена точкой на координатной плоскости хОy.

При решении задачи (4) – (6) сначала строят так называемую допустимую область, т.е. множество точек (х, y) плоскости, координаты которых удовлет­воряют всем ограничениям (5) и лежат в первой четверти координатной плос­кости (ограничение (6)). Поскольку все ограничения (5) – линейные, то допус­тимая область будет представлять собой выпуклый многоугольник (конечный или бесконечный) или пустое множество.

Затем среди точек допустимой области находят оптимальную, т.е. такую точку М₀ координаты которой (х₀ , y₀) доставляют минимум (максимум) целе­вой функции Z. Для этого по виду целевой функции (4) строят линию уровня функции Z, соответствующую Z=0, т.е. прямую L₀: c₁ x + c₂ y = 0 и находят градиент функции Z – вектор , который пока­зывает направление наибыстрейшего возрастания функции Z. Вектор анти­градиента (-с₁, -с₂) будет показывать направление наибыстрейшего убывания целевой функции Z. Вектор градиента перпендикулярен линии уровня L₀.

Перемещая линию уровня L₀ параллельно самой себе в направлении градиента (с₁, с₂), находим последнюю точку допустимой области, которую она пересекает при таком движении. Очевидно, что это будет точка максимума. Перемещая линию уровня в противоположном направлении (-с₁, -с₂), находим точку минимума. Поясним этот метод на конкретном примере.

Геометрическим методом найти максимум и минимум функции Z для

x, y ³ 0 при заданных ограничениях.

Z = x – 3y

КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задание 2. Геометрическим методом найти максимум и минимум функции Z для x, y ³ 0 при заданных ограничениях:

Варианты:

1. Z = 2x + y 2. Z = 3x + y

3x - 4y £ 4 y £ 1

-x + 6y £ 8 x - 2y £ 3

x + y ³ 1 2x + y ³ 1

3. Z = 2x - y 4. Z = x + y

2x + y £ 3 y ³ 2

x + y ³ 6 x + y £ 7

x - 3y £ 3 -x + 2y £ 2

5. Z = 4x + y 6. Z = 3x - y

x - 2y ³ 0 2x + 3y £ 13

4x - y £ 14 x ³ 2

3x + y ³ 7 5x - 3y £ 22

7. Z = 2x + y 8. Z = x + 5y

x ³ 2 3x - y ³ 3

4x - y £ 8 x - y £ 4

x - y ³ -1 x + y ³ 6

9. Z = 5x + y 10. Z = 3x

x - 4y ³ -3 x + y £ 7

4x - 3y £ 14 2x - y £ 11

3x + y ³ 4 4x + y ³ 19

Познавательные статьи:



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману