Помогите с постановкой задачи для симплекс метода

[Diana10]

Здравствуйте, помогите пожалуйста с постановкой задачи. Не могу написать в виде функций, чтобы реализовать задачу в симплекс методе. Заранее спасибо!
Дано:
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} ​$$​
Нужно найти матрицу оптимального пути, при условии, что суммарный трафик проходящий через одно ребро не будет превышать ее пропускной способности, а также нагрузка на ребра будет минимальной, а путь наикратчайшим.

[пианист]

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

[Diana10]

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

[пианист]

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

[Diana10]

пианист в сообщении #719627 писал(а):

Если задача состоит в перемещении максимального трафика из первого узла в пятый, тогда для чего дана матрица требований?

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

[пианист]

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

[Diana10]

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

[пианист]

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

[Diana10]

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

[пианист]

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