Следует иметь в виду, что по любой транспортной таблице можно восстановить

соответствующий предпочитаемый эквивалент системы уравнений (3), (4), а в

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

какая неизвестная в соответствующем уравнении является базисной. Так как в

системе (3), (4) ровно m + n - 1 линейно независимых уравнений, то в любой

транспортной таблице должно быть m + n - 1 занятых клеток.

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

m)

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

Dij = mAij - сij i = 1,m; j = 1,n

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

Dij = pi + qj - cij i =

1,m; j = 1,n (6)

Один из потенциалов можно выбрать произвольно, так как в системе (3), (4) одно

уравнение линейно зависит от остальных. Положим, что р1 = 0.

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

. В данном случае получаем

D11 = 0, p1 + q1 - c11 = 0, 0+q1 -1 = 0, q1 = 1

D12 = 0, p1 + q2 - c12 = 0, 0+q2 -4 = 0, q2 = 4

D22 = 0, p2 + q2 - c22 = 0, р2 +4-6 = 0, р2 = 2

и т.д., получим: q3=0, p3=6, q4= 1, q5= -6.

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

D21 = p2 + q5 - c21 = 2+1-3 = 0

D31 = p3 + q1 - c31 = 6+1-2 = 5

D32 = 5; D13 = -3; D14 = -1; D24 = -2; D15 = -6; D25 = -4.

20

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

max () = 5 =

Для найденной свободной клетки 31 строим цикл пересчета - замкнутую ломаную

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

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

свободной клетке, а все остальные - в занятых клетках. Это будет 31-11-12-22-

23-33. Производим перераспределение поставок вдоль цикла пересчета

41	13			41-r	13+r			20	34
	37	23			37-r	23+r			16	44
		21		r		21-r		21

= 21

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

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

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

иметь свободная клетка 14. Для нее строим цикл пересчета 14-11-31-34

производим перераспределение

20			20-r	r			20
21	30		21+r	30-r		42	10

rmax = 20

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

пока не придем к таблице, для которой все

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

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

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

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

21

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

Динамическое программирование - это вычислительный метод для решения задач

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

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

определяется экстремум функции только от одной переменной.

Знакомство с методом динамического программирования проще всего начать с

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

одного производственного объединения или отрасли. Для определенности можно

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

Предположим, что указано n пунктов, где требуется построить или реконструировать

предприятия одной отрасли, для чего выделено b рублей. Обозначим через fi

(xi) прирост мощности или прибыли на j-м предприятии, если оно

получит xi рублей капитальных вложений. Требуется найти такое

распределение (x1,x2, ... , xn) капитальных

вложений между предприятиями, которое максимизирует суммарный прирост мощности

или прибыли

z = f1(x1) + f2(х2) + ... + fn(xn)

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

x1 + x2 + ... + xn = b

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

неотрицательные значения

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

Функции fj(xj) мы считаем заданными, заметив, что их

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

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

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

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

состояния Fk(x) определим как максимальную прибыль на первых k

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

0 до b. Если из x рублей k-е предприятие получит xk рублей, то

каково бы ни было это значение, остальные x - xk рублей естественно

распределить между предприятиями от первого до (К-1)-го так, чтобы была

получена максимальная прибыль Fk-1(x - xk). Тогда прибыль

k предприятий будет равна fk(xk) + Fk-1(x - x

k). Надо выбрать такое значение xk между 0 и x, чтобы эта сумма

была максимальной, и мы приходим к рекуррентному соотношению

Fk(x)=max{fk(xk) + Fk-1(x-xk)}

0 £ xk £ x

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

F1(x) = f1(x)

Рассмотрим конкретный пример. Пусть производственное объединение состоит

из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс.

рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения

функций fj(xj) приведены в таблице 1, где, например,

число 88 означает, что если третье предприятие получит 600 тыс. руб.

капитальных вложений, то прирост прибыли на этом предприятии составит 88 тыс.

руб.

22

Таблица I

Прежде всего заполняем табл. 2. Значения f2(x2) складываем

со значениями F1(x - x2) = f1(x- x2

) и на каждой северо-восточной диагонали находим наибольшее число, которое

отмечаем звездочкой и указываем соответствующее значение

. Заполняем таблицу 3.

Продолжая процесс, табулируем функции F3(x),

(x) и т.д. В табл. 6 заполняем только одну диагональ для значения x= 700.

Наибольшее число на этой диагонали:

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

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

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

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

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

x*3 = 3 (700-x*4) = 3 (400) = 200 тыс. руб.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14