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