Решение задач линейного программирования транспортного типа: Методические указания к выполнению индивидуальных домашних заданий, страница 3

В левом верхнем углу каждой клетки (i, j) помещается тариф данной перевозки c_ij, а сама клетка предназначается для размещения величины поставки x_ij из i-го пункта назначения в j-й пункт потребления. В клетки этой таблицы следует занести объемы перевозок, соответствующие начальному опорному плану. Этот план перевозок должен быть допустимым, т.е. составлен таким образом, чтобы выполнялись балансовые условия: общая сумма всех поставок от каждого поставщика (сумма по строке) равна объему его производства, а общая сумма поставок каждому потребителю (сумма по столбцу) — его спросу.

Клетки, в которые помещены какие-то перевозки, считаются занятыми, а остальные клетки — свободными. Занятые клетки транспортной таблицы соответствуют базисным, а свободные — небазисным компонентам опорного плана. Поскольку этот план должен быть опорным, то число занятых клеток в нем должно равняться m + n – 1 = 8. Проще всего построить такой план методом северо-западного угла.

1.1. Построение начального опорного плана методом северо-западного угла

Метод северо-западного угла заключается в том, что распределение груза начинается с левого верхнего угла и заканчивается в правом нижнем углу транспортной таблицы. Сначала заполняется верхняя левая (северо-западная) клетка таблицы, в которую помещается максимально допустимый объем перевозки. Его величина ограничена возможностями первого поставщика и спросом первого потребителя, т.е. х₁₁ = min{а₁, b₁}.

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

Таблица 1.1 содержит опорный план, построенный методом северо-западного угла для нашей задачи. Продемонстрируем порядок заполнения этой таблицы. Распределение поставок начинается с левой верхней клетки (1, 1). От первого поставщика должны быть вывезены все 118 единиц груза, причем первая поставка предназначается первому потребителю: х₁₁ = min{а₁, b₁} = min{118, 68} = 68. Так как спрос первого потребителя полностью удовлетворен, то первый столбец «закрывается», т.е. больше не участвует в построении опорного плана. В результате мы приходим как бы к новой таблице, у которой первый столбец исключён, а запас у первого поставщика уменьшился на 68 единиц и стал равен: 118 – 68 = 50.

Далее процесс повторяется, начиная с левой верхней клетки (1, 2). Для определения поставки х₁₂ сравниваются уменьшенное предложение первого поставщика: 118 – 68 = 50 и спрос второго потребителя, равный 68, т.е. х₁₂ = min{50, 68} = 50. Таким образом, от первого поставщика вывезена вся продукция, и первая строка закрывается.

Таблица 1.1

bj ai	68	68	90	31	87
118	15 68	16 50	14	11	17
18	15	16 18	13 0	11	14
98	21	22	16 90	16 8	23
110	0	0	0	0 23	0 87

Однако у второго потребителя остался неудовлетворённым спрос в размере: 68 ‑ 50 = 18 единиц. Удовлетворить эту потребность можно с помощью второго поставщика, т.е. х₂₂ = min{18, 18} = 18. За счёт этой поставки будет удовлетворён спрос второго потребителя и вывезен весь запас второго поставщика. В этом случае одновременно закрывается строка 2 и столбец 2. В этой ситуации нужно ввести нулевую поставку в одну из соседних с клеткой (2, 2) свободных клеток по строке или по столбцу, а именно, в клетку (2, 3) или (3, 2). Для этого следует сравнить тарифы, содержащиеся в этих клетках, и поместить в клетку с меньшим тарифом нулевое значение. Если тарифы этих клеток одинаковы, то нуль можно поместить в любую из них. Так как min{с₂₃, с₃₂} = min{13, 17} = 13, то занятой окажется клетка (2, 3).

Замечание. Такую процедуру нужно выполнять всякий раз, когда одновременно исчерпываются спрос текущего потребителя и запас текущего поставщика. Тогда после окончания работы метода северо-западного угла будет получена таблица, содержащая m + n – 1 занятую клетку, что необходимо для использования метода потенциалов.

В оставшейся части транспортной таблицы третий поставщик имеет запас в 98 единиц, который предлагается третьему потребителю с объемом спроса в 90 единиц, тогда х₃₃ = min{98, 90} = 90. Такой поставкой удовлетворен спрос у третьего потребителя и столбец 3 также закрывается.

Однако не исчерпан запас у третьего поставщика, его остаток равен: 98 – 90 = 8 единиц, которые предлагаются к перевозке четвертому потребителю. Тогда поставка  х₃₄ = min{8, 31} = 8 и строка 3 закрывается.

Поставкой х₃₄ спрос четвёртого потребителя удовлетворён не полностью. Недополученный спрос у четвертого потребителя составляет: 31 – 8 = 23 единицы. Эта потребность удовлетворяется за счет четвёртого поставщика: х₄₄ = min{110, 23} = 23, а затем столбец 4 закрывается.

Оставшимся запасом у четвертого поставщика: 110 – 23 = 87 единиц удовлетворяется спрос в 87 единиц пятого потребителя через поставку х₄₅ = min{87, 87} = 87. Таким образом, в последней клетке (4,5) плана поставок удовлетворяются сразу и последний поставщик, и последний потребитель. Нижняя угловая клетка транспортной таблицы при использовании метода северо-западного угла всегда оказывается занятой.

Итак, построен начальный опорный план, представленный в таблице 1.1. Транспортные затраты на его осуществление рассчитываются как сумма произведений соответствующего тарифа на величину поставки:

S₀ = 1568 + 1650 + 1618 + 1690 + 168 =