Зміст
Введення
1. Економічна сутність завдання
2. Вихідні дані
3. Метод динамічного програмування
4. Метод повного перебору варіантів
5. Інтуїтивні розподілу
5.1. Рівномірний розподіл
5.2. Метод найбільшої планової ефективності
5.3. Самостійне інтуїтивне розподіл
Висновок
Література
Введення
Мета роботи - вивчення економічної сутності та математичної формалізації задачі визначення оптимального варіанту розподілу заданої суми капітальних вкладень між кількома підприємствами галузі, що випускають взаємозамінну продукцію.
1. Економічна сутність завдання
У галузі є М підприємств, що випускають однотипну взаємозамінну продукцію, попит на яку поки не задовольняється повністю. З метою збільшення випуску даної продукції на модернізацію цих підприємств виділена сума капіталовкладень у розмірі Х тис. руб. Кожному підприємству з номером m = 1, 2, ..., M може бути виділена сума X m> = 0, при цьому сума капіталовкладень розподіляється повністю, тобто
(1)
Оптимізація розподілу капіталовкладень проводиться за критерієм максимуму сумарного приросту випуску продукції всіма підприємствами
(2)
Тут g m (x m) - приріст випуску продукції на підприємстві з номером m за умови, що йому виділена сума капіталовкладень x m.
2. Вихідні дані
Вихідними даними для вирішення завдання служать виконані на кожному підприємстві розрахунки з обгрунтування залежностей приросту випуску від розміру капіталовкладень g m (x m). Як правило, ці залежності не вдається отримати в аналітичній формі (у вигляді безперервних і аналітичних функцій) і вони представляються таблично, значеннями функцій при заданих дискретних значеннях аргументу.
Для спрощення подальших обчислень будемо вважати, що величини x m кратні деякої дискретний h = X / N де N - кількість дискрет в распределяемой сумі X. Дискрета h задається заздалегідь, виходячи з розумного компромісу між бажаною точністю і трудомісткістю розрахунків. Зменшення величини дискрети h, взагалі кажучи, збільшує точність, але при цьому зростає трудомісткість підготовки вихідної інформації та її подальшої обробки.
З урахуванням прийнятого допущення величина капіталовкладень x m міняємося дискретно, приймаючи значення x m = nh, n = 0, 1, ..., N. Кожне підприємство розраховує і представляє в міністерство (N +1) М значень, які зручно звести в табл.1 .
При побудові табл.1.1 прийнято М = 5; Х = 300 тис. крб.; N = 6; h = 50 тис. руб.
Таблиця 1 - Приріст випуску продукції при заданій величині капіталовкладень, тис. руб.
Величина капіталовкладень тис. руб. | Порядковий номер підприємства | ||||
1 | 2 | 3 | 4 | 5 | |
1 | 2 | 3 | 4 | 5 | 6 |
0 | 0 | 0 | 0 | 0 | 0 |
50 | 30 | 20 | 20 | 40 | 30 |
100 | 83 | 75 | 61 | 62 | 72 |
1 | 2 | 3 | 4 | 5 | 6 |
150 | 98 | 100 | 112 | 97 | 108 |
200 | 127 | 150 | 140 | 134 | 122 |
250 | 158 | 165 | 152 | 160 | 148 |
300 | 195 | 20 | 180 | 185 | 190 |
3. Метод динамічного програмування
Ідея методу динамічного програмування полягає в тому, що виділена сума Х розподіляється не між усіма М підприємствами (інакше виходить повний перебір), а між двома "підприємствами": останнім підприємством (що має номер М) і групою з (М -1) - го попереднього підприємства, для якого оптимальний розподіл між ними будь часткової суми вже відомо. Це відповідає рішенню основного функціонального рівняння динамічного програмування М-го, останнього кроку
(3)
Тут f M (X) - максимальний сумарний приріст продукції, що отримується від М підприємств при оптимальному розподілі суми Х між M-тим і групою з (М -1) - го перших підприємств, за умови, що виділяється їм часткова сума (Х-Х М) розподіляється оптимально;
f M -1 (X-Х М) - максимальний сумарний приріст продукції, що отримується від (М -1) - го перших підприємств при оптимальному розподілі між ними часткової суми (Х-Х М), що залишилася, від М-го підприємства.
Розв'язати рівняння (3) неможливо, так як функція f M -1 (X-Х М) невідома. Однак її можна виразити за допомогою основного функціонального рівняння для (М-1) - го кроку через функцію максимального сумарного приросту продукції, що отримується при оптимальному розподілі часткових сум у групі з (М-2) - х перших підприємств
(4)
Знову невідома функція f M -2 (nh-Х М-1) однак, використовуючи основне f M -3 (nh-Х М-2) функціональне рівняння, її можна визначити аналогічно через функцію і т.д. Ця процедура рекурентних підстановок невідомих функцій максимального сумарного приросту продукції закінчується точно через М кроків. Дійсно, на останньому кроці підстановок (його номер m = 1) отримуємо основне функціональне рівняння динамічного програмування у вигляді
(5)
Функція f 0 (nh-Х 1) формально є максимальний приріст продукції при оптимальному розподілі часткової суми (nh-Х 1) у групі, що з "0" підприємств. Природно, такий групі, в якій немає жодного підприємства, ніяких коштів не виділяється тому
f 0 (nh-Х 1) = 0 (6)
Звідси випливає, що на першому кроці основне функціональне рівняння має наступне рішення:
(7)
Це означає, що на першому кроці, коли розглядається тільки одне перше підприємство, будь-яка часткова сума nh виділяється йому цілком, так як її нікому, крім нього, розподіляти. Таким чином, оптимальне управління на першій кроці
X 1 * (nh) = nh (8)
Уявімо знайдене рішення основного функціонального рівняння на першому кроці у вигляді табл.2.
Таблиця 2 - Визначення оптимальних управлінь і максимальних приріс продукції на першому кроці
Часткова розподіляється сума | Сума, що виділяється першому підприємству | Оптимальне управління | Максимальний приріст продукції | ||||||
0 | 50 | 100 | 150 | 200 | 250 | 300 | |||
0 | 0 | 0 | 0 | ||||||
50 | 30 | 50 | 30 | ||||||
100 | 83 | 100 | 83 | ||||||
150 | - | 98 | 150 | 98 | |||||
200 | 127 | 200 | 127 | ||||||
250 | 158 | 250 | 158 | ||||||
300 | 195 | 300 | 195 | ||||||
У табл.2 заповнена числами тільки головна діагональ. Ці числа беруться з табл.1 вихідних даних для першого підприємства. Порожні клітини лівіше головної діагоналі показують, що на 1-му кроці вся часткова сума nh цілком віддається першому підприємству, так як на атом кроці інших підприємств немає. Порожні клітини праворуч від головної діагоналі показують, що не може розподілятися часткова сума, більша наявної.
КРОК 1 тривіальний, проте важливий в тому відношенні, що дозволяє почати процес рекурентного обчислення на наступних кроках за основним функціональним рівнянню
f m (nh) = max {g m (x m) + f m -1 (nh - x m)}, n = 1, 2, ..., N;
0 <= xm <= nh, m = 1, 2, ..., M.
КРОК 2. Розподіл часткових сум між другим підприємством і групою з "одного першого підприємства". Для другого кроку основне функціональне рівняння має вигляд
F 2 (nh) = max {g 2 (x 2) + f 1 (nh - x 2)},
0 <= x 2 <= nh; 1 <= n <= N
Його рішення представлене в табл.3
Таблиця 3 - Визначення оптимальних управлінь і максимальних приростів продукції на 2-му кроці.
Часткова розподіляється сума | Сума, що виділяється другому підприємству | Оптимальне управління | Максимальний приріст продукції | ||||||
0 | 50 | 100 | 150 | 200 | 250 | 300 | |||
0 | 0 +0 0 | 0 | 0 | ||||||
50 | 0 +30 30 | 20 +0 20 | 0 | 30 | |||||
100 | 0 +83 83 | 20 +30 | |||||||
50