Поглавје 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 од претходниот став се „операции“).

Операцијата е секогаш контролиран настан, односно од нас зависи како да избереме некои од параметрите што ја карактеризираат нејзината организација. „Организација“ овде се подразбира во широка смисла на зборот, вклучувајќи го и збирот технички средства што се користат во операцијата.

Секој дефинитивен избор на параметри во зависност од нас се нарекува решение. Одлуките можат да бидат успешни и неуспешни, разумни и неразумни. Решенијата се нарекуваат оптимални ако се претпочитаат пред другите поради една или друга причина. Целта на оперативното истражување е прелиминарно квантитативно оправдување на оптималните решенија.

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

Имајте на ум дека самото одлучување оди надвор од опсегот на проучувањето на операцијата и спаѓа во надлежност на одговорното лице, почесто - група на лица на кои им е дадено правото да го направат конечниот избор и кои се одговорни за овој избор. При изборот, тие можат да земат предвид, заедно со препораките кои произлегуваат од математичката пресметка, и голем број размислувања (квантитативна и квалитативна природа) кои не биле земени предвид со оваа пресметка.

Незаменливото присуство на лице (како орган за донесување конечни одлуки) не се откажува дури и во присуство на целосно автоматизиран контролен систем, кој, се чини, донесува одлука без човечко учество. Не смееме да заборавиме дека самото создавање на контролен алгоритам, изборот на една од неговите можни опции, е исто така одлука, и тоа многу одговорна. Со развојот на контролните автомати, човечките функции не се откажуваат, туку едноставно се преместуваат од едно, основно, ниво на друго, повисоко. Покрај тоа, голем број на автоматизирани системи за контрола обезбедуваат активна човечка интервенција за време на контролираниот процес.

Тие параметри, чиј тотал формира решение, се нарекуваат елементи на решението. Како елементи на решението може да се појават различни броеви, вектори, функции, физички знаци итн.. На пример, ако се изготви план за транспорт на хомогени стоки од појдовните точки А 1, А 2, ..., А мдо дестинации ВО 1,В 2 , ..., В n ,тогаш елементи на решението ќе бидат броевите x ij , покажувајќи колку товар ќе биде испратен од 1-та појдовна точка А иВ ј-та дестинација Во ј.Збир на броеви x 11 , x 12, …, x 1 n,…, x m 1, x m 2,…, xmnформира решение.

Во наједноставните проблеми на оперативното истражување, бројот на елементи за решение може да биде релативно мал. Но, во повеќето проблеми од практично значење, бројот на елементи за решение е многу голем, што читателот може да го потврди со обид самостојно да ги избере и „име по име“ елементите на решението во примерите 1 - 8 од претходниот пасус. За едноставност, ќе го означиме целиот сет на елементи на решението со една буква xи кажете „одлука X“.

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

тежински карактеристики на опремата итн.). Конкретно, таквите услови ги вклучуваат средствата (материјални, технички, човечки) со кои имаме право да располагаме и други ограничувања наметнати на решението. Во својот тотал, тие го формираат таканаречениот „сет на можни решенија“.

Ајде повторно да го означиме ова множество со една буква x,но фактот дека решението Xприпаѓа на ова множество, ќе го напишеме како формула: X X(читај: елемент Xвклучени во комплетот x).

Станува збор за тоа дека во мноштвото можни решенија Xистакнете ги тие решенија X(понекогаш - едно, а почесто - цела низа решенија), кои од една или друга гледна точка се поефикасни (поуспешни, попожелни) од другите. За да споредите различни решенија во однос на ефикасноста, треба да имате некој вид квантитативен критериум, таканаречен индикатор за ефикасност (често се нарекува „објективна функција“). Овој индикатор е избран така што ја одразува целната ориентација на операцијата. За „најдобро“ решение ќе се смета она што допринесува за постигнување на целта во максимална мера. За да изберете мерка за изведба „кажи по име“. Ш,Пред сè, треба да се запрашате: што сакамеКон што се стремиме со преземањето на операцијата? При изборот на решение, природно ќе претпочитаме такво што го превртува индикаторот за ефикасност Вмаксимум (или минимум). На пример, би сакал да го максимизирам приходот од операција; ако трошоците се показател за ефикасност, пожелно е да се минимизираат. Ако е пожелно да се максимизира индикаторот за ефикасност, ќе го напишеме во форма W =>макс, и ако е минимизиран - W =>мин.

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

Во некои случаи, се случува операцијата, придружена со случајни фактори, да следи некоја многу специфична цел. А,што може да се постигне само целосно или воопшто да не се постигне (шема „да-не“), а ние не сме заинтересирани за никакви средни резултати. Потоа, како показател за ефикасност, се избира веројатноста за постигнување на оваа цел. Р(А). На пример, ако некој предмет се пука со неопходен услов да се уништи, тогаш индикаторот за ефикасност ќе биде веројатноста за уништување на објектот.

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

За да ги илустрираме принципите на избор на индикатор за ефикасност, да се вратиме повторно на примерите 1 - 8 од § 1, да избереме за секој од нив природен показател за ефикасност и да покажеме дали е потребно да се максимизира или минимизира. При испитувањето на примерите, треба да се има предвид дека не сите имаат избор на индикатор за ефикасност недвосмислено диктиран од вербалниот опис на задачата, така што може да има разлики меѓу читателот и авторот по ова прашање.

1. План за снабдување на претпријатијата.Задачата на операцијата е да обезбеди снабдување со суровини со минимални транспортни трошоци. Индикатор за изведба Р- вкупните трошоци за транспорт на суровини по единица време, на пример, еден месец ( R =>мин).

2. Изградба на дел од автопатот.Потребно е изградбата да се испланира на таков начин што ќе се заврши што е можно поскоро. Природен показател за ефикасност би бил времето за завршување на изградбата, доколку тоа не е поврзано со случајни фактори (неуспеси на опремата, доцнење во извршувањето на поединечни работи). Затоа, како показател за ефикасност, можете да го изберете просечното очекувано време Тзавршување на изградбата (Т =>мин).

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

4. Заштита на патишта од снег.Ова е економски најповолниот план за заштита од снег, затоа, како показател за ефикасност, можете да ги изберете просечните трошоци по единица време (на пример, годишно) Рза одржување и функционирање на патиштата, вклучувајќи ги и трошоците поврзани и со изградбата на заштитни уреди и со расчистување на патиштата и доцнење во сообраќајот (Р =>мин).

5. Рација против подморница.Бидејќи рацијата има многу специфична цел А -уништувањето на бродот, тогаш како показател за ефикасност, треба да ја изберете веројатноста Р(А) дека чамецот ќе биде уништен.

6. Селективна контрола на производите.Мерката за природни перформанси предложена од изјавата за проблемот е просечниот очекуван трошок. Рза контрола по единица време, под услов контролниот систем да обезбедува дадено ниво на квалитет, на пример, просечниот процент на одбиени не е поголем од наведеното ( Р=> мин).

7. Медицински преглед.Како показател за ефикасност, можете да изберете просечен процент (удел) Ппациенти и носители на инфекција кои беа идентификувани (П=>проверка).

8. Библиотечна услуга.Во формулацијата на проблемот намерно беше признаена одредена нејасност:

не е јасно што се подразбира под „најдобра услуга за клиенти“ или „задоволување на нивните потреби во најголема можна мера“. Ако квалитетот на услугата се процени според времето кога претплатникот кој ја побарал книгата чека да ја добие, тогаш просечното време може да се земе како показател за ефикасност. Точекувањата на книгата од страна на читателот кој аплицирал за неа ( Т=> мин). Можете да му пристапите на прашањето од малку поинаква перспектива, избирајќи го просечниот број како показател за ефикасност. Мкниги издадени по единица време (М =>макс).

Разгледаните примери се специјално избрани да бидат толку едноставни што изборот на индикатор за ефикасност е релативно лесен и е директно диктиран од вербалната формулација на задачата, нејзината (речиси секогаш) недвосмислена целна ориентација. Меѓутоа, во пракса тоа не е секогаш случај. Во тоа може да се увери читателот со обид, на пример, да избере показател за ефикасноста на градскиот транспорт. Што треба да се земе како таков индикатор? Просечната брзина на движење на патниците во градот? Или просечниот број на превезени патници? Или просечниот број на километри што ќе треба да ги помине човек, кој транспортот не може да го испорача на вистинското место? Има за што да се размислува овде!

За жал, во повеќето проблеми од практично значење, изборот на индикатор за ефикасност не е едноставен и се решава двосмислено. За секоја сложена задача, типична е ситуација кога ефективноста на операцијата не може исцрпно да се карактеризира со еден број - треба да вклучи други за да и помогнат. Ќе се запознаеме со ваквите „мултикритериумски“ проблеми во § 6.

Примери за решавање на динамички програмски проблеми

Во овој дел, ќе разгледаме (па дури и ќе решиме до крај) неколку едноставни (екстремно поедноставени) примери на динамични програмски проблеми

1. Поставување на најповолната рута помеѓу две точки.Да се ​​потсетиме на проблемот 4 од претходниот став и да го решиме до крај под крајно (и намерно) поедноставени услови. Треба да изградиме патека за поврзување

две точки АИ ВО,од кои вториот лежи североисточно од првиот. За едноставност, да речеме. дека поставувањето на патеката се состои од низа чекори, и на секој чекор можеме да се движиме или на исток или на север; на кој било начин од АВ ВОе скалеста скршена линија, чии отсечки се паралелни со една од координатните оски (сл. 13.1). Трошоците за изградба на секој од овие сегменти се познати. Потребно е да се постави таква патека од АВ ВО,каде што вкупните трошоци се минимални.

Како да се направи тоа? Можете да направите еден од двата начини: или да поминете низ сите можни опции за патека и да ја изберете онаа на која трошоците се минимални (а со голем број сегменти ова е многу, многу тешко!); или поделете го процесот на транзиција од АВ ВОво поединечни чекори (еден чекор - еден сегмент) и оптимизирајте ја контролата по чекори. Излегува дека вториот метод е неспоредливо поудобен! Еве,како и на друго место во оперативното истражување, има предности од намерното, организирано барање решение во однос на наивното „слепо“ набројување.

Ајде да покажеме како се прави ова со конкретен пример. Поделете го растојанието од Апред ВОво источна насока, да речеме, на 7 дела, а во северна насока - на 5 дела (во принцип, фрагментацијата може да биде произволно мала). Потоа било кој пат од АВ ВОопфаќа Т\u003d 7 + 5 \u003d= 12 сегменти насочени кон исток или север (сл. 13.2). Ајде да ставиме на секој од сегментите број што го изразува (во некои произволни единици) трошоците за поставување патека по овој сегмент. Потребно е да се избере таков пат од АВ ВО,за кои збирот на броевите на отсечките е минимален.

Конструираната патека ќе ја разгледаме како контролиран систем С,движејќи се под влијание на контрола од почетната состојба Адо финалето ВО.Состојбата на овој систем пред почетокот на секој чекор ќе се карактеризира со две координати: исток (X)и северна (y),и двата се цел број (0 X 5 7, 0 на 5). За секоја од состојбите на системот (нодална точка на правоаголната мрежа на Сл. 13.2), мора да ја најдеме условната оптимална контрола: одиме од оваа точка на север (контрола „c“) или на исток (контрола „ в"). Оваа контрола е избрана така што цената на сите преостанати чекори (вклучувајќи го и овој) е минимална. Овој трошок ќе продолжиме да го нарекуваме „условна оптимална добивка“ (иако во овој случај тоа не е „добивка“, туку „загуба“) за дадена состојба на системот. Спред да започнете со следниот чекор.

Постапката за условна оптимизација ќе ја расплетуваме во спротивна насока - од крај до почеток. Прво, вршиме условна оптимизација на последниот, 12-ти чекор. Размислете за одделно горниот десен агол на нашата правоаголна решетка (сл. 13.3). Каде можеме да бидеме по 11-тиот чекор? Само

каде што во еден (последниот) чекор можете да стигнете ВО,т.е. во една од точките ВО 1или НА 2.Ако сме во точката ВО 1,немаме избор (присилна контрола): мора да одиме на исток, а тоа ќе не чини 10 единици. Да го запишеме овој број 10 во круг во близина на точката ВО 1,а оптималната контрола ќе биде прикажана со кратка стрелка што произлегува од ВО 1и насочен кон исток. За точка НА 2контролата е исто така принудена (север), протокот до крај е 14, ќе го запишеме во круг во точката НА 2.Така се врши условната оптимизација на последниот чекор и условната оптимална добивка за секоја од точките Б1, Б2пронајден и евидентиран во соодветната кригла.

Сега да го оптимизираме претпоследниот (11-ти) чекор. По претпоследниот (10-ти) чекор можевме да завршиме на некој од бодовите C 1, C 2, C 3(Сл. 13.4). Дозволете ни да најдеме за секоја од нив условна оптимална контрола и условна оптимална исплата. За точка Од 1принудно управување: оди на исток;

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

Слично, „повлекувајќи се“ од претпоследниот чекор назад, за секоја точка со целобројни координати ја наоѓаме условната оптимална контрола („c“ или „b“), која ја означуваме со стрелка и условната оптимална добивка (трошок за крај на патеката), што го пишуваме во круг. Се пресметува на следниов начин: брзината на проток на даден чекор се додава на веќе оптимизираната брзина на проток, запишана во кругот каде што води стрелката. Така, на секој чекор го оптимизираме само овој чекор, а оние што го следат се веќе оптимизирани. Крајниот резултат од постапката за оптимизација е прикажан на сл. 13.5.

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

Ш* = 118.

Сега останува да се изгради безусловна оптимална контрола - траекторија што води од АИ ВОна најевтин начин. За да го направите ова, треба само да ги „послушате стрелците“, односно да прочитате што тие пропишуваат да прават на секој чекор. Таквата оптимална траекторија е означена на сл. 13,5 заокружи двапати. Соодветната безусловна оптимална контрола ќе биде:

x* =(s, s, s, s, во, во, s, во, во, во, во, во),

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

Забележете дека во текот на условната оптимизација, може да се сретнеме со случај кога двете контроли за одредена точка на рамнината се оптимални, т.е., водат до истиот трошок на средства од оваа точка до крајот. На пример, во точката со координати (5; 1) двете контроли „c“ и „b“ се оптимални и го даваат протокот до крај еднаков на 62. Ние произволно избираме која било од нив (во нашиот случај, избравме „c“; исто така можевме да имаме избрано „в“). Вакви случаи на двосмислен избор на оптимална контрола постојано се среќаваат во динамичкото програмирање; во иднина нема посебно да ги означуваме, туку едноставно произволно избираме која било од еквивалентните опции. Се разбира, оптималната контрола на целиот процес може да зависи од ова самоволие, но не и оптималната добивка. Општо земено, во динамичните програмски проблеми (како и во проблемите со линеарно програмирање), решението е далеку од секогаш единствено.

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

x = (s,с, во, во, во, во, с, во, во, во, с, с).

Ајде да ги пресметаме трошоците за оваа траекторија. Тие ќе бидат еднакви В=10 +12 +8+10 +11 +13 +15+8 + +10+9+8+14=128, што е дефинитивно повеќе од Ш* = 118. Во овој случај разликата не е многу голема, но во други може да биде значајна.

Во проблемот решен погоре, условите беа намерно поедноставени до крајност. Се разбира, никој нема да ја води железничката пруга „по скалите“, движејќи се само поради север или поради исток. Направивме такво поедноставување за да избереме само од две контроли во секоја точка: „од“ или „до“. Наместо две можни насоки, би можело да се воведат неколку од нив и дополнително да се преземат помали чекори; ова не е од фундаментално значење, но, се разбира, ги комплицира и ги продолжува пресметките.

Забележете дека задачите слични на оние разгледани погоре многу често се среќаваат во пракса: на пример, при изборот на најбрзата патека помеѓу две точки или најекономичното (во однос на потрошувачката на гориво) зголемување на брзината и висината на авионот.

Да направиме една минлива забелешка. Внимателниот читател веројатно забележал дека во нашиот проблем точките АИ ВО(почеток и крај) во принцип не се разликуваат едни од други: би било можно да се изградат условни оптимални контроли не од крај до почеток, туку од почеток до крај, и безусловно - во спротивна насока. Навистина, тоа е така: во секој проблем со динамично програмирање, „почетокот“ и „крајот“ може да се заменат. Ова е целосно еквивалентно на претходно опишаниот метод во однос на пресметката, но е нешто помалку погодно кога вербално се објаснува идејата за методот: полесно е да се расправа, повикувајќи се на „веќе воспоставените“ услови на почетокот на оваа чекор отколку на оние кои сè уште „доаѓаат“ по овој чекор. Во суштина, двата пристапи се целосно еквивалентни.

2. Проблемот со распределбата на ресурсите.Динамичниот метод на програмирање овозможува успешно решавање на многу економски проблеми (види, на пример, ). Размислете за еден од наједноставните вакви проблеми. Располагаме со одредена залиха на средства (ресурси). ДО,кои треба да бидат распределени меѓу Тпретпријатија P 1 , P 2 , ..., P m . Секое од претпријатијата јаскога се инвестира во него Xгенерира приход врз основа на xт.е. претставува некоја функција ( x). Сите функции ( x) (јас = 1, 2, ..., Т)се дадени (се разбира, овие функции не се намалуваат). Прашањето е како да се распределат средствата ДО.помеѓу претпријатијата, така што вкупно тие даваат максимален приход?

Овој проблем лесно се решава со методот на динамичко програмирање.Иако во неговата формулација не содржи споменување на времето, сепак можете ментално да ја разоткриете операцијата на распределба на средства во одреден редослед, земајќи го предвид инвестирањето на средства во претпријатието P 1 како првиот чекор, а во P 2 итн.

Управуван систем Сво овој случај, средствата или ресурсите што се распределуваат. Состојба на системот Спред секој чекор се карактеризира со еден број С-сè уште не инвестирана готовинска резерва. Во овој проблем, "чекор контроли" се средства x 1, x 2, ..., x 3,доделени на бизниси. Потребно е да се најде оптималната контрола, т.е. таков збир на броеви x 1, x 2, ..., xm,при што вкупниот приход е максимален:

(13.1)

Овој проблем ќе го решиме прво во општа, формулаична форма, а потоа - за конкретни нумерички податоци. Најдете за секого јас-ти чекор е условна оптимална исплата (од овој чекор до крај), доколку на овој чекор му пристапиме со маргина на средства С.Означете ја условната оптимална исплата W i (S),а соодветна условна оптимална контрола се вложените средства јаспретпријатие, - x i (S).

Ајде да започнеме со оптимизација од последното, Т -чекор. Да дојдеме до овој чекор со останатите средства С.Што треба да правиме? Очигледно инвестирајте ја целата сума Сцелосно на претпријатието П м. Затоа, условната оптимална контрола на м-ти чекор: дајте му ги на последното претпријатие сите расположливи средства С,т.е.

и условната оптимална исплата

W m (S)= (S).

Со оглед на цела низа вредности С(поставувајќи ги доволно блиску), ние за секоја вредност Сќе знаеме x m (S)И W m (S).Последниот чекор е оптимизиран.

Да преминеме на претпоследното (Т- 1) чекор. Да му пристапиме со резерва на средства С.Означи Ш м -1 (С)условна оптимална исплата на последните два чекори: ( m- 1)-м и м-m (што е веќе оптимизирано). Ако одвоиме на ( m- 1) чекор ( m- 1) средства на претпријатието X,тогаш ќе биде последниот чекор S-x.Нашата исплата на последните два чекори ќе биде еднаква на

,

и треба да се најде X,при што оваа добивка е максимална:

Знакот значи дека максималната вредност е преземена над сите X,што е можно (да се инвестира повеќе од С,не можеме) од изразот во кадрави загради. Овој максимум е условна оптимална исплата за последните два чекори, а потоа и вредноста X,при што се постигнува овој максимум, е условената оптимална контрола на (Т- 1) чекор.

и соодветната условна оптимална контрола x i (S) -таа вредност X,при што се постигнува овој максимум.

Продолжувајќи на овој начин, конечно стигнуваме до првото претпријатие P 1 . Тука не треба да ги менуваме вредностите S;со сигурност знаеме дека залихата пред првиот чекор е еднаква на ДО:

Значи, се наоѓа максималната добивка (приход) од сите претпријатија. Сега останува само „да ги прочитаме препораките“. Тоа значење X,при што се постигнува максимумот (13,4), а оптимална контрола има на 1-виот чекор. Откако ќе ги инвестираме овие средства во 1. претпријатие, ќе имаме ДО- .„Читање“ на препораката за оваа вредност С,го доделуваме оптималниот износ на средства на второто претпријатие:

,

и така до крај.

Сега да решиме нумерички пример. Почетна состојба на средства К = 10 (конвенционални единици), и се бара оптимално да се дистрибуира меѓу пет претпријатија (t = 5). За едноставност, ќе претпоставиме дека се инвестираат само цели износи на средства. функции на приход ( X) се дадени во Табела 13.1.

Табела 13.1

X
	0,5 1,0 1,4 2,0 2,5 2,8 3,0 3,0	0,1 0,5 1,2 1,8 2,5 2,9 3,5 3,5	0,6 1,1 1,2 1,4 1,6 1,7 1,8 1,8	0,3 0,6 1,3 1,4 1,5 1,5 1,5 1,5	1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3

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

Ајде да извршиме условна оптимизација како што е опишано погоре, почнувајќи од последниот, 5-ти чекор. Секој пат кога доаѓаме до следниот чекор, имајќи резерва на средства С,се обидуваме да одвоиме еден или друг износ на средства за овој чекор, да ја преземеме добивката на овој чекор според табела 13.1, да ја додадеме на веќе оптимизираната добивка на сите наредни чекори до крајот (со оглед дека веќе ни остануваат помалку средства, само за толкав износ на средства што ги доделивме) и да ја пронајдеме инвестицијата на која оваа сума го достигнува својот максимум. Оваа инвестиција е условна оптимална контрола на овој чекор, а максимумот е условно оптимално засилување.

Табелата 13.2 ги прикажува резултатите од условната оптимизација за сите чекори. Табелата е структурирана на следниов начин: првата колона ги дава вредностите на залихата на средства С, сосо кој пристапуваме кон овој чекор. Понатаму, табелата е поделена на пет пара колони, што одговараат на бројот на чекорот. Првата колона од секој пар ја содржи вредноста

Табела 13.2

С	i=5	i=4	i=3	i=2	i=1
x5(С)	Ш 5(С)	x4(С)	С4(С)	x 3(С)	Ш 3(С)	x2(С)	W2(С)	x 1(С)	Ш 1(С)
		1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3 1,3 1,3		1,0 1,3 1,6 2,3 2,5 2,6 2,7 2,8 2,8 2,8		1,0 1,6 2,1 2,4 2,9 3,4 3,6 3,7 3,9 4,1		1,0 1,6 2,1 2,4 2,9 3,5 4,1 4,6 5,1 5,6		5,6

условна оптимална контрола, во втората - условна оптимална исплата. Табелата се пополнува од лево кон десно, од горе до долу. Одлуката на петтиот - последен чекор е принудна: сите средства се распределени;

Во сите други чекори, решението треба да се оптимизира. Како резултат на последователна оптимизација на 5-тиот, 4-тиот, 3-тиот, 2-ри и 1-ви чекори, ќе добиеме комплетна листа на сите препораки за оптимална контрола и безусловна оптимална добивка Ш*за целата операција - во овој случај, тоа е еднакво на 5,6. Во последните две колони од Табела 13.2 се пополнува само една линија, бидејќи точно ја знаеме состојбата на системот пред почетокот на првиот чекор:

S0 = К = 10. Оптималните контроли на сите чекори се врамени. Така, го добивме конечниот заклучок: треба да доделиме две единици од десет на првото претпријатие, пет единици на второто, две на третото, ниту една на четвртото, една единица на петтото. Со оваа распределба приходот ќе биде максимален и еднаков на 5,6.

За да му биде јасно на читателот како се пополнува табелата 13.2, ова ќе го покажеме на еден примерок за пресметка. Нека, на пример, треба да го оптимизираме решението x 3(7)- што да правиме во третиот чекор, ако му пристапиме со резерва на средства S= 7, а кој е максимумот што можеме да го освоиме на сите преостанати

Табела 13.3

x	7 - x		С4(7 - x)	+В 4 (7 - x)
		1,8 1,7 1,6 1,4 1,2 1,1 0,6	1,0 1,3 1,6 2,3 2,5 2,6 2,7	1,8 2,7 2,9 3,0 3,5 3,2 2,7

чекори, вклучувајќи го и третиот? Да претпоставиме дека сите чекори по третиот (4-ти и 5-ти) се веќе оптимизирани, односно првите два пара колони од Табела 13.2 се пополнети. Ајде да најдеме x 3 (7) и Ш 3(7). За да го направите ова, ќе составиме помошна плоча (види табела 13.3). Првата колона ги наведува сите можни прилози. Xна третиот чекор, не надминувајќи S = 7.Во втората колона - што ќе остане по ваквата инвестиција од залиха на средства S = 7.Во третата колона - добивката во третиот чекор од инвестирањето Xво третото претпријатие се пополнува по колона (табела 13.1). Во четвртата колона - оптимална исплата на сите преостанати чекори (четврта и петта), под услов да се приближиме до четвртиот чекор со преостанатите средства (пополнета во колоната јас = 4 табели 13.2). Во петтата колона - збир на две исплати: чекор и оптимизиран понатаму за дадена инвестиција Xво третиот чекор.

Од сите исплати од последната колона, се избира максималната (во табелата 13.3 е еднаква на Ш 3(7) = 3,6, и соодветната контрола X(7) = 2).

Се поставува прашањето: што ако во помошната табела од типот 13.3 се достигне максимумот за повеќе од еден x, и на две или повеќе? Ние одговараме: не е важно кој да избереме; добивката не зависи од тоа. Општо земено, кај динамичните програмски проблеми, решението воопшто не треба да биде единствено (веќе го спомнавме ова).

3. Проблемот со вчитување на машината.Користејќи го методот на динамичко програмирање, можете успешно да решите голем број проблеми за оптимизација опишани во Поглавје 3, особено некои проблеми со програмирање со цели броеви. Забележете дека интегралноста на решенијата, што ги отежнува проблемите со линеарното програмирање, во овој случај не ја комплицира, туку, напротив, ја поедноставува процедурата (како што ни беше поедноставена со интегралноста на вградувањата во претходниот проблем).

Како пример, разгледајте го проблемот со вчитување на машината (веќе го споменавме во претходното поглавје): има одреден сет на објекти P 1 , P 2 ,..., P n (секој во една копија); нивната тежина е позната q 1 , q 2 , ..., q nи трошоците од 1, со 2 , ..., со n .Носивоста на машината е П.Прашањето е кој од артиклите треба да се внесе во автомобилот така што нивната вкупна цена (со вкупната тежина П)беше максимумот?

Треба да ги научите основните концепти и дефиниции за оперативно истражување.

Операција е секоја контролирана активност насочена кон постигнување на целта. Резултатот од операцијата зависи од начинот на неговото спроведување, организацијата, во спротивно - од изборот на одредени параметри. Секој дефинитивен избор на параметри се нарекува решение. Оптимални решенија се сметаат за оние кои, поради една или друга причина, се претпочитаат од другите. Затоа, главната задача на оперативното истражување е прелиминарно квантитативно оправдување на оптималните решенија.

Забелешка 1

Треба да се посвети внимание на формулирањето на проблемот: самото одлучување оди подалеку од опсегот на оперативното истражување и припаѓа на надлежноста на одговорното лице или група на лица, кои може да земат предвид други размислувања освен математички оправдани.

Забелешка 2

Ако во некои задачи на оперативно истражување оптималното решение е она во кое избраниот критериум за ефикасност зема максимална или минимална вредност, тогаш во други задачи тоа воопшто не е потребно. Значи, во проблемот можеме да земеме во предвид оптимален, на пример, таков број на малопродажни места и персонал во нив, во кои просечното време за услуги на клиентите не надминува, на пример, 5 минути, а просечната должина на редот во секое време ќе не повеќе од 3 лица (1, страница .10-11).

Ефикасноста на производствените и комерцијалните активности во голема мера е одредена од квалитетот на одлуките што секојдневно ги носат менаџерите на различни нивоа. Во овој поглед, задачите за подобрување на процесите на одлучување, кои оперативното истражување овозможува да ги реши, се од големо значење. Терминот „оперативно истражување“ првпат се користел во 1939-1940 година. во воената област. Во тоа време, воената опрема и нејзиното управување станаа фундаментално покомплицирани како резултат на научната и технолошката револуција. И затоа, до почетокот на Втората светска војна, имаше итна потреба да се спроведат научни истражувања во областа на ефикасно користење на нова воена опрема, квантитативна проценка и оптимизација на одлуките донесени од командата. Во повоениот период, успесите на новата научна дисциплина беа барани во мирни области: во индустријата, претприемничките и комерцијалните активности, во владините институции и во образовните институции.

Операционото истражување е методологија за примена на математички квантитативни методи за да се оправдаат решенијата на проблемите во сите области на намерна човечка активност. Методите и моделите на оперативно истражување ви овозможуваат да добиете решенија кои најдобро ги задоволуваат целите на организацијата.

Оперативното истражување е наука која се занимава со развој и практична примена на методи за најефективно (или оптимално) управување со организациските системи.

Главниот постулат на оперативното истражување е како што следува: оптимално решение (контрола) е таков збир на вредности на променливи што ја постигнува оптималната (максималната или минималната) вредност на критериумот за ефикасност (објективната функција) на операцијата и ја набљудува одредени ограничувања.

Предмет на оперативно истражување е проблемот на донесување оптимални одлуки во систем со контрола врз основа на проценка на ефективноста на неговото функционирање. Карактеристичните концепти на оперативното истражување се: модел, променливи променливи, ограничувања, целна функција.

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

Целта на оперативното истражување е квантитативно да ги поткрепи одлуките донесени за управувањето со организациите.

Решението кое е најкорисно за целата организација се нарекува оптимално решение, а решението што е најкорисно за еден или повеќе одделенија ќе биде неоптимално.

Како пример за типична задача на организациски менаџмент, каде што се судираат спротивставените интереси на одделенијата, разгледајте го проблемот со управувањето со инвентарот на претпријатието.

Одделот за производство се стреми да произведе што е можно повеќе производи по најниска цена. Затоа, тој е заинтересиран за што е можно подолго и континуирано производство, т.е. за производство на производи во големи количини, бидејќи таквото производство ги намалува трошоците за реконфигурирање на опремата, а оттука и целокупните производствени трошоци. Сепак, производството на производи во големи количини бара создавање на големи количини на залихи на материјали, компоненти итн.

Одделот за продажба е исто така заинтересиран за големи залихи на готови производи за да ги задоволи сите барања на клиентите во секое време. Склучувајќи го секој договор, одделот за продажба, стремејќи се да продаде што е можно повеќе производи, мора на потрошувачот да му понуди најширока можна палета на производи. Како резултат на тоа, често постои конфликт помеѓу одделот за производство и одделот за продажба околу палетата на производи. Истовремено, одделот за продажба инсистира на вклучување во планот на многу производи произведени во мали количини, дури и кога тие не носат голем профит, а секторот за производство бара да се исклучат таквите производи од палетата на производи.

Финансискиот оддел, настојувајќи да го минимизира износот на капиталот потребен за работењето на претпријатието, се обидува да го намали износот на „поврзан“ обртни средства. Затоа, тој е заинтересиран да ги намали залихите на минимум. Како што можете да видите, барањата за големината на залихите за различни оддели на организацијата се различни. Се поставува прашањето која стратегија за залихи ќе биде најкорисна за целата организација. Ова е типична задача на организацискиот менаџмент. Тоа е поврзано со проблемот на оптимизирање на функционирањето на системот како целина и влијае на конфликтните интереси на неговите поделби.

Главни карактеристики на оперативното истражување:

1. Систематски пристап кон анализата на поставениот проблем. Системскиот пристап, или системската анализа, е главниот методолошки принцип на оперативното истражување, кој е следен. Секоја задача, колку и да изгледа приватна на прв поглед, се разгледува од гледна точка на нејзиното влијание врз критериумот за функционирање на целиот систем. Погоре, систематскиот пристап беше илустриран со примерот на проблемот со управувањето со залихите.

2. За оперативното истражување е типично дека при решавање на секој проблем се појавуваат се повеќе нови задачи. Затоа, ако на почетокот се поставени тесни, ограничени цели, примената на оперативните методи не е ефективна. Најголем ефект може да се постигне само со континуирано истражување, обезбедувајќи континуитет во преминот од една задача во друга.

3. Една од суштинските карактеристики на оперативното истражување е желбата да се најде оптимално решение за проблемот. Меѓутоа, ваквото решение често се покажува недостижно поради ограничувањата наметнати од расположливите ресурси (пари, компјутерско време) или нивото на модерната наука. На пример, за многу комбинаторни проблеми, особено проблеми на распоред со бројот на машини n > 4, оптималното решение со современиот развој на математиката може да се најде само со едноставно набројување на опции. Тогаш човек мора да се ограничи на барање „доволно добро“ или неоптимално решение. Затоа, еден од неговите креатори, Т. Саати, го дефинираше оперативното истражување како „... уметност на давање лоши одговори на оние практични прашања на кои се даваат уште полоши одговори со други методи“.

4. Карактеристика на оперативното истражување е тоа што се спроведува на сложено, во многу области. Се создава оперативна група за спроведување на ваква студија. Се состои од специјалисти од различни области на знаење: инженери, математичари, економисти, социолози, психолози. Задачата за создавање на такви оперативни групи е сеопфатна студија на целиот сет на фактори кои влијаат на решавањето на проблемот и употребата на идеи и методи од различни науки.

Секое оперативно истражување последователно поминува низ следните главни фази:

1) опис на планската задача,

2) градење математички модел,

3) изнаоѓање решение,

4) проверка и корекција на моделот,

5) спроведување на најденото решение во пракса.

Опис на задачата за планирање:

Задачи на мрежно планирање и управување

разгледајте ја врската помеѓу роковите за завршување на голем комплекс на операции (работи) и моментите на почетокот на сите операции на комплексот. Овие задачи се состојат во изнаоѓање на минималното времетраење на збир на операции, оптимален сооднос на трошоците и времето на нивното спроведување.

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

Задачите за управување со залихите се да ги пронајдат оптималните вредности на нивоата на залиха (точки на нарачка) и големини на нарачки. Особеноста на ваквите задачи е што со зголемување на нивото на залихите, од една страна, се зголемуваат трошоците за нивно складирање, но, од друга страна, се намалуваат загубите поради евентуален недостиг на порибениот производ.

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

Задачите за поправка и замена на опремата се релевантни поради истрошеноста на опремата и потребата да се замени со текот на времето. Задачите се сведуваат на определување на оптималниот тајминг, бројот на превентивни поправки и проверки, како и моментите на замена на опремата со модернизирана.

Задачите на закажување (закажување) се да се одреди оптималната низа на операции (на пример, обработка на делови) на различни видови опрема.

Задачите на планирање и поставување се да се одреди бројот и локацијата на новите објекти, земајќи ја предвид нивната интеракција со постоечките објекти и меѓу себе.

Проблемите со избор на маршрута, или проблеми со мрежата, најчесто се среќаваат при проучувањето на различни проблеми во транспортот и во комуникацискиот систем и се состојат во определување на најекономични рути (1, стр. 15).

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

Операцијата е секогаш управуван настан, т.е. наше е да ги избереме параметрите кои го карактеризираат начинот на негово организирање.

Ќе се повика секој дефинитивен избор на параметри во зависност од нас одлука.

Оптимални решенија се оние кои поради една или друга причина се претпочитаат од другите.

Главната цел на оперативното истражување е прелиминарно квантитативно оправдување на оптималните решенија. Оперативното истражување нема за цел целосно да го автоматизира донесувањето одлуки. Одлуката секогаш ја носи личноста. Целта на оперативното истражување е да се произведат квантитативни податоци и препораки кои му олеснуваат на лицето да донесува одлуки.

Заедно со главната задача - издржување на оптимални решенија -Обемот на оперативното истражување вклучува и други задачи:

Компаративна евалуација на различни опции за организирање на операцијата,

Евалуација на влијанието врз работата на различни параметри,

Истражување на „тесните грла“, т.е. елементи, чие нарушување има особено силно влијание врз успешноста на операцијата итн.

Овие помошни задачи се од особена важност кога дадена операција не се разгледува изолирано, туку како составен елемент на целината. системиоперации. „Системски“ пристап кон задачите на оперативното истражување бара да се земе предвид меѓусебната зависност и условеноста на цела низа активности, т.е. донесе конечна одлука земајќи ја предвид улогата и местото на оваа операција во системот.

Под ефикасностоперацијата се подразбира како степен на нејзино прилагодување кон извршувањето на задачата со која се соочува.

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

Редоследот на дејства во оперативното истражување.

1. Се формулира целта на студијата и се развива изјавата за проблемот.

2. За примена на квантитативни методи на кое било поле, секогаш е потребно да се изгради математички модел на феноменот. Врз основа на анализата на својствата на оригиналот, овој модел е изграден.

3. По изградбата на моделот, на него се добиваат резултати

4. Тие се толкуваат во однос на оригиналот и се пренесуваат во оригиналот.

5. Со помош на споредба, резултатите од симулацијата се споредуваат со резултатите добиени од директно проучување на оригиналот.

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

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

Директното експериментирање на предмети за решавање на овие проблеми има голем број значајни недостатоци:

1. Нарушен е утврдениот начин на работа на објектот.

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

Препорачливо е да се решат овие проблеми на модел одделен од објектот и имплементиран на компјутер.

При моделирање на информациски системи, математичките модели се широко користени.

Методот на математичко моделирање е метод на проучување на различни предмети со составување на соодветен математички опис и пресметување, врз основа на него, на карактеристиките на предметот што се проучува.

Потребно е да се изгради математички модел. Тој формално го одразува функционирањето на оригиналот и ги опишува главните обрасци на неговото однесување. Во овој случај, сите секундарни, незначителни фактори се исклучени од разгледување.

Цел на математичкото моделирање се сложените системи. Комплексен систем е одреден начин организиран и наменски функционален збир на голем број на информации поврзани и елементи кои се во интеракција под влијание на надворешни фактори.

Постојат 4 главни фази на системи за моделирање на компјутер:

Изградба на концептуален модел на системот и негова формализирање;

Алгоритмизација на моделот на системот и развој на програма за моделирање;

Добивање и толкување на прелиминарни резултати од симулацијата;

Проверка на адекватноста на моделот и системот; прилагодување на моделот

Главната пресметка на индикаторите за квалитет на функционирањето на системот врз основа на резултатите од моделирањето, имплементацијата на моделот.

Предавање 3. Основни поими на методот на стручни проценки. Формирање на експертски групи. гласачките процедури. Методи на рангирање, спарени споредби, оценување во релативна скала.

1. Основни концепти на ИО

И ЗА – научна дисциплина, ангажирана во развој и практична примена на методи за најефективно управување со различни организациски системи.

IO ги вклучува следните делови:

1) математичка програма. (издржување на планови, програми на стопанска дејност); вклучува делови: линеарна програма, нелинеарна програма, динамична програма

2) теоријата на редици базирана на теоријата на случајни процеси;

3) теорија на игри, која овозможува да се поткрепат одлуките донесени во услови на нецелосност на информациите.

При решавање на специфичен контролен проблем, употребата на IO методи вклучува:

Изградба на економски и математички модели за проблеми на одлучување во сложени ситуации или во услови на неизвесност;

Проучување на меѓусебните односи кои го одредуваат последователното одлучување и воспоставување критериуми за изведба кои овозможуваат да се процени предноста на еден или друг начин на дејствување.

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

Операција – секоја контролирана активност насочена кон постигнување цел. Резултатот од операцијата зависи од начинот на неговото спроведување, организацијата, во спротивно - од изборот на одредени параметри. Операцијата е секогаш контролиран настан, односно од нас зависи како да избереме некои од параметрите што ја карактеризираат нејзината организација. „Организација“ овде се подразбира во широка смисла на зборот, вклучувајќи го и збирот технички средства што се користат во операцијата.

Се нарекува секој даден избор на параметри одлука . Одлуките можат да бидат успешни и неуспешни, разумни и неразумни. Оптимално разгледајте ги оние решенија кои, поради една или друга причина, се претпочитаат од другите. Главната задача на оперативното истражување е прелиминарното квантитативно оправдување на оптималните решенија.

Модел на работа – ова е прилично точен опис на операцијата со помош на математички апарат (различни видови функции, равенки, системи на равенки и неравенки итн.). Изготвувањето на модел на операција бара разбирање на суштината на опишаниот феномен и познавање на математичкиот апарат.

Ефикасност на работењето – степенот на неговата приспособливост кон исполнувањето на задачата квантитативно се изразува во форма на критериум за ефикасност - целната функција. Изборот на критериумот за ефикасност ја одредува практичната вредност на студијата. (Неправилно избраниот критериум може да биде штетен, бидејќи операциите организирани според таков критериум на ефикасност понекогаш доведуваат до неоправдани трошоци.)

Задачи на мрежно планирање и управување разгледајте ја врската помеѓу роковите за завршување на голем комплекс на операции (работи) и моментите на почетокот на сите операции на комплексот. Овие задачи се состојат во пронаоѓање на минималното времетраење на комплексот на операции, оптималниот сооднос на трошоците и времето на нивното спроведување.

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

Задачи за управување со залихи се состои во наоѓање на оптимални вредности на нивото на залиха (точка на пренарачување) и големината на нарачката. Особеноста на ваквите задачи е што со зголемување на нивото на залихите, од една страна, се зголемуваат трошоците за нивно складирање, но од друга страна, се намалуваат загубите поради евентуален недостиг на порибениот производ.

Задачи за распределба на ресурси произлегуваат со одреден сет на операции (работи) кои мора да се извршат со ограничени расположливи ресурси, а се бара да се најде оптимална распределба на ресурсите помеѓу операциите или составот на операциите.

Задачи за поправка и замена на опрема релевантни поради истрошеноста на опремата и потребата да се замени со текот на времето. Задачите се сведуваат на определување на оптималниот тајминг, бројот на превентивни поправки и проверки, како и моментите на замена на опремата со модернизирана.

Закажување (закажување) задачи се состојат во одредување на оптималниот редослед на операции (на пример, делови за обработка) на различни видови опрема.

Задачи за планирање и поставување нијасе состојат во одредување на оптималниот број и локација на нови објекти, земајќи ја предвид нивната интеракција со постоечките објекти и меѓу себе.

Задачи за избор на маршрута, или мрежа задачи кои најчесто се среќаваат при проучувањето на различни задачи во транспортот и во комуникацискиот систем и се состојат во определување на најекономични рути.

2. Општата задача на линеарна програма. Оптимално решение

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

ЛП е област на математиката која развива теорија и нумерички методи за решавање проблеми за наоѓање на екстремот (максимум или минимум) на линеарна функција на многу променливи во присуство на линеарни ограничувања, т.е., еднаквости или неравенки што ги поврзуваат овие променливи.

LP методите се применуваат на практични проблеми во кои: 1) потребно е да се избере најдоброто решение (оптимален план) од збир на можни; 2) решението може да се изрази како збир на вредности на некои променливи со големина; а) ограничувањата наметнати на изводливи решенија од специфичните услови на проблемот се формулирани во форма на линеарни равенки или неравенки; 4) целта се изразува како линеарна функција на главните променливи. Вредностите на целната функција, што ви овозможуваат да споредувате различни решенија, служат како критериум за квалитетот на решението.

За практично решавање на економски проблем со математички методи, пред сè, треба да се напише со помош на економско-математички модел. Економско-математички модел - математички опис на истражуваниот економски процес или објект. Овој модел ги изразува моделите на економскиот процес во апстрактна форма користејќи математички односи.

Општа шема на формирање на модел: И

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

2) изразување на односите својствени на феноменот што се проучува, во форма на математички врски (равенки, неравенки). Овие односи формираат систем на ограничувања на проблемот;

3) квантитативно изразување на избраниот критериум за оптималност во форма на целна функција; Јас

4) математичко формулирање на проблемот како проблем на наоѓање на екстремот на целната функција, предмет на ограничувањата наметнати на променливите.

Општ проблем на линеарно програмирањеизгледа како:

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

и линеарна функција

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

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

Пократко, генералниот проблем за линеарно програмирање може да се претстави како:

со ограничувања:

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

Под услов сите променливи да се ненегативни, системот на ограничувања (1) се состои само од неравенки - таквиот линеарен програмски проблем се нарекува стандарден (симетричен); ако системот на ограничувања се состои само од равенки, тогаш проблемот се нарекува канонски.

Посебен случај на канонскиот проблем е проблемот во основна форма, кој се разликува по тоа што сите коефициенти на векторот на ограничување бсе ненегативни, а во секоја равенка има променлива со коефициент 1, која не е вклучена во ниту една од другите равенки. Променливата со ова својство се нарекува основна променлива.

Стандардните и канонските проблеми се посебни случаи на општиот. Секој од нив се користи во својата специфична област. Покрај тоа, сите три формулации се еквивалентни една на друга: секој проблем со линеарно програмирање може да се сведе на канонски, стандарден или општ проблем користејќи едноставни математички трансформации.

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

Системот од m линеарни равенки со n променливи ја има формата

или во стенографија

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

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

Изјава 2.1. Ако за системотмлинеарни равенки соnпроменливи (м < n) рангот на матрицата на коефициенти за променливите е еднаков на 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). Точката А е аголна, бидејќи за која било отсечка што целосно му припаѓа на многуаголникот, на пример, отсечката AP, таа не е внатрешна; точката А е внатрешна на отсечката KL, но оваа отсечка не припаѓа целосно на многуаголникот.

За конвексно множество, аголните точки секогаш се совпаѓаат со темињата на многуаголникот (полиедар), додека тоа не е неопходно за неконвексно множество. Множеството точки се нарекува затворено ако ги вклучува сите негови гранични точки. Множеството точки се нарекува ограничен, ако има топка (круг) со радиус со конечна должина центрирано во која било точка од множеството што целосно го содржи даденото множество; во спротивно множеството се нарекува неограничено.

Конвексно затворено множество точки во рамнина што има конечен број на аголни точки се нарекува конвексен многуаголник ако е ограничен, и конвексен полигонален регион ако е неограничен.

Геометриско значење на решенија на неравенки, равенки и нивни системи

Да ги разгледаме решенијата на неравенки.

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

За да се одреди саканата полурамнина (горна или долна), се препорачува да се постави произволна контролна точка што не лежи на нејзината граница - конструираната линија. Ако нееднаквоста е задоволена во контролната точка, тогаш таа е исто така задоволена во сите точки на полурамнината што ја содржи контролната точка, а не е задоволена во сите точки од другата полурамнина. И обратно, ако нееднаквоста не е задоволена во контролната точка, таа не е задоволена во сите точки од полурамнината што ја содржи контролната точка, и е задоволена во сите точки од другата полурамнина. Како контролна точка, погодно е да се земе потеклото на координатите O (0; 0), што не лежи на конструираната линија.

Размислете за множеството решенија за системите на нееднаквости.

Тврдење 2. Множеството решенија на компатибилен систем m линеарни неравенки во две променливи е конвексен многуаголник (или конвексен полигонален регион).

Секоја од неравенките, во согласност со изјавата 1, дефинира една од полурамнините, која е конвексно збир на точки. Множеството решенија на заеднички систем на линеарни неравенки се точки кои припаѓаат на полурамнините на решенија на сите неравенки, т.е. припаѓаат на нивната раскрсница. Според исказот за пресекот на конвексните множества, ова множество е конвексно и содржи конечен број на аголни точки, т.е. е конвексен многуаголник (конвексна полигонална област).

Координатите на аголните точки - темињата на многуаголникот се наоѓаат како координати на пресечните точки на соодветните прави.

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

5 . Геометриски метод за решавање на проблеми со ЛП

оптимално решение на проблемот ЛП

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

Теоремата го означува главниот начин на решавање на проблемите на ЛП. Навистина, според оваа теорема, наместо да се проучува бесконечно множество остварливи решенија, за да се најде посакуваното оптимално решение меѓу нив, потребно е да се проучат само конечен број на аголни точки на растворниот полиедар.

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

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

Важна последица веднаш следи од теоремите 1 и 2: ако проблемот со LP има оптимално решение, тогаш тој се совпаѓа со барем едно од неговите прифатливи основни решенија.

Значи, оптимумот на линеарната функција на проблемот LP треба да се бара меѓу конечен број од неговите допуштени основни решенија.

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

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

Нека геометрискиот приказ на системот за ограничување е многуаголник ABCDE(Сл. 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. Општа идеја за методот симплекс. Геометриска интерпретација

Графичкиот метод е применлив за многу тесна класа на проблеми за линеарно програмирање: може ефективно да решава проблеми што не содржат повеќе од две променливи. Беа разгледани главните теореми на линеарното програмирање, од кои произлегува дека ако линеарното програмирање има оптимално решение, тогаш тоа одговара на најмалку една аголна точка на полиедарот на решението и се совпаѓа со барем едно од допуштените основни решенија на систем за ограничување. Беше посочен начин за решавање на кој било проблем со линеарно програмирање: да се наброи конечен број на изводливи основни решенија на системот на ограничувања и да се избере меѓу нив она за кое функцијата на цел ја носи оптималната одлука. Геометриски, ова одговара на набројувањето на сите аголни точки на растворниот полиедар. Таквото набројување на крајот ќе доведе до оптимално решение (ако постои), но неговата практична имплементација е поврзана со огромни тешкотии, бидејќи за реални проблеми бројот на изводливи основни решенија, иако конечни, може да биде исклучително голем.

Бројот на допуштени основни решенија што треба да се набројат може да се намали ако набројувањето се врши не случајно, туку земајќи ги предвид промените во линеарната функција, т.е. барајќи да се осигура дека секое наредно решение е „подобро“ (или барем „не полошо“) од претходното во однос на вредностите на линеарната функција (зголемување кога се наоѓа максимумот, намалувајќи го кога се наоѓа минимумот) . Таквото набројување овозможува да се намали бројот на чекори за наоѓање на оптимумот. Да го објасниме ова со графички пример.

Нека областа на изводливи решенија е претставена со многуаголник ABCDE. Да претпоставиме дека неговата аголна точка Аодговара на оригиналното дозволено основно решение. Случајното набројување би требало да проба пет изводливи основни решенија што одговараат на петте аголни точки на многуаголникот. Сепак, цртежот покажува дека по врвот Аповолно да се оди на следниот врв ВО,а потоа до оптималната точка СО.Наместо пет, беа поминати само три темиња, со што постојано се подобрува линеарната функција.

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

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

Симплекс методот првпат бил предложен од американскиот научник Ј. Канторович.

Симплекс методот, кој овозможува решавање на кој било проблем за линеарно програмирање, е универзален. Во моментов, се користи за компјутерски пресметки, но едноставни примери со методот на симплекс може да се решат и рачно.

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

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

правилото за транзиција кон најдоброто (поточно, не најлошото) решение;

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

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

Во литературата доволно детално се опишува: наоѓање на почетниот референтен план (почетно изводливо основно решение), исто така користење на методот на вештачка основа, наоѓање на оптимален референтен план, решавање на проблеми со користење на симплекс табели.

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

Да го разгледаме решението на LLP со методот на симплекс и да го претставиме во однос на проблемот на максимизација.

1. Според состојбата на проблемот, се составува неговиот математички модел.

2. Конструираниот модел се претвора во канонска форма. Во овој случај, може да се истакне основа со почетен референтен план.

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

Симплекс табела: систем на рестриктивни равенки и целна функција се внесуваат во форма на изрази решени во однос на почетната основа. Правата во која се внесуваат коефициентите на целната функција F се нарекува Ф-права или права на целната функција.

4. Почетниот референтен план се наоѓа со извршување на трансформации на симплекс со елементи со позитивна резолуција што одговараат на минималните соодноси на симплекс, а не земајќи ги предвид знаците на елементите од редот F. Ако во текот на трансформациите има 0-ред, чии сите елементи, освен слободниот член, се нули, тогаш системот на рестриктивни равенки на проблемот е неконзистентен. Ако има 0-ред, во кој, освен слободниот член, нема други позитивни елементи, тогаш системот на рестриктивни равенки нема ненегативни решенија.

Ќе се нарече намалување на системот (2.55), (2.56) на нова основа симплекс трансформација . Ако симплекс трансформацијата се смета за формална алгебарска операција, тогаш може да се види дека како резултат на оваа операција, улогите се прераспределуваат помеѓу две променливи вклучени во одреден систем на линеарни функции: една променлива оди од зависна во независна, и другиот обратно - од независен во зависен. Оваа операција е позната во алгебрата како Чекор за елиминација од Јордан.

5. Пронајдениот почетен основен план се испитува за оптималност:

а) ако нема негативни елементи во редот F (не сметајќи го слободниот член), тогаш планот е оптимален. Ако нема нули, тогаш оптималниот план е единствен; ако има барем една нула, тогаш има бесконечен број на оптимални планови;

б) ако има барем еден негативен елемент во редот F, што одговара на колона од непозитивни елементи, тогаш;

в) ако има барем еден негативен елемент во редот F и барем еден позитивен елемент во неговата колона, тогаш можеме да се префрлиме на нов референтен план кој е поблиску до оптималниот. За да го направите ова, наведената колона мора да биде доделена како резолуција, според минималниот сооднос на симплекс, пронајдете го редот за решавање и извршите трансформација на симплекс. Добиениот основен план се преиспитува за оптималност. Опишаниот процес се повторува додека не се добие оптимален план или додека проблемот не биде нерешлив.

Колоната со коефициенти за променлива вклучена во основата се нарекува разрешување. Така, избирајќи променлива воведена во основата (или избирање колона за решавање) од негативниот елемент на редот F, обезбедуваме дека функцијата F се зголемува .

Малку потешко е да се одреди променливата што треба да се исклучи од основата. За да го направат ова, тие ги сочинуваат соодносите на слободните членови кон позитивните елементи на колоната за решавање (таквите односи се нарекуваат симплекс) и ја наоѓаат најмалата меѓу нив, што ја одредува редот (решавањето) што ја содржи исклучената променлива. Изборот на променлива што треба да се исклучи од основата (или изборот на низа за разрешување) според минималниот сооднос на симплекс ја гарантира, како што е веќе утврдено, позитивноста на основните компоненти во новиот референтен дизајн.

Во чекор 3 од алгоритмот, се претпоставува дека сите елементи од колоната со слободни членови се ненегативни. Ова барање не е задолжително, но ако е исполнето, тогаш сите последователни трансформации на симплекс се вршат само со елементи со позитивна резолуција, што е погодно за пресметки. Ако има негативни броеви во колоната на слободни членови, тогаш елементот за решавање се избира на следниов начин:

1) погледнете ја линијата што одговара на некој негативен слободен член, на пример, t-ред, и изберете кој било негативен елемент во него, а колоната што одговара на неа се зема како дозволува (претпоставуваме дека ограничувањата на проблемот се компатибилни );

2) ги сочинуваат односите на елементите на колоната од слободни членови до соодветните елементи на колоната за разрешување кои имаат исти знаци (симплекс соодноси);

3) изберете ја најмалата од симплексните релации. Ќе ја одреди низата за дозвола. Нека биде, на пример, Р-линија;

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

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

Размислете за ЛП од формата:

A е матрица за ограничување;

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

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

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

Претпоставуваме дека сите равенки се линеарно независни, т.е. ранг(а)=м. Во овој случај, основата е минор од редот на матрицата А. Тоа е, има барем една подматрица B од редот m таква што |B|<>0. Сите непознати кои одговараат на B се нарекуваат основни. Сите останати се бесплатни.

Нека Б е некоја основа. Потоа, со пермутирање на колоните од матрицата A, секогаш може да се доведе A во форма A=(B|N),

каде N е подматрица составена од колони на матрицата А кои не припаѓаат на основата. На ист начин, можно е да се подели векторот x на – векторот на основните променливи и.

Секое решение на проблемот (1) го задоволува условот A*x=b и, следствено, системот ја добива следната форма:

Бидејќи |Б|<>0, тогаш постои инверзна матрица. Помножувајќи се со инверзното лево, добиваме:

- заедничка одлука.

Основно решение (во однос на основата Б) е одредено решение за проблемот (2) добиено под условот. Тогаш тоа е единствено определено.

Основното решение се нарекува остварливи, Ако.

Основата што одговара на спроведеното основно решение. повикани остварлива основа. Основното решение се нарекува дегенерирано ако векторот има нула компоненти.

Општото решение ги содржи сите решенија што постојат. Да се ​​вратиме на функцијата цел. Воведуваме Cb-коефициенти пред основните променливи, Cn-остатокот.

Така, добиваме. Заменуваме од општото решение:

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

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

Документација:Нека биде. Размислете за основното решение,.

Според тоа, дали е вредноста на целната функција за основното решение.

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

Потоа гледаме

Така, основното решение е мин. Нека, напротив, не држи, т.е. постои.

Потоа има решение за кое вредноста на целната функција ќе биде помала од вредноста на целната функција за основното решение.

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

Како да се утврди? Сите слободни променливи освен за се уште се 0 исто така.

Потоа во општото решение, каде.

Извадуваме: - неопходен услов.

Основно решение се нарекува редовно ако. Променливата ја изведуваме од основата. Со ново решение се намалува функцијата на целта, бидејќи

Алгоритам:

1. ЛП проблем во стандардна форма.

2. Оставаме линеарно независни равенки.

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

Ние пресметуваме:

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

ако, тогаш ја најдеме компонентата, прикачете ја, така ќе најдеме друго решение; – при што една од основните променливи =0. Ја отфрламе оваа променлива од основата, внесете xi. Добивме нова основа B2 конјугирана со основата B1. Потоа повторно пресметуваме.

1. Ако постои оптимално решение, тогаш по конечен број чекори ќе го добиеме.

Геометриски, постапката се толкува како премин од аголна точка до конјугирана аголна точка долж границата на множеството X, множество решенија на проблемот. Бидејќи има конечен број на аголни точки и строгото намалување на функцијата F(x) забранува двапати поминување низ истата екстремна точка, тогаш ако има оптимално решение, тогаш по конечен број чекори ќе го добиеме.

9. Економско толкување на проблемот, двоен проблем на користење на ресурсите

Задача.За производство на два вида производи P1 и P2, се користат четири типа ресурси S1, S2, S3, S4. Со оглед на залихите на ресурси, бројот на единици ресурси потрошени за производство на единица производ. Позната е добивката добиена од производна единица П1 и П2. Потребно е да се изготви план за производство на производи во кои профитот од неговата продажба ќе биде максимална.

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

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->мин.

Од друга страна, претпријатието што продава ресурси е заинтересирано за фактот дека приходот не е помал од износот што претпријатието може да го добие кога ги преработува ресурсите во готови производи.

A11 единици на ресурс S1, a21 единици на ресурс S2,…., aj1 единици на ресурс Si1,……, am1 единици на ресурс Sm се трошат за производство на единица производ P1 по цена 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. Составете зголемена матрица на системот А, која вклучува матрица од коефициенти за променливи, колона од слободни членови на системот на ограничувања и ред од коефициенти за променливи во линеарна функција.

3. Најдете ја матрицата транспонирана на матрицата А .

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

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

Врската помеѓу оптималните решенија на двојните проблеми се воспоставува со помош на теореми за двојност.

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

Ако X*=(x1*,x2*,…,xn*) И Y*=(y1*,y2*,…,ym*) се прифатливи решенија за заемни двојни проблеми за кои важи еднаквоста,

тогаш е оптималното решение на првобитната задача I, и е оптималното решение на двојната задача II.

Покрај доволниот критериум за оптималност на меѓусебните двојни проблеми, постојат и други важни односи меѓу нивните решенија. Пред сè, се поставуваат прашања: дали секогаш постои истовремено оптимално решение за секој пар двојни проблеми; дали е можно еден од двојните проблеми да има решение, а другиот да нема. Овие прашања се одговорени со следнава теорема.

Првата (главна) теорема за двојност. Ако еден од меѓусебните двојни проблеми има оптимално решение, тогаш има и другиот, а оптималните вредности на нивните линеарни функции се:

Fmax = Змин или F(X*)=Z(Y*) .

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

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

Економско значење на првата теорема за двојност.

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

Економското значење на првата теорема за двојност може да се толкува и на следниов начин: претпријатието не се грижи дали да произведува производи според оптималниот план X*=(x1*,x2*,…,xn*) и да добие максимален профит ( приход) Fmax или продавајте ресурси по оптимални цени Y* =(y1*,y2*,…,ym*) и надомести од продажбата еднаква на неа минималната цена на ресурсите Змин.

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

Нека се дадат два меѓусебни двојни проблеми. Ако секој од овие проблеми е решен со методот на симплекс, тогаш потребно е да се сведе на канонска форма, за што е неопходно да се воведе во системот на ограничувања на проблемот I (накратко) Тне-негативни променливи, но во системот на ограничувања на проблемот II () – n не-негативни променливи, каде што i(j) е бројот на нееднаквоста во која е воведена дополнителната променлива.

Системите на ограничувања за секој од меѓусебните двојни проблеми ќе бидат во форма:

Да воспоставиме кореспонденција помеѓу почетните променливи на еден од двојните проблеми и дополнителните променливи на другиот проблем (табела).

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

ако тогаш ; ако тогаш.

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

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

Коментар.Ако во еден од меѓусебните двојни проблеми се нарушува единственоста на оптималното решение, тогаш оптималното решение на двојниот проблем е дегенерирано. Ова се должи на фактот дека доколку се наруши единственоста на оптималното решение на оригиналниот проблем, недостасува барем една од главните променливи во изразувањето на линеарната функција на неговото оптимално решение во однос на неосновните променливи.

14. Објективно утврдени оценки и нивното значење

Компонентите на оптималното решение на двојниот проблем се нарекуваат оптимални (двојни) проценки на првичниот проблем. Ги повика академик Л.В.Канторович објективно условенипроценки (во литературата се нарекуваат и скриени приходи) .

Дополнителни променливи на оригиналниот проблем I, што ја претставуваат разликата помеѓу залихите би на ресурсите S1,S2,S3,S4 и нивната потрошувачка, експрес преостанати ресурси , и дополнителни променливи на двоен проблем II кои ја претставуваат разликата помеѓу трошоците за ресурси за производство на единица производ од нив и цените cj на производите P1,P2 , изразуваат прекумерна цена над цената.

Така, објективно утврдените проценки на ресурсите го одредуваат степенот на недостиг на ресурси: според оптималниот производствен план, скудните (т.е. целосно искористените) ресурси добиваат проценки кои не се нула, а неретките - нула проценки. Вредноста y*i е проценка на i-тиот ресурс. Колку е поголема вредноста на проценката y*i, толку е поголем недостигот на ресурсот. За ресурс кој не е оскуден y*i=0.

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

Трета теорема за двојност . Компонентите на оптималното решение на двојниот проблем се еднакви на вредностите на парцијалните деривати на линеарната функција Fmax(б1, б2,…, bm)според соодветните аргументи, т.е.

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

Двојните проценки можат да послужат како алатка за анализа и донесување правилни одлуки во индустријата која постојано се менува. Така, на пример, со помош на објективно утврдени проценки на ресурсите, можно е да се споредат оптималните условни трошоци и производствените резултати.

Објективно утврдените проценки на ресурсите овозможуваат да се процени ефектот на не било какви, туку само релативно мали промени во ресурсите. Со нагли промени, самите проценки може да станат различни, што ќе доведе до неможност да се користат за анализа на ефикасноста на производството. Според соодносите на објективно утврдените проценки, може да се утврдат пресметаните норми на замена на ресурсите, според кои тековните замени во рамките на стабилноста на двојните проценки не влијаат на ефикасноста на оптималниот план. Заклучок.Двојните оценки се:

1. Показател за недостаток на ресурси и производи.

2. Показател за влијанието на ограничувањата врз вредноста на целната функција.

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

4. Алатка за споредување на вкупните непредвидени трошоци и резултати.

15. Изјава за транспортна задача според критериумот трошок.

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

ТК се одликува во ЛП по сигурноста на економските карактеристики, карактеристиките на математичкиот модел, присуството на специфични методи на решение.

Наједноставната формулација на TOR во однос на трошоците е како што следува: во Тпојдовните точки A1,…,Am се соодветно a1,…,am единици на хомоген товар (ресурси) што треба да се испорачаат nпотрошувачи 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 равенки со Тnпроменливи. Се претпоставува дека вкупните резерви се еднакви на вкупните потреби, т.е.

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

За транспортниот проблем да има прифатливи планови, потребно е и доволно еднаквоста

Постојат два вида транспортни задачи: затворена , во кои вкупниот обем на товар на добавувачи е еднаков на вкупната побарувачка на потрошувачите и отворени , во кои вкупниот производствен капацитет на добавувачите ја надминува побарувачката на потрошувачите или побарувачката на потрошувачите е поголема од реалниот вкупен капацитет на добавувачите, т.е.

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

Сите тарифи за испорака на стоки до оваа точка ќе се сметаат за еднакви на нула. На овој начин отворениот модел на проблемот се трансформира во затворен. За нов проблем, целната функција е секогаш иста, бидејќи цената на дополнителен превоз е нула. Со други зборови, фиктивниот потрошувач не ја нарушува конзистентноста на системот за ограничување.

Ако, тогаш се воведе фиктивна (m + 1)-та точка на поаѓање, на која се припишува карго залиха еднаква на.

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

Следната теорема е од големо значење за транспортниот проблем.

Теорема. Рангот на матрицата на транспортниот проблем е за еден помал од бројот на равенки, т.е. р ( а )= м + n -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), продолжуваме со пополнување на следната трета ќелија во вториот ред или во втората колона. Ќе продолжиме со овој процес додека, во некоја фаза, ресурсите се и потребите bn не се исцрпат. Последната пополнета ќелија ќе биде во последната n-та колона и во последниот m-ти ред.

Правилото „минимален елемент“.

Почетниот референтен план, изграден според правилото „северозападен агол“, обично излегува дека е многу далеку од оптималниот, бидејќи трошоците cij не се земаат предвид при неговото одредување. Затоа, во понатамошните пресметки, ќе бидат потребни многу повторувања за да се постигне оптималниот план. Бројот на повторувања може да се намали доколку почетниот план е изграден според правилото „минимален елемент“. Нејзината суштина лежи во фактот дека на секој чекор максималното можно „движење“ на товарот во ќелијата се врши со минималната тарифа cij. Почнуваме да ја пополнуваме табелата од ќелијата, што одговара на најмалиот елемент cij од тарифната матрица. Најмалиот од броевите ai или bj се става во ќелијата со најниска тарифа . Потоа, редот што одговара на добавувачот, чии залихи се целосно потрошени, или колоната што одговара на потрошувачот, чија побарувачка е целосно задоволена, е исклучена од разгледување. Може да испадне дека редот и колоната треба да се исклучат во исто време ако залихите на добавувачот е целосно потрошен и побарувачката на потрошувачот е целосно задоволена. Потоа, од преостанатите ќелии од табелата, повторно се избира ќелијата со најниска тарифа и процесот на распределба на залихите продолжува додека не се распределат сите и не се задоволи побарувачката.

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

Општиот принцип на определување оптимален план на транспортната задача со методот на потенцијал е сличен на принципот на решавање на проблемот ЛП со методот симплекс, и тоа: прво се наоѓа основниот план на транспортната задача, а потоа сукцесивно се подобрува додека не се добие оптимален план.

Суштината на потенцијалниот метод е како што следува. Откако ќе се најде првичниот референтен транспортен план, на секој добавувач (секој ред) му се доделува одреден број наречен потенцијал на добавувачот Ai , а на секој потрошувач (секоја колона) му е доделен одреден број наречен потенцијал на потрошувачот.

Цената на еден тон товар во точка е еднаква на цената на еден тон товар пред транспортот + трошоците за неговиот транспорт: .

За да се реши проблемот со транспортот со потенцијалниот метод, потребно е:

1. Изградете основен транспортен план според едно од наведените правила. Бројот на пополнети ќелии треба да биде m+n-1.

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

3. Проверете ја оптималноста, т.е. за слободни ќелии пресметајте резултати. Ако, тогаш транспортот е целисходен и планот X е оптимален - знак на оптималност. Ако има барем една разлика, тогаш одете на нов референтен план. Во својата економска смисла, вредноста ја карактеризира промената на вкупните транспортни трошоци што ќе настанат поради спроведување на единствено снабдување од страна на i-тиот добавувач до j-тиот потрошувач. Ако, тогаш една испорака ќе доведе до заштеда на транспортните трошоци, ако - до нивно зголемување. Затоа, ако меѓу бесплатните насоки на снабдување нема насоки кои заштедуваат транспортни трошоци, тогаш планот што се добива е оптимален.

4. Меѓу позитивните броеви, се избира максимумот, изграден за слободна ќелија, на која одговара на циклусот за повторна пресметка. Откако ќе се изгради циклусот за избраната слободна ќелија, треба да преминете на нов референтен план. За да го направите ова, треба да ги преместите оптоварувањата во ќелиите поврзани со оваа слободна ќелија со циклусот на повторна пресметка.

а) На секоја од ќелиите поврзани со циклус со дадена слободна ќелија и е доделен одреден знак, а оваа слободна ќелија е „+“, а сите други ќелии (темиња на циклусот) се наизменично знаци „–“ и „+“ . Овие ќелии ќе ги наречеме минус и плус.

б) Во минусните ќелии на циклусот, ја наоѓаме минималната понуда, која ја означуваме со. Помалиот од броевите xij во негативните ќелии се пренесува во оваа слободна ќелија. Во исто време, овој број се додава на соодветните броеви во ќелиите со знакот „+“ и се одзема од броевите во ќелиите минус. Ќелија која претходно била слободна станува окупирана и влегува во референтниот план; а ќелијата минус, во која стоеше минимумот од броевите xij, се смета за слободна и го напушта референтниот план.

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

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

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

DP (планирање) е математички метод за изнаоѓање оптимални решенија за повеќестепени (повеќе фази) проблеми. Некои од овие проблеми природно се распаѓаат во посебни чекори (фази), но има проблеми во кои партицијата треба да се воведе вештачки за да се реши со методот DP.

Вообичаено, DP методите ја оптимизираат работата на некои контролирани системи, чиј ефект се проценува адитив, или мултипликативен, целна функција. Адитиве функција од неколку променливи f(x1,x2,…,xn) чија вредност се пресметува како збир на некои функции fj кои зависат само од една променлива xj: . Условите на адитивната целна функција кореспондираат со ефектот на одлуките донесени во одделни фази од контролираниот процес.

R. Bellman-овиот принцип на оптималност.

Значењето на пристапот имплементиран во динамичкото програмирање лежи во замена на решението на оригиналниот повеќедимензионален проблем со низа проблеми од пониска димензија. Основни барања за задачи:

1. предмет на истражување треба да биде контролиран систем (предмет) со дадена валидна државите и допуштена одделенија;

2. задачата мора да дозволи толкување како процес од повеќе чекори, чиј секој чекор се состои од усвојување решенијаОизбирање на една од дозволените контроли кои водат до промена на државата системи;

3. задачата да не зависи од бројот на чекори и да биде дефинирана на секој од нив;

4. состојбата на системот на секој чекор мора да се опише со ист (композициски) сет на параметри;

5. последователната состојба во која се наоѓа системот по изборот на решение на k-тичекор, зависи само од даденото решение и почетната состојба до почетокот к- чекор. Овој имот е главен од гледна точка на идеологијата на динамично програмирање и се нарекува недостаток на последици .

Размислете за прашањата за примена на моделот на динамичко програмирање во генерализирана форма. Нека има задача за управување со некој апстрактен објект што може да биде во различни состојби. Тековната состојба на објектот ќе се идентификува со одредено множество параметри, кои во продолжение ќе бидат означени со S и наречени вектор на состојба. Се претпоставува дека е дадено множеството S од сите можни состојби. Сетот е дефиниран и за објектот прифатливи контроли(контролни дејства) x,кое, без губење на општоста, може да се смета за нумеричко множество. Контролните дејства може да се извршат во дискретни моменти во времето, а контролата решениесе состои во избор на една од контролите. планзадачи или стратегија за управувањесе повикува векторот x=(x1,x2,…,xn-1), чии компоненти се контролите избрани во секој чекор од процесот. Со оглед на очекуваното недостаток на последователен ефектпомеѓу секоја две последователни состојби на објектот Sk и Sk+1, постои позната функционална зависност, која ја вклучува и избраната контрола: . Така, поставување на почетната состојба на објектот и избор на план Xуникатно дефинираат траекторија на однесувањеобјект.

Управување со ефикасност на секој чекор кзависи од моменталната состојба Sk, избраната контрола xk и се квантифицира со користење на функциите fk(xk,Sk), кои се суми адитивна целна функција , карактеризирајќи ја севкупната ефикасност на управувањето со објектот. (Забелешка , дека дефиницијата на функцијата fk(xk,Sk) го вклучува опсегот на дозволени вредности xk , а оваа област по правило зависи од моменталната состојба на Ск). Оптимална контрола , за дадена почетна состојба S1, се сведува на избор на таков оптимален план x* , на кој максимален износ вредности на fk на соодветната траекторија.

Главниот принцип на динамичкото програмирање е дека во секој чекор не треба да се стремиме кон изолирана оптимизација на функцијата fk(xk,Sk), туку да се избере оптималната контрола x*k под претпоставка дека сите следни чекори се оптимални. Формално, овој принцип се реализира со наоѓање на секој чекор к условни оптимални контроли , обезбедувајќи највисока вкупна ефикасност почнувајќи од овој чекор, под претпоставка дека моменталната состојба е С.

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

Овој сооднос се нарекува основна врска со повторување (основна функционална равенка)динамично програмирање. Го имплементира основниот принцип на динамично програмирање, познат и како Белмановиот принцип на оптималност :

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

Главната релација ни овозможува да ги најдеме функциите Zk(s) само Вкомбинирано со почетна состојбашто во нашиот случај е еднаквост.

Принципот на оптималност формулиран погоре е применлив само за контролни објекти за кои изборот на оптимална контрола не зависи од праисторијата на контролираниот процес, односно од тоа како системот дошол до сегашната состојба. Токму оваа околност овозможува да се разложи проблемот и да се овозможи негово практично решение.

За секоја специфична задача, функционалната равенка има своја специфична форма, но секако мора да ја задржи рекурентната природа својствена на изразот (*) и да ја отелотвори главната идеја за принципот на оптималност.

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

Математичкиот модел на конфликтна ситуација се нарекува игра , страни вклучени во конфликтот играчи и исходот од конфликтот победувајќи.

За секоја формализирана игра воведуваме правила , тие. систем на услови што одредува: 1) опции за акциите на играчите; 2) количината на информации што секој играч ги има за однесувањето на партнерите; 3) исплатата до која води секој сет на акции. Типично, добивката (или загубата) може да се квантифицира; на пример, можете да оцените загуба со нула, победа со еден и нерешено со 1/2. Квантифицирање на резултатите од играта се нарекува плаќање .

Играта се вика парна соба , ако се вклучени двајца играчи, и повеќекратни , ако бројот на играчи е повеќе од двајца. Ќе разгледаме само парни игри. На нив играат двајца играчи АИ ВО,чии интереси се спротивни, а под играта подразбираме низа дејствија од страна на АИ ВО.

Играта се вика игра со нулта сума или антагонистички ској , ако добивката на еден од играчите е еднаква на загубата на другиот, т.е. збирот на исплатите на двете страни е нула. За да ја завршите задачата на играта, доволно е да ја означите вредноста на една од нив . Ако назначиме А- освои еден од играчите, б – исплатата на другиот, потоа за игра со нулта сума б= –А, па доволно е да се разгледа, на пример А.

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

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

Некои игри може да се состојат само од случајни потези (т.н. чисти игри на среќа) или само од лични потези (шах, дама). Повеќето игри со карти припаѓаат на игрите од мешан тип, односно содржат и случајни и лични потези. Во продолжение ќе ги разгледаме само личните потези на играчите.

Игрите се класифицирани не само според природата на потезите (лични, случајни), туку и според природата и количината на информации достапни за секој играч во врска со дејствата на друг. Посебна класа на игри се таканаречените „игри со целосни информации“. Игра со целосни информации Се нарекува игра во која секој играч при секој личен потег ги знае резултатите од сите претходни потези, и лични и случајни. Примери на игри со целосни информации се шахот, дама и добро познатата игра tic-tac-toe. Повеќето игри од практично значење не спаѓаат во класата на игри со целосни информации, бидејќи непознатото за постапките на противникот обично е суштински елемент во конфликтните ситуации.

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

стратегија Играчот се нарекува збир на правила кои го одредуваат изборот на неговата акција за секој личен потег, во зависност од ситуацијата. Обично во текот на играта, при секој личен потег, играчот прави избор во зависност од конкретната ситуација. Сепак, во принцип, можно е сите одлуки да ги носи играчот однапред (како одговор на која било дадена ситуација). Тоа значи дека играчот избрал одредена стратегија, која може да се даде во форма на листа на правила или програма. (За да можете да ја играте играта користејќи компјутер). Играта се вика крајна , ако секој играч има конечен број на стратегии, и бескрајна .– во спротивно.

Со цел да се одлучи игра , или најдете одлука за игра , потребно е секој играч да избере стратегија која го задоволува условот оптималност , тие. еден од играчите мора да добие максимална победа, кога вториот се држи до својата стратегија, Во исто време, вториот играч мора да има минимална загуба , доколку првиот се придржува до својата стратегија. Таквите стратегии се нарекуваат оптимална . Оптималните стратегии, исто така, мора да го задоволат условот одржливост , тие. треба да биде непрофитабилно за кој било од играчите да се откаже од својата стратегија во оваа игра.

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

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

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

Заврши игра во која играчот АТоа има Тстратегии, и играчот Б - стрстратегии се нарекува m×n игра.

Размислете за m×n игра од двајца играчи АИ ВО(„ние“ и „противник“).

Нека играчот Аима Тлични стратегии кои ги означуваме со A1,A2,…,Am. Нека играчот ВОдостапни nлични стратегии, ги означуваме B1, B2,…,Bn.

Секоја страна нека избере одредена стратегија; за нас тоа ќе биде Аи, за противникот Бј. Како резултат на изборот на играчите на кој било пар стратегии Ai и Bj (), исходот од играта е единствено определен, т.е. победи aij играч А(позитивен или негативен) и загуба (-aij) на играчот ВО.

Да претпоставиме дека вредностите aij се познати за кој било пар стратегии (Ai, Bj) . Матрица P=aij , чии елементи се исплатите што одговараат на стратегиите Ai и Bj, повикани матрица за плаќање или игра матрица. Редовите од оваа матрица одговараат на стратегиите на играчот А,а колоните се стратегии на играчот Б. Овие стратегии се нарекуваат чисти.

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

Размислете за m×n игра со матрица и одреди ја најдобрата меѓу стратегиите A1, A2,…,Am . Избор на стратегија Ај играчот Атреба да го очекува играчот ВОќе одговори со една од стратегиите Bj за која исплатата за играчот Аминимален (играч ВОсе обидува да му „наштети“ на играчот А).

Означете со најмала исплата на играчот Акога ја избира стратегијата Ai за сите можни стратегии на играчот ВО(најмал број во јас-ти ред од матрицата за исплата), т.е.

Од сите броеви () изберете го најголемиот: .

Ајде да се јавиме пониската цена на играта, или максимална победа (maxmin). Ова е загарантирана исплата на играчот А за која било стратегија на играчот Б. Оттука,

Се нарекува стратегијата што одговара на максимумот максимална стратегија . Играч ВОзаинтересирани за намалување на исплатата на играчот А,избирајќи ја стратегијата Bj, тој ја зема предвид максималната можна исплата за А.Означи

Меѓу сите броеви, изберете го најмалиот

и јавете се врвна цена на играта или минимална исплата(минимум). Его гарантира губење на играчот Б. Затоа,

Стратегијата на минимум се нарекува минимакс стратегија.

Принципот кој им диктира на играчите избор на најпретпазливите стратегии за минимакс и максимум се нарекува минимакс принцип . Овој принцип произлегува од разумната претпоставка дека секој играч се обидува да ја постигне спротивната цел на противникот.

Теорема. Пониската цена на играта никогаш не ја надминува горната цена на играта. .

Ако горните и долните цени на играта се исти, тогаш вкупната вредност на горните и пониските цени на играта се нарекува нето цена на играта, или цената на играта. Стратегиите на минимум што одговараат на цената на играта се оптимални стратегии , и нивната севкупност оптимално решение или одлука за игра. Во овој случај играчот Адобива максимално гарантирано (независно од однесувањето на играчот) ВО)победи v, и играчот ВОго постигнува минимумот загарантиран (без оглед на однесувањето на играчот А)губење v. Решението за играта се вели дека има одржливост , тие. ако еден од играчите се држи до својата оптимална стратегија, тогаш не може да биде поволно за другиот да отстапи од својата оптимална стратегија.

Ако еден од играчите (на пример А)се држи до својата оптимална стратегија, а другиот играч (ВО)тогаш на кој било начин ќе отстапи од својата оптимална стратегија за играчот кој направил отстапување, ова никогаш не може да биде корисно;такво отстапување на играчот ВОво најдобар случај може да ја остави добивката непроменета. а во најлош случај зголемете го.

Напротив, ако ВОсе придржува до својата оптимална стратегија и Аотстапува од своето, тогаш ова во никој случај не може да биде од корист А.

Пар чисти стратегии даваат оптимално решение на играта ако и само ако соодветниот елемент е и најголем во својата колона и најмал во својот ред. Таквата ситуација, доколку постои, се нарекува power point. Во геометријата, точка на површина која има својство: симултан минимум долж едната координата и максимум по другата, се вика моќ точка, по аналогија овој термин се користи во теоријата на игри.

Играта за која , повикани Power Point игра. Елементот што го има ова својство е моќната точка на матрицата.

Значи, за секоја игра со точка на моќност, постои решение кое одредува пар оптимални стратегии за двете страни, што се разликува по следните својства.

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

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

Во теоријата на игри, се докажува дека, особено, секоја игра со целосни информации има точка на моќ и, следствено, секоја таква игра има решение, т.е. има пар оптимални стратегии за едната и другата страна, кои даваат просечна исплата еднаква на цената на играта. Ако играта со целосни информации се состои само од лични потези, тогаш, кога секоја страна ја применува сопствената оптимална стратегија, таа секогаш мора да заврши со сосема дефинитивен исход, имено, исплата точно еднаква на цената на играта.

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

Меѓу конечните игри од практично значење, игрите со точка моќност се релативно ретки; потипичен е случајот кога пониските и повисоките цени на играта се различни. Анализирајќи ги матриците на ваквите игри, доаѓаме до заклучок дека ако на секој играч му се даде избор на единствена стратегија, тогаш, врз основа на разумно дејствувачки противник, овој избор треба да се определи со принципот на минимум. Придржувајќи се до нашата максимална стратегија, за секое однесување на противникот, секако си гарантираме исплатливост еднаква на пониската цена на играта α. мешани стратегии

мешана стратегија Са играчот А се нарекува примена на чисти стратегии 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, без разлика каква активна стратегија користи играчот ВО.За игра 2v2, чистата стратегија на секој противник е активна ако нема ssdl точка. Победа на играчот А(загуба на играчот ВО)– случајна променлива, чие математичко очекување (просечна вредност) е цената на играта. Затоа, просечната исплата на играчот А(оптимална стратегија) ќе биде еднаква на vи за 1-ви и 2-ри противнички стратегии.

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

Просечна исплата на играчот А,доколку користи оптимална мешана стратегија и играчот ВО -чиста стратегија Б1 (ова одговара на првата колона од матрицата за исплати Р),еднаква на цената на играта v: .

Играчот ја добива истата просечна исплата А, ако вториот играч користи стратегија Б2, т.е. . Со оглед на тоа, добиваме систем на равенки за определување на оптимална стратегија и цените на играта v:

Решавајќи го овој систем, ја добиваме оптималната стратегија

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

Примена на теоремата за активна стратегија за наоѓање – оптимална стратегија на играчот ВО,го добиваме тоа за секоја чиста стратегија на играчот А (А1 или А2) просечна загуба на играч ВОеднаква на цената на играта v, т.е.

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

Задачата за решавање на играта, ако нејзината матрица не содржи точка на седло, е потешка, толку е поголема вредноста м И n. Затоа, во теоријата на матричните игри се разгледуваат методи со кои решението на некои игри се сведува на решение на други, поедноставни, особено со намалување на димензијата на матрицата. Можно е да се намали димензијата на матрицата со исклучување дупликат и очигледно неповолни стратегии.

Дупликат се нарекуваат стратегии кои одговараат на истите вредности на елементите во матрицата за исплата, т.е. матрицата ги содржи истите редови (колони).

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

Ако сите елементи од r-тата колона од матрицата се поголеми од соодветните елементи на j-та колона, тогаш за играчот ВО R-та стратегија е непрофитабилна (загубата е поголема).

Постапката за елиминирање на дупликативните и очигледно непрофитабилните стратегии секогаш треба да претходи на решението на играта.

23. Геометриска интерпретација на играта 2×2

Одлука за играта 2×2овозможува јасна геометриска интерпретација.

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

На апсцисата (сл.) Оставете на страна единицасегмент A1A2; точка А1 ( X=0) ја прикажува стратегијата А1, точка А2 ( X=1) ја отсликува стратегијата А2, и сите средни точки од овој сегмент се мешани стратегии Sa на првиот играч, а растојанието од Sa до десниот крај на сегментот е веројатноста p1 на стратегијата A1 , растојанието до левиот крај е веројатноста p2 на стратегијата А2 .

Да нацртаме две нормални на оската x низ точките A1 и A2: оската I-I и оската II-II. На оската I-I, ќе ги одложиме придобивките според стратегијата А1; на оската II-II - исплати според стратегијата А2.

Ако играчот А користи стратегија А1, тогаш неговата исплата според стратегијата Б1 на играчот Б е a11, а според стратегијата Б2 е a12. Броевите a11 и a12 на оската I одговараат на точките B1 и B2.

Ако играчот А користи стратегија А2, тогаш неговата исплата според стратегијата Б1 на играчот Б е a21, а под стратегијата Б2 е еднаква на a22. Броевите a21 и a22 одговараат на точките B1 и B2 на оската II.

Ги поврзуваме точките B1 (I) и B1 (II); B2 (I) и B2 (II). Доби две прави линии. Права линија B1B1– ако играчот Априменува мешана стратегија (секоја комбинација на стратегии А1 и А2 со веројатности p1 и p2) а играчот Б применува стратегија Б1. Победнички играч Аодговара на некоја точка на оваа линија. Просечната исплата што одговара на мешаната стратегија е одредена со формулата a11p1+a21p2 и е претставена со точката M1 на линија B1B1.

Слично на тоа, го конструираме сегментот B2B2 што одговара на употребата на стратегијата B2 од вториот играч. Во овој случај, просечната добивка се одредува со формулата a12p1+a22p2 и е претставена со точката M2 на права линија B2B2.

Треба да најдеме оптимална стратегија S*a, т.е. онаа за која има минимална исплата (за секое однесување ВО)би се свртел до максимум. За да го направите ова, ќе изградиме долната граница на добивката со B1B2 стратегии , т.е., скршената линија B1NB2 означена на сл. задебелена линија. Ова долната граница ќе ја изрази минималната исплата на играчот Аза која било од нејзините мешани стратегии; точкаН , во кој оваа минимална исплата достигнува максимум и го одредува решението (оптималната стратегија) и цената на играта. Точка ордината Ндали има цена за играње v. Точка координати Ннаоѓаме како координати на точките на пресек на правите B1B1 и B2B2. Во нашиот случај, решението на играта беше одредено од пресечната точка на стратегиите. Сепак, тоа нема секогаш да биде случај.

Геометриски е можно да се одреди оптималната стратегија како играч А,како и играчот ВО;и во двата случаи се користи принципот минимакс, но во вториот случај не се конструира долната, туку горната граница на исплатата, а не максималната, туку минимумот се одредува на неа.

Ако матрицата за исплата содржи негативни броеви, тогаш за графичко решение на проблемот подобро е да се префрлите на нова матрица со ненегативни елементи; за да го направите ова, доволно е да се додаде соодветниот позитивен број на елементите на оригиналната матрица. Одлуката на играта нема да се промени, но цената на играта ќе се зголеми за оваа бројка. Графичкиот метод може да се користи за решавање на играта 2×n, m×2.

24. Редукција на матрична игра на линеарен програмски проблем

Играта m×n генерално нема визуелна геометриска интерпретација. Неговото решение е прилично макотрпно за големи ТИ n, сепак, нема фундаментални потешкотии, бидејќи може да се сведе на решавање на проблем со линеарно програмирање. Ајде да го покажеме.

Нека играта m×n е дадена со матрицата за исплати . Играч Аима стратегии А1, А2,..Аи,..Ам , играч ВО -стратегии Б 1,Б 2,..Бјас,.. Б n. Потребно е да се утврдат оптималните стратегии и каде се веројатностите за примена на соодветните чисти стратегии Ai, Bj,

Оптималната стратегија го задоволува следново барање. Го обезбедува играчот Апросечната исплата не помала од цената на играта v, за која било стратегија на играчот ВОи исплата еднаква на цената на играта v, со оптимална стратегија на играчот ВО.Без губење на општоста, поставивме v> 0; тоа може да се постигне со изработка на сите елементи . Доколку играчот Априменува мешана стратегија против секој чиста стратегија Bj играч ВО,тогаш тој добива просечна исплата , или математичко очекување за победа (т.е. елементи ј-ГоКолоните на матрицата за исплати се множат член по член со соодветните веројатности на стратегиите A1, A2,..Ai,..Am и се додаваат резултатите).

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

Секоја од неравенките може да се подели со број. Да воведеме нови променливи: . Тогаш системот добива форма

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

Поделувајќи се со еднаквост, добиваме дека променливите го задоволуваат условот: . Максимизирање на цената на играта vе еквивалентно на минимизирање на количината , така што проблемот може да се формулира на следниов начин: дефинирајте ги вредностите на променливите , мада ги задоволи линеарните ограничувања(*) И додека линеарната функција (2*) се сврте на минимум.

Ова е проблем со линеарно програмирање. Решавајќи ја задачата (1*)–(2*), го добиваме оптималното решение и оптимална стратегија .

За да се одреди оптималната стратегија, треба да се земе предвид дека играчот ВОнастојува да ја минимизира гарантираната исплатливост, т.е. најдете макс. Променливите ги задоволуваат нееднаквостите

кои произлегуваат од фактот дека просечната загуба на играч ВОне ја надминува вредноста на играта, без разлика каква чиста стратегија користи играчот А.

Ако означиме (4*) , тогаш добиваме систем на неравенки:

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

Играта беше сведена на следната задача.

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

Решението на проблемот со линеарното програмирање (5*), (6*) ја одредува оптималната стратегија. Во исто време, цената на играта. (7*)

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

Така, проблемите со линеарното програмирање (1*), (2*) и (5*), (6*) се меѓусебно двојни. Очигледно, при определувањето на оптималните стратегии во конкретни проблеми, треба да се избере еден од меѓусебните двојни проблеми, чиешто решение е помалку макотрпно, и да се најде решението на другиот проблем користејќи теореми за двојност.

Кога решавате произволна конечна игра со големина m×n, се препорачува да се придржувате до следнава шема:

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

оперативно истражување) - релативно нова област, чија кратка историја датира од почетокот на Втората светска војна. Токму оваа мат. науката содржи добро дефиниран сет на општи принципи, да-рж им обезбедува на истражувачите план за спроведување на операциите на научно истражување. Ги вклучува следните фази. 1. Формулирање на проблемот. 2. Изградба на подлога. модел кој го претставува системот што се проучува. 3. Добивање решение од овој модел. 4. Проверка на моделот и решението добиено од него. 5. Воспоставување контрола врз одлуката. 6. Практ. имплементација на решение: имплементација. Формулирање на проблемот Мора да се посвети сериозно внимание на дефинирањето на општата природа на проблемот и, уште поважно, на целите на истражувањето. Овие цели треба да се формулираат во бихејвиорална смисла со цел да се минимизираат или елиминираат двосмисленоста и несигурноста. Исто така, мора да се остави време за правилно да се даде приоритет на реално остварливите цели. Премногу долг список на цели може да предизвика потенцијални потешкотии во нивното спроведување, особено ако овие цели не се јасно поврзани во логичен редослед. Изградба на математички модел Втората фаза на истражување со t.sp. И околу. предлага опис на моделот. Целта на моделот е да го претстави реалниот свет. Во I. o. таквите модели се симболични, изразени во мат. термини. Класичната равенка E \u003d mc2 е типичен пример за подлога. модели. Традиционалните форми за такви модели се алгебарски равенки, да-рж не само вал. поекономично од вербалните формулации, но исто така повлекува темелност и прецизност на дефиницијата неопходни за јасно изразување и разбирање на поединечните елементи и нивните односи. Најважната задача во градењето на таков модел е јасното и прецизно развивање и дефинирање на целната функција. Оваа функција ја изразува врската помеѓу независните и зависните променливи. Изведување решение од даден модел Третата фаза е да се најде решение. По правило, пожелно е да се најде оптимално или подобро решение, но треба да се земе предвид дека таквото решение ќе има вредност само во контекст на моделот што се разгледува. Бидејќи моделот е само приказ на реалниот свет проблем, постојат многу ситуации во кои оптималното решение можеби не е поврзано со најдобриот избор. Меѓутоа, кога оптималното решение се комбинира со помалку оптимални или пореални алтернативни решенија, со можност за нивно последователно тестирање во однос на реален проблем, употребата на оптималното решение повлекува одредени придобивки. Една таква придобивка се однесува на дефиницијата на крајот од студијата. релативното растојание помеѓу ова идеално решение и прифатената алтернатива. Нуспроизвод на оваа методологија е употребата на I. o. е претпоставката дека помалку оптималните решенија може да се гледаат како отскочна штица на патот кон постигнување на целта. Овој метод на последователни приближувања може да го доведе истражувачот на операции до поплодни резултати. Има многу душеци. постапки за добивање решенија во I. о. Овие постапки се засноваат на примена на теоријата на веројатност. Валидација на моделот и решението добиено од него Валидацијата на моделот и решението е поврзано со имплементација на два чекори. Првиот се состои во темелна анализа на сите елементи на моделот, вкл. повторно проверување на неговите алгебарски фактори за присуство на поедноставени козметички грешки, кои можат да влијаат на валидноста. Др. уште поважен чекор вклучува редефинирање на односот на моделот со претпоставките кои првично беа користени за развој на овој модел. Посистематски план за преглед вклучува и употреба на ist. податоци кои лесно може да се внесат во моделот за да може да се добие прототип решение. Овие податоци мора внимателно да се прегледаат за да се обезбеди валидноста на проверката за истражувачот на операции. Треба да се напомене дека штом овој модел практично ќе се развие врз основа на претходните извори. податоци и потреби, може да се однесува многу поинаку во иднина. Др. честа грешка е воведувањето фактори во моделот, то-рж не беа претставени во ист. база на податоци. Воспоставување контрола Петтата фаза, воспоставување контрола врз одлуката, се појавува во текот на повеќекратната употреба на моделот. Контролата врз моделот се воспоставува кога истражувачот на операции дозволува несовпаѓања во вредностите на ist. податоци и признава дека овие несовпаѓања можат да влијаат на односите помеѓу елементите на моделот и добиените решенија. Др. важен чекор може да биде развојот на ограничувања на избраните основи. параметри на моделот за да се воспостави опсег на прифатливи вредности врз основа на реални податоци. Имплементација на моделот Последниот чекор е да се воведат вистински податоци во моделот. Практ. имплементацијата на моделот е поврзана со очигледниот чекор на воведување реални податоци и добивање решение за реален проблем. Покрај тоа, исто така е важно да се процени близината на вистинското решение до ист. претходно добиени решенија, и последиците од оваа одлука за подобрување на начинот на користење на моделот. Овие чекори обезбедуваат важна врска помеѓу подлогата. природата I. o. и вежбајте. резултатите од истражувањето. На крајот на краиштата, овие одлуки и нивните менаџерски импликации се користат од искусен специјалист за вештачка интелигенција. да се усоврши моделот за можна идна употреба. Видете исто така Методологија на (научно) истражување R. S. Endrulis