Блокове програмування
Отже, ми досить докладно вивчили симплекс-метод, подвійний симплекс-метод, а також модифікований симплекс-метод.
Що можна сказати про ці методи? Насамперед, це -універсальні,кінцевіметоди.
Кінцевість- це гарантія вирішення завдання ЛП за кінцеву кількість кроків (нехай і дуже велика).
Універсальність. Це означає, що ці методи мало враховують особливості будови матриці коефіцієнтів обмежень. Головне, що завдання відноситься до класу задач ЛП:
І ось тут ми стикаємося із фундаментальним "законом" математичного програмування:за універсальність треба платити. Іншими словами, конкретне завдання краще, ефективніше вирішувати методом, орієнтованим на особливості саме цього завдання, ніж методом, що повністю ігнорує будь-які особливості.
Наприклад, у нелінійному програмуванні взагалі немає універсальних методів. Практично кожен метод (за винятком, хіба що, повного перебору) висуває певні вимоги як до цільової функції, так і до функцій, що визначають безліч допустимих рішень 1 .
Але повернемося до лінійного програмування.
Багато класів широко поширених завдань ЛП мають специфічну будову матриці обмежень (A) . Ці особливості дозволяють суттєво знизити трудомісткість розв'язання цих завдань.
Перший із аналізованих нами класів представляють завдання так званого "блочного програмування".
Завдання блокового програмування
Деякі завдання ЛП великої розмірності мають такі структурні особливості, що дозволяють знайти оптимальне рішення шляхом т.зв.декомпозиції(або розкладання) вихідного завдання на ряд підзадач меншої розмірності.І ці підзавдання вирішуються практично незалежно друг від друга. Основний ефект при такому підході пов'язаний з тим, що значно легше вирішити багато "маленьких" завдань, ніж одну, але "велику". У математичному програмуванні це пов'язано з поліноміальною і навіть експоненційною залежністю трудомісткості вирішення завдань від їх розмірності.
Перевага методів, що використовують "декомпозицію" вихідного завдання на підзавдання меншої розмірності полягає в тому, що за допомогою цих методів виявляється можливим вирішення завдань такої розмірності, які не вдається вирішити іншими методами через практично нездійсненний обсяг обчислень.
Ситуації, що призводять до постановки таких завдань, трапляються досить часто.
Наприклад, це – завдання планування виробничої діяльності підприємств, що входять до об'єднання. Хоча кожне з таких підприємств може мати свої незалежні обмеження, виробничі програми окремих підприємств зазвичай узгоджують на верхньому рівні управління через об'єктивно існуючі обмеження (пов'язані, наприклад, із загальним обсягом фінансових ресурсів, які має об'єднання).
При цьому виникає завдання ЛП, що має структуру, яку у схематичній формі можна подати в такий спосіб.