Математические методы в экономике

    Присвоим поставке отмеченной меткой  c,  знак плюс. Второй поставке в этом же столбце присвоим знак минус. Далее третьей поставке, находящейся в той же строке, что и вторая, присвоим знак плюс, и т. д. Повторяя этот процесс для всех вершин цикла, получим знакочередующуюся цепь. Найдем в этой цепи минимальную поставку ( ) из поставок по отрицательным вершинам. Эту величину отнимаем из всех поставок в отрицательных вершинах и прибавляем ко всем поставкам в положительных вершинах. Т.о. получим новый план, в котором  не является базисной. Все остальные базисные переменные, а также переменная х_lk являются базисными в новом плане и отмечаются кружком. Некоторые из базисных переменных могут быть равны нулю. Метод потенциалов обеспечивает монотонное убывание значений целевой функции (суммарной стоимости) и позволяет за конечное число шагов найти ее минимум.

 

Алгоритм метода потенциалов.

1. Составить  ПБП и отметить кружками базисные  переменные.

2. Составляем  систему потенциалов из условия U_i+V_j= С_ij для всех отмеченных клеток, т.е. для каждой базисной переменной (обычно U₁=0), тогда все остальные находятся однозначно.

3. Проверить  полученный план на оптимальность.  Условие оптимальности:

С_ij-(U_i+V_j)=0 – для всех отмеченных клеток

С_ij-(U_i+V_j)³0 для всех остальных клеток

а) Критерий оптимальности  выполнен. Записать оптимальный план и значение целевой функции. ЗАДАЧА РЕШЕНА.

б) Критерий  оптимальности не выполнен. Переходим  к пункту 4.

4. Найти D=min(C_ij-(U_j+V_j)) для всех клеток в которых С_ij-(U_i+V_j)<0. Клетка (1, k) в которой достигается этот минимум, будет соответствовать новой базисной переменной  x_lk. Ввести в клетку (1, k) метку c. Перейти к пункту 5.

5. Построить  новое базисное решение с помощью  процедуры перепланировки, включив  переменную x_lk в число базисных переменных. Перейти к пункту 2.

Пример 3.  . На складе А₁ имеется 120 холодильников, на складе А₂ – 180. Их необходимо доставить в 3 магазина В₁, В₂ и В₃ в количествах 70, 140, 90 соответственно. Стоимость перевозки одного холодильника от поставщика к потребителю задается матрицей

 

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

 

Решение. Обозначим через x_ij - количество груза перевозимого от поставщика  A _i к потребителю В _j , где i = 1, 2  и j = 1, 2, 3. Составим таблицу. Тарифы перевозок матрицы С запишем в левый верхний угол каждой клетки таблицы.

 

Таблица 5.

	Ai\Bj	70	140	90
	120	8	5	6
	180	4	9	7

 

В нашей задаче суммарные запасы и потребности равны, следовательно, транспортная задача является закрытой. Определим начальный опорный план задачи. Составим таблицу 6, используя метод северо-западного угла. Начнем заполнение таблицы с клетки (1; 1). Запишем в неё наименьшее из чисел запасов и запросов, соответствующих этой клетке, т.е.  min{70; 120}=70. В клетке (2;1) ставится прочерк, т.к. запросы потребителя В₁ удовлетворены. Далее заполняется следующая по первой строке клетка, т.е. клетка (1; 2), с учётом  уже использованных запасов и удовлетворенных запросов. Имеем min{120-70; 120}=50. Это число записываем в клетке (1; 2). В следующей по первой строке клетке (1;3) ставим прочерк, т.к. все запасы склада А₁ исчерпаны.  Переходим к клетке (2;2). Имеем min{140-50; 180}=90. Для клетки (2;3) получим min{180-90; 90}=90. Итак, таблица 6 имеет вид

Таблица 6.

	Ai\Bj	70	140	90
	120	8        70	5          50	6
	180	4	9          90	7       90

 

Количество заполненных клеток в таблице 6 равно 4, m+n-1=2+3-1=4. Следовательно, полученный план невырожденный. Значение базисных переменных: х₁₁=70, х₁₂=50, х₂₂=90, х₂₃=90. Остальные переменные – небазисные  и их значения равны нулю. Транспортные расходы при данном плане перевозки будут равны: f(x)=c₁₁x₁₁+c₁₂x₁₂+c₂₂x₂₂+c₂₂x₂₃=8×70+5×50+9×90+7×90= 2250.

 Проверим составленный план  на оптимальность, используя метод потенциалов. Вычислим потенциалы по заполненным клеткам. Сумма потенциалов, соответствующих этим клеткам, равна истинному тарифу, записанному в левом верхнем углу рассматриваемой клетки, т.е. U _i + V_j = с_ij, где с_ij - истинный тариф клетки (i, j), i = 1, 2  и j = 1, 2, 3.

.Поиск потенциалов начнем с клетки (1; 1). Имеем U ₁ + V₁ = 8. Полагаем U ₁ = 0, тогда V₁ = 8. Следующая заполненная клетка (1;2), для неё имеем U ₁ + V₂ = 5. Значит, V₂ = 5. Для клетки (2;2) имеем U ₂ + V₂ = 9 Þ U ₂ = 9 – 5 = 4. Последняя заполненная клетка  (2;3), для неё получим U ₂ + V₃ = 7 Þ V₃ = 7 – 4 = 3. Результаты вычислений отразим в таблице 7. Она примет вид

 

 

Таблица 7.

	Ai\Bj	70	140	90
	120	8 −     70	5 +      50	6	U1=0
	180	4 +	9 −      90	7       90	U2=4

                  V₁=8          V₂=5        V₃=3

 

Проверим выполнение условия оптимальности D_ij=c_ij-(U_i+V_j) ³ 0 для всех незанятых клеток.

Свободная клетка  (1;3): D₁₃=c₁₃ - (U₁+V₃)= 6 –(0 + 3) = 3>0.

Свободная клетка  (2;1): D₁₃=с₂₁ – (U ₂ + V₁) = 4 – ( 4 + 8) =  - 8 <0.

  В клетке (2;1) условие оптимальности  не выполняется. Значит, план не  оптимален, и транспортные расходы  можно уменьшить. Вводим в клетку (2,1) метку c . Строим новое базисное решение с помощью процедуры перепланировки, включив переменную x₂₁ в число базисных переменных Переход к новому плану осуществим при помощи цикла. . В нашем случае в таблице 7 выбранный цикл это (2;1) → (2;2) → (1;2) → (1;1) → (2;1). У вершин ломанной проставим знаки   “ + “   и   “ – “. В свободной клетке (2;1) ставим “ + “, а далее идет чередование знаков. Из чисел, соответствующих клеткам со знаком “ – “, выберем наименьшее. Это число используется для пересчёта. В нашем случае min {90;70}=70. Составим новую таблицу 8. В клетку (2;1) запишем 70. В клетках со знаком  “ + “ к числу, находящемуся в клетке прибавляем 70. А в клетках со знаком  “ – “ из числа, находящегося в клетке вычитаем 70. При этом клетка (1;1) становится свободной, а (2;1) – занятой. Клетки (1;3) и (2;3) не изменяются. Таблица 8. имеет вид

Таблица 8.

 

	Ai\Bj	70	140	90
	120	8	5         120	6	U1=0
	180	4       70	9          20	7       90	U2=4

                            V₁=0        V₂=5         V₃=3

 

.Проверим полученный план на  оптимальность. По занятым клеткам вычислим потенциалы.

Пусть U ₁ = 0. Имеем U ₁ + V₂ = 5 Þ V₂ = 5.

           U ₂ + V₂ = 9 Þ  U ₂  = 9 – 5 = 4.

           U ₂ + V₁ = 4  Þ  V₁ = 4 – 4 = 0.

           U ₂ + V₃ = 7  Þ  V₃ = 7– 4 = 3.

Зная потенциалы, по свободным клеткам  проверим выполнение условия оптимальности.

            D₁₁=c₁₁ – (U ₁ + V₁) = 8 - 0 = 8 >0.

            D₁₃=c₁₃ – (U ₁ + V₃)= 6 - 3 = 3 >0

Условие оптимальности не нарушено. Значит, план оптимальный и транспортные расходы уменьшить нельзя. Значения базисных переменных в оптимальном плане: х₁₂=120, х₂₁=70, х₂₂=20, х₂₃=90. Транспортные расходы f(x)= 5·120 + 4·70 + 9·20 + 7·90 = 1690.

Ответ: , f_min =1690.

Пример 4. По техническим причинам на склад А₂ поступило на 40 холодильников меньше. Какому потребителю необходимо уменьшить поставки, чтобы затраты на перевозки были минимальными?

Решение. Введем фиктивного поставщика А₃, который поставляет 40 холодильников с нулевыми тарифами доставки груза. Используя метод северо-западного угла, составим первую таблицу и определим первый опорный план.

Таблица 9

	Ai\Bj	70	140	90
	120	8        70	5          50	6
	140	4	9         90	7       50
	40	0	0	0        40

 

Итак, план . Транспортные расходы f(x) = 8·70 + 5·50 + 9·90 + 7·50 = 560 + 250 + 810 + 350 = =1970.

 

Используя метод потенциалов, проверим план на оптимальность. По занятым клеткам вычислим потенциалы.

U ₁ = 0.   U ₁ + V₁ = 8  Þ  V₁ = 8 – 0 = 8;

              U ₁ + V₂ = 5  Þ  V₂ = 5 – 0 = 5;

              U ₂ + V₂ = 9  Þ  U ₂ = 9 – 5 = 4;

              U ₂ + V₃ = 7  Þ  V₃ = 7 – 4 = 3;

              U ₃ + V₃ = 0 Þ  U ₃ = 0 –3 = – 3.

Зная потенциалы, по свободным клеткам  проверим выполнение условия оптимальности.

              D₁₃=c₁₃ – (U ₁ + V₃ ) = 6 - 3 = 3>0   ;

              D₂₁=c₂₁ – (U ₂ + V₁ ) = 4 – 12 = – 8<0 ;

              D₃₁=c₃₁ – (U ₃ + V₁ ) = 0–5 = – 5 <0;

              D₃₂=c₃₂ – (U ₃ + V₂ ) = 0 – 2 =  – 2<0  .

 

Таким образом, видим, что в трёх клетках (2;1), (3;1) и (3;2) нарушено условие  птимальности, т.к. в них D_ij <0. План Х₁ не оптимален. Произведем улучшение плана. Клетка (2, 1) в которой достигается минимум D_ij, будет соответствовать новой базисной переменной  x₂₁. Введем в клетку (2, 1) метку c. Выберем цикл  (2;1) → (2;2) → (1;2) → (1;1) → (2;1). У вершин цикла проставим знаки   “ + “   и   “ – “. В свободной клетке (2;1) ставим “ + “, а далее идет чередование знаков. Получим таблицу 10.

 

Таблица 10

	Ai\Bj	70	140	90
	120	8 −     70	5 +      50	6	U1=0
	140	4 +	9 −      90	7       50	U2=4
	40	0	0	0       40	U3=3

                  V₁=8          V₂=5        V₃=3

 

Определим число для пересчета  из чисел, соответствующих клеткам  со знаком “ – “, выбрав наименьшее. В нашем случае min {90;70}=70. В клетку (2;1) запишем 70. В клетках со знаком “ + “ к числу, находящемуся в клетке прибавляем 70. А в клетках со знаком  “ - “ из числа, находящегося в клетке вычитаем 70. При этом клетка (1;1) становится свободной, а (2;1) – занятой. Составим новую таблицу 11.

 

Таблица 11

 

	Ai\Bj	70	140	90
	120	8	5         120	6	U1=0
	140	4       70	9          20	7       50	U2=4
	40	0	0	0       40	U3= –3

                            V₁=0        V₂=5         V₃=3

 

Новый опорный план . Транспортные расходы f(x) = 5·120 + 4·70 + 9·20 + 7·50 + 0·40  = 600 + 280 + 180 + 350 + 0  = 1410. Транспортные расходы уменьшились. Значит, план Х ₂ лучше, чем Х ₁.