Задача распределения набора в вузы по специальностям

[Dorofey]

Задача распределения набора в вузы по специальностям:
Дано:
1. Рейтинг вузов (каждому вузу приписаны веса).
2. Рейтинг специальностей (каждой специальности приписаны веса).
3. Требуемое количество студентов по каждой специальности.
4. Ограничение на вместительность вузов (в каждый вуз помещается не более заданного количества студентов)

Требуется распределить студентов по вузам с учетом ограничений двумя способами:
a) Максимально «набить» лучшие вузы по лучшим специальностям
b) Распределить студентов пропорционально рейтингам вузов и специальностей

Для случая а) в качестве целевой функции взял сумму произведений весов вузов, весов специальностей и искомых переменных. Корректно ли это?

Помогите, пожалуйста, выбрать целевую функцию для b)

[provincialka]

Возникают вопросы по постановке задачи.
1. Как соотносятся вузы и специальности? Каждая специальность в одном вузе? В нескольких? В последнем случае, является ли вес специальности независимым от веса вуза?
2. Как определить вес пары (вуз, специальность). Как произведение весов компонент? (А может, как сумму? Или еще что-то?)
3. Есть ли ограничения на число, качество и предпочтения студентов? Или их, как бычков на бойню "распределяют" в нужное место?

Не знаю точно вашу задачу, но целевая функция мне как-то не нравится. Честно говоря, вообще непонятно, что и зачем надо максимизировать. Если студентов хватает - расталкиваем их во вузам. Надо полагать, что у вас возможности вузов по (всем или некоторым) специальностям недостаточны, чтобы покрыть заявку? И надо чем-то жертвовать? В общем, постановка сырая.

[Dorofey]

1. Вузы и специальности - это матрица, на пересечении которой стоят количества студентов. Т.е. считается, что все специальности есть во всех вузах. Дополнительно можно задать набор ограничений сверху и снизу на каждую компоненту матрицы.
2. Вес пары (вуз, специальность) определяется по условию задачи как произведение весов компонент.
3. Других ограничений нет (распределяют в конечном итоге не людей, а контрольные цифры приема).

Т.е. можно решить задачу без оптимизационных методов? (в обоих случаях: а) и b)?)

[Shadow]

Dorofey в сообщении #767687 писал(а):

1. Вузы и специальности - это матрица, на пересечении которой стоят количества студентов. Т.е. считается, что все специальности есть во всех вузах. Дополнительно можно задать набор ограничений сверху и снизу на каждую компоненту матрицы.
2. Вес пары (вуз, специальность) определяется по условию задачи как произведение весов компонент.
3. Других ограничений нет (распределяют в конечном итоге не людей, а контрольные цифры приема).

а) Транспортная задача.

Dorofey в сообщении #767264 писал(а):

3. Требуемое количество студентов по каждой специальности.
4. Ограничение на вместительность вузов (в каждый вуз помещается не более заданного количества студентов)

Если требуемое количество вузов по специальностей не совпадает с общей вместительности всех вузов, надо добавить "условный" ВУЗ или специальность с нулевыми коэффициентами.

[provincialka]

Честно говоря, не вижу, зачем здесь целевая функция. В п. а) упорядочивайте клетки таблицы по убыванию веса (произведения) и заполняйте сверху вниз. Тут будет больше проблем с ограничениями (сверху и снизу), чем с оптимизацией.

[Shadow]

provincialka в сообщении #767700 писал(а):

Честно говоря, не вижу, зачем здесь целевая функция

Если коэффициенты ячейки $C_{ij}$ - произведение рейтингов ВУЗ-а и специальности (в задаче надо полагать, они независимы, что на практике совсем не так), а число студентов $x_{ij}$, как я полагаю, надо максимизировать $\sum C_{ij}x_{ij}$ при ограничений на сумм по рядам и столбцов - класическая транспортная задача.

provincialka в сообщении #767700 писал(а):

упорядочивайте клетки таблицы по убыванию веса (произведения) и заполняйте сверху вниз

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

[provincialka]

Ну, может, и транспортная. Вернее, с вашей функцией - транспортная. Вообще вопрос "подберите мне целевую функцию" какой-то сомнительный.

[Dorofey]

Всем огромное спасибо за обстоятельные замечания!

Shadow в сообщении #767704 писал(а):

... - класическая транспортная задача.

По пункту a) понято, спасибо!

По-поводу независимости весов - считаем, что рейтинг специальностей определяется не их популярностью среди потребителей образовательных услуг, а социально-экономической стратегией государства (есть указивки Путина о приоритетных профессия - из этой серии). С этой точки зрения допущение о независимости уже не выглядит абсурдным.

provincialka в сообщении #767715 писал(а):

Ну, может, и транспортная. Вернее, с вашей функцией - транспортная. Вообще вопрос "подберите мне целевую функцию" какой-то сомнительный.

Уточню вопрос по п. b) Распределить студентов пропорционально рейтингам вузов и специальностей (т.е. суммы искомой матрицы распределения по строкам/столбцам должны быть пропорциональны весовым коэффициентам строк/столбцов, покуда это не противоречит ограничениям):
- К какому классу задач отнести такую постановку? Каков алгоритм такого распределения?

[provincialka]

Пункт б вообще непонятен, два критерия могут противоречить друг другу. Рассмотрим для простоты один критерий - вместимость. Путь вузы могут выпустить $100, 200, 200$ студентов. А из рейтинги - $5, 4, 2$. И как тут поступить? Ориентироваться на минимум, т.е. Запланировать $100, 80, 40$?

[Dorofey]

provincialka в сообщении #767912 писал(а):

Пункт б вообще непонятен, два критерия могут противоречить друг другу. Рассмотрим для простоты один критерий - вместимость. Путь вузы могут выпустить $100, 200, 200$ студентов. А из рейтинги - $5, 4, 2$. И как тут поступить? Ориентироваться на минимум, т.е. Запланировать $100, 80, 40$?

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

А какой еще критерий "оптимальности" распределения можно придумать?

[provincialka]

Придумать можно много чего, главное - зачем. В реальных задачах лучше начинать с эвристики, с формулировки "потребности": чего, собственно хочет автор.
Но вообще-то сама идея весов, измеряемых неизвестно в каких единицах довольно сомнительна.
Постановка в п. а) понятна, а чем она вам не нравится?

[Dorofey]

provincialka в сообщении #767949 писал(а):

Постановка в п. а) понятна, а чем она вам не нравится?

Нравится, с т.з. рынка образования.
Но она слабовата с т.з. управления образованием: получается, что мы под завязку набиваем лучших, и сливаем худших. Иногда требуется наоборот - "разумно" поддержать худших для развития. Хочется такой сценарий тоже реализовать в модели. отсюда навязчивая идея распределения "равномерного" (= справедливого) в каком-то смысле.

[provincialka]

Тогда просто сделайте все веса равными 1.