 |
 |
 |
 |
|
 |
 |
78
где D — множество перестановок чисел от 1 до n.
Отдельно следует остановиться на том, что задача коммивояжера имеет большое количество
содержательных аналогов. Скажем, к аналогичной модели приведет задача разработки графика
переналадки оборудования, которое может выпускать разные типы изделий, но требует определенных
затрат (временных или материальных) при переходе с одного технологического режима на другой.
4.1.4. Задачи с разрывными целевыми функциями. Как уже упоминалось выше, многие
экономические системы характеризуются наличием так называемых постоянных затрат, которые
должны быть произведены независимо от объема производства. Учет в моделях этих и подобных
факторов приводит к появлению в них целевых функций, не обладающих свойством непрерывности. В
качестве примера может быть приведена транспортная задача с фиксированными доплатами. Она
отличается от транспортной задачи в матричной постановке, рассмотренной в главе 3, тем, что в ней
затраты по перевозке груза из i-го пункта производства в j-й пункт потребления определяются как
где с
i,j
— по-прежнему издержки на перевозку единицы груза;
d
i,j
— фиксированная доплата за аренду транспортных средств.
При таких предпосылках целевая функция суммарных затрат на перевозку
содержит «скачкообразные» разрывы, что существенно затрудняет ее минимизацию, поэтому
стандартный метод решения основан на следующем преобразовании. Если ввести вспомогательные
переменные у
i,j
, такие, что
то целевая функция примет вид
Действительно, если у
i,j
=0 , то переменные х
i,j
=0, а при у
i,j
=1 неравенства (4.15) становятся
несущественными, поскольку они и так справедливы для любого опорного плана. Следовательно,
задача (4.16) эквивалентна исходной задаче (4.13). В силу характера ограничений (4.14)-(4.15) задача
(4.16) является задачей частично-целочисленного программирования.
Перечисленные примеры далеко не исчерпывают всего многообразия задач дискретного
программирования. Однако более подробное их рассмотрение требует привлечения достаточно
сложного математического аппарата и выходит за рамки данной книги.
В последующих параграфах мы остановимся на способах решения наиболее известных и хорошо
изученных дискретных задач. Излагаемые ниже методы не имеют универсального характера, с каждым
из них связаны определенные ограничения и, соответственно, ответ на вопрос о выборе того или иного
из них зависит от конкретных особенностей решаемой задачи. Более того, цель изложения состоит в
том, чтобы создать у читателя общие представления об основных идеях и подходах, не углубляясь