Задача линейного программирования. Симплекс метод

[Shtorm]

Вот теперь вроде всё. Исходное опорное решение получено. В задаче не просили проверить - оптимально опорное решение или нет?

[Sverest]

Shtorm в сообщении #594919 писал(а):

В задаче не просили проверить - оптимально опорное решение или нет?

Нет не просили, тут несколько заданий:

Для задачи линейного программирования выполнить следующее:
- найти исходное опорное решение, используя симплексные преобразования,
- решить ее с помощью любого метода искусственного базиса,
- составить для нее двойственную задачу,
- найти решение двойственной задачи, используя найденное решение исходной задачи.

(Оффтоп)

Про остальные еще не смотрел в методичке как делать, сейчас буду смотреть

[Shtorm]

Да тут ещё пахать и пахать.

[Sverest]

В чем смысл этого исходного опорного решения, оно что-то показывает?
В методичке ИОР почему то записано в виде:

$X^{(0)}=(0,0,11/2,0,3/2,0)$

как это вывели?

и тут написано "используя симплексные преобразования" - какие преобразования были симплексными?

[Shtorm]

Опираясь на него - ищут следующее решение, если исходное опорное решение неоптимально. Решение симплексным методом можно геометрически представить себе по аналогии с графическим методом решения функции двух переменных на плоскости. Только поскольку в Симплексном методе чаще всего много переменных, то получается не многоугольник решений, а многомерный многогранник. Исходное опорное решение представляет собой один из углов этого многогранника. Если значение целевой функции неоптимально в этом угле - то осуществляется переход к следующему углу многогранника. Этот переход делается по специальному алгоритму.

-- Пт июл 13, 2012 15:13:33 --

Sverest в сообщении #594924 писал(а):

$X^{(0)}=(0,0,11/2,0,3/2,0)$

В этом ответе я насчитал 6 переменных, а в исходном задании - 5 переменных.

[Sverest]

Shtorm в сообщении #594929 писал(а):

В этом ответе я насчитал 6 переменных, а в исходном задании - 5 переменных.

Я просто взял левый пример из методички, я имел ввиду может мне тоже в таком виде записать?

[Shtorm]

Sverest в сообщении #594934 писал(а):

Я просто взял левый пример из методички, я имел ввиду может мне тоже в таком виде записать?

Да. Это стандартная запись для опорного решения. Возмите систему уравнений, где базисные выражены через свободные и подставьте все свободные переменные равные нулю. Найдёте базисные - и запишите в том виде.

[Sverest]

попробую решить с помощью двухэтапного метода

введем искусственные переменные и составим вспомогательную задачу
$max \:\: T= y_1+y_2$

$\left\{\begin{matrix} x_1+ 2x_2+ x_3+ 6x_4 + x_5+y_1=4\\ 3x_1 -x_2 -x_3 + x_4+y_2=1 \\ x_1 +3x_2+ 5x_3 =9 \end{matrix}\right.$

Преобразуем функцию $T$, выразив ее через свободные переменные

T=4-(x_1+ 2x_2+ x_3+ 6x_4 + x_5)+1-( 3x_1 -x_2 -x_3 + x_4)= 4-x_1- 2x_2- x_3- 6x_4 - x_5+1 -3x_1 +x_2 +x_3 - x_4= 5-4x_1- x_2- 7x_4 - x_5

-- Пт июл 13, 2012 15:46:09 --

Shtorm в сообщении #594940 писал(а):

Да. Это стандартная запись для опорного решения. Возмите систему уравнений, где базисные выражены через свободные и подставьте все свободные переменные равные нулю. Найдёте базисные - и запишите в том виде.

$X^{(0)}=(1,1,1,0,0)$

[Shtorm]

Sverest в сообщении #594944 писал(а):

Shtorm в сообщении #594940 писал(а):

Да. Это стандартная запись для опорного решения. Возмите систему уравнений, где базисные выражены через свободные и подставьте все свободные переменные равные нулю. Найдёте базисные - и запишите в том виде.

$X^{(0)}=(1,1,1,0,0)$

Да. И чтобы окончательно первый этап был завершён ещё добавить в ответ запись:

$$f(X^{(0)})=6$$

[Sverest]

Чтоб потренироваться, решил еще раз найти ИОР, но уже симплекс-методом,
почему то не получается

Для нахождения ИОР целевая функция необязательна(так в методичке написано),
поэтому рассмотрим только систему органичений

Выберем любой отличный от нуля элемент
$\begin{tabular}{c|c|c|c|c|c|c|c} \\ \text{базисные} & \text{свободные} & x_1&(x_2)&x_3&x_4&x_5& \\ \hline x_5&4&1&2&1&6&1&2 \\ \hline ( \:\:)&1&3&-1&-1&1&0&-1\\ \hline &9&1&3&5&0&0&3 \end{tabular}$

Разрешающий столбец $x_2$ строка вторая

$\begin{tabular}{c|c|c|c|c|c|c|c} \\ \text{базисные} & \text{свободные} & x_1&x_2&x_3&x_4&x_5& \\ \hline x_5&6&7&0&-1&8&1& \\ \hline x_2&-1&-3&1&1&-1&0&\\ \hline &12&10&0&2&3&0& \end{tabular}$

Получили отрицательный свободный член, домножим строку на -1

$\begin{tabular}{c|c|c|c|c|c|c|c} \\ \text{базисные} & \text{свободные} & (x_1)&x_2&x_3&x_4&x_5& \\ \hline x_5&6&7&0&-1&8&1&0,857 \\ \hline (x_2)&1&3&-1&-1&1&0&0,333\\ \hline &12&10&0&2&3&0&1,2 \end{tabular} $
Выберем в строке любой положительный элемент
Разрещаюший столбик $x_1$ строка вторая

$\begin{tabular}{c|c|c|c|c|c|c|c} \\ \text{базисные} & \text{свободные} & x_1&x_2&x_3&x_4&x_5& \\ \hline x_5&11/3&0&7/3&4/3&17/3&1& \\ \hline x_1&1/3&1&-1/3&-1/3&1/3&0&\\ \hline &26/3&0&10/3&16/3&-1/3&0& \end{tabular}$

Согласно методичке, это и должно быть ИОР, так как свободные переменные положительны,
но ведь третья переменная же не базисная, где я ошибся

Чтоб было удобней считать методом симплекса, сделал электронную таблицу, прикрепляю ее, она в формате (.ods libre office) данный пример там под черной полосой
http://narod.ru/disk/56438320001.8c9d35726ecc24dee6f323afadf2f487/%D1%81%D0%B8%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81.ods.html

сконвентированный в .xls
http://narod.ru/disk/56438643001.7537e49a535688136817566de7541e59/%D1%81%D0%B8%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81.xls.html

вот еще методичка, может я там что-то не понял
http://narod.ru/disk/56438980001.1fbf72b44aeeba0d2d7f9c599c600713/2.1.6._IOR.mht.html