close

Вход

Забыли?

вход по аккаунту

?

Лекции ИСО

код для вставкиСкачать
оссийский государственный университет им. . анта атематический факультет
афедра компьютерного моделирования и информационных систем
Ц
Александр Васильевич Колесников
доктор технический наук, профессор
Калининград, 2010
редыстория исследования операций
1) Работы Ланчестера по моделированию боевых операций (1916 г.). 2
)
Работы
по
теории
массового
обслуживания
Эрланга,
нашедшие
практическую
реализацию
в
начале
двадцатого
столетия
в
Копенгагене
.
3
)
Исследования
Левинсона
в
области
розничной
торговли
в
начале
20
-
х
годов
.
стория развития методов и средств исследования операций
арождение
исследования
операций
связано
концепцией
индустриального
общества
и
с
разработкой
английскими
военно
-
воздушными
силами
систем
управления
(
1936
±
1937
гг
.
)
:
1
)
системы
обнаружения
и
слежения
за
одиночным
атакующим
самолетом
противника
(«Бодси»)
и
2
)
системы
сопровождения
и
наведения
взаимодействующих
истребителей
военно
-
воздушных
сил
обороны
(«Биггин
Хилл»)
.
Цель
проектов
-
обеспечить
согласованные
действий
участников
боевых
операций
:
людей
и
технических
средств
.
Выработка
оценок
эффективности
разрабатываемых
операций
получила
название
«операционное
исследование»
.
В 1942 г. работы по исследованию военных операций начались в США.
стория развития методов и средств исследования операций
В
1945
±
1950
гг
.
работы
по
исследованию
операций
в
военной
области
в
Англии,
США
и
Канаде
были
продолжены
еще
в
более
широком
масштабе
.
Центр
исследований
сместился
в
авиационную
промышленность
.
В
1965
±
1975
гг
.
наблюдалось
расширение
сферы
применения
исследования
операций
в
новых
направлениях
:
охране
общественного
порядка,
транспорте,
управлении
ростом
и
развитием
городов,
жилищном
строительстве,
здравоохранении,
образовании
и
социальных
услугах
.
стория развития методов и средств исследования операций
В
1965
г
.
американский
социолог
и
политолог
Д
.
Белл
выдвинул
концепцию
постиндустриального
общества
.
Он
обосновал
переход
общественных
отношений
от
индустриального
общества
(рационального
использования
ресурсов)
к
постиндустриальному
(рационального
использования
информации
и
знаний)
.
К
1975
г
.
стали
актуальны
профессиональные
знания
и
опыт
специалистов,
решающих
широкий
круг
практических,
творческих,
интеллектуальных
задач
.
В
1955
г
.
появился
термин
«скусственный
интеллект»
.
В
1969
г
.
появилась
первая
экспертная
система
(система,
использующая
профессиональные
знания
специалиста
для
рассуждений
над
решением
задачи)
.
С
1980
г
.
методы
искусственного
интеллекта
превратились
в
индустрию
.
стория развития методов и средств исследования операций
В
эпоху
разработки
компьютерной
техники
возник
системный
анализ
(А
.
А
.
Богданов,
Л
.
Берталанфи,
Н
.
Винер,
Н
.
Н
.
Моисеев,
Э
.
Эшби
и
др
.
)
.
истемный
анализ
²
это
совокупность
методов,
основанных
на
использовании
ЭВМ
и
ориентированных
на
исследование
сложных
систем
.
Результат
системных
исследований
-
выбор
альтернативы
:
плана
развития
региона,
параметров
конструкции
и
т
.
д
.
К
1979
г
.
сложилась
область
исследований,
вовлекающая
понятия
и
методы
математики,
статистики,
экономики,
управления
и
психологии
±
теория
принятия
решений
.
Начиная
с
1980
г
.
и
до
настоящего
времени
исследование
операций,
системный
анализ,
искусственный
интеллект
и
теория
принятия
решений
±
это
научные
дисциплины
«взявшие
на
себя
ответственность»
за
исследования
того,
как
человек
и
коллективы
людей
вырабатывают
и
принимают
решения
.
стория развития методов и средств исследования операций
аучная сущность исследования операций
История
ИСО
неразрывно
связана
с
разработкой
математических
методов
и
моделей
.
Совокупность
математических
методов
исследования
операций
можно
разбить
на
две
группы
:
1
)
детерминированные
модели
:
линейное
программирование,
целочисленное
программирование,
теория
графов,
потоки
в
сетях,
геометрическое
программирование,
нелинейное
программирование,
теория
оптимального
управления
.
2
)
стохастические
модели
:
теория
массового
обслуживания,
теория
полезности,
теория
игр,
теория
поиска,
имитационное
моделирование
и
динамическое
программирование
.
стория развития методов и средств исследования операций
аучная сущность исследования операций
В
1939
г
.
«родилось»
линейное
программирование
.
Была
напечатана
брошюра
Леонида
Витальевича
Канторовича
«Математические
методы
организации
и
планирования
производства»
.
Однако
методы,
изложенные
Л
.
В
.
Канторовичем,
были
мало
пригодны
для
ручного
счета,
ЭВМ
еще
не
было
и
эта
работа
осталась
почти
не
замеченной
.
Л
.
В
.
Канторович,
академик
АН
СССР,
математик,
экономист,
лауреат
Нобелевской
премии
по
экономике
в
1975
г
.
В
1931
г
.
венгерский
математик
Б
.
Эгервари
рассмотрел
математическую
постановку
и
решил
задачу,
названную
«проблема
выбора»,
а
метод
решения
получил
название
«венгерского
метода»
.
стория развития методов и средств исследования операций
аучная сущность исследования операций
Концепции
Л
.
В
.
Канторовича
после
второй
мировой
войны
были
переоткрыты
на
западе
.
Американский
экономист
Т
.
Купманс
привлекал
внимание
математиков
к
задачам
нахождения
экстремумов
линейных
функций
на
многогранниках,
задаваемых
линейными
неравенствами
и
предложил
этот
раздел
математики
назвать
«Линейное
программирование»
.
Американский
математик
А
.
Данциг
в
1947
году
разработал
эффективный
метод
численного
решения
задач
линейного
программирования
.
Он
получил
название
симплекс
метода
.
Второе
рождение
линейное
программирование
получило
в
начале
пятидесятых
годов
с
появлением
ЭВМ
.
В
1975
году
академик
Л
.
В
.
Канторович
и
профессор
Т
.
Купманс
получили
Нобелевскую
премию
по
экономическим
наукам
за
«вклад
в
разработку
теории
и
оптимального
использования
ресурсов
в
экономике»
.
Тьяллинг
Чарльз
Купманс,
доктор
наук,
профессор,
американский
экономист
и
математик,
лауреат
Нобелевской
премии
по
экономике
в
1975
г
.
стория развития методов и средств исследования операций
аучная сущность исследования операций
С
развитием
линейного
программирования
большое
внимание
уделялось
задачам
нелинейного
программирования
,
в
которых
либо
целевая
функция,
либо
ограничения,
либо
то
и
другое
нелинейны
.
В
1951
г
была
опубликована
работа
Гарольда
Уильяма
Куна
(американский
математик,
специалист
по
теории
игр)
и
Уильяма
Альберта
Таккера
(американский
математик),
в
которой
приведены
необходимые
и
достаточные
условия
оптимальности
для
решения
задач
нелинейного
программирования
.
стория развития методов и средств исследования операций
аучная сущность исследования операций
Термин
динамическое
программирование
впервые
был
использован
в
1940
-
х
годах
Ричардом
Эрнстом
Беллманом
(американский
математик,
специалист
в
области
вычислительной
техники,
профессор)
для
описания
процесса
нахождения
решения
задачи,
где
ответ
на
одну
задачу
может
быть
получен
рекуррентно
только
после
решения
задачи,
«предшествующей»
ей
.
Первые
задачи
теории
массового
обслуживания
были
рассмотрены
сотрудником
Копенгагенской
телефонной
компании,
ученым
Аргеном
Эрлангом,
в
период
между
1908
и
1922
годами
.
Стояла
задача
упорядочить
работу
телефонной
станции
и
заранее
рассчитать
качество
обслуживания
потребителей
в
зависимости
от
числа
используемых
устройств
.
ичард еллман
Американский математик, один из ведущих специалистов в области математики и вычислительной техники, профессор
стория развития методов и средств исследования операций
аучная сущность исследования операций
етод
онте
-
арло
²
общее
название
группы
численных
методов,
основанных
на
получении
большого
числа
реализаций
стохастического
(случайного)
процесса,
который
формируется
таким
образом,
чтобы
его
вероятностные
характеристики
совпадали
с
аналогичными
величинами
решаемой
задачи
.
Используется
для
решения
задач
в
различных
областях
физики,
математики,
экономики,
оптимизации,
теории
управления
и
др
.
Станислав
Мартин
Улам,
польско
-
американский
математик,
автор
метода
Монте
-
Карло,
основной
разработчик
водородной
бомбы
Идея
метода
развита
С
.
Уламом
.
Он
предложил
поставить
«эксперимент»
большое
число
раз
и,
таким
образом,
подсчитав
число
удачных
исходов,
оценить
их
вероятность
.
Он
же
предложил
использовать
компьютеры
для
расчтов
методом
Монте
-
Карло
.
Годом
рождения
метода
-
1949
г
.
,
когда
вышла
статья
Метрополиса
и
Улама
«Метод
Монте
-
Карло»
.
Название
метода
происходит
от
названия
города
в
княжестве
Монако,
широко
известного
своими
казино
с
рулеткой
-
самым
известным
генератором
случайных
чисел
.
В
1950
-
х
годах
метод
использовался
для
расчтов
при
разработке
водородной
бомбы
.
стория развития методов и средств исследования операций
аучная сущность исследования операций
Наиболее
важные
модели
,
разработанные
с
применением
методов
исследования
операций
:
•
Задачи
учета,
прогнозирования
и
планирования
производства
;
•
Модели
финансовой
деятельности,
управления
экономикой,
экономического
анализа
инвестиций,
сбыта
и
рекламы
;
•
Модели
управления
трудовыми
ресурсами
;
•
Модели
вычислительных
и
информационных
систем
;
•
Модели
выбора,
планирования
и
управления
разработкой
проекта
;
•
Модели
управления
запасами
;
•
Модели
составления
календарных
планов
производства
и
последовательности
работ
;
•
Модели
замены,
ремонта
и
анализа
надежности
оборудования
;
•
Модели
размещения
и
загрузки
производственных
мощностей
;
стория развития методов и средств исследования операций
аучная сущность исследования операций
рименение
методов исследования операций: •
военные проблемы, •
работа государственных органов, •
городские системы, •
здравоохранение, •
системы образования, •
транспорт, •
коммунальное обслуживание, •
промышленное производство, •
технологические процессы. редмет и задачи исследования операций
Под
исследованием
операций
понимается
применение
математических
количественных
методов
для
обоснования
решений
во
всех
областях
целенаправленной
человеческой
деятельности
(Е
.
С
.
Вентцель,
профессор,
математик,
крупный
советский
специалист
в
теории
вероятностей,
исследовании
операций)
.
сследование
операций
представляет
собой
искусство
давать
плохие
ответы
на
практические
вопросы,
на
которые
даются
еще
худшие
ответы
другими
методами
(Т
.
Л
.
Саати,
США,
математик,
крупный
специалист
в
исследовании
операций
и
принятии
решений)
сследование
операций
±
1
)
применение
научного
метода,
2
)
комплексными
научными
коллективами,
3
)
для
решения
задач,
связанных
с
управлением
организационными
(человеко
-
машинными)
системами
с
целью
получения
решений,
которые
наилучшим
образом
отвечаю
целям
всей
организации
(Р
.
Акоф,
профессор,
США,
крупный
специалист
в
исследовании
операций
и
управлении,
М
.
Сасиени,
Англия,
специалистка
по
управлению
и
исследованию
операций)
.
Исследование
операций
±
англ
.
management
science,
decision
science,
operations
analysis,
quantitative
analysis,
mathematical
programming
.
редмет и задачи исследования операций
редмет
исследования
операций
-
системы
организационного
управления
или
организации,
которые
состоят
из
большого
числа
взаимодействующих
между
собой
подразделений
не
всегда
согласующихся
между
собой
и
могут
быть
противоположны
.
Цель
исследования
операций
-
количественное
обоснование
принимаемых
решений
по
управлению
.
адачи
исследования
операций
±
1
)
постановка
задачи,
2
)
построение
модели,
3
)
отыскание
решения,
4
)
проверка
модели
и
оценка
решения,
5
)
внедрение
решения
и
контроль
его
правильности
.
ринципы исследования операций
1
.
Системный
подход
к
анализу
поставленной
проблемы
.
Системный
анализ
является
основным
методологическим
принципом
исследования
операций,
который
состоит
в
том,
что
любая
задача,
какой
бы
частной
она
не
казалась,
рассматривается
с
точки
зрения
ее
влияния
на
критерий
функционирования
всей
системы
.
2
.
Для
исследования
операций
характерно,
что
при
решении
каждой
проблемы
возникают
все
новые
и
новые
задачи
.
Если
сначала
ставится
узкие
цели,
применение
операционных
методов
неэффективно
.
Наибольший
эффект
может
быть
достигнут
только
при
непрерывном
исследовании,
обеспечивающем
преемственность
в
переходе
от
одной
задачи
к
другой
.
3
.
Стремление
найти
оптимальное
решение
поставленной
задачи
.
Однако,
часто
такое
решение
оказывается
недостижимым
из
-
за
ограничений,
накладываемых
имеющимися
в
наличии
ресурсами
или
уровнем
современной
науки
.
Тогда
приходится
ограничиваться
поиском
достаточно
хорошего
или
субоптимального
решения
.
4
.
Операционные
исследования
проводятся
комплексно,
по
многим
направлениям
.
Для
проведения
такого
исследования
создается
операционная
группа
.
В
ее
состав
входят
специалисты
различных
областей
:
инженеры,
математики,
экономисты,
социологи,
психологи
.
итуация 1
итуация 2
итуация 3
ицо, принимающее решения
Морской
рыбный
порт
с
двумя
одинаковыми
причалами
и
одним
прибывшим
с
промысла
судном,
которому
нужно
место,
чтобы
разгрузиться,
погрузиться
и
вновь
уйти
в
море
.
На
какой
причал
поставить
судно?
В
любой
ли
ситуации
перед
ЛПР
возникает
задача
(англ
.
problem)
?
онятие задачи в исследовании операций
Если
состояние
порта
таково,
что
он
простаивает
(
ситуация
1
),
т
.
е
.
в
распоряжении
ЛПР
имеются
практически
неограниченные
ресурсы,
то
первое,
что
приходит
ему
на
ум
±
дать
судну
любой
из
двух
причалов
.
При
этом
ЛПР
имело
две
альтернативы
:
"поставить
судно
на
левый
причал"
и
"поставить
судна
на
правый
причал"
.
В
ситуации
2
не
так
все
очевидно,
как
может
показаться
на
первый
взгляд
.
Число
альтернатив
не
изменилось
.
Их
по
±
прежнему
две
:
"предоставить
судну
свободный
причал",
а
также
"перешвартовать
стоящее
у
причала
судно
на
другой
причал
и
предоставить
освободившееся
место
пришедшему
с
промысла"
.
Конечно,
в
этом
случае
ЛПР
должно
отдавать
себе
отчет
в
том,
чего
оно
хочет,
т
.
е
.
какова
его
цель?
Если
цель
±
быстрее
начать
выгрузку
грузов
с
промысла,
то
состояние
-
результат,
которого
можно
достичь
при
реализации
первой
альтернативы
более
предпочтительно,
т
.
е
.
в
этом
случае
цель
будет
достигнута
вероятнее,
чем
при
реализации
второй
альтернативы
(хотя,
если
ввести
тип
судна,
расстояние
от
судна,
двигающегося
в
порт,
количество
груза
на
его
борту
и
то,
что
судно
у
причала
простаивает,
то
можно
склониться
и
ко
второму
варианту)
.
нализ ситуаций
Впервые
ЛПР
задумается
над
ситуацией
3
.
Число
возможных
альтернатив
увеличилось
:
"не
прерывать
обработку
ни
одного
из
двух
судов,
а
поставить
вновь
пришедшее
вторым
бортом
к
левому
судну",
"не
прерывать
обработку
ни
одного
из
двух
судов,
а
поставить
вновь
пришедшее
вторым
бортом
к
правому
судну",
"прервать
обработку
левого
судна,
поставить
его
вторым
бортом
к
правому,
поставить
вновь
прибывшее
на
освободившийся
причал"
и
т
.
п
.
Если
учесть
целеполагание
и
оценки
достижения
цели
,
то
можно
сказать,
что
возникла
задача
.
ринято
считать
[коф,
асиени,
1971
],
что
задача
существует
тогда,
когда
:
1
)
существует
субъект,
перед
которым
возникает
задача
;
2
)
в
распоряжении
субъекта
имеется
минимум
две
альтернативы,
т
.
е
.
есть
выбор
;
3
)
существует
цель,
которую
он
стремится
достичь
;
4
)
существуют
оценки,
по
которым
можно
сравнить
альтернативы
и
судить
о
достижении
цели
.
Однако
для
ЛПР
существующая
задача
становится
предметом
решения
только
тогда,
когда
оно
не
знает
,
какая
альтернатива
наилучшая
и
именно
это
ему
и
требуется
определить
.
нализ ситуаций
птимизационные задачи в науке и технике и принятие решений
ве задачи исследования операций
1
.
лан
снабжения
предприятий
.
Есть
предприятия,
потребляющих
известное
сырье,
и
сырьевые
базы,
которые
могут
поставлять
это
сырье
предприятиям
.
Базы
связаны
с
предприятиями
путями
сообщения
:
ж
/
д,
водными,
автомобильными,
воздушными
со
своими
тарифами
.
Требуется
разработать
такой
план
снабжения
предприятий
сырьем
(с
какой
базы,
в
каком
количестве
и
какое
сырье
доставляется),
чтобы
потребности
в
сырье
были
обеспечены
при
минимальных
расходах
на
перевозки
.
2
.
остройка
участка
магистрали
.
Сооружается
участок
ж
/
д
магистрали
.
В
распоряжении
ЛПР
²
определенное
количество
средств
:
людей,
строительных
машин,
ремонтных
мастерских,
грузовых
автомобилей
и
т
.
д
.
Требуется
спланировать
строительство
(назначить
очередность
работ,
распределить
машины
и
людей
по
участкам
пути,
обеспечить
ремонтные
работы)
так,
чтобы
оно
было
завершено
в
минимально
возможный
срок
.
Цель
-
желаемое состояние объекта в будущем.
Целеполагание
-
осмысление
своей
деятельности
ЛПР
с
точки
зрения
формирования
(постановки)
целей
и
их
реализации
(достижения)
наиболее
экономичными
(рентабельными)
средствами
.
льтернатива
(решение)
-
определенный
выбор
параметров
зависящих
от
ЛПР
.
Решения
могут
быть
удачными
и
неудачными,
разумными
и
неразумными
.
ритерий
(гр
.
kriterion
-
признак
для
суждения)
²
количественный
признак,
основание,
мерило
оценки
альтернатив
(решений)
.
птимальные
решения
-
имеющие,
наивысшую
±
максимальную
(
max)
или
наинизшую
±
минимальную
(
min)
оценку
по
критерию
.
ациональные
решения
-
решения,
по
тем
или
другим
признакам
(чаще
всего
качественным,
не
выраженным
количественно)
предпочтительные
перед
другими
.
перация
-
мероприятие
(система
действий),
объединенное
единым
замыслом
и
направленное
к
достижению
цели
.
Операция
всегда
управляемое
мероприятие,
т
.
е
.
от
ЛПР
зависит,
каким
способом
выбрать
некоторые
параметры,
характеризующие
ее
организацию
.
сновные понятия исследования операций
Элементы
решения
-
параметры,
совокупность
которых
образует
решение
.
В
качестве
элементов
решения
могут
фигурировать
числа,
векторы,
функции
.
Например,
если
составляется
план
перевозок
однородных
грузов
из
пунктов
отправления
в
пункты
назначения
,
то
элементами
решения
будут
числа
,
показывающие,
какое
количество
груза
будет
отправлено
из
i
-
го
пункта
отправления
в
j
-
й
пункт
назначения
.
Совокупность
чисел
и
образует
решение
.
В
простейших
задачах
исследования
операций
количество
элементов
решения
может
быть
сравнительно
невелико
.
Но
в
большинстве
задач,
имеющих
практическое
значение,
число
элементов
решения
очень
велико
.
сновные понятия исследования операций
граничения
(дисциплинирующие
условия)
±
пределы
в
которых
ЛПР
может
распоряжаться
элементами
решения
.
Пределы
зафиксированы
с
самого
начала
и
нарушены
быть
не
могут
(например,
грузоподъемность
машины
;
размер
планового
задания
;
весовые
характеристики
оборудования
и
т
.
п
.
)
.
В
частности,
к
таким
условиям
относятся
средства
(материальные,
технические,
людские),
которыми
ЛПР
вправе
распоряжаться,
и
иные
ограничения,
налагаемые
на
решение
.
бласть
допустимых
решений
-
множество
возможных
с
точки
зрения
ограничений
элементов
решения
.
Целевая
функция
±
отображение
элементов
решения
на
количественные
оценки
показателя
эффективности
(критерия),
показывающее
наилучшее
поведение
(переход
из
состояния
в
состояние)
объекта
при
достижении
цели
.
Выбирая
решение,
ЛПР,
предпочтет
такое,
которое
обращает
показатель
эффективности
в
максимум
(или
же
в
минимум)
.
Целевая
функция
студента?
Сколько
экзаменов
сдает
студент
за
четыре
года
обучения?
Ответ
:
4
экзамена
в
сессию,
две
сессии
в
год
±
итого
32
экзамена
.
Обозначим
-
экзаменационную
оценку
.
Тогда
целевая
функция
студента
имеет
вид
:
-
сновные понятия исследования операций
1
.
лан
снабжения
предприятий
.
Задача
операции
-
обеспечить
снабжение
сырьем
при
минимальных
расходах
на
перевозки
.
Показатель
эффективности
R
²
суммарные
расходы
на
перевозки
сырья
за
единицу
времени,
например,
месяц: 2
.
остройка
участка
магистрали
.
Требуется
так
спланировать
строительство,
чтобы
закончить
его
как
можно
скорее
.
Естественным
показателем
эффективности
было
бы
время
завершения
стройки,
если
бы
оно
не
было
связано
со
случайными
факторами
(отказы
техники,
задержки
в
выполнении
отдельных
работ)
.
Поэтому
в
качестве
показателя
эффективности
можно
выбрать
среднее
ожидаемое
время
Т
окончания
стройки
:
ве задачи исследования операций Целевые функции
ринятие решений
ринятие
решений
±
особый
вид
целенаправленной
деятельности,
заключающийся
в
выборе
одной
из
имеющихся
альтернатив
.
Элементы процесса принятия решений
:
1)
Задача (проблема), подлежащая разрешению;
2)
Принимающий решение ()решающий) элемент ±
человек или коллективный орган, который (при помощи технических средств) решает задачу;
3)
Одна или несколько целей в соответствии с которыми осуществляется выбор;
4)
Несколько (множество) альтернатив, среди которых производится выбор.
одель процесса принятия решений .. иханского и .. аумова
Этап 1. ризнание необходимости решения
Восприятие и признание проблемы
Интерпретация и формулирование проблемы
Определение критериев успешного решения
Этап 2. ыработка решения
Разработка альтернатив
Оценка альтернатив
Выбор альтернативы
Этап 3. ыполнение решения
Организация выполнения решения
Анализ и контроль выполнения решения
Обратная связь и корректировка
одель коллективного принятия решений .. амсоновой и ..фимова
етоды иагностика задач
Постановка и формулировка задачи
Анализ задачи
Метод «бритва Оккама» Диаграмма сродства
Древовидная диаграмма
Диаграмма
«рыбьи кости»
Диаграмма шести слов
Диаграмма связей
Формулировка ограничений, критериев и выявление альтернатив
Сбор данных
Интерпретация данных
Поиск решения
Контрольные листки
Диаграммы Парето Гистограммы
Анализ силового поля
Модифицированный метод Дельфи
Обмен мнениями
Коллажи и фантазии
Матричная диаграмма
нализ эффективности решений и окончательный выбор
резентация результатов
еализация решения
ониторинг и оценка результатов
Логическая диаграмма
Стрелочная диаграмма
ндивидуальные решения
Автор
графика
±
Михай
Чиксентмихайи,
профессор
психологии
Чикагского
университета
.
Люди
часто
используют
метафору
потока,
чтобы
описать
ощущение
легкости
при
выполнении
какого
-
то
дела
(например,
принимают
решения)
.
Основное
условие
для
попадания
в
это
состояние
±
баланс
сложности
и
навыков
в
конкретной
задаче
.
Если
вызов,
который
предъявляет
вам
ситуация,
слишком
велик
±
ЛПР
начинает
нервничать
.
Если
он
слишком
мал
±
ЛПР
не
интересно
.
Лучшие
решения
принимаются
³в
потоке´,
когда
не
скучно,
и
не
страшно
.
сихология принятия решений
Первую
просили
принимать
решение
немедленно,
не
думая
.
Второй
группе
дали
время
на
размышления
.
Третьей
группе
дали
время,
но
при
этом
вс
это
время
отвлекали,
не
давая
размышлять
над
задачей
.
Считалось,
что
это
позволит
испытуемым
сформировать
честное
бессознательное
решение
.
Вот
результаты
.
Те,
кто
принимал
решение
спонтанно,
оказались
правы
в
36
%
случаев
±
это
больше,
чем
случайное
совпадение
(
25
%
)
.
Те,
кто
думали,
показали
заметно
лучшие
результаты
.
Но
еще
лучшие
результаты
показали
те,
кто
НЕ
ДУМАЛ!
Вы
переехали
в
другой
город
и
нужно
искать
жилье
.
Риэлтер
предлагает
четыре
квартиры
.
Они
разные
по
параметрам
и
нужно
принять
решение
.
п
ейкстергюйс
из
университета
Амстердама
поставил
опыт
.
Испытуемые
были
разделены
на
три
группы
.
У
задачи
был
правильный
ответ
±
критерии
выбора
были
известны
и
одна
из
квартир
была
лучше
других
.
сихология принятия решений
Закон
Йеркса
-
Додсона
(Yerkes
-
Dodson)
-
психологический
закон,
сформулирован
1908
году,
который
показывает
успешность
в
зависимости
от
уровня
мотивации
на
задачах
различной
сложности
.
Он
был
многократно
проверен
:
на
животных
и
людях
.
Результаты
всегда
одни
и
те
же
:
для
каждой
задачи
существует
оптимум
мотивации
и
превышение
этого
оптимума
МЕШАЕТ,
а
не
помогает
.
Лишняя
мотивация
мешает
.
Причем
не
только
отрицательная
(наказание),
но
и
положительная!
Притча
о
наказании
наградой
:
³Каждый
день
одного
пожилого
человека
оскорбляла
ватага
десятилетних
мальчишек,
которые
проходили
мимо
его
дома
по
дороге
в
школу
.
Однажды
он
вышел
к
ним
и
сказал
:
³Завтра
за
каждое
ругательство
в
мой
адрес
я
дам
вам
доллар!´
.
Мальчишки
пришли
назавтра
и
он
выполнил
свое
обещание
.
Расплатившись,
он
сказал
:
³Приходите
завтра
еще,
я
буду
давать
вам
по
25
центов´
.
Завтра
повторилась
та
же
история
.
На
следующий
день
он
пообещал
им
по
центу
.
³По
центу?´
±
возмутились
мальчишки
.
³Мы
не
будем
заниматься
этим
за
цент!´
Больше
они
никогда
не
приходили
.
Лишняя
мотивация
мешает
.
сихология принятия решений
оллективные решения
Системы поддержки принятия решений
Ситуационные комнаты Ситуационные центры
Формальная модель задачи принятия решений
Задача принятия решений может быть представлена семеркой:
где
t
-
постановка
задачи
(например,
выбрать
одну
наилучшую
в
некотором
смысле
альтернативу
или
упорядочить
все
множество
альтернатив)
;
X
-
множество
допустимых
альтернатив
(решений,
вариантов,
действий)
;
R
-
множество
критериев
оценки
степени
достижимости
поставленных
целей
;
A
±
множество
шкал
измерения
по
критериям
(шкалы
наименований,
порядковые,
интервальные,
отношений)
;
F
±
отображение
множества
допустимых
альтернатив
в
множество
критериальных
оценок
их
последствий
(исходов)
;
G
±
система
предпочтений
решающего
элемента
;
D
±
решающее
правило,
отражающее
систему
предпочтений
.
инейное программирование
адачи линейного программирования
остановка задачи линейного программирования
инейное программирование
±
метод оптимизации моделей, в которых целевые функции и ограничения строго линейны.
ример
.
Пусть
есть
компания,
которая
производит
краску
для
внутренних
и
наружных
работ
из
двух
видов
сырья
:
M
1
и
M
2
.
Компания
ограничила
ежедневное
производство
краски
для
внутренних
работ
до
2
т,
так
как
нет
спроса
и
приняла
решение
:
производство
краски
для
внутренних
работ
не
должно
превышать
производство
краски
для
наружных
работ
более
чем
на
одну
тонну
.
Требуется
найти
оптимальное
соотношение
между
видами
выпускаемой
продукции
для
максимизации
ежедневного
дохода
.
Расход сырья на тонну краски для наружных работ, т
Расход сырья на тонну краски для внутренних работ, т
Максимально возможный ежедневный расход сырья, т
Сырье М1
6
4
24
Сырье М2
1
2
6
Доход на тонну краски, тыс. руб.
5
4
инейное программирование
еометрический смысл задачи линейного программирования
Задача (модель) ЛП, как и любая задача ИСО, включает три основных элемента.
1.
Переменные, которые следует определить.
2.
Целевая функция, подлежащая оптимизации.
3.
Ограничения, которым должны удовлетворять переменные.
Шаг 1. Определение переменных.
В нашем примере необходимо определить ежедневные объемы производства краски для внутренних и наружных работ. Обозначим эти объемы как переменные модели: -
ежедневный объем производства краски для наружных работ, т;
-
ежедневный объем производства краски для внутренних работ, т;
Шаг 2. Построение целевой функции.
Логично
предположить,
что
целевая
функция,
как
суммарный
ежедневный
доход,
должна
возрастать
при
увеличении
ежедневных
объемов
производства
красок
.
В соответствии с целями компании получаем задачу:
инейное программирование
еометрический смысл задачи линейного программирования
Шаг 3. Определение ограничений.
Ограничения должны учитывать возможности ежедневного потребления сырья и ограниченность спроса на готовую продукцию. Ограничения можно записать в виде:
Из таблицы имеем:
инейное программирование
еометрический смысл задачи линейного программирования
Поскольку
ежедневный
расход
сырья
М
1
и
М
2
ограничен
соответственно
24
и
6
тоннами,
получим
следующие
ограничения
:
Есть
еще
два
ограничения
по
спросу
на
продукцию
.
Первое
:
ежедневный
объем
производства
краски
для
внутренних
работ
не
должен
превышать
ежедневный
объем
производства
краски
для
наружных
работ
:
Второе ограничение: максимальный ежедневный обюъем производства краски для внутренних работ не должен превышать 2 т :
Еще
одно
ограничение
:
переменные
и
должны
быть
неотрицательными
(условие
неотрицательности
переменных)
:
инейное программирование
еометрический смысл задачи линейного программирования
Окончательно задача будет записана следующим образом:
При выполнении ограничений:
Любое
решение,
удовлетворяющее
ограничениям
модели
называется
допустимым
.
Например,
решение
и
будет
допустимым,
так
как
не
нарушает
ни
одного
ограничения
.
Значение
целевой
функции
при
этом
решении
будет
равно
z
=
5
х
3
+
4
х
1
=
19
(тыс
.
руб
.
)
инейное программирование
еометрический смысл задачи линейного программирования
оиск оптимального решения
Как найти оптимальное допустимое решение
, доставляющее максимум целевой функции?
Выводы:
1)
Задача имеем много (бесконечно много) допустимых решений.
2)
Нельзя применять простой перебор, как метод поиска оптимальных допустимых решений.
3)
Необходима эффективная поисковая процедура
рафический способ решения задач линейного программирования
Графический способ состоит из двух этапов:
1)
Построение области допустимых решений, удовлетворяющих всем ограничениям.
2)
Поиск оптимального решения среди всех точек области допустимых решений. 1
1
2
3
4
5
6
2
3
4
5
6
A
F
E
D
C
B
1
5
4
2
3
6
Область допустимых решений
1
2
3
4
5
6
бласть допустимых решений
рафический способ решения задач линейного программирования
лучай максимизации целевой функции
остроение области допустимых решений
Шаг 1. Проведем оси: на оси абсцисс будем указывать значения , а на оси ординат Шаг 2. Отобразим графически ограничения Эти два ограничения показывают, что область допустимых решений (ОДР) будет лежать в первом квадранте. Шаг 3. Отобразим графически остальные ограничения. Для этого заменим неравенства равенствами, получим уравнения прямых и построим по этим уравнениям прямые.
Шаг
4
.
Рассматриваем
как
графически
интерпретируются
неравенства
.
Каждое
из
них
делит
плоскость
(
)
на
две
полуплоскости,
которые
располагаются
по
обе
стороны
от
прямой
.
Точки,
расположенные
по
одну
сторону
от
прямой
±
удовлетворяют
неравенству,
а
по
другую
сторону
±
нет
.
Шаг
6
.
Проверка
на
тестовой
точке
.
Тестовой
точкой
для
проверки
того,
точки
какой
полуплоскости
удовлетворяют
неравенству,
а
какой
нет
является
точка
(
0
,
0
)
.
Подстановка
координат
этой
точки
в
неравенство
и
проверка
удовлетворяет
или
нет
эта
точка
неравенству
однозначно
идентифицирует
полуплоскость
.
Графически
полуплоскости
обозначаются
стрелочками,
привязанными
к
окружностям
.
Если
прямая
проходит
через
точку
(
0
,
0
),
то
в
качестве
тестовой
можно
взять
и
другую
точку
.
Оптимум:
Максимизировать
z = 10
z = 15
z = 21
1
2
рафический способ решения задач линейного программирования
лучай максимизации целевой функции
оиск оптимального допустимого решения
рафический способ решения задач линейного программирования
лучай максимизации целевой функции
оиск оптимального допустимого решения
Шаг
1
.
Определение
направления
возрастания
целевой
функции
.
Для
этого
приравняем
z
к
нескольким
возрастающим
значениям,
например,
10
и
15
.
Подставляем
эти
значения
вместо
z
ы
выражение
целевой
функции,
получаем
два
уравнения
прямых
и
строим
по
этим
уравнениям
графики
(пунктир)
.
Проводим
стрелку
(красный
цвет)
указывающую
направление
возрастания
значений
целевой
функции
.
Шаг
2
.
Перемещение
прямой,
соответствующей
целевой
функции,
перпендикулярно
направлению
возрастания
значений
целевой
функции
в
сторону
стрелки
.
Перемещение
проводится
до
тех
пор,
пока
график
целевой
функции
будет
пересекать
ОДР
.
Шаг
3
.
Определение
оптимума
.
Точка
пересечения
ОДР
и
прямой,
соответствующей
максимально
возможному
значению
целевой
функции,
и
будет
точкой
оптимума
.
рафический способ решения задач линейного программирования
лучай максимизации целевой функции
оиск оптимального допустимого решения
Оптимальное
решение
соответствует
точке
С
.
Эта
точка
±
место
пересечения
прямых
(
1
)
и
(
2
),
поэтому
ее
координаты
находятся
как
решение
системы
уравнений,
задающих
эти
прямые
:
Решением
этой
системы
будет
.
При
этом
значение
целевой
функции
равно
Полученное
решение
означает,
что
для
компании
оптимальным
выбором
будет
ежедневное
производство
23
т
краски
для
наружных
работ
и
1
,
5
т
±
для
внутренних
работ
с
ежедневным
доходом
в
21000
руб
.
инейное программирование
адачи линейного программирования
ахождение минимума целевой функции
ример
.
Компания
ежедневно
производит
800
кг
добавки
±
смеси
кукурузной
и
соевой
муки
.
Состав
добавки
дан
в
таблице
.
Диетологи
требуют,
чтобы
в
добавке
было
не
менее
30
%
белка
и
не
более
5
%
клетчатки
.
Компания
хочет
определить
рецептуру
смеси
минимально
стоимости
с
учетом
требований
диетологов
.
Мука
Белок
(кг на кг муки)
Клетчатка
(кг на кг муки)
Стоимость
(руб
/
кг)
Кукурузная
0,09
0,02
0,30
Соевая
0,6
0,06
0,90
адачи линейного программирования
ахождение минимума целевой функции
пределяем
переменные
.
Поскольку
пищевая
добавка
состоит
только
из
кукурузной
муки,
определим
следующие
переменные
:
-
количество кукурузной муки, используемой в дневном производстве добавки, кг.; -
количество
соевой
муки,
используемой
в
дневном
производстве
добавки,
кг
.;
пределяем
целевую
функцию
.
Целевая
функция
равна
общей
стоимости
пищевой
добавки,
производимой
за
один
день,
и
должна
быть
минимальной
:
адачи линейного программирования
ахождение минимума целевой функции
ведем
ограничения
.
Рассмотрим
количество
белка
в
пищевой
добавке
.
Общее
количество
белка
в
смеси,
состоящей
из
кг
.
кукурузной
муки
и
соевой
муки,
равно
(кг
.
)
Это
количество
должно
составлять
не
менее
30
%
от
общего
объема
смеси
.
Отсюда
получаем
следующее
неравенство
:
Аналогично строится ограничение для клетчатки:
Далее нужно переменные из правых частей неравенств перенести в левые части.
ахождение минимума целевой функции
При выполнении ограничений:
Окончательно модель
примет следующий вид:
500
1000
1500
1
2
3
4
5
6
500
1000
1500
Оптимум:
1
2
3
Минимизировать
Область допустимых решений
бласть допустимых решений
рафический анализ чувствительности
Модель
ЛП
±
«моментальный
снимок»
реальной
ситуации
.
При
этом
параметры
модели
:
коэффициенты
целевой
функции
и
неравенств
ограничений
предполагаются
неизменными
.
Изучение
влияния
изменения
параметров
модели
на
получение
оптимального
решения
называется
анализом
чувствительности
.
Рассмотрим
два
случая
:
1)
Изменение
коэффициентов
переменных
в
целевой
функции
;
2)
Изменение
значений
констант
в
правых
частях
уравнений
ограничений
.
рафический анализ чувствительности
зменение коэффициентов переменных в целевой функции
1
1
2
3
2
3
4
5
A
F
E
D
C
B
Текущая оптимальная точка
Интервал оптимальности
рафический анализ чувствительности
зменение коэффициентов переменных в целевой функции
Общий вид целевой функции задачи ЛП с двумя переменными:
Изменение
значений
коэффициентов
и
приводит
к
изменениям
угла
наклона
прямой
z
.
Если
изменить
угол
наклона,
то
может
и
измениться
оптимальное
решение
.
Оно
будет
в
другой
«угловой»
точке
ОДР
.
Очевидно,
что
существуют
интервалы
изменения
и
при
которых
оптимальное
решение
не
изменится
.
Анализ
чувствительности
дает
такую
информацию
.
В
ходе
анализа
чувствительности
определяется
интервал
оптимальности
отношения
.
Если
значения
этих
дробей
не
выходят
за
пределы
интервала
оптимальности,
то
оптимальное
решение
в
данной
модели
сохраняются
неизменным
.
рафический анализ чувствительности
зменение коэффициентов переменных в целевой функции
В
нашем
примере
целевая
функция
достигает
максимума
в
угловой
точке
С
.
При
изменение
коэффициентов
точка
С
остается
точкой
оптимального
решения,
пока
угол
наклона
прямой
z
будет
лежать
между
углами
наклона
двух
прямых,
пересечением
которых
является
точка
С
.
Это
прямые
Алгебраически это можно записать следующим образом:
или
Неравенство означает, что прямая соответствующая целевой функции не может быть горизонтальной. Неравенство означает, что прямая соответствующая целевой функции не может быть вертикальной. рафический анализ чувствительности
зменение коэффициентов переменных в целевой функции
Используем полученные неравенства для определения интервала оптимальности. Зафиксируем . Пусть тогда: Зафиксируем . Пусть тогда: рафический анализ чувствительности
зменение констант в правых частях уравнений ограничений
1
1
2
3
2
3
4
5
A
F
E
D
C
B
Текущая оптимальная точка
Интервал осуществимости для материала М
1
6
М
1=20
М
1=24
М
1=36
G
рафический анализ чувствительности
зменение
значений
констант
в
правых
частях
уравнений
ограничений
В нашем примере оптимальное решение достигается в угловой точке С
, как точке пересечения прямых, соответствующих ограничениям на ресурсы М
1 и М
2.
При
изменении
уровня
доступности
ресурса
М
1
,
т
.
е
увеличение
или
уменьшение
текущего
уровня
равного
24
т
.
,
точка
С
оптимального
решения
«плывет»
вдоль
отрезка
DG
.
Если
точка
С
выйдет
из
этого
отрезка,
то
невозможно
будет
реализовать
оптимальное
решение
.
Тогда
конечные
точки
D
=
(
2
,
2
)
и
G
=
(
6
,
0
)
отрезка
DG
определяют
интервал
осуществимости
для
ресурса
М
1
.
Количество сырья, соответствующего точке D
= (2,2) равно:
Количество сырья, соответствующего точке G
= (6,0)
равно:
Тогда интервал осуществимости для сырья М
1 равен:
рафический анализ чувствительности
зменение
значений
констант
в
правых
частях
уравнений
ограничений
Определим
М
1
как
М
1
=
24
+
,
где
-
отклонение
количества
материала
М
1
от
текущего
значения
в
24
т
.
Тогда
имеем
:
Это означает, что текущий уровень ресурса М
1может быть уменьшен не более чем на 4 т. и увеличен не более чем на 12 т. В этом случае гарантируется, что оптимальное решение будет достигаться в точке С
. рафический анализ чувствительности
зменение констант в правых частях уравнений ограничений
1
1
2
3
2
3
4
5
A
F
E
D
C
B
Текущая оптимальная точка
Интервал осуществимости для материала М
2
6
М
2 =
4
М
2 =
6
М
2
=
6
G
H
Стоимость ресурса
i
равна:
Изменение значения целевой функции, соответствующего интервалу осуществимости, деленное на значение интервала осуществимости
рафический анализ чувствительности
зменение
значений
констант
в
правых
частях
уравнений
ограничений
Интервал
осуществимости
для
М
2
определяется
конечными
точками
отрезка
BH
,
где
B
=
(
4
,
0
)
и
H
=
(
8
/
3
,
2
)
.
Количество сырья, соответствующего точке B
= (4, 0) равно:
Количество сырья, соответствующего точке H
= (8/3, 2)
равно:
Тогда интервал осуществимости для сырья М
2
равен:
имплекс
-
метод решения задач линейного
программирования
Графический
способ
решения
задач
ЛП
показал,
что
оптимальное
решение
всегда
находится
в
угловой
точке
ОДР
.
В
математике
она
называется
крайней
точкой
множества
.
Это
явление
±
ключевая
идея
алгебраического
симплекс
-
метода
для
решения
задач
ЛП
.
Этот
метод
ориентирован
на
компьютерную
обработку
информации
.
Применение СМ требует преобразования зада ЛП к стандартной форме.
тандартная
форма
задач
линейного
программирования
Чтобы
перейти
к
стандартной
форме
задач
ЛП
необходимо
выполнить
следующие
преобразования
:
1)
Все ограничения, включая ограничения неотрицательности переменных преобразовать в равенства с неотрицательной правой частью.
2)
Все переменные сделать неотрицательными.
реобразование неравенств в равенства
Неравенства
любого
типа
(со
знаками
)
можно
преобразовать
в
равенства
добавлением
в
левую
часть
дополнительных
переменных
.
Те
переменные
которые
добавляются
в
неравенства
называются
остаточным
и,
а
в
неравенства
-
избыточными
.
реобразование неравенств в равенства
статочная
(неотрицательная)
переменная
.
Она
вводится
в
левую
часть
неравенств
.
Рассмотрим
задачу
максимизации
на
примере
производства
красок
.
Ограничение
на
сырье
М
1
имело
вид
:
Введем
остаточную
переменную
,
которая
показывает
остаток
(неиспользованное
количество)
сырья
М
1
.
Тогда
ограничение
преобразуется
в
равенство
:
збыточная
(неотрицательную)
переменная
.
Она
вводится
в
левую
часть
неравенств
.
Эти
неравенства
устанавливают
нижнюю
границу
чего
-
либо
.
Избыточная
переменная
определяет
превышение
значения
левой
части
неравенства
над
этой
границей
.
Рассмотрим
задачу
минимизации
на
примере
производства
добавки
.
Неравенство
показывает,
что
суточное
производство
добавки
не
должно
быть
меньше
800
кг
.
Введем
избыточную
переменную
.
Тогда
ограничение
преобразуется
в
равенство
:
реобразование неравенств в равенства
реобразование правой части к неотрицательному виду
Эквивалентно равенству:
Умножим
обе
части
это
равенства
на
-
1
,
получим
равенство
с
неотрицательной
правой
частью
:
Правую
часть
равенства
всегда
можно
сделать
неотрицательной,
умножив
обе
части
неравенства
на
-
1
.
Неравенство
типа
также
преобразуется
в
неравенство
типа
умножением
обеих
частей
неравенства
на
-
1
.
Например, неравенство
ример.
Рассмотрим следующую задачу ЛП с двумя переменными:
при выполнении ограничений:
1
1
2
3
4
2
3
4
5
A
F
E
D
C
B
ОДР
Оптимум:
тандартная
форма
задач
линейного
программирования
Преобразуем задачу ЛП к стандартной форме:
Имеем
систему
из
m
=
2
уравнений
и
n
=
4
переменных
.
Доказано,
что
угловые
точки
можно
найти
алгебраически,
присвоив
n
–
m
=
4
±
2
=
2
переменным
нулевых
значений
и
решив
систему
уравнений
относительно
оставшихся
m
=
2
переменных
.
Положим
тогда
решением
системы
будет
.
Это
решение
соответствует
точке
А
.
Еще
одну
угловую
точку
можно
определить,
если
положить
.
В
этом
случае
нужно
найти
решение
системы
:
тандартная
форма
задач
линейного
программирования
ример
Решение: , что соответствует точке С.
Как
определить
:
какие
n
-
m
переменные
положить
равными
нулю,
чтобы
получить
конкретную
угловую
точку
.
Во
-
первых,
это
можно
сказать
только
по
графическому
представлению
ОДР
.
Во
-
вторых,
это
можно
только
для
двух
и
трех
переменных
.
Однако
можно
перечислить
все
угловые
точки
ОДР
.
Для
этого
рассмотрим
все
комбинации
n
–
m
переменных,
приравняем
их
нулю
и
затем
найдем
решение
полученной
системы
уравнению
.
Оптимальное
решение
будет
среди
допустимых
угловых
точек
.
Имеем:
угловых точек. На рисунке видны только четыре точки: А, В,С
и D
. Есть и точки E
и F
. Но это недопустимые
угловые точки. Они не рассматриваются при поиск оптимума.
тандартная
форма
задач
линейного
программирования
ример
Комбинаторное число сочетаний из n
по m .
азисные и небазисные переменные
Небазисные
(нулевые) переменные
Базисные переменные
Базисные решения
Угловые точки
Допустимо ли решение?
Значение целевой функции z
(5, 4)
A
Да
0
(4, -
3)
F
Нет
-
(2,5; 1,5)
D
Да
7,5
(2, 3)
B
Да
4
(5, -
6)
E
Нет
-
(1, 2)
C
Да
8 (Оптимум)
Названия угловых точек на «алгебраическом языке»:
ебазисные
(нулевые)
переменные
±
переменные
в
количестве
n
–
m
,
которые
полагаются
равными
нулю
.
азисные
переменные
±
переменные
в
количестве
m
,
которые
доставляют
системе
уравнений
единственное
решение
азисное
решение
±
совокупность
базисных
переменных
.
опустимое
базисное
решение
±
неотрицательное
базисное
решение
.
азмерность задач При возрастании размера задачи (при увеличении n и
m
)
процесс перечисления всех угловых точек становится отдельной сложной задачей.
Например, при n = 20
и
m
= 10 необходимо решить
систем уравнений порядка 10 х 10.
Задачи
ЛП
размерности
10
х
20
считаются
небольшими
.
Реальные
задачи
имеют
сотни
и
тысячи
переменных
.
Симплекс
-
метод
частично
снимает
эту
проблему,
т
.
к
.
рассматривает
не
все
базисные
решения
(угловые
точки
ОДР),
а
только
часть
допустимых
базисных
решений
.
1
1
2
3
4
2
3
4
5
A
F
E
D
C
B
ОДР
Оптимум:
1
.
Увеличиваем
значение
.
До
значения
в
угловой
точке
B
.
Промежуточные
точки
отрезка
AB
не
рассматриваются
.
В
точке
B
алгоритм
должен
увеличивать
,
чтобы
попасть
в
С
и
построить
путь
A
→
B
→
C
.
лгоритм симплекс
-
метода
Алгоритм
симплекс
-
метода
рассматривает
ограниченное
число
допустимых
базисных
решений
.
Алгоритм
начинает
работу
с
исходной
точки
(точка
А
)
.
Здесь
значение
целевой
функции
z
=
0
(
)
.
Если
одна
или
обе
небазисные
переменные
примут
положительные
значения,
то
приведет
ли
это
к
увеличению
z
?
Ответ
:
да,
так
как
рассматривается
задача
максимизации
.
Алгоритм
допускает
увеличение
на
каждом
шаге
значения
только
одной
небазисной
переменной
.
2. Увеличиваем значение . Алгоритм должен построить путь
A
→
D →
C
.
лгоритм симплекс
-
метода
Оба
пути
A→
B
→
C
и
A→
D
→
C
идут
вдоль
границ
ОДР
.
Причина
:
симплекс
-
метод
не
может
«перескочить»
из
точки
A
в
точку
C
сразу
.
Эмпирическое
правило
определения
факта
:
какую
небазисную
переменную
сделать
положительной
в
некоторой
угловой
точке
:
«На
очередной
шаге
задачи
максимизации
выбрать
такую
небазисную
переменную
которая
имеет
наибольший
положительный
коэффициент
в
уравнении
целевой
функции
.
Если
таких
переменных
несколько,
то
выбор
произвольный»
.
Применение
правила
ведет
к
наименьшему
числу
итераций
алгоритма
.
еревод небазисных переменных в базисные и наоборот в каждой угловой точке Точка A
Точка B
Точка C
вводится
исключается
вводится
исключается
Оптимум
Небазисные
(нулевые) переменные
Базисные переменные
1
1
2
3
4
2
3
4
5
A
F
E
D
C
B
ОДР
Оптимум
сключаемая переменная
-
.
Процесс изменения «состояний» переменных. Рассмотрим его для точки A
.
Происходит одновременный обмен «состояниями» между небазисной переменной и базисной переменной , что приводит к новым небазисным переменным и базисным переменным в точке B
.
водимая переменная
-
.
При выполнении ограничений:
лгоритм симплекс
-
метода
Рассмотрим алгоритм симплекс
-
метода на примере производства красок.
Запишем задачу ЛП в стандартной форме:
Представим целевую функцию в виде:
омментарии к таблице
Таблица
показывает
множества
базисных
и
небазисных
переменных,
а
также
решение
соответствующее
начальной
итерации,
которая
начинается
с
точки
. Это соответствует следующим значениям переменных:
Небазисные (нулевые) переменные : Базисные переменные: .
Легко
получаем
решение
.
В
таблице
базисные
переменные
перечислены
в
столбце
«Базис»,
а
их
значения
в
столбце
«Решение»
.
аким
образом
текущая
угловая
точка
определяется
указанием
базисных
переменных
и
их
значений,
а
также
вычислением
значения
целевой
функции
.
Базис
z
Решение
z
1
-
5
-
4
0
0
0
0
0
z
-
строка
0
6
4
1
0
0
0
24
-
строка
0
1
2
0
1
0
0
6
-
строка
0
-
1
1
0
0
1
0
1
-
строка
0
0
1
0
0
0
1
2
-
строка
Представим задачу ЛП в стандартной форме таблицей.
Будет
ли
начальное
решение
оптимальным?
Конечно
нет
.
Увеличение
переменных
приводит
к
увеличению
z
.
Поскольку
коэффициент
при
переменной
в
формуле
целевой
функции
больше,
чем
коэффициент
при
вносим
переменную
в
число
базисных
(она
станет
вводимой)
.
Это
можно
сделать
по
таблице
.
Ищем
z
-
строку,
в
ней
находим
наибольший
отрицательный
коэффициент
и
определяем
в
заголовке
столбца
переменную
.
Если
в
z
-
строке
все
коэффициенты
будут
неотрицательные,
то
означает,
что
достигнуто
оптимальное
решение
.
пределение вводимой и исключаемой переменных
пределение вводимой переменной.
пределение исключаемой переменной.
Чтобы
определить
исключаемую
переменную
по
таблице,
надо
вычислить
точки
пересечения
всех
функций
ограничений
с
положительным
направлением
оси
0
.
Координаты
этих
точек
пересечения
можно
вычислить
как
отношения
правых
частей
равенств
(значение
в
столбце
«Решение»)
к
коэффициентам
при
переменной
в
этих
равенствах,
как
показано
в
следующей
таблице
.
Базис
Коэффициенты при Решение
Точка пересечения
6
24
1
6
-
1
1
0
2
пределение вводимой и исключаемой переменных
Замена исключаемой переменной на вводимую переменную приводит к новым множествам базисных переменных и новому решению в точке B
:
Небазисные (нулевые) переменные : Базисные переменные: Теперь
необходимо
выполнить
преобразования
в
таблице
так,
чтобы
в
столбцах
«Базис»
и
«решения»
получить
новое
решение,
соответствующее
точке
В
.
ычисление нового базисного решения методом аусса
-
ордано
(арл Фридрих аусс -
ильгельм ордан)
Базис
z
Решение
z
1
-
5
-
4
0
0
0
0
0
0
6
4
1
0
0
0
24
0
1
2
0
1
0
0
6
0
-
1
1
0
0
1
0
1
0
0
1
0
0
0
1
2
Ведущий столбец
Ведущая строка
едущий столбец
ассоциируется с вводимой переменной.
едущая строка
ассоциируется в исключаемой переменной.
Элемент на пересечении ведущего столбца и ведущей строки называется ведущим.
Текущая z
-
строка
ычисление нового базисного решения методом аусса
-
ордано
Процесс вычисления базисного решения состоит из двух этапов:
1)
Вычисление
элементов
новой
ведущей
строки
:
Новая
ведущая
строка
=
текущая
ведущая
строка
/
ведущий
элемент
;
2) Вычисление элементов остальных строк, включая z
-
строку: Новая строка = текущая строка ±
(коэффициент текущей строки в ведущем столбце х новая ведущая строка)
Базис
z
Решение
z
1
0
-
2
/3
5/6
0
0
0
2
0
0
1
2/3
1
/6
0
0
0
4
0
0
4/3
-
1
/6
1
0
0
2
0
0
5/3
1/6
0
1
0
5
0
0
1
0
0
0
1
2
Определим по таблице уравнение целевой функции
Ведущий столбец
Ведущая строка
Новая ведущая строка
Новая z
-
строка
Базис
z
Решение
z
1
0
-
2
/3
5/6
0
0
0
2
0
0
1
2/3
1
/6
0
0
0
4
0
0
4/3
-
1
/6
1
0
0
2
0
0
5/3
1/6
0
1
0
5
0
0
1
0
0
0
1
2
Ведущий столбец
Ведущая строка
Базис
z
Решение
z
1
-
5
-
4
0
0
0
0
0
0
6
4
1
0
0
0
24
0
1
2
0
1
0
0
6
0
-
1
1
0
0
1
0
1
0
0
1
0
0
0
1
2
Ведущий столбец
Ведущая строка
Текущая z
-
строка
Новая ведущая строка
Новая z
-
строка
Процесс вычисления базисного решения состоит из двух этапов:
1)
Вычисление
элементов
новой
ведущей
строки
:
Новая
ведущая
-
строка
=
текущая
ведущая
-
строка
/
6
;
2) Вычисление элементов остальных строк, включая z
-
строку: Новая z
-
строка = текущая z
-
строка ±
(
-
5 х новая ведущая строка)
;
Новая -
строка = текущая z
-
строка ±
(
1 х новая ведущая строка)
;
Новая -
строка = текущая z
-
строка ±
(
-
1 х новая ведущая строка)
;
Новая -
строка = текущая z
-
строка ±
(
0 х новая ведущая строка)
;
асчеты для одного шага вычислений нового базисного решения методом аусса
-
ордано
В нашем примере выполним следующие вычисления:
Базис
Коэффициенты при Решение
Точка пересечения
2
/3
4
4/3
2
5/3
5
1
2
Теперь
необходимо
выполнить
преобразования
в
таблице
так,
чтобы
в
столбцах
«Базис»
и
«решения»
получить
новое
решение,
соответствующее
точке
С
.
Замена
исключаемой
переменной
на
вводимую
переменную
приводит
к
новым
множествам
базисных
переменных
и
новому
решению
в
точке
С
:
Небазисные (нулевые) переменные : Базисные переменные: пределение вводимой и исключаемой переменных
ычисление нового базисного решения методом аусса
-
ордано
Базис
z
Решение
z
1
0
0
3/4
1/2
0
0
21
0
1
0
1
/4
-
1/2
0
0
3
0
0
1
-
1
/8
3/4
0
0
3/2
0
0
0
3/8
-
5/4
1
0
5/2
0
0
0
1/8
-
3/4
0
1
1/
2
Поскольку z
-
строка не имеет отрицательных коэффициентов, соответствующих небазисным переменным , полученное решение оптимально.
Явления вычислительного процесса симплекс
-
метода
ырожденность
.
Проверка
условия
допустимости
может
привести
к
многозначности
в
выборе
исключаемой
переменной
.
В
этом
случае
на
следующей
итерации
одна
или
несколько
базисных
переменных
примут
нулевое
значение
.
Тогда
новое
решение
будет
вырожденным
.
С
практической
точки
зрения
вырожденность
объясняется
тем,
что
в
постановке
задачи
ЛАП
есть
как
min
одно
избыточное
ограничение
.
Оптимальное вырожденное решение
Избыточное ограничение
Рассмотрим задачу:
Ограничения:
Точка
оптимума
-
пересечение
трех
прямых
.
Поскольку
задача
двухмерна,
эта
точка
переопределена
.
На
плоскости
для
определения
точки
достаточно
двух
прямых,
а
значит
одно
ограничение
избыточно
.
Явления вычислительного процесса симплекс
-
метода ырожденность
Информация,
что
некоторые
ресурсы
недефицитны,
может
быть
полезна
при
интерпретации
результатов
решения
задачи
.
Эти
сведения
также
могут
помочь
выявить
неточности
и
ошибки
в
постановке
задачи
.
Нет
способов
определить
избыточное
ограничение
по
симплекс
-
таблицам
.
С
вычислительной
точки
зрения
вырожденность
может
привести
к
зацикливанию
.
С
теоретической
точки
зрения
вероятность
зацикливания
в
задачах
ЛП,
решаемых
симплекс
-
методом
очень
мала
.
Явления вычислительного процесса симплекс
-
метода льтернативные оптимальные решения
льтернативные
оптимальные
решения
.
Это
явление
возникает
когда
(для
двухмерного
случая)
прямая,
представляющая
целевую
функцию,
параллельна
прямой,
соответствующей
связывающему
неравенству
(которое
в
точке
пересечения
выполняется
как
точное
равенство)
.
Тогда
целевая
функция
примет
одно
и
то
же
оптимальное
решение
на
некотором
множестве
точек
границы
ОДР
.
Эти
решения
называются
альтернативными
оптимальными
решениями
.
Оптимальное базисные решения
А
B
C
D
Ограничения:
Симплекс
-
метод
может
определить
только
две
угловые
точки
.
На
практике
альтернативные
оптимальные
решения
предоставляют
возможность
сделать
выбор
.
Математически можно найти все точки отрезка ВС как взвешенное среднее.
Явления вычислительного процесса симплекс
-
метода еограниченная целевая функция
еограниченная
целевая
функция
.
Это
явление
возникает,
когда
в
задаче
ЛП
имеет
место
не
ограниченная
ОДР
.
Неограниченное значение целевой функции
Неогран
иченная ОДР
Ограничения:
В
некоторых
задачах
ЛП
значения
переменных
могут
неограниченно
возрастать
без
нарушения
ограничений
.
В
результате
±
целевая
функция
может
возрастать
(
при
максимизации)
или
убывать
(при
минимизации)
неограниченно
.
Неограниченность
решения
показывает
одно
±
модель
разработана
не
корректно
.
Явления вычислительного процесса симплекс
-
метода тсутствие допустимых решений
тсутствие
допустимых
решений
.
Явление
возникает,
если
ограничения
задачи
ЛП
несовместимы
,
т
.
е
.
не
могут
выполняться
одновременно
.
Такая
ситуация
не
возникнет,
если
все
неравенства
-
ограничения
имеют
тип
.
На
практике
возникновение
такого
явления
означает,
что
задача
плохо
сформулирована
.
Псевдооптимальное решение
войственность задач линейного программирования
Исходную
задачу
ЛП
будем
называть
прямой
.
войственная
задача
-
это
задача,
формулируемая
с
помощью
определенных
правил
непосредственно
из
прямой
.
Задача ЛП в стандартной форме записывается так:
Максимизировать или минимизировать целевую функцию
При ограничениях:
В состав n
переменных входят и дополнительные переменные.
Стандартная форма задач ЛП приводит к стандартной таблице симплекс
-
метода.
равила преобразования прямой в двойственную задачу
Переменные
и
ограничения
двойственной
задачи
формируются
путем
симметричных
структурных
преобразований
прямой
задачи
по
следующим
правилам
.
1)
Каждому
из
m
ограничений
прямой
задачи
соответствует
переменная
двойственной
задачи
.
2)
Каждой
из
n
переменных
прямой
задачи
соответствует
ограничение
двойственной
задачи
.
3)
Коэффициенты
при
какой
-
либо
переменной
в
ограничениях
прямой
задачи
становятся
коэффициентами
ограничения
двойственной
задачи,
соответствующего
этой
переменной
.
Правая
часть
формируемого
ограничения
равна
коэффициенту
при
этой
переменной
в
выражении
целевой
функции
.
4)
Коэффициенты
целевой
функции
двойственной
задачи
равны
правым
частям
ограничений
прямой
задачи
.
Переме
нные 2
-
задачи
Переменные прямой задачи
j
±
ое
ограничения
2
-
задачи
Коэффициенты целевой функции 2
-
задачи
реобразование прямой в двойственную задачу
равила определения типа оптимизации и типа ограничений
Прямая задача
Двойственная задача
max
min
min
max
Прямая задача
Максимизировать
При ограничениях
Прямая задача в стандартной форме
Максимизировать
При ограничениях
Двойственные переменные
Двойственная задача
При ограничениях
Минимизировать
ример прямой и двойственной задачи
(избыточное условие)
оотношения между прямой и двойственной задачами Двойственной
к
двойственной
задаче
ЛП
будет
прямая
задача
.
Поэтому
симплекс
-
метод
симметричен
относительно
прямой
и
двойственной
задач
.
Его
можно
использовать
для
определения
оптимального
решения
одной
задачи
непосредственно
из
симплекс
-
таблицы,
содержащей
оптимальное
решение
другой
.
Отсюда
вычисления
можно
проводить
для
той
задачи
(прямой
или
двойственной),
которая
требует
меньших
вычислительных
ресурсов
:
меньший
объем
вычислений
имеет
задача
с
меньшим
количеством
ограничений
.
Экономическая интерпретация двойственности
В
прямой
задаче
коэффициент
-
прибыль
на
единицу
продукции
j
-
го
вида
экономической
деятельности,
причем
на
единицу
продукции
этого
вида
деятельности
расходуется
единиц
ресурса
i
,
максимальные
запасы
которого
ограничены
величиной
.
Для любой пары допустимых решений прямой и двойственной задачи значения (конечные) их целевых функций удовлетворяют неравенству
Максимизировать
При ограничениях
Минимизировать
При ограничениях
Иными
словами
±
для
всех
допустимых
решений
прямой
и
2
-
задач
значения
целевой
функции
задачи
минимизации
всегда
будут
верхним
пределом
значений
целевой
функции
задачи
максимизации
.
Экономическая интерпретация двойственности
Рассмотрим
вариант
оптимума,
т
.
е
.
когда
z
=
w
.
Исходя
из
представлений
прямой
задачи
z
соответствует
величине
дохода
(в
денежных
единицах)
.
Поскольку
доход
±
это
суммарное
количество
ресурсов,
умноженное
на
доход
от
единицы
ресурса,
то
переменная
двойственной
задачи
означает
стоимость
единицы
ресурса
i
.
Для
любой
пары
допустимых
решений
прямой
и
двойственной
задач
неравенство
z
<
w
можно
интерпретировать
так
:
доход < общая стоимость ресурсов.
Это
соотношение
показывает,
что
до
тех
пор,
пока
суммарный
доход
от
всех
видов
деятельности
строго
меньше
суммарной
стоимости
всех
используемых
ресурсов,
решение
как
прямой,
так
и
2
-
задачи
не
может
быть
оптимальным
.
Оптимум
(максимальный
доход)
может
быть
достигнут
только
тогда,
когда
все
потребляемые
ресурсы
использованы
полностью
.
Если
представить
экономическую
систему
со
входом
(потребляемые
ресурсы)
и
выходом
(получаемый
доход),
то
такая
система
будет
находится
в
нестабильном
(неоптимальном
)
состоянии
пока
вход
превышает
выход
.
Устойчивое
состояние
характеризуется
равенством
входа
и
выхода
.
Вход
Выход
Экономическая система
Ресурсы
Доход
елинейное программирование
В
общем
виде
задача
нелинейного
программирования
состоит
в
определении
max
(
min)
значения
функции
При условии, что ее переменные удовлетворяют соотношениям
где f
и -
некоторые известные функции n переменных, а -
заданные числа.
В
результате
решения
задачи
будет
определена
точка
,
координаты
которой
удовлетворяют
ограничениям,
и
такая,
что
для
всякой
другой
точки
,
удовлетворяющей
тем
же
ограничениям,
выполняется
неравенство
етоды решения задач нелинейного программирования
1)
Геометрический метод
2)
Метод множителей Лагранжа
3)
Метод штрафных функций
4)
Генетические алгоритмы
ешение задач нелинейного программирования
Если f
и -
линейные функции, то задача является задачей линейного программирования.
В отличие от ЛП область допустимых решений (ОДР) не всегда выпуклая.
Если
ОДР
задачи
НЛП,
то
ее
решение
сводится
к
определению
такой
точки
этой
области,
через
которую
проходит
гиперповерхность
наивысшего
(наинизшего)
уровня
:
.
Эта
точка
может
находиться
как
на
границе
ОДР,
так
и
внутри
нее
.
Процесс геометрического нахождения решения задачи НЛП включает следующие этапы:
1)
Находят ОДР, ели она пуста, то задача не имеет решения.
2)
Строят гиперплоскость .
3)
Определяют гиперповерхность наивысшего (наинизшего) уровня или устанавливают неразрешимость задачи из
-
за неограниченности функции f
сверху (снизу) на множестве допустимых решений.
4)
Находят точку ОДР, через которую проходит гиперповерхность наивысшего (наинизшего) уровня, и определяют значение функции f
в ней.
Найти максимальное значение функции:
при условиях:
ример задачи 2
4
1
2
3
2
4
6
8
10
12
14
6
8
10
12
D
B
G
C
ОДР
1
2
3
A
4
4
ример решения задачи Так как целевая функция нелинейная, имеем задачу НЛП.
ОДР
±
многоугольник
ABCG
.
Для
решения
задачи
НЛП
нужно
определить
такую
точку
многоугольника
ABCG
,
в
которой
функция
F
принимает
максимальное
значение
.
Построим
линию
уровня
где
h
-
некоторая
постоянная,
и
исследуем
ее
поведение
при
различных
значениях
h
.
При
каждом
значении
h
получаем
параболу,
которая
тем
выше
удалена
от
оси
абсцисс,
чем
больше
значение
h
.
Значит,
функция
F
принимает
максимальное
значение
в
точке
касания
одной
из
парабол
с
границей
многоугольника
ABCG
.
Это
точка
D
,
в
которой
линия
уровня
касается
стороны
BC
многоугольника
ABCG
.
Координаты
этой
точки
D
можно
найти
из
системы
уравнений
:
Решая эту систему, получим . Итак етод множителей агранжа
Рассматривается частный случай общей задачи НЛП: 1)
Система ограничений содержит только уравнения;
2)
Отсутствуют условия неотрицательности переменных;
3)
Функции -
функции непрерывные, вместе со своими частными производными.
Тогда задача НЛП может быть сформулирована следующим образом:
Эта задача называется классической задачей оптимизации
.
Рассмотрим задачу: f
(
X
) ®
max , при условии g
(
X
) = 0.
По
склону
горы
идет
дорога,
требуется
найти
на
ней
самую
высокую
точку
.
На
рисунке
представлена
карта
местности
с
нанесенными
на
нее
линиями
равных
высот
.
Толстая
линия
±
это
дорога
.
Точка
М
,
в
которой
дорога
касается
одной
линий
уровня,
-
это
и
есть
наивысшая
точка
дороги
.
Если
±
точка
плотности,
и
±
е
координаты,
то
задаче
можно
придать
следующую
форму
.
Пусть
f
(
Х
)
²
высота
точки
Х
над
уровнем
моря,
а
уравнение
g
(
X
)
=
0
описывает
дорогу
.
Тогда
наивысшая
точка
дороги
-
решение
задачи
.
Если
бы
дорога
проходила
через
вершину
горы,
то
ее
высшая
точка
была
бы
самой
высокой
точкой
местности,
и
ограничение
можно
было
бы
не
принимать
во
внимание
.
Если
же
дорога
не
проходит
через
вершину,
то,
немного
отклонившись
от
дороги,
можно
было
бы
подняться
выше,
чем
двигаясь
строго
по
дороге
.
Отклонение
от
дороги
соответствует
попаданию
в
такие
точки,
где
g
(
X
)
0
;
при
малых
отклонениях
достижимую
при
этом
высоту
можно
приближенно
считать
пропорциональной
отклонению
.
етод множителей агранжа
ростой пример
Идею
решения
задачи
Лагранжа
можно
представить
следующим
образом
:
можно
попытаться
³исправить´
рельеф
местности
так,
чтобы
отклонение
от
дороги
не
давало
преимуществ
в
достижении
высоты
.
Для
этого
нужно
заменить
высоту
f
(
Х
)
функцией
.
L
(
X
) = f
(
X
) -
g
(
Х
),
где
множитель
подбирается
таким
образом,
чтобы
участок
склона
в
окрестности
точки
М
стал
горизонтальным
(слишком
малое
не
устранит
преимуществ
отклонений
от
дороги,
а
слишком
большое
±
придаст
преимущество
отклонениям
в
противоположную
сторону)
.
Теперь,
поскольку
рельеф
L
(
X
)
делает
площадку
в
окрестности
точки
оптимума
горизонтальной,
эта
точка
удовлетворяет
равенствам
а
так
как
точка
лежит
на
дороге,
то
±
и
ограничению
g
(
X
)
=
0
.
етод множителей агранжа
ростой пример
Разрез горы по АВ
етод множителей агранжа
Для решения задачи НЛП вводят набор переменных , называемых множителями Лагранжа и составляют функцию Лагранжа:
Находят частные производные и рассматривают систему
n + m
уравнений:
с n + m
неизвестными .
Решив систему уравнений, получим все точки , в которых функция может имеет экстремумы. Дальше эти точки должны быть дополнительно исследованы. Методика определения экстремальных точек методом множителей Лагранжа:
1)
Составить функцию Лагранжа.
2)
Найти частные производные от функции Лагранжа по переменным и и приравнять их нулю.
3)
Решить систему уравнений и найти точки, в которых целевая функция может иметь экстремум.
4) Найти среди точек, подозрительных на экстремум, такие, в которых достигается экстремум и вычислить значения функции в этих точках. етод множителей агранжа
етод множителей агранжа
ример
По
плану
производства
предприятию
нужно
изготовить
180
изделий
.
Они
могут
быть
изготовлены
2
способами
.
При
производстве
изделий
1
способом
затраты
равны
руб
.
,
а
при
изготовлении
изделий
2
способом
они
составляют
руб
.
Определить,
сколько
изделий
каждым
из
способов
следует
изготовить,
так
чтобы
общие
затраты
на
производство
продукции
были
минимальными
.
Математическая постановка задачи:
определить минимальное значение функции
при условиях
етод множителей агранжа
ример геометрического решения
B
C
A
ОДР
±
отрезок
АС
.
Линии
уровня
окружности
с
центром
в
точке
(
-
2
,
-
4
)
.
Проводя
из
этой
точки
окружности
разных
радиусов
видим,
что
min
значение
целевая
функция
принимает
в
точке
B
.
Найдем
координаты
точки
B
.
Поскольку
угловой
коэффициент
к
окружности
в
точке
B
совпадает
с
угловым
коэффициентом
прямой
он
равен
-
1
.
Рассматривая
как
неявную
функцию
от
,
и
дифференцируя
уравнение
окружности,
имеем
Приравнивая
полученное
выражение
±
1
,
получаем
одно
из
уравнений
для
определения
координат
точки
B
.
Присоединяем
к
нему
уравнение
прямой,
на
которой
лежит
точка
B
,
имеем
систему
Откуда Это
означает,
что
если
предприятие
изготовит
91
изделие
1
способом
и
89
изделий
2
способом
,
то
общие
затраты
будут
минимальными
и
составят
17278
руб
.
етод множителей агранжа
ример решения метод множителей агранжа
Найдем
min
целевой
функции
без
учета
требования
неотрицательности
переменных
.
Составим
функцию
Лагранжа
Вычислим ее частные производные по и приравняем их нулю:
етод множителей агранжа
ример решения метод множителей агранжа
Перенося в правые части первых двух уравнений и приравнивая их левые части, получим
Решая последнее уравнение совместно с уравнением , находим . Эта
точка
±
подозрительная
на
экстремум
.
Используя
вторые
частные
производные,
можно
показать,
что
в
точке
B
функция
f
имеет
условный
минимум
.
етод штрафных функций
Метод
штрафных
функций
относится
к
группе
непрямых
методов
решения
задач
НЛП
.
Он
преобразуют
задачу
с
ограничениями
в
последовательность
задач
безусловной
оптимизации
некоторых
вспомогательных
функций
.
Они
получаются
модификацией
целевой
функции
с
помощью
функций
-
ограничений
таким
образом,
чтобы
ограничения
в
явном
виде
в
задаче
оптимизации
не
фигурировали
.
Это
обеспечивает
возможность
применения
методов
безусловной
оптимизации
.
Рассмотрим задачу определения максимального значения вогнутой функции при условии и , где -
выпуклые функции. Вместо того, чтобы непосредственно решать эту задачу, находят максимальное значение функции Являющейся
суммой
целевой
функции
задачи,
и
некоторой
функции
определяемой
системой
ограничений
и
называемой
штрафной
функцией
.
Штрафная
функция
обычно
имеет
вид
:
где
а -
весовые коэффициенты. етод штрафных функций
Используя
штрафную
функцию,
последовательно
переходят
от
одной
точки
к
другой
до
тех
пор,
пока
не
получат
приемлемое
решение
.
Координаты последующей точки находят по формуле:
Из
формулы
следует,
что
если
предыдущая
точка
находится
в
ОДР,
то
второе
слагаемое
в
квадратных
скобках
равно
нулю
и
переход
к
последующей
точке
определяется
только
градиентом
целевой
функции
.
Если
же
указанная
точка
не
принадлежит
ОДР,
то
за
счет
данного
слагаемого
на
последующих
итерациях
достигается
возвращение
в
ОДР
.
При
этом,
чем
меньше
,
тем
быстрее
находится
приемлемое
решение
.
Однако
точность
его
определения
снижается
.
Поэтому
итерационный
процесс
начинают
при
малых
значениях
и,
продолжая
его,
эти
значения
постепенно
увеличивают
.
где -
шаг вычислений , вычисляется или выбирается так, чтобы значение функции , зависящее от ,в точке было максимальным. етод штрафных функций
Пусть функция
дифференцируема в точке . Назовем
градиентом функции
вектор:
Геометрически
направление
градиента
функции
совпадает
с
направлением
наискорейшего
возрастания
величины,
задаваемой
этой
функцией,
а
его
модуль
равен
частной
производной
этой
функции
по
данному
направлению
.
онятие градиента
оператор набла
Найдем градиент функции в точке A
(2, 1 ,1).
1. Находим частные производные функции F
:
2. Вычисляем частные производные в точке A
(2, 1 ,1):
3. Вычисляем градиент функции F в точке А
(2, 1, 1) :
онятие градиента
Последовательность выполнения этапов метода штрафных функций:
1)
Определяют исходное допустимое решение.
2)
Выбирают шаг вычислений.
3)
Находят по всем переменным частные производные от целевой функции и функций, определяющих ОДР.
4)
Находят по формуле для координаты точки, определяющей возможное новое решение задачи.
5)
Проверяют,
удовлетворяют
ли
координаты
найденной
точки
системе
ограничений
задачи
.
Если
нет,
то
переходят
к
следующему
этапу
.
Если
координаты
найденной
точки
определяют
допустимое
решение
задачи,
то
исследуют
необходимость
перехода
к
последующему
решению
.
В
случае
такой
необходимости
переходят
к
этапу
2
,
в
противном
случае
найдено
приемлемое
решение
исходной
задачи
.
6)
Устанавливают значения весовых коэффициентов и переходят к этапу 4.
етод штрафных функций
ример Найти максимальное значение функции:
При условиях:
Построим
ОДР
задачи
и
линии
уровня
для
целевой
функции
.
Этими
линиями
служат
окружности
в
центром
в
точке
(
0
;
0
)
.
Точка
касания
одной
из
этих
окружностей
с
ОДР
и
является
искомой
точкой
максимального
значения
целевой
функции
.
етод штрафных функций
8
10
2
4
6
2
4
6
8
10
E
ОДР
Линии уровня
етод штрафных функций
ример
бласть допустимых решений и линии уровня
Построим
ОДР
задачи
и
линии
уровня
для
целевой
функции
.
Этими
линиями
служат
окружности
в
центром
в
точке
(
0
;
0
)
.
Точка
касания
одной
из
этих
окружностей
с
ОДР
и
является
искомой
точкой
максимального
значения
целевой
функции
.
ример етод штрафных функций
Положим . Возьмем . Обозначим через и определим частные производные от функций и по переменным . Используя формулу для построим последовательность допустимых точек, одна из которых определит приемлемое решение.
Так как точка принадлежит ОДР, то второе слагаемое в квадратных скобках равно нулю. Тогда координаты следующей точки вычисляем по формулам:
Проверим теперь, принадлежит ли эта точка ОДР. Для этого найдем:
Так как , то принадлежит ОДР. В этой точке ример етод штрафных функций
2 итерация.
3 итерация.
ример етод штрафных функций
ример етод штрафных функций
4 итерация.
Точка не принадлежит ОДР. Следовательно
Необходим
выбор
числа
.
Оно
должно
быть
выбрано
так,
чтобы
точка
не
слишком
далеко
удалялась
от
границы
ОДР
и
вместе
с
тем
принадлежала
ОДР
.
Этим
требованиями
удовлетворяет,
в
частности,
.
Тогда
имеем
:
5 итерация
.
6 итерация.
7 итерация.
ример етод штрафных функций
8 итерация.
9 итерация.
10 итерация.
ример етод штрафных функций
11 итерация.
12 итерация.
Сравнивая
значения
целевой
функции,
найденные
в
точках
после
10
и
12
итераций,
видим,
что
они
с
точностью
до
0
,
1
совпадают
.
Это
говорит
о
близости
точки,
найденной
на
последней
итерации,
к
точке
максимального
значения
целевой
функции
.
ример етод штрафных функций
инамическое программирование
Словосочетание
динамическое
программирование
впервые
было
использовано
в
1940
-
х
годах
Ричардом
Беллманом
для
описания
процесса
нахождения
решения
задачи,
где
ответ
на
одну
задачу
может
быть
получен
только
после
решения
задачи,
«предшествующей»
ей
.
Слово
«программирование»
в
словосочетании
«динамическое
программирование»
происходит
от
словосочетания
математиче
6
ское
программирование
-
синонима
слова
«оптимизация»
.
Слово
«программа»
в
данном
контексте
означает
оптимальную
последовательность
действий
для
получения
решения
задачи
.
ичард еллман
Американский математик, один из ведущих специалистов в области математики и вычислительной техники, профессор
инамическое программирование
Динамическое
программирование
(ДП)
определяет
оптимальное
решение
n
±
мерной
задачи
путем
ее
декомпозиции
на
n
этапов,
каждый
из
которых
есть
подзадача
относительно
одной
переменной
.
Вычислительное
преимущество
ДП
±
решаются
одномерные
оптимизационные
задачи
вместо
большой
n
-
мерной
задачи
.
ДП
не
использует
«собственных»
вычислительных
алгоритмов
непосредственно
для
каждого
этапа
.
Эти
алгоритмы
проектируются
и
реализуются
по
отдельности
.
Например,
это
могут
быть
алгоритмы
ЛП
.
екуррентная природа вычислений в динамическом программировании
Вычисления в ДП рекуррентные в том смысле, что оптимальное решение одной подзадачи ±
исходные данные для следующей. Решение последней задачи ±
оптимальное решение исходной задачи.
инамическое программирование
онятия декомпозиции и редукции
екомпозиция
²
научный
метод,
использующий
структуру
задачи
и
позволяющий
заменить
решение
одной
большой
задачи
решением
серии
меньших
задач
.
Расчлените
каждую
изучаемую
Вами
задачу
на
несколько
частей,
на
сколько
сможете
и
на
сколько
это
потребуется
Вам,
чтобы
их
было
легко
решить
.
Р. Декарт.
едукция
(лат
.
reductio
²
возвращение,
приведение
обратно)
восстановление
прежнего
состояния,
сведение
сложного
к
более
простому
.
едуцирование
²
наименование
процессов,
ведущих
к
уменьшению
размеров
какого
-
либо
объекта,
упрощению
его
структуры
или
к
ослаблению
напряжения,
силы,
иногда
к
полному
исчезновению
чего
-
либо
.
едукция
-
методологический
прим,
играющий,
важнейшую
роль
в
логике,
математике
и
др
.
дедуктивных
науках
.
Редукция
состоит
в
преобразовании
данных
(задач,
предложений
и
т
.
п
.
)
в
наиболее
удобный
с
какой
-
либо
точки
зрения
вид,
например
в
выражении
их
в
форме
логически
более
простой
и
легче
поддающейся
анализу
.
инамическое программирование
адача о кратчайшем пути
Необходимо
выбрать
кратчайший
путь
между
двумя
городами
(городами
1
и
7
)
Сеть
дорог
на
рисунке
±
возможные
маршруты
между
исходным
городом,
находящемся
в
вершине
1
,
и
конечным
пунктом,
который
находится
в
вершине
7
.
Дуги
взвешены
расстояниями
между
городами
у
условных
единицах
.
1
2
3
4
5
6
7
7
8
5
12
8
9
10
13
9
6
Начало пути
Конец пути
Можно
решить
задачу
полным
перебором
всех
маршрутов
между
вершинами
1
и
7
.
Однако
в
большой
сети
полный
перебор
неэффективен
с
вычислительной
точки
зрения
.
инамическое программирование
адача о кратчайшем пути
Для
решения
задачи
методами
ДП
разделим
ее
на
этапы
.
Вертикальные
пунктирные
линии
на
рисунке
выделяют
три
этапа
.
Это
и
есть
декомпозиция
исходной
задачи
.
Далее
вычисления
выполняются
для
каждого
этапа
в
отдельности
.
Декомпозиция исходной задачи на части
1
2
3
4
5
6
7
8
5
12
8
9
7
13
2
3
4
5
6
7
9
6
0
7
8
5
7
8
5
12
17
12
17
21
Этап 1
Этап 2
Этап 3
инамическое программирование
адача о кратчайшем пути
Общая
задача
состоит
в
вычислении
кратчайших,
постепенно
накапливаемых
расстояний
ко
всем
вершинам
этапа
с
последующим
использованием
этих
расстояний
в
качестве
исходных
данных
для
следующего
этапа
.
Для первого этапа имеем следующие вычисления: Этап 1.
Итоговые результаты:
Кратчайший путь из вершины 1 в вершину 2 ±
7 км; 1 →
3 ±
8 км; 1 →
4 ±
5 км.
Переходим
к
этапу
2
вычисления
кратчайших
(накопленных)
расстояний
к
вершинам
5
и
6
.
Рассматриваем
вершину
5
первой
.
Есть
3
маршрута
для
достижения
вершины
5
:
(
2
,
5
),
(
3
,
5
)
и
(
4
,
5
)
.
Эта
информация
вместе
с
кратчайшими
расстояниями
к
узлам
2
,
3
и
4
определяет
кратчайшее
(накопленное)
расстояние
к
вершине
5
следующим
образом
:
инамическое программирование
адача о кратчайшем пути
Этап 2.
Итоговые результаты:
Кратчайший путь из вершины 4 в вершину 5 ±
12 км; 3 →6 ±
17 км; Последний шаг ±
третий этап. Конечную вершину 7 можно достичь из вершин 5 и 6. Используя итоговые результаты этапа 2 и расстояния от вершин 5 и6 к вершине 7, получим
Этап 3.
Итоговые результаты:
Кратчайший путь к вершине 7 равен 21 км (из вершины 5); Кратчайшее расстояние между вершинами 1 и 7 равно 21 км.
Определим
города,
через
которые
проходит
кратчайший
маршрут
.
Начинаем
с
конца
.
Из
итоговых
результатов
3
этапа
следует,
что
вершина
7
связывается
с
вершиной
5
.
Из
итоговых
результатов
2
этапа
следует,
что
вершина
5
связывается
с
вершиной
4
.
Из
итоговых
результатов
1
этапа
следует,
что
вершина
4
связывается
с
вершиной
1
.
Таким
образом,
оптимальным
маршрутом
является
1
→
4
→
5
→
7
.
1
2
3
4
5
6
7
8
5
12
8
9
7
13
2
3
4
5
6
7
9
6
0
7
8
5
7
8
5
12
17
12
17
21
Этап 1
Этап 2
Этап 3
1 ←
4
4 ← 5
5 ← 7
инамическое программирование
адача о кратчайшем пути
инамическое программирование
адача о кратчайшем пути
Запишем рекуррентные вычисления ДП математически.
Пусть
-
кратчайшее
расстояние
до
вершины
на
этапе
i
,
-
расстояние
от
вершины
до
вершины
.
Тогда
вычисляется
га
о
c
нове
значений
с
помощью
следующего
рекуррентного
уравнения
:
При
i
=
1
полагаем
.
Это
уравнение
показывает,
что
кратчайшие
расстояния
на
этапе
i
должны
быть
выражены
как
функция
следующей
вершины
.
В
терминологии
ДП
именуется
состоянием
системы
на
этапе
i
.
инамическое программирование
В
действительности
состояние
системы
на
этапе
i
-
это
информация,
связывающая
этапы
между
собой
.
При
этом
оптимальные
решения
для
оставшихся
этапов
могут
приниматься
без
повторной
проверки
того,
как
были
получены
решения
на
предыдущих
этапах
.
Такое
определение
состояния
системы
позволяет
рассматривать
каждый
этап
отдельно
и
гарантирует,
что
решение
является
допустимым
на
каждом
этапе
.
Определение
состояния
системы
приводит
к
следующему
унифицированному
положению
.
ринцип
оптимальности
.
На
каждом
этапе
оптимальная
стратегия
определяется
независимо
от
стратегий,
использованных
на
предыдущих
этапах
.
Рассмотренный
выше
пример,
когда
вычисления
выполнялись
последовательно,
от
первого
этапа
до
третьего
раскрывает
суть
алгоритма
прямой
прогонки
.
Известен
и
алгоритм
обратной
прогонки,
вычисления
в
соответствии
с
которым
выполняются
от
третьего
этапа
до
первого
.
Оба алгоритма приводят к одному и тому же результату. Покажем использование алгоритма обратной прогонки, применив табличную форму.
где для . Последовательность вычислений .
лгоритм обратной прогонки
Этап 3.
Поскольку узел 7 связан с узлами 5 и 6 только одним маршрутом, альтернативы для выбора отсутствуют, а результаты третьего этапа сведены в таблицу.
Оптимальное решение
5
9
9
7
6
6
6
7
1
2
3
4
5
6
7
8
5
12
8
9
7
13
2
3
4
5
6
7
9
6
Этап 3
лгоритм обратной прогонки
Этап 2.
Так как маршрута (2,6) не существует, соответствующая альтернатива не рассматривается. Используя значения , полученные на третьем этапе, мы можем сравнить допустимые альтернативные решения, как показано в таблице.
Оптимальное решение
2
12+9=21
21
5
3
8+9=17
9+6=15
15
6
4
7+9=16
13+6=19
16
5
1
2
3
4
5
6
7
8
5
12
8
9
7
13
2
3
4
5
6
7
9
6
Этап 2
Оптимальное решение 2 этапа означает: «Если Вы находитесь в вершине 2 или 4, кратчайший путь к вершине 7 проходит через узел 5, а если в вершине 3 ±
через вершину 6.
лгоритм обратной прогонки
Этап
1
.
Из
вершины
1
начинаются
три
альтернативных
маршрута
:
(
1
,
2
),
(
1
,
3
)
и
(
1
,
4
)
.
Используя
значения
,
полученные
на
втором
этапе,
вычисляем
данные
следующей
таблицы
.
Оптимальное решение
1
7+21=28
8+15=23
5+16=21
21
4
Оптимальное
решение
на
первом
этапе
показывает,
что
кратчайший
путь
проходит
через
вершину
1
.
Далее
из
оптимального
решения
на
этапе
2
следует,
что
из
города
4
нужно
двигаться
в
город
5
.
Из
оптимального
решения
на
этапе
3
следует,
что
вершина
5
связана
с
вершиной
7
.
Следовательно,
полным
маршрутом
с
кратчайшей
длиной,
является
1
→
4
→
5
→
7
и
его
длина
±
21
км
.
лгоритм обратной прогонки
езусловная оптимизация
Поиск
экстремумов
функций
в
условиях
отсутствия
ограничений
на
значения
переменных
называется
безусловной
оптимизацией
.
Иными
словами
подобные
задачи
называют
экстремальными
задачами
без
ограничений
.
сновные понятия экстремальных задач без ограничений
Экстремальная
точка
функции
определяет
либо
ее
максимальное,
либо
минимальное
значение
.
С
математической
точки
зрения
точка
является
точкой
максимума
функции
,
если
неравенство
выполняется
для
всех
,
таких,
что
достаточно
малы
при
всех
других
j
.
Другими
словами,
точка
является
точкой
максимума,
если
значения
функции
в
окрестности
точки
не
превышают
.
Аналогично
точка
является
точкой
минимума
функции
,
если
для
определенного
выше
вектора
h
имеет
место
неравенство
a
b
На
рисунке
показаны
точки
максимума
и
минимума
функции
одной
переменной
f(x)
на
интервале
[
a,b
]
.
Точки
составляют
множество
экстремальных
точек
функции
f(x)
.
Точки
являются
точками
максимума,
а
точки
-
точками
минимума
функции
f(x)
.
Поскольку
значение
называется
глобальным
или
абсолютным
максимумом
,
а
значения
-
локальными
или
относительными
максимумами
.
Подобным
образом,
значение
является локальным
, а -
глобальным минимумом функции
f(x)
.
сновные понятия экстремальных задач без ограничений
етоды оптимизации
Методы одномерной оптимизации
Методы безусловной оптимизации
Методы условной оптимизации
Методы моделирования эволюции
Методы оптимизации
Методы имитирующие интеллект роя
етоды одномерной оптимизации
1.
Метод дихотомического поиска
2.
Метод золотого сечения
3.
Метод чисел Фибоначчи 4.
Метод полиномиальной аппроксимации
Методы безусловной оптимизации
1.
Метод наискорейшего спуска
2.
Метод Розенблока
3.
Метод конфигураций
4.
Метод Хука
-
Дживса
5.
Метод деформируемого многогранника
6.
Метод Нелдера
-
Мида
7.
Метод случайного поиска
8.
Метод сопряженных градиентов
9.
Метод Флетчера
-
Ривса
10.
Метод Ньютона
11.
Метод переменной метрики
12.
Метод Девидсона
-
Флетчера
-
Пауэла
Методы моделирования эволюции
1.
Классические генетические алгоритмы
2.
Генетические микроалгоритмы
3.
Генетические алгоритмы со взаимной эволюцией
4.
Параллельные эволюционные алгоритмы
5.
Генетические алгоритмы для многокритериальной оптимизации
Методы имитирующие интеллект роя
1. Муравьиный алгоритм
(англ. Ant colony optimization
).
2. Метод роя частиц (англ. Particle swarm optimization
).
3. Пчелиный алгоритм
(англ. Bees algorithm
).
4. Оптимизация передвижением бактерий
(англ. Bacterial foraging optimization
).
5. Стохастический диффузионный поиск
(англ. Stochastic diffusion search
).
6. Алгоритм гравитационного поиска
(англ. Gravitational search algorithm
).
7. Алгоритм капель воды
(англ. Intelligent Water Drops algorithm
).
етод дихотомического поиска
Пусть функция f(x)
непрерывна на интервале [
a,b
] и имеет здесь единственный минимум:
Разобьем мысленно данный отрезок пополам и возьмем две симметричные относительно центра точки и . При этом: где -
некоторое число в интервале (0, )
Отбросим тот из концов изначального интервала, к которому ближе оказалась одна из двух вновь поставленных точек с максимальным значением, то есть, если , то берем отрезок
, а отрезок отбрасываем. Иначе берем , а отбрасываем.
Процедура повторяется до достижения заданной точности.
a
b
a
b
Шаг 2
Шаг 1
етод наискорейшего спуска
Пусть целевая функция имеет вид
Задача оптимизации формулируется так:
Основная идея метода ±
идти в направлении наискорейшего спуска, а это направление определяется антиградиентом :
где λ
= vary и рассчитывается на каждом шаге заново.
Алгоритм метода
1.
Задать начальное приближение и точность ε
.
2.
Рассчитать .
3.
Проверить условие останова: иначе
и останов.
ример наискорейшего спуска
Метод
наискорейшего
спуска
может
иметь
трудности
в
патологических
случаях
овражных
функций,
так,
к
примеру,
в
случае
функции
Розенброка
.
лассические генетические алгоритмы
Генетические
алгоритмы
(ГА)
своим
существованием
обязаны
наблюдениям
и
испытаниям
естественных
процессов
наследования,
происходящих
в
мире
живых
организмов,
а
именно
эволюции
и
связанной
с
ней
естественной
селекции
.
Идею
генетических
алгоритмов
предложил
Джон
Генри
Холланд
на
рубеже
шестидесятых
и
семидесятых
годов
.
В
1975
году
им
была
опубликована
книга
"Adaptation
in
Natural
and
Artificial
Systems"
[Holland,
1975
]
.
Описание
ранней
истории
ГА
дано
в
книге
Д
.
Голдберга
"Genetic
Algorithms
in
Search,
Optimization
and
Machine
Learning"
[Goldberg,
1989
]
.
Джон Генри Холланд,
американский ученый, отец генетических алгоритмов
Ученых
заинтересовали
признаки
естественной
эволюции,
а
точнее
тот
факт,
что
эволюция
происходит
на
хромосомах,
а
не
на
живых
существах
.
Holland
верил,
что
введенный
в
компьютер
соответствующий
алгоритм,
может
дать
технологию
решения
трудных
проблем
по
аналогии
с
природой
±
через
эволюцию
.
Он
работал
над
алгоритмами,
оперирующими
с
рядами
бинарных
цифр
:
нулей
и
единиц,
которые
назвал
хромосомами
.
Эти
алгоритмы
производили
имитацию
эволюции
на
популяции
хромосом
и
использовали
механизмы
селекции
или
репродукции
аналогичные
процессам
присущим
естественной
эволюции
.
Такие
же
как
в
природе,
эти
алгоритмы
решали
проблемы
нахождения
"хороших"
хромосом,
ничего
не
зная
о
характере
проблемы,
которую
решали
.
Единственная
имевшаяся
в
распоряжении
компьютера
информация,
это
оценка
каждой
хромосомы,
отражающая
ее
приспособление
.
лассические генетические алгоритмы
Рассмотрим оптимизационную задачу. Для системы, представленной на рисунке необходимо определить: ешение оптимизационной задачи классическим генетическим алгоритмом
Простейшая система управления
Параметры
этой
задачи
-
и
.
Пространство
поиска
будет
содержать
конечное
множество
точек,
которые
можно
закодировать
индивидуумами
.
Параметры
и
-
дискретизированы
и
расположены
в
пределах
от
до
в
виде
соответствующих
бинарных
кодовых
рядов
.
При
этом
соответствует
кодовый
ряд,
состоящий
только
из
нулей,
а
-
кодовый
ряд,
включающий
одни
единицы
.
Длина
этих
кодовых
рядов
зависит
от
значений
и
,
а
также
от
частоты
дискретизации
интервала
.
Предположим,
что
=
-
25
,
а
=
25
и
для
параметров
,
применены
10
-
ти
битовые
кодовые
ряды
.
Тогда
популяция
для
данного
примера
состоит
из
семи
индивидуумов
и
представлена
в
табл
.
5
.
14
.
Первые
десять
генов
каждого
индивидуума
соответствуют
параметру
,
а
остальные
десять
-
параметру
.
Длина
индивидуума,
таким
образом,
равна
20
.
опуляция, хромосомы, гены, генотип, фенотип
Основной,
классический
генетический
алгоритм
называют
часто
также
и
простым
ГА
.
Он
состоит
из
следующих
шагов
:
1
)
инициализации,
т
.
е
.
выбора
начальной
популяции
индивидуумов
;
2
)
оценки
приспособленности
индивидуумов
в
популяции
;
3
)
проверки
условий
остановки
;
4
)
селекции
индивидуумов
;
5
)
применения
генетических
операторов
;
6
)
создания
новой
популяции
;
7
)
вывода
"наилучшего"
индивидуума
.
лок
-
схема классического генетического алгоритма
Инициализация
-
создание
начальной
популяции
.
Основано
на
выборе
разыгрыванием
заданного
числа
хромосом
(индивидуумов),
представленных
бинарными
кодами
определенной
длины
.
Оценка
приспособленности
индивидуумов
в
популяции
основана
на
вычислении
значения
функции
оценки
для
каждого
индивидуума
их
этой
популяции
.
Чем
больше
значение
функции,
тем
лучше
качество
индивидуума
.
Проверка
условий
останова
.
Останов
ГА
может
наступать,
если
дальнейшая
его
работа
уже
не
изменяет
значения
искомого
экстремума
.
Алгоритм
может
останавливаться,
по
истечении
некоторого
времени
работы
или
после
завершения
определенного
количества
выполненных
итераций
.
Если
условие
останова
выполнено,
то
наступает
переход
к
последнему
шагу,
т
.
е
.
вывод
"наилучшего"
индивидуума
.
Если
нет,
то
следующим
шаг
-
селекция
.
писание блок
-
схемы классического Селекция
индивидуумов
.
Основана
на
выборе,
по
значениям
функции
оценки,
тех
индивидуумов
-
родителей,
которые
будут
принимать
участие
в
создании
потомков
следующего
поколения
.
Этот
выбор
проходит
по
принципу
естественной
селекции,
т
.
е
.
наибольший
шанс
на
участие
в
создании
новых
индивидуумов
имеют
индивидуумы
с
наибольшими
значениями
функции
оценки
.
Существует
много
методов
селекции
.
Наиболее
популярный
из
них
±
метод
рулетки
.
Суть
его
состоит
в
том,
что
каждому
индивидууму
ставится
в
соответствие
сектор
колеса
рулетки
со
значением
пропорциональным
значению
функции
оценки
данного
индивидуума
.
Чем
больше
это
значение,
тем
больше
размер
сектора
на
колесе
рулетки
.
Все
колесо
рулетки
соответствует
сумме
значений
функции
оценки
всех
индивидуумов
из
популяции
для
решения
данной
задачи
.
Каждому
индивидууму,
обозначенному
,
где
N
-
численность
популяции,
соответствует
сектор
,
представляющий
собой
часть
всего
колеса,
выраженную
в
процентах
:
При этом обозначает значение функции оценки индивидуума , а -
вероятность выбора индивидуума . писание блок
-
схемы классического Выбор
индивидуума
-
следствие
оборота
колеса
рулетки
.
В
результате
"выигрывает"
индивидуум,
лежащий
в
разыгранном
этим
способами
секторе
колеса
рулетки
.
Очевидно
этот
сектор
тем
больше,
чем
больше
значение
функции
оценки
.
Если
вся
окружность
колеса
рулетки
будет
трактоваться
как
интервал
чисел
[
0
,
100
],
то
разыгрывание
индивидуума
можно
трактовать
как
разыгрывание
числа
из
интервала
[
a,
b
],
где
a
и
b
обозначают,
соответственно,
начало
и
конец
фрагмента
круга
соответствующего
этому
сектору
колеса
.
Очевидно,
что
.
Тогда
разыгрывание
с
помощью
колеса
рулетки
сводится
к
разыгрыванию
числа
из
интервала
[
0
,
100
]
,
которое
соответствует
конкретной
точке
на
окружности
колеса
рулетки
.
В
результате
селекции
создается
родительская
популяция
из
индивидуумов,
называемая
родительской
пулой
.
Она
и
становится
текущей
популяцией
на
очередном
шаге
работы
алгоритма
.
писание блок
-
схемы классического Применение
генетических
операторов
.
Применение
генетических
операторов
к
индивидуумам,
отобранным
методом
селекции,
используется
для
создания
новой
популяции
потомков
.
В
классическом
ГА
применяются
два
основных
генетических
оператора
:
скрещивания
(англ
.
crossover)
и
мутации
(англ
.
mutation)
.
Последний
играет
второплановую
роль
по
сравнению
с
оператором
скрещивания
.
Это
означает,
что
в
классическом
ГА
скрещивание
происходит
почти
всегда,
в
то
время
как
мутация
-
достаточно
редкое
явление
.
Вероятность
скрещивания
принимается
обычно
достаточно
большой
(
),
а
вероятность
мутации
маленькой
(
)
.
Это
соответствует
эволюции
в
живой
природе,
где
мутация
чрезвычайно
редкое
явление
.
писание блок
-
схемы классического Оператор
скрещивания
.
Первый
этап
скрещивания
-
выбор
пар
из
родительской
пулы
.
На
этом
этапе
индивидуумы
из
родительской
популяции
сочетаются
в
пары
.
Выбор
пары
происходит
случайно,
в
соответствии
с
вероятностью
скрещивания
.
Далее,
для
каждой
пары
выбранных
этим
способом
родителей,
разыгрывается
позиция
гена,
определяющая
так
называемую
точку
скрещивания
.
Если
индивидуумы
-
родители
состоят
из
L
генов,
то,
очевидно,
точку
скрещивания
можно
разыграть
как
значение
случайного
числа
равномерно
распределенного
на
интервале
[
1
,
L
-
1
]
.
В
результате
скрещивания
пары
родителей
получается
пара
потомков
по
следующему
правилу
:
1
)
один
п
отомок
складывается
из
генов
на
позициях
от
1
до
,
взятых
от
первого
родителя
и
остальных
генов,
от
позиции
+
1
до
L
,
взятых
от
второго
родителя
;
2
)
второй
потомок
складывается
из
генов
на
позициях
от
1
до
,
взятых
от
второго
родителя
и
остальных
генов,
от
позиции
+
1
до
L
,
взятых
от
первого
родителя
.
писание блок
-
схемы классического Оператор
мутации
.
В
соответствии
с
вероятностью
мутации,
значение
гена
индивидуума
изменяется
на
противоположное
(
0
→
1
или
1
→
0
)
.
Например,
если
в
индивидууме
[
100110101010
]
мутации
подвергся
ген
на
позиции
7
,
то
получим
следующую
хромосому
[
100110001010
]
.
Вероятность
мутации
очень
мала
и
возникает
в
соответствии
с
задаваемой
пользователем
вероятностью
мутации
.
Тогда
для
каждого
гена
разыгрывается
случайное
число
из
интервала
[
0
,
1
]
и,
если
СЧ
,
то
ген
мутирует
.
Создание
новой
популяции
.
Индивидуумы
получаемые
генетическими
операторами
из
индивидуумов
родительской
популяции
формируют
текущую
популяцию
для
новой
итерации
ГА
.
В
классическом
ГА
вся
предыдущая
популяции
индивидуумов
заменяется
на
новую
популяцию
потомков
той
же
самой
численности
.
Вывод
"наилучшего"
индивидуума
.
Если
выполнено
условие
останова
алгоритма,
необходимо
вывести
результат
.
Наилучшее
решение
задачи
-
индивидуум
с
наибольшим
значением
функции
оценки
в
популяции
.
писание блок
-
схемы классического Возьмем
упрощенный
и
немного
искусственный
пример,
нахождения
индивидуума
с
возможно
большим
числом
единиц
.
Предположим,
что
индивидуум
состоит
из
12
генов,
а
популяция
содержит
8
индивидуумов
.
Известно,
что
наилучшим
будет
индивидуум
из
12
единиц
.
Рассмотрим
поэтапно
решение
этой
тривиальной
задачи
с
помощью
ГА
.
Инициализация
.
Генерируем
восемь
бинарных
кодов
с
длиной
равной
12
и
тем
самым
получаем
начальную
популяцию
:
=
[
111001100101
],
=[
010001100100
],
=
[
001100111010
],
=[
010011000101
],
=[
011101110011
],
=[
101011011011
],
=
[
001000101000
],
=
[
000010111100
]
.
ример работы классического Оценка
приспосабливаемости
индивидуумов
в
популяции
.
Значения
функции
оценки
равны
числу
единиц
в
индивидууме
.
Обозначим
функцию
оценки
через
.
Тогда
ее
значения
для
хромосом
в
начальной
популяции
даны
ниже
:
Индивидуумы
характеризуются
наибольшими
значениями
функции
оценки
.
В
этой
популяции
они
наилучшие
кандидаты
на
то,
что
быть
решениями
задачи
.
Поскольку
условие
останова
не
выполнено,
то
следующий
шаг
-
селекция
индивидуумов
в
текущей
популяции
.
ример работы классического Селекция
.
Выполним
селекцию
методом
рулетки
.
Для
каждой
из
восьми
хромосом
текущей
популяции
(
N
=
8
)
имеем
сектора
колеса
рулетки,
выраженные
в
процентах
:
=
15
,
2
,
=
13
,
0
,
=
17
,
4
,
=
6
,
5
,
=
8
,
7
,
=
10
,
9
,
=
17
,
4
,
=
10
,
9
.
Далее
пусть
было
разыграно
восемь
чисел
:
79
,
44
,
9
,
74
,
44
,
86
,
48
,
23
.
Это
означает
выбор
для
репродукции
индивидуумов
:
Индивидуум
был
выбран
три
раза,
а
два
раза
.
Все
выбранные
индивидуумы
входят
в
родительскую
пулу
.
ример работы классического Применение
генетических
операторов
.
Предположим,
что
множество
индивидуумов,
разыгранных
с
помощью
оператора
селекции,
не
мутируют,
а
подлежат
скрещиванию
.
Это
означает,
что
вероятность
скрещивания
,
а
вероятность
мутации
.
Предположим,
что
среди
индивидуумов
,
,
,
,
,
,
,
разыгрыванием
выбраны
следующие
пары
родителей
:
(
и)
,
(и)
,
(и)
,
(и)
,
а
для
пар
разыграны
точки
скрещивания
,
,
,
,
соответственно
.
Тогда
скрещивание
будет
выполнено
в
соответствии
с
рисунком
и
в
результате
имеем
четыре
пары
потомков
.
ример работы классического Создание
новой
популяции
.
После
скрещивания
имеем
следующую
текущую
популяцию
потомков
:
=
[
001111011011
],
=
[
011101110010
],
=
[
101000111010
],
=
[
001000101001
],
=
[
111011011011
],
=
[
011101011011
],
=
[
101001100101
],
=
[
101011110011
]
.
Чтобы
отличить
индивидуумов
предыдущей
популяции
от
индивидуумов
новой
популяции,
последние
обозначены
звездочками
.
Далее,
в
соответствии
с
блок
-
схемой
ГА,
выполняется
шаг
2
,
т
.
е
.
оценка
приспосабливаемости
членов
новой
популяции,
которая
становится
текущей
.
Значения
функции
оценки
для
этой
популяции
следующие
:
=
8
,
=
6
,
=
9
,
=
6
,
=
7
,
=
4
,
=
8
,
=
8
.
Как
видно,
популяция
потомков
теперь
характеризуется
много
большим
средним
значением
функции
оценки,
чем
популяция
родителей
.
Предположим,
что
в
результате
скрещивания
найден
индивидуум
с
наибольшим
значением
функции
оценки,
которого
не
имел
ни
один
из
родителей
.
Чтобы
не
продолжать
итерации,
пусть
и
станет
решением
задачи
.
ример работы классического абота генетического алгоритма над задачей безусловной оптимизации
сновы теории массового обслуживания
Большинство
систем,
с
которыми
человек
имеет
дело
-
стохастические
.
Попытка
их
математического
описания
с
помощью
детерминистических
моделей
приводит
к
огрублению
истинного
положения
вещей
.
При
решении
задач
анализа
и
проектирования
таких
систем
приходится
считаться
с
тем,
что
случайность
является
определяющей
для
процессов,
протекающих
в
системах
.
При
этом
пренебрежение
случайностью,
попытка
³втиснуть´
решение
перечисленных
задач
в
детерминистические
рамки
приводит
к
искажению,
к
ошибкам
в
выводах
и
практических
рекомендациях
.
Первые
задачи
теории
систем
массового
обслуживания
(ТМО)
были
рассмотрены
сотрудником
Копенгагенской
телефонной
компании,
датским
ученым
А
.
К
.
Эрлангом
в
период
между
1908
и
1922
гг
.
Эти
задачи
были
вызваны
к
жизни
стремлением
упорядочить
работу
телефонной
сети
и
разработать
методы,
позволяющие
заранее
повысить
качество
обслуживания
потребителей
в
зависимости
от
числа
используемых
устройств
.
Оказалось,
что
ситуации,
на
телефонных
станциях
±
типичные
и
для
аэродромов,
морских
и
речных
портов,
магазинов,
терминальных
классов,
электронных
вычислительных
комплексов,
радиолокационных
станций
и
т
.
д
.
могут
быть
описаны
в
рамках
ТМО
.
Примерно
80
%
всех
систем
±
это
системы
массового
обслуживания
.
Пример
1
.
Телефонная
связь
времен
Эрланга
представляла
из
себя
телефонную
станцию,
связанную
с
большим
числом
абонентов
.
Телефонистки
станции
по
мере
поступления
вызовов
соединяли
телефонные
номера
между
собой
.
Задача
:
Какое
количество
телефонисток
(при
условии
их
полной
занятости)
должно
работать
на
станции
для
того,
чтобы
потери
требований
были
минимальными
.
Пример
2
.
Система
скорой
помощи
некоего
городского
района
представляет
собой
пункт
(который
принимает
требования
на
выполнение),
некоторое
количество
автомашин
скорой
помощи
и
несколько
врачебных
бригад
.
Задача
:
Определить
количество
врачей,
вспомогательного
персонала,
автомашин,
для
того
чтобы
время
ожидания
вызова
было
для
больных
оптимальным
при
условии
минимизации
затрат
на
эксплуатацию
системы
и
максимизации
качества
обслуживания
.
Пример
3
.
Важной
задачей
является
организация
морских
и
речных
перевозок
грузов
.
При
этом
особое
значение
имеют
оптимальное
использование
судов
и
портовых
сооружений
.
Задача
:
Обеспечить
определенный
объем
перевозок
при
минимальных
расходах
.
При
этом
сократить
простои
судов
при
погрузочно
-
разгрузочных
работах
.
сновы теории массового обслуживания
Входящий поток
Поток событий
«Приход заявки»
Поток событий
«Уход заявки»
Выходящий поток
Очередь
Обслуживающий прибор
Дисциплина очереди
-
Случайная величина «Интервал между приходами двух очередных заявок»
-
Случайная величина «Время обслуживания заявки прибором»
онятие Потоком называют последовательность событий. Поток, состоящий из требований на обслуживание, называют потоком требований.
Поток требований, поступающих в обслуживающую систему, называют входящим потоком.
Поток требований, которые обслужены, называют выходящим потоком.
Совокупность очередей и приборов (каналов) обслуживания называются системой обслуживания.
Каждые требования поступают на свой канал, где подвергается операции обслуживания.
Каждая СМО имеет определенные правила формирования очереди и правила или дисциплину обслуживания.
пределения, термины
СМО различают:
По дисциплине обслуживания:
обслуживание в порядке поступления;
обслуживание в случайном порядке (в соответствии с заданным законом распределения);
обслуживание с приоритетом.
По характеру организации:
с отказами;
с ожиданиями в очереди;
По количеству обслуживающих приборов:
одноканальные;
многоканальные.
лассификация Основная
задача
ТМО
-
установление
зависимости
между
характером
потока
заявок
на
входе
СМО,
производительностью
одного
канала,
числом
каналов
и
эффективностью
обслуживания
.
В качестве критерия эффективности могут быть использованы различные функции и величины:
среднее время простоя системы;
среднее время ожидания в очереди;
закон распределения длительности ожидания требования в очереди;
средний % заявок, получивших отказ; и т.д.
Современная
ТМО
является
совокупностью
аналитических
методов
исследования
перечисленных
разновидностей
СМО
.
сновная задача теории массового обслуживания
Входящий поток
Выходящий поток
Очередь
Обслуживающий прибор (канал)
одель одноканальной экспоненциальной Одноканальная
система
массового
обслуживания
(СМО)
задается
следующими
свойствами
.
СМО
имеет
канал
.
В
СМО
приходят
заявки
.
Если
СМО
пустая
(нет
заявок),
то
приходящая
заявка
занимает
канал
.
Заявка,
приходящая
в
непустую
СМО
(канал
занят),
становится
в
очередь
к
каналу
.
Любая
заявка,
занявшая
канал,
обслуживается,
освобождает
канал
и
уходит
из
СМО
.
Если
в
момент
ухода
очередь
не
пустая,
то
первая
в
ней
заявка
выходит
из
очереди
и
занимает
канал
.
В
экспоненциальной
СМО
приходы
заявок
образуют
пуассоновский
поток
событий
.
Это
означает,
что
время
между
приходами
любых
двух
последовательных
заявок
есть
такая
независимая
случайная
величина,
которая
имеет
экспоненциальное
распределение
вероятностей
.
Кроме
того,
в
экспоненциальной
СМО
время
обслуживания
заявок
также
распределено
экспоненциально
.
Таким
образом,
в
экспоненциальной
СМО
функция
распределения
вероятностей
случайных
величин
и
имеет
следующий
вид
:
где -
параметр распределения.
Функция плотности вероятности
Функция распределения
уассоновский поток событий
Параметр
λ
есть
величина,
обратная
математическому
ожиданию
распределения
.
Следовательно,
для
случайной
величины
параметр
λ
равен
и
представляет
собой
интенсивность
поступления
заявок,
т
.
е
.
среднее
число
заявок,
приходящих
в
единицу
времени
(
-
среднее
время
между
приходами
двух
очередных
заявок
в
СМО)
.
Для
случайной
величины
параметр
λ
равен
и
представляет
интенсивность
обслуживания
заявок
(
-
среднее
время
обслуживания
заявки
каналом)
.
В
дальнейшем
интенсивность
обслуживания
заявок
в
СМО
будем
обозначать
через
μ
.
Цель
анализа
СМО
заключается
в
расчете
ее
характеристик
,
важнейшие
из
которых
следующие
:
-
коэффициент загрузки
ρ
;
-
средняя длина очереди
L
;
-
среднее число заявок в СМО
M ;
-
среднее время ожидания обслуживания
W
;
-
среднее время пребывания заявки в СМО
U
.
уассоновский поток событий
Цель анализа Коэффициент
загрузки
рассчитывается
по
формуле
:
Если
выполняется
условие
ρ
≤
1
(«физический
смысл»
этого
требования
состоит
в
том,
чтобы
«скорость
поступления
работы»
в
систему
не
превышала
«скорости
ее
выполнения»
системой),
то
существует
стационарный
режим
функционирования
СМО
.
В
стационарном
режиме
такие
вероятностные
характеристики
происходящих
в
СМО
процессов,
как
L,
М,
W,
U
не
зависят
от
времени,
т
.
е
.
являются
постоянными
величинами
.
Сами
происходящие
в
СМО
процессы
остаются
при
этом
случайными
.
Если
соотношение
для
ρ
не
выполняется,
то
стационарного
режима
в
СМО
не
существует
.
Действительно,
если
ρ
>
1
,
то,
как
вытекает
из
(
2
),
>
1
,
т
.
е
.
,
или,
что
то
же
самое,
λ
>
μ
.
Это
значит,
что
интенсивность
поступления
заявок
в
СМО
при
ρ
>
1
превышает
интенсивность
их
обслуживания
каналом
(канал
обслуживает
заявки
в
среднем
медленнее,
чем
те
поступают)
.
Поэтому
длина
очереди
заявок
будет
возрастать
каждую
единицу
времени
в
среднем
на
величину
(λ
-
μ
)
.
Со
временем
очередь
будет
постоянно
возрастать
и
стационарного
значения
у
средней
длины
очереди
не
будет
.
асчет коэффициента загрузки В
стационарном
режиме
среднее
число
M
заявок
в
СМО
постоянно
.
Поэтому
среднее
число
заявок,
поступающих
в
СМО
в
единицу
времени,
равно
среднему
числу
заявок,
в
единицу
времени
из
СМО
уходящих
.
Следовательно,
в
стационарном
режиме
интенсивность
потока
уходящих
заявок
равна
λ
.
Эта
величина
меньше,
чем
интенсивность
обслуживания
μ,
т
.
к
.
канал
в
стационарном
режиме
определенную
долю
времени
простаивает
.
Эта
доля
времени
равна
(
1
-
ρ
)
-
коэффициенту
простоя
СМО
.
Интенсивность
выходного
потока
заявок
равна
интенсивности
обслуживания,
когда
канал
занят,
и
равна
нулю,
когда
канал
свободен
.
В
среднем
же
она
равна
интенсивности
поступления
заявок
.
Поэтому
среднее
число
заявок
в
СМО
в
стационарном
режиме
со
временем
не
изменяется,
остается
постоянным
.
асчет коэффициента загрузки Коэффициент загрузки
ρ
в стационарном режиме можно интерпретировать следующими способами:
а) как среднее значение той части единицы времени, в течение которой канал занят;
б)
как
вероятность
застать
канал
занятым
при
обращении
к
нему
в
случайный
момент
времени
;
в) как среднее число заявок в канале.
В
экспоненциальной
СМО,
коэффициент
загрузки
равен
также
вероятности
того,
что
приходящая
в
СМО
заявка
застанет
канал
занятым
.
Далее рассматриваем только стационарные значения
характеристик.
редняя
длина
очереди
L
(среднее
число
заявок
в
очереди)
в
одноканальной
экспоненциальной
СМО
рассчитывается
по
формуле
:
График
зависимости
L
(ρ)
приведен
на
рисунке
.
Среднее
число
M
заявок
в
СМО
равно
сумме
среднего
числа
L
заявок
в
очереди
и
среднего
числа
r
заявок
в
канале
:
где r
-
среднее число заявок в канале.
редняя длина очереди
Действительно, как видно из рисунка видно, что число заявок в СМО складывается из числа заявок в очереди и числа заявок в канале. И, поскольку среднее значение суммы чисел равно сумме их средних, то отсюда получается соотношение для N
.
Зная
среднее
число
заявок
в
какой
-
либо
части
системы,
можно
легко
определить
и
среднее
время
пребывания
заявок
в
этой
части
.
Данные
средние
величины
связаны
знаменитой
формулой
Литтла
,
которая
представляет
собой
своеобразный
«закон
природы»
для
систем
массового
обслуживания
любого
вида,
не
обязательно
только
экспоненциальных
:
где -
интенсивность поступления заявок в выделенную часть системы,
-
среднее время пребывания заявки в этой части,
-
среднее число заявок в ней.
Поскольку
в
стационарном
режиме
среднее
число
заявок
в
заданной
области
системы
постоянно,
то
в
среднем
число
заявок,
поступающих
в
нее
в
единицу
времени,
т
.
е
.
,
равно
числу
заявок,
уходящих
из
нее
в
единицу
времени,
т
.
е
.
.
При
этом
интенсивность
ухода
заявок
складывается
из
интенсивностей
ухода
каждой
из
заявок,
т
.
е
.
.
Отсюда
получаем
-
т
.
е
.
формулу
Литтла
.
Формула иттла
Применяя
формулу
Литтла
к
очереди
в
СМО,
находим
среднее
время
ожидания
обслуживания
через
среднюю
длину
очереди
:
Аналогично вычисляется среднее время пребывания заявки во всей СМО:
Если
учесть,
что
время
прохождения
заявки
через
СМО
складывается
из
времени
ее
прохождения
через
очередь
и
времени
обслуживания
в
канале,
то
величину
U
можно
вычислить
и
как
сумму
соответствующих
средних
времен
:
рименение формулы иттла
Автор
EscapadO
Документ
Категория
Презентации
Просмотров
1 019
Размер файла
6 952 Кб
Теги
лекцииисоnew2
1/--страниц
Пожаловаться на содержимое документа