2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 14:52 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 14:58 
Аватара пользователя


17/12/10
538
Shtorm в сообщении #594919 писал(а):
В задаче не просили проверить - оптимально опорное решение или нет?


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

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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 15:01 
Аватара пользователя


14/02/10
4956
Да тут ещё пахать и пахать.

 Профиль  
                  
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 15:03 
Аватара пользователя


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

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

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

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

 Профиль  
                  
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 15:09 
Аватара пользователя


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

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

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

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



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

 Профиль  
                  
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 15:23 
Аватара пользователя


17/12/10
538
Shtorm в сообщении #594929 писал(а):
В этом ответе я насчитал 6 переменных, а в исходном задании - 5 переменных.


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

 Профиль  
                  
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 15:33 
Аватара пользователя


14/02/10
4956
Sverest в сообщении #594934 писал(а):

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


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

 Профиль  
                  
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 15:40 
Аватара пользователя


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

введем искусственные переменные и составим вспомогательную задачу
$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)$

 Профиль  
                  
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 16:58 
Аватара пользователя


14/02/10
4956
Sverest в сообщении #594944 писал(а):

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


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


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

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

 Профиль  
                  
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение15.07.2012, 00:41 
Аватара пользователя


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

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

Выберем любой отличный от нуля элемент
$\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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 25 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group