Линейное программирование

Сентябрь 14, 2022

Главная
Математика
Линейное программирование

Содержание

2. Вопросы Постановка задачи линейного программирования Графический метод решения задач линейного программирования Симплекс-метод решения задач линейного программирования
3. 1 Постановка задачи ЛП Общая задача ЛП: Найти значения переменных x1,x2….xn, удовлетворяющих ограничениям и обращающих в
4. Допустимое решение задачи линейного программирования - это набор значений x1,x2….xn, удовлетворяющих условиям задачи. Множество всех допустимых
5. Стандартной задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции при выполнении
6. Основной задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции F при
7. Задача о распределении ресурсов Для изготовления 2-х видов продукции P1и P2 используется 4 вида ресурсов S1,
8. Требуется составить такой план производства продукции, при котором прибыль от реализации будет максимальной. x1 х2 –
9. . Задача составления рациона Имеется два вида корма I и II, содержащие питательные вещества S1, S2
10. Необходимо составить дневной рацион нужной питательности, причем затраты на него должны быть минимальными. обозначим через x1
11. 2. Графический метод решения задач линейного программирования Рассмотрим стандартную задачу линейного программирования с двумя переменными (n=2),
12. Задача линейного программирования состоит в нахождении такой точки многоугольника решений, в которой целевая функция принимает экстремальное
13. Исходная задача линейного программирования состоит в нахождении такой точки многоугольника решений, в котором целевая функция принимает
14. Алгоритм решения графическим способом В системе координат строятся прямые, уравнения которых получаются в результате замены в
15. Прямая передвигается параллельно самой себе в направлении вектора , в результате чего находят точку (точки), в
16. Задача о распределении ресурсов Необходимо определить максимум функции при условиях:
17. Решение. Построим многоугольник решений. Для этого в системе ограничений знаки неравенств заменим на знаки точных равенств
18. Найдем полуплоскости, определяемые соответствующими неравенствами и их пересечение. В результате получим многоугольник OABCDE Теперь построим прямую
19. Ответ Следовательно, при изготовлении 6 единиц продукции P1 и 4 единицы продукции P2, предприятие получит максимальную
20. Задача II Составление рациона при условиях:
21. Решение. Построим многоугольник решений. Для этого в неравенствах системы ограничений знаки неравенств заменим на знаки равенств:
22. Построив полученные прямые, найдем соответствующие полуплоскости и их пересечение построим вектор и прямую Передвигаем в направлении
23. Ответ Дневной рацион должен включать в себя 2 кг корма I и 3 кг корма II,
25. Скачать презентацию

Слайд 2

Вопросы
Постановка задачи линейного программирования
Графический метод решения задач линейного программирования
Симплекс-метод решения задач

линейного программирования
Метод искусственного базиса
Двойственность в линейном программировании

Слайд 3

1 Постановка задачи ЛП
Общая задача ЛП: Найти значения переменных x1,x2….xn, удовлетворяющих

ограничениям

и обращающих в максимум (минимум) линейную функцию этих переменных

постоянные величины

Слайд 4

Допустимое решение задачи линейного программирования - это набор значений x1,x2….xn, удовлетворяющих

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

Слайд 5

Стандартной задачей линейного программирования называется задача, которая состоит в определении максимального

(минимального) значения функции

при выполнении условий:

Слайд 6

Основной задачей линейного программирования называется задача, которая состоит в определении максимального

(минимального) значения функции F

при выполнении условий:

Слайд 7

Задача о распределении ресурсов
Для изготовления 2-х видов продукции P1и P2

используется 4 вида ресурсов S1, S2, S3, S4.

Прибыль от реализации продукции Р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 соответственно равна 4 и 6 условных единиц.

Слайд 10

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

быть минимальными.

обозначим через x1 и x2 соответственно количество килограммов корма I и II в дневном рационе. Получим следующую модель:

Слайд 11

2. Графический метод решения задач линейного программирования
Рассмотрим стандартную задачу линейного программирования

с двумя переменными (n=2), состоящую в определении максимального значения функции при условиях:

Слайд 12

Задача линейного программирования состоит в нахождении такой точки многоугольника решений, в

которой целевая функция принимает экстремальное значение.

Слайд 13

Исходная задача линейного программирования состоит в нахождении такой точки многоугольника решений,

в котором целевая функция принимает максимальное значение. Эта точка является одной из вершин многоугольника решений
Теорема Если задача ЛП имеет оптимальный план, то ЦФ достигает своего максимального значения в одной из вершин выпуклого многогранника решений.
Если ЦФ достигает максимального значения более, чем в 1-й вершине многогранника, то она достигает это значение и в любой точке, являющейся выпуклой линейной комбинацией этих вершин (в любой точке на прямолинейном отрезке, соединяющем эти вершины).

Слайд 14

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

в результате замены в ограничениях знаков неравенств на знаки точных равенств.

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

Строится вектор .

Строится прямая .

Слайд 15

Прямая передвигается параллельно самой себе в направлении вектора , в результате

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

Слайд 16

Задача о распределении ресурсов
Необходимо определить максимум функции при условиях:

Слайд 17

Решение.
Построим многоугольник решений. Для этого в системе ограничений знаки неравенств

заменим на знаки точных равенств и построим полученные прямые:

Слайд 18

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

многоугольник OABCDE

Теперь построим прямую

и вектор

Перемещаем прямую в направлении вектора. Последней ее общей точкой с многоугольником служит точка С.

Координаты С удовлетворяют уравнениям прямых I и II

Слайд 19

Ответ
Следовательно, при изготовлении 6 единиц продукции P1 и 4 единицы продукции

P2, предприятие получит максимальную прибыль, равную 24 единицам

Слайд 20

Задача II Составление рациона
при условиях:

Слайд 21

Решение.
Построим многоугольник решений. Для этого в неравенствах системы ограничений знаки неравенств

заменим на знаки равенств:

Слайд 22

Построив полученные прямые, найдем соответствующие полуплоскости и их пересечение
построим вектор

и прямую

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

А – точка пересечения прямых II и I, то ее координаты удовлетворяют уравнениям этих прямых:

Слайд 23

Ответ
Дневной рацион должен включать в себя 2 кг корма I и

3 кг корма II, при этом затраты будут составлять 26 единицам.

Линейное программирование

Содержание

ВопросыПостановка задачи линейного программированияГрафический метод решения задач линейного программированияСимплекс-метод решения задач

1 Постановка задачи ЛПОбщая задача ЛП: Найти значения переменных x1,x2….xn, удовлетворяющих

Допустимое решение задачи линейного программирования - это набор значений x1,x2….xn, удовлетворяющих

Стандартной задачей линейного программирования называется задача, которая состоит в определении максимального

Основной задачей линейного программирования называется задача, которая состоит в определении максимального

Задача о распределении ресурсов Для изготовления 2-х видов продукции P1и P2

Требуется составить такой план производства продукции, при котором прибыль от реализации

. Задача составления рациона Имеется два вида корма I и II,

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

2. Графический метод решения задач линейного программирования Рассмотрим стандартную задачу линейного программирования

Задача линейного программирования состоит в нахождении такой точки многоугольника решений, в

Исходная задача линейного программирования состоит в нахождении такой точки многоугольника решений,

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

Прямая передвигается параллельно самой себе в направлении вектора , в результате

Задача о распределении ресурсовНеобходимо определить максимум функции при условиях:

Решение. Построим многоугольник решений. Для этого в системе ограничений знаки неравенств