Методы оптимизации и модели в экономике

включает в себя три основных этапа: 1) построение математической модели; 2) определение оптимального решения математическим методом; 3) анализ и интерпретация полученного решения На первом этапе определяется: 1)цель исследования; 2) ограничения задачи; 3) осуществляется количественное выражение всех данных задачи Цель задачи оптимизации Цель характеризуется признаком (критерием), по которому сравниваются различные варианты решения, например: наибольшая прибыль, наименьшие издержки, максимальное использование оборудования, достижение определенного результата в минимальное время, наименьшие отходы производства и т.п. Замечание Единого критерия быть не может, как не может быть универсального показателя экономического объекта. В каждой задаче выбирается тот из показателей, который в данном случае представляется наиболее важным. построение мат. модели ресурсов условий построение мат. модели Все ограничения задачи должны быть непротиворечивыми, то есть обеспечивающими существование хотя бы одного решения. Неучет какого-либо ограничения может привести к неосуществимости полученного оптимального решения. С другой стороны чрезвы чайно жесткие ограничения могут сузить область возможных решений и не дадут выявить оптимальное. построение мат. модели max (min) F(x 1, x 2, x 3, …, x n) = c 1x 1 + c 2x 2 + c 3x 3 +… +c n x n, (1) x1, x2, x3, …, xn (2) Σ aij x i = (≥, ≤) b i xi ≥ 0 где i = 1,2,3,…m, j = 1,2,3,…,n Замечание Задачи ЛП могут быть представлены в: общем виде каноническом виде (3) (1) max (c 1x 1 + c 2x 2 + c 3x 3 +… +c nx n ) (2) Σ aij x i ≤ b i (3) xi ≥ 0 где bi ≥ 0, i = 1,2,3,…m, j = 1,2,3,…,n Величины x 1, x 2, x 3, …, x n – инструментальные переменные - составляющие n-мерного вектора столбца. Используемые в задаче константы левой части ограничений состоят из коэффициентов aij , входящих в матрицу А размерности mxn. Константы ограничений b 1, b 2, b 3, …, b m являются компонентами вектора-столбца b. Константы постоянных коэффициентов целевой функции c 1, c 2, c 3, …, c n – компоненты вектора-строки цен c. Предположим, что: m и n конечные числа; матрица A и векторы b и c состоят из фиксированных вещественных чисел; x – любой вещественный вектор, удовлетворяющий m+n ограничениям задачи, тогда: 1. условия неотрицательности переменных x i ≥ 0 представляет неотрицательный ортант n-мерного евклидова пространства En 2. каждое из m ограничений-неравенств определяет замкнутое полупространство в En (множество точек, либо принадлежащих гиперплоскости, либо расположенных по одну сторону от этой гиперплоскости) Тогда в общем случае множество допустимы х решений задачи представляет собой вы пуклое многогранное множество или вы пуклы й многогранник, если это множество ограничено. Таким образом, множество всех инструментальных векторов, удовлетворяющих m+n ограничениям неотрицательности и ограничениям-неравенствам общего вида представляет собой замкнутое выпуклое многогранное множество, расположенное в неотрицательном ортанте nмерного евклидова пространства En Например, для пространства E2 и E3, множество допустимых решений задачи может быть в виде выпуклого многоугольника и многогранника: С геометрической точки зрения задача ЛП состоит в отыскании точки (множества точек) в nмерном пространстве, принадлежащей допустимому выпуклому многогранному множеству, в которой достигается поверхность наибольшего уровня. Эта точка должна принадлежать границе допустимого множества решений задачи. Таким образом, решением задачи ЛП будет одна вершина или несколько вершин и все точки, лежащие между этими вершинами (множество точек), т.е. все вы пуклы е линейны е комбинации этих вершин. Направление наискорейшего роста целевой функции задается градиентом, т.е. вектором-строкой из En, ортогональным к поверхности уровня. или grad F = {c 1,c 2,c 3, …,c n } С геометрической точки зрения задача ЛП состоит в отыскании крайней точки (или точек) в En в направлении вектора-градиента множества допустимых решений задачи. Т.е. решение достигается в той точке (тех точках), где поверхность уровня представляет собой опорную гиперплоскость данного выпуклого многогранного допустимого множества. Отыскание max целевой функции в пространстве E2 В А Единственное решение в точке А А Решение достигается в точках А и В, а также во всех точках отрезка [АВ] Отыскание max целевой функции в пространстве E3 В трехмерном пространстве решением моет быть точка вершины (пересечение трех или более граней), отрезок прямой (пересечение двух граней) или часть некоторой плоскости (грань). Замечание Хотя решение задачи ЛП может быть неединственным, максимальное значение целевой функции единственно. Так как допустимое множество выпукло, а целевая функция линейна, то по теореме о достаточных условиях существования максимума локальный максимум является глобальным. Следовательно, если в вершине допустимого множества целевая функция принимает значение большее ( ≥ ), чем во всех соседних вершинах, то данная вершина является решением задачи. На этом свойстве основан алгоритм симплексметода решения задач ЛП. Если n>m, то решение достигается в такой вершине допустимого множества, в которой по меньшей мере n-m переменных равны нулю. Т.е. хотя бы одна из точек решения имеет по крайней мере столько ненулевых координат, сколько ограничений-неравенств входит в формулировку задачи. Замечание Так как целевая функция непрерывна, то по теореме Вейерштрасса решение существует в том случае, если допустимое множество непусто и ограничено. Значит, возможны случаи, когда задача ЛП не может иметь решения: ограничения задачи несовместимы; многогранная область допустимых решений задачи неограничена. Задача ЛП не может иметь решения Наибольшего решения не достигнуть в области допустимых решений Допустимая область решений пуста Для решения задач ЛП разработаны несколько методов: симплекс-метод или М-метод (универсальный);  метод потенциалов решения транспортных задач; метод Мака решения задач о назначениях;  графический метод Графически могут решаться: 1.задачи, заданные в общем виде с числом переменны х не более двух; 2.задачи, заданные в канонической виде с числом свободных переменных n-m ≤ 2; 3.задачи в произвольной форме записи, которые после приведения к канонической форме будут содержать не более двух свободных переменных Наиболее часто графическим методом решают задачи, записанные в общем виде с числом переменных не более двух. Решение задачи ЛП графическим методом состоит из нескольких этапов: 1.свести задачу ЛП к общему виду; 2.построить в евклидовом допустимых решений; пространстве E2 область 3.построить вектор-градиент grad F = {c 1,c 2}; 4.отыскать крайнюю точку или точки выпуклой многоугольной области при помощи перемещения линий уровня целевой функции в направлении вектора-градиента. Построение области допустимы х решений в E2 Возможные варианты области допустимых решений Трикотажная фабрика для выпуска свитеров и кофт использует 3 вида сырья: шерсть, вискозу и нейлон. Ежемесячные запасы трех видов сырья составляют 1000 кг, 1100 кг и 400 кг соответственно. Количество пряжи каждого вида, необходимое на изготовление 10 изделий, а также прибыль от реализации занесены в таблицу: Расход сырья на 10 изделий Запасы Сырье, кг сырья, кг свитера кофты шерсть 1 вискоза 2 нейлон Определить план вы пуска изделий Прибыль, д.ед. 6 2 1000 1 1100 1 400 максимизирую щий 5 прибы ль фабрики. Сырье, кг Расход сырья на 10 изделий свитера кофты Запасы сырья, кг шерсть 1 2 1000 вискоза 2 1 1100 нейлон 1 400 Пусть x 1, x 2 - количество десятков выпущенных свитеров и Прибыль, д.ед. 6 5 кофт за месяц. Тогда целевая функция задачи – функция прибыли – будет иметь вид: F(x 1, x 2) = 6x 1 +5x 2 Цель задачи: max(6x 1 +5x 2) Запишем ограничения задачи: x 1 + 2x 2 ≤ 1000 2x 1 + x 2 ≤ 1100 x 2 ≤ 400 при x , x ≥ 0 x 1 + 2x 2 ≤ 1000 2x 1 + x 2 ≤ 1100 x 2 ≤ 400 grad F = {6,5} g {600,500} Графически целевая функция представляет собой линию уровня. Линия уровня перпендикулярна вектору-градиенту и характерна постоянством значения функции в каждой ее точке. l* Линия уровня, для которой все точки многоугольной области допустимых решений лежат по одну сторону от нее, называется опорной прямой. Обозначим ее l* l* Тогда точка А будет точкой max целевой функции Несложно определить ее координаты: А(400; 300) l* А Так как точка А (400; 300) - точка максимума целевой функции, то можем утверждать: 1.выпуск свитеров в объеме 4000 штук; 2.выпуск кофточек в объеме 3000 штук; 3.прибыль от реализации этого объема свитеров и кофточек: Значение целевой функции в точке максимума: 6*400 + 5*300 = 3900 у.ед. Ответ: 3900 (4000; 3000) Направление наискорейшего роста целевой функции задается градиентом, т.е. вектором-строкой из En, ортогональным к поверхности уровня. или gradF = {x 1,x 2,x 3, …,x n } С геометрической точки зрения задача ЛП состоит в отыскании крайней точки (или точек) в En в направлении вектора-градиента множества допустимых решений задачи. Под ресурсами понимают:  запасы сы рья, электроэнергии, топлива, трудовы е ресурсы , ресурсы оборудования, посевны е площади и т.д. Для записи ресурсных ограничений (ограничения общего вида) нужно определить какие ресурсы являются лимитирующими, сдерживающими. постановка зада чи В систему ограничений могут входить такие характеристики или дополнительные условия, как:  условия комплектности; обязательности ассортимента; плановы е задания по вы пуску; и т.п. постановка задачи  Решение единственно и достигается в одной из вершин выпуклого многоугольника области допустимых решений задачи  Решение не единственное (наличие альтернативных оптимальных планов задачи)  Решение отсутствует Например, неравенство противоречит неотрицательности переменны х задачи. Или Неравенства противоречат друг другу. ограничения f = 2∙x1 + 3∙x2 x1 + x2 ≥ 10 3x1 + 5x2 ≤ 15 x1, x2 ≥ 0 max F(x 1, x 2, x 3, …, x n ) = c 1x 1 + c 2x 2 + c 3x 3 +… +c n x n, x1, x2, x3, …, xn (1) (2) Σ aij x i ≤ (=) b i x i ≥ 0 где i = 1,2,3,…m, j = 1,2,3,…,n (3) Общий вид задачи ЛП – отыскание max линейной функции с ограничениями в виде неравенств ≤, при условии неотрицательности переменных задачи. Замечание В случае необходимости отыскания min целевой функции F(x 1, x 2, x 3, …, x n ), достаточно домножить целевую функцию на (-1). Например, min(5x 1 + 8x 2 - 10x 5 – 3x 7) = max (-5x 1 - 8x 2 + 10x 5 + 3x 7) Запись задачи ЛП max F(x 1, x 2, x 3, …, x n ) = c 1x 1 + c 2x 2 + c 3x 3 +… +c n x n, x1, x2, x3, …, xn (1) (2) Σ aij x i = b i xi ≥ 0 где i = 1,2,3,…m, j = 1,2,3,…,n (3) Канонический вид задачи ЛП – отыскание max линейной функции с ограничениями в виде равенств, при условии неотрицательности управляющих переменных задачи правых частей ограничений bi. Сведение задачи ЛП к каноническому виду Запись задачи ЛП и Запись задачи ЛП в каноническом виде предполагает: 1)Отыскание max целевой функции; 2)Запись ограничений задачи в виде линейных равенств; 3)Неотрицательность правых частей ограничений задачи; 4)Неотрицательность всех переменных задачи Пример Запись задачи ЛП В оптимизационной задаче цель может состоять в отыскании минимального значения целевой функции. Тогда для сведения min целевой функции к max в задачах линейного программирования достаточно домножить ее на (-1) min (x 1 – 2x 2 + x 3 – 5x 4) = max (-x 1 + 2x 2 - x 3 + 5x 4 ) Пример Запись задачи ЛП Ограничения общего вида в задачах ЛП могут быть записаны в виде неравенств: «≥», «>», «≤», «<» Для сведения ограничений в виде равенств вводят дополнительные неотрицательны е переменны е x n+1, x n+2, …, при помощи которых «уравнивают» значения левой и правой части ограничений. При этом в целевую функцию дополнительные переменные вводят с нулевыми коэффициентами. Пример Запись задачи ЛП Для удовлетворения условия неотрицательности правых частей ограничений, достаточно умножить соответствующее ограничение на (-1). 2x 1 – x 2 + x 3 + 5x 4 – x 5 ≤ -5 -2x 1 + x 2 - x 3 - 5x 4 + x 5 ≥ 5 Пример Запись задачи ЛП Для удовлетворения условия неотрицательности переменных задачи x i : либо заменяют ее на противоположную, либо заменяют ее разностью двух неотрицательных переменных Если x i < 0, то x i ‘ = - x i , где x i ’ ’’ ’ ’’ ’ Если x лю бая, то x = x -x , где x , x i i i i i i ≥ 0 ≥0 Пример Запись задачи ЛП Сведение задачи ЛП к каноническому виду min (x 1 – 2x 2 + x 3 – 5x 4) 2x 1 – x 2 + x 3 + 5x 4 – x 5 ≤ -5 2x 1 +3x 2 - x4 ≤ 4 x 1 , x 2 , x 4, x 5 ≥ 0 1. Сведем цель задачи к отысканию max целевой функции: min (x 1 – 2x 2 + x 3 – 5x 4) = max (-x 1 + 2x 2 - x 3 + 5x 4) 2. добьемся неотрицательности правых частей ограничений задачи: -2x 1 + x 2 - x 3 - 5x 4 + x 5 ≥ 5 Сведение задачи ЛП к каноническому виду max (-x 1 + 2x 2 - x 3 + 5x 4) 2x 1 – x 2 + x 3 + 5x 4 – x 5 ≤ -5 2x 1 +3x 2 - x4 ≤ 4 x 1 , x 2 , x 4, x 5 ≥ 0 3. сведем все неравенства к равенствам Для этого введем две новые дополнительные неотрицательные переменные: x 6, x 7 ≥ 0 тогда -2x 1 + x 2 - x 3 - 5x 4 + x 5 - x 6 2x 1 + 3x 2 - x4 = 5 + x7 = 4 Сведение задачи ЛП к каноническому виду max (-x 1 + 2x 2 - x 3 + 5x 4) 2x 1 – x 2 + x 3 + 5x 4 – x 5 ≤ -5 2x 1 +3x 2 - x4 ≤ 4 x 1 , x 2 , x 4, x 5 ≥ 0 4. Добьемся неотрицательности всех переменных задачи. Для этого заменим переменную x 3, которая по условию может принимать любые значения, неотрицательных переменных: разностью x 3 = x 3’’ - x 3’ , где x 3’, x 3’’ ≥ 0 двух Сведение задачи ЛП к каноническому виду max (-x 1 + 2x 2 - x 3 + 5x 4) 2x 1 – x 2 + x 3 + 5x 4 – x 5 ≤ -5 2x 1 +3x 2 - x4 ≤ 4 x 1 , x 2 , x 4, x 5 ≥ 0 5. С учетом введенных переменных сделаем замену в целевой функции и ограничениях задачи: max (-x 1 + 2x 2 - (x 3’’ - x 3’ ) + 5x 4) -2x 1 + x 2 - (x 3’’ - x 3’ ) - 5x 4 + x 5 - x 6 = 5 2x 1 +3x 2 - x4 + x7 = 4 x 1 , x 2 , x 3’ , x 3’’ , x 4, x 5, x 6, x 7 ≥ 0 Сведение задачи ЛП к каноническому виду 6. Переименуем переменные: x 1 = y 1 x2 = y2 и запишем окончательный ’ x 3 = y3 вид задачи ЛП x 3’’ = y 4 x4 = y5 x5 = y6 x6 = y7 x7 = y8 max (-y 1 + 2y 2 - y 3 + y 4 + 5y 5) -2y 1 + y 2 - y 4 + y 3 - 5y 5 + y 6 – y 7 2y 1 +3y 2 - y5 y 1 , y 2 , y 3, y 4, y 5, y 6, y 7, y 8 ≥ 0 = 5 + y8 = 4 Общий вид задачи ЛП