Переход от одного опорного решения к другому

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

Для свободной клетки, у которой строится цикл, все вершины которого кроме одной находятся в занятых клетках; углы прямые, число вершин чётное. Около свободной клетки цикла ставится знак (+), затем поочерёдно проставляются знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность, и т. д. до тех пор, пока не получим оптимальное решение.

Рассмотрим переход от одного опорного решения к другому на заданном примере.

Строим цикл для клетки (1, 3), имеющей положительную оценку. У вершин цикла ставим знаки (+) и (-) и записываем грузы:

У вершин со знаком (-) выбираем минимальный груз, он равен 60. Его прибавляем к грузам, стоящим у положительных вершин, и отнимаем от грузов, стоящих у отрицательных вершин. Получаем новый цикл:

Новое опорное решение:

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

Таблица 5.4

bi ai				ui
vj		-2

Имеем

Построим цикл для клетки с положительной оценкой :

Произведём перераспределение грузов:

Получим новое решение, которое занесём в табл. 5.5. Проверим его на оптимальность.

Таблица 5.5

bj ai				ui
vj		-2

Получим

Все оценки свободных клеток отрицательные, следовательно, решение оптимальное. Итак,

Стоимость транспортных расходов равна

усл. ед.

По сравнению с исходным опорным решением транспортные расходы уменьшились на 1610-1280=330 усл. ед.

Альтернативный оптимум в транспортных задачах

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

,

где .

Пример. На трёх складах имеется мука в количестве 60, 130 и 90 т, которая должна быть в течение месяца доставлена четырём хлебозаводам в количестве: 30, 80, 60, 110 т соответственно.

Составить оптимальный план перевозок, имеющий минимальные транспортные расходы, если стоимость доставки 1 т муки на хлебозаводы задана матрицей

.

РЕШЕНИЕ. Составим распределительную таблицу 5.6.

Таблица 5.6

bj ai					ui
						-1
vj

По методу минимального тарифа найдём исходное решение. Определим потенциалы строк и столбцов. Найдём оценки свободных клеток:

Так как , то перераспределим грузы относительно клетки (1, 2):

Занесём полученное перераспределение грузов в распределительную таблицу и вычислим потенциалы занятых и оценки свободных клеток (табл. 5.7).

Таблица 5.7

bj ai					ui
						-1
vj

Получим

Так как , то задача имеет альтернативный оптимум и одно из решений равно

.

Стоимость транспортных расходов составляет: усл. ед.

Произведём перераспределение грузов относительно клетки (3, 3):

Занесём в распределительную таблицу полученное перераспределение грузов, вычислим потенциалы занятых и оценки свободных клеток (табл. 5.8):

Таблица 5.8

bj ai					ui
						-1
vj

Получили ещё одно решение:

.

Стоимость транспортных расходов составит усл. ед.

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

Найдём элементы матрицы общего решения:

Итак,

.

Стоимость транспортных расходов составляет 1550 усл. ед.

Вырожденность в транспортных задачах

При решении транспортной задачи может оказаться, что число занятых клеток меньше, чем m + n – 1. В этом случае задача имеет вырожденное решение. Для возможного его исключения нужно ввести в свободную клетку с наименьшей оценкой нулевую поставку. Нуль помещают в такую клетку, чтобы в каждой строке и каждом столбце было не менее одной занятой клетки.

Пример. Фирма осуществляет поставку бутылок на 4 завода, занимающиеся производством прохладительных напитков. Она имеет три склада, причём на складе 1 находится 6000 бутылок, на складе 2 – 3000 бутылок и на складе 3 – 4000 бутылок. Первому заводу требуется 4000 бутылок, второму заводу – 5000 бутылок, третьему заводу – 1000 бутылок и 4 – 3000. Матрицей

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

Как следует организовать доставку бутылок на заводы, чтобы стоимость перевозки было минимальной?

РЕШЕНИЕ. Запишем исходные данные в распределительную таблицу, найдём исходное опорное решение по методу минимального тарифа. Число заполненных клеток равно 5, m+n– 1=6, следовательно, задача является вырожденной.

Для исключения вырожденности необходимо в какую-то клетку ввести нулевую поставку. Такая клетка становится условно занятой, она нужна для вычисления потенциалов занятых клеток. Эта клетка должна иметь наименьший тариф по сравнению с другими клетками, которые могут быть условно занятыми.

Поместим нулевую поставку в клетку (3, 2), после чего появится возможность вычислить все потенциалы.

Bj Ai					ui
1 6000
2 3000					-1
3 4000					-1
vj

Все оценки свободных клеток отрицательные, следовательно, получили оптимальное решение:

.

Стоимость транспортных расходов при данном оптимальном решении составит 52000 усл. ед.

Открытая транспортная задача

При открытой транспортной задаче сума запасов не совпадает с суммой потребностей, т. е.

.

При этом:

а) если , то объём запасов превышает объём потребления, все потребители будут удовлетворены полностью и часть запасов останется на складах. Для решения задачи вводят фиктивного (п + 1)-го потребителя, потребности которого .

Модель такой задачи будет иметь вид

при ограничениях:

б) если , то объём потребления превышает объём запасов, часть потребностей останется неудовлетворённой. Для решения задачи вводят фиктивного (т + 1)-го поставщика, потребности которого .

Модель такой задачи будет иметь вид

при ограничениях:

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

Определение оптимального варианта перевозки грузов

Задача. Составить оптимальный план перевозки грузов от трёх поставщиков с грузами 240, 40, 110 т к четырём потребителям с запросами 90, 190, 40 и 130 т. Стоимость перевозок единицы груза от каждого поставщика к каждому потребителю даны матрицей

.

РЕШЕНИЕ. Запасы грузов у поставщиков: т. Запросы потребителей: т; так как , то вводим фиктивного поставщика с грузом а_4ф = 450 – 390 = 60 т.

Тариф фиктивного поставщика 4ф примем равным 20 усл. ед.

Bj Ai					ui
1240	7	13
240	14		7		-5
3110	3	15			-2
4ф 60
vj

Так как т + п – 1 = 7, а число занятых клеток равно 6, то для исключения вырожденности введём в клетку (2, 2) нулевую поставку. Оценки свободных клеток: , .

Оценка свободной клетки (1, 3) больше нуля, перераспределим грузы:

Запишем полученное перераспределение грузов в табл.:

Bj Ai					ui
1240
240			7		-5
3110					-2
4ф 60
vj

Имеем

, , , , , , , , .

Получили оптимальное решение:

Стоимость транспортных расходов – 3120 усл. ед.