Системен анализ

Публикувано на април 9 2011 Добави коментар

1. Основни понятия и определения. Класификация и основни принципи. Математическо моделиране. Примери.
2. Анализ и синтез на структурата на сложни системи. Описание структурата на сложни системи. Имитационно моделиране.
3. Генератори на случайни числа и тяхното приложение за изследване на алгоритми
4. Апроксимиране на функции. Видове. Норми на вектори.
5. Апроксимиране на функции. Метод на най-малките квадрати. Апроксимации с полиноми от вида xn.
6. Норми на матрици. Обусловеност на матрици. Източници на грешки при апроксимиране на функции
7. Апроксимации с ортогонални полиноми. Изглаждане на данни. Избор на реда на апроксимиращите полиноми. Метод на минимаксната оценка.
8. Математически програмиране. Линейно програмиране. Обща постановка на задачата.
9. Транспортна задача. Примери. Привеждане в каноничен вид.
10. Симплекс метод. Примери. Привеждане в каноничен вид.

Тема 1.
Въведение в теорията на системите. Основни понятия и определения. Класификация и основни принципи. Математическо моделиране. Примери. Компютърът като сложна система.

1.1. Въведение в теорията на системите

Теорията на системите е самостоятелно направление в науката. В понятието система могат да се включат всички обекти от естествените и хуманитарните науки. В настоящата дисциплина ще се разбира приложно-математическия аспект на понятието. Ще бъдат поставени две основни задачи:
1) създаване на единна методология при конструиране на математически модели на технически, икономически, биологически и др. системи;
2) управление на системата по най-добрия начин.

Развитието на теорията на системите е в тясна връзка с възможностите на компютърните технологии.

Определения
Понятието система от гръцки σύστημα (sustēma) и латински (systēma) означава реално или абстрактно съществуващи единици/обекти, включващи всички компоненти/елементи, които си взаимодействат или са свързани помежду си. Всеки обект, който няма връзка с други елементи на системата не е компонент на тази система.
Подсистема е множество от елементи, които представляват система сами по себе си и са част от цялата система.
Според основоположника на Техническата кибернетика Норберт Винер, под система се разбира съвокупност от елементи и връзки между тях, които схващме като една цялост.
Всяко разделяне или обединяване (агрегиране) на реални обекти/единици в системи е условно, следователно това е субективна абстрактна концепция.
Първите определения на понятието система са дадени в произведенията на гръцките философи Евклид, Платон, Аристотел и др. Те разглеждат системата като цялост и подреденост на битието. Представите за система са свързани с понятия като подсистема, елемент, връзки, структура, цялост, цел и др.
В понятието сложна система се предполага, че системата може да се разчлени на отделни подсистеми и елементи с йерархична структура на връзката. Всяка подсистема, като решава конкретна задача, осигурява достигането на общата цел.
В понятието сложна система се влага следния смисъл:
- сложната система може да се разчлени на краен брой подсистеми, които от своя страна също могат да се разчленят на по-прости подсистеми и т.н., докато се получат елементи, неподлежащи на по-нататъшно разчленяване;
- елементите на сложната система функционират във взаимодействие една с друга;
- свойствата на сложната система се определят не само от свойствата на отделните елементи, но и от взаимодействията между тях.

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

Системата взаимодейства с множество други обекти, които са извън нея. Тези външни обекти са обединени под понятието околна среда. Околната среда се определя като множество съществуващи в пространството и времето обекти, които влияят върху системата. Тези връзки са значително по-слаби от вътрешните връзки между елементите на системата.
Връзките на системата с околната среда се осъществяват чрез входовете и изходите на системата.
Съществуването на системата е свързано с осъществяването на определени цели. Целите се постигат чрез изпълнението на дадени операции. Операцията е подредена съвкупност от свързани чрез взаимни отношения и действия за постигането на целта. Операциите могат да бъдат сложни, т.е. да се състоят от няколко синхронно или последователно изпълнявани действия. При това трябва да е в сила принципът за цялост на всяка подсистема, т.е. всяка подсистема трябва да изпълнява определена съставна операция, като изходът от подсистемата да бъде вход за друга подсистема или изход за цялата система.
Действието на системата във времето се нарича поведение на системата. Стремежът й да достигне определено оптимално за нея състояние се нарича целенасочено поведение, а това състояние – нейна цел. Функцията, която определя целта на системата, се нарича целева функция (критерий за ефективност или критерий за качеството на управление). Например, при реалните икономически системи това може да бъде цена, себестойност и др., при технически системи точност или бързодействие на системите за регулиране, или някакъв технико-икономически критерии.
За постигане на поставената цел на системата тя трябва да притежава възможност за вземане на управленчески решения при наличие на различни алтернативи. От самосебе си се разбира, че системата трябва да притежава специален блок- управляваща част. Решението се формира и реализира от управляващата част на системата.
В системите се различават: входно въздействие – с което околната среда, или управляващото устройство (УУ) въздейства на сиситемата (обекта) и реакция – с която тя въздейства на околната среда. Това е показано на следната фигура.

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

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

от математическа гледна точка е едно диференциално уравнение с постоянни коефициенти k и T. Ако обаче, примерно, за обект електродвигател се регламентира, че y(t) е скорост на въртене на ротора, при подаване на захранващо напрежение u(t) на клемите му, т.е. разглежда се това уравнение в отношение с даден обект, то последното може да се приеме като математичен модел на същия.
От друга страна, създаването на ММ предполага, че същият ще бъде използван за определени изследвания на този обект или за синтез на управление.
Създаването на модел само заради самото моделиране е безсмислено.
Моделиране – това понятие се използва в два случая:
- синтез на модели;
- изследвания с модели.
В последния случай се използва и термина “симулация”.
Получаването на модел на даден обект може да стане по два подхода:
- аналитичен, когато връзката между входната и изходна величини на обекта се извежда аналитично, като се изхожда от физическите закони, описващи процесите в него;
- експериментален, обекта на изследване се третира като черна (сива) кутия, събира се по подходящ начин информация за входа и изхода, която се обработва по специални алгоритми (идентификация).
Двата подхода имат своето място в практиката на моделирането. При аналитичният подход, ММ може да се изведе когато обекта е още на етап проектиране, не съществува физически. Обикновено неговото създаване е съпроводено с определени предположения и допускания, които влияят върху точността му. Експерименталният подход изисква реално съществуващ обект. С него се правят експерименти, извеждайки го в динамика по подходящ начин. Тук моделите се получават по-прости и са пряко свързани с реален, конкретен обект. Този подход по-често се използва при синтез на системи за автоматично регулиране (САР), или оптимална настройка на параметрите на регулатори.
Доколкото като резултат от провежданата идентификация на обект се получава също модел, то моделирането и идентификацията не следва да се противопоставят, а да се разглеждат като две възможности, в много случаи взаимно допълващи се при решаване на задачата за получаване на математични модели на обекти. Моделирането към идентификацията може да се разглежда като отношение на общото към частното.
Управление – това е процес на целенасочено въздействие върху обекта, в резултат на което той ще се окаже по близо до желаното от нас състояние.
Оценяване на параметри и състояние. Оценяването е свързано с теория, даваща възможност да се получат стойности за параметрите и състоянието на основата на краен брой наблюдения (извадка от данни). Необходимо е да се направи конкретизация, тъй като с термина параметри могат да се означават параметри на модели (коефициенти на диференциални уравления), или технологични параметри (температура, налягане и др.).
Ако по измервана изходна величина за обект y(t), за време на наблюдение се определя оценка на състоянието в зависимост от съотношението между текущото време t и Т се говори за:
- задача за предсказване, ако се оценява за t > T;
- задача за изглаждане, ако се определя за t < T и
- задача за филтрация, когато се определя за t = T.
Един от съвременните подходи за изследване на сложни системи е синергетиката (наука за самоорганизацията). Изследват се явления, които възникват от съвместното действие на различни фактори, при което всеки фактор поотделно не води до получаване на същото явление или процес.
Разработваните от позицията на синергетиката нелинейни модели имат сериозно научно и практическо приложение в различни аспекти на човешката дейност. Например проблемите на пазарната икономика през последните години се оказват поле на изследвания на синерегетиката.
Използването на опростени модели се оказва особено ефективно, когато се изследват нелинейни явления и процеси. Например, оказва се, че главният мозък на човека управлява само няколко степени на свобода в човешкото тяло, а към тях се настройват всички останали. По подобен начин се конструират и различни технически и икономически системи. Във всички случаи се оказва, че за сложната система, ако се разгледа задълбочено, е нужно да бъде изяснен механизма на взаимодействие в нея. Изучаването на взаимодействието между отделните подсистеми налага изучаването на теорията на динамичните системи.
При анализ и синтез на сложни системи важно значение има разработването на методи за формализирано описание на елементите на системата и тяхното взаимодействие, декомпозицията на системата на системата на подсистеми, координация и агрегация на елементите, оптимизация на структурното изграждане на информационно-управляващи системи, числени методи за решаване на задачите. Проблемите на синтеза на структурата на системата са тясно свързани със задачите за оптимизация на тяхното функциониране. Характерът на взаимодействие между подсистемите и разпределението на функциите между тях в значителна степен се определят от приетите принципи и алгоритми.

1.2. Класификация и основни принципи

Системите се делят на материални и абстрактни. Материалните системи са обекти от реалния свят. Те от своя страна биват изкуствени и естествени. Естествените системи са съвкупност от обекти на природата (физични, химични, биологични и др.). Към изкуствените се отнасят техническите, организационно-икономическите или човешко машинните системи.
Абстрактните системи са продукт на човешкото мислене. Биват описателни (логически) и символни (математически). Логическите системи са системи от понятия и определения за структурата, основните закономерности, състоянието и динамиката на материалните системи.

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

1.3. Математическо моделиране

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

; ;

;

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

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

Някои важни формули и закони на физиката, необходими за решаване на задачата:
Енергия = Сила * Изминат път;
Кинетична енергия = 0,5 * Маса * Скорост2
Потенциална енергия = Тегло * Височина (обикновено над морското равнище);
Тегло = Маса * Земно ускорение;
Път = Скорост * Време.
Закон за запазване на енергията

Във вертикална равнина са дадени точките А и В. Да се определи такава крива, че като се спуска по нея под действие на собственото си тегло, тяло М (скиор), тръгващо от точка А, да стигне до точка В за най-кратко време. За решаване на така формулираната задача могат да се съставят различни математически модели. Йохан Бернули и неговите съвременници са разсъждавали приблизително така: въвежда се в равнината координатна система с начало т. А, хоризонтална ос At и вертикална ос Ax. Точка В има координати (tB, xB). Търси се крива от вида (t, x(t)), където x(t) е функция с непрекъсната първа производна в интервала [0, tB] и x(0)=0, x(tB)=xB. (Това изискване означава за скиора, че няма пропасти между двете точки и значително се намалява риска от непредвидени контузии за него).
На всяка крива (t, x(t)), съединяваща точките А и В, ще отговаря различно време за спускане – Т. Задачата се свежда до намирането на гладка функция x(.), удовлетворяваща условията x(0) и x(tB) = xB, която минимизира времето T(x(.)). За намиране на математическия модел на задачата се използва закона за запазване на енергията. В този смисъл се допуска, че сумите от кинетичната и потенциалните енергии в точките А и В, както и в междинни точки (M и N) са равни. За простота се счита, че потенциалната енергия в точка М е нула, а кинетичната енергия в точка А – също нула, т.е. потенциалната енергия от точка A изцяло се превръща в кинетична енергия в точка М (загубите от силата на триене не се отчитат),
(1) ,
където m масата на тялото, g – земното ускорение, v(t) – скоростта в точка (t, x(t)).
Следователно
(2)
(1) и (2) следват от учебния материал по физика от средното училище.
Времето за преминаване от точка М (с координати (t, x(t)) до точка N (с координати (t+dt, x(t+dt)) по дъга от кривата с дължина

(3)

(3) следва от Питагорова теорема (разстояние между две точки в правоъгълна координатна система) и материалът от курса по Висша математика за дължина на крива, разделът за определени интеграли.
Като се знае връзката между времето, скоростта и пътя (изучава се в VI клас), може да се изчисли dT- времето за преминаване от точка М до точка N
(4)
Общото време за преминаване от точка А(0, 0) до точка В(tB, xB) ще бъде
(5)
(5) се съставя на базата на допускането, че общото време за спускане от точка А до точка В е сума от времената за преминаване между последователни двойки точки, разположени на безкрайно малко разстояние една от друга. Т.е. от основното определение на понятието интеграл лесно се достига до (5).
При така съставения математически модел се търси функцията x(t). А една функция не може да се определи с краен брой елементи. От гледна точка на представянето на една функция в паметта на една изчислителна система ще са необходими безкраен брой клетки от паметта за съхраняване стойностите на функцията. Това е така даже и за най-простата линейна функция .
В този смисъл задачата за най-бързото спускане, както и задачите от вариационното смятане са безкрайно мерни. Т.е. решението на горната задача може да бъде намерено за клас криви, например полиноми до определен ред, експоненциални криви, логаритмични криви, комбинации от различни видове и т.н. Тогава съхраняването на функцията в изчислителните системи няма да бъде по безкраен брой стойности, а по начална и крайна стойност и по параметри. (В случая за линейна функция a и b). При решаване на реална задача никога не се налага да се извършват изчисления с всички стойности на функцията. Необходимо е да се изчислява нейната стойност в конкретна точка.

Пример 2. Артилерийско оръдие. (да се тества на лабораторни упражнения)
Артилерийско оръдие изстрелва снаряд скорост Vo=1000 м/сек. Ако не се отчита влиянието на вятъра (посока и скорост), силата на триене и влажността на въздуха да се определи ъгълът на изстрелване, времето за достигане до целта и да се начертае графиката на движение на снаряд, който трябва да порази цел в следните случаи:
- оръдието е в началото на координатната система, а целта - на зададено разстояние от началото на координатната система и е върху оста Х;
- оръдието е на оста Y (положителна и отрицателна ордината), а целта – на зададено разстояние от началото на координатната система и е върху оста Х;
- оръдието е в началото на координатната система и е насочено по посока на оста X, а целта е със зададени координати. Да се предложи решение в декартова (какво е декартова координатна система? Кой е Рене Декарт?) и полярна координатни системи.
За решение на задачата е необходимо да се състави математически модел на движението на снаряда.

Математическия модел за решението на задача изисква припомняне на познания по физика от средното училище за движение на материална точка в пространството. В случая движението може да се моделира във вертикална равнина xOy. Единствена сила, която действа на снаряда е собственото му тегло (другите фактори – скорост и посока на вятъра, сила на триене на въздуха, влажност и др. са пренебрегнати). Необходимите величини за изчисленията са началната скорост (V0) и ъгъла на изстрелване (α).
Във вертикална посока законите за скоростта и пътя са следните:

(1) , където ;

В хоризонтална посока движението е равномерно, защото не действат сили в тази посока, т.е.
(2) , където

За да се намери разстоянието ОА, е необходимо да се определи времето. Времето tOA = 2. tOB, a tOB може да се намери от (1), защото в точка скоростта по вертикалната ос става равна на нула:
(3)
Най-голямата стойност на ОА ще се бъде, когато sin 2α = 1, т.е. 2α = 900, α = 450.
В настоящия пример е известна стойността на ОА и началната скорост, а се търси α
(4)
С модела на движение на снаряда (1) - (4) могат да се изчисляват координати на снаряда във всеки момент от неговото движение и да се начертае графиката на изминатия от него път. В цикъл се задава начална стойност на t = 0 и стъпка зависеща от точността, като крайната стойност на t е дадена в (3).

Пример 3. Компютърна система.

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

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

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

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

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

Б. Данните се актуализират в една обща форма. Увеличава се сложността за актуализация на обектите (ListBox)

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

Еднаквата структура на таблиците води до създаването само на една таблица за

съхраняване на данните. Тогава ще възникнат проблеми при актуализация и търсене, защото трябва да се определи кои данни ще се актуализират или търсят. Необходими са функции за определяне вида на обекта (по реда на йерархията - „баба”, „мама” или „аз”), с помощта на които да се поддържа целостта на данните. Визуално за потребителя се създават проблеми кой обект се актуализира. Например, след добавяне на нова област, която няма все още общини и населени места при следващото добавяне възниква проблема какво се добавя дали - нова област или първата община към нея. Поради тази причина се налага добавянето на два Check Box-а, за да се уточни вида на добавянето. Къде трябва да се добави новия обект, може да се идентифицира абсолютно точно, ако се използват цветове.

Идеята за това идва от древността. Известна е историята на древните инки, които са позволили държавата им да бъде заробена от шепа испански конквистадори, предвождани от Ф. Писаро. Той умело е използвал борбата за престола между двамата братя – Атахуалпа и Хуаскар. Примамил е първия в лагера си и го затворил в тъмница, после поискал откуп в злато, който да запълни килията, в която бил затворен Атахуалпа. После убил Хуаскар и обвинил брат му, че е извършил братоубийството. Организирали съд по всички испански правила и го осъдили на смърт. Инката искал страстно много да живее, предал страната си и вярата си, но не избягнал смъртта. Пред лицето на смъртта, обаче, той успял да предаде на инките последно писмо-кипу, в което имало заповед да се скрие всичкото злато на инките. Още същия ден повелята му била изпълнена. Десет хиляди инки понесли съкровищата в известно само на тях място. Уморени и гладни те вървели много дни и нощи и свято вярвали, че все някога ще изгонят убийците от земите си скъпоценностите отново ще заемат местата си в храмовете.
Уви, това не се сбъднало. Държавата на инките не се възродила отново. Огромните им съкровища не са намерени и до днес. В историята и традициите на древните инки има много необикновени неща. Едно от най-интересните е липсата на по-висши форми на писменост.
Преданието разказва, че някога инките са имали по-висша писменост, която наричали „килка”. Веднъж страната била обхваната от епидемия и смъртта косяла хората. За да умилостивят боговете, върховният жрец на инките послушал съвета на оракула и заповядал да се унищожат всички паметници на писмеността и забранил използването на това писмо.
Но В. де ла Хара, сътрудничка на музея по археология и етнография към университета „Сан Марко” в Лима, прави съобщение, че е намерила и отчасти разшифровала оригиналната писменост на инките.
Още като студентка тя започва да се занимава с писмеността на инките. Тя е стигнала до извода, че без писменост не е възможно достигане на такова добро съгласуване между всички части на държавния механизъм. Тя намерила решението на проблема върху пъстрите тъкани с различни геометрични фигури и орнаменти на тях. Тя намерила и една много интересна закономерност – в писмеността на инките цветът се използвал за означаване на граматичните и смислови различия, в частност – в писмеността на инките цветът се използвал за разграничаване на глаголните времена. Например знакът за глагола „вървя”, нарисуван със зелен цвят, означава „вървях”, с червен – „вървя”, със син – „ще вървя”.

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

Адекватност на математичните модели (примери) – най-важно условие за тяхното качество !!!

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

В случая може да се говори за създаване на абсолютно неадекватен модел на реалната система.
Тема 2.
Анализ и синтез на структурата на сложни системи за управление. Модели на сложни системи. Имитационно моделиране. Генератори на случайни числа и тяхното приложение за изследване на алгоритми.

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

2.1. Анализ и синтез на структурата на сложни системи за управление

Структурата на системата представлява съвкупност от елементите и връзките между тях, които се определят от разпределението на функциите и поставените пред системата цели. Структурата е начин за организация на цялото (системата) от съставните му части. Ефективността на структурата зависи от броя, значимостта, формата и съдържанието на съставните й части, мястото, което те заемат в цялата система, и съществуващите отношения между тях. В по-широк смисъл структурата е обобщено отношение, което описва системата. Една от главните задачи на структурния анализ е построяването на нагледен модел, който да изобразява съществуващите отношения (връзки), както между елементите, така и с околната среда.
Често структурата е начин за описание на системата като цяло. При това отделните подсистеми не винаги съответстват на реални физически обекти. Те могат да се избират като удобство при осъществяване процеса на управление. Описанието на структурата на сложните системи много често се задава във вид на структурни схеми, т.е. съвкупност от блокове със зададени входове, изходи и връзки между блоковете.
Задачите за анализ на структурата на сложни системи за управление са свързани с определянето на основните характеристики на системата при избрана или зададена структура. Независимо от нивото на разглеждане, общата задача за структурен анализ се свежда до определяне на структурните свойства на цялата система и отделните й подсистеми, като се използват наличната информация и описанието на елементите от системата и взаимните им връзки.
При синтеза на структурата на сложни системи за управление се решават следните задачи:
1. Синтез на структурата на управляваната система, т.е. определяне на състава и взаимните връзки между елементите на системата, оптималната декомпозиция на множеството от управляваните обекти на отделни подмножества.
2. Синтез на структурата на управляващата система:
- избор на броя на нивата и подсистемите (йерархията на системата);
- избор на принципа на организация на управлението, т.е. установяване на правилни взаимоотношения между нивата (съгласуване на целите между отделните подсистеми на различните нива, оптимално стимулиране, разпределяне на правата и отговорностите, създаване на условия за вземане на решения и т.н.)
- оптимално разпределяне на функциите между хората и техниката;
- избор на организационна йерархия.
3. Синтез на структурата на системата за обработване и предаване на информация.

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

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

2.2. Описание на структурата на сложни системи за управление

Конфигурирането на мрежата, по която се обменя информация между подсистемите в сложната система, има важно значение за нормалната работа. В голяма степен тя определя топологията на системата, пространственото разположение на източниците и потребителите на информация.
Най-често използваният математически апарат за изследване каналите за връзка в йерархичните системи е теорията на графите, елементи на която са изучавани в дисциплина „Синтез и анализ на алгоритми”. Графът е съвкупност от множеството на върховете и множеството на ребрата. За структурата на системата върховете са източници и потребители на информация, а ребрата – канали за връзка, които свързват източниците и потребителите на информация. Ако не се отчита ориентацията на графа, а само ребрата, съединяващи върховете, той се нарича неориентиран. Последователността от ребра, които съединяват върхове, образуват верига. Затворена верига се нарича цикъл. Граф, на който ребрата са ориентирани, се нарича ориентиран. Граф, част от ребрата на който са ориентирани, а друга част неориентирани, се нарича смесен.

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

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

2. Матрично представяне.
Съществуват различни форми за матрично представяне на граф.
Матрицата на върховете на неориентирания граф има вида , където , при наличие на връзка и - при отсъствие на връзка. При неориентирани графи тази матрица е симетрична.
При ориентирани графи матрицата А се определя по следния начин:
, ако от върха Oi може да се достигне директно до върха Oj;
- в обратния случай.
Матрица А характеризира връзката връх-връх на графа !!!!!!!!!

Матрицата на инциденциите B при неориентираните графи се определя по следния начин
;
За ориентиран граф

Матрица B характеризира връзката връх-ребро!!!!!!!!
3. Представяне на графи с помощта на множества.

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

Пример 2.1. за описание структура на система със: структурна схема; граф; матрично и множествено. ПОДОБНА ЗАДАЧА ЗА КОНТРОЛНА РАБОТА !!!!!

Матриците А и В са следните (каква размерност има А?)

.
Матрицата В има толкова реда, колкото са върховете на графа и толкова стълба, колкото са ребрата на графа.

Задаването на структурата с помощта на множества е следното
G(1)=(2,3); G(2)=Φ; G(3)=(4,5); G(4)=(2); G(5)=(1,2) – десни инциденции.
G-1(1)=(5); G-1(2)=(1,4,5); G-1(3)=(1); G-1(4)=(3); G-1(5)=(3) – леви инциденции.

2.3. Модели на сложни системи

При изучаване на всяка система се създава модел, който дава възможност да се предсказва нейното поведение. Моделът е отражение на оригинала, на определена страна или група от неговите свойства.
Моделът има следните 4 основни функции:
1) моделът е най простият начин за концентриране и съхранение на цялата информация за свойствата на системата;
2) чрез него и с негова помощ по най-прост, а в много случаи и единствен начин се предава информация за системата (например чрез модела се предава информация на регулатора за динамичните свойства на обекта, който ще се управлява);
3) моделът може да служи за предсказване (прогнозиране) поведението на системата в областта на изменение на входните променливи при валидност на предположенията, при които е създаден;
4) моделът служи като средство за изследване.
Описанието на системите може да се разглежда от функционална и информационна гледна точка.
Функционалното описание на системата определя нейното място и състояние, като оценява нейните взаимоотношения с другите системи и външната среда. Състоянието на системата е множество от съществените свойства, които тя има в даден момент. Външната среда е множество от елементи, които не влизат в състава на системата, но изменението на тяхното състояние предизвиква изменение в състоянието на системата. Изменението на състоянието на системата във времето се предсказва чрез модела на функциониране на системата.
Информационното описание дава представа за организацията на системата. То определя зависимостта между състоянието на системата и нейната структура.
Моделирането има важно значение за управлението на една система. Това е метод за пряко опознаване, при който изучаваният обект (оригинал) се поставя в определено съотношение с друг обект (модел, образ) и моделът е в състояние да замести оригинала на определен стадий на познавателния процес. Моделирането е начин на изобразяване и изучаване на обективната действителност, при който се използват модели.
Моделът е абстрактна или физически реализирана система, която отразява или възпроизвежда определени качества и свойства на изследвания обект (оригинал). Той е обект, система или понятие в определена форма, различна от формата на тяхното реално съществуване.
Моделът е средство, с което се обясняват, опознават и усъвършенстват системите и е удобен инструмент на управлението им. Често под модел се разбира набор от математически зависимости и съотношения, записани на естествен или изкуствен език, които отразяват най-съществените страни на обекта. По своята същност моделът е опростен образ на оригинала. Между оригинала и модела съществуват строго определени съответствия, които позволяват да се изследват системите чрез техните модели. Тъй като моделът отразява само някой от главните, съществените за дадена цел на изследването характеристики на обекта, въпросът за адекватността на модела спрямо оригинала трябва да се разглежда в зависимост от целите на моделирането (робот – домашен помощник; робот – фризьор).
Ролята на математическото моделиране с развитието на изчислителната техника нараства значително. С негова помощ се решават най-различни задачи в областта на автоматизацията във всички производства:
- оптимизация на проектните решения. Избор на най-подходящите процеси, апарати и технологични режими;
- проектиране на най-рационалната система за управление по отношение на структура, функционални възможности и техническа реализация;
- контролни експерименти в случаите, когато е невъзможно те да се извършват върху реалния обект (ядрена енергетика, изследване на динамичното поведение, управляемост на кораба);
- проектиране на информационно осигуряване за всички звена.

При съставяне на математически модели могат да се спазват следните етапи:
1. Изучаване на обекта. Измерват се параметри. Натрупва се статистическа информация. Провеждат се експерименти;
2. Съдържателно описание. Словесно във вид на прости зависимости и блокови схеми се описват свойствата на изследвания обект. Обосновава се постановката на задачата;
3. Декомпозиция. Сложните процеси се декомпозират на подпроцеси;
4. Съставяне на математическото описание. След като са уточнени връзките между отделни подсистеми чрез система от математически съотношения на базата на материалните и енергетичните баланси и фундаменталните закони на физиката, химията, биологията и др. се записват алгебрични, диференциални или интегрални уравнения или системи. Добавят се логически условия и неравенства за ограничения на параметрите;
5. Уточняване на модела. С наличната информация се имитира въздействието върху модела. При различия се правят корекции в параметрите му.

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

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

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

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

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

2.3. Имитационно моделиране

Развитието на мощна компютърна техника през последните години даде тласък на имитационното моделира при изследване на сложни системи. При него с помощта на компютър и подходящо програмно осигуряване е възможно да се възпроизвежда поведението на сложната система. Следователно под имитационно моделиране се разбира осъществяването на компютър на числен метод за реализация на експерименти с математически модели, които описват определени страни от поведението на сложната система с цел получаване на определени функционални характеристики. Необходимостта от прилагането на метода на имитационното моделиране се обуславя от:
1. Сложността на математическите модели и наличието на множество случайни фактори, което ограничава ефективното приложение на класическите методи;
2. Възможността за имитиране, наблюдаване и прогнозиране на поведението на системата в широки граници на изменение на параметрите и околната среда при непълна информация;
3. Определяне на съществените параметри на системата.

Недостатъците на имитационното моделиране са:
1. Често се получават сложни модели, което затруднява програмирането и експериментирането;
2. Анализът на резултатите се извършва с методите на математическата статистика. За получаване на статистически достоверни резултати, е необходимо многократно повторение на имитационните експерименти;
3. Не съществуват методически обосновани принципи за построяване на широк клас модели.
Независимо от посочените недостатъци методът на имитационното моделиране се развива с ускорени темпове.
Етапът на построяването на математически модели за функционирането на системата включва определянето на входните, изходните и управляващите величини и взаимната им връзка в общия алгоритъм за функциониране на системата с цел оценяването на стойностите на избраните критерии. При имитационното моделиране често математическото описание се представя като алгоритмично описание на моделирания процес чрез съдържателно описание на процеса на функциониране на системата. При това са налице два противоречиви фактора: усложняване или опростяване на модела. Във всички случаи е необходимо да се правят разумни компромиси с цел повишаване ефективността на модела. На този етап се определят случайните и детерминираните променливи, структурата на модела и се оценяват параметрите му. Етапът завършва с оценка адекватността на модела. Трябва да се оцени включването на несъществените и съществените променливи, верността на функционалните връзки между входните и изходните променливи, правилното определяне на параметрите на модела и др.
На етапа на програмното осигуряване на имитационното моделиране се решават задачите за съставяне на програмния продукт с универсални или проблемно ориентирани езици, съставяне на програмни процедури за имитация на случайните величини, а също и за настройка на програмите.
При планиране на експеримента се решават задачите за сходимост на стохастичните оценки и броя на имитационните експерименти, след което се съставя планът за провеждането на експерименти с оборудването.

При имитационното моделиране се извършва последователно постъпково моделиране поведението на обекта с помощта на компютър. За целта е необходимо задаване на алгоритъм за определяне на състоянието на модела в следващия момент.

или в рекурентен вид ,
където:
- вектор на състоянието;
- вектор на състоянието на входните величини;
- вектор на управлението.

Фиг.2.1
Следователно състоянието на обекта при имитационното моделиране се определя от рекурентни зависимости за всяка стъпка, като се използват резултатите от предходната. В имитационните модели могат да се отчитат и неконтролируеми фактори:
, където Z(t) е случаен процес, който моделира неопределеността на обекта и средата. Тя може да бъде свързана както с бързите изменения на параметрите на обекта, така и със смущенията, които се наслагват върху входните и изходните сигнали. Тъй като Z(t) е ненаблюдаем, неговото влияние може да се моделира с помощта на метода на Монте Карло, като предварително се дефинират някои статистически свойства на Z(t) (закон за разпределение, корелационни характеристики и други).
Имитационни модели на сложни системи с дискретни събития
Към класа на сложните системи за управление, моделирани като системи с дискретни събития, се отнасят информационните системи, комуникационните системи и други. Моделиращият алгоритъм трябва да бъде дискретна апроксимация на математическия модел за функционирането на системата. За решаване на задачите на имитационното моделиране в този клас системи най-разпространен е принципът на особените състояния. Привеждането на моделиращия алгоритъм в съответствие с този принцип е свързано с моделирането на разглеждания клас системи като съвкупност от паралелно протичащи процеси. Този принцип за имитационното моделиране на системи с дискретни събития се използва при проектирането на сложни системи. Той позволява да се декомпозират моделите на блоковете, при което в имитационния експеримент могат да се включат както блокове с възможност за аналитично описание, така и блокове за експериментално изследване.
При функционирането на сложните системи върху тях действат множество случайни фактори, които при имитационното моделиране трябва програмно да се реализират с помощта на компютър. Това са случайната продължителност на обслужването в системата, случайната продължителност на интервалите, през които пристигат заявките и др. За целта се прилагат различни алгоритми за програмна имитация на различни случайни фактори.

2.4. Генератори на случайни числа и тяхното приложение за изследване на алгоритми

Генерирането на последователности от случайни числа с различно разпределение често се използва за тестване на алгоритми, които по-късно ще се прилагат за анализ на данни, в които присъства случаен елемент. Получаването на случайни числа може да се постигне по няколко метода. Ето някои от тях:
1. Използва се случаен физически процес (например момента на емитиране на електрон от катод). Такива ефекти има много в природата, но трудно могат да се използват на практика, поради необходимост от тяхното измерване
2. Могат да се използват предварително получени последователности от случайни числа, които са записани на файл. Съществуват и книги - таблици със случайни числа с равномерно разпределение, например 01-99, или 001-999 и т.н.
3. Използват се алгоритми, които генерират случайните числа, които веднага се използват от компютърната програма. Такива числа не са изцяло случайни, съществува повторяемост на резултатите, затова се наричат псевдослучайни.

Методите за генериране на случайни числа с едно или друго разпределение обикновено се основават на първоначално получаване на случайно число с равномерно разпределение в интервала [0, 1]. Това число след това се преобразува в друго разпределение. В областта на теорията на числата най-добре е изучена целочислената аритметика. Затова е достатъчно да се генерира цяло число в интервала на неотрицателните числа [0, 231-1], след което полученото цяло число се преобразува в число с плаваща запетая в интервала [0, 1].

Универсално използван метод за генериране на псевдослучайни числа се състои в избор на функция f, която изобразява множеството на целите числа в себе си. Избира се по някакъв начин и следващото цяло число се генерира по израза xk+1 = f(xk). В началния етап на прилагане на алгоритъма f са избирани като доста сложни и невъзможни за разбиране, например като f(x) се избира това цяло число, чието двоично представяне са средните 31 цифри от квадрата на x, представен с 62 цифри.
Използвайки теорията на числата, f може да се избере така, че периодът на повторение да е възмоно най-дълъг, с което се избягва зацикляне на редицата.
Най-често използваната функция за генериране на случайни числа разпространена сега е

където m е t-цифрено двоично число, обикновено 2t. x0, a и c са цели числа от същия интервал. Изхождайки от теорията на числата се дават следните препоръки за избор на същите:

1. x0 може да се избере произволно, включително и x0 = 1. Удобно е при експлоатационни условия на програмата да бъде цифрово представяне на времето, с което ще се получат различи редици.
2. Изборът на а трябва да удовлетворява следните три изисквания:
а) a (mod 8) = 5;
б) ;
в) двоичните цифри на а не трябва да имат видима наредба.
3. Стойността на c се избира да бъде нечетно число, което удовлетворява условието

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

Получаваните случайно генерирани псевдослучайни последователности с равномерно разпределение се използват за генериране на случайни числа с друг закон на разпределение. Най-често срещаното в природата разпределение е нормалното. Основните характеристики на всяко разпределение са средна стойност (математическо очакване) и дисперсия. В литературата са описани различни алгоритми за преобразуване на случайно генерирани числа с равномерно разпределение в числа с нормално разпределение N(0,1). Ето два алгоритъма:

Алгоритъм 1
1. Генерират се 12 числа yi с равномерно разпределение в интервала [0, 1).
2. Изчисляват се 12 числа xi с равномерно разпределение в интервала [-1, 1) по формулата и се сумират.
Полученото число е с достатъчно добро приближение на нормално разпределение (нулево математическо очакване и дисперсия единица). Методът е относително бавен.

Алгоритъм 2
1. Генерират се две случайни числа U1 и U2 с равномерно разпределение в интервала [0, 1).
2. Изчисляват се V1=2*U1-1 и V2=2*U2-1, които също ще са с равномерно разпределение, но в интервала [-1, 1).
3. Изчислява се . Ако S > 1, V1 и V2 се отхвърлят и се преминава към стъпка 1.
4. Изчисляват се и .
Доказано е, че X1 и X2 са случайни величини, имащи нормално разпределение с нулево математическо очакване и дисперсия равна на единица.

В програмното обезпечаване на машините от различни поколения винаги е присъствала функция за генериране на случайни числа с равномерно разпределение.
В програмна среда MATLAB, функция rand генерира равномерно разпределени случайни числа в интервала 0-1 , а randn N(0,1), т.е. с нулево математическо очакване и стандартно отклонение 1. randn(‘state’,J), където J е цяло цисло (например фак. номер на студента), при изпълнение връща случайният генератор в състояние J. Това е полезно тъй като позволява да се генерират едни и същи редици от случайни числа, когато това е необходимо.

Псевдослучайни двоични последователности ( без математически изводи, информативно)
Те представляват периодично повтарящи се реализации с подбрани, неизменни във времето вероятностни характеристики. Отговарят на следните условия:
а) сигналът е на две нива , като преминаването от едно в друго ниво е в дискретни моменти от време , където k е цяло число;
б) сигналът е периодичен с период ;
в) разликата в състоянията +а (броени за елементарното време ) и състоянията –а е единица;
г) в периода Т, състоянията +а и –а образуват серии, кратни на с дължина: са – 1/2; с дължина – 1/4; с дължина -1/8 и т.н. докато се получава число по-голямо от единица;
д) автокорелационната функция има две нива.

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

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

Очевидно е, че между импулсите и ще има малка стойност при големи стойности на N. На практика се използват ПСДП с N не по-малко от 128.
Спектралната плътност на ПСДП се дава с израза

При малки стойности на i< u(t)
+a ∆t
t

-a
T=N. t

a2 Ru( )

- a2/N


Su( )

3 dB

фиг.2.2
Съществуват различни методи за генериране на ПСДП- таблични, аналитични и физични.
Широко се използват генератори на ПСДП, изградени с преместващи регистри, обхванати с обратна връзка, (фиг.2.3) и звено, реализиращо събиране по модул две, съгласно следната таблица:
0+0=0, 0+1=1, 1+0=1 и 1+1 =0.

фиг.2.3

табл.2.1

m
N=2m-1
Полином Изходи за обратна връзка
2 3
1 и 2
3 7
1 и 3
4 15
1 и 4
5 31 u=
2 и 5
6 63 u=
5 и 6
7 127 u=
4 и 7
8 255
2,3,4 и 8
9 211 u=
5 и 9
10 1023 u=
7 и 10
11 2037 u=
9 и 11

Всяка клетка на регистъра е елемент с 2 състояния 0 и 1. Дължината на ПСДП-m се дава с израза
,
където m е броя на клетките в преместващия регистър, фиг.4.12.
С избора на точката за обратна връзка се генерира ПСДП с максимална продължителност ПСДП-m. В таблица (табл.2.1) са дадени брой клетки m и изходите за обратна връзка по модул две.
Пример 2.2. Да се синтезира ПСДП-m с m=4. . По табл.2.1 се избират изходи за обратна връзка по модул 2 –изходи на първа и четвърта клетка. Примерната схема на регистъра е дадена на следната фигура

Синтеза е даден в следната таблица
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1
2 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1
3 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1
4 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0

0 1 0 1 1 0 0 1 0 0 0 1 1 1 1

Като изход може да се вземе изходa на четвърта клетка. Ако за +1 се положи +а, а 0 - за -а се получава следния сигнал

Един алгоритъм, прилагащ метода на Монте Карло с генериране на случайни числа с равномерно разпределение, за изчисляване на кратни интеграли

Идеята на алгоритъма на Монте Карло се състои в това, че се разглежда пространството като n-мерен единичен куб К. Нека R е подмножество на това пространство. По случаен начин се генерират случайни числа, които с еднаква вероятност могат да попадат в К. Ако се генерират N такива точки, то някои от тях (M) ще попаднат в R, а други – не. Отношението M / N се счита за оценка на обема на R. Експериментите показват, че за N = 10 000, се получава точност от около 1%. Такава точност обикновено е достатъчна, дори нейното достигане с други методи може да се окаже доста трудно.

Задача: Да се изчисли кратния интеграл

където , .
Генерират се n поредици от N на брой случайни числа с равномерно разпределение в интервала [a, b]. В изчисленията участват само онези стойности, които са в областта G. Пресмята се стойността на функцията f. Приблизителната стойност на интеграла се дава с формулата

където Mi са точки, принадлежащи на G.

За илюстрация на метода ще бъде се изчислен интеграла
където областта (G) е определена с неравенствата и
и .
Решението при N=6 е дадено в следната таблица.

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

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

Задачи за самостоятелна работа

Задача 1. С помощта на метода на Монте Карло да се намери лицето на кръг с радиус равен на 1.
Аналогично на предната задача в преброяването трябва да участват всички точки, които са в кръга, т.е.

Задача 2. С помощта на метода на Монте Карло да се намери обема на четиримерно тяло, описано със следните неравенства:

Забележка: При фигури извън рамките на единичен хипер куб да се взема предвид умножаването (мащабирането) по всяка координата. Например, ако кубът е с размери 2х2х2, то стойностите за обема на куба и вписаните в него фигури трябва да се умножават с 8.

Приложение

Основни характеристики на непрекъснати случайни величини
f(x) – плътност на вероятност; - функция на разпределение на вероятностите.

1. Математическо очакване (математическа надежда)
;
2. Дисперсия и средноквадратично отклонение

3. Начални моменти и централни моменти

Очевидно и

Основни величини на дискретните случайни величини

1. Математическо очакване (математическа надежда)
; - оценка
2. Дисперсия и средноквадратично отклонение
;
неизместена оценка
3. Начални моменти и централни моменти

Нормален закон за разпределение

Тема 3
Апроксимиране на функции. Основни класове апроксимиращи функции. Метод на най-малките квадрати. Примерни задачи. Лошо обусловени системи. Метод на минимаксната грешка

Задача. В една държава са правени преброявания на нейните жители през 10 години. Резултатите от преброяването са дадени в следната таблица

Данни от преброяване на населението
Година 1930 1940 1950 1960 1970 1980 1990 2000
Млн. жители 4,2 5,3 5,9 7,5 9,1 9,9 10,7 11,4

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

В оригиналния вариант на задачата е дадено населението на САЩ както следва

Данни от преброяване на населението
Година 1900 1910 1920 1930 1940 1950 1960 1970
Жители 75994575 91972266 105710620 123203000 131669275 150697361 179323175 203211926

Необходимо е с помощта на математически модел да се табулират данните (т.е. да се интерполират и екстраполират) за населението от 1900 до 1980 година през една година.
Понятия: интерполация; екстраполация и апроксимация

3.1. Апроксимиране на функции

Анализът на числови данни е обект на числения анализ (раздел от математиката, който се занимава с решаването на математически задачи чрез аритметични процедури. В дадена ситуация обикновено съществуват няколко възможни метода за получаване на търсената апроксимация. Изборът на един от тях зависи от това, какви критерии се използват, за да се прецени колко ефективна е дадената апроксимация. Професията на програмиста не е да реши кой от тези методи трябва да се избере, а да се разгледат съображенията за избор, които предхождат решението. Наличието на различни методи показва, че в едни случаи някои методи са за предпочитане пред останалите. Основните въпроси, на които трябва да се отговори са:
1. Каква грешка можем да допуснем в крайния резултат;
2. За колко време може да се пресметне решението при използване на даден метод.

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

Нека функцията f(x) се апроксимира с помощта на линейната комбинация
(1) ,
където е клас функции (например ), а - константи, се нарича линейна апроксимация на f(x).

Друг широко използван вид апроксимиращи функции са от рационален тип

(2) .

Основната трудност в задачата за апроксимиране на функции е критерият по-който трябва да се избират константите в (1) и (2).

Могат да бъдат предложени четири типа апроксимации от гледна точка на избора на критерии:
1. Точни или интерполационни апроксимации, при които константите се избират така, че точките на измерване (преброяване в горния пример), апроксимиращите функции и първите й ri производни да съвпадат с тези на f(x) (с точност до закръгляне). Този тип апроксимации се разглежда подробно в курса по висша математика. Само ще бъдат изброени видовете интерполационни апроксимации и формулите, по които стават пресмятанията.

Интерполационни полиноми на Лагранж

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

Понятие за крайна разлика от i –ти ред и пример.

Крайни разлики

x ln x Δ Δ2 Δ3 Δ4 Δ5 Δ6

0,3 -1,203973
0,287682
0,4 -0,916291 -0,064538
0,223144 0,023715
0,5 -0,693147 -0,040823 -0,011062
0,182321 0,012653 0,005959
0,6 -0,510826 -0,028170 -0,005103 -0,003534
0,154151 0,007550 0,002425
0,7 -0,356675 -0,020620 -0,002678
0,133531 0,004872
0,8 -0,223144 -0,015748
0,117783
0,9 -0,105361

Формула на Нютон за интерполиране напред с крайни разлики
(3) ,
където , комбинации от m елемента n клас.
Тези формули са развити и модифицирани от Нютон, Гаус, Стирлинг и Бесел и носят техните имена, но в основата им стои (3).

Интерполация чрез сплайн-функции
Кубическите сплайн-функции моделират старо механично устройство. Предлага се между две точки на измерване (възли), да се интерполира с различна кубична функция. Ако сплайн-функцията се представя с функцията s(x) (s(xi)=yi), то идеята на алгоритъма за сплайн-интерполация е минимизация на интеграла . (Механичното значение на този интеграл е минимизиране на потенциалната енергия по дължината на дъгата от квадрата на кривината.)
Кубичната сплайн-функция, удовлетворяваща условията , се нарича естествен кубически сплайн. Както е известно, кубичния полином съдържа 4 коефициента. В n-1 интервала между възлите (точките на измерване) има n-1 фрагмента от кубически криви. Следователно е необходимо определянето на 4n-4 параметъра. Кубичната функция и нейните първа и втора производни съществуват във вътрешните n-2 точки на възлите. Това дава 3(n-2) условия за s. От условието, че в точките на измерване (възлите) s(xi)=yi,,се добавят още n условия. Т.е. общият брой достигна 4n-6. Необходими са още две условия, за да се определят еднозначно всички коефициенти. Те могат да се получат от допускането, че в крайните точки .
На всяка стъпка от итерационния процес трябва да се формира функцията

където коефициентите bi, ci и di се изчисляват с помощта на изразите, които участва параметри, чиито стойности се получават от решаване на система линейни алгебрични уравнения, съставени на базата на споменатите по горе 4n-2 условия. Повече подробности за алгоритъма със сплайн интерполация може да се намерят в книгата на Дж. Форсайт – Computer methods for mathematical computations, в която има представена и програма, реализираща алгоритъма на сплайн интерполацията.

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

Разгледаните методи се отнасят до анализ на данни, зависещи само от една променлива. Често пъти е възможно да се интерполират функции на повече от една променлива. Достатъчно е да се използват няколко интерполации последователно за всяка променлива. Чрез интерполация могат да се пресмятат стойности само в зададения интервал [a, b]. Необходимостта от пресмятане на стойности извън интервала се нарича екстраполация. Екстраполацията по своята същност е един по-неточен в сравнение с интерполацията процес и поради това винаги трябва да се използва с максимална предпазливост. Ако е необходимо използване на екстраполация, то тя трябва да се ограничи възможно най-близко до интервала, обхващащ табличните точки (стойности).

2. Апроксимации по метода на медианите. Целта е да се минимизира интегралът от абсолютните стойности на разликите между f(x) и нейната апроксимация, разпрострян върху интервал [a, b]. При създаване на програмно осигуряване се минимизира тегловната сума от абсолютните на грешките върху дискретно множество от точки, взето от интервала [a, b].

3. Апроксимации по метода на най-малките квадрати. Целта е да се минимизира интегралът на квадрата от разликата между f(x) и нейната апроксимация (евентуално умножен с някаква подходяща тегловна функция), разпрострян върху интервал [a, b]. При създаване на програмно осигуряване се минимизира тегловната сума от квадратите на грешките върху дискретно множество от точки, взето от интервала [a, b].

4. Апроксимации с минимаксна грешка. Целта е да се минимизира максималната големина на разликата между f(x) и нейната апроксимация върху интервала [a, b].

Апроксимации 2, 3 и 4 се формират на базата на минимизиране на нормата на вектора на разликите между f(x) и нейната апроксимация. С понятието норма на вектор се свързва неотрицателно число (скалар), което се използва като мярка за големината на даден вектор. Нормата на вектор се дефинира като
, където параметърът p обикновено приема стойности 1, 2 или ∞.
За p = 1 се получава норма, чиято стойност е сума от абсолютните стойности на координатите на x
.
При p = 2 е прието нормата да се нарича Евклидова норма и представлява дължината на вектора и се дефинира като

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

3.2. Метод на най-малките квадрати

Полиномната апроксимация е метод за апроксимиране на стойността на функция в точка чрез полином, минаващ през дадени стойности (точки). Главният източник на грешки е грешката от прекъсване (стойностите между две точки, в които няма измерване). В следващите примери се разглеждат задачи за апроксимиране на функции, за които са известни само редица от емпирични получени стойности (точки).
Прецизната дефиниция на апроксимации по метода на най-малките квадрати е следната: Нека f(x) е функция, а {xi}, i=1, 2, …, n, е редица от зададени точки, в които са измерени стойностите на f(x), като тези измерени стойности съдържат грешки. Нека с fi се означи точната стойност на f(xi) в точката xi, а с – измерената стойност в същата точка. Дефинира се разликата (грешка, остатък) . Предполага се, че грешките в различните точки са независими.
Нека е редица от функции, дефинирани за всяко xi. Целта е да се апроксимира fi с линейни комбинации на
,
Където коефициентите трябва да се определят така, че да се минимизира

Функцията w(x) се нарича тегловна функция, за която се предполага, че е неотрицателна за всяко xi. Величината Ei се нарича остатък в xi.
След определяне на така, че да се удовлетворява горното условие, се получава апроксимацията (апроксимираща функция)

а самата процедура – апроксимация по метода на най-малките квадрати.
Ако и няма повече зададени точки от параметрите в апроксимиращия полином (т.е. ), то коефициентите ще съвпадат с тези от интерполационния полином на Лагранж. В действителност се разглеждат случаи, в които данните са повече от параметрите на апроксимиращия полином (т.е. ).
Например, ако имаме пет зададени точки, ще се апроксимира с полином от първа степен. Ако полиномът е от четвърта степен, той не може да се използва за т. нар. изглаждане на емпиричните данни. Горните разсъждения са верни и за случаите, когато не се състои само от степени на x. Минимизациите
или
също се използват при анализ на данни.
Ако се интересуваме от абсолютната стойност на грешката, то минимизация по първата от горните формули е за предпочитане. Минимаксната апроксимация има предимството, че ни дава горна граница на грешката за всяка зададена точка. При общи приложения с емпирични данни, обаче, се препоръчва методът на най-малките квадрати, поради факта, че абсолютната стойност не може да се диференцира, а определянето на коефициентите чрез минимаксния метод е по-трудно от останалите два метода.

За пресмятане на се образуват частните производни на Н спрямо и се приравняват на нула (необходими условия за екстремум)
,
Горната система има m+1 уравнения и m+1 неизвестни . Уравненията на тази система се наричат нормални (Гаусови).
За случая, когато и , горната система уравнения приема вида

Ако се въведат означенията

Нормалните уравнения приемат вида

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

Когато стойността на съществено намалява спрямо предходната (m-1), то се изчислява следващата и т.н. докато няма съществено намаляване (примерно няма намаляване с порядък или със зададен %). Щом бъде достигната такава стойност, то тази стойност на m се избира за ред на полинома.

Като мярка за съответствие на апроксимирана функция с реалната, се използва коефициентът на множествена корелация R (мярка за определеност). Той се определя като коефициент на корелация между измерените стойности (y) и изчислените, предсказани по модела с определените коефициенти, или чрез апроксимиращата функция ( )
, където и са съответно средните стойности на и .
Величината се нарича коефициент на детерминация. Стойностите на R са в интервала Колкото по близо е до 1, толкова моделът е по-точен. При R=1 апроксимираща функция преминава през всички експериментални точки.

Илюстрация на метода на най-малките квадрати
За решаването на тази задачата от началото на темата е необходимо да се избере подходящ математически модел, който да даде зависимостта на населението от годината на преброяването. Нека като първо приближение бъде избран линеен модел. Т.е. , където y е населението в млн. жители, x – годината на преброяването, a и b – постоянни коефициенти, които трябва да бъдат определени. Следователно известните величини y и x трябва да послужат за определяне на неизвестните a и b. Броят на точките (годините, в които е имало преброяване) са 8, а неизвестните – 2. Това ще даде възможност за апроксимации с полиноми и от по-висок ред.
На базата на този модел, като се използват данните от таблицата, може да се построи следната система линейни алгебрични уравнения на грешките от апроксимация, когато броят на уравненията (n=8) е по-голям от броя на неизвестните (в случая a и b)

или в матричен вид или

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

От необходимите условия за минимум на Q следва
,
откъдето се получава

това е система нормални (Гаусови) уравнения, записани във векторно-матрична форма. Търсеното решение има вида .
Така решението по МНМК се свежда до създаване на матрица A и вектор b и изпълнение на съответните операции.

Възниква необходимостта от решаване на система линейни уравнения, в която броят на уравненията е по-голям от броя на неизвестните. В съответствие с метода на най-малките квадрати него е необходимо матрицата А да се транспонира и да се умножат отляво дясната и лявата част на системата. В резултат на това действие се получава квадратна система линейни алгебрични уравнения от вида: . Окончателното решение се дава с израза: .
Вследствие на решението на системата уравнения се получават оценките на параметрите a и b съответно 0,1083 и -204,9. Какво е основанието да се гарантира достоверността на получените решения?

За да се даде отговор на въпроса, ще бъдат дефинирани две понятия: норма и обусловеност на матрици.

Норма на матрици

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

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

Обусловеност на матрици

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

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

Да разгледаме системата

, която има решение x=1, y=1 и системата

, която има решение x=10, y=-2.

Тук едно изменение от 0,00002 в коефициента a22 и 0,00001 в b2 предизвиква грубо изменение в решението. Обратната матрица има елементи от порядък 105. За горната система, ако тя е модел на реална система, може да се направи извода, че избраният модел не е адекватен и трябва да се търси друга зависимост, в която участват x и y.
Когато данните са получени емпирично, тогава решението независимо от точността с която се пресмята, може да има груби грешки. Как трябва да се извършат пресмятанията (дали получените резултати са верни?) с точност, която позволяват данните, когато системата е лошо обусловена, е най-трудният проблем, с който може да се сблъска всеки изследовател.

Източници на грешки

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

Голямата стойност на някои от елементите на мащабираната матрица [AT.A]-1 (3677857142,86328) показва лошата обусловеност, а оттам и влошени оценки за оценяваните параметри a и b. Поради тази причина някои автори предлагат да се вземат мерки за подобряване на обусловеността.
За конкретната задача може да се предложи предварително годините на провеждане на преброяванията да не участват в модела, а техните стойности намалени с 1900 например. Тогава най-големият елемент на обратната матрица вече има стойност 11309,5238.
Моделът в този случай добива вида .
Друг вариант за подобряване на обусловеността е да се мащабират годините по формулата . Най-големият елемент на обратната матрица вече има стойност 0,291667 (много добра обусловеност на матрицата), моделът
(Данните са получени с MS Excel. Оценките и в трите модела съвпадат, което демонстрира достойнствата на приложените методи от колективите по математическо осигуряване, които дават добри резултати и при лоша обусловеност).
След получаване на оценките е желателно да се направи проверка за достоверността на получените резултати, която най-добре може да се извърши като се умножи матрицата А с получените стойности на х. След това се пресмята квадратичната грешка като . В таблицата по-долу са дадени резултатите от оценката на параметрите и квадратичната грешка.

Реални данни 4,200 5,300 5,900 7,500 9,100 9,900 10,700 11,400
Оценки 4,208 5,292 6,375 7,458 8,542 9,625 10,708 11,792

Квадратична грешка 0,88

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

Година 1975 1997 2012
Млн. жители 9,08 11,47 13,09

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

, като за данните от задачата той ще изглежда:
или

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

1930 1940 1950 1960 1970 1980 1990 2000
Реални данни 4,200 5,300 5,900 7,500 9,100 9,900 10,700 11,400
Оценки 4,239 5,081 6,217 7,505 8,802 9,965 10,854 11,324

Квадратична грешка 0,5222 Оценки a b c d
-2E-05 0,14 -273,5 2E+05
Година 1975 1997 2012
Млн. жители 9,41 11,24 11,14

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

MS Excel съдържа в себе си удобно средство за решаване на някои задачи от горния тип. Ако се начертае графиката на зависимостта между населението и годините на преброяванията и след това се използва Add Trendline се получава графиката с нейното уравнение от първи ред.

Апроксимации с ортогонални полиноми
Ако е полином от степен j, апроксимацията по най-малки квадрати от степен m може да се запише във вида
.
За да се минимизира

се диференцира по ym и първите производни се анулират

където

При произволен избор на полиномите възникващите изчислителни задачи при решаване на тези нормални уравнения могат да са толкова сериозни, колкото и в предния раздел. Ако, обаче, полиномите се изберат такива, че недиагоналните елементи на матрицата са малки в сравнение с диагоналните елементи, то матрицата D за разлика от G няма да е близка до особена. По-специално, ако полиномите са ортогонални върху множеството от точки , то извън диагоналните елементи ще бъдат без изключение равни на нула. По дефиниция едно множество от полиноми е ортогонално върху множество от точки спрямо тегловната функция w(x), ако

където горният индекс изразява факта, че полиномът ще зависи от броя n на точките. По-нататък се приема, че wi(xi)>0 за всяко i. Ако полиномите са ортогонални, то от горната дефиниция следва системата

която се решава непосредствено

Тъй като , то

За апроксимации през равни интервали е удобно при възможност да се използват нечетен брой точки и се приеме, че нулата е среда на областта на абсцисата, подходящи за апроксимация са полиномите на Грам –Чебишев
N=2L; i=L + s

В таблицата по-долу са дадени формули, по които се изчисляват коефициентите на полиномите на Грам

Тогава апроксимацията на f(s) по най-малките квадрати с първите m полинома на Грам е
, където

За да се изрази апроксимираната функция с x е достатъчно да се направи следната замяна на променливата

Пример:
В таблицата по-долу са дадени данни от измерване на една величина

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

5,1234 5,3057 5,5687 5,9378 6,4370 7,0978 7,9493 9,0253 10,3627

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

От таблицата за изчисляване на коефициентите на полиноми се получават следните резултати (L=4)
За L=4 полиномите на Грам имат вида

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

3,275 0,298 0,0059 0,000012 0,00000012 0,00000015

Стойностите на и не се различават съществено и може да се приеме за ред на полинома m=4.

С полагането може да се получи апроксимиращия полином

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

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

Веднъж изгладените данни могат да бъдат подложени на повторно изглаждане, след което да се апроксимират и т.н. Ако този процес продължи, в крайна сметка ще се стигне до единствена праволинейна апроксимация в цялата област. Поради това изследователят трябва да се довери априорна информация за данните и на своя опит.
Когато е дадено едно множество от точки, не винаги е необходимо само с един полином да се съгласуват тези данни. Възможно е една част от данните да се апроксимират с един полином, а друга част – с друг.
Алгоритъм на пълзящо средно
i=1,2,…,n-L/2; L=2,4,6

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

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

3.3. Метод на минимаксната грешка

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

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

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

МОДЕЛИРАНЕ НА СТАТИКАТА НА МНОГОФАКТОРНИ ОБЕКТИ (СИСТЕМИ)

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

В теорията на експеримента [3] входните променливи се наричат фактори, а пространството определено от тях – факторно пространство. Те образуват входния вектор
, където , ,
могат да се променят (или част от тях) от експериментатора, или само да се контролират. Това е важно, тъй като се свързва с вида на експеримента за натрупване на подходяща информация.
Изходните променливи са целева функция (функция на отклика, параметър за оптимизация). Те могат да бъдат реални изходи на обекта или някакви обобщени технико-икономически показатели (производителност, себестойност, рентабилност и др.), които следва да се оптимизират.
Всяка една от изходните променливи заедно с входните образуват пространството на изхода. Във всеки момент от време в това пространство, състоянието на обекта се дава с изобразяваща точка (върха на вектора), фиг.3.2. Тук n=2.

При изменение на факторите в допустимата област на факторното пространство, изобразяващата точка описва повърхнина. Намирането на тези стойности на факторите, които обезпечават екстремум на целевата функция е задача на оптимизацията на разглеждания обект [2,6,9].
Изходният вектор е . По технологични съображения тук също са валидни ограничения .
v= , отразява смущаващите фактори, които не се поддават на контрол и на практика не могат да бъдат измерени. Мястото на тяхното въздействие, както и природата им обикновено са неизвестни. Те имат случаен характер. Тяхното съвокупно влияние върху изходите се дава като адитивно смущаващо въздействие εi, фиг.3.3. Приема се, че εi е с нормален закон на разпределение, нулева средна стойност и крайна дисперсия, т.е. mε = 0 и σε < ∞, или N(0, ).

Фиг.3

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

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

3.1. ПОНЯТИЕ ЗА РЕГРЕСИЯ И РЕГРЕСИОННИ МОДЕЛИ
Понятието регресия е обобщение на понятието функция. Ако на всяка стойност на една независима промелива x, отговаря друга стойност на y, казва се,че y е функция на x и се записва y=f(x).
Има случаи, когато на една стойност на аргумента xi отговаря множество стойности на yi1, yi2, … yin, следствие на което се получава т.н. поле на корелацията [7,42], при изменение на , фиг. 3. 4.

За всяка стойност на xi, може да се намери оценка на математическото очакване , (средната стойност). Начупената линия, която съединява средните стойности е експерименталната (емпирична ) регресионна зависимост. Ако броя на точките в даден интервал расте неограничено, и , експерименталната крива ще се доближава до теоретичната крива на регресия, а нейният аналитичен вид – регресионен модел.
Като се използват условните вероятности същият може да се запише като
(3.1.1)
Произволна стойност на целевата функция може да се запише по следният начин , . (3.1.2)

3.2. РЕГРЕСИОНЕН АНАЛИЗ
Нека реакцията y се разглежда като случайна величина, флуктуираща около , т.е. , където е шума. Това може да бъде естествена флуктуация, свързана с работата на обекта, или грешка в измерването на . Тук е истинската реакция, а y е наблюдаваната.
Предполага се, че има вида
, (3.2.1)
където са известни величини в процеса на експеримента, които се измерват с пренебрежимо малка грешка, а са неизвестни параметри, подлежащи на оценяване.
Удобно е резултатите от имерванията да се дадат в таблица от вида табл.3.1

Табл.3.1
№ x1 x2 …. xj … xn y
1 x11 x12 … x1j … x1n y1
2 x21 x22 … x2j … x2n y2
.. … … … … … … …
i xi1 xi2 … xij … xin yi
.. … … … … … … …
N xN1 xN2 … xNj … xNn yN

Ще бъде приет следният линеен по коефициенти математичен модел
, (3.2.2)
Записано във векторно-матрична форма (3.2.2) има вида
(3.2.3)
където:
; ;
;
(3.2.4)

X е с размерност Nx(n+1) и се нарича регресионна матрица [45]. се избират така щото стълбовете да са линейно независими, т.е. ранга на матрица X да бъде (n+1).
Моделът (3.2.2) се явява достатъчно общ. Ако се положи , се получава следният полиномен модел
(3.2.5)
Моделът
(3.2.6)
също е частен случай на (3.2.2). Същесъвеното тук е, че тези модели са линейни по коефициенти. По тази причина те се наричат линейни.
За разлика от тях моделът
(3.2.7)
е нелинеен, тъй като е нелинеен по коефициента .
Функциите (променливите) се наричат регресори (предикторни променливи), а y - отклик (реакция).

Може да се забележи, че матрица X при модели (3.2.2), (3.2.5) и (3.2.6) ще има различен вид. Първият стълб . Останалите стълбове се определят като стойности на регресорите при съответните наблюдения i=1,2,..,N. При моделирането могат да се използват както естествени, така и стандартизирани или кодирани променливи. Това обаче следва да се има предвид при анализа и използването на полученият модел.

Условията за прилагане на регресионният анализ са:
1) могат да имат произволно разпределение, но за фиксирани техни стойности са незвисими с нормално разпределение и еднакви дисперсии . Тъй като и е неслучайна величина, то y и имат еднакви разпределения.
2) Факторите се измерват точно (с пренебрежимо малка грешка);
3) Шумът има нулево математическо очакване , не е корелиран и с еднаква дисперсия .

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

Намирането на математичният модел на обект с прилагане на регресионния анализ включва два етапа:
1) оценяване на коефициентите по метода на най-малките квадрати;
2) статистически анализ на резултатите.

Коефициентите са истинските, които не могат да бъдат намерени, тъй като не може да бъде измерена истинската стойност . Вместо се определят оценките . Ако в (3.2.8) се заместят , се получава предсказана по модела стойност , т.е.
(3.2.9)
Разликите
, (3.2.10)
се наричат остатъци.

3.2.1 ОЦЕНЯВАНЕ НА КОЕФИЦИЕНТИТЕ ПО МЕТОДА НА НАЙ-МАЛКИТЕ КВАДРАТИ
Като се отчете факта, че y и трябва да са близки за всички стойности от табл 3.1, може да се запише следната сума от квадрати
(3.2.11)
Оценките ще бъдат намерени от условията , откъдето следва

…………………………………………………………..
(3.2.12)
След преобразуване (3.2.12) може да се запише във вида

………………………………………………………………………

(3.2.13)

Тази система се нарича система нормални (Гаусови) уравнения. Тя е с размерност (k+1)х(k+1), от решението на която се получават търсените коефициенти .

За практическо приложение на метода на регресионния анализ е по-удобно да се използва матрично-векторна форма на запис. За целта се въвеждат следните матрици [7].
а) Матрица на плана на експеримента X
.
X= ;
Елементите на тази матрица са тези от табл.3.1 и съответстват на стойностите на факторите, които се записват по време на експеримента, при пасивен експеримент. При активен експеримент това са планирани стойности, които се задават от експериментатора (план на експеримента).

б) Матрица на регресорите (разширена матрица на плана, при активен експеримент)

F= ;

Може да се забележи,че , някой от елементите на тази матрица съвпадат с факторите , а друга част са известни техни функции. Елементите на F са известни. Тази матрица съдържа N реда, колкото са наблюденията и (k+1) стълба, колкото са коефициентите в модела.

в) Вектор на реакциите (отклиците)
y= .
г) Вектор на коефициентите
b= .
д) Вектор на остатъците
e= .

Като се отчете (3.2.9), (3.2.10) може да се запише по следния начин
(3.2.14)
Ще бъде минимизирана нормата
като се запише градиента
,
откъдето следва векторно-матричният запис на Гаусовите уравнения
(3.2.15)
и решението
(3.2.16)
Ако се предположи, че F има ранг (k+1), то е положително определена и не е изродена. се нарича още информационна матрица, а нейната обратна - ковариационна матрица.

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

Минималната стойност на се нарича остатъчна сума от квадрати и може да се определи
(3.2.18)

При обработване на резултати от пасивен експеримент, с цел намаляване на корелацията между стълбовете на F е удобно да се използват стандартизирани фактори и функции. Доказано е, че дори корелационата връзка между факторите xi да е слаба, при образуване на функции, например xi2, които се разглеждат условно като нови регресори възниква силна връзка между тях. Например, коефициента на корелация между fi =xi и fj =xi2 се дава със следния вид [1]
, (3.2.19)
където кофициента на вариация .
Може да се види, че r ще има малка стойност когато е голямо, т.е. при замяна на фактора (функцията) със стандартизираната такава, чиято стойност е с .
Прилагането на стандартизирани фактори и функции е по уравненията
, , , (3.2.20)
където с са означени оценките на математическото очакване, а с S средноквадратичните отклонения, определени като оценки по съответните стълбове от разширената матрица на плана.

Данните могат да се запишат в таблица, подобна на табл.3.1.
С прилагане на регресионният анализ се оценява вече нов модел
. (3.2.21)
Изследователят обаче се интересува от модел с коефициенти . За целта се използват следните изрази
,
. (3.2.22)

3.2.2 СВОЙСТВА НА ОЦЕНКИТЕ ПО МЕТОДА НА НАЙ-МАЛКИТЕ КВАДРАТИ
Тъй като са случайни, то съгласно (3.2.16) оценките също са случайни величини. При разглеждане на техните качества следва да се отчитат направените предположения за прилагане на регресионния анализ. В [6] са дадени доказателствата на свойствата им.
А) Оценките по МНМК са неизместени, т.е. .
Ако се приеме, че M{e}=0 и , то
M{b} M{y}= , (3.2.23)
т.е. b е неизместена оценка на . Това показва, че методът не въвежда систематична грешка.
Б) Оценките по МНМК са състоятелни. При неограничено нарастване на наблюденията b се схожда по вероятност към истинската стойност , т.е.
, е малко положително число.
В) В класа на линейните неизместени оценки , оценките по МНМК са ефективни (с минимални дисперсии), т.е.

Ако се приеме, че са некорелирани и имат еднаква дисперсия, т.е. , то (I единична матрица) и
(3.2.24)
(3.2.25)

3.2.3. СТАТИСТИЧЕСКИ АНАЛИЗ НА МОДЕЛА
Вторият етап от приложението на регресионният анализ включва проверка на качествата на модела, неговата адекватност. За тази проверка се използва остатъчната сума от квадрати
(3.2.26)
Очевидно е, че колкото е по-малка, толкова предсказаните стойности на реакцията са по-близки до експерименталните. Разликата между тях може да се дължи на следните причини:
а) неправилно подбрана структура на модела;
б) значително влияние на случайната грешка.

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

Дисперсията на грешката се определя по l броя допълнителни опити, l=5-10, при един и същи технологичен режим.
Ще бъде прието

От таблици с F-разпределение (приложение) се избира критична стойност по ниво на значимост и степени на свобода , и и се прави извод:
- ако F , моделът е адекватен;
- при - моделът е неадекватен.

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

В случаите когато не могат да се проведат допълнителни опити за определяне на , например при провеждане на пасивен експеримент, за оценка работоспособността на модела се използва коефициента на множествена корелация R. Определя се обща сума от квадрати
, (3.2.28)
където (3.2.29)
и степени на свобода .
Определя се коефициента на множествена корелация
(3.2.30)
Желателно е R да бъде близко до единица, при значителен брой степени на свобода . При доближаване на N и (k+1), R изкуствено се завишава. Сигурността на изводите е по-голяма колкото е по-голямо .
Необходимо е да се оцени значимостта на коефициента на множествена корелация R. За целта се пресмята
. (3.2.31)
Задава с ниво на значимост и от таблици с F-разпределение се определя , =k, =N-(k+1). Прави се извод:
- ако F> , то R се приема за значимо и моделът може да се използва;
- ако F< , то R се приема за незначим и структурата на модела следва да се промени.

3.2.4 АНАЛИЗ НА ОСТАТЪЦИТЕ
Остатъците се дефинират с израза ei = , i=1,N, или
, (3.2.32)
където ={hij}.
При адекватен модел остатъците трябва да съответстват на шума  и следователно да удовлетворяват направените вече предположения на регресионния анализ.
Използването на изчислителна техника ни дава възможност за графичен анализ на ei. Смисълът на разглеждане на графичните зависимости на остатъците се състои в това, че всяко нарушаване на направените предположения за  се отразява върху ei. За целта те трябва да се представят в подходящ мащаб, при който дисперсията им ще бъде приблизително единица. Това може да се постигне чрез мащабиране на същите по израза
= , (3.2.33)
или като се използват стютентизирани остатъци
di= (3.2.34)
Пресмятането им може да се опрости ако се използват приблизителни изрази
= , или . (3.2.35)

Построяване на зависимостта di от

От нея могат да се видят:
а) Наличие на груби грешки (фиг.3.5.а). Например ако N>20 и съществува di=dmax>3,съгласно правилото за 3, то това наблюдение с голяма вероятност (99.7%) е груба грешка. В този случай трябва да се подхожда внимателно, тъй като това може да се дължи и на самия обект.
б) Прогресиращо изменение на дисперсията на смущението- ако нормираните остатъци наподобяват (фиг.3.5.б).
в) Неправилно зададена структура на модела, неадекватност. От вида на фиг.3.5.в може да се направи извода, че са пропуснати квадратични членове.
г) Удовлетворителен вид на графиката на стюдентизираните остатъци е даден на фиг.3.5.г.

di * d i * * *
* * * * * *
0 * * * * * 0 * *
* * * * * * * *
* * *
* * *
(a) (б)

di di

* * * * * * *
* * * * * * * * *
0 * * * * 0 * * * *
* * * * * *

(в) (г)

фиг.3.5

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

На практика всички фактори влияещи на y следва да се включат в регресионният модел в качеството си на регресори. Ако някои от тях бъдат пропуснати, то това може да се прояви върху графиката на остатъците, от този фактор. Такава графика може да се построи ако са известни стойностите на фактора.
Например, графиката на di от времето (често се дава като di от i) може да даде информация за наличието на корелация във времето на i.
На фиг.3.6 са дадени зависимости при, които има положителна (а), отрицателна (б) корелация, линеен (в) или криволинеен (г) тренд.

di di
* * * *
* * * * * *
0 * * 0
* * * * * *
* * * *
t t
(а) (б)

di * di
* * * *
* * * * * *
0 * * 0 * * * *
* * * * * *
* * * *
t t

(в) (г)
фиг.3.6

Пример 3.1. За статичен обект са симулирани 50 наблюдения на входовете x1, x2 и x3 и 1 изход. Да се определят коефициентите на модела и се извърши статистически анализ на същия. S2 =0.7955. Пресмятанията да се извършат с MATLAB.

» for i=1:50
x1(i)=randn(50,1);
x2(i)=randn(50,1);
x3(i)=randn(50,1);
x0(i)=1;end
x23=x2.*x3;
» load bzad;
Fzad1=[x0 x1 x2 x3 x23 ]; % матрица F
» yzad=Fzad1*bzad’;
» y=yzad+randn(50,1); % изход y
» Rzad1=Fzad1′*Fzad1;
» cond(Rzad1)
ans =
3.5405
» Gzad1=inv(Rzad1);
» b1=Gzad1*Fzad1′*y
b1 =
0.7041
2.0882
3.0801
3.9194
4.9176
» y1=Fzad1*b1;
» e1=y-y1;
» Skost1=e1′*e1/45
Skost1 =
1.0570
» Sost1=sqrt(Skost1)
Sost1 =
1.0281
» FF=Skost1/Skeps
FF =
1.3288< Ftab=6.17 % адекватен модел
» d1=e1/Sost1;
» plot(y1,d1,'*')grid

Зависимост

» Fzad2=[x0' x1 x2 x3]; % матрица F
» Rzad2=Fzad2'*Fzad2;
» cond(Rzad2)
ans =
2.1813
» Gzad2=inv(Rzad2);
» b2=Gzad2*Fzad2'*y
b2 =
1.3410
0.8864
4.0913
1.6492
» y2=Fzad2*b2;
» e2=y-y2;
» Skost2=e2'*e2/46
Skost2 =
28.6754
» Sost2=sqrt(Skost2)
Sost2 =
5.3549
» d2=e2/Sost2;
» plot(y2,d2,'*');grid
» FF=Skost2/Skeps
FF =
36.0486>6.17 % неадекватен модел
»

Зависимост

Тема 4
Математическо програмиране. Линейно програмиране. Транспортна задача. Симплекс метод. Програмно осигуряване. Съставяне на начални решения. Задачи за оптимизация на транспортни разходи и материални запаси.

4.1. Математическо програмиране

Областта от математиката, в която се разработва теорията и числените методи за решаване на екстремални задачи с ограничения, се нарича математическо програмиране. За разлика от класическата теория на екстремалните задачи основно внимание при математическото програмиране се отделя на задачите, свързани с ограничения в областта на изменение на променливите им.
Независимо от разнообразието и съдържанието на задачите за планиране и управление, от математическа гледна точка могат да се обобщят и дефинират по следния начин: да се определят стойностите на променливите, които удовлетворяват определена система уравнения или неравенства и при които дадена функция достига екстремум. Следователно този клас задачи съответстват на задачите на математическото програмиране.
Промишленото производство, потокът на ресурсите в икономиката, управлението на сложни технологични процеси и обекти – всичко това са комплекси на многобройни взаимно свързани процеси. Различията могат да имат място само по отношение на целите, които би трябвало да се постигнат в същността на разглежданите процеси и в обема на необходимите усилия. При управлението на различни явления (системи) е възможно да се изтъкнат съществени черти на сходство. Затова е необходимо да се изясни структурата и състоянието на системата, а също така и целта, която трябва да бъде постигната. Това е нужно, за да се предвиждат действията, които е необходимо да се изпълнят, тяхното разпределяне във времето и техните количествени характеристики, което позволява системата да премине от определено състояние към определена цел.
Ако в изследваната система се установи структура, която може да бъде описана математически (намира се математическия модел) и целта също може да се изрази количествено, то в този случай се използва един или друг изчислителен метод за избиране от всички алтернативи на най-добрия план за действие. Такова използване на математически модели се нарича математическо програмиране. Констатацията, че много икономически и производствени задачи могат да бъдат математически описани (макар и приблизително) с помощта на системи линейни неравенства и уравнения, съдейства за интензивното развитие на линейното програмиране.
Оценката на качеството за функциониране на една система може да бъде изразена чрез различни показатели за качество (целева функция). Ако системата е за автоматично регулиране, подходяща оценка е например бързодействието й. Функционирането на едно съоръжение може да се оценява по неговата производителност, разход на материали и енергия и др. Показател за качеството на работа на една фирма може да бъде печалбата от производството и продажбата на един вид продукция, средната заплата на едно лице от персонала, разходите на материали и енергия и работно време за производството на единица продукция и др.
От направените примери се вижда, че в повечето случаи качеството на функциониране на една система може да се характеризира само с едно число, чиято стойност зависи от параметрите на системата
Q = Q(x),
където x в общия случай е N-мерна величина.

Най-често срещаният случай е този, при който най-изгодният (оптимален) режим се получава при екстремна стойност на показателя за качеството Q. Така например желателно е параметрите да бъдат избрани по такъв начин, че да се получи максимална печалба или минимални разходи на материали и енергия.
Следователно може да се каже, че съществуват голям брой практически задачи, за които е необходимо стопанският ръководител на базата на научно издържани методи да вземе едно или друго управленско решение.
Една от първите и най-важни задачи, която трябва да се реши преди вземането на оптимално решение, е създаването на математически модел на обекта (проблема) и избор на алгоритъм за получаване на резултатите.
Нека допуснем, че е съставен математически модел, в който е направен балансът за разходите на суровините, материалите и работните заплати. В повечето икономически задачи моделът представлява линейна система алгебрични уравнения от вида
или в матрична форма: A.x = B

Обикновено задачата, представена като математически модел от горния вид, не съответства напълно на реалната икономическа задача. Например, ако x1 е изразходваното количество енергия е очевидно, че тази величина трябва да е по-голяма или равна на нула. Следователно, ако при решаването на горната задача се получават отрицателни стойности за x1, може да се направи извода, че използваният модел не е добър (не е адекватен на реалния) и трябва да се направят корекции в него.
Критерият за качество се обособява като функционал, а ограниченията се представят като система от равенства и/или неравенства.
ВАЖНО!! При линейното програмиране показателя на качеството (целевата функция) Q(x) и ограниченията са линейни функции.
Следващите три примера са типични задачи на програмирането и се поддават на линейна формулировка.
В системите, разглеждани във всеки от трите примера, целта е минимизация на пълните разходи, изразени в парични единици. Но в други задачи целта може да е максимизиране на печалба, брой на произвеждани изделия и т.н.
Пример 1. Да предположим, че във Варна, Пловдив и Русе има три консервни завода. Тези заводи произвеждат дневно съответно по 250, 350 и 400 хил. кутии консерви. За реализация (пласиране) на продукцията в страната има пет склада за търговия на едро: в Бургас, София, Видин, В. Търново и Шумен. Всеки склад може да продаде по 200 хил. кутии дневно. Специалистът, зает с разпределението на продукцията, иска да определи броя на кутии, които трябва да се доставят от трите консервни завода на петте пласментни склада така, че всеки склад да може да получи толкова кутии, колкото може да продаде ежедневно, а пълните транспортни разходи да са минимални.
В задачата има всичко 15 възможни процеса (курса) за доставката на кутиите от всеки завод до всеки склад. Самите те имат 15 неизвестни стойности, изразяващи количеството товари, които трябва да бъдат извозени по тези 15 пътища. Такова разпределение на превоза обикновено се нарича програма. Налице са редица ограничения, които един допустим план на превози трябва да удовлетвори, а именно: съгласно плана всеки склад на едро да получи необходимото количество кутии и всеки завод да изпраща не повече кутии, отколкото той може да произведе дневно. Задачата се състои в определяне на такъв план за превоз, наречен оптимален, който е свързан с най-малко транспортни разходи.

Пример 2. (Задача на домакинята). Семейство от 5 члена живее със скромната заплата на главата на семейството. Постоянна задача е определяне на ежеседмичното меню след съответно разглеждане на потребностите, вкусовете на семейството и цената на продуктите. Мъжът трябва да получава дневно по 3000 калории, жената – 1500 (с диета за отслабване), а децата се нуждаят съответно от 3000, 2700 и 2500 калории дневно. Съгласно предписанието на домашния лекар тези калории трябва да бъдат получавани от всеки член на семейството в резултат на консумирането на ограничено отгоре количество мазнини и ограничено отдолу количество въглехидрати и белтъчини. В посочената диета имат голямо значение белтъчините. Освен това всеки член на семейството трябва да задоволи своите потребности и от витамини. Задачата се свежда до това, като се изхожда от цените на продуктите, да се състави седмично меню, минимизиращо издръжката.

Тази задача е типична задача на линейното програмиране: допустимите процеси се състоят в закупуването на различните видове продукти; ограниченията в задачата са потребностите на членовете на семейството от калории и витамини, а също и предписанието на лекаря за горната и долната граница количествата мазнини, белтъчини и въглехидрати, които могат да се консумират от всеки член на семейството. Броят на комбинациите за хранене, удовлетворяващи тези ограничения, е голям. Обаче някой от тези допустими планове са свързани с по-високи разходи, отколкото други. Задачата се състои в намирането на комбинация, която има минимална пълна стойност.
Пример 3. (Обучение в процеса на работа).
Промишлено предприятие сключва договор за произвеждане на определена продукция. Предприятието разполага с по-малко количество работна сила, отколкото е необходимо за произвеждане на определената продукция в размерите, предвидени от изработения план за няколко седмици напред. Във връзка с това е необходимо да се наемат допълнително работници, да ги обучат и използват в работата. Наличната в предприятието работна сила може да бъде използвана или за произвеждането на определения обем продукция, или за обучение на определен брой нови работници за новите работни места, или за изпълнение едновременно на тези два вида работа при условие на дадено съотношение между изработеното от един работник и броя на обучените от тях нови работници. Дори при назначаване на цялата бригада да обучава новите работници в продължение на цяла седмица, тя не би била в състояние да обучи нужния брой. През следващата седмица тази бригада заедно с новите работници може или да работи, или да обучава отново приетите работници, или едновременно да работи, обучава и т.н. Ако продукцията е бързо разваляща се, то при съхраняване на по-рано произведена следва да се понесат определени разходи. Задачата се свежда до съставянето на програма за наемане на работна ръка, произвеждане и съхраняване на продукцията, която осигурява минимални пълни разходи.
Това също е задача на линейното програмиране, макар да се различава от приведените по-горе два примера. Тази задача може да се нарече планиране на работата по време. Процесите в тази задача се свеждат до използване на наличните квалифицирани работници в две насоки: за произвеждане на продукция или за обучение на нови работници, а също и за приемане на нови работници всяка седмица. Интензивността на тези процеси е ограничена от броя на работниците, които са налице в началото на всяка седмица, и отношението между броя на инструкторите и броя на обучаваните. Общата продукция, произведена от всички работници през договорения срок, трябва да бъде не по-малка от искания обем.
Сега задачата може да се формулира още по-точно: да се определи съотношението между броя на наетите и обучаващите се работници, между броя на инструкторите и броя на работниците, заети в производството, между размера на свръх- и непроизведената продукция, за да се минимизират пълните разходи.

4.2. Определение на линейното програмиране

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

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

Да предположим , че изучаваната ситема представлява сама по себе си комплекс от машини, хора, спомагателно оборудване и суровини. За съществуването на тази система има една или друга причина: тя трябва да произвежда определени видове продукти в промишлеността. Основаният на линейното програмиране подход се състои в това, че разглежда системата във вид съвкупности от няколко елементарни функции, наречени технологични процеси. Те са своего рода «черна кутия», на входа на която се подават материалните ресурси (хора, оборудване, суровини), а на изхода се получават продуктите на промишленото производство. Какво става с ресурсите вътре в «черната кутия» – е работа на инженера, технолога и проектанта. Що се отнася до лицето, което формулира задачата, в този технологичен процес него го интересуват само размерът на разходите и продукцията. Различните видове разходи и произведеното се наричат инградиенти.
Количественият показател, използван при всеки технологичен процес, се нарича негова интензивност. За да се измени интензивността на технологичния процес, необходимо е да се изменят неговите разходи и продукция.

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

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

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

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

4.4. Етапи при построяване на математическите модели

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

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

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

Стъпка 3. Да се определят коефициентите на “разход-продукция”. Да се определи количеството на всеки неизвестно, използвано или произведено при използване на всеки технологичен процес в условията на неговата единична интензивност. Тези коефициенти представляват коефициенти на пропорционалност, която свързва интензивността на производствените технологии и потока на неизвестните.

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

Стъпка 5. Да се състави уравнение на материалния баланс. На всички технологични процеси се въвеждат неотрицателни неизвестни ( ), след което за всеки процес се написва уравнение на материалния баланс, което потвърждава, че алгебричната сума на разходите за този процес във всеки технологичен процес (изразени под формата на резултат от неговата интензивност на съответния коефициент “разход-продукция”) е равна на екзогенния поток на тази величина.
В резултат на построения модел се получават съвкупност от математически съотношения, които описват всички допустими планове на системата. Тази съвкупност е моделът на линейното програмиране.
След построяване на модела, задачата на линейното програмиране може да бъде формулирана в математически термини. Решението на тази задача може да се интерпретира като план за системата – разписание на времето и обема на работа, които трябва да бъдат изпълнени от намиращата се дадено начално състояние система за осъществяване на съответния план.
В хода на построяване на математическия модел на системата не винаги се достига от първи път от първата до последната стъпка. Често се случва на някои технологични процеси, обикновено свързани с управлението за използване на ресурси или преизпълнение на изискванията, да не се обръща внимание до момента, докато уравнението на материалния баланс не наложи тяхното включване. Т.е. връщането от стъпка 5 към стъпка 1 понякога е необходимо, преди да бъде завършено построяването на модела.

4.5. Привеждане на моделите в каноничен вид

Всяка задача на линейното програмиране може да бъде приведена към каноничен модел, където се минимизира (максимизира) целева функция с линейни ограничения от тип равенства. Тъй като броя на променливите n в задачите на линейното програмиране е по-голям от броя на ограниченията m (n > m), то за получаване на начално решение (n-m) на брой променливи могат да се приравнят на 0 (свободни променливи). Останалите m на брой променливи се наричат базисни и лесно могат да бъдат определени от системата ограничения от тип равенства. Ако решението съществува, то се нарича базисно. Геометричната интерпретация на допустимите решения съответства на върховете на изпъкнал многоъгълник, получен от ограниченията (виж фигурата в примера, стр.20).
Това означава, че при търсене на оптимално решение на задачите на линейното програмиране е достатъчно да се изчисли целевата функция за всеки от върховете и да се избере онзи връх, за който стойността на целевата функция е оптимална (т.е. да се претърсят всички базисни решения) . Тъй като свободните променливи могат да се избират произволно, то броят на вариантите е

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

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

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

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

Пример 2

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

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

където М е с няколко порядъка по-голямо от коефициентите пред x1 и x2. Например M = 1 000 000. Началното базисно решение е:
x1=0, x2=0, x3=0, x4=0, x5=2, x6=6 .
При правилна оптимизационна процедура стойностите на x5 и x6 ще се нулират при получаване на крайното решение.
Ако се търси минимум на целевата функция, тогава новите членовете в целевата функция трябва да се добавят.

Пример 3: В една фирма се произвеждат два вида изделия A и B. Ресурсите за една смяна са:

Ресурси за една смяна Количество Мерна единица
Производствено оборудване 650 Машиночас
Суровини 300 Тон
Ел. енергия 900 Киловатчас
Трудови ресурси 540 Човекочас

Разходите от различните ресурси в съответните мерни единици за едно изделие от всеки вид са следните:
Ресурси Изделие
А B
Производствено оборудване 4 2
Суровини 1 1
Ел. енергия 3 5
Трудови ресурси 2 3

Колко изделия от всеки вид трябва да се произведат, за да се получи максимална печалба, ако се знае, че печалбата от едно изделие от вид А е 5 лв., а от вид B е 4 лв.?
Решение:
За решението на задачата е необходимо да се построи целевата функция. Нека с x1 бъдат означени броят на изделията от вид А, а с x2 – от вид B. Тогава целевата функция трябва да се изчислява по формулата
Z = 5x1 + 4x2
Ограниченията, които трябва да се удовлетворяват при максимизирането на целевата функция са следните:

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

Горната система представлява каноничния вид на задачата за решаване със симплекс метод. Началното решение е от вида:
Пример 4: Във фирма за производство на електроника се произвеждат два вида изделия, печалбата от които е съответно 9000 и 10000 лв. За монтажа на един елемент от първия вид са необходими 10 човекочаса, а за монтажа на един елемент от втория вид – 15 човекочаса. За едно денонощие във фирмата са осигурени 200 човекочаса. Лимитиращи са количествата и на два вида кристали (А и B), които влизат в електронните изделия, съответно 90 броя кристали от вид А и 180 броя кристали от вид B. Разходът на кристали за производството на електронните изделия са дадени в следната таблица

Кристали Електронно изделие
Първи вид Втори вид
Вид А 15 10
Вид B - 20

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

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

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

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

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

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

В примера за консервните заводи ние искаме планът за превоз на кутиите да минимизира общата стойност на превоза от заводите до складовете. Нека опростим тази задача като предположим, че имаме два завода – завод I и завод II, и три склада, означени с А, В и С. Наличните кутии с консерви от заводите и тяхната потребност в складовете е следната

Налични кутии Потребност от кутии
В завод I 350 В склад А 300
В завод II 650 В склад В 300
В склад С 300
Общо наличност 1000 Общо потребност 900

Произведените в повече 100 кутии не трябва да се превозват, а да останат на място. Стойността на превоза на всяка кутия от който и да е завод до всеки склад е дадена в следната таблица:

Консервни заводи Складове
Склад А Склад В Склад С
Завод I 2,5 1,7 1,8
Завод II 2,5 1,8 1,4
Задачата се състои в това да се определи броят на кутиите, които трябва да се пренесат от всеки завод до всеки склад, като се минимизират общите транспортни разходи.
За да построим модел, който да описва взаимоотношенията между наличните кутии в заводите и потребностите на складовете, ще започнем от анализа на елементарните функции, а именно от технологичния процес, който се състои в превоза от един завод до друг склад. Превозът на една кутия от завод I до склад А като разходи той се нуждае от две величини: една кутия и 2,5 лв. разходи. Като продукция той се нуждае от една величина: една кутия в склад А. Основното предположение се състои в това, че x кутии, които трябва да бъдат транспортирани от завод I до склад А, се нуждаят от разходи на x кутии и 2,5x лв., а като продукция ще бъдат произведени x кутии в завод А.
По какъв начин се осъществява пренасянето и какво става с кутията между пунктовете на изпращане и получаване не е задача на програмирането. В този смисъл технологичният процес наистина се оказва “черна кутия”, в която някои величини постъпват, а други излизат.
Примерът с консервните заводи съдържа шест технологични процеса, които представляват шест възможни способа за превоз на кутиите от двата завода до трите склада. Може също така да се съхранява продукцията на заводите, което да доведе към друг вид възможна елементарна функция на технологичния процес, състояща се в начина на съхраняване. Съхраняването изисква величина и стойност в някой моменти t и получаването на тази величина в някой по-късен момент t+1.

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

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

Списък на технологичните процеси

1. Превоз от I до А. 5. Превоз от II до В
2. Превоз от I до В. 6. Превоз от II до С.
3. Превоз от I до С. 7. Съхраняване на излишъците в I.
4. Превоз от II до А. 8. Съхраняване на излишъците в II.
Като единица за измерване на обема на превоза или съхраняването може да се избере една кутия. За всеки технологичен процес би могло да се избере различна единица. Например превозът може да се измерва в лв. за една кутия, а съхраняването в лв. за 1000 кутии.
Стъпка 2. Може да се счита, че освен стойностите има още една величина, а именно кутията. Обаче икономистите посочват, че аналогични величини в различните места или в различни моменти от време са в същност различни величини. В разглеждания пример ние игнорираме измененията по време и се съсредоточаваме само върху прехвърлянето от едни места на други. Съгласно това ще се получи списък от шест величини, които отразяват два завода, три склада и величина на стойността (парите).
Списък на величините

1. Кутия в завод I. 4. Кутия в склад В.
2. Кутия в завод II. 5. Кутия в склад С.
3. Кутия в склад А. 6. Стойност (лв.)

Стъпка 3. При изписването на коефициентите за “разход-продукция” в модела ще се използват следните споразумения за алгебричните знаци на коефициента: “разходи” ще се считат за положителни, а “продукция” – за отрицателни. Символично:

Или в табличен вид за всяка величина и технологичен процес:
Величини Технологични процеси
1 2 3 4 5 6 7 8
I→A I→В I→С II→A II→В II→С Съхраняване в I Съхраняване в II
1. Кутия в завод I +1 +1 +1 +1
2. Кутия в завод II +1 +1 +1 +1
3. Кутия в склад А -1 -1
4. Кутия в склад В -1 -1
5. Кутия в склад С -1 -1
6. Стойност (лв.) +2,5 +1,7 +1,8 +2,5 +1,8 +1,4

Стъпка 4. Екзогенните (външните) потоци, които постъпват в системата и се нуждаят от системата като цяло, са показани по-долу във вид на “черна кутия”

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

Величини Екзогенни потоци
1. Кутии в I 350 Разходи, постъпващи в системата
2. Кутии в II 650
3. Кутии в А -300
Продукция, нужна на системата
4. Кутии в В -300
5. Кутии в С -300
6. Стойност (лв.) Z Минимални разходи, постъпващи в системата

Стъпка 5. Да съпоставим всеки технологичен процес (от 1 до 8) с неизвестната и подлежаща на определяне величина, която представлява интензивност на този технологичен процес. Обикновено неизвестните на к я технологичен процес се означават с xk. Като се използва таблицата на коефициентите, получена в стъпка 3, се записват уравненията на материалния баланс за всяка величина.

За величината 1 (кутия в I) технологичните процеси за потребление са 1, 2, 3 и 7 (превози и съхраняване). Коефициентите “разход-продукция”, свързани с процес 1, са равни на +1. Чистият поток на процес 1 точно е равен на

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

Аналогично се съставят и останалите уравнения на материалния баланс.

Моделът във форма на уравнения ще бъде от вида:

• Условия за неотрицателност:

• Уравнения на материалния баланс:

Моделът се състои от следните части:

 списък на технологичните процеси на системата и техните неизвестни величини;
 списък на величините на системата. Коефициентите на “разход-продукция” от системата са разположени в колонки по технологичните процеси и по редове за величините;
 екзогенни потоци в системата.

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

4.7. Привеждане на модели от задачи за разпределение в каноничен вид. Примери.

Пример 1. Фирма от хранително-вкусовата промишленост има два склада за брашно и три цеха за хляб и хлебни изделия. Наличностите от брашно в складовете са : в първия склад – 40 тона, във втория склад – 60 тона. Дневните потребности на всеки цех са: първи цех – 40 тона, втори цех – 30 тона, трети цех – 50 тона. Разходите в лв. за превозване на един тон брашно от всеки склад до всеки цех са дадени в следната таблица:
Цех 1 Цех 2 Цех 3
Склад 1 20 40 50
Склад 2 30 50 80

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

В първия вариант някои от уравненията на материалния баланс ще бъдат от тип неравенства. Нека въведем променливите xi,j – количествата брашно транспортирано от i-я склад към j-я цех, където първият индекс показва номера на склада, а втория – номера на цеха. Общият брой на тези променливи е шест.

Условия за неотрицателност:

Уравнения на материалния баланс:

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

Тогава системата от ограничения добива вида:

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

Началното решение е от вида:

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

Цех 1 Цех 2 Цех 3
Склад 1 20 40 50
Склад 2 30 50 80
Склад 3 0 0 0

Условия за неотрицателност:

Уравнения на материалния баланс

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

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

Началното решение е от вида:

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

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

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

Цех 1 Цех 2 Цех 3
Склад 1 40 40 (0)
Склад 2 30 30 60 (30) (0)
Склад 3 20 20 (0)
40 30 50
(0) (0) (20)
(0)

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

Определяне на началните стойности по правилото на „минималния елемент”

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

Цех 1
Цех 2
Цех 3

Склад 1 20
20

40 (20) (0)
Склад 2
10
50
60 (50) (0)
Склад 3 20 20 (0)
40 30 50
(20) (10) (0)
(0) (0)

Пример 2. Фирма за производство на мебели има два завода и три склада за готова продукция. Първият завод за един ден произвежда 400 изделия, а втория 200 изделия от същия тип за същото време. В складовете за един ден могат да се складират следният брой изделия: в първи склад – 150 изделия, във втория склад – 300 изделия и в третия склад – 120 изделия. Разходите за транспортирането на едно готово изделия от съответния цех до съответния склад са дадени в следната таблица

Склад 1 Склад 2 Склад 3
Завод 1 28 30 20
Завод 2 60 50 10

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

Склад 1 Склад 2 Склад 3 Склад 4
Завод 1 28 30 20 0
Завод 2 60 50 10 0

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

Да се намерят началните стойности на променливите по правилата на северозападния ъгъл и минималния елемент от пример 2.

4.8. Двойственост на задачите на линейното програмиране

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

Съществуват два вида двойствени задачи:
- симетрични;
- несиметрични.

Симетричните двойствени задачи се наричат тези, при които ограничителните условия са система линейни неравенства. При това, ако в пряката задача неравенствата са от вида ≤, в двойнствената ще бъдат от вида ≥ и обратно. Ако в пряката задача се търси max, в двойствената задача ще се търси min.
Несиметрични задачи се наричат тези, при които системата от ограничителни условия в едната са системи линейни уравнения, а в двойнствената задача – линейни неравенства. При това в задачата с линейни неравенства не се изисква задължително неотрицателност на променливите, т.е. те могат да бъдат и отрицателни числа.

Ето и вида на правата и обратната задача в общ вид:

Права задача Обратна задача
– min – max

От сравняването на пряката и двойствената задача могат да се направят следните изводи:

1. Ако в правата задача целевата функция се минимизира, в двойствената задача се максимизира и обратно;
2. Коефициентите от целевата функция на правата задача се превръщат в свободни членове на ограниченията в двойнствената и обратно;
3. Матрицата от ограниченията в правата задача е транспонираната матрица на ограниченията в двойствената;
4. Ако ограниченията в пряката задача са от вида ≤, то в двойнствената ще бъдат от вида ≥ и обратно;
5. Екстеремумите на двете целеви функции са равни.

4.9. Целочислено програмиране

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

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

Решаването на задачата за линейното програмиране е възможно по два начина:
- аналитично;
- таблично.

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

б) (3)
или ; (3a)

в) (4)
или (4а)

г) (5)

или (5a)

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

A) Преобразуване на ограниченията тип равенства в ограничения тип неравенства

Наличието на броя ограничения тип равенства дава възможност управляващи параметри да се изразят чрез останалите
(17)

Получените съотношения се заместватв израза за целевата функция Q(x), която става вече функция на управляващи параметри
(18)
Ограниченията ( броя) тип равенства се обръщат в ограничения тип неравенства, съгласно изискването , т.е.
, (19)
или (20)
Очевидно е, че броят на ограниченията остава същия.
Този метод на изключване на част от управляващите параметри от целевата функция дава възможност оптималното решение да се намери лесно.

B) Преобразуване на ограниченията тип неравенства в ограничения тип равенства
броя ограничения тип неравенства (4), (5) могат да се преобразуват в равенства , ако се въведат фиктивни управляващи параметри.
Например при неравенствата от типа (4)

се добавя нов допълнителен параметър в лявата част за да се изпълни равенството
, (20)
при .
Амалогично се подхожда и при неравенства (5), като допълнителните фиктивни параметри се извадят
(21)
Ако се означи общия брой допълнително въведени фиктивни управляващи параметри с , и се включат в критерия за оптималност
(22)
Тук за всички , се приема . Системата от ограничения може да се запише
(23)

Методи за решаване на задачата за линейно програмиране

А) Метод на последователното изключване
Прилага се при прости задачи с малък брой управляващи параметри. Последователно се изключват броя управляващи параметри (17) и заместват в целевата функция и останалите ограничения.

Б) Метод на граничните точки
Вече беше показано как една оптимизационна задача с ограничения тип равенства и неравенства може да се приведе до задача с ограничения тип неравенства. Тъй като целевата функция и ограниченията имат линеен характер, то оптималното решение ще лежи някъде на границите и ще удовлетворява някои от уравненията на системата, описваща границите на многостена
(39)
и (40)
Ако се намерят координатите на върховете на многостена, определящ границите на допустимото пространство за търсене на решението и се изчисли целевата функция за всеки връх , максималната (минималната ) стийност ще бъде търсеното решение. Върховете на многостена се наричат гранични точки.
Примерен вид на решение, при n=2.

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

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

Алгоритъм на симплексният метод.
Дадена е целева функция (1), на която се търси минимум при ограничения от типа (2-5).
1) Преобразуват се всички ограничения тип неравенства (4) и (5) в равенства чрез въвеждане на фиктивни променливи – по описания начин. Получава се следната изходна задача

(45)
с ограничения (46)
(47)
или
(47a)
Всяко решение , удовлетвиряващо (47а) се нарича допустимо решение. Оптимално решение е допустимо решение, при което се получава минимум на целевата функция ;
2) Приемат се n базистни и m опорни (управляващи) параметри. В началoтo управляващите параметри се приемат за свободни. Останалите m базистни се изразяват чрез тях от (47а)

(48)
3) Приема се начално базистно решение за свободните управляващи параметри (49)
и получава начално базистно решение за базистните управляващи параметри : (50)
Необходимо условие базистмото решение да бъде допустимо е всички параметри в (50) да бъдат положителни или равни на нула.
4) Получениете стойности за базистното решение (49) и (50) се заместват в целевата функция и се получава начална базистна стойност на целевата функция

(51)
5) Проверява се за оптималност полученото решение до този етап
А) Ако в всички , полученото базистно решение е оптимално, защото не може да се подобри (при търсене на минимум).
Б) Ако в поне един коефициент например коефициента , това означава, че целевата фуккция Q(x) може да се подобри (в случая намали) ако се повишава .
6) Определя се границата до която може да се повишава (ако ). Той може да расте докато базистните променливи остават положителни.
Ще допуснем, че в базистния параметър коефициентът пред е отрицателен ( )
(52)
Тогава при (53)
се получава (53)
Съгласно (53) може да се повишава докато остава положително, т.е. при до граничната стойност (54)
7) Като базисен параметър се приема , а за свободен .
8) Ако има отрицателни коефициенти пред в няколко уравнения, от тях се отделя този базисен параметър , при който при повишаване на първи ще стане отрицателен. Параметърът се приема за свободен, а за базисен.
9) Преобразува се системата (48) чрез новия базисен параметър, като уравнението
(56)
се решава спрямо , т.е.
(57)
10) Преобразува се целевата функция чрез новия параметър като в нея се замества .
11) Получава се ново базистно решение, като в преобразуваната целева функция Q(x) се замести и алгоритъмът се повтаря от т.5.

Пример. Да се намери минимума на целевата функция (58)
ограничения
(59)
(60)
(61)
(62)
1) Преобразуват се ограниченията (60), (62)
(63)
(64)
(65)
2) Приемат се n=4 свободни управляващи параметри , m=3, базистни . Уравнения (64 – 65) се решават спрямо базистните параметри
(66)
(67)
(68)
3) Намира се начално базистно решение като в (66-68) се заместват . Получените са положителни, следователно базистното решени е допустимо.
4) Получава се начално базистно решение , като в (58) се замести .
Край на първи цикъл
5) Проверява се за оптималност полученото решение. В (58) има отрицателен коефициент пред , което показва, че Q(x) може да се намали ако се повишава ( ).
6) Определя се границата, до която може да се повишава, от условието базистните параметри (66-68) да остават положителни.
В уравнения (66-68) има отрицателни коефициенти пред . При
(69a)
(69б)
Ако в тези уравнения се повишава от 0, първо ще стане отрицателно . В такъв случай за свободен параметър се приема , а за базисен .
7) Преобразува се системата (66-68) чрез новия базисен параметър
(70)
(71)
(72)
8) След заместване на от (70) в целевата функция (58) се получава
(73)
9) След заместване на новите свободни параметри в (73), се намираново базистно решение за Q(x)=8.
Край на втори цикъл
10) В (73) има отрицателен коефициент пред , следователно Q(x) може да се подобри ако се повишава.
11) В базистните параметри пред има отрицателен коефициен само в уравнението за
12) Параметърът се приема за свободен, а за базисен.
13) Преобразува се системата (70-72)
(74)
(75)
(76)
14) Преобразува се целевата функция като в (73) се замести с (74)
(77)
15) Приема се и получава ново базистно решение
.
16) Новото базистно решение за Q(x), при получените стойности на управляващите параметри в т.14 е Q(x)=0.
17) Проверява се новото базистно решение за оптималност. В израза за , (77) няма отрицателни стойности, следователно последното базистно решение не може да се подобри.
18) Оптималните стойности на управляващите параметри са:
.
За тези стойности, целевата функция (58) има минимум . Получените стойности за фиктивните параметри ( ) остават без значение.

Вашият коментар