🗊Презентация Линейное программирование

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

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

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

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

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

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

Задача о распределении ресурсов Задача о распределении ресурсов Для изготовления 2-х видов продукции P1и P2 используется 4 вида ресурсов S1, S2, S3, S4.

Требуется составить такой план производства продукции, при котором прибыль от реализации будет максимальной. 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

. Задача составления рациона Имеется два вида корма I и II, содержащие питательные вещества S1, S2 и S3.

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

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

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

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

Алгоритм решения графическим способом

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

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

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

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

Ответ Следовательно, при изготовлении 6 единиц продукции P1 и 4 единицы продукции P2, предприятие получит максимальную прибыль, равную 24 единицам

Задача II Составление рациона

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

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

Ответ

Вопросы Определите общую задачу линейного программирования Определите основную задачу линейного программирования Определите стандартную задачу линейного программирования Теорема Алгоритм решения графическим способом