Задача№1 (стр. 2 )

	1	2	3	4	Запасы
1	30	42	53	31	17
2	42	25	61	20	18
3	31	40	52	40	16
Потребности	8	4	8	8

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

∑a = 17 + 18 + 16 = 51

∑b = 8 + 4 + 8 + 8 = 28

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

	1	2	3	4	5	Запасы
1	30	42	53	31	0	17
2	42	25	61	20	0	18
3	31	40	52	40	0	16
Потребности	8	4	8	8	23

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

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

	1	2	3	4	5	Запасы
1	30[8]	42	53	31	0[9]	17
2	42	25[4]	61	20[8]	0[6]	18
3	31	40	52[8]	40	0[8]	16
Потребности	8	4	8	8	23

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

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

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

F(x) = 30*8 + 0*9 + 25*4 + 20*8 + 0*6 + 52*8 + 0*8 = 916

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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

	v1=30	v2=25	v3=52	v4=20	v5=0
u1=0	30[8]	42	53	31	0[9]
u2=0	42	25[4]	61	20[8]	0[6]
u3=0	31	40	52[8]	40	0[8]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.

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

F(x) = 30*8 + 0*9 + 25*4 + 20*8 + 0*6 + 52*8 + 0*8 = 916

Задача №5

Исходная матрица имеет вид:

13	13	15	8	9
12	11	6	14	6
13	7	9	5	6
10	10	7	8	7
12	11	6	9	9

Шаг №1.

1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

5	5	7	0	1	8
6	5	0	8	0	6
8	2	4	0	1	5
3	3	0	1	0	7
6	5	0	3	3	6

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент: