Математические методы в решении экономических задач Математические методы в решении экономических задач 2. На данный момент эта тема очень актуальна, так как успешная реализация достижений научно - технического прогресса в нашей стране тесным образом связана с использованием математических методов и средств вычислительной техники при решении задач из различных областей человеческой деятельности. Исключительно важное значение приобретает использование указанных методов и средств при решении экономических задач. В связи с этим для студентов экономических специальностей вузов необходимо как знание возможностей применения математических методов, так и понимание тех проблем, которые возникают при их использовании. Цель курсовой работы - изучить методы решения задач линейного программирования и научиться применять на практике решение задачи графическим, симплекс-методом аналитическим и табличным для прямой и двойственной задачи линейного программирования, а также научиться решать транспортную задачу. Результаты работы рекомендуется использовать для успешного решения задач линейного программирования и дальнейшего изучения математического и линейного программирования. Исследование различных процессов, в том числе и экономических, обычно начинается с их моделирования, то есть отражения реального процесса через математические соотношения. При этом составляются уравнения или неравенства, которые связывают различные показатели переменные исследуемого процесса, образуя систему ограничений. В этих соотношениях выделяются такие переменные, меняя которые можно получить оптимальное значение основного показателя данной системы прибыль, доход, затраты и т. Математическое программирование включает в себя такие разделы математики, как линейное, нелинейное и динамическое программирование. Сюда же обычно относят стохастическое программирование, теорию игр, теорию массового обслуживания, теорию управления запасами и некоторые другие. Математическое программирование -- это раздел высшей математики, посвященный решению задач, связанных с нахождением экстремумов функций нескольких переменных при наличии ограничений на переменные. Методами математического программирования решаются задачи о распределении ресурсов, планировании выпуска продукции, ценообразовании, транспортные задачи и т. Переменными задачи называются величины x1 , x2 , Система ограничений включает в себя систему уравнений и неравенств, которым удовлетворяют переменные задачи и которые следуют из ограниченности ресурсов или других экономических или физических условий, например положительности переменных и т. Целевой функцией называют функцию переменных задачи, которая характеризует качество выполнения задачи и экстремум которой требуется найти. Если целевая функция и система ограничений линейны, то задача математического программирования называется задачей линейного программирования. Множество допустимых решений планов задачи образует область допустимых решений ОДР. Оптимальным решением планом ЗЛП называется такое допустимое решение план задачи, при котором целевая функция достигает экстремума. Правые части всех ограничений должны быть неотрицательными. Все ограничения должны быть представлены в виде равенств, поэтому при переходе от неравенства к равенству используют аппарат дополнительных переменных. Если исходные ограничения определяют расход некоторого ресурса знак "" , то переменные. Если исходные ограничения определяют избыток некоторого ресурса знак "" , то вводится избыточная переменная. Если переменная не имеет ограничения в знаке, то её нужно представить как разность двух неотрицательных переменных:. Такую подстановку следует использовать во всех ограничениях, содержащих эту переменную, а также в выражении для целевой функции. Целевая функция задачи линейного программирования есть уравнение плоскости или гиперплоскости для числа переменных больше трех. Максимальное или минимальное значение целевая функция задачи линейного программирования достигает либо в вершине выпуклого многогранника, либо на одной из его граней. Таким образом, решение решения задачи линейного программирования лежит в вершинах выпуклого многогранника и для его нахождения надо вычислить значения целевой функции в вершинах выпуклого многогранника, определяемого условиями-ограничениями задачи. Требуется составить план производства изделий А? Предприятие предполагает выпускать два вида продукции А? Производство обеспечено сырьем каждого вида в количествах: На изготовление единицы изделия А? Прибыль от реализации единицы изделия А? Трудность построения математической модели заключается в идентификации переменных и последующем представлении цели и ограничений в виде математических функций этих переменных. Если модель содержит только две переменные, то задачу линейного программирования можно решить графически. В случае трёх переменных графическое решение становится менее наглядным, а при большем значении переменных - даже невозможным. Однако графическое решение позволяет сделать выводы, которые служат основой для разработки общего метода решения задачи линейного программирования. Первый шаг при использовании графического метода заключается в геометрическом представлении допустимых решений, то есть построении области допустимых решений ОДР. При получении графического решения переменная X1 откладывается по горизонтальной оси, а X2 - по вертикальной. При формировании ОДР необходимо предотвратить получение недопустимых решений, которые связаны с необходимостью выполнения условия неотрицательности переменных. Перед построением необходимо определить квадранты, в которых будет располагаться ОДР. Квадранты определяются знаками переменных X1 и X2. Условия неотрицательности переменных X1 и X2 ограничивают область их допустимых значений первым квадрантом. Если переменная X1 не ограниченна в знаке, то область ограничивается первым и вторым квадрантом, если X2, то - первым и четвёртым квадрантом. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных. В результате построений получается многоугольник, который определяет пространство решений. В каждой точке, принадлежащей области или границам многоугольника решений, все ограничения выполняются, поэтому все решения, соответствующие этим точкам, являются допустимыми. Пространство решений содержит бесконечное число таких точек, несмотря на это, можно найти оптимальное решение. Для этого необходимо построить в плоскости переменных X1, X2 градиент целевой функции. Определение оптимальной точки зависит от той задачи, которую необходимо решить. Если в целевой функции определена задача максимизации, то оптимальная точка будет располагаться в направлении увеличения градиента, если задача минимизации - то в направлении уменьшения градиента целевой функции. Для определения оптимальной точки будем перемещать целевую функцию в направлении увеличения уменьшения градиента до тех пор, пока она не сместиться в область недопустимых решений. Правильность выбора оптимальной точки можно проверить расчётом целевой функции в вершинах многогранника решений. В ЗЛП область допустимых решений всегда является выпуклым множеством, то есть таким множеством, что наряду с любыми двумя точками, принадлежащими этому множеству, этому же множеству принадлежит и отрезок, соединяющий эти две точки. Любая функция наискорейшим образом увеличивается в направлении своего градиента. Предположим, что будет изготовлено Х? Поскольку производство продукции ограничено имеющимися в распоряжении предприятия сырьем каждого вида и количество изготовляемых изделий не может быть отрицательным, должны выполняться неравенства:. Общая прибыль от реализации Х? Таким образом, мы приходим к следующей математической задаче: Найдем решение сформулированной задачи, используя ее геометрическую интерпретацию. Сначала определим многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств и найдем соответствующие прямые:. Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой -- нет. Чтобы определить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты данному неравенству. Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой принадлежит эта точка, в противном случае -- другая полуплоскость. Это и показано стрелками. Пересечение полученных полуплоскостей и определяет многоугольник решений данной задачи. Координаты любой точки, принадлежащей этому пятиугольнику, удовлетворяют данной системе неравенств и условию неотрицательности переменных. Поэтому сформулированная задача будет решена, если мы сможем найти точку, принадлежащую пятиугольнику OABCD, в которой функция F принимает максимальное значение. Если теперь взять какую-нибудь точку, принадлежащую построенной прямой и многоугольнику решений, то ее координаты определяют такой план производства изделий А1 и А2, при котором прибыль от их реализации равна руб. Далее, полагая h равным некоторому числу, большему чем , мы будем получать различные параллельные прямые. Если они имеют общие точки с многоугольником решений, то эти точки определяют планы производства изделий А1 и А2, при которых прибыль от их реализации превзойдет руб. Координаты этой точки и определяют план выпуска изделий А1 и А2, при котором прибыль от их реализации является максимальной. Найдем координаты точки В как точки пересечения прямых и. Следовательно, ее координаты удовлетворяют уравнениям этих прямых. Симплексный метод -- это метод целенаправленного перебора опорных решений задачи линейного программирования. Он позволяет за конечное число шагов расчета либо найти оптимальное решение, либо установить, что оптимального решения не существует. Идея симплексного метода состоит в следующем. Используя систему ограничений, приведенную к общему виду, т. Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то переходят к другому допустимому базисному решению. Симплексный метод гарантирует, что при этом новом решении линейная форма если и не достигнет оптимума, то приблизится к нему в случае перехода к вырожденному базисному решению значение линейной формы не изменится. С новым допустимым базисным решением поступают так же, пока не находят решение, которое является оптимальным. Если первое найденное базисное решение окажется недопустимым, то с помощью симплексного метода осуществляют переход к другим базисным решениям, которые позволяют приблизиться к области допустимых решений, пока на каком-то шаге не получится допустимое выше. Дадим математическую формулировку задачи. Пусть Х1 и Х2 -- количество изделий А1 и А2, запланированных к производству. Так как количество сырья по каждому виду ограничено, то должны выполняться следующие неравенства:. Эта система неравенств и является системой ограничений данной задачи. Целевая функция линейная форма , выражающая прибыль предприятия, имеет вид. Для сведения системы ограничений-неравенств к системе уравнений прибавим к левой части каждого неравенства добавочные неотрицательные переменные Х3, Х4, Х5. В условиях данной задачи они имеют конкретное экономическое содержание, а именно выражают объем остатков сырья каждого вида после выполнения плана по выпуску продукции. После введения добавочных переменных получим систему уравнений:. Так как система ограничений есть система трех независимых уравнений с двумя переменными, то число базисных переменных должно равняться трём, а число свободных - двум. Для решения задачи симплексным методом прежде всего нужно найти любое базисное решение. В данном случае это легко сделать. Для этого достаточно взять в качестве базисных добавочные переменные Х3, Х4, Х5. Так как коэффициенты при этих переменных образуют единичную матрицу, то отпадает необходимость вычислять определитель. Считая свободными переменные Х1 и Х2 равными нулю, получим базисное решение 0; 0; ; ; , которое к тому же оказалось допустимым. Переходим к поискам оптимального решения. Х3, Х4, Х5; свободные переменные: Для того чтобы судить, оставить ли свободные переменные в числе свободных или их выгоднее с точки зрения приближения к оптимальному решению перевести в базисные, следует выразить через них и линейную форму в данном случае она уже выражена через переменные Х1 и Х2. При этом базисном решении значение линейной формы. Теперь от этого первоначального решения нужно перейти к другому, при котором значение линейной формы увеличится. Из рассмотрения линейной формы видно, что ее значение возрастает при увеличении значений переменных Х1 и Х2. Иными словами, эти переменные невыгодно считать свободными, т. Это и означает переход к новому базисному решению. При симплексном методе на каждом шаге решения предполагается перевод в число базисных только одной из свободных переменных. Как только одна из свободных переменных переходит в число базисных, одна из базисных должна быть переведена на ее место в число свободных. Какую же из четырех базисных переменных нужно вывести? Ответить на этот вопрос помогут следующие рассуждения: Однако оказывается, что увеличение Х2 может продолжаться только до известных границ, а именно до тех пор, пока не нарушится требование неотрицательности переменных. Х3, Х4, Х2; свободные переменные: Выразим базисные переменные и линейную форму через свободные. В данном случае это третье уравнение, которое выделено рамкой. Выразив из этого уравнения Х2, получим:. Подставив это выражение Х2 во все остальные уравнения системы 1. Это уже лучше, чем на I шаге, но не искомый максимум. Дальнейшее увеличение функции F возможно за счет введения переменной Х1 в число базисных; так как эта переменная входит в выражение F с положительным коэффициентом, поэтому ее увеличение приводит к увеличению линейной формы и ее невыгодно считать свободной, т. Х1, Х2, Х3; свободные переменные: Выразим основные переменные и линейную форму через свободные. Из последнего уравнения системы 1. Так как в выражение линейной формы переменные Х4 и Х5 входят с отрицательным коэффициентами, то никакое увеличение F за счет этих переменных невозможно. Следовательно, на III шаге критерий оптимальности достигнут и задача решена. Таким образом, для получения наибольшей прибыли, равной ден. Рассмотренный симплексный метод решения ЗЛП в предыдущем пункте можно свести к записи однотипно заполняемых таблиц. Осуществить это возможно, придерживаясь следующего алгоритма:. Найти начальное опорное решение с базисом из единичных векторов и коэффициенты разложений векторов условий по базису опорного решения. Если опорное решение отсутствует, то задача не имеет решения в силу несовместности системы ограничений. Вычислить оценки разложений векторов условий по базису опорного решения и заполнить симплексную таблицу. Если выполняется признак единственности оптимального решения для любого вектора условий, не входящего в базис, оценка отлична от нуля , то решение задачи заканчивается. Если выполняется условие существования множества оптимальных решений оценка хотя бы одного вектора условий, не входящего в базис, равна нулю , то путем простого перебора находят все оптимальные решения. Если выполняются условия отсутствия оптимального решения вследствие неограниченности целевой функции не имеет решения, если для какого-либо из векторов условий с оценкой, противоречащей признаку оптимальности, среди коэффициентов разложения по базису опорного решения нет положительного , то задача не имеет решения ввиду неограниченности целевой функции. Если пункты алгоритма не выполняются, находят новое опорное решение с использованием условий нахождения оптимального решения. Составим математическую модель задачи. Искомый выпуск продукции А1 обозначим через Х1, продукции А2 - Х2. Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные Х1, Х2 должны удовлетворять следующей системе неравенств:. По своему экономическому содержанию переменные Х1 и Х2 могут принимать только лишь неотрицательные значения: Таким образом, приходим к следующей математической задаче: Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений:. Эти дополнительные переменные по экономическому смыслу означают не используемое при данном плане производства количество сырья того или иного вида. Например, Х3 -- это неиспользуемое количество сырья 1-ого вида и т. Для решения задачи табличным симплексным методом прежде всего нужно найти любое базисное решение. Как видно из таблицы 2. Этот план, конечно, не является оптимальным. Это видно и из 4-й строки таблицы 2. Отрицательные числа не только свидетельствуют о возможности увеличения общей стоимости производимой продукции, но и показывают, на сколько увеличится эта сумма при введении в план единицы того или другого вида продукции. Даже с экономической точки зрения наиболее целесообразным является включение в план производства изделий А2. Определяем вектор, подлежащий исключению из базиса и выбираем разрешающую строку. Следовательно, в базис введем Х2 вместо Х5. Тем самым мы, с экономической точки зрения определили, какое количество изделий А2 предприятие может изготовлять с учетом норм расхода и имеющихся объемов сырья каждого вида. На пересечении разрешающего столбца и строки находится разрешающий элемент - это число 7. Результат записываем в первую строку. Результат записываем во вторую строку. При пересчете у нас в столбике F, таблицы 2. Далее, разрешающим столбцом у нас будет Х1,т. Следовательно, в базис введем Х1 вместо Х4. Под двойственной задачей понимается вспомогательная задача линейного программирования, формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными. Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных. Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной или прямой. Целевая функция исходной задачи задаётся на максимум, а целевая функция двойственной - на минимум. Чтобы составить матрицу для двойственной задачи нужно применить транспонирование то есть замена строк - столбцами, а столбцов - стоками. Число переменных в двойственной задаче равно числу соотношений в системе 1. Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений, т. Целевая функция исходной задачи исследуется на максимум, а система условий содержит только уравнения. Поэтому в двойственной задаче целевая функция исследуется на минимум, а её переменные могут принимать любые значения в том числе и отрицательные. Следовательно, для исходной задачи двойственная задача такова: Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение. Груз требуется перевезти в пять пунктов: Спланировать перевозки так, чтобы общая их стоимость была минимальной. Матрица тарифов сij перевозок между пунктами отправления и пунктами назначения, а также запасы и потребности представлены ниже:. Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения. Проверяем выполнение необходимого и достаточного условия разрешимости задачи. Находим суммарные запасы поставщиков и запросы потребителей: Составляем начальное опорное решение:. Для проверки оптимальности опорного решения необходимо найти потенциалы и оценки. По признаку оптимальности в каждой занятой опорным решением клетке таблицы транспортной задачи сумма потенциалов равна стоимости. Далее одному из потенциалов задаем значение произвольно: Остальные потенциалы находятся однозначно:. Проверяем опорное решение Х1 на оптимальность. С этой целью вычисляем оценки для всех незаполненных клеток таблицы. Начальное опорное решение не является оптимальным, так как имеются положительные оценки. Переходим к новому опорному решению. Находим клетку таблицы, которой соответствует наибольшая положительная оценка:. Циклом в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья - вдоль строк и столбцов, причём в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое - в столбце. При правильном построении опорного плана для любой свободной клетки можно построить лишь один цикл. После того как для выбранной свободной клетки он построен, следует перейти к новому опорному плану. Для этого необходимо переместить грузы в пределах клеток, связанных с данной свободной клеткой. Каждой из клеток, связанных циклом с данной свободной клеткой приписывают определенный знак, причём свободной клетке - знак плюс, а всем остальным клеткам - поочередно знаки минус и плюс таблица 1;1. В данную свободную клетку переносят меньшее из чисел, стоящих в минусовых клетках. Одновременно это число прибавляют к соответствующим клеткам, стоящим в плюсовых клетках, и вычитают из чисел, стоящих в минусовых клетках. Клетка, которая ранее была свободной, становится занятой, а минусовая клетка, в которой стояло минимальное из чисел, считается свободной таблица 1;2. Описанный выше переход от одного опорного плана транспортной задачи к другому называется сдвигом по циклу пересчета. Полученный новый опорный план проверяем на оптимальность. Проверяем опорное решение Х2 на оптимальность. В результате проделанной работы изучено несколько методов решения задачи линейного программирования, а именно графический, симплекс-метод аналитический и табличный для прямой и двойственной задачи линейного программирования, а также изучена транспортная задача. Для достижения поставленной цели были использованы различные источники литературы. На практике рассмотрено решение задачи заданными методами и решена транспортная задача. Математическое программирование в примерах и задачах. Курс высшей математики для экономических вузов. Теория вероятностей и математическое программирование. Курс линейного программирования для экономистов: Общий курс высшей математики для экономистов: Математические методы в решении экономических задач Математические методы в решении экономических задач 2 Введение Актуальность темы. Задачи математического и линейного программирования Исследование различных процессов, в том числе и экономических, обычно начинается с их моделирования, то есть отражения реального процесса через математические соотношения. Построение математической модели экономической задачи включает следующие этапы: Общий вид задачи линейного программирования: Если исходные ограничения определяют расход некоторого ресурса знак "" , то переменные следует интерпретировать как остаток, или неиспользованную часть ресурса. Если исходные ограничения определяют избыток некоторого ресурса знак "" , то вводится избыточная переменная знаком "-". Все переменные должны быть неотрицательными, то есть. Если переменная не имеет ограничения в знаке, то её нужно представить как разность двух неотрицательных переменных: Если такая переменная попадает в оптимальное решение, то. Приступаем к решению задачи. Решить задачу геометрически; Решить задачу симплекс-методом аналитическим и табличным Сформулировать двойственную задачу и найти её решение. Вспомогательная таблица Вид сырья Продукция Ограничения по сырью А? Решение задачи геометрическим методом Трудность построения математической модели заключается в идентификации переменных и последующем представлении цели и ограничений в виде математических функций этих переменных. Далее приступаем к решению задачи: Занесём необходимые нам данные во вспомогательную таблицу: Вид сырья Продукция Ограничения по сырью А? Поскольку производство продукции ограничено имеющимися в распоряжении предприятия сырьем каждого вида и количество изготовляемых изделий не может быть отрицательным, должны выполняться неравенства: Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств и найдем соответствующие прямые: Найдем, например, полуплоскость, определяемую неравенствами. Построим область допустимых решений: Следовательно, ее координаты удовлетворяют уравнениям этих прямых Решим эту систему уравнений: Решение задачи аналитическим симплекс-методом Симплексный метод -- это метод целенаправленного перебора опорных решений задачи линейного программирования. Так как количество сырья по каждому виду ограничено, то должны выполняться следующие неравенства: После введения добавочных переменных получим систему уравнений: Выразив из этого уравнения Х2, получим: Для ответа на вопрос, какую переменную вывести из базисных в свободные, примем: Решить задачу табличным симплексным методом Рассмотренный симплексный метод решения ЗЛП в предыдущем пункте можно свести к записи однотипно заполняемых таблиц. Осуществить это возможно, придерживаясь следующего алгоритма: Привести задачу линейного программирования к каноническому виду. Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные Х1, Х2 должны удовлетворять следующей системе неравенств: Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений: Запишем все расчёты в таблицу Таблица 2. Составим матрицу для исходной задачи: Матрица тарифов сij перевозок между пунктами отправления и пунктами назначения, а также запасы и потребности представлены ниже: Составляем начальное опорное решение: Остальные потенциалы находятся однозначно: Находим клетку таблицы, которой соответствует наибольшая положительная оценка: Для этой клетки строим цикл. Это перемещение производят по следующим правилам: Вычисляем значение целевой функции на втором опорном решении: Далее производим проверку оптимальности опорного решения: Заключение В результате проделанной работы изучено несколько методов решения задачи линейного программирования, а именно графический, симплекс-метод аналитический и табличный для прямой и двойственной задачи линейного программирования, а также изучена транспортная задача. Экономическая теория и исследование операций. Линейная алгебра и программирование. Информационная Библиотека для Вас! Архитектура География Геодезия Геология Геополитика Государство и право Гражданское право и процесс Делопроизводство Детали машин Дистанционное образование Другое Жилищное право Журналистика Компьютерные сети Конституционное право зарубежныйх стран Конституционное право России Краткое содержание произведений Криминалистика и криминология Культурология Литература языковедение Маркетинг реклама и торговля Математика Медицина Международные отношения и мировая экономика Менеджмент и трудовые отношения Музыка Налоги Начертательная геометрия Оккультизм и уфология Педагогика Полиграфия Политология Право Предпринимательство Программирование и комп-ры Психология - рефераты Религия - рефераты Социология - рефераты Физика - рефераты Философия - рефераты Финансы деньги и налоги Химия Экология и охрана природы Экономика и экономическая теория Экономико-математическое моделирование Этика и эстетика Эргономика Юриспруденция Языковедение Литература Литература зарубежная Литература русская Юридпсихология Историческая личность Иностранные языки Эргономика Языковедение Реклама Цифровые устройства История Компьютерные науки Управленческие науки Психология педагогика Промышленность производство Краеведение и этнография Религия и мифология Сексология Информатика программирование Биология Физкультура и спорт Английский язык Математика Безопасность жизнедеятельности Банковское дело Биржевое дело Бухгалтерский учет и аудит Валютные отношения Ветеринария Делопроизводство Кредитование. Вспомогательная таблица Вид сырья.
Почта миасс график работы
Как приготовить наггетсы видео
Современник афиша смоленск расписание