Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

_ij=p_i+q_j-c_ij , iN_m, jN_n

Положим, что p₁=0. Ос­тальные потенциалы находим из условия, что для базисных клеток _ij=0. В данном случае получаем

₁₁=0, p₁+q₁-c₁₁=0, 0+q₁-3=0, q₁=3

₂₁=0, p₂+q₁-c₂₁=0, p₂+3-2=0, p₂= -1

₂₃=0, p₂+q₃-c₂₃=0, -1+q₃-1=0, q₃=2

аналогично, получим: q₂=4, р₃=-1, q₄=5, q₅=1.

Затем вычисляем оценки всех свободных клеток:

₁₂=p₁+q₂-c₁₂=0+4-6= -2

₁₃=p₁+q₃-c₁₃=0+2-4=-2

₁₄=2; ₁₅=1; ₂₄=1; ₂₅=0; ₃₁= -4; ₃₂= -2

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

mах(_ij >0)=2=₁₄,

Для найденной свободной клетки 14 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами зве­нья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 14-34-33-23-21-11. Производим перераспределение поставок вдоль цикла пересчета:

_max=7

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

Таблица 2

Потребл Произв	b1=48	b2=30	b3=29	b4=40	b5=8
a1=40	33 3	6	4	7 3	0	p1=0
a2=45	15 2	30 3	1	3	0	p2=-1
a3=70	6	* 5	29 1	33 4	8 0	p3=1
	q1=3	q2=4	q3=0	q4=3	q5= -1

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

₁₂= -2; ₁₃= -4; ₁₅= -1; ₂₃= -2; ₂₄= -1; ₂₅= -2; ₃₁= -2; ₃₂=0. Поскольку все _ij0 решение является оптимальным:

33 0 0 7

X_оpt1 = 15 30 0 0

0 0 29 33

Однако, так как оценка клетки ₃₂=0, делаем вывод о наличие другого возможного оптимального решения. Для его нахождения строим цикл пересчета клетки 32: 32-22-21-11-14-34, производим перераспределение:

Таблица 3

Потребл Произв	b1=48	b2=30	b3=29	b4=40	b5=8
a1=40	3 3	6	4	37 3	0	p1=0
a2=45	45 2	3	1	3	0	p2=-1
a3=70	6	30 5	29 1	3 4	8 0	p3=1
	q1=3	q2=4	q3=0	q4=3	q5= -1

Находим новые потенциалы. Получаем р_i и q_j соответственно равные потенциалам первого базисного оптимального решения (см. табл. 2). Исходя из этого _max=₃₂, однако элемент с индексом 32 уже присутствует в базисе, поэтому пересчет не имеет смысла. Таким образом получаем второе и последнее базисное оптимальное решение:

3 0 0 37

X_оpt2 = 45 0 0 0

0 30 29 3

Оптимальное распределение инвестиций

Данная задача с n переменными представляется, как многошаговый процесс принятия решений. На каждом шаге определяется экстремум функции только по одной переменной.

Пусть 4 фирмы образуют объединение. Рассмотрим задачу распределения инвестиций в размере 700 тыс. рублей по этим 4 фирмам. Размер инвестиций пусть будет кратен 100 тыс. рублей. Эффект от направления i-й фирме инвестиций в размере ξ (сотен тыс. рублей) выражается функцией f_i(x_i). Приходим к задаче f_l(x_l)+f₂(x₂)+f₃(x₃)+f₄(x₄)max , где x_i - пока еще неизвестный размер х₁+х₂+х₃+х₄≤7; х₁,х₂,х₃.х₄≥0 инвестиций i-й фирме. Эта задача решается методом динамического программирования: последовательно ищется оптимальное распределение для k=2,3 и 4 фирм.

Пусть первым двум фирмам выделено ξ инвестиций. обозначим z₂(ξ) величину инвестиций 2-й фирме, при которой сумма f₂(z_2j)+f_l(ξ-z_2j), 0≤j≤ ξ максимальна, саму эту максимальную величину обозначим F₂(ξ). Далее действуем также: находим функции z₃ и F₃ и т.д. На k-ом шаге для нахождения F_k(ξ) используем основное рекуррентное соотношение: F_k(ξ)=max{f_kj(х_k)+F_(k-1)( ξ-х_k); 0 ≤ х_k ≤ ξ

xj	0	100	200	300	400	500	600	700
f1	0	28	45	65	78	90	102	113
f2	0	25	41	55	65	75	80	85
f3	0	15	25	40	56	62	73	82
f4	0	20	33	42	48	53	56	58

Таблица 1

Жирным цветом обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций по 2-м предприятиям.

ξ	0	100	200	300	400	500	600	700
F2	0	28	53	70	90	106	120	133
x2	0	0	100	100	100	200	300	300

Таблица 2

Жирным цветом обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций по 3-м предприятиям.

ξ	0	100	200	300	400	500	600	700
F2	0	28	53	70	90	106	121	135
x2	0	0	0	0	0	0	100	100

Таблица 3

Жирным цветом обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций по 4-м предприятиям.

Характеристики

Список файлов реферата