7. Лекция: Прикладные задачи дискретного программирования

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

Задачи планирования перевозок

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

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

Рассмотрим распределительную задачу. Эта математическая модель широко освещалась в литературе под самыми различными названиями (обобщенная транспортная задача, задача о взвешенном распределении, -задача, задача о расстановке флота и др.). Опишем ее в следующей интерпретации.

Обобщенная транспортная задача, задача о взвешенном распределении, -задача, задача о расстановке флота и др.

Пусть имеется транспортных линий (скажем, пассажирских); по -й линии нужно выполнить рейсов . В наличии имеются транспортные единицы m типов. Резервы полезного времени транспортной единицы типа составляют . На выполнение транспортной единицей типа рейса требуется время , а затраты на рейс составляют . Требуется указать наиболее экономную расстановку транспортных единиц по линиям.

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

(7.1)

при условиях

(7.2)

- целые, ,

(7.3)

(7.4)

Здесь условия (7.3.) выражают ограничения по фондам времени каждой транспортной единицы, а условия (7.4.) говорят о том, что все рейсы должны быть выполнены.

К совершенно аналогичной модели приводит близкая к описанной задача о выборе средства доставки груза.

Задача о выборе средства доставки груза.

Пусть через обозначены грузообразующие пункты с объемами груза в них . Имеется средств доставки груза (видов транспорта); грузоподъемность - го средства доставки составляет , а наличный его парк равен . Грузы подлежат доставке в один центральный пункт (склад); затраты при осуществлении одной единицей средства доставки рейса от пункта до склада равны . Требуется составить наиболее экономный план доставки.

Через обозначим количество средств доставки типа , отправляющееся из пункта . Тогда задача сведется к минимизации целевой функции вида (7.1.) при условиях (7.2.) и

(7.5)

(7.6)

Распределительная задача имеет весьма разнообразные приложения. Большое число практических ее интерпретаций можно найти в монографии Д.Б. Юдина и Е.Г. Гольштейна (Юдин Д.Б., Гольштейн Е.Г., Задачи и методы линейного программирования . Изд. 2-е переработанное и дополненное, М., "Советское радио", 1964.)

Задача распределения производственной программы.

Пусть требуется распределить изготовление деталей между станками. Индексом будем обозначать детали, индексом — станки с резервами рабочего времени . Пусть плановое задание по деталям задается числами , штучные нормы времени по обработке -м станком -й детали равны , а себестоимость при этом составляет . Требуется составить план распределения работ по станкам, обеспечивающий выполнение задания, не выводящий за пределы резервов времени по каждому станку и минимизирующий суммарную себестоимость.

Обозначим через количество деталей типа , которое следует обработать на станке . Тогда описанная задача распределения программы сведется к модели (7.1.)-(7.4.). Заметим, что во многих интерпретациях распределительной задачи требование целочисленности на переменные может и не накладываться.

Распределительная задача с фиксированными доплатами.

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

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

(7.7)

где

(7.8)

Ограничения по фонду времени каждой транспортной единицы будут теперь иметь вид

(7.9)

где

(7.10)

Ограничения по рейсам (7.4.), равно как и очевидные ограничения (7.2.), при этом сохраняются. Таким образом, задача заключается в минимизации (7.7.) при условиях (7.2.), (7.4.) и (7.9.)

Из (7.7.) и (7.8.) легко усмотреть, что перед нами задача с фиксированными доплатами; ее отличие от рассматривавшихся ранее задач этого рода состоит в том, что здесь фиксированные доплаты входят не только в целевую функцию, но и в ограничения (7.9.). Однако и этот вариант задачи можно свести к целочисленная задача линейного программирования.

Задача о выборе средств доставки грузов.

Пусть грузовой флот имеет в своем составе суда типов. Количество судов типа равно , а затраты при использовании одного судна типа в планируемом периоде составляют . Каждое судно обладает грузовыми емкостями типов (трюмы, танки, палубы и тому подобное); грузоподъемность емкости на судне типа равна . Подлежат перевозке видов грузов. Груз вида имеется в количестве . Требуется выбрать наиболее экономичный комплекс средств доставки этих грузов, совместимый с грузовыми возможностями судов.

Учитывая неделимость транспортных единиц, введем целочисленные переменные , которые обозначают количество судов типа , выделяемое для перевозки. Кроме того, введем переменные , которые обозначают количество грузов вида , подлежащее загрузке в емкость . Тогда мы придем к задаче минимизации

(7.11)

при условиях

(7.12)

- целое;

(7.13)

(7.14)

Здесь ограничения (7.13.) показывают, что общее количество груза, загружаемое в емкости каждого типа, не должно превышать суммарной грузоподъемности этих емкостей по всем судам, а ограничения (7.14.) говорят о том, что перевозки по всем грузам должны быть полностью осуществлены. Отметим, что на переменные требование целочисленности, вообще говоря, не накладывается, так что здесь мы имеем дело с частично целочисленной задачей.

Простая модель развозки (Balinski M.L., Quandt R.E., On an integer program for adelivery problem. Operat. Res., 1964. 12, N2, 300-304.).

Пусть некоторая центральная база снабжает продукцией (ее можно считать однородной) m складов. Развозка продукции на склады осуществляется одним грузовиком, причем каждый склад получает свой заказ полностью в один прием –грузоподъемность грузовика для этого достаточна. Вообще же грузовик может одновременно взять груз, соответствующий не более чем заказам. Грузовик может объезжать склады по определенным r маршрутам. Разумеется, один и тот же склад может находиться на разных маршрутах.

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

Под способом развозки будем понимать любую допустимую комбинацию выполнения заказов. Говоря точнее, способ развозки представляет собой -мерный столбец, -я компонента которого равна единицы, если -й заказ в этом способе удовлетворяется, и равна нулю в противном случае. Для любой реальной задачи при небольших значениях можно фактически выписать все такие способы развозки. Число этих способов будет зависеть не только от этих параметров, но и, например, от числа складов на каждом маршруте, объема заказов и так далее. Кроме того, каждому способу развозки легко сопоставить связанные с ним затраты (учитывающие, помимо упомянутых выше затрат по доставке, также стоимость работ по выгрузке и тому подобное).

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

Введем переменные

(7.15)

Теперь мы естественным образом получаем задачу минимизации суммарных затратт

(7.16.)

при условиях (7.15.) и

(717)

Условия (7.17.) означают, что все заказы должны быть удовлетворены.

Обращаем внимание на то, что модель (7.15.)-(7.17.) физически совпадает со взвешанной задачей о покрытии.

Задача размещения и специализации

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

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

Модели реконструкции.

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

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

Введем переменные

(7.18)

Тогда наша задача сведется к минимизации

(7.19)

при условиях

(7.20)

(7.21)

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

Связь модели (7.18.)-(7.21.) с задачами размещения является довольно прозрачной. Действительно, можно считать, что некоторые (или все) предприятия являются не действующими, а лишь проектируемыми, причем для каждого из них возможно осуществление не более одного способа строительства (то есть некоторые предприятия могут вообще не строиться). Тогда для индексов , отвечающих проектируемым предприятиям, можно заменить условия (7.21.) неравенствами

(7.27)

.

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

Описанная модель является достаточно общей; однако она не учитывает потребителей продукции и не отражает затрат на транспортировку продукции от поставщиков к потребителям. Этот момент является наиболее существенным.

Задача логического проектирования

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

Задача о расположении производственных единиц.

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

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

Нашей целью является назначение (закрепление) центров по местам, минимизирующее суммарные затраты. Каждое такое назначение представляет собой перестановку чисел ; при этом любое из проводимых закреплений центра за местом описывается соответствием . Для любого назначения мы имеем, во-первых, затраты на взаимосвязь между парами центров; мы будем предполагать, что эти затраты при помещении центра в место и центра в место равны произведению величины потока между и на расстояние между и , проходимое этим потоком, то есть составляют . Таким образом, требуется найти перестановку чисел , минимизирующую суммарные затраты

(7.23)

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

(7.24)

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

Модель (7.23.)-(7.24.) имеет весьма широкие практические приложения, отражая существенные черты многих современных задач проектирования. Так, она может быть использована в вопросах планирования расстановки оборудования в целях машиностроительных или химических предприятий. С другой стороны, она же может найти применение для задач о проектировании расположения деталей в ячейках вычислительных и управляющих устройств (например, при нахождении схем монтажа платы, минимизирующих суммарную длину соединений). Здесь эта модель описана в нарочито общих терминах в надежде, что различные более конкретные интерпретации читатель этой лекции найдет сам.