Решение задачи динамического программирования

Решение задачи динамического программирования. Распределение ресурсов предприятиям. Данные возьмем из задачи нелинейного программирования: количество составов и прибыль на 1 состав для каждого предприятия: Предприятие 1. Количество составов Прибыль на 1 состав 6,17 676,8 4,31 – 6,17 388,8 3,08 – 4,31 244,8 1,85 – 3,08 172,8 до 1,85 100,8 Предприятие 2. Количество составов Прибыль на 1 состав 6,18 459,25 4,33 – 6,18 305,25 3,09 – 4,33 151,25 1,85 – 3,09 74,25 до 1,85 -78,75 Предприятие 3. Количество составов Прибыль на 1 состав 5,66 294,68 3,96 – 5,66 40,28 2,83 – 3,96 -214,12 1,7 – 2,83 -298,92 до 1,7 -458,52 Количество составов, выделенных всем трем предприятиям (N), равно 14. Рассчитаем эффективность использования средств предприятиями.

Для этого прибыль на один состав умножим на количество составов, при которых достигается эта прибыль на каждом из предприятий. , где n – количество составов, Pn – прибыль при этом количестве составов.

Количество составов Предприятие 1 Предприятие 2 Предприятие 3 1 100,8 -78,15 -458,52 2 345,6 148,5 -597,94 3 518,4 222,75 -642,36 4 979,2 605 161,12 5 1944 1526,25 201,40 6 2332,8 1831,5 1768,08 Рассчитаем - максимально возможное количество составов для предприятий 1 и 2. составов. Теперь рассчитаем минимально возможное количество составов для предприятий 1 и 2, исходя из того, что максимально возможное количество составов для предприятия 3 равно = 6 составов, тогда составов.

Составим таблицу выделения средств двум предприятиям (1 и 2). Здесь x - общее количество ресурсов (составов) для двух предприятий; x = x1 + x2; 0 x1 6 – допустимое количество составов для предприятия 1; 0 x2 6 – допустимое количество составов для предприятия 2. Отсюда видно, что 0 x, однако количество составов для предприятия 3 не может превышать 6, следовательно x, следовательно x; 8x12. q1, q2 – эффективность использования средств предприятиями 1 и 2 соответственно взятая из предыдущей таблицы.

W2 = q1 + q2 – суммарная эффективность обоих предприятий. Наибольшую суммарную эффективность для каждого значения x будем подчеркивать. x x1 X2 Эффективность q1 q2 W2 8 2 6 345,6 1831,5 2177,1 3 5 518,4 1526,25 2044,65 4 4 979,2 605 1584,2 5 3 1944 222,75 2166,75 6 2 2332,8 148,5 2481,3 9 3 6 518,4 1831,5 2349,9 4 5 979,2 1526,25 2505,45 5 4 1944 605 2549 6 3 2332,8 222,75 2555,55 10 4 6 979,2 1831,5 2810,7 5 5 1944 1526,25 3470,25 6 4 2332,8 605 2937,8 11 5 6 1944 1831,5 3775,5 6 5 2332,8 1526,25 3859,05 12 6 6 2332,8 1831,5 4164,3 Теперь составим таблицу выделения средств всем трем предприятиям.

Так как N – общее количество составов равно 14, а максимально возможное количество составов для предприятий 1 и 2 =12, то всем трем предприятиям может быть выделено 13 или 14 составов.

W3 – суммарная эффективность всех трех предприятий. Количество Составов x3 x Эффективность использования ресурсов q3 W2 W3 13 1 12 -458,52 4164,3 3705,78 2 11 -597,94 3859,05 3261,11 3 10 -642,36 3470,25 2827,89 4 9 161,12 2555,55 2716,67 5 8 201,4 2481,3 2682,7 14 2 12 -597,94 4161,3 3563,36 3 11 -642,36 3859,05 3216,69 4 10 161,12 3470,25 3631,12 5 9 201,4 2555,55 2756,95 6 8 1768,08 2481,3 4249,38 W3 максимальное равно 4249,38, следовательно Z = 4249,38. x3 = 6; x2 = 2; x3 = 6. Вывод: В результате решения задачи динамического программирования я получил, что максимальное значение целевой функции Z = = 4249,38 получается при количестве составов, выделенных 3 предприятиям N = 14, и количестве составов выделенных предприятию 3 x3 = 6. При этом количество составов для предприятий 1 и 2 равно 8. Максимальная эффективности использования 8 составов предприятиями 1 и 2 достигается при выделении предприятию 1 - 6 составов, а предприятию 2 – 2 состава, и она равна 2481,3. Следовательно x1 = 6, x2 = 2, x3 = 6, Z = 4249,38. Плановые задания предприятиям: , где P – плановое задание тыс. тонн, q – производительность состава, x – количество составов, i – номер предприятия.

Для предприятия 1: тыс. тонн; тыс. тонн; тыс. тонн.