гогштошщ. Мат моделирование задача. Решение 3x 1 4x 2 x 3 max 2x 1 x 2 14 x

• Название: Решение 3x 1 4x 2 x 3 max 2x 1 x 2 14 x
• Анкор: гогштошщ
• Дата: 30.11.2022
• Размер: 24.57 Kb.
• Имя файла: Мат моделирование задача.docx
• Тип: Решение; #821982

(задача вариант 4) симплекс-метод

Решение:

3·x₁ + 4·x₂ + x₃ → max
2·x₁ + x₂ ≤ 14
x₁ + x₂ ≤ 8
x₂ + x₃ ≤ 3

Для каждого ограничения с неравенством добавляем дополнительные переменные x₄..x₆.
Перепишем ограничения в каноническом виде:
2·x₁ + x₂ + x₄ = 14
x₁ + x₂ + x₅ = 8
x₂ + x₃ + x₆ = 3

Ищем начальное базисное решение:
Ограничение 1 содержит неравенство, базисной будет добавленная дополнительная переменная x₄
Ограничение 2 содержит неравенство, базисной будет добавленная дополнительная переменная x₅
Ограничение 3 содержит неравенство, базисной будет добавленная дополнительная переменная x₆

Начальная симплекс-таблица

C	3	4	1	0	0	0	0
базис	x1	x2	x3	x4	x5	x6	b
x4	2	1	0	1	0	0	14
x5	1	1	0	0	1	0	8
x6	0	1	1	0	0	1	3

Вычисляем дельты: Δ_i = C₄·a_1i + C₅·a_2i + C₆·a_3i - C_i

Δ₁ = C₄·a₁₁ + C₅·a₂₁ + C₆·a₃₁ - C₁ = 0·2 + 0·1 + 0·0 - 3 = -3
Δ₂ = C₄·a₁₂ + C₅·a₂₂ + C₆·a₃₂ - C₂ = 0·1 + 0·1 + 0·1 - 4 = -4
Δ₃ = C₄·a₁₃ + C₅·a₂₃ + C₆·a₃₃ - C₃ = 0·0 + 0·0 + 0·1 - 1 = -1
Δ₄ = C₄·a₁₄ + C₅·a₂₄ + C₆·a₃₄ - C₄ = 0·1 + 0·0 + 0·0 - 0 = 0
Δ₅ = C₄·a₁₅ + C₅·a₂₅ + C₆·a₃₅ - C₅ = 0·0 + 0·1 + 0·0 - 0 = 0
Δ₆ = C₄·a₁₆ + C₅·a₂₆ + C₆·a₃₆ - C₆ = 0·0 + 0·0 + 0·1 - 0 = 0
Δ_b = C₄·b₁ + C₅·b₂ + C₆·b₃ - C₇ = 0·14 + 0·8 + 0·3 - 0 = 0

Симплекс-таблица с дельтами

C	3	4	1	0	0	0	0
базис	x1	x2	x3	x4	x5	x6	b
x4	2	1	0	1	0	0	14
x5	1	1	0	0	1	0	8
x6	0	1	1	0	0	1	3
Δ	-3	-4	-1	0	0	0	0

Проверяем план на оптимальность: план не оптимален, так как Δ₁ = -3 отрицательна.

Итерация 1

Определяем разрешающий столбец - столбец, в котором находится минимальная дельта: 2, Δ₂: -4
Находим симплекс-отношения Q, путём деления коэффициентов b на соответствующие значения столбца 2
В найденном столбце ищем строку с наименьшим значением Q: Q_min = 3, строка 3.
На пересечении найденных строки и столбца находится разрешающий элемент: 1
В качестве базисной переменной x₆ берём x₂.

В качестве базисной переменной x₆ берём x₂.

C	3	4	1	0	0	0	0
базис	x1	x2	x3	x4	x5	x6	b	Q
x4	2	1	0	1	0	0	14	14 / 1 = 14
x5	1	1	0	0	1	0	8	8 / 1 = 8
x2	0	1	1	0	0	1	3	3 / 1 = 3
Δ	-3	-4	-1	0	0	0	0

Из строк 1, 2 вычитаем строку 3, умноженную на соответствующий элемент в столбце 2.
Вычисляем новые дельты: Δ_i = C₄·a_1i + C₅·a_2i + C₂·a_3i - C

Δ₁ = C₄·a₁₁ + C₅·a₂₁ + C₂·a₃₁ - C₁ = 0·2 + 0·1 + 4·0 - 3 = -3
Δ₂ = C₄·a₁₂ + C₅·a₂₂ + C₂·a₃₂ - C₂ = 0·0 + 0·0 + 4·1 - 4 = 0
Δ₃ = C₄·a₁₃ + C₅·a₂₃ + C₂·a₃₃ - C₃ = 0·(-1) + 0·(-1) + 4·1 - 1 = 3
Δ₄ = C₄·a₁₄ + C₅·a₂₄ + C₂·a₃₄ - C₄ = 0·1 + 0·0 + 4·0 - 0 = 0
Δ₅ = C₄·a₁₅ + C₅·a₂₅ + C₂·a₃₅ - C₅ = 0·0 + 0·1 + 4·0 - 0 = 0
Δ₆ = C₄·a₁₆ + C₅·a₂₆ + C₂·a₃₆ - C₆ = 0·(-1) + 0·(-1) + 4·1 - 0 = 4
Δ_b = C₄·b₁ + C₅·b₂ + C₂·b₃ - C₇ = 0·11 + 0·5 + 4·3 - 0 = 12

Симплекс-таблица с обновлёнными дельтами

C	3	4	1	0	0	0	0
базис	x1	x2	x3	x4	x5	x6	b	Q
x4	2	0	-1	1	0	-1	11	14
x5	1	0	-1	0	1	-1	5	8
x2	0	1	1	0	0	1	3	3
Δ	-3	0	3	0	0	4	12

Текущий план X: [ 0, 3, 0, 11, 5, 0 ]
Целевая функция F: 3·0 + 4·3 + 1·0 + 0·11 + 0·5 + 0·0 = 12
Проверяем план на оптимальность: план не оптимален, так как Δ₁ = -3 отрицательна.

Определяем разрешающий столбец - столбец, в котором находится минимальная дельта: 1, Δ₁: -3
Находим симплекс-отношения Q, путём деления коэффициентов b на соответствующие значения столбца 1
В найденном столбце ищем строку с наименьшим значением Q: Q_min = 5, строка 2.
На пересечении найденных строки и столбца находится разрешающий элемент: 1
В качестве базисной переменной x₅ берём x₁.

C	3	4	1	0	0	0	0
базис	x1	x2	x3	x4	x5	x6	b	Q
x4	2	0	-1	1	0	-1	11	11 / 2 =  11 2
x1	1	0	-1	0	1	-1	5	5 / 1 = 5
x2	0	1	1	0	0	1	3	-
Δ	-3	0	3	0	0	4	12

Из строк 1, 3 вычитаем строку 2, умноженную на соответствующий элемент в столбце 1.
Вычисляем новые дельты: Δ_i = C₄·a_1i + C₁·a_2i + C₂·a_3i - C_i

Симплекс-таблица с обновлёнными дельтами

C	3	4	1	0	0	0	0
базис	x1	x2	x3	x4	x5	x6	b	Q
x4	0	0	1	1	-2	1	1	11 2
x1	1	0	-1	0	1	-1	5	5
x2	0	1	1	0	0	1	3	-
Δ	0	0	0	0	3	1	27

Текущий план X: [ 5, 3, 0, 1, 0, 0 ]
Целевая функция F: 3·5 + 4·3 + 1·0 + 0·1 + 0·0 + 0·0 = 27
Проверяем план на оптимальность: отрицательные дельты отсутствуют, следовательно план оптимален.

Ответ: x₁ = 5, x₂ = 3, x₃ = 0, F = 27