Графическое решение задач линейного программирования. - презентация

1 Графическое решение задач линейного программирования

2 Задача линейного программирования с двумя неизвестными может быть решена графически Замечание: К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2

3 Пусть задача линейного программирования задана в виде:

4 1. Построить область допустимых решений (ОДР) в системе координат, заданную системой ограничений Алгоритм графического решения ЗЛП

5 2. Построить градиент целевой функции F = с 1 х 1 +с 2 х 2 (вектор нормали к прямой с 1 х 1 +с 2 х 2 = F) Алгоритм графического решения ЗЛП

6 3. Построить опорную прямую, перпендикулярную вектору нормали – линию уровня целевой функции Алгоритм графического решения ЗЛП

7 4. Перемещая опорную прямую в направлении вектора нормали, определить «точку входа» и «точку выхода» (первая встретившаяся опорной прямой точка из ОДР и последняя встретившаяся опорной прямой точка из ОДР соответственно) В точке входа: F min В точке выхода: F max Алгоритм графического решения ЗЛП

8 5. Определить координаты оптимальной точки (точки входа или точки выхода) и найти значение целевой функции в ней Алгоритм графического решения ЗЛП Замечание: Оптимальная точка является угловой точкой выпуклой области допустимых решений

9 Минимальное значение целевая функция достигает в точке В: F min = F(B) Максимальное значение: F max = Частные случаи

10 Минимальное значение целевая функция достигает в точке E: F min = F(E) Максимальное значение целевая функция достигает во всех точках отрезка ВС : F min = F(B)= F(C) Частные случаи

11 Решить графически ЗЛП

12 1. Построим область допустимых решений, заданную системой неравенств (см. презентацию Геометрический смысл линейного неравенства)

13 Решить графически ЗЛП 2. Построим вектор нормали N(3;4) и перпендикулярную ему опорную прямую

14 Решить графически ЗЛП 3. Перемещаем опорную прямую в направлении вектора нормали и определяем «точку выхода» Файл 04_model_01. ggb В – точка выхода

15 Решить графически ЗЛП 4. Найдем координаты точки В, как точки пересечения прямых (1) и (3)

16 Решить графически ЗЛП 4. Найдем координаты точки В, как точки пересечения прямых (1) и (3):

17 Решить графически ЗЛП 5. Найдем значение целевой функции в точке В

18 Решить графически ЗЛП Ответ:

19 Литература 1. Кремер Н.Ш., Путко Б.А. Исследование операций в экономике. - М.: ЮНИТИ, с. 2. Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах. Часть 1. - М.: Высшая школа, – C