2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



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


15/06/12
56
Здравствуйте.

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

(Оффтоп)

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

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

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

 Профиль  
                  
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение27.08.2012, 21:19 
Заслуженный участник
Аватара пользователя


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

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


17/10/08

1313
Точнее сказать – нужно посвятить жизнь этому. Программировать самому - это безумие.

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

 Профиль  
                  
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение28.08.2012, 09:40 


15/06/12
56
Спасибо откликнувшимся.
Цитата:
В-четвертых, коммерческие программы типа CPLEX. Дорого, но можно решать задачи с десятками миллионов переменных и ограничений.

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

Спасибо.

 Профиль  
                  
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение28.08.2012, 10:42 


17/10/08

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

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

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

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

 Профиль  
                  
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение28.08.2012, 11:09 


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

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

 Профиль  
                  
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение28.08.2012, 17:23 
Заслуженный участник
Аватара пользователя


30/01/09
6591
VladimirKr в сообщении #611661 писал(а):
И все еще надеюсь, что квалификация большинства участников форума dxdy позволит мне получить ответы на, как мне кажется, простые вопросы.

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

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


28/08/12

9
 !  Toucan:
Спам удален, пользователь забанен

 Профиль  
                  
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение28.08.2012, 17:30 
Заслуженный участник
Аватара пользователя


30/01/09
6591
VladimirKr в сообщении #611138 писал(а):
линейное программирование входило во второстепенный курс «Методы вычислений».

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

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

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

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

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


15/06/12
56
Цитата:
Начальную точку мы уже получили.

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

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

 Профиль  
                  
 
 Re: Симплекс-метод. Допусимый базиз и вспомогательные переменные
Сообщение28.08.2012, 19:06 
Заслуженный участник
Аватара пользователя


30/01/09
6591
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 


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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group