Помощь с контрольной работой по методам оптимальных решений в ИМТП, пример оформления

Контрольная работа №3 Вариант 1 Для строительства четырех объектов используется кирпич, который изготавливается на трех заводах, ежедневная выработка которых составляет 100, 150 и 50 тыс. штук. Ежедневные потребности в кирпиче на каждом из строящихся объектов равны 70, 80, 60 и 85 тыс. штук. Известна матрица тарифов (в рублях) на перевозку 1 тыс. кирпичей с каждого завода к каждому из объектов.

6	7	3	5
1	2	5	6
8	10	20	1

Составить план перевозок кирпича с заводов на объекты, при котором суммарная стоимость перевозок минимальна; установить, единственный ли он. Подсчитать суммарную стоимость перевозок. Решение: Целевая функция: 6x₁₁ + 7x₁₂ + 3x₁₃ + 5x₁₄ + 1x₂₁ + 2x₂₂ + 5x₂₃ + 6x₂₄ + 8x₃₁ + 10x₃₂ + 20x₃₃ + 1x₃₄ → min Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 100 + 150 + 50 = 300 ∑b = 70 + 80 + 60 + 85 = 295 Суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 5.

6	7	3	5	0	100
1	2	5	6	0	150
8	10	20	1	0	50
70	80	60	85	5

  Используя метод северо-западного угла, построим первый опорный план транспортной задачи. План начинается заполняться с верхнего левого угла. Искомый элемент равен c₁₁=6. Для этого элемента запасы равны 100, потребности 70. Поскольку минимальным является 70, то вычитаем его. x₁₁ = min(100,70) = 70.

6	7	3	5	0	100 — 70 = 30
x	2	5	6	0	150
x	10	20	1	0	50
70 — 70 = 0	80	60	85	5	0

Искомый элемент равен c₁₂=7. Для этого элемента запасы равны 30, потребности 80. Поскольку минимальным является 30, то вычитаем его. x₁₂ = min(30,80) = 30.

6	7	x	x	x	30 — 30 = 0
x	2	5	6	0	150
x	10	20	1	0	50
0	80 — 30 = 50	60	85	5	0

Искомый элемент равен c₂₂=2. Для этого элемента запасы равны 150, потребности 50. Поскольку минимальным является 50, то вычитаем его. x₂₂ = min(150,50) = 50.

6	7	x	x	x	0
x	2	5	6	0	150 — 50 = 100
x	x	20	1	0	50
0	50 — 50 = 0	60	85	5	0

Искомый элемент равен c₂₃=5. Для этого элемента запасы равны 100, потребности 60. Поскольку минимальным является 60, то вычитаем его. x₂₃ = min(100,60) = 60.

6	7	x	x	x	0
x	2	5	6	0	100 — 60 = 40
x	x	x	1	0	50
0	0	60 — 60 = 0	85	5	0

Искомый элемент равен c₂₄=6. Для этого элемента запасы равны 40, потребности 85. Поскольку минимальным является 40, то вычитаем его. x₂₄ = min(40,85) = 40.

6	7	x	x	x	0
x	2	5	6	x	40 — 40 = 0
x	x	x	1	0	50
0	0	0	85 — 40 = 45	5	0

Искомый элемент равен c₃₄=1. Для этого элемента запасы равны 50, потребности 45. Поскольку минимальным является 45, то вычитаем его. x₃₄ = min(50,45) = 45.

6	7	x	x	x	0
x	2	5	6	x	0
x	x	x	1	0	50 — 45 = 5
0	0	0	45 — 45 = 0	5	0

Искомый элемент равен c₃₅=0. Для этого элемента запасы равны 5, потребности 5. Поскольку минимальным является 5, то вычитаем его. x₃₅ = min(5,5) = 5.

6	7	x	x	x	0
x	2	5	6	x	0
x	x	x	1	0	5 — 5 = 0
0	0	0	0	5 — 5 = 0	0

 

6[70]	7[30]	3	5	0	100
1	2[50]	5[60]	6[40]	0	150
8	10	20	1[45]	0[5]	50
70	80	60	85	5

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n — 1 = 7. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 6*70 + 7*30 + 2*50 + 5*60 + 6*40 + 1*45 + 0*5 = 1315. Данный план не единственный. Его можно улучшить. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0. u₁ + v₁ = 6; 0 + v₁ = 6; v₁ = 6 u₁ + v₂ = 7; 0 + v₂ = 7; v₂ = 7 u₂ + v₂ = 2; 7 + u₂ = 2; u₂ = -5 u₂ + v₃ = 5; -5 + v₃ = 5; v₃ = 10 u₂ + v₄ = 6; -5 + v₄ = 6; v₄ = 11 u₃ + v₄ = 1; 11 + u₃ = 1; u₃ = -10 u₃ + v₅ = 0; -10 + v₅ = 0; v₅ = 10

	v1=6	v2=7	v3=10	v4=11	v5=10
u1=0	6[70]	7[30]	3	5	0
u2=-5	1	2[50]	5[60]	6[40]	0
u3=-10	8	10	20	1[45]	0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij (1;3): 0 + 10 > 3; ∆₁₃ = 0 + 10 — 3 = 7 (1;4): 0 + 11 > 5; ∆₁₄ = 0 + 11 — 5 = 6 (1;5): 0 + 10 > 0; ∆₁₅ = 0 + 10 — 0 = 10 (2;5): -5 + 10 > 0; ∆₂₅ = -5 + 10 — 0 = 5 max(7,6,10,5) = 10 Выбираем максимальную оценку свободной клетки (1;5): 0 Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

6[70]	7[30][-]	3	5	0[+]	100
1	2[50][+]	5[60]	6[40][-]	0	150
8	10	20	1[45][+]	0[5][-]	50
70	80	60	85	5

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

6[70]	7[25]	3	5	0[5]	100
1	2[55]	5[60]	6[35]	0	150
8	10	20	1[50]	0	50
70	80	60	85	5

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0. u₁ + v₁ = 6; 0 + v₁ = 6; v₁ = 6 u₁ + v₂ = 7; 0 + v₂ = 7; v₂ = 7 u₂ + v₂ = 2; 7 + u₂ = 2; u₂ = -5 u₂ + v₃ = 5; -5 + v₃ = 5; v₃ = 10 u₂ + v₄ = 6; -5 + v₄ = 6; v₄ = 11 u₃ + v₄ = 1; 11 + u₃ = 1; u₃ = -10 u₁ + v₅ = 0; 0 + v₅ = 0; v₅ = 0

	v1=6	v2=7	v3=10	v4=11	v5=0
u1=0	6[70]	7[25]	3	5	0[5]
u2=-5	1	2[55]	5[60]	6[35]	0
u3=-10	8	10	20	1[50]	0

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij (1;3): 0 + 10 > 3; ∆₁₃ = 0 + 10 — 3 = 7 (1;4): 0 + 11 > 5; ∆₁₄ = 0 + 11 — 5 = 6 max(7,6) = 7 Выбираем максимальную оценку свободной клетки (1;3): 3 Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

6[70]	7[25][-]	3[+]	5	0[5]	100
1	2[55][+]	5[60][-]	6[35]	0	150
8	10	20	1[50]	0	50
70	80	60	85	5

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

6[70]	7	3[25]	5	0[5]	100
1	2[80]	5[35]	6[35]	0	150
8	10	20	1[50]	0	50
70	80	60	85	5

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0. u₁ + v₁ = 6; 0 + v₁ = 6; v₁ = 6 u₁ + v₃ = 3; 0 + v₃ = 3; v₃ = 3 u₂ + v₃ = 5; 3 + u₂ = 5; u₂ = 2 u₂ + v₂ = 2; 2 + v₂ = 2; v₂ = 0 u₂ + v₄ = 6; 2 + v₄ = 6; v₄ = 4 u₃ + v₄ = 1; 4 + u₃ = 1; u₃ = -3 u₁ + v₅ = 0; 0 + v₅ = 0; v₅ = 0

	v1=6	v2=0	v3=3	v4=4	v5=0
u1=0	6[70]	7	3[25]	5	0[5]
u2=2	1	2[80]	5[35]	6[35]	0
u3=-3	8	10	20	1[50]	0

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij (2;1): 2 + 6 > 1; ∆₂₁ = 2 + 6 — 1 = 7 (2;5): 2 + 0 > 0; ∆₂₅ = 2 + 0 — 0 = 2 max(7,2) = 7 Выбираем максимальную оценку свободной клетки (2;1): 1 Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

6[70][-]	7	3[25][+]	5	0[5]	100
1[+]	2[80]	5[35][-]	6[35]	0	150
8	10	20	1[50]	0	50
70	80	60	85	5

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

6[35]	7	3[60]	5	0[5]	100
1[35]	2[80]	5	6[35]	0	150
8	10	20	1[50]	0	50
70	80	60	85	5

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0. u₁ + v₁ = 6; 0 + v₁ = 6; v₁ = 6 u₂ + v₁ = 1; 6 + u₂ = 1; u₂ = -5 u₂ + v₂ = 2; -5 + v₂ = 2; v₂ = 7 u₂ + v₄ = 6; -5 + v₄ = 6; v₄ = 11 u₃ + v₄ = 1; 11 + u₃ = 1; u₃ = -10 u₁ + v₃ = 3; 0 + v₃ = 3; v₃ = 3 u₁ + v₅ = 0; 0 + v₅ = 0; v₅ = 0

	v1=6	v2=7	v3=3	v4=11	v5=0
u1=0	6[35]	7	3[60]	5	0[5]
u2=-5	1[35]	2[80]	5	6[35]	0
u3=-10	8	10	20	1[50]	0

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij (1;4): 0 + 11 > 5; ∆₁₄ = 0 + 11 — 5 = 6 Выбираем максимальную оценку свободной клетки (1;4): 5 Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

6[35][-]	7	3[60]	5[+]	0[5]	100
1[35][+]	2[80]	5	6[35][-]	0	150
8	10	20	1[50]	0	50
70	80	60	85	5

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

6[0]	7	3[60]	5[35]	0[5]	100
1[70]	2[80]	5	6	0	150
8	10	20	1[50]	0	50
70	80	60	85	5

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0. u₁ + v₁ = 6; 0 + v₁ = 6; v₁ = 6 u₂ + v₁ = 1; 6 + u₂ = 1; u₂ = -5 u₂ + v₂ = 2; -5 + v₂ = 2; v₂ = 7 u₁ + v₃ = 3; 0 + v₃ = 3; v₃ = 3 u₁ + v₄ = 5; 0 + v₄ = 5; v₄ = 5 u₃ + v₄ = 1; 5 + u₃ = 1; u₃ = -4 u₁ + v₅ = 0; 0 + v₅ = 0; v₅ = 0

	v1=6	v2=7	v3=3	v4=5	v5=0
u1=0	6[0]	7	3[60]	5[35]	0[5]
u2=-5	1[70]	2[80]	5	6	0
u3=-4	8	10	20	1[50]	0

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij. Минимальные затраты составят: F(x) = 3*60 + 5*35 + 0*5 + 1*70 + 2*80 + 1*50 = 635