Задание 1
Районной администрацией принято решение о газификации одного из сёл района, имеющего 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 – стоимость перевозки единицы груза между отдельными пунктами;
Uj – наиболее дешевая перевозка между узлами i и j, U18 = 0.
Формула для вычисления Uj:
Из формулы следует, что наиболее дешевую перевозку Uj до узла j можно вычислить лишь после того, как определена наиболее дешевая перевозка до каждого предыдущего узла i, соединенного дугой с узлом j. Процедура завершается, когда получено Ui последнего звена.
Начнем определять наименьшие затраты с пунктов, стоимость перевозки к которым, от исходного пункта, наиболее дешевая.
1.U20 = 0;
2. U12 = U20 +ак = 0 + 40 = 40;
3. U19 = U20 + ак = 0 + 170 = 170;
4. U12 = min {U20 + a24; U19 + a20} = min {40; 270} = 40;
5. U19 = min {U20 + a25; U12 + a20} = min {170; 140} = 140;
6. U10 = U12 +а21 = 40 + 440 = 480;
7. U11 = U19 + а19 = 140 + 180 = 320;
8. U11 = min {U19 + a19; U10 + a18} = min {320; 830} = 320;
9. U10 = min {U12 + a21; U11 + a18} = min {480; 670} = 480;
10. U5 = U10 +а9 = 480 + 150 = 630;
11. U4 = U11 + а17 = 320 + 530 = 850;
12. U4 = min {U11 + a17; U5 + a7} = min {850; 690} = 690;
13. U5 = min {U10 + a9; U4 + a7} = min {630; 750} = 630;
14. U3 = min {U5 + a6; U4 + a5} = min {990; 810} = 810;
15. U1 = min {U4 + a4; U3 + a3} = min {790; 1040} = 790.
Таким образом из расчетов видно, что минимальные затраты перевозки груза между узлами 20 и 1 равны 790, а соответствующий маршрут c наименьшими затратами будет:
20 – 12 – 10 – 5 – 4 – 1 + 40+440+150+60+100 = 790
Задание 3
Предприятие решило для улучшения финансового состояния наладить выпуск конкурентно способной продукции. Ожидается, что производительность после новой линии составит 20 т продукции в смену. Прибыль от реализации 1 т продукции составит 0,5 тыс. руб. в смену. ............
