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

Решение задачи линейного программирования симплекс-методом. Условие задачи: Найти максимум целевой функции: \[ L(x) = 6x_1 + 6x_2 + 8x_3 \to max \] при ограничениях: \[ \begin{cases} 9x_1 + 3x_2 + 3x_3 \le 1053 \\ 15x_1 + 9x_2 + 10x_3 \le 1170 \\ x_1 + 5x_2 + 5x_3 \le 325 \end{cases} \] при \( x_j \ge 0 \). 1. Приведем задачу к каноническому виду, введя дополнительные балансовые переменные \( x_4, x_5, x_6 \): \[ \begin{cases} 9x_1 + 3x_2 + 3x_3 + x_4 = 1053 \\ 15x_1 + 9x_2 + 10x_3 + x_5 = 1170 \\ x_1 + 5x_2 + 5x_3 + x_6 = 325 \end{cases} \] Целевая функция: \( L(x) - 6x_1 - 6x_2 - 8x_3 = 0 \). 2. Составим первую симплекс-таблицу: Базис | \( x_1 \) | \( x_2 \) | \( x_3 \) | \( x_4 \) | \( x_5 \) | \( x_6 \) | Решение (B) --- | --- | --- | --- | --- | --- | --- | --- \( x_4 \) | 9 | 3 | 3 | 1 | 0 | 0 | 1053 \( x_5 \) | 15 | 9 | 10 | 0 | 1 | 0 | 1170 \( x_6 \) | 1 | 5 | 5 | 0 | 0 | 1 | 325 \( L \) | -6 | -6 | -8 | 0 | 0 | 0 | 0 3. Выбираем разрешающий столбец по наибольшему по модулю отрицательному коэффициенту в строке \( L \). Это столбец \( x_3 \) (коэффициент -8). Находим разрешающую строку по минимальному отношению \( B / x_3 \): Для \( x_4 \): \( 1053 / 3 = 351 \) Для \( x_5 \): \( 1170 / 10 = 117 \) Для \( x_6 \): \( 325 / 5 = 65 \) Минимум 65, значит разрешающий элемент — 5 (строка \( x_6 \)). 4. Выполняем итерацию (заменяем \( x_6 \) на \( x_3 \) в базисе): Базис | \( x_1 \) | \( x_2 \) | \( x_3 \) | \( x_4 \) | \( x_5 \) | \( x_6 \) | Решение (B) --- | --- | --- | --- | --- | --- | --- | --- \( x_4 \) | 8.4 | 0 | 0 | 1 | 0 | -0.6 | 858 \( x_5 \) | 13 | -1 | 0 | 0 | 1 | -2 | 520 \( x_3 \) | 0.2 | 1 | 1 | 0 | 0 | 0.2 | 65 \( L \) | -4.4 | 2 | 0 | 0 | 0 | 1.6 | 520 5. В строке \( L \) остался отрицательный коэффициент -4.4 в столбце \( x_1 \). Находим разрешающую строку: Для \( x_4 \): \( 858 / 8.4 \approx 102.1 \) Для \( x_5 \): \( 520 / 13 = 40 \) Для \( x_3 \): \( 65 / 0.2 = 325 \) Минимум 40, разрешающий элемент — 13 (строка \( x_5 \)). 6. Выполняем итерацию (заменяем \( x_5 \) на \( x_1 \)): Базис | \( x_1 \) | \( x_2 \) | \( x_3 \) | \( x_4 \) | \( x_5 \) | \( x_6 \) | Решение (B) --- | --- | --- | --- | --- | --- | --- | --- \( x_4 \) | 0 | 0.646 | 0 | 1 | -0.646 | 0.692 | 521.5 \( x_1 \) | 1 | -0.077 | 0 | 0 | 0.077 | -0.154 | 40 \( x_3 \) | 0 | 1.015 | 1 | 0 | -0.015 | 0.231 | 57 \( L \) | 0 | 1.66 | 0 | 0 | 0.338 | 0.923 | 696 Так как в строке \( L \) больше нет отрицательных коэффициентов, оптимальное решение найдено. Ответ: \[ x_1 = 40 \] \[ x_2 = 0 \] \[ x_3 = 57 \] Максимальное значение функции: \[ L_{max} = 6 \cdot 40 + 6 \cdot 0 + 8 \cdot 57 = 240 + 456 = 696 \]