Studopediya

КАТЕГОРИЯ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) Полиграфия- (1312) Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) Arhitektura- (3434) Astronomiya- (809) Biologiya- (7483) Biotehnologii- (1457) Военни бизнесмен (14632) Висока technologies- (1363) Geografiya- (913) Geologiya- (1438) на държавата (451) Demografiya- ( 1065) Къща- (47672) журналистика и смирен (912) Izobretatelstvo- (14524) външен >(4268) Informatika- (17799) Iskusstvo- (1338) историята е (13644) Компютри- (11,121) Kosmetika- (55) Kulinariya- (373) културата е (8427) Lingvistika- (374) Literatura- (1642) маркетинг-(23702) математиците на (16968) Механична инженерно (1700) медицина-(12668) Management- (24684) Mehanika- (15423) Naukovedenie- (506) образователна (11852) truda- сигурност (3308) Pedagogika- (5571) Poligrafiya- (1312) Politika- (7869) Лево- (5454) Priborostroenie- (1369) Programmirovanie- (2801) производствено (97 182 ) индустрия- (8706) Psihologiya- (18388) Religiya- (3217) Svyaz (10668) Agriculture- (299) Sotsiologiya- (6455) на (42831) спортист строително (4793) Torgovlya- (5050) транспорт ( 2929) Turizm- (1568) физик (3942) Filosofiya- (17015) Finansy- (26596) химия (22929) Ekologiya- (12095) Ekonomika- (9961) Electronics- (8441) Elektrotehnika- (4623) Мощност инженерно ( 12629) Yurisprudentsiya- (1492) ядрена technics- (1748)

Основни принципи на прилагането на техники за оптимизация

Класификация на математически задачи за програмиране

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

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

Те включват проблеми: линейно програмиране, линейното програмиране, число програмиране, линеен фракционна програмиране, параметрично програмиране, отделими програмиране, квадратното програмиране, динамично програмиране, стохастичен програмиране, геометрична програмиране и други.

Има различни характеристики на задачата за класификация.

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

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

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

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

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

Друга класификация функция - начин на определяне на областта на работни ограничения (1), т.е. определя G. Вариантите са:



1) не съществуват ограничения на всички,

2) лимит, определен от уравнения,

3) ограничения, дадени система на неравенство.

За 1 случай, ако ограниченията не се налагат на променливите (т.е., G = R п), и целевата функция е непрекъсната диференцируема функция, тогава проблемът (1) е класически проблем в крайна (безусловна екстремум). Разтворът се основава на теорията на диференциално смятане, по-специално, Extrema теория и методи въз основа на него.

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

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

тип на задачата

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

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

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

където D - симетрична матрица с размери N х N, - вектора на коефициентите на обективната функция, A - матрица на коефициентите на системата от линейни неравенства - вектор, на реални числа.

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

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

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

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

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

- Геометрична метод;

- А просто симплекс метод и неговите модификации:

- Simplex маса;

- Метод на изкуствена основа;

- Simplex метод с инверсната матрица;

- Метод Dual симплекс;

- Метод на последователните намаления и други остатъци.

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

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

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

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

Специален случай на целочислени програмни проблеми са Булева програмен проблем, когато променливите х J вземе само две стойности - 0 и 1. Най-известният от тези задачи - задача на задача (на служителя да се сложи някаква работа), задачата за избор на маршрут (пътува проблем продавач, проблемът пощальон), проблемът на максимално съответствие, и т.н.

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

- Планиране на оборота;

- Изграждане на мрежа за дистрибуция;

- Разпределение на персонала за операциите;

- Разпределение на ресурсите;

- Рационална организация на транспорта (транспорт проблем);

- Организиране на рационално поръчки на продукти (проблемът на диета);

- Оптимално производство;

- Проблемът за рязане на материала и др.

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

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

,

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

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

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

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

Динамично програмиране - е изчислителен метод за решаване на проблемите на екстремни определена структура, която възниква и се развива в 1950-1953g.g. чрез работата на Белман за динамични задачи по управление на инвентара. Динамично програмиране е насочено от пореден опции за сканиране, което неизбежно води до глобален максимум.

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

- Целта е да се даде възможност за тълкуването като процес на вземане на решения п -step.

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

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

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

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

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

- А последователен подход;

- Serial анализ на възможностите;

- Random търсене.

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

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

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

<== Предишна лекция | На следващата лекция ==>
| Основни принципи на прилагането на техники за оптимизация

; Дата: 01.15.2014; ; Прегледи: 197; Нарушаването на авторските права? ;


Ние ценим Вашето мнение! Беше ли полезна публикуван материал? Да | не



ТЪРСЕНЕ:


Вижте също:



zdes-stroika.ru - Studopediya (2013 - 2017) на година. Тя не е автор на материали, и дава на студентите с безплатно образование и използва! Най-новото допълнение , Al IP: 66.102.9.26
Page генерирана за: 0.053 сек.