Используя обычный симплекс метод Найти min z = 4x1-2x2+x3 x1-2x2+2x3>=9, x1-2x2>=5,…
- User
Используя обычный симплекс метод Найти min z = 4x1-2x2+x3 x1-2x2+2x3>=9, x1-2x2>=5, x1-2x3>=-3, x1+x2+2x3>=3, x1+x2-x3<=0, x1+x2<=2, x1+x3<=6, 2x1-x2+x3<=12, 2x1-x2-2x3<=6, x1+x2-x3>=-3, x1>=0, x3>=0.
- Assistant
Приведем систему к каноническому виду:
x1 - 2x2 + 2x3 + x4 = 9 x1 - 2x2 + x5 = 5 x1 - 2x3 + x6 = -3 x1 + x2 + 2x3 + x7 = 3 x1 + x2 - x3 - x8 = 0 x1 + x2 + x9 = 2 x1 + x3 + x10 = 6 2x1 - x2 + x3 + x11 = 12 2x1 - x2 - 2x3 + x12 = 6 x1 + x2 - x3 - x13 = -3
Запишем симплекс таблицу: Базис | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | св.член ------+----+----+----+----+----+----+----+----+----+-----+-----+-----+-------- x4 | 1 | 0 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 9 x5 | 1 | -2 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 5 x6 | 1 | 0 | -2 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -3 x7 | 1 | 1 | 2 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 3 x8 | 1 | 1 | -1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | -1 | 0 x9 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 2 x10 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 6 x11 | 2 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 12 x12 | 2 | -1 | -2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 6 x2 | 1 | 1 | -1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0
Первый шаг симплекс метода - найдем разрешающую строку. Для этого выберем переменную, при которой свободный коэффициент отрицательный, и найдем минимальное отношение свободного коэффициента к соответствующему элементу этой переменной в строках, где элемент положительный.
x6 имеет отрицательный свободный коэффициент -3. Минимальное отношение (9/2) получится при выборе x9. Таким образом, разрешающая строка - x9.
По найденной разрешающей строке составим разрешающий столбец. Разрешающий элемент - элемент столбца x9 и строки x9.
Базис | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | св.член ------+----+----+----+----+----+----+----+----+-----+-----+-----+-----+-------- x4 | 1 | 0 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 9 x5 | 1 | -2 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 5 x2 | 1 | 1 | -1 | 0 | 0 | 0 | 0 | 1 | -1/2| 0 | 0 | 0 | 1/2 | 1 x7 | 0 | 2 | 4 | 0 | 0 | 0 | 1 | 0 | 1/2 | 0 | 0 | 0 | 0 | -1 x8 | 0 | 2 | -3 | 0 | 0 | 0 | -1 | -1 | 1/2 | 0 | 0 | 0 | 3/2 | -2 x1 | 0 | -2 | 0 | 0 | 0 | 1 | 0 | 0 | 1/2 | 0 | 0 | 0 | -1/2| 3 x10 | 0 | -2 | 1 | 0 | 0 | 0 | 0 | 0 | -1/2| 1 | 0 | 0 | 0 | 4 x11 | 0 | 3 | -1 | 0 | 0 | 0 | 0 | 0 | 1/2 | 0 | 1 | 0 | 0 | 6 x12 | 0 | 3 | -4 | 0 | 0 | 0 | 0 | 0 | 1/2 | 0 | 0 | 1 | 0 | 0 x13 | 0 | 3 | -2 | 0 | 0 | 0 | 0 | 1 | -1/2| 0 | 0 | 0 | 1/2 | 3
Теперь находим новую базисную переменную, выполнив замену разрешающей строки на разрешающий столбец. Новая базисная переменная - x9.
Базис | x1 | x2 | x3 | x4 | x5 | x9 | x7 | x8 | x6 | x10 | x11 | x12 | x13 | св.член ------+----+----+----+----+----+-----+----+----+----+-----+-----+-----+----- x4 | 1 | 0 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 9 x5 | 1 | -2 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 5 x2 | 1 | 1 | -1 | 0 | 0 | -1/2| 1 | 0 | 0 | 0 | 0 | 0 | 1/2 | 1 x7 | 0 | 2 | 4 | 0 | 0 | 1/2 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | -1 x8 | 0 | 2 | -3 | 0 | 0 | -1/2| -1 | 0 | 0 | 0 | 0 | 0 | 3/2 | -2 x1 | 0 | -2 | 0 | 0 | 0 | 1/2 | 0 | 0 | 1 | 0 | 0 | 0 | -1/2| 3 x10 | 0 | -2 | 1 | 0 | 0 | -1/2| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 4 x11 | 0 | 3 | -1 | 0 | 0 | 1/2 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 6 x12 | 0 | 3 | -4 | 0 | 0 | 1/2 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 x13 | 0 | 3 | -2 | 0 | 0 | -1/2| 0 | 1 | 0 | 0 | 0 | 0 | 1/2 | 3
Выразим x5 через небазисные переменные на основе полученной таблицы:
x5 = 5 - x1 + 2x2
Подставим это выражение в функцию цели и получим:
z = 4x1 - 2x2 + x3 z = 4x1 - 2x2 + x3 + 20 - 4x1 + 8x2 z = 6x2 + x3 + 20
Таким образом, минимальное значение функции равно 20 при x1 = 0, x2 = 0, x3 = 0.
Ответ: min z = 20, x1 = 0, x2 = 0, x3 = 0.