1rjpjpsumwjcjиsumtj
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Задача: |
Дано | работ и станок. Для каждой работы известны время появления , вес и дедлайн . Время выполнения всех работ равно . Требуется выполнить все работы так, чтобы значение , где — время окончания работы, было минимальным.
Задача: |
Дано | работ и станок. Для каждой работы известны время появления , вес и дедлайн . Время выполнения всех работ равно . Требуется выполнить все работы так, чтобы значение — суммарной медлительности работы ( ) — было минимальным.
Предисловие
Аналогично задаче , данные задачи решаются при помощи динамического программирования.
Вместо критериев оптимизации
и возьмём более общую для них функцию вида , где функции обладают следующими свойствами:- не убывает для всех ;
- не убывает для всех при .
Получим обобщенную задачу лемме существует оптимальное расписание, в котором каждая работа начинается в момент времени из множества .
, для которой согласноФункции
и удовлетворяют данным условиям, если отсортировать работы так, что и .Алгоритм
Отсортировать работы так, чтобыудовлетворяла условиям неубывания; for s, e T : s e (s, e) = 0; for k = 1..n for s, e T : s e if else , где return
Время работы
Корректность алгоритма
Ниже приведена теорема, показывающая, что возвращаемое алгоритмом значение
равно .Теорема: |
Для любого и для любого , выполняется равенство:
. |
Доказательство: |
Будем полагать, что равенство верно для (очевидно, равенство выполнится при ).Если , тогда что подразумевается в равенстве.Теперь нужно показать, что а) ;б) при .а) Полагаем, что ограничена. Тогда существует такая, что, при которой
б) Полагаем, что ограничена. Среди всех оптимальных расписаний, возвращающих выберем оптимальное расписание , соответствующий вектор времён окончания работ которого минимален при условии, что в лексикографическом порядке.Пусть — время начала работы в расписании . Тогда
Чтобы проверить первое неравенство, нужно показать, что все работы записаны в в пределах интервала , а все работы — в пределах . Докажем первое утверждение (второе доказывается аналогично).Полагаем, что существует работа такая, что , начинающаяся в расписании позже, чем работа . Поменяв местами и , получим оптимальное расписание такое, что, где — объективное значение расписания подразумевает , так как не убывает по условию. Таким образом, также является оптимальным, несмотря на то, что это противоречит лексикографической минимальности расписания . |
Другие задачи
См. также
Источники информации
P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 98 - 104