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

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

Лабораторная работа 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

№ варианта А[I] В[j]
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               






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




Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...


Картограммы и картодиаграммы Картограммы и картодиаграммы применяются для изображения географической характеристики изучаемых явлений...


Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...


Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Примеры задач для самостоятельного решения. 1.Спрос и предложение на обеды в студенческой столовой описываются уравнениями: QD = 2400 – 100P; QS = 1000 + 250P   1.Спрос и предложение на обеды в студенческой столовой описываются уравнениями: QD = 2400 – 100P; QS = 1000 + 250P...

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

Педагогическая структура процесса социализации Характеризуя социализацию как педагогический процессе, следует рассмотреть ее основные компоненты: цель, содержание, средства, функции субъекта и объекта...

Задержки и неисправности пистолета Макарова 1.Что может произойти при стрельбе из пистолета, если загрязнятся пазы на рамке...

Вопрос. Отличие деятельности человека от поведения животных главные отличия деятельности человека от активности животных сводятся к следующему: 1...

Расчет концентрации титрованных растворов с помощью поправочного коэффициента При выполнении серийных анализов ГОСТ или ведомственная инструкция обычно предусматривают применение раствора заданной концентрации или заданного титра...

Studopedia.info - Студопедия - 2014-2025 год . (0.01 сек.) русская версия | украинская версия