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.

Пример. Намерете най-ниската стойност на целевата функция

на набор от разтвори на системата

Solution. Ето - свободните променливи. Rewrite ограничение система (1), както е

Първоначалният разтвор е основен разтвор (7, 0, 0, 12, 0, 10), при което стойността на функцията е нула. Целевата функция вече е изразена по отношение на nonbasic променливи. Стойността на целевата функция може да бъде намален в резултат на увеличението. Сред коефициентите на системата (2) са отрицателни и. Ние намираме връзката (от второто уравнение (2)). Element - позволява. От старата основа изключение въведе в нея от nonbasic променливи. За да изразите това чрез, и от второто уравнение и заместител вместо експресията намерени в първата и третата уравненията на система (2), както и в експресията Е.

Получават система (3), при което - свободните променливи.

Новият основния разтвор е както следва: (10, 0, 3, 0, 0, 1). , Стойността на F може да бъде намален в резултат на увеличението. Сред коефициентите на системата (3) Само един отрицателен: разделителната елемент. Нека се обърнем към нова база:

Новият основен разтвор има формата :, A-нататъшно намаляване на стойността на целевата функция не е възможно.

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

Dana линейното програмиране проблем:

или в кратка форма:

Сред приемливи решения на системата (1.2), за да намерите този, който плаща най-много в линейна форма (1.1).

уравнение

В самолета х 1 О 2 определя направо която разделя равнината на две половини самолети, всяка от които се намира от едната страна на линията. Директен (1.4) се нарича граница и принадлежи към двете половинки равнини.

Координати на точки, лежащи в една и съща полуравнина удовлетворяват неравенството
,

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

Следователно, системата на неравенството (1.2) отговаря на набор от точки X (X 1, X 2), разположена в пресечната точка на полу-равнини, определени от неравенството в системата.

Пресечната точка на краен брой половинки самолети имат изпъкнала многоъгълна област Ω, която е наречена областта на решаването на система (1.2). Ако системата (1.2) е в противоречие, со на площ е празна. Горният проблем (1.1) - (1.3) сега може да се формулира по следния начин: сред всички многоъгълни домейн со точките за да намерите този, който плаща най-много в линейна форма



След като избрана произволно с 0, пишем уравнението на линията на семейството на успоредни линии, нормалната вектор

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

в положителната посока на вектора.

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

среща с площ Ω паралелно на посоката на движение на вектора

По същия начин се тълкува геометрично линейното програмиране проблем в наш тримерно пространство

Всяка неравенството на i1 х 1 + A i2 х 2 + ... + A в X N ≤ B I определя в N-тримерно пространство halfspace състояща се от точки X (X 1, X 2, ... X п), разположени от едната страна на граница hyperplane на i1 х 1 + на i2 х 2 + ... + а в х н ≤ б аз и повечето от това hyperplane. Пресечната точка на краен брой половинки пространства е изпъкнал многостенна Ω домейн, който е набор от всички ограничена решения на записаните задачи.

Линейният формата на точка Х "(х" 1, х "2, ..., х 'N) може да се разглежда като отклонение точка X" (х "1, х" 2, ..., х' N) на hyperplane

= 0,

когато съгласно условията на отклонението от hyperplane да се разбира броят получени в резултат на смяна в лявата страна на уравнението (1.9) вместо х 1, х 2, ..., х п координира точка X ". Геометрична интерпретация на линейното програмиране проблем е да намерите набор от решения Ω * в този момент, което е най-малкото (най-много) избегне hyperplane (1.9).

Схемата за решаване на проблема (1.1) - (1,3) графично.

1. Напишете уравнението на граничните линии.

2. Изграждане графики на граничните линии на равнината.

3. Разпределяне на решения в сферата на системата на неравенството (1.2).

4. Изграждане на полигон решения.

5. изобразени линейна форма (1.1).

6. Определяне на крайната точка на полигона.

7. Изчислете линейна форма в резултат на място.

Пример. Използването на графични метод за намиране на максимума на линейна форма

при условия:

Solution. Напишете уравнението на граничните линии и техните графици са изграждане на самолета в избраната координатна система:

Има решения за всяка област на неравенството използва спомагателното точка, тъй като това е най-удобно да се взема за 0 (0.0), и на кръстовището на половин самолети построени сграда полигон решения Ω. под формата на експресия линеен равнява на всеки произволен брой и изобразените съответстваща на получен директно уравнение:

Direct (1.13) преминава през началото и през друга точка, координатите на които е лесно да се определи.


Фиг. 1.1. Решение на линеен метод за програмиране графично.

В същото време на преместване на линия Z по посока на вектора, ние виждаме, че крайната точка е точка С (5, 3) - точката на пресичане на линиите.

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

които - като се има предвид броя на К.

матрица

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

Ако след това от това уравнение и подобни уравнение получава чрез отстраняване получи

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

В нашия случай, ние получаваме

Отговор: макс Z = 50, х 1 = 5, х = 3 2.

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

Фигура 1). Проблемът е с уникално решение

Ris..2). Задачата има един безкраен набор от решения


Фигура 3). Линейната форма не се ограничава до Фигура 4). Системата на ограничения несъвместими

Основен проблем LP:

(1)

при условия:

;

;

;

;

Въвеждане на 4 допълнителни неизвестни ние получаваме каноничната система (база):





Основа; свободни променливи, определени им равна на 0.

Нека след това в израза за F може да се увеличи, докато F ще намалее. Нека да се увеличи до 5, като Както в случая с "ненадеждни" в основата на всичко, го премахнете от основата, и въведе основа на изричното F и новите основни променливи чрез находка и да го замести в уравнението (1), (2), (3).

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

мин (*)

при условия:




,

Допустимо основния разтвор е както следва: Безплатни променливи. Нека ги равен на 0. решаване на примера по-долу, ние виждаме, че не може да се увеличи, тъй като ще vozrastatat (и ние трябва да бъдат сведени до минимум). So. Безплатна променлива може да се увеличи, но в противен случай тя ще бъде отрицателен.)

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

От "надеждно" за уравнението

ние откриваме

и заместител *). Ние получаваме:

мин

при условия:




Допустимо основния разтвор:

Там може да се увеличи до 6, като

по този начин

Е достигнал оптималното решение: В процеса на преход от едно основно решение на друга стойност F постоянно намалява.

Ние показваме пример на разтвора графично.

Фиг.2

На осите парцел на системата на неравенството (вж. Пример). Изпъкнало региона (Фигура 2) съответства на съвкупността от системата на неравенството решения. Минималните и максималните стойности на целевата функция се постига в точките на пресичане на този многостен вземане на "референтни" прави линии, изготвени перпендикулярна на вектора Нека пишат основа на решения:





Векторът показва положителна посока на движението, в която се увеличава F. Обективната функция на проблема LP достига минимум (максимум) в крайната точка на изпъкналата региона. Ако F получи оптималната стойност на няколко места, да достигне до същата стойност във всяка точка, която е изпъкнала комбинация от точки (случай, обективната функция достига минимум при лицата на) [1]. Множеството от всички планове на проблема с LP е изпъкнал [1-4]. Намирането на оптимално целевата функция намалява с изброяването на екстремните точки на изпъкнал многостен.

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

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


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



ТЪРСЕНЕ:


Вижте също:



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