Все предложенные в монографии экономико-математические модели относятся к классу задач дискретного программирования (за исключением модели (4.1) — (4.4)). И, как известно, методы решения такого типа задач математического программирования разработаны наиболее слабо. В этой главе сделана попытка систематизации методов решения задач дискретного программирования в преломлении к предложенным моделям. Что касается модели (4.1) —(4.4), то она представляет собой фактически формулировку общей задачи математического программирования. Рассматривать методы решения этой модели было бы целесообразно, если в нее входили бы конкретные функциональные зависимости. [c.187]
В последующих параграфах мы остановимся на способах решения наиболее известных и хорошо изученных дискретных задач. Излагаемые ниже методы не имеют универсального характера, с каждым из них связаны определенные ограничения и, соответственно, ответ на вопрос о выборе того или иного из них зависит от конкретных особенностей решаемой задачи. Более того, цель изложения состоит в том, чтобы создать у читателя общие представления об основных идеях и подходах, не углубляясь далеко в вычислительные и математические тонкости, которыми буквально изобилуют алгоритмы дискретного программирования. Заметим также, что достаточно эффективный и широко применяемый подход к решению целочисленных задач основан на сведении их к задачам транспортного типа. Это объясняется тем, что если в условиях транспортной задачи значения запасов (а,.) и потребностей ( .) являются целочисленными, то целочисленным будет и оптимальный план. [c.142]
Еще один тип моделей оптимального планирования связан с ситуацией, когда некоторые или все переменные Xj могут принимать дискретные (в частности, целые) значения. Задачи такого типа решаются методами дискретного или целочисленного программирования. Дискретные (целочисленные) переменные Xj отражают неделимые объекты (например, число рабочих, станков, скважин и т. д.). [c.116]
Решение этой задачи в принципе не так уж сложно — алгоритм дискретного динамического программирования, подробно описанный в 44, приводит к цели с затратой числа операций в общем случае порядка О (Nh 2n). Последовательность точек (6) и объявляется оптимальной траекторией задачи (1) — (5) разумеется, речь идет о приближенно оптимальной траектории, точность зависит от шагов сетки т и А. Если элементарная операция реализована точным решением задачи типа (1) — (5) на малом интервале [t(, tt+1], то мы имеем дело с точной траекторией управляемой системы (2), проходящей через узлы ж/, в моменты tf обычно элементарная операция реализуется не абсолютно точно, и узлы (6), соединенные, например, отрезками прямых, представляют некоторую аппроксимацию решения системы ж=/. Если нас интересует не только оптимальная траектория (6), но и реализующее ее управление и (t), то его можно восстановить по узлам (6) с помощью той же элементарной операции. Следует прежде всего подчеркнуть ту легкость, с которой данный метод справляется со всеми ограничениями на фазовую часть траектории, будь то ограничения на правом конце траектории (х (Т)=Х1) или еще более сложные ограничения типа х (t) G при всех t. В известной монографии [57] отражена история развития методов приближенного решения задач оптимального управления группой ВЦ АН СССР под руководством Н. Н. Моисеева. Работа начиналась с естественной попытки строить минимизирующие последовательности управляющих функций. После первых успехов в решении простейших неклассических задач (это — задачи, содержащие только ограничение типа u U без условий на правом конце траектории в [40] опубликовано решение задачи о максимальной дальности планирования) встретились определенные трудности, связанные с огра- [c.122]
Для того, чтобы выбрать оптимальный (в полном смысле этого слова) проектный вариант новой техники, необходимо использовать модель типа (4.1) — (4.4), в которой были бы известны функциональные взаимозависимости технико-экономических показателей. Однако такая модель носит чисто теоретический характер, так как такие функциональные зависимости пока что ни для одного вида техники не существуют. Поэтому в монографии были предложены другие модели, представляющие собой задачи дискретного (булевого) программирования, позволяющие выбрать наилучший из числа разработанных вариантов. Было отмечено, что основными недостатками таких моделей являются два нет гарантии того, что в рассмотрение попал оптимальный вариант недостаточно полное отражение нелинейного характера взаимозависимостей технико-экономических показателей новой техники. [c.181]
Многие специалисты определяют задачи Э. как формализованное описание и прогнозирование экономии, процессов на основе статистич. анализа данных и ограничивают Э. разработкой и применением аналитич. моделей, причём иногда по традиции — лишь аналити-ко-статистич. (регрессионных) моделей. Однако с 30-х гг. наряду с ними возник др. класс моделей — нормативных. Эти модели позволяют не только рассчитывать варианты структуры и динамики экономич. объектов, но и по определ. критерию оценки выбрать наилучший (оптимальный) вариант. Значит, вклад в их разработку был сделан сов. учёным Л. В. Канторовичем — создателем линейного программирования (1939), что дало возможность ему, В. В. Новожилову, А. Л. Лурье (СССР), Т. Купмансу, Дж. Данцигу (США) и др. сформулировать и решить широкий спектр экономич. задач оптим. распределения и использования ресурсов. Дальнейшее развитие методов оптимизации привело к разработке различных типов нормативных моделей (большое влияние здесь оказали работы Дж. Неймана). В зависимости от характера переменных и формы связей между ними модели могут быть линейными и нелинейными, непрерывными и дискретными, детерминированными и стохастическими и т. д. Их особенностями определяется применение соответствующих методов математического программирования, исследования операций, теории игр. В социалистич. странах нормативные модели широко используются при оптимизации нар.-хоз. планирования на всех его уровнях (напр., работы Н. Н. Некрасова и Н. П. Федоренко в области химизации и развития химич. пром-сти в СССР). В капиталистич. странах методы оптимизации применяются в рамках отд. фирм, а также при разработке гос. программ. В СССР и др. социалистич. странах широко изучается внутр. связь нормативных и аналитич. моделей, создаются комплексы моделей, включающие оба эти типа, разрабатываются их научно-теоретич. основы. Тем самым расширяется круг проблем Э. [c.434]
Смотреть страницы где упоминается термин Типы задач дискретного программирования
: [c.168] [c.179] [c.449] [c.529]Смотреть главы в:
Математические исследования операций в экономике -> Типы задач дискретного программирования