Index · Правила · Поиск· Группы · Регистрация · Личные сообщения· Вход

Список разделов Нужна помощь
 
 
 

Раздел: Нужна помощь Помогите рещить задачу линейного программирования 

Создана: 11 Мая 2013 Суб 16:05:24.
Раздел: "Нужна помощь"
Сообщений в теме: 23, просмотров: 2313

На страницу: Назад  1, 2  Вперёд
  1. Y@shok


    Частый гость


    Более 10 лет на форумеМуж.
    11 Мая 2013 Суб 16:05:24
    Всем привет!

    Дано собственно:
    10 кандидатов, 7 предметных областей.
    Ни один из какндидатов не разбирается во всех семи областях одновременно. Можно представить в виде бинарной матрицы (10 строк, 7 столбцов), где "1" означает, что кандидат разбирается в данной области, "0" - нет :
    1234567
    (к1) 1010100
    (к2) 0010000
    ........
    (к10) 1100100

    Как найти номера кандидатов, которых необходимо принять на работу, чтобы при этом все предметные области были перекрыты их знаниями с наименьшим числом дублирования знаний. Все кандидаты готовы работать за одну и ту же ЗП. Количество нанятых кандидатов не имеет значения. Главное чтобы было наименьшее кол-во дублируемых знаний у кандидатов.
  2. Teruro


    Хранитель


    Более 10 лет на форумеУчастнику дано предупреждение от модератораМуж.
    11 Мая 2013 Суб 17:22:19
    Y@shok писал :Как найти номера кандидатов

    Если решать "в лоб", то
    1. методом перебора получаем 2^10 варианта найма кандидатов,
    2. для каждого варианта проверяем удовлетворяет ли он условию покрытия всех предметных областей.
    3. если да, то считаете для него количество "штрафных баллов".
    4. оставляете вариант с минимальными штрафными баллами.
    всё.
  3. 11 Мая 2013 Суб 17:26:11
    Teruro писал : всё.

    Хлопец
  4. Y@shok


    Частый гость


    Более 10 лет на форумеМуж.
    11 Мая 2013 Суб 17:48:05
    Teruro писал :
    Если решать "в лоб", то
    1. методом перебора получаем 2^10 варианта найма кандидатов,


    Почему 2 в десятой степени?
  5. 11 Мая 2013 Суб 19:51:45
    Я бы вычислил количество "единиц" у каждого кандидата, затем отсортировал этих кандидатов по количеству "единиц" и начал прием на работу с тех, у кого этих "единиц" меньше всего ("счастливчики"). Очередной кандидат принимался бы на работу, если бы его знания могли бы "закрыть" хотя бы одну предметную область. С его зачислением, эта(и) область(и) считается закрытой. Прием кандидатов останавливается, когда все предметные области будут закрыты.
  6. Teruro


    Хранитель


    Более 10 лет на форумеУчастнику дано предупреждение от модератораМуж.
    11 Мая 2013 Суб 23:02:54
    Y@shok писал :Почему 2 в десятой степени?

    Потому что каждого из 10-и кандидатов можно или нанять, или не нанять.

    Впрочем, если вам от этого будет легче, можете выбросить из рассмотрения варианты, в которых нанимается более 7-и кандидатов. Но, мне кажется, вы на проверку этого условия половину времени решения потратите (своего, а не машинного).
  7. Teruro


    Хранитель


    Более 10 лет на форумеУчастнику дано предупреждение от модератораМуж.
    11 Мая 2013 Суб 23:05:00
    туннель писал(а) :Я бы вычислил количество "единиц" у каждого кандидата, затем отсортировал этих кандидатов по количеству "единиц" и начал прием на работу с тех, у кого этих "единиц" меньше всего

    К сожалению, этот алгоритм не даёт правильного решения.

    Контрпример:
    К1: 1000000
    К2: 1111111
    К3-К10: 0000000
  8. 12 Мая 2013 Вск 0:41:07
    Teruro писал :
    туннель писал(а):

    К сожалению, этот алгоритм не даёт правильного решения.

    Контрпример:
    К1: 1000000
    К2: 1111111
    К3-К10: 0000000

    по условию К2 не может быть 1111111.
  9. 12 Мая 2013 Вск 0:52:02
    вообще странная постановка задачи или я неверно моделирую.
    пусть C (m,n)-матрица знаний где Cij осведомленность i-кандидата в области j.
    X вектор размерости m наймов на работу (Xi = { 1, 0 })
    XC = Y вектор покрытия предметных областей.
    предлагается минимизация функции count(Yi | Yi > 1) при ограничении Yi >= 1?
  10. 12 Мая 2013 Вск 1:11:54
    spectrum писал(а) ? ? :

    XC = Y вектор покрытия предметных областей,
    а должна получаться и исследоваться Y -матрица покрытия предметных областей "зачисленных" кандидатов
  11. 12 Мая 2013 Вск 1:14:28
    почему матрица-то?
    вектор тоже матрица Confused
  12. 12 Мая 2013 Вск 1:43:03
    spectrum писал(а) : почему матрица-то?
    вектор тоже матрица Confused

    Вектор это "одномерная" матрица. В итоге задачи должны выйти отобранные кандидаты со своими знаниями в областях. А это можно описать только двумерной матрицей. Нам необходимо иметь ее в ответе, потому что на ее элементы, по задаче, наложены условия (не на всю исходную матрицу, а на эту, выбранную).
  13. 12 Мая 2013 Вск 1:53:33
    туннель писал(а) : В итоге задачи должны выйти отобранные кандидаты со своими знаниями в областях.

    в итоге задачи должны выйти отобранные кандидаты что описывается вектором
  14. 12 Мая 2013 Вск 7:43:50
    spectrum писал(а) :
    туннель писал(а) ... : В итоге задачи должны выйти отобранные кандидаты со своими знаниями в областях.

    в итоге задачи должны выйти отобранные кандидаты что описывается вектором

    Если иметь в виду номера отобранных кандидатов, то Вы безусловно правы и в окончательном итоге задачи именно это и спрашивается.
    Следовательно, в предложенном мною алгоритме необходимо изначально кандидатам "прикрепить бейджики с номерами", а в конце алгоритма "отобрать у принятых кандидатов" их бейджики. Эта "банка" с бейджиками и будет итогом.
  15. Teruro


    Хранитель


    Более 10 лет на форумеУчастнику дано предупреждение от модератораМуж.
    12 Мая 2013 Вск 8:17:54
    туннель писал(а) :по условию К2 не может быть 1111111.

    Тогда
    К1: 1000000
    К2: 1110000
    К3: 0001111
    К4-К10: 0000000
На страницу: Назад  1, 2  Вперёд