![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод вариаций и его применение к задаче минимизации штрафов при обслуживании заявок.
Дискретным программированием называют раздел математического программирования, в котором исследуются и решаются экстремальные задачи на конечных множествах. Для иллюстрации метода вариаций рассмотрим задачу минимизации штрафов при обслуживании заявок. Имеется n заявок с номерами 1, 2,..., n, которые нужно обслужить. Две и более заявок одновременно обслуживаться не могут. Пусть Ti - время обслуживания, а ci - величина штрафа за единицу времени ожидания i -й заявки, i = l, …, n. Требуется найти очередность обслуживания заявок с минимальным общим штрафом. Планами этой задачи дискретного программирования являются перестановки X = (i1, …, in) элементов множества I = {1, 2, …, n). Их число равно n!. В перестановке X в период обслуживания заявки i1, остальные заявки простаивают
Простейшей вариацией плана х назовем транспозицию двух элементов ik и ik+l, k = l, …, n-l (перестановочный прием). Пусть
Алгоритм: 1. Находим для каждой заявки величину 2. Переставляем наши заявки в процессе убывания
|