2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Линейная оптимизация симплекс-методом.
Сообщение09.06.2014, 18:51 
Аватара пользователя


01/06/14
3
Вот такая вот задача.
Прошу объяснить мне — правильно ли я её решаю.
Заранее благодарен.

Условие
Решить задачу линейной оптимизации симплекс-методом.

Линейная целевая функция $f(x)$
$f(x) = -2x_{1}-x_{2}+4x_{3}-x_{4}-x_{5} \to \min$ \enqo(1.1)

Линейные ограничения на переменные $x_{1}$, $x_{2}$, $x_{3}$, $x_{4}$, $x_{5}$ следующие:
$\begin{cases}
x_{2}+2x_{4}-x_{5}=1;\\
x_{1}-x_{4}-x_{5}=1;\\
2x_{2}+x_{3}+2x_{5}=4;
\end{cases} \enqo(1.2)$

Кроме того, по условию задачи переменные неотрицательны:
$x_{j}\leqslant 0; j=1 ... 5$ \enqo(1.3)

Также задан опорный план:
$x^{(0)} = (1;1;2;0;0) \qquad \enqo(1.4)$

Решение
Проверим данное по условию решение — (1.4) подставим в (1.2):
$\begin{cases}
1+2 \cdot 0-0=1;\\
1-0-0=1;\\
2 \cdot 1+2+2 \cdot 0=4;
\end{cases}$

Далее. Так как опорный план задан, то полагаем основными переменными $x_{1}$, $x_{2}$ и $x_{3}$, а неосновоными — $x_{4}$ и $x_{5}$. Переменная $x_{1}$ встречается только во втором уравнении с коэффициентом 1, переменная $x_{3}$ - только в третьем с коэффициентом 1. Переменная $x_{2}$ - помимо первого уравнения - где она фигурирует с коэффициентом 1 - также встречается в третьем уравнении.
Вычтем из первого уравнения системы (1.2) третье - умножив его на два:

$\begin{cases}
x_{2}+2x_{4}-x_{5}=1;\\
x_{1}-x_{4}-x_{5}=1;\\
2x_{2}+x_{3}+2x_{5} - 2(x_{2}+2x_{4}-x_{5})=4;
\end{cases}$

$\begin{cases}
x_{2}+2x_{4}-x_{5}=1;\\
x_{1}-x_{4}-x_{5}=1;\\
2x_{2}+x_{3}+2x_{5} - 2x_{2}-4x_{4}+2x_{5}=4;
\end{cases}$

Заодно переставим местами первое и второе уравнение, и обозначим полученную систему как (2.1):

$\begin{cases}
x_{1}-x_{4}-x_{5}=1;\\
x_{2}+2x_{4}-x_{5}=1;\\
x_{3}-4x_{4}+4x_{5}=4;
\end{cases} \enqo(2.1)$

Для нахождения оптимального решения составляем симплекс-таблицу:
$
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
\text{Базис}\;X_{Bz i}&C_{Bz i}&b& x_{1} & x_{2} &x_{3} &x_{4} &$\color{red}{x_{5}}$&\theta_{i}\\
\hline
$\color{blue}{X_{1}}$&$\color{blue}{-2}$&$\color{blue}{1}$&$\color{blue}{1}$&$\color{blue}{0}$&$\color{blue}{0}$&$\color{blue}{-1}$&$\color{green}{-1}$&$\color{blue}{-1 \gets} $\\
\hline
$X_{2}$&-1&1&0&1&0&2&$\color{red}{-1}$&-1\\
\hline
$X_{3}$&4&4&0&0&1&-4&$\color{red}{4}$&1\\
\hline
\multicolumn{2}{|c|}{C_{j}}&0&-2&-1&4&-1&$\color{red}{-1}$&{-}\\
\hline
\multicolumn{2}{|c|}{\Delta_{j}}&13&0&0&0&-15&$\color{red}{20 \uparrow}$&{-}\\
\hline
\multicolumn{9}{|c|}{\text{Таблица 1. Симплекс-таблица} }\\
\hline
\end{tabular}
$

Таблицу заполняем следующим образом.
1. В столбец $\text{Базис}\;X_{Bz i}$ записываем базисные переменные - $x_{1}$, $x_{2}$ и $x_{3}$.
2. Каждому уравнению системы (2.1) ставим в соответствие по одной из строк базисной переменной $x_{1}$, $x_{2}$ и $x_{3}$. Уравнению ставится в соответствии та строка, которая подписана встречающейся в уравнении базисной переменной.
3. В столбец $C_{Bz i}$ записываем коэффициенты из целевой функции (1.1), стоящие при соответствующих базисных переменных.
4. Каждую колонку $X_{j}$ отводим одной из переменных. В ячейку на пересечении столбца переменной $X_{j}$ и строки $i$-го уравнения, заносим коэффициент $a_{ij}$ из системы (2.1).
5. На пересечении столбца $b$ и строки $i$-го уравнения заносим свободный член $i$-го уравнения.
6. Строку $C_{j}$ заполняем коэффициентами целевой функции, стоящими в целевой функции возле переменных $x_{j}$

Далее - ищем разрешающий столбец. Для этого вычисляем оценки (иначе называемые симплекс-разницами) $Delta_{j}$. Вычисляем их по формулам (2.2) и (2.3):
$\Delta_{0} = $С_{BZ 1} \cdot b_{1} + С_{BZ 2} \cdot b_{2}+ ... +С_{BZ i} \cdot b_{i} \enqo(2.2)
$\Delta_{j} = $С_{BZ 1} \cdot a_{1j} + С_{BZ 2} \cdot a_{2j}+ ... +С_{BZ i} \cdot a_{ij} \enqo(2.3)

Для оптимального плана выполняется условие:
Все $\Delta_{j}\leqslant 0$ - для задачи на максимизацию.
Все $\Delta_{j}\geqslant 0$ - для задачи на минимизацию.

Если критерий оптимальности не выполняется, то необходимо перейти к другому опорному плану. То есть - исключить из базиса некоторую переменную — и ввести вместо неё другую. Вводить в базис следует ту переменную, для которой оценка не удовлетворяет условию (2.3.8). Если таких переменных несколько, то выбираем ту, для которой оценка имеет наибольшее по модулю значение. Столбец с переменной, вносимый в базис, называется разрешающим.
Переменная, которую будем добавлять в базис — $x_{5}$. Её оценка $\Delta_{5}=20$. В таблице (2.3.1) она отмечена стрелкой, а столбец — красным цветом.
Выбрав переменную, которую будем добавлять в базис, рассчитываем последний столбец — по формуле (2.3.9).
$\theta_{i}= \frac{b_{i}}{a_{ij}} \enqo(2.3.9)$
Где $j$ – номер переменной, которую добавляем в базис. В данном случае $j=5$.
Итак, заполняем последний столбец. Из $\theta_{i}$ выбирают наименьшую. Она соответствует той переменной, которую из базиса необходимо убрать. Строка этой переменной называется разрешающей.

В рассматриваемом случае $\min(\theta_{i})=-1$, но $\theta_{1}=\theta_{2}=-1$. Выбираем любую из них — например, $\theta_{1}$. Соответствующая строка в таблице 2.3.1 отмечена стрелкой и голубым цветом. А на пересечении разрешающего столбца и строки находится разрешающий элемент $a_{РАЗР}=a_{kl}$ (выделен зелёным) - для $k$-й разрешающей строки и $l$-го разрешающего столбца.
Разрешающий элемент — $a_{15}$.
Итак, получаем новый базис - $x_{5}$, $x_{2}$, $x_{3}$.

Составляем новую таблицу — таблица 2.3.2. Вместо базисного элемента $x_{1}$ записываем $x_{5}$. Заполняем новую таблицу следующим образом:
а) На месте разрешающего элемента ставим $1$.
б) Все элементы разрешающего столбца — кроме разрешающего элемента и элемента строки $C_{j}$ - равны $0$.
в) Все элементы разрешающей строки — кроме разрешающего элемента и элемента столбца $C_{BZi}$ — высчитываем поделив старое значение на разрешающий элемент.
г) Значения столбца $C_{BZi}$ переписываем так, чтобы они соответствовали новому базису.
д) Значения строки $C_{j}$ переписываем без изменений.
e) Значения других базисных столбцов оставляем неизменными
ж) Остальные элементы $b_{k}$ и $a_{kl}$ — кроме оценок $\Delta_{j}$ и $\theta_{i}$ - высчитываем по правилу прямоугольника – см. формулы (2.3.10), (2.3.11):
$b_{iNEW} = \frac{b_{i} \cdot a_{kl РАЗР} — b_{k} \cdot a_{il}}{a_{kl РАЗР}} \enqo(2.3.10)$

$a_{ij NEW} = \frac{a_{ij} \cdot a_{kl РАЗР} — a_{kj} \cdot a_{il}}{a_{РАЗР kl}} \enqo(2.3.11)$
Получаем таблицу 2

$
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
\text{Базис}\;X_{Bz i}&C_{Bz i}&b& x_{1} & x_{2} &x_{3} &x_{4} &x_{5}&\theta_{i}\\
\hline
$X_{5}$&-1&-1&-1&0&0&1&1&{}\\
\hline
$X_{2}$&-1&0&-1&1&0&3&0&{}\\
\hline
$X_{3}$&4&8&4&0&1&-8&0&{}\\
\hline
\multicolumn{2}{|c|}{C_{j}}&0&-2&-1&4&-1&-1&{}\\
\hline
\multicolumn{2}{|c|}{\Delta_{j}}&33&20&0&0&-35&0&{}\\
\hline
\multicolumn{9}{|c|}{\text{Таблица 2. Симплекс-таблица на втором шаге} }\\
\hline
\end{tabular}
$

Собственно вопрос
В данном случае получаем максимальное значение симплекс-разницы - $\Delta_{j}$ для переменной $b$:
$\Delta_{0} = 33$
По идее — разрешающий столбец — столбец переменной $b$.

Следует игнорировать этот факт, и добавлять в базис переменную со второй максимальной оценкой — то есть переменную $x_{1}$ - с оценкой $\Delta_{1} = 20$ - соответственно, разрешающим назначать столбец с переменной $x_{1}$? Или таки следует назначить разрешающим столбец с переменной $b$?

Или я допустил ошибку где-то раньше?

 Профиль  
                  
 
 Re: Линейная оптимизация симплекс-методом.
Сообщение10.06.2014, 02:47 
Заслуженный участник


16/02/13
4102
Владивосток
просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов)

 Профиль  
                  
 
 Re: Линейная оптимизация симплекс-методом.
Сообщение10.06.2014, 03:44 
Аватара пользователя


01/06/14
3
В системе (2.1) в третьем уравнении ошибка.
Должно быть:

$x_{3}-4x_{4}+4x_{5}=2;$

Я забыл вычесть свободный коэффициент. :facepalm:
Но проблема та же оставалась. :facepalm: :facepalm:

Короче, поискал — нашёл немного другой способ решения подобных задач (вероятно, первый попавшийся мне был ошибочным).

В ближайшее время оформлю правильное решение, и выложу сюда.


iifat в сообщении #873848 писал(а):


Спасибо, изучу материал по ссылке.

 Профиль  
                  
 
 Re: Линейная оптимизация симплекс-методом.
Сообщение10.06.2014, 04:22 
Заслуженный участник


16/02/13
4102
Владивосток
murzei64 в сообщении #873859 писал(а):
В системе (2.1) в третьем уравнении ошибка
Не, арифметику проверять — увольте.
murzei64 в сообщении #873859 писал(а):
Но проблема та же оставалась
Какая — та же? На ту же я вам уже ответил: просматриваются коэффициенты кроме столбца свободных членов.
murzei64 в сообщении #873859 писал(а):
изучу материал по ссылке
На всякий случай: ссылку я дал на четвёртый, что ли, результат поиска в гугле. Не имею в виду, что это какой-то особо заслуживающий доверия источник. Кстати, гугл дал на первой же странице несколько онлайновых сервисов — попробуйте, по идее, они распишут всё решение пошагово.

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

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



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

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


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

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