Файл: Практикум по логистике рекомендовано в качестве учебного пособия.docx

по загруженным клеткам (2 – 2), (2 – 3) определяем другие потенциалы:

α₂ +β₂ = 3;α₂ +2=3;α₂ = 1;

α₂ +β₂ = 2;1+ β₃ =2; β₃ =1.

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

Потребитель	В1	В2	В3		В4		Запасы	αi
Поставщик
А1	1 0	2 60	3		4		60	0
А2	4	3	2			0	80	-1
			80		+
А3	0 40	2		2		1	100	-1
			0		60
Потребность	40	60	80		60		240
βj	1	2	3		2

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

α_i +β_j ≤c_ij

Если для незагруженных клеток условие выполняется, то план оп-

---

тимальный. По таблице 4.3 осуществляем проверку начального плана на оптимальность:

(i – j) = (1 – 3), 0 + 1 ≤ 3;

(i – j) = (1 – 4), 0 + 0 ≤ 4;

(i – j) = (2 – 1), 1 + 1 ≤ 4;

(i – j) = (2 – 4), 1 + 0 > 0, ∆c₂₄ = 1;

(i – j) = (3 – 1), 1 + 1 > 0, ∆c₃₁ = 2;

(i – j) = (3 – 2), 1 + 2 > 2, ∆c₃₂ = 1.

Итак, по трем клеткам условие не выполняется, следовательно, начальный план требует улучшения. Характеристики ∆c_ijпоказывают размер экономии транспортных издержек на единицу перевозимого гру- за. В нашем примере наибольшую экономию можно получить по клетке (i – j) = (3 – 1), где ∆c₃₁ = 2 > {∆c_24; ∆c₃₂}. Следовательно, клетку (3 – 1) необходимо загрузить за счет перераспределения ресурсов из других за- груженных клеток. В таблице клетку (3 – 1) помечаем знаком (+), так как здесь в начальном плане находится вершина максимальной неопти- мальности.

Контур перераспределения ресурсов составляют по следующим правилам:

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

В этой клетке намечаем одну из вершин контура и далее по выше- изложенным правилам строим контур, вершины которого будут нахо-

---

диться в клетках (3 – 1) – (1 – 1) – (1 – 2) – (2 – 2) – (2 – 3) – (3 – 3).

Вершины контура последовательно подразделяем на загружаемые – Зи

разгружаемые – Р, начиная с вершины максимальной неоптимальности (+) (таблица 4.4).

Перераспределение ресурсов по контуру осуществляется с целью получения оптимального плана. В процессе перераспределения ресур- сов по контуру в соответствии с условием неотрицательности перемен- ных x_ijни одно из этих значений не должно превратиться в отрицатель- ное число. Поэтому анализируют только клетки Р,из которых выбирают клетку с минимальным объемом перевозок.

В нашем примере X_min=min {40; 40; 40} = 40. Следовательно,

клетки (1 – 1), (2 – 2), (3 – 3) полностью разгружаются. В клетке (1 – 2) загрузка увеличится на 40 и достигнет 60, в клетке (2 – 3) загрузка со- ставит 40 + 40 = 80, и клетка (3 – 1) загрузится на 40. Проверяем усло- вие N = т + n – 1. В нашем примере т = 3, п = 4, а число загруженных клеток равно 4, т. е. условие не выполняется 6 ≠ 4. В процессе перерас- пределения ресурсов произошла полная разгрузка трех клеток, а мы должны освободить только одну клетку. В этом случае следует в две клетки проставить нули (нулевой ресурс) и считать их условно загру- женными. Например, в клетки (1 – 1) и (3 – 3) проставим нулевой ре- сурс. Получение нового плана (итерации) осуществляется в том же по- рядке, который был рассмотрен:

• 
  по загруженным клеткам (в соответствии с новой загрузкой) вычисляются потенциалы α_i и β_j;
  
• 
  по незагруженным клеткам проводится проверка плана на оптимальность;
  
• 
  находится вершина максимальной неоптимальности и стро- ится новый контур перераспределения, и так далее до тех пор, пока не будет найдено оптимальное решение, удовлетворяющее неравенству α_i
  

---

+β_j≤c_ij

По результатам первой итерации имеем:

---

m n

Z_min  _c_ij x_ij  2 * 60  2 * 80  1* 60  0 * 40  340

i1 j1

Ниже приведены расчеты по второй итерации (таблица 4.5) и оп- тимальный план.

Поиск потенциалов:

α₁ +β₁ = 1;0+ β₁ =1;β₁ =1;

α₁ +β₂ = 2;0+ β₂ =2;β₂ =2;

α₂+β₃ = 2; α₂ +3=2; α₂ =-1;

α₃+β₁ = 0; α₃ +1=0; α₃ =-1;

α₃ + β₃ = 2; -1 + β₃ = 2; β₃ = 3;α₃ +β₄ = 1; -1+β₄= 1; β₄ =2/

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

(i –j) = (1 – 3), 0 + 3 ≤ 3;

(i –j) = (1 – 4), 0 + 2 < 4;

(i –j) = (2 – 1), 1 – 1 < 4;

(i –j) = (2 – 2), 2 – 1 < 3;

(i –j) = (2 – 2), 2 – 1 < 2;

(i –j) = (2 – 4), 2 – 1 > 0.

Клетку (2 – 4) необходимо загрузить.

В соответствии с перераспределением ресурсов по контуру полу- чаем таблицу, для которой вновь рассчитываем потенциалы α_i и β_jи по- следовательность вычислений повторяется.
Таблица 4.5

Потребитель Поставщик	В1	В2	В3	В4	Запасы	α1
А1	1 0	2 60	3	4	60	0
А2	4	3	2 20	0 60	80	-1
А3	0 40	2	2 60	1	100	-1
Потребность	40	60	80	60	240
β1	1	2	3	1

---