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

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

Имеется n заявок с номерами 1, 2,..., n, которые нужно обслужить. Две и более заявок одновременно обслуживаться не могут. Пусть T_i - время обслуживания, а c_i - величина штрафа за единицу времени ожидания i -й заявки, i = l, …, n. Требуется найти очередность обслуживания заявок с минимальным общим штрафом.

Планами этой задачи дискретного программирования являются перестановки X = (i₁, …, i_n) элементов множества I = {1, 2, …, n). Их число равно n!. В перестановке X в период обслуживания заявки i₁, остальные заявки простаивают единиц времени, и, следовательно, штраф за ожидание в этот период составит . Рассматривая далее периоды обслуживания заявок i₁,..., i_n, получаем, что общий штраф для перестановки х равен:

, где - время ожидания заявки.

Простейшей вариацией плана х назовем транспозицию двух элементов i_k и i_k+l, k = l, …, n-l (перестановочный прием). Пусть - номера заявок. Пусть имеются: i_k и i_k+1 заявки, а также и – время обслуживания. Если мы поменяем местами заявки, то получим: – величина разности штрафа. Преобразуем это выражение: .

– необходимое и достаточное условия.

- важность, успешность.

Алгоритм:

1. Находим для каждой заявки величину .

2. Переставляем наши заявки в процессе убывания .