Материал: 3376

Цепью называется упорядоченный набор клеток, обладающих тем свойством, что любые две соседние клетки лежат в одной строке или в одном столбце, причѐм никакие три клетки набора не лежат в одной строке или в одном столбце. Если начальная и конечная клетки цепи лежат в одной строке или в одном столбце, то цепь называется циклом. Набор клеток называется ациклическим, если в нѐм не содержится ни одного цикла. Ациклический набор клеток называется невырожденным, если в нѐм содержится ровно клетка. В противном случае ациклический набор клеток называется вырожденным.

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

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

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

Транспортная задача называется невырожденной, если все еѐ опорные планы являются невырожденными.

Общий метод построения опорных планов состоит в следующем:

выбираем какую-либо клетку i0 , j0 (т.е. клетку в строке с номером i0 и в

Тогда все остальные клетки строки i0 нечем заполнять (они останутся пустыми). Из оставшихся клеток снова выбираем какую-либо клетку i1, j1 и

повторяем всѐ для неѐ. При этом снова строка или столбец будут иметь пустые клетки, все, кроме клетки i1, j1 . И так далее. Полученный план будет опорным.

Обычно применяются две реализации общего метода:

19

1)метод северо-западного угла, при котором на каждом шаге выбирается для заполнения клетка, стоящая в северо-западном углу оставшейся для заполнения части таблицы;

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

Опишем метод потенциалов решения невырожденной транспортной задачи.

Первый шаг.

Методом северо-западного угла или методом минимального элемента находим опорный план.

Второй шаг.

Для заполненных клеток i, j этого плана составляем систему уравнений

ui v j cij ,

где ui – переменная, соответствующая строке с номером i , v j – переменная,

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

Третий шаг.

Проверяем, удовлетворяет ли найденная система потенциалов

план является оптимальным.

Четвертый шаг.

20

неравенство (6.4) не выполнено), то находим цикл, начинающийся в этой клетке, в котором все остальные клетки заняты. Клетки цикла поочередно помечаем знаками + и –, начиная с клетки i0 , j0 , помеченной знаком +.

Находим наименьшую из величин перевозок, помеченных знаком –.

Строим новый план: в клетку i0 , j0 вписывается указанная величина; в

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

Для нового плана снова проделываем шаги 2, 3 и. если надо, 4.

За конечное число операций получаем оптимальный план.

Пример 6.1. В городе имеются 4 хлебозавода B1 , B2 , B3 , B4 , которые снабжаются мукой тремя мелькомбинатами A1 , A2 , A3 . Требуется распределить поставки так, чтобы транспортные расходы были минимальными. Все необходимые данные указаны в таблице 12.2 (стоимости перевозок указаны в рублях).

21