Построить на плоскости область решений линейных неравенств и геометрически найти максимальное и минимальное значения целевой функции в этой области

Пример 1:

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

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

Необходимо найти минимальное значение целевой функции F = 9x₁+2x₂ → min, при системе ограничений:
x₁+4x₂≤53, (1)
x₁-x₂≤3, (2)
7x₁+3x₂≥71, (3)
Шаг №1. Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Построим уравнение x₁+4x₂ = 53 по двум точкам. Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 13.25. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 53. Соединяем точку (0;13.25) с (53;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:1 • 0 + 4 • 0 - 53 ≤ 0, т.е. x₁+4x₂ - 53≤ 0 в полуплоскости ниже прямой.
Построим уравнение x₁-x₂ = 3 по двум точкам. Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = -3. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 3. Соединяем точку (0;-3) с (3;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:1 • 0 - 1 • 0 - 3 ≤ 0, т.е. x₁-x₂ - 3≤ 0 в полуплоскости нижепрямой.
Построим уравнение 7x₁+3x₂ = 71 по двум точкам. Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 23.67. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 10.14. Соединяем точку (0;23.67) с (10.14;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:7 • 0 + 3 • 0 - 71 ≤ 0, т.е. 7x₁+3x₂ - 71≥ 0 в полуплоскости выше прямой.

или

Шаг №2. Границы области допустимых решений.
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.

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

Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
x₁+4x₂=53
7x₁+3x₂=71
Решив систему уравнений, получим: x₁ = 5, x₂ = 12
Откуда найдем минимальное значение целевой функции:
F(X) = 9*5 + 2*12 = 69
Изменение коэффициентов целевой функции.
Изменение значений коэффициентов c₁ и c₂ приводит к изменению угла наклона прямой z. Существует интервалы изменения коэффициентов c₁ и c₂, когда текущее оптимальное решение сохраняется. Задача анализа чувствительности и состоит в получении такой информации. Необходимо определить интервал оптимальности для отношения c₁ / c₂ (или c₂ и c₁). Если значение отношения c₁ / c₂ не выходит за пределы этого интервала, то оптимальное решение в данной модели сохраняется неизменным.
Таким образом, в рамках анализа на чувствительность к изменениям коэффициентов целевой функции могут исследоваться вопросы:
1. Каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходит изменения оптимального решения.
2. На сколько следует изменить тот или иной коэффициент целевой функции, чтобы изменить статус некоторого ресурса.
На предыдущем рисунке видно, что функция достигает своего оптимума в точке, которая является пересечением прямых (x₁+4x₂=53) и (7x₁+3x₂=71). При изменении коэффициентов целевой функции эта точка останется точкой оптимального решения до тех пор, пока угол наклона линии z будет лежать между углами наклона этих прямых. Алгебраически это можно записать следующим образом:

при условии c₁ ≠ 0
или

при условии c₂ ≠ 0
Таким образом, мы получили две системы неравенств, определяющих интервал оптимальности.
При c₂ = 2

или
¹/₂ ≤ c₁ ≤ ¹⁴/₃
При c₁ = 9

или
²⁷/₇ ≤ c₂ ≤ 36
Оценка ресурсов.
На данном этапе важно проанализировать следующие аспекты:
1. На сколько можно увеличить запас некоторого ресурса для улучшения полученного оптимального значения целевой функции.
2. На сколько можно снизить запас некоторого ресурса при сохранении полученного оптимального значения целевой функции.
Оценка ресурса M1
Концевые точки отрезка определяют интервал осуществимости для ресурса M1.
Количество сырья, соответствующего точке (8,5), равно 1·8 + 4·5 = 28
Таким образом, интервал осуществимости для ресурса M1 составляет ≤ M1 ≤ 28
Вычислим значение целевой функции в этих точках:
F(8,5) = 9·8 + 2·5 = 82


Изменение области решений при увеличении запасов ресурса M1
Оценка ресурса M3
Концевые точки отрезка определяют интервал осуществимости для ресурса M3.
Количество сырья, соответствующего точке (13,10), равно 7·13 + 3·10 = 121
Таким образом, интервал осуществимости для ресурса M3 составляет ≤ M3 ≤ 121
Вычислим значение целевой функции в этих точках:
F(13,10) = 9·13 + 2·10 = 137


Изменение области решений при увеличении запасов ресурса M3
Рассмотрим теперь вопрос об уменьшении правой части неактивного ограничения (2). Не изменяя оптимального решения, прямую L2 можно опустить до пересечения с оптимальной точкой. При этом правая часть ограничения (2) станет равной x₁-x₂=-7, что позволит записать ограничение (1) в виде x₁-x₂≤-7.
y_i определяет ценность каждой дополнительной единицы дефицитного ресурса. Чем больше значение y_i, тем выше его приоритет при вложении дополнительных средств.
Теория двойственности.
Составим двойственную задачу к прямой задаче.
-y₁-y₂+7y₃≤9
-4y₁+y₂+3y₃≤2
-53y₁-3y₂+71y₃ → max
y₁ ≥ 0
y₂ ≥ 0
y₃ ≥ 0
Отметим, что решение двойственной задачи дает оптимальную систему оценок ресурсов.
Для решения двойственной задачи используем вторую теорему двойственности.
Подставим оптимальный план прямой задачи в систему ограниченной математической модели:
-1*5 -4*12 = -53 = -53
1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₁ > 0).
-1*5 + 1*12 = 7 > -3
2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y₂ = 0
7*5 + 3*12 = 71 = 71
3-ое ограничение прямой задачи выполняется как равенство. Это означает, что 3-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₃ > 0).
Поскольку x₁>0, первое ограничение в двойственной задаче будет равенством.
Поскольку x₂>0, второе ограничение в двойственной задаче будет равенством.
С учетом найденных оценок, новая система примет вид:
y₂ = 0
-y₁-y₂+7y₃ = 9
-4y₁+y₂+3y₃ = 2
-53y₁+71y₃ → max
или
-y₁+7y₃ = 9
-4y₁+3y₃ = 2
-53y₁+71y₃ → max
Решая систему графическим способом, находим оптимальный план двойственной задачи:


Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
-y₁+7y₂=9
-4y₁+3y₂=2
Решив систему уравнений, получим: y₁ = 0.52, y₂ = 1.36
Откуда найдем максимальное значение целевой функции:
F(X) = -53*0.52 + 71*1.36 = 69
y₁ = 0.52
y₃ = 1.36
Z(Y) = (-53)*0.52+71*1.36 = 69
Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов.
Обоснование эффективности оптимального плана.
При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:
1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что продукт №1 экономически выгодно производить, а его использование предусмотрено оптимальным планом прямой задачи (x₁ > 0)
(-1)*0.52 + 0*0 + 7*1.36 = 9 = 9
2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что продукт №2 экономически выгодно производить, а его использование предусмотрено оптимальным планом прямой задачи (x₂ > 0)
(-4)*0.52 + 0*0 + 3*1.36 = 2 = 2