2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Помогите с постановкой задачи для симплекс метода
Сообщение04.05.2013, 18:58 


04/05/13
6
Здравствуйте, помогите пожалуйста с постановкой задачи. Не могу написать в виде функций, чтобы реализовать задачу в симплекс методе. Заранее спасибо!
Дано:
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 
Заслуженный участник
Аватара пользователя


03/06/08
2147
МО
Расшифруйте, пожалуйста, смысл употребленных слов. Что есть "матрица оптимального пути" - из какого узла в какой сколько проедет? Пропускная способность это, видимо, максимальное значение трафика по каждому ребру.. А как расшифровать "нагрузка на ребра будет минимальной"? Что есть матрица весов - матрица расстояний между узлами?
Ну и, главное, в тексте видится минимум две объектных функции, путь и нагрузка на ребра, а оптимизировать можно только одну.

 Профиль  
                  
 
 Re: Помогите с постановкой задачи для симплекс метода
Сообщение04.05.2013, 20:25 


04/05/13
6
пианист, совершенно верно,
1)Матрица оптимального пути - из какого узла в какой сколько проедет
2)Пропускная способность - максимальное значение трафика по каждому ребру
3)Матрица весов - матрица расстояний между узлами.
"нагрузка на ребра будет минимальной" - максимальная нагрузка на ребро, создаваемая матрицей требований, не будет превышать ее пропускной способности.
Суть задачи заключается в том, чтобы от пункта 1 до пункта 5 передавать трафик по наикратчайшим путям, но таким образом, чтобы не получились задержки, то есть не перегружать ребро, а распределять трафик равномерно.

 Профиль  
                  
 
 Re: Помогите с постановкой задачи для симплекс метода
Сообщение04.05.2013, 21:33 
Заслуженный участник
Аватара пользователя


03/06/08
2147
МО
Т.е. текст про минимальность нагрузки на ребра можно выбросить из условия?
Если задача состоит в перемещении максимального трафика из первого узла в пятый, тогда для чего дана матрица требований?
Вообще, я бы просто принял в качестве переменных эту самую матрицу оптимального пути $x_{ij}$, записал бы через них соответствующую целевую функцию и условия. Если при этом возникнут какие-то конкретные трудности, можно будет их обсудить.

 Профиль  
                  
 
 Re: Помогите с постановкой задачи для симплекс метода
Сообщение04.05.2013, 22:05 


04/05/13
6
пианист в сообщении #719627 писал(а):
Если задача состоит в перемещении максимального трафика из первого узла в пятый, тогда для чего дана матрица требований?

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

 Профиль  
                  
 
 Re: Помогите с постановкой задачи для симплекс метода
Сообщение05.05.2013, 08:38 
Заслуженный участник
Аватара пользователя


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

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


04/05/13
6
пианист, большое спасибо, теперь попробую решить задачку.

 Профиль  
                  
 
 Re: Помогите с постановкой задачи для симплекс метода
Сообщение05.05.2013, 12:05 
Заслуженный участник
Аватара пользователя


03/06/08
2147
МО
Именно _решить_ при такой постановке тривиально :) просто присмотритесь к условию. Я так понимаю - задача дана в качестве упражнения на использование симплекс-метода..

 Профиль  
                  
 
 Re: Помогите с постановкой задачи для симплекс метода
Сообщение05.05.2013, 17:19 


04/05/13
6
пианист, во время реализации задачи в программе запрашивает ввод свободного члена для первого и второго ограничений, я не пойму откуда его взять, пожалуйста подскажите.
Нет, не в качестве упражнений, вообще в последний раз задачи по математике решала на первом курсе, а про линейное программирование прочитала совсем недавно, так как в дипломном проекте пришлось столкнутся с рядом задач по оптимизации, вот теперь сижу, не первую неделю разбираюсь с этими алгоритмами, а самостоятельно все это понять для меня не просто.

 Профиль  
                  
 
 Re: Помогите с постановкой задачи для симплекс метода
Сообщение05.05.2013, 19:21 
Заслуженный участник
Аватара пользователя


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

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

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



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

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


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

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