Методические указания по изучению дисциплины и выполнению контрольной работы (стр. 7 из 14)

Цель ТЗ - минимизировать общие затраты на реализацию плана перевозок, которые можно представить функцией:

(4.7)

Итак, математически ТЗ ставится так.

Даны система ограничений (3.4) и (3.5) (ограничения (3.5) отражают тот факт, что весь груз от всех поставщиков должен быть вывезен, а ограничения (3.4) отражают тот факт, что каждый потребитель должен получить ровно столько груза, сколько ему необходимо) при условии (3.6) и линейная функция (3.7). Найти такое неотрицательное решение, при котором линейная функция (4.7) принимает минимальное значение.

Для того, чтобы ТЗ (3.4)-(3.7) имела допустимые планы, необходимо и достаточно выполнение равенства (3.1)

Решение транспортной задачи состоит из двух этапов:

1 этап. Нахождение начального плана перевозок (x_ij),

удовлетворяющего ограничениям (3.4)-(3.6);

2 этап. Улучшение начального плана перевозок и получение оптимального плана перевозок (x_ij),

доставляющего минимум функции (3.7).

3.3. Построение исходного опорного плана.

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

то это число а записываем в соответствующую клетку (i, j) и считаем ее занятой или базисной, если x_ij = 0 то клетку (i,j) оставляем свободной.

Метод «северо-западного угла». Определение значений x_ij начинается с левой верхней, условно называемой северо-западной, клетки (1,1) табл.1. Находим x₁₁=min(a_1, b₁).

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

2) если а₁>b₁, то х₁₁=b₁, столбец 1 исключается из дальнейшего рассмотрения (первый потребитель В₁ будет полностью удовлетворен), а наличие груза у первого поставщика a₁ уменьшается на b₁;

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

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

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

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

Метод минимального элемента. В отличии от метода северо-западного угла данный метод учитывает при построении исходного плана стоимости перевозок. В ряде случаев он позволяет получить лучшее с точки зрения критерия оптимальности решение, сокращая количество итераций для получения оптимального плана.

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

Переменной, отвечающей выбранной клетке, присваивается минимальное из двух возможных значений: x_ij=min(a_i,b_j). Соответствующая строка или столбец исключаются из дальнейшего рассмотрения, а потребность потребителя или наличие груза у поставщика уменьшается на выбранную величину. Если для выбранной клетки с минимальной стоимостью перевозки наличие груза у поставщика равно потребности потребителя, то из дальнейшего рассмотрения исключаются и строка и столбец (это приводит к вырождению исходного плана).

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

Проверка плана на вырожденность и расстановка ( в случае вырожденности плана) нулей осуществляется так же, как это описано для метода северо-западного угла.

Для нахождения оптимального плана перевозок необходимо уметь оценивать полученный план на оптимальность. Как это сделать, не имея в распоряжении всех возможных планов перевозок, которые можно было бы сравнить между собой? Для оценки плана на оптимальность вводится понятие косвенных затрат. Косвенные затраты - это затраты, получаемые для маршрутов, по которым не осуществляются перевозки при данном плане. Рассчитанные косвенные затраты сравниваются с реальными затратами, которые имели бы место, если бы перевозки по данным маршрутам осуществлялись. Если для всех невыбранных маршрутов косвенные затраты не меньше реальных, то данный план перевозок является оптимальным. Если хотя бы для одного маршрута косвенные затраты меньше реальных, то план перевозок может быть улучшен путем введения в него данного маршрута. Ввод нового маршрута в план перевозок соответствует вводу в список базисных переменных переменной транспортной задачи, соответствующей этому маршруту. Эти рассуждения лежат в основе ряда методов, применяемых для нахождения оптимального плана перевозок. Рассмотрим один из них - метод потенциалов.

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

1. Построить опорный план по одному из правил.

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

3. Проверка плана на оптимальность.

3.1. Определение потенциалов поставщиков и потребителей. Для всех занятых клеток рассчитываются потенциалы по формуле

(3.8)

где u_i - потенциалы поставщиков (строк), v_{j -} потенциалы потребителей (столбцов).

Так как всех занятых клеток должно быть m+n-1, т.е. на единицу меньше числа потенциалов (их m+n), то для определения чисел u_i, v_j необходимо решить систему из m+n-1 уравнений u_i+v_j=c_ij c m+n неизвестными. Система неопределенная, и, чтобы найти частные решения, одному из потенциалов придают произвольное числовое значение (обычно полагают u₁=0), тогда остальные потенциалы определяются однозначно.

3.2. Для всех свободных клеток рассчитываются оценки по формуле

) (3.9)

Здесь

- реальные тарифы, а - косвенные тарифы.

Если все s

то полученный план является оптимальным. При этом, если все s_ij>0, то полученный оптимальный план единственный. В случае, если хотя бы одна оценка s_ij=0, имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции. Если хотя бы для одной свободной клетки , то план может быть улучшен. Переход к шагу 4.

4. Среди отрицательных оценок выбирается минимальная. Например, для клеток (i, j) и (k,l) имеем оценки: s_ij=-2, s_kl=-4. В этом случае наиболее потенциальной (перспективной) является клетка (k,l). Экономически оценка показывает, на сколько денежных единиц уменьшатся транспортные расходы от загрузки данной клетки единицей груза. Так, от загрузки клетки (i,j) единицей груза транспортные расходы уменьшаются на

денежных единиц, а от загрузки единицей груза клетки (k, l) - на денежных единиц. Эффективность плана от загрузки потенциальной клетки грузом в единиц составит денежных единиц.

Для наиболее перспективной свободной клетки (клетки с min отрицательной оценкой) строится замкнутый цикл. Для этого из выбранной свободной клетки проводится по строке или столбцу прямая линия до любой занятой клетки, затем под углом 90

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

5. В вершинах цепи, чередуя проставляются знаки «+» и «-», начиная с выбранной свободной клетки (в нее помещают знак «+»). В клетках со знаком «-» выбирается минимальная поставка (

, которая перераспределяется по цепи: там, где стоит знак «+» она прибавляется, а где «-» - отнимается. В результате чего баланс цикла не нарушается. Исходная свободная клетка становится занятой, а клетка в которой выбрана минимальная поставка - свободной (рис.3.1 а, б)