Калькулятор симплексного методу

Калькулятор розв'яже задачу оптимізації за допомогою симплекс-алгоритму. При необхідності він додасть слабкі, надлишкові та штучні змінні. У випадку штучних змінних для визначення початкового розв'язку використовується метод Великого М або двофазний метод. Доступні кроки.

Цільова функція:

Максимізувати?

Обмеження:

Через кому.

Чи всі змінні невід'ємні?

Метод штучного стартового розчину:

Якщо калькулятор щось не розрахував або ви виявили помилку, або у вас є пропозиція/відгук, будь ласка, зв'яжіться з нами.

Ваш запит

Максимальний розмір $Z = 3 x_{1} + 4 x_{2}$ , з урахуванням $\begin{cases} x_{1} + 2 x_{2} \leq 8 \\ x_{1} + x_{2} \leq 6 \\ x_{1} \geq 0 \\ x_{2} \geq 0 \end{cases}$ .

Розв'язок

У канонічній формі задачу можна записати наступним чином:

Z = 3 x_{1} + 4 x_{2} \to max

\begin{cases} x_{1} + 2 x_{2} \leq 8 \\ x_{1} + x_{2} \leq 6 \\ x_{1}, x_{2} \geq 0 \end{cases}

Додайте змінні (дефіцит або надлишок), щоб перетворити всі нерівності на рівності:

Z = 3 x_{1} + 4 x_{2} \to max

\begin{cases} x_{1} + 2 x_{2} + S_{1} = 8 \\ x_{1} + x_{2} + S_{2} = 6 \\ x_{1}, x_{2}, S_{1}, S_{2} \geq 0 \end{cases}

Запишіть симплекс-таблицю:

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Розв'язок
$Z$	$-3$	$-4$	$0$	$0$	$0$
$S_{1}$	$1$	$2$	$1$	$0$	$8$
$S_{2}$	$1$	$1$	$0$	$1$	$6$

Вхідною змінною є $x_{2}$ , оскільки вона має найбільш від'ємний коефіцієнт $-4$ у Z-рядку.

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Розв'язок	Ratio
$Z$	$-3$	$-4$	$0$	$0$	$0$
$S_{1}$	$1$	$2$	$1$	$0$	$8$	$\frac{8}{2} = 4$
$S_{2}$	$1$	$1$	$0$	$1$	$6$	$\frac{6}{1} = 6$

Вихідною змінною є $S_{1}$ , оскільки вона має найменший коефіцієнт.

Розділіть рядок $1$ на $2$ : $R_{1} = \frac{R_{1}}{2}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Розв'язок
$Z$	$-3$	$-4$	$0$	$0$	$0$
$x_{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$4$
$S_{2}$	$1$	$1$	$0$	$1$	$6$

Додати рядок $2$ помножений на $4$ до рядка $1$ : $R_{1} = R_{1} + 4 R_{2}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Розв'язок
$Z$	$-1$	$0$	$2$	$0$	$16$
$x_{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$4$
$S_{2}$	$1$	$1$	$0$	$1$	$6$

Від рядка $2$ відняти рядок $3$ : $R_{3} = R_{3} - R_{2}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Розв'язок
$Z$	$-1$	$0$	$2$	$0$	$16$
$x_{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$4$
$S_{2}$	$\frac{1}{2}$	$0$	$- \frac{1}{2}$	$1$	$2$

Вхідною змінною є $x_{1}$ , оскільки вона має найбільш від'ємний коефіцієнт $-1$ у Z-рядку.

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Розв'язок	Ratio
$Z$	$-1$	$0$	$2$	$0$	$16$
$x_{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$4$	$\frac{4}{\frac{1}{2}} = 8$
$S_{2}$	$\frac{1}{2}$	$0$	$- \frac{1}{2}$	$1$	$2$	$\frac{2}{\frac{1}{2}} = 4$

Вихідною змінною є $S_{2}$ , оскільки вона має найменший коефіцієнт.

Помножте рядок $2$ на $2$ : $R_{2} = 2 R_{2}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Розв'язок
$Z$	$-1$	$0$	$2$	$0$	$16$
$x_{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$4$
$x_{1}$	$1$	$0$	$-1$	$2$	$4$

Додайте рядок $3$ до рядка $1$ : $R_{1} = R_{1} + R_{3}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Розв'язок
$Z$	$0$	$0$	$1$	$2$	$20$
$x_{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$4$
$x_{1}$	$1$	$0$	$-1$	$2$	$4$

Від рядка $2$ відняти рядок $3$ помножений на $\frac{1}{2}$ : $R_{2} = R_{2} - \frac{R_{3}}{2}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Розв'язок
$Z$	$0$	$0$	$1$	$2$	$20$
$x_{2}$	$0$	$1$	$1$	$-1$	$2$
$x_{1}$	$1$	$0$	$-1$	$2$	$4$

Жоден з коефіцієнтів Z-ряду не є від'ємним.

Оптимум досягнуто.

Отримано наступний розв'язок: $\left(x_{1}, x_{2}, S_{1}, S_{2}\right) = \left(4, 2, 0, 0\right)$ .

Відповідь

$Z = 20$ A досягається за адресою $\left(x_{1}, x_{2}\right) = \left(4, 2\right)$ A.

Калькулятор симплексного методу

Розв'язування оптимізаційних задач симплекс-методом

Ваш запит

Розв'язок

Відповідь