Похожие презентации:
Линейное программирование
1. Линейное программирование
2. Вопросы
Постановказадачи
линейного
программирования
Графический
метод
решения
задач
линейного программирования
Симплекс-метод решения задач линейного
программирования
Метод искусственного базиса
Двойственность
в
линейном
программировании
3. 1 Постановка задачи ЛП
Общая задача ЛП: Найти значения переменныхx1,x2….xn, удовлетворяющих ограничениям
n
aij x j bi (i 1, k )
j 1
n
aij x j bi (i k 1, m
j 1
x 0
и обращающих в максимум
( j 1, n)
j
(минимум) линейную функцию этих
переменных
n
F cjxj
j 1
min(max)
a ,b , c
ij
i
j
постоянные
величины
4.
Допустимое решение задачи линейногопрограммирования - это набор значений
x1,x2….xn, удовлетворяющих условиям
задачи.
Множество всех допустимых решений
называется областью допустимых
решений.
Допустимое решение, при котором
линейная целевая функция F принимает
свое
максимальное
(минимальное)
значение, называется оптимальным.
5.
Стандартнойзадачей
линейного
программирования
называется задача, которая состоит в определении
максимального (минимального) значения функции
n
F c j x j
j 1
при выполнении условий:
n
,
i
1
,
m
a
x
b
ij
j
i
j 1
x 0, j 1, n
j
6. Основной задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функ
Основной задачей линейного программированияназывается задача, которая состоит в определении
максимального (минимального) значения функции F
n
F c j x j
j 1
при выполнении
условий:
n
a ij x j b i , i 1, m
j 1
x 0, j 1, n
j
7.
Задача о распределении ресурсовДля изготовления 2-х видов продукции P1и P2 используется 4
вида ресурсов S1, S2, S3, S4.
Вид ресурса
Запас ресурса
Число единиц ресурсов, расходуемых
на изготовление единиц
продукции
P1
P2
S1
18
1
3
S2
16
2
1
S3
5
0
1
S4
21
3
0
Прибыль от реализации продукции Р1 – 2 , Р2 – 3.
8. Требуется составить такой план производства продукции, при котором прибыль от реализации будет максимальной.
x1 х2 – число единиц продукции Р1 и Р2.Система ограничений будет следующая:
х1+3х2 ≤ 18
2х1+х2 ≤ 16
х2 ≤ 5
3х1≤ 21
х1 ≥ 0 х2 ≥ 0
Прибыль составит: F= 2х1+3х2 →max
9. . Задача составления рациона
Имеется два вида корма I и II, содержащие питательныевещества S1, S2 и S3.
Питательные
вещества
Необходимый
минимум
питательных
веществ
Число единиц
питательных веществ в
1 кг корма
I
II
S1
9
3
1
S2
8
1
2
S3
12
1
6
Стоимость 1 кг корма I и II соответственно равна 4 и 6 условных
единиц.
10. Необходимо составить дневной рацион нужной питательности, причем затраты на него должны быть минимальными.
обозначим через x1 и x2 соответственно количество килограммовкорма I и II в дневном рационе. Получим следующую модель:
F 4x 6x
1
2
3 x1 x 2 9
x1 2 x 2 8
x1 6 x 2 12
x1 0, x 2 0
min
11. 2. Графический метод решения задач линейного программирования
Рассмотрим стандартную задачу линейного программированияс двумя переменными (n=2), состоящую в определении
максимального значения функции при условиях:
F c1 x1 c 2 x 2
a i1 x1 a i 2 x 2 bi
x j 0, j 1,2
i 1, k
12. Задача линейного программирования состоит в нахождении такой точки многоугольника решений, в которой целевая функция принимает экстрема
Задача линейного программирования состоит в нахождении такойточки многоугольника решений, в которой целевая функция принимает
экстремальное значение.
13.
Исходная задача линейного программирования состоитв нахождении такой точки многоугольника решений, в
котором целевая функция принимает максимальное
значение. Эта точка является одной из вершин
многоугольника решений
Теорема Если задача ЛП имеет оптимальный план,
то ЦФ достигает своего максимального значения в
одной из вершин выпуклого многогранника решений.
Если ЦФ достигает максимального значения более,
чем в 1-й вершине многогранника, то она достигает
это значение и в любой точке, являющейся выпуклой
линейной комбинацией этих вершин (в любой точке на
прямолинейном отрезке, соединяющем эти вершины).
14. Алгоритм решения графическим способом
В системе координат строятся прямые, уравнения которых получаются врезультате замены в ограничениях знаков неравенств на знаки точных
равенств.
Находятся полуплоскости, определяемые каждым из ограничений
задачи. Определяется многоугольник решений.
Строится вектор .
Строится прямая .
C c1 , c 2
c x c x
1
1
2
2
const
15.
Прямаяпередвигается параллельно самой себе
в
направлении вектора , в результате чего находят точку
(точки), в которой целевая функция принимает максимальное
значение или устанавливают неограниченность сверху
функции на множестве допустимых решений.
Определяются координаты точки максимума функции и
вычисляется значение целевой функции в этой точке.
16. Задача о распределении ресурсов
Необходимо определить максимум функции при условияхF 2 x1 3 x 2
x1 3 x 2 18
2 x1 x 2 16
x2 5
3 x1 21
0, 0
x2
x1
:
17. Решение.
Построим многоугольник решений. Для этого в системеограничений знаки неравенств заменим на знаки точных
равенств и построим полученные прямые:
3 18
x2
x1
2 x1 x 2 16
x2 5
3 x
21
1
x1 0, x 2 0
I
II
III
IV
V ,VI
18.
Найдем полуплоскости, определяемые соответствующиминеравенствами и их пересечение. В результате получим
многоугольник OABCDE
Теперь построим прямую
и вектор
2 x1 3 x 2 0
C 2,3
Перемещаем прямую в направлении
вектора. Последней ее общей точкой
с многоугольником служит точка С.
Координаты С
удовлетворяют уравнениям
прямых I и II
x1 3 x 2 18
2 x1 x 2 16.
19. Ответ
x1 6, x 2 4Следовательно,
при
продукции P1 и 4
предприятие получит
равную 24 единицам
F max 2 6 3 4 24
изготовлении
6
единиц
единицы продукции P2,
максимальную прибыль,
20. Задача II Составление рациона
F 4 x1 6 x2 minпри условиях:
3 x1 x 2 9
x1 2 x 2 8
x1 6 x 2 12
0, 0
x2
x1
21. Решение.
Построим многоугольник решений. Для этого внеравенствах системы ограничений знаки неравенств
заменим на знаки равенств:
3 9
x1 x 2
x1 2 x 2 8
x1 6 x 2 12
x1 0, x 2 0
I
II
III
IV ,V
22.
Построив полученные прямые, найдем соответствующиеполуплоскости и их пересечение
построим вектор
и прямую
C 4,6
4 x1 6 x 2 12
Передвигаем в направлении вектора, ближайшей общей точкой
с областью допустимых решений является т. А. В этой точке
функция F принимает минимальное значение.
А – точка пересечения прямых II
и I, то ее координаты
удовлетворяют уравнениям этих
прямых:
3x1 x 2 9
x1 2 x 2 8.
23. Ответ
x1 2, x 2 3F min 4 2 6 3 26
Дневной рацион должен включать в себя 2 кг корма I и 3 кг
корма II, при этом затраты будут составлять 26 единицам.
24. Вопросы
1.2.
3.
4.
5.
Определите общую задачу линейного
программирования
Определите
основную
задачу
линейного программирования
Определите
стандартную
задачу
линейного программирования
Теорема
Алгоритм
решения
графическим
способом