Симлекс метод

[nbyte]

Здравствуйте.
Помогите пожалйста, завяз сильно и незнаю с чего начать
Пересмотрел все книги которые нашел в интернете, но вижу у нас немного по другому записывается решение, поэтому мне туго доходит

Вот что я непонимаю
Например мне нужно решить

$$\[\begin{gathered} {\text{z}} = {{\text{x}}_{\text{1}}}{\text{ }} + {\text{ 2}}*{{\text{x}}_{\text{2}}}{\text{ }} + {\text{ 3}}*{{\text{x}}_{\text{3}}}{\text{ }} + {\text{ 4}}*{{\text{x}}_{\text{4}}}{\text{ }} + {\text{ 5}}*{{\text{x}}_{\text{5}}}{\text{ }} - {\text{ }}{{\text{x}}_{\text{6}}}{\text{ }} + {\text{ }}{{\text{x}}_{\text{7}}}{\text{ }} \to {\text{ min}} \hfill \\ {{\text{x}}_{\text{1}}}{\text{ }} + {\text{ }}{{\text{x}}_{\text{2}}}{\text{ }} + {\text{ }}{{\text{x}}_{\text{3}}}{\text{ }} + {\text{ }}{{\text{x}}_{\text{6}}}{\text{ }} = {\text{ 2}}, \hfill \\ {\text{ }} - {\text{ }}{{\text{x}}_{\text{2}}}{\text{ }} + {\text{ }}{{\text{x}}_{\text{3}}}{\text{ }} + {\text{ 2}}*{{\text{x}}_{\text{6}}}{\text{ }} + {\text{ }}{{\text{x}}_{\text{7}}}{\text{ }} = {\text{ 4}}, \hfill \\ {\text{ 2}}*{{\text{x}}_{\text{2}}}{\text{ }} + {\text{ 3}}*{{\text{x}}_{\text{3}}}{\text{ }} + {\text{ }}{{\text{x}}_{\text{4}}}{\text{ }} - {\text{ }}{{\text{x}}_{\text{6}}}{\text{ }} = {\text{ 3}}, \hfill \\ {\text{ }} - {\text{ }}{{\text{x}}_{\text{3}}}{\text{ }} + {\text{ }} + {\text{ }}{{\text{x}}_{\text{5}}}{\text{ }} + {\text{ }}{{\text{x}}_{\text{6}}}{\text{ }} = {\text{ 1}}, \hfill \\ \end{gathered} \] $$

$\[{{\text{x}}_{\text{i}}}{\text{ }} > = {\text{ }}0,{\text{ i }} = {\text{ 1}},..,{\text{7}}\]$
Таблицы у нас составляются в такой форме

Может кто-нибудь сможет подсказать с чего начать решать?
Может где-то что-то есть, где в достаточно понятной форме показано решение?

-- Вс окт 31, 2010 18:10:35 --

Другими словами хочу узнать последовательность действий что-бы решить этот пример.
Что мне нужно сделать на первом шаге?

[kvadratnt]

http://img543.**invalid link**/img543/4567/simplx.jpg

[nbyte]

А где я вот это дело могу скачать? :)

[Alexey1]

У Вас есть формулы по которым должна заполняться таблица?

[Yu_K]

http://www.syktsu.ru/fac/math/app/lp.htm
http://lab127.karelia.ru/~alexmou/tpr/t ... amming.ppt
Google Вам поможет - например эти ссылки выше.

[nbyte]

Давай-те я попробую решить
Есть у меня

(для более удобного вида)
Записываю векторы

$$ \[\begin{gathered} {a_1} = (1,0,0,0) \hfill \\ {a_2} = (1, - 1,2,0) \hfill \\ {a_3} = (1,1,3, - 1) \hfill \\ {a_4} = (0,0,1,0) \hfill \\ {a_5} = (0,0,0,1) \hfill \\ {a_6} = (1,2, - 1,1) \hfill \\ {a_7} = (0,1,0,0) \hfill \\ \end{gathered} \] $$

И вот тут что мне дальше делать?
Мне нужно сначала найти базовый план?
Как мне найти базовый план и решение?

-- Вс окт 31, 2010 22:23:16 --

Буду писать здесь решение по мере продвижения и задавать вопросы где буду застревать, а Вы посмотрите правильно-ли.

[Alexey1]

Вам необходимо найти базовое решение, с которого начнёте поиск оптимального решения. Посмотрите на систему ограничений, какое самое простое решение Вы можете предложить?

[nbyte]

Alexey1 в сообщении #368558 писал(а):

какое самое простое решение Вы можете предложить?

А его надо самому усмотреть (эвристическим способом?)

-- Вс окт 31, 2010 23:22:38 --

Что мне приходит на ум, то это например
$\[{x_0} = (2,0,0,4,3,0,1)\]$

[age]

Алгоритм решения симплекс-задач:
1. Канонизация (от неравенств к равенствам с помощью вспомогательных переменных).
2. Составление первой симплекс-таблицы. Вычисление наименьших элементов в строке целевой функции. Определение разрешающего элемента $\min{\dfrac{a_{ij}}{c_{j}}}$ в столбце с разрешающим минимальным целевым элементом.
3. Симплекс преобразования по правилу "прямоугольника". Новый разрешающий элемент, новая симплекс-таблица и т.д., пока все элементы в строке целевой функции не станут положительными.

-- Вс окт 31, 2010 23:41:01 --

P.S.
У вас, насколько я понял, задача уже в каноническом виде. п.1 не нужен.

[Alexey1]

nbyte в сообщении #368561 писал(а):

А его надо самому усмотреть (эвристическим способом?)

Это не всегда можно сделать, но в Вашем случае его легко найти что Вы и сделали.

[kvadratnt]

nbyte в сообщении #368381 писал(а):

А где я вот это дело могу скачать? :)

http://www.google.ru/#sclient=psy&hl=ru ... 71a8efc76d

[nbyte]

Так, посмотрите тогда как я решаю.
Я тут опять столкнулся с препятствием.

$$\[\begin{gathered} {x_0} = (2,0,0,4,3,0,1) \hfill \\ {x_0},{S^*} = (1,4,5,7) \hfill \\ \end{gathered} \] $$

Вот такая табличка

Проблема в том что по теореме, если в строке $c_j-z_j$ нету положительных чисел, то конечная функция неопределена.
Поэтому ломаю голову что я нетак сделал.

[Alexey1]

Поймите, что таблиц которые реализуют симплекс-метод много. Пока Вы не напишете то, как Вы заполняете таблицу будет трудно найти ошибку.

[nbyte]

По столбцам у меня идут значения векторов $a_2, a_3, a_6, b$
По бокам и верху значения коэффициентов из $\[{\text{z}} = {\text{x1 }} + {\text{ 2}}*{\text{x2 }} + {\text{ 3}}*{\text{x3 }} + {\text{ 4}}*{\text{x4 }} + {\text{ 5}}*{\text{x5 }} - {\text{ x6 }} + {\text{ x7 }} \to {\text{ min}}\]$
$z_j$ строка у меня высчитывается = первый аргумент вектора*боковое число слева + второй аргумент вектора*боковое число слева + ...
$c_j-z_j$ строка = число с верха колонки - $c_j$

[Alexey1]

Ну Вы и написали. У Вас что базис нигде не используется? В середине таблицы должно быть наверное $B^{-1}A$, где $B$ это выбранный базис, а $A$ это матрица коэффициентов (из этого произведения потом выбрать необходимые столбцы).