Студопедия

КАТЕГОРИИ:

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



Построение системы потенциалов




Читайте также:
  1. C2 Покажите на трех примерах наличие многопартийной политической системы в современной России.
  2. II. Построение карты гидроизогипс
  3. II. Построение карты гидроизогипс
  4. II. Построение продольного профиля по оси трассы
  5. II. Системы, развитие которых можно представить с помощью Универсальной Схемы Эволюции
  6. III. Когда выгодно рассматривать движение из движущейся системы отсчета (решения двух задач учителем)?
  7. III. Требования к организации системы обращения с медицинскими отходами
  8. MES-системы (Manufacturing Execution System) - системы управления производством (у нас больше известные как АСУТП)
  9. Ordm;. Понятие полярной системы координат.
  10. Oсoбеннoсти и прoблемы функциoнирoвaния вaлютнoй системы Республики Белaрусь

Рассмотрим алгоритм метода потенциалов и одновременно проиллюстрируем его применение на опорном плане, полученном в
табл. 8.5. Для этого к таблице добавим строку и столбец, в которых записывают значения потенциалов (в результате получим макет табл. 8.6).

 

 

Таблица 8.6

Поставщики U Потребители Запасы
B1 B2 B3 B4 B5  
А1 -12 10 7 4 1 4 a2
U1 - - - 100 -
А2 -1 2 - 7 10 + 6 11 a2
U2 200 50 (1) (6) (1)
А3 -11 8 5 3 - 2 + 2 a1
U3 - - - 200
А4 11 + 8 12 16 - 13 a2
U4 - 150 100 - 50
спрос          
V V1= V2= V3= V4= V5=

 

Систему потенциалов можно построить только для невырожденного опорного плана. Такой план содержит m+n-1 занятых клеток, поэтому для него можно составить систему из m+n-1 линейно независимых уравнений вида (8.28) с m+n неизвестными. Уравнений на одно меньше, чем неизвестных, поэтому система является неопределенной и одному неизвестному придают нулевое значение. После этого остальные потенциалы определяются однозначно. В случае вырожденности опорного плана его дополняют до невырожденного фиктивно нулевыми элементами.

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

Рассмотрим пример, представленный табл. 8.6. С целью наиболее эффективного использования произвольно заданного нулевого потенциала выбирается строка, которая содержит наибольшее количество занятых клеток (строка А4). Полагаем U4= 0. В строке А4 три занятых клетки (А4В2, А4В3 и А4В5), которые связывают соответственно потенциал U4 с потенциалами V2, V3, V5. Определим эти потенциалы: V2= С42U4 = 8- 0 = 8; V3= С43V4 = 12- 0=12; V5= С45U4 = 13- 0=13.



С помощью потенциала U4 определить еще какой-нибудь неизвестный потенциал невозможно, поэтому как либо помечаем его, например, символом *. Теперь поочередно просматриваем столбцы В2, B3 и B5, для которых потенциалы уже определены. В столбце В2 имеется две занятые клетки (А2В2 и А4В2), которые связывают потенциал V2 с потенциалами U2 и U4, потенциал U4 уже определен. Переходим к клетке А2В2 и с помощью С22 определим неизвестный потенциал: U2 = C22 — V2 =7-8 = -1. Помечаем потенциал V2, знаком * и переходим к столбцу B3. В этом столбце нет занятых клеток, которые бы связывали V3 с неизвестными потенциалами строк.

Данный процесс продолжается для остальных строк и столбцов. Однако после его прерывания (невозможно определить еще какие-либо неизвестные потенциалы) остались неопределенными потенциалы U1 и V4. Это произошло потому, что опорный план является вырожденным. Для устранения вырожденности количество занятых клеток дополняется до m+n-1, путем введения нулевых перевозок. Клетки, в которые введены нулевые перевозки, называются фиктивно занятыми.



Чтобы определить потенциалы U1 и V4, необходимо сделать фиктивно занятой одну из незанятых клеток либо строки A1, либо столбца В4, для которых один из потенциалов определен. Задача заключается в минимизации линейной целевой функции, поэтому целесообразно фиктивно занятой сделать клетку, в которой стоит наименьшая стоимость.

Просматривая стоимости, стоящие в незанятых клетках строки A1 и столбца В4, выбираем наименьшую (min(Cij)= 2), которая соответствует клетке А3В4, в нее записываем нуль и считаем занятой. Теперь клетка А3В4 связывает потенциал с потенциалом U3, V4= 2 - (-11) =13. Затем находим U1 = С14 — V4 = 1-13 =- 12.

Система потенциалов построена. Проверяем правильность построения системы. Для этого просматриваем занятые клетки строк и для каждой из них определяем сумму потенциалов. Если для всех занятых клеток выполняется равенство (8.28), то система построена правильно, в противном случае ее надо построить заново или изменить так, чтобы условие (8.28) выполнялось.

Проверка выполнения условия оптимальности для незанятых клеток

Для каждой незанятой клетки проверяется условие (8.29), т. е. сравнивается сумма соответствующих клетке потенциалов со стоимостью. Если для всех незанятых клеток неравенства выполняются, то план является оптимальным. Если нет, то план является неоптимальным. Для каждой клетки, в которой не выполняется условие оптимальности, определяется разность (Ui + Vj) - Cij > 0, которая записывается в левый нижний угол этой же клетки. В рассматриваемом примере (табл. 8.6) имеются три клетки, в которых нарушено условие оптимальности; разности соответственно равны 1, 6 и 1.




Дата добавления: 2015-04-16; просмотров: 19; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.013 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты