Последовательное улучшение производственной программы

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

(7)

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

Математическая модель задачи:

найти производственную программу

(x₁, x₂, x₃, x₄)

максимизирующую прибыль

z = 36x₁+ 14x₂ + 25x₃ + 50x₄ (8)

при ограничениях по ресурсам

(9)

где по смыслу задачи

x₁ ³ 0, x₂ ³ 0, x₃ ³ 0, x₄ ³ 0. (10)

Получили задачу на условный экстремум. Для ее решения систему неравенств (9) при помощи дополнительных неотрицательных неизвестных х₅, х₆, х₇ заменим системой линейных алгебраических уравнений

(11)

где дополнительные переменные имеют смысл остатков соответствующих ресурсов. Среди всех решений системы уравнений (11), удовлетворяющих условию неотрицательности

х₁³0, х₂³0, …, х₅³0, …, х₇³0. (12)

надо найти то решение, при котором функция (8) примет наибольшее значение.

Воспользуемся тем, что правые части всех уравнений системы (11) неотрицательны, а сама система имеет предпочитаемый вид – дополнительные переменные являются базисными. Приравняв к нулю свободные переменные х₁, х₂, х₃, х₄, получаем базисное неотрицательное решение

x₁=0, x₂=0, x₃=0, x₄=0, x₅=208, x₆=107, x₇=181 (13)

первые четыре компоненты которого определяют производственную программу

x₁=0, x₂=0, x₃=0, x₄=0 (14)

по которой мы пока ничего не производим.

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

(15)

Мы пока сохраняем в общем решении х₁=х₂=х₃=0 и увеличиваем только х₄. При этом значения базисных переменных должны оставаться неотрицательными, что приводит к системе неравенств

или т.е. 0 £ х₄ £

Дадим х₄ наибольшее значение х₄ =181/5, которое она может принять при нулевых значениях других свободных неизвестных, и подставим его в (15). Получаем для системы уравнений (11) частное неотрицательное решение

х₁=0, х₂=0, х₃=0, х₄= ; x₅=27; x₆= ; x₇=0 (16)

Нетрудно убедиться, что это решение является новым базисным неотрицательным решением системы линейных алгебраических уравнений (11), для получения которого достаточно было принять в системе (11) неизвестную х₄ за разрешающую и перейти к новому предпочитаемому виду этой системы, сохранив правые части уравнений неотрицательными, для чего за разрешающее уравнение мы обязаны принять третье, так как

а разрешающим элементом будет а₃₄=5. Применив известные формулы исключения, получаем для системы уравнений (11) новый предпочитаемый эквивалент

x₁ + 2x₂ + 2x₃ + x₅ - x₇ = 27

x₁ + x₂ - x₃ + x₆ - x₇ = (17)

x₁ + x₂ + x₃ + x₄ + x₇ =

Приравняв к нулю свободные переменные х₁, х₂, х₃, х₇, получаем базисное неотрицательное решение, совпадающее с (16), причем первые четыре компоненты его определяют новую производственную программу

х₁=0, х₂=0, х₃=0, х₄= . (18)

Исследуем, является ли эта программа наилучшей, т.е. обеспечивает ли она наибольшую прибыль. Для этого выразим функцию прибыли (8) через новые свободные переменные х₁, х₂, х₃, х₇.

Из последнего уравнения системы (17) выражаем базисную переменную х₄ через свободные и подставляем в (8). Получаем

(19)

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

(20)

и исключаем х₁ из всех уравнений системы (17), кроме первого уравнения. Получим следующий предпочитаемый эквивалент системы условий, который определит для системы (11) новое базисное неотрицательное решение и уже третью производственную программу, для исследования которого нам придется выразить функцию (19) через новые свободные переменные, удалив оттуда переменную х₁, ставшую базисной. Мы видели выше, как это делается (удаляли х₄ из (8)).

Важно обратить внимание на то, что эти удаления можно выполнить очень просто. Представим соотношение (8) в виде уравнения

-36х₁ - 14х₂ - 25х₃ - 50х₄ = 0 – z (21)

и припишем его к системе (11). Получается вспомогательная система уравнений

(22)

Напомним, что разрешающую неизвестную в системе (11) мы выбрали х₄. Этой переменной в последнем уравнении системы (22) отвечает наименьший отрицательный коэффициент D₄=-50. Затем мы нашли разрешающий элемент а₃₄=5 и исключили неизвестную х₄ из всех уравнений системы (11), кроме третьего. Далее нам пришлось х₄ исключать и из функции (8). Теперь это можно сделать очень просто, если посмотреть на систему уравнений (22). Очевидно, достаточно умножить третье уравнение системы (22) на 10 и прибавить к четвертому; получим

-6х₁ - 4х₂ - 5х₃ - 10х₄ = 1810 – z (23)

Таким образом, мы преобразовывали вспомогательную систему уравнений (22) к виду

x₁ + 2x₂ + 2x₃ + x₅ - x₇ = 27

x₁ + x₂ - x₃ + x₆ - x₇ = (24)

x₁ + x₂ + x₃ + x₄ + x₇ =

-6x₁ - 4x₂ - 5x₃ +10x₇ = 1810 - z

Первые три уравнения этой системы представляют некоторый предпочитаемый эквивалент (17) системы уравнений (11) и определяют базисное неотрицательное решение (16) и производственную программу (18), а из последнего уравнения системы (24) получается выражение (19) функции цели через свободные переменные. Очевидно, если имеется хотя бы один отрицательный коэффициент D_j при какой-нибудь переменной x_j в последнем уравнении системы (24), то производственная программа не является наилучшей и можно далее продолжать процесс ее улучшения. С помощью (19) мы выяснили, что следует начинать производить продукцию первого вида, т.е. фактически мы нашли в последнем уравнении системы (24) наименьший отрицательный коэффициент

min(D_j<0) = min(-6, -4, -5) = -6 = D₁

и решили перевести свободную переменную х₁ в число базисных, для чего, согласно (20)определили разрешающее уравнение и указали разрешающий элемент а₁₁=1.

Учитывая сказанное выше, теперь мы будем преобразовывать не систему (17), а всю вспомогательную систему (24), по формулам исключения. Эта система преобразуется к виду

x₁ + 2x₂ + 2x₃ + x₅ - x₇ = 27

3x₂ - x₃ - x₅ + x₆ + x₇ = 13 (25)

- x₂ - x₃ + x₄ - x₅ + x₇ = 20

8x₂ + 7x₃ + 6x₅ + 4x₇ = 1972 - z

Первые три уравнения системы (25) представляют некоторый предпочитаемый эквивалент системы уравнений (11) и определяют базисное неотрицательное решение системы условий рассматриваемой задачи

x₁=27, x₂=0, x₃=0, x₄=20, x₅=0, x₆=13, x₇=0 (26)

т.е. определяют производственную программу

x₁=27, x₂=0, x₃=0, x₄=20 (27)

и остатки ресурсов:

первого вида х₅=0

второго вида х₆=13 (28)

третьего вида х₇=0

В последнем уравнении системы (25) среди коэффициентов при неизвестных в левой части уравнения нет ни одного отрицательного. Если из этого уравнения выразить функцию цели z через остальные неотрицательные переменные

z = 1972 - 8х₂ - 7х₃ - 6х₅ - 4х₇ (29)

то становится совершенно очевидным (в силу того, что все x_j³0), что прибыль будет наибольшей тогда, когда

x₂=0, x₃=0, x₅=0, x₇=0 (30)

Это означает, что производственная программа (27) является наилучшей и обеспечивает предприятию наибольшую прибыль

z_max = 1972 (31)

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

Остается заметить, что процесс решения обычно записывается в виде некоторой таблицы 1.

Таблица 1

			36 14 25 50 0 0 0	Пояснения
	Базис	Н	x1 x2 x3 x4 x5 x6 x7
0	х5		4 3 4 5 1 0 0	z0 = H
	х6		2 5 0 2 0 1 0
	х7		3 1 2 5 0 0 1	0
	z0 -z	0 - z	-36 -14 -25 -50 0 0 0
0	х5		1 2 2 0 1 0 -1
	х6	173/5	4/5 23/5 -4/5 0 0 1 -2/5
	х4	181/5	3/5 1/5 2/5 1 0 0 1/5
	z0 -z	1810-z	-6 -4 -5 0 0 0 10
	х1		1 2 2 0 1 0 -1
	х6		0 3 -12/5 0 -4/5 1 2/5	все Dj ³0
	х4		0 -1/5 -4/5 1 -3/5 0 4/5
	z0 -z	1972-z	0 8 7 0 6 0 4

где представлены расширенные матрицы вспомогательных систем уравнений (22) ® (24) ® (25). Эти таблицы принято называть симплексными.

Следует обратить внимание на экономический смысл элементов последней строки последней симплексной таблицы. Например, коэффициент D₃=7 при переменной х₃ показывает, что если произвести одну единицу продукции третьего вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 7 единиц.

В заключение заметим, что в рассматриваемом простейшем примере линейной производственной задачи возможна самопроверка результата.

Воспользуемся тем, что в оптимальной производственной программе х₂=0, х₃=0. Предположим, что вторую и третью продукции мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию. Математическая модель задачи будет выглядеть следующим образом:

Студенту не составит труда решить эту задачу графически и убедиться, что результаты совпадают.

Следует при этом обратить внимание на то, что последовательное улучшение производственной программы

(x₁=0, x₄=0) ® (x₁=0, x₄= ) ® (x₁=27, x₄=20)

на графике означает движение от одной вершины многогранника допустимых решений к другой вершине по связывающей их стороне многоугольника (в случае трех переменных это будет "езда" по ребрам многогранника допустимых решений от одной вершины к другой до достижения оптимальной вершины).

§5. Двойственная задача

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

Теперь представим себе, что возникла новая ситуация. Знакомый предприниматель П (Петров), занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у нас, предлагает нам "уступить" по определенным ценам все имеющиеся у нас ресурсы и обещает платить у₁ рублей за каждую единицу первого ресурса, у₂ руб – второго, у₃ руб – третьего. Возникает вопрос: при каких ценах у₁, у₂, у₃ мы можем согласиться с предложением П.

Величины у₁, у₂, у₃ принято называть расчетными, или двойственными, оценками ресурсов. Они прямо зависят от условий, в которых действует наше предприятие.

Напомним, что в нашей задаче технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С имели вид

Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы А, 4 единицы ресурса первого вида, 2 единицы ресурса второго вида и 3 единицы третьего (элементы первого столбца матрицы). В ценах у₁, у₂, у₃ наши затраты составят 4у₁ + 2у₂ + 3у₃, т.е. столько заплатит предприниматель П за все ресурсы, идущие на производство единицы первой продукции. На рынке за единицу первой продукции мы получили бы прибыль 36 руб. Следовательно, мы можем согласиться с предложением П только в том случае, если он заплатит не меньше

4у₁ + 2у₂ + 3у₃ ³ 36.

Аналогично, во втором столбце матрицы А указаны затраты различных ресурсов на производство единицы продукции второго вида. В ценах П эти затраты составят 3у₁ + 5у₂ + у₃, а на рынке за единицу продукции второго вида мы получили бы прибыль 14 рублей. Поэтому перед предпринимателем П мы ставим условие

3у₁ + 5у₂ + у₃ ³ 14

и т.д. по всем видам продукции.

Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить 208у₁ + 107у₂ + 181у₃ рублей. При поставленных нами условиях предприниматель П будет искать такие значения величин у₁, у₂, у₃, чтобы эта сумма была как можно меньше. Подчеркнем, что здесь речь идет не о ценах, по которым мы когда-то приобретали эти ресурсы, а об этих ценах, которые существенно зависят от применяемых нами технологий, объемов ресурсов и от ситуации на рынке.

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

у (у₁, y₂, y₃)

минимизирующий общую оценку всех ресурсов

f = 208y₁ + 107y₂ +181y₃ (1)

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

(2)

4y₁ + 2y₂ + 3y₃ ³ 36

3y₁ + 5y₂ + y₃ ³ 14

4y₁ + 2y₃ ³ 25

5y₁ + 2y₂ + 5y₃ ³ 50

причем оценки ресурсов не могут быть отрицательными

y₁ 0, y₂ 0, y₃ 0. (3)

Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений (х₁, х₂, х₃, х₄) и (y₁, y₂, y₃) пары двойственных задач необходимо и достаточно выполнение условий

x ₁ (4y₁ + 2y₂ + 3y₃ - 36) = 0 y₁ (4x₁ +3x₂ + 4x₃ + 5x₄ - 208) = 0

x ₂ (3y₁ + 5y₂ + y₃ - 14) = 0 y₂ (2x₁ +5x₂ + 2x₄ - 107) = 0

x ₃ (4y₁ + 2y₃ - 25) = 0 y₃ (3x₁ + x₂ + 2x₃ + 5x₄ - 181) = 0.

x ₄(5y₁ + 2y₂ + 5y₃ - 50) = 0

Ранее было найдено, что в решении исходной задачи х₁>0, x₄>0. Поэтому

4y₁ + 2y₂ + 3y₃ - 36 = 0

5y₁ + 2y₂ + 5y₃ - 50 = 0

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

у₂=0,

то приходим к системе уравнений

4y₁ + 3y₃ - 36 = 0

5y₁ + 5y₃ - 50 = 0

откуда следует

у₁=6, у₃=4.

Таким образом, получили двойственные оценки ресурсов

у₁=6; у₂=0; у₃=4, (4)

причем общая оценка всех ресурсов равна 1972.

Заметим, что решение (4) содержалось в последней строке последней симплексной таблицы исходной задачи. Важен экономический смысл двойственных оценок. Например, двойственная оценка третьего ресурса у₃=4 показывает, что добавление одной единицы третьего ресурса обеспечит прирост прибыли в 4 единицы.

§6. Задача о "расшивке узких мест производства"

При выполнении оптимальной производственной программы первый и третий ресурсы используются полностью, т.е. образуют ²узкие места производства². Будем их заказывать дополнительно. Пусть T(t₁,t₂,t₃)- вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие

H + Q^-1T 0.

Задача состоит в том, чтобы найти вектор

T (t₁, 0, t₃),

максимизирующий суммарный прирост прибыли

W = 6t₁ + 4t₃ (1)

при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы)

(2)

предполагая, что можно надеяться получить дополнительно не более 1/3 первоначального объема ресурса каждого вида

(3)

причем по смыслу задачи

t₁ 0, t₃ 0. (4)

Переписав неравенства (2) и (3) в виде:

(6)

(5)

приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4).

Эту задачу легко решить графически: см. рис. 1. Программа ²расшивки² имеет вид

t₁= , t₂=0, t₃=

и прирост прибыли составит 519 .

Сводка результатов приведена в таблице

Таблица 1

сj					b	x4+i	yi	ti
								46 5/12
aij
								60 1/3
xj								519 2/3
Dj

§7. Транспортная задача линейного программирования

Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в m пунктах производства (хранения) в количествах а₁, а₂,..., а_m единиц, необходимо распределить между n пунктами потребления, которым необходимо соответственно b₁, b₂,..., b_n единиц. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна с_ij и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.

Обозначим через х_ij количество груза, планируемого к перевозке от i-го поставщика j-му потребителю. При наличии баланса производства и потребления

(1)

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

найти план перевозок

Х = (х_ij), i = 1,m; j = 1,n

минимизирующий общую стоимость всех перевозок

(2)

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

(3)

и любому потребителю доставляется необходимое количество груза

(4)

причем по смыслу задачи

х₁₁ > 0,...., x_mn > 0. (5)

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

А(а₁, а₂, а₃) = (54; 60; 63); В(b₁, b₂, b₃, b₄) = (41; 50; 44; 30); С =

Общий объем производства åа_i = 55+60+63 = 178 больше, требуется всем потребителям åb_i = 42+50+44+30 = 166, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 178-166 = 12 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.

Первое базисное допустимое решение легко построить по правилу ²северо-западного угла².

Потребление	b1 =41	b2 =50	b3 =44	b4 =30	b5 =12
Производство
а1 =54						p1 =0
a2 =60						p2 =
a3 =63	*					p3 =
	q1 =	q2 =	q3 =	q4 =	q5 =

Следует иметь в виду, что по любой транспортной таблице можно восстановить соответствующий предпочитаемый эквивалент системы уравнений (3), (4), а в таблице записаны лишь правые части уравнений, причем номер клетки показывает, какая неизвестная в соответствующем уравнении является базисной. Так как в системе (3), (4) ровно m + n - 1 линейно независимых уравнений, то в любой транспортной таблице должно быть m + n - 1 занятых клеток.

Обозначим через

m )

вектор симплексных множителей или потенциалов. Тогда

D_ij = m A_ij - с_ij i = 1,m; j = 1,n

откуда следует

D_ij = p_i + q_j - c_ij i = 1,m; j = 1,n (6)

Один из потенциалов можно выбрать произвольно, так как в системе (3), (4) одно уравнение линейно зависит от остальных. Положим, что р₁ = 0. Остальные потенциалы находим из условия, что для базисных клеток . В данном случае получаем

D₁₁ = 0, p₁ + q₁ - c₁₁ = 0, 0+q₁ -1 = 0, q₁ = 1

D₁₂ = 0, p₁ + q₂ - c₁₂ = 0, 0+q₂ -4 = 0, q₂ = 4

D₂₂ = 0, p₂ + q₂ - c₂₂ = 0, р₂ +4-6 = 0, р₂ = 2

и т.д., получим: q₃=0, p₃=6, q₄= 1, q₅= -6.

Затем по формуле (6) вычисляем оценки всех свободных клеток:

D₂₁ = p₂ + q₅ - c₂₁ = 2+1-3 = 0

D₃₁ = p₃ + q₁ - c₃₁ = 6+1-2 = 5

D₃₂ = 5; D₁₃ = -3; D₁₄ = -1; D₂₄ = -2; D₁₅ = -6; D₂₅ = -4.

Находим наибольшую положительную оценку

max () = 5 =

Для найденной свободной клетки 31 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 31-11-12-22-23-33. Производим перераспределение поставок вдоль цикла пересчета

				41-r	13+r
					37-r	23+r
				r		21-r

= 21

Получаем второе базисное допустимое решение:

bj	b1 =41	b2 =50	b3 =44	b4 =30	b5=12
ai
а1 =54				*		p1 =0
a2 =60						p2 =2
a3 =63						p3 =1
	q1 =1	q2 = 4	q3 = 0	q4 = 6	q5= -1

Находим новые потенциалы, новые оценки. Наибольшую положительную оценку будет иметь свободная клетка 14. Для нее строим цикл пересчета 14-11-31-34 производим перераспределение

			20-r	r
21		21+r	30-r

r_max = 20

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

D_ij £ 0 i = 1,m; j = 1,n

Читателю не составит труда проверить, что будет оптимальным базисное допустимое решение

§8. Динамическое программирование.

Распределение капитальных вложений

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

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

Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через f_i(x_i) прирост мощности или прибыли на j-м предприятии, если оно получит x_i рублей капитальных вложений. Требуется найти такое распределение (x₁,x₂,..., x_n) капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли

z = f₁(x₁) + f₂(х₂) +... + f_n(x_n)

при ограничении по общей сумме капитальных вложений

x₁ + x₂ +... + x_n = b

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

x_j = 0, или 1, или 2, или 3,...

Функции f_j(x_j) мы считаем заданными, заметив, что их определение - довольно трудоемкая экономическая задача.

Воспользуемся методом динамического программирования для решения этой задачи.

Введем параметр состояния и определим функцию состояния. За параметр состояния x примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния F_k(x) определим как максимальную прибыль на первых k предприятиях, если они вместе получают x рублей. Параметр x может изменяться от 0 до b. Если из x рублей k-е предприятие получит x_k рублей, то каково бы ни было это значение, остальные x - x_k рублей естественно распределить между предприятиями от первого до (К-1)-го так, чтобы была получена максимальная прибыль F_k-1(x - x_k). Тогда прибыль k предприятий будет равна f_k(x_k) + F_k-1(x - x_k). Надо выбрать такое значение x_k между 0 и x, чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению

F_k(x)=max{ f _k(x _k) + F_k-1(x- x _k)}

0 £ x _k £ x

для k = 2, 3, 4,..., n. Если же k=1, то

F₁(x) = f₁(x)

Рассмотрим конкретный пример. Пусть производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения функций f_j(x_j) приведены в таблице 1, где, например, число 88 означает, что если третье предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 88 тыс. руб.

Таблица I

Прежде всего заполняем табл. 2. Значения f₂(x₂) складываем со значениями F₁(x - x₂) = f₁(x- x₂) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение . Заполняем таблицу 3.

Продолжая процесс, табулируем функции F₃(x), (x) и т.д. В табл. 6 заполняем только одну диагональ для значения x= 700. Наибольшее число на этой диагонали:

Z_max = 155 тыс. руб.,

причем четвертому предприятию должно быть выделено

х^*₄ = ₄ (700) = 300 тыс. руб.

На долю остальных трех предприятий остается 400 тыс. руб. Из табл. 5 видно, что третьему предприятию должно быть выделено

x^*₃ = ₃ (700-x^*₄) = ₃ (400) = 200 тыс. руб.

Продолжая обратный процесс, находим

x*₂ = ₂ (700 - x*₄ - x*₃) = ₂ (200) = 100 тыс. руб.

На долю первого предприятия остается

x*₁ = 700 - x*₄ - x*₃ - x*₂ = 100 тыс. руб.

Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:

x*₁ =100; x*₂ =100; x*₃ = 200; x*₄ = 300.

Оно обеспечивает производственному объединению наибольший воможный прирост прибыли 155 тыс. руб.

Студенту рекомендуется проверить выполнение равенства

f₁(x*₁) + f₂(x*₂) + f₃(x*₃) + f₄(x*₄) = z _max

Таблица 2

	x - x2	0 100 200 300 400 500 600 700
x2	F1(x - x2) f2(x2)	0 20 34 46 53 55 60 60
0		0 20* 34 46 53 55 60 60
		18 38* 52* 64 71 73 78
		29 49 63 75 82 84
		45 65* 79 91 98
		62 82* 96 108
		78 98* 112*
		90 110
		98.

Таблица 3

x	0 100 200 300 400 500 600 700
F2(x)	0 20 38 52 65 82 98 112
` (x)	0 0 100 100 300 400 500 500

Таблица 4

	x - x3	0 100 200 300 400 500 600 700
x3	F2(x - x3) f3(x3)	0 20 38 52 65 82 98 112
0		0 20 38 52 65 82 98 112
		25* 45* 63* 77 90 107 123
		41 61 79* 93 106 123
		52 72 94* 112 126
		74 94* 112* 126*
		82 102 120
		88 106
		90.

Таблица 5

x	0 100 200 300 400 500 600 700
F3(x)	0 25 45 63 79 94 112 126
(x)	0 100 100 100 200 400 400 400

Таблица 6

	x - x4	0 100 200 300 400 500 600 700
x4	F3(x - x4) f4(x4)	0 25 45 63 79 94 112 126
		155*
		125.

§9. Динамическая задача управления производством

и запасами

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

x_j - число изделий, производимых в j -й месяц;

y_j - величина запаса к началу j го месяца (это число не содержит изделий, произведенных в j -м месяце);

d_j - число изделий, которые должны быть отгружены в j -й месяц;

f_j (x_j,y_j+1) - затраты на хранение и производство изделий в j -м месяце.

Будем считать, что величины запасов к началу первого месяца y₁ и к концу последнего y_n+1 заданы.

Задача состоит в том, чтобы найти план производства

(x₁, x₂,..., x_n) (1)

компоненты которого удовлетворяют условиям материального баланса

x_j + y_j - d_j = y_j+1 j = 1,n (2)

и минимизируют суммарные затраты за весь планируемый период

(3)

причем по смыслу задачи

x_j ³ 0, y_j ³ 0, j = 1,n (4)

Прежде чем приступить к решению поставленной задачи, заметим, что для любого месяца j величина y_j+1 запаса к концу месяца должна удовлетворять ограничениям

0 £ y_j+1 £ d_j+1 + d_j+2 +... + d_n (5)

т.е. объем производимой продукции x_j на этапе j может быть настолько велик, что запас y_j+1 удовлетворяет спрос на всех последующих этапах, но не

имеет смысла иметь y_j+1 больше суммарного спроса на всех последующих этапах. Кроме того, из соотношений (2) и (4) непосредственно следует, что переменная x_j должна удовлетворять ограничениям

0 £ x_j £ d_j + y_j+1 (6)

Следует также заметить, что переменные x_j, y_j могут принимать только целые неотрицательные значения, т.е. мы получили задачу целочисленного нелинейного программирования.

Будем решать задачу (1)-(6) методом динамического программирования.

Введем параметр состояния и составим функцию состояния.

За параметр состояния x примем наличный запас в конце k -го месяца

x = y_k+1 (7)

а функцию состояния F_k(x) определим как минимальные затраты за первые k месяцев при выполнении условия (5)

(8)

где минимум берется по неотрицательным целым значениям x₁,...,x_k, удовлетворяющим условиям

x_j + y_j - d_j = y_j+1 j = 1, k-1 (9)

x_k + y_k - d_k = x (10)

Учитывая, что

(11)

и величина запаса y_k к концу (k-1) периода, как видно из уравнения (10), равна

y_k = x + d_k - x_k (12)

приходим к рекуррентному соотношению

(13)

где минимум берется по единственной переменной x_k, которая, согласно (6) может изменяться в пределах

0 £ x_k £ d_k + x (14)

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

0 £ x £ d_k+1 + d_k+2 +... + d_n (15)

а индекс k может принимать значения

k = 2, 3, 4,..., n (16)

Если k=1, то

F₁(x = y₂) = min f₁(x₁, x) (17)

x₁

где

x₁ = x + d₁ - y₁ (18)

0£ x £ d₂ + d₃ +... + d_n (19)

т.е. на начальном этапе при фиксированном уровне y₁ исходного запаса каждому значению параметра x отвечает только одно значение переменной x₁, что несколько уменьшает объем вычислений.

Применив известную вычислительную процедуру динамического программирования, на последнем шаге (при k = n) находим значение последней компоненты x_n* оптимального решения, а остальные компоненты определяем как

(20)

Рассмотрим более подробно функции затрат f_j(x_j, y_j+1) и рекуррентные соотношения. Пусть

j_j(x_j) = ax_j² + bx_j + c

j_j (x_j) - затраты на производство (закупку) x_j единиц продукции на этапе j;

h_j - затраты на хранение единицы запаса, переходящей из этапа j в этап j+1.

Тогда затраты на производство и хранение на этапе j равны

f_j(x_j, y_j+1) = j_j(x_j) + h_j y_j+1 = ax_j² + bx_j + c + h_j y_j+1. (21)

Выведенные ранее рекуррентные соотношения динамического программирования для решения задачи управления производством и запасами в нашем случае принимают вид:

(22)

где

k = 2, 3,..., n (23)

0 £ y_k+1 £ d_k+1 + d_k+1 +... + d_n (24)

0 £ x_k £ d_k + y_k+1 (25)

y_k = y_{k+1 +} d_k - x_k (26)

(27)

Если же k=1, то

(30)

(29)

(28)

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

W_k(x_k, y_k+1) = ax_j² + bx_j + c + h_ky_k+1 + F_k-1(y_k) (31)

и записать рекуррентное соотношение (22) в виде

F_k(x=y_k+1) = min W_k(x_k, y_k+1) (32)

x_k

где минимум берется по целочисленной переменной x_k, удовлетворяющей условию (25).

Пример. Рассмотрим трехэтапную систему управления запасами с дискретной продукцией и динамическим детерминированным спросом.

Пусть спрос (заявки) потребителей на нашу продукцию составляют: на первый этап d₁=3 единицы, на второй – d₂=2, на третий - d₃=4 единицы. К началу первого этапа на складе имеется только 2 единицы продукции, т.е. начальный уровень запаса равен y₁=2. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h₁=1, h₂=3, h₃=2. Затраты на производство x_j единиц продукции на j-м этапе определяются функцией

j_j(x_j) = x_j² + 5x_j + 2 (33)

т.е. а=1; b=5; с=2. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а наши общие затраты на производство и хранение за все три этапа были наименьшими.

Исходные данные задачи можно кратко записать одной строкой:

d₁ d₂ d₃ a b c h₁ h₂ h₃ y₁

1 2 4 1 5 2 1 3 2 2

Воспользовавшись рекуррентными соотношениями, последовательно вычисляем

F₁ (x = y₂), F₂ (x = y₃),..., F_k (x = y_k+1),... и соответственно находим ₁ (x= y₂), ₂ (x = y₃),..., ` _k (x = y_k+1),...

Положим k = 1. Согласно (27) имеем

(34)

Учтем, что согласно (28) параметр состояния x = у₂ может принимать целые значения на отрезке

0 у₂ d₂ + d₃

0 y₂ 2 + 4

т.е.

у₂ = 0, 1, 2, 3, 4, 5, 6.

При этом, вообще говоря, каждому значению параметра состояния должна отвечать определенная область изменения переменной x₁, характеризуемая условием (29)

0 х₁ 3 + у₂

Однако, на первом этапе объем производства х₁ не может быть меньше единицы, так как спрос d₁ = 3, а исходный запас у₁ = 2. Более того, из балансового уравнения

х₁ + у₁ - d₁ = у₂

непосредственно следует, что объем производства связан со значением параметра состояния x= у₂ соотношением

x₁ = y₂ + d₁ - y₁ = y₂ + 3 - 2 = y₂ +1 (35)

В этом и состоит особенность первого этапа. Если задан уровень запаса к началу первого этапа, то каждому значению у₂ отвечает единственное значение х₁ и потому

F₁(x = y₂) = W₁ (x₁, y₂)

Придавая у₂ различные целые значения от 0 до 6 и учитывая (35), находим