поговорим о ЛОНИИС

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.

Вы здесь » поговорим о ЛОНИИС » КОММЕНТАРИИ к ПРОГРАММАМ » Программа женихи - невесты

Программа женихи - невесты

Страница: 1

Сообщений 1 страница 4 из 4

1

  • Автор: Борис
  • Активный участник
  • Зарегистрирован: 2011-05-20
  • Приглашений: 0
  • Сообщений: 3498
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    1 месяц 9 дней
  • Последний визит:
    2024-04-07 21:02:23

Транспортная задача имеет много формулировок.
Рассмотри частный случай: женихи – невесты.
Есть m женихов и n невест.
Каждый жених выбирает одну невесту.
Для каждого жениха – i каждая невеста – j имеет оценку – s[i,j].
Величину s[I,j] в  данной задаче оценка равна случайному числу из диапазона 1…w.
Транспортная задача имеет  два нахождения оптимального решения:
Линейное программирование и метод потенциалов.
Есть и много методов для нахождения решений с нахождением локальных минимумов.
Эти решения могут соответствовать ситуациям, которые возникают в реальной жизни.
Пока рассмотрим такой метод.
Женихи поочередно выбирают невесту с максимальной оценкой.
Для оценки - величина zzz.
Равна средней оценке выбранных невест.
Программа промежуточная. Зарезервированы кнопки и таблицы.
Скачать программу
https://yadi.sk/d/RgqEPBJ2VL4KlA

Пример счёта:

Исходные данные 
                Результата
m=10      n=10      w=10          zzz = 0,94

m=20      n=20      w=20          zzz = 0,9775

m=50      n=50      w=50          zzz = 0,9884

m=100     n=100     w=100         zzz = 0,9947

m=500     n=500     w=500         zzz = 0,9988

m=1000    n=1000    w=1000        zzz = 0,9995

m=2000    n=2000    w=2000        zzz = 0,9997,9997

Отредактировано Борис (2021-12-04 19:55:12)

0

2

  • Автор: Борис
  • Активный участник
  • Зарегистрирован: 2011-05-20
  • Приглашений: 0
  • Сообщений: 3498
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    1 месяц 9 дней
  • Последний визит:
    2024-04-07 21:02:23

Задача на тему "женихи - невесты" в ветви "Моделирование паросочетаний"
Моделирование паросочетаний

Отредактировано Борис (2021-12-04 20:05:00)

0

3

  • Автор: ABC
  • Активный участник
  • Зарегистрирован: 2010-09-27
  • Приглашений: 0
  • Сообщений: 5931
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    2 месяца 25 дней
  • Последний визит:
    Вчера 17:12:16

Повторяю условие задачи.
Транспортная задача имеет много формулировок.
Частный случай: женихи – невесты.
Есть m женихов и n невест.
Каждый жених выбирает одну невесту.
[size=20][color=blue]Для каждого жениха – i каждая невеста – j имеет оценку – s[i,j].
Величина s[I,j] в  данной задаче: случайное число из диапазона 1…w.
Выше даны программы для нахождения максимума функции
∑c(i,j)*x(i,j) где
c(i,j) – оценка невесты j женихом i
x(i,j) – равно 1 при выборе женихом I невесты j, иначе 0.
Число женихов – n
Число невест – m
Исследуется алгоритм.
1. На основе алгоритма предыдущего поста определяется исходный план
пар: жених невеста. Суммарная оценка – zzz.
2. Поочередно выбираются по две пары: жених, невеста.
Далее операция:
if ( s[a,b]+s[c,d])  < ( s[a,d]+s[c,b])
  then   begin f := f+1; s4[a,b] := 0;      s4[c,d]:=0
s4[a,d] :=1; s4[c,b] :=1;
end;
3. Если такая операция произошла, то процесс выбора пар начинается заново.
4. Конечная оценка zzz1.

Скачать программу «2-Транспортная»
https://yadi.sk/d/cDrO-ik_CcgnsQ

Гипотеза.
Предложенный алгоритм даёт оптимальное решение.

Отредактировано ABC (2021-12-04 20:15:28)

0

4

  • Автор: ABC
  • Активный участник
  • Зарегистрирован: 2010-09-27
  • Приглашений: 0
  • Сообщений: 5931
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    2 месяца 25 дней
  • Последний визит:
    Вчера 17:12:16

Повторяю условие задачи.
Транспортная задача имеет много формулировок.
Частный случай: женихи – невесты.
Есть m женихов и n невест.
Каждый жених выбирает одну невесту.
Для каждого жениха – i каждая невеста – j имеет оценку – s[i,j].
Величина s[I,j] в  данной задаче: случайное число из диапазона 1…w.
Выше даны программы для нахождения максимума функции
∑c(i,j)*x(i,j) где
c(i,j) – оценка невесты j женихом i
x(i,j) – равно 1 при выборе женихом I невесты j, иначе 0.
Число женихов – n
Число невест – m
Исследуется алгоритм.
1. На основе алгоритма 2-Транспортная определяется исходный план
пар: жених невеста. Суммарная оценка – zzz.
2. Случайно t раз выбираются по две пары: жених, невеста.
s4[a,b] =1   s[c,d]= 1
3.Далее операция:
if ( s[a,b]+s[c,d])  < ( s[a,d]+s[c,b])
  then   begin f := f+1; s4[a,b] := 0;      s4[c,d]:=0
s4[a,d] :=1; s4[c,b] :=1;
end;
3. Конечная оценка zzz1.

Скачать программу «3-Транспортная»
https://yadi.sk/d/WDeKi1A6o2JOzA

Отредактировано ABC (2021-12-04 20:28:03)

0

Страница: 1

Вы здесь » поговорим о ЛОНИИС » КОММЕНТАРИИ к ПРОГРАММАМ » Программа женихи - невесты