В наше время большое количество задач планирования и управления во многих отраслях народного хозяйства, а также достаточно большой объём частных прикладных задач можно решить методами математического программирования. Одними из наиболее развитых в области решения оптимизационных задач являются методы линейного программирования. Данные методы позволяют нам описать с достаточной точностью задачи деятельности коммерции, такие, как планирование товарооборота; размещение розничной торговой городской сети; планирование товароснабжения города, района; организация рациональных перевозок товаров; распределение работников торговли должностям [1].
Линейное программирование является математической дисциплиной, которая посвящена теории, а так же методам решения экстремальных задач на множествах n-мерного векторного пространства, которые задаются системами линейных уравнений и неравенств.
Линейное программирование возникло в 40-х годах прошлого века как один из разделов теории оптимизации, точнее, в 1939 г. было положено начало линейному программированию советским математиком-экономистом Л.В. Канторовичем в его работе «Математические методы организации и планирования производства». После появления этой работы был открыт новый этап в применении математики в экономике.
Исторически задача линейного программирования впервые была задана в 1947 г. Дж. Б. Данцигом, Маршаллом Вудом и некоторыми их сотрудниками в департаменте военно-воздушных сил США. В те времена эта группа исследовала возможности использования математических, а так же смежных с ними методов для решения военных задач и проблем планирования. Далее для развития данных идей в ВВС организуется исследовательская группа, которая называется Project SCOOP. Первое решение задачи линейного программирования, увенчавшееся успехом, на ЭВМ SEAC проводилось в январе 1952 г.
Достаточно быстро линейное программирование стало известным методом для решения задач планирования и экономики, в которых переменные могут принимать вещественные значения. В некоторых случаях удавалось приспособить линейное программирование так же и для дискретных задач, но систематическое изучение данного программирования к комбинаторике началось лишь несколько десятилетий спустя. Одним из первых эту область начал осваивать, несомненно, Джек Эдмондс, работающий над полиэдральной комбинаторикой, знания о которой достаточно расширили наши познания о связи линейных задач и комбинаторных.
Основная проблема линейного программирования это решение задачи максимизации или минимизации линейной функции или функции нескольких переменных, ограниченной системой неравенств. Возможен вариант, где потребуется решение задачи с помощью поиска экстремума для системы линейных функций на множестве, которые могут задаваться как равенствами, так и линейными неравенствами. Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях.
Линейные неравенства на переменные ограничивает полупространство в линейном пространстве. В результате все неравенства ограничивают многогранник, который, может быть бесконечным. Такой многогранник называется полиэдральным комплексом. Уравнение W(x) = c, где W(x) – минимизируемый или максимизируемый линейный функционал, создает гиперплоскость L(c). Данная зависимость создает семейство параллельных гиперплоскостей. Тогда формулировка экстремальной задачи будет записываться так: требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Следует отметить, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, при этом, их будет больше одной, если пересечение содержит k-мерную грань или ребро. Таким образом, максимум функционала можно искать в вершинах многогранника [2-3].
Существует несколько методов для решения задач линейного программирования:
1. Простой перебор;
2. Направленный перебор;
3. Симплекс-метод.
Рассмотрим более подробно симплексный метод, который представляет собой алгоритм решения оптимизационной задачи в многомерном пространстве путём перебора вершин выпуклого многогранника.
Принцип симплексного метода состоит в том, необходимо выбрать одну из вершин многогранника и после этого начинать движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Последовательность вычислений данного метода можно разделить на две основные фазы:
1. последовательный переход от одной вершины к другой, ведущий к оптимизации значения целевой;
2. функции нахождение исходной вершины множества допустимых решений.
Анализ эффективности и наблюдения метода в практических задачах и приложениях привело к развитию других способов измерения эффективности.
Симплекс-метод имеет среднюю полиномиальную сходимость при широком выборе распределения значений в случайных матрицах.
Вычислительная эффективность оценивается при помощи двух параметров:
1) Числа итераций, необходимого для получения решения;
2) Затрат машинного времени.
Рассмотрим пример, в котором нужно определить объём производства продукции (х1 и х2) двух видов продукции (Р1 и Р2), максимализирующих величину прибыли предприятия:
(1)
при заданных ресурсных ограничениях (
):
и при х1 ≥ 0 и х2 ≥ 0 .Решение этой задачи симплексным методом [(F(х) = 124] имеет место при объёмах производства х1 = 8, х2 = 14 и недоиспользовании второго вида ресурса в размере 18 ед.
Решение задачи состоит в определении цен за единицу каждого из используемых видов ресурсов y1, y2 и y3. При этом выручка производителя от продажи ресурсов могла быть равна ожидаемой прибыли от реализации готовых изделий.
Математическая модель двойственной задачи линейного программирования в данном примере имеет вид:
, (3)
при ограничениях
, (4)
если y1 ≥ 0, y2 ≥ 0, y3 ≥ 0. При решении данной двойственной задачи симплекс-методом значения о. о. оценок ресурсов составят: y1 = 0,636; y2 = 0 и y3 = 0,545.
Линейное программирование применяется в ведущих мировых корпорациях, фирмах и предприятиях, позволяя решать проблему распределения ограниченных ресурсов между конкурирующими видами деятельности с тем, чтобы максимизировать или минимизировать некоторые численные величины, такие как маржинальная прибыль или расходы. Методы линейного программирования так же может использоваться в таких областях как планирование производства, с целью максимального увеличения прибыли, оптимизация перевозок товаров в целях сокращения расстояний, распределение персонала с целью максимально увеличить эффективность работы, а также в задачах по оптимизации научных исследований [4-5].