VII Международная студенческая научная конференция Студенческий научный форум - 2015

В наше время большое количество задач планирования и управления во многих отраслях народного хозяйства, а также достаточно большой объём частных прикладных задач можно решить методами математического программирования. Одними из наиболее развитых в области решения оптимизационных задач являются методы линейного программирования. Данные методы позволяют нам описать с достаточной точностью задачи деятельности коммерции, такие, как планирование товарооборота; размещение розничной торговой городской сети; планирование товароснабжения города, района; организация рациональных перевозок товаров; распределение работников торговли должностям [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)

при заданных ресурсных ограничениях ():

и при х₁ ≥ 0 и х₂≥ 0 .Решение этой задачи симплексным методом [(F(х) = 124] имеет место при объёмах производства х₁ = 8, х₂= 14 и недоиспользовании второго вида ресурса в размере 18 ед.

Решение задачи состоит в определении цен за единицу каждого из используемых видов ресурсов y₁, y₂ и y₃. При этом выручка производителя от продажи ресурсов могла быть равна ожидаемой прибыли от реализации готовых изделий.

Математическая модель двойственной задачи линейного программирования в данном примере имеет вид:

, (3)

при ограничениях , (4)

если y₁≥ 0, y₂≥ 0, y₃≥ 0. При решении данной двойственной задачи симплекс-методом значения о. о. оценок ресурсов составят: y₁= 0,636; y₂= 0 и y₃= 0,545.

Линейное программирование применяется в ведущих мировых корпорациях, фирмах и предприятиях, позволяя решать проблему распределения ограниченных ресурсов между конкурирующими видами деятельности с тем, чтобы максимизировать или минимизировать некоторые численные величины, такие как маржинальная прибыль или расходы. Методы линейного программирования так же может использоваться в таких областях как планирование производства, с целью максимального увеличения прибыли, оптимизация перевозок товаров в целях сокращения расстояний, распределение персонала с целью максимально увеличить эффективность работы, а также в задачах по оптимизации научных исследований [4-5].

Список использованной литературы

1. Тарасов В.Л. Экономико-математические методы и модели. Учебное пособие. - Н.Новгород: ННГУ, 2003. - 64с.

2. Канторович Л.В. Экономический расчёт наилучшего использования ресурсов Наука, 2011. 760 с.

3. Грешилов А.А. Прикладные задачи математического программирования: М.: Логос, 2006. 288 с.

4. Yanovskii A.A., Simonovskii A.Ya., Klimenko E.M. On the Influence of the Magnetic Field upon Hydrogasdynamic Processes in a Boiling Magnetic Fluid // Surface Engineering and Applied Electrochemistry. – 2014. – Vol. 50, No. 3, pp. 260–266.

5. Яновский А.А., Симоновский А.Я., Клименко Е.М. К вопросу о влиянии магнитного поля на гидрогазодинамические процессы в кипящей магнитной жидкости // Электронная обработка материалов. – 2014. – № 3, С. 66-72.

6. Яновский А.А., Спасибов А.С. Математическое моделирование процессов в кипящих намагничивающихся средах // Современные наукоемкие технологии. 2014. № 5-2. С. 183-186.

7. Яновский А.А., Симоновский А.Я., Савченко П.И. Моделирование гидрогазодинамических процессов в кипящей магнитной жидкости // В сборнике: информационные системы и технологии как фактор развития экономики региона. Ставрополь, 2013. С. 159-163.

Код для цитирования: Скопировать