Прикладная математика (стр. 6 из 14)
Обозначим через
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.
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. Динамическое программирование.
Динамическое программирование - это вычислительный метод для решения задач управления определенной структуры. Данная задача с 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 - xk). Надо выбрать такое значение 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 тыс. руб.
Прежде всего заполняем табл. 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 тыс. руб.Продолжая обратный процесс, находим
x*2 =
2 (700 - x*4 - x*3) = 2 (200) = 100 тыс. руб.На долю первого предприятия остается
x*1 = 700 - x*4 - x*3 - x*2 = 100 тыс. руб.
Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:
x*1 =100; x*2 =100; x*3 = 200; x*4 = 300.
Оно обеспечивает производственному объединению наибольший воможный прирост прибыли 155 тыс. руб.