Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Значение целевой функции изменилось на 56 единиц по сравнению с предыдущим этапом.

Этап 2

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1. . m, j=1. . n), просматривая все занятые клетки.

Потенциалы Ui, Vj:

U1=0 V1=C1,1-U1= 1 U4=C1,4-V1= 0 V4=C4,4-U4= 5 U3=C4,3-V4= - 2 V3=C3,3-U3= 9 U2=C3,2-V3= - 8 V2=C2,2-U2= 9 Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток

S1,2 = c1,2 - (u1 + v2) = - 2.

S1,3 = c1,3 - (u1 + v3) = - 6.

S1,4 = c1,4 - (u1 + v4) = 1.

S2,1 = c2,1 - (u2 + v1) = 14.

S2,4 = c2,4 - (u2 + v4) = 7.

S3,1 = c3,1 - (u3 + v1) = 4.

S3,2 = c3,2 - (u3 + v2) = - 4.

S4,2 = c4,2 - (u4 + v2) = - 6.

S4,3 = c4,3 - (u4 + v3) = - 4.

Поставщик	Потребитель					Запасы груза
	B1	B2	B3	B4
A1	- 1 21	7	+ 3	6	21
A2	7	1 19	1 7	4	26
A3	3	3	- 7 17	+ 3 8	25
A4	+ 1 4	3	5	- 5 20	24
Потребность	25	19	24	28

Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,3). Для нее оценка равна - 6.

Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Делаем сдвиг по циклу на величину перевозок в 17 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".

В результате перемещения по циклу получим новый план:

Стоимость перевозок Z= 192

Значение целевой функции изменилось на 102 единиц по сравнению с предыдущим этапом.

Этап 3

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1. . m, j=1. . n), просматривая все занятые клетки.

Потенциалы Ui, Vj:

U1=0 V1=C1,1-U1= 1 V3=C1,3-U1= 3 U4=C1,4-V1= 0 U2=C3,2-V3= - 2 V2=C2,2-U2= 3 V4=C4,4-U4= 5 U3=C4,3-V4= - 2 Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток

S1,2 = c1,2 - (u1 + v2) = 4.

S1,4 = c1,4 - (u1 + v4) = 1.

S2,1 = c2,1 - (u2 + v1) = 8.

S2,4 = c2,4 - (u2 + v4) = 1.

S3,1 = c3,1 - (u3 + v1) = 4.

S3,2 = c3,2 - (u3 + v2) = 2.

S3,3 = c3,3 - (u3 + v3) = 6.

S4,2 = c4,2 - (u4 + v2) = 0.

S4,3 = c4,3 - (u4 + v3) = 2.

Так как все оценки Si,j>=0, то полученный план является оптимальным.

Транспортная задача решена.

Стоимость перевозок F= 192

Метод минимального элемента

1111 33333 4 55 6 777

Пункт назначения Пункт отправления	1	2	3	4	Запасы
1	1 21	7 -	3 -	6 -	21
2	7 -	1 19	1 7	4 -	26
3	3 -	3 -	7 -	3 25	25
4	1 4	3 -	5 17	5 3	24
Потребности	25	19	24	28	= 96

Z = 122+119+17+325+14+517+53=226, в методе северо-западного угла стоимость перевозки была выше и составляла 350.

Распределительный метод

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

Характеристики

Список файлов ответов (шпаргалок)