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

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

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

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

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

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

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

Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы А, 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)

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

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

3y₁+5y₂ + y₃ ³ 14, (2)

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.

Если же учесть, что второй ресурс был избыточным (т.к. x₆=13), то у₂=0, и мы приходим к системе уравнений

4y₁ + 3y₃ - 36 = 0,

5y₁ + 5y₃ - 50 = 0,

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

у₁=6, у₃=4.

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

У_опт = (6, 0, 4), (4)

причем общая (минимальная) оценка всех ресурсов равна

F_min = 1972.

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

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

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

H + Q^-1T .

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

T (t₁, 0, t₃),

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

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

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

(2)

,

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

, (3)

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

t₁ 0, t₃ 0. (4)

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

- t₁ + t₃ ≤ 27,

t₁ - t₃ ≤ 13, (5)

3 t₁ - 4 t₃ ≤ 20;

5 5

t₁≤ 208/3, (6)

t₃≤ 181/3

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

Эта задача решается графически (см. рис. 1). Решению соответствует т.А (; ).

Программа ²расшивки² имеет вид

T_опт = (; 0; );

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

Рис. 1

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

Таблица 1

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

Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в 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);

С_3,4= .

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

Первое базисное допустимое решение легко построить по правилу ²северо-западного угла², которое состоит в том, чтобы на каждом этапе мы максимально загружаем «северо-западную клеточку»:

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

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

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

m )

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

D_ij = mA_ij - с_ij ,

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

D_ij = p_i + q_j - c_ij, . [2] (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. Производим перераспределение поставок вдоль цикла пересчета, максимально загружая клетку 31.

				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, .

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

R_min = 24*4 + 30*0 + 4*6 + 44*2 + 41*2 + 22*5 = 460.

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

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

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

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

P(Х)= 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) рублей естественно распределить между предприятиями от первого до (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) = { f _k(x _k) + F_k-1(x- x _k)}

для 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 тыс. руб.

Таблица 1

xj
f1(x1)
f2(x2)
f3(x3)
f4(x4)

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

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

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

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

тыс.руб.

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

тыс.руб.

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

тыс.руб

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

тыс.руб.

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

Xопт=(100; 100; 200; 300).

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

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

Таблица 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 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
`	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 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
	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.

Дата добавления: 2015-06-04