Задача по линейному программированию
Решаю из сборника задач для себя и наткнулся на такую задачу.
Каждый из m станков может обрабатывать n типов деталей. Известны резервы времени работы станков a[i], i=1..m, и число деталей каждого вида b[j], j=1..n. Известно время обработки каждой детали на каждом станке t[i][j], i=1..m, j=1..n. Определить план загрузки станков, обеспечивающий минимальное суммарное время работы оборудования.
Нашел алгоритм Джонсона. Алгоритм решает задачу правильно, но не учитывая резерв времени работы. Подскажите как решить эту задачу, используя какой то алгоритм.
Ответы (1 шт):
Тут нет никаких этапов обработки и связей между ними, так что алгоритм Джонсона тут не нужен. Это обычная задача линейного программирования.
Если обозначить искомый план загрузки как l, то задача минимизировать функцию
при ограничениях:
Используйте любой алгоритм для решения задачи линейного програмирования.