3.2. Методы составления исходного опорного плана.

Первым шагом в решении транспортной задачи является составление исходного опорного плана, который последовательно улучшается до получения оптимального решения. При составлении исходного плана по методу северо-западного угла, первой загружается клетка (1; 1). Если закрывается строка, то следующей загружается клетка (2; 1); если же закрывается столбец, то следующей загружается клетка (1; 2). Итак, каждый раз загружается клетка, соседняя, либо по строке, либо по столбцу (в зависимости от конкретных данных задачи). Последней будет загружена клетка (m, n). В результате загруженные клетки расположатся вдоль диагонали (1, 1)–(m, n), поэтому способ "северо-западного угла" называют еще диагональным способом. Недостатком данного метода является то, что он не учитывает значения элементов Aij матрицы транспортных расходов, в результате чего полученное этим методом начальное распределение (начальный план перевозок) может быть весьма далеким от оптимального. Составление исходного плана методом минимальных элементов. Первой в распределительной таблице загружается клетка с наименьшим тарифом. Далее загружается клетка той же строки (столбца) со следующим по величине тарифом и т.д. Поскольку при заполнении таблицы учитываются величины тарифов, то, как правило, построенный план оказывается ближе к оптимальному, нежели построенный способом северо-западного угла. После составления исходного плана определяется его вырожденность. Вырождение матрицы наступает тогда, кода при особых условиях дальнейшее её решение невозможно. В данном типе задач вырождение по является при числе занятых клеток меньшем, чем (m + n-1) где m –число поставщиков, а n – число потребителей. Для сохранения неизменным числа занятых клеток m + n.

3.3 Методы нахождения оптимального плана.

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

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

Построив замкнутый контур для свободной клетки, вычисляем алгебраическую сумму

где – свободная клетка. Критерием оптимальности плана будут

все алгебраические суммы

Наиболее распространенным методом решения транспортной задачи (6.2) – (6.5) является метод потенциалов. По данному опорному плану, у которого число занятых клеток равно m+n-1, каждому поставщику и потребителю придается число, называемое потенциалом. Потенциалы выбираются так, чтобы их сумма для каждой загруженной грузом клетки была равна тарифу перевозки единицы груза. Так, если клетка (i; k) базисная (занятая), то

(3.6)

Решив систему из уравнений вида получим значения потенциалов соответственно i-го поставщика и k-го потребителя. Далее вычислим оценки свободных клеток по формуле

(3.8)

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

Рисунок 3.1.

Например, цикл имеет вид, показанный на рисунке 3.1, где клетка "-" и т.д.; знаки чередуются. В отрицательных вершинах цикла определяем наименьшую загрузку клетки, т.е. min(20, 30) = 20.

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

Рисунок 3.2

Тема № 4. Дискретные экономико-математические модели