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