Контрольная работа по " Методы оптимальных решений"

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i>c_ij

Выбираем максимальную оценку свободной клетки (3;1): 4

Для этого в  перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки  «-», «+», «-».

 

	B1	B2	B3	B4	B5	Запасы
A1	8[150] [–]	3 [60] [+]	5	6	4	210
A2	5	10 [150] [–]	4 [100] [+]	8	7	250
A3	4	4	5 [70] [–]	7 [130]	3	200
A4	6	8	7	6 [90]	2 [200]	290
Потребности	150	210	170	220	200

 

Цикл приведен в таблице (3,1; 3,3; 2,3; 2,2; 1,2; 1,1).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 70. Прибавляем 70 к объемам грузов, стоящих в плюсовых клетках и вычитаем 70 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

 

	B1	B2	B3	B4	B5	Запасы
A1	8[80]	3 [130]	5	6	4	210
A2	5	10 [80]	4 [170]	8	7	250
A3	4 [70]	4	5	7 [130]	3	200
A4	6	8	7	6 [90]	2 [200]	290
Потребности	150	210	170	220	200

 

Проверим оптимальность  опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

 

	v1=8	v2=3	v3=-3	v4=11	v5=7
u1=0	8[80]	3[130]	5	6	4
u2=7	5	10[80]	4[170]	8	7
u3=-4	4[70]	4	5	7[130]	3
u4=-5	6	8	7	6[90]	2[200]

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i>c_ij

Выбираем максимальную оценку свободной клетки (2;1): 5.

Для этого в  перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки  «-», «+», «-».

 

	B1	B2	B3	B4	B5	Запасы
A1	8[80] [–]	3 [130] [+]	5	6	4	210
A2	5 [+]	10 [80] [–]	4 [170]	8	7	250
A3	4 [70]	4	5	7 [130]	3	200
A4	6	8	7	6 [90]	2 [200]	290
Потребности	150	210	170	220	200

 

Цикл приведен в таблице (2,1; 2,2; 1,2; 1,1).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е.у = min (1, 1) = 80. Прибавляем 80 к объемам грузов, стоящих в плюсовых клетках и вычитаем 80 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

 

	B1	B2	B3	B4	B5	Запасы
A1	8	3 [210]	5	6	4	210
A2	5 [80]	10	4 [170]	8	7	250
A3	4 [70]	4	5	7 [130]	3	200
A4	6	8	7	6 [90]	2 [200]	290
Потребности	150	210	170	220	200

 

Проверим оптимальность  опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

 

	v1=3	v2=3	v3=2	v4=6	v5=2
u1=0	8	3[210]	5	6	4
u2=2	5[80]	10	4[170]	8	7
u3=1	4[70]	4	5	7[130]	3
u4=0	6	8	7	6[90]	2[200]

 

Опорный план является оптимальным, так все оценки свободных  клеток удовлетворяют условию u_i + v_i≤c_ij.

Минимальные затраты  составят:

 

 4. Сетевое планирование и управление. Расчёт основных           показателей   

     Задачи контрольной работы №  4

По следующим  данным построить сеть, определить временные характеристики ее работ и событий, критический путь и его длину.

Работа	Продолжительность
(1,2)	5
(1,3)	6
(1,4)	7
(2,5)	5
(2,4)	8
(3,4)	4
(3,6)	5
(4,5)	10
(4,6)	3
(4,7)	8
(5,7)	10
(5,8)	10
(6,7)	13
(6,9)	10
(7,8)	7
(7,9)	6
(7,10)	10
(8,10)	12
(9,10)	8

 Решение:

Построим сетевую  модель задачи.

Воспроизведём график сети, проставив над каждым событием слева – ранний, а справа – поздний сроки наступления  события, внизу – резервы событий.

Критический путь: (1,2)(2,4)(4,5)(5,7)(7,8)(8,10).

Продолжительность критического пути: 52.

Проведем расчет характеристик работ и событий  сети в таблице.

 

Работа (i,j)	tij	Ранние сроки: начало tijР.Н.	Ранние сроки: окончание tijР.О.	Поздние сроки: начало tijП.Н.	Поздние сроки:окончание tijП.О.	Резервы времени:полныйtijП	Резервы времени: свободный tijС.В.	Резервы времени: событийRj
(1,2)	5	0	5	0	5	0	0	0
(1,3)	6	0	6	3	9	3	0	3
(1,4)	7	0	7	6	13	6	6	0
(2,4)	8	5	13	5	13	0	0	0
(2,5)	5	5	10	18	23	13	13	0
(3,4)	4	6	10	9	13	3	3	0
(3,6)	5	6	11	15	20	9	5	4
(4,5)	10	13	23	13	23	0	0	0
(4,6)	3	13	16	17	20	4	0	4
(4,7)	8	13	21	25	33	12	12	0
(5,7)	10	23	33	23	33	0	0	0
(5,8)	10	23	33	30	40	7	7	0
(6,7)	13	16	29	20	33	4	4	0
(6,9)	10	16	26	34	44	18	13	5
(7,8)	7	33	40	33	40	0	0	0
(7,9)	6	33	39	38	44	5	0	5
(7,10)	10	33	43	42	52	9	9	0
(8,10)	12	40	52	40	52	0	0	0
(9,10)	8	39	47	44	52	5	5	0

 

 

 

 

 

 

1. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: Высшая школа, 2001.
2. Дойхен Л. А. Математическое программирование : учеб. пособие. – Хабаровск, 2002.
3. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. - М.: Высшая школа, 1998.
4. Подиновский В.В. Математическая теория выработки решений в сложных ситуациях. Учебник. М.: МО СССР, 1982.
5. Томас Ричард. Количественные методы анализа хозяйственной деятельности. - М.: Дело и Сервис, 1999.
6. Эддоус М., Стэнсфилд Р. Методы принятия решений. М.: Аудит ЮНИТИ, 1997.
7. Математические методы принятия решений в экономике. Под ред. В.А. Колемаева. М.: «Финстатинформ», 1999.
8. Хазанова Л.Э., Математические методы в экономике. Учебное пособие. М.: изд. «ВЕК»,2001.

Воронина Наталья Борисовна, БУ (ДБС)-11, 4 курс, № 1101271