Реферат: Прикладная математика
Следует иметь в виду, что по любой транспортной таблице можно восстановить соответствующий предпочитаемый эквивалент системы уравнений (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.
|
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
Получаем второе базисное допустимое решение:
|
|
b1 =41 |
b2 =50 |
b3 =44 |
b4 =30 |
b5=12 |
|
|
|
||||||
|
а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 |
bj
aiНаходим новые потенциалы, новые оценки. Наибольшую положительную оценку будет иметь свободная клетка 14. Для нее строим цикл пересчета 14-11-31-34 производим перераспределение
| 20 | 20-r | r | 20 | ||||
|
|
30 | 21+r | 30-r | 42 | 10 |
21rmax = 20
и получаем третье базисное допустимое решение. Продолжаем процесс до те пор, пока не придем к таблице, для которой все
 |
 |
Dij £ 0 i = 1,m; j = 1,n
Читателю не составит труда проверить, что будет оптимальным базисное допустимое решение
§8. Динамическое программирование.
|
Динамическое программирование - это вычислительный метод для решения задач управления определенной структуры. Данная задача с n переменными представляется как многошаговый процесс принятия решений. На каждом шаге определяется экстремум функции только от одной переменной.
Знакомство с методом динамического программирования проще всего начать с рассмотрения нелинейной задачи распределения ресурсов между предприятиями одного производственного объединения или отрасли. Для определенности можно считать, что речь идет о распределении капитальных вложений.
Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через fi(xi) прирост мощности или прибыли на j-м предприятии, если оно получит xi рублей капитальных вложений. Требуется найти такое распределение (x1,x2, ... , xn) капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
