7.2. Нахождение опорного плана

Решение ТЗ, как и других ЗЛП, начинается с нахождения опорного плана. В отличие от ОЗЛП с произвольными ограничениями и минимизируемой функцией, решение ТЗ всегда существует.

Любая совокупность значений (x_ij) (i=1, ...,m; j=1, ...,n), удовлетворяющая условиям (2), (3) (так называемым «балансовым условиям»): все заявки удовлетворены, все запасы исчерпаны называется допустимым планом перевозок (решением).

Если полученное решение позволяет минимизировать расходы на транспортировку, т.е. если план (x_ij) среди всех допустимых планов приводит к наименьшей стоимости всех перевозок, то решение называется оптимальным или оптимальным планом.

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

Система ограничений закрытой ТЗ содержит m+n уравнений, связанных соотношением , и mn переменных. Не все m+n уравнений нашей задачи являются линейно независимыми. Так, складывая между собой почленно все уравнения (2) i=1,2,…,m и все уравнения (3) j=1,2,…,n, получаем два одинаковых уравнения. В транспортной таблице такое сложение равнозначно соответственно по членному сложению столбцов и почленному сложению строк.

Наличие в системе ограничений 2-х одинаковых уравнений говорит о ее линейной зависимости. Если одно из этих уравнений отбросить, то в общем случае система ограничений должна содержать m+n-1 линейно независимых уравнений.

Опорный план называется невырожденным, если он содержит m+n-1 положительных компонент (перевозок), иначе он называется вырожденным.

Таким образом, если каким-либо способом получен невырожденный опорный план ТЗ, то в матрице (i=1,2,…,m; j=1,2,…,n) значений его компонент положительными являются только m+n-1, а остальные равны нулю.

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

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

Как известно, базисным переменным, включенным в опорный план, соответствует система линейно независимых векторов.

Для проверки линейной независимости векторов условий, соответствующих компонентам допустимого плана, используют циклы.

Циклом называется такая последовательность клеток таблицы ТЗ (i₁,j₁),(i₁,j₂),(i₂,j₂),...,(i_k,j₁), в котором только две соседние клетки расположены в одном столбце или одной строке таблицы, причем последняя клетка находится в той же строке или столбце, что и первая. Построение циклов начинают какой-либо занятой клетки, вычерчивают вспомогательную линию, параллельную столбцам или строкам таблицы к другой занятой клетке, в которой возможен поворот под углом 90, и продолжают вычерчивание к следующей занятой клетке, стремясь возвратиться к исходной клетке. Если такой возврат возможен, то получен цикл и план является не опорным. Клетки, в которых происходит поворот под прямым углом, определяют вершины цикла.

Система векторов условий ТЗ линейно независима тогда и только тогда, когда из соответствующих им клеток таблицы нельзя образовать ни одного цикла. Следовательно, допустимый план ТЗ Х= (i=1,2,…,m; j=1,2,…,n) является опорным только в том случае, когда из занятых им клеток нельзя образовать ни одного цикла, все вершины которого лежат в занятых клетках.

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

Для проверки возможности образования цикла используется метод вычеркивания:

1. Если в строке или столбце таблицы одна занятая клетка, то она не может входить в какой-либо цикл, т.к. имеет только две клетки в каждой строке или столбце. Следовательно, можно вычеркнуть все строки таблицы, содержащие по одной занятой клетке, затем вычеркнуть все столбцы, содержащие по одной занятой клетке, далее вернуться к строкам и продолжить вычеркивание строк и столбцов.

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

Существует несколько схем построения первоначального опорного плана:

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

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

Существенный недостаток метода ”северо-западного” угла состоит в том, что он построен без учета значений стоимости перевозки единицы груза.