2 Практическая часть

Условие задачи. Пусть имеются nкандидатов для выполнения этих работ. Назначение кандидатаiна работуjсвязано с затратамиC_ij (i,j= 1,2,…,n). Требуется найти назначение кандидатов на все работы, дающие минимальные суммарные затраты, при этом каждого кандидата можно назначать только на одну работу и каждая работа может быть занята только одним кандидатом. Исходные данные приведены в таблице:

Таблица .2.4 Исходные данные

AiBj	B1	B2	B3	B4
A1	3	7	3	8
A2	2	4	4	5
A3	4	7	2	8
A4	9	7	3	8

входные данные:

n– количество кандидатов и работ, целый тип данных

C(n,n) - затраты (руб.), вещественный тип данных.

Выходные данные:

Smin- суммарные затраты (руб.), вещественный тип данных;

X(n,n) - назначение кандидата на работу, целый тип данных.

2.1 Решение задачи с помощью математического аппарата

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

Таблица 2.1.1 Опорный план методом минимальной стоимости

Ai Bj	B1	B2	B3	B4
A1	3 0	7 1	3 0	8 –
A2	2 1	4 –	4 –	5 –
A3	4 –	7 –	2 1	8 –
A4	9 –	7 –	3 0	8 1

Минимальные суммарные затраты составят:

F=0*3+1*7+0*3+1*2+1*2+0*3+1*8=19

Для нахождения оптимального плана используем метод потенциалов.

Составим систему уравнений U_i+V_j =C_ijдля заполненных клеток транспортной таблицы и определим значенияU_iиV_j.

U₁+V₁=3U₁=0V₁=3

U₁+V₂=7U₂=-1V₂=7

U₁+V₃=3U₃=0V₃=3

U₂+V₁=2U₄=0V₄=8

U₃+V₃=3

U₄+V₃=3

U₄+V₄=8

Рассчитаем величины ∆_ij=U_i+V_j-C_ijдля свободных клеток таблицы.

∆₁₄=U₁+V₄-C₁₄=0+8-8=0

∆₂₂=U₂+V₂-C₂₂=-1+7-4=2

∆₂₃=U₂+V₃-C₂₃=-1+3-4=-2

∆₂₄=U₂+V₄-C₂₄=-1+8-5=2

∆₃₁=U₃+V₁-C₃₁=0+3-4=-1

∆₃₂=U₃+V₂-C₃₂=0+7-7=0

∆₃₄=U₃+V₄-C₃₄=0+8-8=0

∆₄₁=U₄+V₁-C₄₁=0+3-9=-6

∆₄₂=U₄+V₂-C₄₂=0+7-7=0

Так как есть положительные значения, план является не оптимальным. Необходимо выбрать наибольшее положительное число и осуществить сдвиг по циклу для выбранной клетки.

Таблица 2.1.3 Опорный план методом потенциалов

Ai Bj	B1	B2	B3	B4
A1	3 1	7 –	3 0	8 –
A2	2 0	4 1	4 –	5 –
A3	4 –	7 –	2 1	8 –
A4	9 –	7 –	3 0	8 1

Проверим полученный план на оптимальность.

U₁+V₁=3U₁=0V₁=3

U₁+V₃=3U₂=-1V₂=5

U₂+V₁=2U₃=-1V₃=3

U₂+V₂=4U4=0V₄=8

U₃+V₃=2

U₄+V₃=3

U₄+V₄=8

Рассчитаем величины ∆_ij=U_i+V_j-C_ijдля свободных клеток таблицы.

∆₁₂=U₁+V₂-C₁₂=0+5-7=-2

∆₁₄=U₁+V₄-C₁₄=0+8-8=0

∆₂₃=U₂+V₃-C₂₃=-1+3-4=-2

∆₂₄=U₂+V₄-C₂₄=-1+8-5=2

∆₃₁=U₃+V₁-C₃₁=-1+3-4=-2

∆₃₂=U₃+V₂-C₃₂=-1+5-7=-3

∆₃₄=U₃+V₄-C₃₄=-1+8-8=-1

∆₄₁=U₄+V₁-C₄₁=0+3-9=-6

∆₄₂=U₄+V₂-C₄₂=0+5-7=-2

Так как есть положительные значения, план является не оптимальным. Необходимо выбрать наибольшее положительное число и осуществить сдвиг по циклу.

Таблица 2.1.4 Оптимальный план решения задачи

Ai Bj	B1	B2	B3	B4
A1	3 1	7 –	3 –	8 –
A2	2 0	4 1	4 –	5 0
A3	4 –	7 –	2 1	8 –
A4	9 –	7 0	3 0	8 1

Проверим полученный план на оптимальность.

U₁+V₁=3U₁=0V₁=3

U₂+V₁=2U₂=-1V₂=5

U₂+V₂=4U₃=1V₃=1

U₂+V₄=5U4=2V₄=6

U₃+V₃=2

U₄+V₃=3

U₄+V₄=8

Рассчитаем величины ∆_ij=U_i+V_j-C_ijдля свободных клеток таблицы.

∆₁₂=U₁+V₂-C₁₂=0+5-7=-2

∆₁₃=U₁+V₃-C₁₃=0+1-3=-2

∆₁₄=U₁+V₄-C₁₄=0+6-8=-2

∆₂₃=U₂+V₃-C₂₃=-1+1-4=-4

∆₃₁=U₃+V₁-C₃₁=1+3-4=0

∆₃₂=U₃+V₂-C₃₂=1+5-7=-1

∆₃₄=U₃+V₄-C₃₄=1+6-8=-1

∆₄₁=U₄+V₁-C₄₁=2+3-9=-4

∆₄₂=U₄+V₂-C₄₂=2+5-7=0

Так как все ∆_ij <=0, то получен оптимальный план решения задачи.

Минимальные суммарные затраты при решении задачи методом потенциалов составят:

F=1*3+0*2+1*4+1*2+0*3+1*8=17

Ответ: для получения минимальных суммарных затрат необходимо назначить кандидата А₁на работу В₁, кандидата А₂на работу В₂, кандидата А₃на работу В₃, кандидата А₄на работу В₄.