Сетевые модели (работа 1)

Задание 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> – стоимость перевозки единицы груза между отдельными пунктами;

U_>j> – наиболее дешевая перевозка между узлами i и j, U_>18> = 0.

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

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

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

1.U_>20>= 0;

2. U_>12>= U_>20>+а_>к> = 0 + 40 = 40;

3. U_>19> = U_>20> + а_>к> = 0 + 170 = 170;

4. U_>12> = min {U_>20> + a_>24>; U_>19> + a_>20>} = min {40; 270} = 40;

5. U_>19> = min {U_>20> + a_>25>; U_>12> + a_>20>} = min {170; 140} = 140;

6. U_>10>= U_>12>+а_>21> = 40 + 440 = 480;

7. U_>11> = U_>19> + а_>19> = 140 + 180 = 320;

8. U_>11> = min {U_>19> + a_>19>; U_>10> + a_>18>} = min {320; 830} = 320;

9. U_>10> = min {U_>12> + a_>21>; U_>11> + a_>18>} = min {480; 670} = 480;

10. U_>5>= U_>10>+а_>9> = 480 + 150 = 630;

11. U_>4> = U_>11> + а_>17> = 320 + 530 = 850;

12. U_>4> = min {U_>11> + a_>17>; U_>5> + a_>7>} = min {850; 690} = 690;

13. U_>5> = min {U_>10> + a_>9>; U_>4> + a_>7>} = min {630; 750} = 630;

14. U_>3> = min {U_>5> + a_>6>; U_>4> + a_>5>} = min {990; 810} = 810;

15. U_>1> = min {U_>4> + a_>4>; U_>3> + a_>3>} = 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 тыс. руб. в смену. Деньги на покупку и переоборудование участка в размере 2 млн. руб. взяты в банке под 20% годовых из расчёта 1,5 млн. руб. на закупку оборудования и 0,5 млн. руб. на работы по демонтажу старого оборудования и установку нового оборудования. Определить, через какое время может быть возвращён кредит в банк. Затраты на проведение работ в нормальном и максимальном режимах указаны в таблице.

Работа	Нормальный режим	Максимальный режим
1 2 3 4 5 6 7	40 50 50 70 80 40 30	20 30 30 70 70 20 20	35 35 40 50 65 35 17	30 50 40 100 80 25 25

Работа

Нормальный режим

Максимальный режим

Продолжительность дн.

Затраты

Продолжительность дн.

Затраты

100

Составим график проведения работ по пуску новой линии.

На переоборудование цеха необходимо: 40+50+50+70+80+40+30 = 360 дней.

2. График можно улучшить, выполняя некоторые работы параллельно. Получим график:

На этом графике обозначены работы:

(0;1) - подготовка технического задания;

(1;2) - заказ и поставка нового оборудования;

(1;3) – заказ и поставка нового электрооборудования;

(2;4) – установка нового оборудования;

(3;4) – установка нового электрооборудования;

(1;4) – переобучение персонала;

(4;5) – сдача в эксплуатацию новой линии.

По графику, путь (0;1), (1;2), (2;4), (4;5) имеет продолжительность: 40+50+70+30 = 190 дней.

По графику, путь (0;1), (1;3), (3;4), (4;5) имеет продолжительность: 40+50+80+30 = 200 дней.

По графику, путь (0;1), (1;4), (4;5) имеет продолжительность: 40+40+30 = 110 дней.

Критическим путём графика является путь, на котором находятся работы: (0;1), (1;3), (3;4), (4;5).

График улучшается на 360 – 200 = 160 дней.

Определим, через какое время после начала выпуска продукции возвращаем кредит в банк.

Через 200 дней после начала работ предприятие истратит 1500 т. руб. на приобретение оборудования и 265 т. руб. на его установку и сдачу в эксплуатацию.

В наличии у предприятия останется: 2000-1500-260 = 240 т. руб. от кредита.

Построим график изменения кредита в зависимости от времени получения прибыли предприятия от выпуска продукции.

С (200;240) D (300;1240) А (0;2000) В (360;2400).

Для построения графика изменения кредита в зависимости от времени, составим уравнение. Через 360 дней после выдачи банком кредита под 20% годовых, долг предприятия составит 2400 т. руб. Поэтому известны две точки этой прямой: А (0;2000) В (360;2400).

Согласно уравнению прямой, проходящей через две точки:

(у – у_>А>) / (у_>В> – у_>А)> = (х – х_>А)> / (х_>В>– х_>А>),

(у – 2000) / (2400 – 2000) = (х – 0) / (360 – 0).

Решая уравнение получим:

(у – 2000) / 400 = х) / 360;

400х = 360 (у – 2000);

400х – 360у + 720000 = 0/ 40;

10х – 9у + 18000 = 0.

Найдём уравнение прибыли предприятия. Известно, что через 200 дней после начала работ у предприятия осталось от кредита 240 т. руб. Через 100 дней после начала выпуска продукции предприятие получит прибыль: 0,5 т.р. *20 тонн *100 дней = 1000 т. руб. У предприятия будет в наличии: 1000+240 = 1240 т. руб.

Таким образом, для нахождения уравнения прибыли имеем две точки: С (200;240) D (300;1240).

(у – у_>С>) / (у_>D> – у_>C>_>)> = (х – х_>C>_>)> / (х_>D>_>>– х_>C>);

(у – 240) / (1240 – 240_>)> = (х – 200_>)> / (300_>>– 200);

(у – 240) / 1000 = (х – 200_>)> / 100;

1000 (х – 200_>)> = 100 (у – 240_>)>;

1000х – 200000 = 100у – 24000;

1000х – 100у – 176000 = 0 /: 100;

10х – у – 1760 = 0.

Определим время, когда кредит может быть возвращён в банк. Для этого составим систему уравнений:

10х – 9у + 18000 = 0

10х – у – 1760 = 0

- 8у + 19760 = 0 10х – 2470 – 1760 = 0

-8у = 19760 10х = 4230

у = 2470 т.р. х = 423 день.

3. График выполнения работ может быть сжат за счёт выполнения некоторых операций в максимально интенсивном режиме. Учитывая наклоны кривой, производим сжатие операций (0;1), (2;4), (3;4), (4;5), получим сетевой график.

Новый график имеет пути:

(0;1), (1;2), (2;4), (4;5) – 152 дня;

(0;1), (1;3), (3;4), (4;5) – 152 дня;

(0;1), (1;4), (4;5) – 92 дня.

Таким образом, критический путь сокращён с 200 до 152 дней, а это значит, что предприятие начнёт производить продукцию через 152 дня после начала работ. Определим, сколько предприятию придётся заплатить за уменьшение критического пути:

(0,1) 30 – 20 = 10 т.р. (3,4) 80 – 70 = 10 т.р.

(1,2) 50 – 30 = 20 т.р. (4,5) 25 – 20 = 5 т.р.

(2,4) 100 – 70 = 30 т.р.

Таким образом, сжатие работ обойдётся предприятию в: 10 + 20 + 30 + 10 + 5 = 75 т. руб.

График изменения кредита в зависимости от времени определяет уравнение: 10х – 9у + 18000 = 0.

Найдём уравнение прибыли. Через 152 дня после начала работ у предприятия осталось от кредита: 2000 – 1500 – 260 – 75 = 155 т. руб.

Через 100 дней после начала выпуска продукции предприятие получит прибыль: 20 т. руб. * 0,5 т. руб. * 100 дн. = 1000 тыс. руб., и у него будет в наличии 1000 + 155 = 1155 т. руб.

Таким образом, для нахождения уравнения прибыли предприятия имеем две точки: С (152;155) D (252;1155).

Согласно уравнению прямой, проходящей через 2 точки, получим:

(у – у_>С>) / (у_>D> – у_>C>_>)> = (х – х_>C>_>)> / (х_>D>_>>– х_>C>),

(у – 155) / (1155 – 155_>)> = (х – 152_>)> / (252_>>– 152);

(у – 155) / 1000 = (х – 152_>)> / 100;

1000 (х – 152) = 100 (у – 155_>)>;

1000х – 152000 = 100у – 15500 /: 100.

Составляем систему уравнений:

10х – у – 1365 = 0 у = 10х – 1365;

10х – 9у + 18000 = 0 10х - 9 (10х – 1365) + 18000 = 0;

10х – 90х + 12285 + 18000 = 0.

-80х + 30285 = 0;

-80х = 30285 у = 3780-1365;

х = 378 дней у = 2415 т. руб.

Таким образом, через 378 дней предприятие может вернуть кредит в банк. По сравнению с предыдущим случаем предприятие вернёт в банк деньги раньше на 423–378 = 45 дней. При нормальном режиме работ критический путь составляет 200 дней, стоимость работ 260 т. руб. При максимальном режиме критический путь уменьшится до 152 дней, минимальная стоимость работ составит: 260 + 75 = 335 т. руб.