Э.А. Кравцова
Информационные совокупности в способах оптимизации
Методические указания
по исполнению практических занятий
Дисциплина – «Способы оптимизации»
Профессии – 230700.62 «Прикладная информатика», 231000.62 «Программная инженерия», 230400.62 «технологии и Информационные системы», 080801«Прикладная информатика (в экономике)»,230105 «ПО вычислительной техники и автоматизированных совокупностей», 230100.62 «Информатика и вычислительная техника»
Допущено ФГБОУ ВПО «Госуниверситет-УНПК» для применения в учебном ходе в качестве методических указаний для высшего профобразования
Орел 2013
Авторы: старший учитель кафедры ИС Э.А.Кравцова
Критик: к.т.н., доцент кафедры ИС О. В. Конюхова
Методические указания содержат описание пяти практических занятий по дисциплине «Способы оптимизации». Они посвящены выработке у студентов навыков разработки математических и информационных моделей процессов в предметной области; и содействуют приобретению навыков экспериментальных изучений при выборе способа оптимизации, так же при ответе типовых оптимизационных задач. Методические указания содержат теоретические сведения по разглядываемым вопросам, практические примеры и справочную данные, нужную для исполнения лабораторных работ.
Методические указания предназначены для студентов очной формы обучения профессий 230700.62 «Прикладная информатика», 231000.62 «Программная инженерия», 230400.62 «технологии и Информационные системы», 080801«Прикладная информатика (в экономике)»,230105 «ПО вычислительной техники и автоматизированных совокупностей», 230100.62 «Информатика и вычислительная техника».
Редактор
Технический редактор
Орловский национальный технический университет
Лицензия ИД 00670 от 5.01.2000
Подписано к печати Формат 60 84 1\16
Печать офсетная. Усл. печ. л.5,6. Тираж 10 экз.
Заказ №__________
Отпечатано с готового оригинал-макета
на полиграфической базе ФГБОУ ВПО «Госуниверситет — УНПК»
© ФГБОУ ВПО «Госуниверситет — УНПК», 2012
© Кравцова Э.А. 2013
СОДЕРЖАНИЕ
1.Линейное программирование: симплекс – способ 4
2.Особые задачи линейного программирования 19
3. Ответ целочисленных задач 23
4. Ответ задач многокритериальной оптимизации 27
5. Сетевая модель, расчет главных параметров сетевого графика 31
6.Теория игр 48
Литература 54
Практическое занятие №1
Линейное программирование: симплекс-способ ответа задач линейного программирования, геометрическая интерпретация задач
Практическое занятие №2
10)
| В А | ||||
Практическое занятие №3
Ответ задач по нелинейной оптимизации. Способ множителей Лагранжа.
Практическое занятие №4
Сетевая модель, расчет главных параметров сетевого графика.
Построение сетевого графика
Сетевые графики являются ориентированные графы, дугам либо вершинам которых приписаны кое-какие числовые значения.
В большинстве случаев, вершины, именуемые событиями, соответствуют моментам времени начала либо окончания одной либо нескольких операций, а дуги – операциям.
Различают три вида событий: исходное, завершающее и промежуточное. Исходное – это такое событие, с которого начинается исполнение комплекса операций. Завершающее соответствует достижению конечной цели, т. е. завершению комплекса операций. Сетевые графики с несколькими завершающими событиями именуются многоцелевыми. К промежуточным относятся все другие события.
События, в большинстве случаев, обозначаются кружками. Предполагается, что события не имеют длительности во времени.
Моментом свершения события считается момент окончания исполнения всех входящих в это событие операций. Пока не выполнены все входящие в событие операции, не имеет возможности свершиться само событие, и не может быть начата ни одна из конкретно следующих за ним операций.
Различают три вида операций:
1) настоящая операция ( ) – процесс, требующий затрат времени и ресурсов (разработка проекта, подвоз материалов, исполнение монтажных работ и т. д.);
2) операция — ожидание ( ) – процесс, требующий лишь затрат времени (затвердение бетона, естественная сушка штукатурки перед началом малярных работ, рост растений и т. д.);
3) фиктивная операция ( ), либо логическая зависимость, отражает технологическую либо ресурсную зависимость в исполнении некоторых операций.
При построении сетевых графиков нужно выполнять определенные правила:
1) в сети не должно быть событий (не считая исходного), в каковые не входит ни одна дуга;
2) не должно быть событий (не считая завершающего), из которых не выходит ни одной дуги;
3) сеть не должна содержать контуров;
4) каждая пара событий сетевого графика возможно соединена не более чем одной дугой. В случае, если изобразить в один момент делаемые три разные операции , , с неспециализированными начальным и конечным событиями (Рис. 4.1), то появляется путаница по причине того, что разные операции имеют одно да и то же обозначение (2,5). В этом случае рекомендуется ввести дополнительные события и соединить их с последующими фиктивными операциями (Рис. 4.2);
Рис. 4.1
5) номер начального события любой операции должен быть меньше номера ее конечного события.
Для отражения технологической либо ресурсной зависимости в исполнении операций используют фиктивные операции. Предположим, что операция может выполняться по окончании завершения операций и , а операция – лишь по окончании завершения операции .
Рис. 4.2
Эта зависимость представлена на Рис. 4.3, из которого видно, что операция следует за фиктивной операцией и операцией (2,З).
 |
Рис. 4.3
Со своей стороны, операция (2,3) следует за операцией . Тогда в силу транзитивности исполнение операции предшествует исполнению операции .
Построение сетевого графика начинается с составления перечня операций (работ), подлежащих исполнению. Последовательность операций в перечне есть произвольной. Порядок нумерации операций осуществляется в соответствии с последовательностью их записи в перечне. Список операций в зависимости от конкретных условий детализируется. Операции, включенные в перечень, характеризуются определенной длительностью, которая устанавливается на базе действующих нормативов либо по аналогии с ранее выполнявшимися операциями. Такие временные оценки именуются детерминированными. При отсутствия нормативных временных оценок определяются вероятностные оценки.
По окончании составления перечня операций приступают к процедуре построения сети.
Приведем пример построения несложного сетевого графика. Разглядим проект, представленный посредством следующей таблицы:
Таблица 4.1.
Описание составных работ проекта
| Работа | Конкретно предшествующие работы | Время исполнения |
| A | — | |
| B | — | |
| C | B | |
| D | A, C | |
| E | C | |
| F | C | |
| G | D, E, F |
Анализ данных, приведенных в данной таблице, взаимозависимости и последовательности работ, разрешает выстроить сетевой график представленный на рис. 4.4.
Рис. 4.4
В данном сетевом графике кроме работ, указанных в таблице, использованы две фиктивные работы (3,4) и (5,6), обозначенные штриховыми линиями. Эти работы не требуют времени на их исполнение и употребляются в графическом представлении проекта только чтобы верно отобразить связь между работами.
Практическое занятие №5
Неспециализированные сведения
Раздел математики, изучающий конфликтные обстановки на базе их математических моделей, именуется теорией игр. Возможно кроме этого заявить, что теория игр — математическая теория конфликтных обстановок, разрабатывающая советы по самый рациональному образу действий каждого из участников на протяжении конфликтной обстановке, т.е. таких действий, каковые снабжали бы ему отличных показателей.
Игровые схемы возможно использовать во многих экономических обстановках. Выигрышем смогут наряду с этим выступать величина прибыли, себестоимость, эффективность применения дефицитных ресурсов, производственных фондов, и т.д.
Значительным событием есть то, что рекомендации и методы теории игр созданы применительно к таким конфликтным обстановкам, каковые владеют свойством многократной повторяемости. В случае, если конфликтная обстановка реализуется однократно либо ограниченное число раз, то советы теории игр становятся малоэффективными.
Анализ настоящей конфликтной обстановке требует ее значительного (время от времени радикального) упрощения – учета только самые существенных для конфликта факторов. Поэтому, возможно разглядывать игру как упрощенную математическую модель конфликтной обстановке, характеризующуюся наличием определенных правил. Эти правила устанавливают:
1. выбор образа действия игроков на каждом этапе игры;
2. данные, которой владеет любой игрок при осуществлении таких выборов;
3. плату для каждого игрока по окончании завершения любого этапа игры.
Стратегией игры именуется совокупность правил, определяющих поведение игрока в течении всей игры. Стратегии каждого игрока определяют результаты либо платежи в игре; наряду с этим любой игрок имеет некое множество (конечное либо нескончаемое) вероятных стратегий.
К числу определяющих черт игр возможно отнести следующие:
1. имеется конфликтующих сторон (игроков), принимающих ответы, интересы которых не совпадают;
2. сформулированы правила выбора допустимых стратегий, узнаваемые игрокам;
3. выяснен комплект вероятных конечных состояний игры (к примеру, выигрыш, проигрыш, ничья);
4. всем участникам игры (игрокам) заблаговременно известны платежи, соответствующие каждому вероятному конечному состоянию.
Конфликтные обстановки, видящиеся в практике, порождают разные виды игр. Классификация игр вероятна по различным показателям.
А) По количеству игроков. В игре может учавствовать любое конечное число игроков. В случае, если игроков всего двое, либо игроки объединяются в две группы, преследующие противоположные цели, то имеет место парная игра. В зависимости от количества стратегий в игре они делятся на конечные и нескончаемые.
Б) В зависимости от взаимоотношений участников различают бескоалиционные (участники не имеют права заключать соглашения) и коалиционные игры (время от времени употребляются синонимы – некооперативные и кооперативные игры соответственно).
В) По характеру выигрышей игры делятся на игры с нулевой и ненулевой суммой . В играх с нулевой суммой неспециализированный капитал игроков не изменяется, а только перераспределяется на протяжении игры, в связи с чем сумма выигрышей равна нулю (наряду с этим проигрыш рассматривается как отрицательный выигрыш). В играх с ненулевой суммой сумма выигрышей хороша от нуля.
Г) По виду функции выигрыша игры делятся на матричные, биматричные и др. В матричных играх (при двух участниках) выигрыши первого игрока задаются матрицей, в биматричных – выигрыши каждого игрока задаются собственной матрицей.
Д) По количеству ходов игры делятся на одноходовые (выигрыш распределяется по окончании одного хода каждого игрока) и многоходовые (выигрыш распределяется по окончании нескольких ходов).
Стратегия игрока именуется оптимальной, если она снабжает данному игроку при многократном повторении игры максимальный средний выигрыш либо минимально вероятный средний проигрыш, независимо от поведения соперника.
В будущем мы ограничимся рассмотрением парных матричных игр с нулевой суммой. Задание стратегий двух игроков в парной игре для того чтобы типа абсолютно определяет ее финал, т.е. выигрыш одного либо проигрыш другого. Как уже отмечалось, результаты конечной парной игры с нулевой суммой возможно задавать матрицей, строки и столбцы которой соответствуют разным стратегиям 1-го и 2-го игроков соответственно, а ее элементы — выигрышам одной стороны (равные проигрышам второй). Эта матрица именуется платежной матрицей либо матрицей игры.
Игры без седловых точек
Итак, в случае, если матрица игры содержит седловую точку, то ее ответ находится по принципу минимакса. Разглядим методику ответа игры, в платежной матрице которой отсутствует седловая точка. Использование минимаксных стратегий каждым из игроков снабжает первому выигрыш не меньше , а второму проигрыш не больше . Учитывая, что , конечно для игрока I желание расширить выигрыш, а для игрока II – уменьшить проигрыш. Поиск для того чтобы решения ведет к применению сложной стратегии, пребывающей в случайном применении двух и более чистых стратегий с определенными возможностями. Такая сложная стратегия в теории игр именуется смешанной. Смешанные стратегии игроков I и II будем обозначать, соответственно,
и
где , ? возможности применения соответствующих чистых стратегий. Разумеется, должны быть выполнены условия нормировки для возможностей
Одна из главных теорем теории игр говорит, что каждая конечная игра двух лиц с нулевой суммой имеет, по крайней мере, одно ответ, быть может, в смешанных стратегиях. Из данной теоремы направляться, что любая конечная игра имеет цену. Обозначим ее так же, как чистую цену игры, через . Цена игры – средний выигрыш, приходящийся на одну партию, – постоянно удовлетворяет условию , т.е. лежит между нижней ( ) и верхней ( ) стоимостями игры. Следовательно, любой игрок при многократном повторении игры, придерживаясь смешанных стратегий, приобретает более удачный для себя итог. Оптимальное ответ игры в смешанных стратегиях, так же как и ответ в чистых стратегиях, характеризуется тем, что любой из игроков не заинтересован в отходе от собственной оптимальной смешанной стратегии, в случае, если его соперник использует оптимальную смешанную стратегию, поскольку это ему невыгодно.
Стратегии игроков, входящие в их оптимальные смешанные стратегии, именуются активными.
5.5 Применение линейной оптимизации при ответе матричных игр
Пускай игра не имеет оптимального ответа в чистых стратегиях, т.е. седловая точка отсутствует .
Будем вычислять, что все элементы платежной матрицы неотрицательны (в случае, если это не верно, то возможно ко всем элементам матрицы добавить некое число L, переводящее платежи в область неотрицательных значений — разумеется, наряду с этим цена игры увеличится на L, а ответ задачи не изменится). Так, предполагаем, что 0.
Будем искать ответ игры в смешанных стратегиях
;
Использование игроком I оптимальной смешанной стратегии гарантирует ему, независимо от поведения игрока II, выигрыш, не меньший цены игры .
Пускай игрок II использует собственную активную чистую j-ю стратегию, а игрок I – собственную оптимальную стратегию . Тогда средний выигрыш игрока I будет равен
Учитывая, что не может быть меньше , запишем условия:
(5.4)
Поделив левую и правую части каждого из неравенств (5.4) на цену игры , возьмём
(5.5)
При применении обозначений
(5.6)
неравенства (5.5) примут вид
где, разумеется, все , так как .
Из равенства
и в силу определения (5.6) направляться, что переменные ( ) удовлетворяют условию
Учитывая, что игрок I пытается максимизировать , приобретаем линейную функцию
(5.8)
Так, задача ответа игры свелась к следующей задаче линейной оптимизации: отыскать неотрицательные значения переменных минимизирующие линейную функцию (5.8) и удовлетворяющие ограничениям (5.7).
Из решения задачи линейной оптимизации легко отыскать оптимальную стратегию и цену игры игрока I:
Со своей стороны, оптимальная стратегия игрока II
возможно отыскана из выражения
где — неотрицательные переменные задачи линейной оптимизации
которая есть двойственной по отношению к задаче, представленной условиями (5.7) и (5.8).
В данной совокупности неравенств переменные
Так, оптимальные стратегии
и
игры с платежной матрицей ( ) смогут быть отысканы методом решения симметричной пары двойственных задач линейной оптимизации.
Исходная задача Двойственная задача
вероятности применения и Цена игры стратегий игроками I и II равны
5.6 Задачи для независимого ответа
Методом сведения двойственных задач линейного программирования отыскать оптимальные смешанные стратегии и цену игры матричных игр с этими платежными матрицами:
| 1) | -8 | 2) | -2 | -5 | 3) | -1 | 4) | -6 | 5) | -3 | ||||
| -8 | -4 | -4 | -3 | -1 |
| 6) | -3 | 7) |  |
-1 | 9) | -1 | |||||||||
| -5 | -3 | -1 | |||||||||||||
| -9 | -1 | -2 | -3 |
ЛИТЕРАТУРА
1. Сборник задач по высшей математике для экономистов: Учебное пособие /Под ред. В.И.Ермакова. – М.: ИНФРА-М, 2001 (и поздние издания)
2. Кузнецов А.В., Мороз Н.И., Костевич Л.С. Управление к ответу задач по математическому программированию.– Мн: Вышэйшая школа,2001
3. Налбандян Ю.С. Управление к ответу задач по линейной алгебре. Способ. указания для студентов профессии «Менеджмент организаций». — Ростов-на-Дону: 2007.
4. Неспециализированный курс высшей математики для экономистов: Учебник/Под ред. В.И.Ермакова. – М.: ИНФРА-М, 2000 (и поздние издания).
5. Изучение операций в экономике / Под ред. Н.Ш.Кремера – М.: ЮНИТИ, 1997 (и поздние издания).
6. Солодовников А.С., Бабайцев П.А., Браилов А.В Математика в экономике. Ч.1. М.: статистика и Финансы, 2001
Э.А. Кравцова
Информационные совокупности в способах оптимизации
Методические указания
по исполнению практических занятий
Дисциплина – «Способы оптимизации»
Профессии – 230700.62 «Прикладная информатика», 231000.62 «Программная инженерия», 230400.62 «технологии и Информационные системы», 080801«Прикладная информатика (в экономике)»,230105 «ПО вычислительной техники и автоматизированных совокупностей», 230100.62 «Информатика и вычислительная техника»
Допущено ФГБОУ ВПО «Госуниверситет-УНПК» для применения в учебном ходе в качестве методических указаний для высшего профобразования
Орел 2013
Авторы: старший учитель кафедры ИС Э.А.Кравцова
Критик: к.т.н., доцент кафедры ИС О. В. Конюхова
Методические указания содержат описание пяти практических занятий по дисциплине «Способы оптимизации». Они посвящены выработке у студентов навыков разработки математических и информационных моделей процессов в предметной области; и содействуют приобретению навыков экспериментальных изучений при выборе способа оптимизации, так же при ответе типовых оптимизационных задач. Методические указания содержат теоретические сведения по разглядываемым вопросам, практические примеры и справочную данные, нужную для исполнения лабораторных работ.
Методические указания предназначены для студентов очной формы обучения профессий 230700.62 «Прикладная информатика», 231000.62 «Программная инженерия», 230400.62 «технологии и Информационные системы», 080801«Прикладная информатика (в экономике)»,230105 «ПО вычислительной техники и автоматизированных совокупностей», 230100.62 «Информатика и вычислительная техника».
Редактор
Технический редактор
Орловский национальный технический университет
Лицензия ИД 00670 от 5.01.2000
Подписано к печати Формат 60 84 1\16
Печать офсетная. Усл. печ. л.5,6. Тираж 10 экз.
Заказ №__________
Отпечатано с готового оригинал-макета
на полиграфической базе ФГБОУ ВПО «Госуниверситет — УНПК»
© ФГБОУ ВПО «Госуниверситет — УНПК», 2012
© Кравцова Э.А. 2013
СОДЕРЖАНИЕ
1.Линейное программирование: симплекс – способ 4
2.Особые задачи линейного программирования 19
3. Ответ целочисленных задач 23
4. Ответ задач многокритериальной оптимизации 27
5. Сетевая модель, расчет главных параметров сетевого графика 31
6.Теория игр 48
Литература 54
Практическое занятие №1