П.2.5. Решение задачи о назначениях

Порядок решения задачи о назначениях с помощью QSB рассмотрим на примере. Подготовьте исходные данные задачи для решения на ЭВМ:

Кандидаты	Затраты времени по работам

Итак, в нашей задаче: ЦФ на минимум, 4 кандидата и 4 работы.

Выберите опцию 4 – Задача о назначениях в главном меню системы. На экране появится функциональное меню, идентичное рассмотренному ранее.

В функциональном меню выберите опцию 2 – Ввод новой задачи, введите название задачи (например, prim4), ответьте на вопросы о задаче. Варианты ответов: ЦФ на минимум, 4 кандидата, 4 работы, будем использовать заданные обозначения кандидатов (О₁, О₂,...,О_п – от objects) и работ (Т₁, Т₂,...,Т_п – от tasks). По окончании нажмите клавишу Spacebar .На экране появится шаблон для ввода затрат времени на монтажные работы.

Заполните шаблон следующим образом:

Ввод коэффициентов затрат/прибыли Стр.1 Кандид. Раб. О1: Т1: 3____ Т2: 7____ Т3: 5_____ Т4: 8____ О2 Т1: 2____ Т2: 4___ Т3: 4_____ Т4: 5____ О3 Т1: 4____ Т2: 7____ Т3: 2_____ Т4: 8____ О4 Т1: 9____ Т2: 7____ Т3: 3_____ Т4: 8____

После нажатия Spacebar на экране появится функциональное меню.

В функциональном меню выберите опцию 5 – Решение задачи. На экране появится меню опции <Решение>:

Меню опции <Решение>

пункт 1---- Решение и просмотр начальной таблицы 2---- Решение и просмотр всех таблиц 3---- Решение и просмотр итоговой таблиц 4---- Решение без просмотра таблиц 5---- Возврат в функциональное меню

Выбор опции 5 обеспечивает возврат в функциональное меню без решения задачи. При выборе остальных опций задача будет решена. При этом для задач небольшой размерности доступны все режимы, а для больших задач – только опции 4-5.

Выберите опцию 2 – Решение и просмотр всех таблиц. Результаты решения на каждой итерации представленными одинаковыми по форме таблицами:

итерация 1
К/Р	Т1	Т2	Т3	Т4	линия
О1		2.000	2.000	2.000	<--
О2			2.000		<--
О3	2.000	3.000		3.000
О4	6.000	2.000		2.000
линия			^

Итерация 1 представляет собой первый шаг алгоритма венгерского метода. В строке «линия» вычеркнутые столбцы помечены символом (^). В столбце «линия» вычеркнутые строки помечены символом (<--). Переход к следующей итерации осуществляется нажатием любой клавиши, кроме G , ри нажатии которой вычислительный процесс пойдёт без остановки до конца.

Процесс поиска оптимального решения заканчивается на второй итерации. После нажатия любой клавиши на экране появляется меню способов представления полученного решения задачи.

Выберите опцию 1 – просмотр итогового решения. На экране появится таблица с результатами решения задачи:

Сводка назначений для prim4 Стр.: 1
Канд.	Раб.	затр/приб.	Канд.	Раб.	затр/приб.
О1	Т1	3.000	О3	Т3	2.000
О2	Т2	4.000	О4	Т4	8.000
Мин. значение цф = 17 число итераций = 2

Первый кран закрепляется за первой работой, второй – за второй, третий – за третьей, четвёртый – за четвёртой. При этом минимальное время на монтаж всех объектов равно 17.

 

П.2.6. Решение сетевых задач (NET)

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

Пусть имеются пять пунктов, соединённых между собой дорогами так, что из любого пункта можно проехать в любой другой пункт. Известно расстояние от пункта i до пункта j.

Требуется найти кратчайший маршрут от пункта 1 до любого другого пункта.

Подготовьте исходные данные задачи для решения на ЭВМ: определите число ветвей и узлов в задаче (20 ветвей и 5 узлов).

Из пункта i	Расстояние до пункта j

Выберите опцию 5 – Сетевое моделирование (NET) в главном меню системы. На экране появится функциональное меню, идентичное рассмотренному ранее.

В функциональном меню выберите опцию 2 – Ввод новой задачи, введите название задачи (например, prim5 ), ответьте на вопросы о задаче. Варианты ответов: 20 ветвей, 5 узлов будем использовать алгоритм кратчайшего пути. По окончании нажмите клавишу Spacebar . На экране появится шаблон для ввода расстояния между пунктами.

Заполните шаблон следующим образом:

Ветвь Номер	Ветвь Код	Нач. узел	Кон. узел	Расстоян.	Ветвь Номер	Ветвь Код	Нач. узел	Кон. узел	Расстоян.
	<B1 > <B2 > <B3 > <B4 > <B5 > <B6 > <B7 > <B8 > <B9 > <B10 >	<1> <1> <1> <1> <2> <2> <2> <2> <3> <3>	<2> <3> <4> <5> <1> <3> <4> <5> <1> <2>	<10 > <25 > <25 > <10 > <1 > <10 > <15 > <2 > <8 > <9 >		<B11 > <B12 > <B13 > <B14 > <B15 > <B16 > <B17 > <B18 > <B19 > <B20 >	<3> <3> <4> <4> <4> <4> <5> <5> <5> <5>	<4> <5> <1> <2> <3> <5> <1> <2> <3> <4>	<20 > <10 > <14 > <10 > <24 > <15 > <10 > <8 > <25 > <27 >

Можно дать произвольные названия ветвям длиной до 6 символов (заданные по умолчанию – В₁,...,В_п). Узлы нумеруются последовательно, начиная с 1 до 5. Ветви вводятся в произвольной последовательности. После нажатия Spacebar на экране появится функциональное меню.

В функциональном меню выберите опцию 5 – Решение задачи. На экране появится меню опции <Решение>:

Меню опции <Решение> prim 5

пункт 1---- Решение и просмотр по шагам 2---- Решение без просмотра по шагам 3---- Возврат в функциональное меню

Выбор опции 3 обеспечивает возврат в функциональное меню без решения задачи. Опция 1 обеспечивает просмотр процесса решения задачи с помощью заданного вами алгоритма (алгоритма кратчайшего пути). Опция 2 даёт решение без просмотра процесса по шагам.

Выберите опцию 2 – Решение без просмотра по шагам. Результат решения задачи:

итоговый кратчайший путь для prim5 Стр.: 1
узел	Расстояние	Кратчайший руть из узла 1
		1-2(В1)
		1-3(В2)
		1-2-4(В1-В7)
		1-2-5(В1-В8)

В графе «Расстоян» показана длина кратчайшего пути от 1 пункта до указанного пункта в графе «узел»; в последней графе – названия пунктов, через которые проходит кратчайший путь, а в скобках – названия ветвей. После нажатия любой клавиши на экране появится меню <Решение>.

Выйдите в функциональное меню и выберите 7 – Измерение задачи.

На экране появится меню опции <Изменение>, в котором выберите опцию 5 – Выбор алгоритма. На экране появится меню выбора алгоритма модели, где показан текущий алгоритм и предложено 3 варианта выбора: алгоритм кратчайшего пути (1), алгоритм максимального потока (2) и алгоритм минимального размаха дерева (3).

итоговый поток для prim5 Стр.:1
Ветвь	поток
1-2(В1) 1-3(В2) 1-4(В3) 1-5(В4) 2-3(В6) 2-4(В7) 2-5(В8) 3-4(В11) 3-5(В12) 4-5(В16)
Макс. итоговый поток = 0

 

Введите цифру 2 и нажмите Enter . Ранее введённые данные о расстоянии между пунктами теперь интерпретируются как величина потока (объём грузоперевозок) между этими пунктами. Найдём максимальную величину потока от начального узла до конечного, т.е. максимальный суммарный объём грузоперевозок. Для этого вернитесь в функциональное меню и решите задачу.

Поскольку сеть замкнута в нашей задаче, то максимальный поток получился равным нулю.

П.2.7. Решение сетевых задач (СРМ)

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

Рассчитать параметры сети и оптимизировать сетевой график, если известны время выполнения (продолжительность) и стоимость работ в нормальных и экстремальных условиях.

Подготовьте исходные данные задачи для решения на ЭВМ: определите число работ в задаче (12 работ).

Выберите опцию 6 – Сетевое моделирование (СРМ) в главном меню системы.

В функциональном меню выберите опцию 2 – Ввод новой задачи, введите название задачи (например, prim6 ), ответьте на вопросы о задаче (12 работ). По окончании нажмите клавишу Spacebar . На экране появится шаблон для ввода продолжительности и стоимости работ в нормальных и критических условиях. Если критические характеристики не известны, то оставляются пропуски. Продолжительность и стоимость работ задаются длиной не более 6 цифр, включая запятую.

 

Код работы	Время	Стоимость
норм.	крит	норм.	крит.
1-2 1-3 1-4 2-3 2-6 3-5 4-5 4-7 5-6 5-7 6-8 7-8

Заполните шаблон следующим образом:

Номер	Назв.	Нач. узел	Кон. узел	Норм. продолж.	Крит. продолж.	Норм. стоим.	Крит. стоим.
	<1-2 > <1-3 > <1-4 > <2-3 > <2-6 > <3-5 > <4-5 > <4-7 > <5-6 > <5-7 > <6-8 > <7-8 >	<1> <1> <1> <2> <2> <3> <4> <4> <5> <5> <6> <7>	<2> <3> <4> <3> <6> <5> <5> <7> <6> <7> <8> <8>	<5 > <4 > <8 > <3 > <7 > <3 > <5 > <4 > <9 > <11 > <8 > <10 >	<3 > <4 > <7 > <2 > <5 > <3 > <5 > <3 > <6 > <7 > <6 > <9 >	<2000 > <3000 > <4000 > <1200 > <2000 > <8000 > <3000 > <3000 > <700 > <1500 > <600 > <1000 >	<2500 > <3000 > <5000 > <1500 > <3000 > <8000 > <3000 > <3700 > <1600 > <2000 > <1500 > <1050 >

Можно дать произвольные названия работам длиной до 6 символов. Работы вводятся в произвольной последовательности. После нажатия Spacebar на экране появится функциональное меню.

В функциональном меню выберите опцию 5 – Решение задачи. На экране появится меню опции <Решение>:

 

Меню опции <Решение> prim 6

Опции 1---- Решение с показом результатов 2---- Решение без показа результатов 3---- печать итогового решения 4---- критический анализ 5---- Возврат в функциональное меню

Выбор опции 5обеспечивает возврат в функциональное меню без решения задачи. Опция 1 обеспечивает просмотр процесса решения задачи по шагам. Опция 2 даёт решение без показа результатов. Опция 3 позволяет напечатать итоговые результаты. Опция 4 необходима для проведения критического анализа.

Выберите опцию 2 - Решение с показом результатов и нажмите Enter .

В первой графе таблицы дан порядковый номер работы, во второй – код работы, в третьей и четвёртой – раннее и позднее время начала работы, в пятой и шестой – раннее и позднее время окончания работы, в седьмой – резерв времени по работам. Критические работы в последней графе помечены надписью «крит». В последней строке показано суммарное время выполнения работ (34) и суммарная стоимость (30000).

СРМ анализ для prim6 Стр.: 1
№ работы	назв.	раннее начало	позднее начало	раннее оконч.	позднее оконч.	Резерв
	1-2 1-3 1-4 2-3 2-6 3-5 4-5 4-7 5-6 5-7 6-8 7-8	5.0000 5.0000 8.0000 8.0000 8.0000 13.000 13.000 22.000 24.000	2.0000 6.0000 7.0000 19.000 10.000 8.0000 20.000 17.000 13.000 26.000 24.000	5.0000 4.0000 8.0000 8.0000 12.000 11.000 13.000 12.000 22.000 24.000 30.000 34.000	7.0000 10.000 8.0000 10.000 26.000 13.000 13.000 24.000 26.000 24.000 34.000 34.000	2.0000 6.0000 крит. 2.0000 14.000 2.0000 крит. 12.000 4.0000 крит. 4.0000 крит.
сум. время = 34 сум. стоим. = 30000

После нажатия любой клавиши на экране появится графическое изображение найденного решения:

Критические пути prim6 сум. время = 34 сум. стоим. = 30000 кп#1:

После нажатия любой клавиши осуществляется возврат в меню <Решение>. Выберите опцию 4 – критический анализ.

При выполнении критического анализа исходные данные будут уничтожены.

Эвристический метод оптимизирует сеть по критерию «время-стоимость». Результаты критического анализа показываются по шагам. Перед выполнением каждого шага выдаётся запрос: «Сократить время, увеличив стоимость (Y/N)?». Каждый раз отвечайте Y , пока не появится сообщение: «Анализ выполнен».

По шагам выводится информация о том, какая критическая работа сокращается, каково при этом увеличение её стоимости, суммарное время выполнения и суммарная стоимость работ:

 

Сокращается: Крит. работа: I продолжит-ть 7 увеличение ст-сти: 300 Критические пути prim6 сум. время = 28 сум. стоим. = 32150 кп#1:

В результате проведения критического анализа суммарное время выполнения работ уменьшилось с 34 до 28 единиц, а стоимость увеличилась с 30000 до 32150 д.е.

Программа Сетевое моделирование (PERT) предусмотрена для расчёта параметров сети, когда продолжительности работ оцениваются пессимистически, наиболее вероятно и оптимистически. Процесс взаимодействия пользователя с этой программой аналогичен рассмотренному выше.