Контрольная на тему Контрольная работа 111124-01

Контрольная работа № 1

Задача № 1 Служба занятости имеет в наличии четыре вакантных места по разным специальностям, на которые претендуют четыре человека. Проведено тестирование претендентов, результаты которого в виде баллов представлены в матрице. Распределить по данным, представленным в таблице, претендентов на вакантные места таким образом, чтобы на каждое место был назначен человек с наибольшим набранным по тестированию баллом.








3
9
1
3

7
0
4
5

4
4
4
3

2
0
6
5







Решение
Математическая модель задачи о назначении:
F = ??cijxij > max , (1) где набранные баллы, х - претендент
при условиях:
?xij = ai, i = 1,2,…, m, (2)
?xij = bj, j = 1,2,…, n, (3)
Баллы претендентов заданы таблицей:


1
2
3
4
Претенденты

1
3
9
1
3
1

2
7
0
4
5
1

3
4
4
4
3
1

4
2
0
6
5
1

Вакансия
1
1
1
1



Проверим необходимое и достаточное условие разрешимости задачи.
?a = 1 + 1 + 1 + 1 = 4
?b = 1 + 1 + 1 + 1 = 4
Условие баланса соблюдается.

Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую претенденту, либо столбец, соответствующий вакансии.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен 0
Для этого элемента запасы равны 1, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x22 = min(1,1) = 1.

3
x
1
3
1

x
0
x
x
1 - 1 = 0

4
x
4
3
1

2
x
6
5
1

1
1 - 1 = 0
1
1
0


Искомый элемент равен 1
Для этого элемента запасы равны 1, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x13 = min(1,1) = 1.

x
x
1
x
1 - 1 = 0

x
0
x
x
0

4
x
x
3
1

2
x
x
5
1

1
0
1 - 1 = 0
1
0


Искомый элемент равен 2
Для этого элемента запасы равны 1, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x41 = min(1,1) = 1.

x
x
1
x
0

x
0
x
x
0

x
x
x
3
1

2
x
x
x
1 - 1 = 0

1 - 1 = 0
0
0
1
0


Искомый элемент равен 3
Для этого элемента запасы равны 1, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x34 = min(1,1) = 1.

x
x
1
x
0

x
0
x
x
0

x
x
x
3
1 - 1 = 0

2
x
x
x
0

0
0
0
1 - 1 = 0
0



1
2
3
4
претенденты

1
3
9
1[1]
3
1

2
7
0[1]
4
5
1

3
4
4
4
3[1]
1

4
2[1]
0
6
5
1

Вакансии