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

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

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

Графический метод. В линейном программировании используется графический метод, с помощью которого определяют выпуклые множества (многогранник решений). Если основная задача линейного программирования имеет оптимальный план, то целевая функция принимает значение в одной из вершин многогранника решений (см. рисунок).

Решение задачи линейного программирования графическим методом включает следующие этапы:

На плоскости X10X2 строят прямые. Определяются полуплоскости.

Определяют многоугольник решений;

Строят вектор N (c1,c2), который указывает направление целевой функции;

Передвигают прямую целевую функцию c1x2 + c2x2 = 0 в направлении вектора N до крайней точки многоугольника решений.

Вычисляют координаты точки и значение целевой функции в этой точке.

Рис. 1 Иллюстрация к графическому методу

Простой перебор. Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа 2Х1 + 5Х2? 10, то, очевидно, 0? Х1? 10/2 = 5 и 0? Х2? 10/2 = 5. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его «обращенную» к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.

Проведем перебор точек параллелепипеда с шагом 1/10n последовательно при n=2,3,…, вычисляя значения целевой функции и проверяя наличие ограничений. Из всех точек, удовлетворяющих ограничениям, возьмем ту, в которой целевая функция максимальна. Решение найдено! (Более строго выражаясь, найдено с точностью до 1/10n .).

Направленный перебор. Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно — т.н. метод случайного поиска) менять ее координаты на определенную величину ?, каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка — в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до?; если необходимо, в окрестности найденного решения проводим направленный перебор с шагом ?/2, ?/4 и т. д.).

Симплекс-метод. Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации. Он был предложен американцем Г. Данцигом в 1951 г. Симплекс-метод состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум.

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

Первый полиномиальный алгоритм, метод эллипсоидов, был предложен в 1979 году советским математиком Л. Хачияном, разрешив таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, некомбинаторную природу, нежели симплекс-метод. Однако в вычислительном плане этот метод оказался неперспективным.

Тем не менее, сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП —методов внутренней точки, первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году. Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования, разработанные в 1960;х годах Фиако (Fiacco) и МакКормиком (McCormick).

Продемонстрируем применение симплекс-метода на следующем примере.

Пример. Рассмотрим задачу линейного программирования: F = 15 Х1 + 12 Х2 + 14 Х3 > max .

Х1 / 200 + Х2 / 300 + Х3 / 120? 100 ,.

Х1 / 300 + Х2 / 100 + Х3 / 100? 100, Х3 / 80? 100 .

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

В соответствии с симплекс-методом введем т.н. «свободные переменные» Х4, Х5, Х6, соответствующие недоиспользованным мощностям, т. е. перейдем к системе уравнений:

Х1 / 200 + Х2 / 300 + Х3 / 120 + Х4 = 100, Х1 / 300 + Х2 / 100 + Х3 / 100 + Х5 = 100, Х3 / 80 + Х6 = 100 ,.

15 Х1 + 12 Х2 + 14 Х3 = F .

У этой системы имеется очевидное решение, соответствующее вершине многогранника допустимых значений переменных:

Х1 = Х2 = Х3 = 0, Х4 = Х5 = Х6 = 100, F = 0.

В терминах исходной задачи это значит, что ничего не надо выпускать.

Такое решение приемлемо только на период летних отпусков.

Выбираем переменную, которая входит в целевую функцию F с самым большим положительным коэффициентом. Это Х1 .

Сравниваем частные от деления свободных членов в первых трех уравнениях на коэффициенты при только что выбранной переменной Х1: 100 / (1/200) = 20 000, 100 / (1/300) =30 000, 100/0 = +? .

Выбираем строку, которой соответствует минимальное из всех положительных отношений. В рассматриваемом примере — это первая строка, которой соответствует отношение 20 000.

Умножим первую строку на 200, чтобы получить Х1 с единичным коэффициентом:

Х1 + 2/3 Х2 + 2/1,2 Х3 + 200 Х4 = 20 000 .

Затем умножим вновь полученную строку на (-1/300) и сложим со второй строкой, получим.

7/900 Х2 + 4/900 Х3 — 2/3 Х4 + Х5 = 100/3.

Ту же преобразованную первую строку умножим на (-15) и сложим со строкой, в правой части которой стоит F, получим:

2 Х2 — 11 Х3 — 3000 Х4 = F — 300 000.

В результате система уравнений преобразуется к виду, в котором переменная Х1 входит только в первое уравнение:

Х1 + 2/3 Х2 + 2/1,2 Х3 + 200 Х4 = 20 000 ,.

• 7/900 Х2 + 4/900 Х3 — 2/3 Х4 + Х5 = 100/3, Х3 / 80 + Х6 = 100 ,
• 2 Х2 — 11 Х3 — 3000 Х4 = F — 300 000.

Очевидно, у новой системы имеется улучшенное по сравнению с исходным решение, соответствующее вершине в шестимерном пространстве:

Х1 = 20 000, Х2 = Х3 = Х4 = 0, Х5 = 100/3, Х6 = 100, F = 300 000.

В терминах исходной задачи это значит, что надо выпускать только кухни. Такое решение приемлемо, если допустимо выпускать только один вид продукции.

Повторим описанную выше операцию. В строке с F имеется еще один положительный коэффициент — при Х2 (если бы положительных коэффициентов было несколько — мы взяли бы максимальный из них). На основе коэффициентов при Х2 (а не при Х1, как в первый раз) образуем частные от деления соответствующих свободных членов на эти коэффициенты:

20 000 / (2/3) = 30 000, (100/3) / (7/900) = 30 000/7, 100/0 = + ?.

Таким образом, нужно выбрать вторую строку, для которой имеем наименьшее положительное отношение 30 000/7. Вторую строку умножим на 900/7 (чтобы коэффициент при Х2 равнялся 1). Затем добавим обновленную строку ко всем строкам, содержащим Х2, предварительно умножив их на подходящие числа, т. е. такие, чтобы все коэффициенты при Х2 стали бы после сложения равны 0, за исключением коэффициента второй строки, который уже стал равняться 1. Получим систему уравнений:

Х1 + 9/7 Х3 + 1800/7 Х4 — 600/7 Х5 = 120 000/7, Х2 + 4/7 Х3 — 600/7 Х4 + 900/7Х5 = 30 000/7,.

Х3 / 80 + Х6 = 100 ,.

— 85/7 Х3 — 19 800/7 Х4 — 1800/7 Х5 = F — 308 571.

Поскольку все переменные неотрицательны, то из последнего уравнения следует, что прибыль F достигает своего максимального значения, равного 308 571, при Х3 = Х4 = Х5 = 0. Из остальных уравнений следует, что при этом Х1 = 120 000/7 = 17 143, Х2 = 30 000/7 = 4286, Х6 = 100. Поскольку в строке с F не осталось ни одного положительного коэффициента при переменных, то алгоритм симплекс-метода закончил свою работу, оптимальное решение найдено.