2 Двойственная задача

Для задачи, приведенной в задании 1:

1) составить двойственную задачу;

2) привести оптимальный план двойственной задачи, вычислить значение целевой функции;

3) сделать вывод о найденном решении прямой задачи;

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

Составим задачу, двойственную данной:

Система ограничений:

Ее решение:

y₁=3/4, y₂=31/4, y₃=0, y₄=0, y₅=0.

F = 1093.

Проверка:

Значения целевых функций прямой и двойственной задачи совпадают.

По второй теореме двойственности следует:

Так как y₁ = 3/4 > 0, значит данный ресурс будет использован полностью.

Так как y₂ = 31/4 > 0, значит данный ресурс будет использован полностью.

Так как y₃ = 0, значит данный ресурс избыточен.

По третьей теореме двойственности:

При изменении первого ресурса (Т1 = 238) на единицу, значение целевой функции изменяется на Y₁ = 3/4.

При изменении второго ресурса (Т2 = 118) на единицу, значение целевой функции изменяется на Y₂ = 31/4.

При изменении третьего ресурса (Т3 = 123) на единицу, значение целевой функции не изменится.

3 Задача о распределении капиталовложений динамического программирования

Решить задачу о распределении капиталовложений динамического программирования (1 вариант).

Для реконструкции и модернизации производства на n предприятиях выделены денежные средства с. По каждому из n предприятий известен возможный прирост g_i(x) (i = 1..n) выпуска продукции в зависимости от выделенной ему суммы x (0 ≤ x ≤ c). Требуется:

1. распределить средства с между предприятиями так, чтобы суммарный прирост выпуска продукции на всех n предприятиях достиг максимальной величины f_n(c) (этот основной результат получить для с=100 млн. руб. и n=4);

2. используя выполненное решение основной задачи, найти оптимальное распределение:

   1. 100 млн. руб. между тремя предприятиями;

   2. 80 млн. руб. между тремя предприятиями.

Исходные данные представлены в таблице 3.

Таблица 3

	Предприятия
	№1	№2	№3	№4
	Z1(u1)	Z2(u1)	Z3(u1)	Z4(u1)
20	10	12	11	16
40	31	26	36	37
60	42	36	45	46
80	62	54	60	63
100	76	78	77	80

Пошаговое решение представлено в таблицах 4-7.

Таблица 4

X3	U4	Z4	F4
0	0	0	0
20	20	13	13
40	40	27	27
60	60	44	44
80	80	69	69
100	100	73	73

Таблица 5

X2	U3	X3	Z3	F4	Z3+F4	F3
0	0	0	0	0	0	0
20	0	20	0	13	13	-
	20	0	16	0	16	16
40	0	40	0	27	27	-
	20	20	16	13	29	-
	40	0	32	0	32	32
60	0	60	0	44	44	-
	20	40	16	27	43	-
	40	20	32	13	45	45
	60	0	40	0	40	-
80	0	80	0	69	69	69
	20	60	16	44	60	-
	40	40	32	27	59	-
	60	20	40	13	53	-
	80	0	57	0	57	-
100	0	100	0	73	73	-
	20	80	16	69	85	85
	40	60	32	44	76	-
	60	40	40	27	67	-
	80	20	57	13	70	-
	100	0	70	0	70	-

Таблица 6

X1	U2	X2	Z2	F3	Z2+F3	F2
0	0	0	0	0	0	0
20	0	20	0	16	16	16
	20	0	11	0	11	-
40	0	40	0	32	32	32
	20	20	11	16	27	-
	40	0	19	0	19	-
60	0	60	0	45	45	45
	20	40	11	32	43	-
	40	20	19	16	35	-
	60	0	30	0	30	-
80	0	80	0	69	69	69
	20	60	11	45	56	-
	40	40	19	32	51	-
	60	20	30	16	46	-
	80	0	44	0	44	-
100	0	100	0	85	85	85
	20	80	11	69	80	-
	40	60	19	45	64	-
	60	40	30	32	62	-
	80	20	44	16	60	-
	100	0	59	0	59	-

Таблица 7

X0	U1	X1	Z1	F2	Z1+F2	F1
0	0	0	0	0	0	0
20	0	20	0	16	16	16
	20	0	9	0	9	-
40	0	40	0	32	32	32
	20	20	9	16	25	-
	40	0	18	0	18	-
60	0	60	0	45	45	45
	20	40	9	32	41	-
	40	20	18	16	34	-
	60	0	24	0	24	-
80	0	80	0	69	69	69
	20	60	9	45	54	-
	40	40	18	32	50	-
	60	20	24	16	40	-
	80	0	38	0	38	-
100	0	100	0	85	85	85
	20	80	9	69	78	-
	40	60	18	45	63	-
	60	40	24	32	56	-
	80	20	38	16	54	-
	100	0	50	0	50	-

Оптимальный план распределения кредита - 100 млн. 4 предприятия:

U₁^* = 0; X₁ = 100;

U₂^* = 0; X₂ = 100;

U₃^* = 20; X₃ = 80;

U₄^* = 80.

При кредите в 100 млн. денежных единиц на три предприятия:

U₂^* = 0; X₁ = 100;

U₃^* = 20; X₂ = 80;

U₄^* = 80.

При кредите в 80 млн. денежных единиц на три предприятия:

U₂^* = 0; X₁ = 80;

U₃^* =0; X₂ = 80;

U₄^* = 80.