Линейное программирование в экономике
Линейное программирование – это математическая дисциплина, в которой описаны теоретические основы и методы решения экстремальных задач, т.е. задач по нахождению максимального или минимального значения функции при заданных значениях аргумента.
Основы экономико-математического моделирования и линейного программирования
Одним из основных и важнейших инструментов математического моделирования является линейное программирование. Оно представляет собой разновидность аналитического средства изучения процессов, которые имеют место быть в экономической жизни.
Моделирование (и в том числе линейное программирование как частный случай моделирования) как средство изучения окружающей действительности используется в тех случаях, когда проведение экспериментов с реальными объектами слишком дорого, запрещено или в принципе неосуществимо. В частности, именно моделирование является основным методом исследования экономических объектов, процессов и явлений.
Все формы математического моделирования любого экономического объекта предполагают последовательную реализацию следующих этапов:
- описание экономической задачи;
- построение математической модели (т.е. математическая формализация экономической ситуации);
- практическое использование математической модели, получение решения и его анализ на допустимость, устойчивость и другие критерии;
- экономическая интерпретация полученного решения.
Характеристика линейного программирования
Линейное программирование является одним из разделов этой математической теории, которая зачастую используется в науке для решения экономических задач. Впервые теоретические основы линейного программирования были сформулированы и опубликованы в 1939 году советским математиком и экономистом Л.В. Канторовичем. В том числе и за эту работу он в 1975 году был удостоен Нобелевской премии по экономике.
Методы линейного программирования на данный момент широко используются при решении экономических задач в области распределения ресурсов, планирования производства, проблем снабжения предприятий и др.
Общая задача линейного программирования (еще называется стандартной задачей) заключается в нахождении минимума линейной целевой функции, которая принимает следующий вид:
Рисунок 1. Линейная функция. Автор24 — интернет-биржа студенческих работ
Если в экономической задаче присутствуют ограничения в форме неравенств, то она называется основной задачей линейного программирования. Эта задача может принять канонический вид, если вместо системы неравенств будет использоваться система равенств. Осуществить трансформацию задачи к каноническому виду можно благодаря введению дополнительных переменных.
Кроме того, допускаются и другие приемы работы с представлением задачи линейного программирования. Так, если в задаче, нацеленной на определение максимальной величины, поменять знаки у коэффициентов (плюс на минус, или наоборот), то задача уже будет нацелена на определение минимальной величины.
Существует несколько «классических» экономических задач, решение которых находится с помощью применения методов линейного программирования. Перечислим эти примеры:
- задача производственного планирования – заключается в составлении хозяйствующим субъектом такого плана производства продукции нескольких видов (при ограниченном объеме имеющихся у него материальных, трудовых и финансовых ресурсов), реализация которого принесет ему максимальный доход;
- задача потребителя – заключается в совершении покупателем (потребителем) выбора между продуктами, которые представлены в магазине, т.е. могут быть им приобретены при ограниченном объеме имеющихся у него денежных средств (бюджетное ограничение); причем этот выбор должен принести ему наибольшее удовлетворение;
- транспортная задача – заключается в составлении такого плана перевозок продукции со станций хранения до пунктов доставки (с учетом ограничений по объемам загрузки транспортных средств и потребностям пунктов доставки), реализация которого позволит минимизировать объем издержек, вызванных этими перевозками.
Для решения этих и ряда других задач необходимо создать математическую модель в виде целевой функции (или системы целевых функций), пример которой приведен выше, с учетом ограничений (одно из базовых ограничений: х должно быть больше 0, и др.). Этому и посвящено линейное программирование.
Методы решения задач линейного программирования
Для решения общей задачи линейного программирования в большинстве случаев специалисты обращаются к такому известному методу, как симплекс-метод. Он был разработан американским математиком Джорджем Бернард Данцигом и впервые представлен публике в 1949 году.
Этот метод справедливо считается одним из самых эффективных алгоритмов решения задач линейного программирования – при решении прикладных задач он неоднократно демонстрировал хорошие результаты. Залог успеха симплекс-метода состоит в его комбинаторном характере, т.е. он предполагает, что при поиске оптимального решения необходимо последовательно перебрать все вершины многогранника допустимых решений.
Ещё один метод решения задач линейного программирования – это метод эллипсоидов, который относится к категории полиномиальных алгоритмов. Его разработчиком (относительно задач линейного программирования) считается советский математик Л. Хачиян, который предложил данный метод в 1979 году.
Метод эллипсоидов кардинальным образом отличается от симплекс-метода, так как имеет некомбинаторную природу. В вычислительном плане этот метод оказался неперспективным, однако именно он стал предвестником создания и использования методов внутренней точки. Методы внутренней точки трактуют задачу линейного программирования непрерывно, поэтому поиск осуществляется вдоль траекторий в пространстве переменных задачи.
Линейное программирование: общие принципы
Линейное программирование — это математическая дисциплина, посвящённая теории и методам разрешения экстремальных задач на множествах многомерного векторного пространства, которые определяются системами линейных уравнений и неравенств.
Введение
Успешное разрешение фактически любой экономической проблемы зависит от выбора самого лучшего метода использования имеющихся ресурсных возможностей. В процессе экономической деятельности необходимо выполнять распределение таких важнейших ресурсов, как финансы, товары, сырьевые запасы, технические средства, рабочая сила и другое. От оптимального распределения этих, как правило, не бесконечных ресурсных возможностей в конечном итоге зависят результаты деятельности. Смысл методов оптимизации заключается в том, чтобы на базе наличия определённых запасов ресурсов, определить самый лучший способ их использования или распределения, который обеспечивает самые лучшие параметры по требуемым показателям. При этом следует учитывать существующие ограничения, накладываемые на использование ресурсных возможностей существующей экономической ситуацией. Способами оптимизации в экономике, в научной и социальной сфере способны стать многие главные направления математического программирования, в частности, линейное, нелинейное и динамическое программирование.
Линейное программирование
Под линейным программированием понимаются методы математического моделирования, которые выработаны для оптимизации использования ограниченных ресурсных возможностей. Линейное программирование является наиболее простым и самым проработанным разделом математического программирования. Линейное программирование успешно применяется в оборонной промышленности, индустриальных областях и других сферах.
Повсеместное использование данных методов подкрепляется обширным набором программных алгоритмов, реализующих эти методы. Алгоритмы линейного программирования, при учёте их значительной эффективности, выступают в качестве основы оптимизационных алгоритмов для других, более сложных типов моделей и задач исследования операций, включая целочисленное, нелинейное и стохастическое программирование. Расчёты в методе линейного программирования, как и практически во всех задачах исследования операций, как правило, могут быть очень трудоёмкими и этот факт предопределяет применение вычислительной техники.
Линейное программирование служит для определения оптимального плана распределения ограниченных однородных ресурсов для решения поставленной задачи.
Приведём конкретный пример. Компания «Яркие краски» осуществляет производство красок для внутренних и наружных работ, применяя для этого сырьё двух типов: М1 и М2. Ниже приведена таблица, где представлены основные исходные данные задачи.
Рисунок 1. Исходные данные задачи. Автор24 — интернет-биржа студенческих работ
Маркетинговое подразделение компании установило ограничение на ежедневный выпуск краски для внутренних работ двумя тоннами по причине ограниченного спроса на неё, а также выдвинуло условие, что дневной выпуск краски для внутренних работ не может превышать больше чем на одну тонну выпуск краски для наружных работ. Компания хочет определить наилучшее соотношение между типами выпускаемой продукции, обеспечивающее самый большой общий каждодневный доход.
Задача линейного программирования, подобно всем другим задачам исследования операций, может состоять из следующих компонентов:
- Совокупность переменных, которые необходимо определить.
- Целевая функция, подлежащая оптимизации.
- Перечень ограничений, которым обязаны удовлетворять все переменные.
Определение переменных считается первым этапом в создании модели. Если выполнено определение всех переменных, то задание ограничений и выработка целевой функции, обычно, может считаться несложной проблемой.
Для указанного примера нужно определить ежедневные объёмы выпуска краски для внутренних и наружных работ. Выберем следующие обозначения:
- X1 является переменной, которая определяет ежедневный выпуск краски для наружных работ, задаваемый в тоннах.
- X2 является переменной, которая определяет ежедневный выпуск краски для внутренних работ, измеряемый тоже в тоннах.
Затем, на основе введённых переменных, необходимо найти целевую функцию. Очевидно, что в нашем варианте целевой функцией может считаться общий ежедневный доход, который обязан возрастать при увеличении объёма выпускаемых красок. Зададим следующие обозначения:
Z является целевой функцией, которая определяет общий ежедневный доход и должна измеряться в тысячах долларов.
В соответствии с условиями рассматриваемого примера, целевая функция может быть представлена следующей формулой:
Далее согласно поставленной задаче и целям компании, необходимо определить условия, которые обеспечивают максимум целевой функции. Для этого необходимо определить последний элемент модели, то есть, ограничения, которые учитывают имеющиеся возможности ежедневного использования сырья и уровень спроса на уже готовую продукцию. В соответствии с таблицей, в которой представлены исходные данные, имеем:
- М1 = 6Х1 + 4Х2 (т) используемый сырьевой объём.
- М2 = 1Х1 + 2Х2 (т) используемый сырьевой объём.
Так как дневной расход сырья М1 и М2 ограничен указанными выше объёмами, то можно определить следующие ограничения:
Существуют ещё два ограничения, задаваемые объёмом спроса на готовую продукцию:
- Максимальный дневной объём выпуска краски для внутренних работ не должен превышать две тонны.
- Дневной объём выпуска краски для внутренних работ не должен превышать дневной объём выпуска краски для наружных работ более чем на тонну.
Первое ограничение может быть записано так:
Второе ограничение может быть представлено как разность между дневными объёмами выпуска красок для внутренних и наружных работ, которая должна быть менее тонны, то есть:
Любое решение, удовлетворяющее модельным ограничениям, станет допустимым. Так решением может быть Х1 = 3 и Х2 = 1, и оно является допустимым. Такая задача может иметь бесконечное множество решений, то есть максимальное значение данной целевой функции нельзя найти простым перебором допустимых решений.