Тема 2.4. Симплекс метод за линейното програмиране.
Двуизмерен линейното програмиране проблема решен графично. За случая N = 3 триизмерното пространство и обективната функция може да се счита достигне оптимална стойност на един от върховете на многостен.
В общата форма, когато проблемът участва N са известни, може да се каже, че е възможно региона определя от система ограничения, изглежда изпъкнал многостен в п тримерно пространство, и оптимална стойност на обективната функция се постига в един или повече върхове. Решаването на тези задачи, графично, когато броят на променливи, над 3 много трудно. Налице е универсален метод за решаване на задачи на линейното програмиране, наречен симплекс метода.
симплекс метода е основната линейно програмиране. Решение започва с преглед на един от върховете на условията полиедъра. Ако тестът не съвпада с пика на максимум (минимум), а след това отиде до близкия, увеличаване на стойността на целевата функция за решаване на проблема на максималните и намаляване когато решаването на проблема до минимум. Така преминаването от един връх в друга подобрява стойността на обективната функция. Тъй като броят на върховете на многостен е ограничен, на крайните броя на стъпките, със сигурност ще намерите оптималната стойност, или установяването на факта, че проблемът е нерешим.
Този метод е универсален, приложим към всеки линейното програмиране проблем в канонична форма. система от ограничения тук - система от линейни уравнения, в които неизвестно количество по-голямо от броя на уравнения. Ако рангът на системата е равна на р. ние можем да избираме R неизвестни са изразени по отношение на останалите неизвестни. За определеност, да приемем, че избрания на първо място, поредна, неизвестен X 1. X 2. X р. След това, нашата система от уравнения може да се запише като
Подобен резултат може да бъде всякакъв вид съвместна система. например, методът Гаус. Не винаги е възможно да се изрази през останалата част от първите R неизвестни (направихме го да запише специфична). Въпреки това, те R неизвестното трябва да съществува. Тези неизвестни (променливи) се наричат основни, а други са безплатни.
Даване на определени стойности на свободните променливи и изчисляване на стойностите на основа (изразено чрез безплатно), ще получат различни решения на нашата система от ограничения. По този начин, можете да получите на всяко решение. Ние сме заинтересовани в специални разтвори, получени в случаите, когато свободните променливи са равни на нула. Такива решения се наричат основни. тях толкова, колкото различните основни вида ограничения в тази система. Основен разтвор се нарича допустима основен разтвор или базисното решение. ако то е не-отрицателни стойности на променливи. Ако се приема като основен променлива X 1. 2. X X R. След това разтворът 1. б 2. б R. 0. 0> ще бъде позоваването при условие, че б 1. б 2. б R ≥ 0.
Симплекс метод се основава на теоремата, който се нарича основното теоремата на метода на симплекс. Сред най-добрият проблема планове линейното програмиране в канонична форма е задължен да има референтен разтвор на неговата система на ограничения. Ако проблемът е уникална оптимална план, той съвпада с референтен разтвор. Различни окачващите разтвори на системни ограничения ограничен брой. Следователно, решението на проблема в канонична форма може да се търсят решения за подкрепа на бюста и един от тях, за които стойността на F е най-големият. Но, първо, всички референтни решения не са известни и трябва да бъдат намерени, а от друга страна, в реални приложения на тези решения и много груба сила едва ли е възможно. Методът на симплекс е определена процедура насочено модели изброяване решения. Въз основа на някои открити в аванс от стандартните разтвори по определен начин на алгоритъм симплекс, ние изчисляваме новата референтна решение, в който целевата функция F стойност е по-малко от старите. След редица стъпки, стигаме до базисното решение, което е най-добрият план.
Така симплекс метод прави определен ред, когато първата (източник) основни разтвори, и когато други основни разтвори. Неговата идея е както следва.
ограничения Imeyasistemu. редуцира до общ изглед, който е на системата от m линейни уравнения с п променливи (m
Свързани статии