02.11.2019 14:18
andron2303 26 7100 Источник

Пролог


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

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

§1. Постановка задачи линейного программирования


Определение: Линейное программирование – математическая дисциплина, посвященная теории и методам решения экстремальных задач на множествах n- мерного пространства, задаваемых системами линейными уравнений и неравенств.

Общая задача линейного программирования (далее – ЛП) имеет вид:

image

§2. Каноническая форма задачи ЛП


Каноническая форма задачи ЛП:

image

Замечание: Любая задача ЛП сводится к канонической.

Алгоритм перехода от произвольной задачи ЛП к канонической форме:

  1. Неравенства с отрицательными $inline$b_i$inline$ умножаем на (-1).
  2. Если неравенство вида (?), то к левой части добавляем $inline$s_i$inline$ – добавочную переменную, и получаем равенство.
  3. Если неравенство вида (?), то из левой части вычитаем $inline$s_i$inline$, и получаем равенство.
  4. Делаем замену переменных:

  • Если $inline$x_i ? 0$inline$, то $inline$x_i'= -x_i ? 0$inline$
  • Если $inline$x_i$inline$ — любой, то $inline$x_i= x_i' - x_i''$inline$, где $inline$x_i', x_i''? 0$inline$

Замечание: Будем нумеровать $inline$s_i$inline$ по номеру неравенства, в которое мы его добавили.

Замечание: $inline$s_i$inline$ ?0.

§3. Угловые точки. Базисные/свободные переменные. Базисные решения


Определение: Точка $inline$Х ? D$inline$ называется угловой точкой, если представление$inline$ Х= ?Х^1+ (1-?) Х^2,где Х^1,Х^2 ?D;0< ?<1 $inline$ возможно только при $inline$Х^1=Х^2 $inline$.

Иными словами, невозможно найти две точки в области, интервал проходящий через которые содержит $inline$Х$inline$ (т.е. $inline$Х$inline$ – не внутренняя точка).

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

Определение: Пусть есть система m уравнений и n неизвестных (m < n). Разделим переменные на два множества: (n-m) переменные положим равными нулю, а остальные m переменных определяются решением системы исходных уравнений. Если это решение единственно, то тогда ненулевые m переменных называют базисными; нулевые (n-m) переменных – свободными (небазисными), а соответствующие результирующие значения переменных называют базисным решением.

§4. Симплекс-метод


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

Необходимые условия для применения симплекс-метода:

  1. Задача должна иметь каноническую форму.
  2. У задачи должен быть явно выделенный базис.

Определение: Явно выделенным базисом будем называть вектора вида:$inline$(..0100..)^T, (..010..)^T,(..0010..)^T...$inline$, т.е. только одна координата вектора ненулевая и равна 1.

Замечание: Базисный вектор имеет размерность (m*1), где m – количество уравнений в системе ограничений.

Для удобства вычислений и наглядности обычно пользуются симплекс-таблицами:

image

  • В первой строке указывают «наименование» всех переменных.
  • В первом столбце указывают номера базисных переменных, а в последней ячейке – букву Z (это строка функционала).
  • В «середине таблицы» указывают коэффициенты матрицы ограничений — aij.
  • Последний столбец – вектор правых частей соответствующих уравнений системы ограничений.
  • Крайняя правая ячейка – значение целевой функции. На первой итерации ее полагают равной 0.

Замечание: Базис – переменные, коэффициенты в матрице ограничений при которых образуют базисные вектора.

Замечание: Если ограничения в исходной задаче представлены неравенствами вида ?, то при приведении задачи к канонической форме, введенные дополнительные переменные образуют начальное базисное решение.

Замечание: Коэффициенты в строке функционала берутся со знаком “-”.

Алгоритм симплекс-метода:

1. Выбираем переменную, которую будем вводить в базис. Это делается в соответствии с указанным ранее принципом: мы должны выбрать переменную, возрастание которой приведет к росту функционала. Выбор происходит по следующему правилу:

  • Если задача на минимум – выбираем максимальный положительный элемент в последней строке.
  • Если задача на максимум – выбираем минимальный отрицательный.

Такой выбор, действительно, соответствует упомянутому выше принципу: если задача на минимум, то чем большее число вычитаем – тем быстрее убывает функционал; для максимума наоборот – чем большее число добавляем, тем быстрее функционал растет.

Замечание: Хотя мы и берем минимальное отрицательное число в задаче на максимум, этот коэффициент показывает направление роста функционала, т.к. строка функционала в симплекс-таблице взята со знаком “-”. Аналогичная ситуация с минимизацией.

Определение: Столбец симплекс-таблицы, отвечающий выбранному коэффициенту, называется ведущим столбцом.

2. Выбираем переменную, которую будем вводить в базис. Для этого нужно определить, какая из базисных переменных быстрее всего обратится в нуль при росте новой базисной переменной. Алгебраически это делается так:

  • Вектор правых частей почленно делится на ведущий столбец
  • Среди полученных значений выбирают минимальное положительное (отрицательные и нулевые ответы не рассматривают)

Определение: Такая строка называется ведущей строкой и отвечает переменной, которую нужно вывести из базиса.

Замечание: Фактически, мы выражаем старые базисные переменные из каждого уравнения системы ограничений через остальные переменные и смотрим, в каком уравнении возрастание новой базисной переменной быстрее всего даст 0. Попадание в такую ситуацию означает, что мы «наткнулись» на новую вершину. Именно поэтому нулевые и отрицательные элементы не рассматриваются, т.к. получение такого результата означает, что выбор такой новой базисной переменной будет уводить нас из области, вне которой решений не существует.

3. Ищем элемент, стоящий на пересечении ведущих строки и столбца.

Определение: Такой элемент называется ведущим элементом.

4. Вместо исключаемой переменной в первом столбце (с названиями базисных переменных) записываем название переменной, которую мы вводим в базис.

5. Далее начинается процесс вычисления нового базисного решения. Он происходит с помощью метода Жордана-Гаусса.

  • Новая Ведущая строка = Старая ведущая строка / Ведущий элемент
  • Новая строка = Новая строка – Коэффициент строки в ведущем столбце * Новая Ведущая строка

Замечание: Преобразование такого вида направлено на введение выбранной переменной в базис, т.е. представление ведущего столбца в виде базисного вектора.

6. После этого проверяем условие оптимальности. Если полученное решение неоптимально – повторяем весь процесс снова.

§5. Интерпретация результата работы симплекс-метода


1. Оптимальность

Условие оптимальности полученного решения:

  • Если задача на максимум – в строке функционала нет отрицательных коэффициентов (т.е. при любом изменении переменных значение итогового функционала расти не будет).
  • Если задача на минимум – в строке функционала нет положительных коэффициентов (т.е. при любом изменении переменных значение итогового функционала уменьшаться не будет).

2. Неограниченность функционала

Однако, стоит отметить, что заданный функционал может не и достигать максимума/минимума в заданной области. Алгебраический признак этого можно сформулировать следующим образом:

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

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

3. Альтернативные решения

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

Алгебраический признак существования альтернативы:

После достижения оптимального решения имеются нулевые коэффициенты при свободных переменных в строке функционала.

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

Эпилог


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

Чуть позже напишу статью о практической реализации симплекс-метода, а также несколько статей о Методе искусственных переменных (М-Метод), Методе Гомори и Методе ветвей и границ.

Спасибо за внимание!

P.S.

Если уже сейчас Вы мучаетесь с реализацией симплекс-метода, советую почитать книгу А. Таха Введение в исследование операций — там все неплохо разобрано и в теории, и на примерах; а также посмотрите примеры решения задач matburo.ru — это поможет с реализацией в коде.

Комментарии (26)


  1. ferocactus
    02.11.2019 20:07
    #20839570

    А что за необходимость заставляет писать собственную реализацию симплекс-метода?


    1. andron2303 Автор
      03.11.2019 21:01
      #20839686

      Что касается необходимости в реализации, есть два основных мотива, как мне кажется. Первый — элементарно разобраться, как все это устроено. Пытливых умов всегда достаточно, к счастью. И лучший способ это сделать — прочувствовать каждый шаг алгоритма, а лучше ручной реализации ничего для этого не придумаешь. И второй мотив — в учебных целях. Такая задача решается в рамках курса Исследование операций, его читают на многих специальностях. И неискушенному исследователю может быть достаточно сложно это сделать — реально доступной для понимания литературы и статей мало. Поэтому несколько статей по этому поводу — моя попытка облегчить кому-то жизнь :)


      1. x67
        03.11.2019 00:39
        #20840256

        Забавно, но в попытке сделать изучение темы доступнее вы сделали такую же сухую, непонятную многим, статью, как и другие)
        https://imgs.xkcd.com/comics/standards.png


        1. andron2303 Автор
          03.11.2019 09:49
          #20840700

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


          1. malkovsky
            03.11.2019 13:16
            #20841088

            Статья хорошая, проделана довольно большая работа, однако вынужден согласиться с x67 — не совсем понятно, чем ваша статья лучше описаний в методичках (к слову я рекомендую первоисточник — книгу Д. Данцига по линейному программированию), чем она их дополняет?

            Почему вы ничего не написали про то, как найти начальный базисный план? Вы сами писали симплекс-метод, так что не могли не натолкнуться на эту проблему. К примеру в python/scipy реализован двухфазный симплекс-метод, который в первой фазе как раз ищет начальный базис. Вообще для демонстраций он очень удобен, так как выдает всю последовательность точек, в которых побывал, можно заодно с ним и сравнение сделать.

            Еще, кажется, у вас половина формул написаны нормальным TeX-шрифтом (видимо через встроенный в хабраредактор?), половина скриншотами формул не очень хорошего качества, если нужно, могу помочь это поправить.

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

            Надеюсь, вы учтете это, когда соберетесь писать еще статьи. Удачи!


            1. andron2303 Автор
              03.11.2019 22:41
              #20842122

              Спасибо! Все учту :)


  1. Ametrin
    03.11.2019 21:22
    #20839776

    У нас в вузе была классная методичка, пятая часть которой посвящена как раз симлекс-методу. На мой взгляд, написано немного доступнее, чем у Вас. «Салмин И.Д. Математические методы решения оптимизационных задач».


    1. andron2303 Автор
      03.11.2019 21:51
      #20839868

      До этого не встречал такую методичку. Сейчас посмотрел, действительно, объяснено достаточно понятно. Только вот при поиске информации про линейное программирование в интернете, скорее всего на эту методчку не наткнешься. Я не наткнулся, по крайней мере. Хабр в этом плане ранжирутеся получше :) Некоторые вещи я мог написать не очень понятно: это, фактически, один из первых таких опытов. Но некоторые полезные моменты из статьи вынести все-таки можно, а именно на такие мелочи в академических книжках внимание и не обращают. Но за методику спасибо, добавлю ее потом в советы по литературе.


      1. ukt
        03.11.2019 01:37
        #20840356

        Предлагаю наткнуться на «Таха Х.А. 2005. Вильямс. Введение в исследование операций», мне когда то изрядно помогла.


        1. andron2303 Автор
          03.11.2019 09:51
          #20840704

          Как раз в P.S. у меня есть ссылка на эту книгу. Она неплохая, но там есть пару минусов, на мой взгляд. Хотя, возможно, это зависит от редакции — в разные годы наполнение там было разным.


    1. ctacka
      03.11.2019 14:59
      #20841332

      Как только прочитал "симплекс-метод", сразу вспомнил Игоря Дмитриевича. :)


      1. andron2303 Автор
        03.11.2019 22:41
        #20842124

        У каждого, наверно, есть похожие воспоминания и ощущения… :)


  1. embden
    03.11.2019 02:23
    #20840416

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


    1. andron2303 Автор
      03.11.2019 09:54
      #20840708

      Учту пожелания в следующих статьях :) Раз такой запрос возник — значит людям это интересно.


  1. ganqqwerty
    03.11.2019 03:17
    #20840440

    Ох как зубодробительно. Ну хоть примеров-то добавьте, ну там хотя бы из финансов. Хочу я накупить всяких разных акций, портфель, значит, создать, ага. Каждая акция в разное время разную цену имеет. Могу накупить побольше акций Микрософта, или побольше акций Сбербанка. Вот и получается, что стоимость моего портфеля — это функция от времени, цены акций в разное время, и их соотношения в портфеле. Интересно у такой функции найти глобальный максимум. Вообще, все эти задачи оптимизации — это про поиск глобального максимума. А что такое глобальный максимум?
    Ну представьте себе параболу перевёрнутую, у неё бугор такой посередине — вот это глобальный максимум. Или там гору — у неё на самом высоком пике этот максимум, а у оврага — на самой большой глубине. А у инвестиционного портфеля максимум там, где бабок больше всего, а чуть соотношение акций поменяешь или время пройдёт — сразу бабок меньше станет.

    Как искать бугорок у параболы? С помощью отрезка, который мы двигаем по ней, меняя его длину. Как искать дно оврага? Треугольничками, у которых мы меняем длины сторон и аккуратно их по оврагу двигаем. А если овраг четырёхмерный? Тетраэдриками! Ну и так далее. И видео можно вставить, да хоть вот это: youtu.be/HUqLxHfxWqU
    Возникает вопрос — а по какому же алгоритму нам эти треугольнички располагать в пространстве? И вот тут вы выпрыгиваете из кустов со своими таблицами, а тем, кто не верит — демонстрируете доказательство.


    1. andron2303 Автор
      03.11.2019 10:00
      #20840720

      С такой подачей получится практически целый глубинный курс по оптимизации :) Хотя, если бы всегда его начитывали так подробно, было бы намного эффективней, имхо. Люди понимали бы природу того или иного метода. Как раз то, о чем я писал — следующий шажок: не просто алгоритм используем, а каждое действие осознаем. Но не глубоко, т.к. концепция оптимизационных задач нам не до конца понятна. То, о чем Вы говорите — супер. Это реально принесло бы пользу людям. Займусь этим :)


      1. ganqqwerty
        04.11.2019 12:46
        #20843162

        Мне кажется, это не про «подробно», это про смысл происходящего. Все-таки, мы ж прикладники, в основном, интересно, что за задачка решалась изначально. Я через 10 лет после выпуска из универа про симплекс-метод это и помню — что это для поиска бугорка у параболы произвольной размерности путем прикладывания к ней произвольной размерности треугольничков.


        1. malkovsky
          04.11.2019 13:37
          #20843320

          Кажется вы путаете симплекс-метод для задачи ЛП (о котором идет речь в статье) с методом Нелдера-Мида
          Что примечательно — на википедии по этому поводу специальный эпиграф, видимо часто путают

          This article is about the linear programming algorithm. For the non-linear optimization heuristic, see Nelder–Mead method.

          Not to be confused with Dantzig's simplex algorithm for the problem of linear optimization.


          1. ganqqwerty
            04.11.2019 18:31
            #20844442

            Гм, в самом деле.


  1. ICELedyanoj
    03.11.2019 11:58
    #20840918

    В ВУЗе был у нас один преподаватель с кафедры информатики — он написал алгоритм симплекс-метода и все старшекурсники ходили к нему за решением.
    Я был на втором курсе, и меня зацепила одна идея. На парах для симплекс-метода мы использовали простые дроби. Алгоритм итеративный, поэтому даже если задача изначально подгоняется под целочисленный конечный результат, то алгоритм нашего преподавателя всё равно давал 1.9999999, так и печаталось на расчётках.
    Дело было в конце девяностых, компа у меня своего не было. На ВУЗовских компах был только GW-Basic и офис. Но офис был с VBA, поэтому я решил убить двух зайцев сразу и написал VBA-макрос, который умеет симплекс-метод, причём делает это при помощи простых дробей, т.е. никаких 1.999999.
    Написал, показал его преподам, получил какую-то там премию на олимпиаде ВУЗовской.
    Даже потроллил препода насчёт дробей.
    Макрос в книге Excel закрыл паролем, пароль не помню :(


    1. Palich239
      05.11.2019 07:04
      #20846300

      Сейчас тот же Excel из коробки умеет симлекс-метод (а может что-то и пошустрее), вдруг пригодится


      1. ICELedyanoj
        05.11.2019 16:41
        #20849518

        Ого, спасибо, не знал. В 2007-м добавили.
        Наверное у меня подсмотрели.


        1. andron2303 Автор
          05.11.2019 17:12
          #20849698

          :D


  1. AmartelRU
    03.11.2019 14:08
    #20841198
    +1

    1. В задаче ЛП на вектор b не налагается никаких ограничений. Это верно и для канонической формы. Вот в методах искусственного базиса (М-метод, двухэтапный симплекс-метод) действительно требуется неотрицательность b (по понятным причинам — вектор b оказывается начальным базисным планом в этих методах, а план должен быть неотрицателен).
    2. Если «статья направлена на понимание теоретической части вопроса», то стоит ссылаться не на графический метод решения, а на теорему о том, что экстремум выпуклой функции на выпуклом многограннике достигается в его вершине.
    3. Альтернативные решения — это не только другие крайние точки, но и вся грань, ими образованная, т.е. решений может быть бесконечно много (но значение целевой функции на каждом из них, разумеется, одинаковое).

    Достижение «более глубокого понимания теоретической части» без единого упоминания двойственности остаётся под вопросом. Вот Вы пишете: «Коэффициенты в строке функционала берутся со знаком “-”.». Или про критерий оптимальности: «в строке функционала нет положительных коэффициентов». Но никак не объясняете, почему же это так. Хотя критерий оптимальности — это, фактически, ограничения двойственной задачи. В случае канонической задачи они имеют вид uA ? c или же uA — c ? 0. При u = 0 как раз и возникнет знак минус у «коэффициентов в строке функционала».

    Помимо своей фундаментальной значимости, двойственность используется и на практике (при исследовании устойчивости, например). Если к решённой задачи ЛП добавить новое ограничение, то с помощью двойственного симплекс-метода можно задачу «дорешать» с финальной симплекс-таблицы, а не решать полностью с нуля.

    В общем, спасибо за статью, но в качестве пожелания к последующим — хотя бы ссылайтесь на важные вещи, чтобы читатели были в курсе их существования.

    P.S. Целая статья про М-метод? Я заинтригован :)


    1. andron2303 Автор
      03.11.2019 22:55
      #20842136

      Спасибо за замечания, все учту. Что касается М-Метода, там больше упор хотелось сделать на реализацию :) По теории там особо писать нечего, если только дублировать Симплекс-Метод.


  1. oji
    03.11.2019 15:30
    #20841378

    Когда-то, лет 10-12 назад, делал частичную (ограничения только вида <=) реализацию симплекс-метода на VBA, с выводом промежуточных решений. Недавно выложил в общий доступ, кому интересно, можете скачать тут.