Формализация задачи планирования 2

В продолжение вчерашней записи.
Если чуть изменить задачу, то можно обойтись двукратным решением задачи линейного программирования (или это ее частный случай - транспортная задача? не помню).

Меняем задачу так: Проверить выполнимость плана. Если не выполним, то скомплектовать плавки, максимизируя общую массу отлитого; если план выполним, то добавляем к нему план следующей недели и комплектуем плавки так, чтобы был полностью выполнен план текущей недели и еще отлито что-то из следующего плана, по-прежнему максимизируем массу отлитого.

Т.е. исходим из того, что оборудование должно быть загружено максимально. Для нашего завода это разумная посылка - заказов много и проблема их выполнить все в срок. Еще тут предполагается, что мы планируем критичное оборудование, т.е. узкое место именно здесь, увеличение производительности здесь не создаст проблем на остальных участках. В общем, голдраттовская "теория ограничений" на практике.

Формальная постановка задачи и алгоритм чуть меняются:
1. Проверка выполнимости плана:
(Сумма по j) X_ij <= A_i - текущий план как ограничение
(Сумма по i) M_i*X_ij < C_j - верхнее ограничение массы плавки (нижнее аналогично)
Целевая функция: (Сумма по i и j) M_i*X_ij -> max - максимизируем общую массу отлитого.

2. Опорное решение элементарно: все X_ij=0

3. Решаем транспортную задачу, получаем оптимальное решение.

4. Если план выполним, то первая группа ограничений реализуется как равенство: (Сумма по j) X_ij = A_i
Если это не соблюдено, то план невыполним и полученное решение это тот максимум, который мы можем сделать из плана текущей недели.

5. Если план выполним, то увеличиваем систему: добавляем в нее план следующей недели, но отдельными позициями (т.е. "отливка А" из плана текущей недели и "отливка А" из плана следующей недели - это две разные позиции, хотя физически они одинаковые).

6. Ограничения для плана текущей и плана следующей недели различаются: для текущей недели берем равенства, для следующей недели - неравенства. Целевая функция такая же (с учетом того, что переменных в ней больше).

7. Решение, полученное на предыдущем этапе, является опорным для новой задачи (новые переменные мы приравниваем 0).

8. Решаем транспортную задачу с практически удвоенным числом переменных и находим оптимальную комплектацию плавок.

Финальные замечания:
а) Эта задача так красиво выглядит для одной марки стали - для нескольких марок сначала придется поделить количество плавок между марками стали, а затем оптимизировать эти группы отдельно. Реально стоит сначала выделить редкие стали (всякую там нержавейку) и минимизировать число плавок там - не больше пяти в неделю, это можно и перебором. Остается разобраться с двумя наиболее популярными марками стали.
б) Постановка задачи молчаливо предполагает, что все печи работают независимо, т.е. общее максимальное количество плавок есть сумма максимумов по всем печам. Реально это может быть не так - одновременно плавки на двух крупных печах может не потянуть силовой кабель, так что и тут возможны переборные вариации.