З. Подготовка и расчет контрольного примера.

3.1.Исходные данные и постановка задачи.

Пусть имеется 4-е устройства для монтажа 4-х объектов (n=4); известна матрица затрат С_ij времени монтажа каждым устройством каждого объекта

( i,j=1,2,3,4)

3 7 5 8

2 4 4 5

C_ij = 4 7 2 8

9 7 3 8

Требуется распределить устройства (А_i) так чтобы суммарное время монтажа всех объектов (В_j) было минимальным.

3.2.Математическая модель и критерий оптимизации представляются в виде (2.2) и (2.3)

X ₁₁+X₁₂+X₁₃+X₁₄=1

X₂₁+X₂₂+X₂₃+X₂₄=1

X₃₁+X₃₂+X_ЗЗ+X₃₄=1

X₄₁+X₄₂+X₄₃+X₄₄=1

3.3. Построение исходной таблицы и расчет.

Исходную таблицу строят согласно пунктам 2.3.

По данным таблицы 3.1 согласно п.п. 2.3.1. алгоритма рассчитывают численные данные и строят таблицу 3.2.

Таблица 3.1

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

Таблица 3.2

Ai	B1	B2	B3	B4	Ai
A1	0	4	2	5	1
A2	0	2	2	3	1
A3	2	5	0	6	1
A4	6	4	0	5	1
Bj	1	1	1	1
Dj	0	2	0	3

Продолжая п.п.2.3.1. алгоритма расчетные данные заносят в таблицу 3.3.

Таблица 3.3

Ai	B1	B2	B3	B4	Ai
A1	-0-*	-2-	-2-	-2-	1
A2	-0-	-0-*	-2-	-0-	1
A3*	2	3	0*	3	1
A4*	6	2	0	2	1
Bj	1	1	1	1

Переходят к п.п. 2.3.2. алгоритма. В результате число нулей помеченных точками не равно числу п , т.е. решение не является оптимальным. Продолжают расчет по этапу п.п. 2.3.3. (в таблице 3.3.):

• отмечают точкой (по п.п.а ) ) все строки в которых не имеется ни одного отмеченного точкой нуля – строка 4

• отмечают точкой (по п.п.б ) ) все столбцы, содержащие перечеркнутый нуль , хотя бы в одной из отмеченных точкой строк – столбец 3;

• отмечают точкой все строки, содержащие отмеченные точкой нули, хотя бы в одном из отмеченных точкой столбцов – строка 3;

• действия по б) и в) повторять не надо, так как отмечать точками больше нечего;

• зачеркивают непомеченные строки – 1-ую и 2-ую строки и помеченные столбцы – 3-ий столбец (все нули перечеркиваются хотя бы один раз).

Из тех клеток, где не проходят линии перечеркивания, определяют наименьшее число – это число 2. Вычитают его из каждого числа не вычеркнутых столбцов и прибавляют к каждому числу вычеркнутых строк. Результаты сводят в таблицу 3.4 и переходят к п.п. 2.3.2. алгоритма.

Таблица 3.4.

Ai	B1	B2	B3	B4	Ai
A1	0*	2	4	2	1
A2	0	0*	4	0	1
A3*	0	1	0*	1	1
A4*	4	0	1	0*	1
Bj	1	1	1	1

После выполнения п.п. 2.3.2 количество нулей помеченных точкой равно n=4, следовательно решение в таблице 3.4 является оптимальным.

В результате оптимальное распределение исполнителей по видам работ будет:

А₁  В₁; А_З  В_З;

А₂  В₂; А₄  В₄;

Значение целевой функции (2.3) равно:

Z_min=С₁₁*X₁₁+С₂₂*X₂₂+С_ЗЗ*X_ЗЗ+С₄₄*X₄₄=3*1+4*1+2*1+8*1=17ед.