УПРАЖНЕНИЯ 6.4.4

1. Решите задачу из упражнения 6.4.2.2 с помощью средства Поиск решения.

2. Решите задачу из упражнения 6.4.2.5 с помощью средства Поиск решения.

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

1. Каждой дуге поставлена в соответствие (неотрицательная) стоимость прохождения единицы потока по данной дуге.

2. Дуги могут иметь положительную нижнюю границу пропускной способности.

3. Любой узел сети может выступать в качестве как источника, так и стока.

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

6.5.1. Сетевая модель

Рассмотрим сеть G = (N, А) с ограниченной пропускной способностью, где N - множество узлов, А - множество дуг. Обозначим

xtj - величина потока, протекающего от узла i к узлу у,

ц,. (?,.) - верхняя (нижняя) граница пропускной способности дуги (i, j),

ctj - стоимость прохождения единицы потока по дуге (t, j),

f. - величина чистого результирующего потока, протекающего через узел i.

На рис. 6.36 показано, как на схемах сетей будем отображать определенные параметры дуг. Метка [/,] указывает положительное (отрицательное) значение предложения (спроса), соответствующего узлу i.

6.5. ЗАДАЧА НАХОЖДЕНИЯ ПОТОКА НАИМЕНЬШЕЙ СТОИМОСТИ

if -IJ-

Рис. 6.36. Обозначение параметров дуг

Пример 6.5.1

Компания GrainCo снабжает зерном из трех зернохранилищ три птицеводческие фермы. Предложение зернохранилищ составляет 100, 200 и 50 тысяч бушель зерна, а спрос ферм - 150, 80 и 120 тысяч бушель соответственно. Компания может транспортировать зерно по железной дороге, за исключением трех маршрутов, где используется автомобильный транспорт.

На рис. 6.37 показаны возможные маршруты между зернохранилищами и птицеводческими фермами. Зернохранилища представлены узлами 1, 2 и 3; их предложения указаны метками [100], [200] и [50] соответственно. Фермы обозначены узлами 4, 5 и 6 с величинами спроса [-150], [-80] и [-120]. Маршруты транспортировки зерна показаны на рис. 6.37 дугами, соединяющими узлы сети. Дуги (1, 4), (3, 4) и (4, 6) соответствуют автомобильным маршрутам. Эти маршруты имеют верхние и нижние границы пропускных способностей. Например, по маршруту (1, 4) можно провести от 50 до 80 тысяч бушелей зерна. Другие маршруты соответствуют железнодорожному транспорту, пропускная способность которого практически не ограничена. Стоимость транспортировки одного бушеля зерна показана возле каждой дуги.

[-150]

[-80]

Рис. 6.37. Схема сети для примера 6.5.1

УПРАЖНЕНИЯ 6.5.1 -

1. Компания разрабатывает 4-этапный план производства некоего продукта согласно следующим данным.

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

2. Пусть в предыдущем упражнении возможна недопоставка продукции со штрафом 1,50 долл. за единицу продукции при задержке в течение одного этапа. Сформулируйте задачу как сетевую модель.

3. Пусть в упражнении 1 производственные возможности каждого из четырех этапов составляют соответственно 110, 95, 125 и 100 единиц продукции, что не позволяет выполнить все заказы (без недопоставок продукции) в срок. Штраф за недопоставку единицы продукции равен 1,50 долл. при задержке в течение одного этапа. Сформулируйте задачу как сетевую модель.

4. Химическая компания владеет двумя заводами, которые производят определенные химические компоненты для двух клиентов; потребности этих клиентов составляют 660 и 800 тонн продукции ежемесячно. Первый завод может производить от 400 до 800 тонн, а второй - от 450 до 900 тонн продукции ежемесячно. На первом заводе расходы на производство одной тонны продукции составляют 25, на втором - 28 долл. Сырье для заводов поставляют два поставщика, которые могут поставить не менее 500 тонн сырья по цене 200 долл. за тонну первому заводу и не менее 750 тонн по цене 210 долл. второму заводу. Химическая компания предполагает самостоятельно транспортировать и сырье, и готовую продукцию. Стоимость транспортировки одной тонны сырья от первого поставщика к заводам составляет 10 долл. для первого завода и 12 долл. - для второго. Аналогичные стоимости перевозок от второго поставщика равны 9 и 13 долл., соответственно для первого и второго заводов. Стоимость перевозки одной тонны продукции от первого завода к клиентам 1 и 2 составляет 3 и 4, от второго завода - 5 и 2 долл. соответственно. Допустим, из одной тонны сырья можно получить одну тонну готовой продукции. Сформулируйте задачу в виде сетевой модели.

5. В двух открытых школах необходимо изменить расовый баланс среди учащихся путем дополнительного их набора из национальных меньшинств. Учащиеся из национальных меньшинств должны составлять от 30 до 40% от общего количества. Учащиеся из национальных меньшинств живут в трех общинах, а обычные - в двух. В следующей таблице приведены расстояния от общин до школ (в милях).

Расстояние от школы до

Школа Количество учащихся общины национальных меньшинств обычной общины

учащихся в каждой школе.

6.5.2. Сетевая модель как задача линейного программирования

Определение модели сети с ограниченной пропускной способностью как задачи линейного программирования необходимо для разработки симплексного алгоритма решения задач данного типа (алгоритм описан в следующем разделе). Используя