X ij ≥ 0

Необходимо составить такой план перевозок, при котором стоимость перевозимых грузов будет минимальной.

_{m n}

Z = å å c_ij x _ij → min

^{i=1 j=1}

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

Когда выполняется 3 условие - задача закрыта.

Если 3 условие не выполняется - задача открыта.

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

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

Особенности транспортной задачи:

1. Ограничения представлены в виде уравнений.

2. Коэффициенты при неизвестных в ограничениях равны единице.

3. Каждая неизвестная входит только в два уравнения по строке и по столбцу.

4. Любое решение, выполняющее 1,2,3,4 условия транспортной задачи и содержащее не более m+n-1 называется допустимым. Если более - неверно, менее - вырожденная.

Допустимое решение, обращающее целевую функцию в min, называется оптимальным.

Распределительным методом могут решаться следующие землеустроительные задачи:

1. Определение оптимальных планов перевозки продукции от производителя к потребителю.

2. Рациональное размещение жилых зон, объектов промышленности, транспорта, соц-культ. быта и пр.

3. Оптимизация транспортных потоков населения.

4. Устранение недостатков землепользований и землевладений.

Порядок решения задачи распределительным методом:

1. Постановка задачи с формулированием цели.

2. Сбор исходной информации и ее обработка.

3. Заполнение исходной матрицы и составление первоначального опорного плана.

4. Вычисление цены плана и анализ его на оптимальность.

5. Последовательное улучшение плана для получения оптимального.

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

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

- минимального элемента;

- северо-западного угла;

- аппроксимации и др.

Любой из них обеспечивает получение опорного решения и в этом смысле все методы равноценны. Однако, степень "близости" опорных решений, получаемых различными методам, к оптималь­ному решению может быть существенно различной. Наилучшие по этому критерию опорные решения дает, как правило, метод аппроксимации.

Алгоритм метода минимального (максимального) элемента:

1. Из всех значений Cij матрицы выбирается наименьшее (наибольшее).

2. В клетку с наименьшим (наибольшее) значением Cij ставится требуемая поставка груза.

3. Выбирается следующая по величине Cij и заносится поставка груза.

4. Операция повторяется до тех пор, пока весь груз не будет распределен по маршрутам.

Алгоритм метода северо-западного угла:

1. Первой заполняется верхняя левая (т. е. северо-западная) клетка.

2. Далее заполняется следующая (в зависимости от того, что осталось в наличии запасы A1 или потребности B1) слева или снизу клетка.

3. Операция повторяется до тех пор, пока весь груз не будет распределен по маршрутам.

Алгоритм метода апроксимации (на min):

1. По каждой строке и столбцу находятся два минимальных значения Cij.

2. Определяется их разность m_i, m_j.

3. Из всех разностей выбирается наибольшая Km.

4. По строке или столбцу, где наибольшая разность, в клетку где размещается самое наименьшее значение C_ij ^min записывают поставку груза (требуемую).

5. Далее повторяют с вычисление новых разностей до получения опорного плана.

6. Полученное решение проверяют по числу занятых клеток. Если в ходе применения приведенного алгоритма на каких-либо шагах окажется, что Ai=0 и Bj=0, то опорное решение будет вырожденным - некоторые занятые клетки будут заполнены нулями. Формальным источником вырожденности является равенство типа:

А1 =В1, А1 = В1 + В2, А1+А2 = В1 + В2

Как уже отмечалось, в случае, когда Ai=0 и Bj=0 можно вычеркнуть либо i-ю строку, либо j-й столбец. Для того, чтобы приблизить опорное решение к оптимальному, целесообразно выполнить следующее правило:

в i-й строке, исключая рассматриваемую клетку, определить наименьшее значение Сij(C’ij), в j-м столбце, исключая рассматриваемую клетку, также определить наименьшее значение Сij(C’ij), если Сij < C’ij, то вычеркиваем j-й столбец, в противном случае – i-ю строку.

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

При решении задач на максимум приведенный алго­ритм меняется только в двух пунктах: в п.1 вместо минимальных находят два максимальных значения Сij, а в п.4 заполняет клет­ку не с наименьшим, а с наибольшим значением Cij.

При решении могут возникнуть следующие случаи:

1. Если имеется несколько наибольших разностей, то предпочтение отдается той, для которой есть C_ij ^min.

2. Если C_ij ^min имеется по нескольким Km, то для решения берут ту клетку, в которую можно занести большую поставку груза.

3. Если и в этом случае наблюдается полное равенство, то выбирают любую клетку.

3. Методы улучшения опорного плана.

При использовании метода потенциалов производят вычисление условных оценок (потенциалов) a _i, b _j.

Условный потенциал - это специальная оценка грузов, расположенных в пунктах назначения и отправления.

Потенциалы могут вычисляться по формуле:

a _i + С_ij = b _j

Такое условие записи для каждой занятой клетки, где Xij > 0

Где одному потенциалу присваивается любое значение.

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

При решении задач на минимум.

План оптимален в том случае, если для свободных клеток выполняется условие:

a _i + С_ij > b _j

В случае неоптимальности плана его улучшают, при этом для клетки, где не выполняется условие отрицательности, строится многоугольник (прямоугольник).

Правила построения многоугольника:

1. Стороны многоугольника должны пересекаться под прямым углом и располагаться по столбцам таблицы.

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

3. В начале вершины, лежащей в испытуемой клетке, присваивается знак плюс, далее знаки чередуются.

4. Среди всех грузов находящихся в клетках с отрицательными вершинами, выбирается min значение Хmin. Далее с соответствующими знаками клеток производится алгебраическое сложение производных.

Улучшение обычно начинают с той клетки, характеристика которой по модулю наибольшая.

Характеристика свободных клеток вычисляется по формуле:

åij = (a _i + С_ij) - b _j

это способствует наименьшему количеству итераций.

После каждого улучшения производят вычисление целевой функции с контролем по формулам:

_{m n}

Z = å å c_ij x _{i j} ------> min

^{i=1 j=1}

_{m n}

Z = å b _j b _j - å a _i a _i

^{j=1 i=1}

5. Решение задач с дополнительными ограничениями.

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

Их может быть несколько:

1. Требуется ввести конкретное условие в заданную клетку

x _{i j} = d _{i j}

Если в определенной клетке установлено определенное количество ресурса, то в этом случае до начала решения в исходной матрице делают следующие преобразования:

- из соответствующего столбца потребностей и строки ресурсов вычитают оговоренное число (dij); и для того, чтобы данная клетка не вошла в дальнейшее решение, блокируют оценку данной клетки, т.е. делают оценку этой клетки очень маленькой величиной при решении задач на max; или очень большой при решении на min.

2. x _{i j}> d _{i j}

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

3. x _{i j}< d _{i j}

Если в определенную клетку следует записать не более определенного количества ресурса, то в клетке делается пометка и задача решается как предусмотрено алгоритмом. Корректировка ответа производится по окончании решения.

4. d* _{i j}< x _{i j}< d** _{i j}

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

Пункт назнач. Пункт отправ.	I	II	III	IV	Запасы	Столбец разностей
	1025	20 Х	13	15 Х	1000	=
	25 500	18 .	16 .	15 Х	6000
	22	16 Х	14 Х	13 Х		=
	26 Х	. 14 Х	. 12	10	1800	=
Потребность	2000 1900 1700		3500	1500
Строка разностей	31	24	24	3

..

- многоугольник

..

_{m n}

å a_ij = å b _ij

^{j=1 i=1}

MIN

X₁₁ = 100 (блокируем оценку клетки)

X₂₁ > 200

X₃₃ < 400

100 < X₄₂ < 200

а) m+n-1

б) b _j +a _i = С_{i j} (занятые клетки)

a _i + b _j -С_ij < 0 min

> 0 max

6. Вариантные решения задач с использованием матрицы оптимального плана.

А. Альтернативные решения с отклонением целевой функции от экстремума.

Не всегда возможно выполнить дополнительные условия, сохранив оптимальность решения. Приведём фрагмент оптимального решения транспортной задачи:

Пусть, например, задано дополнительное условие 116≤X₂₂≤450. Клетка (2,2) уже занята. Проведём проверку дополнительных условий:

96≤450, условие выполнено; 96≤116, условие не выполнено. Исходя из этого, нам необходимо увеличить ресурс клетки (2,2). Что позволит нам выполнить дополнительное условие, но приведёт к получению не оптимального решения. Оценим возможности увеличения ресурса. Возможно построение двух циклов: (2,2), (2,1), (1,1), (1,2) и (2,2), (2,4), (3,4), (3,2). В первом случае, по оценкам испытуемых клеток, (10+22) – (4+8), ухудшение опорного плана произойдёт на 20, на единицу перемещаемого ресурса, во втором, соответственно на 8. Следовательно выбираем второй вариант. Максимально возможный перемещаемый ресурс в построенном цикле X_min =290. Следует ли переместить именно 290? (Оба дополнительные условия выполняются!) Ни в коем случае. Чем больший ресурс мы переместим, тем сильнее нарушим оптимальность решения. Таким образом мы должны переместить только 20 (116-96). Окончательный вариант решения будет следующим:

В. Изменение уровней производства и потребления в отдельных пунктах при сохранении общего объёма производства.

Рассмотрим демонстрационный пример:

Один из районов города (второй) нуждается в дополнительном размещении пяти супермаркетов.

Супермаркет
Школа
…..
Завод

Где, X_{i j} - количество объектов, С_{i j} - стоимость строительства одного объекта.

Основной задачей рассматриваемого примера является снижение расходов на строительство, следовательно, надо перераспределять размещение школ находящихся в районе с С_{1 j} max, в данном случае это – район 4.

При этом мы:

· Выполним поставленное условие

· Обеспечим минимальное значение целевой функции с учётом дополнительных условий

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

С. Определение альтернативных оптимальных решений.

Поиск других оптимальных решений, зачастую представляет не малый практический интерес. Если в случае проверки опорного решения на оптимальность, оценка одной или нескольких свободных клеток оказалась равной нулю (σ _ij =0), то при перемещении ресурсов, по описанным выше правилам, из занятой клетки в свободную значение целевой функции не изменится, следовательно мы имеем одно или несколько альтернативных решений. Причём необходимо отметить, что возможно, как всего ресурса, так и его части. В первом случае мы будем иметь дело с оптимальным базисным, а во втором не базисным решением.

7. Примеры решения градостроительных и землеустроительных задач.

Задача № 1

Распределить объекты социальной инфраструктуры таким образом, чтобы количество их посещений в месяц было максимальным.