§6. Задача прокладки трубопровода

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

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

Y	(север)				B
	13 11 12 8	9 12 14	9 13 14	10 14 14
	13 15 12	10 11	10 16	8 10
	10 13 14	12 13	9 10	12 14
A			Рис. 1		X (восток)

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

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

В точку В можно попасть из В₁ или В₂, В узлах запишем стоимость пути. Стрелкой покажем минимальный путь. Рассмотрим предпоследний шаг (рис. 3).

Рис. 3

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

min{13+10, 14+14)=min{23, 28}=23,

т.е. по оси Y.

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

Получим X_опт=(с, с, в, с, в, в, в), где с — север, в —восток. Минимальные затраты составляют 10+13+8+12+9+9+10=71 млн р.

Если решать задачу исходя из оптимальности на каждом этапе, то решение будет следующим: X=(с, в, в, с, в, с, в). Затраты составят 10+12+11+10+9+13+10=75>71.

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

7. Упражнения

В задачах 7.1 и 7.2 найти оптимальное распределение средств между п предприятиями при условии, что прибыль f(х), полученная от каждого предприятия, является функцией от вложенных в него средств х. Вложения кратны x, а функции f(х) заданы таблично.

7.1.

x	1	2	3	4	5	6	7	8	9
f1(х)	5	9	12	14	15	18	20	24	27	S0=9
f2(х)	7	9	11	13	16	19	21	22	25	n=3
f3(х)	6	10	13	15	16	18	21	22	25	x=1

7.2.

x	1	2	3	4	5
f1(х)	0,2	0,9	1,0	1,2	2,0	S0=5
f2(х)	1,0	1,1	1,3	1,4	1,8	n=4
f3(х)	2,1	2,5	2,9	3,9	4,9	x=1
f4(х)	0	2,0	2,5	3,0	4,0

7.3. В условиях задачи 7.1 найти оптимальное распределение средств S₀=8.

7.4. В условиях задачи 7.2 найти оптимальное распределение средств S₀=9 между четырьмя предприятиями, если функция прибыли для четвертого предприятия задана следующей таблицей:

x	1	2	3	4	5	6	7	8	9
f4(х)	3	5	7	11	13	15	20	22	24

7.5. В условиях задачи 7.2 найти оптимальное распределение средств S₀=6 между четырьмя предприятиями.

7.6. В условиях задачи 7.3 найти оптимальное распределение средств между 2-, 3- и 4-м предприятиями (1-е предприятие исключить).

В задачах 7.7 — 7.9 найти оптимальное распределение ресурсов S₀ между двумя отраслями производств I и II в течение п лет, если даны функции доходов f₁(х) и f₂(х) для каждой отрасли, функции возврата ₁(х) и ₂(х). По истечении года только все возвращенные средства перераспределяются, доход в производство не вкладывается.

7.7. S₀=40000 ед.; n=4; f₁(х)=0,4х; f₂(х)=0,3х;₁(х)=0,5х; ₂(х)=0,8х.

7.8. S₀=10000 ед.; n=4; f₁(х)=0,1х²; f₂(х)=0,5х;₁(х)=0,75х; ₂(х)=0,3х.

7.9. Решить задачу 7.7 при условии, что в начале каждого года дополнительно поступают средства в размерах S=10000.

В задачах 7.10  7.12 составить математическую модель, записать уравнения Беллмана и решить графически следующие задачи на определение оптимальных сроков замены оборудования. Даны: первоначальная стоимость оборудования р₀, его ликвидная стоимость (t), стоимость содержания r(t) в течение года оборудования возраста t лет, п — срок эксплуатации, в конце которого оборудование продается. Критерий оптимальности  суммарные затраты на эксплуатацию оборудования в течение п лет с учетом первоначальной покупки и последующей продажи.

7.10. р₀=8000; (t)=р₀2^t; r(t)=0,1p₀(t+1); п=5.

7.11. n=5. Стоимость нового оборудования зависит от года покупки p_k=5000+500(k1); (k=1, 2, ..., 5); (t)=p_k2^t; r_k(t)=0,1p_k(t+1).

7.12. р₀=8000; п=5, (t) и r(t) заданы таблично:

t	0	1	2	3	4	5
(t)		6000	5000	3000	1000	500
r(t)	600	800	1100	1500	2000	