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)

Обективната функция 1 страница

Ограничения:

Етап 1. Зоната за изграждане на изпълними решения (SDT).

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

Фигура 6.1. Graphic илюстрация на решаване на задачи на линейното програмиране

Изчисленията за изграждането на първите две ограничения:

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

Етап 2. Окончателното определяне на оптималните стойности на променливите и ,

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

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

За да се определят точните координати на точката на контакт линия на обективната функция граница SDT (точните стойности и ), Необходими за решаване на система, включваща две уравнения: и , Ние решаваме тази система от уравнения: , Заместването на тази стойност във второто уравнение:

Т.е. , Максималната стойност на целевата функция ,

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

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

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

Забележка. Последната точка - точка SDT гранично-пропускателен пункт.

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

Пример. Необходимо е да се сведе до минимум обективната функция



със следните ограничения:

Poctavim според тази задача следната система от линейни уравнения:

(6.1)

(6.2)

(6.3)

Решете тази система чрез последователно елиминиране на неизвестни (метод на Гаус). Тя се основава на следните елементарни трансформации са:

1. Умножение на - или уравнението на редица различни от нула;

2. Добавяне на две уравнения и последващо заместване на един от тях получи сумата;

3. Промяна на местоположението на всеки две уравнения.

С помощта на елементарни преобразувания получаваме следната система:

(6.4)

(6.5)

(6.6)

Уравнение (6.6) - е сумата от уравнения (6.2) и (6.3).

Уравнение (6,5) - е сумата от уравнения (6.2) и (6.6).

Уравнение (6.4) - е сумата на (6.1) и уравнения (6.5) и (6.6).

нека , Стойностите на променливите са както следва: ,

Тези стойности са решение на уравненията (6.4) - (6,6) и, следователно, на системата от уравнения (6.1) - (6,3). Освен това, Т.е. разтворът намерено е валиден.

защото (Sm.6.4), че е необходимо да се увеличи, за да се намали стойността на целевата функция Но не може да го увеличи до безкрай, в противен случай стойността на и стане отрицателен ( Тези изрази са получени съответно от уравнения 6.5 и 6.6). Съгласно първото уравнение То може да бъде равна на 4/3, съгласно второто уравнение 3. За всички задачи извършва условия, необходими да се най-малката от тези стойности - (Ако вземем след това Какво е приемливо и Това не е приемливо за нашия проблем, т.е. се вземат ). След това от (6,5), че ,

С помощта на елементарни преобразувания ние намали система от уравнения (6.4) - (6.6) на следните системи:

(6.7)

(6.8)

(6.9)

Системата (6.7) - (6,9) от (6,4) - (6,6) се получава както следва:

,

разделят това уравнение от 3, получаваме - Заместник в (6.6)

Ние пишем решението на (6.7) - (6.9):

,

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

Simplex - метод. навигационните пътища решения

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

при условия:

...

Тук икона Това означава "всичко".

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

Помислете стъпките на разтворите за търсене симплекс - със следния пример.

Пример. Модел рязане листови материали. Изборът на най-добрият вариант.

Има определен стандартен материал под формата на листове, които трябва да бъдат отрязани, за да се получи поне 80sht. 1 и части, като не по-малко от 40ps. 2. известни части, четири начина на рязане на листа, всеки от които дава резултатите, показани в Таблица 6.1.

Таблица 6.1 Входни данни за решаване на проблема

Методи за рязане на листа
резултат 3 статии от тип 1; 1 брой тип 2 2 броя тип 1; 6 части, такива като 2 1, т от тип 1; 9 тип 2 части 0 Тип 1 части; Тип 2 13 части

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

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

е - А всички комбинирани листа поток.

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

(6.10)

(6.11)

(6.12)

Ограничение (6.10) се предвижда определен брой парчета от тип 1, ограничението (6.11) - като се има предвид броя на елементите от тип 2. Limit (6.12) е необходимо, тъй като брой листа не може да бъде отрицателна.

За да се реши този проблем, използвайте метода за симплекс, трябва системата (6.10) - (6.12) резултата на стандартния формуляр:

(6.13)

(6.14)

(6.15)

Очевидно след разтвор на (6.13) - (6.15): ,

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

Етап 1. Спомагателни.

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

Трансформация на системата (6.13) - (6.15) в (6.16) - (6.18):

(6.16)

(6.17)

(6.18)

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

,

След това, прилагането на симплекс - алгоритъм за решаване на проблема със спомагателни. След това се извършва работата в системата (6.16) - (6.18).

1. изразява своите основни променливи и чрез свободни променливи

,

2. Определяне на целевата функция:

,

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

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

За текущата основния разтвор тъй като ,

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

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

,

т.е. Ние получи нов основен разтвор:

,

Отново извършване на симплекс алгоритъм:

1. Отново, ние изразяваме основните променливи са достъпни чрез:

2. ,

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

4. Въвеждане в базата тъй като тази променлива в израза за целевата функция има коефициент на "-3". тъй като , тъй като (Вж., Уравнение (6.17), като се има предвид, че ). е , Т.е.. може да се увеличи до 80/3 (40 невъзможно, защото в този случай ). Следователно, Т.е. Имаме нов основен разтвор: ,

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

,

Желаната функция не може да се намали, като ,

променливи Т.е. Те се преместиха в категорията на свободните променливи и да се изхвърли. Крайният основния разтвор Това е оптимална за етапа на подкрепа 1 и са валидни за системата (6.13) - (6.15).

Етап 2. Ние работим със системата (6.13) - (6.15). Като действащ основен разтвор Получен чрез свеждане до минимум в стъпка 1, оценявам го за първоначалния проблем с целевата функция , Така започва повторното използване на симплекс - алгоритъм, но за първоначалния проблем.

1. С помощта на (6.13) - (6.15) получаваме:

2. (Мълчи).

3. Този основен разтвор не е оптимално, тъй променлив Тя е с отрицателен коефициент.

4. Ние влизаме в база променлива х 2.

; (Expression мълчи).

, може да се увеличи най-много до 40/16 = 5/2, с

т.е. Имаме нов основен разтвор: ,

Отново изпълнява симплекс - алгоритъм:

1.2. изразявам чрез свободни променливи ,

(Мълчи).

3. По отношение на целевата функция на всички коефициентите на променливите са положителни. Т.е. текущата основния разтвор е оптимално, тогава , Т.е. технология е най-добрият вариант да се използва само първия и втория методи за рязане на листове, на метода трябва да бъдат изрязани първия лист 25 и втори лист 2.5, а най-ниската обща листа натрупан дебит са 27.5 бр. Броят на части, произведени в този случай ще бъде: на елемента тип 1 -

,

т тип 2 -


Лекция 7

Числени методи за решаване нелинейно програмиране (търсене на екстремум функция на една променлива)

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

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

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

1. Числени методи за намиране на екстремум на функции на една променлива.

1.1. Класическият метод.

1.2. дори бюст метод.

1.3. златен метод раздел.

1.4. метод на Фибоначи и т.н.

2. Числени методи за намиране на екстремум п - променливи.

2.1. Числени методи в проблеми без ограничения.

2.1.1. координира метод спускане.

2.1.2. Джийвс - Метод кука.

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

2.1.4. метод на Нютон.

2.1.5. Методът на конюгатни посоки и т.н.

2.2. Числени методи в проблеми с ограничения.

2.2.1. координира метод спускане.

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

2.2.3. Методът на бариерни функции.

2.2.4. Методът на наказателните функции.

2.2.5. метод линеаризация и т.н.

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

Търсене Методи екстремни функции на една променлива

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

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

Класическият метод за минимизиране (максимално) функциите на една променлива

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

<== Предишна лекция | На следващата лекция ==>
| Обективната функция 1 страница

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


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



ТЪРСЕНЕ:


Вижте също:

  1. Аз Обявата 3.3. функция на файлове, работа с масив от стойности
  2. I. Функцията за освобождаване от отговорност на сърцето. Ролята на апарата за вентил в неговото прилагане.
  3. Уеб-сайт трябва да бъде идентичен на дисплея в Microsoft Internet Explorer и Netscape Navigator, и много желателно - в последните и предпоследните версии на тези програми.
  4. Групиране агрегат функция
  5. Административен и правен статут на благотворителни Page 1
  6. Административен и правен статут на организации страница благотворителна 10
  7. Административен и правен статут на благотворителни организации страница 11
  8. Административен и правен статут на благотворителни организации, страница 12
  9. Административен и правен статут на благотворителни организации, страница 13
  10. Административен и правен статут на благотворителни организации страница 14
  11. Административен и правен статут на благотворителни организации страница 15
  12. Административен и правен статут на благотворителни организации страница 16




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