Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Методы целочисленного программирования
Целочисленное программирование – раздел линейного программирования, разрабатывающий и исследующий методы решения задач, искомые переменные которых имеют целочисленные значения. Математическая модель целочисленного программирования имеет вид (1.2)
Метод отсекающих плоскостей
Метод отсекающих плоскостей разработан Р. Гомори в 1957-1958 годах. Алгоритм метода включает этапы: Этап 1. Ослабленная задача. Целочисленность искомых переменных игнорируется, симплекс-методом определяется оптимальный план. Этап 2. Расширенная задача. Если план нецелочисленный, составляется дополнительное ограничение, “отсекающее” дробную часть искомой переменной. Дополнительное ограничение включается в систему ограничений и решается расширенная задача [3].
Метод ветвей и границ
Метод ветвей и границ применяется для решения полностью или частично целочисленных задач. Предложен А Лэндом и Дж. Дойгом в 1960 г. Дана математическая модель целочисленного линейного программирования при ограничениях (1.3) Найти вектор , максимизирующий целевую функцию. Для целочисленной переменной можно указать верхнюю и нижнюю границы, в пределах которых содержатся оптимальные значения
. (1.4)
В начале итерации метода ветвей и границ необходимо иметь: 1. Список задач линейного программирования, каждая из которых должна быть решена в последующих итерациях. 2. Нижнюю границу оптимального значения линейной формы задачи . На первой итерации в качестве берется значение целевой функции в любой целочисленной точке . Если точку указать невозможно, то принимают . Пусть в результате итераций метода получили список из задач: и существует . Алгоритм метода ветвей и границ содержит этапы: 1 Этап. Выбирается из списка задач линейного программирования задача для решения, . Задача решается. 2 Этап. Если задача имеет решение , то переходим к этапу 3. Иначе – исключаем задачу из списка, = . Переход к этапу 1. При делаем вывод, что исходная задача не имеет решения и процесс решения заканчивается. 3 Этап. Если , то переходим к этапу 4. В противном случае задача исключается из списка. Переход к этапу 1.
4 Этап. Если все компоненты вектора удовлетворяют условию целочисленности, то переходим к этапу 5. В противном случае задача из списка исключается. План запоминается, . Переход к этапу 1. При вектор является решением исходной задачи и процесс решения заканчивается. 5 Этап Задача из списка исключается. В список включаются две новые задачи линейного программирования – задача и задача , = . Переход к этапу 1. Процесс разбиения задачи на две новые задачи линейного программирования осуществляется следующим образом. Пусть - дробная компонента в полученном оптимальном плане и целая часть. Тогда задача имеет вид: при ограничениях (1.5) Тогда задача имеет вид: при ограничениях (1.6) Процесс решения продолжается пока не будут решены все задачи линейного программирования из списка. Решение задачи будет на последней итерации [4].
Практическая работа №1 «Метод отсечения в моделировании систем»
Цель: получить теоретические знания и практические навыки в моделировании систем методами линейного программирования. Используемые приемы и технологии: линейное программирование, целочисленное программирование. Ключевые термины: математическая модель, симплекс-метод, метод отсекающих плоскостей, метод ветвей и границ. Постановка задачи: Разработайте математическую модель выбора оптимального проекта информационной системы организации. Разработайте программу, формализующую математическую модель выбора оптимального проекта информационной системы организации на языке С++.
Варианты заданий
Разработайте программу на языке С++, формализующую алгоритм решения оптимизационной задачи симплекс-методом
Вариант 1 Вариант 2 Вариант 3
при ограничениях при ограничениях при ограничениях
Вариант 4 Вариант 5 Вариант 6
при ограничениях при ограничениях при ограничениях
Вариант 7 Вариант 8 Вариант 9
при ограничениях при ограничениях при ограничениях
Вариант 10 Вариант 11 Вариант 12
при ограничениях при ограничениях при ограничениях
Методические указания
1 Выбрать вариант задания по последней цифре номера зачетной книжки. 2 Разработать математическую модель выбора оптимального проекта информационной системы. 3 Разработать алгоритм решения задачи. 4 Разработать программу выбора оптимального проекта информационной системы. 5 Оформить отчет по практической работе. Содержание отчета должно включать: Титульный лист 1 Постановка задачи. 2 Описание алгоритма решения задачи 3 Математическая модель выбора проекта информационной системы организации. 4 Диаграмма классов. 5 Оптимальное решение математической модели информационной системы.
1.3. 3 Контрольные вопросы
1 Что называется математической моделью? 2 Что называется оптимальным решением? 3 Что называется допустимым решением? 4 Какие этапы метода Гаусса-Жордана? 5 Какой алгоритм метода обыкновенное Жорданово исключение? 6 Какой алгоритм метода модифицированное Жорданово исключение? 7 Какие этапы алгоритма метода отсекающих плоскостей? 8 Какие этапы алгоритма метода ветвей и границ? 9 Как формулируется условие оптимальности? 10 Как формулируется условие допустимости?
|
||||||
Последнее изменение этой страницы: 2021-07-19; просмотров: 137; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.17.6.75 (0.026 с.) |