2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Задача распределения набора в вузы по специальностям
Сообщение24.09.2013, 12:34 


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

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

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

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

 Профиль  
                  
 
 Re: Задача распределения набора в вузы по специальностям
Сообщение24.09.2013, 22:02 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Задача распределения набора в вузы по специальностям
Сообщение25.09.2013, 14:52 


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

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

 Профиль  
                  
 
 Re: Задача распределения набора в вузы по специальностям
Сообщение25.09.2013, 15:21 


26/08/11
2057
Dorofey в сообщении #767687 писал(а):
1. Вузы и специальности - это матрица, на пересечении которой стоят количества студентов. Т.е. считается, что все специальности есть во всех вузах. Дополнительно можно задать набор ограничений сверху и снизу на каждую компоненту матрицы.
2. Вес пары (вуз, специальность) определяется по условию задачи как произведение весов компонент.
3. Других ограничений нет (распределяют в конечном итоге не людей, а контрольные цифры приема).
а) Транспортная задача.
Dorofey в сообщении #767264 писал(а):
3. Требуемое количество студентов по каждой специальности.
4. Ограничение на вместительность вузов (в каждый вуз помещается не более заданного количества студентов)
Если требуемое количество вузов по специальностей не совпадает с общей вместительности всех вузов, надо добавить "условный" ВУЗ или специальность с нулевыми коэффициентами.

 Профиль  
                  
 
 Re: Задача распределения набора в вузы по специальностям
Сообщение25.09.2013, 15:30 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача распределения набора в вузы по специальностям
Сообщение25.09.2013, 15:40 


26/08/11
2057
provincialka в сообщении #767700 писал(а):
Честно говоря, не вижу, зачем здесь целевая функция
Если коэффициенты ячейки $C_{ij}$ - произведение рейтингов ВУЗ-а и специальности (в задаче надо полагать, они независимы, что на практике совсем не так), а число студентов $x_{ij}$, как я полагаю, надо максимизировать $\sum C_{ij}x_{ij}$ при ограничений на сумм по рядам и столбцов - класическая транспортная задача.
provincialka в сообщении #767700 писал(а):
упорядочивайте клетки таблицы по убыванию веса (произведения) и заполняйте сверху вниз
Ну, это будет опорный план, дальше нужно еще поработать.Метод потенциалов или "падающего камня" - про явторого только слышал, не решал.

 Профиль  
                  
 
 Re: Задача распределения набора в вузы по специальностям
Сообщение25.09.2013, 16:22 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача распределения набора в вузы по специальностям
Сообщение26.09.2013, 09:09 


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

Shadow в сообщении #767704 писал(а):
... - класическая транспортная задача.


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

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

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


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

 Профиль  
                  
 
 Re: Задача распределения набора в вузы по специальностям
Сообщение26.09.2013, 10:21 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача распределения набора в вузы по специальностям
Сообщение26.09.2013, 14:45 


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

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

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

 Профиль  
                  
 
 Re: Задача распределения набора в вузы по специальностям
Сообщение26.09.2013, 15:06 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача распределения набора в вузы по специальностям
Сообщение27.09.2013, 10:15 


24/09/13
5
provincialka в сообщении #767949 писал(а):
Постановка в п. а) понятна, а чем она вам не нравится?


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

 Профиль  
                  
 
 Re: Задача распределения набора в вузы по специальностям
Сообщение27.09.2013, 10:18 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
Тогда просто сделайте все веса равными 1.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group