1.3. Критерий (правило) отбора первоначального опорного базисного плана. Особые случаи получения первоначального опорного плана
Из линейной алгебры известно, что если ранг системы линейных уравнений равен r и некоторые r переменных системы выражены через остальные переменные, то эти r переменных можно взять за основные (базисные).
Критерий (правило) отбора первоначального опорного базисного плана трактует следующая теорема .
Теорема 13.2. Если на каждом шаге заполнения таблицы поставок (любым из двух методов) возникает только одна заполненная клетка и при этом из последующего рассмотрения на каждом шаге (кроме последнего) выпадает либо одна строка, либо один столбец, то переменные, соответствующие заполненным клеткам можно принять за базисные.
Из условия данной теоремы следует, что число заполненных клеток таблицы поставок равно n + m – 1, т.е. равно рангу системы (13.9),(13.10). Поэтому теорема будет доказана, если показать, что переменные, соответствующие заполненным клеткам, могут быть выражены через переменные , соответствующие свободным клеткам.
Предположим, что переменные, соответствующие заполненным клеткам, возникшие на первых t шагах применения метода, (t = 1,2,…,m+ n -2), можно выразить через переменные, соответствующие свободным клеткам тех строк и столбцов, которые выпадали из рассмотрения на этих первых t шагах.
Пусть также на (t + 1) – м шаге реализации метода заполнена (p,q) – я клетка и из дальнейшего рассмотрения выпала, например, р – я строка. Выразим переменную xpq из уравнения баланса по р – й строке
. (13.4)
Пусть среди переменных правой части (13.4) имеются переменные, соответствующие клеткам, заполненным на первых t шагах. Тогда по предположению их можно выразить через переменные, соответствующие свободным клеткам тех строк и столбцов, которые были удалены при реализации первых t шагов.
В случае же, если на (t+1) –м шаге из дальнейшего рассмотрения выпал q – й столбец, то xpq следует выразить из уравнения баланса по q – му столбцу.
Подобные рассуждения следует последовательно провести для каждого из шагов заполнения таблицы поставок. Этим теорема 13.2 будет доказана.
Из теоремы 13.2 следует, что методы северо-западного угла и наименьших затрат приводят к базисным распределениям поставок в том и только в том случае, если на каждом (кроме последнего) шаге заполнения таблицы поставок из дальнейшего рассмотрения выпадет строго либо одна строка, либо один столбец.
Однако, как показывает практика, это условие выполняется далеко не всегда. Рассмотрим особые случаи, когда на каком – то конкретном шаге из дальнейшего рассмотрения выпадают одновременно и одна строка и один столбец. Покажем, что необходимо делать для того, чтобы и в этом случае получающийся план поставок был бы базисным (опорным).
Задача 13.2. Получить опорный план распределения поставок для транспортной задачи, заданной таблицей 13.4.
Решение. Задачу будем решать методом северо-западного угла.
На первом шаге спланируем поставку 20 единиц груза от поставщика 1, запасы которого составляют 30 единиц груза, получателю 1 (х11 = 20) .
Таблица 13.4 – Исходные данные для задачи 13.2.
|
20 |
10 |
40 |
30
|
1 20 |
3 10 |
5 |
30
|
3 |
3 |
2 |
10
|
4 |
1 |
2 |
Запишем в клетку (1.1) х11 = 20. При этом потребности первого получателя будут удовлетворены полностью и клетки (2.1) (3.1) перечеркнем пунктирной линией. Из дальнейшего рассмотрения выпадет столбец 1.
На втором шаге спланируем перевозку оставшихся у первого поставщика 10 единиц груза второму потребителю. Запишем в клетку (1.2) х12 = 10. При этом складывается ситуация, когда одновременно выполняются потребности второго получателя и исчерпываются возможности первого поставщика, т.е на одном (не последнем) шаге из дальнейшего рассмотрения должны выпасть первая строка и второй столбец.
Продолжая использовать метод северо-западного угла, мы, конечно, получим распределение поставок, но число заполненных клеток, а следовательно, и число базисных переменных будет меньше, чем m + n -1 = 3=3 -1 = 5. Такое распределение не будет базисным и не может считаться первоначальным опорным планом.
Для того, чтобы все-таки можно было решить такую задачу предложено использовать следующий примем.
Разобьем шаг 2 на два шага. Предположим, что после поставки в клетку (1.2) 10 единиц груза из дальнейшего рассмотрения выпадет только первая строка. Для того, чтобы все же вывести из рассмотрения второй столбец, делаем еще один шаг: даем нулевую (фиктивную) поставку в произвольную, но не вычеркнутую клетку второго столбца, например в клетку (2.2).
В результате получим таблицу 13.5.
Таблица 13.5 – Таблица распределения поставок после третьего шага
|
20 |
10 |
40 |
30
|
1 20 |
3 10 |
5 |
30
|
3 |
3 0 |
2 |
10
|
4 |
1 |
2 |
Отметим, что аналогично можно было предположить, что после второго шага из дальнейшего рассмотрения выпал только второй столбец. Тогда на третьем шаге нулевую поставку следует сделать в произвольную, но не вычеркнутую клетку первой строки.
Дальнейшее распределение выполним классическим методом северо-западного угла и получим распределение поставок, показанное в таблице13.6.
Таблица 13.6 – Окончательная таблица распределения поставок в задаче 13.2
|
20 |
10 |
40 |
30
|
1 20 |
3 10 |
5 |
30
|
3 |
3 0 |
2 30 |
10
|
4 |
1 |
2 10 |
Анализируя таблицу 13.6, можно отметить, что ней имеется ровно m + n – 1= = 3 + 3 – 1 = 5 заполненных клеток, хотя одна из них с нулевой (фиктивной) поставкой. Тогда в соответствии с теоремой 13.2 такое распределение поставок является базисным, и полученный первоначальный план распределения является опорным планом.
Отметим, что аналогичным приемом можно воспользоваться и в случае использования метода наименьших затрат в том случае, если на каком – то шаге из дальнейшего рассмотрения выпадают одновременно и строка, и столбец. * * *