Вопрос № 17 Транспортная задача. Алгоритм метода потенциалов

Определение

Матрица С=(с_ij) (i= 1,m j =1,n) называется матрицей тарифов, а сами числа с_ij- тарифами

Определение

Планом транспортной задачи называется матрица вида Х=( х_ij) (i= 1,m j =1,n) в которой все элементы неотрицательные

Требуется найти значение переменных х_ij (i= 1,m j =1,n) обращающих в минимум целевую функцию

_{При ограничениях}

Ограничения:

X₁₁+ X₁₂₊ X₁_n=a₁

X₂₁+ X₂₂₊ X_2n=a₂ поставщика

X_m1+ X_m2+ X_mn=a_m

X₁₁+ X₁₂₊ X_m₁=b₁

X₂₁+ X₂₂₊ X_m₂=b₂ спрос потребителя

X_1n+ X_2n+ X_mn=b_n

X_ij≥0 i=1…m j=1…n

_{Решение:}

_{1.Цель: минимизация расходов}

_{2.Критерий эффективности величина расходов}

_{3.Неуправляемые факторы: запасы поставщика и потребноть потребителя}

Управляемые факторы: количество груза от поставщика к потребителю

Матрица вида Х=( х_ij) (i= 1,m j =1,n Называется планом транспортной задачи

4. Множество решений-множество матриц вида Х

5. ограничения по сроку потребителя и запасу поставщика

6.лпр- менеджер

Построение математической модели

Целевая функция :

Z=∑ ∑ a_ijx_ij→min

Ограничения:

X₁₁+ X₁₂₊ X₁_n=a₁

X₂₁+ X₂₂₊ X_2n=a₂ поставщика

X_m1+ X_m2+ X_mn=a_m

X₁₁+ X₁₂₊ X_m1=b₁

X₂₁+ X₂₂₊ X_m₂=b₂ спрос потребителя

X_1n+ X_2n+ X_mn=b_n

X_ij≥0 i=1…m j=1…n

Замечания: данная математическая модель составляется с учетом предположения что исходная задача является закрытой

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

Метод решения аналогичен синтетическому и представляет совокупность этапов.

1. построение опорного плана

2.проверка его на оптимальность

3.Переход от одного опорного плана к другому

Опорный план транспортной задачи.

Система ограничений вида (2) m+n уравнений и mn неизвестных → справедлива теорема:

Каждый опорный план транспортной задачи 1,2 содержит m+n базисную переменную и mn – (m+n+1) свободную переменную

Клетка соответствующая базисной переменной опорного плана называется ЗАГРУЖЕННОЙ, а клетка свободной переменной –СВОБОДНОЙ

АЛГОРИТМ:

Построение плана методом минимальной стоимости

1. загрузить в транспортную таблицу клетку с минимальным тарифом

2. исключить из рассматриваемых соответствующую поставку или потребность

3. в оставшиеся части транспортной таблицы загрузить клетку с минимальным тарифом

4. Повторить п. 2 и 3 до тех пор пока не будут исчерпаны запасы всех поставщиков , удовлетворен спрос всех потребителей

5. если в результате будет загружено m+n-1 клеток то опорный план построен. в противоположном случае все последующие клетки заполнить 0 чтобы число загруженных клеток стало (m+n-1)

Вопрос № 17 Транспортная задача. Алгоритм метода потенциалов.

Алгоритм решения транспортной задачи методом потенциалов

Алгоритм решения транспортной задачи

методом потенциалов

1. условие транспортной задачи представить в виде таблицы

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

3. построить опорный план методом минимальной стоимости

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

Потенциалы u_i и v_j записываем в столбце и в строке, которые добавляем к таблице.

5. Для всех свободных клеток найти оценки D_ij= u_i + v_j - c_ij.

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

Если все D_ij£0, то найденное решение оптимально.

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

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

ОПРЕДЕЛЕНИЕ:циклом называется набор клеток состоящий из2 и только 2 соседних клеток расположенных в 1-ой строке или столбце. При этом каждая клетка набора лежит в той же строке или столбце что и исходная. Среди всех клеток табл. ровно 1 клетка явл. свободной

Замечание. графиком изображения цикла является замкнутая ломаная звенья которой расположены только в строках или столбцах а все за исключением 1-ой расположены в загруженных клетках.

Алгоритм построения цикла

8 поставить в вершинах получившейся ломаной знаки + или – против часовой стрелки начиная с выбранной клетки.

9 выбрать загруженные клетки в которых стоит знак – и найти среди них наименьшее значение груза

изменить значение груза в вершинах цикла на величину l с учетом знака стоящего в клетке

повторить п.4-9

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

Замечания:

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

· объем переходов между аi и bj заранее определен и равен а

· в этом случае вводится дополнительное ограничение xij≥a

· существует ограничение на пропускную способность т.е.объем перевозок ограничен величиной bв этом случае ограничения xij≤b

· не допускается перевозка груза из некого пункта Аi в bj в этом случае соответствующий тариф С=∞

Вопрос №18

Задача о назначениях

необходимо назначить m работников на n работ чтобы коэффициент выполнения был максимальный при условии что 1 работник выполняет только 1 работу и 1 работа может быть выполнена только 1 работником

эффективность выполнения представлена в виде таблицы.