Опорный план метод северо западного угла. Транспортная задача: метод Северо-Западного угла. Опорное решение транспортной задачи

Постановка задачи

Исходные данные

Метод «северо-западного угла»

БЛОК-СХЕМА (АЛГОРИТМ РЕШЕНИЯ)

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

Методы построения начального опорного решения

МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА

Метод вычеркивания

Метод северо-западного угла

Метод минимальной стоимости

Главная › Телефон › Опорный план метод северо западного угла. Транспортная задача: метод Северо-Западного угла. Опорное решение транспортной задачи

Составить экономико-математическую модель и решить задачу с помощью надстройки «Поиск решения».

Решение:

Экономико-математическая модель:

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

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

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

x ij – равное 1 показывает, что i-го работника необходимо назначить на выполнение j-ой работы.

Экономико-математическая модель задачи составлена. Решим эту задачу с использованием надстройки Excel «Поиск решения».

На рисунке 1 представлен ход работы утилиты «Поиск решения».

Рисунок 1 – Ход работы утилиты Поиск решения

На рисунке 2 представлен результат решения задачи.

Рисунок 2 – Результат решения задачи

Вывод: из рисунка 2 следует, что для того, чтобы общая величина затрат была минимальной необходимо для выполнения работы А1 назначить работника В4, А2 – В3, А3 – В5, А4 – В1, А5 – В2, при этом суммарные затраты будут минимальны и составят 25 ед.

Задача 2 Транспортная задача

Исходная информация транспортной задачи представлена в таблице 2.

Таблица 2 – Исходные данные

	В1	В2	В3	В4	Запасы
А1
А2
А3
Потребности

Определить:

1. приближенный план, схему перевозок, а также его стоимость методом северо-западного угла;

2. приближенный план, схему перевозок, а также его стоимость методом минимального элемента;

3. оптимальный план, схему перевозок, а также его стоимость с помощью надстройки «Поиск решения».

Метод северо-западного угла

Проверим необходимое и достаточное условие разрешимости задачи.

Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 3 (120-117). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

Занесем исходные данные в распределительную таблицу 3.

Таблица 3 – Распределительная таблица

Первый опорный план начинается заполняться с верхнего левого угла (таблица 4).

Таблица 4 – Опорный план 1

	В1	В2	В3	В4	В5		Запасы
А1						u 1 =0

А2						u 2 =-2

А3						u 3 =-4

	v 1 =3	v 2 =6	v 3 =10	v 4 =5	v 5 =4
Потребности

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 3*30 + 6*10 + 4*17 + 8*23 + 6*7 + 1*30 + 0*3 = 474

u 1 + v 2 = 6; 0 + v 2 = 6; v 2 = 6

u 2 + v 2 = 4; 6 + u 2 = 4; u 2 = -2

u 2 + v 3 = 8; -2 + v 3 = 8; v 3 = 10

u 3 + v 3 = 6; 10 + u 3 = 6; u 3 = -4

u 3 + v 4 = 1; -4 + v 4 = 1; v 4 = 5

u 3 + v 5 = 0; -4 + v 5 = 0; v 5 = 4

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(1;3): 0 + 10 > 5; ∆ 13 = 0 + 10 - 5 = 5

(1;4): 0 + 5 > 2; ∆ 14 = 0 + 5 - 2 = 3

(1;5): 0 + 4 > 0; ∆ 15 = 0 + 4 - 0 = 4

(2;5): -2 + 4 > 0; ∆ 25 = -2 + 4 - 0 = 2

max(5,3,4,2) = 5

Выбираем максимальную оценку свободной клетки (1;3): 5

Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» (таблица 5).

Таблица 5 – Цикл 1

	В1	В2	В3	В4	В5
А1						u 1 =0
		-		+
А2						u 2 =-2
		+		-
А3						u 3 =-4

	v 1 =3	v 2 =6	v 3 =10	v 4 =5	v 5 =4

Цикл приведен в таблице (1,3 → 1,2 → 2,2 → 2,3).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план (таблица 6).

Таблица 6 – Опорный план 2

	В1	В2	В3	В4	В5
А1						u 1 =0

А2						u 2 =3

А3						u 3 =1

	v 1 =3	v 2 =1	v 3 =5	v 4 =0	v 5 =-1

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u i , v j . по занятым клеткам таблицы, в которых u i + v j = c ij , полагая, что u 1 = 0.

u 1 + v 1 = 3; 0 + v 1 = 3; v 1 = 3

u 2 + v 3 = 8; 5 + u 2 = 8; u 2 = 3

u 2 + v 2 = 4; 3 + v 2 = 4; v 2 = 1

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(2;1): 3 + 3 > 3; ∆ 21 = 3 + 3 - 3 = 3

(2;5): 3 -1 > 0; ∆ 25 = 3 -1 - 0 = 2

Выбираем максимальную оценку свободной клетки (2;1): 3

Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» (таблица 7).

Таблица 7 – Цикл 2

	В1	В2	В3	В4	В5
А1						u 1 =0
-				+
А2						u 2 =3
+				-
А3						u 3 =1

	v 1 =3	v 2 =1	v 3 =5	v 4 =0	v 5 =-1

Цикл приведен в таблице (2,1 → 2,3 → 1,3 → 1,1).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 13. Прибавляем 13 к объемам грузов, стоящих в плюсовых клетках и вычитаем 13 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план 3 (таблица 8).

Таблица 8 – Опорный план 3

	В1	В2	В3	В4	В5
А1						u 1 =0

А2						u 2 =0

А3						u 3 =1

	v 1 =3	v 2 =4	v 3 =5	v 4 =0	v 5 =-1

u 1 + v 1 = 3; 0 + v 1 = 3; v 1 = 3

u 1 + v 3 = 5; 0 + v 3 = 5; v 3 = 5

u 3 + v 3 = 6; 5 + u 3 = 6; u 3 = 1

u 3 + v 4 = 1; 1 + v 4 = 1; v 4 = 0

u 3 + v 5 = 0; 1 + v 5 = 0; v 5 = -1

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(3;2): 1 + 4 > 3; ∆ 32 = 1 + 4 - 3 = 2

Выбираем максимальную оценку свободной клетки (3;2): 3

Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» (таблица 9).

Таблица 9 – Цикл 3

	В1	В2	В3	В4	В5
А1						u 1 =0
-				+
А2						u 2 =0
+		-
А3						u 3 =1
		+		-
	v 1 =3	v 2 =4	v 3 =5	v 4 =0	v 5 =-1

Цикл 3 приведен в таблице (3,2 → 3,3 → 1,3 → 1,1 → 2,1 → 2,2).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 7. Прибавляем 7 к объемам грузов, стоящих в плюсовых клетках и вычитаем 7 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план 4.

Таблица 10 – Опорный план 4

	В1	В2	В3	В4	В5
А1						u 1 =0

А2						u 2 =0

А3						u 3 =-1

	v 1 =3	v 2 =4	v 3 =5	v 4 =2	v 5 =1

u 1 + v 1 = 3; 0 + v 1 = 3; v 1 = 3

u 2 + v 1 = 3; 3 + u 2 = 3; u 2 = 0

u 2 + v 2 = 4; 0 + v 2 = 4; v 2 = 4

u 3 + v 5 = 0; -1 + v 5 = 0; v 5 = 1

u 1 + v 3 = 5; 0 + v 3 = 5; v 3 = 5

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(1;5): 0 + 1 > 0; ∆ 15 = 0 + 1 - 0 = 1

(2;5): 0 + 1 > 0; ∆ 25 = 0 + 1 - 0 = 1

Выбираем максимальную оценку свободной клетки (1;5): 0

Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» (таблица 11).

Таблица 11 – Цикл 4

	В1	В2	В3	В4	В5
А1						u 1 =0
-							+
А2						u 2 =0
+		-
А3						u 3 =-1
		+					-
	v 1 =3	v 2 =4	v 3 =5	v 4 =2	v 5 =1

Цикл 4 приведен в таблице (1,5 → 1,1 → 2,1 → 2,2 → 3,2 → 3,5).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 5) = 3. Прибавляем 3 к объемам грузов, стоящих в плюсовых клетках и вычитаем 3 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план 5 (таблица 12).

Таблица 12 – Опорный план 5

	В1	В2	В3	В4	В5
А1						u 1 =0

А2						u 2 =0
		-
А3						u 3 =-1

	v 1 =3	v 2 =4	v 3 =5	v 4 =2	v 5 =0

u 1 + v 1 = 3; 0 + v 1 = 3; v 1 = 3

u 2 + v 1 = 3; 3 + u 2 = 3; u 2 = 0

u 2 + v 2 = 4; 0 + v 2 = 4; v 2 = 4

u 3 + v 2 = 3; 4 + u 3 = 3; u 3 = -1

u 3 + v 4 = 1; -1 + v 4 = 1; v 4 = 2

u 1 + v 3 = 5; 0 + v 3 = 5; v 3 = 5

u 1 + v 5 = 0; 0 + v 5 = 0; v 5 = 0

Опорный план 5 является оптимальным, так все оценки свободных клеток удовлетворяют условию u i + v j ≤ c ij .

Минимальные затраты составят:

F(x) = 3*7 + 5*30 + 0*3 + 3*23 + 4*17 + 3*10 + 1*30 = 368

Схема перевозок:

из 1-го склада необходимо груз направить 1-му потребителю в количестве 7 ед., 3-му потребителю в количестве 30 ед.;

из 2-го склада необходимо груз направить 1-му потребителю – 23 ед., 2-му потребителю – 17ед.;

из 3-го склада необходимо груз направить второму потребителю – 10 ед., 4-му – 30 ед.

На 1-ом складе остался невостребованным груз в количестве 3 ед.

Оптимальный план является вырожденным, так как базисная переменная x 15 =0.

©2015-2019 сайт
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-08-26

Четыре предприятия экономического района для производства продукции используют однородное сырье, спрос на которое составляет b j (у.е.).

Объем предложения сырья от трех поставщиков составляет, соответственно, a i (у.е.). Известны отпускные цены поставщиков р i (д.е./у.е.) и тарифы перевозок с ij (д.е./у.е.) от каждого поставщика А i к каждому предприятию В j . Требуется найти планы перевозок сырья предприятиям, при которых будут минимальными денежные затраты:

1)только на закупку сырья;

2)только на транспортировку сырья;

3)на закупку и транспортировку сырья.

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

4 вариант.

Имеются три поставщика А i и четыре потребителя B j . Предложения поставщиков (а i), спросы потребителей (b j), а также затраты на перевозку единицы груза (с ij) от пункта А i к пункту B j заданы матрицей С (д.е./ед).

Найти первое опорное решение транспортной задачи методом северо-западного угла. Решение: Проверяем условие сбалансированности (закрытости) задачи

Т.к. то вводим дополнительный столбец (потребитель) с потребностью b 5 =70 - 48 = 22 (ед.).

Составляем транспортную таблицу:

Таблица 2

Начинаем заполнение таблицы с левой верхней клетки: записываем максимально возможное значение x 11 =min(30;12)=12. Спрос потребителя В 1 удовлетворен и первый столбец исключаем из рассмотрения. Запасы первого поставщика равны 30-12 = 18.

В таблице находим новый северо-западный угол - клетку А 1 В 2 и записываем х 12 =min(18;10)=10.

В запасе поставщика А 1 осталось 8.

Находим следующий северо-западный угол х 13 =min(8;15)=8. Таким образом запас первого поставщика исчерпан - исключаем из рассмотрения первую строку.

В оставшейся таблице находим «северо-западный угол » и т.д. В результате получаем распределение поставок (см. табл.2). На каждом шаге (кроме последнего) из рассмотрения выпадали либо строка, либо столбец, а на последнем - и строка и столбец.

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

Найдем оптимальное решение транспортной задачи, выбрав первый опорный план методом минимального элемента.

Решение: Минимальный тариф c 33 =2; x 33 =min(22;15) =15.

Третий столбец вычеркиваем (обнуляем). Минимальный тариф для оставшихся клеток с 22 =4, х 22 =min(18;10) =10. Второй столбец вычеркиваем.

Для оставшихся клеток минимальный тариф с 34 =4, х 34 =min(22 - 15; 11) =7. Третью строку вычеркиваем.

Для оставшихся клеток минимальный тариф с 24 =5, х 24 =min(18-10;11-7) = 4.

Четвертый столбец вычеркиваем. Из оставшихся клеток основной таблицы минимальный тариф с 11 =6, х 11 =min(30;12) = 12. Первый столбец вычеркиваем.

Аналогично заполняем фиктивный столбец х 15 = 18, х 25 =4. Получаем первый опорный план. Количество загруженных клеток равно 3+5-1=7, т.е. выполняется необходимое условие невырожденности плана.

Таблица 3

Поставщики	Потребители
B 1		B 3	B 5
A 1
A 2
A 3

V j

Стоимость перевозки по этому плану составит:

L 1 =6*12 + 0*18 + 4*10 + 5*4 + 0*4 + 2*15 + 4*7 = 190 (д.е.). Число загруженных клеток равно m+n-1=3 + 5- 1 = 7, т.е. необходимое условие невырожденности плана выполняется. Последовательно, из уравнений, составленных для загруженных клеток, определяем потенциалы поставщиков и потребителей:

U 3 =0; V 1 =C 31 - U 3 = 5- 0 = 5; U 2 = C 21 - V 1 = 11 - 5 = 6;

V 2 = C 22 - U 2 = 4-6 = -2; V 3 = C 23 - U 2 = 8 - 6 = 2;

U 3 = C 33 - V 3 = 2 - 2 = 0; V 4 = C 34 - U 3 = 4 - 0 = 4;

V 5 = C 25 - U 2 = 0 - 6 = -6

Составим разности для свободных клеток:

12 = U 1 + V 2 - C 12 = 0 - 2 - 8 = -10

13 = U 1 + V 3 - C 13 = 0 + 2 - 13 = -11

14 = U 1 + V 4 - C 14 = 0 + 4 - 15 = -11

21 = U 2 + V 1 - C 21 = 6 + 5 - 11 = 0

23 = U 2 + V 3 - C 23 = 6 + 2 - 8 = 0

31 = U 3 + V 1 - C 31 = 0 + 5 - 5 = 0

32 = U 3 + V 2 - C 32 = 0 - 2 - 9 = -11

35 = U 3 + V 5 - C 35 = 0 - 6 - 0 = -6

Так как все разности то полученный план оптимален.

Минимальные затраты составят 190 (д.е.)

Этап I. Поиск первого опорного плана .

1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

План начинается заполняться с верхнего левого угла.

Искомый элемент равен c 11 =7. Для этого элемента запасы равны 20, потребности 25. Поскольку минимальным является 20, то вычитаем его.

x 11 = min(20,25) = 20.

Искомый элемент равен c 22 =7. Для этого элемента запасы равны 55, потребности 40. Поскольку минимальным является 40, то вычитаем его.

x 22 = min(55,40) = 40.

Искомый элемент равен c 23 =0. Для этого элемента запасы равны 15, потребности 50. Поскольку минимальным является 15, то вычитаем его.

x 23 = min(15,50) = 15.

Искомый элемент равен c 33 =10. Для этого элемента запасы равны 45, потребности 35. Поскольку минимальным является 35, то вычитаем его.

x 33 = min(45,35) = 35.

Искомый элемент равен c 34 =2. Для этого элемента запасы равны 10, потребности 30. Поскольку минимальным является 10, то вычитаем его.

x 34 = min(10,30) = 10.

Искомый элемент равен c 44 =7. Для этого элемента запасы равны 70, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x 44 = min(70,20) = 20.

Искомый элемент равен c 45 =8. Для этого элемента запасы равны 50, потребности 45. Поскольку минимальным является 45, то вычитаем его.

x 45 = min(50,45) = 45.






Потребности

2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 9. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 7*20 + 5*5 + 7*40 + 0*15 + 10*35 + 2*10 + 7*20 + 8*45 + 0*5 = 1315

Этап II. Улучшение опорного плана .

предварительные потенциалы

u 4 + v 4 = 7; -6 + u 4 = 7; u 4 = 13

u 4 + v 5 = 8; 13 + v 5 = 8; v 5 = -5

u 4 + v 6 = 0; 13 + v 6 = 0; v 6 = -13

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(1;2): 0 + 9 > 3; ? 12 = 0 + 9 - 3 = 6
(3;1): 8 + 7 > 1; ? 31 = 8 + 7 - 1 = 14
(3;2): 8 + 9 > 4; ? 32 = 8 + 9 - 4 = 13
(4;1): 13 + 7 > 3; ? 41 = 13 + 7 - 3 = 17
(4;2): 13 + 9 > 4; ? 42 = 13 + 9 - 4 = 18
(4;3): 13 + 2 > 2; ? 43 = 13 + 2 - 2 = 13

max(6,14,13,17,18,13) = 18

Выбираем максимальную оценку свободной клетки (4;2): 4

Для этого в перспективную клетку (4;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».






Потребности

Цикл приведен в таблице (4,2 > 4,4 > 3,4 > 3,3 > 2,3 > 2,2).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 4) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.






Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u i , v j . по занятым клеткам таблицы, в которых u i + v j = c ij , полагая, что u 1 = 0.

u 1 + v 1 = 7; 0 + v 1 = 7; v 1 = 7

u 2 + v 1 = 5; 7 + u 2 = 5; u 2 = -2

u 2 + v 2 = 7; -2 + v 2 = 7; v 2 = 9

u 2 + v 3 = 0; -2 + v 3 = 0; v 3 = 2

u 3 + v 3 = 10; 2 + u 3 = 10; u 3 = 8

u 3 + v 4 = 2; 8 + v 4 = 2; v 4 = -6

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(1;2): 0 + 9 > 3; ? 12 = 0 + 9 - 3 = 6
(1;5): 0 + 13 > 6; ? 15 = 0 + 13 - 6 = 7
(1;6): 0 + 5 > 0; ? 16 = 0 + 5 - 0 = 5
(2;5): -2 + 13 > 3; ? 25 = -2 + 13 - 3 = 8
(2;6): -2 + 5 > 0; ? 26 = -2 + 5 - 0 = 3
(3;1): 8 + 7 > 1; ? 31 = 8 + 7 - 1 = 14
(3;2): 8 + 9 > 4; ? 32 = 8 + 9 - 4 = 13
(3;5): 8 + 13 > 6; ? 35 = 8 + 13 - 6 = 15
(3;6): 8 + 5 > 0; ? 36 = 8 + 5 - 0 = 13

max(6,7,5,8,3,14,13,15,13) = 15

Выбираем максимальную оценку свободной клетки (3;5): 6

Для этого в перспективную клетку (3;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».






Потребности

Цикл приведен в таблице (3,5 > 3,3 > 2,3 > 2,2 > 4,2 > 4,5).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.






Потребности

u 1 + v 1 = 7; 0 + v 1 = 7; v 1 = 7

u 2 + v 1 = 5; 7 + u 2 = 5; u 2 = -2

u 2 + v 2 = 7; -2 + v 2 = 7; v 2 = 9

u 4 + v 2 = 4; 9 + u 4 = 4; u 4 = -5

u 4 + v 5 = 8; -5 + v 5 = 8; v 5 = 13

u 3 + v 5 = 6; 13 + u 3 = 6; u 3 = -7

u 3 + v 4 = 2; -7 + v 4 = 2; v 4 = 9

u 4 + v 6 = 0; -5 + v 6 = 0; v 6 = 5

u 2 + v 3 = 0; -2 + v 3 = 0; v 3 = 2

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(1;2): 0 + 9 > 3; ? 12 = 0 + 9 - 3 = 6
(1;4): 0 + 9 > 8; ? 14 = 0 + 9 - 8 = 1
(1;5): 0 + 13 > 6; ? 15 = 0 + 13 - 6 = 7
(1;6): 0 + 5 > 0; ? 16 = 0 + 5 - 0 = 5
(2;4): -2 + 9 > 2; ? 24 = -2 + 9 - 2 = 5
(2;5): -2 + 13 > 3; ? 25 = -2 + 13 - 3 = 8
(2;6): -2 + 5 > 0; ? 26 = -2 + 5 - 0 = 3

max(6,1,7,5,5,8,3) = 8

Выбираем максимальную оценку свободной клетки (2;5): 3

Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».






Потребности

Цикл приведен в таблице (2,5 > 2,2 > 4,2 > 4,5).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.






Потребности

u 1 + v 1 = 7; 0 + v 1 = 7; v 1 = 7

u 2 + v 1 = 5; 7 + u 2 = 5; u 2 = -2

u 2 + v 3 = 0; -2 + v 3 = 0; v 3 = 2

u 2 + v 5 = 3; -2 + v 5 = 3; v 5 = 5

u 3 + v 5 = 6; 5 + u 3 = 6; u 3 = 1

u 3 + v 4 = 2; 1 + v 4 = 2; v 4 = 1

u 4 + v 5 = 8; 5 + u 4 = 8; u 4 = 3

u 4 + v 2 = 4; 3 + v 2 = 4; v 2 = 1

u 4 + v 6 = 0; 3 + v 6 = 0; v 6 = -3

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(3;1): 1 + 7 > 1; ? 31 = 1 + 7 - 1 = 7
(4;1): 3 + 7 > 3; ? 41 = 3 + 7 - 3 = 7
(4;3): 3 + 2 > 2; ? 43 = 3 + 2 - 2 = 3

Выбираем максимальную оценку свободной клетки (3;1): 1

Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».






Потребности

Цикл приведен в таблице (3,1 > 3,5 > 2,5 > 2,1).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.






Потребности

u 1 + v 1 = 7; 0 + v 1 = 7; v 1 = 7

u 3 + v 5 = 6; -6 + v 5 = 6; v 5 = 12

u 2 + v 5 = 3; 12 + u 2 = 3; u 2 = -9

u 2 + v 3 = 0; -9 + v 3 = 0; v 3 = 9

u 4 + v 5 = 8; 12 + u 4 = 8; u 4 = -4

u 4 + v 2 = 4; -4 + v 2 = 4; v 2 = 8

u 4 + v 6 = 0; -4 + v 6 = 0; v 6 = 4

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(1;2): 0 + 8 > 3; ? 12 = 0 + 8 - 3 = 5
(1;3): 0 + 9 > 4; ? 13 = 0 + 9 - 4 = 5
(1;5): 0 + 12 > 6; ? 15 = 0 + 12 - 6 = 6
(1;6): 0 + 4 > 0; ? 16 = 0 + 4 - 0 = 4
(4;3): -4 + 9 > 2; ? 43 = -4 + 9 - 2 = 3

max(5,5,6,4,3) = 6

Выбираем максимальную оценку свободной клетки (1;5): 6

Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».






Потребности

Цикл приведен в таблице (1,5 > 1,1 > 3,1 > 3,5).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 5) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.






Потребности

u 1 + v 1 = 7; 0 + v 1 = 7; v 1 = 7

u 3 + v 1 = 1; 7 + u 3 = 1; u 3 = -6

u 3 + v 4 = 2; -6 + v 4 = 2; v 4 = 8

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(2;4): -3 + 8 > 2; ? 24 = -3 + 8 - 2 = 3
(4;1): 2 + 7 > 3; ? 41 = 2 + 7 - 3 = 6
(4;3): 2 + 3 > 2; ? 43 = 2 + 3 - 2 = 3
(4;4): 2 + 8 > 7; ? 44 = 2 + 8 - 7 = 3

max(3,6,3,3) = 6

Выбираем максимальную оценку свободной клетки (4;1): 3

Для этого в перспективную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».






Потребности

Цикл приведен в таблице (4,1 > 4,5 > 1,5 > 1,1).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.






Потребности

u 1 + v 5 = 6; 0 + v 5 = 6; v 5 = 6

u 2 + v 5 = 3; 6 + u 2 = 3; u 2 = -3

u 2 + v 3 = 0; -3 + v 3 = 0; v 3 = 3

u 4 + v 5 = 8; 6 + u 4 = 8; u 4 = 2

u 4 + v 1 = 3; 2 + v 1 = 3; v 1 = 1

u 3 + v 1 = 1; 1 + u 3 = 1; u 3 = 0

u 3 + v 4 = 2; 0 + v 4 = 2; v 4 = 2

u 4 + v 2 = 4; 2 + v 2 = 4; v 2 = 2

u 4 + v 6 = 0; 2 + v 6 = 0; v 6 = -2

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(4;3): 2 + 3 > 2; ? 43 = 2 + 3 - 2 = 3

Выбираем максимальную оценку свободной клетки (4;3): 2

Для этого в перспективную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».






Потребности

Цикл приведен в таблице (4,3 > 4,5 > 2,5 > 2,3).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 5) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.






Потребности

u 1 + v 5 = 6; 0 + v 5 = 6; v 5 = 6

u 2 + v 5 = 3; 6 + u 2 = 3; u 2 = -3

u 2 + v 3 = 0; -3 + v 3 = 0; v 3 = 3

u 4 + v 3 = 2; 3 + u 4 = 2; u 4 = -1

u 4 + v 1 = 3; -1 + v 1 = 3; v 1 = 4

u 3 + v 1 = 1; 4 + u 3 = 1; u 3 = -3

u 3 + v 4 = 2; -3 + v 4 = 2; v 4 = 5

u 4 + v 2 = 4; -1 + v 2 = 4; v 2 = 5

u 4 + v 6 = 0; -1 + v 6 = 0; v 6 = 1

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(1;2): 0 + 5 > 3; ? 12 = 0 + 5 - 3 = 2
(1;6): 0 + 1 > 0; ? 16 = 0 + 1 - 0 = 1

Выбираем максимальную оценку свободной клетки (1;2): 3

Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».






Потребности

Цикл приведен в таблице (1,2 > 1,5 > 2,5 > 2,3 > 4,3 > 4,2).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 5) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.






Потребности

u 1 + v 2 = 3; 0 + v 2 = 3; v 2 = 3

u 4 + v 2 = 4; 3 + u 4 = 4; u 4 = 1

u 4 + v 1 = 3; 1 + v 1 = 3; v 1 = 2

u 3 + v 1 = 1; 2 + u 3 = 1; u 3 = -1

u 3 + v 4 = 2; -1 + v 4 = 2; v 4 = 3

u 4 + v 3 = 2; 1 + v 3 = 2; v 3 = 1

u 2 + v 3 = 0; 1 + u 2 = 0; u 2 = -1

u 2 + v 5 = 3; -1 + v 5 = 3; v 5 = 4

u 4 + v 6 = 0; 1 + v 6 = 0; v 6 = -1

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u i + v j ? c ij .

Минимальные затраты составят: F(x) = 3*20 + 0*15 + 3*45 + 1*15 + 2*30 + 3*10 + 4*20 + 2*35 + 0*5 = 450

Анализ оптимального плана .

Из 2-го склада необходимо груз направить в 3-й магазин (15), в 5-й магазин (45)

Из 3-го склада необходимо груз направить в 1-й магазин (15), в 4-й магазин (30)

Из 4-го склада необходимо груз направить в 1-й магазин (10), в 2-й магазин (20), в 3-й магазин (35)

На 4-ом складе остался невостребованным груз в количестве 5 ед.

Оптимальный план является вырожденным, так как базисная переменная x 46 =0.

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

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

Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно m+n-1 и векторы условий, соответствующие этим клеткам, линейно независимы.

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

Составить опорное решение методом северо-западного угла транспортной задачи, в которой 5 поставщиков и 5 потребителей. данные записаны в таблице 6

Таблица 6

Распределяем запасы первого поставщика. Так как его запасы меньше запросов первого потребителя, то в клетку (1,1) записываем перевозку и исключаем из рассмотрения первого поставщика. Определяем оставшиеся неудовлетворенными запросы первого потребителя.

Распределяем запасы второго поставщика. Так как его запасы, меньше запросов первого потребителя, то записываем в клетку (2,1) перевозку и исключаем из рассмотрения второго поставщика. Определяем оставшиеся неудовлетворенными запросы первого потребителя.

Распределяем запасы третьего поставщика. Так как его запасы больше запросов первого потребителя, то записываем в клетку (3,1) перевозку и исключаем из рассмотрения первого потребителя. Определяем оставшиеся неудовлетворенными запросы третьего поставщика.

Распределяем запасы третьего поставщика. Так как его запасы меньше запросов второго потребителя, то в клетку (3,2) записываем перевозку и исключаем из рассмотрения третьего поставщика. Определяем оставшиеся неудовлетворенными запросы второго потребителя.

Распределяем запасы четвертого поставщика. Так как его запасы больше запросов второго потребителя, то записываем в клетку (4,2) перевозку и исключаем из рассмотрения второго потребителя. Определяем оставшиеся неудовлетворенными запросы четвертого поставщика.

Распределяем запасы четвертого поставщика. Так как его запасы меньше запросов третьего потребителя, то в клетку (4,3) записываем перевозку и исключаем из рассмотрения четвертого поставщика. Определяем оставшиеся неудовлетворенными запросы третьего потребителя.

Распределяем запасы пятого поставщика. Так как его запасы больше запросов третьего потребителя, то в клетку (5,3) записываем перевозку и исключаем из рассмотрения третьего потребителя. Определяем оставшиеся неудовлетворенными запасы пятого поставщика.

Распределяем запасы пятого поставщика. Так как его запасы больше запросов четвертого потребителя, то в клетку (5,4) записываем перевозку и исключаем из рассмотрения четвертого потребителя. Определяем оставшиеся неудовлетворенными запасы пятого поставщика.

Распределяем запасы пятого поставщика. Так как его запасы равны запросам пятого потребителя, то в клетку (5,5) записываем перевозку и исключаем из рассмотрения пятого поставщика и пятого потребителя.

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

Результаты построения опорного решения приведены в таблице 7.

Западного

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

Теорема 38.2 Свойство системы ограничений транспортной задачи

Ранг системы векторов-условий транспортной задачи равен N=m+n-1 (m — поставщики, n-потребители)

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

Ввиду того, что ранг системы векторов-условий транспортной задачи равен m+n — 1, опорное решение не может иметь отличных от нуля координат более m+n-1. Число отличных от нуля координат невырожденного опорного решения равняется m+n-1, а для вырожденного опорного решения меньше m+n-1

Цикл

Циклом называется такая последовательность клеток таблицы транспортной задачи (i 1 , j 1),(i 1 , j 2),(i 2 , j 2),...,(i k , j 1), в которой две и только две соседние клетки распложены в одной строке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.

Цикл изображают в виде таблицы транспортной задачи в виде замкнутой ломаной линии. В цикле любая клетка является угловой, в которой происходит поворот звена ломаной линии на 90 градусов. Простейшие циклы изображены на рисунке 38.1

Теорема 38.3
Допустимое решение транспортной задачи X=(x ij) является опорным тогда и только тогда, когда из занятых клеток таблицы нельзя образовать ни одного цикла.

Метод вычеркивания позволяет проверить, является ли данное решение транспортной задачи опорным.

Пусть допустимое решение транспортной задачи, которое имеет m+n-1 отличных от нуля координат, записано в таблицу. Чтобы данное решение было опорным, векторы-условий, соответствующие положительным координатам, а также базисным нулям, должны быть линейно независимыми. Для этого занятые решением клетки таблицы должны быть расположены так, чтобы нельзя было из них образовать цикл.

Строка или столбец таблицы с одной занятой клеткой не может входить в какой-либо цикл, так как цикл имеет две и только две клетки в каждой строке или столбце. Следовательно, чтобы вычеркнуть сначало либо все строки таблицы, содержащие по одной занятой клетке, либо все столбцы, содержащие по одной занятой клетке, далее вернуться к столбцам (строкам) и продолжать вычеркивание.

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

Если же после вычеркивания останется часть клеток, то эти клетки образуют цикл, система соответствующих векторов-условий является линейно зависимой, а решение не является опорным.

Примеры "вычеркнутого" (опорного) и "не вычеркнутого" (не опорного решений):

Логика вычеркивания :

Вычеркнуть все столбцы, в которых всего одна занятая клетка (5 0 0), (0 9 0)
Вычеркнуть все строки, в которых всего одна занятая клетка (0 15), (2 0)
Повторить цикл (7) (1)

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

Заполнение таблицы транспортной задачи начинается с левого верхнего угла, поэтому и называется метод северо-западного угла.

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

Пример 38.1

Составить опорное решение, используя метод северо-западного угла.

1. Распределяем запасы 1-го поставщика.
Если запасы первого поставщика больше запросов первого потребителя, то записываем в клетку (1,1) сумму запроса первого потребителя и переходим ко второму потребителю. Если же запасы первого поставщика меньше запросов первого потребителя, то записываем в клетку (1,1) сумму запасов первого поставщика, исключаем из рассмотрения первого поставщика и переходим ко второму поставщику.

Пример : так как его запасы a 1 =100 меньше запросов первого потребителя b 1 =100, то в клетку (1,1) записываем перевозку x 11 =100 и исключаем из рассмотрения поставщика.
Определяем оставшиеся неудовлетворенными запросы 1-го потребителя b 1 = 150-100=50.

2. Распределяем запасы 2-го поставщика.
Так как его запасы a 2 = 250 больше оставшихся неудовлетворенными запросов 1-го потребителя b 1 =50, то в клетку (2,1) записываем перевозку x 21 =50 и исключаем из рассмотрения 1-го потребителя.
Определяем оставшиеся запасы 2-го поставщика a 2 = a 2 — b 1 = 250-50=200. Так как оставшиеся запасы 2-го поставщика равны запросам 2-го потребителя, то в клетку (2,2) записываем x 22 =200 и исключаем по своему усмотрению либо 2-го поставщика, либо 2-го потребителя. В нашем примере мы исключили 2-го поставщика.
Вычисляем оставшиеся неудовлетворенными запросы второго потребителя b 2 =b 2 -a 2 =200-200=0.

	150	200	100	100
100	100
250	50	200			250-50=200 200-200=0
200
	150-100-50=0

3. Распределяем запасы 3-го поставщика.
Важно! В предыдущем шаге у нас был выбор исключать поставщика или потребителя. Так как мы исключили поставщика, то запросы 2-го потребителя все же остались (хоть и равны нулю).
Мы должны записать оставшиеся запросы равные нулю в клетку (3,2)
Это связано с тем, что если в очередную клетку таблицы (i,j) требуется поставить перевозку, а поставщик с номером i или потребитель с номером j имеет нулевые запасы или запросы, то ставится в клетку перевозка, равная нулю (базисный нуль), и после этого исключается из рассмотрения либо соответствующий поставщик, либо потребитель.
Таким образом, в таблицу заносятся только базисные нули, остальные клетки с нулевыми перевозками остаются пустыми.

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

Так как в предыдущем шаге мы исключили из рассмотрения второго поставщика, то в клетку (3,2) записываем x 32 =0 и исключаем второго потребителя.

Запасы 3-го поставщика не изменились. В клекту (3,3) записываем x 33 =100 и исключаем третьего потребителя. В клетку (3,4) записываем x 34 =100. Ввиду того, что наша задача с правильным балансом, запасы всех поставащиков исчерпаны и запросы всех потребителей удовлетворены полностью и одновременно.

Опорное решение
	150	200	100	100
100	100
250	50	200
200		0	100	100

4. Проверяем правильность построения опорного решения.
Число занятых клеток должно быть равно N=m(поставщики)+m(потребители) — 1=3+4 — 1=6.
Применяя метод вычеркивания, убеждаемся, что найденное решение является "вычеркиваемым" (звездочкой отмечен базисный нуль).

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

Потребности

Метод минимальной стоимости прост и позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи C=(c ij).

Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости:

и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую , заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы груза использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь затем поставщик исключается из рассмотрения. Аналогично с потребителем.

Пример 38.2

Используя метод минимальной стоимости построить начальное опорное решение транспортной задачи.

1. Запишем отдельно матрицу стоимостей для того, чтобы было удобнее выбирать минимальные стоимости.

2. Среди элементов матрицы стоимостей выбираем наименьшую стоимость C 11 =1, отмечаем ее кружочком. Данная стоимость имеет место при перевозке груза от 1-го поставщика 1-му потребителю. В соответствующую клетку записываем максимально возможный объем перевозки:
x 11 = min {a 1 ; b 1 } = min {60; 40} =40 т.е. минимум между запасами 1-го поставщика и запросами 1-го потребителя.

2.1. Запасы 1-го поставщика уменьшаем на 40.
2.2. Исключаем из рассмотрения 1-го потребителя, так как его запросы полностью удовлетворены. В матрице C вычеркиваем 1-ый столбец.

3. В оставшейся части матрицы C минимальной стоимостью является стоимость C 14 =2. Максимально возможная перевозка, которую можно осуществить от 1-го поставщика 4-му потребителю равна x 14 = min {a 1 "; b 4 } = min {20; 60} = 20 , где a 1 со штрихом это оставшиеся запасы первого поставщика.
3.1. Запасы 1-го поставщика исчерпаны, поэтому исключаем его из рассмотрения.
3.2. Запросы 4-го потребителя уменьшаем на 20.

4. В оставшейся части матрицы С минимальная стоимость C 24 =C 32 =3. Заполняем одну из двух клеток таблицы (2,4) или (3,2). Пусть в клетку запишем x 24 = min {a 2 ; b 4 } = min {80; 40} =40 .
4.1. Запросы 4-го потребителя удовлетворены. Исключаем его из рассмотрения вычеркивая 4-й столбец в матрице C.
4.2. Уменьшаем запасы 2-го поставщика 80-40=40.

5. В оставшейся части матрицы C минимальная стоимость C 32 =3. Запишем в клетку (3,2) таблицы перевозку x 32 = min {a 3 ; b 2 } = min {100; 60} =60 .
5.1. Исключим из рассмотрения 2-го потребителя. Из матрицы C исключаем 2-ой столбец.
5.2. Уменьшим запасы 3-го поставщика 100-60=40

6. В оставшейся части матрицы C минимальная стоимость C 33 =6. Запишем в клетку (3,3) таблицы перевозку x 33 = min {a 3 "; b 3 } = min {40; 80} =40
6.1. Исключим из рассмотрения 3-го поставщика, а из матрицы C 3-ю строку.
6.2. Определяем оставшиеся запросы 3-го потребителя 80-40=40.

7. В матрице C остался единственный элемент C 23 =8. Записываем в клетку таблицы (2,3) перевозку X 23 =40.

8. Проверяем правильность построения опорного решения.
Число занятых клеток таблицы равно N=m+n — 1=3+4 -1.
Методом вычеркивания проверяем линейную независимость векторов-условий, соответствующих положительным координатам решения. Порядок вычеркивания показан на матрице X:

Вывод: Решение методом минимальной стоимости (таблица 38.3) является "вычеркиваемым" и, следовательно опорным.