Информационни системи в техники за оптимизация

методически указания
за изпълнението на практическото обучение

Дисциплина - "Методи за оптимизация"

Специалности - 230700.62 "Приложна информатика", 231000.62 "Софтуерно инженерство", 230400.62 "Информационни системи и технологии", 080801 "Приложна информатика (в икономиката)," 230105 "Софтуер на компютърна техника и автоматизирани системи", 230100.62 "Компютърни науки и инженерство"

Одобрен VPO "State University-UNPK" за използване в учебния процес като насоки за висше професионално образование

Рецензент: Ph.D. Доцент, катедра Е. О. В. Konyuhova

Методически указания съдържат описание на пет работни семинара по темата "оптимизация". Те са посветени на развитието на умения на студентите в разработването на математически модели на процеси и информация в областта на обект; както и да допринесе за придобиване на умения за експериментално изследване при избора на метод за оптимизация, както и в решаването на проблеми, типични за оптимизация. Инструкции съдържат теоретична информация по въпросите, практически примери и допълнителна информация, необходима за лабораторна работа.

Насоки са предназначени за редовни студенти специалност 230700.62 "Приложна информатика", 231000.62 "Софтуерно инженерство", 230400.62 "Информационни системи и технологии", 080801 "Приложна информатика (в икономиката)," 230105 "Софтуер на компютърни съоръжения и автоматизирани системи" 230100.62 "Компютърни науки и инженерство".

Орел държавен технически университет

Подписано с формата на печат от 60 84 1 \ 16

Офсетов печат. Дир. Печ. l.5,6. Тираж 10 екземпляра.

Отпечатано с готовия оригинално разположение

печат на основата на VPO "State University - ESPC»

1.Lineynoe програмиране: симплекс - метод 4

2.Spetsialnye линейното програмиране проблем 19

3. С решението за проблемите целочислени 23

4. решаване на няколко критерия за оптимизация 27 Проблем

5. мрежа модел, изчисляване на основните параметри на графика мрежа 31

Практически урок №1

Линейно програмиране: симплекс метод за решаване на линейни програмни проблеми, геометрични проблеми при тълкуването

№2 практически урок

Практически урок №3

Решението за нелинейни оптимизационни задачи. метод на Лагранж множител.

Практически урок №4

Мрежа модел, изчисляване на основните параметри на схемата на мрежата.

Изграждане на мрежа график

Мрежа диаграми са насочени графики, дъги или върховете на които се приписват на някои числени стойности.

Обикновено на върха, наречена събитията съответстват на часовете, в началото или в края на една или повече сделки и дъгата - операции.

Има три вида събития: първоначално, междинни и за прекратяване. Original - това е събитие, което започва изпълнението на сложни операции. Закриване съответства на крайната цел, т.е.. Е. Завършването на сложни операции. Мрежови диаграми с няколко окончателно събитие наречени многоцелеви. За междинно съединение включва всички други събития.

Събития обикновено са обозначени с кръгове. Предполага се, че събитията не са с продължителност във времето.

Счита се, че моментът на събитие за изпълнение, за да бъде в края на изпълнението на всички членове в случай на операции. До всички членове на операциите на събитието не може да се случи на самото събитие, и поради това не може да се стартира, никой от тях веднага след операцията.

Има три вида операции:

1) действителната работа () - процес, който изисква време и ресурси (формулиране Доставка на материали, Строителни и монтажни работи и т.н.) ..

2) операция - чака () - процес, който изисква време отнема само (втвърдяване на бетона, мазилка естествено сушене преди боядисване операции, растежа на растенията, и т.н.) ..

3) работа сляпо (), или логическа зависимост отразява технологичния ресурс или зависимост при изпълнение на определени операции.

При изграждането на графиците на мрежата трябва да следват определени правила:

1) в мрежата трябва да бъде Няма събития (различни от оригинала), които не са включени във всяка една дъга;

2) не трябва да бъде събития (с изключение на финала), на които не надвишават някоя от дъгата;

3) Мрежата не съдържат вериги;

4) всяка двойка на графика мрежа от събития, могат да бъдат свързани не повече от една дъга. Ако ние представляваме едновременно изпълнява три различни операции. , с обща начална и крайна събития (фиг. 4,1), след това объркване произтича от факта, че различните операции са същите означението (2.5). В този случай се препоръчва да се въвеждат допълнителни събития и свързването им със следните фиктивни операции (фигура 4.2.);

5) на броя на първоначалните мероприятия на всяка операция трябва да бъде по-малък от броя на окончателния си събитие.

За да се отрази на технологични или ресурсни зависимости при изпълнение на операциите, използвани фиктивно на работа. Да приемем, че операцията може да се извърши след приключване на операциите и. експлоатация и - само след приключване на работата.

Тази зависимост е показана на Фиг. 4.3, което показва, че операцията след операцията и сляпо операцията (2, В).

Анализ на данните, показани в таблицата, работната последователност и взаимната зависимост позволява да се изгради мрежа графиката, показана на фиг. 4.4.

Информационни системи в техники за оптимизация

В допълнение към тази мрежа график работата, посочен в таблицата, две сляпо работа бяха използвани (3.4) и (5.6), обозначено с пунктирана линия. Тези работи не се нуждаят от време за тяхното изпълнение и се използват в графично представяне на проекта само, за да се показва правилно връзката между делата.

Практически урок №5

Клон на математиката, че проучванията на конфликтните ситуации, въз основа на техните математически модели, наречена теория на игрите. Човек може да се каже, че теорията на игрите - математическата теория на конфликтни ситуации, да се разработят препоръки за най-рационалния начин на действие на всеки един от участниците в конфликта, т.е. такива действия, които биха го възможно най-добрия резултат предоставят.

схеми на игра могат да се прилагат в много икономически ситуации. Така Gain може да действа като маржът на печалбата, разходите, ефективността на използването на ограничените ресурси, производствени мощности и т.н.

Основният факт е, че методите и насоките, разработени теория на игрите, които се прилагат за тези конфликтни ситуации, които са собственост на множествена рецидив. Ако възникне конфликтна ситуация веднъж или ограничен брой пъти, препоръките на теорията на игрите са неефективни.

Анализ на актуалното състояние на конфликт изисква значително (понякога радикални), за да се опрости - като се вземат предвид само най-важните фактори за конфликта. В тази връзка, можем да разгледаме в игра като опростен математически модел на конфликтната ситуация, характеризираща се с наличието на определени правила. Тези правила:

1. Изборът на образа на играчите действия на всеки етап на играта;

2. Информацията, която всеки играч има по реализация на тези избори;

3. Таксата за всеки играч след приключването на всяка фаза на играта.

Стратегия игра е набор от правила, които определят поведението на играча по време на играта. Стратегия на всеки играч се определя резултати или плащания в играта; и всеки играч има набор (краен или безкраен) на възможни стратегии.

Сред определящите характеристики на играта включват следното:

1. има конфликтни страни (играчи), които вземат решения, чиито интереси не съвпадат;

2. формулират стратегии за допустими правилата за избор известни играчи;

3 определя набор от възможни състояния на играта (например, печалба, загуба, равенство);

4. всички участници в играта (на играчите) са известни на авансовите плащания, отговарящи на всеки възможни крайни състояния.

Конфликтни ситуации, възникнали в практиката, пораждат различни видове игри. Класификация на игри на разположение на различни основания.

А) Според броя на играчите. Играта може да участва всеки краен брой играчи. Ако само двама играчи или играчи са обединени в две групи, преследващи противоречиви цели, а след това на двойки. В зависимост от броя на политики в играта, те са разделени на краен и безкраен.

Б) В зависимост от отношенията между участниците се прави разграничение между, които отказват сътрудничество (участниците не разполагат с правото да сключи споразумение) и кооперативни игри (понякога се използват като синоними - не оказват съдействие и сътрудничество игри, съответно).

Б) В зависимост от естеството печели играта са разделени на игра с нулев резултат, и не-нулев резултат. В с нулев резултат игри от общия капитал на играчите не се променя, но се преразпределя само в играта, и по тази причина размерът на печалбата е равна на нула (в този случай загубата се разглежда като отрицателен печалба). В игри с ненулева сума от размера на печалбите е различно от нула.

D) По видове игри функциите на финал са разделени в матрицата, bimatrix т.н. игри Матричните (за двама души) спечели първия сет играч матрица в bimatrix -. Победи всеки играч се определя от нейната матрица.

D) на броя на навивките на играта са разделени в едната посока (спечелим разпределени след като един от всеки играч) и многоходова (печалби, разпределени след няколко удара).

стратегия на играча се нарича оптимален, ако тя осигурява този играч под повтори игра възможно най-високата средна печалба или възможно най-ниската средна загуба, независимо от поведението на противника.

В бъдеще ние ще се ограничим до двойката матрица с нулев игри. Създаване стратегии на двамата играчи в двойки игра от този тип напълно определя изхода, т.е. печели или губи един на друг. Както вече бе отбелязано, крайният двойка игра с нулев резултат да настроите матрица, редовете и колоните, които съответстват на различни стратегии за 1-ви и 2-ри играчи, съответно, както и неговите елементи - печалбите от едната страна (останалите равни Загуба записи). Тази матрица се нарича финал матрица или матрични игри.

Игри без седло точки

Така че, ако матрицата на играта се състои от една точка на седлото, това е решение на принципа на Минимакс. Помислете за начина на решаване на играта в матрицата на плащане, който не разполага с точка седло. Минимакс Прилагане на стратегии на всеки от играчите осигурява първата печалба по-малко. и втора загуба вече не. Имайки предвид, че. естествено за играча Искам да се увеличи печалбата, и играчът II - да се намали загубата. Търсенето на такива решения води до използването на комплексна стратегия, която се състои в произволна употреба на две или повече чисти стратегии с някои вероятности. Подобна сложна стратегия в теорията на игрите се нарича смесена. Смесени стратегии на играчите I и II, ще бъдат обозначени съответно,

къде. # 8209; вероятността от съответните чисти стратегии. Очевидно е, че трябва да бъде обработена нормализиране на вероятността

Една от основните теореми на теорията на игрите твърди, че всеки краен игра на две лица, нулев резултат има поне едно решение може да бъде в смесени стратегии. Тази теорема означава, че всеки краен игра има цена. Ние го, както и нетната стойност на играта чрез означаване. Цена на играта - средното увеличение на една от страните - винаги отговаря. т.е. Тя се намира между долната () и горна () цените на играта. Ето защо, всеки играч при повтарящи се игри, придържайки се към смесени стратегии, получава по-благоприятния резултат за себе си. Оптималното решение на играта в смесени стратегии, както и под формата на разтвор в чисти стратегии, характеризираща се с факта, че всеки един от играчите не се интересуват от отдалечаване от оптималната си смесен позиция, ако той му се прилага оптимална смесена стратегия, тъй като тя е в негова полза.

Стратегии играчи в рамките на своите оптимални смесени стратегии се наричат активни.

5.5 Използването на линеен оптимизация за решаване на игри Матрицата

Нека играта не е най-доброто решение в чисти стратегии, т.е. седло точка липсва.

Ние приемаме, че всички елементи на плащане матрица на неотрицателна (ако не е, то е възможно за всички елементи на матрицата, за да добавите няколко L, изпращане на плащания на не-отрицателни стойности - очевидно, цената на играта ще се увеличи до L, и решението няма да се промени на проблема). По този начин, ние приемаме, че> 0.

Ние търсим решение на играта в смесени стратегии

Използването на играч, който оптимално смесена стратегия го уверява, независимо от поведението на играча II на, печалбата не е по-малко от цената на играта.

Нека играчът II използва своята силна нетната й-ти стратегия, и играчът I - тяхната оптимална стратегия. Тогава средната играч да получа ще бъде равна

Като се има предвид, че тя не може да бъде по-малко. напишете условия:

Разделяйки двете страни на всяко от неравенствата (5.4) върху цената на играта. получаваме

При използване на символи

(5.5) е под формата

където очевидно всичко. тъй като.

и определението (5.6) следва, че променливите () не отговаря на условието

Като се има предвид, че играчът се стреми да максимизира. Ние получи линейна функция

Следователно, проблемът за решаване намалява игра следната линейна проблем оптимизация: намери неотрицателни променливи стойности минимизиране на линейна функция (5.8) и отговарят на ограниченията (5.7).

С решаването на проблема с линейна оптимизация е лесно да се намери стойността на играта и оптималната стратегия за Играч I:

На свой ред, оптималната стратегия за Player II

Тя може да се намери от експресията

къде - не-отрицателни променливи линеен проблемни оптимизация

което е двойно по отношение на проблема, представен от условията (5.7) и (5.8).

В тази система на неравенството променливи

По този начин, оптималната стратегия

игри с матрицата на плащане () могат да бъдат открити чрез решаване на симетричен двойката двойна линейни оптимизация.

Двойното проблема първоначален проблем

Цената на играта, както и вероятността от стратегии на играч I и II се

5.6 Задачи за независим решение

Чрез намаляване на двойните проблеми на линейното програмиране, за да намери оптималната смесена стратегия и цената на игри игри Матрицата с такъв финал матрица: