По методу северо-западного угла (СЗУ)

Название этого метода связано с особой разметкой транспортной таблицы: стороны таблицы называют по сторонам света (верхняя – северная, нижняя – южная), а углы соответственно помечают как промежуточные направления (левый верхний – северо-западный угол или СЗУ и т.д.) (табл. 4.1).

Составление опорного плана начинают с СЗУ таблицы – заполняют клетку A₁ B₁ меньшим из чисел a₁ и b₁, т.е. x₁₁ = min { a₁, b₁ }. От соотношения a₁ и b₁ зависит последовательность заполнения таблицы:

· Если a₁ > b₁, то x₁₁ = b₁ – это значит, что заявка потребителя B_{1 ­}удовлетворена полностью. В этом случае говорят, что столбец B₁ «закрыт» и переходят к заполнению клетки A₁B₂ (т.е. передвигаются по строке вправо, к следующему потребителю). При этом x₁₂ = min { a₁ – b₁, b₂ }.

· Если a₁ < b₁, то запасы поставщика A₁ исчерпаны (строка A₁ « закрыта»), а заявка потребителя B₁ удовлетворена не полностью. Поэтому, чтобы закончить обслуживание заявки B₁, переходим к клетке A₂ B₁ (т.е. к следующему поставщику) и записываем в нее значение x₂₁ = min { a₂, b₁ – a₁ }.

· Если a₁= b₁, то закрываем строку A₁ и строку B₁, а затем переходим к клетке A₂ B₂.

Процесс продолжается до тех пор, пока не будут исчерпаны запасы a_i, и заявки b_j не будут удовлетворены полностью. Это всегда возможно, т.к. по условию задача сбалансирована, т.е. предложение товаров равно спросу на них. Основным свойством транспортной задачи является то, что она всегда имеет решение.

Надо сказать, что название метода достаточно условно, поскольку заполнение таблицы можно начинать с любого угла.

В табл. 4.1-4.2 показано начало решения задачи – обслуживание потребителей B₁ и B₂. Результат решения задачи приведен в табл. 4.3.

4.2. Составление опорного плана ТЗ

По методу минимума стоимостей перевозки

 

Метод минимума стоимостей перевозок аналогичен методу СЗУ, только надо заполнять в первую очередь те клетки, для которых стоимости перевозок стоимости наименьшие. Если таких

 

Таблица 4.1

СВУ

СЗУ

Первая итерация решения ТЗ по методу СЗУ

 

Пункт назначения (ПН)

Запасы

B1

B2

B3

B4

B5

B6

ai

Пункт отправления (ПО)

A1

1

25; 7

A2

A3

31

A4

34

Заявки

bj

18; 0

ЮВУ

ЮЗУ

 

Таблица 4.2

Вторая итерация решения ТЗ по методу СЗУ

Пункт назначения (ПН)

Запасы

B1

B2

B3

B4

B5

B6

ai

Пункт отправления (ПО)

A1

1

2

25; 7; 0

A2

3

32; 28

A3

31

A4

34

Заявки

bj

18; 0

11; 4; 0

 

 

клеток несколько, целесообразнее сначала заполнить клетки, соответствующие наибольшим объемам заявок. Пример решения транспортной задачи методом минимума стоимостей перевозок показан в табл. 4.4 – 4.6.

 

 

Таблица 4.3

Результат решения ТЗ по методу СЗУ

Пункт назначения (ПН)

Запасы

B1

B2

B3

B4

B5

B6

ai

Пункт отправления (ПО)

A1

1

2

25; 7; 0

A2

3

4

5

32; 28; 4; 0

A3

6

7

31; 15; 0

A4

8

9

34; 21; 0

Заявки

bj

18; 0

11; 4; 0

24; 0

20; 16; 0

28; 13; 0

21; 0

 

 

Таблица 4.4

Первая итерация решения ТЗ

по методу минимума стоимостей перевозок

Пункт назначения (ПН)

Запасы

B1

B2

B3

B4

B5

B6

ai

Пункт отправления (ПО)

A1

1

25; 5

A2

A3

31

A4

Заявки

bj

20; 0

Таблица 4.5

Вторая итерация решения ТЗ

по методу минимума стоимостей перевозок

Пункт назначения (ПН)

Запасы

B1

B2

B3

B4

B5

B6

ai

Пункт отправления (ПО)

A1

1

25; 5

A2

A3

31

A4

2

34; 16

Заявки

bj

18; 0

20; 0

 

 

Таблица 4.6

Результат решения ТЗ

по методу минимума стоимостей перевозок

Пункт назначения (ПН)

Запасы

B1

B2

B3

B4

B5

B6

ai

Пункт отправления (ПО)

A1

3

1

25; 5; 0

A2

4

7

6

32; 26; 5; 0

A3

5

8

31; 7; 0

A4

2

9

34; 16; 0

Заявки

bj

18; 0

11; 6; 0

24; 0

20; 0

28; 23; 16; 0

21; 0

4.3. Сравнение планов по критерию стоимости

Необходимо подсчитать суммарные затраты на транспортировку (значение целевой функции): W = f (x) = S с_ij x_ij.

Для примеров, рассмотренных в 4.1-4.2, получим:

· для плана, построенного по методу СЗУ:

W_СЗУ = 7 × 18 + 1 × 7 + 1 × 4 + 8 × 24 + 5 × 4 + 5 × 16 + + 7 × 15 + 9 × 13 + 9 × 21 = 840;

· для плана, построенного по методу минимума стоимостей: W_МС = 1 × 5 + 1 × 20 + 1 × 6 + 7 × 5 + 4 × 21 + 4 × 24 + + 7 × 7 +1 × 18 + 9 × 16 = 457.

Лучшим считается план с меньшей суммарной стоимостью перевозок. Для примеров п.п. 4.1-4.2, – это план, составленный по методу минимума стоимостей перевозок: W_МС = 457 < W_СЗУ = 840.

4.4. Проверка лучшего опорного плана

На оптимальность

 

Для проверки плана на оптимальность можно применить метод потенциалов.

Для этого надо ввести так называемые псевдостоимости . Входящие в псевдостоимости величины a_i и b_j называют потенциалами. Псевдостоимости обладают следующими свойствами:

при x_ij ¹0(базисные клетки); (4.1)

при x_ij = 0(свободные клетки). (4.2)

 

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

Для транспортной задачи 4х6 введем величины a₁, a₂, a₃, a₄, соответствующие первым четырем ограничениям, и b₁, b₂, b₃, b₄, b₅, b₆ – остальным ограничениям.

Запишем условия (4.1) для базисных клеток:

a₁ + b₂ = 1;

a₁ + b₄ = 1;

a₂ + b₂ = 1;

a₂ + b₅ =7;

a₂ + b₆ = 4;

a₃ + b₃ = 4;

a₃ + b₅ =7;

(4.3)

a₄ + b₁ =1;

a₄ + b₅ =9.

Запишем условия (4.2) для свободных клеток:

 

a₁ + b₁ £ 7;

a₁ + b₃ £ 8;

a₁ + b₅ £ 5;

a₁ + b₆ £ 3;

a₂ + b₁ £ 7;

a₂ + b₃ £ 8;

a₂ + b₄ £ 5;

a₃ + b₁ £ 3;

a₃ + b₂ £ 7;

a₃ + b₄ £ 5;

a₃ + b₆ £ 5;

a₄ + b₂ £ 2;

(4.4)

a₄ + b₃ £ 4;

a₄ + b₄ £ 9;

a₄ + b₆ £ 9.

 

 

Система (4.3) состоит из 9 уравнений и содержит 10 переменных: . Поскольку число независимых переменных в данной системе равно 4 + 6 - 1 = 9, то одна переменная из множества a или b свободная. Пусть это будет a₁. Положив a₁ =0, получим: a₁ = 0, a₂ = 0, a₃ =2, a₄ = 4, b₁ = –3, b₂ =1, b₃ = 2, b₄ = 1, b₅ = 5, b₆ = 4. Составим таблицу перевозок, соответствующую данному решению (табл. 4.7).

Полученное решение a₁, a₂, a₃, a₄, b₁, b₂, b₃, b₄, b₅, b₆ подставляем в систему (4.4), т.е. в пустые клетки. Если ограничения системы (4.4) являются верными неравенствами при найденном решении, то проверяемый допустимый план исходной задачи является оптимальным, иначе - план не оптимален, и его надо улучшать.

Из табл. 4.7 видно, что при данном решении не выполняются четвертое, одиннадцатое, двенадцатое и тринадцатое неравенства системы (4.4) – им соответствуют клетки А₁В₆, А₃В₆, А₄В₂, А₄В₃. Это значит, что полученное решение не оптимально, его необходимо улучшить.

Таблица 4.7

Проверка плана ТЗ на оптимальность и первый цикл пересчета

	b1 = –3	b2 = 1	b3 = 2	b4 = 1	b5 = 5	b6 = 4
a1 = 0	–3 £ 7	1 = 1	2 £ 8	1 = 1	5 £ 5	4 £ 3
– a2 = 0	–3 £ 7	1 = 1	2 £ 8	1 £ 5	5 = 5	4 = 4
a3 = 2	–1 £ 3	3 £ 7	4 = 4	3 £ 5	7 = 7	6 £ 5
– + + a4 = 4	1 = 1	5 £ 2	6 £ 4	5 £ 9	9 = 9	8 £ 9

4.5. Улучшение плана