Нужна помощь
Помогите рещить задачу линейного программирования
Создана: 11 Мая 2013 Суб 16:05:24.
Раздел: "Нужна помощь"
Сообщений в теме: 23, просмотров: 2500
-
11 Мая 2013 Суб 16:05:24Всем привет!
Дано собственно:
10 кандидатов, 7 предметных областей.
Ни один из какндидатов не разбирается во всех семи областях одновременно. Можно представить в виде бинарной матрицы (10 строк, 7 столбцов), где "1" означает, что кандидат разбирается в данной области, "0" - нет :
1234567
(к1) 1010100
(к2) 0010000
........
(к10) 1100100
Как найти номера кандидатов, которых необходимо принять на работу, чтобы при этом все предметные области были перекрыты их знаниями с наименьшим числом дублирования знаний. Все кандидаты готовы работать за одну и ту же ЗП. Количество нанятых кандидатов не имеет значения. Главное чтобы было наименьшее кол-во дублируемых знаний у кандидатов. -
11 Мая 2013 Суб 17:22:19Y@shok писал
:Как найти номера кандидатов
Если решать "в лоб", то
1. методом перебора получаем 2^10 варианта найма кандидатов,
2. для каждого варианта проверяем удовлетворяет ли он условию покрытия всех предметных областей.
3. если да, то считаете для него количество "штрафных баллов".
4. оставляете вариант с минимальными штрафными баллами.
всё. -
-
11 Мая 2013 Суб 19:51:45Я бы вычислил количество "единиц" у каждого кандидата, затем отсортировал этих кандидатов по количеству "единиц" и начал прием на работу с тех, у кого этих "единиц" меньше всего ("счастливчики"). Очередной кандидат принимался бы на работу, если бы его знания могли бы "закрыть" хотя бы одну предметную область. С его зачислением, эта(и) область(и) считается закрытой. Прием кандидатов останавливается, когда все предметные области будут закрыты.
-
11 Мая 2013 Суб 23:02:54Y@shok писал :Почему 2 в десятой степени?
Потому что каждого из 10-и кандидатов можно или нанять, или не нанять.
Впрочем, если вам от этого будет легче, можете выбросить из рассмотрения варианты, в которых нанимается более 7-и кандидатов. Но, мне кажется, вы на проверку этого условия половину времени решения потратите (своего, а не машинного). -
11 Мая 2013 Суб 23:05:00туннель писал(а) :Я бы вычислил количество "единиц" у каждого кандидата, затем отсортировал этих кандидатов по количеству "единиц" и начал прием на работу с тех, у кого этих "единиц" меньше всего
К сожалению, этот алгоритм не даёт правильного решения.
Контрпример:
К1: 1000000
К2: 1111111
К3-К10: 0000000 -
-
12 Мая 2013 Вск 0:52:02вообще странная постановка задачи или я неверно моделирую.
пусть C (m,n)-матрица знаний где Cij осведомленность i-кандидата в области j.
X вектор размерости m наймов на работу (Xi = { 1, 0 })
XC = Y вектор покрытия предметных областей.
предлагается минимизация функции count(Yi | Yi > 1) при ограничении Yi >= 1? -
-
12 Мая 2013 Вск 1:43:03
Вектор это "одномерная" матрица. В итоге задачи должны выйти отобранные кандидаты со своими знаниями в областях. А это можно описать только двумерной матрицей. Нам необходимо иметь ее в ответе, потому что на ее элементы, по задаче, наложены условия (не на всю исходную матрицу, а на эту, выбранную). -
12 Мая 2013 Вск 7:43:50
Если иметь в виду номера отобранных кандидатов, то Вы безусловно правы и в окончательном итоге задачи именно это и спрашивается.
Следовательно, в предложенном мною алгоритме необходимо изначально кандидатам "прикрепить бейджики с номерами", а в конце алгоритма "отобрать у принятых кандидатов" их бейджики. Эта "банка" с бейджиками и будет итогом. -
