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

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

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






Каждому поставщику (ограничению по запасам) поставим в соответствие потенциал ui (i = ), а каждому потребителю (ограничению по спросу) — потенциал vj (j = ).

Согласно теореме о потенциалах, каждой занятой клетке будет соответствовать уравнение ui + vj = cij. Так как всех занятых клеток должно быть т+п– 1, т. е. на единицу меньше числа потенциалов, то для определения чисел ui, vj необходимо решить систему из т+п– 1 уравнений с т+п неизвестными: ui+ vj = cij. Одному из потенциалов задают обычно значение, равное нулю.

Для исследования плана на оптимальность по каждой свободной клетке проверяется условие ui+ vj ≤ cij. Если хотя бы одна свободная клетка не удовлетворяет данному условию, то опорный план не является оптимальным, его можно улучшить за счет загрузки этой клетки. Если таких клеток несколько, то наиболее перспективной для загрузки является клетка, для которой разность (оценка) между тарифом клетки и суммой потенциалов наименьшая, т. е. Sij = сij – (ui + vj) < 0.

Например, для клеток (i;k) и (i;t) имеем оценки: Sik= -5, Sit= -10. Здесь наиболее потенциальной является клетка (i;t). Экономически оценка показывает, на сколько денежных единиц уменьшатся транспортные издержки от загрузки данной клетки единицей груза. Эффективность плана от загрузки потенциальной клетки грузом в λ единиц составит ΔF = Sij · λ ден.ед. Если для всех свободных клеток оценки Sij≥ 0, то опорный план перевозок является оптимальным.

Итак, если для опорного плана перевозок указанное условие оптимальности не выполняется, то за счет загрузки свободной клетки с отрицательной оценкой план перевозок улучшается. Для наиболее перспективной свободной клетки строится замкнутый цикл с вершинами в загруженных клетках. Вершинам этого цикла условно приписываются знаки: свободной клетке – плюс, следующей по часовой или против часовой стрелки занятой клетке – минус, следующей – снова плюс и т. д. Из поставок в клетках цикла с «отрицательными» вершинами выбирается наименьшее количество λ груза, которое и перемещается по клеткам этого цикла: прибавляется к поставкам в положительных вершинах и вычитается из поставок в отрицательных вершинах, в результате чего баланс цикла не нарушится.

Сформулируем алгоритм решения ТЗ методом потенциалов:

1) построить опорный план по одному из правил;

2) вычислить потенциалы поставщиков и потребителей ui и vj (i = ),; (j = ), решив систему уравнений вида ui+ vj = cij;

3) вычислить оценки Sij для всех свободных клеток по
формуле Sij = сij – (ui + vj). Если все Sij≥ 0, то полученный план является оптимальным. При этом если все Sij≥ 0, то полученный оптимальный план единственный. В случае, если хотя бы одна оценка Sij= 0, имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции.

ПРИМЕР 2.1: В трех хранилищах А1, А2, А3 имеется соответственно 70, 90 и 50 т топлива. Требуется спланировать перевозку топлива четырем потребителям В1, В2, В3, В4, спрос которых равен соответственно 50, 70, 40 и 40 т, так, чтобы затраты на транспортировку были минимальны. Стоимость перевозки 1 т указана в табл. 2.1.

Таблица 2.1.

Хранилища Потребители Запас топлива, т
B1 В2 В3 B4
Стоимость перевозки 1 т топлива, ден.ед.
A1          
А2          
А3          
Потребность в топливе, т         210 > 200

РЕШЕНИЕ: Поскольку запасы топлива в хранилищах превышают спрос потребителей, задача является открытой, вводится фиктивный потребитель, спрос которого b5 = 210 – 200 = 10 т. Все затраты для фиктивного потребителя сi5 = 0 (i = ). После введения фиктивного потребителя открытая модель задачи преобразовалась в закрытую, а распределительная таблица принимает вид таблицы 2.2.

Таблица 2.2.

Хранилища Потребители Запас топлива, т
B1 В2 В3 В4 В5
Стоимость перевозки 1 т топлива, ден. ед.
А1            
А2            
А3            
Потребность в топливе, т            

Исходный опорный план получим, например, по правилу «минимального элемента». Так как наименьшими являются нулевые тарифы для клеток (1; 5), (2; 5), (3; 5), то загрузим первой, например, клетку (1; 5), х15= 10 т. Второй загружаем клетку (3; 3), хзз = 40 т. Далее загружаем клетки (1; 2), (3; 1), (2; 2), (2; 4), полагая х12 = 60 т, х31 = 10 т, х22 = 10 т, х21 = 40 т, х24= 10 т (таблица 2.3).

Таблица 2.3.

В А B1 В2 В3 В4 В5 За-пас  
А1     + 2         – 0   u1=0
                   
А2                 + 0   u2=1
                 
А3                       u3=-1
                   
Спрос              
  v1=3 v2=2 v3=2 v4=6 v5=0    

В результате распределения топлива по потребителям получили невырожденный план: условие для занятых клеток m+n–1=3+5–1=7 выполняется.

Для определения потенциалов составляем уравнения для занятых клеток: u1 + v2 = 2, u1 + v5 = 0, u2 + v1 = 4, u2 + v2 =3, и2 + v4 =7, u3 + v1 = 2, u3 + v3 =1. Положим, например, u1 = 0, тогда и2 = 1, u3 = –1, v1 =3, v2 = 2, v3 = 2, v4 = 6, v 5 = 0.

Определим оценки свободных клеток:

S11 = 5 − (0 + 3) = 2 > 0, S23 = 5 − (1 + 2) = 2 > 0, S34 = 5 − (-1 + 6) = 0, S13 = 3 − (0 + 2) = 3 > 0, S25 = 0 − (0 + 2) = -2 < 0, S35 = 0 − (-1 -0) = 2 > 0, S14 = 6 − (0 + 6) = 0, S32 = 4 − (-1 + 2) = 3 > 0,

Определив потенциалы, устанавливаем, что среди оценок свободных клеток одна отрицательная: S25 = –1, следовательно, план перевозок можно улучшить за счет загрузки клетки (2;5). Цикл для нее выделен линией в таблице 2.3.

Наименьшее количество топлива в отрицательных вершинах цикла равно 10 т. После смещения по циклу 10 т получаем новый план перевозок (таблица 2.4). Полученный план является вырожденным. Поставим число 0, например, в клетку (2; 2).

Таблица 2.4.

В А B1 В2 В3 В4 В5 За-пас  
А1                       u1=-1
                   
А2                       u2=0
                   
А3                       u3=-2
                   
Спрос              
  v1=4 v2=3 v3=3 v4=7 v5=0    

Для нового плана определяем новые потенциалы и находим оценки свободных клеток: S11 = 2 >0, S13 = l >0, S14 = 0, S15 = 1 > 0, S23 = 2 > 0, S32 = 3 > 0, S34=0, S35 = 2 >0.

Оценки всех свободных клеток Sij > 0, следовательно, получен оптимальный план. Поскольку среди оценок имеются равные нулю, то за счет загрузки клеток (1; 4), (3; 4) можно получить новые планы, но значение целевой функции не изменится. Это случай бесчисленного множества оптимальных планов.

Итак, в таблице 2.4 получили оптимальный план

Х* = , для которого значение целевой функции равно

F(X*) = 2 · 70 + 4 · 40 + 7 · 40 + 2 · 10 + 1 · 40 = 640.

Десять тонн топлива, находящегося в хранилище А2, осталось нераспределенным.







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



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

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

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

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

Условия приобретения статуса индивидуального предпринимателя. В соответствии с п. 1 ст. 23 ГК РФ гражданин вправе заниматься предпринимательской деятельностью без образования юридического лица с момента государственной регистрации в качестве индивидуального предпринимателя. Каковы же условия такой регистрации и...

Седалищно-прямокишечная ямка Седалищно-прямокишечная (анальная) ямка, fossa ischiorectalis (ischioanalis) – это парное углубление в области промежности, находящееся по бокам от конечного отдела прямой кишки и седалищных бугров, заполненное жировой клетчаткой, сосудами, нервами и...

Основные структурные физиотерапевтические подразделения Физиотерапевтическое подразделение является одним из структурных подразделений лечебно-профилактического учреждения, которое предназначено для оказания физиотерапевтической помощи...

Машины и механизмы для нарезки овощей В зависимости от назначения овощерезательные машины подразделяются на две группы: машины для нарезки сырых и вареных овощей...

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

Именные части речи, их общие и отличительные признаки Именные части речи в русском языке — это имя существительное, имя прилагательное, имя числительное, местоимение...

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