IPB
ЛогинПароль:

> Компиляция правил для данного раздела

1. Заголовок темы должен быть информативным. В противном случае тема закрывается и удаляется ...
2. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
3. Одна тема - один вопрос (задача)
4. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> Дискретная математика, Потоки в сетях
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 30
Пол: Женский
Реальное имя: Ира

Репутация: -  0  +


Помогите пожалуйста решить задачки... wacko.gif

1. Для заданной сети найти максимальный поток и минимальный разрез, отделя.щий исток от стока. Истоком является вершина1, стоком-вершина2. В качестве начального потока взять поток по одному из путей из истока в сток.

2. Задана матрица (aij) эффективности выполнения i-ым рабочим j-ой работы. Расставить рабочих по работам так, чтобы min(aij)--max(задача о назначении рабочих на конвейер). первоночальную расстановку рабочих по работам выполнить так: i рабочий назначается на i работу.

3. Задана матрица (aij)-стоимости доставки единицы груза от производителя i к потребителю j. Предложение a(i) производителя и спрос b(j)-потребителя единицы груза задаются в виде таблицы:
Найти план перевозок fij


333.doc - удален! См. правила!

Сообщение отредактировано: APAL -


Прикрепленные файлы
Прикрепленный файл  111.bmp ( 512.88 килобайт ) Кол-во скачиваний: 381
Прикрепленный файл  222.bmp ( 320.81 килобайт ) Кол-во скачиваний: 386
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Прогрессор
****

Группа: Пользователи
Сообщений: 602
Пол: Мужской
Реальное имя: Михаил

Репутация: -  9  +


Что за изврат совать bmpшные картинки? angry.gif
Прикрепленное изображение Прикрепленное изображение

Цитата
Помогите пожалуйста решить задачки...
А в чём проблема? Нет алгоритмов?

Сообщение отредактировано: Atos -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 30
Пол: Женский
Реальное имя: Ира

Репутация: -  0  +


Цитата
А в чём проблема? Нет алгоритмов?

Да есть и аглоритмы ипримеры решения. Только почему-то у меня не получается. Вот например, превая задача. Вроде всё ясно и просто. Но.....увы... не могу довести до конца wacko.gif

P.S.
Цитата
333.doc - удален! См. правила!

ну посмотрела.... ничего не нашла. Я не знаю как переделывать картинки. Мне ж никто ни рассказал(((
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Цитата(Малышка @ 20.02.2006 7:49)
ну посмотрела.... ничего не нашла.

Цитата(Правила Форума)
1. на форуме запрещается:
...
11. выкладывать задачи в формате DOC (или других документов office). Разрешено или текст или графику.

И это не нашла? Просто открой свой DOC, сними с него скриншот (клавишей PrtScn) и сохрани через Paint в формате JPG ...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Прогрессор
****

Группа: Пользователи
Сообщений: 602
Пол: Мужской
Реальное имя: Михаил

Репутация: -  9  +


Цитата
Да есть и аглоритмы ипримеры решения. Только почему-то у меня не получается. Вот например, превая задача. Вроде всё ясно и просто. Но.....увы... не могу довести до конца
Так, может, напишешь, как именно пыталась решать и где загвоздка? И какими алгоритмами надо решить задачи (хотя бы названия алгоритмов, даже для потоков это можно не одним способом делать). Если можешь, отсканируй.

Сообщение отредактировано: Atos -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Новичок
*

Группа: Пользователи
Сообщений: 30
Пол: Женский
Реальное имя: Ира

Репутация: -  0  +


Дубль два...
1. Для заданной сети найти максимальный поток и минимальный разрез, отделя.щий исток от стока. Истоком является вершина1, стоком-вершина2. В качестве начального потока взять поток по одному из путей из истока в сток. (применить алгорит Форда-Фалкерсона)

2. Задана матрица (aij) эффективности выполнения i-ым рабочим j-ой работы. Расставить рабочих по работам так, чтобы min(aij)--max(задача о назначении рабочих на конвейер). первоночальную расстановку рабочих по работам выполнить так: i рабочий назначается на i работу.

3. Задана матрица (aij)-стоимости доставки единицы груза от производителя i к потребителю j. Предложение a(i) производителя и спрос b(j)-потребителя единицы груза задаются в виде таблицы:
Найти план перевозок fij


Эскизы прикрепленных изображений
Прикрепленное изображение Прикрепленное изображение Прикрепленное изображение
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


По сетям, потокам и всяким методам (типа Форда-Фалкерсона) в Инете (Яндекс, например, задействуй) полно, при этом очень подробно и хорошо (даже с анимированными картинками). Ты скажи - что ты сама уже сделала и в чем проблема? Хоть что-то начала делать?..

Atos, это, наверное, к тебе - ты любишь графы smile.gif
Так что готовься стирать помаду со щек (см. последний мессадж в первую тему Малышки и ее фото..) smile.gif smile.gif


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Прогрессор
****

Группа: Пользователи
Сообщений: 602
Пол: Мужской
Реальное имя: Михаил

Репутация: -  9  +


Ты не поняла... зачем ещё раз дублировать условия? Было бы интереснее взглянуть на примеры решения, раз они у тебя есть.
Ладно, вторую и третью задачу попробую решить, но , может быть, получится не совсем теми способами, которые тебе нужны.

Первая задача. Значит, алгоритм Форда-Фолкерсона. Будем искать увеличивающие пути.
Пусть в качестве начального потока взяли путь 1-2-3-4-5-6 с пропускной способностью 2.
1 итерация. Вершину 1 помечаем [+s, бесконечность] Вершину 6 помечаем [+1, 2]. Вершина 6 - это сток, значит, нашли увеличивающий путь 1-6 с пропускной способностью 2.
2 итерация. Вершину 1 помечаем [+s, бесконечность] Вершину 2 помечаем [+1, 5-2=3]. Вершину 4 помечаем [+1, 5].
Вершину 6 помечаем [+2, 1]. Вершина 6 - это сток, значит, нашли увеличивающий путь 1-2-6 с пропускной способностью 1.
3 итерация. Вершину 1 помечаем [+s, бесконечность]. Вершину 2 помечаем [+1, 5-3=2]. Вершину 4 помечаем [+1, 5] Вершину 3 помечаем [+2, 3-2=1] Вершину 4 помечаем [+1, 5] Вершину 5 помечаем [+4, 6-2=4]. Нельзя пометить больше ни одной вершины и сток не помечен, значит, других увеличивающих путей нет. Максимальный поток f* равен сумме начального и двух найденных путей.

Найдём минимальный разрез. 1 поместим в X. f*(1,2)=3<c(1,2)=5, значит, 2 поместим в X. f*(2,3)=2<c(2,3)=3, значит, 3 поместим в X. f*(3,4)=2<c(3,4)=6, значит, 4 поместим в X. f*(4,5)=2<c(4,5)=4, значит, 5 поместим в X.
Нашли разрез X={1,2,3,4,5}, V/X=[6}.

Сообщение отредактировано: Atos -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 30
Пол: Женский
Реальное имя: Ира

Репутация: -  0  +


Пример аналогичный для второй задачки...
Прикрепленное изображение
Прикрепленное изображение
Прикрепленное изображение
А это для третьей....
Прикрепленное изображение
Прикрепленное изображение
Прикрепленное изображение
Прикрепленное изображение

P.S. А за первую задачку..... огромное-огромное спасибочки)))) чмок тебя give_rose.gif

Сообщение отредактировано: Малышка -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Прогрессор
****

Группа: Пользователи
Сообщений: 602
Пол: Мужской
Реальное имя: Михаил

Репутация: -  9  +


Извини, не успел решить задачи... а в связи с выходными до понедельника в инете меня не будет sad.gif
по второй задаче - оптимальный минимум там равен 6, а порядок расстановки рабочих может быть разным... Алгоритм очень подробно описан тут, надо только внимательно разобраться в пометках строк и столбцов...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 30
Пол: Женский
Реальное имя: Ира

Репутация: -  0  +


Цитата
Извини, не успел решить задачи... а в связи с выходными до понедельника в инете меня не будет

Да мне-то не с спеху.... мне в мае это сдавать. Так что если ты мне поможешь, я буду очень благодарна))) rolleyes.gif

Цитата
по второй задаче - оптимальный минимум там равен 6, а порядок расстановки рабочих может быть разным... Алгоритм очень подробно описан тут, надо только внимательно разобраться в пометках строк и столбцов...

ну попробую... может и до меня дойдёт это))))
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Новичок
*

Группа: Пользователи
Сообщений: 30
Пол: Женский
Реальное имя: Ира

Репутация: -  0  +


Atos, прости, но мне кажется что в первой задачки.... твоё решение.. в третьей итерации ошибка...
Цитата
3 итерация. Вершину 1 помечаем [+s, бесконечность]. Вершину 2 помечаем [+1, 5-3=2]. Вершину 4 помечаем [+1, 5] Вершину 3 помечаем [+2, 3-2=1] Вершину 4 помечаем [+1, 5] Вершину 5 помечаем [+4, 6-2=4].

Кажется, что 5 вершина получает пометку [+4, 4-2=2]... может я ошиблась? Посмотри, пожалуйста... smile.gif
И еще... ты написал про вершину 4 два раза... это опечатка твоя, или так и надо?

Сообщение отредактировано: Малышка -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Прогрессор
****

Группа: Пользователи
Сообщений: 602
Пол: Мужской
Реальное имя: Михаил

Репутация: -  9  +


Цитата
ты написал про вершину 4 два раза... это опечатка твоя?
опечатка
Цитата
Кажется, что 5 вершина получает пометку [+4, 4-2=2]
верно, тут я тоже попутался, второпях набирал... unsure.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Новичок
*

Группа: Пользователи
Сообщений: 30
Пол: Женский
Реальное имя: Ира

Репутация: -  0  +


Такссс, значит первая задачка решена.....
Спасибочки, огромное give_rose.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 30
Пол: Женский
Реальное имя: Ира

Репутация: -  0  +


Я надеюсь ты мне поможешь с остальными.... плиззз.... give_rose.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Прогрессор
****

Группа: Пользователи
Сообщений: 602
Пол: Мужской
Реальное имя: Михаил

Репутация: -  9  +


Конечно, помогу... сейчас разбираюсь потихоньку в третьей задаче... во всех этих метках, действительно, не так просто
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Новичок
*

Группа: Пользователи
Сообщений: 30
Пол: Женский
Реальное имя: Ира

Репутация: -  0  +


Миш, ну сё там? Получается? Или ты забыл про меня? rolleyes.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Прогрессор
****

Группа: Пользователи
Сообщений: 602
Пол: Мужской
Реальное имя: Михаил

Репутация: -  9  +


Да всё как-то серьёзно приняться времени не хватало... 10.gif и тут ещё случайно у себя некоторые файлики с сообщиниями потёр, перекачивать пришлось... Не сомневаяся, решу обязательно, ты вроде писала, тебе это до мая?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Гость






Цитата
ты вроде писала, тебе это до мая?

yes2.gif угук....спасибки
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Новичок
*

Группа: Пользователи
Сообщений: 30
Пол: Женский
Реальное имя: Ира

Репутация: -  0  +


Цитата(Гость @ 8.03.2006 20:39) *

yes2.gif угук....спасибки

это я писала..просто войти забыла(((

Ну сё...про меня не забыли? blink.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 20.09.2020 1:45
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name