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)

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




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

Разглеждане на хомогенна проблема LP Пример №1 ал 1.5..:

(1)

Като прибавим към лявата страна на неравенството на системата променлива подходящ баланс трансформиране на проблема (1) в канонична форма:

(2)

За удобство и еднаквост напиши определянето на целевата функция като уравнение:

(3)

Напиши (2) и (3) първа симплекс таблица:

- 2 (4)
- 1
- 4 - 3 - 1

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

Освен това, с променлива определя от първия ред на таблицата (4), която е кондензирана запис на първото уравнение (2). при тя приема формата:

Вторият ред определя променлива маса

Третият ред дефинира :

Стойността на целевата функция се определя от индекса на линия:

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

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



Ние виждаме, че в маса (4) без негативизъм състоянието на всички елементи на индекса на линия (разбира се на, с изключение на дясната част Застанал в колоната на свободни термини) не е изпълнено. Освен това, двете колони освободи променливи и съдържа отрицателни елементи в индекса на линия: - -3 и 4 - съответно.

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

,

където - Водеща номера на колоната.

В този случай, и допустимо отношения съответно:

Ние добавяме към масата за симплекс (4) колона :

- 2 (5)
- 1
- 4 - 3 - 1

На маса (5) отрицателен елемент - колона 4, магистър взето в рамка, за да се изолира водеща колона. Можете, разбира се, изберете колоната, или всеки друг разумен начин: цвят, шрифт и т.н.

Сред всички допустими отношения Намерете най-малкото: ,

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

- 2 (6)
- 1 5 =
- 4 - 3 - 1

Следващата ни цел е да трансформира начина на Гаус маса (6) в нова симплекс таблица, първата колона на която ще се превърне в основната линия, съдържащ номер 1 в резултата (трета) линия.

На първо място, се разделят на водещ ред на ключов елемент:

- 2 (7)
- 4 - 3 - 1

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

Ние сега носят следната трансформация Гаус:

1) се изважда от първия ред на (трета) линията на олово;

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

3) добавите към водещите на индекса на линия, умножен по 4.

В резултат на това, ние получаваме нова таблица:

(8)
- 5

Лесно е да се види, че имаме една маса симплекс. Наистина, в таблицата (8), след колонна пермутация с колона през последните три колони на матрицата на идентичност се получава; безплатно членове колона е неотрицателна; обективна функция Това зависи само от наличните променливи и

Имайте предвид, че колоната Ставайки основен, свален "от базата" колона , Поради това, процесът е направил се нарича една операция замяна. В този случай, операцията се състои от поредица от елементарни трансформации Гаус 1), 2) и 3).

Така втори симплекс маса (8), което съответства на втория референтен разтвор. променливи и - Безплатен и, следователно, и , От първото уравнение е.

стойността на основната променлива е 3: , основна променлива определя от второто уравнение:

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

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

Този референтен разтвор също не е оптимална, както следва от факта, че индексът на ред от таблицата (8) има негативен елемент (-5) във втората колона, която ние сега избират като водеща колона. След това ние намираме линията, водеща до минималното допустимо съотношение и ключов елемент:

2
9.5 (9)
- 5

Разделете водещ ред (първи) за ключов елемент :

(10)
- 5

След това ние правим следния превръщането на Гаус:

1) изважда първия ред на втората умножава по 2;

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

3) се добавят към индекс първия ред на умножен по 5. Резултатът е една маса трета симплекс:

(11)

Тя съответства на третия сравнителен разтвор:

- И стойността на целевата функция ,

Тъй като линията на индекс на маса (11) не съдържа негативни елементи получи препратка решение е оптимално: и (12) В този Тук ние звездичките означават оптималните стойности на променливите.

По този начин, проблемът (2), и задача (1), адресирани до него.

1.8.2. Симплекс метод алгоритъм.

Сега описание на метода на разтвор, по общ начин.

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

(1)

Тук ние считаме свободните променливи , Ние пишем функцията като уравнение:

(2)

Уравнения (1) и (2) съответства на първата симплекс таблица:

... .. ... ..
... .. ... ..
... .. ... .. (3)
... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... ..
... .. ... ..
... .. ... ..

Започнете метод алгоритъм симплекс.

Стъпка 1. В таблицата на симплекс е референтния разтвор. В първия етап, той ще бъде:

и (4)

Стъпка 2. Проверете състоянието на оптималност на получените стандартните разтвори. Ако ред на последната (индекс) маса (3) не съдържа отрицателни елементи, т.е. всички коефициентите на целевата функция неположителна: референтното решение е оптимално. Разтворът се завърши и да преминем към стъпка 9.

Ако условието за оптималност: Не е изпълнено, а след това решението на проблема продължи.

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

Стъпка 4. Определяне на минималния приемлив съотношението на за всеки ред по правилото:

където - Водеща номера на колоната.

Стъпка 5. Изберете броя водещ на линията с минималното приемливо съотношение на ,

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

Стъпка 6. Разделете линия, водеща до ключов елемент от Застанал в пресечната точка на водещите линии и водещата колона. В резултат на това, ключов елемент в място Ние се получи един: ,

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

Стъпка 8. Отидете на стъпка 1.

Стъпка 9. Декларирам, че получените оптимално решение и екранните решения на резултатите. След това, отидете в края на алгоритъма.

Стъпка 10. Ние ви информира, че там не е решение и да отидете в края на алгоритъма.

Край алгоритъм.





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


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



ТЪРСЕНЕ:


Вижте също:



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