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

Август 19, 2022

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

Содержание

2. Этапы графического решения задачи линейного программирования 1. Строят прямые, уравнения которых получаются в результате замены в
3. f(X) = 2x1-5x2→max Целевая функция: Ограничения: 3x1 + 2x2 ≥ 6 (1) X1 ≤ 4 (2)
4. Построение области допустимых планов 1) Построение границы 1: 3x1 + 2x2 = 6 – прямая линия
5. 2 0 3 (1) х1 х2
6. 2) Построение границы 2: х1 = 4 –прямая линия Решение неравенства 2: 0 ≤ 4 –
7. 0 3 х1 х2 2 4 6 6 4 Многоугольник ABCDEF является областью допустимых планов. Координаты
8. II. Оптимизация целевой функции: 1) Построение линии уровня целевой функции: Линия, на которой функция принимает одно
9. II. Оптимизация целевой функции: 2) Построение градиента: g = (2; -5) – (коэффициенты при Х в
10. 0 3 х1 х2 2 4 6 6 4 -5
11. 0 3 х1 х2 2 4 6 6 4 -5
12. Передвигаем линию уровня в направлении градиента (если задача на max), при этом значение целевой функции возрастает.
13. 0 3 х1 х2 2 4 6 6 4 -5 Х*
14. Оптимальный план Х* совпадает с точкой D. Чтобы вычислить значения плана необходимо вычислить координаты точки пересечения
15. Оптимальный план Х* = (4; 0) Максимальное значение целевой функции: max f(X) = f(X*) = 2*4
16. Непустое множество планов основной задачи линейного программирования образует выпуклый многогранник. Каждая вершина этого многогранника определяет опорный
17. Таким образом, исходная задача линейного программирования состоит в нахождении такой точки многоугольника решений, в которой целевая
18. При нахождении решения могут встретиться случаи, изображенные на рис. 1 - 4. Из рис. 2 видно,
19. На рис. 3 изображен случай, когда целевая функция не ограничена сверху на множестве допустимых решений. На
20. Пример. Для производства двух видов изделий А и В предприятие использует три вида сырья. Нормы расхода
21. Учитывая, что изделия А и В могут производиться в любых соотношениях (сбыт обеспечен), требуется составить такой
23. Скачать презентацию

Слайд 2

Этапы графического решения задачи линейного программирования
1. Строят прямые, уравнения которых получаются

в результате замены в ограничениях знаков неравенств на знаки точных равенств.
2. Находят полуплоскости, определяемые каждым из ограничений задачи.
3. Находят многоугольник решений.
4. Строят вектор-градиент целевой функции .
5. Строят линию уровня целевой функции , проходящую через многоугольник решений.
6. Передвигают прямую в направлении вектора , в результате чего-либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность сверху функции на множестве планов.
7. Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке.

Слайд 3

f(X) = 2x1-5x2→max Целевая функция:
Ограничения:
3x1 + 2x2 ≥ 6 (1)
X1 ≤ 4 (2)
X2

≤ 4 (3)
X1 + x2 ≤ 6 (4)
X1 ≥ 0 , x2 ≥ 0 (5-6)

Математическая модель задачи.

Слайд 4

Построение области допустимых планов
1) Построение границы 1: 3x1 + 2x2 =

6 – прямая линия
Решение неравенства 1: Подставляем координаты точки О(0;0) в неравенство: 3*0 + 2*0 ≥ 6-неверно, следовательно точка О не принадлежит области допустимых планов.

Слайд 5

2
0
3
(1)
х1
х2

Слайд 6

2) Построение границы 2: х1 = 4 –прямая линия
Решение неравенства 2:

0 ≤ 4 – верно
3) Построение границы 3: х2 = 4 – прямая линия
Решение неравенства 3: 0 ≤ 4 – верно
4)Построение границы 4: х1 + x2 = 6 – прямая линия
Решение неравенства 4: 0 + 0 ≤ 6 - верно

Слайд 7

0
3
х1
х2
2
4
6
6
4
Многоугольник ABCDEF является областью допустимых планов. Координаты любой точки многоугольника, в

том числе его границ являются допустимым планом задачи.
Например точки (2;2), (3;2), (3;1)
Значение целевой функции F(X)=2x1-5x2 в этих точках равны соответственно -6, -4, 1.

Слайд 8

II. Оптимизация целевой функции:
1) Построение линии уровня целевой функции:
Линия, на которой

функция принимает одно и то же значение. (линия уровня)
f (X) = 0 => 2x1-5x2 = 0

Слайд 9

II. Оптимизация целевой функции:
2) Построение градиента:
g = (2; -5) – (коэффициенты

при Х в целевой функции)
Градиент - вектор, направление которого показывает максимальную скорость роста этой функции.

Слайд 10

0
3
х1
х2
2
4
6
6
4
-5

Слайд 11

0
3
х1
х2
2
4
6
6
4
-5

Слайд 12

Передвигаем линию уровня в направлении градиента (если задача на max), при

этом значение целевой функции возрастает. Если задача на min, то - в направлении, противоположном градиенту.
Последняя точка контакта линии уровня с областью допустимых планов определяет оптимальный план (Х*), на котором целевая функция принимает max (или min) значение.

Слайд 13

0
3
х1
х2
2
4
6
6
4
-5
Х*

Слайд 14

Оптимальный план Х* совпадает с
точкой D.
Чтобы вычислить значения плана необходимо

вычислить координаты точки пересечения соответствующих границ, где он находиться.
Х* (2) ∩ (5)
Х1 = 4
Х2 = 0

Координаты являются решением системы уравнений, прямых в результате пересечения которых получается точка Х*

Слайд 15

Оптимальный план Х* = (4; 0)
Максимальное значение целевой функции:
max f(X) =

f(X*) = 2*4 – 5*0 = 8

Слайд 16

Непустое множество планов основной задачи линейного программирования образует выпуклый многогранник. Каждая

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

Слайд 17

Таким образом, исходная задача линейного программирования состоит в нахождении такой точки

многоугольника решений, в которой целевая функция F принимает максимальное значение. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим линию уровня, проходящую через многоугольник решений, и будем передвигать ее в направлении вектора до тех пор, пока она не пройдет через ее последнюю общую точку с многоугольником решений. Координаты указанной точки и определяют оптимальный план данной задачи.
Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств.

Слайд 18

При нахождении решения могут встретиться случаи, изображенные на рис. 1 -

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

Рис. 1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А (вершине многоугольника).

Слайд 19

На рис. 3 изображен случай, когда целевая функция не ограничена сверху

на множестве допустимых решений.

На рис. 4 – случай, когда система ограничений задачи несовместна.

Слайд 20

Пример.
Для производства двух видов изделий А и В предприятие использует три

вида сырья. Нормы расхода сырья каждого вида на изготовление единицы продукции данного вида приведены в табл. В ней же указаны прибыль от реализации одного изделия каждого вида и общее количество сырья данного вида, которое может быть использовано предприятием.
Определить оптимальный план выпуска продукции, при котором прибыль будет максимальной.

Слайд 21

Учитывая, что изделия А и В могут производиться в любых соотношениях

(сбыт обеспечен), требуется составить такой план их выпуска, при котором прибыль предприятия от реализации всех изделий является максимальной,
Математическая модель задачи: среди всех неотрицательных решений данной системы линейных неравенств требуется найти такое, при котором функция F принимает максимальное значение.

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

Содержание

Этапы графического решения задачи линейного программирования1. Строят прямые, уравнения которых получаются

f(X) = 2x1-5x2→max Целевая функция:Ограничения:3x1 + 2x2 ≥ 6 (1)X1 ≤ 4 (2)X2

Построение области допустимых планов1) Построение границы 1: 3x1 + 2x2 =

203(1)х1х2

2) Построение границы 2: х1 = 4 –прямая линияРешение неравенства 2:

03х1х224664Многоугольник ABCDEF является областью допустимых планов. Координаты любой точки многоугольника, в

II. Оптимизация целевой функции:1) Построение линии уровня целевой функции:Линия, на которой

II. Оптимизация целевой функции:2) Построение градиента:g = (2; -5) – (коэффициенты

03х1х224664-5

03х1х224664-5

Передвигаем линию уровня в направлении градиента (если задача на max), при

03х1х224664-5Х*

Оптимальный план Х* совпадает с точкой D.Чтобы вычислить значения плана необходимо

Оптимальный план Х* = (4; 0)Максимальное значение целевой функции:max f(X) =

Непустое множество планов основной задачи линейного программирования образует выпуклый многогранник. Каждая

Таким образом, исходная задача линейного программирования состоит в нахождении такой точки

При нахождении решения могут встретиться случаи, изображенные на рис. 1 -

На рис. 3 изображен случай, когда целевая функция не ограничена сверху

Пример.Для производства двух видов изделий А и В предприятие использует три

Учитывая, что изделия А и В могут производиться в любых соотношениях

Похожие презентации

Этапы графического решения задачи линейного программирования
1. Строят прямые, уравнения которых получаются

f(X) = 2x1-5x2→max Целевая функция:
Ограничения:
3x1 + 2x2 ≥ 6 (1)
X1 ≤ 4 (2)
X2

Построение области допустимых планов
1) Построение границы 1: 3x1 + 2x2 =

2
0
3
(1)
х1
х2

2) Построение границы 2: х1 = 4 –прямая линия
Решение неравенства 2:

0
3
х1
х2
2
4
6
6
4
Многоугольник ABCDEF является областью допустимых планов. Координаты любой точки многоугольника, в

II. Оптимизация целевой функции:
1) Построение линии уровня целевой функции:
Линия, на которой

II. Оптимизация целевой функции:
2) Построение градиента:
g = (2; -5) – (коэффициенты

0
3
х1
х2
2
4
6
6
4
-5

0
3
х1
х2
2
4
6
6
4
-5

0
3
х1
х2
2
4
6
6
4
-5
Х*

Оптимальный план Х* совпадает с
точкой D.
Чтобы вычислить значения плана необходимо

Оптимальный план Х* = (4; 0)
Максимальное значение целевой функции:
max f(X) =

Пример.
Для производства двух видов изделий А и В предприятие использует три