Определение оптимального плана перевозок (стр. 2 из 2)

Рисунок 1. Пример построения цепи к свободной клетке А₂ - В₁

Алгебраическую сумму показателей C_ij в вершинах цепи называем характеристикой цепи. Следовательно, в представленном примере

Е= – 4 +2 +1 – 3= – 4.

Следовательно, изменение поставок по данной цепи на 1 т уменьшает значение Zна 4 у.е.

Суть метода потенциалов заключается в том, что проверки допустимого плана на оптимальность особым образом определяются числа, называемые «потенциалами», при помощи которых достаточно просто вычисляются характеристики цепей к свободным клеткам. Единственное требование к потенциалам – каждый показатель критерия оптимальности базисной клетки должен быть равен алгебраической сумме потенциалов строки и столбца.

Потенциалы строк и столбцов определяются следующим образом. В табл. 3 произвольно принимается потенциал строки А₁ равным 3 (может быть принято и любое другое число). В строке А₁ находятся две базисные клетки, показатели C_ij, которых равны 4 и 1. Тогда потенциал столбца В₁ равен 4-3=1, а В₂ 1 – 3 = – 2. В столбце В₂ находится еще одна базисная клетка, в которой C_ij=3, следовательно, потенциал строки А₂ равен 3 – (–2) =5, тогда потенциалы столбцов В₃ и В₄ равны соответственно 2 – 5 = – 3, строки А₃ = 7 и столбца В₅ = – 3 .

Обозначив потенциалы строк через u_i , потенциалы столбцов v_j, а показатели оптимальности в базисных клетках через C_ij , можно записать

C_ij= u_i+v_j; u_i= C_ij - v_j; v_j = C_ij - u_i (6)

Характеристики цепей к свободным клеткам обозначимЕ_ij. Зная потенциалы их строк и столбцов,

Е_ij = C_ij– (u_i+v_j) . (7)

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

Если же характеристик Е_ij будет равна нулю, то перераспределение поставок по данной цепи не изменит значения целевой функции. Для базисных клеток характеристики равны нулю.

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

Е₁₃= 3; Е₁₄= 4; Е₁₅= 4; Е₂₁= – 4; Е₂₅= 3 –(5+( – 3)) =1;

Е₃₁= – 5; Е₃₂= 0; Е₃₃= – 2.

Видно, что отрицательных характеристик три: А₂ - В₁, А₃- В₁ и А₃ – В₃. Наибольшая по абсолютной величине отрицательная характеристика в А₃- В₁, которая составляет – 5. перераспределим поставки по цепи к этой клетке. Для этого составим цепь с вершинами: А₁- В₁,А₁– В₂,А₂– В₂ ,А₂– В₄, ,А₃– В₄ ,

А₃- В₁. Положительными вершинами в этой цепи будут А₃– В₁, ,А₁– В₂, ,А₂– В₄ (так как увеличение поставок в этих клетках приводит к уменьшению значения целевой функции), а остальные отрицательными.

Наименьшая по величине поставка в отрицательных вершинах цнпи равна 7 (в А₂– В₂). Прибавляем по 7 к объемам поставки в положительных вершинах и вычитаем из поставок в отрицательных также по 7. Получившийся план перевозок записываем в таблицу 4 и определяем новые потенциалы, произвольно приняв потенциал строки А₁ равным 1. Значение целевой функции при новом плане поставок будет на 7

5=35 у.е. меньше, т.е.:

Z=363 – 35=328 у.е.

Характеристики свободных клеток для вновь созданного плана будут следующими:

Е₁₃= -2; Е₁₄= -1; Е₁₅= -1; Е₂₁= 1; Е₂₂ =5; Е₂₅ =1;

Е₃₂= 5; Е₃₃= – 2.

В таблице 4 отрицательных характеристик свободных клеток четыре: А₁– В₃,А₁– В₄,А₁– В₅ ,А₃– В₃. Перераспределим поставки по цепи к любой из этих клеток, допустим к А₁– В₅, по цепи: А₁– В₅, А₃– В₅, А₃– В₁, А₁– В₁. Положительные вершины цепи А₁– В₅ и А₃– В₁, а отрицательные А₃– В₅ и А₁– В₁, минимальная поставка равна 15 от поставщика А₁к потребителю В₁, т.е. А₁– В₁ (таблица 4/1).

Таблица 4.

Таблица 4/1.

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

Значение целевой функции при новом плане:

Z=328 – 15

1 =313 у.е.

Аналогично определяем потенциалы строк и столбцов и рассчитываем характеристики цепей к свободным клеткам:

Е₁₁= 1; Е₁₄= 0; Е₁₃= -1; Е₂₁= 1; Е₂₂ =4; Е₂₃ =1;

Е₃₂= 4; Е₃₃= – 2.

Таблица 5.

Принимаем перераспределение поставок по цепи к А₃– В₃, т.к. характеристика данной клетки отрицательная и наибольшая по абсолютному значению. Составляем цепь перераспределения: А₃– В₃, А₂– В₃ , А₃– В₄ , А₃– В₄ (таблица 5/1).

Таблица 5/1.

Минимальная поставка в отрицательных вершинах (А₃– В₄) равна 3. Получившийся план перевозок представлен в таблице 6.

Значение целевой функции при новом плане:

Z=313 – 3

2=307 у.е.

Аналогично определяем потенциалы строк и столбцов и рассчитываем характеристики цепей к свободным клеткам:

Е₁₁= 1; Е₁₄= 2; Е₁₃= 1; Е₂₁= -1; Е₂₂ =2; Е₂₅ = -1;

Е₃₂= 4; Е₃₄= 2.

Отрицательными характеристиками обладают две клетки: А₂– В₁ и А₂– В₅. Произведем поставку 17 т из А₂в В₁ (таблица 7).

Таблица 6.

Таблица 7.

При таком плане перевозок значение целевой функции:

Z=307 – 17=209 у.е.

Характеристики цепей к свободным клеткам:

Е₁₁= 1; Е₁₄= 2; Е₁₃= 1; Е₂₂= 3; Е₂₃=2; Е₂₅ = 0;

Е₃₂= 4; Е₃₄= 1.

Таким образом, в данном плане перевозок нет ни одной отрицательной характеристики. Нулевая оценка клетки А₂– В₅ указывает на то, что данную программу можно изменить так, что эта клетка станет базисной, но при этом получится равноценный план с той же величиной затрат.

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

Оптимальный план перевозок даст снижение стоимости перевозок по сравнению с исходным:

ИСХОДНЫЕ ДАННЫЕ К ЛАБОРАТОРНОЙ РАБОТЕ №2

Таблица 1.

Базы	Пункты потребления										Запасы сырья, т
Базы	В₁	В₂	В₃	В₄	В₅	В₆	В₇	В₈	В₉	В₁₀	Запасы сырья, т
А₁	3	1	6	2	4	8	3	4	7	6	120
А₂	2	3	5	7	3	2	6	5	1	3	140
А₃	9	8	4	7	1	5	4	7	2	4	180
А₄	3	6	6	5	3	7	3	2	5	3	200
А₅	4	2	3	2	4	1	2	3	5	4	90
А₆	1	3	1	6	2	4	2	4	3	2	130
А₇	8	2	3	1	2	6	3	2	1	4	200
А₈	4	1	2	3	6	4	1	6	7	1	170
А₉	1	4	3	3	5	1	7	1	9	4	150
А₁₀	3	2	5	4	8	6	2	8	3	7	100
Спрос потре-бителей, т	120	140	180	200	90	130	200	170	150	100

Таблица 2.

Вариант	База	Вариант	База	Вариант	База
1	1,2,3,4,5	7	9,10,1,2,3	13	2,5,7,8,9
2	2,3,4,5,6	8	10,2,3,4,5	14	8,4,6,3,1
3	3,4,5,6,7	9	1,3,5,7,9	15	9,3,6,7,10
4	4,5,6,7,8	10	2,4,6,8,10	16	1,2,8,9,10
5	5,6,7,8,9	11	1,2,5,6,9	17	3,9,2,7,6
6	6,7,8,9,10	12	9,7,1,3,5	18	1,4,6,8,9