К настоящему времени широкое развитие получили методы блочного линейного программирования, в частности метод Данцига-Вульфа. Основная идея метода заключается в эквивалентном преобразовании исходной задачи (5.1)-(5.4) к новой задаче, называемой главной. В процессе определения текущего плана главной задачи возникают задачи блоков (предприятий), которые могут решаться независимо.
Полное решение задачи (5.1)-(5.4) состоит из следующих трех этапов:
1. Нахождение опорного плана главной задачи - этап запуска алгоритма.
2. Поиск решения главной задачи - информационный этап - итерационная процедура, которая заканчивается, если выполнено условие оптимальности плана.
3. Восстановление решения задачи (5.1)-(5.4) - этап поиска решений.
Предположим, что задача (5.1)-(5.4) решается в системе (T + 1) ЭВМ. Считается, что в памяти ЭВМ блока t содержатся исходные данные t-го предприятия (матрицы ). В ЭВМ центра записаны вектор В и числа m, T. ЭВМ центра связана с ЭВМ блоков, которые функционируют независимо друг от друга.
Общая структура алгоритма блочного программирования приведена на рисунке 5.2.
математический компьютерный модель решение
Для описания всей процедуры решения исходной задачи необходимо указать математические выражения задач центра и предприятий для всех выделенных этапов и информацию, передаваемую между этими задачами.