Планирование n заданий на m Машины с линейным программированием

Question

Я слышал, что вы можете использовать линейное программирование для задач планирования. Я действительно не понимаю, как это сделать, потому что линейное программирование является оптимальным и планирование в больших масштабах (например, планирование n заданий на машинах m) имеет экспоненциальные трудности.

Так как я могу решить, например, проблему 100 заданий и 10 машин с использованием линейного программирования? Можете ли вы дать мне некоторое объяснение или дальнейшее чтение?

Answer 1

Так как я могу решить, например, проблему 100 рабочих мест и 10 машин с использованием линейного программирования?

Как правило, вы не можете. Это не та проблема планирования, к которой применимо линейное программирование (LP).

В проблеме LP у вас есть набор переменных, которые вы хотите решить. У вас есть набор линейных неравенств, которые представляют собой ограничения на эти переменные. И у вас есть линейная функция этих переменных (т. Е. Нет показателей, без деления, нет «if-then-else» и т. Д.), Которые представляют стоимость (или преимущество) данного решения.

Если у вас есть такая проблема, вы можете использовать LP для эффективного создания оптимального решения. Планирование магазина, как и то, о чем вы просите, не является проблемой.

LP склоняется к планированию более высокого уровня. Например, сколько каждого продукта следует делать на каждой фабрике? В такой проблеме вы часто можете указать ограничения как линейные неравенства и стоимость (или преимущества) как линейную функцию, как вы должны сделать, чтобы использовать LP. Заметьте, я сказал «сколько из каждого продукта ...», а не «сколько ...». Поскольку это еще одно ограничение LP - переменные должны иметь возможность принимать реальные значения. Если вам нужно решение для решения целочисленных задач, вы изучаете проблему программирования целых чисел (или смешанного целочисленного программирования).