Завдання 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 |
Складемо графік проведення робіт з пуску нової лінії.
На переобладнання цеху необхідно: 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У + 18 000 = 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У - 176 000 = 0 /: 100;
10х - у - 1760 = 0.
Визначимо час, коли кредит може бути повернений в банк. Для цього складемо систему рівнянь:
10х - 9У + 18 000 = 0
10х - у - 1760 = 0
- 8у + 19 760 = 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У + 18 000 = 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У + 18 000 = 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 т. крб.