Содержание
Ситуация 1 3
Ситуация 2 6
Ситуация 3 12
Ситуация 1
Решить задачу линейного программирования графическим способом
Решение:
1. Построим допустимых область решений системы ограничений
Решением каждого ограничения системы является полуплоскость с граничащей ей прямой.
Построим прямую . Она проходит через точки (0;4) и (-10;0). Для того чтобы определить, какая плоскость удовлетворяет неравенству, необходимо выбрать любую точку не принадлежащую прямой. Выберем точку начала координат (0;0), подставим в неравенство и получим 0 < 20. Данное утверждение является верным, следовательно, неравенству соответствует полуплоскость, включающая точку (0;0).
Построим прямую . Она проходит через точки (0; 12,25) и (9,8; 0). Выберем точку начала координат (0;0), подставим в неравенство и получим 0 > 49. Данное утверждение не является верным, следовательно, неравенству соответствует полуплоскость, не включающая точку (0;0).
Построим прямую . Она проходит через точки (0;-16) и (8;0). Выберем точку начала координат (0;0), подставим в неравенство и получим 0 < 16. Данное утверждение является верным, следовательно, неравенству соответствует нижняя полуплоскость, включающая точку (0;0).
Рисунок 1 – Решение задачи графическим методом
Пересечение этих полуплоскостей, каждая из которых определяется соответствующим неравенством системы и удовлетворяет условиям, определяет выпуклый Треугольник АВС.
Треугольник АВС – область допустимых значений системы ограничений, любая точка этого многоугольника является допустимым решением задачи.
2. Найдем оптимальное решение
Оптимальное решение может быть только в угловых точках треугольника т. А, т. В, т. С.
Чтобы найти оптимальное решение можно найти координаты всех угловых точек, вычислить значение целевой функции во всех угловых точках. Наименьшее из этих значений и будет минимальным значением целевой функции, а координаты соответствующей угловой точки – оптимальным решением.
Существует другой способ, который позволяет графически сразу найти угловую точку, соответствующую оптимальному решению. Для этого построим линию уровня.
Приравняем целевую функцию постоянной величине а:
Это уравнение является множеством точек, в котором целевая функция принимает значение, равное а. Меняя значение а, получим семейство параллельных прямых, каждая из которых называется линией уровня
Пусть а = 0, тогда построим линию уровня . Вычислим координаты двух точек, удовлетворяющих соответствующему уравнению. В качестве одной из этих точек удобно взять точку О (0;0), а в качестве второй точки возьмем точку (1; 5).
Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными производными функции цели