Контрольная работа по дисциплине "Программирование"

 

КОНТРОЛЬНАЯ РАБОТА

Вариант-34

 

Задача 1. Решить транспортную задачу по критерию стоимости.

Матрица цен:                         Емкость АТС:                       Потребность районов:

                                     

 

Решение:

 

Данная транспортная задача имеет открытый тип, так как суммарный запас (предложение)  емкостей АТС  больше суммарных потребностей районов:

Чтобы привести задачу к закрытому типу, вводим фиктивного потребителя B6, потребность которого составляет 269-99=70, а стоимость перевозки равна 0.

 

Обозначим через – объем электроэнергии, переданной от поставщика (станции) потребителю (району) .

Тогда система ограничений примет вид: 

 

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

Тогда целевую функцию можно записать:

Условие неотрицательности объемов перевозок:

 

1. Найдем методом минимального элемента допустимый план перевозок:

 

Потребители   Поставщики	B1	B2	B3	B4	B5	B6*	Запасы
A1	7    -	12    -	2     38	14    -	2     -	0    -	38
A2	19   -	23    -	8     4	13    7	13 11	0     16	38
A3	14    -	8     -	24    -	8      47	23    -	0      -	47
A4	8     47	6     -	8     -	12    -	9    -	0    -	47
A5	17    18	4    27	32     -	13     -	19	0    54	99
Потребности	65	27	42	54	11	70

 

Загрузку начинаем с клетки, которой соответствует наименьший тариф :

Такой   клеткой является клетка (1,3), для которой  .

Помещаем в клетку . Из дальнейшего рассмотрения исключаем первую строку (запасы на станции А1 закончились).

Снова ищем клетку с минимальным тарифом: это клетка  (5, 2), для которой с=4. Помещаем в нее . Исключаем второй столбец. И т.д.

 В результате полного  распределения, получаем исходное  опорное решение:

 

   ,

F(x) = 2*38 + 8*4 + 13*7 + 13*11 + 0*16 + 8*47 + 8*47 + 17*18 + 4*27 + 0*54  = 1508

 

2)   Проверим план  X0 на  оптимальность методом потенциалов:

Поставщику ставим в соответствие потенциалы  ,  а потребителю и определяем их.

Назначаем ,  и находим все остальные потенциалы из условия, что для занятых клеток должны выполняться условия:

u1 + v3 = 2; 0 + v3 = 2; v3 = 2

u2 + v3 = 8; 2 + u2 = 8; u2 = 6

u2 + v4 = 13; 6 + v4 = 13; v4 = 7

u3 + v4 = 8; 7 + u3 = 8; u3 = 1

u2 + v5 = 13; 6 + v5 = 13; v5 = 7

u2 + v6 = 0; 6 + v6 = 0; v6 = -6

u5 + v6 = 0; -6 + u5 = 0; u5 = 6

u5 + v1 = 17; 6 + v1 = 17; v1 = 11

u4 + v1 = 8; 11 + u4 = 8; u4 = -3

u5 + v2 = 4; 6 + v2 = 4; v2 = -2

 

	v1=11	v2=-2	v3=2	v4=7	v5=7	v6=-6
u1=0	7	12	2   38	14	2	0
u2=6	19	23	8[4	13  7	13   [11	0 16
u3=1	14	8	24	8   47	23	0
u4=-3	8  47	6	8	12	9	0
u5=6	17 18	4   27	32	13	19	0  54

Для всех свободных клеток находим  оценки из соотношения

.

 

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

(1;1): 0 + 11 > 7; ∆11 = 0 + 11 - 7 = 4

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

max(4,5) = 5

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

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

 

	1	2	3	4	5	6	Запасы
1	7	12	2  38 [-]	14	2  [+]	0	38
2	19	23	8   4[+]	13  7	13  11[-]	0  16	38
3	14	8	24	8  [47	23	0	47
4	8  47	6	8	12	9	0	47
5	17  18	4  27	32	13	19	0  54	99
Потребности	65	27	42	54	11	70

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

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

 

	1	2	3	4	5	6	Запасы
1	7	12	2  27	14	2  11	0	38
2	19	23	8  15	13  7	13	0  16	38
3	14	8	24	8  47	23	0	47
4	8  47	6	8	12	9	0	47
5	17  18	4  27	32	13	19	0  54	99
Потребности	65	27	42	54	11	70

Проверим оптимальность опорного плана. Находим потенциалы и оценки:

 

	v1=11	v2=-2	v3=2	v4=7	v5=2	v6=-6
u1=0	7	12	2  27	14	2  11	0
u2=6	19	23	8  15	13  7	13	0  16
u3=1	14	8	24	8  47	23	0
u4=-3	8  47	6	8	12	9	0
u5=6	17[18]	4[27]	32	13	19	0[54]

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

(1;1): 0 + 11 > 7; ∆11 = 0 + 11 - 7 = 4

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

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

 

	1	2	3	4	5	6	Запасы
1	7  +	12	2  27  -	14	2  11	0	38
2	19	23	8  15  +	13  7	13	0  16  -	38
3	14	8	24	8  47	23	0	47
4	8  47	6	8	12	9	0	47
5	17[18]  -	4[27]	32	13	19	0[54]  +	99
Потребности	65	27	42	54	11	70

 

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

В результате получим новый опорный план.

 

	1	2	3	4	5	6	Запасы
1	7  16	12	2  11	14	2  11	0	38
2	19	23	8  31	13  7	13	0	38
3	14	8	24	8 47	23	0	47
4	8  47	6	8	12	9	0	47
5	17  2	4  27	32	13	19	0  70	99
Потребности	65	27	42	54	11	70