Из задач этого типа наиболее важной и изученной является так называемая транспортная задача с фиксированными доплатами. Это математическая задача линейного программирования специального вида. Её можно рассматривать как задачу об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки.
Транспортная задача по теории сложности вычислений входит в класс сложности P. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).
Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку). Под названием транспортная задача, определяется широкий круг задач с единой математической моделью, эти задачи относятся к задачам линейного программирования и могут быть решены оптимальным методом. Однако, спец.метод решения транспортной задачи позволяет существенно упростить её решение, поскольку транспортная задача разрабатывалась для минимизации стоимости перевозок.
Методы решения задач дискретного и целочисленного программирования.
В задачах дискретного программирования область допустимых решений не является связной, поэтому не является выпуклой в обычном понимании. Отыскание решения таких задач сопряжено со значительными трудностями. Для решения задач дискретного и целочисленного программирования разработаны специальные методы. Эти методы делятся на 3 группы:
|
|
1. методы отсечения;
2. комбинаторные методы;
3. методы случайного поиска и эвристические методы.
Метод отсечения для решения задач целочисленного линейного программирования
Сущность методов отсечения состоит в том, что сначала задача решается без условия целочисленности. Если полученный план целочисленный, то задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами:
·оно должно быть линейным;
·должно отсекать найденный оптимальный нецелочисленный план;
·не должно отсекать ни одного целочисленного плана.
Дополнительное ограничение, обладающее указанными свойствами, называется правильным отсечением.
Комбинаторные методы решения задач целочисленного линейного программирования
Комбинаторные методы решения задач дискретного программирования основаны на полном переборе, в котором включены правила оценивания и отбраковки целых подмножеств решений, заведомо не содержащих оптимального решения. Классическая схема этого метода называется метод ветвей и границ
Методы случайного поиска
В случае простых целевых функций методы случайного поиска менее эффективны, чем любая регулярная процедура, но они оказываются полезными в более сложных случаях, когда целевая функция столь сложна, что невозможно заранее установить какие-либо ее свойства, позволяющие рационально выбирать направления поиска. Такие методы случайного поиска пригодны для любой целевой функции независимо от того, является она унимодальной или нет. Известно, что для любого регулярного алгоритма можно построить специальную функцию (класс функций), на которой он не будет работать. Случайный поиск позволяет оптимизировать любую функцию, хотя и с разной (иногда очень низкой) эффективностью. Методы случайного поиска создают подходящие предпосылки для применения в дальнейшем других методов поиска. Поэтому их (методы СП) часто применяют в сочетании с одним или несколькими методами других типов.
|
|
Эвристические методы
Эвристические методы основаны на подсознательном мышлении, не допускают алгоритмизации и характеризуются неосознанным (интуитивным) способом действий для достижения осознанных целей. Эвристические методы ещё называют методами инженерного (изобретательного) творчества.
Сейчас практически во всех преуспевающих фирмах, занятых созданием материальной и нематериальной (программы, методики) продукции, поиск новых идей и решений ведется с помощью тех или иных эвристических методов. А для современного инженера знание этих методов становится столь же необходимым, как и умение писать и читать. Даже журналисты, художники, бизнесмены и представители других профессий, кто остро нуждается в оригинальных идеях, активно используют такие методы.
Эвристические методы медленно, но постоянно совершенствуются и развиваются: от общих рекомендаций — к последовательности действий, далее — к алгоритмизованным методами, наконец, к созданию искусственного интеллекта.
Заключение
Дискретные оптимизационные задачи находят широкое применение в различных областях, где используются математические методы для анализа происходящих там процессов. Необходимость решения таких задач приводит к тому, что дискретная оптимизация становится важным элементом образования специалистов, связанных с ее применением при решении задач, возникающих в приложениях. Поэтому технология решения задач дискретного программирования должна стать одной из важных составных частей современного математического образования для специалистов по прикладной математике. В настоящее время разработаны современные методы и алгоритмы решения задач дискретного программирования. Разработаны пакеты прикладных программ, позволяющие решать ряд стандартных задач дискретного программирования. Знание существа применяемых алгоритмов и технологий их реализации позволяет более эффективно использовать разработанные пакеты. При возникновении новых нестандартных задач реализация алгоритмов их решения требует информации о технологии решения задач дискретной оптимизации.
|
|