Графическкий метод решения ЗЛП (2)

1.

1

2. Графический метод решения ЗЛП

В линейном программировании используется графический метод, с помощью которого
определяют выпуклые множества (многогранник решений). Если основная задача линейного
программирования имеет оптимальный план, то целевая функция принимает значение в одной
из вершин многогранника решений

3.

Определение. Любое решение системы ограничений называется допустимым решением ЗЛП.
Определение. Допустимое решение, в котором целевая функция достигает максимального или минимального значения,
называется оптимальным решением.
В силу этих определений задача ЛП может быть сформулирована следующим образом: среди всех точек выпуклой области,
являющейся решением системы ограничений, выбрать такую, координаты которой минимизируют (максимизируют) линейную
функцию F = с1x + с2y.
Заметим, что переменные x, y в ЗЛП принимают, как правило, неотрицательные значения (x≥ 0, y ≥ 0), поэтому область расположена в I
четверти координатной плоскости.
Рассмотрим линейную функцию F = с1x + с2y и зафиксируем какое-нибудь ее значение F.
Пусть, к примеру, F = 0, т.е. с1x + с2y = 0.
Графиком этого уравнения будет прямая, проходящая через начало координат (0;0) (рис.).
При изменении этого фиксированного значения F = d, прямая с1x+ с2y = d будет смещаться параллельно и «зачертит» всю плоскость.
Пусть D – многоугольник – область решения системы ограничений. При изменении d прямая с1x + с2y = d, при некотором значении
d = d 1 достигнет многоугольника D, назовем эту точку А «точкой входа», и затем, пройдя многоугольник, при некотором значении
d = d2 будем иметь с ним последнюю общую точку В, назовем В «точкой выхода».
Очевидно, что своего наименьшего и наибольшего значения целевая функция F=с1x + с2y достигнет в точках «входа» А и «выхода» В.
Учитывая, что оптимальное значение на множестве допустимых решений целевая функция принимает в вершинах области D, можно
предложить следующий план решения ЗЛП:

4.

Решение задачи линейного программирования графическим методом включает
следующие этапы:
1. На плоскости X10X2 строят прямые.
2. Определяются полуплоскости.
3. Определяют многоугольник решений;
4. Строят вектор N(c1,c2),
который указывает направление целевой функции;
5. Передвигают прямую целевую функцию c1x2 + c2x2 = 0 в направлении вектора N до
крайней точки многоугольника решений.
6. Вычисляют координаты точки и значение целевой функции в этой точке.

5. Могут возникать следующие ситуации:

1. Целевая функция принимает экстремальное (минимальное или максимальное) значение
в единственной точке А.

6.

2. Целевая функция принимает экстремальное значение в любой точке отрезка АВ.

7.

3. Целевая функция не ограничена сверху (при поиске на максимум) или снизу (на
минимум)

8.

4. Система ограничений задачи несовместна

9. ПРИМЕР. Компания изготавливает два вида продукции – П1 и П2. Для производства продукции используются два вида сырья – С1 и С2.

Оптовые цены единицы
продукции равна: 5 д.е. для П1 и 4 д.е. для П2. Расход сырья на единицу
продукции вида П1 и вида П2 дан в таблице.
Таблица - Расход сырья на производство продукции
Сырье
Расход сырья на 1 ед. продукции
Максимальный запас
сырья, ед.
П1
П2
С1
6
4
24
С2
1
2
6
Установлены ограничения на спрос продукции:
ежедневный объем производства продукции П2 не должен превышать ежедневный объем производства
продукции П1 не более чем на 1 тонну;
максимальный ежедневный объем производства П2 не должен превышать 2 т.
Требуется определить:
1. Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализации
продукции был максимальным?
2. Сформулировать математическую модель задачи линейного программирования.
Решить задачу линейного программирования графическим способом (для двух переменных).

10.

Решение.
Сформулируем математическую модель задачи линейного программирования.
x1 – производство продукции П1, ед.
x2 – производство продукции П2, ед.
x1, x2 ≥ 0
Ограничения по ресурсам
6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
Ограничения по спросу
x1 +1 ≥ x2
x2 ≤ 2
Целевая функция
5x1 + 4x2 → max

11.

Тогда получаем следующую ЗЛП:
Z=5x1 + 4x2 → max
6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
x 2 - x1 ≤ 1
x2 ≤ 2
x1, x2 ≥ 0

12.

Необходимо найти максимальное значение целевой функции
F = x 1 +2x 2 → max,
при системе ограничений:
2x 1 +7x 2 ≤10, (1)
6x 1 -x 2 ≤8, (2)
8x 1 +7x 2 ≤19, (3)
x 1 ≥ 0, (4)
x 2 ≥ 0, (5)

13.

Шаг №1.
Построим область допустимых решений, т.е. решим
графически систему неравенств. Для этого построим каждую прямую и
определим полуплоскости, заданные неравенствами (полуплоскости
обозначены штрихом).
Построим уравнение 2x 1 +7x 2 ≤10 по двум точкам. Для нахождения
первой точки приравниваем x 1 = 0. Находим x 2 = 1.43.
Для нахождения второй точки приравниваем x 2 = 0. Находим x 1 = 5. Соединяем точку
(0;1.43) с (5;0) прямой линией.
Определим полуплоскость, задаваемую неравенством.
Выбрав точку (0; 0), определим знак неравенства в
полуплоскости:2 • 0 + 7 • 0 - 10 ≤ 0, т.е. 2x 1 +7x 2 - 10≤ 0 в полуплоскости
ниже прямой.

14.

Построим уравнение 6x 1 -x 2 ≤8 по двум точкам.
Для нахождения первой точки приравниваем x 1 = 0.
Находим x 2 = -8.
Для нахождения второй точки приравниваем x 2 = 0.
Находим x 1 = 1.33.
Соединяем точку (0;-8) с (1.33;0) прямой линией.
Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим
знак неравенства в полуплоскости:
6 • 0 - 1 • 0 - 8 ≤ 0, т.е. 6x 1 -x 2 - 8≤ 0 в полуплоскости ниже
прямой.

15.

Построим уравнение 8x 1 +7x 2 ≤19 по двум точкам.
Для нахождения первой точки приравниваем x 1 = 0.
Находим x 2 = 2.71.
Для нахождения второй точки приравниваем x 2 = 0.
Находим x 1 = 2.38.
Соединяем точку (0;2.71) с (2.38;0) прямой линией.
Определим полуплоскость, задаваемую неравенством.
Выбрав точку (0; 0), определим знак неравенства в
полуплоскости:8 • 0 + 7 • 0 - 19 ≤ 0, т.е. 8x 1 +7x 2 - 19≤ 0 в полуплоскости ниже прямой.

16.

17.

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

18.

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

19.

20.

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