определения, данные в разделе 6.5.1, мы можем записать задачу линейного программирования для сети с ограниченной пропускной способностью следующим образом.

Минимизировать 2 = ]СЛ

при ограничениях

Z хд- Z xi=fj> J*N>

Результирующий чистый поток /., протекающий через узел j, вычисляется по формуле

fj = (величина потока, выходящего из узла j) - (величина потока, входящего в узел j).

Узел у выступает в качестве источника, если /у > 0, и как сток при /у < 0.

Нижнюю границу пропускной способности ltj можно удалить из ограничений с помощью подстановки xtj = х0 + 11Г Для нового потока xv верхней границей пропускной способности будет величина ut. - В этом случае результирующий поток через узел i будет равен ft -1 , а через узел j - f + На рис. 6.38 показаны преобразования характеристик дуги после исключения ее нижней границы пропускной способности.

Рис. 6.38. Исключение нижних границ пропускных способностей

Пример 6.5.2

Запишем задачи линейного программирования для сети (см. рис. 6.37) до и после исключения нижних границ пропускных способностей.

Основные ограничения формулируемой задачи линейного программирования связаны с определением входных и выходных потоков, протекающих через каждый узел, что порождает следующую задачу ЛП.

Сделаем замечание о структуре коэффициентов, формирующих ограничения. В столбце, соответствующем переменной хц, всегда в строке / стоит +1, а в строке

j--1. Остальные коэффициенты равны нулю. Такая структура коэффициентов

типична для сетевых моделей.

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

хи = х1* + 50>

ХЫ = * + 70,

х46 = xv> + 100.

В результате получаем следующую задачу линейного программирования.

Соответствующая сеть после исключения нижних границ пропускных способностей дуг показана на рис. 6.39. Отметим, что данную сеть можно получить непосредственно из сети, представленной на рис. 6.37, с помощью преобразований, показанных на рис. 6.38, причем без необходимости записи в виде задачи линейного программирования.

[-80]

Рис. 6.39. Сеть из примера 6.5.2 после исключения нижних границ пропускных способностей

Пример 6.5.3. Распределение рабочих

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

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

Обозначим через х количество рабочих, нанятых на начало (-го месяца и освобожденных на начало у-го. Например, х12 - это количество рабочих, нанятых в январе только на один месяц.

Чтобы сформулировать задачу линейного программирования, нужно добавить еще пятый месяц (май). Тогда, например, переменная х{5 будет обозначать количество рабочих, нанятых в апреле на один месяц. Естественно, на май нет заказа на рабочих.

Ограничения строятся так, чтобы спрос на рабочих в месяц к можно было бы удовлетворить за счет всех рабочих хц, где / < к < j. Обозначив через s, (s, > 0) количество рабочих, лишних в месяце /, получим следующую задачу линейного программирования.

В данной задаче ЛП нет той специальной структуры коэффициентов ограничений, что была в модели из примера 6.5.2. Тем не менее эта задача имеет свою специфику, которая позволит преобразовать ее в сетевую модель. Выполним следующие действия.

1. Из п-го уравнения (ограничения) задачи создадим новое (п + 1)-е уравнение, умножив п-е уравнение на -1.

2. Оставляем первое уравнение без изменений.

3. Для /= 2, 3, п последовательно заменяем г-е уравнение разностью ;-го и (/- 1)-го уравнений.