Пример 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% от общего количества. Учащиеся из национальных меньшинств живут в трех общинах, а "обычные" - в двух. В следующей таблице приведены расстояния от общин до школ (в милях).
Расстояние от школы до
Школа Количество учащихся общины национальных меньшинств "обычной" общины
(не более) | | | | | |
1 1500 | | | | | |
2 2000 | | | | | |
Количество учащихся | | | | 1000 | 1000 |
Сформулируйте задачу как | сетевую | модель | и определите расовый | состав |
учащихся в каждой школе.
6.5.2. Сетевая модель как задача линейного программирования
Определение модели сети с ограниченной пропускной способностью как задачи линейного программирования необходимо для разработки симплексного алгоритма решения задач данного типа (алгоритм описан в следующем разделе). Используя
определения, данные в разделе 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 | | | | | | | | | | = 100 |
Узел 2 | | | | | | | | | | = 200 |
Узел 3 | | | | | | | | | | = 50 |
Узел 4 | | | | | | | | | | = -150 |
Узел 5 | | | | | | | | | | = -80 |
Узел 6 | | | | | | | | | | = -120 |
Нижние границы | | | | | | | | | | |
Верхние границы | | | | | | | | | | |