как подступиться к решению задачки по методам оптимизации?

[IHmG]

Посмотрите, пожалуйста, правильно ли я решаю задачу. Начал с графического способа. Привел к каноническому виду. Сомневаюсь на 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 :)

[Brukvalub]

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

[IHmG]

Нашел учебник,
вот что там есть

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

[Brukvalub]

(Оффтоп)

IHmG в сообщении #1028170 писал(а):

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

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

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

[Lia]

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

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

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

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

[Lia]

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

[IHmG]

IHmG в сообщении #1028170 писал(а):

Нашел учебник

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

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

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

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

[IHmG]

Brukvalub в сообщении #1028155 писал(а):

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

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

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

[Xaositect]

IHmG в сообщении #1030534 писал(а):

Или книгу нужно подряд читать?

Вы уж извините за прямоту, но судя по этой и предыдущим темам, Вам надо подряд читать учебники начиная с первого-второго курса.

[IHmG]

Xaositect в сообщении #1030592 писал(а):

IHmG в сообщении #1030534 писал(а):

Или книгу нужно подряд читать?

Вы уж извините за прямоту, но судя по этой и предыдущим темам, Вам надо подряд читать учебники начиная с первого-второго курса.

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

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