Загальна кількість N границь області S, де шукається максимум функції P, дорівнює mn + m + kn = n(m + k) + m. Фундаментальним фактом, що установлюється теорією для задач лінійного програмування, є те, що екстремум цільової функції завжди досягається у вершинах багатогранника, яким в таких здачах являється область S пошуку екстремуму.

Динамічне програмування. На практиці часто доводиться зустрічатися з випадкам, коли метою оптимального планування є встановлення найкращої послідовності тих чи інших робіт. Розглянемо основні принципи динамічного програмування на прикладі задачі про комівояжера. Нехай є всього п’ять пунктів: A0, A1, A2, A3, A4 із відстанями. Для визначення найкоротшого шляху комівояжера будемо розвивати варіанти його пересування послідовно, пункт за пунктом. Починаємо з варіантів, що складаються з трьох ділянок: A0, Aі1, Аі2,Аі3, групуючи їх по останньому пункту Аі3. Результати розгляду варіантів записуються в таблицю. Далі розвиваються і порівнюються лише перспективні варіанти. Розвиток кожного з них є однозначним (оскільки для кожного з них залишається лише один не відвіданий пункт). Вибираємо чотири перспективних варіанти. Подальший їх розвиток заключається у поверненні у вихідний пункт A0. Для цих чотирьох остаточних маршрутів обчислимо сумарні відстані . Таким чином, наявні два оптимальні маршрути руху комівояжера A0A1A3A4A2A0 і A0A2A4A3A1 A0, що мають мінімальну з усіх можливих маршрутів довжину. В описаній процедурі в загальному випадку підлягає аналізу n(n – 1)(n – 2) + +

неповних варіантів. Якби процедура відсіву починалася з часткових варіантів, які б включали одну ділянку, то загальне число досліджуваних варіантів виразилось би сумою c1n + c2n + …+ c nn-1 = 2n – 2,що при великих n значно менше, ніж загальне число всіх варіантів, що дорівнює, як вже було відмічено, n!

3. Системний аналіз при розв’язуванні задач

планування та управління

Під системним аналізом (СА) прийнято розуміти сукупність прийомів та методів вивчення складних об’єктів, котрі будемо називати узагальненими динамічними системами. Прикладами таких систем можуть бути сонячна система, людський організм, промислове підприємство. Дослідження узагальнених динамічних систем в СА розбивається на декілька основних етапів. Постановка задачі полягає із визначення об’єкта дослідження, а також завдання критерію для вивчення цього об’єкта. Визначення границь системи та її структуризація. Зміст полягає в тому, що вся сукупність об’єктів і процесів, що мають відношення до поставленої цілі, розбиваються на два класи – власне систему, що вивчається, і зовнішнє середовище. Після цього наступає третій важливий етап - складання математичної моделі системи, що вивчається. Перший крок – параметризація, тобто опис виділених елементів системи та елементарних впливів на неї за допомогою тих чи інших параметрів. Другий крок – визначення різного роду залежностей між введеними параметрами. Характер цих залежностей може бути довільним: для кількісних (числових) параметрів залежності звичайно задаються у вигляді систем рівнянь, для якісних параметрів можуть бути використаними табличні способи завдання залежностей, основані на перерахуванні всіх можливих комбінацій значень параметрів. Сучасний СА, як правило, має справу із системами, що характеризуються великим числом параметрів різної природи. Залежності між ними звичайно являються різноманітними і складними. Одним з найбільш вживаним прийомом є розбиття досліджуваної системи на підсистеми. Виділення підсистем і встановлення їх ієрархії, окрім спрощення описання, переслідує і другу мету: у процесі дослідження виконується уточнення первісної структуризації (розбиття на елементи) і параметризація системи, а також заключна фіксація цілей і критеріїв. В результаті цього (третього) етапу виникає закінчена математична модель системи, описана на формальній (наприклад, алгоритмічній) мові. Наступний крок – дослідження побудованої моделі. Тут перша задача – прогноз розвитку досліджуваної системи. Для її розв’язку задаються різні припущення про зовнішні впливи на систему на протязі періоду, що розглядається, та за допомогою побудованої математичної моделі визначають розподіл ймовірностей значень параметрів, що характеризують систему, для довільних фіксованих моментів часу. Отримавши прогноз розвитку системи, виконують аналіз його результатів на відповідність заданим цілям і критеріям та, у випадку необхідності, виробляють пропозиції на покращення прийнятого раніше управління. Потім знову виробляється прогноз вже при новому управлінні, знову виробляється пропозиція по покращенню управління і т.д., поки не отримується задовільний результат.

По суті тут описаний метод розв’язку задачі синтезу управління методом “спроб і помилок”. Розуміється, остання задача розв’язується лише тоді, коли метою СА є розроблення оптимального або, точніше, наближено оптимального управління. В ряді випадків виявляється достатнім обмежитися лише прогнозом розвитку системи.

4. Методи теорії ігор.

Теорія ігор по суті являє собою математичну теорію конфліктних ситуацій. Мета теорії – розроблення рекомендацій по раціональному образу дії кожного з противників в ході конфліктної ситуації. Сучасна теорія ігор була розроблена в 40–х роках минулого століття як загальна математична система для аналізу економіки. Основні ідеї цієї теорії були взяті із таких звичайних ігор, як шахи, бридж, пасьянс, доміно чи шашки. Загальна теорія розроблялася без безпосереднього зв’язку з деякою конкретною грою. Гра визначається своїми правилами. Розглянемо, наприклад, задачу визначення правил гри в шахи в ході спостереження за грою. Після чотирьох-п’яти партій основні правила гри стали очевидними, однак, щоби осягти всі правила, знадобилося б спостерігати ще за дуже багатьма партіями. По аналогії з цим, складні взаємодії в системах людського суспільства або в екологічних системах можна уявляти собі як здійснення гри з дуже великим числом учасників –