double arrow

Алгоритм метода потенциалов

1. Условия задачи запитать в форме распределительной таблицы.

2. Проверить: является ли задача сбалансированной.

3. Построить начальный опорный план.

4. Вычислить потенциалы поставщиков и потребителей (численные значения потенциалов Ui и Vj определяются из системы уравнений, получаемых по всем базисным клеткам плана из равенства Ui+Vj=Cij ).

5. Вычислить оценки свободных клеток плана по формуле Δij=Cij – (Ui+Vj). Если оценки Δij свободных клеток плана – неотрицательны, то план о птимальный. Если же среди оценок есть отрицательные, то построенный план не является оптимальным.

Для получения лучшего плана поступают так:

1) Клетку с наименьшей отрицательной оценкой переводят в базисную вместо какой-либо прежней базисной.

2) Для вводимой клетки строится замкнутый цикл; ей приписывается знак «+», а следующей базисной (только в вершинах) по ходу цикла в любом направлении знак «-», затем опять «+» и т.д.

3) В клетках со знаком «-» выбирается наименьшая загрузка, которая перемещается по циклу с прибавлением его в положительных и вычитанием в отрицательных клетках.

4) В итоге одна из базисных клеток становится свободной и образуется новых опорный план, который также проверяется на оптимальность.

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

Если целевая функция модели задачи на максимум, то:

- начальный опорный план строится по способу максимального элемента;

- план будет оптимальным, если все оценки свободных клеток неположительны (≤ 0);

- выбор перспективной клетки для нового плана производится по наибольшей положительной оценке свободных клеток;

- перемещение «грузов» по циклу по прежнему производится с наименьшей «загрузкой».

Пример. Три предприятия производят продукцию в количествах 650; 450; 550 единиц изделий. Готовая продукция отгружается в четыре хранилища, пропускная способность которых соответственно 300; 600; 150 и 400 единиц изделий. Тарифы перевозок задаются матрицей с:

Методом потенциалов найти оптимальный план перевозки продукции.

Решение:

1. Запишем условие задачи в виде распределительной таблицы, обозначая предприятия - Аί, а хранилища - Вj.

Bj Аi B1 (300) B2 (600) B3 (150) B4 (400)
A1 (650) 8 10 7 5
A2 (450) 5 8 10 7
A3 (550) 12 7 10 8

2.Суммарное количество груза поставщиков , а потребителей не совпадает. Следовательно, данная задача является открытой, небаланс составляет 1650-1450=200 ед. и вызван меньшей пропускной способностью хранилищ, следовательно, вводим пятое фиктивное хранилище В5 с грузом 200 единиц и нулевыми тарифами.

3. Построим начальный опорный план.

Применим способ “предпочтительных оценок”. Первой загрузим клетку (3; 5), так как при наличие в таблице нуль-строки или нуль-столбца, загружать начинаем ту клетку, которая имеет наибольшую по модулюразность между нулем и минимальным тарифом. Загрузка составляет min {550; 200} = 200. При этом пятый столбец полностью зактрывается.Следующей загрузим клетку (1; 4), так как тариф этой клетки наименьший среди оставшихся и загрузка больше чем для клетки (2; 1). Загрузка равна min {650; 400} = 400. При этом полностью загружается четвертый столбец. Далее загружаем клетку (2; 1). Загрузка равна min {450; 300} = 300 и закрывается первый столбец. Следующей загружаем клетку (3; 2), так загрузка этой клетки min {550 - 200; 600} = min {350; 600} = 350 больше чем загрузка клетки (1; 3), имеющей такой же тариф, min {650 - 400; 150} = min {250; 150} = 150. Таким образом, закрывается третья строка. Загружаем клетку (1; 3), при этом закрываем третий столбец. Оставшиеся клетки загружаются однозначным образом.

Распределительная таблица 1

Bj Аi B1 (300) B2 (600) B3 (150) B4 (400) B5 (200)  
A1 (650) 8 100 -10 150 7 400 5 + 0 U1=0
A2 (450) 300 5 150 8 10 7 0 U2=-2
A3 (550) 12 350 +7 10 8 - 200 0 U3=-3
  V1=7 V2=10 V3=7 V4=5 V5=3  

Итак, загруженных клеток оказалось 7, равно числу 3+5-1, следовательно составленный план невырожденной и является начальным опорным планом.

4. Вычислим потенциалы поставщиков и потребителей.

Если U1=0, то из первых трех уравнений определяются V2=10; V3=7; V4=5. По найденному V2=10 определяются U2=-2 и U3=-3. По U2=-2 найдем V1=7. Зная U3=-3, найдем V5=3. Найденные значения потенциалов плана занесены в последней строке и последнем столбце распределительной таблицы 1.

5. Сейчас вычисляем оценки Δij свободных клеток плана:

Δ11 = 8 – (7 + 0) = 1 > 0;

Δ15 = 0 – (0 + 3) = - 3 < 0;

Δ23 = 10 – (7 - 2) = 5 > 0;

Δ24 = 7 – (5 - 2) = 4 > 0;

Δ25 = 0 – (3 - 2) = -1 < 0;

Δ31 = 12 – (7 - 3) = 8 > 0;

Δ33 = 10 – (7 - 3) = 6 > 0;

Δ34 = 8 – (5 - 3) = 6 > 0.

Так как среди оценок имеются отрицательные, то найденный опорный план не является оптимальным.

Улучшим данный план, следующим образом: переводим в базисную клетку (1, 5), как имеющую наименьшую отрицательную оценку (Δ15 = - 3). C этой целью строим для неё замкнутый цикл с вершинами в базисных клетках (1, 5); (3, 5); (3, 2); (1, 2), расставляя в вершинах поочередно, начиная с клетки (1, 5), знаки «+» и «-». Построенный цикл в распределительной таблице 1 изображен штриховыми линиями.

Из загрузок в «отрицательных» клетках цикла выбираем наименьшую величину 100. Груз в 100 ед. прибавляем в «положительных» (1, 5); (3, 2) и вычитаем в «отрицательных» (1, 3); (3,5) клетках. В итоге прежняя базисная клетка (1, 2) становится свободной, а вместо неё вводится (1, 5).

Получаем новый опорный план, представленный распределительной таблицей 2.

Распределительная таблица 2

Bj Аi B1 (300) B2 (600) B3 (150) B4 (400) B5 (200)  
A1 (650) 8 10 150 7 400 5 100 0 U1=0
A2 (450) 300 5 150 8 10 7 0 U2=1
A3 (550) 12 450 7 10 8 100 0 U3=0
  V1=4 V2=7 V3=7 V4=5 V5=0  

Рассчитав оценки свободных клеток видим, что Δ25 = - 1, что свидетельствует о том, что полученный план также не является оптимальным.

Улучшаем его, путем перевода в базисные клетки (2; 5). В итоге получим распределительную таблицу 3.

Распределительная таблица 3

Bj Аi B1 (300) B2 (600) B3 (150) B4 (400) B5 (200)  
A1 (650) 8 10 150 7 400 5 100 0 U1=0
A2 (450) 300 5 50 8 10 7 100 0 U2=0
A3 (550) 12 550 7 10 8 0 U3=-1
  V1=5 V2=8 V3=7 V4=5 V5=0  

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

Транспортные расходы при этом составят:

f = 150 . 7 + 400 . 5 + 300 . 5 + 50 . 8 + 550 . 7 = 8800 д.ед.

Ответ: Продукция первого предприятия в количестве 150 ед. направляется в третье, а 400 ед. в четвертое хранилище, 100 ед. продукции остается на предприятии. Продукция второго предприятия направляется в количествах 300 ед. и 50 ед. соответственно в первое и второе хранилище. Продукция третьего предприятия полностью вывозится во второе хранилище. Транспортные расходы при этом будут минимальными и составят 8800 ден. единиц.

Литература:

1. Кузнецов А.В. и др. Руководство к решению задач по математическому программированию: Учеб.пособие / А.В.Кузнецов, Н.И.Холод, Л.С.Костевич. – Мн.: Выш.шк., 2001, с. 129 – 155.

2. Минюк С.А. Математические метод и модели в экономике: Учеб.пособие. – Мн.: ТетраСистемс, 2002, с. 66-75.

Контрольные вопросы:

1. Сформулируйте транспортную задачу.

2. Какова табличная форма транспортной задачи?

3. Какие транспортные задачи называются сбалансированными?

4. Сформулируйте теорему разрешимости транспортной задачи.

5. Как решаются транспортные задачи с нарушенным балансом между спросом и предложением?

6. Какими способами можно построить начальный опорный план транспортной задачи?

7. В чем сущность способа «северо-западного угла»?

8. В чем сущность способа «предпочтительных оценок»?

9. В чем сущность способа Фогеля?

10. Как разрешается проблема вырождения в транспортной задаче?

11. В чем сущность метода потенциалов? Как с его помощью проверяется опорный план транспортной задачи на оптимальность?

12. Когда транспортная задача имеет единственное решение?

13. Какие особенности при решении транспортных задач на максимум?


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: