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

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

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

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

К числу задач линейного программирования можно отнести задачи:

• 1.    рационального использования сырья и материалов;

• 2.    задачи оптимального раскроя;

• 3.    оптимизации производственной программы предприятий;

• 4.    оптимального размещения и концентрации производства;

• 5.    составления оптимального плана перевозок, работы транспорта (транспортные задачи);

• 6.    управления производственными запасами;

Алгоритмы решения задач линейного программирования

Основными алгоритмами, представленными на данный момент, являются:

• 1.    Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях. Каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c)пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

• -    нахождение исходной вершины множества допустимых решений,

• -    последовательный переход от одной вершины к другой, ведущий к оптимизации значения целевой функции.

• 2.    Метод эллипсоидов — алгоритм нахождения точки, лежащей в пересечении выпуклых множеств. Полиномиальный алгоритм теоретически мог бы стать новым стандартом, однако, на практике алгоритм Хачияна применять почти невозможно: существуют задачи размером в 50 переменных, для которых требуются более 24 тысяч итераций метода Хачияна, количество же существенно более простых итераций симплекс -метода в таких случаях исчисляется сотнями или даже десятками [2].

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

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