Методом расчленения бендерса

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

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

2. Стоимость перевозки и хранения на складах является фиксированной положительной величиной, если перевозится положительное количество, или нулем в противном случае, как это показано на рис. 1 для склада i. Фиксированные затраты f_i представляют капиталовложения, требуемые для строительства i-го склада.

3. Затраты на доставку к потребителю j из i-го склада являются линейными функциями объема продукции с ценой за единицу равной

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

Задача может быть сформулирована как частично-целочисленная задача линейного программирования, в которой переменные типа 0 и 1 представляют альтернативы строительства данного склада. Пусть есть объем продукции перевозимой со склада i к потребителю j, тогда должно выполняться условие:

(27)

где d_j-потребность j-го потребителя в продукции.

Введем в рассмотрение обозначения

(28)

(29)

Тогда математическая формулировка этой задачи запишется в следующем виде:

Если y_i = 1, тогда используется склад i. Если y_i = 0, то x_ij = 0 для всех j, и капитальные затраты равны нулю. Пусть y = (y₁, …, y_m) фиксировано, тогда (30)-(33) представляет обычную задачу ЛП. Алгоритм Бендерса добавляет ограничения к чисто целочисленной задаче МР2 путем решения двойственной к (30)-(33),которая имеет вид:

Множество Р в задаче (34)-(36) это множество всех переменных, удовлетворяющих (35) и (36), а задача Р2 имеет вид:

Алгоритм может быть начат с учета нескольких или даже ни одного из ограничений вида (37) задачи Р2. Пусть решение этой ограниченной задачи МР2 есть Y. После этого должна быть решена двойственная пара задач (30)-(33) и (34)-(36), причем, y фиксируется при значении y⁰. Оптимальное решение может быть получено в явной форме. Пусть множество складов, которые предполагается открыть на данной итерации, обозначено так:

(40)

Мы предполагаем, что условие y ≠ 0 выполнено, так что I не пусто. Задача (30)-(33)приобретает вид:

(41)

(42)

Поскольку С_ij ≥ 0, то ограничения (42) на оптимальном решении выполняются, как равенства. Из-за того, что ограничения (42) независимы, то решение находится непосредственно, если положить x_ij = 1 для минимальных С_ij и нулем в противном случае, т.е.

(43)

(44)

Это решение связывает потребителей с наиболее выгодным складом К_j. Для того, чтобы получить соответствующее двойственное решение, используем условие дополняющей не жесткости:

(45)

Остальные двойственные ограничения таковы:

(46)

(47)

Подставляя (45) в целевую функцию (34), мы удостоверяемся, что ее значение не зависит от , поскольку появляется дважды с противоположными знаками. Таким образом, мы можем положить Для того, чтобы максимизировать (34), остающиеся слагаемые u_ij должны быть взяты настолько малыми, насколько позволяют ограничения (46)-(47). Это приводит к следующему оптимальному решению:

(48)

(49)

Пусть d⁰ - оптимальное значение целевой функции двойственной задачи, а z⁰ - оптимальное значение, полученное при решении МР2. Если

(50)

то текущее решение оптимально; если - нет, то образуется новое ограничение с помощью ,

(51)

Это ограничение добавляется к МР2, далее снова решается двойственная задача и МР2, и так до тех пор, пока не будет найдено решение задачи.

Пример.

Рассмотрим пример, взятый из /3/ с.293, представляющий собой задачу размещения вида (30)-(33) с четырьмя пунктами размещения (складами) и потребителями, причем затраты на строительство складов f_i = 7 для всех i, а матрица затрат на перевозки

(52)

Цикл1. Первоначально в МР2 не вводится никаких ограничений. Выберем y⁰ = (0, 1, 0, 0) и положим z = -∞. Решая пару линейных задач (30)-(33), (34)-(36), находим

(53)

Начальная задача МР2 такова:

(54)

Решением задачи (54) будет точка y⁰ = (1, 0, 1, 0), в которой значение z⁰ = 18. Решаем при этом значении y⁰ пару линейных задач (30)-(32), (34)-(36). После этого получаем

, (55)

Критерий оптимальности (50) не выполняется, так как d⁰ = 14, а и d⁰ ≠ к, из чего следует, что оптимальное решение пока не найдено, поэтому решаем задачу МР2, добавив в нее дополнительное ограничение из (34)-(36):

(56)

Решением задачи МР2 (56) является точка y⁰ = (1, 0, 0, 0), что дает значение z⁰ = 21.

При данном значении y⁰ решаем снова пару линейных задач (30)-(32) и (34)-(36). В результате получаем:

(57)

Критерий оптимальности (50) для данных y⁰ и z⁰ не выполняется, так как и их значения не совпадают, вследствие чего нужно решать новую задачу МР2, полученную из (57) с добавлением в нее дополнительного ограничения из (34)-(36):

(58)

Решением задачи МР2 (58) является точка y⁰ = (0, 0, 1, 0), в которой значение z⁰ = 25.

При найденном значении y⁰ решаем пару линейных задач (30)-(32) и (34)-(36), в результате чего получаем:

(59)

Критерий оптимальности (50) и в этом случае не выполняется, поскольку поэтому необходимо решать новую задачу МР2, получающуюся из (58) с добавлением в нее ограничения из (34)-(36) с учетом (59):

(60)

Решением задачи (60) является точка y⁰ = (1, 0, 0, 1), в которой значение z⁰ = 26.

При найденном значении y⁰ решаем пару линейных задач (30)-(32) и (34)-(36), в результате чего получаем:

(61)

В этом случае критерий оптимальности выполняется, поскольку что свидетельствует о том, что точка y⁰ = (1, 0, 0, 1) является оптимальной.

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

Решение исходной задачи

Мaтрица перевозок

1.0 0.0 0.0 0.0

0.0 0.0 0.0 0.0

0.0 0.0 0.0 0.0

0.0 1.0 1.0 1.0

Значение целевой функции = 26.000

Координаты размещения складов

1.0 0.0 0.0 1.0

ЗАДАНИЕ К РАБОТЕ

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

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

5. Стоимость перевозки и хранения на складах является фиксированной положительной величиной, если перевозится положительное количество, или нулем в противном случае, как это показано на рис. 1 для склада i. Фиксированные затраты f_i представляют капиталовложения, требуемые для строительства i-го склада.

6. Затраты на доставку к потребителю j из i-го склада являются линейными функциями объема продукции с ценой за единицу равной

f = (30 – n, 1 + n, 6, 7);

.

ЛИТЕРАТУРА

1 J.F. Benders Partitioning Procedures for solving mixed variables programming problems. Numerische Mathematik, №4, 1962, p.p. 238-252.

2 Л.С. Лэсдон Оптимизация больших систем. –М.:, Наука, 1975, -432с.