Планирование n заданий на m станках с помощью линейного программирования
Я слышал, что вы можете использовать линейное программирование для планирования задач. Я не очень понимаю, как это сделать, потому что линейное программирование оптимально, а планирование в больших масштабах (например, планирование n заданий на m машинах) имеет экспоненциальную сложность.
Так, как я могу решить, например, проблему 100 рабочих мест и 10 машин, используя линейное программирование? Можете ли вы дать мне какое-то объяснение или дальнейшее чтение?
1 ответ
Так, как я могу решить, например, проблему 100 рабочих мест и 10 машин, используя линейное программирование?
Как правило, вы не можете. Это не та проблема планирования, к которой применимо линейное программирование (LP).
В задаче LP у вас есть набор переменных, для которых вы хотите решить. У вас есть набор линейных неравенств, которые представляют ограничения для этих переменных. И у вас есть линейная функция от этих переменных (т. Е. Без показателей степени, без деления, без "если-то-еще" и т. Д.), Которая представляет стоимость (или выгоду) данного решения.
Если у вас есть такая проблема, вы можете использовать LP для эффективного создания оптимального решения. Планирование работы магазинов, как и то, о чем вы спрашиваете, не такая проблема.
LP имеет тенденцию поддаваться планированию "более высокого уровня". Мол, сколько из каждого продукта я должен сделать на каждом заводе? В такой задаче вы часто сможете указать ограничения в виде линейных неравенств, а стоимость (или выгоду) - в виде линейной функции, что необходимо сделать, чтобы использовать LP. Обратите внимание, я сказал "сколько из каждого продукта...", а не "сколько...". Потому что это еще одно ограничение LP - переменные должны иметь возможность принимать реальные значения. Если вам нужно ваше решение, чтобы дать целочисленные решения, вы смотрите на проблему целочисленного программирования (или смешанного целочисленного программирования).