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

МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

Примерная контрольная работа для студентов факультета ЭУиФ

1.  Линейное прогграммирование.

Фирма "ИнтерКоннект" производит 4 типа Internet-маршрутизаторов: Backbone, Subnet, Local, T3000. В таблице приведены затраты труда на производство, стоимость производства, спрос и прибыль для каждого маршрутизатора.

Вид маршрутизатора	Число часов труда / ед.	Стоимость, у. е./ед.	Максимальный ежедневный спрос	Прибыль с продажи единицы
Backbone	0,5	33	15	10
Subnet	1	38	20	9
Local	2	45	13	11
T3000	1,5	50	15	15

Фирма располагает ежедневным бюджетом в 1600 у. е. и 50 часами человеко-труда. Необходимо сформулировать такой производственный план, чтобы обеспечить максимальную ежедневную прибыль при условии, что фирма взяла на себя обязательства произвести не менее 10 единиц маршрутизаторов Backbone.

2.  Линейное программирование. Графический метод.

.

3.  Линейное программирование. Симплекс-метод.

С помощью симплекс-метода решить задачу линейного программирования:

4.  Линейное программирование. Двойственные задачи.

Решить задачу линейного программирования; составить задачу, двойственную данной, и также найти её решение:

5.  Решить задачу дробно-линейного программирования:

6.  Целочисленное линейное программирование.

Найти оптимальное решение задачи целочисленного линейного программирования:

- целые числа.

7.  Транспортная задача.

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

Поставщики	Мощности поставщиков	Потребители и их спрос
		F	G	H	I
		50	50	80	60
A	40	5	3	1	8
B	30	4	2	9	8
C	50	9	4	2	7
D	80	3	2	4	5
E	50	4	6	1	5

8.  Теория игр.

Зная платежную матрицу:

,

определить нижнюю и верхнюю цены игры и найти решение игры.

9.  Взаимозачет долгов предприятий.

Взаимные долги 6 предприятий представлены в таблице (в млн. руб.):

Предприятия	1	2	3	4	5	6
1	0	-30	50	-60	-125	100
2	30	0	130	70	-10	-20
3	-50	-130	0	-60	80	40
4	60	-70	60	0	-100	150
5	125	10	-80	100	0	-200
6	-100	20	-40	-150	200	0

Найти сумму всех взаимных долгов, сальдо каждого предприятия, суммарное абсолютное сальдо системы, произвести взаимозачет долгов и составить новую таблицу.

10. Сетевое планирование.

По данным таблицы:

№	Работа ( i, j )	Минимальная продолжитель­ ность работы (сут.) a ( i, j )	Нормальная продолжитель­ ность работы (сут.) t ( i, j )	Максимальная продолжитель­ ность работы (сут.) b ( i, j )	Коэффициент затрат на ускорение работ (руб./ сут.) h ( i, j )	Нормаль­ная cтоимость работы (руб.) C ( i , j )
1	(0,1)	2	5	6	3	70
2	(0,4)	3	4	8	8	40
3	(1,2)	4	5	12	10	140
4	(1,5)	6	8	9	4	20
5	(2,8)	3	4	10	5	55
6	(8,3)	4	9	12	3	40
7	(2,3)	5	7	10	3	50
8	(3,7)	2	6	8	6	60
9	(7,9)	5	12	15	4	100
10	(4,5)	6	9	12	5	100
11	(4,6)	10	16	20	8	150
12	(5,3)	2	3	4	9	50
13	(5,6)	2	3	6	15	100
14	(6,7)	6	9	10	4	60

необходимо:

1)  построить и упорядочить сетевой график,

2)  для нормальной продолжительности всех работ определить: сроки свершения событий и их резервы времени, критический путь и его время, временные параметры работ, найти стоимость проекта,

3)  найти коэффициенты напряженности работ и классифицировать работы по зонам (необязательное задание),

4)  за счет свободных резервов времени работ определить наименьшую возможную стоимость проекта, построить новый сетевой график и определить все критические пути в нем,

5)  провести оптимизацию сетевого графика методом "время-стоимость" с целью уменьшения общего времени выполнения проекта, найти новую стоимость проекта, построить график оптимальной зависимости стоимости проекта от его продолжительности.

11. Нелинейное программирование.

Найти геометрически наибольшее значение функции при ограничениях:

12. Решить задачу целочисленного линейного программирования методом Беллмана:

z =4x1+ x2+4 x3+ 4x4+3 x5 ® max

2x1+ x2+2 x3+ x4+ 2x5 £ 22

0 £ x1 £4; 0 £ x2 £5;

0 £ x3 £6; 0 £ x4 £4

0 £ x5 £4