Характеристика типовых задач математического моделирования и подходов к их решению

Пусть Хij – количество груза, отправляемого с базы Аi в пункт Вj.

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

 

Таблица 2.5.1

Исходная таблица

Пункт направления	В1	В2	В3	В4	В5	Запасы, аi
A1	2	10	15	14	4	150
A2	3	7	12	5	8	170
A3	21	18	6	13	16	260
Потребности	100	90	160	150	80	580

 

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

 

 

2.6 Нахождение опорного плана транспортной задачи методом северо-западного угла

 

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

 

Таблица 2.6.1

Пункт направления	B1	B2	B3	B4	B5	Запасы
A1	2[100]	10[50]	15	14	4	150
A2	3	7[40]	12[130]	5	8	170
A3	21	18	6[30]	13[150]	16[80]	260
Потребности	100	90	160	150	80	580

 

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

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

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

 

F(x) = 2*100 + 10*50 + 7*40 + 12*130 + 6*30 + 13*150 + 16*80 = 5950

 

2.7 Нахождение опорного плана транспортной задачи методом наименьшего элемента

 

Используя метод наименьшего элемента, построим первый опорный план транспортной задачи (Табл. 2.7.1).

 

Таблица 2.7.1

Пункт направления	B1	B2	B3	B4	B5	Запасы
A1	2[100]	10	15	14	4[50]	150
A2	3	7[20]	12	5[150]	8	170
A3	21	18[70]	6[160]	13	16[30]	260
Потребности	100	90	160	150	80	580

 

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

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

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

 

F(x) = 2*100 + 4*50 + 7*20 + 5*150 + 18*70 + 6*160 + 16*30 = 3990

2.8 Решение транспортной задачи методом потенциалов

 

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

 

Таблица 2.8.1

	v1=2	v2=10	v3=15	v4=22	v5=25
u1=0	2[100]	10[50]	15	14	4
u2=-3	3	7[40]	12[130]	5	8
u3=-9	21	18	6[30]	13[150]	16[80]

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij (Табл. 2.8.1).

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

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

 

Таблица 2.8.2

Пункт направления	B1	B2	B3	B4	B5	Запасы
A1	2[100]	10[50][-]	15	14	4[+]	150
A2	3	7[40][+]	12[130][-]	5	8	170
A3	21	18	6[30][+]	13[150]	16[80][-]	260
Потребности	100	90	160	150	80	580

 

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

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е.

 

у = min (1, 2) = 50

 

Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план (Табл. 2.8.3).

 

Таблица 2.8.3

Пункт направления	B1	B2	B3	B4	B5	Запасы
1	2[100]	10	15	14	4[50]	150
2	3	7[90]	12[80]	5	8	170
3	21	18	6[80]	13[150]	16[30]	260
Потребности	100	90	160	150	80	580

 

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

 

Таблица 2.8.4

	v1=2	v2=-11	v3=-6	v4=1	v5=4
u1=0	2[100]	10	15	14	4[50]
u2=18	3	7[90]	12[80]	5	8
u3=12	21	18	6[80]	13[150]	16[30]

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij (Табл. 2.8.4).

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

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

 

Таблица 2.8.5

Пункт направления	B1	B2	B3	B4	B5	Запасы
A1	2[100][-]	10	15	14	4[50][+]	150
A2	3[+]	7[90]	12[80][-]	5	8	170
A3	21	18	6[80][+]	13[150]	16[30][-]	260
Потребности	100	90	160	150	80

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

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

 

Таблица 2.8.6

Пункт направления	B1	B2	B3	B4	B5	Запасы
A1	2[70]	10	15	14	4[80]	150
A2	3[30]	7[90]	12[50]	5	8	170
A3	21	18	6[110]	13[150]	16	260
Потребности	100	90	160	150	80	580

 

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

 

Таблица 2.8.7

	v1=2	v2=6	v3=11	v4=18	v5=4
u1=0	2[70]	10	15	14	4[80]
u2=1	3[30]	7[90]	12[50]	5	8
u3=-5	21	18	6[110]	13[150]	16

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij (Табл. 2.8.7).

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

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

 

 

Таблица 2.8.8

Пункт направления	B1	B2	B3	B4	B5	Запасы
A1	2[70]	10	15	14	4[80]	150
A 2	3[30]	7[90]	12[50][-]	5[+]	8	170
A 3	21	18	6[110][+]	13[150][-]	16	260
Потребности	100	90	160	150	80	580