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

В этом случае целевая функция имеет вид:

→ max

Пусть имеем следующую матрицу стоимостей:

 

1 9 8 6

 

15 3 13 7

 

13 13 15 10

 

3 14 12 17

 

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

 

1 9 8 6 16 8 9 11

 

15 3 13 7 * (-1) + 17 = 2 14 4 10

 

13 13 15 10 4 4 2 7

 

3 14 12 17 14 3 5 0

 

2. Редуцируя матрицу,

8 0 1 3

C_э= 0 12 2 8

2 2 0 5

14 3 5 0

 

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

 

0 1 0 0

Х= 1 0 0 0

0 0 1 0

0 0 0 1

 

3. Методом проб и ошибок строим матрицу назначения Х и по ней вычисляем максимальное значение целевой функции:

F (x) = 9+15+15+17= 56 ед.

Задача о размещении производства.

Распределитель производства трех видов товаров Т_1,Т_2, Т₃ среди пяти предприятий П_1, П_2, П_3, П_4, П₅ с целью получения максимальной прибыли от продажи товаров со следующими данными:

издержки производства c_ij единицы товара (руб.)

	П1	П2	П3	П4	П5
Т1
Т2
Т3

затраты по сбыту d_ijединицы товара (руб.)

	П1	П2	П3	П4	П5
Т1
Т2
Т3

годовой спрос и цена товара (руб.)

	Спрос Qi (шт.)	Цена Pi(руб.)
Т1
Т2
Т3

Решение:

1.Экономико – математическая постановка задачи. Расчет прибыли для каждой пары «товар – производитель» T_i, П_j определяем по следующей модели: прибыль = цена – издержки – затраты:

h_ij= P_j - (c_ij+ d_ij)

Например, для пары Т₁– П₁ получим:

h₁₁= 60- (20+20)=20, и т.д.

Получим следующую матрицу

	П1	П2	П3	П4	П5
Т1		- 15
Т2		- 55		-15	- 30
Т3

 

Формируем матрицу годовой прибыли с учетом спроса:

H_ij= h_ij*Q_i,(тыс.руб.)

Для пары Т₁– П₁:

H₁₁ = 20*40000 = 800 тыс. руб. и т.д.

Получаем следующую матрицу:

	П1	П2	П3	П4	П5
Т1		- 600
Т2		- 11000		-300	- 6000
Т3

 

2. Модифицируем матрицу умножением всех элементов на (- 1) и сложением с максимальным числом матрицы (8000) и для устранения дисбаланса вводим два вида Т_4, Т₅ фиктивной продукции с нулевой прибылью, поскольку матрица должна быть квадратной:

	П1	П2	П3	П4	П5	min
Т1
Т2
Т3
Т4
Т5

 

3. Редуцируем матрицу по строкам и столбцам:

 

600 2000 1400 0 1000

 

1000 19000 0 11000 14000

 

180 480 0 780 480

 

0 0 0 0 0

0 0 0 0 0

 

4. Модифицируем матрицу путем исключения строк 4,5 и столбцов 3,4, получим сокращенную матрицу:

 

600 2000 1000 420 1820 820

 

1000 19000 14000 - 180 = 820 18820 13820

 

180 480 480 0 300 300

 

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

 

420 1820 1400 0 820

820 18820 0 11000 13820

С₃ = 0 300 0 780 300

0 0 180 180 0

0 0 180 180 0

 

по которой строим матрицу назначения:

 

420 1820 1400 0 820

 

820 18820 0 11000 13820

 

0 300 0 780 300

 

 

 

0 0 0 1 0

 

0 0 1 0 0

 

1 0 0 0 0

 

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

П_max= 1400+8000+1800= 11,2 млн. руб.

Таким образом, оптимальное решение данной задачи следующие: производство первого вида продукции назначается предприятию 4, второго вида - предприятию 3, третьего вида – предприятию 1. На предприятиях 2 и 5 производить данную продукцию нецелесообразно.

 

 

Задания к контрольной работе по теме «Задача о назначениях».

Вариант №1. Назначить четыре вида работ пяти машинам, чтобы минимизировать стоимость

	Виды работ
Машины

 

Вариант №2. Назначить четыре из пяти должностей пятерым работникам таким образом, чтобы максимизировать прибыль

	Должности
Кандидаты

Вариант №3. Назначить четыре вида работы пяти машинам, чтобы максимизировать прибыль

	Виды работ
Машины

Вариант №4. Назначить четыре из пяти должностей пятерым работникам таким образом, чтобы минимизировать стоимость

	Должности
Кандидаты

 

Вариант №5. Корпорации RMC требуется назначить пять должностей пятерым работникам, причем должность 1 должна быть назначена второму работнику. Найдите оптимальное решение на основе матрицы стоимостей, приведенной ниже

	Должности
Кандидаты

Вариант №6. Назначить пятерых рабочих на пять рабочих мест на основе матрицы стоимостей, приведенной ниже так, чтобы рабочий 2 был назначен на рабочее место 4 или 5

	Виды работ
Рабочие

Вариант №7. Корпорация BKW-фирма, состоящая из нескольких подразделений, которая предлагает работу. Прибыль от выполнения пяти видов работ каждым из шести подразделений, показана ниже. Найдите оптимальное решение. Какое подразделение получит работу? Почему?

	Виды работ
Отделы

Вариант №8. Назначить четыре из пяти должностей пятерым работникам таким образом, чтобы максимизировать прибыль, причем должность 4 должна быть обязательно назначена

 

	Должности
Работники

Вариант №9. К матрице прибыли, приведенной ниже, добавить дополнительного работника, который может выполнять виды работ 1, 3 и 5 с прибылью 50, 20 и 100 соответственно. Этот работник, однако, не способен выполнять виды работ 2 и 4. Найти оптимальное решение

	Виды работ
Работники

Вариант №10. Найти минимальное и максимальное решение для задачи назначений, приведенной ниже

	Виды работ
Работники	A
B
C
D
E

Вариант №11. 6 претендентов на 5 должностей проходят собеседование. "Оценка"каждого претендента и его ежемесячная зарплата при выполнении различных видов работ показаны ниже в двух отдельных матрицах. Определите назначение на работу на основе "оценки" и отдельно на основе зарплаты. Какова разница в стоимости наилучшего назначения, если вместо минимизации зарплаты максимизировать "оценку?" Содержимое ячеек матрицы не обязательно выражается в долларах или каких-либо денежных единицах.

 

 

"Оценка" претендента за месяц

 

	Должности
Претенденты

 

Ежемесячная зарплата претендента

	Должности
Претенденты

Вариант №12. В цехе шесть рабочих были специально подготовлены для обслуживания определенных станков. Эти рабочие могут работать на любом из пяти станков. Цех имеет много заказов и все пять станков постоянно заняты. Один из рабочих, не занятых обслуживанием станка, обычно выполняет канцелярскую работу. На основе приведенного ниже плана стоимости обслуживания каждого станка каждым из пяти рабочих определить оптимальные назначения.

	Станки
Рабочие	A
B
C
D
E
F

 

Вариант №13. Некий продавец собирается продать 4 автомобиля. Основываясь на ценах, предложенных четырьмя потенциальными покупателями, определить, какую машину должен получить каждый из них, чтобы максимизировать прибыль продавца.

 

	Chevy	Ford	Dodge	Pontiac
Carol	5,000	4,000	3,200	4,900
John	3,500	3,500	3,100	5,000
Harry	4,200	3,700	2,950	4,750
Paul	3,800	4,100	3,000	4,600

 

 

Вариант №14. Некий продавец собирается продать 4 автомобиля. Потенциальными покупателями являетесь Вы и Ваши партнеры. Предложенные Вами и Вашими партнерами цены приведены ниже. Решите эту задачу так, чтобы минимизировать Ваши расходы и расходы Ваших партнеров.

	Chevy	Ford	Dodge	Pontiac
Carol	5,000	4,000	3,200	4,900
John	3,500	3,500	3,100	5,000
Harry	4,200	3,700	2,950	4,750
Paul	3,800	4,100	3,000	4,600

 

Распределить работы таким образом, чтобы минимизировать временные затраты на выполнение всех работ при условии, что каждый из претендентов получит одну и только одну из работ. Матрица временных затрат каждого претендента на выполнение каждой из работ приведена ниже.

Вариант № 15.

Работники	Номера работ
Иванов
Петров
Сидоров
Копылов
Минин
Резько

Вариант № 16.

Работники	Номера работ
Качурова
Панова
Стевко
Санин
Пинских
Петров

Вариант № 17.

Работники	Номера работ
Володин
Ганшин
Попов
Сидоров
Хаджиев
Зорин

Вариант № 18.

Работники	Номера работ
Чертков
Демичев
Фурцева
Токин
Столяров
Носов

 

Вариант № 19.

Работники	Номера работ
Суслов
Ларин
Выгонова
Петров
Васин
Титов

Вариант № 20.

Работники	Номера работ
Беляев
Сидоров
Ваничкин
Зайцева
Ватагин
Родин

 

Вариант № 21.

Работники	Номера работ
Шорин
Волков
Чайников
Летвинов
Дорина
Быкова

Вариант № 22.

Работники	Номера работ
Скляров
Данин
Панина
Шолохов
Власенко
Сытин

Вариант № 23.

Работники	Номера работ
Тыквин
Болшев
Строгина
Жданов
Чёрный
Ногина

 

Вариант № 24.

Работники	Номера работ
Костина
Кузнецов
Швындин
Петров
Сидоров
Иваненко

 

Вариант № 25.

Работники	Номера работ
Никитин
Коткова
Равин
Глатерман
Чуйкова
Санченко

Вариант № 26.

Работники	Номера работ
Сеченов
Кудрявцев
Попкова
Танин
Воловик
Пьянова

 

Вариант № 27.

Работники	Номера работ
Иванов
Петров
Сидоров
Васин
Лорин
Борисова

 

Вариант № 28.

Работники	Номера работ
Вырин
Карина
Рожнев
Суслова
Пинкин
Лапин

Вариант № 29.

Работники	Номера работ
Анукин
Павлова
Динченко
Волохов
Ританин
Бобова

 

Вариант № 30.

Работники	Номера работ
Говорухин
Панюшкин
Попков
Ратникова
Капин
Мастерова

Тестовые задания по теме

«Задача о назначениях»

1. Задача о назначениях относится к классу задач:

1) линейного программирования;

2) эконометрических;

3) статистических;

4) имитационных;

5) не относится ни к одному из указанных классов.

 

2. Имеются две работы r₁, r₂ и два рабочих L₁, L₂, каждый из которых может выполнить любую работу. Элементы a_ij матрицы А показывает время, необходимое рабочему i для выполнения работы j.

Матрица А

Работа   Рабочий	r1	r2
L1
L2

Решите задачу о назначениях. Чему равно минимальное время выполнения двух работ?

Варианты ответов:
1) 9; 2) 10; 3) 11; 4) 12; 5)13.

 

3. Оптимальный план задачи о назначениях можно представить в виде:

1) квадратной матрицы, в каждой строке которой находится одна единица;

2) квадратной матрицы, в каждом столбце которой находится одна единица;

3) квадратной матрицы, в каждой строке и в каждом столбце которой находится одна единица;

4) квадратной матрицы, в каждой строке которой находится хотя бы одна единица;

5) квадратной матрицы, в каждом столбце которой находится хотя бы одна единица.

 

4. Имеются две работы r₁, r₂ и три рабочих L₁, L₂ и L_3, каждый из которых может выполнить любую работу. Элементы a_ij матрицы А показывает время, необходимое рабочему i для выполнения работы j.

Матрица А

Работа   Рабочий	r1	r2
L1
L2
L3

Решите задачу о назначениях. Чему равно минимальное время выполнения двух работ?

Варианты ответов:
1) 5; 2) 6; 3) 7; 4) 8; 5)9.

 

5. Фирма получила заказы на разработку пяти программных продуктов. Для выполнения этих заказов решено привлечь пятерых наиболее опытных программистов. Каждый из них должен написать одну программу. В следующей таблице приведены оценки времени (в днях), необходимого программистам для выполнения каждой из этих работ. Оценки даны самими программистами, и у фирмы нет основания им не доверять.

 

 

Программа   Программист
Галкин
Палкин
Малкин
Чалкин
Залкин

После редукции матрицы по строкам получили:

1) верно; 2) не верно.

 

6. Фирма получила заказы на разработку пяти программных продуктов. Для выполнения этих заказов решено привлечь пятерых наиболее опытных программистов. Каждый из них должен написать одну программу. В следующей таблице приведены оценки времени (в днях), необходимого программистам для выполнения каждой из этих работ. Оценки даны самими программистами, и у фирмы нет основания им не доверять.

 

 

Программа   Программист
Галкин
Палкин
Малкин
Чалкин
Залкин

 

 

После редукции матрицы по строкам получили:

1) верно; 2) не верно.

 

7. Фирма получила заказы на разработку пяти программных продуктов. Для выполнения этих заказов решено привлечь пятерых наиболее опытных программистов. Каждый из них должен написать одну программу. В следующей таблице приведены оценки времени (в днях), необходимого программистам для выполнения каждой из этих работ. Оценки даны самими программистами, и у фирмы нет основания им не доверять.

 

Программа   Программист
Галкин
Палкин
Малкин
Чалкин
Залкин

 

 

После редукции матрицы по строкам получили:

1) верно; 2) не верно.

 

8. Фирма получила заказы на разработку пяти программных продуктов. Для выполнения этих заказов решено привлечь пятерых наиболее опытных программистов. Каждый из них должен написать одну программу. В следующей таблице приведены оценки времени (в днях), необходимого программистам для выполнения каждой из этих работ. Оценки даны самими программистами, и у фирмы нет основания им не доверять.

 

 

Программа   Программист
Галкин
Палкин
Малкин
Чалкин
Залкин

 

 

После редукции матрицы по строкам получили:

1) верно; 2) не верно.

Тематика рефератов.

 

1. Технология принятия решений в области занятости населения.

2. Технология принятия решения в области совершенствования кадрового состава организации.

3. Технология принятия решения в области перехода предприятия на новый вид промышленной продукции.

4. Технология принятия решения в области повышения качества промышленного товара.

5. Технология принятия решения в области совершенствования деятельности потребительской кооперации.

6. Технология принятия решения в области повышения качества продовольственного товара.

7. Технология принятия решения в области перехода фирмы на новый вид продовольственной продукции.

8. Технология принятия решения в сфере коммунального обслуживания населения.

9. Технология принятия решения по улучшению экологической обстановки в области.

10. Технология принятия решения по совершенствованию структуры организации.

11. Оценка качества и эффективности разработки управленческих решений.

12. Системный подход к разработке управленческих решений.

13. Внешняя среда и ее влияние на разработку, и реализацию управленческого решения.

14. Выбор и классификация методов решений в управленческой деятельности.

15. Коммуникации и их роль в управленческом решении.

16. Информационные процессы и потоки в управлении (характеристики и классификация).

17. Использование метода «дерева решений» при формировании управленческого решения.

18. Технология организации и проведения «мозгового штурма».

19. Технология организации и проведения экспертного опроса методом «Дельфи».

20. Технология организации и проведения морфологического анализа.

21. Понятие метода иерархий при анализе альтернативных вариантов.

22. Экспертные системы как средство поддержки управленческого решения.

23. Использование сетевых технологий для получения информации необходимой для принятия управленческого решения.

24. Основные категории и понятия теории систем.

25. Использование методов линейного программирования при выборе окончательного варианта решения.

26. Понятия о многокритериальных задачах выбора.

27. Использование функции полезности в задачах формирования управленческого решения.

28. Анализ существующих компьютерных средств поддержки управленческого решения.

29. Анализ возможностей табличного процессора «Excel» как средства поддержки управленческого решения.

30. Технология использования функционального – стоимостного анализа в разработке управленческого решения.

31. Использование метода сценариев при формировании управленческого решения.

32. Способы оценки степени риска. Управление риском.

 

Вопросы для самопроверки и подготовки к экзамену

 

1. Сформулировать постановку следующих экономико-математических моделей: линейной модели производства, задачи, транспортной задачи, задачи о назначениях.

2. Описать экономический смысл целевой функции, ограничений, основных и дополнительных переменных транспортной задачи.

3. Описать экономический смысл целевой функции, ограничений, основных и дополнительных переменных в линейной модели производства.

4. Описать экономический смысл целевой функции, ограничений, основных и дополнительных переменных в задаче о назначениях.

5. Геометрическая интерпретация целевой функции задачи линейного программирования.

6. Описать алгоритм графического метода решения линейных задач.
7. Перечислить особые случаи решения задачи линейного программирования графическим методом.

8. Записать каноническую форму записи задачи линейного программирования.

9. Записать стандартную форму записи задачи линейного программирования.

10. Записать правила перехода от стандартной формы записи линейной задачи к канонической форме записи.