Задачи динамического программирования

Дисциплина Методы оптимизации

Вид работы	Контрольная
ВУЗ	Финансовый университет
Дата	13.05.2018
Преподаватель	Александрова И.А.
Вариант	3

Тема 3. Транспортная задача.
Задача  №  3.  Найти  решение  транспортной  задачи,  если  из  А2 в  В4 перевозки  запрещены,  из  А1 в  В3 должно  быть  доставлено  не  менее  n  единиц груза, а из А3
в В1 не более m единиц груза.

	40	40	30	50
40	3	1	5	4
60	6	1	2	3
60	4	4	5	7

n=20, m=15


Тема 4. Метод искусственного базиса.
Задача  №  4.  Решить  задачу  линейного  программирования  методом искусственного базиса.
z=2-5x5-4x4 = min
x3-x1-2x5=23
x2-x4+x5=18
2x3-x1+x4-3x5=52
xi≥0


Тема 5. Задачи целочисленного программирования
Задача № 5. Решить задачу целочисленного программирования  
a) графическим способом; 
б) методом Гомори; 
в)  дать  геометрическую  интерпретацию  введения  дополнительного
ограничения.
z=3x+4y+3= max
y-x-2≤0
x+y-9≤0

Тема 6. Задачи многокритериальной оптимизации
Задача № 6. Найти компромиссное решение многокритериальной за-дачи оптимизации методом идеальной точки.
f1=6x1+x2=max
f2=4x1+6x2=max
x1+x2<=20
x1≤12, x2≤15

Тема 7. Задачи динамического программирования
Задача №  7.  Планируется  работа  двух  предприятий  на  n   лет. Начальные  ресурсы  равны s0.  Средства  x ,  вложенные  в  1-е  предприятие  в  начале года,  дают  в  конце  года  прибыль  f1(x) ,  и  возвращаются  в  размере  g1(x) . Средства  y ,  вложенные  в  2-е  предприятие  в  начале  года,  дают  в  конце  года прибыль  f2(y)   и  возвращаются  в  размере  g2(y)  В  конце  года  возвращенные  средства  заново  перераспределяются между  отраслями. Определить  оптимальный план распределения средств и найти максимальную прибыль.
s0=3000
n=4
f1(x)=0.7x; g1(x)=0,2x
f2(y)=0.6y; g2(y)=0,4y

Задача №  8.  Планируется  работа  трех  предприятий  на  1  год.    Начальные  средства  равны s2=4  тыс.  у.е.,  а  вложения  кратны  1  тыс.  у.е.  При  этом x  тыс.  у.е.,  вложенные  в  k -е  предприятие  в  начале  года,    дают  в  конце  года прибыль  fk(x).  Определить  оптимальный  план  распределения  средств  и найти максимальную прибыль.
x	f1(x)	f2(x)	f3(x)
1	5	4	5
2	9	8	10
3	13	14	15
4	20	19	18

Тема 7. Элементы теории игр
Задача  №  9.  Игра  задана  платежной  матрицей  A .  Составить  соответствующую  игрокам  пару  двойственных  задач,  найти  оптимальные  стратегии и цену игры.
1	3	5
3	1	3
5	3	1