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