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

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

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

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

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

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

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

Далее процесс повторяется, начиная с левой верхней клетки (1, 2). Для определения поставки х12 сравниваются уменьшенное предложение первого поставщика: 118 – 68 = 50 и спрос второго потребителя, равный 68, т.е. х12 = 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 единиц. Удовлетворить эту потребность можно с помощью второго поставщика, т.е. х22 = min{18, 18} = 18. За счёт этой поставки будет удовлетворён спрос второго потребителя и вывезен весь запас второго поставщика. В этом случае одновременно закрывается строка 2 и столбец 2. В этой ситуации нужно ввести нулевую поставку в одну из соседних с клеткой (2, 2) свободных клеток по строке или по столбцу, а именно, в клетку (2, 3) или (3, 2). Для этого следует сравнить тарифы, содержащиеся в этих клетках, и поместить в клетку с меньшим тарифом нулевое значение. Если тарифы этих клеток одинаковы, то нуль можно поместить в любую из них. Так как min{с23, с32} = min{13, 17} = 13, то занятой окажется клетка (2, 3).

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

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

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

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

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

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

S0 = 1568 + 1650 + 1618 + 1690 + 168 =