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

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

Манасян С.К.,
Преподаватель КТСТ

2. Найти максимальное значение целевой функции

F = 4x+6y → max,
• при системе ограничений:
5x+4y≤40, (1)
5x+2y≤35, (2)
x+4y≤24,
(3)
x ≥ 0, y ≥ 0,

3. Шаг 1. Построим область допустимых решений

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

4. Рис. 1. Область допустимых решений (ОДР)

5. Шаг 2. Границы области допустимых решений

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

6. Рис. 2. Границы ОДР

7. Шаг 3. Рассмотрим целевую функцию

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

8. Рис. 4. Максимум ЦФ при выполнении ограничений

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

• Прямая F(x) = const пересекает область в
точке C. Так как точка C получена в
результате пересечения прямых (1) и (3), то
ее координаты удовлетворяют уравнениям
этих прямых:
5x+4y=40
x+4y=24
Решив систему уравнений, получим:
• x = 4, y = 5

10. Максимальное значение целевой функции

• Решая систему (1),(3):
5x+4y≤40, (1)
x+4y≤24,
(3)
• найдем максимальное значение целевой
функции:
F(X) = 4*4 + 6*5 = 46