Реферат: Прикладная математика
Находим новые потенциалы, новые оценки. Наибольшую положительную оценку будет иметь свободная клетка 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 тыс. руб.
Студенту рекомендуется проверить выполнение равенства
f1(x*1) + f2(x*2) + f3(x*3) + f4(x*4) = 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 | 0 20* 34 46 53 55 60 60 |
100 | 18 | 18 38* 52* 64 71 73 78 |
200 | 29 | 29 49 63 75 82 84 |
300 | 45 | 45 65* 79 91 98 |
400 | 62 | 62 82* 96 108 |
500 | 78 | 78 98* 112* |
600 | 90 | 90 110 |
700 | 98 | 98 . |
|
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 | 0 20 38 52 65 82 98 112 |
100 | 25 | 25* 45* 63* 77 90 107 123 |
200 | 41 | 41 61 79* 93 106 123 |
300 | 52 | 52 72 94* 112 126 |
400 | 74 | 74 94* 112* 126* |
500 | 82 | 82 102 120 |
600 | 88 | 88 106 |
700 | 90 | 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 |
0 | 0 | 126 |
100 | 30 | 142 |
200 | 52 | 146 |
300 | 76 | 155* |
400 | 90 | 153 |
500 | 104 | 149 |
600 | 116 | 141 |
700 | 125 | 125 . |
§9. Динамическая задача управления производством
|
Предприятие производит партиями некоторые изделия. Предположим, что оно получило заказы на n месяцев. Размеры заказов значительно меняются от месяца к месяцу. Поэтому иногда лучше выполнять одной партией заказы нескольких месяцев, а затем хранить изделия, пока они не потребуются, чем выполнять заказ в тот именно месяц, когда этот заказ должен быть отправлен. Необходимо составить план производства на указанные n месяцев с учетом затрат на производство и хранение изделий. Обозначим:
xj - число изделий, производимых в j -й месяц;
yj - величина запаса к началу j го месяца (это число не содержит изделий, произведенных в j -м месяце);
dj - число изделий, которые должны быть отгружены в j -й месяц;
fj (xj,yj+1) - затраты на хранение и производство изделий в j -м месяце.
Будем считать, что величины запасов к началу первого месяца y1 и к концу последнего yn+1 заданы.
Задача состоит в том, чтобы найти план производства
(x1, x2, ..., xn) (1)
компоненты которого удовлетворяют условиям материального баланса
xj + yj - dj = yj+1 j = 1,n (2)
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10