3.4Методы составления первоначального опорного плана тз

Симплексный подход как метод последовательного улучшения плана начинается с составления первоначального решения задачи. Для ТЗ существует 3 основных метода составления первоначального опорного плана.

Метод Северо-Западного угла

I. Верхний левый элемент таблицы x₁₁ равен наименьшему из запаса a₁ и заказа b₁. Возможны три случая:

1. a₁<b₁ тогда x₁₁=a₁, и заполняем нулями оставшуюся часть первой строки;

2. a₁>b₁ тогда x₁₁=b₁, и заполняем нулями оставшуюся часть первого столбца;

3. a₁=b₁ тогда x₁₁=a₁=b₁, и заполняем нулями оставшуюся часть первой строки и оставшуюся часть первого столбца.

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

Метод минимальной стоимости

Нумеруем клетки таблицы в порядке возрастания их тарифов. На каждом шаге заполняется элемент с наименьшим номером из незаполненной части таблицы аналогично методу Северо-Западного угла.

Метод двойного предпочтения

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

3.5Метод потенциалов решения тз

Решение транспортной задачи осуществляется методом потенциалов. Потенциал – это некоторое число, поставленное в соответствие поставщику (потенциал поставщика) и потребителю (потенциал потребителя).

Обозначим потенциал поставщика A_i как U_i, а потенциал потребителя B_j как решение ТЗ методом потенциалов основывается на следующей теореме:

Теорема о потенциалах

Опорный план ТЗ будет оптимален, если

1. Для каждой клетки с ненулевой перевозкой (загруженной) сумма потенциалов будет равна тарифу

U_i + V_j=с_ij

2. Для каждой клетки с нулевой перевозкой (незагруженной) сумма потенциалов будет меньше или равна тарифу

U_i+ V_jср_ij

Сумма потенциалов в незагруженной клетке называется косвенным тарифом и обозначается с^*_ij

с^*_ij =U_i+ V_j

Идея метода состоит в следующем. Составляется первоначальный опорный план, по которому считается выполненным первое условие оптимальности. Проверяется выполнение второго условия и если оно не выполняется, строится новый план путем загрузки клетки с недоиспользованным потенциалом. Перераспределение осуществляется по циклу – прямоугольному замкнутому контуру, вершины которого занятые клетки и который возникает в таблице при добавлении к занятым клеткам клетки, выбранной для загрузки. Таким образом, цикл – совокупность клеток, представляющая собой прямоугольный многоугольник. Вершины цикла – занятые клетки, и для каждой вершины существует еще хотя бы одна занятая клетка и в ее строке, и в ее столбце. Цикл при условии невырожденности плана существует и единственен. Его вид может быть различен (рис. 3.2).

Рис. 3.2. Виды циклов, возникающих при перераспределении перевозок

в транспортной таблице

Алгоритм метода потенциалов решения ТЗ

1. Составляем первоначальный план ТЗ одним из выше описанных методов (Северо-Западного угла, минимальной стоимости или двойного предпочтения).

2. В невырожденном опорном плане должно быть n+m–1 занятых клеток. Если в опорном плане занятых клеток меньше, то недостающее число их добавляем из числа незанятых, помечая их * и считая занятыми с нулевыми первозками. При выборе добавляемых к плану клеток:

• в таблице не должен возникать цикл;

• прямой тариф добавляемой клетки должен быть как можно меньше;

• клетка не должна входить в занятые клетки предыдущих планов.

(Последние два правила носят рекомендательный характер).

3. По занятым клеткам (с ненулевыми перевозками) составляем уравнения потенциалов вида

U_i+ V_j=с_ij.

4. Количество переменных в полученной системе n+m – число потенциалов поставщиков + число потенциалов потребителей. Поэтому одному из неизвестных потенциалов задается произвольное значение (чаще всего 0) и разрешается система уравнений (находятся все потенциалы).

5. Через полученные значения потенциалов для пустых клеток вычисляются косвенные тарифы

с^*_ij =U_i+ V_j.

6. Для пустых клеток находятся разности между косвенным и прямым тарифом клетки

с^*_ij – с_ij.

Если все эти разности отрицательны, то полученный план оптимален (выполняется условие U_i+ V_jс_ij). Если существуют клетки с положительными разностями косвенного и прямого тарифов, то производим перераспределение груза по следующему алгоритму.

Построение цикла и перераспределение груза

Находим незанятую клетку с максимальной положительной разностью между косвенным и прямым тарифом и отмечаем ее знаком +, как бы присоединяя ее к занятым. (Если таких значений несколько, желательно выбирать клетку с меньшим тарифом). Количество занятых клеток в таблице, таким образом становится равным n+m, что обуславливает в ней наличие единственного цикла. Цикл – это совокупность клеток, представляющая собой многоугольник. Вершины цикла – занятые клетки, и для каждой вершины существует еще хотя бы одна занятая клетка и в ее строке, и в ее столбце. Отыскиваем такой цикл и от клетки, помеченной знаком + (с максимальной положительной разностью между косвенным и прямым тарифом), поочередно помечаем вершины цикла знаками – и +.

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

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

7. Переходим к шагу 2.

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