ПОЗНАВАТЕЛЬНОЕ

Сила воли ведет к действию, а позитивные действия формируют позитивное отношение

Как определить диапазон голоса - ваш вокал

Игровые автоматы с быстрым выводом

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

Целительная привычка

Как самому избавиться от обидчивости

Противоречивые взгляды на качества, присущие мужчинам

Тренинг уверенности в себе

Вкуснейший "Салат из свеклы с чесноком"

Натюрморт и его изобразительные возможности

Применение, как принимать мумие? Мумие для волос, лица, при переломах, при кровотечении и т.д.

Как научиться брать на себя ответственность

Зачем нужны границы в отношениях с детьми?

Световозвращающие элементы на детской одежде

Как победить свой возраст? Восемь уникальных способов, которые помогут достичь долголетия

Как слышать голос Бога

Классификация ожирения по ИМТ (ВОЗ)

Глава 3. Завет мужчины с женщиной

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Постановка задачи и алгоритмы решения.

Задача референта (или директора).

На собеседование в фирму явились n претендентов на 1 место. Референт путем предварительного опроса претендентов экспертно установил значения времени, которые необходимы каждому претенденту для индивидуального собеседования с директором. Необходимо определить такую последовательность приглашения на собеседование, при которой суммарное время ожидания всеми претендентами было бы минимальным (что в духе времени, но не традиций).
Данные задачи: список из n фамилий и время на собеседование: T₁, T₂, …, T_n. Решения задачи, очевидно, определяются по всем возможным перестановкам из n первых натуральных чисел, дающим все варианты очередности собеседования.

Пример 1. Референт директора (он не учился в ПетрГУ) составил список в алфавитном порядке, указав для каждого ориентировочную продолжительность собеседования. На весь прием референт, как видно из таблицы, отвёл 1,5 часа.

Таблица 1.

Суммарное время собеседования не изменится при любой последовательности приёма. Можно ли минимизировать суммарное время ожидания в очереди (пока это время составляет 175 мин.) при прежнем суммарном времени приема?

Задание 1: Составить оптимальное расписание для этого примера.

Сформулируем «решающее правило»: для минимизации суммарного времени ожидания значения T₁, T₂, …, T_n необходимо упорядочить по возрастанию. Тогда оптимальное расписание это последовательность индексов < j₁ , j₂ , ... , j_n > - номеров исходного списка после его упорядочения. Этому порядку номеров (расписанию) соответствует минимальное суммарное время ожидания.

Алгоритм, позволяющий найти решение комбинаторной задачи без какого-либо перебора вариантов, называют решающим правилом. Подобные этому «правила» привлекают относительной простотой и наглядностью шагов (процедур), ведущих к решению задачи.

Задача одного станка.

Имеется n деталей и один станок. Для каждой детали заданы: время обработки на станке T_j и величина штрафа (или затрат на хранение) α_j за единицу времени (например, час) пребывания j-й детали (j=1,n) в очереди на обработку. Необходимо определить такую последовательность обработки деталей, для которой суммарный штраф за время нахождения деталей в очереди будет минимальным. Как и в предыдущей задаче, выбор производится по всем перестановкам.

Пример 2. Решить задачу одного станка дляn = 5. Время обработки каждой детали и штрафы за хранение этих деталей заданы в таблице 2.:

Таблица 2.

Решение. Если решать эту задачу по схеме решения 1-й задачи, то получим: t₁=0, t₂=3, t₃=3+5=8, t₄=8+6=14, t₅=14+7=21 (мин). В сумме имеем 46 (мин).

Затраты на хранение: α₁t₁=0, α₂t₂=1·3=3, α₃t₃=2·8=16, α₄t₄=3·14=42,. a₅t₅=4·21=84. Суммарные затраты на хранение равны: 3+16+42+84=145 (руб.).

Но это решение не является оптимальным.

Сформулируем «решающее правило»: для определения оптимальной последовательности обработки деталей необходимо вычислить коэффициенты, равные отношению величин штрафа к времени обработки (α_j / T_j,) , и упорядочить эти значения в порядке их убывания. Тогда оптимальное расписание это последовательность индексов < j₁ , j₂ , ... , j_n > - номеров деталей после её упорядочения. Этому порядку номеров соответствует минимальный суммарный штраф.

Задание 2: В среде Excel определите оптимальную очередность обработки деталей, затраты на хранение каждой из деталей и суммарные затраты на хранение.

Задача двух станков (Джонсона, упорядочения и т.п.).

Постановка задачи и алгоритмы решения.

Имеется n деталей, каждая из которых сначала должна быть обработана на станке А, а затем на станке B. Время обработки каждой детали на обоих станках задано. Время переноса деталей с первого станка на второй не учитывается.

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

3.1. Рассмотрим «решающее правило» получения оптимального расписания:

1. Фиксируем множество номеров всех деталей: I = { 1, 2,…, n }.

1. Определяем множество номеров деталей J, для которых время обработки на первом станке не превышает время обработки на втором станке.
2. Определяем множество номеров оставшихся деталей Q=I \ J.
3. Формируем список J* = < j₁^*, j₂^*, ... ,j_k^* > номеров деталей из элементов множества J , упорядоченных в порядке возрастания времени T_1i (1-й станок).
4. Формируем список Q* = < q₁^*, q₂^*, ... ,q_s^* > номеров деталей из элементов множества Q , упорядоченных в порядке убывания времени T_2i (2-й станок).
5. Тогда Х* =< j₁^*, j₂^*, ... ,j_k^*, q₁^*, q₂^*, ... ,q_s^* > оптимальный порядок следования номеров деталей (k+s=n).

Пример 3. Решить задачу двух станков дляn = 5. Время обработки каждой детали на каждом из станков задано в таблице 3.: Таблица 3.

Применим «решающее правило» к нашему примеру:

1. I= {1, 2, 3, 4, 5}.

2. J = {3, 4}.

3. Q = I \ J = {1, 2, 5}.

4. J* = <3, 4>.

5. Q* = <5, 1, 2>.

6. Х* = <3, 4, 5, 1, 2>

3.2.Рассмотрим теперь итерационный алгоритм метода Джонсона (в краткой форме):

1. Определяем место (номер столбца) минимального элемента таблицы.
2. Выполняем перестановку столбцов таблицы согласно следующим правилам:

a. - Если минимальный элемент в первой строке, то меняем столбец с этим номером с первым столбцом; если во второй, как в нашем примере, то с последним.

b. - При наличии одинаковых элементов в обеих строках, но в разных столбцах, делаем такую перестановку одновременно.

c. - Если одинаковые минимальные элементы в одной строке, то (согласно п.п. a. и b.) учитываем соответствующие им значения элементов другой строки.

1. «Зачёркиваем» зафиксированный столбец (столбцы), и переходим на шаг 1.

В соответствии с алгоритмом на 4-й итерации получена оптимальная последовательность обработки: <3, 4, 5, 1, 2>. Здесь пора отметить, что, как и в предыдущих задачах, единственность решения вовсе не гарантируется.

Осталось найти суммарное время обработки деталей, соответствующее этому порядку обработки. Это время полезно сравнить, например, со временем для исходной последовательности, может быть, всё уже было «оптимизировано» до нас. Очевидно, что T* >= max(S T_1J ;S T_2J) = max(31;28) = 31.

Существуют несколько способов расчета суммарного времени. Рассмотрим (без формул) один из них:

1. Первый станок работает без перерывов (без простоев), следовательно, достаточно сложить время работы 2-го станка и время его простоев.
2. Как рассчитать суммарные простои 2-го станка?:
   - время обработки 1-й детали 1-м станком становится исходным значением суммы времени простоев 2-го станка (см. таблицу 4).
   Далее шаг за шагом (j=1, n-1) сравниваем значения времени обработки деталей:
   - если 2-й станок обрабатывает j–ю деталь за большее время, чем 1-й обрабатывает следующую (j+1) деталь, то разность значений времени (отрицательная) запоминается «в строке простоев» как «резерв времени» второго станка, и обязательно учитывается на следующем шаге;
   - если 2-й станок обрабатывает j–ю деталь за меньшее время, чем 1-й обрабатывает следующую (j+1) деталь, то разность (положительная) суммируется с возможно имеющимся «резервом времени», полученным на предыдущем шаге, и эта сумма также запоминается;
3. Непосредственно суммируем положительные значения простоев 2-го станка.

Таблица 4.

3.3. В завершении рассмотрим алгоритм приоритетов- эффективный и удобный для реализации в Excel метод решения задачи 2-х станков.

Алгоритм состоит из 2 шагов: на первом шаге определяются приоритеты всех изделий – числа P_j (j=1,n), по формуле:

P_j=sign(t_1j-t_2j)·(M-min(t_1j;t_2j))

Где M– некоторое «большое число» (например, значение 100 в таблице 5), а sign(х)– математическая функция «знак числа х» (функция ЗНАК() в Excel )

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

Таблица 5

Задание 3: В среде Excel (с использованием необходимых формул) определите суммарное время обработки для исходной последовательности деталей (пример 3) и сравните его с минимальным временем (33 мин.).

Задание 4: (индивидуальное!) В среде Excel решить задачу двух станков при n = 8. Время обработки деталей (16 значений) самостоятельно получить с помощью датчика случайных чисел (значения равномерно распределённой на [10;30] целочисленной СВ ). Получить (и использовать) необходимые формулы для расчёта суммарного времени обработки деталейдля исходной и для оптимальной последовательности.

Вопросы к работе:

1. Дайте понятие решающего правила.

2. Что такое перестановки? Как определить число перестановок из n элементов?

3. Какие решения называют оптимальными?

4. Сколько оптимальных решений имеет первая задача (по примеру 1)

5. Как в первой задаче получить максимум суммарного времени?

6. Сформулируйте задачу одного станка.

7. Какой смысл имеют коэффициенты α_j / T_j, в задаче одного станка?

8. Сформулируйте задачу двух станков.

9. Сформулируйте решающее правило получения оптимального расписания в задаче двух станков.

10. Поясните понятие «резерв времени» в задаче двух станков.

11. Как Вы рассчитали простои 2-го станка в задаче двух станков в Excel.

12. Найдите другое оптимальное расписание в задаче примера 3.

13. Как изменится оптимальное решение задачи двух станков, если станки А и B поменять местами?

14. ………………………………..