Контрольная работа по "Математике"

 

т.к. все Δ положительные либо 0, значит получено решение задачи.

Из таблицы следует:

Значит максимальную прибыль получим при выпуске изделий А в количестве , изделий В в количестве и доход составит ден. ед.

Задание 4.

Решить  транспортную задачу, заданную распределительной таблицей.

 

	40	20	40
30
25
15
30

 
Значение коэффициентов распределительной таблицы.

Значения	Вариант 9
	2
	4
	3
	2
	5
	2
	4
	1
	4
	5
	3
	5

Решение:

Решим задачу методом Северо-Западного угла

аi \ bj	40	20	40
30	30 2	- 4	- 3
25	10 2	15 5	- 2
15	- 4	5 1	10 4
30	- 5	- 3	30 5

Так сумма ai = 30 + 25 + 15 + 30 = 100 и сумма bj = 40 + 20 + 40 = 100, то модель закрытая.

Затраты на перевозки = 30*2 + 10*2 + 15*5 + 5*1 + 10*4 + 30*5 = 350 (ден.ед).

План построен базисный. Т.к. число занятых клеток m+n-1= 3 + 4 – 1 = 6. Проверим, получили ли мы оптимальный план с помощью метода потенциалов.

Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 2; 0 + v1 = 2; v1 = 2

u2 + v1 = 2; 2 + u2 = 2; u2 = 0

u2 + v2 = 5; 0 + v2 = 5; v2 = 5

u3 + v2 = 1; 5 + u3 = 1; u3 = -4

u3 + v3 = 4; -4 + v3 = 4; v3 = 8

u4 + v3 = 5; 8 + u4 = 5; u4 = -3

 

 

 

	v1=2	v2=5	v3=8
u1=0	2[30]	4	3
u2=0	2[10]	5[15]	2
u3=-4	4	1[5]	4[10]
u4=-3	5	3	5[30]

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

(1;2): 0 + 5 > 4; ∆12 = 0 + 5 - 4 = 1

(1;3): 0 + 8 > 3; ∆13 = 0 + 8 - 3 = 5

(2;3): 0 + 8 > 2; ∆23 = 0 + 8 - 2 = 6

max(1,5,6) = 6

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

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

	1	2	3	Запасы
1	2[30]	4	3	30
2	2[10]	5[15][-]	2 [+]	25
3	4	1[5] [+]	4[10][-]	15
4	5	3	5[30]	30
Потребности	40	20	40

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

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

	1	2	3	Запасы
1	2[30]	4	3	30
2	2[10]	5[5]	2[10]	25
3	4	1[15]	4	15
4	5	3	5[30]	30
Потребности	40	20	40

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 2; 0 + v1 = 2; v1 = 2

u2 + v1 = 2; 2 + u2 = 2; u2 = 0

u2 + v2 = 5; 0 + v2 = 5; v2 = 5

u3 + v2 = 1; 5 + u3 = 1; u3 = -4

u2 + v3 = 2; 0 + v3 = 2; v3 = 2

u4 + v3 = 5; 2 + u4 = 5; u4 = 3

	v1=2	v2=5	v3=2
u1=0	2[30]	4	3
u2=0	2[10]	5[5]	2[10]
u3=-4	4	1[15]	4
u4=3	5	3	5[30]

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

(1;2): 0 + 5 > 4; ∆12 = 0 + 5 - 4 = 1

(4;2): 3 + 5 > 3; ∆42 = 3 + 5 - 3 = 5

max(1,5) = 5

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

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

	1	2	3	Запасы
1	2[30]	4	3	30
2	2[10]	5[5] [-]	2[10][+]	25
3	4	1[15]	4	15
4	5	3 [+]	5[30][-]	30
Потребности	40	20	40

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

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

 

	1	2	3	Запасы
1	2[30]	4	3	30
2	2[10]	5	2[15]	25
3	4	1[15]	4	15
4	5	3[5]	5[25]	30
Потребности	40	20	40

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 2; 0 + v1 = 2; v1 = 2

u2 + v1 = 2; 2 + u2 = 2; u2 = 0

u2 + v3 = 2; 0 + v3 = 2; v3 = 2

u4 + v3 = 5; 2 + u4 = 5; u4 = 3

u4 + v2 = 3; 3 + v2 = 3; v2 = 0

u3 + v2 = 1; 0 + u3 = 1; u3 = 1

	v1=2	v2=0	v3=2
u1=0	2[30]	4	3
u2=0	2[10]	5	2[15]
u3=1	4	1[15]	4
u4=3	5	3[5]	5[25]

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

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

F(x) = 2*30 + 2*10 + 2*15 + 1*15 + 3*5 + 5*25  = 265

Анализ оптимального плана.

Из 1-го склада необходимо весь груз направить в 1-й магазин

Из 2-го склада необходимо груз направить в 1-й магазин (10), в 3-й магазин (15)

Из 3-го склада необходимо весь груз направить в 2-й магазин

Из 4-го склада необходимо груз направить в 2-й магазин (5), в 3-й магазин (25)

 Задание 5.

Решить транспортную задачу. Заданы мощности поставщиков аj (j = 1, 2, 3), емкости потребителей bj (j = 1, 2, 3) и матрица стоимостей перевозок единицы продукции от каждого поставщика каждому потребителю. Требуется найти план перевозок, при котором суммарные транспортные затраты будут наименьшими.

bj	25	19	21
40	5	3	6
17	2	1	2
23	7	4	8