Экономические задачи решаемые математическим программированием

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

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

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

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

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

Все формы математического моделирования любого экономического объекта предполагают последовательную реализацию следующих этапов:

1. описание экономической задачи;
2. построение математической модели (т.е. математическая формализация экономической ситуации);
3. практическое использование математической модели, получение решения и его анализ на допустимость, устойчивость и другие критерии;
4. экономическая интерпретация полученного решения.

Характеристика линейного программирования

Линейное программирование является одним из разделов этой математической теории, которая зачастую используется в науке для решения экономических задач. Впервые теоретические основы линейного программирования были сформулированы и опубликованы в 1939 году советским математиком и экономистом Л.В. Канторовичем. В том числе и за эту работу он в 1975 году был удостоен Нобелевской премии по экономике.

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

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

Рисунок 1. Линейная функция. Автор24 — интернет-биржа студенческих работ

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

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

Существует несколько «классических» экономических задач, решение которых находится с помощью применения методов линейного программирования. Перечислим эти примеры:

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

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

Методы решения задач линейного программирования

Для решения общей задачи линейного программирования в большинстве случаев специалисты обращаются к такому известному методу, как симплекс-метод. Он был разработан американским математиком Джорджем Бернард Данцигом и впервые представлен публике в 1949 году.

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

Ещё один метод решения задач линейного программирования – это метод эллипсоидов, который относится к категории полиномиальных алгоритмов. Его разработчиком (относительно задач линейного программирования) считается советский математик Л. Хачиян, который предложил данный метод в 1979 году.

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

Источник

1. Определение задачи математического программирования

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

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

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

Классическая задача математического программирования – задача выбора таких значений некоторых переменных, подчиненных системе ограничений в форме равенств, при которых достигается max или min функции.

2. Допустимое решение задачи, одр, оптимальное решение задачи.

Допустимым решением задачи называется любой n-мерный вектор

x (x = (,,…,)), удовлетворяющий системе ограничений и условию неотрицательности.

Множество допустимых решений образует ОДР.

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

3. Экономико–математические модели задач лп: задача о банке

К экономико-математическим моделям задач ЛП относятся:Задача планирования производства, определения оптимального ассортимента продукции, о диете, о банке, составления жидких смесей, Транспортная задача

Построение экономико – математической модели.

Задача о банке

Собственные средства банка в сумме с депозитами составляют 100 млн. $. Не менее 35 млн. $ из этой суммы размещена в кредитах (не ликвид). Ликвидное ограничение ценных бумаг должны составлять не менее 30 %, размещенных в кредитах и ликвидных активах.

Пусть — средства, размещенные в кредитах,– средства, размещенные в ликвидных активах.

Банк. Огран. (1)

Кред. Огран.

Ликвид. Огран.

Условие неопределенности ,≥0 (4)

— доходность кредитов, — доходность ликвидных активов

F = при услов. (1) – (4).

4. Экономико – математические модели задач лп: задача определения оптимального ассортимента продукции.

— П1, — П2

F = 3

2

3

5. Задача лп, стандартная форма, каноническая форма.

К математическим задачам линейного программирования относят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов.

Задачей линейного программирования является выбор из множества допустимых планов наиболее выгодного (оптимального).

Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.

В общем виде модель записывается следующим образом:

Целевая функция: F (x)= c1x1 + c2x2 + . + cnxn → max(min)

ограничения: a11x1 + a12x2 + . + a1nxn b1,

требование неотрицательности: xj ≥ 0,

Задача имеет каноническую форму, если является задачей на максимум (минимум) линейной функции F и ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х1, х2, . хn являются неотрицательными:

F (x) =

, i= 1,2…m

, j = 1,2…n

В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной функции f и система ограничений ее состоит из одних линейных неравенств типа «

F (x) =

, i= 1,2…m

, j = 1,2…n

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

Если допустимое множество не пусто, а целевая функция ограничена сверху (для задачи максимизации, а для задачи минимизации — ограничена снизу) на этом множестве, то задача ЛП имеет оптимальное решение.

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

Источник