Основни концепти на оперативно истражување. Операционо истражување Решение за игри во мешани стратегии

И.Н. Слинкин

Учебник за студенти на педагошките универзитети

насока информатика

Шадринск, 2003 година

Слинкина И.Н.

Оперативно истражување. Наставно помагало. - Шадринск: издавачка куќа на Државниот педагошки институт Шадринск, 2002. - 106 стр.

Слинкина И.Н. – кандидат за педагошки науки

Во учебникот е претставен теоретскиот дел од предметот „Операциски истражувања“. Наменет е за студенти на редовни и вонредни катедри на факултети кои ја спроведуваат специјалноста „Информатика“.

© Државниот педагошки институт Шадрински

© Слинкина И.Н., 2002 година

Прашања до блоковите од предметот „Операционо истражување“ 5

1.1. Предмет и цели на оперативното истражување 7

1.2. Основни поими и принципи на оперативно истражување 8

1.3. Математички модели на операции 10

1.4. Разбирање на линеарно програмирање 12

1.5. Примери на економски проблеми на линеарно програмирање. Проблемот на најдобро искористување на ресурсите 13

1.6. Примери на економски проблеми на линеарно програмирање. Проблемот на избор на оптимални технологии 15

1.7. Примери на економски проблеми на линеарно програмирање. Проблем со смесата 16

1.8. Примери на економски проблеми на линеарно програмирање. Транспортна задача 17

1.9. Основни типови на пишување задачи за линеарно програмирање 19

1.10. Методи на конверзија 21

1.11. Премин во канонска форма 22

1.12. Премин кон симетрична нотација 25

2.1. Геометриска интерпретација на проблем со линеарно програмирање 28

2.2. Графички решавање на задачи од линеарно програмирање 29

2.3. Својства на решенијата на проблем со линеарно програмирање 34

2.4. Општа идеја за методот симплекс 35

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

2.6. Знак за оптималноста на основниот план. Симплекс табели 40

2.7. Транзиција кон не-лош референтен план. 44

2.8. Симплекс трансформации 46

2.9. Алтернативен оптимум (знак за бесконечноста на множеството референтни планови) 51

2.10. Знакот за неограниченост на целната функција 52

2.11. Концептот на дегенерација. Монотоност и конечност на методот на симплекс. Јамка 53

2.12. Концептот на двојност за симетрично линеарно програмирање проблеми 54

3.1. Асиметрични двојни задачи 57

3.2. Отворени и затворени модели на транспортната задача 61

3.3. Изградба на првичниот основен план. Правило 63 од северозападниот агол

3.4. Изградба на првичниот основен план. Правило за минимален елемент 64

3.5. Изградба на првичниот основен план. Вогел метод 64

3.6. Потенцијален метод 65

3.7. Решавање транспортни проблеми со ограничувања на пропусниот опсег 69

3.8. Примери на дискретни програмски проблеми. Проблемот со транспортот на контејнери. Задача проблем 71

3.9. Суштината на методите за дискретна оптимизација 72

3.10. Задача со конвексно програмирање 74

3.11. Метод на Лагранжови множители 75

3.12. Градиентни методи 77

4.1. Методи на казнени и бариерни функции 78

4.2. Динамично програмирање. Основни концепти. Суштина на методите на решение 79

4.3. Стохастичко програмирање. Основни поими 81

4.4. Игри со матрица со нулта сума 83

4.5. Чисти и мешани стратегии и нивните својства 85

4.6. Својства на чисти и мешани стратегии 88

4.7. Намалување на матрична игра на ZLP 92

4.8. Задачи на теоријата на редици. Класификација на системи за редици 94

4.9. Пренос на настани 96

4.10. Шема на смрт и репродукција 97

4.11. Мала Формула 99

4.12. Наједноставните системи за редици 101

Прашања до блоковите од предметот „Операциски истражувања“

Блок 1

1. Предмет и задачи на оперативното истражување.

2. Основни концепти и принципи на оперативно истражување.

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

4. Концептот на линеарно програмирање.

5. Примери на економски проблеми на линеарно програмирање. Задача

6. Примери на економски проблеми на линеарно програмирање. Проблемот на избор на оптимални технологии.

7. Примери на економски проблеми на линеарно програмирање. Проблем со мешавината.

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

9. Основни типови на пишување проблеми со линеарно програмирање.

10. Методи на трансформација.

11. Премин во канонска форма.

12. Премин кон симетричната нотација.

Блок 2

1. Геометриска интерпретација на проблемот со линеарното програмирање.

2. Решавање задачи на линеарно програмирање со графички метод.

3. Својства на решенија на проблем со линеарно програмирање.

4. Општа идеја за методот симплекс.

5. Изградба на почетен основен план за решавање на проблеми од линеарно програмирање по методот симплекс.

6. Знак за оптималност на основниот план. Едноставни табели.

7. Премин кон ненајлош референтен план.

8. Едноставни трансформации.

9. Алтернативен оптимум (знак за бесконечноста на множеството референтни планови).

10. Знак за неограниченост на целната функција.

11. Концептот на дегенерација. Монотоност и конечност на методот на симплекс. Јамка.

12. Концептот на двојност за симетрично линеарно програмирање проблеми.

Блок 3

1. Асиметрични двојни проблеми.

2. Отворени и затворени модели на транспортниот проблем.

3. Изградба на првичниот основен план. Правило на северозападниот агол.

4. Изградба на почетен основен план. Правило за минимален елемент.

5. Изградба на почетен основен план. Вогел метод.

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

7. Решавање на транспортни проблеми со ограничен пропусен опсег.

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

9. Суштина на методите за дискретна оптимизација.

10. Проблемот на конвексното програмирање.

11. Метод на Лагранжови множители.

12. Градиентни методи.

Блок 4

1. Метод на казнени и бариерни функции.

2. Динамично програмирање. Основни концепти. Суштината на методите на решение.

3. Стохастичко програмирање. Основни концепти.

4. Матрични игри со нулта сума.

5. Чисти и мешани стратегии.

6. Својства на чисти и мешани стратегии.

7. Намалување на матричната игра на LLP

8. Проблеми на теоријата на редици. Класификација на системи за редици.

9. Текови на настани.

10. Шема на смрт и репродукција.

11. Мала формула.

12. Наједноставните системи за редици.

Блок 1.

Предметот и целите на оперативното истражување

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

Потребите од практиката оживеаја посебни научни методи, кои погодно се групирани под името „оперативно истражување“.

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

Нека се преземе некоја акција за да се постигне одредена цел. Лицето (или групата на лица) што го организира настанот секогаш има одредена слобода на избор: може да се организира на еден или друг начин. Одлуката е одреден избор од голем број опции достапни за организаторот.

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

Задача 1.За најдобро искористување на ресурсите.

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

Задача 2.За мешавините.

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

Задача 3.транспортна задача.

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

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

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

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

Основни концепти и принципи на оперативно истражување

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

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

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

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

Цел на оперативно истражување– прелиминарно квантитативно поткрепување на оптималните решенија.

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

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

Дефиниција:Параметрите, чија целина формира решение, се нарекуваат елементи на решението.

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

Покрај елементите на решението во која било задача на оперативно истражување, дадени се и услови кои се фиксирани во состојбата на проблемот и не можат да бидат прекршени. Особено, таквите услови ги вклучуваат средствата (материјални, технички, човечки) што може да се отстранат и други ограничувања наметнати на решението. Во својот тотал, тие го формираат таканаречениот „сет на можни решенија“. Да го означиме ова множество X, а тоа што решението x припаѓа на ова множество, ќе напишеме: хОХ.

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

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

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

Задача 1.За најдобро искористување на ресурсите.

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

Задача 2.За мешавините.

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

Задача 3.транспортна задача.

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

1. Предметот и целите на проучувањето на операциите во стопанството. Основни концепти на теоријата на оперативно истражување.

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

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

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

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

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

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

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

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

На множеството прифатливи решенија се дадени услови кои се фиксирани и не можат да бидат прекршени.

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

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

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

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

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

Настан, работа, патека.

Настаните се резултати од извршување на една или повеќе активности. Тие немаат временско продолжување.

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

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

3. Изработка и нарачка на мрежниот дијаграм.

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

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

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

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

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

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

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

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

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

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

Настан е фактот на завршување на една или повеќе работни места, неопходни и доволни за почеток на една или повеќе наредни работни места. На секој настан му е доделен број, наречен код. Секоја работа е дефинирана со два настани: код за почеток на настан, означен со i, и код за завршен настан, означен со j.

Настаните кои немаат претходни активности се нарекуваат почетни настани; настани кои немаат последователни - финални.

1 Насоката на градење мрежа може да биде од различна природа. Може да се изгради мрежен график од почетниот настан до последниот и од конечниот до почетниот (почетниот), како и од кој било од настаните до почетниот или конечниот.

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

Каква работа (работа) треба да се направи за да се започне оваа работа;

Каква работа треба да се работи паралелно со оваа работа;

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

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

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

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

4. Критична патека на мрежниот дијаграм. Временски резерви. Рани и доцни датуми на настани и активности во мрежниот дијаграм.

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

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

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

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

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

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

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

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

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

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

5. Динамично програмирање. Белмановиот принцип на оптималност и контрола.

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

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

Главниот недостаток на методот е, според зборовите на Белман, „проклетството на димензионалноста“ - неговата сложеност катастрофално се зголемува со зголемување на димензионалноста на проблемот.

6. Проблемот со распределбата на средствата помеѓу претпријатијата.

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

7. Изјава за проблемот на линеарно програмирање.

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

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

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

Контролираните варијабли се цените на сите производи од групата f.

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

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

б) барањето за ненегативност на контролираните променливи (во нашиот проблем за предвидување, ќе бараме цените за производите од групата f да не паѓаат под 80% од цените во последниот временски момент);

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

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

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

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

Најдете ја минималната вредност на функцијата

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

a11x1 + a22x2 b1

(2.2)a21x1 + a22x2 b2

aM1x1 + aM2x2 bM

(2,3) x1 0, x2 0

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

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

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

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

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

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

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

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

Симплекс методот се заснова на теорема наречена фундаментална теорема на методот на симплекс. Меѓу оптималните планови за линеарно програмирање проблем во канонска форма, неопходно е референтно решение за неговиот систем на ограничувања. Ако оптималниот план на проблемот е единствен, тогаш тој се совпаѓа со некое референтно решение. Постојат многу различни решенија за поддршка за системот за ограничување. Затоа, решението на проблемот во канонска форма би можело да се бара со набројување на референтните решенија и избирање меѓу нив она за кое вредноста на F е најголема. Но, прво, сите референтни решенија се непознати и треба да се најдат, а второ, во реалните проблеми има многу такви решенија и директно набројување е тешко возможно. Симплекс методот е одредена постапка на насочено набројување на референтни решенија. Врз основа на некое претходно пронајдено референтно решение со користење на одреден алгоритам на методот симплекс, пресметуваме ново референтно решение на кое вредноста на целната функција F не е помала од старата. По низа чекори, доаѓаме до референтно решение, што е оптимален план.

10. Изјава за транспортниот проблем. Методи за одредување на базни планови.

Има m точки на поаѓање („добавувачи“) и n точки на потрошувачка („потрошувачи“) на некој идентичен производ. За секоја ставка се дефинирани:

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

вj - побарувачка на j-тиот потрошувач, j= 1,…,n;

cij - трошоците за транспорт на една единица производство од точката Ai - i-ти снабдувач, до точка Bj - j-ти потрошувач.

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

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

Под транспортниот план се подразбира обемот на сообраќај, т.е. количината на стоки што треба да се транспортираат од i-тиот добавувач до j-тиот потрошувач. За да се изгради математички модел на задачата, потребно е да се внесат m n променливи хij, i= 1,…, n, j= 1, …, m, секоја променлива хij го означува обемот на сообраќај од точката Ai до точката Bj. Множеството променливи X = (xij) ќе биде планот што треба да се најде врз основа на изјавата за проблемот.

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

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

Ако оваа нееднаквост е строго исполнета, тогаш проблемот се нарекува „отворен“ или „неурамнотежен“, но ако , тогаш проблемот се нарекува „затворен“ транспортен проблем и ќе ја има формата (2):

Состојба на рамнотежа.

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

11. Алгоритам за решавање на транспортниот проблем.

Примената на алгоритмот бара усогласеност со голем број предуслови:

1. Трошоците за транспорт на единица производ од секоја точка на производство до секоја дестинација мора да бидат познати.

2. Мора да се знае залихата на производи во секое место на производство.

3. Мора да се знаат барањата за храна во секоја точка на потрошувачка.

4. Вкупната понуда мора да биде еднаква на вкупната побарувачка.

Алгоритмот за решавање на транспортниот проблем се состои од четири фази:

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

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

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

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

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

12. Модели за управување со залихи.

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

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

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

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

веројатност.

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

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

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

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

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

процес на надополнување. Може да биде моментален или дистрибуиран со текот на времето;

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

13. Системи за редици (QS) и индикатори за нивната ефикасност.

Системите за редици (QS) се системи од посебен тип кои спроведуваат повторено извршување на задачи од ист тип. Ваквите системи играат важна улога во многу области на економијата, финансиите, производството и секојдневниот живот. Како примери на CMOs во финансиската и економската; Во сферата, банки од различни видови (комерцијални, инвестициски, хипотекарни, иновативни, штедни), осигурителни организации, државни акционерски друштва, компании, фирми, здруженија, задруги, даночни инспекторати, ревизорски служби, разни комуникациски системи (вклучувајќи телефонски централи ), комплекси за утовар и истовар (пристаништа, товарни станици), бензински пумпи, разни претпријатија и организации во услужниот сектор (продавници, информативни пултови, фризери, билетарници, менувачници, поправки, болници). Системите како компјутерски мрежи, системи за собирање, складирање и обработка на информации, транспортни системи, автоматизирани производствени локации, производни линии, различни воени системи, особено системи за воздушна одбрана или ракетна одбрана, исто така може да се сметаат како еден вид QS.

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

Системите за редици може да бидат едноканални или повеќеканални.

Секој QS е дизајниран да опслужува (изврши) одреден проток на апликации (барања) кои пристигнуваат на влезот на системот во најголем дел не редовно, туку во случајни времиња. Барањата за сервисирање, во овој случај, исто така не траат константно, познато време, туку случајно време, кое зависи од многу случајни, понекогаш за нас непознати причини. По сервисирањето на барањето, каналот се ослободува и е подготвен да го прими следното барање. Случајната природа на протокот на барања и времето на нивното сервисирање доведува до нерамномерно оптоварување на QS: во други времиња, неуслужените барања може да се акумулираат на влезот на QS, што доведува до преоптоварување на QS, а понекогаш и со бесплатни канали, нема да има барање на влезот на QS, што доведува до преоптоварување на QS, т.е. да ги стави во мирување нејзините канали. Апликациите што се акумулираат на влезот на QS или „влегуваат“ во редот или, поради неможноста за понатамошно останување во редот, го оставаат QS непослужен.

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

14. Равенки на динамика за веројатни состојби (равенки на Колмогоров). Ограничете ги веројатностите на состојбите.

Формално диференцирајќи ја равенката Колмогоров-Чепман во однос на s при s = 0, ја добиваме директната равенка на Колмогоров:

Формално диференцирајќи ја равенката Колмогоров-Чепман во однос на t при t = 0, ја добиваме инверзната Колмогорова равенка

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

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

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

Да претпоставиме дека наведениот услов е исполнет и, според тоа, постојат маргиналните веројатности:

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

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

15. Процесот на смрт и репродукција.

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

Множечките текови λi(t) се тековите на Поасон што доведуваат до зголемување на функцијата X(t). Според тоа, μi(t) се текови на смрт што доведуваат до намалување на функцијата X(t).

Да ги составиме равенките на Колмогоров според графикот:

Ако нишка со конечен број состојби:

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

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

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

16. Системи за редици со неуспеси.

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

Треба да се напомене дека во овој случај бројот на канали е 1 (). Овој канал прима Поасон проток на барања, чиј интензитет е еднаков на . Времето влијае на интензитетот:

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

17. Системи за редици со чекање.

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

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

Ние ќе ги нумерираме состојбите на QS според бројот на барања во системот (и сервисирани и на чекање):

— каналот е бесплатен;

— каналот е зафатен, нема редица;

— каналот е зафатен, едно барање е во редот;

— каналот е зафатен, k - 1 барања се во редот;

- каналот е зафатен, тони апликации се во редот.

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

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

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

Играта со матрица со нулта сума со два играчи може да се гледа како следнава апстрактна игра со двајца играчи.

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

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

Секоја стратегија на играчот i=; j = често се нарекува чиста стратегија.

Дефиниција. Мешаната стратегија на играчот е комплетен сет на веројатности за примена на неговите чисти стратегии.

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

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

Слично на тоа, за играчот 2, кој има n чисти стратегии, мешаната стратегија y е збир од броеви

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

Бидејќи секој пат кога играчот користи една чиста стратегија ја исклучува употребата на друга, чистите стратегии се некомпатибилни настани. Исто така, тие се единствените можни настани.

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

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

Решението на игри со големина 2xn или nx2 овозможува јасна геометриска интерпретација. Ваквите игри може да се решат графички.

На рамнината XY, по должината на апсцисата, издвоивме еден сегмент A1A2 (Слика 5.1). Секоја точка од сегментот е поврзана со некоја мешана стратегија U = (u1, u2). Покрај тоа, растојанието од некоја средна точка U до десниот крај на овој сегмент е веројатноста u1 за избор на стратегија A1, растојанието до левиот крај е веројатноста u2 за избор на стратегија A2. Точката А1 одговара на чистата стратегија А1, точката А2 одговара на чистата стратегија А2.

На точките А1 и А2 ги враќаме перпендикуларите и ги одложуваме исплатите на играчите на нив. На првата нормална (коинцидира со оската OY), ја прикажуваме исплатата на играчот А кога користи стратегија А1, на втората - кога ја користи стратегијата А2. Ако играчот А користи стратегија А1, тогаш неговата исплата со стратегијата Б1 на играчот Б е 2, а со стратегијата Б2 е 5. Броевите 2 и 5 на оската OY одговараат на точките Б1 и Б2. Слично на тоа, на втората нормална ги наоѓаме точките Б "1 и Б" 2 (исплати 6 и 4).

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

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

Ординатите на точките кои припаѓаат на прекината линија B1MB"2 ја одредуваат минималната исплата на играчот А кога користи мешани стратегии. Оваа минимална вредност е најголема во точката М, затоа, оваа точка одговара на оптималната стратегија U* = (,), а нејзината ордината е еднаква на цената на играта v.

Координатите на точката М ги наоѓаме како координати на пресечната точка на правите B1B"1 и B2B"2.

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

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

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

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

Го добиваме системот: y = 4x + 2,

Ајде да го решиме: 4x + 2 = -x + 5,

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

Значи U = (2/5, 3/5), v = 22/5.

20. Биматрикс игри.

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

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

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

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

неизвесност на цели;

несигурноста на нашето знаење за животната средина и факторите кои дејствуваат во оваа појава (неизвесност на природата);

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

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

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

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

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

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

Друг екстремен случај може да биде нестохастичката несигурност (според E.S. Wentzel - „лоша несигурност“), во која нема претпоставки за стохастичка стабилност. Конечно, можеме да зборуваме за среден тип на несигурност, кога се донесува одлука врз основа на некои хипотези за законите на дистрибуција на случајни променливи. Во исто време, одлучувачот мора да ја има на ум опасноста од несовпаѓање меѓу неговите резултати и реалните услови. Овој ризик од неусогласеност се формализира со помош на коефициенти на ризик.

Одлуката за ризик може да се заснова на еден од следниве критериуми:

критериум за очекувана вредност;

комбинации на очекувана вредност и варијанса;

познато гранично ниво;

најверојатно настан во иднина.

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

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

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

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

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

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

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

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

1.3. Општа изјава за задачата на оперативното истражување

Задачите за оперативно истражување спаѓаат во две категории: а) директни и б) инверзни.

Директни задачиодговори на прашањето: кој ќе биде индикаторот за ефикасност Зако под дадени услови y  Yќе се донесе некаква одлука x  X. За да се реши таков проблем, изграден е математички модел кој овозможува изразување на индикаторот за ефикасност преку дадени услови и решение, и тоа:

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

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

З– индикатор за изведба (објективна функција),

Ф– функционална зависност помеѓу променливите.

Оваа зависност во различни модели се изразува на различни начини. Врска помеѓу И обично се изразува како ограничувања на

Доколку типот на зависност Фпознат, потоа индикаторот Зсе наоѓа со директна замена И на оваа функционалност.

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

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

Сакаше да најдетаква одлука
при што индикаторот за ефикасност З = одлучете се:

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

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

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

Заеднички карактеристики на оперативното истражување

Во секоја задача, зборуваме за некој вид на настан кој следи одредена цел.

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

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

Карактеристики на оперативно истражување

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

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

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

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

Основни концепти на оперативно истражување

ОПЕРАЦИЈА - секој контролиран (односно, зависи од изборот на параметри) настан, обединет со единствен план и насочен кон постигнување некоја цел.

РЕШЕНИЕ - секој дефинитивен избор на параметри во зависност од нас.

ОПТИМАЛНИ РЕШЕНИЈА - одлуките од една или друга причина се претпочитаат од другите.

ЦЕЛТА НА СТУДИЈАТА ЗА РАБОТА е прелиминарно квантитативно поткрепување на оптималните решенија.

ЕЛЕМЕНТИ НА РЕШЕНИЕ - параметри чиј тотал формира решение.

ИНДИКАТОР НА ИЗВЕДБА (ЦЕЛНА ФУНКЦИЈА) е квантитативен критериум кој овозможува споредување на различни решенија во однос на ефикасноста и ја одразува целната ориентација на операцијата (W => max или W => min).

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

Концептот на математички модел на операција

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

Директни и инверзни проблеми на оперативното истражување

ДИРЕКТНИТЕ ПРОБЛЕМИ одговараат на прашањето што ќе се случи ако под дадени услови донесеме некоја одлука x X, т.е. каков ќе биде индикаторот за ефикасност W (или одреден број индикатори).

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

ОБРАТНИ ПРОБЛЕМИ одговараат на прашањето како да се избере решение x со цел индикаторот за ефикасност W да се сврти на максимум (минимум).

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

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

Поглавје 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 .Носивоста на машината е П.Прашањето е кој од артиклите треба да се внесе во автомобилот така што нивната вкупна цена (со вкупната тежина П)беше максимумот?