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

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

Метод декомпозиции транспортных задач





Применим метод декомпозиции к Т-задаче:

(1) (2) "Хij³0.(3)

Использование этого метода целесообразно, если m << n или m>>n. Решаются идентично. Отличаются распределением условий между основной и вспомогательной задачами. Рассмотрим случай, когда m << n. Тогда основная задача формируется по условиям ПО. Множество D 0 описывается ограничениями (1), а D1 – условиями (2) и (3). Множество D1 представляет собой выпуклый многогранник (ограниченность вытекает из условий). Поэтому, любую точку в D1 можно представить в виде линейной комбинации его вершин:

S Zv =1; " Zv ³ 0, где Xvij – координаты v -ой вершины. Введем обозначения: (6) (7)Тогда основная задача запишется в виде (4) " Zv ³ 0. Для сбалансированной задачи условие (4) выполняется автоматически. откуда для сбалансированной задачи следует При решении основной задачи условие (4) из модели исключается. Для определения статуса текущего базисного решения основной задачи необходимы относительные оценки. Нахождение оценок связано с решением вспомогательной задачи. Для построения вспомогательной задачи сделаем ряд преобразований: D v = pTP v - sv= = Так как основная задача решается на минимум, то оптимальному статусу соответствуют неположительные оценки. Поэтому нужно искать максимальную оценку. Если она окажется не > 0, то все оценки неположительны и признак оптимальности выполнился. В противном случае необходимо продолжить решение основной задачи. Задача: Вместо поиска максимума на дискретном множестве вершин перейдем к эквивалентной задаче поиска на всем непрерывном множестве D1: (5) " X ij ³ 0. – вспомогат. задача. В оптимальном решении этой задачи Вспомогательная задача включает группу условий (5). Равенства (5) - независимые и вспомогательная задача распадается на n простейших независимых задач, каждая из которых имеет всего одно условие: " X ij ³ 0. Критерий вспомогательной задачи равен сумме критериев этих задач: Оптимальное решение задачи, как линейной, находится на границе. При этом только одна переменная не равна нулю (базис имеет размерность 1). Поэтому ее решение состоит в определении максимального коэффициета в критерии. Пусть максимум достигается на индексе i*, то есть Тогда имеем: Xvi*j = bj, Xvij =0, " i, i ¹ i*, и максимальная оценка определится как . Если L * всп £ 0, то полож. оценок нет, тек решение основной задачи будет оптимальным.

При L*всп > 0 начинается новая итерация:

1. пo (6) и (7) находим Р v и sv;

2. вычисляем эл-ты напр. столбца как коэффициенты разложения вектора Р v по текущему базису: a v = P -1B P v;

3. проводим симплекс-преобразование основной задачи, в результате которого получаем новое решение и новую обратную матрицу; 4. вычисляем p T= s TB P -1B;

5. решаем вспомогательную задачу: вычисляем разности , находим оптимальные решения n задач и максимальную оценку основной задачи.

Из рассмотренной вычислительной схемы следует, что эффективность метода тем выше, чем сильнее неравенство m << n или m>>n.

bi ai        
         
         

Пример. Решим транспортную задачу с двумя ПО и четырьмя ПН: Числа в ячейках таблицы - затраты на перевозки Cij. Исходная модель задачи: L = SS CijXij àmin

Координирующая задача формируется по условиям:

" Zv ³0

sv Баз. . P 0 P n +1 P n +2
M Zn+ 1      
M Zn+ 2      
pТ M M

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

bj        
p 1 -C 1 j M -2 M -5 M -1 M -4
p 2 -C 2 j M -1 M -3 M -4 M -2
v =1 X 121=8 X 122=4 X 113=10 X 124=8

и модифицируем критерий Составим нач. таблицу координирующей задачи:

В последней строке значения pi получены умножением первого столбца на столбцы P n+i. Решение вспомогательной задачи представляем в таблице:

sv Баз   P0 P n +1 P n +2 P1 q
M Zn+ 1          
M Zn+ 2          
pТ M M  

при j =1 максимальная разность равна M -1, поэтому X121 = b1 =8. Клетки с максимальными разностями выделены цветом фона. Критерий: [(M -1)*8 + (M -3)*4 + (M -1)*10 + (M -2)*8] > 0.

sv Баз. P0 P n +1 P n +2
  Z 1   0,1  
M Zn+ 2   -2  
pТ -2 M +4,6 M

Так как признак оптимальности не выполняется, переходим к итерациям. Находим s1: s 1=1*8 + 3*4 + 1*10 + 2*8 = 46. Вычисляем компоненты вектора Р 1:

Р 11= X1 13=10; P 21= X1 21+ X1 2 2 + X1 24= 8+4+8 = 20.

bj        
p 1 - C1j 2,6-2 M -0,4-2 M 3,6-2 M 0,6-2 M
p 2 -C 2 j M -1 M -3 M -4 M -2
v =2 X 221=8 X 222=4 X 223=10 X 224=8

. Его разложение по нач. базису: .

Добавляем столбец P 1с элементами a 1 в начальную таблицу в качестве напр.столбца: Взяв 1-ю строку за направляющую и выполнив симплекс-преобразование, получаем новое решение основной задачи:

Для выяснения статуса этого решения снова находим максимальную оценку основной задачи, решая вспомогательную задачу: L2всп>0, то есть решение основной задачи не является оптимальным. Вычисляем

sv Баз P0 Pn+1 Pn+2
  Z 1   0,1  
  Z 2   -1/15 1/30
pТ -7/15 38/15

коэффициент критерия при Z 2: s 2=1*8 + 3*4 + 4*10 + 2*8 = 8+12+40+16 = 76. Определяем компоненты вектора Р 2: Р 12=0, P22 = 8+4+10+8 = 30

, и добавляем его к последней

sv Баз. P0 P n +1 P n +2 P2 q
  Z 1   0,1     -
M Zn+2   -2      
pТ -2 M +4,6 M    

таблице основной задачи: В результате симплекс-преобразования получаем: Соотв. вспомогательная задача:

bj        
p 1 -C 1 j -37/15 -82/15 -22/15 -67/15
p 2 -C 2 j 23/15 -7/15 -22/15 8/15
v =3 X 321=8 X 322=4 X 313=10 X 324=8

Критерий L 3 всп =(23/15)*8–(7/15)*4–(22/15)*10+(8/15)*8=0. Оптимальное решение осн. задачи: Z* 1=1, Z* 2=0, L* = 46*1 + 76*0 = 46.

X* 21 = 8, X* 22 = 4, X* 13 = 10, X* 24 = 8.

 








Дата добавления: 2015-04-19; просмотров: 440. Нарушение авторских прав; Мы поможем в написании вашей работы!




Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...


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


Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...


Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Почему важны муниципальные выборы? Туристическая фирма оставляет за собой право, в случае причин непреодолимого характера, вносить некоторые изменения в программу тура без уменьшения общего объема и качества услуг, в том числе предоставлять замену отеля на равнозначный...

Тема 2: Анатомо-топографическое строение полостей зубов верхней и нижней челюстей. Полость зуба — это сложная система разветвлений, имеющая разнообразную конфигурацию...

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

Этапы трансляции и их характеристика Трансляция (от лат. translatio — перевод) — процесс синтеза белка из аминокислот на матрице информационной (матричной) РНК (иРНК...

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

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

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