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

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

Типичное задание:
Компании нужно направить коммивояжеров в новые рынки сбыта. Имеется три вакансии и четыре кандидата. Результат назначения кандидата на определенное место определяется ожидаемым увеличением прибыли. Прибыль, которую может дать кандидат, работая на той или иной территории, показана в таблице.
Исходная матрица имеет вид:
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. В качестве целевой функции выбираем Максимальная прибыль.