Комментарии 27
А что за необходимость заставляет писать собственную реализацию симплекс-метода?
Что касается необходимости в реализации, есть два основных мотива, как мне кажется. Первый — элементарно разобраться, как все это устроено. Пытливых умов всегда достаточно, к счастью. И лучший способ это сделать — прочувствовать каждый шаг алгоритма, а лучше ручной реализации ничего для этого не придумаешь. И второй мотив — в учебных целях. Такая задача решается в рамках курса Исследование операций, его читают на многих специальностях. И неискушенному исследователю может быть достаточно сложно это сделать — реально доступной для понимания литературы и статей мало. Поэтому несколько статей по этому поводу — моя попытка облегчить кому-то жизнь :)
Забавно, но в попытке сделать изучение темы доступнее вы сделали такую же сухую, непонятную многим, статью, как и другие)
https://imgs.xkcd.com/comics/standards.png
Это статья направлена на понимание теоретической части вопроса. Например, почему выбор новой базисной переменной происходит именно так, как он происходит. Будет еще одна (а может и не одна) статья по этому поводу, и там будут примеры и практика. А здесь формат другой — подробный разбор теории, с нюансами.
Статья хорошая, проделана довольно большая работа, однако вынужден согласиться с x67 — не совсем понятно, чем ваша статья лучше описаний в методичках (к слову я рекомендую первоисточник — книгу Д. Данцига по линейному программированию), чем она их дополняет?
Почему вы ничего не написали про то, как найти начальный базисный план? Вы сами писали симплекс-метод, так что не могли не натолкнуться на эту проблему. К примеру в python/scipy реализован двухфазный симплекс-метод, который в первой фазе как раз ищет начальный базис. Вообще для демонстраций он очень удобен, так как выдает всю последовательность точек, в которых побывал, можно заодно с ним и сравнение сделать.
Еще, кажется, у вас половина формул написаны нормальным TeX-шрифтом (видимо через встроенный в хабраредактор?), половина скриншотами формул не очень хорошего качества, если нужно, могу помочь это поправить.
Возможно вам будет интересно посмотреть (а может даже и что-нибудь оттуда взять) на мой черновик, который я использовал для анимаций траекторий разных оптимизационных методов.
Надеюсь, вы учтете это, когда соберетесь писать еще статьи. Удачи!
Почему вы ничего не написали про то, как найти начальный базисный план? Вы сами писали симплекс-метод, так что не могли не натолкнуться на эту проблему. К примеру в python/scipy реализован двухфазный симплекс-метод, который в первой фазе как раз ищет начальный базис. Вообще для демонстраций он очень удобен, так как выдает всю последовательность точек, в которых побывал, можно заодно с ним и сравнение сделать.
Еще, кажется, у вас половина формул написаны нормальным TeX-шрифтом (видимо через встроенный в хабраредактор?), половина скриншотами формул не очень хорошего качества, если нужно, могу помочь это поправить.
Возможно вам будет интересно посмотреть (а может даже и что-нибудь оттуда взять) на мой черновик, который я использовал для анимаций траекторий разных оптимизационных методов.
Надеюсь, вы учтете это, когда соберетесь писать еще статьи. Удачи!
У нас в вузе была классная методичка, пятая часть которой посвящена как раз симлекс-методу. На мой взгляд, написано немного доступнее, чем у Вас. «Салмин И.Д. Математические методы решения оптимизационных задач».
До этого не встречал такую методичку. Сейчас посмотрел, действительно, объяснено достаточно понятно. Только вот при поиске информации про линейное программирование в интернете, скорее всего на эту методчку не наткнешься. Я не наткнулся, по крайней мере. Хабр в этом плане ранжирутеся получше :) Некоторые вещи я мог написать не очень понятно: это, фактически, один из первых таких опытов. Но некоторые полезные моменты из статьи вынести все-таки можно, а именно на такие мелочи в академических книжках внимание и не обращают. Но за методику спасибо, добавлю ее потом в советы по литературе.
Как только прочитал "симплекс-метод", сразу вспомнил Игоря Дмитриевича. :)
НЛО прилетело и опубликовало эту надпись здесь
Ох как зубодробительно. Ну хоть примеров-то добавьте, ну там хотя бы из финансов. Хочу я накупить всяких разных акций, портфель, значит, создать, ага. Каждая акция в разное время разную цену имеет. Могу накупить побольше акций Микрософта, или побольше акций Сбербанка. Вот и получается, что стоимость моего портфеля — это функция от времени, цены акций в разное время, и их соотношения в портфеле. Интересно у такой функции найти глобальный максимум. Вообще, все эти задачи оптимизации — это про поиск глобального максимума. А что такое глобальный максимум?
Ну представьте себе параболу перевёрнутую, у неё бугор такой посередине — вот это глобальный максимум. Или там гору — у неё на самом высоком пике этот максимум, а у оврага — на самой большой глубине. А у инвестиционного портфеля максимум там, где бабок больше всего, а чуть соотношение акций поменяешь или время пройдёт — сразу бабок меньше станет.
Как искать бугорок у параболы? С помощью отрезка, который мы двигаем по ней, меняя его длину. Как искать дно оврага? Треугольничками, у которых мы меняем длины сторон и аккуратно их по оврагу двигаем. А если овраг четырёхмерный? Тетраэдриками! Ну и так далее. И видео можно вставить, да хоть вот это: youtu.be/HUqLxHfxWqU
Возникает вопрос — а по какому же алгоритму нам эти треугольнички располагать в пространстве? И вот тут вы выпрыгиваете из кустов со своими таблицами, а тем, кто не верит — демонстрируете доказательство.
Ну представьте себе параболу перевёрнутую, у неё бугор такой посередине — вот это глобальный максимум. Или там гору — у неё на самом высоком пике этот максимум, а у оврага — на самой большой глубине. А у инвестиционного портфеля максимум там, где бабок больше всего, а чуть соотношение акций поменяешь или время пройдёт — сразу бабок меньше станет.
Как искать бугорок у параболы? С помощью отрезка, который мы двигаем по ней, меняя его длину. Как искать дно оврага? Треугольничками, у которых мы меняем длины сторон и аккуратно их по оврагу двигаем. А если овраг четырёхмерный? Тетраэдриками! Ну и так далее. И видео можно вставить, да хоть вот это: youtu.be/HUqLxHfxWqU
Возникает вопрос — а по какому же алгоритму нам эти треугольнички располагать в пространстве? И вот тут вы выпрыгиваете из кустов со своими таблицами, а тем, кто не верит — демонстрируете доказательство.
С такой подачей получится практически целый глубинный курс по оптимизации :) Хотя, если бы всегда его начитывали так подробно, было бы намного эффективней, имхо. Люди понимали бы природу того или иного метода. Как раз то, о чем я писал — следующий шажок: не просто алгоритм используем, а каждое действие осознаем. Но не глубоко, т.к. концепция оптимизационных задач нам не до конца понятна. То, о чем Вы говорите — супер. Это реально принесло бы пользу людям. Займусь этим :)
Мне кажется, это не про «подробно», это про смысл происходящего. Все-таки, мы ж прикладники, в основном, интересно, что за задачка решалась изначально. Я через 10 лет после выпуска из универа про симплекс-метод это и помню — что это для поиска бугорка у параболы произвольной размерности путем прикладывания к ней произвольной размерности треугольничков.
Кажется вы путаете симплекс-метод для задачи ЛП (о котором идет речь в статье) с методом Нелдера-Мида
Что примечательно — на википедии по этому поводу специальный эпиграф, видимо часто путают
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.
Что примечательно — на википедии по этому поводу специальный эпиграф, видимо часто путают
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.9999999, так и печаталось на расчётках.
Дело было в конце девяностых, компа у меня своего не было. На ВУЗовских компах был только GW-Basic и офис. Но офис был с VBA, поэтому я решил убить двух зайцев сразу и написал VBA-макрос, который умеет симплекс-метод, причём делает это при помощи простых дробей, т.е. никаких 1.999999.
Написал, показал его преподам, получил какую-то там премию на олимпиаде ВУЗовской.
Даже потроллил препода насчёт дробей.
Макрос в книге Excel закрыл паролем, пароль не помню :(
Я был на втором курсе, и меня зацепила одна идея. На парах для симплекс-метода мы использовали простые дроби. Алгоритм итеративный, поэтому даже если задача изначально подгоняется под целочисленный конечный результат, то алгоритм нашего преподавателя всё равно давал 1.9999999, так и печаталось на расчётках.
Дело было в конце девяностых, компа у меня своего не было. На ВУЗовских компах был только GW-Basic и офис. Но офис был с VBA, поэтому я решил убить двух зайцев сразу и написал VBA-макрос, который умеет симплекс-метод, причём делает это при помощи простых дробей, т.е. никаких 1.999999.
Написал, показал его преподам, получил какую-то там премию на олимпиаде ВУЗовской.
Даже потроллил препода насчёт дробей.
Макрос в книге Excel закрыл паролем, пароль не помню :(
Сейчас тот же Excel из коробки умеет симлекс-метод (а может что-то и пошустрее), вдруг пригодится
Если книга не запаролена целиком, а только сам VBA project запаролен, то его можно легко распаролить простым hex-редактором.
Способ распаролить VBA проект
Кстати, похожим образом можно распаролить защиту листов и книги — удалив элементы sheetProtection и workbookProtection в компонентах соответственно листа или книги.
- Сохранённый в новом формате документ (.xlsm, .xlsb, .xlam) распаковываем zip-архиватором (7-zip умеет это делать даже без пердварительной смены расширения на .zip)
- Среди файлов находим vbaProject.bin и открываем его в hex-редакторе
- Меняем DPB на DPx
- Обратно запаковываем zip-архив и возвращаем изначальное имя книги
- При открытии книги нажимаем ОК на предупреждении
- Обязательно задаём новый пароль на проект, после чего можем его полностью разлочить
Кстати, похожим образом можно распаролить защиту листов и книги — удалив элементы sheetProtection и workbookProtection в компонентах соответственно листа или книги.
1. В задаче ЛП на вектор b не налагается никаких ограничений. Это верно и для канонической формы. Вот в методах искусственного базиса (М-метод, двухэтапный симплекс-метод) действительно требуется неотрицательность b (по понятным причинам — вектор b оказывается начальным базисным планом в этих методах, а план должен быть неотрицателен).
2. Если «статья направлена на понимание теоретической части вопроса», то стоит ссылаться не на графический метод решения, а на теорему о том, что экстремум выпуклой функции на выпуклом многограннике достигается в его вершине.
3. Альтернативные решения — это не только другие крайние точки, но и вся грань, ими образованная, т.е. решений может быть бесконечно много (но значение целевой функции на каждом из них, разумеется, одинаковое).
Достижение «более глубокого понимания теоретической части» без единого упоминания двойственности остаётся под вопросом. Вот Вы пишете: «Коэффициенты в строке функционала берутся со знаком “-”.». Или про критерий оптимальности: «в строке функционала нет положительных коэффициентов». Но никак не объясняете, почему же это так. Хотя критерий оптимальности — это, фактически, ограничения двойственной задачи. В случае канонической задачи они имеют вид uA ⩽ c или же uA — c ⩽ 0. При u = 0 как раз и возникнет знак минус у «коэффициентов в строке функционала».
Помимо своей фундаментальной значимости, двойственность используется и на практике (при исследовании устойчивости, например). Если к решённой задачи ЛП добавить новое ограничение, то с помощью двойственного симплекс-метода можно задачу «дорешать» с финальной симплекс-таблицы, а не решать полностью с нуля.
В общем, спасибо за статью, но в качестве пожелания к последующим — хотя бы ссылайтесь на важные вещи, чтобы читатели были в курсе их существования.
P.S. Целая статья про М-метод? Я заинтригован :)
2. Если «статья направлена на понимание теоретической части вопроса», то стоит ссылаться не на графический метод решения, а на теорему о том, что экстремум выпуклой функции на выпуклом многограннике достигается в его вершине.
3. Альтернативные решения — это не только другие крайние точки, но и вся грань, ими образованная, т.е. решений может быть бесконечно много (но значение целевой функции на каждом из них, разумеется, одинаковое).
Достижение «более глубокого понимания теоретической части» без единого упоминания двойственности остаётся под вопросом. Вот Вы пишете: «Коэффициенты в строке функционала берутся со знаком “-”.». Или про критерий оптимальности: «в строке функционала нет положительных коэффициентов». Но никак не объясняете, почему же это так. Хотя критерий оптимальности — это, фактически, ограничения двойственной задачи. В случае канонической задачи они имеют вид uA ⩽ c или же uA — c ⩽ 0. При u = 0 как раз и возникнет знак минус у «коэффициентов в строке функционала».
Помимо своей фундаментальной значимости, двойственность используется и на практике (при исследовании устойчивости, например). Если к решённой задачи ЛП добавить новое ограничение, то с помощью двойственного симплекс-метода можно задачу «дорешать» с финальной симплекс-таблицы, а не решать полностью с нуля.
В общем, спасибо за статью, но в качестве пожелания к последующим — хотя бы ссылайтесь на важные вещи, чтобы читатели были в курсе их существования.
P.S. Целая статья про М-метод? Я заинтригован :)
Когда-то, лет 10-12 назад, делал частичную (ограничения только вида <=) реализацию симплекс-метода на VBA, с выводом промежуточных решений. Недавно выложил в общий доступ, кому интересно, можете скачать тут.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Подробный разбор симплекс-метода