Опорный план

из "Методы оптимизации управления для менеджеров "

В таких случаях математики говорят, что записанные пять ограничений не являются независимыми. Поскольку первые два ограничения в сумме означают то же самое, что и последние три, фактически ограничений, влияющих на значения переменных решения, не пять, а четыре. [c.122]
Поскольку ограничения в этой задаче образуют систему уравнений относительно переменных решения, можно было бы попытаться решить эту систему, чтобы найти значения переменных. Но переменных решения в нашей задаче 6, а независимых уравнений для их решения только 4. Можно произвольно положить значение двух каких-нибудь переменных решения равными 0 (например, Хи=0 и Х]2=0), тогда остальные переменные решения могут быть однозначно определены из системы уравнений, образованной ограничениями. Получившийся план перевозок, разумеется, необязательно будет оптимальным, но он обязательно является допустимым, поскольку удовлетворяет всем ограничениям. [c.122]
Такой план называется опорным. От множества других допустимых планов он отличается тем, что число ненулевых переменных решения (ненулевых перевозок) точно равно количеству независимых ограничений в транспортной задаче или, иначе, сумме числа поставщиков и потребителей минус 1. [c.122]
например, т = 10, а п = 20, то количество переменных будет 200, а количество ненулевых переменных в опорном плане - только 29. [c.123]
В теории линейного программирования доказывается, что оптимальный план обязательно является опорным. Иными словами, искать оптимальный план перевозок нужно только среди опорных планов. В этом и состоит основное значение опорного плана. [c.123]
Опорным называется такой план, в котором количество ненулевых перевозок равно сумме количеств поставщиков и потребителей минус единица. [c.123]
Оптимальный план перевозок следует искать только среди множества опорных планов. [c.123]

Вернуться к основной статье