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

Пример 1:

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

а). найти область допустимых значений (многоугольник решений);  

б). найти оптимумы целевой функции.

 

Решение от преподавателя:

Решение.

        Необходимо найти максимальное значение целевой функции Z = x₁+6x₂ → max             

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


Рассмотрим целевую функцию задачи Z = x₁+6x₂ → max. 
Построим прямую, отвечающую значению функции Z = x₁+6x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации Z(X). Начало вектора – точка (0; 0), конец – точка (1;6). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Задача не имеет допустимых решений. ОДР представляет собой бесконечное множество (не ограничена).

      Необходимо найти минимальное значение целевой функции F = x₁+6x₂ → min

Рассмотрим целевую функцию задачи Z = x₁+6x₂ → min. 
Построим прямую, отвечающую значению функции Z = x₁+6x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации Z(X). Начало вектора – точка (0; 0), конец – точка (1;6). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая Z(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (2) и (4), то ее координаты удовлетворяют уравнениям этих прямых:
x₁+2x₂=12
x₂=3
Решив систему уравнений, получим: x₁ = 6, x₂ = 3
Откуда найдем минимальное значение целевой функции:
Z(X) = 1*6 + 6*3 = 24                               

Пример 2:

Решить графически линейную задачу:

Решение от преподавателя:

1) Строим допустимое множество, которое ограничено прямыми

2) Отмечаем градиент целевой функции c = (1; 2) и линию уровня функции , соответствующую значению 0.

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

4) Для подсчета точных координат точки минимума a достаточно решить следующую систему, которая состоит из уравнений, опеределящих прямые (2) и (3):

У нее есть единственное решение (x₁, x₂) = (4/3; 2/3). Подставляя его в целевую функцию, получаем значение 8/3.

Ответ: в задаче имеется единственная точка минимума с координатами (4/3; 2/3), а сам минимум равен 8/3.
Максимума целевая функция не достигает.

Пример 3:

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

а) найти область допустимых значений (многоугольник решений);  

б) найти оптимумы целевой функции.

 

 

Решение от преподавателя:

№9.                                                             

max  и  min  Z =  x₁ + 6x₂                                                

                           2x₁ +   x₂   12                                                 

                             x₁ + 2x₂   12                                                

                             x₁    2                                                            

                             x₂   3 

Решение.

        Необходимо найти максимальное значение целевой функции Z = x₁+6x₂ → max             

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


Рассмотрим целевую функцию задачи Z = x₁+6x₂ → max. 
Построим прямую, отвечающую значению функции Z = x₁+6x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации Z(X). Начало вектора – точка (0; 0), конец – точка (1;6). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Задача не имеет допустимых решений. ОДР представляет собой бесконечное множество (не ограничена).

      Необходимо найти минимальное значение целевой функции F = x₁+6x₂ → min

Рассмотрим целевую функцию задачи Z = x₁+6x₂ → min. 
Построим прямую, отвечающую значению функции Z = x₁+6x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации Z(X). Начало вектора – точка (0; 0), конец – точка (1;6). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая Z(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (2) и (4), то ее координаты удовлетворяют уравнениям этих прямых:
x₁+2x₂=12
x₂=3
Решив систему уравнений, получим: x₁ = 6, x₂ = 3
Откуда найдем минимальное значение целевой функции:
Z(X) = 1 · 6 + 6 · 3 = 24                               

 

Пример 4:

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

Решение от преподавателя:

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



Рассмотрим целевую функцию задачи F = x₁+x₂ → max. 
Построим прямую, отвечающую значению функции F = x₁+x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (1;1). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией. 

Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых: 
2x₁+4x₂=16 
x₁+3x₂=9 
Решив систему уравнений, получим: x₁ = 6, x₂ = 1 
Откуда найдем максимальное значение целевой функции: 
F(X) = 1*6 + 1*1 = 7 

Пример 5:

Для всех значений параметра λ ∈ R решить задачу:

Решение от преподавателя:

Строим допустимое множество, ограниченное прямыми

Оно изображено на следующем рисунке (треугольник BCD):

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

Они зависят от расположения вектора градиента c = (λ, 1) относительно границ множества. Прежде всего необходимо рассмотреть те значения λ, при которых линия уровня целевой функции оказывается параллельной граничным отрезкам допустимого множества.

Линия уровня будет параллельна некоторому граничному отрезку тогда и только тогда, когда нормальный вектор к прямой, содержащей отрезок, будет коллинеарен с градиентом целевой функции. Следовательно, линия уровня параллельна прямой (1) при λ = 1/3, прямой (3) при λ = 1 и прямой (4) при λ = 5 (прямую (2) мы не рассматриваем, потому что она не определяет границу допустимого множества).

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

В зависимости от λ, точками экстремума могут быть либо точки B, C или D, либо все точки какого-то из граничных отрезков. Координаты точек B, C и D найдем соответственно из систем

Решив их, получаем

Обозначим целевую функцию через z. Теперь мы можем найти ее экстремумы в зависимости от значения параметра λ.

Рассмотрим все возможные случаи. Если λ < 1/3, то минимум достигается в точке B, а максимум в точке D; при этом

В случае λ = 1/3 точками минимума являются все точки отрезка

а точкой максимума по-прежнему остается точка D; при этом

Если 1/3 < λ < 1, то тогда точкой минимума является C, а точкой максимума D; при этом

При λ = 1 точкой минимума остается C, а точками максимума будут все точки отрезка

причем

Если 1 < λ < 5, то минимум остается в точке C, а максимум перемещается в точку B. При этом

В случае λ = 5 точками минимума будут все точки отрезка

а точкой максимума будет B, причем z_min = 0 и z_max = 8. Наконец, при λ > 5 точкой минимума будет D, точкой максимума B, а экстремумы будут равны

 

 

Пример 6:

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

Решение от преподавателя:

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

Рассмотрим целевую функцию задачи F = 3x₁+2x₂ → max. 
Построим прямую, отвечающую значению функции F = 3x₁+2x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (3;2). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией. 

Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых: 
x₁+6x₂=11 
5x₁+3x₂=17 
Решив систему уравнений, получим: x₁ = 2.5556, x₂ = 1.4074 
Откуда найдем максимальное значение целевой функции: 
F(X) = 3*2.5556 + 2*1.4074 = 10.4815