Cтраница 2
К сожалению, описанная в предыдущем параграфе модификация метода Балинского уже не может быть непосредственно перенесена на распределительную задачу с фиксированными доплатами. [16]
Ограничения на характеристики в виде системы неравенств ( 3 - 6) выражаются следующими типами функций РП: аддитивными, мультипликативными ( в частности, квадратичными), с фиксированными доплатами, смешанного типа. [17]
Рассмотрим транспортную задачу с фиксированными доплатами. [18]
Применимость такой модели к транспортной задаче в сетевой постановке обеспечивается преобразованием сети за счет увеличения ее размерности к виду, соответствующему обычной транспортной задаче, содержащей только поставщиков и потребителей. Известно [16], что если фиксированные доплаты для всех направлений одинаковы и оптимальное решение линейной программы, соответствующей задаче, без доплат не имеет нулевых компонент, то решение задачи с фиксированными доплатами будет совпадать с оптимальным решением задачи без доплат. В нашем случае доплаты действительно одинаковы, однако заранее можно утверждать, что решение задачи будет вырождено, так как часть направлений перекачки не участвует при перераспределении потока. [19]
Другой путь создания приближенных методов, напротив, является чисто детерминированным и заключается в разработке эвристических приемов, максимально использующих специфику задачи. Некоторые такие приемы для задач с фиксированными доплатами описываются в гл. [20]
Отметим наконец, что для некоторых частных задач построены приближенные методы, вовсе не использующие случайного поиска, а учитывающие лишь специфику модели. Один такой метод, предназначенный для решения транспортной задачи с фиксированными доплатами ( см. § 5 гл. [21]
Специфика этого класса задач позволяет разработать ряд приемов, приводящих к вполне приемлемым на практике планам. В § 1 эти приемы излагаются применительно к транспортной задаче с фиксированными доплатами. В § 2 указаны возможности их распространения на более общие случаи. [22]
Легко видеть, что этот процесс представляет собой известный метод минимального элемента для нахождения опорного плана транспортной задачи ( см. § 1 гл. Полученный таким образом план и предлагается принять за приближенный план задачи с фиксированными доплатами. [23]
Из задач этого типа наиболее важной и изученной является так называемая транспортная задача с фиксированными доплатами. [24]
Большие успехи достигнуты на втором направлении. Для отдельных классов целочисленных задач ( задачи коммивояжера, задачи размещения, транспортной задачи с фиксированными доплатами и др.) разработаны приближенные методы решения. Накопленный вычислительный опыт позволяет указать размерности задач, при которых разработанные специальные приближенные методы оказываются еще эффективными. [25]
Применимость такой модели к транспортной задаче в сетевой постановке обеспечивается преобразованием сети за счет увеличения ее размерности к виду, соответствующему обычной транспортной задаче, содержащей только поставщиков и потребителей. Известно [16], что если фиксированные доплаты для всех направлений одинаковы и оптимальное решение линейной программы, соответствующей задаче, без доплат не имеет нулевых компонент, то решение задачи с фиксированными доплатами будет совпадать с оптимальным решением задачи без доплат. В нашем случае доплаты действительно одинаковы, однако заранее можно утверждать, что решение задачи будет вырождено, так как часть направлений перекачки не участвует при перераспределении потока. [26]
Задача (2.6) - (2.7) включена в наш перечень дискретных моделей по чисто формальным причинам, которые были подробно объяснены в § 1 гл. Однако некоторые дальнейшие обобщения этой схемы уже приводят к дискретным задачам в собственном смысле слова. Одним из наиболее непосредственных обобщений такого рода является описывавшаяся ранее транспортная задача с фиксированными доплатами ( см. § 5 гл. [27]