Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Лабораторная работа 13. Решение транспортной задачи в матричной постановке




Рассмотрим пример, в котором требуется решить транспортную задачу методом потенциалов , что значения a[i], b[j],c[i,j] (iÎ[1..4], jÎ[1..3]), заданы в таблице 1.

 

Таблица 1.

  j
I Bj Ai
1  
3  
4  

 

Решение.

Транспортная задача имеет решение тогда и только тогда, когда выполняется соотношение :

 

В данном случае, , поэтому необходимо ввести в рассмотрение фиктивного (внешнего) потребителя (№4) :

b[4]= =12-11=1

Положим для всех iÎ[1..4] с[i,4]=100

Определим исходное базисное решение методом северо-западного угла.

 

Таблица 2.

j 1 2 3 4
i Bj Ai 1 7 3 1 Ui
1 1 1 2 1 2 100 0
0 - 0 + -4 -3
2 2 3 4 1 100 -1
0 0 -2 -2
3 1 4 1 3 100 -2
2 + 0 - -3 -1
4 3 5 1 1 3 100 1 -3
1 0 0 0
Vj 1 2 -2 97 Ui Vj

 

Стоимость перевозок составит: L(x)= 127

 

По критерию оптимальности определим, является ли найденное решение наилучшим. d[3,1] =max{ d[i,j]| iÎ[1..4], jÎ[1..4] }=2 ³ 0, значит полученное базисное решение не является оптимальным и необходимо перейти к новому базису.

 

Строим цикл П, который будет состоять из клеток x[3,1], x[1,1], x[1,2], x[3,2], в позициях q которых записываются соответственно ‘+’, ‘-’, ‘+’ ,‘-’. Среди значений x[i,j], в клетках которых записаны ,‘-’ находим минимальное Q=min x[i,j]. Оно равно 1, и достигается на клетке [1,1]. Т.о. клетку [3,1] вводим в базис, а клетку [1,1] выводим из базиса.

 

Пересчитаем значения x[i,j] для нового базиса.

 

Таблица 3.

j 1 2 3 4
I Bj Ai 1 7 3 1 Ui
1 2 1 2 1 2 100 0
-2 0 -4 -3
2 4 2 3 4 1 100 -1
-2 0 -2 -2
3 1 1 1 4 0 3 100 -2
0 0 -3 -1
4 5 3 5 1 1 3 100 1 -3
-1 0 0 0
Vj -1 2 -2 97 Ui Vj

Стоимость перевозок составит: L(x)=125. По критерию оптимальности определим, является ли найденное решение наилучшим. max{ d[i,j]| iÎ[1..4], jÎ[1..4] }£ 0, значит полученное базисное решение является оптимальным Стоимость перевозок без учета фиктивного потребителя составит L(x)=25

Задание. Решить транспортную задачу методом потенциалов, значения a[i] (iÎ[1..4]) и b[j] (jÎ[1..3]) заданы в таблице 4, значения c[i,j] задать произвольным образом.

Таблица 4


Поможем в написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой





Дата добавления: 2014-12-06; просмотров: 680. Нарушение авторских прав; Мы поможем в написании вашей работы!

Studopedia.info - Студопедия - 2014-2022 год . (0.026 сек.) русская версия | украинская версия
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7