Контрольная работа: Решение задач линейного программирования различными методами

Индивидуальное задание:

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

Таблица 10. 06 вариант транспортной задачи

Вид механизма	Себестоимость выполнения единицы работы механизма ,гр.				Количество единиц ai механизмов
	B1	B2	B3	B4
A1	11	4	3	1	15
A2	6	8	9	7	10
A 3	4	8	4	2	35
Потребности bj участков в механизмах	25	20	10	5

Исходные массивы для решения транспортной задачи по программе TRAN 2

Распечатка с ЭВМ с результатом решения

Оптимальный план транспортной задачи

x ₁₂ =15; x _­21 =5; x ₂₂ =5; x ₃₁ =20; x ₃₃ =10; x _­34 =5.

Z =15*4+5*6+5*8+20*4+10*4+5*2=260.

Анализ результатов и выводы

Решение транспортной задачи на ЭВМ автоматизирует работу по вычислению решений транспортных задач и на тестируемом входном условие получается за 3 итерации, как и при ручном вычислении.

Задание 6

Решение многоэтапных задач методом динамического программирования

Цель задания: приобрести практические навыки решения многоэтапных задач методом динамического программирования.

Индивидуальное задание.

В таблице 11 приведены значения g_i ( x ) возможного прироста продукции на четырех предприятиях в зависимости от выделенной на реконструкцию и модернизацию производства суммы x .

Распределить между предприятиями имеющиеся 100 тыс. гр., чтобы общий прирост f ₄ (100) выпуска продукции был максимальным. Для упрощения вычислений значения x принимать кратными 20 тыс. гр.

Таблица 11

Предприятие	Прирост выпуска продукции, тыс. гр.	Средства c , тыс. гр.					Номер варианта
		20	40	60	80	100
1	G1 (x)	11	21	40	54	62	6
2	G2 (x)	13	20	42	45	61
3	G3 (x)	12	22	34	55	60
4	G 4 ( x )	10	27	33	57	69

Функциональное уравнение Беллмана для рассматриваемой задачи

f ₁ ( x )= max [ g ₁ ( x )]= g ₁ ( x ) – для пер в ого предприятия;

- для остальн ых предприятий.

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

Таблица 12

Средства с, тыс. гр.	Предприятие
	1	2	3	4
	G1 (x)	G2 (x)	G3 (x)	G 4 ( x )
20	11	13	12	10
40	21	20	22	27
60	40	42	34	33
80	54	45	55	57
100	62	62	60	69

Таблица 13

X1 * (c)	20	40	60	80	100
F1 (c)	11	21	40	54	62

Таблица 14

x С	0	20	40	60	80	100	F2 (c)	X2 * (c)
20	0+13	12+0	13	0
40	0+24	12+13	22+0	25	20
60	0+42	12+24	22+13	34+0	42	0
80	0+45	12+42	22+24	34+13	55+0	55	80
100	0+67	12+45	22+42	34+24	55+3	60+0	68	80

Таблица 15

x С	0	20	40	60	80	100	F3 (c)	X3 * (c)
20	0+13	10+0	13	0
40	0+29	10+13	27+0	27	40
60	0+42	10+25	27+13	33+0	42	0
80	0+55	10+42	27+25	33+13	57+0	57	80
100	0+68	10+55	27+42	33+25	52+13	69+0	69	40

Таблица 16

С	X1 * (c)	F 1 (c)	X2 * (c)	F 2 (c)	X3 * (c)	F 3 (c)	X 4 * ( c )	F4 (c)
0	0	0	0	0	0	0	0	0
20	20	11	20	13	0	13	0	13
40	40	21	20	24	20	25	40	27
60	60	40	60	42	0	42	0	42
80	80	54	80	45	80	55	80	57
100	100	62	20	67	80	68	40	69

Итак, из таблицы 16 видно, что наибольший прирост выпуска продукции, который могут дать четыре предприятия при распределении между ними 100 тыс. грн. составляет 69 тыс. грн. При этом четвертому предприятию нужно выделить 40 тыс. грн., а остальным 60 тыс. грн.