Вопрос по симплекс-методу

[robot80]

Taurus, во второй сверху записи система у Вас записана верно. Это так называемая М-задача.
(В некоторых учебниках рекомендуют преобразовать исходную матрицу коэффициентов так, чтобы выделилась единичная матрица. Но в симплекс-методе ещё нужно, чтобы правые части были положительны, а добиться этого непросто. В общем, с этим преобразованием не заморачиваются и прехпдят к М-задаче).
А вот таблицы у Вас составлены неверно. В исходной системе у вас три строки, значит и в симплес-таблице их тоже должно быть три.
---------------
А что за парметры $zj$? Если оценки $\delta = C_{B} A_{j} - c_{j}$ посчитаны верно, то никаких дополнительных критериев на оптимальность не надо.

[Taurus]

robot80, таблицы я представил для другой формы (сообщение № 10), которая, очевидно, неверна.
Таблицы для этой записи
$L'=x_1+2x_2-x_3-Mx_6\to \max$

$$\left\{ \begin{array}{rcl} -x_1+4x_2-2x_3+x_4= 12 \\ x_1+x_2+2x_3+x_5= 17 \\ 2x_1-x_2+2x_3+x_6= 4 \\ \forall x_j \geqslant 0\\ \end{array} \right.$$

выглядят так

$Zj=\sum\limits_{i}^{}C_ia_{ij}$, используется в Таблице 0 для определения оценок: $\triangle _j=Z_j-C_j$
Спасибо за отклик.

В итоге $L=\frac{34}{3}\approx 11,3$, что не равняется значению, полученному через подстановку $x_1=0, x_2=\frac{16}{3}, x_3=\frac{14}{3}$ в исходную функцию (будет 6). Не должны ли они совпадать?

Вот блин, я же минус потерял при вычислении $Z_2$ в первой же таблице.

[robot80]

Очевидно, что $z_0 =\triangle_0$, потому что это одно и тоже. У вас какя-то путаница в вычислении оценок $\triangle_j$. Например, в последней таблице должно быть$\triangle_1 = \frac23 - \frac76 -1 = -\frac32$, а у вас $4M - \frac76$, должно быть $\triangle_4 = \frac12$, а у вас $\frac56$. Формула для оценок такая: $\triangle_j = C_{s 1} a_{1 j} +C_{s 2} a_{2 j}+C_{s 3} a_{3 j} - C_{j}$. Если применить эту формулу, то никаких букв М в оценках последней таблице быть не должно (за исключением последнего искусственного столбца, в котором будет заведомо положительная оценка и поэтому его обычно вообще не пишут). Так что пересчитайте оценки начиная с самой первой таблицы. Возможно, что вообще все расчёты неверны (если выбрали не тот направляющий столбец).

[ex-math]

Далась Вам эта М-задача. Сделайте преобразование Жордана-Гаусса, введя в базис $x_1$ или $x_3$. Ответ $(4,4,0)$, значение $12$.

[Taurus]

robot80
Да, как я и написал в предыдущем сообщении -- потерял минус, уже пересчитал.

[robot80]

ex-math, по сути преобразование симплекс-таблиц и есть преобразование Жордана-Гаусса. Проблема в том, что при этом преобразовании должно выполняться два условия: значение функции должно не убывать, правые части системы уравнений должны быть положительны. Выполнение этих двух условий гарантирует М-задача.

[ex-math]

robot80
В данном случае можно было третью координату $A_3$ привести к единице, а первую и вторую к нулю. При этом и правые части останутся положительными, и шестого столбца с неудобными буквами $M$ не появится.

-- 18.04.2015, 20:09 --

Еще лучше было бы проделать это с $A_1$, поскольку он входит в базис оптимального решения. Так быстрее получится, но это не совсем честно. Изначально-то решение неизвестно.

[robot80]

ex-math, вот именно, что в данном случае. В некоторых частных случаях (когда коэффициенты подобраны удачно) можно в исходной системе уравнений выделить единичную матрицу и сохранить положительные правые части. Но насколько я знаю, в общем случае этого сделать нельзя. А пробовать, угадывать - это тратить время. Так уж лучше сразу составить М-задачу. Преобразование симплекс-таблиц можно организовать в excel'e, так что расчёты будут проводиться быстро.

[ex-math]

Да, так не всегда удается сделать. Я-то думал, что ТС считает вручную, как и я, и будет рад сэкономить.

[Taurus]

Я и считал вручную. Два дня считал.

[ex-math]

Здесь еще важно оформить именно так, как требуют. Если хотят с М, значит, пусть будет с М.