2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение27.08.2012, 13:33 
Здравствуйте.

Предыстория:

(Оффтоп)

В 1990 году я закончил один из столичных ВУЗов по специальности «прикладная математика». Учился неплохо, имею «красный» диплом.
Не смотря на очень высокий уровень преподавания и контроля усвоения материала со строгими экзаменами по профилирующим дисциплинам, линейное программирование входило во второстепенный курс «Методы вычислений». Данный курс завершался зачетом, но не экзаменом и не входил в программу госэкзамена.
В общем, к стыду своему, я «проспал» тему «Линейное программирование».
Сложилось так, что я не работаю по основной специальности. Пришлось получить несколько дополнительных квалификаций, в основном, в области финансового анализа и учета и производственного менеджмента.
Где бы я ни работал, я всегда старался максимально использовать свои знания математики и, естественно, через некоторое время, где-то в 1996 году, первый раз столкнулся с экономической задачей, требующей знания линейного программирования. «Проспал» в свое время эту тему – не беда, помню, что базовые результаты по ЛП - достаточно простое приложение конечномерной линейной алгебры над действительным полем. Нашел какую-то книжку (помню, что автор – японец) по экономической математике с описанием симплекс-метода и внимательно изучил. Но самообучение сыграло со мной злую шутку. Так как мне необходимо было в сжатые сроки реализовать симплекс-метод на достаточно больших размерностях (~ 1000х1000), я уделил много внимания формальному описанию алгоритма, лишь бегло ознакомившись с теоретическими результатами.
Задача была решена. Использование разработанной методики принесло существенный экономический эффект. Есть чем гордиться.
Через некоторое время, возникла схожая экономическая задача. Я с энтузиазмом применил разработанное ранее ПО и, вдруг, полезли ошибки. Подробное разбирательство показало, что если ранее все линейные неравенства, задающие область решений были типа «<=», то теперь присутствуют и неравенства «>=», что приводит к введению т.н. вспомогательных переменных и решению дополнительной задачи минимизации линейной функции – суммы этих дополнительных переменных. Это делается с целью поиска первого решения и допустимого базиса, а также проверки на совместность системы неравенств. Данная ветка алгоритма ранее не использовалась, поэтому отлаживалась только по тестовым примерам, приведенным в книге.
Ошибка оказалась не в программе! Подробное исследование показало ошибку в методе, описанном в используемой книге. Логическая ошибка, делающая предложенный метод неприменимым в общем случае.
На дворе стоял 1998-й год, все описания симплекс-метода, которые я смог найти – были в учебниках по экономической математике и содержали эту ошибку. Я думаю, что это связано с тем, что все экономисты, переписывающие учебники друг у друга читали один и тот же источник, и, так же как и я, не осмысливали критически теоретическую сторону.
Жаль, что я «проспал» в свое время курс линейного программирования! Я точно знаю, что наши преподаватели такого косяка бы не допустили. И симплекс-метод преподавался корректно.

Видимо, я не умею искать математическую литературу в сети. Запросы в интернете приводят либо к ссылкам на курсовые и дипломные работы, не имеющие ничего общего с нормальной математикой, либо к ссылкам на бумажные книги. Ну и на одном из первых мест стоит статья в Википедии. Как назло, с той же ошибкой:
Симплекс-Метод
Обратите внимание на описание первой фазы двухфазного симплекс-метода: для определения совместности системы и нахождения первого допустимого решения и допустимого базиса используется минимизация суммы вспомогательных переменных. Если минимум =0, то система совместна и:
«… Это означает, что все вспомогательные переменные были выведены из базиса, и текущее решение является допустимым». (конец цитаты)
А с чего это вспомогательные переменные выведены из базиса? Равенство компоненты решения нулю вовсе не гарантирует, что это компонента не опирается вектор допустимого базиса. Верно только обратное утверждение.
Простейший контрпример: вырожденный случай (нулевая матрица >= 0).
Я уверен, что существует где-то на просторах инета правильно описанная методика, но я не нашел. Кроме одной англоязычной статьи, описывающей симплекс-метод на конкретном числовом примере размерности 3х3. Там правда сказано, что если после первой фазы вспомогательные переменные остались в базисе, то «нужно искать подходящие столбцы для замены» без описания как это делать в общем случае.
В свое время я сам для себя изложил симплекс-метод от постановки задачи до решения в общем виде. Когда пишешь – лучше запоминаешь детали. Сейчас мне предстоит ответственная работа по решению целого ряда экономических задач больших размерностей с использованием симплекс-метода.
А вопрос (просьба) состоит в следующем: Пожалуйста, может ли кто-нибудь из специалистов проверить то что я написал на предмет ошибок? Это всего 15 страниц несложной линейной алгебры. Файл здесь(формат MS Word 2003 с компонентой MS Equаtion для формул)

Спасибо за внимание,
Крамарев Владимир

 
 
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение27.08.2012, 21:19 
Аватара пользователя
VladimirKr
Успехов Вам в Вашем начинании. Вряд ли я могу Вам чем-то помочь, поскольку 1) никогда не программировал симплекс-метода, 2) никогда не заморачивался с изучением тонкостей метода. Однако попробую дать пару замечаний. Тут как-то выступал один знаток прикладной математики, который, в частности, охарактеризовал, чем наш специалист отличается от ихнего. Его точка зрения - наш будет с нуля программировать свою программу симплекс-метода. Когда читал его, подумал, что за ерунда, потому как считал, что наш только и смотрит, где что можно украсть. Однако, получается, что где-то он и прав. Да, есть такой специалист. По моему мнению (может и некомпетентному), эффективная программа решения задачи линейного программирования симплекс-методом для задач большой размерности крайне сложна и потребует для её создания нескольких человеко-лет. Есть два выхода. Первый - воспользоваться готовой программой. Я Вам тут не посоветую, что взять. Я юзал матлаб. Второй выход - если очень надо, чтобы была своя программа - программировать не симплекс метод, а какой-нибудь итерационный алгоритм. Например, метод внутренней точки. На мой взгляд, трудоёмкость программирования тут на два порядка (приблизительно) меньше. Возможно программа будет работать дольше, чем фирменная. Может и сильно дольше. (Например, вместо 0.1 сек. будет работать 3 сек. - ну и что?).

 
 
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение28.08.2012, 00:07 
Точнее сказать – нужно посвятить жизнь этому. Программировать самому - это безумие.

Во-первых, симплекс-метод реализован в Excel - не знаю, насколько хорошо. Также есть он в Open Office.
Во-вторых, можно что-нибудь бесплатное найти: GLPK, lp_solve, CLP/CBC - последний очень высокого качества
В-третьих, можно использовать недорогую коммерческую среду моделирования с встроенными бесплатными решателями (Quick NP)
В-четвертых, коммерческие программы типа CPLEX. Дорого, но можно решать задачи с десятками миллионов переменных и ограничений.

 
 
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение28.08.2012, 09:40 
Спасибо откликнувшимся.
Цитата:
В-четвертых, коммерческие программы типа CPLEX. Дорого, но можно решать задачи с десятками миллионов переменных и ограничений.

Позволю себе усомниться. Как Вы представляете себе механизм загрузки и хранения массива данных порядка $((10^7))^2$ и соблюдения необходимой точности вычислений?
Боюсь, что плохо сформулировал вопрос. Я не спрашивал, насколько трудно реализовывать СМ и какие реализации уже есть. Этот велосипед уже сделан мной лет 15 назад. Единственное, что из обычной dll переведен в COM, для красоты осталось добавить потокозащищенность. Это будет маленький модуль большой ERP.
Вопрос чисто теоретический. Попробую сформулировать еще раз: Почти все описания симплекс-метода, которые я встречал, содержат одну и ту же ошибку (кстати, верно ли это?). Пришлось изобрести еще один велосипед: корректный переход к допустимому базису после первой фазы двухфазного симплекс-метода.
Прошу проверить, правильно ли я это сделал.

Спасибо.

 
 
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение28.08.2012, 10:42 
Очень трудно найти задачи, где каждый элемент связан с каждым другим элементом. Поэтому, громоздкие задачи имеют разряженные матрицы и в процессе решения хранят только ненулевые элементы. Примерные расходы памяти 12 байт на ненулевой элемент.

Обратная матрица представляется в так называемом мультипликативном виде. Точность достигается за счет так называемой рефакторизации. В противном случае, уже даже в задачах 300x300 начинаются проблемы с точностью и устойчивостью. И дело, разумеет не только в точности, но и в производительности и расходах памяти – при тупой реализации симплекс метода нулевые элементы начинают заполняться ненулевыми.

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

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

 
 
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение28.08.2012, 11:09 
Цитата:
И наш прямой вопрос тоже есть ответ. Можете найти указанные мной пакеты, там есть координаты разработчиков (это e-mail, форумы и т.д.). И задать свой вопрос. Они покрутят пальцем у виска, но, скорее всего, Вам квалифицированно ответят. Квалифицированно, понимете? Впрочем, как хотите.

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

 
 
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение28.08.2012, 17:23 
Аватара пользователя
VladimirKr в сообщении #611661 писал(а):
И все еще надеюсь, что квалификация большинства участников форума dxdy позволит мне получить ответы на, как мне кажется, простые вопросы.

На мою квалификацию не расчитывайте (однако самому интересно разобраться, и возможно помочь Вам). Прочёл в Википедии про двухфазный метод. И вот тут возник вопрос: а почему нас (точнее, Вас) должно волновать - останутся ли вспомогательные переменные в базисе или нет? Нас должны интересовать исключительно две вещи. Первая вещь. Будут ли равны нулю все вспомогательные переменные? Если нет, то в исходной задаче допустимых точек нет. А вот если они будут равны, то нам интересна вторая вещь - значения основных переменных. После чего про первую фазу забываем (и что там было в базисе, а что не было - не нужно нам это), и возвращаемся к решению исходной задачи (без всяких вспомогательных переменных). Начальную точку мы уже получили. Т.о. я совсем не понял постановку вопроса. Но прочитал всё очень бегло. Попробую прочитать подробнее.

 
 
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение28.08.2012, 17:29 
 !  Toucan:
Спам удален, пользователь забанен

 
 
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение28.08.2012, 17:30 
Аватара пользователя
VladimirKr в сообщении #611138 писал(а):
линейное программирование входило во второстепенный курс «Методы вычислений».

Не думаю, что "Методы вычислений" второстепенный курс на специальности "Прикладная математика".

-- Вт авг 28, 2012 18:51:10 --

VladimirKr в сообщении #611138 писал(а):
Подробное разбирательство показало, что если ранее все линейные неравенства, задающие область решений были типа «<=», то теперь присутствуют и неравенства «>=»

А что, нельзя данное оганичение умножить на $-1$?

 
 
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение28.08.2012, 18:01 
Цитата:
Начальную точку мы уже получили.

Но не получили начальный базис, если в нем остались столбцы на позициях вспомогательных переменных...
Цитата:
А что, нельзя данное оганичение умножить на -1 ?

И отрицательный свободный член справа... До свидания, первое допустимое решение...

 
 
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение28.08.2012, 19:06 
Аватара пользователя
VladimirKr
Попробуйте почитать С.А.Ашманов. Линейное программирование. гл.5 пар.5. Конкретно на стр. 183 по-моему то, что Вы спрашиваете.
VladimirKr в сообщении #611138 писал(а):
Сейчас мне предстоит ответственная работа по решению целого ряда экономических задач больших размерностей с использованием симплекс-метода

Если не секрет, то что Вы подразумеваете под большой размерностью?

-- Вт авг 28, 2012 20:09:08 --

VladimirKr в сообщении #611138 писал(а):
Видимо, я не умею искать математическую литературу в сети.

Пользуйтесь поисковиком http://libgen.info. Задавайте запросы типа "линейное программировние" или "симплекс-метод".

-- Вт авг 28, 2012 20:30:16 --

VladimirKr в сообщении #611661 писал(а):
Еще, все же, предполагаю, что корректный СМ - это не настолько сакральные знания, что требуется консультация у напрямую у разработчиков

Для начала можно почитать Муртаф Б. Современное линейное программирование. Теория и практика.

 
 
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение29.08.2012, 09:08 
мат-ламер
Цитата:
Попробуйте почитать С.А.Ашманов. Линейное программирование. гл.5 пар.5. Конкретно на стр. 183 по-моему то, что Вы спрашиваете.
...
Пользуйтесь поисковиком http://libgen.info. Задавайте запросы типа "линейное программировние" или "симплекс-метод".
...
Для начала можно почитать Муртаф Б. Современное линейное программирование. Теория и практика.

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

Конечно, не десятки миллионов. Где-то $2000^2$
Работает секунд 30 на iCore2duo 800MHz. Приемлемо. Возможно, подготовка данных из-за тяжелых запросов к БД будет занимать больше времени...

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group