Реферат: 5 различных задач по программированию

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

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

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

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

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

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

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

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

а всеостальные - в занятых клетках. Это будет 31-11-12-22-23-33. Производим

перераспределение поставок вдоль цикла пересчета

36 4 36-r 4+r 28 12

28 32 28-r 32+r 20 40

8 r 8-r 8

= 8

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

bj b1 =36 b2 =32 b3 =40 b4 =53 b5=9

ai

а1 =40 28 12 * p1 =0

a2 =60 20 40 p2 = -1

a3 =70 8 53 9 p3 =0

q1 =2 q2 = 3 q3 = 2 q4 = 1 q5=0

Находим новые потенциалы, новые оценки.

D13 = -2; D14 = 0; D15 = 0; D21 = -3; D24 = -2; D25 = -1; D32 = -4; D33 =

-5,

т.е. все Dij £ 0 i = 1,m; j = 1,n

Общая стоимость всех перевозок для второго базисного допустимого решения:

L= 28* 2 + 12 *3 + 20 *2 + 40 + 8* 2+ 53 =241 – минимальная стоимость.

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ. РАСПРЕДЕЛЕНИЕКАПИТАЛЬНЫХ ВЛОЖЕНИЙ

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