Содержание к диссертации
Введение
Глава 1. Обзор оптимизационных методов решения задач возникающих при создании математического обеспечения информационных систем 12
1.1.Основные методы нахождения точного решения 12
1.2.Основные методы нахождения приближенного решения 17
1.3. Применение принципа итеративной регуляризации в задаче математического программирования 20
Глава 2. Модель математического обеспечения интерактивной системы поддержки принятия решений при управлении производством 24
2.1.Введение в производственную задачу 24
2.2. Проблема упорядочивания разновременных операций 30
2.3. Содержательная постановка задачи 37
2.4. Описание переменных модели 43
2.5. Метод решения производственной задачи математического обеспечения информационной системы 46
2.6. Описание уравнений модели 52
Глава 3. Применение метода итеративной регуляризации к производственной задаче 63
3.1. Схема решения задачи 63
3.2. Регуляризирующий алгоритм 67
Глава 4. Общая схема и пример работы программы 79
4.1. Организация программы 79
4.1.1. Осуществления связи с базой данных и создание своей 81
4.1.2. Формирование матриц на основе числовых данных 82
4.1.3. Опрос экспертов 84
4.1.4. Формирование матриц на основе «жестких» экспертных ограничений и «мягких» экспертных пожеланий 86
4.1.5. Приведение информации к системе линейных уравнений и неравенств 88
4.1.6. Вывод из оптимизации определенных операций 94
4.1.7. Назначение весов технологических параметров 95
4.1.8. Выполнение некоторого числа итераций. 96
4.1.9. Анализ результата после данного числа итераций 97
4.1.10. Формирование плана производства 98
4.1.11. Оценка выполнения плана производства и корректировка плана 99
4.2. Пример работы программы 100
Основные результаты работы 120
Литература 122
- Применение принципа итеративной регуляризации в задаче математического программирования
- Метод решения производственной задачи математического обеспечения информационной системы
- Приведение информации к системе линейных уравнений и неравенств
- Оценка выполнения плана производства и корректировка плана
Введение к работе
Общая характеристика работы. Диссертационная работа посвящена разработке интерактивной компьютерной системе поддержки принятия решений при управлении производством с неспециализированным оборудованием. Предлагаемая система отличается тем, что позволяет учитывать многие технологические параметры совместно с экспертными оценками. Производственный план, который предлагает система, обладает высокой надежностью и устойчивостью к возможным сбоям и бракам на производстве. В работе излагается модель, которая приводит к задаче линейного программирования. В качестве алгоритма решения задачи используется метод итеративной регуляризации.
Актуальность проблемы. В современном мире возникает необходимость в специальных программах и информационных системах, ориентированных на решение конкретных проблем. В частности, такая потребность стала особенно актуальна для крупных промышленных предприятий [10-29]. Одна из стандартных ситуаций, в которых руководство предприятия сталкивается с проблемой принятия ответственного решения, состоит в том, что предлагается заказ на изготовления определенной продукции, например, машиностроения.
Для того чтобы принять взвешенное решение, руководству необходимо ответить для себя на ряд вопросов, перечислим основные из них:
1. Располагает ли предприятие основными фондами для выполнения заказа.
Может ли оно выделить трудовые ресурсы в нужном количестве и необходимой квалификации.
Как будет обеспеченно производство всеми необходимыми материалами, заготовками, сырьем.
Гарантированно ли выполнение заказа в срок.
Какова себестоимость производства и как она соотносится с предлагаемой оплатой заказа.
Для того чтобы ответь на эти основные и другие, связанные с этими, вопросами необходимо смоделировать процесс производства. Разумеется, при этом необходимо прогнозировать возможные сбои и браки, могущие возникнуть в процессе производства, причем с учетом, как их вероятностей, так и их последствий.
Одновременно, в процессе моделирования необходимо разработать, оптимальный план производства, без которого невозможно ответь на эти основные вопросы.
Естественно, что под «оптимальностью» надо понимать не столько строгую минимизацию себестоимости, сколько устойчивость плана к реальным сбоям и проблемам.
Итак, еще до того как ответить на вопрос браться ли за этот заказ вообще, нужно разработать план его выполнения.
Нередко при составлении плана руководство обладает достаточно большими степенями свободы, с помощью которых можно существенно, по-разному планировать. Например, изготовлять ли детали в том или ином цеху, использовать ли только свободные мощности или позволять сдвигать выполнение операций
по другим заказам и использовать занятые на них мощности, и так далее.
При составлении такого плана необходимо использовать огромное количество информации относительно как имеющихся на предприятии ресурсов, так и необходимых технологических условий для производства.
Кроме большого количества числовой информации необходимо учитывать накопленный практический опыт специалистов, который может выражаться не только в числовом виде, но и в виде качественных рекомендаций. Заметим также, что мнения экспертов надо делить на категорические требования, которые надо выполнять обязательно, и на пожелания, которые надо стремиться выполнить, учитывая «вес», то есть степень важности, пожеланий [87].
Все эти соображения достаточно наглядно доказывают актуальность создания специальной информационной системы, помогающей руководителю предприятия как принимать решения, так и реализовывать их.
Целью предлагаемой работы является разработка специального математического и программного обеспечения вычислительных машин, ориентированного на решении ряда задач, возникающих на производственном предприятии при получении нового заказа. При этом предлагаемая информационная система может применяться в различных вариантах. Простейшим является вариант с использованием только свободных ресурсов предприятия, а более сложным является, вариант со сдвигами уже существующих заказов.
Научная новизна. Предложен новый подход к разработке интерактивной системы, основанной на совместном и одновременном использовании большого количества информации, носящей как объективный характер, выраженный численно, так и субъективный характер выраженный количественно и качественно.
Новым в предлагаемой работе является разработка математической модели, которая обеспечивает составление плана производства с указанием, в каком количестве и порядке использовать имеющиеся трудовые и производственные ресурсы. При этом модель сводится к задаче математического программирования [49-64,75-77].
Существенно новым является и то, что, несмотря на то, что методы решения задач математического программирования хорошо разработаны, в работе используется не классические схемы их решения, а более современные [1-9].
Используемый в работе метод оперяется на принцип итеративной регуляризации, который имеет ряд преимуществ по сравнению с классическими методами, дающими строго оптимальное решение, например симплекс-методом [75-77]. Перечислим их [6,7]:
Возможность строгого выполнения экспертных требований.
Возможность частичного удовлетворения мягких экспертных пожеланий сообразно с их весами.
Получение псевдорешения несовместных уравнений.
Решение обладает минимальной нормой.
Устойчивость решения к возмущениям данных.
Каждая итерация очень проста по сравнению с классическим методом.
Возможность остановки итераций, если с экспертной точки зрения, полученный результат достаточно хорош. Разработан специальный интерфейс, обеспечивающий
возможность удобного интерактивного человеко-машинного общения, необходимого для решения данной задачи.
Практическая ценность предлагаемой информационной системы состоит в том, что составленный ею план производства обладает всеми необходимыми качествами. Перечислим их [12]:
1. План удовлетворяет всем имеющимся на данном
предприятии ограничениям.
Ограничениям, связанным с использованием трудовых ресурсов. Ограничениям, как по квалификации, так и по количеству.
Ограничениям, связанным с производственными мощностями.
Временным ограничениям.
Ограничениям в использовании дефицитных ресурсов.
План использует все имеющиеся практические знания специалистов, выражающихся как в форме жестких запрещений, так и в форме предпочтений, причем предпочтения могут задаваться с различными весами.
Минимизируется себестоимость, причем учитывается отдельная оплата за использование разрешенной сверхурочной работы оплаты и вынужденных простоев рабочей силы.
План обеспечивает наиболее равномерную загрузку рабочих центров, при выполнении изложенных выше требований.
Наглядное представление об очередном плане после определенного числа итераций. Это дает возможность руководителю прекратить итеративный процесс, когда результат окажется удовлетворительным. При этом различными цветами числовых показателей в таблицах и графиками отражается степень точности выполнения ограничений.
6. В случае невозможности составить план,
удовлетворяющий строго всем ограничениям, показываются узкие
места и возможные варианты их устранения. Например, увеличения
срока, привлечение дополнительных ресурсов, сокращение объема
заказа, и так далее.
Апробация работы. По теме диссертации опубликовано пять печатных работ, в том числе основные результаты диссертационной работы докладывались на следующих конференциях:
Международная научно-техническая конференция «Фундаментальные проблемы радиоэлектронного приборостроения» INTERMATIC-2003 (Москва, 2003г). Работа отмечена дипломом и почетной медалью Международной академии авторов научных открытий и изобретений «За заслуги в деле изобретательства» в области математического моделирования управления производственным предприятием.
Конференция «Российская электроника -нефтегазовому комплексу» (Чебоксары, 2003г.).
Международная научно-техническая школа-конференция «Молодые ученые - науке, технологиям и
профессиональному образованию» Молодые ученые-2003 (Москва, 2003г.). Работа награждена почетной грамотой в области Информационных технологий.
Система нашла применение в управлении деятельного производства компании ООО «Клиент-Серверные-Технологии» с октября 2003 года. Данная работа используется как часть модуля «МЗ-Эксперт» интегрированной системы управления предприятием «МЗ».
Используемый ранее модуль имел следующие практические недочеты по сравнению с описываемым вариантом:
Отсутствие минимизации себестоимости.
Недостаточное использование экспертных оценок.
Неравномерность загрузки рабочих центров. Автор благодарит научного руководителя доктора
технических наук Л. Я. Миллера за руководство исследованием и постоянное внимание к работе.
Автор приносит благодарность генеральному директору ООО «Клиент-Серверные-Технологии» кандидату экономических наук В.Д. Шалюхну за помощь в решении многих вопросов по разработке и реализации данной системы.
Автор благодарит коллектив кафедры
«Автоматизированные системы управление » РГУ нефти и газа имени И.М. Губкина, где он получил образование, позволившее выполнить настоящее исследование.
Особенную благодарность автор приносит за научные консультации и огромную помощь в работе доктору технических наук, профессору Е.В. Гливенко.
Применение принципа итеративной регуляризации в задаче математического программирования
Рассмотрим модель, которая оптимизирует производственный процесс. Пусть надо распределить среди некоторых рабочих центров производство определенных деталей, сумма которых составляет экзогенно заданный план.
Это распределение должно быть подчинено с одной стороны группе жестко заданных требований, которые будут перечислены ниже, с другой стороны согласоваться с определенными экспертными оценками разных аспектов производственного процесса и, наконец, с третьей стороны являться оптимальным с точки зрения выбранной целевой функции.
Рассмотрим подробнее один из возможных вариантов жестко заданных требований, определенных планом и производственной необходимостью. План задает срок, к которому должны быть произведены все детали и собранны в виде конечной, для данного производства, продукции. Должен быть составлен иерархический список деталей по порядку последовательной обработки из простейших заготовок к конечным изделиям. Иначе говоря, должно быть задано дерево последовательных выполнений операций. Нужно задать также точное количество всех типов деталей, заготовок, сырья, ресурсов. Остановимся подробнее на понятиях заготовка деталь. Деталь делается из заготовки (или группы заготовок), но зачастую деталь сама является заготовкой для следующей операции. Для конкретной операции эти понятия различаются четко: заготовка до операции, деталь после. Кроме перечисленных данных, которые относятся к данному заказу, необходимо строго определить ряд других численных данных. Эти данные должны характеризовать имеющиеся в наличии производственные мощности и трудовые ресурсы, с учетом их квалификации. Для этого, в частности, должна быть составлена матрица, столбцами в которой являются все типы производственных операций, а строками все типы рабочих центров, на которых данную операцию можно производить. Аналогичная матрица составляется из чисел, задающих время изготовления минимальной партии деталей данного типа (точнее говоря, минимального количества операций) на данном рабочим центре. Еще одна соответствующая матрица определяет себестоимость производства данной минимальной партии деталей на ячейке. (Ячейкой, иногда для краткости будем называть рабочий центр). Напомним, кстати, что под термином «рабочий центр» понимают обычно объединение определенного рабочего места, со всем необходимым оборудованием, совместно с рабочим нужной квалификации. Можно также употреблять этот термин для обозначения не только одного рабочего с необходимым оборудованием, но и группу рабочих, совместно с их станками, объеденными с точки зрения данной производственной проблемы в единое целое. Другие важные понятия это заготовка и деталь. Деталь делается из заготовки, но она может являться заготовкой для следующей операции, поэтому оба эти термина применяются одновременно. Для каждой операции эти понятия различаются четко: заготовка до операции, деталь после. Кроме перечисленных выше данных, определяющих производственные возможности данного рабочего центра, необходимо знать количество рабочего времени для каждой ячейки. Также надо определить оплату сверхурочных часов работы, возможно различную для каждой ячейки. Эта оплата может быть задана и с учетом величины занятого дополнительного времени. Например, до десяти процентов сверхурочных часов для данного рабочего центра стоят «А», от десяти процентов до двадцати процентов стоят «В», от двадцати процентов до тридцати процентов стоят «С», а выше тридцати процентов перегружать рабочие центры запрещено. Кроме оплаты сверхурочных часов должна быть определена компенсация за простой, вынужденный по производственной необходимости или целесообразности. Это необходимо задать, так как во время простоя рабочие не получают сдельной оплаты. Разумеется, что величины простоев, даже с учетом применяемой компенсации, не должны быть слишком велики, что тоже должно быть согласовано с экспертом, а затем заданно численно. Кроме перечисленных точных цифровых данных модель позволяет включать в себя экспертные оценки, которые являются аккумулированными практическими знаниями, полученными специалистами во время производственной деятельности. Учет практического опыта специалистов является одним из главных достоинств предлагаемой модели, опирающейся на особенности процесса сходимости при итеративной регуляризации. Подробнее остановимся на этом ниже, а сейчас лишь коснемся того, что в данной модели можно задать группу дополнительных данных. Эти данные составляют экспертные оценки, которые характеризуют категорию «желательности» к различным сторонам производственной деятельности [65-73]. Также заметим, что, кроме «желательных» соображений экспертов, вводятся абсолютно твердые экспертные запреты, наличие которых существенно влияют на надежность полученного результата. В качестве целевой функции целесообразно использовать себестоимость размещаемого на данном предприятии заказа. Разумеется, надо фиксировать все виды издержек. Остановимся на этом подробнее. Должны учитываться все расходы на зарплату, включая оплату сверхурочных часов работы и компенсацию за вынужденные простои. При этом допускаются различные варианты расчета для разных рабочих центров. Издержки, связанные с потреблением ресурсов, например, электроэнергии, воды и так далее. Использование фондов, с учетом их амортизации, возможных ремонтов и так далее. Должны учитываются все расходы на закупку сырья и заготовок, поставку определенных видов деталей внешними поставщиками. Таковы в общих чертах необходимые для расчета основной производственной задачи данные. Итак, подытожим данный параграф. Разработанная модель распределяет некий заказ между рабочими центрами. Распределение происходит с учетом всех численных ограничений, а также с учетом экспертных оценок как жестких, так и мягких. Если при этих условиях поместить заказ невозможно, то модель сообщает об этом. Модель в этом случае перечисляет все узкие места и возможности их изменения, при помощи привлечения дополнительных производственных ресурсов.
Метод решения производственной задачи математического обеспечения информационной системы
Напрашивается идея свести данную задачу к стандартной задаче математического программирования, или даже, что еще удобнее, к задаче линейного программирования. Для этого надо лишь ввести целевую функцию. В качестве целевой функции было бы естественно взять суммарную себестоимость всего заказа, с учетом всех доплат (например, за сверхурочную работу) и всех компенсаций.
Можно было бы воспользоваться имеющимися хорошо разработанными методами решения задачи линейного программирования, начиная с самого первого метода - симплексного. Можно было также привлечь методы целочисленного программирования, что давало бы возможность получить ответ в удобном виде, а не обрабатывать ответ после решения в окончательном виде.
Однако, поставленные численные эксперименты, как на условных численных данных, так и на реальных, заставили пойти другим путем. Дело в том, что точные методы решения задачи математического программирования, наряду с безусловными преимуществами (например, большая скорость сходимости процесса), обладают существенными недостатками. Одним из них является отсутствие устойчивости решения, относительно даже незначительного изменения численных данных. Это очевидное следствие того, что решение ищется только в вершинах многомерного многогранника, образованного гиперплоскостями ограничений. С практической точки зрения этот недостаток очень существенен. Действительно, все численные данные не только не совсем точны, но и могут несколько изменятся по ходу производства. Любая болезнь рабочего, поломка станка, или мелкая проблема с поставками есть изменение численных данных. И при этом решение может перескочить в совершенно другую вершину. Это означает абсолютно новый план, с, возможно, совсем новым размещением операций по рабочим центрам. Заметим, что все это делается только для того чтобы абсолютно точно выполнить все уравнения и, может быть, совершенно незначительно понизить себестоимость. Иначе говоря, небольшие преимущества абсолютно точного решения ведут к потере очень существенного свойства устойчивости приближенного решения. Другим недостатком является достаточно строгое требование имеющихся алгоритмов решения задачи математического программирования к виду матрицы. Вырожденная матрица, несовместные уравнения приведут к невозможности прямого решения задачи. Хотя, разумеется, с некоторыми из указанных недостатков разработаны методы борьбы, но проблемы все-таки остаются. Применяемый в данной работе метод не только свободен от указанных недостатков, но и обладает рядом других преимуществ, дающих большие практические удобства. Неизбежной, по-видимому, платой за это является медленная сходимость метода. Однако, на практике это не очень существенно, так как итеративный процесс организован таким образом, что по истечению не слишком большого числа итераций полученный результат хотя и не является оптимальным, но является достаточно хорошим. Это обеспечивается, в частности, и устойчивостью. Кроме того, в модель введено большое количество различных экспертных оценок, гарантирующих приемлемость полученного решения. Не совсем понятно и что вообще означает «абсолютная оптимальность» на практике, так как в числовых данных допускаются отклонения. Применим процесс итеративной регуляризации, обеспечивающий сходимость, к решению системы линейных уравнений при ограничениях Где большинство неизвестных х І обозначают вытянутый в вектор двумерный массив { Z ц } показывающий сколько операций і -ого типа делается на j -том рабочем центре. Часть неизвестных составляет дополнительные переменные, превращающие неравенства в уравнения. При этом конечное «решение» обладает минимальной нормой (нормальное псевдорешение). В нашем конкретном случае под нормой понимается сумма квадратов всех переменных. При решении системы линейных уравнений методом итеративной регуляризации целевая функция отсутствует в математическом смысле. Однако в экономическом смысле она присутствует. Это минимизация себестоимости выполнения данного заказа и, таким образом, максимизация прибыли предприятия, как разницы между стоимостью заказа и себестоимостью его выполнения. Роль целевой функции выполняет последнее уравнение. Левой частью этого уравнения является полная себестоимость заказа, учитывающая все издержки производства, в том числе оплату труда, включая компенсацию за вынужденные простои и дополнительную оплату сверхурочной работы. В правой части этого последнего уравнения стоит назначенная экспертами «идеальная себестоимость», то есть число, заведомо меньшее чем любая реальная себестоимость.
Алгоритм, стремясь уменьшить неизбежную невязку в последнем уравнении, будет минимизировать реальную себестоимость.
Заметим, что это свойство дает дополнительную возможность для руководителей предприятием управлять составлением плана. Действительно, чем меньше «идеальная себестоимость», тем больше невязка и, следовательно, тем жестче алгоритм борется за минимизацию себестоимости. При этом остальные невязки, например борьба со сверхурочной работой, исправляются медленнее. Таким образом, руководители могут искать наиболее приемлемый для себя вариант, пробуя делать расчеты с различной «идеальной себестоимостью».
Приведение информации к системе линейных уравнений и неравенств
Схема решения задачи состоит из восьми последовательных этапов. 1. Точное описание рассматриваемого заказа. Срок выполнения заказа и его оплата. 2. Детальное рассмотрение экспертами дерева последовательных обработок деталей и их количество. Точный список всех необходимых материалов, заготовок, фондов и ресурсов, в том числе трудовых. 3. Разбиение экспертами всего периода выполнения заказа не «периоды», в каждом из которых есть свой план производства. С точки зрения решения оптимизационной задачи каждый такой крупный период можно рассматривать как самостоятельный заказ со своими данными. При том метод решения их всех одинаковый, но данные разные. Таким образом, основная задача разбивается на ряд последовательных задач. Впредь будим говорить только о решении такой подзадачи, называя ее для краткости задачей. 4. Выбор из базы данных всех сведений об имеющихся ресурсов, которыми располагает производство. Ресурсов в широком смысле, то есть список рабочих центров с их оборудованием и трудовыми ресурсами; имеющиеся готовые детали; ограничения на использование дефицитных ресурсов, таких, как, например, электричество, вода и так далее. Все данные о сроках выполнения различных операций на разных рабочих центрах, совместно с их себестоимостью. Тариф платы сверхурочных работ и простоев для каждого рабочего центра. Возможность поставок деталей внешними поставщиками и их стоимость. 5. Список всех пожеланий, составленный экспертами, причем в этот список включаются «мягкие» пожелания и «жесткие» требования. Ниже об этом будет сказано подробнее, так как именно в этом состоит новизна и основное преимущество применяемого метода. Пока укажем лишь на то, что степень мягкости может быть задана количественно, то есть может быть задан «вес» каждого пожелания. 6. Срок выполнения каждой задачи (подзадачи) разбивается на предплановый, основной и послеплановый периоды. Основной отрезок времени, например, месяц, разбивается на небольшие части (назовем их условно днями). Каждый такой день, в идеале, то есть при отсутствии чрезвычайных происшествий, не отличается от остальных дней из этой основной группы. В течение каждого дня происходит весь цикл работ, причем каждая деталь проходит лишь одну операцию. Именно план на день и является основной задачей, в которой применяется предлагаемый оптимизационный метод. Предплановый день и послеплановый день лишь создают условия для основного отрезка времени и определяются экспертами.
Нормировка данных, взятых из базы данных, для подготовки работы программы. Работа программы, в результате которой вырабатывается план на один день. Это означат, что выдается, сколько операций надо делать на каждом рабочем центре. Одновременно выдается информация о загрузке каждой ячейки, о количестве сверхурочной работы, о простоях или неполной загрузке рабочих центров. Может случиться, что эксперты предложили слишком перегруженный план, который выполнить при существующих ограничениях невозможно. В этом случае, некоторый результат все-таки выдается, но красный цвет, которым он печатается, сигнализирует о невозможности выполнения плана. При этом количество операций бывает выполнено меньше, чем запланировано, и одновременно, многие рабочие центры заняты сверхурочными, себестоимость при этом очень велика. Как правило, тогда экспертам необходимо изменить план, например, увеличить срок или привлечь дополнительные ресурсы к ячейкам, помеченным красным цветом. Возможен случай, когда план несколько перегружен, тогда сигнал желтого цвета, предупреждает об этом. Кстати, интенсивность цвета показывает степень перегруженности. Предусмотрен также случай, когда план недогружен, о чем также сигнализируется. При этом эксперты должны, естественно, сжать сроки или убрать ресурсы. После корректировки плана делается новый расчет. И так до тех пор, пока результаты не признаны удовлетворительными. Таким образом, хотя каждый из полученных результатов является оптимальным при предполагаемых данных и сроках, только последний является сбалансированным результатом.
Оценка выполнения плана производства и корректировка плана
Дальнейшее развитие математического программирования привело к созданию целых новых направлений. Были разработаны специальные алгоритмы линейного и нелинейного программирования. В числе других появились целочисленное и дискретное программирование [75-77,80,81].
Алгоритмы решения задач математического программирования позволяют решать многие задачи, возникающие при создании математического обеспечения информационных систем. Однако, при их применении возникают определенные проблемы. Рассмотрим их подробнее.
В задачах выпуклого программирования и, в частности, в наиболее часто встречающемся линейном программировании существование оптимальной точки зависит от существования седловой точки функции Лагранжа. Таким образом, задача сводится к поиску одновременного решения прямой и двойственной задачи. Оптимальная точка может находиться только в одной из вершин N-мерного многоугольника, ограниченного гиперплоскостями соответствующих ограничений. Это, с одной стороны, удобно, так как резко сокращается перебор, то есть количество итераций. В момент разработки Л. В. Канторовичем симплекс-метода это было особенно принципиально, так как расчет в задаче приходилось делать почти вручную.
С другой стороны, нахождение оптимального решения в вершине приводит к тому, что решение не является устойчивым. Это создает определенные проблемы во многих прикладных задачах.
Действительно, малейшее изменение численных данных может переместить оптимальную точку в совершенно другую вершину, даже совсем не обязательно в соседнюю. Это особенно принципиально, если учитывать, что, как правило, численные данные достаточно неточны, и значит, могут быть несколько изменены.
Другой проблемой является то, что алгоритм не способен находить решение для вырожденной матрицы. Хотя с этим недостатком зачастую можно бороться все тем же небольшим изменением численных данных, то есть возмущением элементов основной матрицы, но определенные трудности это все-таки создает.
Среди полезных свойств симплексного метода решения задачи математического программирования надо отметить также наличие одновременного решения двойственной задачи. Во многих экономических проблемах оптимальные значения двойственных переменных несут очень важную информацию. В частности, двойственные оценки или, иначе говоря, цена ограничений, была положена академиком Канторовичем в основу его теории ценообразования. Надо отметить, однако, что практическая ценность знания оптимального значения цены ограничения, то есть изменения целевой функции при изменении ограничений, снижается не только от отсутствия устойчивости решения, но и оттого, что это решение носит чисто дифференциальный, а не интегральный характер.
Другим известным методом решения оптимизационных задач является градиентный метод [82,83]. Этот метод известен также под названием «наискорейшего спуска» для целевой функции, у которой ищется минимум и, соответственно, «наискорейшего подъема» для максимизируемого функционала. Как известно в основе его лежит нахождение градиента в каждой следующей точке. Если рассматривать этот метод в применении к задаче математического программирования, то видно, что он обладает определенными практическими преимуществами в решении экономико-математических проблем, но и некоторыми недостатками по сравнению с симплексным методом.
К основным преимуществам надо отнести устойчивость решения и простоту каждой итерации, а к основным недостаткам медленную сходимость и необходимость специальной теории для вычисления длины шага. Градиентный метод, в его классическом виде, не гарантирует от нахождения локального, а не глобального экстремума. При этом появляется и зависимость «оптимального» решения от начальной точки. Методы нахождения точного оптимального решения прикладных оптимизационных задач хорошо дополняются методами нахождения приближенного решения. Остановимся на этом подробнее. Прикладная или вычислительная математика в значительной мере занимается проблемой получения приближенных значений некоторых отображений, возникающих при решении определенных математических моделей. Такие модели делятся на «корректные» и «некорректные». Корректной моделью называется модель, если связанное с ней отображение справедливо на всем пространстве и непрерывно на нем.
