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

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

Метод потенциалов




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

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

Для удобства первые m уравнений исходной задачи умножим на –1; неизвестные двойственной задачи, соответствующие первым m уравнениям исходной задачи, обозначены через u1, u2, ..., um, а неизвестные, соответствующие последним n уравнениям – через v1, v2, ..., vn. Систему неравенств двойственной задачи кратко можно записать в виде

(i= ; j= ).

Неизвестные u1, u2 ,..., um будем рассматривать как оценки единицы груза, находящегося в распоряжении соответствующего поставщика, или потенциалы поставщиков, а неизвестные v1 ,v2,..., vm – как оценки единицы груза, доставленного соответствующему потребителю, или потенциалы потребителей. Потенциалы можно интерпретировать соответственно как цены в пункте поставщика или в пункте потребителя.

Применяя теорему 2.8 о дополняющей нежесткости, приходим к следующему критерию оптимальности.

Таблица 2.9

 

Задача 1 Задача 2
Минимизировать где Максимизировать где
при условиях . . . . . . . . . . . . при условиях . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 


Окончание таблицы 2.9

 

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . , . . .     любого знака    

 

Теорема 2.11.(критерий оптимальности плана транспортной задачи). Для того чтобы план перевозок Х* = ( ) был оптимальным, необходимо и достаточно, чтобы существовали числа ( ) и ( ), удовлетворяющие следующим условиям:

а) для всех базисных клеток плана ( >0) ;

б) для всех свободных клеток ( =0) .

Замечание. В оба условия критерия потенциалы ui и vj входят только в виде разностей vj – ui , и поэтому потенциалы определяются с точностью до постоянного слагаемого, т. е. если числа и удовлетворяют условиям критерия, то им будут удовлетворять и числа и , где с – произвольное число.

Проверим исходное опорное решение Х0, полученное ранее, на оптимальность. С этой целью составим систему уравнений, соответствующих положительным перевозкам (занятым клеткам) плана Х0, т. е.

v1 u1=2, v2 – u2=3, v3 – u3=4,

v2 – u1=4, v3 – u2=6, v4u3=5,

где u1, u2, u3 потенциалы поставщиков, а v1, v2, v3, v4 потенциалы потребителей (для удобства эти потенциалы записаны справа и снизу от плана Х0). Решим данную систему, положив, например, u1 = 0. Получим следующие значения:

v1 = 2, v2 = 4, u2 = 1, v3 = 7, u3 = 3, v4 = 8.

Для свободных клеток плана Х0 составим систему неравенств:

Подставляя полученные значения потенциалов в данную систему неравенств, имеем:

Неравенства не выполняются для двух перевозок x13 = 0 и x14 = 0 плана Х0 (для двух свободных клеток). Значит план Х0 не оптимален и требуется построить новый (улучшенный) план перевозок, для которого транспортные затраты меньше или, по крайней мере, равны затратам для предыдущего плана.

Обозначим разность (vj – ui) cij= . Эта величина называется оценкой свободной клетки. Для двух клеток (1,3) и (1,4) эти оценки положительны. Выбираем максимальную из них .

В новом, улучшенном, плане клетка (1,4) (соответствующая максимуму ) должна быть занятой. Введем в план перевозку x14 = e (значение e будет определено ниже). Для того чтобы новый план удовлетворял условиям (2.10)–(2.11), внесем в план Х0 следующие поправки. Перевозку х12 = 50, стоящую в той же строке матрицы Х0, что и х14 = e, уменьшим на e; перевозку х22 = 250, стоящую в том же столбце, что и х12, увеличим на e; аналогично х23 = 100 уменьшим на e, х33 = 250 увеличим на e и, наконец, х34 = 200 уменьшим на e.
В результате новый план перевозок Х1e будет иметь вид, представленный на рис. 2.12.

 

                 
      50-e           e   u1
                       
                 
        250+e     100-e       u2
                         
               
              250+e   200-e   u3
                         
  v1     v2     v3     v4    

 

Рис. 2.12

 

Здесь e должно удовлетворять неравенствам , т. е. (чтобы все значения 50 – e, 100 – e, 200 – e были неотрицательными). Для плана Х1e стоимость перевозок составит

Выбрав наибольшее возможное значение e, т. е. e = 50, получим новый план Х1, представленный на рис. 2.13. Перераспределение перевозок при переходе от плана Х0 к плану Х1 было произведено по замкнутой ломаной линии, называемой обычно циклом (этот цикл отмечен пунктиром на рис. 2.12). Вычислим транспортные затраты для плана Х1

 

.

 

Они оказались меньше транспортных затрат для плана Х0. Следовательно, план Х1 лучше плана Х0. Таким образом, включение в план Х1 перевозки x14 = 50, оказалось оправданным и транспортные затраты уменьшились на величину .

 

                 
                    u1
                         
                 
                    u2
                         
                 
                    u3
                         
  v1     v2     v3     v4    

 

Рис. 2.13

 

Далее найдем новые значения потенциалов поставщиков и потребителей из уравнений

v1 u1 = 2, v2 – u2 = 3 v3 – u3 = 4,

v4 – u1 = 3, v3 – u2 = 6, v4 – u3 = 5,

соответствующих занятым клеткам плана Х1.

При u1 = 0 получим v1 = 2, v4 = 3, u3 = –2, v3 = 2, u2 = –4, v2 = –1.

Подставив найденные значения потенциалов в неравенства

соответствующие свободным клеткам плана Х1, получим

v2 u1 = –1 < 4, v1 – u2 = 6 > 4, v1 u3 = 4 < 6,

v3 u1= 2 < 5, v4 u2 = 7 = 7, v2 u3 = 1 < 5.

Не выполняется только третье неравенство, соответствующее перевозке х21 = 0. В плане Х1 только одна положительная оценка . Включая в план Х1 перевозку , и, перераспределяя другие перевозки по циклу , получим новый план Х2 (см. рис. 2.14)

 

                 
                    u1
                       
               
                    u2
                       
               
                    u3
                         
v1 v2 v3 v4

 

Рис. 2.14

 

План Х2 лучше плана Х1, т. к. для него стоимость транспортных затрат оказалась меньше, чем для плана Х1. Применительно к плану Х2 вновь составим систему уравнений

v1u1 = 2, v1 u2 = 4, v3u3 = 4,

v4 u1 = 3, v2 u2 = 3, v4 u3 = 5

и неравенств

Положив u1 = 0, из последней системы уравнений получим v1 = 2, v4 = 3, u3 = –2, v3 = 2, u2 = –2, v2 = 1. Найденные значения потенциалов удовлетворяют последней системе неравенств. Действительно,

Так как потенциалы u1 = 0, v4 = 3, u3 = –2, v1 = 2, v3 = 2, u2 = –2, v2 = 1 удовлетворяют обоим условиям критерия оптимальности, то план Х2 будет оптимальным, а стоимость перевозок f2) = 3600 является минимальной.

Оптимальное решение формулируется следующим образом. Первый поставщик должен доставить 150 ед. груза первому потребителю и 100 ед. четвертому, второй поставщик доставит 50 ед. груза первому потребителю и 300 ед. второму и третий поставщик – 350 ед. третьему потребителю и 100 ед. – четвертому. Суммарные транспортные расходы составляют 3600 (денежных единиц). Оптимальный план Х2 выпишем в виде матрицы

 

.

 

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

Шаг 1. Проверить, является ли данная транспортная задача закрытой. Если да, то перейти ко второму шагу. Если нет, то свести ее к закрытой задаче путем введения либо фиктивного поставщика, либо фиктивного потребителя.

Шаг 2.Найти исходное опорное решение (исходный опорный план) закрытой транспортной задачи.

Шаг 3. Проверить полученное опорное решение на оптимальность:

а) вычислить для него потенциалы поставщиков ui и потребителей vj ;

б) для всех свободных клеток (i,j) вычислить оценки ;

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

Шаг 4. Выбрать клетку (i*,j*) с наибольшей положительной оценкой и для нее построить замкнутый цикл перераспределения груза. Цикл начинается и заканчивается в выбранной клетке. Получим новое опорное решение, в котором клетка (i*, j*) окажется занятой. Возвращаемся к третьему шагу.

Через конечное число шагов будет получено оптимальное решение, т. е. оптимальный план перевозок продукции от поставщиков к потребителям.

 







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

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








Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7