Какие процессы исследует линейное программирование

Линейное программирование: общие принципы

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

Введение

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

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

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

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

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

Приведём конкретный пример. Компания «Яркие краски» осуществляет производство красок для внутренних и наружных работ, применяя для этого сырьё двух типов: М1 и М2. Ниже приведена таблица, где представлены основные исходные данные задачи.

Рисунок 1. Исходные данные задачи. Автор24 — интернет-биржа студенческих работ

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

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

1. Совокупность переменных, которые необходимо определить.
2. Целевая функция, подлежащая оптимизации.
3. Перечень ограничений, которым обязаны удовлетворять все переменные.

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

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

1. X1 является переменной, которая определяет ежедневный выпуск краски для наружных работ, задаваемый в тоннах.
2. X2 является переменной, которая определяет ежедневный выпуск краски для внутренних работ, измеряемый тоже в тоннах.

Затем, на основе введённых переменных, необходимо найти целевую функцию. Очевидно, что в нашем варианте целевой функцией может считаться общий ежедневный доход, который обязан возрастать при увеличении объёма выпускаемых красок. Зададим следующие обозначения:

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

В соответствии с условиями рассматриваемого примера, целевая функция может быть представлена следующей формулой:

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

• М1 = 6Х1 + 4Х2 (т) используемый сырьевой объём.
• М2 = 1Х1 + 2Х2 (т) используемый сырьевой объём.

Так как дневной расход сырья М1 и М2 ограничен указанными выше объёмами, то можно определить следующие ограничения:

Существуют ещё два ограничения, задаваемые объёмом спроса на готовую продукцию:

1. Максимальный дневной объём выпуска краски для внутренних работ не должен превышать две тонны.
2. Дневной объём выпуска краски для внутренних работ не должен превышать дневной объём выпуска краски для наружных работ более чем на тонну.

Первое ограничение может быть записано так:

Второе ограничение может быть представлено как разность между дневными объёмами выпуска красок для внутренних и наружных работ, которая должна быть менее тонны, то есть:

Любое решение, удовлетворяющее модельным ограничениям, станет допустимым. Так решением может быть Х1 = 3 и Х2 = 1, и оно является допустимым. Такая задача может иметь бесконечное множество решений, то есть максимальное значение данной целевой функции нельзя найти простым перебором допустимых решений.

Источник

Лекция 3. Линейное программирование

3.1. Линейное программирование как инструмент математического моделирования экономики

Линейное программирование сформировалось как отдельный раздел прикладной математики в 40 – 50-х гг. ХХ в. благодаря работам советского ученого, лауреата Нобелевской премии Л.В. Канторовича. В 1939 году им была опубликована работа «Математические методы организации и планирования производства», в которой он с использованием математики решил экономические задачи о наилучшей загрузке машин, раскрое материалов с наименьшими расходами, распределении грузов по нескольким видам транспорта и другие, предложив метод разрешающих множителей 8 .

Л.В. Канторович впервые сформулировал такие широко используемые экономико-математические понятия, как оптимальный план, оптимальное распределение ресурсов, объективно обусловленные оценки, указав многочисленные области экономики, где они могут быть применены.

Понятие линейного программирования было введено американским математиком Д. Данцигом, который в 1949 г. предложил алгоритм решения задачи линейного программирования, получивший название «симплексный метод».

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

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

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

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

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

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

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

К задачам линейного программирования сводится широкий круг вопросов планирования экономических процессов, где ставится задача поиска наилучшего (оптимального) решения.

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

(3.1)

от n переменных x₁, x₂, …, х_n при наложенных функциональных ограничениях:

(3.2)

и прямых ограничениях (требовании неотрицательности переменных)

, (3.3)

где a_ij, b_i, c_j – заданные постоянные величины.

В системе ограничений (3.2) знаки «меньше или равно», «равно», «больше или равно» могут встречаться одновременно.

ЗЛП в более краткой записи имеет вид:

,

;

.

Вектор Х = (x₁, x₂, …, х_n) компоненты которого удовлетворяют функциональным и прямым ограничениям задачи называют планом (или допустимым решением) ЗЛП.

Все допустимые решения образуют область определения задачи линейного программирования, или область допустимых решений (ОДР). Допустимое решение, которое доставляет максимум или минимум целевой функции f(X), называется оптимальным планом задачи и обозначается f(X * ), где Х * =(x₁ * , x₂ * , …, х_n * ).

Еще одна форма записи ЗЛП:

,

где f(X * ) есть максимальное (минимальное) значение f(С, х), взятое по всем решениям, входящим в множество возможных решений Х.

Определение 2 11 . Математическое выражение целевой функции и ее ограничений называются математической моделью экономической задачи.

Для составления математической модели необходимо:

2) составить целевую функцию исходя из цели задачи;

3) записать систему ограничений, учитывая имеющие в условии задачи показатели и их количественные закономерности.

Источник