1. Предмет и цели на изследването на операциите в икономиката. Основни понятия на теорията за изследване на операциите.

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

Целта на изследването на операциите е да обоснове количествено взетите решения за управление на организации.

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

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

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

Целта на оперативните изследвания е предварителното количествено обосноваване на оптимални решения.

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

Параметрите, чиято комбинация образува решение, се наричат ​​елементи на решението.

Наборът от осъществими решения са дадени условия, които са фиксирани и не могат да бъдат нарушавани.

Индикаторът за ефективност е количествена мярка, която ви позволява да сравнявате различни решения по отношение на ефективността.

2. Концепцията за мрежово планиране и управление. Мрежов модел на процеса и неговите елементи.

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

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

Основни понятия на мрежовия модел:

Събитие, работа, път.

Събитията са резултат от една или повече задачи. Те нямат продължение във времето.

Пътеката е верига от задачи, следващи една след друга, свързващи началния и крайния върх.

Продължителността на пътуването се определя от сумата от продължителностите на съставните му работи.

3. Изграждане и организиране на мрежова схема.

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

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

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

Трудът е производствен процес, който изисква време, труд и материални ресурси, който, когато е завършен, води до постигане на определени резултати.

Зависимост (фиктивна работа), която не изисква време, е изобразена с пунктирана стрелка. Фиктивната работа се използва в мрежова диаграма, за да покаже връзките между събития и дейности.

Мрежовата диаграма използва време, цена и други характеристики на работата.

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

Цената на работата е преките разходи, необходими за нейното завършване, в зависимост от продължителността и условията на тази работа.

Ресурсите се характеризират с необходимостта от физически единици, необходими за извършване на дадена работа.

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

Събитие е фактът на завършване на една или повече задачи, който е необходим и достатъчен за започване на една или повече следващи работи. На всяко събитие се присвоява номер, наречен код. Всяка задача се дефинира от две събития: начален код на събитие, означен с i, и краен код на събитие, означен с j.

Събития, които нямат предишна работа, се наричат ​​начални; събития, които нямат последващи, са крайни.

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

2 При изграждането на мрежа се разрешават следните проблеми:

Каква работа(и) трябва да бъде завършена, за да започне тази работа;

Каква работа е препоръчително да се извършва успоредно с тази работа;

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

4 Формата на графиката трябва да е проста и визуално лесна за възприемане.

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

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

4. Критичен път на мрежовата диаграма. Времеви резерви. Ранни и късни дати на събития и работа в графика на мрежата.

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

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

Две концепции са от особено значение при изготвянето на мрежова диаграма:

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

Късното завършване на работата е най-късният срок за завършване на работата, при който общата продължителност на работата не се увеличава. Определя се от най-краткия път от дадено събитие до завършване на цялата работа.

Предсрочното завършване е краен срок, преди който работата не може да бъде завършена. Равно е на ранното начало плюс продължителността на тази работа

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

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

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

Частен (безплатен) резерв е максималното време, за което може да се забави изпълнението на дадена задача, без да се променя ранното начало на следващата. Този резерв е възможен само когато събитието включва две или повече задачи (зависимости), т.е. две или повече стрелки (плътни или пунктирани) са насочени към него. Тогава само една от тези задачи ще има ранен завършек, който съвпада с ранния старт на следващата задача, но за останалите това ще бъдат различни стойности. Тази разлика за всяка работа ще бъде нейният частен резерв.

5. Динамично програмиране. Принципът на Белман за оптималност и управление.

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

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

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

6. Проблемът с разпределението на средствата между предприятията.

Можем да кажем, че процедурата за конструиране на оптимално управление с помощта на метода на динамичното програмиране е разделена на два етапа: предварителен и окончателен. На предварителния етап, за всяка стъпка, SOE се определя в зависимост от състоянието на системата (постигната в резултат на предишни стъпки) и условно оптималното усилване на всички останали стъпки, започвайки от тази, също в зависимост от състоянието . На последния етап се определя (безусловното) оптимално управление за всяка стъпка. Предварителната (условна) оптимизация се извършва стъпка по стъпка в обратен ред: от последната стъпка към първата; крайна (безусловна) оптимизация - също на стъпки, но в естествен ред: от първата стъпка до последната. От двата етапа на оптимизация, първият е несравнимо по-важен и отнема много време. След завършване на първия етап, завършването на втория не представлява никаква трудност: остава само да „прочетете“ препоръките, които вече са подготвени на първия етап.

7. Постановка на задачата за линейно програмиране.

Линейното програмиране е популярен инструмент за решаване на икономически проблеми, които се характеризират с наличието на един критерий (например максимизиране на доходите от производството чрез оптимален избор на производствена програма или например минимизиране на транспортните разходи и др.). Икономическите проблеми се характеризират с ограничения на ресурсите (материални и/или финансови). Те се записват под формата на система от неравенства, понякога под формата на равенства.

От гледна точка на прогнозиране на приемливи ценови интервали (или обеми на продажби) в рамките на обобщения непараметричен метод, използването на линейно програмиране означава:

Критерият е MAX цена на следващия продукт от групата на интерес f.

Контролирани променливи са цените на всички продукти от група f.

Ограниченията в нашия проблем за прогнозиране с помощта на обобщения непараметричен метод са:

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

б) изискването за неотрицателност на контролираните променливи (в нашия проблем за прогнозиране ще изискваме цените на продуктите от група f да не падат под 80% от ценовите стойности в последния времеви момент);

в) бюджетно ограничение под формата на равенство - изискването размерът на разходите за закупуване на продукти от група f да бъде постоянен (при отчитане на 15% инфлация, например).

8. Графичен метод за решаване на задачи от линейно програмиране.

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

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

Намерете минималната стойност на функция

(2.1) Z = С1х1+С2х2

a11x1 + a22x2 b1

(2.2)a21x1 + a22x2 b2

aM1x1 + aM2x2 bM

(2.3) x1 0, x2 0

Да приемем, че системата (2.2) при условие (2.3) е непротиворечива и нейният многоъгълник на решение е ограничен. Всяко от неравенствата (2.2) и (2.3), както беше отбелязано по-горе, дефинира полуравнина с гранични линии: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), x1=0 , x2=0 . Линейна функция (2.1) за фиксирани стойности на Z е уравнението на права линия: C1x1 + C2x2 = const. Нека построим многоъгълник от решения на системата от ограничения (2.2) и графика на линейната функция (2.1) при Z = 0 (фиг. 2.1). Тогава поставената задача за линейно програмиране може да получи следната интерпретация. Намерете точката на многоъгълника на решение, в която опорната права C1x1 + C2x2 = const и функцията Z достигат минимум.

Стойностите на Z = C1x1 + C2x2 се увеличават по посока на вектора N = (C1, C2), така че преместваме правата Z = 0 успоредна на себе си по посока на вектора X. От фиг. 2.1 следва, че правата линия два пъти става референтна линия по отношение на многоъгълника на решение (в точки A и C) и приема минималната стойност в точка A. Координатите на точка A (x1, x2) се намират чрез решаване на система от уравнения на прави линии AB и AE.

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

Случай 1. Правата C1x1 + C2x2 = const, движеща се по посока на вектора N или срещу него, постоянно пресича многоъгълника на решението и не е опора за него в никоя точка. В този случай линейната функция не е ограничена върху многоъгълника на решението както отгоре, така и отдолу (фиг. 2.2).

Случай 2. Правата линия, която се движи, все пак става опора спрямо многоъгълника на решенията (фиг. 2.2, a - 2.2, c). Тогава, в зависимост от вида на областта, линейната функция може да бъде ограничена отгоре и неограничена отдолу (фиг. 2.2, а), ограничена отдолу и неограничена отгоре (фиг. 2.2, б) или ограничена както отдолу, така и отгоре (фиг. 2.2, c).

9. Симплексен метод.

Симплексният метод е основният в линейното програмиране. Решаването на проблема започва с разглеждане на един от върховете на полиедъра от условия. Ако разглежданият връх не съответства на максимума (минимума), тогава те се преместват в съседния, като увеличават стойността на целевата функция при решаване на проблема за максимума и го намаляват при решаване на проблема за минимума. По този начин преместването от един връх към друг подобрява стойността на целевата функция. Тъй като броят на върховете на полиедъра е ограничен, в краен брой стъпки е гарантирано да се намери оптималната стойност или да се установи фактът, че проблемът е неразрешим.

Този метод е универсален, приложим за всяка задача на линейно програмиране в канонична форма. Системата от ограничения тук е система от линейни уравнения, в която броят на неизвестните е по-голям от броя на уравненията. Ако рангът на системата е r, тогава можем да изберем r неизвестни, които изразяваме чрез останалите неизвестни. За категоричност приемаме, че са избрани първите последователни неизвестни X1, X2, ..., Xr. Тогава нашата система от уравнения може да бъде записана като

Симплексният метод се основава на теорема, наречена основна теорема на симплексния метод. Сред оптималните планове на задача за линейно програмиране в канонична форма задължително има референтно решение на нейната система от ограничения. Ако оптималният план на проблема е единствен, то той съвпада с някакво референтно решение. Има краен брой различни поддържащи решения на системата от ограничения. Следователно решение на задачата в канонична форма може да се търси чрез търсене в референтните решения и измежду тях да се избере това, за което стойността на F е най-голяма. Но, първо, всички референтни решения са неизвестни и трябва да бъдат намерени, и, второ, в реални задачи има много от тези решения и директното търсене едва ли е възможно. Симплексният метод е определена процедура за насочено изброяване на опорни решения. Въз основа на определено еталонно решение, намерено предварително с помощта на определен алгоритъм на симплексния метод, ние изчисляваме ново референтно решение, на което стойността на целевата функция F е не по-малка от старата. След поредица от стъпки стигаме до референтно решение, което е оптималният план.

10. Постановка на транспортния проблем. Методи за определяне на опорни планове.

Има m изходни точки („доставчици“) и n точки на потребление („потребители“) на някакъв идентичен продукт. За всеки артикул са определени:

ai - производствените обеми на i-тия доставчик, i = 1, …, m;

вj - търсенето на j-тия потребител, j= 1,…,n;

сij е цената на транспортирането на една единица продукт от точка Ai, i-тия доставчик, до точка Bj, j-тия потребител.

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

Необходимо е да се намери транспортен план, при който търсенето на всички потребители да бъде напълно задоволено, докато има достатъчно доставки от доставчици и общите транспортни разходи ще бъдат минимални.

Транспортният план се отнася до обема на превозите, т.е. количеството стоки, което трябва да се транспортира от i-тия доставчик до j-тия потребител. За да се изгради математически модел на задачата, е необходимо да се въведат m·n променливи xij, i= 1,..., n, j= 1,..., m, като всяка променлива xij означава обема на превоза от т. Ai до точка Bj. Наборът от променливи X = (xij) ще бъде планът, който трябва да бъде намерен въз основа на формулирането на проблема.

Това е условие за решаване на затворени и отворени транспортни задачи (КТЗ).

Очевидно, за да бъде разрешима задача 1, е необходимо общото търсене да не надвишава обема на продукцията от доставчиците:

Ако това неравенство е стриктно изпълнено, тогава проблемът се нарича „отворен” или „небалансиран”, но ако , тогава проблемът се нарича „затворен” транспортен проблем и ще има формата (2):

Условие за баланс.

Това е условие за решаване на затворени транспортни задачи (CTP).

11. Алгоритъм за решаване на транспортната задача.

Прилагането на алгоритъма изисква спазването на редица предпоставки:

1. Разходите за транспортиране на единица продукт от всяка точка на производство до всяка дестинация трябва да бъдат известни.

2. Трябва да се знае запасът от продукти във всяка точка на производство.

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

4. Общото предлагане трябва да е равно на общото търсене.

Алгоритъмът за решаване на транспортния проблем се състои от четири етапа:

Етап I: Представете данните под формата на стандартна таблица и намерете възможното разпределение на ресурсите. Приемливо е разпределение на ресурсите, което ви позволява да задоволите цялото търсене в дестинациите и да премахнете целия запас от продукти от производствените точки.

Етап 2. Проверка на оптималността на полученото разпределение на ресурсите

Етап 3. Ако полученото разпределение на ресурсите не е оптимално, тогава ресурсите се преразпределят, намалявайки разходите за транспорт.

Етап 4. Повторна проверка на оптималността на полученото разпределение на ресурсите.

Този итеративен процес се повтаря, докато се получи оптималното решение.

12. Модели за управление на запасите.

Въпреки факта, че всеки модел за управление на инвентара е предназначен да отговори на два основни въпроса (кога и колко), има значителен брой модели, при конструирането на които се използват различни математически инструменти.

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

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

детерминистичен;

вероятностен.

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

Вероятностното търсене може да бъде стационарно, когато функцията на плътността на вероятността на търсенето не се променя с времето, и нестационарно, когато функцията на плътността на вероятността се променя в зависимост от времето. Горната класификация е илюстрирана на фигурата.

Най-простият случай е случаят на детерминирано статично търсене на продукти. Този тип консумация обаче е доста рядка на практика. Най-сложните модели са моделите от нестационарен тип.

В допълнение към естеството на търсенето на продукти, когато се изграждат модели за управление на запасите, трябва да се вземат предвид много други фактори, например:

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

процес на попълване на запасите. Може да бъде мигновен или разпределен във времето;

наличие на ограничения за оборотен капитал, складова площ и др.

13. Системи за масово обслужване (QS) и показатели за тяхната ефективност.

Системите за масово обслужване (QS) са системи от специален тип, които реализират многократно изпълнение на подобни задачи. Такива системи играят важна роля в много области на икономиката, финансите, производството и ежедневието. Като примери за QS във финансовите и икономическите; в сферата можем да посочим различни видове банки (търговски, инвестиционни, ипотечни, иновационни, спестовни), застрахователни организации, държавни акционерни дружества, дружества, фирми, сдружения, кооперации, данъчни инспекции, одиторски услуги, различни комуникационни системи (вкл. телефонни централи), товаро-разтоварни комплекси (пристанища, товарни гари), бензиностанции, различни предприятия и обслужващи организации (магазини, информационни бюра, фризьорски салони, билетни каси, обменни бюра, сервизи, болници). Системи като компютърни мрежи, системи за събиране, съхраняване и обработка на информация, транспортни системи, автоматизирани производствени зони, производствени линии, различни военни системи, по-специално системи за противовъздушна или противоракетна отбрана, също могат да се разглеждат като вид QS.

Всяка QS включва в структурата си определен брой обслужващи устройства, които се наричат ​​обслужващи канали (устройства, линии). Ролята на канали могат да играят различни устройства, лица, извършващи определени операции (касиери, оператори, фризьори, продавачи), комуникационни линии, автомобили, кранове, ремонтни екипи, железопътни линии, бензиностанции и др.

Системите за масово обслужване могат да бъдат едноканални или многоканални.

Всеки QS е проектиран да обслужва (изпълнява) определен поток от приложения (изисквания), пристигащи на входа на системата, най-често не редовно, а в произволни моменти. Обслужването на приложенията в този случай също не продължава постоянно, предварително известно време, а произволно време, което зависи от много случайни, понякога неизвестни за нас причини. След обслужване на заявката каналът се освобождава и е готов да приеме следваща заявка. Случайният характер на потока от заявки и времето на тяхното обслужване води до неравномерно натоварване на QS: в други моменти необслужваните приложения могат да се натрупват на входа на QS, което води до претоварване на QS, а понякога и когато има свободни канали на входа на QS, няма да има приложения, което води до недотоварване на QS, т.е. до бездействието на каналите му. Приложенията, които се натрупват на входа на QS, или се „присъединяват“ към опашката, или поради невъзможността за по-нататъшно оставане в опашката оставят QS необслужен.

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

14. Динамични уравнения за вероятностни състояния (уравнения на Колмогоров). Пределни вероятности на състоянията.

Формално диференцирайки уравнението на Колмогоров-Чапман по отношение на s при s = 0, получаваме директното уравнение на Колмогоров:

Формално диференцирайки уравнението на Колмогоров-Чапман по отношение на t при t = 0, получаваме обратното уравнение на Колмогоров

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

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

На фиг. показва графика на състояния и преходи, които отговарят на заявеното условие: от всяко състояние системата рано или късно може да премине към всяко друго състояние. Условието няма да бъде изпълнено, когато посоката на стрелка 4-3 в графиката на Фиг. се промени, а обратното.

Да приемем, че заявеното условие е изпълнено и следователно съществуват ограничаващите вероятности:

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

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

15. Процес на смърт и размножаване.

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

Потоците на възпроизвеждане λi(t) ще се наричат ​​потоци на Поасон, водещи до нарастване на функцията X(t). Съответно μi(t) са потоците на смъртта, водещи до намаляване на функцията X(t).

Нека съставим уравнението на Колмогоров от графиката:

Ако потокът е крайно състояние:

Системата от уравнения на Колмогоров за процеса на смърт и размножаване с ограничен брой състояния има формата:

Процесът на чисто възпроизвеждане е процес на смърт и размножаване, при който интензитетите на всички смъртни потоци са равни на нула.

Процесът на чиста смърт е процес на смърт и възпроизводство, при който интензитетите на всички възпроизводствени потоци са равни на нула.

16. Системи за масово обслужване с повреди.

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

Трябва да се отбележи, че в този случай броят на каналите е 1 (). Този канал получава Поасонов поток от заявки, чийто интензитет е равен на . Времето влияе върху интензивността:

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

17. Системи за масово обслужване с изчакване.

Заявка, получена, когато каналът е зает, е в опашка и чака обслужване.

Система с ограничена дължина на опашката. Нека първо приемем, че броят на местата в опашката е ограничен от m, т.е. ако едно приложение пристигне в момент, когато вече има m приложения в опашката, то оставя системата необслужена. В бъдеще, чрез насочване на m към безкрайност, ще получим характеристиките на едноканален QS без ограничения на дължината на опашката.

Ще номерираме състоянията на QS според броя на приложенията в системата (както обслужвани, така и очакващи обслужване):

— каналът е безплатен;

— каналът е зает, няма опашка;

— каналът е зает, една заявка е в опашката;

—каналът е зает, k - 1 заявки са на опашка;

— каналът е зает, тонове приложения са на опашка.

18. Методи за вземане на решения в условия на конфликт. Матрични игри. Чисти и смесени стратегически игри.

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

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

Матрична игра за двама играчи с нулева сума може да се разглежда като следната абстрактна игра за двама играчи.

Първият играч има m стратегии i = 1,2,...,m, вторият играч има n стратегии j = 1,2,...,n. Всяка двойка стратегии (i,j) е свързана с число aij, което изразява печалбата на играч 1 за сметка на играч 2, ако първият играч приеме своята i-та стратегия, а 2 - неговата j-та стратегия.

Всеки играч прави един ход: играч 1 избира своята i-та стратегия (i=), 2 - своята j-та стратегия (j=), след което играч 1 получава печалбата aij за сметка на играч 2 (ако aij

Всяка стратегия на играч i=; j = често се нарича чиста стратегия.

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

Така, ако играч 1 има m чисти стратегии 1,2,...,m, тогава неговата смесена стратегия x е набор от числа x = (x1,..., xm), удовлетворяващи отношенията

xi³ 0 (i= 1,m), =1.

По същия начин, за играч 2, който има n чисти стратегии, смесената стратегия y е множеството от числа

y = (y1, ..., yn), yj ³ 0, (j = 1,n), = 1.

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

Чистата стратегия е специален случай на смесена стратегия. Наистина, ако в смесена стратегия някоя i-та чиста стратегия се приложи с вероятност 1, тогава всички други чисти стратегии не се прилагат. И тази i-та чиста стратегия е частен случай на смесена стратегия. За да запази тайната, всеки играч прилага свои собствени стратегии, независимо от избора на другия играч.

19. Геометричен метод за решаване на матрична игра.

Решението на игри с размер 2xn или nx2 позволява ясна геометрична интерпретация. Такива игри могат да бъдат решени графично.

В равнината XY по оста на абсцисата начертаваме един сегмент A1A2 (Фигура 5.1). Нека присвоим на всяка точка от отсечката някаква смесена стратегия U = (u1, u2). Освен това разстоянието от някаква междинна точка U до десния край на този сегмент е вероятността u1 за избор на стратегия A1, разстоянието до левия край е вероятността u2 за избор на стратегия A2. Точка A1 съответства на чиста стратегия A1, точка A2 съответства на чиста стратегия A2.

В точки A1 и A2 ще възстановим перпендикуляри и ще поставим печалбите на играчите върху тях. На първия перпендикуляр (съвпадащ с оста OY) показваме печалбата на играч A при използване на стратегия A1, на втория - при използване на стратегия A2. Ако играч A използва стратегия A1, тогава неговата печалба със стратегия B1 на играч B е равна на 2, а със стратегия B2 е равна на 5. Числата 2 и 5 на оста OY съответстват на точки B1 и B2. По същия начин, на втория перпендикуляр намираме точки B"1 и B"2 (печалби 6 и 4).

Свързвайки точки B1 и B"1, B2 и B"2, получаваме две прави линии, разстоянието от които до оста OX определя средната печалба за всяка комбинация от съответни стратегии.

Например разстоянието от всяка точка на сегмента B1B"1 до оста OX определя средната печалба на играч A за всяка комбинация от стратегии A1 и A2 (с вероятности u1 и u2) и стратегия B1 на играч B.

Ординатите на точките, принадлежащи на прекъснатата линия B1MB"2, определят минималната печалба на играч A, когато той използва всякакви смесени стратегии. Тази минимална стойност е най-голямата в точка M, следователно тази точка съответства на оптималната стратегия U* = ( ,), и неговата ордината е равна на цената на играта v .

Намираме координатите на точка M като координати на пресечната точка на прави B1B"1 и B2B"2.

За да направите това, трябва да знаете уравненията на линиите. Можете да създадете такива уравнения, като използвате формулата за уравнението на права, минаваща през две точки:

Нека създадем уравнения с права линия за нашия проблем.

Линия B1B"1: = или y = 4x + 2.

Директен B2B"2: = или y = -x + 5.

Получаваме системата: y = 4x + 2,

Нека го решим: 4x + 2 = -x + 5,

x = 3/5, y = -3/5 + 5 = 22/5.

Така U = (2/5, 3/5), v = 22/5.

20. Би-матрични игри.

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

Разработена е и теория за оптималното поведение на играча за биматрични игри, но решаването на такива игри е по-трудно от обикновените матрични игри.

21. Статистически игри. Принципи и критерии за вземане на решения при условия на пълна и частична несигурност.

В оперативните изследвания е обичайно да се разграничават три вида несигурност:

несигурност на целите;

несигурността на нашите знания за околната среда и факторите, действащи в това явление (несигурност на природата);

несигурност на действията на активен или пасивен партньор или противник.

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

От друга страна, другите два вида несигурности засягат главно формулирането на целевата функция на уравненията на ограниченията и метода за вземане на решение. Разбира се, горното твърдение е доста условно, както и всяка класификация. Представяме го само с цел да подчертаем още някои характеристики на несигурностите, които трябва да се имат предвид в процеса на вземане на решения.

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

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

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

Друг краен случай може да бъде несигурност от нестохастичен тип (по думите на E.S. Ventzel - „лоша несигурност“), при която не съществуват допускания за стохастична стабилност. И накрая, можем да говорим за междинен тип несигурност, когато се взема решение въз основа на някои хипотези за законите на разпределение на случайни променливи. В същото време вземащият решение трябва да има предвид опасността от несъответствие между неговите резултати и реалните условия. Този риск от несъответствие се формализира с помощта на рискови коефициенти.

Вземането на решение при рискови условия може да се основава на един от следните критерии:

критерий за очаквана стойност;

комбинации от очаквана стойност и дисперсия;

известно гранично ниво;

най-вероятното събитие в бъдещето.

Глава 1. Предмет и задачи на оперативните изследвания.

§ 1. Какво е изследване на операциите и какво прави.

§ 2. Основни понятия и принципи на изследването на операциите.

§ 3. Математически модели на операциите.

Глава 2. Разновидности на проблемите на изследването на операциите и подходите за тяхното решаване.

§ 4. Преки и обратни задачи на изследването на операциите. Детерминирани задачи.

§ 5. Проблемът за избор на решение при условия на несигурност.

§ 6. Многокритериални проблеми в оперативните изследвания. „Системен подход”.

Глава 3. Линейно програмиране.

§ 7. Задачи на линейно програмиране.

§ 8. Основният проблем на линейното програмиране.

§ 9. Наличие на решение на 03LP и методи за намирането му.

§ 10. Транспортна задача на линейното програмиране.

§ 11. Задачи от целочислено програмиране. Концепцията за нелинейно програмиране.

Глава 4. Динамично програмиране.

§ 12. Метод на динамично програмиране.

§ 13. Примери за решаване на задачи по динамично програмиране.

§ 14. Задача за динамично програмиране в общ вид. Принципът на оптималност.

Глава 5. Марковски случайни процеси.

§ 15. Понятието марковски процес.

§ 16. Потоци от събития.

§ 17. Уравнения на Колмогоров за вероятности на състоянията. Вероятности за крайно състояние.

Глава 6. Теория на масовото обслужване.

§ 18. Проблеми на теорията на масовото обслужване. Класификация на системите за масово обслужване.

§ 19. Схема на смъртта и размножаването. Формулата на Литъл.

§ 20. Най-простите системи за масово обслужване и техните характеристики.

§ 21. По-сложни проблеми на теорията на масовото обслужване.

Глава 7. Статистическо моделиране на случайни процеси (метод Монте Карло).

§ 22. Идея, цел и обхват на приложимост на метода.

§ 23. Единична партида и форми на нейната организация.

§ 24. Определяне на характеристиките на стационарен случаен процес въз основа на едно изпълнение.

Глава 8. Игрови методи за обосноваване на решение.

§ 25. Предмет и задачи на теорията на игрите.

§ 26. Антагонистични матрични игри.

§ 27. Методи за решаване на крайни игри.

§ 28. Проблеми на теорията на статистическите решения.

ПРЕДМЕТ И ЦЕЛИ НА ОПЕРАЦИОННОТО ИЗСЛЕДВАНЕ

Основни понятия и принципи на изследването на операциите

В този раздел ще се запознаем с терминологията, основните понятия и принципите на науката „изследване на операциите“.

Операция е всяко събитие (система от действия), обединено от един план и насочено към постигане на някаква цел (всички събития, разгледани в параграфи 1 - 8 на предходния параграф, са „операции“).

Една операция винаги е контролирано събитие, тоест от нас зависи как да изберем някои параметри, които характеризират нейната организация. „Организация“ тук се разбира в широкия смисъл на думата, включително набор от технически средства, използвани в операцията.

Всеки специфичен избор на параметри, който зависи от нас, се нарича решение. Решенията могат да бъдат успешни и неуспешни, разумни и неразумни. Оптималните решения са тези, които са за предпочитане пред други въз основа на определени характеристики. Целта на оперативните изследвания е предварителното количествено обосноваване на оптимални решения.

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

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

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

Тези параметри, чиято комбинация образува решение, се наричат ​​елементи на решението. Като елементи на решението могат да се появят различни числа, вектори, функции, физически характеристики и т. н. Например, ако се изготви план за транспортиране на хомогенни стоки от точките на тръгване A 1, A 2,…, A mдо дестинации В 1,B 2, ..., B n,тогава елементите на решението ще бъдат числа x ij , показващ колко товари ще бъдат изпратени от 1-вата точка на тръгване A i V йта дестинация В дж.Набор от числа х 11 , х 12, …, х 1 n , …, х m 1, х m2,…, х мнобразува разтвор.

В най-простите задачи за изследване на операциите броят на елементите на решението може да бъде относително малък. Но в повечето задачи с практическо значение броят на елементите на решението е много голям, както читателят може да провери, като се опита самостоятелно да идентифицира и „назове“ елементите на решението в примери 1 - 8 от предишния параграф. За простота ще обозначим целия набор от елементи на решението с една буква хи кажете "решение" Х".

В допълнение към елементите на решението, които ние до известна степен можем да контролираме, във всяка задача за изследване на операциите има и зададени „дисциплиниращи“ условия, които са фиксирани от самото начало и не могат да бъдат нарушавани (например товароносимост на машината размер на планираната задача;

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

Нека означим това множество отново с една буква Х,и фактът, че решението хпринадлежи към това множество, ще го запишем като формула: х х(прочетете: елемент хвключени в комплекта Х).

Въпросът е, че в множеството възможни решения хподчертайте тези решения х(понякога едно, но по-често цяла област от решения), които от една или друга гледна точка са по-ефективни (успешни, за предпочитане) от други. За да сравните различни решения по отношение на ефективността, трябва да имате някакъв количествен критерий, така нареченият показател за ефективност (често се нарича „обективна функция“). Този индикатор е избран така, че да отразява целевата ориентация на операцията. За „най-добро“ решение ще се счита това, което най-много допринася за постигане на целта. За да изберете, „име по име“ индикатор за ефективност W,Преди всичко трябва да се запитате: какво искамеКакво целим, когато предприемаме операция? Когато избираме решение, естествено ще предпочетем такова, което обръща показателя за ефективност Удо максимум (или до минимум). Например, бих искал да максимизирам приходите от операция; ако индикаторът за ефективност са разходите, препоръчително е те да бъдат намалени до минимум. Ако е желателно да се увеличи максимално показателят за ефективност, ще го запишем във формуляра W => max, и ако е минимизиран - W =>мин.

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

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

Избирането на грешен индикатор за ефективност е много опасно. Операциите, организирани по неуспешно избран критерий, могат да доведат до неоправдани разходи и загуби (да си припомним например прословутия „вал“ като основен критерий за оценка на икономическата дейност на предприятията).

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

1. План за снабдяване на предприятието.Целта на операцията е да се осигури доставката на суровини при минимизиране на транспортните разходи. Индикатор за ефективност Р- общи разходи за транспортиране на суровини за единица време, например месец ( R =>мин.).

2. Изграждане на участък от магистралата.Необходимо е да се планира строителството по такъв начин, че да завърши възможно най-скоро. Естествен индикатор за ефективност би бил времето за завършване на строителството, ако не беше свързано със случайни фактори (откази на оборудването, забавяне на завършването на отделни работи). Следователно средното очаквано време може да бъде избрано като показател за ефективност Tзавършване на строителството (T =>мин.).

3. Продажба на сезонни стоки.Като индикатор за ефективност можете да вземете средната очаквана печалба P от продажбата на стоки за сезона (P => max).

4. Снегозащита на пътища.Говорим за икономически най-изгодния план за защита от сняг, следователно като показател за ефективност можете да изберете средни разходи за единица време (например годишно) Рза поддръжка и експлоатация на пътища, включително разходи, свързани както с изграждането на защитни устройства, така и с разчистването на пътищата и със закъсненията на трафика (R =>мин.).

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

6. Пробен контрол на продуктите.Естествен индикатор за ефективност, предложен от постановката на проблема, е средната очаквана цена Рза контрол за единица време, при условие че системата за контрол осигурява дадено ниво на качество, например средният процент на дефектите не е по-висок от даден ( Р=> мин).

7. Медицински преглед.Можете да изберете средния процент (дял) като индикатор за ефективност Qидентифицирани пациенти и носители на инфекция (Q =>проверка).

8. Библиотечно обслужване.Умишлено е допусната известна неяснота при формулирането на проблема:

Не е ясно какво означава „най-добро обслужване на клиентите“ или „задоволяване на техните искания в максимална степен“. Ако качеството на услугата се съди по времето, което абонатът, който е поискал книгата, чака да я получи, тогава средното време може да се приеме като индикатор за ефективност Tочакванията на читателя, подал заявка за книгата ( T=> мин). Можете да подходите към въпроса от малко по-различни позиции, като изберете средното число като показател за ефективност Мкниги, издадени за единица време (М =>макс).

Разгледаните примери бяха специално подбрани толкова прости, че изборът на показател за ефективност беше относително лесен и беше пряко продиктуван от вербалната формулировка на проблема и неговата (почти винаги) недвусмислена целева насоченост. На практика обаче това не винаги е така. Читателят може да провери това, като се опита например да избере индикатор за ефективността на градския транспорт. Какво да приемем за такъв показател? Средна скорост на пътниците, пътуващи из града? Или средният брой превозени пътници? Или средният брой километри, които човек, който не може да бъде транспортиран до правилното място, ще трябва да измине пеша? Тук има много за размисъл!

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

Примери за решаване на задачи по динамично програмиране

В този раздел ще разгледаме (и дори ще решим докрай) няколко прости (изключително опростени) примера за проблеми с динамично програмиране

1. Полагане на най-изгодния маршрут между две точки.Нека си припомним задача 4 от предишния параграф и да я решим докрай в изключително (и умишлено) опростени условия. Трябва да изградим свързващ път

две точки АИ IN,от които вторият лежи на североизток от първия. За простота, да кажем. че правенето на път се състои от поредица от стъпки и на всяка стъпка можем да се движим или на изток, или на север; всякакъв начин от А V INе стъпаловидна начупена линия, чиито сегменти са успоредни на една от координатните оси (фиг. 13.1). Разходите за изграждането на всяка от тези секции са известни. Необходимо е да се постави такъв път от А V IN,при които общите разходи са минимални.

Как да го направим? Можете да направите един от двата начина: или да преминете през всички възможни варианти на пътя и да изберете този с минимални разходи (а при голям брой сегменти това е много, много трудно!); или разделете процеса на преход от А V INна отделни стъпки (една стъпка - един сегмент) и оптимизирайте управлението стъпка по стъпка. Оказва се, че вторият метод е несравнимо по-удобен! Тук,както навсякъде в оперативните изследвания, има предимства на целенасоченото, организирано търсене на решение пред наивното „сляпо“ търсене.

Нека демонстрираме как се прави това с конкретен пример. Разделете разстоянието от Апреди INв източна посока, да речем, на 7 части, а в северна посока - на 5 части (по принцип раздробяването може да бъде колкото искате). Тогава всеки път от А V INвключва T= 7 + 5 == 12 сегмента, насочени на изток или север (фиг. 13.2). Нека поставим на всеки сегмент число, изразяващо (в някои конвенционални единици) цената на полагането на път по този сегмент. Трябва да изберете този път от А V IN,за които сумата от числата на отсечките е минимална.

Ще разглеждаме пътя, който се изгражда като контролирана система С,движещи се под влияние на контрола от първоначалното състояние Адо края IN.Състоянието на тази система преди началото на всяка стъпка ще се характеризира с две координати: източна (Х)и северен (y),и двете са цели числа (0 х 5 7, 0 при 5). За всяко от състоянията на системата (възлова точка на правоъгълната решетка на фиг. 13.2) трябва да намерим условно оптимално управление: трябва да отидем от тази точка на север (контрола “c”) или на изток (контрола "° С"). Този контрол е избран така, че цената на всички стъпки, оставащи до края (включително тази) да е минимална. Ще продължим да наричаме тази цена „условна оптимална печалба“ (въпреки че в този случай това не е „печалба“, а „загуба“) за дадено състояние на системата Спреди да започнете следващата стъпка.

Ще разгърнем процедурата по условна оптимизация в обратна посока – от края към началото. Първо, ще извършим условна оптимизация на последната, 12-та стъпка. Нека разгледаме отделно горния десен ъгъл на нашата правоъгълна мрежа (фиг. 13.3). Къде можем да бъдем след 11-та стъпка? само

докъдето можете да стигнете в една (последна) стъпка IN,в една от точките В 1или В 2 .Ако сме в точка В 1,нямаме избор (принудителен контрол): трябва да отидем на изток и това ще ни струва 10 единици. Нека напишем това число 10 в кръг близо до точката В 1,и показваме оптимален контрол с къса стрелка, излизаща от В 1и насочена на изток. За точка НА 2контролът също е принуден (север), дебитът до края е 14, ще го напишем в кръг в точката В 2 .По този начин се извършва условната оптимизация на последната стъпка и условната оптимална печалба за всяка от точките е Б 1, Б 2намерени и записани в съответния кръг.

Сега нека оптимизираме предпоследната (11-та) стъпка. След предпоследната (10-та) стъпка може да се окажем в една от точките C 1, C 2, C 3(фиг. 13.4). Нека намерим за всеки от тях условното оптимално управление и условното оптимално усилване. За точка C 1принудителен контрол: отидете на изток;

ще ни струва 21 единици до края (11 на тази стъпка, плюс 10, написани в кръга на В 1).Записваме числото 21 в кръг на точката C 1.За точка C 2контролът вече не е принудителен: можем да вървим както на изток, така и на север. В първия случай ще изразходваме 14 единици на тази стъпка и от НА 2Остават още 14, общо 28 единици. Ако отидем на север, ще похарчим 13 + 10, за общо 23 единици. Това означава, че условното оптимално управление в точката C 2 -отидете на север (маркираме това със стрелка и записваме числото 23 в кръг близо до C 2),За точка C 3контролът отново е принуден („с“), това ще струва 22 единици до края (поставете стрелката на север, напишете числото 22 в кръг на C 3).

По същия начин, „отстъпвайки“ от предпоследната стъпка назад, намираме за всяка точка с целочислени координати условното оптимално управление („c“ или „c“), което означаваме със стрелка, и условното оптимално усилване (консумация към край на пътя), който записваме в кръг. Изчислява се по следния начин: дебитът на тази стъпка се добавя към вече оптимизирания дебит, изписан в кръга, където сочи стрелката. Така на всяка стъпка оптимизираме само тази стъпка, а следващите вече са оптимизирани. Крайният резултат от процедурата за оптимизация е показан на фиг. 13.5.

Така условната оптимизация вече е завършена: без значение в коя от възловите точки се намираме, вече знаем накъде да отидем (стрелка) и колко ще ни струва да стигнем до края (числото в кръга). В кръг в точка Аоптималното усилване се записва за цялата конструкция на пътя от А V В:

W* = 118.

Сега остава да се построи безусловно оптимално управление - траектория, водеща от АИ INпо най-евтиния начин. За да направите това, трябва само да „слушате стрелките“, тоест да прочетете какво ви инструктират да правите на всяка стъпка. Тази оптимална траектория е отбелязана на фиг. 13,5 кръгче два пъти. Съответният безусловен оптимален контрол ще бъде:

x* =(s, s, s, s, in, in, s, in, in, in, in, in)

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

Обърнете внимание, че по време на условна оптимизация може да се сблъскаме със случай, когато и двата контрола за дадена точка от равнината са оптимални, т.е., те водят до еднакъв разход на средства от тази точка до края.Например, в точка с координати (5; 1) и двата контрола „c“ и „b“ са оптимални и дават дебит до края, равен на 62. Ние произволно избираме който и да е от тях (в нашия случай избрахме „c“; със същия успех бихме могли да изберем „c“ “). Такива случаи на двусмислен избор на оптимално управление постоянно се срещат в динамичното програмиране; в бъдеще няма да ги маркираме специално, а просто ще избираме произволно някоя от еквивалентните опции. Разбира се, оптималният контрол на целия процес, но не и оптималното усилване, може да зависи от този произвол. Като цяло при задачите на динамичното програмиране (както и при задачите на линейното програмиране) решението далеч не винаги е единственото.

Сега нека се върнем в началото и се опитаме да решим проблема по „наивен“ начин, избирайки на всяка стъпка, като започнем от първата, най-печелившата (за тази стъпка) посока (ако има две от тях, изберете която и да е ). По този начин ще придобием контрол

x = (c, s, в, в, в, в, s, в, в, в, s, s).

Нека изчислим разходите за тази траектория. Те ще бъдат равни У=10 +12 +8+10 +11 +13 +15+8 + +10+9+8+14=128, което със сигурност е повече от W* = 118. В този случай разликата не е много голяма, но в други може да е значителна.

В проблема, решен по-горе, условията бяха умишлено опростени до крайност. Разбира се, никой няма да кара железопътна линия „на стъпала“, движейки се само на север или на изток. Направихме това опростяване, за да избираме във всяка точка само от две контроли: „c“ или „c“. Вместо две възможни посоки би било възможно да се въведат няколко от тях и освен това да се предприемат по-малки стъпки; Това не е от принципно значение, но, разбира се, усложнява и удължава изчисленията.

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

Нека направим една мимолетна забележка. Внимателният читател вероятно е забелязал, че в нашия проблем точките АИ IN(начало и край) по принцип не се различават един от друг: би било възможно да се конструират условни оптимални управления не от край към начало, а от начало до край, а безусловни - в обратна посока. Наистина, това е вярно: във всеки проблем с динамично програмиране „началото“ и „краят“ могат да бъдат разменени. Това е напълно еквивалентно на описания по-горе метод по отношение на изчисленията, но е малко по-малко удобно, когато се обяснява устно идеята на метода: по-лесно е да се спори, като се позовава на „вече установени“ условия в началото на дадена стъпка отколкото на тези, които все още „предстоят“ след тази стъпка. По същество и двата подхода са напълно равностойни.

2. Проблем с разпределението на ресурсите.Методът на динамично програмиране ви позволява успешно да решавате много икономически проблеми (вижте например). Нека разгледаме една от най-простите подобни задачи. Имаме на разположение известен резерв от средства (ресурси) ДА СЕ,които трябва да се разпределят между Tпредприятия P 1, P 2, ..., P m. Всяко от предприятията П азкогато инвестирате малко пари в него хгенерира доход в зависимост от х, т.е. представляващи някакъв вид функция ( х). Всички функции ( х) (аз = 1, 2, ..., T)са дадени (разбира се, тези функции са ненамаляващи). Въпросът е как трябва да се разпределят средствата? ДА СЕ.между предприятията, така че общо да дават максимален доход?

Този проблем се решава лесно с помощта на метода на динамичното програмиране.Въпреки че във формулировката си не се споменава време, все пак можете мислено да разгърнете операцията по разпределяне на средства в някаква последователност, като първата стъпка е инвестирането на средства в предприятие П 1, второто - към П 2 и т.н.

Управлявана система Св този случай средствата или ресурсите, които се разпределят. Състояние на системата Спреди всяка стъпка се характеризира с едно число С-паричен резерв от средства, които все още не са инвестирани. В този проблем „стъпковите контроли“ са средството x 1, x 2, ..., x 3,разпределени на предприятия. Необходимо е да се намери оптималното управление, т.е. такъв набор от числа x 1, x 2, ..., x m,при което общият доход е максимален:

(13.1)

Нека решим тази задача първо в обща, формулна форма, а след това за конкретни числени данни. Ще намерим за всеки по нещо азна тата стъпка е условната оптимална печалба (от тази стъпка до края), ако сме подходили към тази стъпка с резерв от средства С.Нека обозначим условното оптимално усилване W i (S),а съответният условен оптимален контрол са вложените средства в аз-то предприятие, - xi(S).

Нека започнем оптимизацията от последния, T -та стъпка. Нека подходим към тази стъпка с останалите средства С.Какво да правим? Очевидно инвестирайте цялата сума Сизцяло в предприятие П м. Следователно, условно оптимално управление на м-стъпка: дайте всички налични средства на последното предприятие С,т.е.

и условната оптимална печалба

W m (S) = (S).

Дадена е цяла гама от значения С(поставяйки ги достатъчно близо), за всяка стойност ние Сще знаем xm(S)И Wm(S).Последната стъпка е оптимизирана.

Да преминем към предпоследния, (T- 1)та стъпка. Нека се обърнем към него с резерв от средства С.Нека обозначим W m -1 (S)условно оптимално изплащане на последните две стъпки: ( м- 1) та и м-m (който вече е оптимизиран). Ако изберем чрез ( м- 1)та стъпка ( м- 1) средства на предприятието Х,тогава ще остане последната стъпка S - x.Нашата печалба в последните две стъпки ще бъде равна на

,

и трябва да намерите нещо подобно Х,при което тази печалба е максимална:

Знакът означава, че максималната стойност се взема над всички Х,възможно (инвестирайте повече от С,ние не можем), от израза във къдрави скоби. Този максимум е условната оптимална печалба за последните две стъпки, в противен случай стойността Х,при което се постига този максимум е условното оптимално управление на (T- 1)та стъпка.

и съответното условно оптимално управление x i (S) -след това стойността Х,при което се достига този максимум.

Продължавайки по този начин, най-накрая ще стигнем до 1-во предприятие P 1. Тук няма да е необходимо да променяме стойностите С;знаем със сигурност, че резервът от средства преди първата стъпка е равен на ДА СЕ:

И така, максималната печалба (доход) от всички предприятия е намерена. Сега всичко, което остава, е да „прочетете препоръките“. Това значение Х,при което се постига максимум (13.4) и има оптимален контрол на 1-ва стъпка. След като инвестираме тези средства в първото предприятие, ще ни останат ДА СЕ- .„Четене“ на препоръката за тази стойност С,Разпределяме оптималния размер на средствата на второто предприятие:

,

и т.н. до края.

Сега нека решим числен пример. Първоначален запас от средства К = 10 (условни единици), като се изисква оптималното му разпределение между пет предприятия (t = 5). За простота ще приемем, че са инвестирани само цели суми средства. Функции на дохода ( х) са дадени в таблица 13.1.

Таблица 13.1

Във всяка колона, започвайки от определен размер на инвестицията, доходът спира да се увеличава (в действителност това съответства на факта, че всяко предприятие е в състояние да „приеме“ само ограничено количество средства).

Нека извършим условна оптимизация, както е описано по-горе, като започнем от последната, 5-та стъпка. Всеки път, когато пристъпваме към следващата стъпка, имайки резерв от средства С,опитваме се да разпределим тази или онази сума средства за тази стъпка, вземаме печалбите на тази стъпка съгласно таблица 13.1, добавяме ги с вече оптимизираните печалби на всички следващи стъпки до края (като се има предвид, че вече имаме по-малко останали средства, просто за тази сума средства, която сме подчертали) и намерете инвестицията, при която тази сума достига максимум. Тази инвестиция е условният оптимален контрол на тази стъпка, а самият максимум е условната оптимална печалба.

Таблица 13.2 показва резултатите от условната оптимизация за всички стъпки. Таблицата е структурирана по следния начин: първата колона дава стойностите на запасите от средства S, sс които подхождаме към тази стъпка. Таблицата е допълнително разделена на пет двойки колони, съответстващи на номера на стъпката. Първата колона на всяка двойка съдържа стойността

Таблица 13.2

условно оптимално управление, във втория - условно оптимално усилване. Таблицата се попълва отляво надясно, отгоре надолу. Решението на петата - последна - стъпка е принудително: всички средства са разпределени;

Във всички останали стъпки решението трябва да бъде оптимизирано. В резултат на последователна оптимизация на 5-та, 4-та, 3-та, 2-ра и 1-ва стъпка ще получим пълен списък с всички препоръки за оптимален контрол и безусловното оптимално усилване W*за цялата операция - в случая е равно на 5,6. В последните две колони на таблица 13.2 е попълнен само един ред, тъй като знаем точно състоянието на системата преди началото на първата стъпка:

S 0 = К = 10. Оптималните контроли на всички стъпки са подчертани с рамка. Така получихме окончателното заключение: трябва да разпределим две единици от десет на първото предприятие, пет единици на второто, две на третото, нито едно на четвъртото и едно звено на петото. При това разпределение доходът ще бъде максимален и равен на 5,6.

За да стане ясно на читателя как се попълва таблица 13.2, ще демонстрираме това с едно примерно изчисление. Нека, например, трябва да оптимизираме решението х 3(7)- какво да правим на третата стъпка, ако подходим с резерв от средства S= 7, а колко е максимумът, който можем да спечелим на всички останали

Таблица 13.3

стъпки, включително третата? Да приемем, че всички стъпки след третата (4-та и 5-та) вече са оптимизирани, т.е. първите две двойки колони на Таблица 13.2 са попълнени. Ще намерим х 3 (7) и W 3(7). За да направим това, ще създадем спомагателна таблица (виж Таблица 13.3). Първата му колона изброява всички възможни прикачени файлове хна третата стъпка, не повече от S = 7.Във втората колона - какво ще остане след такава инвестиция от резерва на средствата S = 7.В третата колона - печалбите в третата стъпка от инвестиране на средства хв третото предприятие се попълва съгласно колоната (Таблица 13.1). В четвъртата колона - оптималните печалби на всички оставащи стъпки (четвърта и пета) при условие, че сме достигнали четвъртата стъпка с оставащите средства (попълва се в колоната аз = 4 таблици 13.2). В петата колона - сумата от две печалби: стъпка и допълнително оптимизирана за дадена инвестиция хв третата стъпка.

От всички печалби в последната колона се избира максимумът (в таблица 13.3 той е равен на W 3(7) = 3,6 и съответната контрола х(7) = 2).

Възниква въпросът: какво ще стане, ако в спомагателна таблица като 13.3 максимумът се постигне при повече от един х, а с две или повече? Ние отговаряме: няма абсолютно никакво значение кой ще изберете; печалбите не зависят от това. По принцип при задачите на динамичното програмиране решението не трябва да е уникално (вече споменахме това).

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

Като пример, разгледайте проблема за зареждане на машина (вече го споменахме в предишната глава): има определен набор от обекти P 1, P 2,..., P n (всеки в едно копие); теглата им са известни q 1 , q 2 , ..., q nи цена от 1, с 2, ..., с n.Товароносимостта на машината е Q.Въпросът е кои елементи трябва да се вземат в колата, така че общата им цена (с общо тегло Q)максимално ли беше?

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

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

Целта на изследването на операциите е предварителна количествена обосновка на оптимални решения, от които може да има повече от едно. Окончателният избор на решение излиза извън обхвата на изследването на операциите и се прави с помощта на така наречената теория на решенията.

Всяка задача за изследване на операции има първоначални „дисциплиниращи“ условия, т.е. такива първоначални данни, които са фиксирани от самото начало и не могат да бъдат нарушавани. Взети заедно, те образуват така нареченото множество от възможни решения.

За да сравните различни решения по отношение на ефективността, трябва да имате количествен критерий, наречен показател за ефективност(или целева функция). Този индикатор е избран да отразява целевата ориентация на операцията.

Често операцията е придружена от действието на случайни фактори. След това като показател за ефективност се приема не самата стойност, която бихте искали да оптимизирате, а нейната средна стойност (или математическо очакване).

Понякога една операция, придружена от случайни фактори, преследва такава цел А, което може да бъде постигнато напълно или да не бъде постигнато изобщо (като „да-не“). Тогава вероятността за постигане на тази цел се избира като показател за ефективност стр(А). (Ако стр(А) = 0 или 1, тогава стигаме до проблема с „черната кутия“, известен в кибернетиката.)

Избирането на грешен индикатор за ефективност е много опасно. Операциите, организирани по неудачно избран критерий, могат да доведат до неоправдани разходи и загуби. (Например „вал“ като основен критерий за оценка на икономическата дейност на предприятието.)

1.3. Обща постановка на проблема за изследване на операциите

Проблемите на изследването на операциите попадат в две категории: а) напред и б) назад.

Директни задачиотговорете на въпроса: на какво ще бъде равен показателят за ефективност? З, ако при дадени условия г  Yще бъде взето някакво решение х  х. За решаването на такъв проблем се конструира математически модел, който позволява да се изрази показателят за ефективност чрез дадени условия и решение, а именно:

Където
определени фактори (първоначални данни),

контролни променливи (решение),

З– индикатор за ефективност (целева функция),

Е– функционална зависимост между променливите.

Тази зависимост се изразява по различен начин в различните модели. Зависимост между И обикновено се изразява в ограничения върху

Ако видът на зависимостта Ее известен, тогава индикаторът Зсе намира чрез директно заместване И в тази функционалност.

Обратни задачиотговори на въпроса: как при тези условия изберете решение
така че показателят за ефективност Зобърнат на максимум (минимум). Този проблем се нарича проблем за оптимизиране на решението.

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

Трябва да се намеритакова решение
при което показателят за ефективност З = избирам:

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

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

Оперативни изследвания

Оперативни изследвания(IO) (английски) Изследване на операциите, Орегон) - дисциплина, занимаваща се с разработването и прилагането на методи за намиране на оптимални решения, основани на математическо моделиране, статистическо моделиране и различни евристични подходи в различни области на човешката дейност. Понякога се използва името математически методи за изследване на операциите.

Изследването на операциите е прилагането на математически, количествени методи за обосноваване на решения във всички области на целенасочената човешка дейност. Изследването на операциите започва, когато се използва един или друг математически апарат за обосноваване на решения. Операция- всяко събитие (система от действия), обединено от един план и насочено към постигане на някаква цел (например дейностите от задачи 1-8, изброени по-долу, ще бъдат операции). Една операция винаги е контролирано събитие, т.е. зависи от лицето как да избере параметрите, които характеризират нейната организация (в широк смисъл, включително набор от технически средства, използвани в операцията). Решение(успешно, неуспешно, разумно, неразумно) - всеки специфичен набор от параметри в зависимост от дадено лице. Оптимално- решение, което е за предпочитане пред други въз основа на една или друга характеристика. Цел на оперативните изследвания- предварителна количествена обосновка на оптимални решения въз основа на показателя ефективност. Самото вземане на решение надхвърля обхвата на оперативните изследвания и попада под отговорността на отговорното(ите) лице(а). Елементи на решението- параметри, комбинацията от които образува решение: числа, вектори, функции, физически характеристики и др. Ако елементите на решението могат да бъдат контролирани в определени граници, тогава зададените („дисциплиниращи“) условия (ограничения) се фиксират незабавно и не могат да бъдат нарушени (товароносимост, размери, тегло). Такива условия включват средствата (материални, технически, човешки), с които дадено лице има право да се разпорежда, и други ограничения, наложени на решението. Тяхната съвкупност формира много възможни решения.

Примери: Изготвен е план за транспортиране на стоки от точките на тръгване A 1, A 2, ..., A m до дестинации B 1, B 2, ..., B n. Елементите на решението са числата x ij, показващи колко товар ще бъде изпратен от i-тата точка на отпътуване A i до j-тата дестинация B j. Решението е набор от числа x 11, x 12, …, x m1, x m2, …, x mn

Бъдещата връзка между IR и теорията на (сложните) системи не е напълно ясна.

Типични задачи

Взети от различни области на практиката

1. План за снабдяване на предприятието
2. Изграждане на участък от магистралата
3. Продажба на сезонни стоки
4. Снегозащита на пътища
5. Рейд срещу подводници
6. Пробен контрол на продуктите
7. Медицински преглед
8. Библиотечно обслужване

Някои примери за формулировки на проблеми, свързани с IR:

• Задачи за планиране и изпращане, като например проблем с планиране на Open Shop, проблем с график на Flow Shop, проблем с график на Job Shop. bg: График за работни места ) и т.н.

Характерна черта на изследването на операциите е системният подход към проблема и анализа. Системният подход е основният методологичен принцип на изследването на операциите. Тя е следната. Всеки проблем, който се решава, трябва да се разглежда от гледна точка на влиянието му върху критериите за функциониране на системата като цяло. Характерно за оперативните изследвания е, че с всеки разрешен проблем могат да възникнат нови проблеми. Важна характеристика на изследването на операциите е желанието да се намери оптималното решение на даден проблем (принципът на „оптималността“). На практика обаче такова решение не може да бъде намерено поради следните причини:

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

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

AI се използва главно от големи западни компании при решаване на проблеми с планирането на производството (контролинг, логистика, маркетинг) и други сложни задачи. Използването на изкуствения интелект в икономиката позволява да се намалят разходите или, казано по друг начин, да се увеличи производителността на предприятието (понякога няколко пъти!). IO се използва активно от армиите и правителствата на много развити страни за оценка на бойната ефективност на оръжия, военна техника и военни формирования, разработване на нови видове оръжия, решаване на сложни проблеми за снабдяване на армии, насърчаване на армии, разработване на военни стратегии, развитие на междудържавна търговия механизми, прогнозиране на развитието (например климат) и т.н. Сложни проблеми с повишена важност се решават с помощта на AI методи на суперкомпютри, но разработката се извършва на прости персонални компютри. AI методите могат да се използват и в малки предприятия, използващи компютър.

История

В началото на войната бойните патрули на съюзническата авиация за откриване на вражески кораби и подводници са дезорганизирани. Участието на специалисти по изследване на операциите в планирането направи възможно установяването на маршрути за патрулиране и графици на полети, при които вероятността обектът да остане незабелязан е намалена до минимум. Получените препоръки бяха приложени за организиране на патрули над Южния Атлантик с цел прихващане на германски кораби с военни материали. От петте вражески кораба, които пробиха блокадата, три бяха прихванати по пътя от Япония за Германия, един беше открит и унищожен в Бискайския залив и само един успя да избяга благодарение на внимателен камуфлаж.

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

Във Великобритания национализацията на някои видове промишленост създаде възможност за провеждане на икономически изследвания, базирани на математически модели в национален мащаб. Изследването на операциите започна да се използва при планирането и изпълнението на няколко държавни, социални и икономически дейности. Например, проучвания, проведени за Министерството на храните, позволиха да се предвиди въздействието на правителствената ценова политика върху семейния бюджет.

В САЩ въвеждането на методите за изследване на операциите в практиката на икономическото управление се случи малко по-бавно - но дори и там много опасения скоро започнаха да привличат специалисти от този вид за решаване на проблеми, свързани с регулирането на цените, повишаването на производителността на труда, ускоряването на доставката на стоки за потребителите и др. Лидерството в областта на прилагането на методите за контрол на научните изследвания принадлежи на авиационната индустрия, която не можеше да не върви в крак с нарастващите изисквания към ВВС. През 50-60-те години на миналия век на Запад бяха създадени дружества и центрове за изследване на операциите, които публикуваха свои собствени научни списания; повечето западни университети включиха тази дисциплина в своите учебни програми.

Най-голям принос за формирането и развитието на новата наука направиха Р. Акоф, Р. Белман, Й. Данциг, Г. Кун, Т. Саати (Английски)Руски , Р. Черман (САЩ), А. Кофман, Р. Форд (Франция) и др.

Важна роля в създаването на модерен математически апарат и развитието на много области на изследването на операциите принадлежи на Л. В. Канторович, Б. В. Гнеденко, М. П. Бусленко, В. С. Михалевич, Н. Н. Моисеев, Ю. М. Ермолаев, Н. З. Шору и др.

За изключителния си принос в развитието на теорията за оптималното използване на ресурсите в икономиката академик Л. В. Канторович, заедно с проф. Т. Купманс (САЩ), е удостоен с Нобелова награда за икономика през 1975 г.

Вижте също

Бележки

Литература

• Хемди А. Таха.Въведение в изследването на операциите = Изследване на операциите: Въведение. - М.: Уилямс, 2007. - 912 с. - ISBN 0-13-032374-8
• Дегтярев Ю. И.Изследване на операции: учебник за университети, специализирани в автоматизирани системи за управление. - М.: Висше училище, 1986.
• Грешилов А. А.Математически методи за вземане на решения. - М.: MSTU im. Н.Е. Бауман, 2006. - 584 с. - ISBN 5-7038-2893-7

Връзки

• Оперативни изследванияв директорията за връзки на Open Directory Project (dmoz).

Фондация Уикимедия. 2010 г.

Вижте какво е „Изследване на операциите“ в други речници:

оперативни изследвания- — изследване на операциите Приложна област на кибернетиката, използвана за решаване на практически организационни (включително икономически) проблеми. Това е комплекс... Ръководство за технически преводач

Приложна посока на кибернетиката, използвана за решаване на организационни (включително икономически) проблеми (разпределение на ресурсите, управление на запасите, подреждане и координация и др.). Основният метод е системен анализ на целенасочени действия... ... Голям енциклопедичен речник

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

Конструиране, развитие и приложения на математиката. модели за вземане на оптимални решения. Съдържанието на теоретичното аспект на I. o. са анализ и решение на математиката. проблеми със селекцията в даден набор от допустими решения на X елемент, удовлетворяващ тези или ... Математическа енциклопедия

ОПЕРАЦИОННИ ИЗСЛЕДВАНИЯ- метод за изучаване, анализ и оценка на операциите, техните количествени и качествени показатели. Проучва хода и резултатите от операциите, като взема предвид взетите решения, количествените и качествени характеристики на баланса на силите и средствата, бойните методи... ... Войната и мирът в термини и определения

Приложна посока на кибернетиката, използвана за решаване на организационни (включително икономически) проблеми (разпределение на ресурсите, управление на запасите, подреждане и координация и др.). Основният метод е системен анализ на целеви... ... енциклопедичен речник

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

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

ОПЕРАЦИОННИ ИЗСЛЕДВАНИЯ- направление в икономическите и математическите методи, основаващи се на моделиране на математически процеси и явления. И около. включва систематичен подход, състоящ се от търсене на значими взаимодействия при оценка на дейностите или стратегията на която и да е част... ... Голям икономически речник

ОПЕРАЦИОННИ ИЗСЛЕДВАНИЯ- направление в изследването и проектирането на системи за управление на базата на математическо моделиране на процеси и явления. И около. включва систематичен подход, състоящ се от търсене на съществуващи взаимодействия при оценка на дейностите или стратегията на която и да е част... Енциклопедичен речник по психология и педагогика Прочетете повече

1. Основни понятия на AI

И ОТНОСНО – научен дисидент, ангажиран с разработването и практическото прилагане на методи за най-ефективно управление на различни организационни системи.

IO включва следните раздели:

1) математическа програма. (обосновка на планове, програми за стопанска дейност); включва раздели: линейна програма, нелинейна програма, динамична програма

2) теория на масовото обслужване, базирана на теорията на случайните процеси;

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

При решаването на конкретен контролен проблем използването на AI методи включва:

Изграждане на икономико-математически модели за решаване на задачи в сложни ситуации или условия на несигурност;

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

Основни понятия и дефиниции на ИО.

Операция – всяка контролирана дейност, насочена към постигане на цел. Резултатът от операцията зависи от метода на нейното изпълнение, организация, в противен случай - от избора на определени параметри. Една операция винаги е контролирано събитие, тоест от нас зависи как да изберем някои параметри, които характеризират нейната организация. „Организация“ тук се разбира в широкия смисъл на думата, включително набор от технически средства, използвани в операцията.

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

Операционен модел – това е доста точно описание на операцията с помощта на математически апарат (различни видове функции, уравнения, системи от уравнения и неравенства и др.). Изготвянето на модел на операция изисква разбиране на същността на описваното явление и познаване на математическия апарат.

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

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

Проблеми с опашката са посветени на изследването и анализа на обслужващи системи с опашки от приложения или изисквания и се състоят в определяне на показателите за ефективност на системите, техните оптимални характеристики, например определяне на броя на обслужващите канали, времето за обслужване и др.

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

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

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

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

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

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

2. Общ проблем с линейна програма. Оптимизиране на решението

Икономико-математически модел

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

Методите на ЛП се прилагат към практически проблеми, при които: 1) е необходимо да се избере най-доброто решение (оптимален план) от множество възможни; 2) решението може да бъде изразено като набор от стойности на някои променливи; а) ограниченията, наложени на възможните решения от специфични условия на проблема, се формулират под формата на линейни уравнения или неравенства; 4) целта се изразява под формата на линейна функция на основните променливи. Стойностите на целевата функция, позволяващи сравнение на различни решения, служат като критерий за качеството на решението.

За практическо решаване на икономически проблем с помощта на математически методи, първо трябва да се запише с помощта на икономико-математически модел. Икономико-математическият модел е математическо описание на икономическия процес или обект на изследване. Този модел изразява законите на икономическия процес в абстрактна форма, използвайки математически зависимости.

Обща схема на моделиране: I

1) избор на определен брой променливи величини, чието присвояване на числени стойности еднозначно определя едно от възможните състояния на изследваното явление;

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

3) количествен израз на избрания критерий за оптималност под формата на целева функция; аз

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

Обща задача за линейно програмиранеима формата:

Дадена е система от m линейни уравнения и неравенства с n променливи

и линейна функция

Необходимо е да се намери решение на системата X=(x1,x2,…,xj,…,xn), където линейната функция F приема оптималната (т.е. максимална или минимална) стойност.

Система (1) се нарича система с ограничения, а функцията F се нарича линейна функция, линейна форма, целева функция или целева функция.

По-накратко, общият проблем с линейното програмиране може да бъде представен като:

с ограничения:

Оптимално решение (или оптимален план)на проблем с LP е решение X=(x1,x2,…,xj,…,xn), система от ограничения (1), която удовлетворява условие (3), при което линейната функция (2) приема оптималната (максимална или минимална) стойност.

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

Специален случай на каноничен проблем е проблем в основна форма, характеризиращ се с това, че всички коефициенти на ограничителния вектор bса неотрицателни и във всяко уравнение има променлива с коефициент 1, която не е включена в нито едно от другите уравнения. Променлива с това свойство се нарича основна.

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

4 . Елементи на линейната алгебра

Система от m линейни уравнения с n променливи има формата

или в кратка форма

Всякакви m променливи от система от m линейни уравнения с n променливи (m< n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Такой определитель часто называют базисным минором матрицы А. Тогда остальные m–n переменных называются неосновными (или свободными).

За да се реши система (2.1) при условие m< n сформулируем утверждение.

Твърдение 2.1. Ако за систематамлинейни уравнения снпроменливи (м < н) рангът на матрицата от коефициенти за променливите е равен на m, т.е. Ако има поне една група основни променливи, тогава тази система е неопределена и всеки произволен набор от стойности на неосновни променливи съответства на едно решение на системата.

Решение X=(x1,x2,…,xn) на система (2.1) се нарича допустима, ако съдържа само неотрицателни компоненти, т.е. xj>=0 за всяко j=1,n. В противен случай решението се нарича невалидно.

Сред безкрайния брой решения на системата се разграничават така наречените основни решения.

Основно решениена система от m линейни уравнения с n променливи е решение, в което всички n–m второстепенни променливи са равни на нула.

В задачите на линейното програмиране особен интерес представляват допустимите основни решения или, както се наричат ​​още, референтни планове. Основно решение, в което поне една от главните променливи е равна на нула, се нарича изродено.

Изпъкнали множества от точки

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

Набор от точки се нарича изпъкнал, ако то заедно с произволни две свои точки съдържа цялата отсечка, свързваща тези точки.

Изпъкналите множества имат важно значение Имот: Пресечната точка (обща част) на произволен брой изпъкнали множества е изпъкнало множество.

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

Точка от множество се нарича вътрешна, ако част от неговата околност съдържа точки само от това множество.

Точка от множество се нарича гранична точка, ако някоя от неговите околности съдържа както точки, принадлежащи на даденото множество, така и точки, които не му принадлежат.

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

На фиг. 2.4 показва примери за различни точки на многоъгълника: вътрешни (точка M), гранични (точка N) и ъглови (точки A, B, C, D, E). Точка A е ъглова точка, тъй като за всеки сегмент, изцяло принадлежащ на многоъгълник, например сегмент AP, той не е вътрешен; точка A е вътрешна за отсечката KL, но тази отсечка не принадлежи изцяло на многоъгълника.

При изпъкнало множество ъгловите точки винаги съвпадат с върховете на многоъгълника (многостена), докато при неизпъкнало множество това не е необходимо. Множество от точки се нарича затворено, ако включва всички свои гранични точки. Множеството от точки се нарича ограничен, ако има топка (окръжност) с радиус с крайна дължина с център във всяка точка от множеството, която изцяло съдържа даденото множество; в противен случай се казва, че множеството е неограничено.

Изпъкнал затворен набор от точки в равнина, имащ краен брой ъглови точки, се нарича изпъкнал многоъгълник, ако е ограничен, и изпъкнал многоъгълен регион, ако е неограничен.

Геометричен смисъл на решения на неравенства, уравнения и техните системи

Нека разгледаме решенията на неравенствата.

Твърдение 1. Множеството от решения на неравенството с две променливи a11x1+a12x2<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1 , включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравен­ства a11x1+a12x2>=b1.

За да се определи желаната полуравнина (горна или долна), се препоръчва да се зададе произволна контролна точка, която не лежи на нейната граница - построената права линия. Ако едно неравенство е валидно в контролна точка, тогава то е валидно във всички точки на полуравнината, съдържаща контролната точка, и не е валидно във всички точки на другата полуравнина. Обратно, ако дадено неравенство не е изпълнено в контролна точка, то не е изпълнено във всички точки на полуравнината, съдържаща контролната точка, и е изпълнено във всички точки на другата полуравнина. За контролна точка е удобно да се вземе началото на координати O (0;0), което не лежи на построената права.

Нека разгледаме набор от решения на системи от неравенства.

Твърдение 2. Множеството от решения на съвместна система от линейни неравенства с две променливи е изпъкнал многоъгълник (или изпъкнала многоъгълна област).

Всяко от неравенствата, в съответствие с твърдение 1, определя една от полуравнините, която е изпъкнало множество от точки. Множеството от решения на съвместна система от линейни неравенства са точки, които принадлежат на полуравнините на решения на всички неравенства, т.е. принадлежат на тяхното пресичане. Според твърдението за пресичането на изпъкнали множества, това множество е изпъкнало и съдържа краен брой ъглови точки, т.е. е изпъкнал многоъгълник (изпъкнала многоъгълна област).

Координатите на ъгловите точки - върховете на многоъгълника - се намират като координати на пресечните точки на съответните прави.

При конструирането на области на решение за системи от неравенства могат да възникнат и други случаи: множеството от решения е изпъкнала многоъгълна област (фиг. 2.9, а); една точка (фиг. 2.9, b); празно множество, когато системата от неравенства е непоследователна (фиг. 2.9, c).

5 . Геометричен метод за решаване на задачи на ЛП

оптимално решение на проблема с LP

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

Теоремата показва основния начин за решаване на проблемите на LP. Всъщност, съгласно тази теорема, вместо да се изследва безкраен набор от възможни решения, за да се намери желаното оптимално решение сред тях, е необходимо да се изследват само краен брой ъглови точки на полиедъра на решението.

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

Теорема 2. Всяко допустимо базисно решение на задачата LP отговаря на ъглова точка на многостена на решението и обратно, на всяка ъглова точка на многостена на решението съответства допустимо базисно решение.

Едно важно следствие следва директно от теореми 1 и 2: Ако дадена ЛП задача има оптимално решение, то то съвпада с поне едно от нейните допустими базисни решения.

Така, оптимумът на линейната функция на задачата на ЛП трябва да се търси сред крайния брой нейни допустими базисни решения.

И така, наборът от възможни решения (полиедър на решението) на проблема с LP е изпъкнал многостен (или изпъкнала многостенна област), а оптималното решение на проблема се намира поне в една от ъгловите точки на полиедъра на решението.

Разгледайте проблема в стандартна форма с две променливи (П = 2).

Нека геометричният образ на ограничителната система е многоъгълник А Б В Г Д(фиг. 4.1). Необходимо е да се намери точка сред точките на този многоъгълник, в която линейната функция F=c1x1+c2x2 приема максимална (или минимална) стойност.

Да разгледаме т.нар линия на ниво линейна функция Е, т.е. линия, по която тази функция приема същата фиксирана стойност А, т.е. Е = а,или c1x1+c2x2=a.

На многоъгълника на решение намерете точката, през която минава линията на функционалното ниво Е с най-високото (ако линейната функция се максимизира) или най-ниското (ако се минимизира) ниво.

Уравнението на линията на нивото на функцията c1x1+c2x2=a е уравнението на правата линия. На различни нива Алиниите на нивото са успоредни, тъй като техните ъглови коефициенти се определят само от връзката между коефициентите c1 и c2 и следователно са равни. По този начин линиите на ниво функция Е – Това са своеобразни „паралели“, обикновено разположени под ъгъл спрямо координатните оси.

Важно свойство на линията на нивото на линейна функция е, че когато линията се измества паралелно в една посока, нивото само се увеличава, а когато се измества в другата посока, само намалява. Векторът c=(c1,c2), излизащ от началото, показва посоката на най-бързо нарастване на функцията F. Линията на нивото на линейната функция е перпендикулярна на вектора c=(c1,c2).

Процедурата за графично решаване на проблема с LP:

1. Конструирайте многоъгълник от решения.

2. Конструирайте вектор c=(c1,c2) ​​и първо начертайте линия на ниво линейна функция за него Е, например F=0.

3. Чрез успоредно движение на правата F=0 по посока на вектора c(-c) да се намери точката Amax(Bmin), в която F достига своя максимум (минимум).

1. Чрез съвместно решаване на уравненията на прави, пресичащи се в оптималната точка, намерете нейните координати.

2. Изчислете Fmax(Fmin).

Коментирайте.Минималната точка е „входната“ точка в полигона на решението, а максималната точка е „изходната“ точка от полигона.

6. Обща идея за симплексния метод. Геометрична интерпретация

Графичният метод е приложим за много тесен клас проблеми на линейното програмиране: той може ефективно да решава проблеми, съдържащи не повече от две променливи. Разгледани са основните теореми на линейното програмиране, от които следва, че ако дадена задача за линейно програмиране има оптимално решение, то то съответства на поне една ъглова точка на полиедъра на решението и съвпада с поне едно от допустимите основни решения на система от ограничения. Беше посочен начин за решаване на всяка задача на линейното програмиране: да се изброят краен брой възможни основни решения на системата от ограничения и да се избере сред тях това, на което целевата функция прави оптималното решение. Геометрично това съответства на изброяването на всички ъглови точки на полиедъра на решението. Такова изчерпателно търсене в крайна сметка ще доведе до оптимално решение (ако то съществува), но практическото му прилагане е свързано с огромни трудности, тъй като за реални проблеми броят на изпълнимите основни решения, макар и краен, може да бъде изключително голям.

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

Нека областта на възможните решения е представена с многоъгълник А Б В Г Д. Да приемем, че неговата ъглова точка Асъответства на първоначалното осъществимо базово решение. Произволното търсене би изисквало тестване на пет възможни основни решения, съответстващи на петте ъглови точки на многоъгълника. От чертежа обаче става ясно, че след вр Аизгодно е да се преместите в съседен връх IN,и след това до оптималната точка СЪС.Вместо пет, минахме само през три върха, подобрявайки последователно линейната функция.

Идеята за последователно подобряване на решението формира основата на универсален метод за решаване на проблеми с линейно програмиране - симплексен метод или метод на последователно подобряване на плана.

Геометричният смисъл на симплексния метод се състои в последователен преход от един връх на ограничителния полиедър (наречен начален) към съседния, при който линейната функция приема най-добрата (поне не най-лошата) стойност по отношение на цел на проблема; до намиране на оптималното решение – върхът, където се постига оптималната стойност на целевата функция (ако задачата има краен оптимум).

Симплексният метод е предложен за първи път от американския учен Дж. Данциг през 1949 г., но още през 1939 г. идеите на метода са разработени от руския учен Л.В. Канторович.

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

За прилагане на симплексния метод - последователно подобряване на решението - е необходимо да се овладее три основни елемента:

метод за определяне на всяко първоначално възможно основно решение на проблем;

правилото за преход към най-доброто (по-точно, не по-лошо) решение;

критерий за проверка на оптималността на намереното решение.

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

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

7 . Алгоритъм на симплексния метод.

Нека разгледаме решението на ZLP с помощта на симплексния метод и да го представим във връзка с проблема за максимизиране.

1. Въз основа на условията на задачата се съставя нейният математически модел.

2. Завършеният модел се преобразува в канонична форма. В този случай може да се идентифицира основа с първоначален референтен план.

3. Каноничният модел на проблема е написан под формата на симплексна таблица, така че всички свободни членове да са неотрицателни. Ако е избран първоначалният референтен план, преминете към стъпка 5.

Симплексна таблица: система от ограничителни уравнения и целева функция се въвеждат под формата на изрази, разрешени спрямо първоначалната база. Редът, в който са записани коефициентите на целевата функция F, се нарича F-линия или линия на целевата функция.

4. Първоначалният референтен план се намира чрез извършване на симплексни трансформации с положителни разрешаващи елементи, съответстващи на минималните симплексни отношения, и без да се вземат предвид знаците на елементите на F-реда. Ако по време на трансформациите се срещне 0-ред, чиито всички елементи, с изключение на свободния член, са нули, тогава системата от ограничителни уравнения за задачата е непоследователна. Ако срещнем 0-ред, в който, освен свободния член, няма други положителни елементи, тогава системата от ограничителни уравнения няма неотрицателни решения.

Ще наречем редукцията на система (2.55), (2.56) до нов базис симплекс трансформация . Ако симплексната трансформация се разглежда като формална алгебрична операция, тогава може да се забележи, че в резултат на тази операция ролите се преразпределят между две променливи, включени в определена система от линейни функции: едната променлива преминава от зависима към независима, а другата , напротив, от независим към зависим. Тази операция е известна в алгебрата като Джордан елиминационна стъпка.

5. Намереният първоначален план за поддръжка се проверява за оптималност:

а) ако в F-реда няма отрицателни елементи (без да се брои свободният термин), тогава планът е оптимален. Ако няма нули, тогава има само един оптимален план; ако има поне една нула, тогава има безкраен брой оптимални планове;

б) ако в F-реда има поне един отрицателен елемент, който съответства на колона от неположителни елементи, тогава;

в) ако има поне един отрицателен елемент в F-реда и има поне един положителен елемент в неговата колона, тогава можете да преминете към нов референтен план, който е по-близо до оптималния. За да направите това, посочената колона трябва да бъде обозначена като разрешаваща колона, използвайки минималното симплексно съотношение, да намерите разрешаващия ред и да извършите симплексна трансформация. Полученият референтен план отново се проверява за оптималност. Описаният процес се повтаря до получаване на оптимален план или докато се установи неразрешимостта на проблема.

Колоната от коефициенти за променлива, включена в основата, се нарича разрешаваща. По този начин, чрез избиране на променлива, въведена в основата (или избиране на разрешаваща колона) въз основа на отрицателния елемент на F-реда, ние гарантираме, че функцията F нараства .

Малко по-трудно е да се определи променливата, която да бъде изключена от базата. За да направят това, те съставят съотношенията на свободните членове към положителните елементи на разрешаващата колона (такива отношения се наричат ​​симплексни) и намират най-малката сред тях, която определя реда (разрешаваща), съдържащ изключената променлива. Изборът на променлива, изключена от основата (или изборът на разрешаваща линия) според минималната симплексна релация гарантира, както вече беше установено, положителността на базовите компоненти в новия референтен план.

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

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

2) съставят отношенията на елементите на колоната от свободни термини към съответните елементи на разрешаващата колона, които имат същите знаци (симплексни отношения);

3) изберете най-малкото от симплексните отношения. Това ще определи разрешаващия низ. Нека бъде напр. Р- линия;

4) в пресечната точка на разделящата колона и реда се намира разделящ елемент. Ако елементът от y-реда се окаже разрешаващ, то след симплексната трансформация свободният член на този ред ще стане положителен. В противен случай на следващата стъпка отново се осъществява достъп до t-реда. Ако проблемът е разрешим, тогава след определен брой стъпки няма да останат отрицателни елементи в колоната със свободни условия.

8. Метод на обратната матрица

Нека разгледаме LP от формата:

A – матрица на ограниченията;

C=(c1,c2,…,cn)–ред вектор;

X=(x1,x2,…,xn) – променливи;

е векторът на дясната страна.

Приемаме, че всички уравнения са линейно независими, т.е. ранг(а)=m. В този случай основата е минор от порядъка на матрицата A. Т.е. има поне една подматрица B от ред m, така че |B|<>0. Всички неизвестни, съответстващи на B, се наричат ​​основни. Всички останали са безплатни.

Нека B е някаква основа. Тогава чрез пренареждане на колоните на матрица A винаги можем да редуцираме A до формата A=(B|N),

където N е подматрица, състояща се от колони на матрица A, които не принадлежат към основата. По същия начин е възможно векторът x да се раздели на вектор от основни променливи и.

Всяко решение на задача (1) удовлетворява условието A*x=b и следователно системата приема следния вид:

защото |B|<>0, тогава има обратна матрица. Умножавайки отляво по обратното, получаваме:

- общо решение.

Базовото решение (спрямо основата B) е частно решение на задача (2), получено при условието. След това се определя еднозначно.

Основното решение се нарича осъществими, Ако.

Базата, съответстваща на внедреното основно решение. Наречен приложима основа. Основното решение се нарича изродено, ако векторът има нулеви компоненти.

Общото решение съдържа всички съществуващи решения. Да се ​​върнем към целевата функция. Въвеждаме Cb – коефициенти пред основните променливи, Cn – останалите.

Така получаваме. Заменяме от общото решение:

Изявление. Критерий за оптималност на основното решение.

Да речем. Тогава основното решение е оптимално. Ако, тогава основното решение не е оптимално.

документ:Нека бъде. Нека разгледаме основното решение, .

Следователно е стойността на целевата функция за основното решение.

Нека има друго решение: (Xb,Xn).

Тогава да погледнем

По този начин основното решение е най-мин. Нека, напротив, да не се изпълни, т.е. съществува.

Тогава има решение, за което стойността на целевата функция ще бъде по-малка от стойността на целевата функция за основното решение.

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

Как да определите? Всички свободни променливи освен все още са равни на 0.

След това в общото решение, където.

Да извадим: – необходимо условие.

Основно решение се нарича редовно ако. Извличаме променливата от основата. При ново решение целевата функция намалява, т.к

Алгоритъм:

1.LP задача в стандартна форма.

2. Оставяме линейно независими уравнения.

3. Намерете матрица B такава, че |B|<>0 и основното решение.

Изчисляваме:

ако, тогава има оптимално решение – това е основното решение;

if, тогава намираме компонента, добавяме го и по този начин намираме друго решение; – при което една от основните променливи =0. Премахваме тази променлива от основата и въвеждаме xi. Получихме нова основа B2, спрегната на основата B1. След това изчисляваме отново.

1. Ако има оптимално решение, то след краен брой стъпки ще го получим.

Геометрично, процедурата се интерпретира като преход от ъглова точка към спрегната ъглова точка по границата на множеството X - множеството от решения на проблема. защото има краен брой ъглови точки и строгото намаляване на функцията F(x) забранява преминаването през една и съща крайна точка два пъти, тогава ако има оптимално решение, тогава след краен брой стъпки ще го получим.

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

Задача.За производството на два вида продукти P1 и P2 се използват четири вида ресурси S1, S2, S3, S4. Дадени са запасите от ресурси, броят единици ресурси, изразходвани за производството на единица продукция. Известна е печалбата, получена от единица продукция P1 и P2. Необходимо е да се състави производствен план, при който печалбата от продажбата му да бъде максимална.

Задачааз(оригинал):

F=c1x1+c2x2+…+CnXn->max с ограничения:

и условието за неотрицателност x1>=0, x2>=0,…,Xn>=0

Съставете производствен план X=(x1,x2,…,Xn), в който печалбата (приходите) от продажбите на продукта ще бъде максимална, при условие че потреблението на ресурси за всеки вид продукт не надвишава наличните резерви

ЗадачаII(двойно)

Z=b1y1+b2y2+…+BmYm->мин

с ограничения:

и условието за неотрицателност

y1>=0, y2>=0,…,yn>=0.

Намерете такъв набор от цени (оценки) на ресурсите Y=(y1,y2,…,yn), при които общите разходи за ресурси ще бъдат минимални, при условие че разходите за ресурси при производството на всеки вид продукт ще бъдат не по-малко от печалбата (прихода) от продажбата на тези продукти

В горния модел bi(i=1,2,…,m) означава ресурсния резерв Si; aij – броят единици ресурс Si, изразходвани за производството на единица продукция Pj(j=1,2,…,n); cj– печалба (приход) от продажбата на единица продукция Pj (или цена на продукта Pj) .

Да предположим, че дадена организация е решила да закупи ресурси S1, S2,..., Sm на предприятието и е необходимо да се определят оптимални цени за тези ресурси y1, y2,..., ym. Очевидно закупуващата организация е заинтересована да изразходва всички ресурси Z в количества b1,b2,…,bm при цени y1,y2,…,ym съответно са били минимални, т.е. Z=b1,y1+b2y2+…+bmym->min.

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

За да се произведе единица продукт P1, a11 единици ресурс S1, a21 единици ресурс S2,...., aj1 единици ресурс Si1,......, am1 единици ресурс Sm се консумират на цена y1 ,y1,...,yi,...,ym, съответно. Следователно, за да се удовлетворят изискванията на продавача, разходите за ресурси, изразходвани за производството на единица продукт P1, трябва да бъдат не по-малки от неговата цена c1, т.е. a11y1+a21y2+…+am1ym>=c1.

По същия начин можете да създадете ограничения под формата на неравенства за всеки тип продукт P1, P2,…Pn. В дясната част на таблицата са дадени икономико-математическият модел и съдържателна интерпретация на така получената дуална задача II.

Цените на ресурсите y1,y1,…,yi,…,ym са получили различни имена в икономическата литература: счетоводство, имплицитно, сянка . Значението на тези имена е, че е условно , "фалшиви" цени. За разлика от „външните“ цени c1,c2,…,cn за продукти, известни по правило преди началото на производството, цените на ресурсите y1,y2,…,ym са вътрешни , тъй като те не са дадени отвън, а се определят пряко в резултат на решаването на проблема, поради което по-често се наричат оценки ресурси.

10. Взаимно дуални задачи на ЛП и техните свойства

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

И двете задачи имат следното Имоти:

1. В едната задача се търси максимумът на линейна функция, в другата – минимумът.

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

3. Всяка от задачите е дадена в стандартна форма, а в задачата за максимизиране всички неравенства от вида "<=", а в задаче минимизации – все неравенства вида ">=".

4. Матриците на коефициентите за променливите в системите за ограничения на двата проблема се транспонират една към друга.

5. Броят на неравенствата в системата от ограничения на една задача съвпада с броя на променливите в друга задача.

6. Условията за неотрицателност на променливите се запазват и в двете задачи.

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

Две задачи за линейно програмиране I и II, които имат посочените свойства, се наричат ​​симетрични двойствени задачи. По-нататък за простота ще ги наричаме просто двойни задачи.

Всеки проблем на LP може да бъде свързан с неговата двойна задача.

11. Алгоритъм за съставяне на двойна задача:

1. Намалете всички неравенства на системата от ограничения на първоначалния проблем до едно значение: ако в първоначалния проблем те търсят максимума на линейна функция, тогава намалете всички неравенства на системата от ограничения до формата "<=", а если минимум – к виду ">=". За тези неравенства, при които това изискване не е изпълнено, умножете по –1.

2. Съставете разширена матрица на система A, която включва матрица от коефициенти за променливи, колона от свободни членове на системата от ограничения и ред от коефициенти за променливи в линейна функция.

3. Намерете матрицата, транспонирана към матрица A .

4. Формулирайте двойна задача въз основа на получената матрица и условия за неотрицателност на променливите: те формират целевата функция на двойствения проблем, като вземат свободните членове на системата от ограничения на първоначалния проблем като коефициенти за променливите; съставете система от ограничения за двойствения проблем, като вземете матрични елементи като коефициенти за променливите и коефициенти за променливите в целевата функция на първоначалния проблем като свободни членове и запишете неравенства с противоположно значение; запишете условието за неотрицателност на променливите на двойствения проблем.

12. Първа теорема за двойственост

Връзката между оптималните решения на двойствени проблеми се установява с помощта на теореми за двойственост.

Достатъчен знак за оптималност.

Ако X*=(x1*,x2*,…,xn*) И Y*=(y1*,y2*,…,ym*) – допустими решения на взаимно двойствени задачи, за които е налице равенство,

тогава е оптималното решение на първоначалния проблем I и на двойствения проблем II.

В допълнение към достатъчния знак за оптималност на взаимно двойствени проблеми, има и други важни връзки между техните решения. На първо място възникват въпросите: винаги ли има едновременно оптимални решения за всяка двойка двойни проблеми; Възможно ли е един от двойните проблеми да има решение, а другият да няма? Отговор на тези въпроси дава следната теорема.

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

Fмакс = Zmin или F(X*)=Z(Y*) .

Ако линейната функция на едната задача не е ограничена, то условията на другата задача са противоречиви (задачата няма решение).

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

Икономически смисъл на първата теорема за двойствеността.

Производствен план X*=(x1*,x2*,…,xn*) и набор от цени (оценки) на ресурси Y*=(y1*,y2*,…,ym*) се оказват оптимални тогава и само тогава, когато печалбата (приходите) от продуктите, намерени при „външни“ (предварително известни) цени c1, c2,…, cn, е равна на разходите за ресурси при „вътрешни“ (определени само от решаването на задачата) цени y1 ,y2,…,ym. За всички други планове хИ YИ в двата проблема печалбата (приходите) от продукти винаги е по-малка от (или равна на) разходите за ресурси.

Икономическият смисъл на първата теорема за дуалност може да се тълкува по следния начин: предприятието е безразлично дали да произвежда продукти според оптималния план X*=(x1*,x2*,…,xn*) и да получава максимална печалба (приход) Fmax или продавайте ресурси на оптимални цени Y* =(y1*,y2*,…,ym*) и възстановява от продажбата минималната цена на ресурсите Zmin.

13. Втора теорема за двойственост

Нека са дадени две взаимно двойствени задачи. Ако всяка от тези задачи се решава с помощта на симплексния метод, тогава е необходимо да се приведат в канонична форма, за което трябва да се въведе в системата от ограничения на задача I (в кратка нотация) Tнеотрицателни променливи и в системата от ограничения на задача II () – н неотрицателни променливи, където i(j) е номерът на неравенството, в което е въведена допълнителната променлива.

Системите от ограничения за всяка от взаимно двойствените задачи ще приемат формата:

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

Теорема. Положителните (ненулеви) компоненти на оптималното решение на една от взаимно двойствените задачи съответстват на нулеви компоненти на оптималното решение на другата задача, т.е. за всяко i=1,2,…,m u j=1,2,…,n: ако X*j>0, тогава; Ако , тогава и по подобен начин,

ако, тогава ; ако, тогава.

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

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

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

14. Обективно определени оценки и тяхното значение

Компонентите на оптималното решение на двойствения проблем се наричат ​​оптимални (двойни) оценки на първоначалния проблем. Академик Л. В. Канторович ги нарече обективно определен"оценки (в литературата се наричат ​​още скрити доходи) .

Допълнителни променливи на първоначалната задача I, представляващи разликата между резервите bi на ресурси S1, S2, S3, S4 и консумацията им, експрес оставащи ресурси , и допълнителни променливи на двойна задача II, представляващи разликата между разходите за ресурси за производство на единица продукция от тях и цените cj на продуктите P1, P2 , експресен превишение на разходите над цената.

По този начин обективно определените оценки на ресурсите определят степента на недостиг на ресурси: според оптималния план за производство дефицитните (т.е. напълно използвани) ресурси получават ненулеви оценки, а неоскъдните ресурси получават нулеви оценки. Стойността y*i е оценка на i-тия ресурс. Колкото по-висока е стойността на оценката y*i, толкова по-голям е недостигът на ресурса. За неоскъден ресурс y*i=0.

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

Трета теорема за двойственост . Компонентите на оптималното решение на двойния проблем са равни на стойностите на частичните производни на линейната функция Fмакс(b1, b2,…, bm)по съответните аргументи, т.е.

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

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

Обективно определените оценки на ресурсите ни позволяват да преценим ефекта не от всякакви, а само от относително малки промени в ресурсите. При внезапни промени самите оценки могат да станат различни, което ще направи невъзможно използването им за анализ на ефективността на производството. Въз основа на съотношенията на обективно определени оценки могат да се определят изчислените норми на заменяемост на ресурсите, при които заместванията, извършени в рамките на стабилността на двойните оценки, не влияят на ефективността на оптималния план. Заключение.Двойните оценки са:

1. Индикатор за недостиг на ресурси и продукти.

2. Индикатор за влиянието на ограниченията върху стойността на целевата функция.

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

4. Инструмент за сравняване на общи условни разходи и резултати.

15. Постановка на транспортния проблем въз основа на разходния критерий.

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

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

Най-простата формулировка на техническите спецификации според критерия цена е следната: в Tв точките на тръгване A1,…,Am има съответно a1,…,am единици хомогенен товар (ресурси), които трябва да бъдат доставени нпотребители B1,…,Bn в количества b1,…,bn единици (нужди). Известни са транспортните разходи Cij за транспортиране на единица товар от i-тата точка на тръгване до j-тата точка на потребление.

Необходимо е да се изготви транспортен план, т.е. да се намери колко единици товар трябва да бъдат изпратени от i-тата точка на отпътуване до j-тата точка на потребление, така че да се задоволят напълно нуждите и така че общият транспорт разходите са минимални.

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

Тук количеството на товара, транспортиран от i-тата точка на тръгване до j-тото местоназначение, е равно на xij, запасът от товари в i-тата точка на тръгване се определя от стойността ai>=0, а необходимостта от товар на j-тата дестинация е bj>=0 . Приема се, че всички xij>=0.

Матрицата се нарича тарифна матрица (разходи или транспортни разходи).

План за транспортни задачи се нарича матрица, където всяко число xij обозначава броя на единиците товар, които трябва да бъдат доставени от i-тата точка на отпътуване до j-тото местоназначение. Матрицата xij се нарича транспортна матрица.

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

Променливите xij трябва да отговарят на ограниченията за запасите, потребителите и условията за неотрицателност:

– ограничения върху резервите (2);

– ограничения за потребителите (2);

– условия на неотрицателност (3).

По този начин, математически, транспортният проблем се формулира по следния начин. Дадени са системата от ограничения (2) при условие (3) и целевата функция (1). Сред набора от решения на система (2) се изисква да се намери неотрицателно решение, което минимизира функция (1).

Системата от ограничения на задача (1) – (3) съдържа m+n уравнения с Tнпроменливи. Приема се, че общите резерви са равни на общите потребности, т.е.

16. Признак за разрешимост на транспортната задача

За да има допустими планове една транспортна задача е необходимо и достатъчно да е изпълнено равенството

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

Отворен модел може да се преобразува в затворен. Така че, ако, тогава фиктивна (n+1)-та дестинация се въвежда в математическия модел на транспортния проблем. За целта в матрицата на задачата е предвидена допълнителна колона, за която търсенето е равно на разликата между общия капацитет на доставчиците и действителното търсене на потребителите:

Всички тарифи за доставка на товари до тази точка ще се считат за равни на нула. Това трансформира отворения модел на проблема в затворен. За нова задача целевата функция винаги е една и съща, тъй като цените за допълнителен транспорт са равни на нула. С други думи, фиктивният потребител не нарушава съвместимостта на системата от ограничения.

Ако, тогава се въвежда фиктивна (m+1)-та точка на тръгване, към която се приписва товарен запас, равен на.

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

За транспортната задача е важна следната теорема.

Теорема. Рангът на матрицата на транспортния проблем е с едно по-малко от броя на уравненията, т.е. r ( а )= м + н -1.

От теоремата следва, че всеки референтен дизайн трябва да има (m-1)(n-1) свободни променливи, равни на нула, и m+n-1 базисни променливи.

Ще търсим транспортния план на транспортната задача директно в таблицата за разпределение. Да приемем, че ако променливата xij приеме стойност, тогава ще запишем тази стойност в съответната клетка (I,j), но ако xij=0, тогава ще оставим клетката (I,j) свободна. Като се вземе предвид теоремата за ранга на матрицата в таблицата на разпределението опорният план трябва да съдържа m+n-1 заети клетки, а останалите ще са безплатни.

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

Набор от клетки на транспортна матрица, в който две и само две съседни клетки са разположени в един ред или в една колона и последната клетка от набора лежи в същия ред или колона като първата, се нарича затворена цикъл .

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

Следните важни свойства на плановете за транспортни проблеми са свързани с набор от циклични клетки:

1) допустим план за транспортна задача е референтен тогава и само тогава, когато не може да се образува цикъл от клетките, заети от този план;

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

17. Изграждане на първоначален опорен план

Правилото на "северозападния ъгъл".

За да съставите първоначалния план за транспортиране, е удобно да използвате правилото „северозападен ъгъл“, което е както следва.

Ще попълваме, започвайки от горния ляв ъгъл, условно наричан „северозападен ъгъл“, като се движим по-нататък по линията надясно или надолу по колоната. Нека поставим в клетка (1; 1) по-малкото от числата a1 и b1, т.е. Ако, тогава първата колона е „затворена“, т.е. търсенето на първия потребител е напълно удовлетворено. Това означава, че за всички останали клетки от първата колона количеството на товара за .

Ако, тогава първият ред е подобно „затворен“, т.е . Пристъпваме към попълване на съседната клетка (2; 1), в която влизаме.

След като попълните втората клетка (1; 2) или (2; 1), преминаваме към попълване на следващата трета клетка по втория ред или във втората колона. Ще продължим този процес, докато на даден етап ресурсите am и нуждите bn не бъдат изчерпани. Последната попълнена клетка ще бъде в последната n-та колона и в последния m-ти ред.

Правилото за "минимален елемент".

Първоначалният референтен план, изграден съгласно правилото "северозападен ъгъл", обикновено се оказва много далеч от оптималния, тъй като при определянето му не се вземат предвид стойностите на разходите cij. Следователно по-нататъшните изчисления ще изискват много итерации, за да се постигне оптимален план. Броят на итерациите може да бъде намален, ако първоначалният план е изграден съгласно правилото за „минимален елемент“. Същността му се състои в това, че на всяка стъпка се извършва максимално възможното „движение“ на товара в клетката с минимална тарифа cij. Започваме да попълваме таблицата от клетката, която съответства на най-малкия елемент cij от тарифната матрица. По-ниското от числата ai или bj се поставя в клетката с най-ниската тарифа . След това редът, съответстващ на доставчик, чийто инвентар е напълно изразходван, или колоната, съответстваща на клиент, чието търсене е напълно удовлетворено, се изключва от разглеждане. Може да е необходимо да се елиминират ред и колона едновременно, ако инвентарът на доставчика е напълно изразходван и търсенето на клиента е напълно удовлетворено. След това от останалите клетки на таблицата отново се избира клетката с най-ниска тарифа и процесът на разпределяне на запасите продължава до разпределяне на всички и задоволяване на търсенето.

18. Метод на потенциалите

Общият принцип за определяне на оптималния план за транспортен проблем с помощта на потенциалния метод е подобен на принципа за решаване на LP проблем с помощта на симплексния метод, а именно: първо се намира референтен план за транспортен проблем и след това последователно подобрява, докато се получи оптимален план.

Същността на потенциалния метод е следната. След като бъде намерен първоначалният референтен транспортен план, на всеки доставчик (всеки ред) се присвоява определено число, наречено потенциален доставчик Ai, и на всеки потребител (всяка колона) се присвоява определено число, наречено потребителски потенциал.

Цената на тон товар в точка е равна на цената на тон товар преди транспортирането + цената на транспортирането му: .

За да разрешите транспортен проблем с помощта на потенциалния метод, трябва:

1. Съставете основен транспортен план според едно от посочените правила. Броят на запълнените клетки трябва да бъде m+n-1.

2. Изчислете потенциалите и съответно доставчиците и потребителите (за заетите клетки): . Броят на попълнените клетки е m+n-1, а броят на уравненията е m+n. защото броят на уравненията е с едно по-малък от броя на неизвестните, тогава едно от неизвестните се оказва свободно и може да приеме произволна числена стойност. Например, . Останалите потенциали за даден референтен разтвор ще бъдат определени еднозначно.

3. Проверка за оптималност, т.е. за свободни клетки, изчислете оценки. Ако, тогава транспортирането е целесъобразно и план Х е оптимален - знак за оптималност. Ако има поне една разлика, преминете към нов референтен план. В своето икономическо значение стойността характеризира промяната в общите транспортни разходи, която ще възникне поради еднократна доставка от i-тия доставчик до j-тия потребител. Ако, тогава една доставка ще доведе до спестяване на транспортни разходи, но ако - до увеличаване на същите. Следователно, ако сред свободните направления за доставка няма направления, които спестяват транспортни разходи, тогава полученият план е оптимален.

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

а) На всяка от клетките, свързани с цикъл с дадена свободна клетка, се поставя определен знак, като тази свободна клетка е „+“, а на всички останали клетки (върхове на цикъла) се поставят последователно знаците „–“ и „ +”. Ще наричаме тези клетки минус и плюс.

б) В отрицателните клетки на цикъла намираме минималното предлагане, което означаваме с. По-малкото от числата xij, разположени в отрицателните клетки, се прехвърля в тази свободна клетка. В същото време това число се добавя към съответните числа в клетките със знака „+“ и се изважда от числата в клетките минус. Клетка, която преди е била свободна, става заета и влиза в поддържащата равнина; и клетката минус, която съдържа минимума от числата xij, се счита за свободна и напуска плана за поддръжка.

Така беше определен нов опорен план. Описаният по-горе преход от един референтен план към друг се нарича смяна в цикъла на преизчисляване. При изместване по цикъла на преизчисляване броят на заетите клетки остава непроменен, а именно остава равен на m+n-1. Освен това, ако има две или повече еднакви числа xij в отрицателните клетки, тогава само една от тези клетки се освобождава, а останалите остават заети с нулеви доставки.

5. Полученият референтен план се проверява за оптималност, т.е. повторете всички стъпки от стъпка 2.

19. Концепцията за динамично програмиране.

ДП (планиране) е математически метод за намиране на оптимални решения на многоетапни (многоетапни) проблеми. Някои от тези проблеми естествено се разделят на отделни стъпки (етапи), но има проблеми, при които разделянето трябва да бъде въведено изкуствено, за да бъдат решени по метода на DP.

Обикновено методите на DP оптимизират работата на някои контролирани системи, чийто ефект се оценява добавка, или мултипликативен, целевата функция. Добавкаизвиква се функция на няколко променливи f(x1,x2,…,xn), чиято стойност се изчислява като сбор от някои функции fj, които зависят само от една променлива xj: . Членовете на адитивната целева функция съответстват на ефекта от решенията, взети на отделни етапи от контролирания процес.

Принцип на оптималност на Р. Белман.

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

1. обектът на изследване трябва да бъде контролирана система (обект) с даден валиден държави и приемливо отдели;

2. задачата трябва да позволява тълкуване като многоетапен процес, всяка стъпка от който се състои от приемане решенияОизбор на един от допустимите контроли, водещи до промяна на състоянието системи;

3. задачата да не зависи от броя на стъпките и да се определя на всяка от тях;

4. състоянието на системата на всяка стъпка трябва да се описва с еднакъв (по състав) набор от параметри;

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

Нека разгледаме въпросите за прилагането на модела на динамично програмиране в обобщена форма. Нека задачата е да се контролира някакъв абстрактен обект, който може да бъде в различни състояния. Текущото състояние на обекта ще бъде идентифицирано с определен набор от параметри, които допълнително ще бъдат обозначени с S и наречени вектор на състоянието. Приема се, че е дадено множество S от всички възможни състояния. Има и набор, дефиниран за обекта допустими контроли(контролни действия) Х,което без загуба на общост може да се счита за числено множество. Контролните действия могат да се извършват в отделни моменти от времето и управлението решениесе състои в избор на един от контролите. Планирайтезадачи или стратегия за управлениесе нарича вектор x=(x1,x2,…,xn-1), чиито компоненти са контролите, избрани на всяка стъпка от процеса. С оглед на очакваното няма последействиемежду всеки две последователни състояния на обекта Sk и Sk+1 съществува известна функционална връзка, която включва и избраното управление: . По този начин се задава първоначалното състояние на обекта и се избира план хясно дефинирайте траектория на поведениеобект.

Контролирайте ефективността на всяка стъпка кзависи от текущото състояние Sk, избраното управление xk и се определя количествено с помощта на функциите fk(xk,Sk), които са термини адитивна целева функция , характеризиращи общата ефективност на фасилити мениджмънта. (Забележка , че дефиницията на функцията fk(xk,Sk) включва обхвата на допустимите стойности xk , и тази област, като правило, зависи от текущото състояние на Sk). Оптимален контрол , за дадено начално състояние S1, се свежда до избор на такъв оптимален план x* , при което се постига максимална сума стойности на fk на съответната траектория.

Основният принцип на динамичното програмиране е, че на всяка стъпка не трябва да се стремим към изолирана оптимизация на функцията fk(xk,Sk), а да избираме оптималното управление x*k при предположението, че всички следващи стъпки са оптимални. Формално този принцип се прилага чрез намиране на всяка стъпка к условни оптимални управления , осигурявайки най-голямата обща ефективност, като се започне от тази стъпка, като се приеме, че текущото състояние е S.

Нека Zk(s) означава максималната стойност на сумата от функции fk през всички стъпки от кпреди П(получава се при оптимално управление на даден сегмент от процеса), при условие че обектът в началото на стъпката ке в състояние S. Тогава функциите Zk(s) трябва да отговарят на рекурентната връзка:

Това съотношение се нарича основна рекурентна връзка (основно функционално уравнение)динамично програмиране. Той прилага основния принцип на динамичното програмиране, известен също като Принцип на оптималност на Белман :

Оптималната стратегия за управление трябва да отговаря на следното условие: каквото и да е първоначалното състояние ск на k-тата стъпка и управлението, избрано на тази стъпка xk, последващото управление (управленските решения) трябва да бъде оптимално по отношение на cocmo Яния ,в резултат на решението, взето на стъпка k .

Основната връзка ни позволява да намерим функциите Zk(s) само Vкомбинирано с начално състояние,което в нашия случай е равенството.

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

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

20. Концепцията за игрови модели.

Математическият модел на конфликтна ситуация се нарича игра , страни, участващи в конфликта - играчи, и изходът от конфликта е печеля.

За всяка формализирана игра, правила , тези. система от условия, която определя: 1) опции за действия на играчите; 2) количеството информация, която всеки играч има за поведението на своите партньори; 3) печалбата, до която води всеки набор от действия. Обикновено печалбата (или загубата) може да се определи количествено; например можете да оцените загуба като нула, победа като единица и равенство като 1/2. Количественото определяне на резултатите от игра се нарича плащане .

Играта се нарича парна баня , ако включва двама играчи, и многократни , ако броят на играчите е повече от двама. Ще разгледаме само игрите на двойки. Те включват двама играчи АИ IN,чиито интереси са противоположни, а под игра разбираме поредица от действия от страна на АИ IN.

Играта се нарича игра с нулева сума или антагонистичен небе , ако печалбата на един от играчите е равна на загубата на другия, т.е. сумата от печалбите на двете страни е нула. За да изпълните игровата задача, достатъчно е да посочите стойността на една от тях . Ако обозначим А– печалби на един от играчите, b – печалбите на другия, след това за игра с нулева сума b = –А, следователно е достатъчно да разгледаме напр А.

Извиква се изборът и изпълнението на едно от действията, предвидени в правилата прогрес играч. Движенията може да са лични И случаен . Личен ход – това е съзнателен избор от играча на едно от възможните действия (например ход в шах). Наборът от възможни опции за всеки личен ход се регулира от правилата на играта и зависи от съвкупността от предишни ходове от двете страни.

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

Някои игри могат да се състоят само от произволни ходове (т.нар. чист хазарт) или само от лични ходове (шах, дама). Повечето игри с карти принадлежат към игри от смесен тип, т.е. съдържат както произволни, така и лични ходове. В бъдеще ще разглеждаме само личните ходове на играчите.

Игрите се класифицират не само по естеството на ходовете (лични, произволни), но и по естеството и количеството информация, достъпна за всеки играч относно действията на другия. Специален клас игри са така наречените „игри с пълна информация“. Игра с пълна информация е игра, в която всеки играч, с всеки личен ход, знае резултатите от всички предишни ходове, както лични, така и произволни. Примери за игри с пълна информация включват шах, дама и добре познатата игра „тик-так-пръст“. Повечето игри с практическо значение не принадлежат към класа на игрите с пълна информация, тъй като несигурността относно действията на врага обикновено е съществен елемент от конфликтните ситуации.

Една от основните концепции на теорията на игрите е концепцията стратегии .

Стратегия Играчът е набор от правила, които определят избора на неговото действие при всеки личен ход, в зависимост от текущата ситуация. Обикновено по време на играта, при всеки личен ход, играчът прави избор в зависимост от конкретната ситуация. По принцип обаче е възможно всички решения да се вземат предварително от играча (в отговор на дадена ситуация). Това означава, че играчът е избрал конкретна стратегия, която може да бъде определена като списък с правила или програма. (По този начин можете да играете играта с помощта на компютър.) Играта се нарича крайна , ако всеки играч има краен брой стратегии и безкраен .– в противен случай.

За да реши игра , или намерете решение на играта , за всеки играч трябва да изберем стратегия, която отговаря на условието оптималност , тези. един от играчите трябва да получи максимална печалба, когато вторият се придържа към стратегията си, В същото време вторият играч трябва да има минимална загуба , ако първият се придържа към стратегията си. Такива стратегии се наричат оптимален . Оптималните стратегии също трябва да отговарят на условието устойчивост , тези. Трябва да е неизгодно за всеки играч да изостави стратегията си в тази игра.

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

Целта на теорията на игрите е да се определи оптималната стратегия за всеки играч.

21. Платежна матрица. Долна и горна цена на играта

Най-добрата игра, в която играчът АТо има Tстратегии и играчът V – стрстратегии се нарича m×n игра.

Да разгледаме игра m×n на двама играчи АИ IN(„ние” и „враг”).

Нека играчът Аима Tлични стратегии, които обозначаваме като A1,A2,…,Am. Нека играчът INна разположение нлични стратегии, нека ги обозначим B1,B2,…,Bn.

Нека всяка страна избере конкретна стратегия; за нас ще бъде Ai, за врага Bj. В резултат на избора на играчите на която и да е двойка стратегии Ai и Bj (), резултатът от играта е еднозначно определен, т.е. печалби на играча aij А(положителен или отрицателен) и загуба (-aij) на играча IN.

Да приемем, че стойностите на aij са известни за всяка двойка стратегии (Ai,Bj) . Матрица P=aij , чиито елементи са печалбите, съответстващи на стратегии Ai и Bj, Наречен платежна матрица или матрицата на играта. Редовете на тази матрица съответстват на стратегиите на играча а,и колоните – стратегиите на играча б. Тези стратегии се наричат ​​чисти.

Матрицата на играта m×n има формата:

Разгледайте m×n игра с матрица и определете най-добрата измежду стратегиите A1,A2,…,Am . Избор на стратегия за AI играч Атрябва да очаква, че играчът INще му отговори с една от стратегиите Bj, за които играчът печели Аминимален (плейър INсе стреми да "навреди" на играча А).

Нека означим с най-малката печалба на играча Акогато избира стратегия Ai за всички възможни стратегии на играч IN(най-малкото число в азред на платежната матрица), т.е.

Сред всички числа () избираме най-голямото: .

Да се ​​обадим най-ниската цена на играта, или максимални печалби (maxmin). Това е гарантирана победа за играч А за всяка стратегия на играч Б. следователно

Стратегията, съответстваща на максимин, се нарича максимин стратегия . Играч INзаинтересовани от намаляване на печалбите на играча а,когато избира стратегия Bj, той взема предвид максималната възможна печалба за А.Нека обозначим

Измежду всички числа изберете най-малкото

и да се обадим топ цена на играта или минимакс победа(минимакс). Егото гарантира загуба на играч B. Следователно,

Стратегията, съответстваща на minimax, се нарича минимакс стратегия.

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

Теорема. Долната цена на играта винаги не надвишава горната цена на играта .

Ако горната и долната цена на играта са еднакви, тогава общата стойност на горната и долната цена на играта се нарича чистата цена на играта, или на цената на играта. Съответстващите на цената на играта минимаксни стратегии са оптимални стратегии , и тяхната съвкупност - оптимално решение или решение на играта. В този случай играчът Аполучава максимално гарантирания (независимо от поведението на играча) IN)печалби v, и играчът INпостига гарантирания минимум (независимо от поведението на играча а)губещ v. Казват, че решението на играта има устойчивост , тези. Ако един играч се придържа към оптималната си стратегия, тогава не може да бъде изгодно за другия да се отклони от оптималната си стратегия.

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

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

Двойка чисти стратегии и дава оптимално решение на играта, ако и само ако съответният елемент е едновременно най-големият в своята колона и най-малкият в своя ред. Тази ситуация, ако съществува, се нарича захранваща точка. В геометрията се нарича точка от повърхност, която има свойството да има едновременно минимум в една координата и максимум в друга мощност точка, по аналогия този термин се използва в теорията на игрите.

Играта, за която , Наречен играейки с Power Point. Елемент, който има това свойство, е силовата точка на матрицата.

И така, за всяка игра с точка на мощност има решение, което определя двойка оптимални стратегии за двете страни, различаващи се по следните свойства.

1) Ако и двете страни се придържат към оптималните си стратегии, тогава средната печалба е равна на нетната цена на играта v, което е едновременно долната и горната му цена.

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

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

22. Решение на играта в смесени стратегии.

Сред ограничените игри с практическо значение игрите със сила са сравнително редки; по-типичен случай е, когато долната и горната цена на играта са различни. Анализирайки матриците на такива игри, стигаме до извода, че ако на всеки играч се даде избор на една стратегия, тогава, разчитайки на разумно действащ противник, този избор трябва да се определя от принципа на минимакса. Като се придържаме към нашата стратегия maximin, за всяко поведение на врага ние очевидно си гарантираме печалба, равна на по-ниската цена на играта α.Такива комбинирани стратегии, състоящи се от използването на няколко чисти стратегии, редуващи се според случаен закон с a определени честотни съотношения, се наричат ​​в теорията на игрите смесени стратегии

Смесена стратегия Sa играч A е прилагането на чисти стратегии A1,A1,…,Ai,…,Am с вероятности p1,p2,…pi,…pm, като сумата на вероятностите е равна на 1: . Смесените стратегии на играч А са написани като матрица

или като низ Sa=(p1,p2,…,pi,…,pm).

По подобен начин смесените стратегии на играч Б се означават с:

Или Sb=(q1,q2,…,qi,…,qn),

където сумата от вероятностите за поява на стратегии е равна на 1: .

Очевидно всяка чиста стратегия е частен случай на смесена, при която всички стратегии с изключение на една се прилагат с нулеви честоти (вероятности), а тази се използва с честота (вероятност) 1.

Оказва се, че чрез използването не само на чисти, но и на смесени стратегии е възможно всяка крайна игра да получи решение, т.е. двойка такива (в общия случай смесени) стратегии, така че когато и двамата играчи ги използват, печалбата ще бъде равна на цената на играта и когато Всяко едностранно отклонение от оптималната стратегия може само да промени печалбата в посока, неблагоприятна за девианта. И така, въз основа на принципа на минимакса, той се определя оптимално решение (или решение)игри: това са двойка оптимални стратегии в общия случай смесени, имащи следното свойство: ако един от играчите се придържа към оптималната си стратегия, то за другия не може да бъде изгодно да се отклони от своята. Нарича се печалбата, съответстваща на оптималното решение на цената на играта v . Цената на играта удовлетворява неравенството:

Където α и β са долната и горната цена на играта.

Посоченото твърдение съставлява съдържанието на т.нар фундаментална теорема на теорията на игрите.Тази теорема е доказана за първи път от Джон фон Нойман през 1928 г. Известните доказателства на теоремата са относително сложни; Затова ще дадем само неговата формулировка.

Всяка ограничена игра има поне едно оптимално решение, вероятно сред смесени стратегии.

От основната теорема следва, че всяка крайна игра има цена.

Нека бъде – двойка оптимални стратегии. Ако чиста стратегия е включена в оптимална смесена стратегия с ненулева вероятност, тогава тя се извиква активен (полезен) .

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

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

Тази теорема е от голямо практическо значение - предоставя конкретни модели за намиране на оптимални стратегии при липса на седлова точка.

Нека помислим Игра с размер 2x2, което е най-простият случай на ограничена игра. Ако такава игра има седлова точка, тогава оптималното решение е двойка чисти стратегии, съответстващи на тази точка.

Игра, в която няма седлова точка, в съответствие с основната теорема на теорията на игрите оптималното решение съществува и се определя от двойка смесени стратегииИ.

За да ги намерим, използваме теоремата за активните стратегии. Ако играчът Асе придържа към оптималната си стратегия , тогава средната му печалба ще бъде равна на цената на играта v, без значение каква активна стратегия използва играчът IN.За игра 2x2 всяка стратегия на чист противник е активна, ако няма средна точка. Печалбите на играча А(загуба на играч IN)– случайна променлива, чието математическо очакване (средна стойност) е цената на играта. Следователно печалбата на средния играч А(оптимална стратегия) ще бъде равно на vкакто за 1-ва, така и за 2-ра вражеска стратегия.

Нека играта е дадена от матрица на изплащане.

Средни печалби на играчи а,ако използва оптимална смесена стратегия и играчът В -чиста стратегия B1 (това съответства на 1-вата колона на матрицата на печалбите R),равна на цената на играта v: .

Играчът получава еднакви средни печалби А, ако 2-ри играч използва стратегия B2, т.е. . Имайки предвид това, получаваме система от уравнения за определяне на оптималната стратегия и цените на играта v:

Решавайки тази система, ние получаваме оптималната стратегия

и цената на играта.

Прилагане на теоремата за активните стратегии при търсене – оптимална стратегия на играча IN,откриваме това за всяка чиста стратегия за играч А (А1 или А2) средна загуба на играч INравна на цената на играта v, т.е.

Тогава оптималната стратегия се определя по формулите: .

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

Дубликат се наричат ​​стратегии, които съответстват на еднакви стойности на елементи в платежната матрица, т.е. матрицата съдържа еднакви редове (колони).

Ако всички елементи на i-тия ред на матрицата са по-малко от съответните елементи на k-тия ред, тогава i-тата стратегия за играча Анерентабилен (по-малка печалба).

Ако всички елементи на r-тата колона на матрицата са по-големи от съответните елементи на j-тата колона, тогава за играча IN R-тата стратегия е нерентабилна (загубата е по-голяма).

Процедурата за елиминиране на дублиращи се и очевидно нерентабилни стратегии трябва винаги да предхожда решението на играта.

23. Геометрична интерпретация на играта 2x2

Решение на играта 2x2позволява ясна геометрична интерпретация.

Нека играта е определена от платежната матрица P=(aij), i, j=1,2.

По абсцисната ос (фиг.) ще начертаем мерна единицасегмент A1A2; точка A1 ( х=0) изобразява стратегия A1, точка A2 ( х=1) изобразява стратегия A2 и всички междинни точки на този сегмент са смесени стратегии Sa на първия играч, а разстоянието от Sa до десния край на сегмента е вероятността p1 на стратегия A1 , разстояние до левия край – вероятност p2 на стратегия A2 .

Нека начертаем два перпендикуляра на абсцисната ос през точките A1 и A2: ос I-I и ос II-II. На оста I-I ще нанесем печалбите за стратегия A1; по ос II-II – печалби за стратегия A2.

Ако играч A използва стратегия A1, тогава неговата печалба със стратегия B1 на играч B е a11, а със стратегия B2 е равна на a12. Числата a11 и a12 на ос I съответстват на точки B1 и B2.

Ако играч A използва стратегия A2, тогава неговата печалба със стратегия B1 на играч B е a21, а със стратегия B2 е равна на a22. Числата a21 и a22 съответстват на точки B1 и B2 на ос II.

Свързваме точки B1 (I) и B1 (II); B2 (I) и B2 (II). Имаме две прави линии. Директен B1B1– ако играчът Априлага смесена стратегия (всяка комбинация от стратегии A1 и A2 с вероятности p1 и p2), а играч B използва стратегия B1. Играчът печели Асъответства на някаква точка, лежаща на тази права. Средната печалба, съответстваща на смесената стратегия, се определя по формулата a11p1+a21p2 и е представена от точка M1 на права B1B1.

По същия начин конструираме сегмента B2B2, съответстващ на използването на стратегия B2 от втория играч. В този случай средната печалба се определя по формулата a12p1+a22p2 и се представя от точка M2 на директен B2B2.

Трябва да намерим оптималната стратегия S*a, т.е. тази, за която минималната печалба (за всяко поведение IN)би се обърнал на максимум. За това ще изградим долна граница на печалбата за B1B2 стратегии , т.е. прекъснатата линия B1NB2, отбелязана на фиг. удебелена линия. Това долната граница ще изрази минималната печалба на играча Ас която и да е от неговите смесени стратегии; точкан , в който тази минимална печалба достига максимум и определя решението (оптималната стратегия) и цената на играта. Ординатна точка нима цена за играта v. Координати на точки ннамираме като координати на пресечните точки на прави B1B1 и B2B2. В нашия случай решението на играта се определяше от пресечната точка на стратегиите. Това обаче не винаги ще е така.

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

Ако платежната матрица съдържа отрицателни числа, тогава за графично решаване на проблема е по-добре да преминете към нова матрица с неотрицателни елементи; За да направите това, достатъчно е да добавите съответното положително число към елементите на оригиналната матрица. Решението на играта няма да се промени, но цената на играта ще се увеличи с това число. Графичният метод може да се използва за решаване на играта 2×n, m×2.

24. Свеждане на матрична игра до задача на линейно програмиране

В общия случай играта m×n няма ясна геометрична интерпретация. Решението му е доста трудоемко за големи TИ н, той обаче няма фундаментални трудности, тъй като може да се сведе до решаване на проблем с линейно програмиране. Нека го покажем.

Нека играта m×n е дадена от матрицата на изплащане . Играч Аима стратегии A1,A2,..Ai,..Am , играч В -стратегии б 1,б 2,..баз,.. бн. Необходимо е да се определят оптималните стратегии и къде са вероятностите за използване на съответните чисти стратегии Ai,Bj,

Оптималната стратегия отговаря на следното изискване. Той осигурява на играча Асредни печалби, не по-малко от цената на играта v, за всяка стратегия на играча INи печалби, равни на цената на играта v, с оптималната стратегия на играча IN.Без загуба на общоприетост приемаме v> 0; това може да се постигне чрез направата на всички елементи . Ако играчът Априлага смесена стратегия срещу всяка чиста стратегия на Bj играч IN,тогава той получава средни печалби , или математическо очакване за победа (т.е. елементи й-Gоколоните на платежната матрица се умножават термин по термин по съответните вероятности на стратегии A1, A2,..Ai,..Am и резултатите се добавят).

За оптимална стратегия всички средни печалби не са по-малки от цената на играта v, следователно получаваме система от неравенства:

Всяко от неравенствата може да се раздели на число. Нека въведем нови променливи: . След това системата приема формата

Гол на играча А -увеличете максимално гарантираните си печалби, т.е. цена на играта v.

Разделяйки по равенство, намираме, че променливите отговарят на условието: . Максимизиране на цената на играта vе еквивалентно на минимизиране на количеството , Следователно проблемът може да се формулира по следния начин: определяне на стойностите на променливите , матака че да удовлетворяват линейните ограничения(*) И докато линейната функция (2*) прилагани до минимум.

Това е проблем с линейно програмиране. Решавайки задача (1*)–(2*), получаваме оптималното решение и оптимална стратегия .

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

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

Ако означим (4*), получаваме система от неравенства:

Променливите отговарят на условието.

Играта се сведе до следващия проблем.

Определяне на променливи стойности , които удовлетворяват системата от неравенства (5*)И максимизиране на линейната функция

Решението на проблема с линейното програмиране (5*), (6*) определя оптималната стратегия. В същото време цената на играта. (7*)

След като сме съставили разширени матрици за проблеми (1*), (2*) и (5*), (6*), ние се уверяваме, че една матрица е получена от друга чрез транспониране:

По този начин проблемите на линейното програмиране (1*), (2*) и (5*), (6*) са взаимно двойствени. Очевидно, когато се определят оптималните стратегии в конкретни проблеми, трябва да се избере един от взаимно двойствените проблеми, чието решение е по-малко трудоемко, и да се намери решение на другия проблем, като се използват теореми за двойственост.

При решаване на произволна крайна игра с размер m×n се препоръчва да се придържате към следната схема:

1. Изключете от платежната матрица стратегии, които са очевидно нерентабилни в сравнение с други стратегии. Такива стратегии за играча А