Примеры решений Транспортная задача Теория игр Поток сети Параметры сетевой модели Задача коммивояжера Метод Гомори Симплексный метод Графический метод Многоканальные СМО

Задача о назначениях. Нахождение максимальной прибыли

Типичное задание:
Компании нужно направить коммивояжеров в новые рынки сбыта. Имеется три вакансии и четыре кандидата. Результат назначения кандидата на определенное место определяется ожидаемым увеличением прибыли. Прибыль, которую может дать кандидат, работая на той или иной территории, показана в таблице.
Исходная матрица имеет вид:
5 5 M 2 2
7 4 2 3 1
9 3 5 M 2
7 2 6 7 8

Решение получаем через калькулятор.
Модифицируем матрицу умножением всех элементов на (-1) и затем сложением их с максимальным элементом матрицы (9) так, чтобы матрица не содержала бы отрицательных элементов:

4 4 M 7 7
2 5 7 6 8
0 6 4 M 7
2 7 3 2 1

Для устранения дисбаланса добавляем дополнительные строки.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
0 0 M 3 3 4
0 3 5 4 6 2
0 6 4 M 7 0
1 6 2 1 0 1
0 0 0 0 0 0

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
0 0 M 3 3
0 3 5 4 6
0 6 4 M 7
1 6 2 1 0
0 0 0 0 0
0 0 0 0 0

После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

[0]

[-0-]

M

3

3

[-0-]

3

5

4

6

[-0-]

6

4

M

7

1

6

2

1

[-0-]

[-0-]

[-0-]

[-0-]

[-0-]

[0]

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

0

0

M

3

3

0

3

5

4

6

0

6

4

M

7

1

6

2

1

0

0

0

0

0

0

Минимальный элемент сокращенной матрицы (1) вычитаем из всех ее элементов:

0

0

M

3

3

0

2

4

3

6

0

5

3

M

7

1

5

1

0

0

0

0

0

0

0

Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:

1

0

M

3

4

0

2

4

3

6

0

5

3

M

7

1

5

1

0

0

1

0

0

0

1

1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

1

0

M

3

4

0

0

2

4

3

6

0

0

5

3

M

7

0

1

5

1

0

0

0

1

0

0

0

1

0

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:

1

0

M

3

4

0

2

4

3

6

0

5

3

M

7

1

5

1

0

0

1

0

0

0

1

0

0

0

0

0

После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

1

[0]

M

3

4

[0]

2

4

3

6

[-0-]

5

3

M

7

1

5

1

[-0-]

[0]

1

[-0-]

[-0-]

[0]

1

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

1

0

M

3

4

0

2

4

3

6

0

5

3

M

7

1

5

1

0

0

1

0

0

0

1

Минимальный элемент сокращенной матрицы (3) вычитаем из всех ее элементов:

1

0

M

0

1

0

2

1

0

3

0

5

0

M

4

1

5

1

0

0

1

0

0

0

1

Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:

1

0

M

0

1

0

2

1

0

3

0

5

0

M

4

4

8

1

0

0

4

3

0

0

1

1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

1

0

M

0

1

0

0

2

1

0

3

0

0

5

0

M

4

0

4

8

1

0

0

0

4

3

0

0

1

0

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:

1

0

M

0

1

0

2

1

0

3

0

5

0

M

4

4

8

1

0

0

4

3

0

0

1

0

0

0

0

0

После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

1

[0]

M

[-0-]

1

[-0-]

2

1

[0]

3

[0]

5

[-0-]

M

4

4

8

1

[-0-]

[0]

4

3

[0]

[-0-]

1

В результате получаем эквивалентную матрицу Сэ:

1

0

M

0

1

0

2

1

0

3

0

5

0

M

4

4

8

1

0

0

4

3

0

0

1

4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить максимальное значение прибыли.

1

[0]

M

[-0-]

1

[-0-]

2

1

[0]

3

[0]

5

[-0-]

M

4

4

8

1

[-0-]

[0]

4

3

[0]

[-0-]

1

Cmax = 3 + 5 + 9 + 8 + 0 = 25
Альтернативный вариант №2.

1

[0]

M

[-0-]

1

[0]

2

1

[-0-]

3

[-0-]

5

[0]

M

4

4

8

1

[-0-]

[0]

4

3

[-0-]

[0]

1


 Cmax = 8 + 5 + 7 + 5 + 0 = 25

Перейти к онлайн решению своей задачи

Решение задачи о назначении на максимум

Распределить производство трех видов товара Т1, Т2, Т3 среди пяти предприятий П1, П2, П3, П4, П5 с целью получения максимальной прибыли от продажи товаров по следующим данным:
Издержки производства cij единицы товара

 

П1

П2

П3

П4

П5

Т1

20

25

40

15

35

Т2

10

30

5

35

35

Т3

5

10

2

5

10

Затраты по сбыту dij единицы товара

 

П1

П2

П3

П4

П5

Т1

20

50

20

10

15

Т2

10

80

10

35

50

Т3

5

5

5

15

5

Годовой спрос и цена товара

 

Спрос, Qi

Цена, Pi

Т1

40000

60

Т2

200000

55

Т3

60000

40

Решение:
Экономико-математическая постановки задачи. Расчет прибыли для каждой пары товара-производитель Ti, Пi определяем по следующей модели:
прибыль = цена – издержки – затраты
hij = Pj – (cij + dij)

 

П1

П2

П3

П4

П5

Т1

20

-15

0

35

10

Т2

35

-55

40

-15

-30

Т3

30

25

33

20

25

Формируем матрицу годовой прибыли с учетом спроса Qi.
Hij = hij * Qi

 

П1

П2

П3

П4

П5

Т1

800

-600

0

1400

400

Т2

7000

-11000

8000

-3000

-6000

Т3

1800

1500

1980

1200

1500

Полученные данные обрабатываем с помощью сервиса Задача о назначениях. Выбираем количество столбцов равное 5, количество строк - 3. Заполняем матрицу Hij. В качестве целевой функции выбираем Максимальная прибыль.
Профессии будущего
РБК Тренды изучили прогнозы российских и зарубежных футурологов, и составили список самых востребованных профессий в ближайшие 30 лет. Это профессии из 19 отраслей: от медицины и транспорта до культуры и космоса
Подробнее
Налоговый вычет на обучение
√ 120 тыс. руб. - максимальная сумма расходов на обучение
√ вычет от государства
√ вычет от работодателя
Подробнее
Требуются авторы студенческих работ!
  • регулярный поток заказов;
  • стабильный доход
Подробнее
Курсовые на заказ