Метод динамического программирования для ЗНП с мультипликативной целевой функцией - Метод динамического программирования для решения задач

Пусть имеется оптимизационная задача вида:

(1) (2)

(3) - задан(4)

Здесь предполагается, что FJ(xJ,yJ)>0 для всех допустимых значений xJ,yJ. В этом случае для решения задачи (1)-(4) рекуррентные соотношения Беллмана имеют вид:

(5)

, (6)

При j=1 величина y1 задана, поэтому в этом случае решается только одна задача максимизации.

В результате решения оптимизационных задач в соответствии (5) и (6) получим условные точки максимума и функции, . Далее, делая обратный ход алгоритма, находим окончательное решение задачи и.

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

Пусть конструируется электронный прибор, состоящий из трех основных компонентов. Все компоненты соединены последовательно, поэтому выход из строя одной из них приводит к отказу всего прибора. Надежность (вероятность безотказной работы) прибора можно повысить путем дублирования каждого компонента. Конструкция прибора позволяет использовать запасных блоков для каждого j-того компонента, т. е. каждый компонент может содержать до блоков, соединенных параллельно. Общая стоимость прибора не должна превышать С долларов. Если j-тый компонент имеет штук соединенных параллельно блоков, то его надежность составляет и стоимость. Требуется определить количество блоков в каждом j-том компоненте, при котором надежность прибора максимальна, а стоимость прибора не превышает заданной величины С.

Построение ММ. По определению, надежность F прибора, состоящего из N последовательно соединенных компонентов, каждый из которых включает параллельно соединенных блоков, равна произведению надежности компонент. Тогда ММ имеет вид:

(7) (8)

, (9)

Из физического смысла задачи следует, что, >0 для всех допустимых.

Введем дополнительную переменную - количество средств, израсходованных на дублирование компонент 1,2,... j-1.Тогда можно записать:

(10) (11)

Из (10) следует: . Тогда с учетом (9) область допустимых значений будет иметь вид, а рекуррентные соотношения Беллмана принимают вид:

(12).

(13)

Покажем применение рекуррентных соотношений Беллмана для решения задачи (7)-(9), решаемых в порядке. Проводя преобразования, аналогичные преобразованиям задачи о загрузке рюкзака, получим:

Здесь, есть область изменения при фиксированном.

Похожие статьи

• Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач

  Постановка задачи. Пусть имеются N видов грузов с номерами. Единица груза j-го вида имеет все aJ. Если груз j-го вида берется в количестве xJ, то его...

• Изложение теоретических аспектов исследования, Динамическое программирование - Реферативно-прикладное исследование применения экономико-математических методов в решении задач производства (метод нелинейного программирования)

  Динамическое программирование Динамическое программирование -- один из разделов оптимального программирования, в котором процесс принятия решения и...

• Анализ чувствительности оптимального решения ЗЛП к вариациям коэффициентов целевой функции., Графический способ анализа чувствительности оптимального решения к вариациям C[j - Исследование чувствительности оптимального решения задачи линейного программирования к вариациям ее параметров и введению нового ограничения

  Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то...

• Транспортная задача и ее решение методом потенциалов - Решение оптимизационных экономических задач методами линейного программирования

  Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...

• Особенности постановки и решения общей задачи линейного программирования - Определение оптимальной стратегии рыночного поведения с использованием макроэкономических методов и моделей

  Второй раздел курсовой работы посвящен особенностям постановки и решения общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП)....

• Автоматизированное решение транспортной задачи линейного программирования, Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала., С помощью полученных в результате реализации модели отчетов сделать рекомендации филиалу фирмы по расширению программы выпуска ассортимента продукции. - Определение оптимальной стратегии рыночного поведения с использованием макроэкономических методов и моделей

  В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....

• Решение смешанной задачи для уравнения теплопроводности методом конечных разностей

  Решение смешанной задачи для уравнения теплопроводности методом конечных разностей 1. Цель работы Ознакомление с методами решения смешанных задач для...

• Некоторые особенности решения задач нелинейного программирования - Экономико-математические методы

  Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой...

• Теоремы двойственности и их использование в задачах ЛП - Решение оптимизационных экономических задач методами линейного программирования

  Исходная задача: При ограничениях: Двойственной является следующая задача: При ограничениях: Число неизвестных в двойственной задаче равно 2....

• Функции распределения вероятностей для параметров, описываемых обобщенными интервальными оценками - Метод представления знаний в интеллектуальных системах поддержки экспертных решений

  Пусть Dl, r() соответственно левые (правые) границы интервалов I, отвечающих на криволинейной трапеции ОИО значениям 0< < 1. Тогда интересующая нас...

• Нелинейное программирование - Реферативно-прикладное исследование применения экономико-математических методов в решении задач производства (метод нелинейного программирования)

  Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...

• Введение - Решение оптимизационных экономических задач методами линейного программирования

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

• Анализ работы методов - Комплексное исследование численных методов для задачи решения нелинейных уравнений

  Метод дихотомии требует менее всего итераций цикла для получения корней уравнения с заданной точностью. Если расчет ведется без помощи ЭВМ, то это...

• Решение задач ЛП с использованием программы (Simplex), Заключение - Решение оптимизационных экономических задач методами линейного программирования

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

• Введение - Реферативно-прикладное исследование применения экономико-математических методов в решении задач производства (метод нелинейного программирования)

  Большое число экономических и планово-производственных задач связано с распределением каких-либо, как правило, ограниченных ресурсов (сырья, рабочей...

• Практическое применение метода нелинейного программирования при решении конкретной задачи - Реферативно-прикладное исследование применения экономико-математических методов в решении задач производства (метод нелинейного программирования)

  В начале пятилетнего периода работы предприятию выделена сумма в C руб. для приобретения нового оборудования. Стоимость одного комплекта оборудования...

• Геометрический метод решения задач ЛП - Решение оптимизационных экономических задач методами линейного программирования

  Необходимо найти минимальное значение целевой функции F = 4x1+18x2 > min, при системе ограничений: X1+4x2?14(1) X1+6x2?15(2) X1+x2?5(3)...

• Применение теории динамического программирования для КУП "СПЕЦКОММУНТРАНС", Основные понятия и обозначения - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")

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

• Постановка задачи многокритериальной оптимизации - Многокритериальная оптимизация на основе нейросетевой, нечеткой и нейро-нечеткой аппроксимации функции предпочтений лица, принимающего решения

  Пусть - вектор параметров задачи (вектор варьируемых параметров), где - n-мерное арифметическое пространство (пространство параметров). Множеством...

• Введение - Моделирование распределительных процессов на основе динамических задач векторной оптимизации

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

• Решение двойственной задачи симплексным методом (с использованием симплексной таблицы) - Методика решения двойственных задач линейного программирования

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

• Сетевое планирование и управление - Реферативно-прикладное исследование применения экономико-математических методов в решении задач производства (метод нелинейного программирования)

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

• Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы

  Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...

• Примеры экономических задач, приводящихся к задачам ЛП - Решение оптимизационных экономических задач методами линейного программирования

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

• Теория игр - Реферативно-прикладное исследование применения экономико-математических методов в решении задач производства (метод нелинейного программирования)

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

• Постановка задачи, Основные сведения - Комплексное исследование численных методов для задачи решения нелинейных уравнений

  Провести комплексное исследование численных методов для задачи решения нелинейных уравнений. 1. Решить нелинейные уравнения А) ; Б) ; В) . 2....

• Метод решения задачи - Многокритериальная оптимизация на основе нейросетевой, нечеткой и нейро-нечеткой аппроксимации функции предпочтений лица, принимающего решения

  Многокритериальный оптимизация нейронный аппроксимация Общая схема рассматриваемого метода является итерационной и состоит из следующих основных этапов....

• Анализ чувствительности оптимального решения к вариациям правых частей ограничений - Исследование чувствительности оптимального решения задачи линейного программирования к вариациям ее параметров и введению нового ограничения

  Ограничение чувствительность задача программирование Вариации правых частей ограничений приводят к изменению области допустимых решений ЗЛП, в действии...

• Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи

  Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...

• Результаты применения МГА для оптимизации ИП - Возможности генетических алгоритмов для решения задачи многокритериальной оптимизации инвестиционного портфеля

  Все генетические алгоритмы участвовали в двух группах тестов. В каждой группе исследовались различные наборы значений управляющих параметров МГА:...

• Основные методы решения задач, Решение задачи с помощью математического аппарата - Формирование оптимального штата фирмы

  Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....

• Методы решения задач календарного планирования, Точные методы. - Особенности математического моделирования задач, связанных с календарным планированием производственных процессов

  Календарный производственный программирование однооперационный Все существующие методы решения задач календарного планирования3 по степени достижения...

• Порядок составления базисного плана при решении задач симплексным методом - Методы линейного программирования

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

• Общая постановка задачи линейного программирования (ЛП) - Решение оптимизационных экономических задач методами линейного программирования

  Задачей линейного программирования (ЛП) называется задача минимизации или максимизации линейного функционала при линейных ограничениях. В литературе...

• Симплексный метод решения задач ЛП - Решение оптимизационных экономических задач методами линейного программирования

  Вид сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции P1 P2 P3 P4 S1 4 1 1 1 3 S2 18 2 4 6 1 Прибыль от единицы...

• Элементы теории массового обслуживания - Реферативно-прикладное исследование применения экономико-математических методов в решении задач производства (метод нелинейного программирования)

  Системы массового обслуживания -- это такие системы, в которые в случайные моменты времени поступают заявки на обслуживание, при этом поступившие заявки...

• РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера

  Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...

• Инженерные методы решения задач математического моделирования - Математическое моделирование в электромеханике

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

• Применение теории линейного программирования для КУП "СПЕЦКОММУНТРАНС", Модели линейного программирования. Основные определения - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")

  Модели линейного программирования. Основные определения Еще одним классом задач экономико-математического моделирования являются задачи линейного...

• Решение задачи графическим методом - Математическое моделирование в менеджменте и маркетинге

  Необходимо найти максимальное значение целевой функции L(x)= 2x1+2x2 > max, при системе ограничений: 6x1+8x2?48, (1) 8x1+11x2?88, (2)...

Метод динамического программирования для ЗНП с мультипликативной целевой функцией - Метод динамического программирования для решения задач

Предыдущая | Следующая