математика. 6,7,8 мат. Вид ресурсов

• Название: Вид ресурсов
• Анкор: математика
• Дата: 04.03.2022
• Размер: 65.04 Kb.
• Имя файла: 6,7,8 мат.docx
• Тип: Документы; #382705
• страница: 3 из 3

Искомый элемент равен c₃₂ = 3. Для этого элемента запасы равны 120, потребности 170. Поскольку минимальным является 120, то вычитаем его.

x₃₂ = min(120, 170) = 120.

x	2	x	0
1	4	5	190
x	3	x	120 - 120 = 0
0	170 - 120 = 50	140

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

x₂₂ = min(190, 50) = 50.

x	2	x	0
1	4	5	190 - 50 = 140
x	3	x	0
0	50 - 50 = 0	140

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

x₂₃ = min(140, 140) = 140.

x	2	x	0
1	4	5	140 - 140 = 0
x	3	x	0
0	0	140 - 140 = 0

В результате получен первый опорный план, который является допустимым, так как все грузы от поставщиков вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.

	B1	B2	B3	Запасы
A1	5	2[180]	2	180
A2	1[110]	4[50]	5[140]	300
A3	6	3[120]	8	120
Потребности	110	350	140

Число занятых клеток таблицы (должно быть m + n – 1 = 5) 5. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно:

F(x) = 2·180 + 1·110 + 4·50 + 5·140 + 3·120 = 1730

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 2; 0 + v₂ = 2; v₂ = 2

u₂ + v₂ = 4; 2 + u₂ = 4; u₂ = 2

u₂ + v₁ = 1; 2 + v₁ = 1; v₁ = -1

u₂ + v₃ = 5; 2 + v₃ = 5; v₃ = 3

u₃ + v₂ = 3; 2 + u₃ = 3; u₃ = 1

	v1 = -1	v2 = 2	v3 = 3
u1 = 0	5	2[180]	2
u2 = 2	1[110]	4[50]	5[140]
u3 = 1	6	3[120]	8

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

(1;3): 0 + 3 > 2; ∆₁₃ = 0 + 3 - 2 = 1 > 0

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

	1	2	3	Запасы
1	5	2[180][-]	2[+]	180
2	1[110]	4[50][+]	5[140][-]	300
3	6	3[120]	8	120
Потребности	110	350	140

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

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

	B1	B2	B3	Запасы
A1	5	2[40]	2[140]	180
A2	1[110]	4[190]	5	300
A3	6	3[120]	8	120
Потребности	110	350	140

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 2; 0 + v₂ = 2; v₂ = 2

u₂ + v₂ = 4; 2 + u₂ = 4; u₂ = 2

u₂ + v₁ = 1; 2 + v₁ = 1; v₁ = -1

u₃ + v₂ = 3; 2 + u₃ = 3; u₃ = 1

u₁ + v₃ = 2; 0 + v₃ = 2; v₃ = 2

	v1 = -1	v2 = 2	v3 = 2
u1 = 0	5	2[40]	2[140]
u2 = 2	1[110]	4[190]	5
u3 = 1	6	3[120]	8

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

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

F(x) = 2·40 + 2·140 + 1·110 + 4·190 + 3·120 = 1590

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

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

Из 2-го склада необходимо груз направить 1-му потребителю (110 ед.), 2-му потребителю (190 ед.)

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