Нахождение первоначального базисного распределения поставок

Одним из возможных методов нахождения первоначального базисного распределения поставок является метод "северо-западного" угла, показанный в следующем примере.

Пример 7.2. Найти первоначальное базисное распределение поставок для транспортной задачи из примера 7.1.

Решение. Дадим переменной х ₁₁максимально возможное значение или, иными словами, максимальную возможную поставку в клетку (1,1) таблицы поставок: x ₁₁ = min {60, 20} = 20. После этого спрос первого потребителя полностью удовлетворен, а потому первый столбец таблицы поставок выпадает из последующего рассмотрения (заполненные клетки будем перечеркивать, как в табл. 7.2); клетки, выпавшие из последующего рассмотрения, перечеркнуты штриховой линией. В таблице поставок найдем "северо-западный" угол — клетку (1,2), и дадим туда максимально возможную поставку. Учитывая, что первый поставщик уже отдал 20 единиц груза, и у него осталось только 40 = 60 — 20 единиц груза, получаем, что х ₁₂=min{40,110} = 40. После этого мощность первого поставщика полностью реализована и из рассмотрения выпадает первая строка таблицы поставок [перечеркиваем сплошной линией клетку (1,2) и штриховой линией оставшиеся свободные клетки первой строки]. В оставшейся таблице снова находим "северо-западный угол" и т.д. В результате получаем следующее исходное распределение поставок:

Таблица 7.2

Число заполненных клеток в полученном распределении оказалось равным m + n - 1 = 3 + 4 - 1 = 6, т.е. числу основных (базисных) переменных. Это, конечно, не случайно. Дей­ствительно, на каждом шаге (кроме последнего) данного мето­да из рассмотрения выпадали либо строка, либо столбец, а на последнем шаге и столбец, и строка. Поэтому число запол­ненных клеток (число шагов) на единицу меньше, чем сумма числа строк и столбцов таблицы поставок, т.е. равно m + n - 1. Оказывается (см. теорему 7.2), что эта же особенность шагов метода "северо-западного" угла является причиной того, что полученное распределение является базисным.

Метод "северо-западного угла" имеет существенный недоста­ток: он построен без учета значений коэффициентов затрат задачи. С другой стороны, данный метод допускает модификацию, лишенную этого недостатка: на каждом шаге максимально возможную поставку следует давать не в "северо-западную" клетку оставшейся таблицы, а в клетку с наименьшим коэффициентом затрат. При этом распределение поставок оказывается, вообще говоря, ближе к оптимуму, чем распределение, полученное по методу "северо-западного угла". Такой метод получения опорного плана называется методом наименьших затрат. Рассмотрим этот метод на следующем примере.

Пример 7.3. Найти методом наименьших затрат первоначальное распределение поставок в задаче из примера 7.1.

Решение. Находим в таблице поставок клетки с наименьшим коэффициентом затрат. Таких клеток две - (1,1) и (2,1) с коэффициентами затрат, равными 1. Сравним максимально возможные поставки для этих клеток: для клетки (1,1) х ₁₁= min{60,20} = 20, для клетки (2,1) x ₂₁ = min{ 120,20} = 20. Так как они совпадают, то максимально возможную поставку даем в любую из них. Например, даем поставку, равную 20 единицам, в клетку (2,1). В результате спрос первого потребителя удовлетворен, и первый столбец таблицы поставок выпадает из последующего рассмотрения (см. табл. 7.3).

Таблица 7.3

В оставшейся таблице наименьшим коэффициентом затрат обладают две клетки; с ₁₂= с ₂₄ = 2. Сравним максимально возможные поставки для этих клеток: для клетки (1,2) х ₁₂ = min {60,110} = 60; для клетки (2,4) х ₂₄ = min{120 - 20, 110} = ⁼ 100. Даем поставку в клетку (2,4), для которой максимально возможная поставка оказалась больше: х ₂₄ = 100. При этом из рассмотрения выпадает вторая строка таблицы поставок (см. табл. 7.4). Аналогично, продолжая заполнение таблицы поставок шаг за шагом, получаем х ₁₂ = min{40,110} = 60, х ₃₂⁼ min{100,110 -60} = 50, х ₃₄ = min{ 100 - 50,110 - 100} = 10, x ₃₃ = min {100 - 60,40} = 40 (см. табл. 7.5).

Сравним найденное распределение поставок с распределением, полученным для той же задачи по методу "северо-западного" угла (пример 7.2, табл. 7.2). Вычислим для каждого из этих распределений суммарные затраты в денежных единицах:

в примере 7.2

в примере 7.3 .

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

Таблица 7.4

Таблица 7.5

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

Из теоремы 7.2 следует, что методы "северо-западного" утла и наименьших затрат приводят к базисным распределениям поставок, если на каждом (кроме последнего) шаге из рассмотрения выпадает либо одна строка, либо один столбец.

Рассмотрим теперь те особые случаи, когда на некотором шаге заполнения из рассмотрения выпадают одновременно и строка, и столбец. Укажем, как следует поступать, чтобы метод заполнения по-прежнему удовлетворял условиям теоремы 7.2, и получаемое распределение поставок было базисным.

Пример 7.4. Найти первоначальное базисное распределение поставок для следующей транспортной задачи (табл. 7.6):

Таблица 7.3

Воспользуемся методом "северо-западного" угла. На первом шаге следует дать поставку, равную 20 единицам, в клетку (1,1). В результате будет удовлетворен спрос первого потребителя и из рассмотрения выпадет первый столбец. На втором шаге поставку в 10 единиц следует дать в клетку (1,2). При этом из последующего рассмотрения выпадают и первый поставщик (который реализовал остатки своего груза), и второй потребитель, полностью удовлетворивший свой спрос. Продолжая использовать метод "северо-западного" угла, мы дополним таблицы поставок, но число заполненных клеток окажется меньше, чем число основных (базисных) переменных, равное m + n - 1 = 3 + 3- 1 = 5. Такое распределение не будет базисным, и для продолжения решения распределительный метод будет неприемлем. Избежать этого можно, используя следующий искусственный прием.

Разобьем второй шаг на два шага. Допустим, что после поставки в клетку (1,2) из рассмотрения выпадает, например, только первая строка. Для того, чтобы вывести из рассмотрения второй столбец, делаем еще один шаг: даем нулевую (фиктивную) поставку в произвольную, но не вычеркнутую клетку второго столбца, например, в клетку (2.2). После таких трех шагов имеем табл. 7.7.

Таблица 7.7

Аналогично, можно было допустить, что после второго шага израссмотрения выпал только второй столбец. Тогда на третьем шаге нулевую поставку следует дать в произвольную, но не вычеркнутую клетку первой строки.

При последующем заполнении таблицы поставок используем метод "северо-западного" угла обычным образом. Окончательно получаем распределение поставок (табл. 7.8).

Таблица 7.8

Перечеркнутые клетки, отвечающие базисным переменным, и в дальнейшем будем называть заполненными, несмотря на то, что среди них возможны клетки с нулевыми поставками.

Рассмотренный искусственный прием применяется также при методе наименьших затрат, если при использовании этого метода на некотором шаге из рассмотрения выпадают одновременно и строка, и столбец.