2014 dxdy logo

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

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




 
 Помогите с постановкой задачи для симплекс метода
Сообщение04.05.2013, 18:58 
Здравствуйте, помогите пожалуйста с постановкой задачи. Не могу написать в виде функций, чтобы реализовать задачу в симплекс методе. Заранее спасибо!
Дано:
1)матрица пропускной способности сети
$$
\begin{bmatrix}
0 & 48 & 8 & 0 & 16 \\
48 & 0 & 7 & 23 & 66 \\
8 & 7 & 0 & 77 & 16 \\
0 & 23 & 77 & 0 & 94 \\
16 & 66 & 16 & 94 & 0 
\end{bmatrix}
​$$
2)матрица весов(пути)
$$
\begin{bmatrix}
0 & 5 & 5 & 0 & 7 \\
5 & 0 & 9 & 4 & 4 \\
5 & 9 & 0 & 3 & 9 \\
0 & 4 & 3 & 0 & 6 \\
7 & 4 & 9 & 6 & 0 
\end{bmatrix}
​$$
3)матрица требований(трафик который необходимо передать)
$$
\begin{bmatrix}
0 & 1 & 2 & 0 & 2 \\
0 & 0 & 3 & 4 & 0 \\
0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 2 \\
0 & 0 & 0 & 0 & 0 
\end{bmatrix}
​$$
Нужно найти матрицу оптимального пути, при условии, что суммарный трафик проходящий через одно ребро не будет превышать ее пропускной способности, а также нагрузка на ребра будет минимальной, а путь наикратчайшим.

 
 
 
 Re: Помогите с постановкой задачи для симплекс метода
Сообщение04.05.2013, 19:48 
Аватара пользователя
Расшифруйте, пожалуйста, смысл употребленных слов. Что есть "матрица оптимального пути" - из какого узла в какой сколько проедет? Пропускная способность это, видимо, максимальное значение трафика по каждому ребру.. А как расшифровать "нагрузка на ребра будет минимальной"? Что есть матрица весов - матрица расстояний между узлами?
Ну и, главное, в тексте видится минимум две объектных функции, путь и нагрузка на ребра, а оптимизировать можно только одну.

 
 
 
 Re: Помогите с постановкой задачи для симплекс метода
Сообщение04.05.2013, 20:25 
пианист, совершенно верно,
1)Матрица оптимального пути - из какого узла в какой сколько проедет
2)Пропускная способность - максимальное значение трафика по каждому ребру
3)Матрица весов - матрица расстояний между узлами.
"нагрузка на ребра будет минимальной" - максимальная нагрузка на ребро, создаваемая матрицей требований, не будет превышать ее пропускной способности.
Суть задачи заключается в том, чтобы от пункта 1 до пункта 5 передавать трафик по наикратчайшим путям, но таким образом, чтобы не получились задержки, то есть не перегружать ребро, а распределять трафик равномерно.

 
 
 
 Re: Помогите с постановкой задачи для симплекс метода
Сообщение04.05.2013, 21:33 
Аватара пользователя
Т.е. текст про минимальность нагрузки на ребра можно выбросить из условия?
Если задача состоит в перемещении максимального трафика из первого узла в пятый, тогда для чего дана матрица требований?
Вообще, я бы просто принял в качестве переменных эту самую матрицу оптимального пути $x_{ij}$, записал бы через них соответствующую целевую функцию и условия. Если при этом возникнут какие-то конкретные трудности, можно будет их обсудить.

 
 
 
 Re: Помогите с постановкой задачи для симплекс метода
Сообщение04.05.2013, 22:05 
пианист в сообщении #719627 писал(а):
Если задача состоит в перемещении максимального трафика из первого узла в пятый, тогда для чего дана матрица требований?

нет, нужно перемещать "матрицу требований", а "от пункта 1 до пункта 5" хотела привести в виде примера, не удачно получилось.

 
 
 
 Re: Помогите с постановкой задачи для симплекс метода
Сообщение05.05.2013, 08:38 
Аватара пользователя
А, ну тогда все просто: ищем минимум $\sum_{i,j} d_{ij}x_{ij}$, где $d$ матрица расстояний (весов), Ваш п.1 дает условия на $x$ сверху, п.3 - снизу. Полученную задачу ЛП можно решить, в ч., с помощью симплекс-метода.

 
 
 
 Re: Помогите с постановкой задачи для симплекс метода
Сообщение05.05.2013, 09:52 
пианист, большое спасибо, теперь попробую решить задачку.

 
 
 
 Re: Помогите с постановкой задачи для симплекс метода
Сообщение05.05.2013, 12:05 
Аватара пользователя
Именно _решить_ при такой постановке тривиально :) просто присмотритесь к условию. Я так понимаю - задача дана в качестве упражнения на использование симплекс-метода..

 
 
 
 Re: Помогите с постановкой задачи для симплекс метода
Сообщение05.05.2013, 17:19 
пианист, во время реализации задачи в программе запрашивает ввод свободного члена для первого и второго ограничений, я не пойму откуда его взять, пожалуйста подскажите.
Нет, не в качестве упражнений, вообще в последний раз задачи по математике решала на первом курсе, а про линейное программирование прочитала совсем недавно, так как в дипломном проекте пришлось столкнутся с рядом задач по оптимизации, вот теперь сижу, не первую неделю разбираюсь с этими алгоритмами, а самостоятельно все это понять для меня не просто.

 
 
 
 Re: Помогите с постановкой задачи для симплекс метода
Сообщение05.05.2013, 19:21 
Аватара пользователя
Упс.
Тогда кидайте предметную постановку, так, как тут изложено, ничего осмысленного описываться не может.
Задачу о пяти узлах вполне можно решать в Excel, если по-быстрому надо, там есть такая приблуда в надстройках, "Поиск решения" называется, это во-первых.
Во-вторых, вообще тут решать нечего: перевозки по Вашей матрице требований, по минимуму, должны быть осуществлены, а брать больший объем бессмысленно, т.к. это может лишь увеличить общий километраж; так что она (матрица требований) и дает решение. Но, как уже говорилось, совершенно невозможно себе представить, чтобы какая-то реальная задача приводила к такой модели, что-то, скорее всего, упущено.
Что именно запрашивает Ваша программа, сказать в точности не могу, программами ЛП с диалоговым интерфейсом отродясь не пользовался, даже не знал, что таковые имеются. Скорее всего, речь идет о значениях, содержащихся в матрицах 1. и 3. Могу только порекомендовать изучить мануал.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group