Нахождение рациональных затрат при строительстве трубопроводов и транспортных артерий

Требуется проложить путь (трубопровод, шоссе) между двумя пунктами А и В таким образом, чтобы суммарные за­траты на его сооружение были минимальные.

Решение. Разделим расстояние между пунктами А и В на шаги (отрезки). На каждом шаге можем двигаться либо строго на восток (по оси X), либо строго на север (по оси Y). Тогда путь от А в В представляет ступенчатую ломаную линию, от­резки которой параллельны одной из координатных осей. За­траты на сооружение каждого из отрезков известны (рис. 2.2) в млн р.

Рис. 2.2

Разделим расстояние от А до В в восточном направлении на 4 части, в северном – на 3 части. Путь можно рассматри­вать как управляемую систему, перемещающуюся под влияни­ем управления из начального состояния А в конечное В. Со­стояние этой системы перед началом каждого шага будет характеризоваться двумя целочисленными координатами х и у. Для каждого из состояний системы (узловой точки) найдем условное оптимальное управление. Оно выбирается так, что­бы стоимость всех оставшихся шагов до конца процесса была минимальна. Процедуру условной оптимизации проводим в об­ратном направлении, т.е. от точки В к точке А.

Найдем условную оптимизацию последнего шага (рис. 2.3).

Рис. 2.3

В точку В можно попасть из B₁ или В₂. В узлах запишем стоимость пути. Стрелкой покажем минимальный путь.

Рассмотрим предпоследний шаг (рис. 2.4).

Рис. 2.4

Для точки В₃ условное управление — по оси X, а для точки B₅ — по оси Y. Управление для точки В₄ выбираем как

т.е. по оси Y.

Условную оптимизацию проводим для всех остальных уз­ловых точек (рис. 2.5).

Рис. 2.5

Получим

где с — север, в —восток.

Минимальные затраты составляют

Если решать задачу исходя из оптимальности на каждом этапе, то решение будет следующим:

Затраты составят 10 +12 + 11 + 10 + 9 + 13 +10 = 75 > 71.

Ответ. Прокладывать путь целесообразно по схеме: с, с, в, с, в, в, в, при этом затраты будут минимальные и составят 71 млн р.

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

Рекуррентные соотношения будут иметь вид:

для предприятия № 1:

для всех остальных предприятий:

Решение будем проводить согласно рекуррентным соотно­шениям в четыре этапа.

1-й этап. Инвестиции производим только первому пред­приятию. Тогда

f₁(50)=12, f₁(100)=17, f₁(150)=23,

f₁(200)=34, f₁(250)=42.

2-й этап. Инвестиции выделяем первому и второму пред­приятиям. Рекуррентное соотношение для 2-го этапа имеет вид

тогда

при х = 50 f₂(50) = max (12 + 13) = max (12, 13) = 13,

при x = 100 f₂(100) = max (17,12 + 13,15) = max (17, 25, 15) =25,

при х = 150 f₂(150) = max (23,17 + 13, 12 + 15,25) = max (23,30, 27,25) =30,

при х = 200 f₂(200) = max (34,23 + 13,17 + 15,12 + 25,33) = max (34, 36, 32, 37, 33) = 37,

при х = 250 f₂(250) = max (42,34 + 13,23 + 15,17 + 25,12 + 33,41) = max (42, 47, 38, 42, 45, 41) = 47.

3-й этап. Финансируем 2-й этап и третье предприятие. Расчеты проводим по формуле

тогда

при х = 50 f₃(50) = mах (13, 11) = 13,

при x = 100 f₃(100) = max (15,13 + 11,16) = max (15, 24, 16) = 24,

при х = 150 f₃(150) = max (25,15 + 11,13 + 16,21) = max (25, 26, 29, 21) = 29,

при х = 200 f₃(200) = max (33,25 + 11,15 + 16,13 + 21,35) = max (33, 36, 31, 34, 35) = 36,

при x = 250 f₃(250) = max (41,33 + 11,25 + 16,15 + 21,13 + 35,43) = max (41, 44, 41, 36, 48, 43) = 48,

4-й этап. Инвестиции в объеме 250 млн. р. распределяем между 3-м этапом и четвертым предприятием.

При х = 250 f₄(250) = max (48,36 + 11,29 + 18,24 + 22,13 + 34,44) = max (48, 47, 47, 46, 47, 44) = 48.

Получены условия управления от 1-го до 4-го этапа. Вер­немся от 4-го к 1-му этапу. Максимальный прирост выпус­ка продукции в 48 млн. р. получен на 3-м этапе как 13 + 35, т.е. 35 млн. р. соответствуют выделению 200 млн. р. третьему предприятию. Согласно 2-му этапу 13 млн. р. получены при выделении 50 млн. р. второму предприятию.

Таким образом, инвестиции в объеме 250 млн. р. целесообразно выделить второму, третьему и четвертому предприятиям по 50 млн. р. каждому, при этом прирост продукции будет максимальным и составит 48 млн. р.