Блоково програмиране
И така, ние проучихме симплексния метод, двойния симплексен метод и модифицирания симплексен метод достатъчно подробно.
Какво може да се каже за тези методи? На първо място, това сауниверсални,крайниметоди.
Крайносттае гаранция за решаване на проблема с LP в краен брой стъпки (макар и много големи).
Гъвкавост. Това означава, че тези методи практически не отчитат структурните особености на матрицата на коефициента на ограничаване. Основното е, че проблемът принадлежи към класа на задачите на LP:
И тук се сблъскваме с фундаменталния "закон" на математическото програмиране:трябва да платите за универсалността. С други думи, по-добре и по-ефективно е да се реши конкретен проблем чрез метод, който е ориентиран към характеристиките на този конкретен проблем, отколкото чрез метод, който напълно игнорира всякакви характеристики.
Например, в нелинейното програмиране изобщо няма общи методи. Почти всеки метод (с изключение, може би, на изчерпателното изброяване) налага определени изисквания, както към целевата функция, така и към функциите, които определят множеството от възможни решения 1 .
Но обратно към линейното програмиране.
Много класове от широко използвани LP проблеми имат специфична структура на матрицата на ограниченията (A). Тези функции могат значително да намалят сложността на решаването на тези проблеми.
Първият от класовете, които разглеждаме, са задачите от така нареченото "блоково програмиране".
Блокиране на задачи по програмиране
Някои високоразмерни проблеми на LP имат такива структурни особености, които позволяват намирането на оптималното им решение чрез т.нар.декомпозиция(или декомпозиция) на първоначалния проблем на редица подзадачи с по-малък размер.Освен това тези подзадачи се решават почти независимо една от друга. Основният ефект от този подход е, че е много по-лесно да се решат много "малки" проблеми, отколкото един "голям". В математическото програмиране това се дължи на полиномиалната и дори експоненциална зависимост на сложността на решаването на проблемите от тяхната размерност.
Предимството на методите, които използват "разлагането" на първоначалния проблем на подзадачи с по-малка размерност, е, че с помощта на тези методи е възможно да се решават проблеми с такова измерение, които не могат да бъдат решени с други методи поради почти невъзможното количество изчисления.
Ситуациите, водещи до формулиране на подобни проблеми, са доста чести.
Например, това са задачите за планиране на производствената дейност на предприятията, включени в асоциацията. Въпреки че всяко от тези предприятия може да има свои собствени независими ограничения, производствените програми на отделните предприятия обикновено се координират на най-високото ниво на управление поради обективно съществуващи ограничения (свързани например с общия размер на финансовите ресурси, с които разполага сдружението).
В този случай възниква проблем на LP, който има структура, която може да бъде представена в схематичен вид по следния начин.