Эконоико-математические модели управления

Эконоико-математические модели управления Задача линейного программирования Математическое программирование изучает задачи поиска экстремума (минимума или максимума) функции нескольких переменных при наличии ограничений на эти переменные. Сущность экстремальных задач состоит в том, чтобы из множества допустимых наборов значений выбрать оптимальный с определенной точки зрения. 2 Математическая модель задачи линейного программирования (ЗЛП) имеет следующие составные части: (1) (2) позволяет выбирать оптимальный, т. е. наилучший план из множества возможных планов ЗЛП. В экономике целевая функция может представлять собой прибыль, издержки производства, объем реализации и т. п. 3 Стандартной формой ЗЛП называют: (3) при ограничениях: (4) 4 В свернутом виде ЗЛП имеет вид: (5) (6) 5 Если система ограничений представляет собой систему уравнений, можно использовать методы решения систем линейных алгебраических уравнений из линейной алгебры. ЗЛП в канонической форме имеет вид: (7) при ограничениях: (8) 6  матрица коэффициентов системы ограничений: (9)  матрица-строка коэффициентов целевой функции: (10)  матрица-столбец свободных членов: (11)  матрицастолбец неизвестных: (12) 7 Тогда каноническую форму записи ЗЛП можно представить в следующем матричном виде, эквивалентном первоначальному: (13) (14) где 0 - нулевая матрица-столбец той же размерности, что и Х. В математике и информатике каноническая, нормальная или стандартная форма математического объекта - это стандартный способ представления этого объекта в виде математического выражения. Часто это тот, который обеспечивает простейшее представление объекта и который позволяет идентифицировать его уникальным способом. 8 (15) (16) 9 или в свернутой форме с использованием символов суммирования: (17) (18) 10 Условный пример: Привести задачу линейного программирования к канонической форме: Решение. Введем в каждое неравенство системы ограничений выравнивающие переменные x4, x5, x6. Запишем систему в виде равенств. В первое и третье уравнения x4, x6 вводятся в левую часть со знаком «+», а во второе уравнение вводится x5 со знаком «-». 11 Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на (-1): 12 Допустим, что Подставляя данное выражение в систему ограничений и целевую функцию и записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме: 13 Графический метод эффективно применяется в случае двух переменных: х1 и x2. Пусть математическая формулировка задачи линейного программирования (ЗЛП) имеет вид: (1) при ограничениях: (2) 14 Графический метод решения ЗЛП состоит в следующем. - Областью решений линейного неравенства ai1x1 + ai2x2 ≤ bi является одна из двух полуплоскостей, на которые прямая ai1x1 + ai2x2 = 0, соответствующая данному неравенству, делит всю координатную плоскость. Для того, чтобы определить, какая из двух координатных полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство. Если оно удовлетворяется, то областью решений является полуплоскость, содержащая данную точку. В противном случае, областью решений является полуплоскость, не содержащая данную точку. 15 2. Строится вектор-градиент* целевой функции (рис. 1) и ее линия уровня l, прямая, перпендикулярная вектору градиента и проходящая, например, через начало координат. *Градие́нт (от лат. gradiens, род. п. gradientis «шагающий, растущий») — вектор, своим направлением указывающий направление наибольшего возрастания некоторой скалярной величины φ, (значение которой меняется от одной точки пространства к другой, образуя скалярное поле), а по величине (модулю) равный скорости роста этой величины в этом направлении. 16 Рис. 1. Область допустимых значений и вектор-градиент 17 Данное обстоятельство запишем в виде: 4. Если при таком перемещении окажется, что линия уровня совпадает с одной из сторон области допустимых решений, то ЗЛП имеет бесконечное множество решений. 5. Если же вдруг окажется, что первой (последней) точки не существует, то задача отыскания min (max) целевой функции Q является неразрешимой. 18 Двумерные задачи линейного программирования решаются графически. Для случая n = 3 можно рассмотреть трехмерное пространство, и целевая функция будет достигать своего оптимального значения в одной из вершин трехмерного многогранника. Основная идея симплекс-метода состоит в следующем. Этот метод является универсальным, применимым к любой задаче линейного программирования представленной в канонической форме. Система ограничений - система линейных уравнений, в которой количество неизвестных больше количества уравнений (n < m). Если ранг системы равен n, то мы можем выбрать n неизвестных, которые выразим через остальные неизвестные. Приведем ЗЛП к канонической форме. Задача оформляется в виде симплекс таблицы (табл.). Таблица - Первоначальный вид симплекс-таблицы Порядок работы с симплекс таблицей Рисунок - Схема преобразования элементов симплекс-таблицы Решение. Составим математическую модель задачи. Пусть x1 - количество корпусов типа А, х2 - количество корпусов типа В, которые должны быть произведены в неделю (по смыслу задачи эти переменные неотрицательны). Таким образом, приходим к задаче линейного программирования. Решим задачу симплекс-методом. Введем три дополнительные переменные x3, x4, x5 и придем к задаче: В качестве опорного плана выберем: Составим симплекс-таблицу. В последней оценочной строке есть отрицательные элементы, поэтому нужно делать шаг симплекс-метода. Выбираем столбец с наименьшей оценкой, а затем разрешающий элемент по наименьшему отношению свободных членов к коэффициентам столбца. Результат шага запишем в таблицу (разрешающий элемент будем выделять жирным). Аналогично будем повторять шаги, пока не придем к таблице с неотрицательными оценками. Итак, разрешающий элемент: min отрицательный -4, следовательно это разрешающий столбец. Ищем min (элементы плана делим на элементы разрешающего столбца):