Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Задачи с разрывными целевыми функциями

Задачи с разрывными целевыми функциями. Как уже упоминалось выше, многие экономические системы характеризуются наличием так называемых постоянных затрат, которые должны быть произведены независимо от объема производства. Учет в моделях этих и подобных факторов приводит к появлению в них целевых функций, не обладающих свойством непрерывности. В качестве примера может быть приведена транспортная задача с фиксированными доплатами. Она отличается от транспортной задачи в матричной постановке, рассмотренной в главе 3, тем, что в ней затраты по перевозке груза из i-го пункта производства в j-й пункт потребления определяются как

где сi,j — по-прежнему издержки на перевозку единицы груза;

di,j — фиксированная доплата за аренду транспортных средств.

При таких предпосылках целевая функция суммарных затрат на перевозку

содержит «скачкообразные» разрывы, что существенно затрудняет ее минимизацию, поэтому стандартный метод решения основан на следующем преобразовании. Если ввести вспомогательные переменные уi,j, такие, что

то целевая функция примет вид

Действительно, если уi,j =0 , то переменные хi,j =0, а при уi,j =1 неравенства (4.15) становятся несущественными, поскольку они и так справедливы для любого опорного плана. Следовательно, задача (4.16) эквивалентна исходной задаче (4.13). В силу характера ограничений (4.14)-(4.15) задача (4.16) является задачей частично-целочисленного программирования.

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

В последующих параграфах мы остановимся на способах решения наиболее известных и хорошо изученных дискретных задач. Излагаемые ниже методы не имеют универсального характера, с каждым из них связаны определенные ограничения и, соответственно, ответ на вопрос о выборе того или иного из них зависит от конкретных особенностей решаемой задачи. Более того, цель изложения состоит в том, чтобы создать у читателя общие представления об основных идеях и подходах, не углубляясь далеко в вычислительные и математические тонкости, которыми буквально изобилуют алгоритмы дискретного программирования. Заметим также, что достаточно эффективный и широко применяемый подход к решению целочисленных задач основан на сведении их к задачам транспортного типа. Это объясняется тем, что если в условиях транспортной задачи значения запасов (аi) и потребностей (bj) являются целочисленными, то целочисленным будет и оптимальный план.