Помогите пожалуйста решить задачки...
1. Для заданной сети найти максимальный поток и минимальный разрез, отделя.щий исток от стока. Истоком является вершина1, стоком-вершина2. В качестве начального потока взять поток по одному из путей из истока в сток.
2. Задана матрица (aij) эффективности выполнения i-ым рабочим j-ой работы. Расставить рабочих по работам так, чтобы min(aij)--max(задача о назначении рабочих на конвейер). первоночальную расстановку рабочих по работам выполнить так: i рабочий назначается на i работу.
3. Задана матрица (aij)-стоимости доставки единицы груза от производителя i к потребителю j. Предложение a(i) производителя и спрос b(j)-потребителя единицы груза задаются в виде таблицы:
Найти план перевозок fij
333.doc - удален! См. правила!
Прикрепленные файлы
111.bmp ( 512.88 килобайт )
Кол-во скачиваний: 495
222.bmp ( 320.81 килобайт )
Кол-во скачиваний: 493
Что за изврат совать bmpшные картинки?
Дубль два...
1. Для заданной сети найти максимальный поток и минимальный разрез, отделя.щий исток от стока. Истоком является вершина1, стоком-вершина2. В качестве начального потока взять поток по одному из путей из истока в сток. (применить алгорит Форда-Фалкерсона)
2. Задана матрица (aij) эффективности выполнения i-ым рабочим j-ой работы. Расставить рабочих по работам так, чтобы min(aij)--max(задача о назначении рабочих на конвейер). первоночальную расстановку рабочих по работам выполнить так: i рабочий назначается на i работу.
3. Задана матрица (aij)-стоимости доставки единицы груза от производителя i к потребителю j. Предложение a(i) производителя и спрос b(j)-потребителя единицы груза задаются в виде таблицы:
Найти план перевозок fij
Эскизы прикрепленных изображений
По сетям, потокам и всяким методам (типа Форда-Фалкерсона) в Инете (Яндекс, например, задействуй) полно, при этом очень подробно и хорошо (даже с анимированными картинками). Ты скажи - что ты сама уже сделала и в чем проблема? Хоть что-то начала делать?..
Atos, это, наверное, к тебе - ты любишь графы
Так что готовься стирать помаду со щек (см. последний мессадж в первую тему Малышки и ее фото..)
Ты не поняла... зачем ещё раз дублировать условия? Было бы интереснее взглянуть на примеры решения, раз они у тебя есть.
Ладно, вторую и третью задачу попробую решить, но , может быть, получится не совсем теми способами, которые тебе нужны.
Первая задача. Значит, алгоритм Форда-Фолкерсона. Будем искать увеличивающие пути.
Пусть в качестве начального потока взяли путь 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}.
Пример аналогичный для второй задачки...
А это для третьей....
P.S. А за первую задачку..... огромное-огромное спасибочки)))) чмок тебя
Извини, не успел решить задачи... а в связи с выходными до понедельника в инете меня не будет
по второй задаче - оптимальный минимум там равен 6, а порядок расстановки рабочих может быть разным... Алгоритм очень подробно описан http://www.allmath.ru/highermath/algebra/graph/graph4.htm, надо только внимательно разобраться в пометках строк и столбцов...
Atos, прости, но мне кажется что в первой задачки.... твоё решение.. в третьей итерации ошибка...
Такссс, значит первая задачка решена.....
Спасибочки, огромное
Я надеюсь ты мне поможешь с остальными.... плиззз....
Конечно, помогу... сейчас разбираюсь потихоньку в третьей задаче... во всех этих метках, действительно, не так просто
Миш, ну сё там? Получается? Или ты забыл про меня?
Да всё как-то серьёзно приняться времени не хватало... и тут ещё случайно у себя некоторые файлики с сообщиниями потёр, перекачивать пришлось... Не сомневаяся, решу обязательно, ты вроде писала, тебе это до мая?
я тут вторую задачу кажется смогла решить! Посмотри пожалуйта. Я просто не уверенна, особенно в метках. плиззз....
Эскизы прикрепленных изображений
Здрасте=) У меня тут задачка похожая первой.. Но я уже сделал все кроме минимального разреза.. Совершенно не понимаю что это такое и как оно ищется.. Разъясните поподробней плз=) Пасиба заранеее!
А создать новую тему не судьба? Или обязательно делать из чужой темы свалку?. GoodWind
Нафиг новую? Просто пояснить прошу=)