Контрольная работа: Методы решения транспортных задач

1) Выберем переменными задачи x₁ – изделий вида А1 ; x₂ – изделий вида А2 .

Составим систему ограничений в виде неравенств

Составим целевую функцию z (x) = 25·x₁ + 17·x₂ → max, т.е. обеспечить максимальную выручку от реализации готовой продукции.

2) Найдем решение сформулированной задачи, используя ее геометрическую интерпретацию. Сначала определим многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств и найдем соответствующие прямые

Эти прямые изображены на рис. 1. Пересечение полученных полуплоскостей и определяет многоугольник решений данной задачи.

Рис. 1. Графическое представление математической модели

Как видно из рис. 1, многоугольником решений является пятиугольник ОАВС D . Координаты любой точки, принадлежащей данному пятиугольнику, удовлетворяют данной системе неравенств и условию неотрицательности переменных. Поэтому сформулированная задача будет решена, если мы сможем найти точку, принадлежащую пятиугольнику ОАВС D , в которой функция z принимает максимальное значение. Чтобы найти указанную точку, построим вектор , перпендикулярный прямой 25·x₁ + 17·x₂ = h , где h – некоторая постоянная такая, что данная прямая имеет общие точки с многоугольником решений.

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

Находим координаты точки C как координаты точки пересечения прямых 8·x₁ + 6·x₂ = 848 и 5·x₁ + 2·x₂ = 432.

Решив эту систему уравнений, получим , . Итак, выручка от реализации будет наибольшей, если в плане по производству содержится выпуск 64 изделий А1 и 56 изделий А2 , и, составляет 25·64 + 17·56 = 2552 ден. ед.

3) Запишем данную задачу в форме основной задачи линейного программирования. Для этого от ограничений-неравенств перейдем к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений

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

	Базисные переменные	25	17	0	0	0
0 0 0		848 532 432	8 3 5	6 5 2	1 0 0	0 1 0	0 0 1
		0	-25	-17	0	0	0

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

Вторая итерация

	Базисные переменные	25	17	0	0	0
0 0 25		784/5 1364/5 432/5	0 0 1	14/5 19/5 2/5	1 0 0	0 1 0	-8/5 -3/5 1/5
		2160	0	-7	0	0	0

Третья итерация

	Базисные переменные	25	17	0	0	0
17 0 25		56 60 64	0 0 1	1 0 0	5/14 -19/14 -1/7	0 1 0	-4/7 11/7 3/7
		2552	0	0	5/2	0	1

Из табл. видно, что найденный новый опорный план исходной задачи X* = (64;56; 0; 60; 0) является оптимальным. При этом maxz = 2552.

Итак, выручка от реализации будет наибольшей, если в плане по производству содержится выпуск 64 изделий А1 и 56 изделий А2 , и, составляет 2552 ден. ед.

4)Для данной задачи , тогда . Число переменных в двойственной задаче равно числу уравнений в исходной задаче, т.е. 3. Коэффициенты в целевой функции двойственной задачи являются свободными членами неравенств-ограничений, т.е. числами 848, 532, 432. Т.к., в исходной системе ограничения представлены неравенствами, то в двойственной задаче переменные являются неотрицательными.

Следовательно, двойственная задача такова: найти минимум функции z ^* (x) = 848·y₁ + 532·y₂ + 432·y₃ при условиях

Из последней симплекс-таблицы (итерация 3) видно, что двойственная задача имеет решение , , .

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

Примем некоторые обозначения: i - индекс строки j - индекс столбца m - количество поставщиков n - количество потребителей X_i,j - перевозка между поставщиком A_i и потребителем B_j .

Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям. Находим опорный план по правилу северо-западного угла: Введем некоторые обозначения: A_i ^* - излишек нераспределенного груза от поставщика A_i B_j ^* - недостача в поставке груза потребителю B_j

Помещаем в клетку (1,1) меньшее из чисел A₁ ^* =370 и B₁ ^* =300 Так как спрос потребителя B₁ удовлетворен, то столбец 1 в дальнейшем в расчет не принимается Помещаем в клетку (1,2) меньшее из чисел A₁ ^* =70 и B₂ ^* =280 Так как запасы поставщика A₁ исчерпаны, то строка 1 в дальнейшем в расчет не принимается Помещаем в клетку (2,2) меньшее из чисел A₂ ^* =450 и B₂ ^* =210 Так как спрос потребителя B₂ удовлетворен, то столбец 2 в дальнейшем в расчет не принимается Помещаем в клетку (2,3) меньшее из чисел A₂ ^* =240 и B₃ ^* =330 Так как запасы поставщика A₂ исчерпаны, то строка 2 в дальнейшем в расчет не принимается Помещаем в клетку (3,3) меньшее из чисел A₃ ^* =480 и B₃ ^* =90 Так как спрос потребителя B₃ удовлетворен, то столбец 3 в дальнейшем в расчет не принимается Помещаем в клетку (3,4) меньшее из чисел A₃ ^* =390 и B₄ ^* =290 Так как спрос потребителя B₄ удовлетворен, то столбец 4 в дальнейшем в расчет не принимается Помещаем в клетку (3,5) меньшее из чисел A₃ ^* =100 и B₅ ^* =100

Целевая функция F=11320

Решаем задачу распределительным методом:

Этап 1

Определим значения оценок S_i,j для всех свободных клеток (неоптимальные выделены красным цветом ). Для этого строим цикл для каждой свободной клетки и, перемещаясь по клеткам цикла, складываем тарифы клеток. При этом тарифы в нечетных клетках берутся со знаком "плюс", в четных - со знаком "минус". S_1,3 = c_1,3 -c_1,2 +c_2,2 -c_2,3 = 12 S_1,4 = c_1,4 -c_1,2 +c_2,2 -c_2,3 +c_3,3 -c_3,4 = 4 S_1,5 = c_1,5 -c_1,2 +c_2,2 -c_2,3 +c_3,3 -c_3,5 = -3 S_2,1 = c_2,1 -c_2,2 +c_1,2 -c_1,1 = 5 S_2,4 = c_2,4 -c_2,3 +c_3,3 -c_3,4 = 8 S_2,5 = c_2,5 -c_2,3 +c_3,3 -c_3,5 = -2 S_3,1 = c_3,1 -c_3,3 +c_2,3 -c_2,2 +c_1,2 -c_1,1 = -14 S_3,2 = c_3,2 -c_3,3 +c_2,3 -c_2,2 = -6

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

Перемещаем по циклу груз величиной в 90 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:

Целевая функция F= 10060

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

Этап 2

Определим значения оценок S_i,j для всех свободных клеток (неоптимальные выделены красным цветом ). Для этого строим цикл для каждой свободной клетки и, перемещаясь по клеткам цикла, складываем тарифы клеток. При этом тарифы в нечетных клетках берутся со знаком "плюс", в четных - со знаком "минус". S_1,3 = c_1,3 -c_1,2 +c_2,2 -c_2,3 = 12 S_1,4 = c_1,4 -c_1,1 +c_3,1 -c_3,4 = -10 S_1,5 = c_1,5 -c_1,1 +c_3,1 -c_3,5 = -17 S_2,1 = c_2,1 -c_2,2 +c_1,2 -c_1,1 = 5 S_2,4 = c_2,4 -c_2,2 +c_1,2 -c_1,1 +c_3,1 -c_3,4 = -6 S_2,5 = c_2,5 -c_2,2 +c_1,2 -c_1,1 +c_3,1 -c_3,5 = -16 S_3,2 = c_3,2 -c_3,1 +c_1,1 -c_1,2 = 8 S_3,3 = c_3,3 -c_3,1 +c_1,1 -c_1,2 +c_2,2 -c_2,3 = 14

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

Перемещаем по циклу груз величиной в 100 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:

Целевая функция F= 8360

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

Этап 3

Определим значения оценок S_i,j для всех свободных клеток (неоптимальные выделены красным цветом ). Для этого строим цикл для каждой свободной клетки и, перемещаясь по клеткам цикла, складываем тарифы клеток. При этом тарифы в нечетных клетках берутся со знаком "плюс", в четных - со знаком "минус". S_1,3 = c_1,3 -c_1,2 +c_2,2 -c_2,3 = 12 S_1,4 = c_1,4 -c_1,1 +c_3,1 -c_3,4 = -10 S_2,1 = c_2,1 -c_2,2 +c_1,2 -c_1,1 = 5 S_2,4 = c_2,4 -c_2,2 +c_1,2 -c_1,1 +c_3,1 -c_3,4 = -6 S_2,5 = c_2,5 -c_2,2 +c_1,2 -c_1,5 = 1 S_3,2 = c_3,2 -c_3,1 +c_1,1 -c_1,2 = 8 S_3,3 = c_3,3 -c_3,1 +c_1,1 -c_1,2 +c_2,2 -c_2,3 = 14 S_3,5 = c_3,5 -c_3,1 +c_1,1 -c_1,5 = 17

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

Перемещаем по циклу груз величиной в 110 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:

Целевая функция F= 7260

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

Этап 4

Определим значения оценок S_i,j для всех свободных клеток (неоптимальные выделены красным цветом ). Для этого строим цикл для каждой свободной клетки и, перемещаясь по клеткам цикла, складываем тарифы клеток. При этом тарифы в нечетных клетках берутся со знаком "плюс", в четных - со знаком "минус". S_1,1 = c_1,1 -c_1,4 +c_3,4 -c_3,1 = 10 S_1,3 = c_1,3 -c_1,2 +c_2,2 -c_2,3 = 12 S_2,1 = c_2,1 -c_2,2 +c_1,2 -c_1,4 +c_3,4 -c_3,1 = 15 S_2,4 = c_2,4 -c_2,2 +c_1,2 -c_1,4 = 4 S_2,5 = c_2,5 -c_2,2 +c_1,2 -c_1,5 = 1 S_3,2 = c_3,2 -c_3,4 +c_1,4 -c_1,2 = -2 S_3,3 = c_3,3 -c_3,4 +c_1,4 -c_1,2 +c_2,2 -c_2,3 = 4 S_3,5 = c_3,5 -c_3,4 +c_1,4 -c_1,5 = 7

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

Перемещаем по циклу груз величиной в 160 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:

Целевая функция F= 6940

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

Этап 5

Определим значения оценок S_i,j для всех свободных клеток (неоптимальные выделены красным цветом ). Для этого строим цикл для каждой свободной клетки и, перемещаясь по клеткам цикла, складываем тарифы клеток. При этом тарифы в нечетных клетках берутся со знаком "плюс", в четных - со знаком "минус". S_1,1 = c_1,1 -c_1,4 +c_3,4 -c_3,1 = 10 S_1,2 = c_1,2 -c_1,4 +c_3,4 -c_3,2 = 2 S_1,3 = c_1,3 -c_1,4 +c_3,4 -c_3,2 +c_2,2 -c_2,3 = 14 S_2,1 = c_2,1 -c_2,2 +c_3,2 -c_3,1 = 13 S_2,4 = c_2,4 -c_2,2 +c_3,2 -c_3,4 = 2 S_2,5 = c_2,5 -c_2,2 +c_3,2 -c_3,4 +c_1,4 -c_1,5 = -1 S_3,3 = c_3,3 -c_3,2 +c_2,2 -c_2,3 = 6 S_3,5 = c_3,5 -c_3,4 +c_1,4 -c_1,5 = 7

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

Перемещаем по циклу груз величиной в 20 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:

Целевая функция F= 6920

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

Этап 6

Определим значения оценок S_i,j для всех свободных клеток (неоптимальные выделены красным цветом ). Для этого строим цикл для каждой свободной клетки и, перемещаясь по клеткам цикла, складываем тарифы клеток. При этом тарифы в нечетных клетках берутся со знаком "плюс", в четных - со знаком "минус". S_1,1 = c_1,1 -c_1,5 +c_2,5 -c_2,2 +c_3,2 -c_3,1 = 9 S_1,2 = c_1,2 -c_1,5 +c_2,5 -c_2,2 = 1 S_1,3 = c_1,3 -c_1,5 +c_2,5 -c_2,3 = 13 S_2,1 = c_2,1 -c_2,2 +c_3,2 -c_3,1 = 13 S_2,4 = c_2,4 -c_2,5 +c_1,5 -c_1,4 = 3 S_3,3 = c_3,3 -c_3,2 +c_2,2 -c_2,3 = 6 S_3,4 = c_3,4 -c_3,2 +c_2,2 -c_2,5 +c_1,5 -c_1,4 = 1 S_3,5 = c_3,5 -c_3,2 +c_2,2 -c_2,5 = 8

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

Целевая функция F= 6920

2) Метод потенциалов

Примем некоторые обозначения: i - индекс строки j - индекс столбца m - количество поставщиков n - количество потребителей X_i,j - перевозка между поставщиком A_i и потребителем B_j .

Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям. Находим опорный план по правилу северо-западного угла: Введем некоторые обозначения: A_i ^* - излишек нераспределенного груза от поставщика A_i B_j ^* - недостача в поставке груза потребителю B_j

Помещаем в клетку (1,1) меньшее из чисел A₁ ^* =370 и B₁ ^* =300 Так как спрос потребителя B₁ удовлетворен, то столбец 1 в дальнейшем в расчет не принимается Помещаем в клетку (1,2) меньшее из чисел A₁ ^* =70 и B₂ ^* =280 Так как запасы поставщика A₁ исчерпаны, то строка 1 в дальнейшем в расчет не принимается Помещаем в клетку (2,2) меньшее из чисел A₂ ^* =450 и B₂ ^* =210 Так как спрос потребителя B₂ удовлетворен, то столбец 2 в дальнейшем в расчет не принимается Помещаем в клетку (2,3) меньшее из чисел A₂ ^* =240 и B₃ ^* =330 Так как запасы поставщика A₂ исчерпаны, то строка 2 в дальнейшем в расчет не принимается Помещаем в клетку (3,3) меньшее из чисел A₃ ^* =480 и B₃ ^* =90 Так как спрос потребителя B₃ удовлетворен, то столбец 3 в дальнейшем в расчет не принимается Помещаем в клетку (3,4) меньшее из чисел A₃ ^* =390 и B₄ ^* =290 Так как спрос потребителя B₄ удовлетворен, то столбец 4 в дальнейшем в расчет не принимается Помещаем в клетку (3,5) меньшее из чисел A₃ ^* =100 и B₅ ^* =100

Целевая функция F=11320

Решаем задачу методом потенциалов:

Этап 1

Полагая потенциал U₁ =0, определяем остальные потенциалы из соотношения U_i +V_j =C_i,j (i=1..m, j=1..n) , просматривая все занятые клетки. Потенциалы U_i , V_j : U₁ =0 V₁ =C_1,1 -U₁ = 14 V₂ =C_1,2 -U₁ = 8 U₂ =C_2,2 -V₂ = 2 V₃ =C_2,3 -U₂ = 5 U₃ =C_3,3 -V₃ = 3 V₄ =C_3,4 -U₃ = 1 V₅ =C_3,5 -U₃ = 6 Определяем значения оценок S_i,j =C_i,j -(U_i +V_j ) для всех свободных клеток (неоптимальные выделены красным цветом ) S_1,3 = c_1,3 - (u₁ + v₃ ) = 12. S_1,4 = c_1,4 - (u₁ + v₄ ) = 4. S_1,5 = c_1,5 - (u₁ + v₅ ) = -3. S_2,1 = c_2,1 - (u₂ + v₁ ) = 5. S_2,4 = c_2,4 - (u₂ + v₄ ) = 8. S_2,5 = c_2,5 - (u₂ + v₅ ) = -2. S_3,1 = c_3,1 - (u₃ + v₁ ) = -14. S_3,2 = c_3,2 - (u₃ + v₂ ) = -6. Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (3,1) . Для нее оценка равна -14 . Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Перемещаем по циклу груз величиной в 90 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:

Целевая функция F= 10060

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

Этап 2

Полагая потенциал U₁ =0, определяем остальные потенциалы из соотношения U_i +V_j =C_i,j (i=1..m, j=1..n) , просматривая все занятые клетки. Потенциалы U_i , V_j : U₁ =0 V₁ =C_1,1 -U₁ = 14 V₂ =C_1,2 -U₁ = 8 U₃ =C_1,3 -V₁ = -11 U₂ =C_2,2 -V₂ = 2 V₃ =C_2,3 -U₂ = 5 V₄ =C_3,4 -U₃ = 15 V₅ =C_3,5 -U₃ = 20 Определяем значения оценок S_i,j =C_i,j -(U_i +V_j ) для всех свободных клеток (неоптимальные выделены красным цветом ) S_1,3 = c_1,3 - (u₁ + v₃ ) = 12. S_1,4 = c_1,4 - (u₁ + v₄ ) = -10. S_1,5 = c_1,5 - (u₁ + v₅ ) = -17. S_2,1 = c_2,1 - (u₂ + v₁ ) = 5. S_2,4 = c_2,4 - (u₂ + v₄ ) = -6. S_2,5 = c_2,5 - (u₂ + v₅ ) = -16. S_3,2 = c_3,2 - (u₃ + v₂ ) = 8. S_3,3 = c_3,3 - (u₃ + v₃ ) = 14. Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,5) . Для нее оценка равна -17 . Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Перемещаем по циклу груз величиной в 100 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:

Целевая функция F= 8360

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

Этап 3

Полагая потенциал U₁ =0, определяем остальные потенциалы из соотношения U_i +V_j =C_i,j (i=1..m, j=1..n) , просматривая все занятые клетки. Потенциалы U_i , V_j : U₁ =0 V₁ =C_1,1 -U₁ = 14 V₂ =C_1,2 -U₁ = 8 V₅ =C_1,5 -U₁ = 3 U₃ =C_1,3 -V₁ = -11 U₂ =C_2,2 -V₂ = 2 V₃ =C_2,3 -U₂ = 5 V₄ =C_3,4 -U₃ = 15 Определяем значения оценок S_i,j =C_i,j -(U_i +V_j ) для всех свободных клеток (неоптимальные выделены красным цветом ) S_1,3 = c_1,3 - (u₁ + v₃ ) = 12. S_1,4 = c_1,4 - (u₁ + v₄ ) = -10. S_2,1 = c_2,1 - (u₂ + v₁ ) = 5. S_2,4 = c_2,4 - (u₂ + v₄ ) = -6. S_2,5 = c_2,5 - (u₂ + v₅ ) = 1. S_3,2 = c_3,2 - (u₃ + v₂ ) = 8. S_3,3 = c_3,3 - (u₃ + v₃ ) = 14. S_3,5 = c_3,5 - (u₃ + v₅ ) = 17. Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,4) . Для нее оценка равна -10 . Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Перемещаем по циклу груз величиной в 110 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:

Целевая функция F= 7260

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

Этап 4

Полагая потенциал U₁ =0, определяем остальные потенциалы из соотношения U_i +V_j =C_i,j (i=1..m, j=1..n) , просматривая все занятые клетки. Потенциалы U_i , V_j : U₁ =0 V₂ =C_1,2 -U₁ = 8 V₄ =C_1,4 -U₁ = 5 V₅ =C_1,5 -U₁ = 3 U₂ =C_2,2 -V₂ = 2 U₃ =C_4,3 -V₄ = -1 V₃ =C_2,3 -U₂ = 5 V₁ =C_3,1 -U₃ = 4 Определяем значения оценок S_i,j =C_i,j -(U_i +V_j ) для всех свободных клеток (неоптимальные выделены красным цветом ) S_1,1 = c_1,1 - (u₁ + v₁ ) = 10. S_1,3 = c_1,3 - (u₁ + v₃ ) = 12. S_2,1 = c_2,1 - (u₂ + v₁ ) = 15. S_2,4 = c_2,4 - (u₂ + v₄ ) = 4. S_2,5 = c_2,5 - (u₂ + v₅ ) = 1. S_3,2 = c_3,2 - (u₃ + v₂ ) = -2. S_3,3 = c_3,3 - (u₃ + v₃ ) = 4. S_3,5 = c_3,5 - (u₃ + v₅ ) = 7. Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (3,2) . Для нее оценка равна -2 . Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Перемещаем по циклу груз величиной в 160 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:

Целевая функция F= 6940

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

Этап 5

Полагая потенциал U₁ =0, определяем остальные потенциалы из соотношения U_i +V_j =C_i,j (i=1..m, j=1..n) , просматривая все занятые клетки. Потенциалы U_i , V_j : U₁ =0 V₄ =C_1,4 -U₁ = 5 V₅ =C_1,5 -U₁ = 3 U₃ =C_4,3 -V₄ = -1 V₁ =C_3,1 -U₃ = 4 V₂ =C_3,2 -U₃ = 6 U₂ =C_2,2 -V₂ = 4 V₃ =C_2,3 -U₂ = 3 Определяем значения оценок S_i,j =C_i,j -(U_i +V_j ) для всех свободных клеток (неоптимальные выделены красным цветом ) S_1,1 = c_1,1 - (u₁ + v₁ ) = 10. S_1,2 = c_1,2 - (u₁ + v₂ ) = 2. S_1,3 = c_1,3 - (u₁ + v₃ ) = 14. S_2,1 = c_2,1 - (u₂ + v₁ ) = 13. S_2,4 = c_2,4 - (u₂ + v₄ ) = 2. S_2,5 = c_2,5 - (u₂ + v₅ ) = -1. S_3,3 = c_3,3 - (u₃ + v₃ ) = 6. S_3,5 = c_3,5 - (u₃ + v₅ ) = 7. Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (2,5) . Для нее оценка равна -1 . Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Перемещаем по циклу груз величиной в 20 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:

Целевая функция F= 6920

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

Этап 6

Полагая потенциал U₁ =0, определяем остальные потенциалы из соотношения U_i +V_j =C_i,j (i=1..m, j=1..n) , просматривая все занятые клетки.

Потенциалы U_i , V_j : U₁ =0 V₄ =C_1,4 -U₁ = 5 V₅ =C_1,5 -U₁ = 3 U₂ =C_5,2 -V₅ = 3 V₂ =C_2,2 -U₂ = 7 V₃ =C_2,3 -U₂ = 4 U₃ =C_2,3 -V₂ = -2 V₁ =C_3,1 -U₃ = 5 Определяем значения оценок S_i,j =C_i,j -(U_i +V_j ) для всех свободных клеток (неоптимальные выделены красным цветом ) S_1,1 = c_1,1 - (u₁ + v₁ ) = 9. S_1,2 = c_1,2 - (u₁ + v₂ ) = 1. S_1,3 = c_1,3 - (u₁ + v₃ ) = 13. S_2,1 = c_2,1 - (u₂ + v₁ ) = 13. S_2,4 = c_2,4 - (u₂ + v₄ ) = 3. S_3,3 = c_3,3 - (u₃ + v₃ ) = 6. S_3,4 = c_3,4 - (u₃ + v₄ ) = 1. S_3,5 = c_3,5 - (u₃ + v₅ ) = 8. Так как все оценки S_i,j >=0, то полученный план является оптимальным. Транспортная задача решена.

Целевая функция F= 6920