Математика \ Математика

Транспортная задача. Матричные игры: Методические указания к практическим занятиям, страница 8

а)       

                 

 

 

Новая текущая таблица, полученная перестройкой по циклу , представлена на рис.6а). Слева от строк и над столбцами уже записаны потенциалы этой таблицы – они находятся так же, как в примере 3. Вычисляя псевдостоимости по формуле (10), находим, что (1, 4) – единственная   клетка   c   отрица-

     

ельной    псевдостоимостью   

б)  

     

 

 

  

      Рис. 6

 Цикл  текущей таблицы (см. шаг 2б) в алгоритме метода потенциалов) содержит незанятую клетку (1, 4) и занятые клетки (1, 2), (2, 2), (2, 4); в этом цикле

и Результатом перестройки таблицы а)  на рис.6 по циклу    будет таблица б) на рис.6,  которая  удовлетворяет признаку оптимальности

(проверьте!) и, следовательно, представляет оптимальный план         для всех  остальных  клеток. В данной ТЗ  оптимальный план – единственный, так как в  заключительной опорной таблице    для всех незанятых клеток.

Текущие значения целевой функции проще вычислять по формуле (11),         

 в заключительной таблице целесообразно проверить значение непосредственным вычислением, в нашем примере  

Пример 5. Найти все оптимальные планы ТЗ, в которой      

Решение: Начальная опорная таблица данной ТЗ, построенная методом МС, представлена на рис. 7а). Вычисляя потенциалы и псевдостоимости, находим  начальная таблица удовлетворяет признаку оптимальности и    По формуле (9) 

а)

б)

 

Рис. 7

 для любого допустимого плана  в оптимальных планах   (почему?). Используя ограничения (3), последовательно находим

              Условие (4) неотрицательности всех   выполнено, очевидно, при   Множество оптимальных планов  рассматриваемой ТЗ  бесконечно, каждому     из     соответствует оптимальный план задачи, представленный таблицей ТЗ на рис. 7б) (при каких   этот план  будет опорным?)

Замечание 1. В примере 5 преобразование таблицы 7а) в таблицу 7б) отличается от перестройки по циклу    только тем, что при вычислении новых значений    в клетках цикла число  заменяется  на  число    из промежутка   В общем случае  такое преобразование опорной  таблицы можно выполнить, принимая за  «начальную» в цикле перестройки любую незанятую клетку  результатом преобразования всегда будет таблица ТЗ. Если исходная таблица удовлетворяет признаку оптимальности и, кроме того,   различным    из    будут соответствовать таблицы ТЗ, представляющие  бесконечное множество оптимальных планов.

Скачать файл