Решение задач линейного программирования транспортного типа: Методические указания к выполнению индивидуальных домашних заданий, страница 10

Шаг 2. В таблице 3.2 представлен полученный план X₁, для которого вновь рассчитываются потенциалы строк U_i и потенциалы столбцов V_j, а также значения ∆_ij. 

 

                1  0  0  –

 Х₁ =     –  1  –  –     ,     S₁ = 41.

             –  –  1  0

            –  –  –  1

Таблица 3.2

bj ai	К 1	М 1	В 1	Ю 1	Ui
И    1	2 1   –	10 0	9 0      +	7	10
П    1	15	4 1	14	8	16
С    1	13	14	16       1 –	11 0      +	3
Е    1	4 +	15	13	19  1 –	-5
Vj	12	20	19	14	S1 = 41

План X₁ не оптимален, так как имеются ∆_ij > 0. Выпишем максимальное положительное значение: ∆₄₁  = 13. Свободная клетка (4, 1) отмечается «+», к ней составляется цикл, в который включены клетки (4, 1), (1, 1), (1, 3), (3, 3), (3, 4), (4, 4).

Выбирается корректирующая величина θ = min{x₁₁, x₃₃, x₄₄} = min{1, 1, 1} = 1. Освобождается занятая клетка (4, 4) с наибольшим тарифом, а свободная клетка (4, 1) становится занятой со значением, равным 1. Проводится корректировка плана по циклу: к значению в плюсовой клетке прибавляется θ, а от значения в минусовой клетке отнимается θ. Значение целевой функции уменьшается: 

S₂ = S₁ – ∆₄₁×θ = 41 – 131 = 28.

Получен новый опорный план X₂, представленный в таблице 3.3.

        

             0  0  1  –

 Х₂ =   –  1  –  –      ,     S₂ = 28.

            –  –  0  1

            1  –  –  –

Шаг 3. Проверка плана Х₂ показывает, что условия критерия оптимальности для него не выполнены. Максимальное положительное значение ∆₃₂  = 3. Проведем корректировку плана с помощью цикла, в который входят клетки (3, 2), (1, 2), (1, 3) и (3, 3). Поскольку величина θ равна нулю, значение целевой функции останется прежним, S₃ = 28.

Таблица 3.3

bj ai	К 1	М 1	В 1	Ю 1	Ui
И   1	2 0	10 – 0	9 + 1	7	10
П   1	15	4 1	14	8	16
С   1	13	14 +	16 –  0	11 1	3
Е   1	4 1	15	13	19	8
Vj	12	20	19	14	S2 = 28

Шаг 4. Получен новый опорный план X₃, представленный в таблице 3.4. Его проверка на оптимальность показывает, что для всех свободных клеток выполнено условие: ∆_ij < 0. Значит, этот план оптимален.

Таблица 3.4

bj ai	К 1	М 1	В 1	Ю 1	Ui
И   1	2 0	10 0	9 1	7	10
П   1	15	4 1	14	8	16
С   1	13	14 0	16	11 1	6
Е   1	4 1	15	13	19	8
Vj	12	20	19	17	S3 = 28

Ответ:

                                                  –  –  1  –

                             Х^* =     –  1  –  –     ,     S^* = 28.

                                         –  –   –  1

                                         1  –  –  –

Экономическая интерпретация решения задачи о назначении напарников

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

Иванов и Васин,     Петров и Мишин, 

Сидоров и Юрин,   Егоров и Костин.

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

Решение задачи о назначениях венгерским методом

Более простым способом решения задачи о назначениях является «венгерский метод». В его основе лежит следующее свойство ее решений: оптимальное решение задачи о назначениях не изменится, если из всех элементов любой строки или столбца матрицы стоимости назначений C = (c_ij) вычесть одно и то же число.

Исходная матрица стоимости назначений в нашей задаче имеет вид

С0 =	2	10	9	7
	15	4	14	8
	13	14	16	11
	4	15	13	19

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

Шаг 1. Этот шаг предназначен для получения в матрице стоимости назначений возможно большого числа нулевых элементов. Для этого в каждой строке матрицы С находят минимальный элемент (2, 4, 11, 4 соответственно), который вычитают из всех элементов данной строки. Получаем следующую матрицу.

С1 =	0	8	7	5
	11	0	10	4
	2	3	5	0
	0	11	9	15

Затем в каждом столбце полученной матрицы находят минимальный элемент (0, 0, 5, 0 соответственно), который вычитают из всех элементов этого столбца. В результате получим такую матрицу.

С2 =	0	8	2	5
	11	0	5	4
	2	3	0	0
	0	11	4	15

Шаг 2. Допустим, что в модифицированной матрице C₂ нам удалось выбрать (пометить) четыре нулевых элемента так, что каждая строка и столбец содержат ровно один помеченный нуль. Тогда план, содержащий единицы в тех же клетках, что и помеченные нули, будет допустимым решением задачи о назначениях. Причем этому плану соответствует минимальное общее количество правонарушений (общая стоимость назначений), а значит, он будет оптимальным решением.