Лекция 2. Алгоритм метода потенциалов

 

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

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

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

При этом информация должна отвечать следующим требованиям:

а) все виды ресурсов должны измеряться в единых величинах
(физических или стоимостных);

б) наличие ресурсов и потребность в них должны быть уравнены;

в) процесс перераспределения ресурсов должен выражаться в натуральных или стоимостных оценках.

Целью решения задачи является нахождение минимума или максимума функции, т. е.

,

где i, I ₀ – соответственно номер и множество поставщиков;

j, J ₀– соответственно номер и множество потребителей;

– материально-денежные затраты (или доход) для использования единицы ресурса поставщика i потребителем j;

х_ij – объем ресурса поставщика i для потребителя j.

Экстремум должен быть обеспечен при соблюдении приведенных ниже условий.

1. По использованию возможностей каждого из поставщиков

, ,

где А_i – запасы поставщика i.

Данное соотношение обозначает, что объем ресурсов, полученных потребителями от поставщика, будет равен запасам этих ресурсов у поставщика. Количество таких ограничений будет равно числу поставщиков (). Например, применительно к первому поставщику (i = 1) ограничение может иметь вид х ₁₁ + х ₁₂ + х ₁₃ +... + х _{1 п} = А ₁.

2. По удовлетворению запросов каждого из потребителей

, ,

где В_j – заказы потребителя j.

Соотношение обозначает, что объем ресурсов, полученных от разных поставщиков, будет равен заказу каждого из потребителей. Число таких ограничений будет равно количеству потребителей (). Например, применительно к первому потребителю (j = 1) ограничение может иметь вид .

3. По соотношению наличия ресурсов (возможности поставщиков) и потребности в них (заказов потребителей)

, .

Данное соотношение определяет тип задачи: открытый или закрытый. В первом случае наличие ресурсов не равно потребности в них, во втором – равно.

Решение предусматривает нахождение х_ij,т. е. объема ресурса i для потребителя j. При этом решение задачи может быть ориентировано как на минимум, так и на максимум.

Рассмотрим пример реализации алгоритма данного метода.

1. Возможности поставщиков ресурсов, т: А – 330, В – 592, С – 710, Д – 1240. Итого – 2872 т.

2. Заказы потребителей ресурсов, т: первый – 542, второй – 810, третий – 792, четвертый – 800. Итого – 2944 т.

3. Материально-денежные затраты на перевозку грузов (ресурсов) от поставщиков к потребителям представлены в табл. 1.

4. Переменные не должны быть отрицательными, т. е. х_ij > 0.

 

Т а б л и ц а 1. Материально-денежные затраты на перевозку 1 т грузов, у.е.

 

Поставщики	Потребители
1-й	2-й	3-й	4-й
А	3,10	3,37	2,43	2,87
В	2,95	2,64	2,96	3,97
С	4,30	3,06	3,21	3,51
Д	2,42	4,05	3,21	2,59
Фиктивный (Е ф)	0,00	0,00	0,00	0,00

 

Поскольку наличие ресурсов (A_i), т. е. возможности поставщиков, не равно потребности в ресурсах, т. е. заказам потребителей (В_j),то задача является открытой. Преобразуем ее в закрытую задачу. Для этого вводим положительную величину, которая увели­чивает меньшее значение, т. е. наличие ресурсов (), до большего, т. е. потребностей (). Поскольку ресурсов недостает, то вводим пятый (недостающий) фиктивный ресурс (или поставщика Е _ф)с объемом, равным 72 т, Е _ф= 2944–2872. При этом материально-денежные затраты () по перевозке недостающего груза от поставщика к потребителю i будут нулевыми. Всего поставщиков будет пять (i = 1,..., 5), а потребителей – четыре (j = 1,..., 4).

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

 

 

Т а б л и ц а 2. Исходная информация для решения задачи

 

Поставщики	Потребители	Наличие ресурсов, т
1-й	2-й	3-й	4-й
А	3,10 х 11	3,37 х 12	2,43 х 13	2,87 х 14
В	2,95 х 21	2,64 х22	2,96 х 23	3,97 х 24
С	4,3 х 31	3,06 х 32	3,21 х 33	3,51 х 34
Д	2,42 х 41	4,05 х42	3,21 х43	2,59 х 44
Е ф	х 51	х 52	х 53	х 54
Потребность в ресурсах, т

 

Решение задачи методом потенциалов предусматривает постепенное улучшение исходного плана (допустимого или опорного) до оптимального. При этом опорное решение можно получить способами северо-западного угла и предпочтительных оценок.

Рассмотрим способы получения опорного решения.

Способ северо-западного угла. Сущность его состоит в следующем. Задание по перевозкам (х_ij) начинаем распределять с верхней клетки слева, условно принятой за северо-западный угол (1; 1). В нее записываем число x ₁₁, равное меньшему из значений, стоящих в строке (330) и столбце (542), которые содержат эту клетку, т. е. записываем 330. В этом случае ресурсы первого поставщика исчерпаны, но заказ первого заказчика не выполнен на 212 т (542 – 330). Чтобы удовлетворить этот заказ, рассматриваем возможности второго поставщика В (В = 592) и в клетку х ₂₁запишем меньшее из значений для этой клетки (212 и 592), т. е. 212. Теперь заказ первого потребителя в количестве 542 т выполнен, однако возможности поставщика В недоиспользованы на 380 единиц (592 – 212). Их распределяем второму потребителю, начиная с клетки (2; 2). Для нее характерны следующие значения: в строке – оставшийся ресурс поставщика В (второго) – 380 т и заказ – 810 т (в соответствующем столбце). По тому же принципу план распределяем и дальше. Таким образом, получаем опорный план (табл. 3).

 

 

Т а б л и ц а 3. Опорный план задачи, определенный способом

Северо-западного угла

 

Поставщики	Потребители	Наличие ресурсов, т
1-й	2-й	3-й	4-й
А	3,10	3,37	2,43	2,87
В	2,95	2,64	2,96	3,97
С	4,3	3,06	3,21	3,51
Д	2,42	4,05	3,21	2,59
Е ф
Потребность в ресурсах, т

 

Недостаток способа северо-западного угла состоит в том, что при его использовании коэффициенты не учитываются. Это приводит к увеличению объема вычислений в процессе поиска оптимального плана.

Способ предпочтительных оценок. При использовании способа предпочтительных оценок учитываем следующее:

1) распределение плана осуществляем исходя из значений . Следует отметить, что при решении задачи на минимум лучшей будет клетка с меньшим значением , а на максимум – с большим ();

2) построение опорного плана начинаем со строки или столбца с наибольшим количеством запрещенных клеток (обозначаются такие клетки прочерком). В этой строке или столбце выбираем лучшую (в соответствии с целью задачи) клетку и в нее записываем меньшее число (по наличию ресурса или потребности в нем в строке или столбце для этой клетки). Затем определяем следующую клетку и продолжаем этот процесс до тех пор, пока ресурсы поставщика не будут исчерпаны (в строке), а заказы потребителя – выполнены (в столбце);

3) если имеются нуль-строка или нуль-столбец, то при решении
задачи на минимум план записываем в ту нуль-клетку, для которой характерна большая по абсолютной величине разность между нулем и лучшим (в соответствии с целью задачи) значением целевой функции (0 – ), стоящим в строке или столбце для этого нуля. При решении задачи на максимум за основу принимаем нуль с соответствующей меньшей разностью. В данном случае = 0 (в строке для этого нуля стоят нулевые оценки). Таким образом, рассматриваем коэффициенты столбца (0; 2,42), затем (0; 2,64), (0; 2,43), (0; 2,59). Большая разность характерна для клетки к ₅₂ (0; 2,64). В нуль-клетку к ₅₂записываем возможный план х ₅₂ = 72. При этом возможности поставщика Е _фбудут исчерпаны. В другом случае рассматривали бы клетку х ₅₄(0; 2,59) и т. д.;

4) после распределения плана в строках (столбцах) с запрещенными клетками и в нуль-строке (столбце) распределение плана выполняем по оставшимся клеткам, начиная с лучшей (с точки зрения достижения цели). В нашем примере такой клеткой будет клетка k ₄₁ при = 2,42. В нее записываем 542 и, таким образом, заказ первого потребителя будет выполнен. Затем находим лучшую клетку из оставшихся и продолжаем этот процесс до полного распределения плана. Следующей лучшей клеткой будет клетка k ₁₃ при = 2,43. В нее заносим план, равный 330, и т. д. В результате получим опорный план (табл. 4).

Таким образом, использование способа северо-западного угла обеспечило нахождение опорного плана, т. е. решения, при котором ресурсы распределены, а заказы выполнены.

Затраты материально-денежных средств на выполнение плана, полученного данным способом, составят:

F = 330 × 3,10 + 212 × 2,95 + 380 × 2,64 + 430 × 3,06 +

+ 280 × 3,21 + 512 × 3,21 + 728 × 2,59 + 0 × 72 = 8376,15.

 

Т а б л и ц а 4. Опорный план, определенный способом предпочтительных оценок

Поставщики	Потребители	Наличие ресурсов, т
1-й	2-й	3-й	4-й
А	3,10	3,37	2,43	2,87
В	2,95	2,64	2,96	3,97
С	4,3	3,06	3,21	3,51
Д	2,42	4,05	3,21	2,59
Е ф
Потребность в ресурсах, т

 

Затраты материально-денежных средств на выполнение опор­ного плана, полученного способом предпочтительных оценок, составят:

F = 330 × 2,43 + 592 × 2,64 + 146 × 3,06 + 462 × 3,21 +

+ 102 × 3,51 + 542 × 2,42 + 698 × 2,59 + 72 × 0 = 7772,00.

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

При построении опорного или исходного плана важно обеспечить соблюдение следующего правила: число заполненных клеток должно составлять сумму строк (т)и столбцов (п)без единицы (т + п – 1). В нашем случае число строк равно пяти, столбцов – четырем. Следовательно, заполненных клеток должно быть восемь. В обоих случаях их количество равно восьми. В том случае, если число заполненных клеток меньше т + п – 1, можно сделать следующее: а) поменять местами несколько строк или столбцов; б) поставить нуль в лучшую (с точки зрения достижения цели) из оставшихся пустых клеток. Следует помнить, что число заполненных клеток будет меньше т + п – 1, если какое-либо значение в строке «потребность в ресурсах» равно значению суммы или разности значений столбца «наличие ресурсов» (или наоборот).

Построенный опорный план необходимо проверять на оптимальность. Проверка включает два этапа.

1. Нахождение потенциалов (оценочных коэффициентов) для заполненных клеток, т. е. клеток, в которых записан план.

2. Проверка на потенциальность незаполненных клеток. Проверка состоит в том, чтобы выяснить, имеются ли свободные клетки для улучшения плана, т. е. уменьшения значения F (функции) при решении задачи на минимум или увеличения F при решении задачи на максимум. Рассмотрим содержание этапов.

Потенциалы для заполненных клеток определяем по формуле

, (1)

откуда ; (2)

, (3)

где – потенциал столбца или потребителя j;

j = 1 – потенциал строки i или поставщика i, i = 1,..., 5.

Поскольку в уравнении (1) имеется два неизвестных, то одному из них придаем произвольное значение, например и ₁= 0. При этом за основу дальнейших расчетов принимаем опорный план, полученный способом предпочтительных оценок. В табл. 5 введем дополнительную строку (для обозначения потенциалов столбцов v_j) и дополнительный столбец (для обозначения потенциалов строк и_i).

Поскольку и_i = 0, то по коэффициенту 2,43 () занятой клетки k ₁₃ определим: . Так как в строке u ₁ больше нет заполненных клеток, то берем вновь определенный потенциал v ₃и на его основе (с учетом заполненных клеток столбца v ₃) найдем новые потенциалы. В столбце v ₃ заполненной является клетка k ₃₃, для которой следует определить потенциал строки u ₃.Согласно формуле (3) . Поскольку в столбце v ₃ больше заполненных клеток не имеется, то принимаем за основу найденное значение u ₃ = – 0,78 и рассчитываем по данным заполненных клеток к ₃₄ и к ₃₂ потенциалы v ₄ и v ₂. Они соответственно равны: v ₄ = λ ₃₄ + и ₃ = 3,51 + + (–0,78) = 2,73; v ₂ =λ ₃₂ + и ₃ = 3,06 + (–0,78) = 2,28. Таким образом, вычисления продолжаем до определения потенциалов для всех строк и столбцов. После этого проверяем возможность улучшения плана за счет незаполненных клеток, т. е. проверяем план на потенциальность. Решение будет оптимальным, если для незаполненных клеток выполняются условия:

при решении задачи на минимум

; (4)

при решении задачи на максимум

. (5)

 

Т а б л и ц а 5. Рабочая таблица оптимизации распределения ресурсов

Между потребителями

 

Поставщики	Потребители	Ресурсы	Потенциалы поставщиков, иi
1-й	2-й	3-й	4-й
А	3,10	3,37	2,43	2,87		и 1
В	2,85	2,64	2,96	3,97		и 2 –0,26
С	4,3	+ 3,06 146	3,21	3,51 102 –		и 3 –0,78
Д	2,42	4,05	3,21	2,59		и 4 0,04
Е ф		72 –		+		и 5 2,28
Потребность в ресурсах						–
Потенциалы потребителей, vj	v 1 2,56	v 2 2,28	v 3 2,43	v 4 2,73

В нашем случае проверяем незаполненные клетки по формуле (4). Нарушения будут иметь место, если для незаполненной клетки характерно неравенство . При этом величина нарушения потенциальности (k_ij)составит: .

Из табл. 5 следует, что нарушение характерно для клетки k ₅₄. Величиной нарушения потенциальности является k_ij,т. е. k ₅₄= 2,73 – 2,28 – – 0 = 0,45. С экономической точки зрения величина непотенциальности означает, на сколько денежных единиц изменится значение F (при решении задач на минимум F уменьшается, на максимум – возрастает), если в непотенциальную клетку вследствие перераспределения плана введем задание (х_ij),равное единице. Клетка с нарушением потенциальности становится основой для улучшения плана. Если же в результате проверки определено несколько нарушений, то при решении задач на минимум и максимум в качестве исходной для улучшения плана принимают клетку с наиболь­шим нарушением. Улучшение плана выполняем на основе цикла, который строится по приведенным ниже правилам.

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

2. Вершины цикла проходят только по заполненным клеткам. При этом поворот линии цикла осуществляют только в занятых клетках и под углом 90°. Число вершин цикла в строке или столбце должно быть четным (если число заполненных клеток меньше чем т + п – 1, то в цикле могут получиться две и более незаполненные клетки). Решение в подобной ситуации возможно, если номер другой незаполненной клетки (кроме той, что послужила началом цикла, т. е. непотенциальной и с наибольшим нарушением), будет нечетным по отношению к начальной клетке цикла.

3. В непотенциальную клетку цикла ставится знак «плюс», в следующую – «минус» и так поочередно (если число заполненных клеток цикла меньше чем т + п – 1,то в другие клетки цикла, кроме начальной, ставится нуль). При этом необходимо, чтобы знак для данных нулевых клеток был положительным, что достигается, если номера этих клеток будут нечетными (принимая номер клетки начала цикла за 1).

В нашем случае непотенциальной клеткой является клетка к ₅₄. Она является началом цикла, который пройдет по клеткам k ₅₄ – k ₅₂ – k ₃₂ – k ₃₄. Проставляем знаки в вершинах цикла: k ₅₄(+), k ₅₂(–), k ₃₂ (+), k ₃₄ (–). По цепи цикла перемещаем меньшее число клетки со знаком «минус» (т. е. 72) и получаем новый план (табл. 6).

Материально-денежные затраты на выполнение плана составят:

F ₂= 330 × 2,43 + 592 × 2,64 + 218 × 3,06 + 462 × 3,21 + 30 ×

× 3,51 + 542 × 2,42 + 698 × 2,59 + 72 × 0 = 7739,60.

 

Т а б л и ц а 6. Улучшенный план распределения ресурсов

Поставщики	Потребители	Ресурсы	Потенциалы поставщи­ков иi
1-й	2-й	3-й	4-й
А	3,10	3,37	2,43	2,87
В	2,95	2,64	2,96	3,97		–0,36
С	4,3	3,06	3,21	3,51		–0,78
Д	2,42	4,05	3,21	2,59		0,14
Е ф						2,73
Потребность в ресурсах						–
Потенциалы по­требителей Vj	2,56	2,28	2,43	2,73

 

Новый план вновь проверяем на потенциальность, т. е. опять выполняем расчеты двух этапов. И продолжаем эти расчеты до тех пор, пока в незаполненных клетках не будет нарушений. В нашем случае таких нарушений нет. Следовательно, F ₂= F _min = 7739,6 у.е. Значения F,следующие после первого, можно определять по упрощенной схеме по формуле

F_{j+ 1} = F_j ± b_{j+ 1} + p_{j+ 1} ,

где F_j – значение функции, определенной по данным из предыдущей таблицы;

b_{j+ 1} – величина непотенциальности клетки, положенной в основу цикла;

p_{j+ 1}– значение плана, перемещаемое по циклу (знак «–» – при минимуме или знак «+» – при максимуме).

 

В нашем случае F ₁ = 7772,0 у.е., b_{j+ 1} = 0,45, p_{j+ 1} = 72. В результате имеем:

F ₂ = 7772,0 – 0,45 × 72 = 7739,6 у.е.

Оптимальная программа предусматривает удовлетворение потребности третьего потребителя за счет ресурсов первого поставщика(А),т. е. х ₁₃ = 330, потребности второго – за счет ресурсов второго поставщика (х ₂₂= 592) и т. д. Значение х ₅₄, равное72, означает, что при недостатке ресурсов поставщиков и критерии оптимальности, которым является минимум материально-денежных затрат, целесообразнее всего недовыполнять заказ четвертого потребителя.