Министерство образования республики беларусь белорусский государственный университет гуманитарный факультет Кафедра информационных технологий
Скачать 0.49 Mb.
|
7 Дискретное программированиеДискретное программирование — раздел оптимального программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. В противоположность задачам оптимизации с непрерывными переменными, переменные в задачах дискретного программирования принимают только дискретные значения, например, целочисленные. В экономике огромное количество задач носит дискретный характер. Прежде всего это связано с физической неделимостью многих факторов и объектов расчета: напр., нельзя построить 2,3 завода или купить 1,5 автомобиля. Все отраслевые задачи строятся в расчете на определенное количество предприятий или проектных вариантов. В планировании распространены типовые размеры предприятий, типовые мощности агрегатов — все это вносит дискретность в расчеты. Наконец, плановые показатели: годовые, месячные или суточные периоды — это дискретные, раздельные периоды, у каждого из которых есть свое начало и свой конец. Дискретными являются задача о коммивояжере, задача о назначениях, задачи теории расписаний и т. д. Для решения задач Д. п. применяется ряд способов. Самый простой (для линейных дискретных задач) — решение обычной задачи линейного программирования с проверкой полученного результата на целочисленность и округлением его до приближенного целочисленного решения. Часто в практических задачах искомые переменные принимают только два значения — “1” и “0”. (Их называют задачами булева линейного программирования.) Иногда Д. п. называется целочисленным Пример задач дискретного программирования можно посмотреть в приложении 5. 8 Стохастическое программированиеСтохастическое программирование — раздел математического программирования, совокупность методов решения оптимизационных задач вероятностного характера. Это означает, что либо параметры ограничений (условий) задачи, либо параметры целевой функции, либо и те и другие являются случайными величинами (содержат случайные компоненты). В ст.“Транспортная задача”, напр., приведена детерминированная модель. В стохастической постановке та же задача будет более близкой к реальности. Рассмотрим одно условие (заданный объем спроса) и допустим, что спрос bj потребителя j — случайная величина bj(w), где w — характеристика распределения этой величины. Тогда в одних случаях (при одних ее реализациях) возникает ущерб от неудовлетворенного спроса — штраф за дефицит”, в других, наоборот, потребитель получает излишний груз и, следовательно, тратит дополнительные средства на хранение и перевозку. Все это усложняет решение задачи, т. е. нахождение оптимального варианта прикрепления поставщиков к потребителям. Вероятностный характер задач планирования часто объясняется неполнотой информации об их условиях. Бывает, однако, и так, что сложную детерминированную задачу, для точного решения которой требуется слишком большой объем вычислений, целесообразно привести к вероятностному виду, хотя вся информация известна. Это называется “стохастическое расширение детерминированной задачи”. Объем вычислений при этом существенно сокращается. Образно говоря, модель как бы рассматривается издалека: детали исчезают, но зато общая структура задачи становится более ясной, обозримой. Казалось бы, при решении стохастических задач проще всего находить средние величины всех случайных параметров, сводить, таким образом, задачу к детерминированной и использовать обычные методы математического программирования. Однако опыт показывает, что такой подход не всегда эффективен: при некоторых реализациях случайных величин задача может не иметь решения. Не во всех случаях пригодна и т. н. жесткая постановка задачи С. п., означающая, что ограничения задачи должны обязательно удовлетворяться при всех реализациях случайных параметров. Впрочем, во многих задачах она и не требуется. Можно ограничиться условием: чтобы соблюдалась некоторая заданная вероятность удовлетворения ограничений. Наиболее успешно решаются двухэтапные задачи С. п. Их смысл можно показать на примере планирования производства при неопределенном будущем спросе на продукцию. Сначала (первый этап) устанавливается предварительный оптимальный план (задача выступает как детерминированная, ее решение — вектор с детерминированными компонентами). Под этот план проектируется и устанавливается оборудование, ведется технологическая подготовка производства и т. д. На втором этапе план корректируется в соответствии с реальным спросом. При этом чем лучше были учтены все статистические характеристики возможного спроса в предварительном плане, тем меньше затрат потребуется на корректировку действительного объема производства. Если продолжить в дальнейшем такие корректировки на основе учета характеристик случайного спроса, то двухэтапная задача перерастет в многоэтапную стохастическую задачу управления |
Похожие:
 | Республики Беларусь Белорусский государственный университет Юридический факультет Принятие решения по акту проверки и порядок его обжалования в Республике Беларусь 3 |  | Республики Беларусь Белорусский Государственный Университет Интересный факт из истории создания Java-технологии, или удар по «пакету Windows» 29 |
| Республики Беларусь Учреждение образования «Белорусский государственный... Составители: В. А. Овсянкин, кандидат педагогических наук, доцент, Г. Н. Сущенко, старший преподаватель | | Министерство образования и науки РФ новосибирский государственный... Когда появляется изображение цепи ордена Андрея Первозванного на российском гербе |
| Республики Беларусь Белорусский государственный университет Управляющие... Если необходимо обеспечить выполнение цикла хотя бы один раз, то удобно использовать оператор цикла с постусловием: 20 | | Дмитрий Олегович Роль информационных технологий в обеспечении деятельности... Роль информационных технологий в обеспечении деятельности банковской системы Республики Беларусь на примере сэд «Канцлер» |
| Совершенствование правового регулирования таможенных процедур переработки... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Московский государственный... | | Государственный образовательный стандарт высшего профессионального... На основании статьи 35 Закона Республики Беларусь от 20 июля 2007 года "Об обращении с отходами" Министерство природных ресурсов... |
| Классификация и кодирование информации; системы классификации; методы кодирования Министерство образования республики беларусь учреждение оразования «мозырский государственный педагогический университет имени И.... | | Республики Беларусь Учреждение образования «Белорусский государственный... Контрольная работа предназначена для самостоятельного выполнения студентами с целью проверки качества освоения ими теоретического... |
| Пояснительная записка программа интернатуры по оториноларингологии... Заведующая кафедрой болезней уха, горла, носа учреждения образования «Белорусский государственный медицинский университет», кандидат... | | Республики Беларусь Учреждение образования «Белорусский государственный... Дневник здоровья предназначен для определения физического состояния студентов бгпу, записи заданий преподавателя для самостоятельных... |
| «московский психолого-социальный университет» факультет информационных технологий утверждаю Рабочая программа предназначена для бакалавров кафедр Информатики и математики и Информационных технологий очной и заочной формы... | | Министерство образования и науки российской федерации правительство... Правила определяют основные требования технической эксплуатации железной дороги |
| Применение технологий olap и Data Mining для поддержки принятия стратегических решений в вузе Дагестанский государственный университет, факультет информатики и информационных технологий, Махачкала, Россия | | Учебно-методический комплекс по модулю «астрономия» (б кв ) Факультет... ... |
