Методы принятия управленческих решений: для менеджеров

93 ся понятие цикла транспортной задачи. Циклом в таблице условий транспортной задачи (табл.30) на­ зывается замкнутая ломаная, состоящая из звеньев, расположенных вдоль строк и столбцов, все вершины которой, кроме одной, распо­ ложены в занятых клетках таблицы. Для любой свободной клетки, то есть клетки, где на месте Ху находится прочерк, можно постро­ ить лишь один цикл. Суть метода потенциалов заключается в том, что после на­ хождения опорного плана каждому поставщику (строке) ставится в соответствие число С,, называемое потенциалом поставщика Л,, а каждому потребителю (столбцу) - число Vj , называемое потенциа­ лом потребителя. Числа t/, и V j выбирают так, чтобы в любой за­ нятой клетке выполнялось равенство t/, + Vj = с,у. Рхли план Х* = [х)5,1)2,...,дГт„) транспортной задачи являет­ ся оптимальным, то ему соответствует система т п + т чисел Uj и * Vj , удовлетворяющих условиям * • • — — Uj +Vj = Cjj для Xjj > О, г = l,m, у = 1,и ; (53 и* + Vj < Cjj для Xjj = О, I = \,т, j = \,п . (54 Необходимое и достаточное условие оптимальности плана транспортной задачи в том, что ему должны соответствовать числа Uj и V j , удовле1воряющие условиям Ду = Су - (f7, + Ку )> О для свободных и Ду =Cjj -(Uj + Vj)=0 для занятых клеток. Потенциалы находят из ус;ювия Uj +V j =Су , где Су - стои­ мость перевозки единицы груза, указанная в /'-ой строке и у'-м столбце занятой клетки. Опорный гшан задачи содержит (и -н /и -1) линейно независимых уравнений вида (53) с (п + т) неизвестными. Число