Реализация на ЭВМ решения задачи оптимального распределения средств на расширение производства

      F_k(x) = (z_k(x_k)+F_k-1(x – x_k-1))

Решение исходной задачи получим при х = Х₀, k= N, т. е. из соотношения

      F_N(X₀) = (z_N(x_N)+F_N-1(X₀ - x_N)).

Найдя F_N(X₀) =  (X₀), определяем . Зная , находим X₀– . Следовательно, найдем и F_N-1(X₀– ). Из выражения

      F_N-1(X₀– ) = (z_N-1(x_N-1) + F_N-2(X₀ – – x_N-1))

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

     Вычислительная  схема решения задачи распределения ресурсов методом динамического программирования состоит в следующем: промежуток 0 ≤ x ≤ X₀ разбивают, например, на n интервалов с шагом ∆ и считают, что функции z_i(x) и F_i(x)определены только в точках х =0, ∆, 2∆, 3∆,..., причем n∆ =X₀. Значения F_N(x) для х, отличных от точек k∆, где k=0, 1, 2,.., n, получают интерполяцией. При i=1 функция F₁(x) определяется равенством F₁(x) = z₁(x). Множество значений F₁(k∆) =z₁(k∆) (к=0,1,2, …, n) записывают в таблицу. Зная значения F₁(k∆), переходят к вычислению значений функции F₂(k∆):

      F₂(x) = (z₂(k∆)+F₁(X₀-k∆)).

В ходе вычислений устанавливаются не только значения F₂(x), 
x = k∆, 0≤k≤X₀ (k =0,1,2, …, n), но и такие значения x₂, при которых достигает максимума выражение z₂(k∆)+ F₁(X₀-k∆).

      Переходим к отысканию функции F₃(x) и т. д. Пройдя весь процесс вычисления функций F_i(x) (i= ), получим

      F_N(X₀) = (z_N(x_N)+F_N-1(X₀-x_N)).

т. е. F_N(X₀) =max Z, . На последнем этапе достигается максимальное значение функции цели F_N(X₀) и оптимальный объем ресурса, выделяемого  
N-му предприятию, т. е. . Затем процесс вычислений просматривается в обратном порядке. Зная находим X₀ – – объем ресурса, подлежащего распределению между оставшимися N–1 предприятиями. Так как раньше найдено значение

      F_N-1(x) = (z_N-1(x_N-1)+F_N-2(X₀-x_N-1))

отсюда  находим F_N-1(X₀- ) и, следовательно, и т.д. Продолжая процесс к началу, определяем . Тем самым будет завершен процесс определения оптимального плана распределения ограниченного ресурса. Практическое применение рассмотренной выше схемы представлено в приложении. Ниже проиллюстрируем рассмотренную задачу числовым примером.

2. Пример задачи распределения ресурсов

     Имеются 6 предприятий, между которыми следует  распределить 200 единиц ограниченного  ресурса. Получаемая предприятиями  прибыль в зависимости от выделенной суммы х представлена в табл. 1. Приняв ∆ = 40, найти оптимальный план распределения

Таблица 1 Прибыль, получаемая предприятиями в зависимости от выделенных средств.

     Пусть N = 1, тогда F₁(x) = z₁(x)

Значения  функции F₁(x) помещены в табл. 2. Предположим теперь, что ресурс X₀ = 200 единиц распределяется между двумя предприятиями. Тогда 
F₂(x) = (z₂(x₂) + F₁(x-x₂)), 0 ≤ x ≤ X₀

Произведем  вычисления значений функций F₂(x) и представим их в табл. 2.

     F₂(40) = (z₂(0) + F₁(40), z₂(40) + F₁(0)) = (0 + 30, 28 + 0) = 30,

     F₂(80) = (z₂(0) + F₁(80), z₂(40) + F₁(40), z₂(80) + F₁(0)) = (0 + 58, 
28 + 30, 62 + 0) = 62,

     F₂(120) = (z₂(0) + F₁(120), z₂(40) + F₁(80), z₂(80) + F₁(40), z₂(120) + 
+ F₁(0)) = (0 + 120, 28 + 58, 62 + 30, 122 + 0) = 122.

     Аналогично  имеем

     F₂(160) = (0 + 150, 28 + 120, 62 + 58, 122 + 30, 146 + 0) = 152,

     F₂(200) = (0 + 180, 28 + 150, 62 + 120, 122 + 58, 146 + 30, 175 + 
+0) = 122.

     Пусть далее, имеющаяся сумма распределяется между тремя предприятиями. Получим  F₃(x) = (z₃(x₃) + F₂(x-x₃)), 0 ≤ x ≤ X₀ . Значения функции F₃(x) представлены в табл 2

     F₃(40) = (z₃(0) + F₂(40), z₃(40) + F₂(0)) = (0 + 30, 31 + 0) = 31,

     F₃(80) = (z₃(0) + F₂(80), z₃(40) + F₂(40), z₃(80) + F₂(0)) = (0 + 62, 
31 + 30, 67 + 0) = 67,

     F₃(120) = (0 + 122, 31 + 62, 67 + 30, 130 + 0) = 130,

     F₃(160) = (0 + 152, 31 + 122, 67 + 62, 130 + 30, 144 + 0) = 160.

     F₃(200) = (0 + 182, 31 + 152, 67 + 122, 130 + 62, 144 + 30, 183 + 
+ 0) = 152

     Затем распределяем ресурсы между четырьмя предприятиями

     F₄(x) = (z₄(x₄) + F₃(x-x₄)), 0 ≤ x ≤ X₀

     F₄(40) = (0 + 31, 25 + 0) = 31,

     F₄(80) = (0 + 67, 25 + 31, 73 + 0) = 73,

     F₄(120) = (0 + 130, 25 + 67, 73 + 31, 125 + 0) = 130,

     F₄(160) = (0 + 160, 25 + 130, 73 + 67, 125 + 31, 152 + 0) = 160.

     F₄(200) = (0 + 192, 25 + 160, 73 + 130, 125 + 67, 152 + 31, 180 + 
+ 0) = 203

Таблица 2

     Аналогично  распределяем ресурсы между пятью, а затем шестью предприятиями  F₅(x) = (z₅(x₅) + F₄(x-x₅)), 0 ≤ x ≤ X₀

     F₅(40) = (0 + 31, 30 + 0) = 31,

     F₅(80) = (0 + 73, 30 + 31, 77 + 0) = 77,

     F₅(120) = (0 + 130, 30 + 73, 77 + 31, 127 + 0) = 130,

     F₅(160) = (0 + 160, 30 + 130, 77 + 73, 127 + 31, 149 + 0) = 160,

     F₅(200) = (0 + 203, 30 + 160, 77 + 130, 127 + 73, 149 + 31, 170 + 
+ 0) = 207

     И наконец F₆(x) = (z₆(x₆) + F₅(x-x₆)), 0 ≤ x ≤ X₀

     F₆(40) = (0 + 31, 35 + 0) = 35,

     F₆(80) = (0 + 77, 35 + 31, 80 + 0) = 80,

     F₆(120) = (0 + 130, 35 + 77, 80 + 31, 132 + 0) = 132,

     F₆(160) = (0 + 160, 35 + 130, 80 + 77, 132 + 31, 155 + 0) = 165.

     F₆(200) = (0 + 207, 35 + 160, 80 + 130, 132 + 77, 155 + 31, 187 + 
+ 0) = 210

     Из таблицы 2 находим оптимальный план распределения. Как видно из табл.2 максимальное значение функции цели составляет 210 единиц, т.е. . Из приведенных расчетов значений F₆(х) находим, что шестому предприятию должно быть выделено = 80 единиц ресурса, остальным пяти 200 – 80 = 120 единиц. Из табл. 2 находим, что оптимальное распределение ресурса 120 единиц ресурса между пятью предприятиями составляет 130 единиц прибыли. При этом третьему предприятию следует выделить = 120 единиц ресурса. Отсюда = 0, =0, = 0, = 0. Оптимальный план распределения

     X^*=, z(X^*)= 210

     Проверка  очевидна z(X^*) = z₁(0) + z₂(0) + z₃(120) + z₄(0) + z₅(0) + 
+z₆(80) = 210

ЗАКЛЮЧЕНИЕ

     В ходе выполнения курсовой работы были рассмотрены теоретические аспекты решения задач динамического программирования. Динамическое программирование — это метод нахождения оптимальных решений в задачах с многошаговой (многоэтапной) структурой Схема динамического программирования состоит в погружении решаемой задачи в параметрическое семейство задач (иногда называемых подзадачами) и последующем решении этих задач, используя принцип оптимальности Беллмана и вытекающее из него рекуррентное уравнение Беллмана. Математически принцип оптимальности может быть представлен следующим образом: