ГЛАВА 3. ПРИКЛАДНЫЕ ЗАДАЧИ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ

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

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

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

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

при условиях

Требование целочисленности на переменные здесь не накладывается. Однако мы хотим напомнить (см. § 1 гл. 2), что транспортная задача (1.2) — (1.3) является представителем класса задач, всегда обладающих целочисленными планами при целочисленных исходных данных именно по этой причине мы начинаем с нее наш перечень дискретных задач о перевозках.

Примером собственно дискретной задачи о перевозках является транспортная задача с фиксированными доплатами (см. § 5 гл. 2). Напомним, что в этой задаче требуется при обычных «транспортных» ограничениях (1.3) минимизировать разрывную целевую функцию

где каждая функция имеет вид

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

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

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

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

при условиях

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

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

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

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

Распределительная задача имеет весьма разнообразные приложения. Большое число практических ее интерпретаций читатель может найти в монографии Д. Б. Юдина и Е. Г. Гольштейна [44]. Здесь мы остановимся только на одной из них, уже не связанной с вопросами транспортировки, но имеющей важное значение в вопросах распределения производственной программы.

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

Обозначим через количество деталей типа которое следует обработать на станке Тогда описанная задача распределения программы сведется к модели (1-6)-(1.9).

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

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

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

где

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

где

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

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

В основе аналогичного сведения, описанного в § 5 гл. 2, лежало наличие верхних границ для переменных Здесь эти границы также удастся найти при естественном предположении, что все Действительно, из (1.9) мы имеем для всех

С учетом (1.12) и так что

Таким образом,

Введем теперь вспомогательные переменные

Рассмотрим задачу минимизации

при условиях (1.7), (1.9), (1.15) и

Ее эквивалентность исходной задаче (1.10), (1.7), (1.9), (1.12) устанавливается точно теми же приемами, которые были применены в § 5 гл. 2 для транспортной задачи с фиксированными доплатами.

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

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

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

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

при условиях

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

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

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

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

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

выборе наиболее экономичной комбинации этих способов.

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

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

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

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

Обращаем внимание читателя на то, что модель (1.23) — (1.25) фактически совпадает со взвешенной задачей о покрытии, рассмотренной в § 3 гл. 2.