2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 как подступиться к решению задачки по методам оптимизации?
Сообщение17.06.2015, 15:11 


29/05/15
100
Посмотрите, пожалуйста, правильно ли я решаю задачу. Начал с графического способа. Привел к каноническому виду. Сомневаюсь на 5 шаге... переменная входит с коэффициентом -1... а именно $-x_2$ ... там ошибка?

где именно в рекомендованной книге изложен симплекс-метод? не могу найти...

Цитата:
Даны условия канонической задачи линейного программирования $(D, f): f(x)=CX \to \max, D = \left\lbrace X\in R^n: AX = b, x\geqslant 0\right\rbrace$ Точнее, указаны матрица A и векторы $c$ и $b$ (последний записан строкой). Необходимо последовательно выполнить следующие задания.

1. Применяя вычислительную процедуру симплекс-метода, решить задачу (D,f), т.е. указать ее оптимальный план $x^*$ и максимальное значение функционала $(f(x^*))$ или установить, что задача $(D, f)$ не имеет решения: множество $D=\varnothing$ (пусть) или функционал f не ограничен сверху на $D$

2. Применяя вычислительную процедуру двухфазного симплекс-метода, решить эту же задачу $(D,f)$ сравнить результаты и объемы вычислений пп 1 и 2

3. Задачу $(D,f)$ решить графически. Сравнить результаты заданий пп 1-3

$C= (0, 3, 1, -1, 1)$
$b = (6, 2, 1)$
A $ \begin{pmatrix} 2 & 1 & 1 & 1 & 2 \\
1 & 1 & 0 & 1 & 0 \\
1 & -1 & 0 & 0 & 1  \end{pmatrix}
$


Выпишем математическую модель задачи линейного программирования

Требуется отыскать $3x_2+x_3-x_4+x_5 \to \max$ при этом на переменные $x_1...x_5$ наложены линейные ограничения
$$
\begin{cases}
2x_1+x_2+x_3+x_4+2x_5=6\\
x_1+x_2+x_4=2\\
x_1-x_2+x_5=1
\end{cases}
$$

Решим задачу графически
1. Так как переменных 5, а уравнений 3 - графическим методом решать задачу можно
2. Выразим 3 переменные через 2 других
$$
\begin{cases}
x_3=6-2x_1-x_2 \geqslant 0\\
x_4=2x_1-x_2 \geqslant 0\\
x_5=1-x_1+x_2
\end{cases} (1)
$$

3. Пользуясь условием неотрицательности перейдем к другой системе неравенств
$
\begin{cases}
2x_1+x_2 \leqslant 6\\
x_1+x_2 \leqslant 2\\
x_1-x_2 \leqslant 1 \\
x_1 \geqslant 0 \\
x_2 \geqslant 0
\end{cases} (2)
$

4. Подставим в целевую функцию $x_1$ и $x_2$
$3x_2+(6-2x_1-x_2)-(2-x_1-x_2)+(1-x_1+x_2)=-2x_1+4x_2+5\to \max (3)$

5. (2) и (3) приведем к каноническому виду

Цитата:
из лекций канонический вид - это
- Все ограничения, кроме условия неотрицательности должны быть со знаком "равно"
- Ограничения, имеющие знак "меньше или равно" можно преобразовать к ограничению со знаком "равно" путем добавления к левой части неотрицательной переменной
- Ограничения, имеющие знак "больше или равно" можно преобразовать к ограничению со знаком "равно" путем вычитания из левой части неотрицательной переменной
- Все свободные члены ограничения должны быть "больше" 0 (если $b_i < 0$, то данное ограничение умножаем на -1)
- Все переменные должны быть неотрицательными
- Если $x_k$ не подчинено условием неотрицательности, то производим замену $x_k=x_i-x_j$ $x_i \geqslant 0,x_j \geqslant 0$


$$
2x_1+x_2\leqslant6 \Leftrightarrow 
\begin{cases}
2x_1+x_2 + x_3 = 6\\
x_3 \geqslant 0
\end{cases} 
$$

$$
x_1+x_2\leqslant 2 \Leftrightarrow 
\begin{cases}
x_1+x_2 + x_4 = 2\\
x_4 \geqslant 0
\end{cases} 
$$

Вопрос в том, что делать со следующим ограничением :?:

$
x_1-x_2\leqslant 1
$

вроде как $x_2$ нужно представить как некую разность ... или все-так можно записать так

$$
x_1-x_2\leqslant 1
\Leftrightarrow 
\begin{cases}
x_1-x_2+x_5 = 1 \\
x_5 \geqslant 0
\end{cases} 
$$


Окончательно задача в каноническом виде запишется так
$$
-2x_1+4x_2+5\to \max
$$

при ограничениях

$$
\begin{cases}
2x_1+x_2+x_3=6\\
x_1+x_2+x_4=2\\
x_1-x_2+x_5=1\\
x_i \geqslant 0,\, i=\bar{(1,5)}
\end{cases}  (3)
$$


6. Найдем начальное допустимое базисное решение (НДБР)
Цитата:
из лекций
- сколько л\нез ограничений столько и базисных переменных
- базисные - те переменные, которые встречаются только в одном из ограничений с положительным коэффициентом
- запись НДБР - не базисной переменной присвоить значение 0, а к базисным, значение соответствующих свободных членов


$\begin{pmatrix} 2 & 1 & 1 & 0 & 0 | 6 \\  
1 & 1 & 0 & 1 & 0 | 2 \\  
1 & -1 & 0 & 0 & 1| 1
\end{pmatrix}$


$x_3,x_4,x_5$ - базисные переменные
$x_1,x_2$ - не базисные переменные

Отсюда НДБР $x^0=(0,0,6,2,1)$

6. Построим допустимое множество
$2x_1+x_2=6 (1)$
$x_1+x_2=2$
$x_1-x_2=1$

7. Построим линии уровня $f(x)=-2x_1+4x_2+5= \operatorname{const}$, возьмем $c=0$ $f(x)=-2x_1+4x_2+5=0$

8. Построим график
Изображение

9. Построим grad (т.к. задача на максимум), который показывает направление возрастания или убывания функции

Цитата:
в лекциях

Градиент (антиградиент) показывает направление возрастания (убывания) функции

$f(x) = a_1x_1+a_2x_2$

градиент $\nabla f(x) = (\frac{\partial f(x)}{\partial x_1}, \frac{\partial f(x)}{\partial x_2})$
$\nabla f(x) = (a_1,a_2)$
$-\nabla f(x) = (-\frac{\partial f(x)}{\partial x_1}, -\frac{\partial f(x)}{\partial x_2})$
$-\nabla f(x) = (-a_1,-a_2)$



судя по врезке дальше можно записать
$\nabla f(x) = (-2,4)$

я правильно понимаю :?:

только вот не понятно... как по этому градиенту судить о возрастании или убывании функции :?:

10. Определение точек max и min
:?: как это делается? если просто подставить координаты точек пересечения ... то получим 7 в точке А ... но ведь x должны быть "больше или равные 0"? тогда остается только точка B и тут значение функции равно 4... совсем ничего не понимаю :( тут никакого матана применять не надо?

Я думаю,что точкой максимум служит точка B на графике

$$
\begin{cases}
x_1+x_2 = 2 \\
x_1-x_2 = 1 
\end{cases} 
(\frac{3}{2}, \frac{1}{2})
$$

ответ $f_{max} = 4 $
$x^* (\frac{3}{2}, \frac{1}{2})$

Ещё вопрос :?:
на 2 шаге мы выражали 3 переменные через 2... нужно ли переходить назад ко всему набору переменных? ради интереса посмотрел, что исходная функция будет также равна 4 :)

 Профиль  
                  
 
 Re: как подступиться к решению задачки по методам оптимизации?
Сообщение17.06.2015, 15:17 
Заслуженный участник
Аватара пользователя


01/03/06
13619
Москва
Начните с изучения дисциплины по учебникам, например, "Палий И.А. Линейное программирование".

 Профиль  
                  
 
 Re: как подступиться к решению задачки по методам оптимизации?
Сообщение17.06.2015, 16:09 


29/05/15
100
Нашел учебник,
вот что там есть Изображение

Можете порекомендовать что-нибудь попроще... или проще этой книги уже ничего нет для решения такой задачки?

 Профиль  
                  
 
 Re: как подступиться к решению задачки по методам оптимизации?
Сообщение17.06.2015, 16:47 
Заслуженный участник
Аватара пользователя


01/03/06
13619
Москва

(Оффтоп)

IHmG в сообщении #1028170 писал(а):
Можете порекомендовать что-нибудь попроще... или проще этой книги уже ничего нет для решения такой задачки?

Проще этой книги Уставы гарнизонной и караульной служб.

Интересно, где же вы "учитесь", если кроме формулировки задачи вам никто ничего не объясняет? :shock:

 Профиль  
                  
 
 Posted automatically
Сообщение17.06.2015, 16:51 
Модератор


20/03/14
11513
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

Литературу рекомендовали, первая помощь оказана.

- отсутствуют собственные содержательные попытки решения задач(и).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 Профиль  
                  
 
 Posted automatically
Сообщение24.06.2015, 13:13 
Модератор


20/03/14
11513
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 Профиль  
                  
 
 Re: как подступиться к решению задачки по методам оптимизации?
Сообщение24.06.2015, 13:18 


29/05/15
100
IHmG в сообщении #1028170 писал(а):
Нашел учебник

... и начал его внимательно читать... обнаружил, что повествование прерывается на стр 76 :( кто-нибудь встречал эту книжку в полном объеме? сам ищу... но может у кого в запасниках уже лежит?

вот еще одно пособие того же автора нашел... и похоже это разные книги... какое издание лучше читать? :D

к сожалению, очень мало времени... понимаю, что у всех его мало... но если книга уже читана... можно сразу сказать и это проще чем прочитать 2 книги такого объема :)

помогите пожалуйста локализовать усилия... уже скоро закукарекаю от математики :)

 Профиль  
                  
 
 Re: как подступиться к решению задачки по методам оптимизации?
Сообщение24.06.2015, 18:10 


29/05/15
100
Brukvalub в сообщении #1028155 писал(а):
Начните с изучения дисциплины по учебникам, например, "Палий И.А. Линейное программирование".


Вот тут во флейме хочу отписываться о продвижении в чтении книги :) Можно попросить схему решения задачи (лучше с опорой на конкретные разделы пособия) ? Или книгу нужно подряд читать?

Думаю моя попытка решения с опорой на конспект очень сильно страдает (как минимум) в плане оформления...

 Профиль  
                  
 
 Re: как подступиться к решению задачки по методам оптимизации?
Сообщение24.06.2015, 20:38 
Заслуженный участник
Аватара пользователя


06/10/08
6422
IHmG в сообщении #1030534 писал(а):
Или книгу нужно подряд читать?
Вы уж извините за прямоту, но судя по этой и предыдущим темам, Вам надо подряд читать учебники начиная с первого-второго курса.

 Профиль  
                  
 
 Re: как подступиться к решению задачки по методам оптимизации?
Сообщение25.06.2015, 13:59 


29/05/15
100
Xaositect в сообщении #1030592 писал(а):
IHmG в сообщении #1030534 писал(а):
Или книгу нужно подряд читать?
Вы уж извините за прямоту, но судя по этой и предыдущим темам, Вам надо подряд читать учебники начиная с первого-второго курса.


Напротив, я благодарен за прямоту. Согласен с Вашим мнением. Просто сейчас сессия на 5 курсе и мне нужно сдать то, что есть шансы сдать. А пробелов действительно очень много на базовых курсах и я понимаю, что если получу диплом - это будет чудо. Слава Богу сейчас со здоровьем стало лучше и я могу хоть что-то учить и пытаться сдавать.

Кстати, чудом, видимо с Божьей помощью я как-то умудрился получить зачет. Вернуться к материалу необходимо потом, но сейчас надо заниматься пробелами в младших курсах

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

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



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

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


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

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