Контрольная работа: Сетевые модели

Районной администрацией принято решение о газификации одного из сёл района, имеющего 25 жилых домов. Разработать такой план газификации села, чтобы общая длинна трубопроводов была наименьшей. Проанализировать решение задачи на единственность. В случае не единственности решения найти все решения и доказать, что других нет.

Выберем наикротчайшие пути между узлами. Из расчёта моего варианта, по условию задачи, газификацию в селе нужно начинать с дома под номером 20.

А24=40 переходим к дому (12). А23=90 переходим к дому (18) А27=60 переходим к дому (17). А28=40 переходим к дому (13) А34=70 переходим к дому (22). А38=70 переходим к дому (21) А39=90 переходим к дому (25). А20=100 переходим к дому (19) А29=160 переходим к дому (16). А45=110 переходим к дому (14) А14=30 переходим к дому (9). А16=30 переходим к дому (10) А13=100 переходим к дому (8). А43=100 переходим к дому (7) А15=30 переходим к дому (15). А12=80 переходим к дому (2) А2=80 переходим к дому (3). А5=120 переходим к дому (4) А7=60 переходим к дому (5). А4=100 переходим к дому (1) А19=180 переходим к дому (11). А42=210 переходим к дому (24) А32=410 переходим к дому (23). А11=220 переходим к дому (6)

Находим общую протяжённость трубопровода:

40+90+60+40+70+70+90+100+160+110+30+30+100+100+30+80+80+120+60+100+180+210+410+220 = 2610 метров.

На рисунке показан самый экономичный вариант газификации села начиная с дома №20.

Задание 2

Транспортному предприятию требуется перевезти груз из одно пункта в другой. Нужно определить маршрут доставки груза, которому соответствуют наименьшие затраты. Из расчёта моего варианта, по условию задачи, доставить груз нужно из пункта 20 в пункт 1. Ограничим транспортную сеть до пунктов, стоимость перевозки которых к пункту назначения, наиболее дешевая. В результате получим сеть:

Введем обозначения:

а _k – стоимость перевозки единицы груза между отдельными пунктами;

U_j – наиболее дешевая перевозка между узлами i и j , U₁₈ = 0.

Формула для вычисления U_j :

Из формулы следует, что наиболее дешевую перевозку U_j до узла j можно вычислить лишь после того, как определена наиболее дешевая перевозка до каждого предыдущего узла i , соединенного дугой с узлом j . Процедура завершается, когда получено U_i последнего звена.

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

1.U₂₀ = 0;

2. U₁₂ = U₂₀ +а_к = 0 + 40 = 40;

3. U₁₉ = U₂₀ + а_к = 0 + 170 = 170;

4. U₁₂ = min {U₂₀ + a₂₄ ; U₁₉ + a₂₀ } = min {40; 270} = 40;

5. U₁₉ = min {U₂₀ + a₂₅ ; U₁₂ + a₂₀ } = min {170; 140} = 140;

6. U₁₀ = U₁₂ +а₂₁ = 40 + 440 = 480;

7. U₁₁ = U₁₉ + а₁₉ = 140 + 180 = 320;

8. U₁₁ = min {U₁₉ + a₁₉ ; U₁₀ + a₁₈ } = min {320; 830} = 320;

9. U₁₀ = min {U₁₂ + a₂₁ ; U₁₁ + a₁₈ } = min {480; 670} = 480;

10. U₅ = U₁₀ +а₉ = 480 + 150 = 630;

11. U₄ = U₁₁ + а₁₇ = 320 + 530 = 850;

12. U₄ = min {U₁₁ + a₁₇ ; U₅ + a₇ } = min {850; 690} = 690;

13. U₅ = min {U₁₀ + a₉ ; U₄ + a₇ } = min {630; 750} = 630;

14. U₃ = min {U₅ + a₆ ; U₄ + a₅ } = min {990; 810} = 810;

--> ЧИТАТЬ ПОЛНОСТЬЮ <--