Использование метода динамического программирования для решения экономических задач

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования

«Брестский государственный университет имени А. С. Пушкина»

Математический факультет

Кафедра математического моделирования

Курсовая работа

ИСПОЛЬЗОВАНИЕ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ

ЭКОНОМИЧЕСКИХ ЗАДАЧ

Брест 2008 г.

СОДЕРЖАНИЕ ВВЕДЕНИЕ

1. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

1.1 Многошаговые процессы в динамических задачах

1.2 Принцип оптимальности и рекуррентные соотношения

1.3 Вычислительная схема

1.4 Планирование производственной программы

1.5 Оптимальное распределение средств на расширение производство

2. РЕШЕНИЕ ЭКОНОМИЧЕСКИХ ЗАДАЧ МЕТОДОМ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

2.1 Задачи выбора кратчайшего пути

2.2 Задачи планирования производственной программы

2.3 Задачи оптимального распределения средств на расширение производства ЗАКЛЮЧЕНИЕ СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

ВВЕДЕНИЕ

Динамическое программирование (иначе — динамическое планирование) — это метод нахождения оптимальных решений в задачах с многошаговой (многоэтапной) структурой. Многие экономические процессы расчленяются на шаги естественным образом. Это все процессы планирования и управления, развиваемые во времени. Естественным шагом в них может быть год, квартал, месяц, декада, неделя, день и т. д. Однако метод динамического программирования может использоваться при решении задач, где время вообще не фигурирует; разделение на шаги в таких задачах вводится искусственно. Поэтому «динамика» задач динамического программирования заключается в методе решения.

В экономической практике встречается несколько типов задач, которые по постановке или способу решения относятся к задачам динамического программирования. Это задачи оптимального перспективного и текущего планирования во времени. Их решают либо путем составления комплекса взаимосвязанных статических моделей для каждого периода, либо путем составления единой динамической задачи оптимального программирования с применением многошаговой процедуры принятия решений.

Цель работы:

1) Изучить метод динамического программирования.

2) Применить метод динамического программирования к решению экономических задач.

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

1. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

1.1 Многошаговые процессы в динамических задачах Динамическое программирование (планирование) представляет собой математический метод для нахождения оптимальных решений многошаговых (многоэтапных) задач. Некоторые из таких задач естественным образом распадаются на отдельные шаги (этапы), но имеются задачи, в которых разбиение приходится вводить искусственно, для того чтобы можно было решить методом динамического программирования. К таким задачам можно отнести задачу выбора кратчайшего пути.

Пусть на некоторый период времени Т, состоящий из m лет, планируется деятельность группы промышленных предприятий. В начале планируемого периода на развитие предприятий выделяются основные средства Q₀, которые необходимо распределить между предприятиями. В процессе функционирования предприятий выделенные им средства частично расходуются. Однако каждое из этих предприятий за определенный период времени (хозяйственный год) получает прибыль, зависящую от объема вложенных средств. В начале каждого года имеющиеся средства могут перераспределяться между предприятиями. Требуется определить, сколько средств надо выделить каждому предприятию в начале каждого года, чтобы суммарный доход от всей группы предприятий за весь период времени Т был максимальным.

Процесс решения такой задачи является многошаговым. Шагом управления (планирования) здесь будет хозяйственный год. Управление процессом состоит в распределении (перераспределении) средств в начале каждого хозяйственного года.

1.2 Принцип оптимальности и рекуррентные соотношения Метод динамического программирования позволяет одну задачу со многими переменными заменить рядом последовательно решаемых задач с меньшим числом переменных. Процесс решения задачи разбивается на шаги. При этом нумерация шагов, как правило, осуществляется от конца к началу.

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

Основным принципом, на котором базируются оптимизация многошагового процесса, а также особенности вычислительного метода динамического программирования, является принцип оптимальности

Р. Беллмана.

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

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

Принцип оптимальности имеет конструктивный характер и непосредственно указывает процедуру нахождения оптимального решения. Математически он записывается выражением вида

f_{n — l}(S_l) = (R_{l + 1}(S_l, U_{l + 1}) + f_{n — (l + 1)}(S_{l + 1})) (1.1)

(l =)

где — оптимальное значение эффекта, достигаемого за n — l шагов; n количество шагов (этапов); S_l = (s_l⁽¹⁾;…;s_l^(m)) — состояние системы на lм шаге; U_l = (u_l⁽¹⁾;…;u_l^(m)) — решение (управление), выбранное на l-м шаге; R_l — непосредственный эффект, достигаемый на l-м шаге.

Optimum в выражении (1.1) означает максимум или минимум в зависимости от условия задачи.

Все вычисления, дающие возможность найти оптимальное значение эффекта, достигаемого за п шагов, f_n(S₀), проводятся по формуле (1.1), которая носит название основного функционального уравнения Беллмана или рекуррентного соотношения. Действительно, при вычислении очередного значения функции f_n-l используются значение функции f_n-_(l+1), полученного на предыдущем шаге, и непосредственное значение эффекта R_l+1(S_l, U_l+1), достигаемого в результате выбора решения U_l+1 при заданном состоянии системы S_l. Процесс вычисления значений функции f_n-l осуществляется при естественном начальном условии f₀(S_n)= 0, которое означает, что за пределами конечного состояния системы эффект равен нулю.

1.3 Вычислительная схема Оптимальное решение задачи методом динамического программирования находится на основе функционального уравнения (1.1). Чтобы определить его, необходимо:

1. записать функциональное уравнение для последнего состояния процесса (ему соответствует l = n — 1):

f₁(S_n — ₁) = (R_n(S_n — ₁, U_n) + f₀(S_n));

2. найти R_n(S_n — ₁, U_n) из дискретного набора его значений при некоторых фиксированных S_n — ₁ и U_n из соответствующих допустимых областей (так как

3.

f₀(S_n) = 0, то f₁(S_n — ₁) = R_n(S_n — ₁, U_n))

В результате после первого шага известно решение U_n и соответствующее значение функции f₁(S_n — ₁);

4. уменьшить значение l на единицу и записать соответствующее функциональное уравнение. При l = n — k (k =) оно имеет вид

f_k(S_n — _k) = (R_n-_k+1(S_n — _k, U_n-_k+1) + f_k-₁(S_n-_k+1)); (1.2)

5. найти условно-оптимальное решение на основе выражения (1.2);

6. проверить, чему равно значение l. Если l = 0, расчет условно-оптимальных решений закончен, при этом найдено оптимальное решение задачи для первого состояния процесса. Если l 0, перейти к выполнению пункта 3;

7. вычислить оптимальное решение задачи для каждого последующего шага процесса, двигаясь от конца расчетов к началу.

1.4 Планирование производственной программы Предприятие изготавливает машины, спрос на которые в каждом из месяцев равен D_t (t =) единиц. Запас машин на складе предприятия на начало планируемого периода i₀ единиц. Пусть общие затраты c_t(x_t, i_t) состоят из затрат c (x_t) на производство машин и затрат hi_t на их содержание до отправки потребителю, т. е.

c_t(x_t, i_t) = c (x_t) + hi_t

В свою очередь затраты c (x_t) на производство машин складываются из условно-постоянных k и пропорциональных lx_t (l единиц на каждую единицу продукции). Таким образом, для любого месяц

c (x_t) = k + lx_t..

Затраты на хранение единицы продукции равны h, поэтому затраты на содержание запасов численно равны уровню запасов на конец месяца, умноженному на h. Складские площади предприятия ограничены, и хранить можно не более M единиц продукции. Производственные мощности также ограничены, и в каждом месяце можно изготовить не более B единиц продукции. Требуется определить производственную программу изготовления машин x_t, удовлетворяющую спрос в каждом из месяцев планируемого периода D_t (t =) и обеспечивающую минимальные затраты на производство продукции и содержание запасов. Запас продукции на складе в конце планируемого периода должен быть равен нулю.

Для решения задачи методом динамического программирования и записи рекуррентного соотношения будем использовать следующие обозначения: n (n =) — номер планируемого отрезка времени (соответствует обратной нумерации месяцев); j — уровень запаса на конец отрезка; d_n — спрос на продукцию на n-м отрезке (d₁ = D_T, d₂ = D_T-1, …, d_n = D₁); c_n(x, j) — затраты, связанные с выпуском х единиц продукции на n-м отрезке и с содержанием запасов, объем которых на конец n-го отрезка равен j единиц; f_n(i) — значение функции, равное затратам на производство и хранение продукции за n последних месяцев при условии, что уровень запасов на начало n-го месяца составляет i единиц; x_n(i) — производство продукции на n-м отрезке, если уровень запасов на начало отрезка равен i единиц.

Число шагов решения задачи совпадает с числом месяцев (количеством плановых отрезков времени п). Так как уровень запасов на конец планового периода, должен равен нулю, то для п = 0

f₀(0) = 0 (1.3)

Перейдем к рассмотрению первого отрезка (n = 1). Запас i₁ на начало этого отрезка неизвестен. Однако ясно, что он может быть равен любому неотрицательному целому числу, не превышающему вместимости склада и спроса в рассматриваемом отрезке, т. е. не должен превышать min (d₁, M). Для полного удовлетворения спроса на последнем отрезке объем должен быть равен d₁ — i₁. Следовательно,

f₁(i) = c₁(x₁, j₁) = c₁(d₁ — i, j₁) = c₁(d₁ — i, 0), (1.4)

где i = 0, 1, …, min (d₁, M).

Перейдем ко второму шагу (n = 2). Уровень запасов на начало второго отрезка равен i. При этом величина i может принимать любые неотрицательные целочисленные значения, не превышающие min (d₁ + d₂, M). Целочисленные значения х (обьем выпуска) во втором отрезке при заданном i должен быть не меньше, чем d₂ — i (спрос на данном отрезке должен быть удовлетворен), но не больше min (d₁ + d₂ — i, B), так как запас на конец планового периода равен нулю и производство продукции в любом отрезке не превышает В. Минимальные суммарные затраты на производство и хранение продукции за два последних месяца

f₂(i) = min (c₂(x, i + x — d₂) + f₁(i + x — d₂)), (1.5)

где i = 0, l, …, min (d₁ + d₂, M);

d₂ — i x min (d₁ + d₂ — i, B).

Аналогично можно записать рекуррентное соотношение для n = 3. Общее рекуррентное соотношение имеет вид

f_n(i) = min (c_n(x, i + x — d_n) + f_n-₁(i + x — d_n)) (n =) (1.6)

где i = 0, 1, …, min (d₁ + d₂ + … + d_n, M);

d_n — i x min (d₁ + d₂ + … + d_n — i, B).

В выражении (1.6) величина i + x — d_n = j_n характеризует уровень запасов на конец отрезка п.

Заметим, что, поскольку уровень запасов i на начало каждого месяца (за исключением первого) неизвестен, необходимо учесть все возможные его значения и произвести поочередно вычисления: f₁(i), i = 0, 1, …, min (d₁, M), f₂(i), i = 0, l, …, min (d₁ + d₂, M), …, f_{n — 1}(i), i = 0, 1, …, min (d₁ + d₂ + +… + d_{n -1}, M), f_n(i₀), i₀ — известная величина.

На основании полученных расчетов находится объем выпуска продукции в каждом месяце, соответствующий оптимальному решению задачи. Для первого месяца планового периода он равен x_N(i₀) и позволяет достичь f_N(i₀). Уровень запасов на начало второго месяца i_{N — 1} = i₀ + x_N(i₀) — d_N, а объем выпуска во втором месяце x_{N — 1}(i_{N — 1}). Рассматривая таким образом плановые отрезки до конца планового периода, находим объем выпуска в каждом из месяцев.

1.5 Оптимальное распределение средств на расширение производство Широкий класс составляют задачи, в которых речь идет о наиболее целесообразном распределении во времени тех или иных ресурсов (денежных средств, рабочей силы, сырья и т. п.). Рассмотрим простейший пример задачи такого рода.

Группе предприятий выделяются дополнительные средства на реконструкцию и модернизацию производства. По каждому из п предприятий известен возможный прирост g_i(x) (i =) выпуска продукции в зависимости от выделенной суммы х. Требуется так распределить между предприятиями средства с, чтобы общий прирост f_n© выпуска продукции был максимальным.

В соответствии с вычислительной схемой динамического программирования рассмотрим сначала случай п = 1, т. е. предположим, что все имеющиеся средства выделяются на реконструкцию и модернизацию одного предприятия. Обозначим через f₁(x) максимально возможный прирост выпуска продукции на этом предприятии, соответствующий выделенной сумме х. Каждому значению х отвечает вполне определенное (единственное) значение g_i(x) выпуска, поэтому можно записать, что

f₁(x) = max (g₁(x)) = g₁(x). (1.7)

Пусть теперь n = 2, т. е. средства распределяются между двумя предприятиями. Если второму предприятию выделена сумма х, то прирост продукции на нем составит g₂(x). Оставшиеся другому предприятию средства (c — x) в зависимости от величины х (а значит, и c — x) позволят увеличить прирост выпуска продукции до максимально возможного значения f₁(c — x). При этом условии общий прирост выпуска продукции на двух предприятиях

g₂(x) + f₁(c — x) (1.8)

Оптимальному значению f₂© прироста продукции при распределении суммы c между двумя предприятиями соответствует такое х, при котором сумма (1.8) максимальна. Это можно выразить записью

f₂© = (g₂(x) + f₁(c — x))

Значение f₃© можно вычислить, если известны значении f₂©, и т. д.

Функциональное уравнение Беллмана для рассматриваемой задачи запишется в следующем виде:

f_n© = (g_n(x) + f_{n — 1}(c — x)) (1.9)

Итак, максимальный прирост выпуска продукции на n предприятиях определяется как максимум суммы прироста выпуска на n-м предприятии и прироста выпуска на остальных n — 1 предприятиях при условии, что оставшиеся после n-го предприятия средства распределяются между остальными предприятиями оптимально.

Имея функциональные уравнения (1.7) и (1.9), мы можем последовательно найти сначала f₁, затем f₂, f₃, … и, наконец, f_{n — 1} и f_n для различных значений распределяемой суммы средств.

Для отыскания оптимального распределения средств, прежде всего, находим величину x_n*© ассигнований n-му предприятию, которая позволяет достичь полученного нами максимального значения f_n прироста продукции. По величине оставшихся средств c — x_n*© и уже известному нам значению f_{n — 1} устанавливаем x_{n — 1}*(c) — величину ассигнований (n — 1)-му предприятию и т. д. и, наконец, находим x₂*©, x₁*©.

2. РЕШЕНИЕ ЭКОНОМИЧЕСКИХ ЗАДАЧ МЕТОДОМ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

2.1 Задачи выбора кратчайшего пути В задачах выбора кратчайшего пути нет естественного деления на шаги. Это деление вводиться искусственно, для чего расстояние между начальной и конечной вершинами сети разбивается на N частей и за каждый шаг оптимизации принимается каждая такая часть.

Пример 1

Найти путь минимальной длины между начальной и конечной вершинами сети методом динамического программирования (цифры, приписанные дугам сети, означают расстояния между соответствующими вершинами) для рис. 2.1.

Рис 2.1

Решение: разобьем все множество вершин на подмножества. В первое подмножество включим исходную вершину 1, во второе — вершины, в которые входят дуги, выходящие из вершины 1, в третье — вершины, в которые входят дуги, выходящие из вершин второго подмножества. Таким образом, продолжая разбиение, получаем пять подмножеств: {1}, {2, 3}, {4, 5}, {6, 7, 8}, {9}. Очевидно, что любой маршрут из вершины 1 в вершину 9 содержит ровно четыре дуги, каждая из которых связывает вершины, принадлежащие соответствующим подмножествам. Следовательно, процесс решения задачи (нахождения оптимального маршрута) разбивается на четыре этапа. На первом этапе принимается решение, через какую вершину, принадлежащую второму подмножеству, начать путь из вершины 1. На втором этапе необходимо определить, через какую вершину, принадлежащую третьему подмножеству, начать путь из некоторой вершины, и т. д.

Пронумеруем этапы от конечной вершины сети к начальной (см. рис. 2.1) и введем обозначения: п — номер шага (n = 1, 2, 3, 4); f_n(s) — минимальные затраты прохождения пути от вершины s до конечной вершины, если до конечной вершины осталось n шагов; j_n(s) — номер вершины, через которую нужно продолжить путь из вершины s, чтобы достичь f_n(s); c_sj — стоимость прохождения пути из вершины s в вершину j. Здесь все обозначения несут важную смысловую нагрузку: f означает целевую функцию, s — состояние системы (номер вершины), индекс n несет динамическую информацию о том, что из вершины s до конечной вершины осталось п шагов.

Предположим, что путь пройден, следовательно, число оставшихся шагов равно нулю (n = 0) и f_n(s) = f₀(9) = 0, так как вершина 9 конечная.

Рассмотрим последний шаг (n = 1) и вычислим для него значение функции. Очевидно, что в вершину 9 можно попасть из вершин 8, 7, 6. Вычислим затраты прохождения пути для этих трех состояний:

f₁(6) = c_6,9 + f₀(9) = 5 + 0 = 5, s = 6, j₁(6) = 9;

f₁(7) = c_7,9 + f₀(9) = 7 + 0 = 7, s = 7, j₁(7) = 9;

f₁(8) = c_8,9 + f₀(9) = 8 + 0 = 8, s = 8, j₁(8) = 9;

Занесем данные для удобства в таблицу.

Таблица 2.1

Произведем расчет для n = 2. Из вершины 4 в вершину 9 можно попасть через вершину 6, или через вершину 7, или через 8. Поэтому оптимальный маршрут из вершины 4 найдется из выражения

f₂(4) = min (c_4,6 + f₁(6); c_4,7 + f₁(7); c_4,8 + f₁(8)) = min (14; 13; 16) = 13

Здесь s = 6 и j₂(4) = 7, т. е. условно-оптимальный маршрут проходит через вершину 7.

Аналогично находим значения функции для s = 5:

f₂(5) = min (c_5,6 + f₁(6); c_5,7 + f₁(7); c_5,8 + f₁(8)) = min (11; 10; 12) = 10, j₂(5) = 7;

Занесем данные для удобства в таблицу.

Таблица 2.2

Цифры в столбцах таблиц, находящиеся слева от двойной вертикальной черты, представляют собой сумму стоимости c_sj прохождения пути из вершины s в вершину j и стоимости f_{n — 1}(j) прохождения пути из вершины j в вершину 9. В каждой строке выбирается наименьшая из этих сумм. Этим определяются условно-оптимальные затраты прохождения пути из вершины s в конечную вершину. Затраты (значение функции) обозначены f_n(s) и записаны в первом столбце справа от вертикальной черты, а вершина, через которую проходит условно-оптимальный маршрут, обозначен j_n(s).

Аналогично вычислим значения функции для третьего шага (n = 3):

f₃(2) = min (c_2,4 + f₂(4); c_2,5 + f₂(5)) = min (20; 14) = 14, s = 2, j₃(2) = 5;

f₃(3) = min (c_3,4 + f₂(4); c_3,5 + f₂(5)) = min (17; 16) = 16, s = 3, j₃(3) = 5.

Занесем данные в таблицу.

Таблица 2.3

Вычисления для четвертого шага (п = 4).

f₄(1) = min (c_1,2 + f₃(2); c_1,3 + f₃(3)) = min (16; 19) = 16, s = 1, j₄(1) = 2.

Таблица 2.4

Очевидно, что минимальные затраты f₄(1) = 16 и оптимальный маршрут проходит через вторую вершину, так как j₄(1) = 2. Далее из таблицы 2.3 при s = 2 следует, что оптимальный маршрут проходит через вершину 5, так как j₃(2) = 5. Продолжая рассмотрение таблиц, для п = 2 определяем, что оптимальный маршрут проходит через вершину 7 (j₂(5) = 7). Наконец, из вершины 7 попадаем в конечную вершину 9.

Таким образом, двигаясь от последней таблицы к первой, определяем оптимальный маршрут = (1 — 2 — 5 — 7 — 9), затраты прохождения пути составляют f₄(1) = 2 + 4 + 3 + + 7 = 16.

Пример 2

Найти путь минимальной длины между начальной и конечной вершинами сети методом динамического программирования (цифры, приписанные дугам сети, означают расстояния между соответствующими вершинами) для рис. 2.2.

Рис. 2.2

Решение: разобьем все множество вершин на подмножества. В первое подмножество включим исходную вершину 1, во второе — вершины, в которые входят дуги, выходящие из вершины 1, в третье — вершины, в которые входят дуги, выходящие из вершин второго подмножества. Таким образом, продолжая разбиение, получаем пять подмножеств: {1}, {2, 3}, {4, 5, 6}, {7, 8, 9}, {10}. Очевидно, что любой маршрут из вершины 1 в вершину 10 содержит ровно четыре дуги, каждая из которых связывает вершины, принадлежащие соответствующим подмножествам. Следовательно, процесс решения задачи (нахождения оптимального маршрута) разбивается на четыре этапа. На первом этапе принимается решение, через какую вершину, принадлежащую второму подмножеству, начать путь из вершины 1. На втором этапе необходимо определить, через какую вершину, принадлежащую третьему подмножеству, начать путь из некоторой вершины, и т. д.

Пронумеруем этапы от конечной вершины сети к начальной (см. рис. 2.2) и введем обозначения: п — номер шага (n = 1, 2, 3, 4); f_n(s) — минимальные затраты прохождения пути от вершины s до конечной вершины, если до конечной вершины осталось n шагов; j_n(s) — номер вершины, через которую нужно продолжить путь из вершины s, чтобы достичь f_n(s); c_sj — стоимость прохождения пути из вершины s в вершину j. Здесь все обозначения несут важную смысловую нагрузку: f означает целевую функцию, s — состояние системы (номер вершины), индекс n несет динамическую информацию о том, что из вершины s до конечной вершины осталось п шагов.

Предположим, что путь пройден, следовательно, число оставшихся шагов равно нулю (n = 0) и f_n(s) = f₀(10) = 0, так как вершина 10 конечная.

Рассмотрим последний шаг (n = 1) и вычислим для него значение функции. Очевидно, что в вершину 10 можно попасть из вершин 7, 8, 9. Вычислим затраты прохождения пути для этих трех состояний:

f₁(7) = c_7,10 + f₀(10) = 7 + 0 = 7, s = 7, j₁(7) = 10;

f₁(8) = c_8,10 + f₀(10) = 7 + 0 = 7, s = 8, j₁(8) = 10;

f₁(9) = c_9,10 + f₀(10) = 8 + 0 = 8, s = 9, j₁(9) = 10;

Занесем данные для удобства в таблицу.

Таблица 2.5

Произведем расчет для n = 2. Из вершины 4 в вершину 10 можно попасть через вершину 7, или через вершину 8, или через 9. Поэтому оптимальный маршрут из вершины 4 найдется из выражения

f₂(4) = min (c_4,7 + f₁(7); c_4,8 + f₁(8); c_4,9 + f₁(9)) = min (10; 12; 14) = 10

Здесь s = 4 и j₂(4) = 7, т. е. условно-оптимальный маршрут проходит через вершину 7.

Аналогично находим значения функции для s = 5 и s = 6:

f₂(5) = c_5,7 + f₁(7) = 13, j₂(5) = 7;

f₂(6) = c_6,9 + f₁(9) = 16, j₂(6) = 9;

Занесем данные для удобства в таблицу.

Таблица 2.6

Здесь четыре клетки зачеркнуты, поскольку из вершины 6 нельзя попасть в вершины 7 и 8, а из вершины 5 — в вершины 8 и 9.

Цифры в столбцах таблиц, находящиеся слева от двойной вертикальной черты, представляют собой сумму стоимости c_sj прохождения пути из вершины s в вершину j и стоимости f_{n — 1}(j) прохождения пути из вершины j в вершину 9. В каждой строке выбирается наименьшая из этих сумм. Этим определяются условно-оптимальные затраты прохождения пути из вершины s в конечную вершину. Затраты (значение функции) обозначены f_n(s) и записаны в первом столбце справа от вертикальной черты, а вершина, через которую проходит условно-оптимальный маршрут, обозначен j_n(s).

Аналогично вычислим значения функции для третьего шага (n = 3):

f₃(2) = min (c_2,4 + f₂(4); c_2,5 + f₂(5)) = min (20; 16) = 16, s = 2, j₃(2) = 4;

f₃(3) = min (c_3,4 + f₂(4); c_{3, 6} + f₂(6)) = min (18; 25) = 18, s = 3, j₃(3) = 4.

Занесем данные в таблицу.

Таблица 2.7

Вычисления для четвертого шага (п = 4).

f₄(1) = min (c_1,2 + f₃(2); c_1,3 + f₃(3)) = min (19; 20) = 19, s = 1, j₄(1) = 2.

Таблица 2.8

Очевидно, что минимальные затраты f₄(1) = 19 и оптимальный маршрут проходит через вторую вершину, так как j₄(1) = 2. Далее из таблицы 2.7 при s = 2 следует, что оптимальный маршрут проходит через вершину 4, так как j₃(2) = 4. Продолжая рассмотрение таблиц, для п = 2 определяем, что оптимальный маршрут проходит через вершину 7 (j₂(4) = 7). Наконец, из вершины 7 попадаем в конечную вершину 10. Таким образом, двигаясь от последней таблицы к первой, определяем оптимальный маршрут = (1 — 2 — 4 — 7 — 10), затраты прохождения пути составляют f₄(1) = 3 + 6 + 3 + + 7 = 19.

2.2 Задачи планирования производственной программы В задачах планирования производственной программы естественное деление на шаги, т. е. число шагов совпадает с числом месяцев (количеством плановых отрезков времени п).

Пример 1

Определить оптимальную производственную программу изготовления машин x_t, удовлетворяющую спрос в каждом из месяцев планируемого периода D_t и обеспечивающую минимальные затраты на производство продукции и содержание запасов. Если затраты на производство продукции составляют:

с (0) = 0, с (1) = 13, с (2) = 15, с (3) = 17, с (4) = 19, с (5) = 21, с (6) = 23

Плановый период состоит из четырех месяцев

(t =). D₁ = 3, D₂ = 4, D₃ = 4, D₄ = 2, i₀ = 2, h = 2, B = 6, M = 4

Решение.

Рассмотрим n = 0 (отрезок за пределом планового периода). В соответствии с формулой (1.3) уровень запасов на конец планового периода равен нулю:

f₀(0) = 0.

D₁ = d₄ = 3, D₂ = d₃ = 4, D₃ = d₂= 4, D₄ = d₁= 2.

Для п = 1 (см. формулу (1.4)):

x₁(i) = d₁ — i;

f₁(i) = c₁(x₁, j₁) = c₁(d₁ — i, 0) = c₁(2 — i);

i =

Расчет всех значений f₁(i) выполним в таблице 2.9, где f₁(i) = c₁(2 — i).

Таблица 2.9

Для второго отрезка (n = 2) значения функции f₂(i) вычисляются по формуле (1.5):

f₂(i) = min (c₂(x) + h (i + x — d₂) + f₁(i + x — d₂)),

где i =, 4 — i x 6 — i.

В таблице 2.10 приведены все возможные значения сумм c₂(x) + h (i + x d₂) + f₁(i + x — d₂). Здесь предусмотрено по одной строке для каждого возможного значения начального уровня запаса i, который не должен превышать min (d₁ + d₂, M), и по одному столбцу для возможных значений выпуска х. Поскольку спрос на продукцию в каждом месяце должен быть удовлетворен, а уровень запасов конец каждого отрезка не может превысить

4 ед., некоторые клетки в таблице зачеркнуты. Эти клетки соответствуют недопустимым сочетаниям значений i и х. Так, если i = 0, то спрос удается удовлетворить только при условии х 4. Если i = 4, то х 2, иначе запас на конец планового периода будет больше нуля. В каждой клетке таблицы слева от двойной черты записана сумма трех слагаемых. Первое слагаемое — значение c (x), второе слагаемое — затраты на содержание запасов, равные уровню запасов на конец отрезка, умноженному на h = 2. Так, например, при i = 3 и x = 1 уровень запасов на конец отрезка равен нулю, поэтому в соответствующей клетке второе слагаемое равно нулю. При i = 2 и x = 4 уровень запасов на конец отрезка равен 2, следовательно, в соответствующей клетке таблицы второе слагаемое равно 4. Наконец, третье слагаемое есть ранее вычисленное значение f₁(i + x — d₂) = f₁(i + x — 4), взятое из таблицы 2.9.

Таблица 2.10

Значение функции f₂(i), записанное в правом крайнем столбце таблицы 2.10, представляет собой минимальную из всех сумм в клетках строки для каждого фиксированного i, а x₂(i) — соответствующий выпуск продукции. Например, при i = 0 оптимальный выпуск равен 6 ед., так как наименьшая сумма в этой строке (23 + 4 + 0) находится в столбце, соответствующем х = 6.

Для п = 3 рекуррентное соотношение имеет вид

f₃(i) = min (c₃(x) + h (i + x — d₃) + f₂(i + x — d₃))

где i =, 4 — i x 6.

Расчет значений f₃(i) приведен в таблице 2.11:

Таблица 2.11

Аналогично для п = 4 рекуррентное соотношение имеет вид

f₄(i) = min (c₄(x) + h (i + x — d₄) + f₃(i + x — d₄)),

где i = i₀ = 2, d₄ — i₀ = 1×6 = min (d₁ + d₂ + d₃ + d₄ — i, B).

Расчет значений f₄(i) приведен в таблице 2.12. Таблица состоит из двух строк: заглавной и предназначенной для записи вычислений при начальном уровне запаса i₀ = 2. Здесь можно сделать предположений о значениях i, так как запас на начало первого месяца планового периода известен.

Таблица 2.12

Минимальные затраты, связанные с производством и хранением продукции за четыре месяца, f₄(i) = 56.

При x₄ = 5 уровень запасов на начало второго месяца (конец первого) равен i₃ = i₀ + x₄ — d₄ = 2 + 5 — 3 = 4. Рассматривая строку таблицы 2.11, соответствующую i₃ = 4, видим, что x₃ = 0. Поскольку запас продукции на начало третьего месяца равен нулю (i₂ = i₃ + x₃ — d₃ = 4 + 0 — 4 = 0), из

таблицы 2.10 находим x₂ = 6. Аналогично i₁ = i₂ + x₂ — d₂ = 0 + 6 — 4 = 2, из

таблицы 2.9 находим x₁ = 0. Таким образом, чтобы достичь оптимальных затрат, равных 56 единицам, требуется в первый месяц изготовить 5 машин, во второй — 0, в третий — 6 и в четвертый — 0.

Пример 2

Определить оптимальную производственную программу изготовления машин x_t, удовлетворяющую спрос в каждом из месяцев планируемого периода D_t и обеспечивающую минимальные затраты на производство продукции и содержание запасов. Если затраты на производство продукции составляют:

с (0) = 0, с (1) = 13, с (2) = 15, с (3) = 17, с (4) = 19, с (5) = 21, с (6) = 23

Плановый период состоит из четырех месяцев

(t =). D₁ = 3, D₂ = 3, D₃ = 2, D₄ = 4, i₀ = 1, h = 1, B = 5, M = 4

Решение.

Рассмотрим n = 0 (отрезок за пределом планового периода). В соответствии с формулой (1.3) уровень запасов на конец планового периода равен нулю: f₀(0) = 0.

D₁ = d₄ = 3, D₂ = d₃ = 3, D₃ = d₂= 2, D₄ = d₁= 4.

Для п = 1 (см. формулу (1.4)):

x₁(i) = d₁ — i;

f₁(i) = c₁(x₁, j₁) = c₁(d₁ — i, 0) = c₁(4 — i);

i =

Расчет всех значений f₁(i) выполним в таблице 2.13, где f₁(i) = c₁(2 — i).

Таблица 2.13

Для второго отрезка (n = 2) значения функции f₂(i) вычисляются по формуле (1.5):

f₂(i) = min (c₂(x) + h (i + x — d₂) + f₁(i + x — d₂))

где i =, 2 — i x 5.

Таблица 2.14

В таблице 2.10 приведены все возможные значения сумм c₂(x) + h (i + x d₂) + f₁(i + x — d₂). Здесь предусмотрено по одной строке для каждого возможного значения начального уровня запаса i, который не должен превышать min (d₁ + d₂, M), и по одному столбцу для возможных значений выпуска х. Поскольку спрос на продукцию в каждом месяце должен быть удовлетворен, а уровень запасов конец каждого отрезка не может превысить 4 ед., некоторые клетки в таблице зачеркнуты. Эти клетки соответствуют недопустимым сочетаниям значений i и х. Так, если i = 0, то спрос удается удовлетворить только при условии х 4. Если i = 4, то х 2, иначе запас на конец планового периода будет больше нуля. В каждой клетке таблицы слева от двойной черты записана сумма трех слагаемых. Первое слагаемое — значение c (x), второе слагаемое — затраты на содержание запасов, равные уровню запасов на конец отрезка, умноженному на h = 2. Так, например, при i = 2 и x = 4 уровень запасов на конец отрезка равен 2, следовательно, в соответствующей клетке таблицы второе слагаемое равно 4. Наконец, третье слагаемое есть ранее вычисленное значение f₁(i + x — d₂) = f₁(i + x — 4), взятое из таблицы 2.9.

Значение функции f₂(i), записанное в правом крайнем столбце таблицы 2.10, представляет собой минимальную из всех сумм в клетках строки для каждого фиксированного i, а x₂(i) — соответствующий выпуск продукции. Например, при i = 0 оптимальный выпуск равен 6 ед., так как наименьшая сумма в этой строке (23 + 4 + 0) находится в столбце, соответствующем х = 6.

Для п = 3 рекуррентное соотношение имеет вид

f₃(i) = min (c₃(x) + h (i + x — d₃) + f₂(i + x — d₃)),

где i =, 3 — i x 5.

Расчет значений f₃(i) приведен в таблице 2.15:

Таблица 2.15

Аналогично для п = 4 рекуррентное соотношение имеет вид

f₄(i) = min (c₄(x) + h (i + x — d₄) + f₃(i + x — d₄)),

где i = i₀ = 1, d₄ — i₀ = 2×5 = min (d₁ + d₂ + d₃ + d₄ — i, B).

Расчет значений f₄(i) приведен в таблице 2.16. Таблица состоит из двух строк: заглавной и предназначенной для записи вычислений при начальном уровне запаса i₀ = 2. Здесь можно сделать предположений о значениях i, так как запас на начало первого месяца планового периода известен.

Таблица 2.16

Минимальные затраты, связанные с производством и хранением продукции за четыре месяца, f₄(i) = 57.

При x₄ = 2 уровень запасов на начало второго месяца (конец первого) равен i₃ = i₀ + x₄ — d₄ = 1 + 2 — 3 = 0. Рассматривая строку таблицы 2.15, соответствующую i₃ = 0, видим, что x₃ = 5. Поскольку запас продукции на начало третьего месяца равен нулю (i₂ = i₃ + x₃ — d₃ = 0 + 5 — 3 = 2), из

таблицы 2.14 находим x₂ = 0. Аналогично i₁ = i₂ + x₂ — d₂ = 2 + 0 — 2 = 0, из

таблицы 2.13 находим x₁ = 4. Таким образом, чтобы достичь оптимальных затрат, равных 57 единицам, требуется в первый месяц изготовить 2 машины, во второй — 5, в третий — 0 и в четвертый — 4.

2.3 Задачи оптимального распределения средств на расширение производства В задачах оптимального распределения средств на расширение производства естественное деление на шаги, т. е. число шагов совпадает с числом предприятий.

Пример 1

Производственному объединению из четырех предприятий выделяется банковский кредит в сумме 60 млн. ден. ед. для реконструкции и модернизации производства с целью увеличения выпуска продукции. Значения g_i(x_i) (i =) дополнительного дохода, получаемого на предприятиях объединения в зависимости от выделенной суммы x_i, приведены в таблице 2.17. Распределить выделенный кредит между предприятиями так, чтобы дополнительный доход объединения был максимальным.

Таблица 2.17

Решение.

Пусть п = 1. В соответствии с формулой (1.7) в зависимости от начальной суммы c получаем с учетом таблицей 2.17 значения f₁©, помещенные в таблицу 2.18.

Таблица 2.18

Предположим теперь, что средства вкладываются в два предприятия. Тогда в соответствии с формулой (1.9)

f₂© = (g₂(x) + f₁(c — x))

Очередная задача — найти значения функции f₂© для всех допустимых комбинаций c и x. Для упрощения расчетов значения x будем принимать кратными 20 тыс. ден. ед. и для большей наглядности записи оформлять в виде таблиц. Каждому шагу будет соответствовать своя таблица. Рассматриваемому шагу соответствует табл. 2.19.

Для каждого значения (20, 40, 60) начальной суммы c распределяемых средств в таблице 2.19 предусмотрена отдельная строка, а для каждого возможного значения x (0, 20, 40, 60) распределяемой суммы — столбец. Некоторые клетки таблицы останутся незаполненными, так как соответствуют недопустимым сочетаниям c и x. Такой, например, будет клетка, отвечающая строке c = 20 и столбцу x = 40, ибо при наличии 20 тыс. ден. ед. естественно отпадает вариант, при котором одному из предприятий выделяется 40 тыс. ден. ед.

Таблица 2.19

В каждую клетку таблицы будем вписывать значение суммы g₂(x) + f₁(c x). Первое слагаемое берем из условий задачи (см. табл. 2.17), второе — из таблицы 2.18. Так, например, при распределении начальной суммы с = 60 тыс. ден. ед. одним из вариантов может быть следующий: второму предприятию выделяется 40 тыс. ден. ед. (х = 40), тогда первому 60 — 40 = 20 тыс. ден. ед. При таком распределении первоначальной суммы на втором предприятий будет обеспечен прирост продукции на сумму в 19 тыс. ден. ед. (см. табл. 2.17), на первом — 9 тыс. ден. ед. (см. табл. 2.18).

Общий прирост составит (19 + 9) тыс. ден. ед., что и записано в соответствующей клетке таблицы 2.19. В двух последних столбцах таблицы проставлены максимальный по строке прирост продукции (в столбце f₂(c)) и соответствующая ему оптимальная сумма средств, выделенная второму предприятию (в столбце x₂*(c)). Так, при начальной сумме с = 40 тыс. ден. ед. максимальный прирост выпуска продукции составляет 20 тыс. ден. ед. (11 + 9), и это достигается выделением второму предприятию 20, а первому — 20 — 20 = 0 тыс. ден. ед.

Расчет значений f₃© приведен в таблице 2.20. Здесь использована формула, получающаяся из (1.9) при п = 3 :

f₃© = (g₃(x) + f₂(c — x))

Первое слагаемое в таблице 2.20 взято из табл. 2.17, второе — из табл. 2.19.

Таблица 2.20

Аналогичным образом находятся значения f₄©.

Таблица 2.21

Полученные результаты можно сравнить с теми, которые приведены в сводной таблице (табл. 2.22, см. последние два столбца), составленной на основе расчетных таблиц, начиная с табл. 2.17.

Таблица 2.22

Табл. 2.22 содержит много ценной информации и позволяет единообразно решать целый ряд задач. Например, и табл. 2.22 видно, что наибольший дополнительный доход объединения из четырех предприятий может дать распределение между ними 60 тыс. ден. ед. (с = 60), составляет 45 тыс. ден. ед. (f₄(60) = 45). При этом четвертому предприятию должно быть выделено 20 тыс. ден. ед. (x₄*(60) = 20), а остальным трем — 60 — 20 = 40 тыс. ден. ед. Из той же таблицы видно, что оптимальное распределение оставшихся 40 тыс. ден. ед. (с = 40) между тремя предприятиями обеспечит увеличения дополнительного дохода на сумму 32 тыс. ден. ед. (f₃(40) = 32) при условии, что третьему предприятию будет выделено 40 тыс. ден. ед. (x₃*(40) = 40), а остальным двум 40 — 40 = 0 тыс. ден. ед. Следовательно, на долю первого и второго средств не останется.

Итак, максимальный дополнительный доход на четырех предприятиях при распределении между ними 60 тыс. ден. ед. составляет 45 тыс. ден. ед. и будет получен, если первому и второму предприятиям средств не выделять, третьему — 40 тыс. ден. ед., а четвертому — 20 тыс. ден. ед.

Пример 2

Производственному объединению из трех предприятий выделяется банковский кредит в сумме 60 млн. ден. ед. для реконструкции и модернизации производства с целью увеличения выпуска продукции. Значения g_i(x_i) (i =) дополнительного дохода, получаемого на предприятиях объединения в зависимости от выделенной суммы x_i, приведены в таблице 2.23. Распределить выделенный кредит между предприятиями так, чтобы дополнительный доход объединения был максимальным.

Таблица 2.23

Решение.

Пусть п = 1. В соответствии с формулой (1.7) в зависимости от начальной суммы c получаем с учетом таблицей 2.23 значения f₁©, помещенные в таблицу 2.24.

Таблица 2.24

Предположим теперь, что средства вкладываются в два предприятия. Тогда в соответствии с формулой (1.9)

f₂© = (g₂(x) + f₁(c — x))

Очередная задача — найти значения функции f₂© для всех допустимых комбинаций c и x. Для упрощения расчетов значения x будем принимать кратными 20 тыс. ден. ед. и для большей наглядности записи оформлять в виде таблиц. Каждому шагу будет соответствовать своя таблица. Рассматриваемому шагу соответствует табл. 2.25.

Для каждого значения (20, 40, 60) начальной суммы c распределяемых средств в таблице 2.25 предусмотрена отдельная строка, а для каждого возможного значения x (0, 20, 40, 60) распределяемой суммы — столбец. Некоторые клетки таблицы останутся незаполненными, так как соответствуют недопустимым сочетаниям c и x. Такой, например, будет клетка, отвечающая строке c = 20 и столбцу x = 40, ибо при наличии 20 тыс. ден. ед. естественно отпадает вариант, при котором одному из предприятий выделяется 40 тыс. ден. ед.

Таблица 2.25

В каждую клетку таблицы будем вписывать значение суммы g₂(x) + f₁(c x). Первое слагаемое берем из условий задачи (см. табл. 2.23), второе — из таблицы 2.24. Так, например, при распределении начальной суммы с = 60 тыс. ден. ед. одним из вариантов может быть следующий: второму предприятию выделяется 40 тыс. ден. ед. (х = 40), тогда первому 60 — 40 = 20 тыс. ден. ед. При таком распределении первоначальной суммы на втором предприятий будет обеспечен прирост продукции на сумму в 34 тыс. ден. ед. (см. табл. 2.23), на первом — 9 тыс. ден. ед. (см. табл. 2.24).

Общий прирост составит (34 + 9) тыс. ден. ед., что и записано в соответствующей клетке таблицы 2.25. В двух последних столбцах таблицы проставлены максимальный по строке прирост продукции (в столбце f₂(c)) и соответствующая ему оптимальная сумма средств, выделенная второму предприятию (в столбце x₂*(c)). Так, при начальной сумме с = 20 тыс. ден. ед. максимальный прирост выпуска продукции составляет 11 тыс. ден. ед. (11 + 0), и это достигается выделением второму предприятию 20, а первому — 20 — 20 = 0 тыс. ден. ед.

Расчет значений f₃© приведен в таблице 2.26. Здесь использована формула, получающаяся из (1.9) при п = 3:

f₃© = (g₃(x) + f₂(c — x)).

Таблица 2.26

Полученные результаты можно сравнить с теми, которые приведены в сводной таблице (табл. 2.27, см. последние два столбца), составленной на основе расчетных таблиц, начиная с табл. 2.23.

Таблица 2.27

Табл. 2.27 содержит много ценной информации и позволяет единообразно решать целый ряд задач. Например, и табл. 2.27 видно, что наибольший дополнительный доход объединения из трех предприятий может дать распределение между ними 60 тыс. ден. ед. (с = 60), составляет 47 тыс. ден. ед. (f₃(60) = 47). При этом третьему предприятию должно быть выделено

20 тыс. ден. ед. (x₃*(60) = 20), а остальным двум — 60 — 20 = 40 тыс. ден. ед. Из той же таблицы видно, что оптимальное распределение оставшихся

40 тыс. ден. ед. (с = 40) между двумя предприятиями обеспечит увеличения дополнительного дохода на сумму 34 тыс. ден. ед. (f₂(40) = 32) при условии, что второму предприятию будет выделено 40 тыс. ден. ед. (x₂*(40) = 40), а на долю первого средств не останется (40 — 40 = 0).